Kind of a companion post for a Code Mesh talk we did:
Infinite Lambda Calculus
The code we used for the talk
The file we ended up with in the talk (it is what it is)
./lambs.txt Also there are some lambdas over here^
Maybe the talk has a main point. Goes like this:
We can come up with a recipe for making a loopy thing:
λx.x x
(λx.x x) (λx.x x)
goes on and on. Maybe for forever.foo
like so: (λx.x x) (λx.foo (x x))
will give us as many foo
s as we want. Doing a few steps of evaluation will get us foo (foo ((λx.foo (x x)) (λx.foo (x x))))
. If we do more steps we get more foo
s.f
, instead of just with foo
, because lambda abstraction: λf.(λx.x x) (λx.f (x x))
λf.(λx.x x) (λx.f (x x))
to λf.(λx.f (x x)) (λx.f (x x))
λf.(λx.f (x x)) (λx.f (x x))
is the Y combinator :)