A Short Introduction to the Lambda Calculus (2004) [pdf]

The Greg Michaelson book is a really great intro, and he's made the postscript sources (without index) available on his website http://www.macs.hw.ac.uk/~greg/books/.

Another (old) gem that I feel like suggesting to anyone interested in this topic is 'Introduction to Functional Programming' by Philip Wadler and Richard Bird, which is also available online for free:

https://usi-pl.github.io/lc/sp-2015/doc/Bird_Wadler.%20Intro...

I have fond memories of playing Alligator Eggs

http://worrydream.com/AlligatorEggs/

With some of my older family members and a couple of mildly intoxicated friends who vaguely understood the theory. It's well worth playing with to learn the lambda calculus.

I believe it comes down to procedural vs declarative. Relational Algebra is fairly procedural (do X, then Y, then Z). Where as Relational Calculus(https://www.tutorialcup.com/dbms/relational-calculus.htm) is declarative.

"Algebra" and "calculus" are often used for historical reasons rather than technical ones.

But as it were, LC cannot be expressed as a universal algebra. Not quite. The lambda terms introduce local binding which throws off an algebraic representation. The best you can do is have a (sorted) representation which includes free variables and then have a quotient of that algebra be LC. Even that doesn't quite work, though, since `x` is not a valid LC term.

I'm not sure "calculus" has a technical meaning in the same sense "algebra" does, and, as mentioned by tel, the use is mostly historical. But note that other historical simple languages such as combinator systems are often referred to as calculi, like the SKI-calculus. In modern programming language theory, formal models of languages are informally referred to as "calculi" as well, mostly as a reference to the lambda calculus.

Barendregt, in his famous book on the lambda calculus has a great justification: once you look at models for the lambda calculus you are forced to introduce notions from analysis, such as continuity. The arguments and proofs would feel right at home in a book on classical analysis. So it's the models that put the calculus in lambda calculus. :)

Of course the real answer is probably history, but it's much more interesting to say that you can simply find connections to calculus if you look hard enough...

λ calculus is left associative - that is, a sequence of applications A B C is interpreted as (A B) C, so we first reduce (λf x. f (f x)) (λy.* 2 y), yielding λx . (λy. * 2 y) ((λy.2 * y) x), and only then apply 5 to it, which finally lets us unravel everything and get 20.

> I'm kind of stuck on 3b in section 8.

So you managed to do exercise 8.7 ? I wonder if there is an answer shorter than 22 symbols...

Nice instance of lambda golfing!