2
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\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$ – Anton Trunov Apr 30 '16 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$ – artemonster Apr 30 '16 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 '18 at 11:38
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\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$ – artemonster Apr 30 '16 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 '16 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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