It’s been a while since I mentioned SICP and this time I’ve got something worth mentioning. We’re on section 4 of the book now, which is writing a Scheme interpreter in Scheme. At the start the idea is just to get the basic syntax down but later on you change the evaluation model for fun and effect.
I’ve been working on exercise 4.5, which involves supported an “extended” syntax for conditional evaluation. It lets you pass the result from a test to a receiving function if the result evaluates to “true”.
(cond ((cons 1 2) => cdr)
(else false))
That evalutes to 2. The standard is not clear if the predicate has to be pure. If I run the following in DrScheme:
(cond ((begin (print "once") (cons 1 2)) (cdr)))
I receive 2 back and see “once” printed once to the screen. But if the interpreter assumes that the test is (a) pure and (b) cheap to compute we can rewrite it like this:
(if (cons 1 2)
(cdr (cons 1 2))
(else false))
Rewriting the side-effecting code in this fashion would print “once” twice. Not good.
The following is more-or-less the way the book presents it to you, with my small changes to evaluate the extended syntax. It rewrites a series of cond expressions into nested if statements, which are evaluated until you find something that’s true or you reach the final else.
;; Assumes pure test predicates for (test => func) syntax because
;; the test is evaluated twice.
(define (expand-clauses clauses)
(if (null? clauses)
'false ; no else clause
(let ((first (car clauses))
(rest (cdr clauses)))
(if (cond-else-clause? first)
(if (null? rest)
(sequence->exp (cond-actions first))
(error "ELSE clause isn't last -- COND->IF" clauses))
(make-if
(cond-predicate first)
(if (cond-extended? first)
(list (cond-extended-actions first) (cond-predicate first))
(sequence->exp (cond-actions first)))
(expand-clauses rest))))))
The alternative is not to rewrite the cond syntax as a series of nested if statements. Instead we evaluate the predicate and pass that pre-evaluated value to the receiving function if it’s true. But damn if that isn’t a really difficult thing to do.
In the end I had to interleave evaluation and application of values, since the evaluator would always attempt to further evaluate any primitive value I gave it. (If I’m missing something really obvious here I’ll kick myself.)
;; Attempt to evaluate test predicate only once so that impure code
;; can be used without affecting program state twice.
(define (eval-cond-extended clauses env)
(if (null? clauses)
'false
(let ((this (car clauses))
(rest (cdr clauses)))
(if (cond-else-clause? this)
(if (null? rest)
(eval (sequence->exp (cond-actions this)) env)
(error "ELSE clause isn't last -- EVAL-COND" clauses))
(let ((testval (eval (cond-predicate this) env)))
(if (true? testval)
(if (cond-extended? this)
(apply (eval (cond-extended-actions this) env) (list testval))
(eval (sequence->exp (cond-actions this)) env))
(eval-cond-extended rest env)))))))
Notice the (apply (eval .. a few lines from the end there? That’s where it gets very ugly because the evaluator doesn’t accept pre-computed values.
The third alternative, and one that I haven’t looked at too closely because it seems fraught with other “interesting” issues, is inserting the computed value back into the environment so that the evaluator can see it.
Basically we would translate to this statement:
(let (result (test))
(if result
(function result)
false))
This avoids the issue of computing something twice and running state-changing code twice but you have to drop variables into the interpreted environment which might already be used. If you go this route you either use some variable naming scheme that you can ensure doesn’t clash or deal with it. And for a toy evaluator, I think that’s too deep for me.
