What are some resources for learning Lambda Calculus?

Question

So the Wikipedia entry on Lambda Calculus was interesting but I've finished it. I wish to dive a little deeper and get a better understanding of Lambda Calculus.

Can anyone recommend what they consider to be the best book or primer to Lambda Calculus?

See the math.sx question [Learning Lambda Calculus](http://math.stackexchange.com/questions/967/learning-lambda-calculus/1059#1059) — Charles Stewart, Dec 31 '12 at 17:20
I voted to reopen as, despite being off-topic from some viewpoints , the subject is really central to programming and we should hear other opinions. — alinsoar, Jan 20 '17 at 12:50

score 28 · Accepted Answer · edited Aug 23 '18 at 18:16

28

If you are done with the Wikipedia entry, follow its link to the online Structure and Interpretation of Computer Programs, do the assignments, or read the book.

edited Aug 23 '18 at 18:16

Netwave

40,134
6
50
93

answered Feb 05 '09 at 11:02

gimel

83,368
10
76
104

3

+1 This is a classic resource. It was the coursebook for my uni's first programming course. – Mark Pim Feb 05 '09 at 11:32
4

ditto. although it's more about practicalness, not about the formal-ness of lambda calculus itself. – Jason S Feb 05 '09 at 16:32
+1 Reading now...instead of 6-7 years ago... Rocks a developer's/coder's/programmer's world. – Aggelos Biboudis Jan 16 '10 at 16:43
Play around in DrRacket for a while. – Nathan Lilienthal Nov 07 '14 at 20:17
6

@gimel How does SICP help in learning lambda calculus. – Totoro Nov 13 '14 at 10:01
@batman - see http://stackoverflow.com/questions/2750421/what-type-of-lambda-calculus-would-lisp-loosely-be-an-example-of (Lisp corresponds to an untyped, call-by-value lambda calculus extended with constants.) – gimel Nov 13 '14 at 17:37
sicp does not help learning lambda calculus, but help to practice it practically. – alinsoar Jan 20 '17 at 12:51
3

SICP does not help learning Lambda Calculus. It is NOT a book on Lambda Calculus, but on programming. – Nawaz Sep 15 '19 at 14:06

score 16 · Answer 2 · edited Aug 23 '18 at 19:07

16

Well, there's always An Introduction to Lambda Calculus. I've tried reading it a few times, but always got stuck. I have a nagging feeling that I already know most of this stuff and would probably have an easier time understanding it if it was presented in terms of Lisp/Scheme rather than math. You might have better luck, though :)

edited Aug 23 '18 at 19:07

Will Ness

70,110
9
98
181

answered Feb 05 '09 at 11:42

fred-o

1,342
8
12

score 12 · Answer 3 · edited Feb 28 '19 at 05:00

12

I found "An introduction to Lambda Calculi for Computer Scientists" by Chris Hankin to be pretty good, but I only really used it for one class - not used it in the real world :)

edited Feb 28 '19 at 05:00

Glorfindel

21,988
13
81
109

answered Feb 05 '09 at 11:30

Spedge

1,668
1
19
36

1

Best of the books I've tried – Thomas Ahle Jun 02 '13 at 20:43
@ThomasAhle what other books have you tried? – acorello Dec 11 '14 at 14:25

oakenshield1 · Answer 4 · 2012-09-27T11:21:25.530

5

I recently bought a book from Amazon titled as "An Introduction to Functional Programming Through Lambda Calculus" by Greg Michaelson. It is more of an introduction to functional programming and also introduces lambda calculus. The first impression is quite good. A self contained and easy to read book. Here , you can download free version without index in PostScript.

edited Sep 27 '12 at 11:21

answered Sep 27 '12 at 11:14

oakenshield1

851
1
11
26

David C · Answer 5 · 2018-09-14T15:37:39.973

5

The book that really made me start to use and understand lambda calculus was "Representation and Inference for Natural Language" by Blackburn and Bos. This is a book about natural language processing using Prolog. Another book you might consider is "Natural Language Understanding" by Allen. Finally, if you like lambda calculus, you will probably also enjoy combinatory logic, as the combinators can be defined as lambda expressions. For this, I strongly recommend Smullyan's book of puzzles, "To Mock A Mockingbird." Toward the end he uses the combinators to build a rudimentary programming language.

edited Sep 14 '18 at 15:37

answered Mar 15 '13 at 15:21

David C

173
1
8

2

The Blackburn and Bos book is now available online, http://www.coli.uni-saarland.de/publikationen/softcopies/Blackburn:1997:RIN.pdf – David C Mar 17 '13 at 22:34

score 5 · Answer 6 · edited Feb 28 '19 at 08:00

5

I think the reference on the subject of lambda-calculus itself still is Barendregt's book.

Beyond that it pretty much depends on what "part" of lambda-calculus you are interested in : typing ? proof theory ? term rewriting ? functional programming ?

Each of these is a field in itself, and I don't know of any book that covers it all.

edited Feb 28 '19 at 08:00

Glorfindel

21,988
13
81
109

answered Feb 05 '09 at 12:15

Axelle Ziegler

2,505
17
19

correct, but it is for very advanced programmers, not for beginners. – alinsoar Jan 20 '17 at 12:52

score 5 · Answer 7 · answered Feb 05 '09 at 16:38

5

Try writing a lambda calculus interpetter, ideally in a functional language using the build in syntax of the language rather than via a parser. This is surprisingly easy and a good way to improve your feel for it.

answered Feb 05 '09 at 16:38

Brian

25,523
18
82
173

score 2 · Answer 8 · answered Dec 17 '10 at 01:00

Here is a nice explanation (using Scheme): http://www.cs.brown.edu/courses/cs173/2002/Lectures/2002-10-28-lc.pdf

And here's a nifty bit (from my blog), reducing recursive factorial to pure lambdas: http://blogs.msdn.com/b/ashleyf/archive/2008/12/03/the-lambda-calculus.aspx

Have fun!

What are some resources for learning Lambda Calculus?

8 Answers8

Linked