In both Scheme and Common Lisp, the
IF conditional is a special form
with a simple evaluation rule:
- Evaluate the predicate.
- If the predicate evaluates to a true value, evaluate and the second argument(the then-clause) and return the result.
- If the predicate evaluates to false, evaluate the third argument, if any, and return the result of evaluation.
If one tries to model
IF as a procedure in terms of the more general
COND conditional, one might end up with something like this:
(define (my-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause)))
This even works fine for simple cases:
(my-if (= 2 3) 0 5) ;; 5 (my-if (= 1 1) 0 5) ;; 0
But there is a very big problem with
MY-IF. Consider the recursive
definition of the nth number in the Fibonacci sequence.
(define (fib n) (if (or (= n 0) (= n 1)) 1 (+ (fib (- n 1)) (fib (- n 2))))) (fib 1) ;; 1 (fib 3) ;; 3 (fib 8) ;; 34
This definition assumes that if
1, the recursion
does not happen and the constant
1 is returned. But if we now
IF with our
(define (fib n) (my-if (or (= n 0) (= n 1)) 1 (+ (fib (- n 1)) (fib (- n 2)))))
MY-IF is a normal procedure, a call to
(fib 1) will can
be reduced as follows using the substitution model:
(fib 1) -> (my-if (or (= 1 0) (= 1 1)) 1 (+ (fib (- 1 1)) (fib (- 1 2)))) -> (my-if true 1 (+ (my-if (or (= 0 0) (= 0 1)) 1 (+ (fib (- 0 1)) (fib (- 0 2)))) (my-if (or (= -1 0) (= -1 1)) 1 (+ (fib (- -1 1)) (fib (- -1 2)))))) -> ...
As we see, this evaluation will never finish under the applicative
order of evaluation where all the arguments to a function will be
evaluated before ever entering the body of the function. So even if
the “predicate” of our
true, the third argument,
else clause, is always evaluated and since that is recursive,
the evaluation never terminates and we might get a recursion-depth
exceeded error from the Scheme interpreter.
This is the reason why some simple special forms like
exist to enable basic constructs in a language.
Disclaimer: This is a note to myself as I solve the SICP exercises.