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.
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
These two videos are probably the simplest introductions to Lambda Calculus and the Y Combinator:
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
If you’re wondering about the different birds associated with combinators, see: