Thursday, February 7, 2013

Scheme in 5000 lines of C part 2: (let ((them (eat 'cake))))

I've spent the last week implementing the Scheme binding constructs let and let* for my little toy Scheme (https://github.com/maxburke/evilscheme). In Scheme, as with Common Lisp, the difference between let and let* is that let* ensures the bindings are evaluated left-to-right whereas for let they are unspecified. So, if you have let*, you should have let. Easy peasy! (If I'm wrong please let me know!)

The binding constructs surprisingly easy to implement. The VM which started out as purely stack-based (ie, (+ 1 1) became PUSH 1, PUSH 1, ADD) now has instructions for loading from, and storing to, basically arbitrary locations on the stack. The compiler now creates a spot for the active local variables and loads from/stores to those stack slots as required. The slots then are recycled as scopes are exited/entered. On my list for future refactoring is merging the opcodes used to load from/store to stack slots with the opcodes used to load from/store to argument slots because it's the same thing now.

The compiler -- so far -- is sort-of-multi-pass. It does a single pass over the source AST and does a rough compilation. After it performs some clean-up passes on the generated bytecode.

One pass removes the nops that are inserted into the bytecode stream as a result of branching. One difficulty I ran into when compiling conditional branches is that in many cases the branch targets weren't yet known, and when they were known it was a lot of messy code to find where the actual branch target was. The workaround I picked was to insert nops as branch targets, and then use these nops as the first instruction of the resulting basic blocks. It sounds kinda convoluted but it was much cleaner and straight forward to implement. This nop-removal pass, well, removes the nops and updates the branch instruction targets accordingly.

Another pass inspects all branch targets and if the instruction is a return, it replaces the branch with a return instruction. This is the only optimization pass. So far.

The last pass promotes all tail calls to use the VM's tailcall opcode. Scheme has a requirement that implementations must be tail recursive and, although I'm not gunning for 100% standards adherence, I wondered how difficult it would be to add. This pass takes calls that could be tail calls (basically any instruction sequence of a call proceeded immediately by a return) and replaces it with a tail call. The VM then ensures that these tail calls are executed in constant space.

I'm going to tackle closures next because it's been something on my want-to-do list for a while. After that I'll probably tackle the garbage collector, alternative lambda syntax (ie, (define (foo a b c)) in addition to (define foo (lambda (a b c)))), interactive REPL + error callbacks instead of just assertions, benchmarking, and proper quasi-quotation. I'm not sure what I'll do with continuations, that part of the spec I may skip entirely because I'm too dumb to understand how call/cc actually works, but some sort of co-routine mechanism will probably end up going in.

Follow on to part 3: Scheme in 5000 lines of C part 3: Testing, random thoughts on closures.
View the source on GitHub: https://github.com/maxburke/evilscheme