PL/0, Part 2: Parameters for procedures

---

Since the first argument of the instructions of the original PL/0 VM is here only to support nested procedures, to eliminate this without losing the support for nested procedures require a way to "un-nest" nested procedures; one would naturally choose to do lambda lifting, which roughly means to lifting the procedures defined in the "inside" to the top-level and converting free variables any those procedures might depend on into parameters on the way; this requies support for procedure parameters which vanilla PL/0 does not have, so we'll have to implement that first. Turns out it requires a bit more effort than I originally anticipated. The plan was as follows:

• First we'll change the parser so that (in this order):
  • It supports call statements with arguments;
  • It supports procedure definition with arguments;
• Then we'll change the compiler so that:
  • It checks if the arity of the call statements matches with the procedure being called.
• Then we'll decide how to pass the arguments on the stack (PL/0 vm does not have registers) and then implement the thing.

The first and second point requires relatively little work but the last point turned out to be (probably) impossible with the original VM. Notice that the original PL/0 VM (which we've been using till now) does not have registers; this means all argument-passing can only be done on stack (even with compilers that do pass arguments with registers, the stack is used when there's too many parameters anyway). Basically we have the two choices:

• Push the arguments onto the stack before creating a new stack frame, i.e. the order of things on the stack would be arguments-stackframe-localvars. In this case arguments can be accessed with the base pointer and negative offsets. Since the base pointer always points to the beginning of the stack frame, an extra teardown step is required to remove the arguments pushed onto the stack for the procedure call.
• Push the arguments onto the stack after creating a new stack frame, i.e. the order of things on the stack would be stackframe-arguments-localvars. In this case there is no teardown step for arguments (one just reset the base pointer when returning) and it's also possible to change the local variable allocating part to accomodate that; but the arguments have to be put onto the stack after the stack frame and the only instruction that can construct a proper, usable stack frame also performs a goto.

From this we can see both options requires something that the original PL/0 VM does not have (and we still haven't touched upon the topic of returning values yet!). For this reason I would like to add the following things to the original VM:

• A register named A.
• Three new instructions: POP, PUSHA and POPA.
  • POP pops a value from the stack and discards it.
  • PUSHA pushes the current value of A onto the stack.
  • POPA pops a value from the stack and assigns it to A.

The support for parameters can be thus implemented as this:

• The stack layout is "arguments-stackframe-localvars".
• The code for putting the arguments onto the stack is executed befor the CAL instruction.
• A number of POP s are inserted after the CAL instruction; the number of POP s would be the same as the number of arguments.

This extension opens up the possibility for supporting returning values as well ; it can be implemented as this:

• Adding a return statement to the language; this statement takes a single expression as its argument.

• When compiling the return statement, the following instructions are generated:

  (code for the expression being returned)
  POPA 0, 0
  OPR 0, 0
  

• The code for the call site is compiled into this:

  (code for arguments)
  CAL (procedure)
  POP 0, 0
  POP 0, 0
  ...  (the same amount of POP as the arguments)
  PUSHA 0, 0