Can anyone explain lambda calculus and currying? I have read the wikipedia articles several times, but that hasn’t helped. I have also searched YouTube for helpful videos, but found none.
Sorry, but my knowledge of html tags is vacuous, so I hope you can read tex tags.
The basic lambda calculus statement is \lambda x, f(x) which is read as the function whose value at x is f(x). For example, \lambda x, x^2 + 3x + 7 is exactly the same as the function that most mathematicians would write f(x) := x^2 + 3x + 7. Also note that \lambda x, f(x) is exactly the same thing as \lambda a, f(a). It is best to think of \lambda as a quantifier, that is something that eliminates a variable. In f(x), x is a variable, while in \lambda x, f(x), the dependence on x has disappeared (although the x hasn’t). Let me also observe that the statement common in calculus books and student papers (learning the wrong thing from the books) that f(x) is a function is incorrect. The name of the function is f. Some functions, sin and log for example, do have names but most don’t. The use of lambda calculus allows us to say f = \lambda x, f(x) since the dependence on x is now gone. Very few mathematicians actually use this language (most are more-or-less ignorant of it); it is mostly used in formal logic. I don’t think I have ever used it in a publication.
I largely wrote the informal explanation of the lambda-calculus on the Wikipedia article, so if you tell me what you don’t understand, perhaps we can improve it.
As for what Currying is. Well, we have a problem if we want to write a function that accepts multiple arguments in the lambda-calculus, as functions only ever expect to receive a single argument. We can either then have the argument expect a product type, with all the arguments bundled together, and extract them from the input in the body of the function, or we can write a function that accepts a single argument, then returns as output another function which accepts another argument, and so on. Of course, in some sense, these two schemes are equivalent. We move from the product passing scheme to the other form using a process called Currying, and back again using a process called uncurrying.
That is, if you have a Haskell interpreter handy, we can write:
curry :: ((a, b) -> c) -> a -> b - c
curry f a b = f (a, b)
uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry f (a, b) = f a b
I don’t have any knowledge of functional programming languages, so the Haskell example doesn’t help me. The wikipedia article loses me at currying and lambda terms. In fact, lambda terms appear to lack a concrete definition in the article. The real problem may be that the concept is too abstract for a non-expert to learn.
Here’s the basic idea behind currying:
Suppose you have a function that takes two arguments and returns the sum, for example, func(x, y) returns x + y.
Now suppose you want to use this function to add a bunch of numbers to 3 and see what you get. One way would be to evaluate func(3, 1), func(3, 2), func(3, 3), and so on. Another way is to define a new function, call it func2, like this: func2(y) returns func(3, y). That’s all currying is.
Then we can evaluate func2(1) to get 1 + 3, and so on.
In languages that support first-class functions, you can write functions that return curried versions of other functions, which in the above example does not really accomplish anything interesting, but there are better uses for it in programming.
Lambda calculus is just a formalized way of talking about first-class functions (i.e., functions as an actual thing that you can do things with, as opposed to just the blackbox that they are in algebra and calculus.)
In your example, does currying save any steps? And why doesn’t func2(y) return func2(3, y)?
Currying doesn’t necessarily save any steps in processing the function - there will still be 3 + 1 evaluated at some point in func2(1) or func(3,1). Though hopefully you see that at least it saves space since you only need to use the single argument y, not a repeated 3.
That gets at part of your second question: func2 takes only one argument, so you can’t say “func2(3,y)”, since that’s not how func2 operates.
To make it explicitly clear, func2(y) returns the same result as func(3,y). That’s probably how you read it, but when discussing the lambda calculus, it can help to be clear about what’s actually going on.
Why is there an emphasis on a function taking only a single argument, if that argument is itself a function? Isn’t that kind of cheating?
In this example, x and y are just integer arguments, not functions. But there are functions that take other functions are arguments. (In functional programming you would build up to those after studying simpler kinds.)
I’m having trouble figuring out how func and func2 interact. Is func2 an argument of func?
in pseudocode:
func(x, y)
out = x + y
return out
func2(x)
out = func(x, 3)
return out
I’m sorry; I don’t have any computer programming knowledge.
func(x, y) = x + y
func2(x) = func(x, 3)
So this just replaces the second argument with an integer?
Yes, as described as the intention of the function earlier “Now suppose you want to use this function to add a bunch of numbers to 3”
I think for a reasonable approach here it’d be a good thing to know why you want to understand lambda calculus and what background you do have, apart from no programming.
To me the informal description seems straightforward, while the actual application seems clear as ink.
Fair enough. I’m taking a (graduate-level) class in mathematical linguistics. The professor is inaccessible and awful at explaining concepts. The textbook is terse/laconic to the point of being unhelpful. I took calculus in HS and statistics in college. I have also taken classes in informal and formal logic.
The lambda calculus is all about providing a mathematical foundation for reasoning about programs, so there is a reasonable assumption floating around that anybody who’s trying to wrap their head around it has some background in programming and some degree of mathematical maturity. If you don’t have those things, you’re going to have fill in your background before you have a reasonable chance of getting it.
So what should I read first?
It’s not something you can learn by reading. You have to learn how to program, which requires you to program, and you have to develop some math background, which requires you to do math. I see that you’re already teaching yourself Python, which is a great start. It’s tough to say exactly how much math is enough, but ideally you’d be doing the math requirements of a computer science major. At a bare minimum, you should have basic courses in discrete math and computability theory–that’s what you really need to start getting a handle on mathematical linguistics.
True, though for a classic text, Structure and Interpretation of Computer Programs is not a bad place to go. Although your best bet is if you can find a course that uses it as a text. (Note that some of the original lectures that went with the book are available online as well).