• Nov 13 2008
Different properties one can expect from any λ-calculus

In this post I will show two different sets of properties that any variation of λ-calculus with explicit substitutions may or must have. The must: 1) Any substitution must end, i. e. the process of change a variable by a term must always end, no matter...

• 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...