Is there a Scheme interpreter that uses Normal-order evaluation?

Question

I've been slowly working my way though the exercises in Structure and Interpretation of Computer Programs. Section 1.1.5 talks about applicative vs. normal-order evaluation, and the topic has come up several times in the text afterward. Since the interpreter uses applicative-order evaluation, it's easy to just insert display debug statements in your code to see exactly how it works. It would help my understanding to be able to do the same thing for normal-order evaluation.

Does anyone know of a Scheme (or Lisp) interpreter that's implemented using normal-order evaluation instead of applicative-order?

Update:

Here's a short example modified from the one given in SICP. I'll define my own add procedure to print out the arguments, and use the square procedure from the book.

(define (add x y)
  (display x)
  (display y)
  (newline)
  (+ x y))

(define (square x) (* x x))

Now if I run the short program (square (add 1 2)) using applicative-order evaluation, the result of (add 1 2) will only be computed once then passed to the square procedure. The operands 12 should be printed once before the final result. We can just run this in an interpreter to verify that this is what happens.

> (square (add 1 2))
12
9

Using normal-order evaluation, though, the single operand (add 1 2) should be copied into the square procedure, which would evaluate as (* (add 1 2) (add 1 2)). The operands 12 should be printed twice before the final result.

I'd like to be able to run this in an interpreter that does normal-order evaluation to verify that this is indeed how it works.

Answer 1

Racket has a lazy language. It's better than just an interpreter, since you can write programs that are made of plain racket modules and lazy ones.

As for debugging using printouts -- you can do that in this lazy language, and you get something similar to unsafe IO in Haskell. This can still be confusing sometimes though. (And if you wanted an interpreter to plug printouts into it, it would also be confusing, because it follows the lazy evaluation...)

Answer 2

Turns out Scheme actually comes with what is essentially a normal-order evaluator already. They're those fabled macros you've probably heard so much about, and we can rewrite the examples of sections 1.1.4--1.1.5 to use macro expansion in lieu of procedure application rather easily:

(define (print . items)
  (for-each display items))

(define-macro (add x y)
  `(begin (print "[ADD " ',x " " ',y "]")
          (+ ,x ,y)))

(define-macro (mul x y)
  `(begin (print "[MUL " ',x " " ',y "]")
          (* ,x ,y)))

(define-macro (square x)
  `(begin (print "[SQUARE " ',x "]")
          (mul ,x ,x)))

(define-macro (sum-of-squares x y)
  `(begin (print "[SUM-OF-SQUARES " ',x " " ',y "]")
          (add (square ,x) (square ,y))))

(define-macro (f a)
  `(begin (print "[F " ',a "]")
          (sum-of-squares (add ,a 1) (mul ,a 2))))

Ignore the PRINTs, their logic is a little beyond where you're at in the text, but they're just a shorthand for lots of DISPLAYs. Actually, you would want to entirely forgo the tracing-by-printing in favor of using the system's macro-expansion function. but this varies with the implementation (e.g. in Ypsilon you would use (macro-expand '(f 5))).

If you load these definitions (with the caveat that DEFINE-MACRO is non-standard, but that shouldn't be a problem in practice since most Schemes provide it), then evaluating (f 5) like the book does will print out (of course I prettied it up a little):

[F 5]
[SUM-OF-SQUARES (add 5 1) (mul 5 2)]
[ADD (square (add 5 1))         (square (mul 5 2))]
     [SQUARE (add 5 1)]
     [MUL (add 5 1) (add 5 1)]
          [ADD 5 1]
                    [ADD 5 1]
                                [SQUARE (mul 5 2)]
                                [MUL (mul 5 2) (mul 5 2)]
                                     [MUL 5 2]
                                               [MUL 5 2]
136

Which is more or less what the book illustrates the process should be.

---

Writing these sorts of macros is basically like writing a normal procedure, except that

• Instead of DEFINE, you use DEFINE-MACRO.
• There is no implicit BEGIN over the body, so you need to supply your own if you have multiple expressions.
• The entire body expression is prefixed with a grave accent.
• All instances of the parameters are prefixed with a comma.

That's Writing Scheme Macros 101.

Now all in all, this is a little silly to spring macros on someone on just the first chapter of SICP. But if you say you're having an inordinate amount of difficulty modifying Racket to do what you want (and then there are those not using Racket at all), then here's an alternative.