How to implement a Scheme interpreter without recursion?

2
votes

I tried to design a Scheme interpreter which is non-recursive, using a stack and pointer to walk on the AST and evaluate.

Things are just fine if I only need to tackle with pure procedure calls. However, once macros comes, the irregular syntax makes it hard to write a non-recursive routine. (because of the mixture of different semantics) What's worse, the non-recursive approach seemingly becomes incredibly complex when taking built-in macros (like if, conf let, etc.) into account.

Any good suggestions on implementing a non-recursive interpreter? Or any materials on that? I've googled hard but found nothing.

And, I wonder whether the mainstream Scheme interpreters use this kind of approach. Maybe I can just write in recursion and it won't be blamed.

2
schemeinterpreter
Have to different phases of your interpreter, expand the macros and then eval - Daniel Gratzer
If you only implement syntax-rules then yes, you can sneak by with simple, dumb, pattern expansion. syntax-case supports arbitrary scheme so you'd need to run your interpreter in 2 phases - Daniel Gratzer
Also, either if or cond is a macro. Not both. There needs to be at least 1 form of conditional evaluation. - Daniel Gratzer
@ymfoi let is a macro too. An expression like (let ((foo 42) (bar 10)) (+ foo bar)) expands to ((lambda (foo bar) (+ foo bar)) 42 10). - Chris Jester-Young
They can be both built-in. They cannot both be macros. - Fred Foo

2 Answers

6
votes

In vanilla r5rs scheme, macros are just a DSL for rearranging the AST. They operate on a purely syntactic level and should be separate from the interpreter.

In R6RS or CL or whatever, macros can actually do computations which means they need 2 runs of the interpreter, one to expand macros and one to evaluate the resulting AST.

For example given this code

 (let ((x 5))
   (if (= x 5)
       (display "Woohoo")
       (error)))

You should run a macro expander over it in the first phase leaving the AST

 ((lambda (x)
    (cond
      ((= x 5) (display "Woohoo"))
      (else (error)))) 5)

Doing this should evaluate no code. Merely rearrange the AST. Then when your interpreter runs over it, it shouldn't even have to know that macros exist.

So your final scheme interpreter should look like this

Parse File
   |
   |
   |
Expand All Macros
   |
   |
   |
Optimize/Black Magic
   |
   |
   |
Optional ByteCode compilation or similar IL
   |
   |
Evaluate
   |
   |
Profit
4
votes

Whle researching for my Scheme compiler I have read lots of papers about all sorts of old problems related to compilation. Related to macros and @jozefg's nice illustration of separating actual interpreting and macro espansions that I found was Alexpander, written by Al Petrofsky. He has also written Eval in one define, which is a nice interpreter with syntax-rules.

I have previously written a Lisp1 interpreter that runs on Brainf*ck. It had a stack with alternating cell addresses to set-car! the result and the expression to be evaluated.

Eval is something like this:

(pop_stack register1) ; expression
(while-not-zero register1
   ... do computation
   (pop_stack register2) ; return address
   (open-cons register2) ; opens location
   (set-car register1)   ; sets value 
   (pop_stack register1)) ; next job

It supports standard McCharty LISP1 stuff, including macros (flambda).

A simple expression like (cons 'a 'b) used 6 rounds in the while loop, like this:

  1. (cons 'a 'b)
  2. cons => procedure:cons
  3. (pre-apply procedure:cons 'a 'b)
  4. 'a => a
  5. 'b => b
  6. (apply procedure:cons 'a 'b)

Because of this i could rename every keyword. Eg. this works:

(let ((mylambda lambda))
   (mylambda (x) (cons '1 x)))