Functions, abstraction and compiling

More puzzles from my compiler writing experiments – this time figuring out how function calls work. They are so ingrained as part of computer languages – it seems somehow surprising to me that they are quite challenging to implement as bytecode.

Conceptually, functions are primarily a means for humans to break problems down into smaller parts in order to better reason about them – the process of doing this is called abstraction. What is good for human reasoning, is also good for efficient use of finite space in memory – so good functions will be able to be reused in as many places as possible (to be general, in other words).

At the low level, when a function is called we jump to a new location of the code, do some stuff, and then return to where we came from. We also need to deal with arguments passed to the function (giving it different values to work on), and then we need to keep things like the return address and result of the function somewhere safe.

The Jellyfish Virtual Machine is a stack machine – so everything needs to be stored on a single stack we can push and pop values to and from (vectors in this case). Calling a function is a case of:

1. Calculating and pushing the return address to the stack.
2. Calculating and pushing all the arguments onto the stack in order.
3. Jump to the function pointer.

;; return a list of vector instructions to generate 
;; a function call to an existing function pointer
(define (emit-fncall x addr)
  ;; generate instructions to eval and push all the arguments
  (let ((args (emit-expr-list (cdr x))))
     ;; first push the address we want to return to to the stack
     ;; skip the argument pushing code and the following function jump
     ;; we need to tell the linker to fix the address later on:
     (emit (list 'add-abs-loc 'this 1
                 ;; adds absolute location to the offset
                 (vector ldl (+ (length args) 2) 0)))
     args ;; code to push arguments to stack
     (emit (vector jmp addr 0))))) ;; jump to the function pointer

One complexity is that we won’t know the exact address of the function until the compilation process is finished, so we need to tag the relevant instruction to be modified in a second pass later on – this is called linking, which stitches the addresses together properly after compiling.

When we are in the function with the stack set up correctly we need to:

1. Pop all the arguments from the stack and put them somewhere where they can be referred to by name.
2. Do the body of the function.
3. Store the end result on the stack.
4. Jump back to the return address.

When finished, the only thing should be the result of the function call at the top of the stack. The code to generate this is provided by the core “lambda” function (which can be assigned to a name for calling later or called directly – anonymously).

;; lambda - create a function, and return the pointer to it
(define (emit-lambda x)
  (let* ((body
          ;; first we need to get all the arguments out of the
          ;; stack so the function body can refer to them
           (map ;; map over the argument names
            (lambda (arg)
              (make-variable! arg)
              ;; store the value where it can be looked up by the name
              (vector sta (variable-address arg) 0))
            (cadr x))
           ;; now args are stored, do the body
           (emit-expr-list (cddr x))
           ;; swap ret pointer with the result 
           ;; so it's the top of the stack
           (emit (vector swp 0 0))
           ;; jump to the address on the stack
           (emit (vector jms 0 0))))
         ;; make-function! stores the code in a table 
         ;; and returns the address the function will exist at
         (loc (make-function! body)))
      ;; use the linker again to offset 
      ;; from function code section start
      (list 'add-abs-loc 'function-code 1
            (vector ldl loc 0))))))

Building pyramids with code composition

The Al Jazari 2 bots currently have six basic actions – move forward/backwards, turn 90 degrees left or right, pick up the block underneath them or drop the block to the space they are currently sitting on. Given these instructions, how do we procedurally build pyramids (of any given size) like this in their minecraft-esque world?

The Pyramids of Guimar, Canary Islands, Spain
The Pyramids of Guimar, Canary Islands, Spain

1. A pyramid can be built as a series of plateaus layered on top of each other, the plateaus can be built from material mined from nearby:


2. A single plateau can be built as a series of single block wide ridges next to each other, mined from a series of trenches. This is an example ridge/trench of size 3:


3. We need a gap between the ridge and the trench in order to place the plateau in the correct place in the pyramid (also the bots can only climb a single block at a time, otherwise they get stuck).

So in order to build a complete pyramid, we write the code to build a ridge/trench of any size and figure out the steps in-between to get the robot into the right position for the next one. The simplest ridge/trench is a single block long, so lets try writing some code to do that:


The lambda, and bot-sequence etc are scheme code required to get the bot language working, we’re just interested in the contents of the “seq”. After running these instructions we’re in the right place for the next block. Note that the majority of the actions are involved with positioning the bot after doing it’s work. To place the next cube we copy the code and add some more ‘forward’s (as we have to travel a bit further going back and forth):


This is already getting pretty long – we could do with a way to do repetition, so I’ve added a ‘repeat’ form to the language which takes a count, a name bound to the current iteration number (like a ‘for’ loop) and a list of instructions. This is the complete ridge/trench definition for any size, including gaps of any size:


The majority of the code is the maths to get the bot picking up and placing blocks further and further apart including the gap parameter. When collapsed into a function and run we get this:


With the bot ending up in the same place as it started. In order to create a square plateau we call this function, move sideways and repeat, and then move back to where we started again when we’re done:


Going from a plateau function to a pyramid is even shorter, and involves moving inwards diagonally and building smaller plateaus each time. Of course it also mines out a negative pyramid at the same time:


Here is a time lapse of a massive 8×8 pyramid being built, the code ‘compiles’ to 3224 low level instructions:

So this is a kind of programming that encourages solving problems through composition of abstractions – from the low level instructions, simple loops, primitive building constructs, up to complete structures. I’m not sure why in educational languages such as Scratch this is somehow sidelined (interestingly it’s not in Logo, it’s predecessor). Whether this is due to the ubiquity of imperative programming that leads to a focus on manipulation of state, or this kind of programming being considered as too advanced – but for me it’s fundamental, and I’m pretty sure it wouldn’t be that challenging for the kids in the CodeClub I’m running either.