A question about lexical binding
jurgen_defurne
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. An environment is built, which consists
of frames, where values are fetched. Not too different from a deep
binding environment, is it ?
However, going through SICP yesterday evening, and I had to skip
forward and backward a few times, because the MCE is in chapter 4, and
lexical binding is in chapter 5, is that the main difference between
lexical and deep binding is the compilation, or maybe even the
analysis process is.
When the meta-circular evaluator interprets an s-expression, this is
real interpretation. Things are executed as they come, and not much
previewing is done. So when the evaluator enters an application, it
does not know what frames it needs to expect, nor the number of
bindings in the current frame.
It seems to me that implementing lexical binding rests upon the
possibility of replacing the dependency for finding something in the
environment by name, by finding something by number.
However, for finding something by number, frames must have a
predefined size.
In order to have a predefined size, the complete extent of the code
(of a function definition) must have been analysed beforehand.
There seem to two ways here to proceed. As shown in SICP, it is
possible to separate analysis from execution. A list of functions is
built, and only when the analysis is complete, this list is executed.
In this case, the system depends upon compilation by the host system :
the functions (lambda closures) returned by the analyser are compiled
by the host system. The other way (also shown in SICP), is to create
the lexical binding through compilation.
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. Am I
correct here ? And do I finally understand deep binding, lexical
binding and the difference between them ?
Regards,
Jurgen
Pascal J. Bourguignon
> 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.
This is the important point. Lexical scoping and dynamic scoping
differs when you cross a function call.
Both:
(defvar *a*)
(let ((*a* 1))
(let ((*a* 2))
*a*))
and:
(let ((a 1))
(let ((a 2))
a))
behave quite the same (even if implemented differently).
The difference will be visible when we do:
(defvar *a* 0)
(defun f (x)
;; [1]
(+ x *a*))
(let ((*a* 1))
(let ((*a* 2))
;; [2]
(f 42)))
and:
(let ((a 0))
(defun g (x)
;; [3]
(+ x a)))
(let ((a 1))
(let ((a 2))
;; [4]
(g 42)))
don't behave the same.
In the first, dynamic, case, we have three environments:
d --> d2=((*a* . 2)) d1=((*a* . 1)) d0=((*a* . 0))
and the current dynamic environment, d, refer to d2 both inside the lets, and inside the function f.
In the second, lexical, case, we have three environments:
l2=((a . 2))
l1=((a . 1))
l0=((a . 0))
There is no "current" lexical environment. Each lexical location (in the
source) has its own lexical environment.
In the lexical location [3], the lexical environment is l0 (where a is bound to 0).
In the lexical location [4], the lexical environment is l2 (where a is bound to 2).
--
__Pascal Bourguignon__
jurgen_defurne
wrote:
So, in the first case, I should get 82 as answer, because *a* is bound
to 2 when f is invoked, and in the second case I should get 0, because
a is 0 at the moment g is defined.
What you illustrated was the part that I already more or less
understood.
However, my question went further, and by looking at the two above
illustrations of the environment, it seems that a lexical environment
is not dependent upon compilation, but only on the possibility to
build an isolated environment, a separate environment just
specifically created for that one function.
This is one of the things that I find less appealing in SICP.
Sometimes things are not really clear. Looking upon it from the
previous perspective, a lexical environment and its implementation
should have been introduced as an exercise to the meta-circular
evaluator, not something to be introduced with compilation. In the
latter case, the way a lexical environment is implemented should have
been separate from what a lexical environment really is.
Thanks,
Jurgen
kod...@eurogaran.com
http://www.flownet.com/ron/specials.pdf
If not, it may shake your preconceptions.
Pascal J. Bourguignon
> So, in the first case, I should get 82 as answer, because *a* is bound
44 actually.
> to 2 when f is invoked, and in the second case I should get 0, because
42 in fact.
> a is 0 at the moment g is defined.
Yes.
> What you illustrated was the part that I already more or less
> understood.
>
> However, my question went further, and by looking at the two above
> illustrations of the environment, it seems that a lexical environment
> is not dependent upon compilation, but only on the possibility to
> build an isolated environment, a separate environment just
> specifically created for that one function.
Yes. Basically, you have several lexical environments, all active at
the same time, depending on where you access them from. There are
several pointers to lexical environments. On the other hand, while
there are several dynamic environment, only one is visible at a given
time, from all the place (in monothreaded situations). There's only
one pointer to one dynamic environment (per thread).
However, at the implementation level, instead of building one big
monolothic structure for each environment, we use often a shadowing
technique, where only the elements that change from one environment to
the other. Hence the chaining of the environments.
There's also the caveat that in Common Lisp, lexical or special
variables may shadow each other.
(let ((a 1)) ; lexical
(let ((a 2)) ; special
(declare (special a))
;; [0]
(f a))
;; [1]
a)
So in the environemnt at [0], A refers a special variable bound to 2,
while at [1], A refere a lexical variable bound do 1.
> This is one of the things that I find less appealing in SICP.
> Sometimes things are not really clear. Looking upon it from the
> previous perspective, a lexical environment and its implementation
> should have been introduced as an exercise to the meta-circular
> evaluator, not something to be introduced with compilation. In the
> latter case, the way a lexical environment is implemented should have
> been separate from what a lexical environment really is.
You could also consult LiSP for implementation questions.
"Lisp in Small Pieces". This book covers Lisp, Scheme and other
related dialects, their interpretation, semantics and compilation. To
sum it up in a few figures: 500 pages, 11 chapters, 11 interpreters
and 2 compilers. <http://www-spi.lip6.fr/~queinnec/WWW/LiSP.html>
--
__Pascal Bourguignon__
jurgen_defurne
wrote:
I ordered a few weeks ago via a colleague, whose mother-in-law lives
in Paris, the 2007 French edition.
Regards,
Jurgen
Tamas K Papp
Thanks for posting, this is a very nicely written intro.
Tamas
Robert Maas, http://tinyurl.com/uh3t
> 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 believe I may have a succinct understanding of the difference
between lexical and special bindings, and may be able to answer
your questions with good explanations. I would like Pascal and/or
Kent to please tell correct any mistakes I make below:
Whenever a binding (of a symbol) occurs, it either makes a lexical
binding, masking any outer lexical binding of the same symbol, or
makes a special binding, masking outer special binding of the same
symbol. Likewise whenever a reference to a symbol occurs, it either
makes a lexical reference (to the innermost lexical binding for
that symbol), or makes a special reference (to the innermost
special binding for that symbol). Declaractions and/or
proclamations determine whether any particular binding or reference
is treated as lexical or special.
When a lexical closure is defined, it carries the lexical binding
stack from the point of definition with it, so that when the
function is later called *that* lexical scope is used as the base
for further lexical bindings, *not* the lexical scope of the
caller. But the special binding stack is *not* carried over into
the closure being defined. Thus when a closure is called, the body
is intepreted using the lexical bindings from the point of
definition but the special bindings from the point of call. Note
that in Common Lisp, all functions are closures, it's just that
most of the time the lexical scope is the null scope with no
current lexical bindings. It's only if the DEFUN or LAMBDA or other
function-defining form occurs inside an explicit binding such as
LET, then the lexical bindings aren't trivial, and there's a
difference between such a lexical closure and an old-style function
that might have been defined in earlier versions of Lisp that
didn't have closures.
It should be possible to implement an *interpretor*, with no
lookahead whatsoever except to look at the top level of any binding
form to see whether there's a declaration of the bound variable
that will override the outer declaraction or default, switching
that variable between special and lexical treatment. Simply have
two binding association-lists, one for special bindings and one for
lexical bindings.
When interpreting a LET or other binding form, simply check each
variable being bound to see if it is currently treated as a lexical
or special variable, and push (var . startingValue) onto the
appropriate association list.
When interpreating a variable reference, check the variable to see
whether it's currently treated as a lexical or special variable,
and do the lookup on the appropriate association list. The result
of the lookup will always return a pair (var . currentValue), and
value-lookup does CDR of that pair while SETQ does RPLACD of that
same pair.
Whenever a closure is defined, wrap an extra form around the body
of the function definition which binds the lexical association list
system-variable to the current *VALUE* of that system-variable.
This is innerd stuff, so you can't just use LET to do it. You need
an UNWIND-PROTECT of something that pushes the old lexical
association list onto a system stack and then overwrites the
system-variable with the desired lexical association list, i.e. the
l.a.l. of the *defining* point. Then upon fallout from the
UNWIND-PROTECT, pop the system stack and overwrite the
system-variable with that association list. So for example,
(function (lambda (x) (+ x y)))
where both x and y are currently treated as lexical variables,
would actually build something like:
'(lambda (x)
(unwind-protect
(progn (system-magic-push-lexical-context **current-lexical-context**)
(setq **current-lexical-context**
(quote ,**current-lexical-context**))
(+ x y))
(setq **current-lexical-context** (system-magic-pop-lexical-context))))
Note the comma inside the back-apostrophe causes symbol-value of
**current-lexical-context** to be called at the moment the
(function ...) form is interpreted, thus capturing the lexical
environment at that moment. But the enclosing SETQ occurs *inside*
application of the lambda form later, thus changing the lexical
environment at function-call time to match what it had been earlier
at closure-building time when the FUNCTION form was interpreted.
The system magic push/pop stuff also is executed at runtime, to
save and restore the lexical environment around where the function
was called, so that after the function returns the rest of the
calling code won't have been affected.
Of course deep binding like this is very slow if there are a lot of
variable bindings simultaneously present. For lexical variables
this shouldn't be a problem, because nobody in their right mind
would write a function with more than about twenty local (lexical)
variables, and nobody in their right mind would define a closure
inside a lexical environment with more than about five local
(lexical) variables to be captured in the lexical closure, and
doing ASSOC on an association list of length twenty-five or less is
blindingly fast on modern CPUs. For special variables where you
might have a thousand global variables simultaneously set up, speed
might be a slight problem. So the best solution might be to use an
association list of current bindings only for lexical bindings, so
that it's trivial to pass it into closures as I demonstrated above,
but use shallow binding for special variables, like this:
(let ((var initialValue))
forms...)
if var is currently to be treated as special variable ==>
(unwind-protect
(progn (push (cons 'var var) **masked-special-bindings**)
(setq var initialValue)
forms...)
(let ((oldpair (pop **masked-special-bindings**)))
(assert (eq (car oldpair) 'var)) ;This is why either way below works
(set (car oldpair) (cdr oldpair)) ;The "right" way
(setf (symbol-value (car oldpair)) (cdr oldpair)) ;What really happens
(set 'var (cdr oldpair)) ;The kludge way, the CAR is a dunzell this way
(setf (symbol-value 'var) (cdr oldpair)) ;What really happens
))
Note that special bindings don't require any magic system push/pop,
nor any constant values encapsulated via backapostrophe-comma to
pass from one context to another. They can be handled by ordinary
push and pop, but using a magic system variable that shouldn't ever
be touched directly by any user code.
So if my understanding, and proposed implementation of *pure*
interpretor, is correct above, let me quickly answer your other
questions:
> The meta-circular evaluator from SICP uses a deep binding
> environment. I have built such a thing too for my system.
But for lexical bindings captured by lexical closures, such as this
code
(let ((x 5))
(list (function (lambda () x))
(function (lambda (v) (setq x v)))
which returns a list of two closures sharing a single lexical
binding, did you do it **right**, sorta like the way I proposed
above, where the *current* (at define-closure time, inside that LET
binding) value of lexical binding stack (in this case (x . 5) in
front of whatever else was in effect at that time) is captured into
a quoted value and passed into a binding form at the top of each
closure that is defined? If you enable *print-circular* will you
see two places where a quoted lexical-bindings value is referenced,
where the value itself is **EQ**shared** between those two places.
> 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?
"by name" is wrong. It's really "by symbol", where the same "name"
in different packages gives a different symbol. It's not sufficient
to treat a package as if it were merely a namespace (as in C++),
because you can intern a symbol by a certain name into a package,
then encapsulate that symbol in some forms, then unintern that
symbol (so all already-created encapsulations of that symbol now
refer to an uninterned symbol henceforth), then intern a new symbol
by the same name in the same package, and encapsulate that new
symbol in more forms. Then despite the fact that both symbols were
using exactly the same namespace at the time they were
encapsulated, they are not the same symbol at all, they are two
separate symbols. I presume that's what you really meant, right?
So let me re-phrase your question before answering:
} However, deep binding has the problem that depending upon the
} caller, a function can behave different because values are
} searched for by symbol in the environment (association list)? Am
} I correct ?
I see no problem there. If the symbol is treated as a special
variable, the current (at call-time) dynamic (special) environment
gets used, so the same function (with free variable) may get access
to different bindings for that same variable depending on who
called it. But if the symbol is treated as a lexical variable, then
within a single function that was defined earlier, it will *always*
be referencing exactly the same lexical binding that had been
passed by a mechanism such as I proposed above, i.e. it will get
the binding that had been in effect at function-definition time.
The *value* of that binding may change from time to time, if *any*
code with access to that binding ever does SETQ on that binding,
but the binding itself will be fixed forever within the body of
that function (closure) definition.
> 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.
See the succinct distinction I described above (if Pascal and/or
Kent agrees I got it right): Within body of defined function
(closure), dynamic (special) binding context are the caller's while
lexical binding context is frozen from when the function (closure)
was defined. Do you now see clearly the difference *inside* the
body of some closure that had been defined earlier?
> ... the main difference between lexical and deep binding is the
> compilation,
No. No compilation is neeced at all. There are three ways that I
can think of to do it right:
- Fully interpreted, no analysis, *only* brute-force recursive
exploration of parse trees, as I described above.
- Analysis of each toplevel form to create binding frames, then the
code inside a frame is converted to reference the frame rather
than search association lists directly, making the code run much
faster even if it's still purely interpreting. Thus it might be
a JIT transformer, where any time a binding sub-form is seen
that sub-form is explored to convert symbol references to
binding-frame references. This achieves shallow binding for more
efficient tight loops without the need for actually compiling.
- Analysis of each toplevel form, followed by JIT compilation to
bytecode or CPU instructions, what CMUCL seems to do AFAIK, what
you are probably thinking of.
> or maybe even the analysis process is.
Even that's not necessary, as you see above. That's the second of
the three ways I list just above.
> When the meta-circular evaluator interprets an
> s-expression, this is real interpretation. Things are
> executed as they come, and not much previewing is
> done. So when the evaluator enters an application, it
> does not know what frames it needs to expect, nor the
> number of bindings in the current frame.
And as I show above, you can get both lexical and special bindings
all mixed together *correctly* per CL semantics, using the method I
outlined above. (ALL CODE COMPOSED FOR THIS MESSAGE, NONE OF IT
TESTED. I REALLY HOPE PASCAL OR KENT LOOKS IT OVER AND CATCHES ANY
MISTAKES I MADE.)
> As shown in SICP, it is possible to separate analysis from execution.
Yes, but analysis isn't at all necesary if my idea above is
correct.
> A list of functions is built, and only when the analysis is
> complete, this list is executed.
**NO** Even with the full CMUCL compilation method, at most you
need to inspect each single function as you compile it, which can
occur at the moment it is first called, not at all necessary to
compile it when it's first defined. I wonder how CMUCL handles it:
* (defun foo (x y) (* x y (+ x y)))
FOO
* (symbol-function 'foo)
#<Interpreted Function FOO {90181F1}>
* (foo 3 5)
120
* (symbol-function 'foo)
#<Interpreted Function FOO {90181F1}>
It looks like functions without any lexical bindings are compiled
at the moment the defining form is evaluated, i.e. at
function-define time, as you would claim is *necessary* but I claim
is merely one of several ways to do it.
(let ((x 5))
(list (function (lambda () x))
(function (lambda (v) (setq x v)))))
=> (#<Interpreted Function "LET ((X 5))" {901CA41}>
#<Interpreted Function "LET ((X 5))" {901CA91}>)
(setq twoclosures *)
(funcall (car twoclosures))
=> 5
(funcall (cadr twoclosures) 42)
(funcall (car twoclosures))
=> 42
twoclosures
=> (#<Interpreted Function "LET ((X 5))" {901CA41}>
#<Interpreted Function "LET ((X 5))" {901CA91}>)
Same there, all analysis happens at the time the function-defining happens.
Let's try compiling one of those closures now:
(compile nil (cadr twoclosures))
Error in function C::GET-LAMBDA-TO-COMPILE:
#<Interpreted Function "LET ((X 5))" {901CA91}> was defined in a non-null environment.
That's weird. Is that a bug or deficiency in CMUCL, that it can't
compile anonymous lexical closures? What if I use DEFUN instead of
FUNCTION LAMBDA to build named lexical closures, then try to
compile one of them?
(let ((x 5))
(defun getx () x)
(defun setx (v) (setq x v))
)
Converted GETX.
Converted SETX.
(symbol-function 'getx)
#<Interpreted Function GETX {901E5E1}>
* (compile 'getx)
Error in function C::GET-LAMBDA-TO-COMPILE:
#<Interpreted Function GETX {901E5E1}> was defined in a non-null environment.
So CMUCL can't compile closures at all??
What if defining form is embedded in another function?
(defun define-two-closures (initval)
(let ((x initval))
(defun getx () x)
(defun setx (v) (setq x v))
))
(define-two-closures 47)
Converted GETX.
Converted SETX.
(symbol-function 'getx)
=> #<Interpreted Function GETX {901F4A1}>
(compile 'define-two-closures)
Converted GETX.
Converted SETX.
Compiling LAMBDA (INITVAL):
Compiling Top-Level Form:
(define-two-closures 86)
(symbol-function 'getx)
=> #<Closure Over Function GETX {9040F61}>
So I guess the only way to compile a lexical closure in CMUCL is if
the definition of that closure is embedded inside a DEFUN which is
then compiled. Let's see if I can get compiled anonymous closures:
(defun make-two-closures (initval)
(let ((x initval))
(list
(function (lambda () x))
(function (lambda (v) (setq x v)))
)))
(compile 'make-two-closures)
Compiling LAMBDA (INITVAL):
Compiling Top-Level Form:
(make-two-closures 73)
=> (#<Closure Over Function "LAMBDA (INITVAL)" {9036B11}>
#<Closure Over Function "LAMBDA (INITVAL)" {9036B21}>)
Yeah!!
> What I found critical here in my understanding of
> lexical binding, is that it depends upon compilation,
No, I don't believe that's true at all. Now that you've provoked me
to think this out well enough to come up with my preliminary design
for a pure-interpretor that handles both lexical and special
bindings *correctly* per CL semantics, maybe I'll try actually
implementing it, in Forth, working with another guy who told me he
wants to build a Lisp machine by first getting a bare-machine Forth
then defining Lisp inside Forth. I'd be using Pocket Forth on my
Mac, but the Lisp-in-Forth code would be the same for both of us.
[By the way, if my idea is correct, then the implementors of
PowerLisp ought to be ashamed of themselves for violating CL
semantics by making *all* variables special at all times, whe they
could instead have thought of the same idea I did and wrote their
interpretor correctly per lexical bindings. Of course if I made
a big mistake, Emily Litelle ... "Never mind"]
> and that it is very difficult (maybe impossible ?) to
> build an interpreter with lexical binding. Am I
> correct here?
If I'm correct, then you are not correct.
Would you like to join me/us in trying to write a Lisp-in-Forth
*interpretor* that respects lexical bindings via what I proposed above?
Just a tiny subset to demonstrate/prove the concept.
We'd use association lists for both bindings and READ of a symbol.
sexpr := atom | (...sexprs...) ;No dotted lists READable
atom := symbol | integer ;No strings etc. etc. etc. readable
symbol := ...caseSensitiveLetters... ;Hungarian spelling instead of hypens
We'd have strings implemented internally (and strings would print
out just fine), which we obtain via ReadLine, and then parse via
ReadFromString. Because we always have a fixed string to parse
from, we can write completely separate tokenizer and collector
instead of needing them to be intertwined.
ForthInput: ReadLine
ReadLineInput: (cons 3 5)
ReadLineReturnValue: "(cons 3 5)"
ForthInput: Tokenize
TokenizerReturnValue: (Open (Symbol cons) (Integer 3) (Integer 5) Close)
ForthInput: Collect
CollectorReturnValue: (cons 3 5)
ForthInput: Eval
EvalReturnValue: (3 . 5)
Rob Warnock
+---------------
| jurgen_defurne <jurgen....@pandora.be> writes:
| > This is one of the things that I find less appealing in SICP.
| > Sometimes things are not really clear. Looking upon it from the
| > previous perspective, a lexical environment and its implementation
| > should have been introduced as an exercise to the meta-circular
| > evaluator, not something to be introduced with compilation. In the
| > latter case, the way a lexical environment is implemented should have
| > been separate from what a lexical environment really is.
|
| You could also consult LiSP for implementation questions.
| "Lisp in Small Pieces". This book covers Lisp, Scheme and other
| related dialects, their interpretation, semantics and compilation. To
| sum it up in a few figures: 500 pages, 11 chapters, 11 interpreters
| and 2 compilers. <http://www-spi.lip6.fr/~queinnec/WWW/LiSP.html>
I strongly second this recommendation, In particular,
Chapter 6 "Fast Interpretation" should be quite helpful,
especially Section 6.1.9 "Variations on Environments",
where Queinnec discusses different ways to represent
lexical environments.
-Rob
-----
Rob Warnock <rp...@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Rob Warnock
+---------------
| It seems to me that implementing lexical binding rests upon the
| possibility of replacing the dependency for finding something in the
| environment by name, by finding something by number.
No, that's not the proper distinction. You most certainly *can* have
[and most simple Scheme interpreters *do* have!] lexical environments
which are searched by name.
The proper distiction you're looking for is that the lexical
environment for a function is "captured" (recorded) at the time
the function is first *created* [which is the time when its
defining lambda expression is evaluated], and it is *that*
environment that is later searched for looking up the values
of variables, *not* the (dynamic) global environment. [Or more
precisely, the lexical environment is searched *before* the
global environment.]
Said another way, every function instance (closure) is a tuple of
a lambda body, a list of the lambda's arguments, and a captured
environment -- the environment that was current when the defining
lambda expression was evaluated, yielding a function (closure).
When the function is later called, the saved environment is
extracted from the function instance (the closure) and is
(temporarily) made the current environment, then new bindings
pairing up the lambda's formal arguments with the function's
actual call-time argument values are made, and added to the
(now-)current environment. The lambda body is then executed,
with the extended environment (the args plus the saved closure
environment). When the function returns its value(s), the current
lexical environment is *abandoned*, and the previous (caller's)
environment is restored as the current now-current environment.
+---------------
| There seem to two ways here to proceed. As shown in SICP, it is
| possible to separate analysis from execution.
+---------------
That is true [and desirable for efficiency], but it is *not* necessary!
+---------------
| 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.
| Am I correct here?
+---------------
No, sorry, you are quite incorrect here. It is thoroughly possible
(and both easy & quite common!) to have a "pure" interpreter with
lexical binding.
-Rob
p.s. As mentioned in a parallel reply thread, Christian Queinnec's
"Lisp in Small Pieces" (or "Les Languages Lisp", en Francais, or
the revised 2007 edition "Principes d'implantation de Scheme et Lisp")
is practically required reading for anyone seriously delving into
the internals workings of Scheme or Lisp interpreters/compilers.
Kaz Kylheku
> 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.
Pascal J. Bourguignon
Or in the same program:
;; dynamic: B1 refers to A1
(defvar x 'special) ; A1
(print (funcall (lambda () x))) ; B1
(print (funcall
;; lexical: B2 refers to A1
(let ((x 'guess-what)) ; A2
(lambda () x)))) ; B2
prints SPECIAL twice.
The second time, because the lambda is called in a context where the
binding of x to GUESS-WHAT is not in effect anymore. The FUNCALL is
not within the lexical scope of that binding.
Sight is not enough alone, you need to understand the context and the
meaning too.
--
__Pascal Bourguignon__