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

Here Comes Solitude

Last month, I read Clay Shirky’s excellent book, Here Comes Everybody. Shirky’s a smart guy, and I’ve learned something every time I’ve read him. Strongly recommended.

The book’s theme is how the Internet is driving the cost for groups to self-organize to zero, and how that is reshaping our culture. We’re living through it every day, but Shirky looks at it as a big picture.

Video Test 2

Want to make the Internet a better place?

Help me out by watching these two tiny video clips (7 seconds each). Then come back here and post a comment and say whether the video worked for you.

Link to video page

Thanks.

Video Test 1

I want to see if I can embed a Vimeo video into a post.  Got some travel videos…

Pronunciation of “Bruschetta” from Bob Miller on Vimeo.

That didn’t embed. Let’s try embedding it right in WordPress.

Have to upgrade WordPress for that.

If you know of a better way to publish HD video, leave a comment, thanks.

EOT

End Of Trip.

Pics later.  Sleep now.

Milan

We’ve had a lot of fun on this trip and done some wonderful stuff.  However, visiting Milan was not one of them.  First, it’s hot here.  32° C (90° F) and most buildings are hotter inside.

Secondly, the city is on vacation this month.  The city is especially on vacation this weekend, because today, 15.8, is a national holiday, celebrating the assumption of the Virgin.  Last night we walked for an hour looking for an open restaurant.  (We finally found one.)

Nonetheless, the National Museum for Science and Technology Leonardo da Vinci was a good find.  We saw models of many of Leonardo’s inventions and some other exhibits, including a recreation of a circa 1950 steelworks.

A long day ahead

After about three hours’ sleep, we got up at 03:00 (Athens time).  We’re in the Milano Linate airport now.  Hopping to Frankfurt, then direct to Portland.  Couple of hours in Portland, 2.5 hours driving home.  If all goes well, we’ll get home by 16:00 PDT.  About 21 hours.  If all goes well.

Lake Maggiore and Milano

This morning we woke up in Locarno, Switzerland, on the north shore of Lake Maggiore.  We’d planned to hang around Locarno until 1:00, then catch the autostrada to Milan and drop off Mito.  But we’re not so good at following our own plans these days.