Disclaimer: I’m not a computer scientist or mathematician. This post is about what I’ve learnt so far about Lambda Calculus. Most of the resources I’ve come across seem to assume either prior knowledge of advanced maths notation or extensive practical experience of lambda functions in software engineering. I’ve tried to avoid this and explain things step by step, but have no doubt made assumptions and mistakes of my own. Corrections (or questions) are welcome. I’ll include a list of the resources I’ve used to piece this together in a later post.
[For those who came in late… part 1, part 2, part 3]
Introduction to Lambda Calculus – Reading List
Most of the resources I found expect prior knowledge of mathematical notation or programming, but these worked for me, with little of either:
- A great introduction by Jake Peck on his blog, Suspended Chord
- The Stanford Encyclopedia of Philosophy – Lambda Calculus
- A Tutorial Introduction to the Lambda Calculus by Raúl Rojas (.pdf)
- Section five of this explanation at diderot.one is helpful on combinators
Helpful Lambda Calculus Videos
Computerphile
These two videos are probably the simplest introductions to Lambda Calculus and the Y Combinator:
Alex Lugo
The embed below starts at about 6 minutes into the video, where there are a couple of nice worked examples of simple beta reduction. Early on it explains currying (a method for working through functions one argument at a time). Towards the end it gets into expressing integers and increment and decrement functions.
Gabriel Lebec – A Flock of Functions
These two videos are brilliant and detailed… and hard to follow if you don’t know either Lambda Calculus or Javascript. The second one has the best explanation of Church Numerals and arithmetic in Lambda Calculus that I’ve seen.
If you’re wondering about the different birds associated with combinators, see:
To Dissect A Mockingbird (this has rather interesting diagrammatic forms of different combinators that I haven’t had a chance to look at in detail… yet.)
To Mock a Mockingbird (full text here)