setf implementation
Mark-Jason Dominus
Steele says that setf is a macro, and gives a sample implementation
which is a big if-else switch that examines the form of its argument
to decide which settor function to use. Then he enumerates all the
different things that you are allowed to setf.
I was surprised by this, because I had picked up a different idea from
somewhere. I had always imagined that setf was a regular function, or
perhaps a special form, and had a simpler and more general
implementation, like this:
When you evaluate (cdr ...), you get back a pointer to the cdr, and
then the enclosing function receives this pointer as an argument.
Normally, the enclosing function will access the contents of the cdr
via this pointer, but if the enclosing function is `setf', it uses
that same pointer to store a new value for the cdr instead of
accessing the old value.
This seems much simpler and more general than a macro with forty-seven
separate cases.
Has `setf' ever been implemented this way?
Is it still implemented this way on any systems?
If my idea works, why does Steele explain the macro implementation instead?
Erik Naggum
| I was surprised by this, because I had picked up a different idea from
| somewhere.
it's a notion from C's pointer concept. as such, it's pretty bogus.
| When you evaluate (cdr ...), you get back a pointer to the cdr, and
| then the enclosing function receives this pointer as an argument.
that's precisely what you don't do in Common Lisp. you don't get a
pointer to the CDR, you get the value of the CDR, which may or may not be
a pointer, depending on its type. in any case, you're not getting a
pointer to something settable.
consider this schematic (yikes, I'm having to resort to graphics!):
+-------+-------+
X: | CAR | CDR |--> ZOT
+-------+-------+
|
V
FOO
when you evaluate (CDR X), you get ZOT back. if you wish the CDR of X to
point to something else, you would do (setf (cdr x) 'bar), but if you
have already obtained ZOT, you don't know where to store BAR.
therefore, in C terminology, what SETF gives you is the address of the
slot you wish to change, but that is not at all similar to a pointer to
the value _in_ that slot.
therefore, your approach won't work, since it misses out on the crucial
level of indirection.
#:Erik
Joe Marshall
Mark-Jason Dominus <m...@op.net> wrote in message
news:86i2o6$o2t$1...@monet.op.net...
> The other day I was reading CLTL, and I got to the section about setf.
> Steele says that setf is a macro, and gives a sample implementation
> which is a big if-else switch that examines the form of its argument
> to decide which settor function to use. Then he enumerates all the
> different things that you are allowed to setf.
>
> perhaps a special form, and had a simpler and more general
> implementation, like this:
>
> then the enclosing function receives this pointer as an argument.
> via this pointer, but if the enclosing function is `setf', it uses
> that same pointer to store a new value for the cdr instead of
> accessing the old value.
>
> This seems much simpler and more general than a macro with forty-seven
> separate cases.
>
> Has `setf' ever been implemented this way?
> Is it still implemented this way on any systems?
> If my idea works, why does Steele explain the macro implementation
instead?
Your idea would work, but at a terrible cost. Every object would be subject
to one level of indirection, so every primitive function would have to
dereference
a pointer to get at the actual bits (including primitives like + and EQ).
Jason Kantz
> somewhere. I had always imagined that setf was a regular function, or
> perhaps a special form, and had a simpler and more general
> implementation, like this:
> When you evaluate (cdr ...), you get back a pointer to the cdr, and
> then the enclosing function receives this pointer as an argument.
You are confusing setf with the function rplacd, which is an inversion
function for cdr.
setf needs to be a macro because it transforms Lisp expressions that are
generalized variables, like (cdr x) or (aref foo 3 5), into the
appropriate inversions.
Check out Ch 12 Generalized Variables in
On Lisp: Advanced Techniques for Common Lisp
by Paul Graham
http://www.amazon.com/exec/obidos/ASIN/0130305529/jasonkantz/
--
Jason Kantz
http://kantz.com/jason/
Stig Hemmer
m...@op.net (Mark-Jason Dominus) writes:
> When you evaluate (cdr ...), you get back a pointer to the cdr, and
> then the enclosing function receives this pointer as an argument.
> via this pointer, but if the enclosing function is `setf', it uses
> that same pointer to store a new value for the cdr instead of
> accessing the old value.
No. Consider:
> (setf a '(1 2))
(1 2)
> (car a)
1
Do you see any pointer here? If SETF had been an ordinary function,
(setf (car a) 3) would not get any pointer to anywhere, just an
ordinary plain number 1, with no indication of where it comes from.
So, SETF has to be a macro.
Stig Hemmer,
Jack of a Few Trades.
PS: Using CAR instead of CDR because the point is clearer that way.
The above is still true for the result of CDR.
Barry Margolin
Stig Hemmer <st...@pvv.ntnu.no> wrote:
>[About SETF]
>m...@op.net (Mark-Jason Dominus) writes:
>> When you evaluate (cdr ...), you get back a pointer to the cdr, and
>> then the enclosing function receives this pointer as an argument.
>> Normally, the enclosing function will access the contents of the cdr
>> via this pointer, but if the enclosing function is `setf', it uses
>> that same pointer to store a new value for the cdr instead of
>> accessing the old value.
>
>No. Consider:
>
>> (setf a '(1 2))
>(1 2)
>
>> (car a)
>1
>
>Do you see any pointer here?
Of course not. His theory was that everything *except* SETF automatically
deferences the pointer. That includes the PRINT function. So you never
actually see the pointer.
It's a possible way to implement the language, but as someone else pointed
out, it means that all accesses are slowed down just to make writing SETF a
little easier. This is not really an appropriate tradeoff.
Also, historically, SETF is a recent addition to the language. The
language originally had lots of type-specific setters, such as RPLACA and
RPLACD for setting the car and cdr of a cons. SETF was created as a way to
unify them all into a common syntax. Implementing it as a macro meant that
no changes to the underlying Lisp implementations were necessary. This is
the normal way that the Lisp language evolves -- the ability to write
functions and macros that look syntactically just like built-ins is
important for this.
--
Barry Margolin, bar...@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Erann Gat
<bar...@bbnplanet.com> wrote:
> Also, historically, SETF is a recent addition to the language. The
> language originally had lots of type-specific setters, such as RPLACA and
> RPLACD for setting the car and cdr of a cons. SETF was created as a way to
> unify them all into a common syntax. Implementing it as a macro meant that
> no changes to the underlying Lisp implementations were necessary. This is
> the normal way that the Lisp language evolves -- the ability to write
> functions and macros that look syntactically just like built-ins is
> important for this.
If we ever get around to doing a major revision on Common Lisp there's
a cool idea from T and Oaklisp that I'd like to see adopted. There,
functions are objects that respond to the SETTER method, e.g.
(setter 'car) --> 'rplaca
(setter 'cdr) --> 'rplacd
and so on. Then setf simply becomes something like:
(setf (fn . args) . more-args) --> (apply (setter fn) (append args more-args))
Much more elegant than a hairy macro IMHO.
Erann Gat
g...@jpl.nasa.gov
Barry Margolin
Erann Gat <g...@jpl.nasa.gov> wrote:
>If we ever get around to doing a major revision on Common Lisp there's
>a cool idea from T and Oaklisp that I'd like to see adopted. There,
>functions are objects that respond to the SETTER method, e.g.
>
>(setter 'car) --> 'rplaca
>(setter 'cdr) --> 'rplacd
>
>and so on. Then setf simply becomes something like:
Dylan also uses this strategy.
>(setf (fn . args) . more-args) --> (apply (setter fn) (append args more-args))
>
>Much more elegant than a hairy macro IMHO.
Common Lisp could already do most of this using the (setf XXX) function
names. However, in some cases it really needs to do a per-function macro
expansion. For instance, SETF of LDB has to update the place that holds
the original value -- integers themselves are immutable.
Mark-Jason Dominus
>The cdr must have a pointer in it;
>that's what a list is all about. The only question is whether
>the cdr function in
>
> (f (cdr foo))
>
>puts the pointer onto the stack for f to dereference later, or whether
>it dereferences immediately and puts the result onto the stack for f
>to examine. I was suggesting that it might do the former.
Ding! Light dawns; it could put the pointer on the stack, but it is
not the pointer that setf would need in order to work the way I wanted.
I was indeed missing out on a crucial level of indirection, and it
would indeed be inefficient to make it work the way I said.
Thanks folks.
Mark-Jason Dominus
Joe Marshall <jmar...@alum.mit.edu> wrote:
>Your idea would work, but at a terrible cost. Every object would be
>subject to one level of indirection, so every primitive function
>would have to dereference a pointer to get at the actual bits
>(including primitives like + and EQ).
I must be missing something. I thought that what eq actually *did* do
in real implementations was to compare the pointers, which was
why (eq "Foo" "Foo") might be either true or false.
As for +, not everything needs to be represented with pointers. For
example, an implementation could use some sort of tagged pointer
representation in which the first few bits of the word labeled the
type of the object being represented, whether it was a pointer or a
fixnum or whatever, and the rest of the bits contained the actual
data.
For example, if you have 32-bit words, you might reserve the first two
as a type tag, as follows:
00: positive fixnuum
11: negative fixnum
01: pointer to string
10: pointer to cons
The other 30 bits in the word are the fixnum itself, or the actual
pointer.
Now the + operator can be implemented with the computer's native ADD
instruction when its arguments are fixnums, because the representation
of a lisp fixnum and the native representation of an integer are
identical.
In this model, a cons is two consecutive 32-bit words; the first one
holds the car, and the second the cdr. The cdr is likely to be a
pointer to another cons, and the car could be a pointer to another
cons, or it could just be a fixnum.
Most of the rest of the other responses in this thread seemed to me to
miss the point of my question. I'm not suggesting that
(cdr foo)
should actually return a pointer to the lisp programmer; I'm talking
about internal representations that are only ever seen by the person
who implemented the interpeter. The cdr must have a pointer in it;
that's what a list is all about. The only question is whether
the cdr function in
(f (cdr foo))
puts the pointer onto the stack for f to dereference later, or whether
it dereferences immediately and puts the result onto the stack for f
to examine. I was suggesting that it might do the former.
If, as you say, this would incur a terrible performance penalty, I'm
afraid I don't see it.
Barry Margolin
>Joe Marshall <jmar...@alum.mit.edu> wrote:
>>Your idea would work, but at a terrible cost. Every object would be
>>subject to one level of indirection, so every primitive function
>>would have to dereference a pointer to get at the actual bits
>>(including primitives like + and EQ).
>
>I must be missing something. I thought that what eq actually *did* do
>in real implementations was to compare the pointers, which was
>why (eq "Foo" "Foo") might be either true or false.
You're talking about different pointers. Consider:
(setq a (cons 'x 'y))
(setq b (cons 'x 'z))
(eq (car a) (car b))
(setf (car a) 'w)
The OP's idea was that (car a) would return a pointer to the first cons's
car cell, and (car b) would return a pointer to the second cons's car cell.
Those two pointers would clearly be different. EQ would have to follow
both those pointers to determine that the cells each contain a pointer to
the same X symbol. But SETF would update the contents of the cell that the
pointer refers to.
Tim Bradshaw
> The only question is whether
> the cdr function in
> (f (cdr foo))
> puts the pointer onto the stack for f to dereference later, or whether
> it dereferences immediately and puts the result onto the stack for f
> to examine. I was suggesting that it might do the former.
Yes that's what it does -- it returns a pointer (or something that is
in general a pointer, there will be special cases for fixnums and so
on).
*But this does not mean SETF can just be a function*! Because it
can't `modify' that pointer in any useful way, in particular it can't
store the modified value back into the place it came from, because it
has no idea *where* it came from (how could it know that?). In order
to do that what would have to be returned by CDR would be a pointer to
the CDR part of the CONS cell itself, which in turn would contain a
pointer to the actual contents of the cell. Then SETF could get at
the actual cons and change the CDR to point somewhere else. But every
other function in the system would have to go through this double
indirection as well.
--tim
Giuseppe Cicero
Pierre R. Mai
> Most of the rest of the other responses in this thread seemed to me to
> miss the point of my question. I'm not suggesting that
>
> (cdr foo)
>
> should actually return a pointer to the lisp programmer; I'm talking
> about internal representations that are only ever seen by the person
> who implemented the interpeter. The cdr must have a pointer in it;
Just a nit: Since all current implementations of Common Lisp are compilers
in normal production use (and a couple don't even have interpreters for
interactive use at the top r-e-p loop anymore), it is usually much more
enlightening to think about implementations at the compiler level, and not
at the interpreter level. While interpretation vs. compilation isn't
really an issue here, thinking in terms of interpretation will often lead
you astray in other contexts, IMHO.
Since you've seen the low-level engineering problem with your
implementation strategy (see your own follow-up), I'm only going
to comment about the high-level engineering problem, which hasn't been
taken up yet, AFAIK:
setf per design _isn't_ about setting some pointed-to "physical"
location to some value: setf is about updating generalized
references, which is much more general than pointers and physical
locations: setf is about logical "locations".
Take an example: Many implementations have a function to give you
the pathname of the current working directory (for operating systems
that have such a notion), e.g.
(default-directory)
will yield the current working directory. With setf, I can (and many
implementations do) define a setf-expander (or a "setf function", for
that matter) for default-directory, which will update the OS's idea of
what the current directory is:
(default-directory)
=> #p"/prj/CLASH/"
(setf (default-directory) #p"/prj/")
=> #p"/prj/"
(default-directory)
=> #p"/prj/"
But when we come down to the implementation level, there probably is
no pointer to anything that we want to modify: We probably need to
call into the OS to change the directory, instead of or in addition
to modifying some internal state.
This is just one example of the generality of generalized references,
which is used (and sometimes abused) fairly often in various parts of
the ANSI CL standard (see e.g. CLOS accessors), the Metaobject
Protocol, various implementations, many software packages, etc.
The beauty of setf is that it gives a very regular syntax to the
setting of something, and let's the implementor hide all the ugly
book-keeping and stuff beneath this very regular syntax. Yes, this
necessitates some ugliness in the implementation of setf, but gives a
very clear interface to both users (setf) and function implementors
(defun and defgeneric of (setf function), define-setf-*, defsetf,
define-modify-macro, etc.)
Regs, Pierre.
--
Pierre Mai <pm...@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
Pierre R. Mai
> has no idea *where* it came from (how could it know that?). In order
> to do that what would have to be returned by CDR would be a pointer to
> the CDR part of the CONS cell itself, which in turn would contain a
> pointer to the actual contents of the cell. Then SETF could get at
> the actual cons and change the CDR to point somewhere else. But every
> other function in the system would have to go through this double
> indirection as well.
AFAIK it would also complicate the garbage collector quite a bit,
since you'd have pointers into the middle of objects lying all over
your stack(s).
Barry Margolin
>In order
>to do that what would have to be returned by CDR would be a pointer to
>the CDR part of the CONS cell itself, which in turn would contain a
>pointer to the actual contents of the cell. Then SETF could get at
>the actual cons and change the CDR to point somewhere else. But every
>other function in the system would have to go through this double
>indirection as well.
That's precisely what the original poster was suggesting.
Tom Breton
> The other day I was reading CLTL, and I got to the section about setf.
> Steele says that setf is a macro, and gives a sample implementation
> which is a big if-else switch that examines the form of its argument
> to decide which settor function to use. Then he enumerates all the
> different things that you are allowed to setf.
> When you evaluate (cdr ...), you get back a pointer to the cdr, and
> then the enclosing function receives this pointer as an argument.
> Normally, the enclosing function will access the contents of the cdr
> via this pointer, but if the enclosing function is `setf', it uses
> that same pointer to store a new value for the cdr instead of
> accessing the old value.
This is C thinking. It doesn't work very well for Lisp, because Lisp
is run interpreted, run compiled, and transformed by a multitude of
macros. You also would have to pass that extra pointer around every
time you did anything at all.
> If my idea works, why does Steele explain the macro implementation instead?
Neither is very good. And that isn't what CLTL2 describes.
Since I built two setf cousins last nite (callf and callf2), and it's
still kind of fresh in my mind, I'll explain a little. This is
basically copied from CLTL2.
You call (get-setf-method PLACE) and bind the 5 values, the form your
macro outputs builds a let statement that binds whatever and then
calls whatever setq-like list-form get-setf-method has given you.
That's about it.
That works well interpreted, because it concisely handles all the setf
methods, even user-defined ones. And it works well compiled, because
in compilation, the macro gets figured out once and for all, and the
extra bindings caused by the let (hopefully) get optimized away.
--
Tom Breton, http://world.std.com/~tob
Not using "gh" since 1997. http://world.std.com/~tob/ugh-free.html
Tim Bradshaw
> That's precisely what the original poster was suggesting.
I don't think it is -- I think he was missing the fact that you'd need
this extra indirection.
--tim
Rob Warnock
+---------------
| Then setf simply becomes something like:
|
Minor quibble: There's a very good reason why you *really* want it to be
[as it sort of already is in CL]:
(setf (fn . args) new-value) --> (apply (setter fn) (cons new-value args))
namely, consider that "fn" might have &OPTIONAL, &KEY, or even &REST args
[assuming, of course, that if "fn" does then "(setter fn)" must, too].
-Rob
-----
Rob Warnock, 8L-846 rp...@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
1600 Amphitheatre Pkwy. FAX: 650-933-0511
Mountain View, CA 94043 PP-ASEL-IA
Mark-Jason Dominus
Tim is right.
Barry Margolin
I know you're the OP, but it sure seemed like that was what you were
saying, but maybe you didn't know it. You wrote:
]When you evaluate (cdr ...), you get back a pointer to the cdr, and
]then the enclosing function receives this pointer as an argument.
]Normally, the enclosing function will access the contents of the cdr
]via this pointer, but if the enclosing function is `setf', it uses
]that same pointer to store a new value for the cdr instead of
]accessing the old value.
"access the contents of the cdr via this pointer" seems to mean
dereferencing the pointer.
Lieven Marchand
> If we ever get around to doing a major revision on Common Lisp there's
> a cool idea from T and Oaklisp that I'd like to see adopted. There,
> functions are objects that respond to the SETTER method, e.g.
We could even go a step further and take the concept of updater
functions from Pop-11. Originally, I thought they were roughly
equivalent in power to setf expansions but
http://www.deja.com/[ST_rn=ps]/getdoc.xp?AN=514603811&fmt=text
set me straight.
--
Lieven Marchand <m...@bewoner.dma.be>
If there are aliens, they play Go. -- Lasker
Jeff Dalton
> g...@jpl.nasa.gov (Erann Gat) writes:
>
> > If we ever get around to doing a major revision on Common Lisp there's
> > a cool idea from T and Oaklisp that I'd like to see adopted. There,
> > functions are objects that respond to the SETTER method, e.g.
>
> We could even go a step further and take the concept of updater
> functions from Pop-11.
Why is that one step further? It looks like almost exactly the same
thing to me.