At this point it's worth looking briefly at what is required to implement something more "serious" without a lot of excessive pain. It's really quite easy:

1. We really want variable length arguments
2. We want primitives that allow us to create and access arrays. Lets call them "array" and "index", and we want to make sure "index" works with "assign" or provide an alternative to get the address of the slot in the array.
3. We'd like local variables.

Why did I make these specific choices?

Variable length argument lists makes it possible to implement a lot of functions in a more user friendly manner. Most importantly, implementing things like a dynamic object system with a minimal number of primitives is far easier if you have a way of turning an array into a list of arguments and the other way around - it allows the implementation of methods like a Ruby like #send

Arrays should be pretty obvious. More flexible would be a Ruby like #pack or #unpack or ways of accessing raw memory. However arrays are sufficient to get most of the advantages, and simple enough to implement very easily without adding more typing etc. We do eventually need to get to typing, but

Local variables should also be pretty obvious. We can emulate them now, by wrapping functions in another function, and have the "real" function have extra arguments, like below, but it's hardly satisfying:

(defun real_func (arg,localvar1,localvar2) ( ... ) )
(defun func (arg) (real_func arg 0 0))

The three points above will therefore be the focus of the next couple of parts.

Adding arrays

Let's deal with the trivial bit first, finally adding something to the runtime library:

Implementing "array"

DO_BEFORE= [:do,
  [:defun, :array, [:size],[:malloc,[:mul,:size,4]]
] 

We're just calling the C-library's "malloc" and multiplying the input by 4 (yes, I'm assuming 32 bit pointers again here, so sue me - certainly this needs to be abstracted out at some point, but by then this code will be unrecognizable). Note that depending on platform and typical array size this can be horribly inefficient for small allocations, but that's for later.

So we can create arrays, but not access them. We could easily enough do this in C, BUT there's one constraint: We want to be able to assign to the array with the "assign" primitive instead of calling a special function to access arrays.

Quick interlude for object purists

Yes, this is not object oriented. Yes, we could hide it, and bootstrap classes and a #send method or similar, and implement everything in terms of that. But why? What we are working on now is for all intents of purposes the "syntax tree" of the language - we'll soon add a parser, and it's easy enough to hide non-object oriented constructs like this then, or make it a special "privileged" set of instructions to facilitate implementation of the runtime "kernel" of the language. You'll see the benefits clearer once we get around to implementing an object system, even though it can be limited to being used in a handful of places easily enough.

Implementing "index"

The syntax will be [:index, array, index value]. Here's the first stab to add to the Compiler class:

  def compile_index scope,arr,index
    source = compile_eval_arg(scope, arr)
    @e.movl(source,:edx)
    source = compile_eval_arg(scope, index)
    @e.save_result(source)
    @e.sall(2,:eax)
    @e.addl(:eax,:edx)
    return [:indirect,:edx]
  end

Notice that this gets quite a bit of x86 specific stuff back in compiler.rb, but we'll worry about that later. The logic is fairly straightforward:

• Evaluate the first argument to get at the address of the array
• Move that address into a temporary register - I picked %edx. The reason we do this is that the compiler doesn't have any register allocation at all yet, and %eax is used for return values regardless.
• Evaluate the second argument.
• Multiply the second argument by four to get the number of bytes for the offset from the start of the array (note that we use "sall" which is a left arithmetic shift - shifts are cheaper than multiplications on most architectures; in the tradition of this series I haven't verified if that makes a difference on x86)
• Add the start address to the offset.
• The result is [:indirect,:edx] - we'll need to add support for the new use of indirect, indicating that %edx does not hold the actual value, but a pointer to it.

We hook this into #compile_exp like this:

   return compile_index(scope,*exp[1..-1]) if (exp[0] == :index)
 

So, lets deal with :indirect. We need to change two places. First and foremost, we need to add the following line to #compile_eval_arg:

  @e.emit(:movl,"(%#{aparam.to_s})",@e.result_value) if atype == :indirect

This takes care of the case when and :index occurs anywhere but as the target of an :assign. It reads the value pointed to.

Then we need to change #compile_assign to store the result in a different way when :indirect is used. Here's a diff of #compile_assign

   def compile_assign scope, left, right
     source = compile_eval_arg(scope, right)
     atype, aparam = get_arg(scope,left)
-    raise "Expected an argument on left hand side of assignment" if atype != :arg
-    @e.save_to_arg(source,aparam)
+    if atype == :indirect
+      @e.emit(:movl,source,"(%#{aparam})")
+    elsif atype == :arg
+      @e.save_to_arg(source,aparam)
+    else
+      raise "Expected an argument on left hand side of assignment"
+    end
     return [:subexpr]
   end

An example:

require 'compiler'
prog = [:do,
  [[:lambda, [:i], [:do,
        [:assign, :i, [:array, 2]],
        [:printf, "i=%p\n",:i],
        [:assign, [:index, :i, 0], 2],
        [:assign, [:index, :i, 1], 42],
        [:printf, "i[0]=%ld, i[1]=%ld\n",[:index,:i,0],[:index,:i,1]]
      ]
    ],10]
]
Compiler.new.compile(prog)

Here's the [:index, :i, 0] expression, with some comments:

    movl    8(%ebp), %eax     ; Move "i" to %eax
    movl    %eax, %edx        ; Save it to %edx
    movl    $0, %eax          ; The 0 from [:index, :i, 0]
    sall    $2, %eax          ; Multiply by 4
    addl    %eax, %edx        ; Add the offset to the address saved in %edx
    movl    $2, (%edx)        ; Copy the value 2 into the address of the beginning of "i"

It's a pretty good example of complete lack of optimization, and both some trivial optimization of the original program as well as peephole optimization of the assembly could reduce it to next to nothing, but it works...

So lets run it:

$ make testarray
ruby testarray.rb >testarray.s
as   -o testarray.o testarray.s
testarray.s: Assembler messages:
testarray.s:97: Warning: unterminated string; newline inserted
cc    -c -o runtime.o runtime.c
gcc -o testarray testarray.o runtime.o
$ ./testarray 
i=0x889a008
i[0]=2, i[1]=42

Get the source

You can download the source here.

It's been a long time, and but I finally have a little bit of time again, and it's time to continue.

At this point the next step is some re-factoring. As it stands the compiler is very tightly tied to x86, and before it gets bigger it's worth starting to redress that. The obvious solution is to start splitting out the code generation into a separate class. First of all I'll add a basic "emitter" - a class that just is responsible for spitting out the assembler instructions. I'll try to make it less x86 specific than what it replaces, but I won't put in a lot of effort to isolate all the x86 code straight away.

Let's walk through some of it:

First we require the emitter (the full source is linked below) and add this to the Compiler constructor:

  def initialize
    @e = Emitter.new
    ...
  end

Then we rip the assembler prolog and epilog out of compile_main, and replace it with this:

    @e.main do
      @main = Function.new([],[])
      compile_exp(Scope.new(self,@main),exp)
    end

The Emitter#main method looks like this:

  def main
    puts ".text"
    export(:main,:function)
    label(:main)
    leal("4(%esp)",:ecx)
    andl(-16,:esp)
    pushl("-4(%ecx)")
    pushl(:ebp)
    movl(:esp,:ebp)
    pushl(:ecx)
    yield
    popl(:ecx)
    popl(:ebp)
    leal("-4(%ecx)",:esp)
    ret()
    emit(".size","main",".-main")
  end

I won't go into this in a lot of detail - it's a rehash of the old prolog and epilog, and then yield back to the compiler. You can read through the full source, but this depends on Emitter#method_missing and a few utility methods to make it more pleasant to write the emitter code without having to use puts all over the place. Gradually pushing the puts's down also makes it far easier to change this emitter to do other things later, such as write to file or do just in time code generation in memory. Here's the guts of it the utility functions - for the rest, see the download:

  def method_missing(sym,*args)
    emit(sym,*args)
  end
  def emit op,*args
    puts "\t#{op}\t"+args.collect{|a|to_operand_value(a)}.join(',')
  end
  def int_value param
    return "$#{param.to_i}"
  end
  def to_operand_value src
    return int_value(src) if src.is_a?(Fixnum)
    return "%#{src.to_s}" if src.is_a?(Symbol)
    return src.to_s
  end

Let's look at some of the other ones. #compile_while:

  def compile_while(scope, cond, body)
    @e.loop do |br|
      var = compile_eval_arg(scope,cond)
      @e.jmp_on_false(br)
      compile_exp(scope,body)
    end
    return [:subexpr]
  end

Nice. While this is not entirely architecture independent - other CPU's might have other constructs that are as suitable for doing loops - it is generic enough that given implementing Emitter#loop and #Emitter#jump_on_false it will work on any CPU, and implementing them should be fairly simple and doable on any CPU. For x86, to be equivalent to the old version, this is the code required:

  def loop
    br = get_local
    l = local
    yield(br)
    jmp(l)
    local(br)
  end
 def jmp_on_false(label,op=:eax)
    testl(op,op)
    je(label)
  end

The #loop method depends on a couple of utility functions that handles allocation of branch labels:

  def label(l)
    puts "#{l.to_s}:"
    l
  end
  def local(l=nil)
    l = get_local if !l
    label(l)
  end
  def get_local
    @seq +=1
    ".L#{@seq-1}"
  end

#local may be a bit "evil" - it has the side effect of outputting the label AND returning it, allocating a local label if none was given on input. Not sure combining all of that is a great idea, but it makes for compact code.

Most of the code in the compiler changes in very similar ways, so I won't go through that much more, but here are a few more examples. #output_functions changes to this:

  def output_functions
    @global_functions.each do |name,func|
      @e.func(name) { compile_exp(Scope.new(self,func),func.body) }
    end
  end

With the appropriate emitter function looking like this:

  def func name
    export(name,:function) if name.to_s[0] != ?.
    label(name)
    pushl(:ebp)
    movl(:esp,:ebp)
    yield
    leave
    ret
    emit(".size",name.to_s, ".-#{name}")
  end

A better example of how this isolates architecture specific changes is #compile_eval_arg:

  def compile_eval_arg scope,arg, call = false
    prefix = call ? "*" : ""
    atype, aparam = get_arg(scope,arg)
    return "$.LC#{aparam}" if atype == :strconst
    return "$#{aparam}" if atype == :int
    return aparam.to_s if atype == :atom
    if atype == :arg
      puts "\tmovl\t#{PTR_SIZE*(aparam+2)}(%ebp),%eax"
    end
    return "#{prefix}%eax"
  end

The new version:

  def compile_eval_arg scope,arg
    atype, aparam = get_arg(scope,arg)
    return aparam if atype == :int
    return @e.addr_value(aparam) if atype == :strconst
    @e.load_address(aparam) if atype == :addr
    @e.load_arg(aparam) if atype == :arg
    return @e.result_value
  end  

There isn't all that much more to say about the emitter. The full updated version is can be found here.

Next time we'll be back to something more directly useful: Support for arrays.

Uh, yeah. So much for posting the next part in a few days. I think I'll stop trying to second guess when I'll next have time (but sine I'm going off to Norway for vacation for a week, it's a safe bet the next part won't show up until later than that).

For those who care (anyone? anyone at all? didn't think so), I've been very busy lately, both with a big new project at work that'll see us relaunching the websites for three large restaurant chains in the UK. The exciting part of it isn't the code - that's pretty straight forward - but the infrastructure we're building, which is giving me a great opportunity to set up a very resilient OpenVz based setup with every single component virtualized.

My spare time has all been taken up by other projects which I might say more about some other time...

Anyone, back to the subject at hand...

What can we do so far?

Each step so far has included minor bits and pieces to test specific features. But it's hard to get an idea for how complete a language is becoming without writing something a little bit more substantial. In this case I've chosen to write a "text-mangler" that will "parse" an s-expression like (Lisp like) syntax and turn it into a Ruby script that will run the compiler with the equivalent program.

It will not be a proper parser, but merely a very simple case of rewriting pieces of text to turn something like this:

(foo "bar" 1 2 3)

into something like this:

[:foo, "bar", 1,2,3]

Simple enough to do, but it'll test quite a few things.

Preliminaries

First of all I'll separate the compiler from the "driver" - the little snippet of code containing the actual program, and instantiating and running the compiler. Essentially the entire Compiler class gets moved into a separate file. Here's a really stripped down starting point that illustrates how to use it, and how we'll start producing the "parser":

require 'compiler'
prog = [:do,
  [:puts, "require 'compiler'\\n"],
  [:puts, "prog = [:puts,'Program goes here']"],
  [:puts, ""],
  [:puts, "Compiler.new.compile(prog)"]
]
Compiler.new.compile(prog)

Notice that the program included here reproduces another program with the same structure. If run, it'll output another driver program containing a basic program itself.

Our goal is to expand on this program so that it will read a Lisp like program and output something almost exactly like above. The program above, in fact, should be exactly what we'd expect to get if "parsing"

   (puts "Program goes here")

The rules

What exactly will we "parse"?

We'll turn

• [ ... ] into ( .... )
• foo into :foo
• 123 into 123
• a, b into :a :b
• "foo" into "foo"

There are lots of copouts here:

• We won't tokenize properly, so lots of invalid input will create even more broken output
• It won't handle escaped double quotes at all.
• No error checking.
• Did I mention no error checking?

This is throwaway code - I'm not intending to write a Lisp compiler - so I'm even less inclined than usual to spend time writing something robust. Consider this a test of the capabilities of the compiler so far, and a way of planning out what to add next. Nothing more.

So lets write the damn thing

First of all: This is an exercise in bootstrapping. First we write the "parser" in our current syntax. Then we'll manually translate it into the lisp like syntax it translate. Then we'll finally use itself to regenerate it's own Ruby syntax. This roundtrip will also serve as a test:

• Make it parse itself to generate Ruby.
• Run the Ruby to generate assembler.
• Assemble the parser.
• Run the result on itself again.
• Compare the Ruby code generated in the first iteration with the one generated in the second. If they're not identical something is broken.

This is an IMPORTANT series of steps to keep in mind. Whenever you bootstrap a compiler for a new language or a part of one in the language it compiles so it can process it's own source, you want to make VERY sure that each step can process the next version of itself correctly, and that you archive every single version, since it's very easy to get yourself into a situation where you suddenly have a lot of uncompilable broken code when iterating the syntax and semantics of a new language.

First we spit out a driver as described above:

require 'compiler'
prog = [:do,
  [:defun, :parse, [:c,:sep], [] ],
  [:puts, "require 'compiler'\\n"],
  [:puts, "prog = [:do,"],
  [:parse, 0,0],
  [:puts, "]\\n"],
  [:puts, "Compiler.new.compile(prog)"]
]
Compiler.new.compile(prog)

The code above defines a "parse" function for future use. It then outputs a prolog, calls the parse function, and outputs a tiny epilog, just like the first part of writing the compiler itself. Next we need to start filling in the parse function:

 [:defun, :parse, [:c,:sep],
    [:while, [:and, [:ne, [:assign, :c, [:getchar]], -1], [:ne, :c, 41]], [:do,
         ...
    ]]
 ]

Hard to read? What about if I rewrite it like this:

defun parse c,sep
  while (c=getchar) != -1 and c != 41
    ...
  end
end

Character 41 (decimal) is incidentally right paranthesis. It's a shortcut to make it trivial to use this function recursively to parse expressions.

So "c" is obviously the current character. What about "sep"? Sep will be use later to indicate whether or not to output "," to separate sub-expressions.

So why are they passed as arguments? Well, there's the first reminder for this step: We lack local variables. They'll be added shortly.

Next piece. Inside the while loop we add this:

     [:if, [:eq,:c, 40], [:do,
            [:printf, "["],
            [:parse,0,0],
            [:printf, "]"],
            [:assign, :sep, 1]
          ], ... (else bit goes here)
     ]

In other words: If we see a '(' (ASCII 40), we output '[', call parse() recursively, output ']' and indicate that a comma separator is needed on the next sub expression.

Then:

      [:if, [:eq, :c, 34], [:do,
              [:putchar,34],
              [:parse_quoted,0],
              [:putchar,34],
              [:assign, :sep, 1]
            ], (... else goes here)

If we see a double quote (ASCII 34), output double-quotes, call a new function "parse_quoted" to deal with it, output double-quotes again, and indicate we need a separator.

And here's the last chunk of "parse":

           [:do,
              [:if, [:and, [:isspace, :c], :sep], [:do,
                  [:printf, ","],
                  [:assign, :sep, 0]
                ]
              ],
              [:if, [:and, [:isalnum, :c], [:not, :sep]], [:do,
                    [:assign, :sep, 1],
                    [:if, [:not, [:isdigit, :c]],[:printf,":"]]                 
                ]
              ],
              [:putchar, :c]
            ]

If "c" is whitespace (calling isspace() from the c library) and "sep" is not 0, we output the separator, and clear the flag. Note that this relies on Ruby ignoring trailing "," in array declarations, so [1,2,3,] works the same way as [1,2,3].

Then, if "c" is alphanumeric (isalnum(c)) and "sep" isn't set, we'll indicate we need a separator and specifically if it's not a digit we'll assume it needs to be turned into a Ruby symbol and output ':', then we'll finally output the character. The reason we check to see that "sep" isn't set is to avoid outputing ":" in front of every letter.

That leaves parse_quotes, which looks like this:

  [:defun, :parse_quoted, [:c],
    [:while, [:and, [:ne, [:assign, :c, [:getchar]], -1], [:ne, :c, 34]], [:do,
        [:putchar, :c]
      ]
    ]
  ],

or:

defun parse_quoted c
  while (c=getchar) != -1 and (c != 34)
      putchar c
  end
end

Put it all together, and this is the result:

require 'compiler'
prog = [:do,
  [:defun, :parse_quoted, [:c],
    [:while, [:and, [:ne, [:assign, :c, [:getchar]], -1], [:ne, :c, 34]], [:do,
        [:putchar, :c]
      ]
    ]
  ],
  [:defun, :parse, [:c,:sep],
    [:while, [:and, [:ne, [:assign, :c, [:getchar]], -1], [:ne, :c, 41]], [:do,
        [:if, [:eq,:c, 40], [:do,
            [:printf, "["],
            [:parse,0,0],
            [:printf, "]"],
            [:assign, :sep, 1]
          ],
          [:if, [:eq, :c, 34], [:do,
              [:putchar,34],
              [:parse_quoted,0],
              [:putchar,34],
              [:assign, :sep, 1]
            ],
            [:do,
              [:if, [:and, [:isspace, :c], :sep], [:do,
                  [:printf, ","],
                  [:assign, :sep, 0]
                ]
              ],
              [:if, [:and, [:isalnum, :c], [:not, :sep]], [:do,
                    [:assign, :sep, 1],
                    [:if, [:not, [:isdigit, :c]],[:printf,":"]]
                ]
              ],
              [:putchar, :c]
            ]
          ]
        ]
      ]
    ]
  ],
  [:puts, "require 'compiler'\\n"],
  [:puts, "prog = [:do,"],
  [:parse, 0,0],
  [:puts, "]\\n"],
  [:puts, "Compiler.new.compile(prog)"]
]
Compiler.new.compile(prog)

Completely unreadable and a nightmare to debug. So lets translate it into our Lisp like syntax and see if it can process itself. Some regexps and manual massage later:

(do
 (defun parse_quoted (c)
   (while (and
           (ne (assign c (getchar)) -1)
           (ne c 34))
     (do (putchar c))
     )
   )
 (defun parse (c sep)
   (while (and
           (ne (assign c (getchar)) -1)
           (ne c 41))
     (do
      (if (eq c 40)
          (do
           (printf "[")
           (parse 0 0)
           (printf "]")
           (assign sep 1)
           )
        (if (eq c 34)
            (do
             (putchar 34)
             (parse_quoted 0)
             (putchar 34)
             (assign sep 1)
             )
          (do
           (if (and (isspace c) sep)
               (do
                (printf ",")
                (assign sep 0)
                )
             )
           (if (and (isalnum c) (not sep))
               (do
                (assign sep 1)
                (if (not (isdigit c)) (printf ":"))
                )
             )
           (putchar c)
           )
          )
        )
      )
     )
   )
  (puts "require 'compiler'\\n")
  (puts "prog = [:do,")
  (parse 0 0)
  (puts "]\\n\\n")
  (puts "Compiler.new.compile(prog)")
)

Yikes. More parenthesis than in actual Lisp. I wouldn't call it readable (particularly the lack of an "else" keyword or similar makes it hard to see where an else block begins, but it's an improvement. The real goal was to write a slightly larger test, anyway.

Lets test it by running it on "itself", then compiling the result, and run that on itself, and check that they match:

$ make parser
ruby parser.rb >parser.s
as   -o parser.o parser.s
cc    -c -o runtime.o runtime.c
cc   parser.o runtime.o   -o parser
$ ./parser parser2.rb
$ make parser2
ruby parser2.rb >parser2.s
as   -o parser2.o parser2.s
parser2.s: Assembler messages:
parser2.s:238: Warning: unterminated string; newline inserted
parser2.s:239: Warning: unterminated string; newline inserted
cc   parser2.o runtime.o   -o parser2
$ ./parser2 parser3.rb
$ diff -B parser2.rb parser3.rb
$

Nice.

Next time we'll go back to the compiler and do some refactoring, before adding some functionality (such as local variables) that would make the above example quite a bit cleaner. Once that's done it's time for a real parser for a much nicer syntax.

In the meantime the archive of the files for this round can be found here

UPDATE: Fixed a bug in compile_while

Ok, so I know it's been far too long. Lots going on at the moment... This is a very short part, but I'll try to get the next part cleaned up in the next few days (teaser at the end...)

Implementing 'while' as a primitive

I like small language cores, and it really appeals to me to implement control structures as methods rather than hardcoding them into the language. As we've seen, 'while' can be implemented fairly easily in terms of a quite basic language. We could streamline it even more by reducing the verbiage needed to pass anonymous functions or by adding a Lisp style macro facility.

There's an added complication: Using lambda's that are not proper closures, which is the case for us so far, means there's no way for the body to access external variables. That makes the while loop pretty useless. The "proper" way of fixing that would be to actually implement proper closures, and I promise we'll get there, but not right now - there are other pieces to get in place first.

So I'm biting the bullet and adding a built in "while" construct for now. It also serves the purpose of showing how it's usually done - it's quite simple really.

As usual we start with a simple C test to see how to do this:

int main() {
  while (foo()) {
    bar();
  }
}

gcc -S, and this is the relevant part:

   jmp .L2
.L3:
    call    bar
.L2:
    call    foo
    testl   %eax, %eax
    jne .L3

Notice how the condition is placed at the end, and we start by jumping to the end? The alternative is to place the conditional check at the start, reversing the test and making it jump to after the end of the loop, and then placing an unconditional jump after the body, like the example below, but that results in one extra branch instruction per iteration of the loop:

.L3:
    call    foo
    testl   %eax, %eax
    je .L2
    call    bar
    jmp .L3
.L2:

This is not a big deal since performance isn't a concern right now, but the distinction here doesn't add any complexity to speak of. So here's what we do:

  def compile_while(scope, cond, body)
    start_while_seq = @seq
    cond_seq = @seq + 1
    @seq += 2
    puts "\\tjmp\\t.L#{cond_seq}"
    puts ".L#{start_while_seq}:"
    compile_exp(scope,body)
    puts ".L#{cond_seq}:"
    var = compile_eval_arg(scope,cond)
    puts "\\ttestl\\t#{var}, #{var}"
    puts "\\tjne\\t.L#{start_while_seq}"
    return [:subexpr]
  end

Then we add it to #compile_exp:

   return compile_while(scope,*exp[1..-1]) if (exp[0] == :while)

And a test:

prog = [:do,
  [:call, [:lambda, [:i],
      [:while,
        :i,
        [:do,
          [:printf, "Countdown: %ld\\n", :i],
          [:assign, :i, [:sub, :i, 1]]
        ]
      ]
    ], [10] ]
  ]

Wrapping it up

Like last time, I've tar'ed up the files for step 9 together with a Makefile here. If you have Ruby, make and gcc installed you should be able to just untar it and run make to get the "step9" test binary:

[vidarh@dev step9]$ make
ruby step9.rb >step9.s
as   -o step9.o step9.s
cc    -c -o runtime.o runtime.c
cc   step9.o runtime.o   -o step9
[vidarh@dev step9]$ ./step9 
Countdown: 10
Countdown: 9
Countdown: 8
Countdown: 7
Countdown: 6
Countdown: 5
Countdown: 4
Countdown: 3
Countdown: 2
Countdown: 1
[vidarh@dev step9]$ 

Next time

Next time we'll start putting together and going through a simple "text mangler" that'll let us "parse" a lisp like syntax and generate a Ruby script that runs the compiler on the equivalent program...

It will turn this (not the complete program):

(defun parse () (let (c sep expr) 
  (assign sep 0)
  (assign expr 0)
  (while (and (ne (assign c (getchar)) -1) (ne c 41))
        (if (eq c 40)
          (do (copy_expr) (assign sep 1))
          (if (eq c 59)
                (parse_comment)
                (if (eq c 34) 
                  (do (parse_quoted c) (assign sep 1))
                  (do
                   (if (and (isspace c) sep) (do (printf ",") (assign sep 0)))
                   (if (and (isalnum c) (not sep)) 
                           (do (assign sep 1) (if (not (isdigit c)) (printf ":")))
                         )
                   (putchar c)
                   )
                  )
                )
          )
        )
  ))

into this plus driver code to run the compiler:

[:defun, :parse, [], [:let, [:c, :sep, :expr], 
  [:assign, :sep, 0],                             
  [:assign, :expr, 0],
  [:while, [:and, [:ne, [:assign, :c, [:getchar]], -1], [:ne, :c, 41]],
        [:if, [:eq, :c, 40],
          [:do, [:copy_expr], [:assign, :sep, 1]],
          [:if, [:eq, :c, 59],
                [:parse_comment],
                [:if, [:eq, :c, 34], 
                  [:do, [:parse_quoted, :c], [:assign, :sep, 1]],
                  [:do,
                   [:if, [:and, [:isspace, :c], :sep], [:do, [:printf, ","], [:assign, :sep, 0]]],
                   [:if, [:and, [:isalnum, :c], [:not, :sep]], 
                           [:do, [:assign, :sep, 1], [:if, [:not, [:isdigit, :c]], [:printf, ":"]]],
                         ],
                   [:putchar, :c],
                   ],
                  ],
                ],
          ],
        ],
  ]],

By the end of it it will process itself and spit out the equivalent parse-tree encoded in Ruby. Note how I've put "parse" in quotes etc.. It hardly deserves to be described as a parser - we'll get to a real parser a few steps further out.

Note that I am not going to go down towards writing a Lisp, but I figured since I've used a Lisp like syntax so far for examples, it would be a good test to see whether we're far enough along to do something remotely useful yet. It did need a couple of helper functions beyond what's present so far to get a decent result, but not much. The "real" parser will be for a much more Ruby-ish syntax.

Last time we looked at an improved way of handling loops etc. using anonymous functions. But most of that is relatively limited if there's no way of modifying variables. Sure, you can get away with recursion and not allow mutation or even other side effects at all. It might satisfy some functional programming purists, but it would not satisfy me and it would also require some fairly sophisticated optimizations to get decent performance.

I like the principle of reducing side effects as much as possible, and pushing side effects up, so much so that it's one of the factors I pointed out in my post about reducing coupling through unit tests. But I don't like sacrificing simplicity and/or performance for the sake of a "purer" approach.

So lets introduce assignment, and at the same time add in basic arithmetic and comparisons.

Assignment

We'll cheat and keep what we introduce into the actual compiler as minimal as possible. That means assignments go into the compiler, and arithmetic and comparisons are confined to a new C runtime for simplicity for now. It is temporary, I promise. Just another shortcut.

Why don't we give assignment the same treatment? Well, we could, if we introduced a transparent way of passing the address of a variable as an argument to a function, but it would still mean compiler changes, would be slower and it seems it wouldn't actually bring any benefits.

Another reason for not taking that route is that it opens up a can of worns: If we allow taking the address of stack variables, it gets easy to shoot yourself in the foot by accessing it after the stack frame is dead. We could accept that risk (it's not like this compiler is a bastion of safety at the moment, with mostly no typing and no error checking to speak of), or we can introduce "environments" and guarantee that any variable you take the address of will live on the heap and stay alive until you lose the reference... But that's more complicated than I'd like right now. Environments is one of the approaches to keeping local variables "alive" in the heap that would let us do proper closures instead of mere lowly anonymous functions, though, so we might eventually bite the bullet.

Adding assignment to the compiler is trivial anyway.

Here's the first try:

  def compile_assign scope, left, right 
    source = compile_eval_arg(scope, right) 
    atype, aparam = get_arg(scope,left) 
    raise "Expected a variable on left hand side of assignment" if atype != :arg 
    puts "\tmovl\t#{source},#{PTR_SIZE*(aparam+2)}(%ebp)" 
    return [:subexpr] 
  end 

Notice our first error message... We'll eventually need to bite the bullet and add lots more of those, as well as handling them a bit better than just letting the compiler fail with an exception message and a stack trace, but it's a start.

What this function does is quite straightforward: It compiles the right hand expression, then copies the result into the variable.

Can you spot the problem?

It's not a bug, it's a feature! Right... It only allows assignment to a local variable. Whether that is indeed a bug or a feature is open for discussion - many languages does allow for assignment to function/method arguments as well as local (and sometimes global) arguments. I promise we'll look at this closer later, but for now it's simply not important.

We then update #compile_exp by adding this:

   return compile_assign(scope,*exp[1..-1]) if (exp[0] == :assign) 

And test it with this (the output needs to be linked with the arithmetic functions in the next step, or rather it at least needs :sub):

prog = [:call, [:lambda, [:i],
    [:do,
      [:printf, "Testing sub and assign (before): %ld\\n", :i],
      [:assign, :i, [:sub, :i, 1]],
      [:printf, "Testing sub and assign (after): %ld\\n", :i],
    ]
  ], [10] ]

Arithmetic and comparisons

Here's our new C runtime:

signed int add(signed int a, signed int b)
{
  return a + b;
}
signed int sub(signed int a, signed int b)
{
  return a - b;
}
signed int div(signed int a, signed int b)
{
  return a / b;
}
signed int mul(signed int a, signed int b)
{
  return a * b;
}
signed int ne(signed int a, signed int b)
{
  return a != b;
}
signed int eq(signed int a, signed int b)
{
  return a == b;
}
signed int not(signed int a)
{
  return !a;
}
// Note that our "and" won't shortcircuit, as the
// evaluation happens before this function is called.
signed int and(signed int a, signed int b)
{
  return a && b;
}
signed int gt(signed int a, signed int b)
{
  return a > b;
}
signed int lt(signed int a, signed int b)
{
  return a < b;
}

Not very exciting is it?

I'm not going to try to make it very exciting, but it's worth considering what would be involved in adding compilation of it, though I won't complete that now. Lets look at a single example, "lt", and show the process, though you should be used to it by now. gcc -S on just the "lt" function gives:

lt:
    pushl   %ebp
    movl    %esp, %ebp
    movl    8(%ebp), %eax
    cmpl    12(%ebp), %eax
    setl    %al
    movzbl  %al, %eax
    popl    %ebp
    ret

(Uh-oh, what's that setl / movzbl stuff? This is an optimization - cmpl compares the two operands and set a number of condition codes. "set[something]" sets a value in a single byte register %al based on the condition codes - in this case "l" for less. "movzbl" then takes that byte, extends the value up to 32 bits by filling the remaining bits with 0 and puts it into %eax - don't worry about it)

To add this to the compiler we'd do compile_eval_arg on the left and right arguments. After doing it to the left, we'd need to store the result somewhere temporarily, in case we try to use %eax again. We'd then need to issue the cmpl/setl/movzbl instructions, and we'd be done.

The function could look something like this:

def compile_lt scope,left,right
    l = compile_eval_arg(scope, left)
    puts "\tmovl\t#{l},%ecx"
    r = compile_eval_arg(scope, right)
    puts "\tcmpl\t%ecx, %eax"
    puts "\tsetl\t%al"
    puts "\tmovzbl %al,%eax"
    return [:subexpr] 
end

Note that this is completely untested - I haven't even checked that I got the operands to cmpl in the right order.

More importantly, this illustrates one reason for not jumping into this and spending time on doing the same thing for all of these functions right away: Notice that we needed a temporary register? Notice how that was wasteful, because we could have just put things into %ecx right away? Notice how this is a recipe for a lot of pain, because we might have even more complex situations where it is handy (though not strictly necessary) to have even more temporary registers?

Register allocation is a huge subject in itself. It boils down to figuring out the most efficient way of stuffing a large number of temporary and long lived variables into a very scarce (on the x86 in particular) resource, namely registers. You want to make the most of them, because access to registers is generally far faster than memory accesses, and because many architectures have instructions that requires the use of specific registers for specific purposes.

It gets complicated fast, because while using a register when you can is good, "spilling" - that is the process of storing a variable back to memory and loading another variable it it's place - when you have more variables in use than registers can get even more expensive than accessing things straight from memory in the first place. Figuring out what combination of variables is most efficient to keep in registers or move in and out of registers is something that can make grown men cry, and many simple compilers just ignore this problem and pick a very simple and inefficient approach.

At least reading the wikipedia article linked to above is worthwhile if you want to know more about this, though a few searches should turn up a lot of papers. I don't intend to add any advanced register allocation to this compiler until it's far closer to being functionally complete. But we will need to deal with some of it, but it's something I'd rather defer doing a proper implementation of until more functionality is in place for the simple reason that doing it well is a hell of a lot of work, and doing a half assed job at it will at least make things work, even though performance will suffer.

Wrapping it up

Since there's now a separate file for the C runtime support, I've tar'ed up the files for step8 together with a Makefile here. If you have Ruby, make and gcc installed you should be able to just untar it and run make to get the "step8" test binary:

$ make
ruby step8.rb >step8.s
as   -o step8.o step8.s
cc    -c -o runtime.o runtime.c
cc   step8.o runtime.o   -o step8
$ ./step8 
Testing sub and assign (before): 10
Testing sub and assign (after): 9
$