How to Bootstrap a Compiler for a Functional Language

Chapter 3: Hello World

So now that we have some basic functionality established, let's write our first program!

Program Layout

To start let's look at how a program is organized. Aside from some configuration and global symbols, the two main parts of a program are the text and data. The text section is where our code will be stored, it is immutable. The data section is where our data will be stored, it is mutable.

.global main:
.text
main:
   (system-call $1 $1 $hello_world $12) #sys_write
   (system-call $60 $0 $0 $0)     #sys_exit
.data
hello_world:
   .ascii "hello world\n"
   .zero 1

Processing Argv

Next, since the compiler accepts arguments from the command line, we need to do some processing to turn argc/argv into an S-Expression.

   # before_main_argv:
   #    argv = ()
   #    let t = argv
   #    for a in argv:
   #       t.tail = (a ())
   #       t = t.tail

   (pop %rax)            # put argc in %rax
   (mov $argv %r9)
   (movq $0 0\[%r9\])
   (movq $0 8\[%r9\])

before_main_argv:
   (cmp $0 %rax)
   (je before_main_end)

   (pop %r12)            #this = argv[i]
   (mov $0 %r13)
   (close())             #r8 is argv[i]

   (mov %r8 0\[%r9\])    #set t.head = argv[i]
   (mov $0 %r12)
   (mov $0 %r13)
   (close())
   (mov %r8 8\[%r9\])    #set t.tail = ()
   (mov %r8 %r9)         #set t = t.tail

   (dec %rax)            #dec argc
   (jmp before_main_argv)

before_main_end:

Heap Allocation of Atoms

Atoms are placed in a contiguous memory region and tracked with a simple counter.

allocate-atom-data := λ. (
   #calculates where to place next atom data in atom pool
   #the atom pool is a string pool where new atom data can be written
   #r12 holds pointer to head of new data (the pointer to return as an atom)
   #r13 holds pointer to tail of new data (currently the same as head pointer)
   (mov $a_section %r12)
   (mov $a_counter %r13)
   (add 0\[%r13] %r12)
   (mov %r12 %r13)
);
  
progress-atom-data := λ. (
   #update atom pool to protect our new data
   (mov $a_section %r8)
   (mov %r13 %r9)
   (sub %r8 %r9)         # %r8 = tail of new data - atom section = length of atom section
   (mov $a_counter %r8)
   (movq %r9 0\[%r8\])
);

Heap Allocation of Cons Cells

Cons cells are similarly put into a contiguous memory region and tracked with a simple counter.

allocate-heap := λsize. (
   (mov $s_section %r8)
   (mov $s_counter %r9)
   (mov 0\[%r9\] %r10)   # %r10 = s_counter value
   (add %r10 %r8)        # %r8 = pointer to new data
   (add size %r10)       # s_counter += size
   (mov %r10 0\[%r9\])   # store s_counter
);

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.