It's all Geek to me?

Jacob Fugal lukfugl at gmail.com
Wed Feb 21 13:27:24 MST 2007


On 2/21/07, Jacob Fugal <lukfugl at gmail.com> wrote:
> On 2/21/07, Steve <smorrey at gmail.com> wrote:
> > But what the heck does it mean to "contain the lambda calculus properly"?
<snip long theory ramble>

More specifically to the page you quoted, the previous sentences are:

"What does it mean for functions to have "lexical scoping"? It means
that functions can access variables of its enclosing functions."

There are two things going on here. First, the fact that functions can
be created anywhere, not just at the global scope. Hence, a function
can be defined inside of another function (aside: they can also be
returned from functions, assigned to variables, and passed as
parameters to another function).

Second, having this nesting of functions makes the question of access
to the environment surrounding the function definition important. If I
(in my own pseudocode, not any specific language) define:

  let make_add_n = function(n) {
    let add_n = function(x) {
      return (x + n)
    }
    return add_n
  }
  let add_4 = make_add_n(4)
  add_4(6) # => 10

the question of whether the add_n function, local to make_add_n, has
access to the variable n is important. If it does, every works as
expected. If not, I will have an error because add_n attempts to
access a variable which it cannot see.

The relation to the lambda calculus is that the binding of identifiers
within lambda expressions follows similar rules. In the lambda
expression[1] equivalent to the above psuedocode:

  (((lambda n. (lambda x. (+ n x))) 4) 6)

n is available within (lambda x. ...) with the same binding as the
enclosing scope.

The presence of lexical scope is necessary (although not sufficient by
itself) so that Lua expressions can be reasoned about using the same
rules as the lambda calculus. The lambda calculus allows us to
transform the above expression as follows:

   (((lambda n. (lambda x. (+ n x))) 4) 6)
-> ((lambda x. (+ 4 x)) 6)
-> (+ 4 6)
-> 10

Since the language "contains the lambda calculus properly", the result
of this transformation is equivalent to the result of the original
program.

Jacob Fugal

[1] I've cheated and augmented the formal lambda calculus with
integers and the + function. The strictly formal lambda calculus,
being as simple as possible, doesn't include these concepts.



More information about the PLUG mailing list