I stumbled on SICP in my Google searches. I will give it a try tonight.
When going through SICP, it really helps to write and run some code along with the text. Racket is a good environment for that. This explains how to configure Racket to best work with the code in SICP.
Yikes. Looks like SICP relies on Lisp. I don’t think I’m comfortable working with a functional programming language.
Lisp is about as functional as Python is. If you’re comfortable with Python, it’s like five minutes to go from that to Lisp once you start reading SICP, which explicitly teaches you Lisp in the process of teaching you everything else.
The use of parentheses and the weird notation are off-putting.
It’s worth it to get to use SICP. Besides, if you think Lisp looks weird you’re gonna be in for a hell of a shock when you see the kinds of formalisms mathematicians like to use.
Good point–I’m already stymied by the weird formalism of lambda calculus.
Actually, Lisp can help you learn lambda calculus, given that it is (partially) built on it. I’ve always found that a great way to learn is by doing, and with Racket you can learn the lambda calculus by typing lambda calculus expressions and seeing what happens.
Skimming the text, I don’t see that it directly covers lambda calculus. How could I play around with it in Racket?
There is a ‘special form’ (kind of like a function but not really) called ‘lambda’ that acts something like the lambda in lambda calculus does. The big difference is that you can’t curry like you can in Haskell: A Lisp function of two arguments must always be called with two arguments; it won’t turn into a function of one argument if you call it with one argument.
An example (text after the > is what you type yourself):
> ((lambda (x) (+ x 5)) 5)
10
The lambda up there is an anonymous function. (‘Anonymous’ just means ‘without a name’.) It has a single parameter, x, and the body of the function adds 5 to x. The entire expression applies that function to 5, causing the expression (+ 5 5) to be evaluated, resulting in 10, which you can see above.
If you want to explore currying, it’s a little more annoying because you have to do it by hand, like this:
> (((lambda (x) (lambda (y) (+ x y))) 5) 6)
11
You can see that we had to use two lambdas up there; one for the outer function and one for the inner. The outer function binds x to 5 (that is, it makes x another name for the value 5) and returns the inner function, which therefore looks like this:
(lambda (y) (+ 5 y))
I have replaced the x with 5, to show what’s occurred. Now, when we look at the larger expression, we have:
((lambda (y) (+ 5 y)) 6)
So we’re applying a function of one argument, which adds 5 to its argument, to the value 6. This has the predictable result of (+ 5 6), which evaluates to 11.
Anyway, Racket is a good way to explore all of this stuff for yourself.
Let me take a stab at this.
First, let’s dispense with the notational issue. Lambda calculus has a specific notation for functions that’s useful in many respects, but can confuse neophytes. People that write out lambda calculus expressions also seem to have an aversion to parentheses, which can make it harder to understand what’s going on (somewhat ironic, considering the proliferation of parentheses in derivative languages like Lisp). Here’s the basic idea.
We’re all used to functions like:
f(x) = x * 4
i.e., a function that takes one argument (x) and returns x times 4. Lambda calculus syntax expresses this a little differently (using a capital ‘L’ for a lambda):
L x . (x * 4)
Hopefully the correspondence should be obvious: the letter after the ‘L’ is the parameter of the function, and everything inside those parentheses is the function definition (the parentheses are not required, but I’m going to put them in).
Now let’s think about what it means to “call” a function. Suppose I want to compute 4 times 4. Using the definition of “f” from above, I could write “f(4)”. One way to think about calling “f” is that we replace every instance of “x” in the function definition with the function argument:
f(4) = 4 * 4
We can “call” functions in lambda calculus in a similar way, but the notation is a little different: we’ll just put the argument to the function after the function definition:
[L x . (x * 4)] 4
This is normally written without the brackets, but I’m putting them in to (hopefully) help you keep the function and its argument straight.
To compute the result of this function, we do the same replacement that we do in a normal function notation. We will take the function definition and apply it to the argument. This means that we will find every place in the function definition where “x” shows up and replace it with the argument. This is called “beta reduction”:
[L x . (x * 4)] 4
=> 4 * 4
=> 16
Hopefully this all makes sense, so far. But there’s definitely a drawback: lambda calculus only lets you define functions that take one argument. What if you want to define a function that takes two arguments?
f(x, y) = x * y
To figure this out, I’m going to introduce a trick: we’re used to functions where the arguments are “simple” things like integers, and the result we get from evaluating a function is also something simple like an integer. But lambda calculus lets us do more than that. I can have a function that returns another function:
L y . (L x . (x * y))
This looks a little bit weird, but lambda calculus is cool: I can use exactly the same rule for calling a function as I did before. Let’s see what happens when I apply this function to 4. Remember, I’m just going to substitute every instance of “y” with 4:
[L y . (L x . (x * y))] 4
=> L x . (x * 4)
So what I got back is a new function that multiplies its argument by 4 (note that this looks exactly the same as the original multiply-by-four function we had before). What we have here is a function, let’s call it “make-multiply-by-n”, that takes an argument, n, and gives us back a new function that multiplies anything by n.
So what happens if we perform two levels of application?
[[L y . (L x . (x * y))] 4] 5
Well, let’s just walk through it. We’ll do our function applications from the inside out:
[[L y . (L x . (x * y))] 4] 5
=> [L x . (x * 4) 5]
=> 5 * 4
Cool, huh? By applying our special “make-multiply-by-n” function to 4, we created a new “multiply-by-4” function that we applied to 5, to compute 5 * 4.
If we take a step back, we can see what we did: with our special function, we were able to take two arguments (4 and 5) and, by using our application rule twice, compute their product. In essence, we have something that behaves like a function that takes two arguments, even though it was constructed out of two functions that each take just one argument.
That is “currying.”
Edit: and I see that I spent a lot more words to do what Derleth did above (and with almost the same example, too).
Goodish’s law: As an online discussion of lambda currying grows longer, the probability of a link similar to thisapproaches 1.
That’s funny… it always makes me think of this.
I’m getting a 403 error on that link, Derleth.
SICP doesn’t directly discuss the lambda calculus. But it approaches it in a way that really helps you to understand some of its usefulness in programming. If you wanted a more theoretical/mathematical approach (for which you probably have the requisite knowledge) it won’t be best.
And it’s (sort of) a good thing that LISP is so simple and limits what you can do; it may make it easier to see why you’d want to do that.
Lisp is no more limiting than Python is.
MilTan, please check your PM inbox.
I don’t see how we created a new function.
So what does lambda calculus accomplish that regular functions do not? So far it seems that all it accomplishes is making it more complicated to call a function that needs two or more arguments.
It looks like your example and MilTan’s example are working from opposite directions. I would have guessed that the outer function would bind x to 6.
All that I’ve figured out so far is that there is some context in which two arguments can’t be passed in a single function, but that same context allows a function to serve as an argument. Weird.