From: tin gherdanarra
Subject: Call by value, but (please check my hypothesis)
Date:
Message-ID: <3r537vFhu3j0U1@individual.net>
Dear Lispniks,
I understand that Lisp does not pass around
references in the sense that only "handles"
to lists (as python does, for example).
This has the consequence that if I do a
(setf (getf '(a 0 b 1 c 2 d 3) 'b) 99) it
is NOT that getf returns a handle to
the "1" and the setf crawls after the spot
in memory to replace it with a "2".
setf looks into the generalized variable
'(getf (a 0 b 1 c 2 d 3) b) and determines
that it has to pull a replacd on the
'(a 0 b 1 c 2 d 3) to replace the 1 with
a 2. In other words, setf uses something
like a case to lookup what it has to do
with getf...
If I have function that does a getf, I
have to get this function into
setf's lookup table. This can be done
with "define-modify-macro".
This, however, leads to problems if
the nesting level of an item in a
tree is not known in advance. The macro
is defined and carved in stone at compile-time.
This means if I have a list like
(a 0 (b 1 c 2 (d 3 (e 4) f 5) g 6)),
I cannot walk the tree recursively and
change to find a certain item and change
it with setf. This is because I cannot
make a generalized variable (since it
is not known at macro compile time how
deep I will want to go). Is this correct?
Is there a way out?
Thanks for your attention
Tin
tin gherdanarra wrote:
> Dear Lispniks,
>
> I understand that Lisp does not pass around
> references in the sense that only "handles"
> to lists (as python does, for example).
>
> This has the consequence that if I do a
> (setf (getf '(a 0 b 1 c 2 d 3) 'b) 99) it
> is NOT that getf returns a handle to
> the "1" and the setf crawls after the spot
> in memory to replace it with a "2".
>
> setf looks into the generalized variable
> '(getf (a 0 b 1 c 2 d 3) b) and determines
> that it has to pull a replacd on the
> '(a 0 b 1 c 2 d 3) to replace the 1 with
> a 2. In other words, setf uses something
> like a case to lookup what it has to do
> with getf...
>
> If I have function that does a getf, I
> have to get this function into
> setf's lookup table. This can be done
> with "define-modify-macro".
No, define-modify-macro is only used when defining a macro. For
functions you use define-setf-expander or defun with the function name
(setf <accessor>). It sounds like you want something like this:
(defun tree-ref (tree index &rest indexes)
(if (null indexes)
(nth index tree)
(apply #'tree-ref (nth index tree) indexes)))
(defun (setf tree-ref) (value tree index &rest indexes)
(if (null indexes)
(setf (nth index tree) value)
(apply #'(setf tree-ref) value (nth index tree) indexes)))
-- MJF
tin gherdanarra wrote:
> Dear Lispniks,
>
> I understand that Lisp does not pass around
> references in the sense that only "handles"
In general, objects are passed by reference in Lisp. When something
else is the case, it is an optimization that can be done when an object
fits into a cell. This is done with small integers or characters, for
instance.
> to lists (as python does, for example).
A Lisp list isn't a container abstraction. It's an object that arises
when cons cells are used in accordance with a certain convention.
An empty list is the symbol NIL. That is to say, the symbol named "NIL"
in the "COMMON-LISP" package. (NIL may be implemented as an actual
reference to this symbol, or as a special bit pattern that is made to
behaves as a reference to that symbol whenever called upon to do so).
A proper list of 1 element is implemented as a reference to a cons cell
whose CAR field contains that element, and whose CDR field is NIL.
A proper list of N elements, where N > 0, is implemented as a cons
cell, whose CAR field holds the first element of the list, and whose
CDR field refers to the remaining list of N - 1 elements (the list of 0
elements being NIL).
> This has the consequence that if I do a
> (setf (getf '(a 0 b 1 c 2 d 3) 'b) 99) it
> is NOT that getf returns a handle to
> the "1" and the setf crawls after the spot
> in memory to replace it with a "2".
That is correct. SETF actually understands the syntax of the (GETF
...) expression, and knows what to do with it.
But note that it's illegal to be modifying a list literal.
> setf looks into the generalized variable
> '(getf (a 0 b 1 c 2 d 3) b) and determines
> that it has to pull a replacd on the
> '(a 0 b 1 c 2 d 3) to replace the 1 with
> a 2. In other words, setf uses something
> like a case to lookup what it has to do
> with getf...
Yes. SETF performs a lookup through its large repertoire of registered
expanders. It has an expander for GETF which tells it exactly what to
do.
> If I have function that does a getf, I
> have to get this function into
> setf's lookup table. This can be done
> with "define-modify-macro".
Correct. A use of GETF wrapped in a function hides the GETF.
This is exactly like the C language. In C, *E is an lvalue, if
expression E is a pointer to something. You can assign to it using *E =
2.
If you wrap that inside a function, you can't assign through it any
longer:
int x() { return *E; }
x() = 2; /* oops */
The = operator understands the /form/ of the left hand side; only
certain forms can be lvalues, and they are only considered lvalues when
they are to the left of an assignment operator.
The return value of a function isn't an lvalue, so that doesn't work.
> This, however, leads to problems if
> the nesting level of an item in a
> tree is not known in advance. The macro
> is defined and carved in stone at compile-time.
> This means if I have a list like
> (a 0 (b 1 c 2 (d 3 (e 4) f 5) g 6)),
> I cannot walk the tree recursively and
> change to find a certain item and change
> it with setf. This is because I cannot
> make a generalized variable (since it
> is not known at macro compile time how
> deep I will want to go). Is this correct?
> Is there a way out?
That is not correct. You just need a SETF expander that understands
parameters. The NTH function is an example. You don't know which
element of the list will be selected; it's a parameter that is not
necessarily known at compile time.
(defvar *list* (list 1 2 3))
(defvar *index* 1)
(setf (nth *index* *list*) 2)
The macro expands to code that can handle the parameter.
If you can write a function that will walk the tree to some specified
place and store an item there, you can develop the SETF veneer over it.
Try this:
(defun three-level-set (list index-0 index-1 index-2 item)
(setf (nth index-2 (nth index-2 (nth index-0 list))) item))
(defvar *list* (copy-tree '(((a b) (c d)) ((e f) (g h)))))
(three-level-set *list* 1 1 0 'z)
That should replace the G symbol by Z: choose the second sublist,
second sublist within that, replace first item by Z.
The SETF works through the nested NTH expressions.
From: Peter Seibel
Subject: Re: Call by value, but (please check my hypothesis)
Date:
Message-ID: <m2slv61q66.fsf@gigamonkeys.com>
tin gherdanarra <···········@gmail.com> writes:
> Dear Lispniks,
>
> I understand that Lisp does not pass around references in the sense
> that only "handles" to lists (as python does, for example).
Your understanding is somewhat flawed. Lisp does pass around
references. However a Lisp list and a Python list are different kinds
of objects.
> This has the consequence that if I do a (setf (getf '(a 0 b 1 c 2 d
> 3) 'b) 99) it is NOT that getf returns a handle to the "1" and the
> setf crawls after the spot in memory to replace it with a "2".
In this case GETF doesn't return anything; rather SETF knows how to
set the appropriate place the list that is GETF's second arg. However
in this case you are invoking undefined behavior since the place that
you are setting is a literal list.
> setf looks into the generalized variable '(getf (a 0 b 1 c 2 d 3) b)
> and determines that it has to pull a replacd on the '(a 0 b 1 c 2 d
> 3) to replace the 1 with a 2. In other words, setf uses something
> like a case to lookup what it has to do with getf...
Something like that. However the generalized variable in this case is
the second form in the GETF form which, as I pointed out above, is not
a place that you can set with defined behavior. However if you had:
(let ((someplist (list 'a 0 'b 1 'c 2 'd 3))
(setf (getf someplist 'b) 2)
it would work in the sense that the variable someplist would now
contain:
(a 0 b 2 c2 d 3)
Whether the original list was modified or someplist given a completely
new value is not defined.
> If I have function that does a getf, I have to get this function
> into setf's lookup table. This can be done with
> "define-modify-macro".
Sort of.
> This, however, leads to problems if the nesting level of an item in
> a tree is not known in advance. The macro is defined and carved in
> stone at compile-time. This means if I have a list like (a 0 (b 1 c
> 2 (d 3 (e 4) f 5) g 6)), I cannot walk the tree recursively and
> change to find a certain item and change it with setf. This is
> because I cannot make a generalized variable (since it is not known
> at macro compile time how deep I will want to go). Is this correct?
Sort of. However I think you are somewhat confused about how lists
work. You can modify the cons cells that make up a list by navigating
to the right cons cell and SETFing the CAR or CDR as you see
fit. However that may or may not actually do what you want insofar as
how the effect on the list will be seen in other places that hold a
reference to "the list". For more details see:
<http://www.gigamonkeys.com/book/they-called-it-lisp-for-a-reason-list-processing.html>
> Is there a way out?
Almost certainly. What are you actually trying to do?
-Peter
--
Peter Seibel * ·····@gigamonkeys.com
Gigamonkeys Consulting * http://www.gigamonkeys.com/
Practical Common Lisp * http://www.gigamonkeys.com/book/
On Wed, 12 Oct 2005 19:38:40 GMT, Peter Seibel <·····@gigamonkeys.com>
wrote:
>Whether the original list was modified or someplist given a completely
>new value is not defined.
That sounds bizarre. Is there any lisp where (setf (getf plist key)
newvalue) actually creates a new plist instead of the seemingly far
more reasonable behavior of destructively modifying the original
plist?
If not, why was it specified that way?
There are almost sure to be programs with the bug of relying on the
seemingly reasonable behavior. Any function with the purpose of
modifying a plist, given that plist as an argument, would be likely to
have that bug.
From: Peter Seibel
Subject: Re: Call by value, but (please check my hypothesis)
Date:
Message-ID: <m2mzle11vq.fsf@gigamonkeys.com>
·@b.c writes:
> On Wed, 12 Oct 2005 19:38:40 GMT, Peter Seibel <·····@gigamonkeys.com>
> wrote:
>
>>Whether the original list was modified or someplist given a
>>completely new value is not defined.
>
> That sounds bizarre. Is there any lisp where (setf (getf plist key)
> newvalue) actually creates a new plist instead of the seemingly far
> more reasonable behavior of destructively modifying the original
> plist?
Not that I know of.
> If not, why was it specified that way?
Presumably to give implementations lattitude to make optimizations
that would otherwise be forbidden. Whether any implementation has ever
taken advantage of that lattitude, I don't know.
Or possibly the spec was written just a bit too losely, who knows?
FWIW, what the specification actually says is:
setf of getf is permitted to either write the value of place itself,
or modify of any part, car or cdr, of the list structure held by
place.
This is pretty standard spec language for "this operation will give
you the functional result you expect, but can be implemented pretty
much however so you'd better not rely on anything else."
Obviously there's a case where writing the value of the place is the
only possible implementation:
(let ((x nil))
(setf (getf x 'a) 1))
Since there are no cons cells to be modified, SETF has no choice but
to create some new list structure and store it in the place. As for
giving the implementations permission to modify CDRs of the existing
list structure I don't know of anything implementation tricks that
would make that a good idea but who knows.
> There are almost sure to be programs with the bug of relying on the
> seemingly reasonable behavior. Any function with the purpose of
> modifying a plist, given that plist as an argument, would be likely
> to have that bug.
Yup. Basically, plists aren't really meant to be used that way.
-Peter
--
Peter Seibel * ·····@gigamonkeys.com
Gigamonkeys Consulting * http://www.gigamonkeys.com/
Practical Common Lisp * http://www.gigamonkeys.com/book/
From: Thomas A. Russ
Subject: Re: Call by value, but (please check my hypothesis)
Date:
Message-ID: <ymid5m42gtq.fsf@sevak.isi.edu>
·@b.c writes:
>
> On Wed, 12 Oct 2005 19:38:40 GMT, Peter Seibel <·····@gigamonkeys.com>
> wrote:
>
> >Whether the original list was modified or someplist given a completely
> >new value is not defined.
>
> That sounds bizarre. Is there any lisp where (setf (getf plist key)
> newvalue) actually creates a new plist instead of the seemingly far
> more reasonable behavior of destructively modifying the original
> plist?
What about
(let ((plist nil))
(setf (getf plist :foo) :bar))
what can it destructively modify? It can, however, change the
binding of plist.
> If not, why was it specified that way?
See above. Also, to allow implementations to have options in deciding
what the best way to handle it is. Some testing with ACL 5 shows that
the decision to destructively modify depends on exactly what is being
done. If the value for an existing key is changed, it is done
destructively. If a new key is inserted, new list structure is created.
For example:
USER> (let* ((plist (list :x 3))
(old plist))
(setf (getf plist :y) 10)
(eq old plist))
NIL
USER> (let* ((plist (list :x 3))
(old plist))
(setf (getf plist :x) 10)
(eq old plist))
T
> There are almost sure to be programs with the bug of relying on the
> seemingly reasonable behavior. Any function with the purpose of
> modifying a plist, given that plist as an argument, would be likely to
> have that bug.
Not if coded appropriately to the Spec. There are only a few functions
which are GUARANTEED to be destructive. Most others are ALLOWED, but
not required to be destructive. DELETE vs REMOVE is a case in point and
is often a new user pitfall.
Moral: Don't rely on destructive operations unless the standard
mandates that they be destructive. You can't write portable code if you
make assumptions about what "reasonable behavior" is, because different
vendors and programmers have different ideas of what is reasonable.
--
Thomas A. Russ, USC/Information Sciences Institute
From: tin gherdanarra
Subject: Re: Call by value, but (please check my hypothesis)
Date:
Message-ID: <3r70hqFhq47hU1@individual.net>
Peter Seibel wrote:
> tin gherdanarra <···········@gmail.com> writes:
>
>
>>Dear Lispniks,
>>
>>I understand that Lisp does not pass around references in the sense
>>that only "handles" to lists (as python does, for example).
>
>
> Your understanding is somewhat flawed.
Guilty as charged!
> Lisp does pass around
> references. However a Lisp list and a Python list are different kinds
> of objects.
>
A python list is not a linked list?
>
>>This has the consequence that if I do a (setf (getf '(a 0 b 1 c 2 d
>>3) 'b) 99) it is NOT that getf returns a handle to the "1" and the
>>setf crawls after the spot in memory to replace it with a "2".
>
>
> In this case GETF doesn't return anything; rather SETF knows how to
> set the appropriate place the list that is GETF's second arg. However
> in this case you are invoking undefined behavior since the place that
> you are setting is a literal list.
Aha. This makes sense. GETF is not evaluated by SETF.
>
>
>>setf looks into the generalized variable '(getf (a 0 b 1 c 2 d 3) b)
>>and determines that it has to pull a replacd on the '(a 0 b 1 c 2 d
>>3) to replace the 1 with a 2. In other words, setf uses something
>>like a case to lookup what it has to do with getf...
>
>
> Something like that. However the generalized variable in this case is
> the second form in the GETF form which, as I pointed out above, is not
> a place that you can set with defined behavior.
I thought that setf creates a new list and returns it.
This is why I was baffled at first that setf destructively modifies
a variable with a list.
> However if you had:
>
> (let ((someplist (list 'a 0 'b 1 'c 2 'd 3))
> (setf (getf someplist 'b) 2)
>
> it would work in the sense that the variable someplist would now
> contain:
>
> (a 0 b 2 c2 d 3)
>
> Whether the original list was modified or someplist given a completely
> new value is not defined.
>
>
>>If I have function that does a getf, I have to get this function
>>into setf's lookup table. This can be done with
>>"define-modify-macro".
>
>
> Sort of.
>
>
>
> <http://www.gigamonkeys.com/book/they-called-it-lisp-for-a-reason-list-processing.html>
I have read parts of your book in spring and liked it a lot.
In fact, I am trying to build a better database prothesis
on your example in the book. I skipped the chapter on
lists and conses, though. (Arrogance). I will follow
up to the link after these messages.
>
>>Is there a way out?
>
>
> Almost certainly. What are you actually trying to do?
I want to build something like nested hash tables with
plists. plists are cool for debugging because you can
look at them more easily and manipulate them more easily.
At least, this was the theory.
Thanks
Tin
tin gherdanarra <···········@gmail.com> writes:
> Dear Lispniks,
>
> I understand that Lisp does not pass around
> references in the sense that only "handles"
> to lists (as python does, for example).
>
> This has the consequence that if I do a
> (setf (getf '(a 0 b 1 c 2 d 3) 'b) 99) it
> is NOT that getf returns a handle to
> the "1" and the setf crawls after the spot
> in memory to replace it with a "2".
>
> setf looks into the generalized variable
> '(getf (a 0 b 1 c 2 d 3) b) and determines
> that it has to pull a replacd on the
> '(a 0 b 1 c 2 d 3) to replace the 1 with
> a 2. In other words, setf uses something
> like a case to lookup what it has to do
> with getf...
>
> If I have function that does a getf, I
> have to get this function into
> setf's lookup table. This can be done
> with "define-modify-macro".
This is mostly correct.
There are cases however where setf do call the reader:
(defparameter x (list 1 2 3))
(defparameter y 4)
(setf (car (cdr x)) y)
setf will call (cdr x), obtain (2 3) and
call (fdefinition '(setf car)) with '4 and '(2 3)
> This, however, leads to problems if
> the nesting level of an item in a
> tree is not known in advance. The macro
> is defined and carved in stone at compile-time.
> This means if I have a list like
> (a 0 (b 1 c 2 (d 3 (e 4) f 5) g 6)),
> I cannot walk the tree recursively and
> change to find a certain item and change
> it with setf. This is because I cannot
> make a generalized variable (since it
> is not known at macro compile time how
> deep I will want to go).
> Is this correct?
Not exactly.
You could generate the code to do the tree walking at run-time.
But you still have the problem because your setter is ill defined.
See below.
> Is there a way out?
1- getf doesn't work on trees, only on plist.
2- assuming you write your own tree-getf:
(defun tree-getf (tree indicator &optional default)
(cond
((atom tree) default) ; an improper tree, or the end: NIL
((consp (car tree)) (or (tree-getf (car tree) indicator default)
(tree-getf (cdr tree) indicator default)))
((eql (car tree) indicator) (cadr tree))
(t (tree-getf (cddr tree) indicator default))))
(mapcar (lambda (x) (tree-getf '(a 0 (b 1 c 2 (d 3 (e 4) f 5) g 6)) x))
'(a b c d e f g h))
--> (0 1 2 3 4 5 6 NIL)
you can write a simple corresponding setter:
(defun (setf tree-getf) (value tree indicator &optional default)
(labels ((find-place (tree)
(cond
((atom tree) nil)
((consp (car tree)) (or (find-place (car tree))
(find-place (cdr tree))))
((eql (car tree) indicator) (cdr tree))
(t (find-place (cddr tree))))))
(let ((place (find-place tree)))
(cond
(place (setf (car place) value))
;; Here we have a problem: we would like to prepend on the tree
;; place the new property, but we can't;
;; let's insert it in second position.
(tree (warn "We cannot prepend, we insert in second position")
(setf (cddr tree) (cons indicator (cons value (cddr tree))))
value)
(t (error "We cannot modify NIL"))))))
(defvar tree)
(setf tree (copy-tree '(a 0 (b 1 c 2 (d 3 (e 4) f 5) g 6))))
(mapcar (lambda (x) (setf (tree-getf tree x) 42)) '(a b c d e f g h))
-->
WARNING: We cannot prepend, we insert in second position
(42 42 42 42 42 42 42 42)
tree --> (A 42 H 42 (B 42 C 42 (D 42 (E 42) F 42) G 42))
Unfortunately, So in this case, you see that you'll need to use the complex
define-setf-expander:
(defun find-place (tree indicator)
(cond
((atom tree) nil)
((consp (car tree))
(or (find-place (car tree) indicator)
(find-place (cdr tree) indicator)))
((eql (car tree) indicator) (cdr tree))
(t (find-place (cddr tree) indicator))))
(define-setf-expander tree-getf (tree indicator &optional default
&environment env)
"Set the value associated to the indicator in the p-tree, or
prepend a new p-association if not found."
(declare (ignore default))
;; The simple case is similar, but we need to return the values specified:
(multiple-value-bind (i-dummies i-vals i-newval i-setter i-getter)
(get-setf-expansion indicator env)
(multiple-value-bind (t-dummies t-vals t-newval t-setter t-getter)
(get-setf-expansion tree env)
(let ((store (gensym)))
(values
`(,@i-dummies ,@t-dummies)
`(,@i-vals ,@t-vals)
`(,store)
`(let ((indicator ,i-getter)
(tree ,t-getter))
(let ((place (find-place tree indicator)))
(if place
(progn (rplaca place ,store) ,store)
(progn (cons indicator (cons ,store tree))))))
`(let ((indicator ,i-getter)
(tree ,t-getter))
(let ((place (find-place tree indicator)))
(if place
(car place)
(tree-getf ,t-getter indicator ',default)))))))))
(setf tree (copy-tree '(a 0 (b 1 c 2 (d 3 (e 4) f 5) g 6))))
(mapcar (lambda (x) (incf (tree-getf tree x 0))) '(a b c d e f g h))
--> (1 2 3 4 5 6 7 (H 1 A 1 (B 2 C 3 (D 4 (E 5) F 6) G 7)))
Note however how this accessor is ill defined (well, actually you
didn't specify what should happen when the indicator is not in the
tree or when the tree is NIL, so it's my fault): since H is not in the
tree, it's prepended to it, and as specified, returned. In this case,
the setf-expander expand to the place tree instead of the place
(tree-getf tree x 0). Some times we have to modify a car in the tree,
some times we have to modify the tree variable. Bad. To avoid this
inconsistency, we'd have to specify that a tree has always a header,
perhaps a structure:
(defstruct tree nodes)
so you cannot call: (let ((tree nil)) (setf (tree-getf tree 'x) 'v))
but you have to do: (let ((tree (make-tree))) (setf (tree-getf tree 'x) 'v))
The the setf-expansion would be normal.
Finally, note that as implemented, with calls such as:
(incf (tree-getf tree indicator 0) value)
find-place is called twice. (If this is a problem, you could cache one result).
--
__Pascal Bourguignon__ http://www.informatimago.com/