All Lisp educational litterature introduce, usually early on,
the notion of environment. Yet, for the C/Java brain washed
mind set (I'm one of those) this just looks like an inessential
curiosity.
The reason is probably due to the fact that in those languages,
the heap is never implicitly used. You have to either malloc
or new explicitely, and then, you have to keep track yourself
of those newly created entities.
I've decided to try to put 2 and 2 together and came up with:
(defvar *test-binding* 42)
(defvar *bar* 31415926)
(defun test ()
(let ((*test-binding* -1))
(foo))
(foo))
(defun foo ()
(format t "~%*test-binding* is ~a *bar* is ~a" *test-binding* *bar*))
CL-USER 15 > (test)
*test-binding* is -1 *bar* is 31415926
*test-binding* is 42 *bar* is 31415926
NIL
There, there.
My understanding, right now, is that let creates some sort
of hash table "the environment", and pushes it on top of the
"environment stack".
When foo is called it looks-up any variable binding into the
top of the environment stack, or moves backwards in the stack
until it finds it, eventually reaching the "top of the environment
stack" which is just another name for the "global environment",
that which contains the binding for all special variables.
I had been puzzled by the magic shadowing and restoring that
let introduces, and hadh't come up with a clear mental model
of how this could possibly work.
Now I guess I do :-)
--
JFB
verec <·····@mac.com> writes:
> My understanding, right now, is that let creates some sort
> of hash table "the environment", and pushes it on top of the
> "environment stack".
>
> When foo is called it looks-up any variable binding into the
> top of the environment stack, or moves backwards in the stack
> until it finds it, eventually reaching the "top of the environment
> stack" which is just another name for the "global environment",
> that which contains the binding for all special variables.
>
> I had been puzzled by the magic shadowing and restoring that
> let introduces, and hadh't come up with a clear mental model
> of how this could possibly work.
>
> Now I guess I do :-)
Maybe you do, but your example and model fail to incorporate the
important differences between special bindings and lexical bindings.
I found this model pretty decent:
http://groups.google.com/group/comp.lang.lisp/msg/40a7fd52fba37473
"Lisp in Small" Pieces also has information about different
implementation strategies for Lisp binding semantics, and their
benefits and drawbacks. Worth reading if you want to improve your
mental modelling on this topic.
Zach
On 2006-10-15 19:36:11 +0100, Zach Beane <····@xach.com> said:
>> I had been puzzled by the magic shadowing and restoring that
>> let introduces, and hadh't come up with a clear mental model
>> of how this could possibly work.
>>
>> Now I guess I do :-)
>
> Maybe you do, but your example and model fail to incorporate the
> important differences between special bindings and lexical bindings.
[...]
> "Lisp in Small" Pieces also has information about different
> implementation strategies for Lisp binding semantics, and their
> benefits and drawbacks. Worth reading if you want to improve your
> mental modelling on this topic.
Thanks
--
JFB
On Sun, 15 Oct 2006 18:20:11 +0100, verec <·····@mac.com> wrote:
>
> The reason is probably due to the fact that in those languages,
> the heap is never implicitly used. You have to either malloc
> or new explicitely, and then, you have to keep track yourself
> of those newly created entities.
There are plenty of ways for the heap to be used implicitly in
Java: classloading, object deserialization, autoboxing, insertion into
collection classes, clone(), conversion methods like Date.valueOf(), etc.
--
Jack Unrue
On 2006-10-15 19:10:53 +0100, Jack Unrue <·······@example.tld> said:
>> The reason is probably due to the fact that in those languages,
>> the heap is never implicitly used. You have to either malloc
>> or new explicitely, and then, you have to keep track yourself
>> of those newly created entities.
>
> There are plenty of ways for the heap to be used implicitly in
> Java: classloading, object deserialization, autoboxing, insertion into
> collection classes, clone(), conversion methods like Date.valueOf(), etc.
That's essentially true (but I could be nit-picking no end :) though
the point is that neither C[1] nor Java do allocate from the heap
at variable declaration time[2], the way Lisp's let does at variable
binding time.
BTW: java.util.Date does not have a "valueOf" method, though
java.lang.String has valueOf(int), autoboxing/unboxing is flagged
as such in most IDE (Eclipse) unless you explicitely turn the
warning off, clone() is "just" a specialization of "new"... Did
I say I was more fussy than precise? :-)
[1] I purposefully left C++ out
[2] save for the "read-only closures" introduced with the final
keyword in Java.
--
JFB
verec <·····@mac.com> writes:
> That's essentially true (but I could be nit-picking no end :) though
> the point is that neither C[1] nor Java do allocate from the heap
> at variable declaration time[2], the way Lisp's let does at variable
> binding time.
What makes you think Lisp does that?
Zach
On 2006-10-15 21:30:51 +0100, Zach Beane <····@xach.com> said:
> verec <·····@mac.com> writes:
>
>> That's essentially true (but I could be nit-picking no end :) though
>> the point is that neither C[1] nor Java do allocate from the heap
>> at variable declaration time[2], the way Lisp's let does at variable
>> binding time.
>
> What makes you think Lisp does that?
My understanding is that when let is executed, a new
hashtable (environment) is created to hold the bindings.
This could at least theoretically by allocated on the stack,
except that only a "sufficiently smart compiler (TM)" will
know, at that time, whether or not a closure is going to
be returned, thus "leaking" the environment to the outside,
at which point the heap seems to be the most natural place.
(defun leak-env ()
(let ((x 1))
(lambda (y) (+ x y))))
CL-USER 1 > (setf *f* (leak-env))
#<Function 1 subfunction of LEAK-ENV>
CL-USER 2 > (funcall *f* 7)
8
There's no way the storage for "x" inside leak-env could
have been allocated on the stack.
Though, in my first example
(defun test ()
(let ((*test-binding* -1))
(foo))
(foo))
that was a possibility, I think.
--
JFB
verec <·····@mac.com> writes:
> My understanding is that when let is executed, a new
> hashtable (environment) is created to hold the bindings.
This is fine for a mental model of the semantics, but don't put too
much stock in it as an implementation strategy.
> This could at least theoretically by allocated on the stack,
> except that only a "sufficiently smart compiler (TM)" will
> know, at that time, whether or not a closure is going to
> be returned, thus "leaking" the environment to the outside,
> at which point the heap seems to be the most natural place.
Lexical scope makes this unnecessary. It's easy to find exactly all
the places where a binding is modified, and which bindings are
captured in a closure. No need for an SSC.
I'll reiterate my suggestion to pick up "Lisp in Small Pieces" to see
how environments can be implemented in a slow interpreter, a fast
interpreter, and a compiler. Your notion fits in with the "slow
interpreter" side of things; real Common Lisp implementations take
advantage of faster techniques.
Zach
verec <·····@mac.com> writes:
> My understanding is that when let is executed, a new
> hashtable (environment) is created to hold the bindings.
> This could at least theoretically by allocated on the stack,
> except that only a "sufficiently smart compiler (TM)" will
> know, at that time, whether or not a closure is going to
> be returned, thus "leaking" the environment to the outside,
> at which point the heap seems to be the most natural place.
Your example never creates a closure. It only uses a dynamically bound
variable, which could be either deep- or shallow-bound. Neither require
use of a heap.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
On Sun, 15 Oct 2006 19:59:10 +0100, verec <·····@mac.com> wrote:
>
> BTW: java.util.Date does not have a "valueOf" method
I meant java.sql.Date
--
Jack Unrue
On Sun, 15 Oct 2006 19:59:10 +0100, verec <·····@mac.com> wrote:
>
> On 2006-10-15 19:10:53 +0100, Jack Unrue <·······@example.tld> said:
>
> > There are plenty of ways for the heap to be used implicitly in
> > Java: classloading, object deserialization, autoboxing, insertion into
> > collection classes, clone(), conversion methods like Date.valueOf(), etc.
>
> That's essentially true (but I could be nit-picking no end :) though
> the point is that neither C[1] nor Java do allocate from the heap
> at variable declaration time[2], the way Lisp's let does at variable
> binding time.
Depending on which JVM one chooses to run, a variable declaration
most certainly can cause a heap allocation, if that JVM allocates
Java stack frames on the heap.
--
Jack Unrue
On 2006-10-15 21:02:39 +0100, Jack Unrue <·······@example.tld> said:
> On Sun, 15 Oct 2006 19:59:10 +0100, verec <·····@mac.com> wrote:
>>
>> On 2006-10-15 19:10:53 +0100, Jack Unrue <·······@example.tld> said:
>>
>>> There are plenty of ways for the heap to be used implicitly in
>>> Java: classloading, object deserialization, autoboxing, insertion into
>>> collection classes, clone(), conversion methods like Date.valueOf(), etc.
>>
>> That's essentially true (but I could be nit-picking no end :) though
>> the point is that neither C[1] nor Java do allocate from the heap
>> at variable declaration time[2], the way Lisp's let does at variable
>> binding time.
>
> Depending on which JVM one chooses to run, a variable declaration
> most certainly can cause a heap allocation, if that JVM allocates
> Java stack frames on the heap.
Feel like arguing, heh? :-)
If we distinguish the norm from the exceptions, then the following
statements are probably true:
Most JVMs do allocate local storage on the stack,
Most C compilers create executables whose runtime behavior
uses the stack for local variables
Most CL implementations, whether interpreted or compiled,
use the heap for environment storage.
At least, the last point is a mental model that I couldm't
fault with any actual Lisp counter example.
I'm happy if you can provide me with one.
Many thanks.
--
JFB
verec <·····@mac.com> writes:
> On 2006-10-15 19:10:53 +0100, Jack Unrue <·······@example.tld> said:
>
> >> The reason is probably due to the fact that in those languages,
> >> the heap is never implicitly used. You have to either malloc
> >> or new explicitely, and then, you have to keep track yourself
> >> of those newly created entities.
> > There are plenty of ways for the heap to be used implicitly in
>
> > Java: classloading, object deserialization, autoboxing, insertion into
> > collection classes, clone(), conversion methods like Date.valueOf(), etc.
>
> That's essentially true (but I could be nit-picking no end :) though
> the point is that neither C[1] nor Java do allocate from the heap
> at variable declaration time[2], the way Lisp's let does at variable
> binding time.
Let doesn't allocate from the heap at variable binding time, except
perhaps in the case of special variables. But this isn't really all
that different from the implicit allocation needed by ThreadLocal
variables in Java.
For example, if one were to write something like:
(let ((x 1))
(let ((x 2))
(let ((x 3))
)))
There would be no heap allocation going on at all!
The allocation from the heap in Lisp tends to happen only in
MAKE-INSTANCE, the MAKE-... constructors for defstructs, the VECTOR and
ARRAY constructors and everybody's favorite: CONS. [OK, there are
perhaps a few more as well.] But even in Java, the various substring
functions also end up allocating additional storage.
What you don't get in Java or C is anything like bindable special
variables. You either have local, lexical variables or you have global
variables that you can't temporarily bind to new values. One of the
neat things about Lisp, though, is that you could add a new binding form
to the language to handle special bindings if it didn't already exist.
I don't know how to do that in Java or C and have the rebinding happen
automatically. [I do know how to do it manually in Java].
> BTW: java.util.Date does not have a "valueOf" method, though
> java.lang.String has valueOf(int), autoboxing/unboxing is flagged
> as such in most IDE (Eclipse) unless you explicitely turn the
> warning off, clone() is "just" a specialization of "new"... Did
> I say I was more fussy than precise? :-)
>
> [1] I purposefully left C++ out
> [2] save for the "read-only closures" introduced with the final
> keyword in Java.
> --
> JFB
>
--
Thomas A. Russ, USC/Information Sciences Institute
On 2006-10-17 18:52:27 +0100, ···@sevak.isi.edu (Thomas A. Russ) said:
>> That's essentially true (but I could be nit-picking no end :) though
>> the point is that neither C[1] nor Java do allocate from the heap
>> at variable declaration time[2], the way Lisp's let does at variable
>> binding time.
>
> Let doesn't allocate from the heap at variable binding time, except
> perhaps in the case of special variables. But this isn't really all
> that different from the implicit allocation needed by ThreadLocal
> variables in Java.
>
> For example, if one were to write something like:
>
> (let ((x 1))
> (let ((x 2))
> (let ((x 3))
> )))
>
> There would be no heap allocation going on at all!
I would tend to agree with that. My "mental model" says
that in this case, none of the 'x' do "leak out" out of
its enclosing let, in which case a straight stack allocation
is all what is required.
> What you don't get in Java or C is anything like bindable special
> variables.
Yes. That was the point of the "Aha" :-)
> You either have local, lexical variables or you have global
> variables that you can't temporarily bind to new values. One of the
> neat things about Lisp, though, is that you could add a new binding form
> to the language to handle special bindings if it didn't already exist.
Huh? Could you give an example of such an alternate binding
rule? Or are you just saying that you could get the effect of
let's rebinding specials with some form of your own other than
let?
> I don't know how to do that in Java or C and have the rebinding happen
> automatically. [I do know how to do it manually in Java].
class Closure<E> {
E e ;
void set(E e) { this.e = e ; }
E get() { return e ; }
}
...
final Closure<Integer> counter = new Closure<Integer>(0) ;
return new Object() {
int hash = counter.get() ; {
counter.set(1+hash) ;
}
public int
hashCode() {
return hash ;
}
}
???
Many thanks
--
JFB
verec <·····@mac.com> writes:
> On 2006-10-17 18:52:27 +0100, ···@sevak.isi.edu (Thomas A. Russ) said:
> > (let ((x 1))
>
> > (let ((x 2))
> > (let ((x 3))
> > )))
> > There would be no heap allocation going on at all!
>
>
> I would tend to agree with that. My "mental model" says
> that in this case, none of the 'x' do "leak out" out of
> its enclosing let, in which case a straight stack allocation
> is all what is required.
Actually, the same is true for special variables, if an implementation
chooses to save the old values on the stack. I would guess that most
implementations would, in fact, do this.
> > What you don't get in Java or C is anything like bindable special
> > variables.
>
> Yes. That was the point of the "Aha" :-)
>
> > You either have local, lexical variables or you have global
> > variables that you can't temporarily bind to new values. One of the
> > neat things about Lisp, though, is that you could add a new binding form
> > to the language to handle special bindings if it didn't already exist.
>
> Huh? Could you give an example of such an alternate binding
> rule? Or are you just saying that you could get the effect of
> let's rebinding specials with some form of your own other than
> let?
The latter. In other words, if LET didn't already rebind specials, you
could use a lisp macro to do that for you. One example would be the
following:
(defmacro special-let (((special-variable new-value)) &body body)
(let ((old-value (gensym)))
`(let ((,old-value ,special-variable))
(unwind-protect
(progn (setf ,special-variable ,new-value)
,@body)
(setf ,special-variable ,old-value)))))
And then use it like:
(special-let ((*my-special-variable* 'new))
(print *my-special-variable*))
Now, I've simplified the example macro. In the real case you would want
to be able to process a list of binding forms instead of just a single
one like I used. Fortunately, you get to use regular lisp code to write
such a macro. It might be a good exercise to write such a macro
yourself.
[Notes: UNWIND-PROTECT is used to insure the value gets set back even
if there is some RETURN-FROM form or error in the body code.
MACROEXPAND-1 is very useful when trying to figure out how
macros work (and how to debug them!).
> > I don't know how to do that in Java or C and have the rebinding happen
> > automatically. [I do know how to do it manually in Java].
>
> class Closure<E> {
> E e ;
> void set(E e) { this.e = e ; }
> E get() { return e ; }
> }
> ...
> final Closure<Integer> counter = new Closure<Integer>(0) ;
> return new Object() {
> int hash = counter.get() ; {
> counter.set(1+hash) ;
> }
> public int
> hashCode() {
> return hash ;
> }
> }
What I don't see here is how this propagates the value down into code
that isn't in the lexical scope of the variable definition, in other
words, much more like the dynamic scope of Lisp special variables.
The manual way would be to write something like
public class Global {
public int VALUE = 0;
}
And then use it with something along these lines:
int oldValue = Global.VALUE;
try {
Global.VALUE = 20;
...
} finally {
Global.VALUE = oldValue;
}
Then anything called in the "..." which references Global.VALUE would
get the appropriate reference, in particular code that was defined in
another file that references the global variable.
What I don't know how to do is how to setup the try...finally block in
some more automated fashion. There is an inability to write
user-defined forms that wrap code around other code that makes this
difficult to do in Java.
--
Thomas A. Russ, USC/Information Sciences Institute
On 2006-10-18 19:16:27 +0100, ···@sevak.isi.edu (Thomas A. Russ) said:
> int oldValue = Global.VALUE;
> try {
> Global.VALUE = 20;
> ...
> } finally {
> Global.VALUE = oldValue;
> }
>
> Then anything called in the "..." which references Global.VALUE would
> get the appropriate reference, in particular code that was defined in
> another file that references the global variable.
>
> What I don't know how to do is how to setup the try...finally block in
> some more automated fashion. There is an inability to write
> user-defined forms that wrap code around other code that makes this
> difficult to do in Java.
Ironically, that sounds easy in C++ ...
Something along the lines (sorry, my C++ is quite rusty,
though I guess the gist of it is correct)
tenplate <class T> struct Rebinder {
T& org ;
T orgVal ;
Rebinder(T& orig, T newVal) : org(orig) {
orgVal = org ;
org = newVal ;
}
~Rebinder() {
org = orgVal ;
}
}
int global1 = 1;
float float2 = 2.1 ;
int foo() {
Rebinder r1(global1, 30) ;
...
{
...
Rebinder r2(global1, 50) ;
{
...
Rebinder r3(global1, 75) ;
}
}
...
Rebinder f1(float2, 3.14) ;
...
}
--
JFB