Question: Consider a metacircular evaluator which does not implement the if construct, but only a cond. Louis Reasoner claims that if is unnecessary, since we could evaluate the following procedure using the metacircular evaluator:
(define (if predicate action alternative)
(cond (predicate action)
(else alternative)))
Explain why this does not work. In particular, suppose you use this if procedure to define factorial:
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
The result of evaluating (factorial 3) using the if statement above makes the program running forever, but I have no idea why. Any hint on this will be appreciated! Thanks!
An if expression is a special form, it doesn't follow the same evaluation rules as a normal procedure - hence it can't be implemented by a procedure, it has to use a syntactical transformation (say, using a macro or in your case, changing the underlying interpreter). To see this, look at this simple example:
(if #t 'ok (/ 1 0))
=> 'ok
The division by zero never occurred, because only the 'ok part of the expression got evaluated. Try to evaluate the same expression using your implementation of if - you'll get a division by zero error.
So now you see, an if expression is evaluated differently depending on the value of the condition, only the consequent is executed or only the alternative is executed, but never both. And that's the reason why your factorial example fails - even if the base case is reached, the other branch is also executed, creating an infinite loop.