I thought about how in lambda calculus (and many implementations of functional programming languages) function (lambda) application and lambda itself, as a construct, are "primitive things", usually somehow implemented by an interpeter. Then I thought, can you "boil-down" these two things to more primitve stuff. For instance, we have a following expression (apply is usually implicit by the syntax convetions, but whatever)

(apply (\x.\y.x) (a b))

The interpreter:
1. Constructs a new environment, where arguments are bound to lambda's terms, i.e. new_env = this_env.append({"x":a, "y":b, "body":"x"})
2. Performs a rewrite of the whole application term with lambda's body, i.e. new_env["body"]

Given only the environment manipualtion "primitives", like: "construct", "append", and "get", doesn't that make whole lambda calculus just a clever trick to hide memory ("tape") mutations? Now I know that turing machine and lambda calculus are equivalent, but is there something more to LC than just what I've described? What have I missed?

  • $\begingroup$ The interpreter needs to treat free variables too: en.wikipedia.org/wiki/…. Nowadays almost everybody uses lexical scopes, so you'd need to create a closure first. $\endgroup$ Apr 30, 2016 at 16:44
  • $\begingroup$ Again, closure is an object (environment) with bindings. This just an additional "complication" to this memory-management abstraction, isn't it? $\endgroup$ Apr 30, 2016 at 16:50
  • $\begingroup$ Well, anything that is workable on a computer for which any notion of state is defined, is actually a memory manipulation algorithm. Can't see how can it be the other way? $\endgroup$
    – noncom
    Sep 21, 2018 at 11:38

1 Answer 1


That seems reasonable to me, although I've never thought of other that way. The critical point is that LC essentially involves variables and substitution. So I wouldn't say it "hides" memory ops, exactly, that's just how LC substitution translates to Turing machinery. On the other hand, substitution is not primitive - combinatory logic eliminates both variables and substitution. So you might say LC introduces rather than hides something.

  • $\begingroup$ But again, combinators operate on stack of stacks. They just hide all that symbol->value mapping and make it implicit. They do not eliminate the "tape", right? $\endgroup$ Apr 30, 2016 at 20:07
  • $\begingroup$ Well, I confess I've never tried to think about how combinators would translate into Turing machines. But a Turing Machine without a tape would not be a Turing Machine, I think. More to the point: if you don't have vars and substitution then you don't have symbol->value bindings. At least not formally, you can still philosophically interpret your syms, but such extra-syntactic semantic bindings are not relevant to computation. So you still have a tape, but nothing is hidden or implicit. Dealing with the tape is just what computation is, in part. At least that's my understanding. $\endgroup$
    – user48832
    Apr 30, 2016 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.