archives

Lambda the Ultimate seems an Overstatement (not)

As far as I know, no Turing machine and no Chomsky Type 0 or Type 1 language uses lambda expressions. In fact, my analysis indicates that Type 0 and Type 1 languages cannot use lambda expressions, because lambda expressions presume a syntax by design. Doesn't a context-sensitive language determine syntax based on run time state and the content of the expression being processed? If so, that precludes specifying a syntax at design time.

Consequently, lambda expressions are a convenience or optimization of techniques used by Turing machines, reading (i.e., getting) arguments from a program stored on its tape. That's why LtU seems an overstatement to me.