PL/0, Part 3: References


Comments are added using (* and *). Nestings are supported.


We need to add the following instructions:

  • REF l, n pushes the location of variable (l, n) (the same parameters used in LOD and STO) onto the stack.
  • DEREF 0, 0 pops the stack top value, uses the value as an address onto the stack itself, retrieves the value at that address and put that onto the stack.
  • POPR 0, 0 pops the stack top value and stores it at the address specified by the value in the register A.

Thus assigning to a dereferenced lvalue would be:

(instructions for right-hand side)
(instructions for the left-hand side)
POPA 0, 0
POPR 0, 0

We need to change the syntax as well. This was the original syntax:

statement = [ ident ":=" expression | "call" ident 
              | "input" ident | "print" expression 
              | "begin" statement {";" statement}  "end" 
              | "if" condition "then" statement 
              | "while" condition "do" statement ];

condition = "odd" expression |
            expression ("="|"!="|"<"|"<="|">"|">=") expression ;

expression = [ "+"|"-"] term { ("+"|"-") term};

term = factor {("*"|"/") factor};

factor = ident | number | "(" expression ")";

A few points need to be changed:

  • The left-hand side of the assignment statement (the ident in ident ":=" expression) should be changed into:

    statement = [ lvalue ":=" expression | ... | "input" lvalue | ... ]
    lvalue = ident
           | expression "[]" {"[]"} (* <-- the dereference operator *)

    The {"[]"} part is to support nth-indirect references.

  • The definition for factor should be changed into:

    factor = {"valof"} refterm
    refterm = [ "ref" ] ident | number | "(" expression ")" 

The syntax is this way since we can always treat a value as a pointer and deref it but we can only take a ref of certain kinds of things (currently variables only). With this syntax one can technically do pointer arithmetics e.g. (ref a+3 takes the address of a and adds 3) but since we haven't had arrays yet we'll say that it's undefined behaviour for now. We won't check if the operand of valof is a proper pointer (we'll just say dereferring a non-pointer is undefined, since these kind of things work differently according on the backend the program runs on). ref can only goes with variables because that's what we've designed for the VM; and we won't check if the operand of ref is a non-pointer: since we put every intermediate value on the stackf ref-ing things like a literal actually can make sense, and even if we don't put every intermediate value on the stack we can always put the value being ref-ed onto the stack and take that address; of course this would be a ball of mess, but everything would be cleaned up once we put the type system in place.

The source code for this can be found at

A note for future development

I was actually going to implement lambda lifting after this, but it turned out to be quite complicated. Since the reason I want to implement lambda lifting in the first place is to get rid of the "field" parameter of VM instructions, I've decided to remove the ability to have nested procedures instead; this would make the language more like C instead of pascal. But to be honest, I rarely used nested procedures when writing the code in Nim, I suppose removing them to have a language that's way simpler to implement is a tradeoff worthwhile to have. The compiler, of course, is going to be largely changed; I'll post an update when this is done.


Last update: 2024.3.8