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:

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:

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:

The support for parameters can be thus implemented as this:

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

The code

The code for this part can be found here. With this version of code one can finally implement Tower of Hanoi in a sensible way (shown here). RETURN statements are also added to the syntax as well, but this version of the language has no way to make use of it since we still can't call procedures in expressions; I reckon it's better to add that alongside with the type system because then we can have a separate void type and use the return type of procedures to decide whether we should add the PUSHA instruction at the end of the call site.


Last update: 2024.3.2