How to Bootstrap a Compiler for a Functional Programming Language

Chapter 4: User Defined Functions

In a previous chapter we decided on a simple calling convention for functions. Here we will extend this calling convention to define arbitrary functions for the user.

What does a first-order function look like?

First-order functions are functions that can be defined without the need for closures. In GNU Assembly a first-order function takes the following format.

function_name:
   (enter-function ())
   (push-arguments args)
   (push-locals body)
   (get-text body)
   (exit-function ())

The first concept to address here is the concept of a stack frame. A stack frame is initialized as follows.

enter-function := λ. (
   (push %rbp)
   (mov %rsp %rbp)
);

The enter-function snippet will push the current base pointer onto the stack to be restored when we leave the function. The current stack pointer is then stored as the base pointer to serve as the location of our stack frame. A stack frame is simply a pointer to our function context where local variables may be stored. Before we exit our function we should remember to clean up our local context by restoring the stack pointer and base pointer.

exit-function := λ. (
   (mov %rbp %rsp)
   (pop %rbp)
   ret
);

How are multiple arguments passed to a function?

Multiple arguments may still be passed to a function in the format of an S-Expression, however they must be destructured into locals before they can be used. Assuming that we only accept S-Expressions as arguments, then each local will be two words.

push-arguments := λargs. match args (
    ( () () )
    ( (more_args (Variable v)) (
       (pushq 0\[%r13\])
       (pushq 8\[%r13\])
       (mov 8\[%r12\] %r13)
       (mov 0\[%r12\] %r12)
       (push-arguments more_args)
    ))
);

Here we expect our arguments to be tail oriented, so (f 1 2 3) must be implemented as f (((() 1) 2) 3) to match our calling convention.

What do higher-order functions look like?

A closure must be implemented with a slightly more complicated calling convention. We will use far calls for closures to permit position independent calling. A closure may be stored as a two-tuple (closure_state closure_function). A call to a closure can then be applied with a calling convention such as apply closure_function closure_state args.

This is an Excerpt from The Bootstrap Book

The Bootstrap Book is released under the terms of the permissive MIT license. If you quote or copy the book, please make a reference. That is all I ask, please.