Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Does LETF lead to an identity crisis?

14 views
Skip to first unread message

Pascal Costanza

unread,
Apr 22, 2004, 9:07:08 AM4/22/04
to cost...@web.de

I am currently thinking about how to implement a correct version of
LETF, but there are some subtle issues involved whose consequences I
don't completely understand yet, and I would be interested in getting
some feedback.

First of all some background information. (Those who know about LETF in
general can safely skip this section.)

The general idea
~~~~~~~~~~~~~~~~

Common Lisp provides LET as a binding operator, both for lexical and
special variables; SETQ as an assignment operator, again both for
lexical and special variables; and SETF as a generalized assignment
operator.

The distinction between LET and SETQ is that LET creates a new binding
while SETQ modifies an existing binding. SETF modifies the result of
subsequent calls of the form that is passed as its first argument. So...

(SETF (AREF A 2) 5)

...means that the next time (AREF A 2) is called, this should evaluate
to 5. Usually, this is achieved by storing the value 2 in an array that
is referenced by A.

Now it seems straightforward to provide a generalized binding operator
in a similar way. The idea is that...

(LETF (((AREF A 2) 5))
...)

...creates a new scope (either a lexical or a dynamic one) in which
(AREF A 2) evaluates to 5 - however outside of that scope, (AREF A 2)
should still evaluate to the value it has outside of that scope.

LETF exists for some CL implementations as a library. However, AFAICS,
it uses a hack that doesn't do the right thing in a strict sense. In
those implementations, LETF is implemented as a macro that would, for
example, expand the form above to:

(UNWIND-PROTECT
(LET ((TEMP (AREF A 2)))
(SETF (AREF A 2) 5)
...)
(SETF (AREF A 2) TEMP))

The problem here is that
a) This allows only for dynamically scoped redefinitions.
b) In the dynamic extent of the LETF form, the array A is changed
_globally_ - this means that other threads also see the change which
they strictly shouldn't.

How to implement LETF correctly
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

I think that LETF can be implemented correctly. There are mainly two
schemes:

a) [Copying semantics] The LETF form can create a new copy of the object
to be modified, such that...

(LETF (((AREF A 2) 5))
...)

...would expand into this:

(LET ((A (COPY-ARRAY A)))
(SETF (AREF A 2) 5)
...)

b) [Accessor semantics] The access function can be redefined, such that...

(LETF (((AREF A 2) 5))
...)

...would expand into that:

(FLET ((AREF (AN-ARRAY AN-INDEX)
(IF (AND (EQ AN-ARRAY A)
(EQL AN-INDEX 2))
5
(AREF AN-ARRAY AN-INDEX))))
...)

In case a) it depends on the "specialness" of the variable A whether the
redefinition is dynamically or lexically scoped (and I am convinced that
this is the right thing [0]). In case b), a dynamically scoped
redefinition can be achieved via the DFLET operator I have described in
[1]. [2]

Identity problems
~~~~~~~~~~~~~~~~~

What I don't understand at the moment is what the outcome of the
following form should be:

(LET ((A #(0 1 2 3 4)))
(LET ((A* A))
(LETF (((AREF A 2) 5))
(PRINT (EQL (AREF A* 2)
(AREF A 2)))
(PRINT (EQL A* A)))))

I am pretty sure that the first PRINT form should print NIL. In general,
there needs to be a way to access the previous binding of a variable
(like CALL-NEXT-FUNCTION in [1]), and it's natural to achieve this
through binding it to a different variable before LETF creates a new
binding. The copying semantics would naturally lead to NIL while I don't
see how to implement this correctly with accessor semantics.

I am not so sure what the result of the second PRINT form should be.
Accessor semantics would result in T while copying semantics would by
default result in NIL. I know in principle how achieve T even for
copying semantics, by making use of comparands [3]. However, I don't
have a clear idea what the "correct" result - T or NIL - would be.
Intuitively, I tend to prefer T, because A and A* still refer to the
conceptually same entity.

I would appreciate some feedback about this issue, like: Do you have
some philosophical or some practical argument what to prefer? Have you
ever encountered a scenario in which a decision for either one or the
other result did matter? Do you think the issue matters at all in
practice? What did the Lisp Machines do in this regard? Are there other
venues where I can ask for feedback? And so on...

Thanks a lot in advance,
Pascal

P.S.: Of course, LETF shouldn't work only for arrays. What I would like
to do is to build a framework that one can plug their own LETF expanders
into, and maybe provide some convenience library to make this easier...


[0] All the generalized references in ANSI CL have one "dominant" part
that would be a natural base to determine whether LETF should create a
lexical or a special binding in specific cases. This is also consistent
with the behavior of SETF.

[1] Pascal Costanza, "Dynamically Scoped Functions as the Essence of
AOP", http://doi.acm.org/10.1145/944579.944587

[2] ANSI CL strictly doesn't allow redefinition of built-in operators,
but I don't mind at the moment.

[3] For example, see: Pascal Costanza and Arno Haase, "The Comparand
Pattern", http://www.pascalcostanza.de/ComparandPatternRC1.pdf

--
ECOOP 2004 Workshops - Oslo, Norway
*1st European Lisp and Scheme Workshop, June 13*
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
*2nd Post-Java Workshop, June 14*
http://prog.vub.ac.be/~wdmeuter/PostJava04/

Barry Margolin

unread,
Apr 22, 2004, 9:47:12 AM4/22/04
to
In article <4087C37C...@web.de>, Pascal Costanza <cost...@web.de>
wrote:


> a) [Copying semantics] The LETF form can create a new copy of the object
> to be modified, such that...
>
> (LETF (((AREF A 2) 5))
> ...)
>
> ...would expand into this:
>
> (LET ((A (COPY-ARRAY A)))
> (SETF (AREF A 2) 5)
> ...)

This doesn't do the right thing in the following case:

(letf ((aref a 2) 5)
(setf (aref a 3) 4)))

The SETF form updates the copy of the array rather than the original
array.

This solution also requires a substantial change to
DEFINE-SETF-EXPANDER, so that it can return the expression to make a
copy of the containing object.

> I would appreciate some feedback about this issue, like: Do you have
> some philosophical or some practical argument what to prefer? Have you
> ever encountered a scenario in which a decision for either one or the
> other result did matter? Do you think the issue matters at all in
> practice? What did the Lisp Machines do in this regard? Are there other
> venues where I can ask for feedback? And so on...

I think the LispM LETF only performed dynamic binding, not lexical
binding. However, it didn't leak into other threads (called processes
on the LispM, since the entire system ran in a single address space).
It had hardware support for dynamic binding of arbitrary memory
locations, using some form of auto-forwarding pointers.

--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Joe Marshall

unread,
Apr 22, 2004, 9:59:35 AM4/22/04
to
Pascal Costanza <cost...@web.de> writes:

> I am currently thinking about how to implement a correct version of
> LETF, but there are some subtle issues involved whose consequences I
> don't completely understand yet, and I would be interested in getting
> some feedback.

> I would appreciate some feedback about this issue, like: Do you have


> some philosophical or some practical argument what to prefer? Have you
> ever encountered a scenario in which a decision for either one or the
> other result did matter? Do you think the issue matters at all in
> practice? What did the Lisp Machines do in this regard? Are there
> other venues where I can ask for feedback? And so on...

You need to integrate LETF with the special binding mechanism. The
Lisp machine had `external value cell pointers' which were a special
kind of forwarding pointer. When the stack group was switched, the
contents of the EVCPs in the SPECPDL were swapped along with the
special bindings for symbols. When a memory fetch found an EVCP, the
hardware would trap and dereference the pointer.

I don't think you can easily do a transparent, portable solution.

Pascal Costanza

unread,
Apr 22, 2004, 12:14:47 PM4/22/04
to
Barry Margolin wrote:

> In article <4087C37C...@web.de>, Pascal Costanza <cost...@web.de>
> wrote:
>
>>a) [Copying semantics] The LETF form can create a new copy of the object
>>to be modified, such that...
>>
>>(LETF (((AREF A 2) 5))
>> ...)
>>
>>...would expand into this:
>>
>>(LET ((A (COPY-ARRAY A)))
>> (SETF (AREF A 2) 5)
>> ...)
>
> This doesn't do the right thing in the following case:
>
> (letf ((aref a 2) 5)
> (setf (aref a 3) 4)))
>
> The SETF form updates the copy of the array rather than the original
> array.

Why do you think that this is not the right thing? LETF is supposed to
create a new binding which implies that changes don't affect the
previous binding, doesn't it?

> This solution also requires a substantial change to
> DEFINE-SETF-EXPANDER, so that it can return the expression to make a
> copy of the containing object.

Yes, something along these lines.


Pascal

Barry Margolin

unread,
Apr 22, 2004, 1:30:53 PM4/22/04
to
In article <c68r1o$rjg$1...@f1node01.rhrz.uni-bonn.de>,
Pascal Costanza <cost...@web.de> wrote:

> Barry Margolin wrote:
>
> > In article <4087C37C...@web.de>, Pascal Costanza <cost...@web.de>
> > wrote:
> >
> >>a) [Copying semantics] The LETF form can create a new copy of the object
> >>to be modified, such that...
> >>
> >>(LETF (((AREF A 2) 5))
> >> ...)
> >>
> >>...would expand into this:
> >>
> >>(LET ((A (COPY-ARRAY A)))
> >> (SETF (AREF A 2) 5)
> >> ...)
> >
> > This doesn't do the right thing in the following case:
> >
> > (letf ((aref a 2) 5)
> > (setf (aref a 3) 4)))
> >
> > The SETF form updates the copy of the array rather than the original
> > array.
>
> Why do you think that this is not the right thing? LETF is supposed to
> create a new binding which implies that changes don't affect the
> previous binding, doesn't it?

You're only binding element 2 of the array, not element 3. So
references to the latter should continue to change the original array.

Peter Seibel

unread,
Apr 22, 2004, 1:33:03 PM4/22/04
to
Pascal Costanza <cost...@web.de> writes:

> Barry Margolin wrote:
>
>> In article <4087C37C...@web.de>, Pascal Costanza
>> <cost...@web.de> wrote:
>>
>>> a) [Copying semantics] The LETF form can create a new copy of the
>>> object to be modified, such that...
>>>
>>>(LETF (((AREF A 2) 5))
>>> ...)
>>>
>>>...would expand into this:
>>>
>>>(LET ((A (COPY-ARRAY A)))
>>> (SETF (AREF A 2) 5)
>>> ...)
>> This doesn't do the right thing in the following case:
>> (letf ((aref a 2) 5)
>> (setf (aref a 3) 4)))
>> The SETF form updates the copy of the array rather than the original
>> array.
>
> Why do you think that this is not the right thing? LETF is supposed to
> create a new binding which implies that changes don't affect the
> previous binding, doesn't it?

Yeah, but you bound (aref a 2), not (aref a 3).

I'm curious, what kinds of things was LETF actually used for on the
Lisp machines?

-Peter

--
Peter Seibel pe...@javamonkey.com

Lisp is the red pill. -- John Fraser, comp.lang.lisp

Dan Schmidt

unread,
Apr 22, 2004, 1:13:58 PM4/22/04
to
Pascal Costanza <cost...@web.de> writes:

| Barry Margolin wrote:
|
| > In article <4087C37C...@web.de>, Pascal Costanza
| > <cost...@web.de> wrote:
| >
| >> a) [Copying semantics] The LETF form can create a new copy of the
| >> object to be modified, such that...
| >>
| >>(LETF (((AREF A 2) 5))
| >> ...)
| >>
| >>...would expand into this:
| >>
| >>(LET ((A (COPY-ARRAY A)))
| >> (SETF (AREF A 2) 5)
| >> ...)
| >
| > This doesn't do the right thing in the following case:
| > (letf ((aref a 2) 5)
| > (setf (aref a 3) 4)))
| > The SETF form updates the copy of the array rather than the original
| > array.
|
| Why do you think that this is not the right thing? LETF is supposed to
| create a new binding which implies that changes don't affect the
| previous binding, doesn't it?

The binding of A, or of (AREF A 2)?

If I were using LETF like that I would assume that it only (semantically)
saved and restored the 2nd element, so I would be confused if I tried to
modify the 3rd element and had my change subsequently be undone.

Joe Marshall

unread,
Apr 22, 2004, 1:38:05 PM4/22/04
to
Peter Seibel <pe...@javamonkey.com> writes:

> I'm curious, what kinds of things was LETF actually used for on the
> Lisp machines?

I think it was used a lot in flavors. It's been a while so I've
forgotten.

Barry Margolin

unread,
Apr 22, 2004, 1:51:28 PM4/22/04
to
In article <oepj6h...@ccs.neu.edu>, Joe Marshall <j...@ccs.neu.edu>
wrote:

I don't recall seeing much use of it, but I didn't look at the internals
of Flavors very much. I think it was there just because it could be --
the underlying "external value cell" mechanism that was used for dynamic
bindings of value cells worked just as well with arbitrary cells, so
they provided the API to it.

Arthur Lemmens

unread,
Apr 22, 2004, 2:26:37 PM4/22/04
to Peter Seibel
Peter Seibel <pe...@javamonkey.com> wrote:

> I'm curious, what kinds of things was LETF actually used for on the
> Lisp machines?

I know nothing about Lisp machines, but I think most CLIM implementations
use it for stuff like:

(letf (((medium-ink medium) +red+)
((medium-line-style medium) my-line-style))
(medium-draw-line* medium x1 y1 x2 y2))

The idea is that the medium's ink and line-style are changed to
whatever you need before drawing the line and are automatically
restored afterwards. This could get messy with multiple threads
accessing the same medium, but that's true for all shared resources,
I suppose.

Kalle Olavi Niemitalo

unread,
Apr 22, 2004, 2:09:54 PM4/22/04
to
Barry Margolin <bar...@alum.mit.edu> writes:

> [LispM] had hardware support for dynamic binding of arbitrary memory

> locations, using some form of auto-forwarding pointers.

Did those fit inside specialized arrays? Someone might want to
LETF an element of a bit-vector.

Joe Marshall

unread,
Apr 22, 2004, 2:47:07 PM4/22/04
to
Barry Margolin <bar...@alum.mit.edu> writes:

> In article <oepj6h...@ccs.neu.edu>, Joe Marshall <j...@ccs.neu.edu>
> wrote:
>
>> Peter Seibel <pe...@javamonkey.com> writes:
>>
>> > I'm curious, what kinds of things was LETF actually used for on the
>> > Lisp machines?
>>
>> I think it was used a lot in flavors. It's been a while so I've
>> forgotten.
>
> I don't recall seeing much use of it, but I didn't look at the internals
> of Flavors very much. I think it was there just because it could be --
> the underlying "external value cell" mechanism that was used for dynamic
> bindings of value cells worked just as well with arbitrary cells, so
> they provided the API to it.

I poked around and found some code that did this:

`(letf-globally (((LDB si:%%Time-Page-Faults-Enable si:%disk-switches) 1))
(LET ((,vector (start-timing))
(,start-time (si:%microsecond-time))
,end-time)
(PROG1 ,form
(SETQ ,end-time (si:%microsecond-time))
(si:%flush-extra-pdl)
(end-timing ,vector ,start-time ,end-time ',form
,(NOT (NULL describe-consing-p))))))

It looks like it is supposed to dynamically bind a bit-field in a
microcode variable.

Pascal Costanza

unread,
Apr 22, 2004, 3:37:38 PM4/22/04
to

Barry Margolin wrote:

> In article <c68r1o$rjg$1...@f1node01.rhrz.uni-bonn.de>,
> Pascal Costanza <cost...@web.de> wrote:
>
>>Barry Margolin wrote:
>>
>>
>>>In article <4087C37C...@web.de>, Pascal Costanza <cost...@web.de>
>>>wrote:
>>>
>>>
>>>>a) [Copying semantics] The LETF form can create a new copy of the object
>>>>to be modified, such that...
>>>>
>>>>(LETF (((AREF A 2) 5))
>>>> ...)
>>>>
>>>>...would expand into this:
>>>>
>>>>(LET ((A (COPY-ARRAY A)))
>>>> (SETF (AREF A 2) 5)
>>>> ...)
>>>
>>>This doesn't do the right thing in the following case:
>>>
>>>(letf ((aref a 2) 5)
>>> (setf (aref a 3) 4)))
>>>
>>>The SETF form updates the copy of the array rather than the original
>>>array.
>>
>>Why do you think that this is not the right thing? LETF is supposed to
>>create a new binding which implies that changes don't affect the
>>previous binding, doesn't it?
>
> You're only binding element 2 of the array, not element 3. So
> references to the latter should continue to change the original array.

OK, you're right. I have been thinking about something else that might
also be useful, but can be achieved differently.

Consequentially, this also means that the effect of (SETF (AREF A 2)
...) inside the LETF form is only seen there, but the former value is
restored outside the LETF form, no matter whether SETF'ed or not...


Pascal

--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/

Pascal Costanza

unread,
Apr 22, 2004, 3:42:30 PM4/22/04
to

Joe Marshall wrote:

> You need to integrate LETF with the special binding mechanism. The
> Lisp machine had `external value cell pointers' which were a special
> kind of forwarding pointer. When the stack group was switched, the
> contents of the EVCPs in the SPECPDL were swapped along with the
> special bindings for symbols. When a memory fetch found an EVCP, the
> hardware would trap and dereference the pointer.
>
> I don't think you can easily do a transparent, portable solution.

My idea is that you need to "declare" the location that you want to
dynamically rebind, just like you need to declare variables special in
order to use dynamic binding. The rest is just double indirection, AFAICS.

So for example, for CLOS classes I want to create a metaclass that
allows slots to be declared special, and so on...

Pascal Costanza

unread,
Apr 22, 2004, 3:55:13 PM4/22/04
to
Nikodemus Siivola has accidentally replied by email:

> In article <4087C37C...@web.de> you wrote:
>
> LETF exists for some CL implementations as a library. However, AFAICS,
> it uses a hack that doesn't do the right thing in a strict sense. In
> those implementations, LETF is implemented as a macro that would, for
> example, expand the form above to:
>
> (UNWIND-PROTECT
> (LET ((TEMP (AREF A 2)))
> (SETF (AREF A 2) 5)
> ...)
> (SETF (AREF A 2) TEMP))
>
> The problem here is that
> a) This allows only for dynamically scoped redefinitions.
> b) In the dynamic extent of the LETF form, the array A is changed
> _globally_ - this means that other threads also see the change which
> they strictly shouldn't.
>

> This is probably in the philosophical objection section, but
> find perservation of identity a more compelling argument in favor
> of the above implementation then the dynamicity of scope against.
> If two threads both have the same object, then accesses to it
> should be locked anyways.
>
> Do you have a use in mind for non-dynamic LETF? I sort
> of fail to see one.

For example, this could be a basis for a reasonable implementation of
WITH-ADDED-MACROS. See
http://www.lispworks.com/reference/HyperSpec/Issues/iss360_w.htm and
http://www.lispworks.com/reference/HyperSpec/Issues/iss181_w.htm for
some information.

I am also more interested in dynamically scoped redefinitions, but at
least I want to design my version of LETF in a way that doesn't prevent
lexically scoped redefinitions, in order to keep it more consistent with
the rest of Common Lisp.


Pascal

Kaz Kylheku

unread,
Apr 22, 2004, 4:08:10 PM4/22/04
to
Pascal Costanza <cost...@web.de> wrote in message news:<4087C37C...@web.de>...

And ``outside of that scope'' should also mean ``in another thread
running concurrently that has access to the array A''.

The only reasonable way to do this is to actually bind the *form*
(AREF A 2) to a new storage location which has nothing to do with the
array. The LETF operator has to be smart enough to know that 2 is a
parameter, so that in the enclosed scope, all expressions in the form
(AREF A <X>) will refer to the new storage location whenever <X> is an
expression that evaluates to 2.



> LETF exists for some CL implementations as a library. However, AFAICS,
> it uses a hack that doesn't do the right thing in a strict sense. In
> those implementations, LETF is implemented as a macro that would, for
> example, expand the form above to:
>
> (UNWIND-PROTECT
> (LET ((TEMP (AREF A 2)))
> (SETF (AREF A 2) 5)
> ...)
> (SETF (AREF A 2) TEMP))
>
> The problem here is that
> a) This allows only for dynamically scoped redefinitions.
> b) In the dynamic extent of the LETF form, the array A is changed
> _globally_ - this means that other threads also see the change which
> they strictly shouldn't.

If you want anything else, you have to change the structure of arrays
so that they behave like environments. When you override some dynamic
variable, you don't copy the entire environment. The environment has a
structure that lets you do the job without doing that.

Arrays cells are not bindings, they are storage locations. A binding
is the association between a name and a storage location. Arrays have
an association between an (AREF ) form, part of which is evaluated,
and a storage location. To change a binding means to choose a new
storage location for that form.

If you want (AREF ...) to behave like a binding, you need one more
level of indirection: references have to go through indexing, then a
binding indirection to get to the storage location.

In other words, an array has to become an environment containing
bindings. Each element is actually two cells. The normal storage
location, and a binding which can refer to the adjacent storage
location (the case of a normal, non-overridden array) or it can refer
somewhere else.

One quick-and-dirty way to emulate all this is to store symbols in the
array, and then use a function called SYMBOLIC-AREF on them:

(defun symbolic-aref (symbolic-array &rest indices)
(symbol-value (apply #'aref indices))

#|
(defun symbolic-aset (.... indices new-value)
...)

(defsetf ....)
|#

When you create the symbolic-array, you stuff it with gensyms. Then
the dynamic rebinding of cells can work by way of a dynamic rebinding
of these symbols (maybe using PROGV?).

For speed, maybe a parallel normal (non-symbolic) array can somehow be
used as a cache, in contexts where you know you don't have a
rebinding.

The symbolic array could have a hidden cell which is initially NIL,
and is always overriden by LETF to T. To see whether parts of an
array have been dynamically rebound, you just examine that cell. If
LETF discovers that there is a NIL, then it knows that it's about to
do the outer-most rebinding, and can add code to flush the cache array
to the symbol values, and the reverse flush on termination of that
contour.

Steven M. Haflich

unread,
Apr 24, 2004, 5:13:39 AM4/24/04
to
Pascal Costanza wrote:

>> You're only binding element 2 of the array, not element 3. So
>> references to the latter should continue to change the original array.
>
> OK, you're right. I have been thinking about something else that might
> also be useful, but can be achieved differently.

Right. And don't forget to think about the semantics of lambda-binding
a slot of a displaced array. Ouch! :-)

Scott McKay

unread,
Apr 24, 2004, 8:13:57 AM4/24/04
to

"Arthur Lemmens" <alem...@xs4all.nl> wrote in message
news:opr6veun...@news.xs4all.nl...

Yes, 'letf' is just 'let' for a "place" rather than a lexical
or special variable.

CLIM, I think, called it 'letf-globally' because it was a
kludge w.r.t. multiple threads.

As far as I can see, it is not possible to to 'letf' correctly
without using some kind of thread-local storage.

Pascal Costanza

unread,
Apr 24, 2004, 5:19:52 PM4/24/04
to

Kaz Kylheku wrote:
[useful stuff]

Thanks. Yes, this is roughly what I am also thinking about, but you have
provided some more ideas that will most probably be useful. Thanks a lot.

Pascal Costanza

unread,
Apr 24, 2004, 5:23:44 PM4/24/04
to

Steven M. Haflich wrote:

> Pascal Costanza wrote:
>
>>> You're only binding element 2 of the array, not element 3. So
>>> references to the latter should continue to change the original array.
>>
>> OK, you're right. I have been thinking about something else that might
>> also be useful, but can be achieved differently.
>
> Right. And don't forget to think about the semantics of lambda-binding
> a slot of a displaced array. Ouch! :-)

I don't think that's an important case. CL implementations are already
allowed to separate displaced arrays from their targets when you call
vector-push-extend, so I am not worried too much to add another exception.

Pascal Costanza

unread,
Apr 24, 2004, 5:24:53 PM4/24/04
to

Scott McKay wrote:

> As far as I can see, it is not possible to to 'letf' correctly
> without using some kind of thread-local storage.

My idea is to rely on progv which I hope does the right thing in
multi-threaded CL implementations.

0 new messages