let and letrec
This one is for Scheme newbies. How is let different from letrec? As you already know let introduces new bindings and evaluate its body in a new environment enriched by those bindings.
(let ((a 10) (b 20))
(+ a b))
=> 30
let gets evaluated to the value of the last expression in its body. We can also bind procedures using let:
(let ((sqr (lambda (x) (* x x))))
(sqr 10))
=> 100
Is it possible for such a procedure to make recursive calls to itself? Let us check that out:
(let ((fact (lambda (n)
(if (= n 0) 1
(* n (fact (- n 1)))))))
(fact 4))
=> reference to undefined identifier: fact
Our attempt to make fact call itself has failed. Why? The following steps show how the variable fact is bound by let:
- fact is bound to the new, enriched environment.
- The lambda expression is evaluated in the current environment, which do not have a binding for fact and the evaluation fails at the recursive call.
Now we know why the recursive call failed. Only the body of let is evaluated in the enriched enivironment. In contrast letrec evaluates both the binding expressions and the body in the new, enriched environment. Let us rewrite the factorial procedure using a letrec:
(letrec ((fact (lambda (n)
(if (= n 0) 1
(* n (fact (- n 1)))))))
(fact 4))
=> 24
These are the steps followed by letrec for making new bindings:
- fact is bound to the new, enriched environment.
- The lambda expression is evaluated in this enriched environment. and it has no problem looking up the variable fact.
- The body is evaluated in the enriched environment.
We can even bind mutually recursive procedures in letrec:
(letrec ((even? (lambda (n) (if (= n 0) #t (odd? (- n 1)))))
(odd? (lambda (n) (if (= n 0) #f (even? (- n 1))))))
(even? 10) ;; => #t
(odd? 3) ;; => #t
(even? 11))
=> #f
