Re: A question about lexical binding

On 2008-10-14, jurgen_defurne <jurgen.defurne@xxxxxxxxxx> wrote:
For a couple of years (well, since I started learning Lisp and Scheme
in my spare time) already I am trying to fathom what the real meaning
of lexical scope is. I know how to use them, I program Perl at day,
and I know the extent of lexical variables, and I can use them to
build closures.

However, I am currently going over SICP, and I am building an
evaluator in Perl, to make the distance between what is being
evaluated and the implementation larger. The meta-circular evaluator
from SICP uses a deep binding environment. I have built such a thing
too for my system.

However, deep binding has the problem that depending upon the caller,
a function can behave different because values are searched for by
name in the environment ? Am I correct ?

The proposed solution is lexical binding. The difficulty I had in
understanding lexical binding is that at first sight it did not seem
different from deep binding.

Well, under the mere faculty of sight, they sometimes may be indistinguishable.

;; dynamic: B refers to A

(defvar x) ; A
(lambda () x) ; B

;; lexical: B refers to A
(let (x) ; A
(lambda () x)) ; B

X refers to X either way, what's the diff, right?

The static view doesn't always reveal what happens when the function is
instantiated more than once. Or what might happen if the definition wasn't
lexically apparent to the reference.

As usual, that which is visible (i.e. syntax) doesn't reveal semantics,
or potential semantics.

What I found critical here in my understanding of lexical binding, is
that it depends upon compilation, and that it is very difficult (maybe
impossible ?) to build an interpreter with lexical binding.

In a simple interpreter, lexical binding can be implemented in exactly the same
way as dynamic binding.

Variable references of both kinds (dynamic and lexical) can be implemented
by naively searching the chain of dynamic environment frames, starting from the
innermost nesting and proceeding outward, for a variable until a match is found
by name.

Whether you get lexical or dynamic scope depends on how you terminate the
search and how (or whether) you make closures.

If you terminate the search upon encountering a frame which is marked a a
toplevel frame, you have lexical references; references only ``see'' physically
enclosing definitions. This can be implemented by having an attribute bit in
the environment frame which says ``this frame has no lexical parent; it is a
toplevel frame''. You set this bit whenever you create an evaluation
environment for a toplevel form, or whenever you create an evaluation frame for
a function call.

To have full lexical scope, you need closures also. You achieve these by
retaining the activation chain along with the anonymous function. When that
function is called, that chain is installed as its environment for resolving
variables.

On the other hand, if your variable references do a full search of all of the
frames, not stopping at the top-level bit, then they have indefinite scope
rather than lexical scope. Furthermore, if your lambda operator doesn't retain
a reference to any frames, then you have dynamic extent: when you leave an
evaluation frame, the frame is popped off the stack, and no more references
remain to it anywhere. Dynamic extent plus indefinite scope give you dynamic
scope. An anonymous function has no environment of its own, so it simply
searches that of its caller.

Compilation of lexical environments for better performance is an optimization,
not a necessary implementation strategy.

correct here ? And do I finally understand deep binding, lexical
binding and the difference between them ?

The key is the semantic difference in how these variables behave, and
consequently how you use them, not how they are implemented in some
meta-circular evaluator.

I.e. the way you ``get'' lexical and dynamic scoping is by writing Lisp
programs that appropriately take advantage of lexical and dynamic variables.
.

Relevant Pages

  • Re: What Does Lexical Mean?
    ... or an environment can occur. ... places where that something is "in scope", that is, has a certain ... you now probably have enough context to go ... A binding is ... ...
    (comp.lang.lisp)
  • Re: Moving from Used to New...
    ... You do not need a research grade frame. ... to buy a new scope. ... of cash, especially when dealers ask for 14,000. ... I purchased a phase contrast 40x lens and a 40x ...
    (sci.techniques.microscopy)
  • Re: Scope and program structure problems
    ... then I'd be declaring the variables/objects explicitly ... I personnally find the assignment, import, class and def statements (all having a binding behaviour) to be rather explicit. ... their scope according to how/where they were declared. ... Names bound within a class statement lives in the class's namespace ...
    (comp.lang.python)
  • Re: Reintroducing fish, the friendly interactive shell
    ... Fish supports universal variables, which are variables whose value is ... Universal variables have the outermost scope, ... Universal variables make it much more practical to use environment ... Can you specify the normal behaviour of shell? ...
    (comp.unix.shell)
  • Re: dynamic scope
    ... variable takes a long time because you have to look in all those frames along ... With lexical scope the ... So, if you're going to have lexical scope, just use deep binding. ...
    (comp.lang.logo)