An untyped lambda calculus interpreter made to learn the basics of lambda calculus and concepts of functional programming.
Lambda(λ) calculus is a formal system developed by Alonzo Church to express mathematical functions and is the foundation of functional programming languages. Lambda calculus (function-based) and Turing machines (state-based) are both universal models of computation, part of the Church-Turing Thesis.
Grammar at a glance:
- Identifier:
x- Identifier as expected in a programming language - Grouping:
(x)- Grouping terms to avoid ambiguity - Abstraction:
λx.y- Define function or lambda (anonymous function) - Application:
x y- Invoke a lambda
See grammar.ebnf for EBNF grammar of this untyped lambda calculus.
- Run -
cargo run - Build release -
cargo build --release
- An Introduction to Functional Programming Through Lambda Calculus. Michaelson (9780486478838)
- Computerphile - Lambda Calculus
- Computerphile - Y Combinator
- Untyped Lambda Calculus slides
- https://en.wikipedia.org/wiki/Church_encoding
- https://en.wikipedia.org/wiki/Beta_normal_form
- https://hbr.github.io/Lambda-Calculus/lambda2/lambda.html
- https://tadeuzagallo.com/blog/writing-a-lambda-calculus-interpreter-in-javascript/
- https://blog.shaynefletcher.org/2016/10/eliminating-left-recursion.html
- https://lucasfcosta.com/2018/07/29/An-Introduction-to-Lambda-Calculus-Part-1.html
- https://www.youtube.com/watch?v=3VQ382QG-y4