• Nov 13 2008
Making a thesis

In all previous posts I've tried to teach the different aspects inside my thesis. But after going deeper and deeper, the concepts tend to complicate too much, and much more dedication from the reader is needed. After trying to add another technical...

• Sep 9 2008
Explicit Substitutions, or Substitutions If You Need to Implement Them

As I told you before, performance is something desirable when programming a λ interpreter. The sustitutions we saw are made in one step. I will note the beta step as →β and a substitution step as →. For instance, (λx.x) z  →β  x[x/z]  →  z. The computations...

• Jul 29 2008
And now for something completely different

With this cite of Monthy Python, I will move into another family of calculi. What's wrong with our good ol' λ-calculus? Nearly nothing, except if you want to implement it in a real PC. In one of the firsts posts I've mentioned the α-congruence. The...

• Jun 13 2008
How to create "recursive" functions in λ-calculus

As you probably already now, recursive function are those that call them self. For instance, you can define the factorial function as: fact(0) = 1 fact(n) = n*fact(n-1) This doesn't look like something you can say with the small syntaxis of the λ-calculus...

• May 2 2008
Arithmetic with Lambda Calculus

One simple way to make arithmetic expressions in lambda calculus, is just to extend the calculus with the arithmetic rules: (λx.(λy. x+y)) 2 3 → (λy. 2+y) 3 → 2+3 = 5 But that's pretty easy for us, and (as you problably have already noticed) we like...