Scheme and Macro Expansion

I got to work on my Scheme interpreter this weekend.  Real life had interfered for about three weeks straight.

I’m still working on syntax-case, the code transformation workhorse.  I’ve got two separate pieces of Scheme code.  There’s an expander for a subset of Scheme (no macros) that has the framework for α-substitution and is tied into my interpreter.  Then there’s another expander that I wrote in Chicken Scheme which just handles the pattern matching of syntax-case.  That part is debugged and uses the same syntax objects and environments as my Scheme.

Which is kind of useless.  Being written in full Scheme, it won’t run in my Scheme subset.  (My scheme doesn’t have cond, let, etc.)  And it won’t run in Chicken Scheme, because Chicken Scheme uses a different environment format.  But I can use Chicken Scheme to call the pattern match routine with some test input and see whether it finds the pattern variables and binds them correctly.  Which it does, for a small set of tests.

I also puzzled out how syntax-case ties into the macro expander.  Typical use is like this.

(define-syntax my-macro
  (lambda (x)
    (syntax-case x (<literal> ...)
      (<pattern> <output expression>)
      ...)))

Because syntax-case is wrapped in a lambda, it will run when the lambda is called, which is at macro use time.  That’s the right time to bind the pattern variables.  So no extra tricks are needed (I think) to delay its execution.  syntax-case does need to be a special form, so the evaluator doesn’t try to evaluate its arguments before applying it.

So now I’m working on the syntax keyword.  syntax substitutes pattern variables into template expressions, and it expands ellipses.  For example, given this pattern

(my-letrec ((var init) ...) body ...)

and this input form

(my-letrec
  ((a 0) (b #f))
  (display b)
  (display (+ b 3)))

and this syntax template

(syntax ((lambda (var ...) body ...) init ...))

I’m working on generating the right output, which, does to α-substition, is too unreadable to post here.

Actually, I’m not working on it.  I’ve spent the day scanning the literature trying to see how others have done it.  And I haven’t found any actual implementations yet.  So I’m thinking about it…

NAND Gates to Tetris, wrap up.

That was a load of fun.  I finished all the class projects in The Elements of Computing Systems.  The projects got more involved as they got higher-level.

Nand Gates to Tetris, part 2

First, I told all my friends about this textbook.  Last night, I started doing the exercises.  I’ve done about half the course now, including all the hardware sections.  It’s been a lot of fun.  I’ve never designed a CPU before, and it was fun seeing how all the pieces fit together.

The machine the class uses has a weird architecture.  It’s definitely more pedagogical than useful.  For example, there are no shift instructions.  It reminds me of the old bit slice processors — the instruction set is a lot like microcode.

Nand Gates to Tetris

If you haven’t seen this, you should go see it.

From NAND Gates to Tetris in 14 Weeks.

http://www.idc.ac.il/tecs/

It’s an undergraduate class that starts by building simple logic circuits, uses those to build sequential circuits, then registers, CPUs, VMs, compilers, OSes, and applications.  Every project builds on the last one, and at the end, the student has a game (Tetris) every part of which he has constructed himself, down to the NAND gates.  Okay, not really, but he’s been exposed to every level of technology and should have good comprehension of how each layer is implemented.

The whole textbookSelected chapters of the book, the problem sets, the simulator software, and the unit tests are available free at the above URL.

Pretty amazing stuff!