home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / World_Of_Computer_Software-02-387-Vol-3of3.iso / p / pascal-.zip / pascal- / specs / Computer.fw < prev    next >
Text File  |  1993-01-04  |  14KB  |  381 lines
  1. @=~
  2.  
  3. ~A~<A Pascal Computer~>
  4.  
  5. The Pascal computer is an operational definition of the model of
  6. computation underlying Pascal-.
  7. It is an abstract machine with a memory,
  8. a ~/base register~/ capable of addressing that memory,
  9. and a processor.
  10. The processor has an internal stack, and is capable of executing a sequence
  11. of operations that
  12. evaluate expressions,
  13. transmit values between the processor stack and memory,
  14. transmit values to and from an external device,
  15. and control the sequence of execution.
  16.  
  17. Any program written in Pascal- can be expressed, without loss of
  18. information, as a program for the Pascal computer.
  19. This chapter describes the components of the model of computation defined
  20. by the Pascal computer, and shows how its operations are expressed as
  21. symbolic instructions.
  22.  
  23. ~B
  24.  
  25. Variables in Pascal- exist only during an activation of the procedure in
  26. which they are declared.
  27. An ~/activation record~/ is defined for each procedure, and each time that
  28. procedure is invoked storage for a new instance of its activation record is
  29. allocated dynamically.
  30. When the procedure returns, the storage is freed.
  31. Each variable declared in a procedure becomes a field in the activation
  32. record for that procedure, and is accessed relative to the beginning of the
  33. activation record.
  34. Operations that access a variable must therefore specify two pieces of
  35. information: the address of the activation record holding that variable and
  36. the displacement of the variable's storage from the beginning of that
  37. activation record.
  38. The displacement of a variable's storage is known at compile time, because
  39. the compiler maps the variables declared in a procedure into fields in the
  40. activation record for that procedure.
  41. Because the activation records themselves are allocated dynamically,
  42. however, their addresses are not known until the program is executed.
  43.  
  44. The scope rules of Pascal- guarantee that the only variables that can be
  45. accessed directly are those in the currently-executing procedure and any
  46. procedures containing the declaration of the currently-executing procedure.
  47. By convention, the base register of the Pascal- computer always holds the
  48. address of the activation record of the currently-executing procedure.
  49. In addition to the fields representing variables of the procedure, each
  50. activation record has a field called the ~/static chain~/ that represents
  51. the address of the activation record for the procedure in which the
  52. currently-executing procedure was declared.
  53. Therefore the address of any activation record can be found by starting at
  54. the activation record addressed by the base register and following the
  55. static chain a specific number of steps.
  56. The number of steps can be determined by the compiler: if the variable is
  57. local to the current procedure, 0 steps are required; if it is local to the
  58. procedure containing the current procedure's definition, 1 step is
  59. required, and so forth.
  60.  
  61. Three operations are defined to place variable and parameter addresses
  62. onto the processor's stack:
  63.  
  64. ~$~<Variable access~>==~{
  65. Variable:
  66.   "Variable(" $/*Static chain steps*/ "," $/*Displacement*/ ")\n"
  67.  
  68. ValParam:
  69.   "ValParam(" $/*Static chain steps*/ "," $/*Displacement*/ ")\n"
  70.  
  71. VarParam:
  72.   "VarParam(" $/*Static chain steps*/ "," $/*Displacement*/ ")\n"
  73.  
  74. ~<Array element and record field access~>
  75. ~}
  76.  
  77. ~{Variable~} obtains the address of the local activation record from the
  78. base register, follows the static chain the specified number of steps to
  79. find the address of the activation record containing the desired variable,
  80. and adds the specified displacement.
  81. The result, which is the address of the variable, is pushed onto the
  82. processor's stack.
  83.  
  84. Parameters and variables are stored in different parts of the activation
  85. record, and therefore their displacements are interpreted differently.
  86. ~{ValParam~} behaves like ~{Variable~}, except that it interprets the
  87. displacement as a parameter displacement rather than a variable
  88. displacement.
  89.  
  90. The activation record field representing a variable parameter
  91. contains the address of the variable rather than its value.
  92. ~{VarParam~} thus behaves like ~{ValParam~} except that instead of pushing
  93. the sum of the activation record address and the displacement onto the
  94. stack it pushes the contents of the field addressed by that sum.
  95.  
  96. Brinch-Hansen does not provide a distinct ~{ValParam~} operation in his
  97. description of the Pascal computer.
  98. Instead, he fixes the relationship between the parameter and variable
  99. storage areas of the activation record and uses ~{Variable~} to access
  100. both.
  101. This tactic violates a basic rule of modularity: encapsulate design
  102. decisions that may change.
  103. A Pascal computer is an abstraction that must be realized on a variety of
  104. different real machines, and the layout of an activation record is
  105. something that depends strongly on the machine.
  106.  
  107. Addresses of array elements and record fields must be computed in two
  108. steps, because the array or record itself might be a variable parameter.
  109. The first step places the address of the array or record onto the stack,
  110. the second uses the appropriate displacement to compute the address of the
  111. element or field.
  112. (In the case of an indexed reference, the value of the subscript expression
  113. is computed and placed on the stack before the second step.)
  114.  
  115. ~$~<Array element and record field access~>==~{
  116. Index:
  117.   $/*Indexed variable*/
  118.   $/*Index expression*/
  119.   "Index(" $/*Lower*/ "," $/*Upper*/ "," $/*Length*/ "," $/*Line*/ ")\n"
  120.  
  121. Field:
  122.   $/*Record variable*/
  123.   "Field(" $/*Displacement*/ ")\n"
  124. ~}
  125.  
  126. ~{Index~} first removes the address of the array variable and the value of
  127. the subscript expression from the processor's stack.
  128. If the subscript value is not in bounds, ~{Index~} reports an error at the
  129. specified source line.
  130. Otherwise it subtracts the value of the lower bound and multiplies by the
  131. length of an element to obtain the relative address of the element.
  132. This relative address is added to the address of the indexed variable and
  133. the result is pushed onto the processor's stack.
  134.  
  135. ~{Field~} removes the address of the record variable from the processor's
  136. stack, adds the specified displacement, and pushes the result.
  137.  
  138. ~B
  139.  
  140. An expression may be a constant, the value of a variable, or a computation
  141. involving the values of other expressions.
  142. In each case, the process of expression evaluation leads to a value on the
  143. processor's stack.
  144.  
  145. ~$~<Expression evaluation~>==~{
  146. Constant:
  147.   "Constant(" $/*Integer*/ ")\n"
  148.  
  149. Value:
  150.   $/*Variable address*/
  151.   "Value(" $/*Number of memory locations*/ ")\n"
  152.  
  153. ~<Computation~>
  154. ~}
  155.  
  156. ~{Constant~} simply pushes the specified value onto the stack.
  157. ~{Value~} first removes the address of the variable from the stack and then
  158. pushes the specified number of memory locations, starting at that address.
  159.  
  160. There are two kinds of computation in Pascal-, those having one operand and
  161. those having two.
  162. In each case the operation removes the appropriate number of values from
  163. the processor's stack, uses them to compute a single result, and then pushes
  164. that result onto the processor's stack.
  165.  
  166. ~$~<Monadic~>~(~2~)~M==~{
  167. ~1:
  168.   $/*Expression*/
  169.   "~2\n"
  170. ~}
  171.  
  172. ~$~<Dyadic~>~(~2~)~M==~{
  173. ~1:
  174.   $/*Expression*/
  175.   $/*Expression*/
  176.   "~2\n"
  177. ~}
  178.  
  179. ~$~<Computation~>==~{
  180. ~<Dyadic~>~(Lss~,Less~)
  181. ~<Dyadic~>~(Leq~,NotGreater~)
  182. ~<Dyadic~>~(Gtr~,Greater~)
  183. ~<Dyadic~>~(Geq~,NotLess~)
  184. ~<Dyadic~>~(Equ~,Equal~)
  185. ~<Dyadic~>~(Neq~,NotEqual~)
  186. Nop:
  187.   $/*Expression*/
  188.  
  189. ~<Dyadic~>~(Add~,Add~)
  190. ~<Dyadic~>~(Sub~,Subtract~)
  191. ~<Dyadic~>~(Mul~,Multiply~)
  192. ~<Dyadic~>~(Div~,Divide~)
  193. ~<Dyadic~>~(Mod~,Modulo~)
  194. ~<Monadic~>~(Neg~,Minus~)
  195.  
  196. ~<Dyadic~>~(And~,And~)
  197. ~<Dyadic~>~(Or~,Or~)
  198. ~<Monadic~>~(Not~,Not~)
  199. ~}
  200.  
  201. ~B
  202.  
  203. The simplest statements are those that transmit information between the
  204. processor, the memory and the external device.
  205. They consist of single processor operations, whereas control statements
  206. consist of sequences of processor operations.
  207.  
  208. ~$~<Statement execution~>==~{
  209. AssignmentStatement:
  210.   $/*Variable address*/
  211.   $/*Expression value*/
  212.   "Assign(" $/*Length*/ ")\n"
  213.  
  214. ReadStatement:
  215.   $/*Variable address*/
  216.   "Read\n"
  217.  
  218. WriteStatement:
  219.   $/*Expression value*/
  220.   "Write\n"
  221.  
  222. ~<Control statements~>
  223. ~}
  224.  
  225. ~{AssignmentStatement~} stores the contents of a specified number of
  226. elements from the processor stack at a specified location in memory.
  227. Both the elements and the address are removed from the stack.
  228. ~{ReadStatement~} removes the variable address from the processor's stack
  229. and reads a single integer value from the external device
  230. into that address in memory.
  231. ~{WriteStatement~} removes a single integer from the processor's stack
  232. and writes it to the external device.
  233.  
  234. Control statements use results obtained by the processor to control the
  235. execution sequence.
  236. Normally, operations are executed in the order in which they are given.
  237. Two operations, ~{Do~} and ~{Goto~}, are used to alter the normal order.
  238. Each of these operations nominates a specific operation to be executed next.
  239. They do so by giving a name.
  240. Names are associated with operations by the pseudo-operation ~{DefAddr~}.
  241. ~{DefAddr~} associates the specified name with the next operation in the
  242. sequence.
  243. A sequence of ~{DefAddr~} pseudo-operations is allowed; in that case
  244. ~/all~/ of the names are associated with the operation following the
  245. sequence of pseudo-operations.
  246.  
  247. ~{Do~} removes one element from the processor's stack.
  248. If that element's value is 0, then the next operation executed will be the
  249. operation whose name is specified by the ~{Do~} operation.
  250. Otherwise the next operation executed will be the next in sequence.
  251.  
  252. The operation executed after a ~{Goto~} operation will always be the
  253. operation whose name is specified by the ~{Goto~} operation.
  254.  
  255. ~$~<Control statements~>==~{
  256. WhileStatement:
  257.   "DefAddr(L" $1/*Label*/ ")\n"
  258.   $2/*Expression*/
  259.   "Do(L" $4/*Label*/ ")\n"
  260.   $3/*Statement*/
  261.   "Goto(L" $1 ")\n"
  262.   "DefAddr(L" $4/*Label*/ ")\n"
  263.  
  264. OneSided:
  265.   $1/*Expression*/
  266.   "Do(L" $3/*Label*/ ")\n"
  267.   $2/*Statement*/
  268.   "DefAddr(L" $3/*Label*/ ")\n"
  269.  
  270. TwoSided:
  271.   $1/*Expression*/
  272.   "Do(L" $3/*Label*/ ")\n"
  273.   $2/*Statement*/
  274.   "Goto(L" $5 ")\n"
  275.   "DefAddr(L" $3/*Label*/ ")\n"
  276.   $4/*Statement*/
  277.   "DefAddr(L" $5/*Label*/ ")\n"
  278. ~}
  279.  
  280. ~B
  281.  
  282. Each procedure consists of a sequence of operations.
  283. Before executing these operations, a new activation record must be
  284. established for the procedure.
  285. The size of the parameter and variable storage areas in the activation
  286. record, and the amount of storage required by the procedure on the
  287. processor's stack are all known to the compiler.
  288. If the processor's stack does not have enough free storage,
  289. the ~{Procedure~} operation terminates execution of the program
  290. and reports an error at the source program line containing the procedure
  291. definition.
  292.  
  293. In addition to allocating storage for the activation record, the field
  294. representing the static chain must be set to address the activation record
  295. of the procedure in which the new procedure was declared.
  296. This address is not known to the compiler, and must be supplied at run time
  297. by the ~{ProcCall~} operation.
  298. The procedure being called must be visible to the calling procedure,
  299. because Pascal- only allows direct calls (there are no procedure-valued
  300. variables or parameters).
  301. Because the called procedure is visible, the activation record of the
  302. procedure in which the called procedure is defined can be found by stepping
  303. along the static chain, and the compiler can determine the number of steps
  304. required.
  305.  
  306. Before calling a procedure, the caller places the procedure's argument
  307. values onto the processor's stack in order from left to right.
  308. On return, the procedure deletes these values from the processor's stack.
  309.  
  310. ~$~<Procedure activation~>==~{
  311. ProcedureDefinition:
  312.   $6/*Nested procedure definitions*/
  313.   "Procedure(" $1/*Parameter size*/ "," $2/*Local size*/
  314.     "," $3/*Temp size*/ ",L" $4/*Label*/ "," $5/*Line*/ ")\n"
  315.   $7/*Statements*/
  316.   "EndProc(" $1/*Parameter size*/ ")\n"
  317.  
  318. ProcedureStatement:
  319.   $/*Arguments*/
  320.   "ProcCall(" $/*Static chain steps*/ ",L" $/*Label*/ ")\n"
  321.  
  322. ~}
  323.  
  324. Nested procedure definitions are separated in the Pascal- computer code
  325. because the only effect of procedure nesting in Pascal- is to provide
  326. scopes for variables.
  327. Once the variable accesses have been expressed in terms of activation
  328. records, the procedure nesting is redundant.
  329.  
  330. ~B
  331.  
  332. A complete program acts like a procedure called by some external agency.
  333. It needs no name, however, because the operator that begins it is unique
  334. (~{Program~} rather than ~{Procedure~}).
  335. Also, because a program has no arguments, program termination does not
  336. require anything to be removed from the processor's stack.
  337.  
  338. ~$~<Program execution~>==~{
  339. Program:
  340.   "Program(" $/*AR size*/ "," $/*Temp size*/ "," $/*Line*/ ")\n"
  341.    $/*Statements*/
  342.    "EndProg\n"
  343. ~}
  344.  
  345. ~B
  346.  
  347. The fundamental relationship among the operations of the Pascal- computer
  348. is the sequence: one operation following another.
  349. Because execution begins with the program, its operations appear at the
  350. beginning of the program text.
  351.  
  352. In order to facilitate testing of the compiler, the program for the Pascal
  353. computer is considered to be a sequence of C pre-processor macro calls.
  354. Each operation is defined by a C pre-processor macro, and these definitions
  355. are provided by including them in the program text when it is provided to
  356. the C compiler.
  357.  
  358. ~$~<Code syntax~>==~{
  359. Sequence:
  360.   $ $
  361.  
  362. Text:
  363.   "#include \"pascal.h\"\n\n"
  364.   $/*Program text*/
  365.   $/*Procedure bodies*/
  366. ~}
  367.  
  368. ~B~<Specification file for symbolic machine code~>
  369.  
  370. Templates for producing structured output are specified in a type-~{ptg~}
  371. file.
  372.  
  373. ~O~<computer.ptg~>~{
  374. ~<Variable access~>
  375. ~<Expression evaluation~>
  376. ~<Statement execution~>
  377. ~<Procedure activation~>
  378. ~<Program execution~>
  379. ~<Code syntax~>
  380. ~}
  381.