CODEWITHSUNDEEP
schemeinterpreter
Determinant
Determinant

Reputation: 4056

How to implement a Scheme interpreter without recursion?

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.

Upvotes: 2

Views: 920

Answers (2)

Sylwester
Sylwester

Reputation: 48775

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)))

Upvotes: 4

daniel gratzer
daniel gratzer

Reputation: 53901

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

Upvotes: 5

Related Questions