From: Bobby Abraham
Subject: Lexical variables vs Dynamic
Date: 
Message-ID: <babraham.74.740328356@unpcs1.cs.unp.ac.za>
I am curious to know how symbol values are determined when dealing
with both lexical and dynamic variables.

I realise that there must be two different environments. But when
searching for a value does the interpreter search the special environment 
before the lexical one and return the first value found or is some other 
scheme used.

If so what are the implications for running interpreted code.  Is Dynamic 
variable lookup quicker than lexical?

Winston and Horn give a good account of a lisp interpreter using
lexical and another using dynamic variables but not one implementing 
both kinds. 

Thank you
-------------------------------------------------------------------
Bobby Abraham
Dept. of Computer Science
University of Natal, Pietermaritzburg
email - ········@unpcs1.cs.unp.ac.za
        ·······@unpsun1.cc.unp.ac.za
-------------------------------------------------------------------

From: Pekka P Pirinen
Subject: Re: Lexical variables vs Dynamic
Date: 
Message-ID: <PEKKA.93Jun18135349@gollum.harlqn.co.uk>
> I am curious to know how symbol values are determined when dealing
> with both lexical and dynamic variables.

If you want to mix them, there are two reasonable ways:

1. Use different syntaxes altogether for lexical and dynamic
variables, which makes the implementations independent of each other.

2. If symbols are to be used to refer to both, the only reasonable
convention is that a symbol refers to a lexical variable if and only
if there is a lexically enclosing binding (e.g.  LET) of that lexical
variable.  There must then be some way for distinguishing bindings of
dynamic and lexical variables; in Common Lisp, a binding form refers
to the dynamic variable (called "special" in CL) if the symbol has
been declared as such in that environment, otherwise lexical.

(let ((x 1)	; a lexical binding, because there are no declarations
      (y 2))	; a dynamic binding, because of the DECLARE
  (declare (special y))
  x		; the lexical x, because there is a binding of it
  y		; the dynamic y, because of the DECLARE
  z)		; the dynamic z, because there is no binding of a lexical z

W&H's simple interpreter does not implement this distinction exactly;
what it calls lexical is more like definition-time dynamic.

Interpreters typically implement variable lookup by searching the
lexical environment first and then, if no lexical binding was found,
looking it up in the dynamic environment.  This tends to make dynamic
variables categorically slower than lexical, since the lexical
environment is searched in both cases.

The technique that W&H use for their environment is called deep
binding.  A faster technique is shallow binding: store the current
value of a variable in the value of the symbol, bind variables by
assigning the new value to the symbol and storing the old value in the
environment so that you can restore it when the binding form is
exited.  Shallow binding is what modern Lisps usually use for their
dynamic variables.

An interpreter can also preprocess the code and emit different code
for lexical and dynamic variables.  In this case, no searches are
needed; lexical variables just refer to a slot in the current
activation record (or an earlier one for closed-over variables),
dynamic variables to the value cell of the symbol (shallow binding).
These are approximately equally fast, as they both involve one
dereference.


Pekka P. Pirinen		·····@harlequin.co.uk
Harlequin Limited, Cambridge, England -- finally
From: Barry Margolin
Subject: Re: Lexical variables vs Dynamic
Date: 
Message-ID: <1vsqk7INNksa@early-bird.think.com>
In article <·····················@unpcs1.cs.unp.ac.za> ········@unpcs1.cs.unp.ac.za (Bobby Abraham) writes:
>I am curious to know how symbol values are determined when dealing
>with both lexical and dynamic variables.
>
>I realise that there must be two different environments. But when
>searching for a value does the interpreter search the special environment 
>before the lexical one and return the first value found or is some other 
>scheme used.

In Common Lisp, whether a variable is lexical or dynamic is a lexical
property of the variable.  So the implementation knows a priori which
environment to search for each variable.  In effect, it first searches the
lexical environment to find the lexical/dynamic indicator, and then
searches the indicated environment for the value.  Usually, when code is
compiled the first search occurs only at compile time, and the second
search often turns into a direct lookup; for lexical variables it's
generally an index into a lexical environment, and for dynamic variables on
shallow binding systems it's a reference to the symbol's value cell.

-- 
Barry Margolin
System Manager, Thinking Machines Corp.

······@think.com          {uunet,harvard}!think!barmar
From: Erann Gat
Subject: Re: Lexical variables vs Dynamic
Date: 
Message-ID: <1vssnd$fe9@elroy.jpl.nasa.gov>
In article <············@early-bird.think.com> ······@think.com (Barry Margolin) writes:

>In Common Lisp, whether a variable is lexical or dynamic is a lexical
>property of the variable.

[Much deleted]

I think you are mistaken.  A lexical property is one which depends only upon
the structure of the code and not upon the circumstances under which the code
is executed or compiled.  So while the presence of a SPECIAL declaration will
guarantee that a variable is dynamic, but there is no way in Common Lisp
to guarantee that a variable is lexical because of the presence of DEFVAR.
For example:

(setq x 1)
(defun baz () x)
(defun foo () (let ( (x 2) ) (baz)))

Foo might return either 1 or 2 depending on whether or not (DEFVAR X)
had been executed before FOO was compiled.  Thus, the lexicality
of X is a dynamic property.

Or am I missing something?

Erann Gat
···@robotics.jpl.nasa.gov
From: Len Charest
Subject: Re: Lexical variables vs Dynamic
Date: 
Message-ID: <CHAREST.93Jun18111659@underdog.jpl.nasa.gov>
In article <··········@elroy.jpl.nasa.gov> ···@robotics.jpl.nasa.gov (Erann Gat) writes:

   In article <············@early-bird.think.com> ······@think.com (Barry Margolin) writes:

   >In Common Lisp, whether a variable is lexical or dynamic is a lexical
   >property of the variable.

   
   (setq x 1)
   (defun baz () x)
   (defun foo () (let ( (x 2) ) (baz)))

   Foo might return either 1 or 2 depending on whether or not (DEFVAR X)
   had been executed before FOO was compiled.  Thus, the lexicality
   of X is a dynamic property.

Uh, did you test this code? The reference to X in BAZ *always* refers
to the dynamic binding of variable X. The LET in FOO creates a new
*lexical* binding for X, but this binding is active only within the
lexical (that is, typographic) scope of the LET. So BAZ never sees
this binding. I think you are confusing CL semantics with Scheme.

..................................................
                                  Len Charest, Jr.
                 JPL Artificial Intelligence Group
                          ·······@aig.jpl.nasa.gov
--
..................................................
                                  Len Charest, Jr.
                 JPL Artificial Intelligence Group
                          ·······@aig.jpl.nasa.gov
From: Erann Gat
Subject: Re: Lexical variables vs Dynamic
Date: 
Message-ID: <1vte10$4of@elroy.jpl.nasa.gov>
In article <·····················@underdog.jpl.nasa.gov> ·······@underdog.jpl.nasa.gov (Len Charest) writes:

>Uh, did you test this code? The reference to X in BAZ *always* refers
>to the dynamic binding of variable X. The LET in FOO creates a new
>*lexical* binding for X, but this binding is active only within the
>lexical (that is, typographic) scope of the LET. So BAZ never sees
>this binding. I think you are confusing CL semantics with Scheme.

From MCL 2.0p2:

? (setq x 1)
1
? (defun baz () x)
;Compiler warnings :
;   Undeclared free variable X, in BAZ.
BAZ
? (defun foo () (let ( (x 2) ) (baz)))
;Compiler warnings :
;   Unused lexical variable X, in FOO.
FOO
? (foo)
1
? (defvar x 1)
X
? (defun foo () (let ( (x 2

Yes, I tested the code.  Did you?  If X is declared special globally
(e.g. via a DEFVAR) then LET will bind X dynamically.  This is one
of the major differences between Scheme and Common Lisp.  In Scheme
dynamic binding is done with a different special form (FLUID-LET).
In Common Lisp the binding type is a property of the symbol.
(I was truly stunned when I first learned this.  IMHO this ties with
the package system as the most annoying of CL's many annoying features.
For the record, though, I believe that CL's cool features more than
outweigh the annoying ones.)

E.
From: Pekka P Pirinen
Subject: Re: Lexical variables vs Dynamic
Date: 
Message-ID: <PEKKA.93Jul13172643@gollum.harlqn.co.uk>
······@think.com (Barry Margolin) wrote 8 Jul 1993 23:13:55 GMT:
: However, it's possible to implement locally lexical variables using
: SYMBOL-MACROLET:

Nice idea, pity that X3J13 spoiled it.  CLtL2 is ambiguous, and could
be read as just forbidding a SPECIAL declaration in a SYMBOL-MACROLET
form, but the dpANS unconditionally requires (p. 3-78) that an error
be signalled if a SYMBOL-MACROLET binding of a special or constant is
attempted.

: > (defvar *foo* 1)
: *FOO*
: > (defun foo () *foo*)
: FOO
: > (lexical-let ((*foo* 2)) (list *foo* (foo)))
Your example would signal an error here.


Pekka P. Pirinen			·····@harlequin.co.uk
Harlequin Limited, Cambridge, England
From: Erann Gat
Subject: Re: Lexical variables vs Dynamic
Date: 
Message-ID: <1vte4j$4q9@elroy.jpl.nasa.gov>
In article <·····················@underdog.jpl.nasa.gov> ·······@underdog.jpl.nasa.gov (Len Charest) writes:

>Uh, did you test this code?

Sorry, my editor ate part of my example.  Here it is again, without the
embarrassing abridgement:


? (setq x 1)
1
? (defun baz () x)
;Compiler warnings :
;   Undeclared free variable X, in BAZ.
BAZ
? (defun foo () (let ( (x 2) ) (baz)))
;Compiler warnings :
;   Unused lexical variable X, in FOO.
FOO
? (foo)
1
? (defvar x 1)
X
? (defun foo () (let ( (x 2) ) (baz)))
FOO
? (foo)
2
? 


Sorry about the confusion.

E.
From: Len Charest
Subject: Re: Lexical variables vs Dynamic
Date: 
Message-ID: <CHAREST.93Jun18181133@underdog.jpl.nasa.gov>
In article <··········@elroy.jpl.nasa.gov> ···@robotics.jpl.nasa.gov (Erann Gat) writes:

   ? (setq x 1)
   1
   ? (defun baz () x)
   ;Compiler warnings :
   ;   Undeclared free variable X, in BAZ.
   BAZ
   ? (defun foo () (let ( (x 2) ) (baz)))
      ^^^^^^^^^
   ;Compiler warnings :
   ;   Unused lexical variable X, in FOO.
   FOO
   ? (foo)
   1
   ? (defvar x 1)
   X
   ? (defun foo () (let ( (x 2) ) (baz)))
      ^^^^^^^^^
   FOO
   ? (foo)
   2
   ? 

It wasn't clear to me that you intended on redefining FOO. Note that
if you don't redefine FOO then (FOO) continues to return 1, regardless
of the fact that X has been DEFVAR'd (i.e., proclaimed special).

In another article Erann writes:

   >... If X is declared special globally
   >(e.g. via a DEFVAR) then LET will bind X dynamically.  This is one
   >of the major differences between Scheme and Common Lisp.  In Scheme
   >dynamic binding is done with a different special form (FLUID-LET).

In CL dynamic bindings are typically DECLARE'd. That's why you got a
compiler warning in the definition of BAZ. True, the declaration is
not required, but if you're going to use free variable references you
may as well switch to ELisp...

   >In Common Lisp the binding type is a property of the symbol.
   >(I was truly stunned when I first learned this.  IMHO this ties with
   >the package system as the most annoying of CL's many annoying features.
   >For the record, though, I believe that CL's cool features more than
   >outweigh the annoying ones.)

The CL package system, while being less than intuitive, is no harder
to use than the condition system or CLOS or triple-nested
backquote...IMHO.  The only attribute of the package system I find
annoying is that I can't redefine the syntax of the colon (see
SET-SYNTAX-FROM-CHAR, CLtL2, p 541). Oh, and package *inheritance*
would be nice.

..................................................
                                  Len Charest, Jr.
                 JPL Artificial Intelligence Group
                          ·······@aig.jpl.nasa.gov
--
..................................................
                                  Len Charest, Jr.
                 JPL Artificial Intelligence Group
                          ·······@aig.jpl.nasa.gov
From: Erann Gat
Subject: Packages (was Re: Lexical variables vs Dynamic)
Date: 
Message-ID: <2000t0$m9p@elroy.jpl.nasa.gov>
In article <·····················@underdog.jpl.nasa.gov> ·······@underdog.jpl.nasa.gov (Len Charest) writes:

[Much deleted]

>In CL dynamic bindings are typically DECLARE'd. That's why you got a
>compiler warning in the definition of BAZ. True, the declaration is
>not required, but if you're going to use free variable references you
>may as well switch to ELisp...

While it is true that avoiding free variables will prevent the problem
I cited, but there is no way to prevent the efficiency lost when a dynamic
binding is unexpectedly introduced because of a forgotten DEFVAR somewhere
in the past.

>The CL package system, while being less than intuitive, is no harder
>to use than the condition system or CLOS or triple-nested
>backquote...IMHO.  The only attribute of the package system I find
>annoying is that I can't redefine the syntax of the colon (see
>SET-SYNTAX-FROM-CHAR, CLtL2, p 541). Oh, and package *inheritance*
>would be nice.

Well, I can ignore triple-nested backquote and conditions, but packages
are always in your face.  For example:

I find it annoying that symbols get interned into packages by the reader,
so that I often have the following happen:

> (foo x) ; FOO is in package BAZ
ERROR: Undefined function FOO  ; Oops! Forgot to use-package BAZ
-> :abort
> (use-package :baz)
ERROR: Using package BAZ would cause a name conflict with symbol FOO
-> ; ARRRGGGHHHHH!  Forget to unintern foo, and anything else I might
have typed in the meantime

The trouble is that Common Lisp really has a flat name space; packages
simply provide a more complex mapping of strings onto symbols for the
reader.  What I really want is a way of managing sets of bindings from
symbols onto their values (i.e. first class environments).

Another annoying feature of packages is the following: suppose I have an
interpreter in the INTERP package.  Now, unless all the keyword symbols
used by the interpreter are exported (or are CL keywords) then a program
will not be properly interpreted unless it is READ in the INTERP package.
That is, the proper operation of a program which calls the interpreter
depends on the binding of *package* at READ time!  If you are using someone
else's code there may be no solution to this problem.

Erann Gat
From: rodrigo vanegas
Subject: Re: Lexical variables vs Dynamic
Date: 
Message-ID: <RV.93Jun18174446@vegas.cs.brown.edu>
In article <·····················@underdog.jpl.nasa.gov>, ·······@underdog.jpl.nasa.gov (Len Charest) writes:
>    In article <············@early-bird.think.com> ······@think.com (Barry Margolin) writes:

>   >In Common Lisp, whether a variable is lexical or dynamic is a lexical
>   >property of the variable.

>    
>    (setq x 1)
>    (defun baz () x)
>    (defun foo () (let ( (x 2) ) (baz)))

>    Foo might return either 1 or 2 depending on whether or not (DEFVAR X)
>    had been executed before FOO was compiled.  Thus, the lexicality
>    of X is a dynamic property.

> Uh, did you test this code? The reference to X in BAZ *always* refers
> to the dynamic binding of variable X. The LET in FOO creates a new
> *lexical* binding for X, but this binding is active only within the
> lexical (that is, typographic) scope of the LET. So BAZ never sees
> this binding. I think you are confusing CL semantics with Scheme.

Uh, did you test this code?  Consider a more explicit variation on the
above.  My Lucid CL says:

|
| > (setq lex 1)
| 1
| > (defun baz-lex () lex)
| BAZ-LEX
| > (defun foo-lex () (let ((lex 2)) (baz-lex)))
| FOO-LEX
| > (defvar *dyn* 1)
| *DYN*
| > (defun baz-dyn () *dyn*)
| BAZ-DYN
| > (defun foo-dyn () (let ((*dyn* 2)) (baz-dyn)))
| FOO-DYN
| > (foo-lex)
| 1
| > (foo-dyn)
| 2
|

Enough said.


rodrigo vanegas
··@cs.brown.edu
From: Barry Margolin
Subject: Re: Lexical variables vs Dynamic
Date: 
Message-ID: <203dpkINN10h@early-bird.think.com>
In article <··········@elroy.jpl.nasa.gov> ···@robotics.jpl.nasa.gov (Erann Gat) writes:
>In article <············@early-bird.think.com> ······@think.com (Barry Margolin) writes:
>>In Common Lisp, whether a variable is lexical or dynamic is a lexical
>>property of the variable.
>I think you are mistaken.  A lexical property is one which depends only upon
>the structure of the code and not upon the circumstances under which the code
>is executed or compiled.

Actually, I'd say that this is something between lexical and dynamic.  I
tend to think of "dynamic" as referring to properties that are dependent on
the runtime environment, but globally special variables (those declared
with SPECIAL proclamations or the DEFxxx macros that expand into it) only
have an effect if they're in the compile-time environment.  Thus:

> (defun foo (x y) (let ((*foo* (+ x y))) (bar)))
FOO
> (compile 'foo)
; Warning: Local variable *FOO* unused.
; Warning: Undefined function BAR
FOO
> (defvar *foo* 0)
*FOO*
> (defun bar () *foo*)
BAR
> (foo 1 2)
0

Notice that even though *FOO* is a dynamic variable at the time FOO is
called, it is still being bound as a lexical variable because it wasn't
declared special at the time it was defined and compiled.

This is one of the few ways in which you can tell whether your code is
being interpreted or compiled.  An interpreter is permitted to defer
checking whether to bind something as a lexical or dynamic variable until
the time the binding form is being executed, but a compiler should decide
at compile time (I'm not exactly sure the CL spec requires this explicitly,
so it's a bad idea to write code that declares globally special variables
after having referenced them as lexicals).
-- 
Barry Margolin
System Manager, Thinking Machines Corp.

······@think.com          {uunet,harvard}!think!barmar