Reading

These notes.

Homework

Do this Homework.

let, let*, letrec - issues with let

Hopefully you agree that "let" is a usefull little special form. (Why do I say special form? Because it doesn't get evaluated the way functions get evaluted.) But it has it's limiations. Suppose I wanted to compute $\left(\sqrt{\pi} + e/\sqrt{\pi}\right)^3$.

> (let ((x (sqrt 3.14159)) (y (/ 2.7128 x))) (expt (+ x y) 3)) ;-- pukes with error x undefined!

You get an error with this, because you are using variable x inside the let's name/value pair list, and that's not allowed. You really need nested let's: the outer-let defining x and the inner let defining y. I.e. you need this:

> (let ((x (sqrt 3.14159))) (let ((y (/ 2.7128 x))) (expt (+ x y) 3)))

But that's clearly not as nice. So scheme provides us with let*, which is like let except that each successive name/value pair can refer to the earlier names.

> (let* ((x (sqrt 3.14159)) (y (/ 2.7128 x))) (expt (+ x y) 3))

So that's let*. In programming languages circles, we would say that let* is syntactic sugar. It makes code sweeter to write and read, but adds no expressive power. Why do I say "adds no expressive power"? Because (let* ((n1 v1) (n2 v2) ... (nk vk)) exp) is just a synonym for (let ((n1 v1)) (let ((n2 v2)) ( ... (let ((nk vk)) exp))...)). So we have let* to make the language convenient, but we could drop it if we wanted to simplify the language itself without losing expressive power.

There is one way that let and let* are insufficient. Let's see what that is. Suppose I want to map the factorial function accross a list, but I haven't defined a factorial function as a named thing. So I want to define it in place, as we often do with functions we want to map accross lists.

(map <define factorial function here> '(1 2 3 4 5 6))

So what do we do? The problem is that when we define factorial normally we do something like (define (F n) (if (= n 0) 1 (* n (F (- n 1))))). So we have a name "F" that we can use to make the recursive call. However, if I'm using "lambda", there's no name there to use. So, I might get the bright idea to use let, something like this:

(map (let ((F (lambda (n) (if (= n 0) 1 (* n (F (- n 1))))))) F) '(1 2 3 4 5 6))

But no, this doesn't work. And let* doesn't fix it. We need to be allowed to use the name inside the value expression from the name value pair, and neither let nor let* allow that. So, we have another variant: letrec ... that allows exactly this.

> (map (letrec ((F (lambda (n) (if (= n 0) 1 (* n (F (- n 1))))))) F) '(1 2 3 4 5 6))
(1 2 6 24 120 720)

Note that letrec is not obvious syntactic sugar the same way let* is ... we can't rewrite using regular let to get the same effect.

let as mere syntactic sugar

The concept of "syntactic sugar" is important. It let's us talk about features that add power vs. those that merely add conveniece. Funnily enough, let itself is syntactic sugar! We can rewrite any let using lambda. Here's how:

(let ((name val)) exp)  is equivalent to  ((lambda (name) exp) val)

Pretty cool, eh? Let's try it out:

> (let ((x (sqrt 3.14159))) (+ x 1))
2.7724531023414976
> ((lambda (x) (+ x 1)) (sqrt 3.14159))
2.7724531023414976

And that means let* could be rewritten as multiple let expressions, which in turn could be rewritten as multiple lambda's. So neither let nor let* are required, because we could replace them with a bunch of lambda expressions (though it would look pretty ugly!).

letrec as mere syntactic sugar

What about letrec? Can we define a recursive function without letrec (and without 'define', of course!)? That's a much more interesting and intense question! It turns out we can define recursive functions without let/let*/letrec/define! Let's see how to do it for factorial. It'd be the same for any other function.

; Let's start with the usual factorial
(define (F n) (if (= n 0) 1 (* n (F (- n 1)))))
(F 5) ; computes 5! = 120

; Let's imagine we couldn't use the name "F" in the define for F we could add an
; extra parameter "self" with the intention that we call F as (F F 5) so that the "self"
; argument to F is always F itself.  Now the recursive call is to the parameter "self" rather
; than to the name F
(define (F self n) (if (= n 0) 1 (* n (self self (- n 1)))))
(F F 5) ; but we have to call it like this!

; Translating this to "let" rather than define is easy, giving us a let expression defining
; a recursive function ... no letrec required!
(let ((F (lambda (self n) (if (= n 0) 1 (* n (self self (- n 1))))))) (F F 5))
;      \/ \_________________________________________________________/ \_____/
;     name                         value                                exp

; Now, we've already showed that let is just syntactic sugar ... we can accomplish the same
; thing, i.e. binding variables to values, simply with lambda
; The equivalence is just: (let ((name val)) exp) is equivalent to ((lambda (name) exp) val)
((lambda (F) (F F 5)) (lambda (self n) (if (= n 0) 1 (* n (self self (- n 1))))))

; if you're an over-achiever, you wouldn't want to hardcode the expression to only
; compute 5!, you'd want a function that could compute factorial of anything
; that's easy, you say (lambda (x) [the whole thing with 5 replaced by x])
(map
  (lambda (x) ((lambda (F) (F F x)) (lambda (self n) (if (= n 0) 1 (* n (self self (- n 1)))))))
  '(1 2 3 4 5 6 7 8 9)
)

Whew! So, we can actually define recursive functions with nothing more than simple lambda. That's pretty cool.

As a last note, let's think about a scheme program. It's a bunch of define's followed by some expression that is the actual run of the program we're interested in. We could chage each of the define's that define functions into define's that define a variable with value given by a lambda (perhaps using letrec for recursive functions). That could be rewritted as a big let* exression, where each define becomes a name/value pair. All the let/let*/letrec expressions could be rewritten using our lambda tricks, and then we have one big expression that is exactly equivalent to our program, but without defines/let/let*./letrec.

what does a programming language really need? lambda calculus

The preceeding discussion might prompt you to ask the question: what's the smallest language that suffices to "do everything"? One thing we've learned is that let/let*/letrec/define aren't needed in scheme. We can rewrite any program that uses them as an equivalent program that does not use them. All we need is lambda. What about lists? What about numbers? What's really the minimum that we need? In the 1930s, the mathematician Alonzo Church introduced a simple language for expressing computation called the lambda calculus. Basically the only operations it provides are creating functions with lambda and applying functions. Nothing else. No integers. No booleans. No lists. Ultimately it was proven to be computationally equivalent to Turing Machines, which gave rise to the Church-Turing Thesis (which you doubtless remember from Theory of Computing! ... right?). While we won't go into the lambda calculus, it is interesting to ask how one might represent something as basic as numbers. One way is based on the idea of funcation composition. If $f$ is a unary function, let $f^{(n)}$ denote $f$ composed with itself $n$ times. We will represent the number $k$ by the function that maps an argument function $f$ to $f^{(k)}$. In other words:

0 : (lambda (f) (lambda (x) x))	
1 : (lambda (f) (lambda (x) (f x)))	
2 : (lambda (f) (lambda (x) (f (f x))))	
3 : (lambda (f) (lambda (x) (f (f (f x)))))
 ...

Believe it or not, with this representation, we can write programs that do arithmetic! Even more, we can simulate a Turing Machine! This means that it suffices to have lambda and function application ... everything else is syntactic sugar. In fact, if we add in the idea of currying functions from Scheme Activity 4, we see that we only need lambdas of one variable --- after all, multi-parameter lambdas can be written in terms of lambdas with one parameter using currying. [Recall, for example, that (lambda (x y) (+ x y)) can be written as (lambda (x) (lambda (y) (+ x y))) with the caveat that instead of calling as (f 2 5) you would call as ((f 2) 5).

Currying and multi-parameter functions as syntactic sugar

Lambda calculas only allows for functions with a single parameter, so can it be true that multi-parameter functions are also mere syntactic sugar? Yes, using curried functions. It's easiest to see with an example of how addition could be expressed as a function of one variable:

> (define add (lambda (x) (lambda (y) (+ x y))))
> ((add 3) 5)
8

So add takes an x-value and returns a function a function of y that adds whatever value y has to the x-value. Following this same approach, we can express a function with n parameters as a sequence of n curried functions each taking a single parameter.

> (define add3 (lambda (x) (lambda (y) (lambda (z) (+ x y z)))))
> (((add3 3) 5) 7)
15

Of course the nested parentheses you need to call the function are a pain. But this is Scheme, so what else do you expect?