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…

Scheme status

I’ve written here before about my efforts to write a Scheme interpreter from scratch.  The last update was in May, but I’m still working on it.  I’ve made 60 git commits since then.  The major thing I’m trying to do is implement macros, but I’m having a hard time of it.  No matter.  When they’re done, I’ll understand macros thoroughly.

A fun way to build a Scheme compiler?

I found this.

An Incremental Approach to Compiler Construction
Abdulaziz Ghuloum

It’s a paper describing an agile approach to building a compiler.  It starts with a tiny “language” that only contains integer constants, and builds a compiler that emits x86 assembly to return integer constants.  Then it incrementally builds that, in “steps of a single working session”, into a compiler for a fully usable Scheme language.

The author is at Indiana University, so I suppose there’s a class to go with it.  I didn’t find the class notes, but I did find a longer tutorial paper.

http://www.cs.indiana.edu/~aghuloum/compilers-tutorial-2006-09-16.pdf

Scheme 9 from Empty Space

While I’ve been off the ‘Net, I’ve been reading a book called Scheme 9 from Empty Space.  It is an annotated source code listing of a complete Scheme interpreter.

This is the best resource I’ve found so far in my quest to implement Scheme myself.

Check it out.

http://www.t3x.org/s9fes/

Scheming, part 7. The Reader.

I haven’t ‘blogged about my Scheme interpreter in ages.  Development stopped from January through March, but I’ve been working on it again.  Here are links to the earlier articles.

• Scheming, part 6
• Scheming, part 5
• Announcing kbscheme
• Scheming, part 3
• Scheming, part 2
• Scheming, part 1
• Not another Scheme interpreter!

The biggest new development  is the reader.  Most developers call them parsers, but Lisp people call them readers.  I have written six readers for Scheme now, and I’ve effectively completed a class in advanced parsing theory.  The current reader works very well, and I do not want to write another.

Scheming, part 6

This morning I added vectors to my Scheme interpreter.  It was surprisingly easy.  It was nearly test-driven development — now that the scheme interpreter has a full unit test harness built in, I got the tests written before I finished the code (though not before I started).

Scheming, part 5

Call/cc works!

That’s the big news.  Lots of little tweaks and cleanup, but call/cc is the big deal.  I’d designed the evaluator to handle call/cc way back when, so it wasn’t a major rewrite.  It was just a matter of figuring out exactly what it had to do.

Announcing kbscheme

I published my scheme interpreter on gitorious.  Now you can follow along.  It needed a name, so I called it kbscheme.  Not a brilliant name but it’ll do.

Here’s the project blurb.

kbscheme

This vanity project is yet another implementation of the Scheme programming language.

Project goals:

• I want to learn Scheme.
• I want to write something in C. I’ve been using higher level languages and my C is rusty.
• I want to write a garbage collector. They’ve always fascinated me, but I’ve never written one.
• I have some research ideas about garbage collection that I want to explore.

Project non-goals:

• a production-quality Scheme interpreter
• full implementation of the language

Check it out, Brandon.

Hint to the git-ignorant (as I was very recently).  Go to the repositories/mainline page and click on the “More info…” links,  Those will show the exact commands needed to copy (clone) the tree onto your local disk.

Actually, I’m still git-ignorant.  Gotta work on that…

Scheming, part 3

GC is hard.  Let’s go shopping.

I’ve been working on my scheme interpreter a lot.  But I don’t have much to show for it.  What I do have, finally, is a working garbage collector (GC).  GC is a real pain to debug.  Every error shows up as a memory corruption bug.

Scheming, part 2

I’ve been working on my Scheme interpreter.  I just got the nonrecursive evaluator working, so it seems like a good time to take stock.