Hi,
Is there any way to get some kind of mutable reference to a field in a
structure? Something like this:
(defstruct foo field)
(defvar foo-instance (make-foo))
(setf (foo-field foo-instance) 1)
(defvar ref (get-reference-to-struct-field foo field-1))
(setf (deref ref) 2)
(foo-field foo-instance) => 2
So far, all I can think of is using a closure:
(defvar foo-instance (make-foo))
(setf (foo-field foo-instance) 1)
(defvar ref (lambda (x) (setf (foo-field foo-instance) x)))
(funcall ref 2)
(foo-field foo-instance) => 2
This works OK, but in the program I'm working on the number of
references could get quite large, and (I assume that) every closure
created pushes some stuff onto the stack.
In case I'm barking up the wrong tree altogether, this is my actual
problem. I'm traversing a parse tree, simulating recursion by looping
and pushing nodes in the tree onto a stack. Most of the nodes in the
tree I want to leave alone, but there are a few I want to modify. This
would be much easier if there was some way to modify a node without
knowing what its parent node is. (The nodes in the tree are represented
as structures.)
Thanks,
Alex
In article <·············@uns-a.ucl.ac.uk>,
Alex Drummond <··········@ucl.ac.uk> wrote:
> So far, all I can think of is using a closure:
>
> (defvar foo-instance (make-foo))
> (setf (foo-field foo-instance) 1)
> (defvar ref (lambda (x) (setf (foo-field foo-instance) x)))
> (funcall ref 2)
> (foo-field foo-instance) => 2
>
> This works OK, but in the program I'm working on the number of
> references could get quite large, and (I assume that) every closure
> created pushes some stuff onto the stack.
I don't see why you would assume that. A closure persists *after* the
function that created it has exited and its stack frame has been popped,
so nothing is pushed on the stack. Closures are the normal way to
implement what you're trying to do.
FYI, Lisp Machines have an object called a "locative" that implements a
reference to an arbitrary data cell, so you might use this on a LispM.
However, this mechanism is not portable.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
From: Alex Drummond
Subject: Re: Mutable reference to a structure field
Date:
Message-ID: <cb02aj$sle$1@uns-a.ucl.ac.uk>
I'm a bit confused about this now. Surely if I (say) created a big list
of closures, that would have to take up some stack space? Isn't the
environment that the closure captures stored on the stack in some way?
(Yes, my knowledge of Lisp implementation is lacking...)
Alex
Barry Margolin wrote:
> In article <·············@uns-a.ucl.ac.uk>,
> Alex Drummond <··········@ucl.ac.uk> wrote:
>
>
>>So far, all I can think of is using a closure:
>>
>>(defvar foo-instance (make-foo))
>>(setf (foo-field foo-instance) 1)
>>(defvar ref (lambda (x) (setf (foo-field foo-instance) x)))
>>(funcall ref 2)
>>(foo-field foo-instance) => 2
>>
>>This works OK, but in the program I'm working on the number of
>>references could get quite large, and (I assume that) every closure
>>created pushes some stuff onto the stack.
>
>
> I don't see why you would assume that. A closure persists *after* the
> function that created it has exited and its stack frame has been popped,
> so nothing is pushed on the stack. Closures are the normal way to
> implement what you're trying to do.
>
> FYI, Lisp Machines have an object called a "locative" that implements a
> reference to an arbitrary data cell, so you might use this on a LispM.
> However, this mechanism is not portable.
>
From: Joe Marshall
Subject: Re: Mutable reference to a structure field
Date:
Message-ID: <8yek1i4m.fsf@comcast.net>
Alex Drummond <··········@ucl.ac.uk> writes:
> I'm a bit confused about this now. Surely if I (say) created a big
> list of closures, that would have to take up some stack space? Isn't
> the environment that the closure captures stored on the stack in some
> way?
They would more likely be stored in the heap. If the compiler
determines that a closure is needed, it arranges to move the stack
allocated variables to the heap.
--
~jrm
From: Alex Drummond
Subject: Re: Mutable reference to a structure field
Date:
Message-ID: <cb03ql$slm$2@uns-a.ucl.ac.uk>
OK, I suppose that means using closures isn't as bad as I thought, thanks :)
Alex
Joe Marshall wrote:
> Alex Drummond <··········@ucl.ac.uk> writes:
>
>
>>I'm a bit confused about this now. Surely if I (say) created a big
>>list of closures, that would have to take up some stack space? Isn't
>>the environment that the closure captures stored on the stack in some
>>way?
>
>
> They would more likely be stored in the heap. If the compiler
> determines that a closure is needed, it arranges to move the stack
> allocated variables to the heap.
>
In article <·············@uns-a.ucl.ac.uk>,
Alex Drummond <··········@ucl.ac.uk> wrote:
> In case I'm barking up the wrong tree altogether, this is my actual
> problem. I'm traversing a parse tree, simulating recursion by looping
> and pushing nodes in the tree onto a stack. Most of the nodes in the
> tree I want to leave alone, but there are a few I want to modify. This
> would be much easier if there was some way to modify a node without
> knowing what its parent node is. (The nodes in the tree are represented
> as structures.)
I wonder why you feel the need to use iteration to do an obviously
recursive process. Chances are if you're building a stack, you should
probably just write it recursively and let the language do it for you.
As far as being able to change the parent, my first reading of your
question seems to indicate that what you're changing is a slot in the
current node. There's no reason to need the parent for that, just (setf
(slot node) new-value). If you need to change a slot in the parent, as
far as I know there are no locatives in Common Lisp, so you really will
have to hold onto a node's parent. However, even if you could get a
C-like pointer to a parent node's slot you'd still need to pass /that/
pointer, which seems like just as much work.
Personally, I would do it like (in a binary tree):
(defun traverse-internal (node parent)
(when node
(traverse-internal (left node) node)
;; You can do stuff to node here or its parent.
;; parent will be nil if node is the root of the tree.
(traverse-internal (right node) node)))
(defun traverse (tree)
(traverse-internal tree nil))
You can mangle that into iteration with an explicitly managed stack if
you feel the need.
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
From: Alex Drummond
Subject: Re: Mutable reference to a structure field
Date:
Message-ID: <cb01js$sl6$1@uns-a.ucl.ac.uk>
Thanks for the reply,
I take your point about recursion/iteration. The only reason I'm using
iteration is because it's really no more difficult in this case, and it
ought to scale better.
The trouble is that there is no uniform means of obtaining the children
of a node in the parse tree (e.g. a binary operator node structure has
different fields to a unary operator node structure, etc.) So if I
wanted to:
a) Take a look at the children of the current node.
b) Possibly do something to them.
I would have to first find out which of various structure types the node
was (in order to look at its children), and /then/ find out which of
various structure types its children were (in order to work out what to
do with them), which would result in massive code duplication.
I could perhaps first build up a list of the children of the current
node (whatever its type may be) and then operate on that list, but of
course I would again need references to the nodes, bringing me back to
my original problem.
I should say that I'm quite prepared to get "tough luck" as an answer to
my question. Probably I ought to use a better representation of parse
trees or something. But it would be nice if there was a better quick and
dirty solution than the closures method I explained in my last post. And
it is a shame that there doesn't appear to be one in Common Lisp. For
all its elegance and power, one of the nicest things about the language
in my experience is that since it isn't in thrall to a particular
paradigm, you can almost always do things using whichever method seems
most intuitive, rather than bending your mind to fit the language.
Alex
Brian Downing wrote:
> In article <·············@uns-a.ucl.ac.uk>,
> Alex Drummond <··········@ucl.ac.uk> wrote:
>
>>In case I'm barking up the wrong tree altogether, this is my actual
>>problem. I'm traversing a parse tree, simulating recursion by looping
>>and pushing nodes in the tree onto a stack. Most of the nodes in the
>>tree I want to leave alone, but there are a few I want to modify. This
>>would be much easier if there was some way to modify a node without
>>knowing what its parent node is. (The nodes in the tree are represented
>>as structures.)
>
>
> I wonder why you feel the need to use iteration to do an obviously
> recursive process. Chances are if you're building a stack, you should
> probably just write it recursively and let the language do it for you.
>
> As far as being able to change the parent, my first reading of your
> question seems to indicate that what you're changing is a slot in the
> current node. There's no reason to need the parent for that, just (setf
> (slot node) new-value). If you need to change a slot in the parent, as
> far as I know there are no locatives in Common Lisp, so you really will
> have to hold onto a node's parent. However, even if you could get a
> C-like pointer to a parent node's slot you'd still need to pass /that/
> pointer, which seems like just as much work.
>
> Personally, I would do it like (in a binary tree):
>
> (defun traverse-internal (node parent)
> (when node
> (traverse-internal (left node) node)
> ;; You can do stuff to node here or its parent.
> ;; parent will be nil if node is the root of the tree.
> (traverse-internal (right node) node)))
>
> (defun traverse (tree)
> (traverse-internal tree nil))
>
> You can mangle that into iteration with an explicitly managed stack if
> you feel the need.
>
> -bcd
In article <············@uns-a.ucl.ac.uk>,
Alex Drummond <··········@ucl.ac.uk> wrote:
> The trouble is that there is no uniform means of obtaining the children
> of a node in the parse tree (e.g. a binary operator node structure has
> different fields to a unary operator node structure, etc.) So if I
> wanted to:
> a) Take a look at the children of the current node.
> b) Possibly do something to them.
> I would have to first find out which of various structure types the node
> was (in order to look at its children), and /then/ find out which of
> various structure types its children were (in order to work out what to
> do with them), which would result in massive code duplication.
>
> I could perhaps first build up a list of the children of the current
> node (whatever its type may be) and then operate on that list, but of
> course I would again need references to the nodes, bringing me back to
> my original problem.
I'm pretty sure I'm barking up the wrong tree here, since most of this
isn't making sense to me. I'm confused as to why you have different
structures for different aritys of operators, but I confess I've not
done a lot with parsers. And I'm still rather confused as to how you
would use locatives to solve this problem.
It does sounds like you're describing dispatch issues, though. You
might want to investigate CLOS if you wish to keep this tree format.
(defgeneric traverse (node parent))
(defmethod traverse ((node unary-node) parent)
;; operate on a unary node
)
(defmethod traverse ((node binary-node) parent)
;; operate on a binary node
)
(defmethod traverse ((node binary-node) (parent unary-node))
;; operate on a binary node with a unary parent
)
It sounds like you should really rethink your data structure, though.
(Actually, I'd investigate CLOS even if you change data structures.)
-bcd
--
*** Brian Downing <bdowning at lavos dot net>
From: Alex Drummond
Subject: Re: Mutable reference to a structure field
Date:
Message-ID: <cb03p4$slm$1@uns-a.ucl.ac.uk>
> I'm pretty sure I'm barking up the wrong tree here, since most of this
> isn't making sense to me. I'm confused as to why you have different
> structures for different aritys of operators, but I confess I've not
> done a lot with parsers. And I'm still rather confused as to how you
> would use locatives to solve this problem.
Well, let's say I was parsing C (which I'm not, but it will do as an
example):
void foo(int a, int b)
{
return (a + b);
}
Presumably, the node in the parse tree representing the function
definition above would have a field containing a list of the function's
arguments, and a field containing the body of the function. Both of
these are "children" of the function definition node, but it's not
obvious that they should be stored in the same way as the children of
the node holding the expression (a + b). In retrospect it would have
been nice to have a unified way of getting the children of a parse tree
node, but it wasn't clear I'd need this when I wrote the parser.
The CLOS idea is interesting though, thanks.
Alex
Brian Downing wrote:
> In article <············@uns-a.ucl.ac.uk>,
> Alex Drummond <··········@ucl.ac.uk> wrote:
>
>>The trouble is that there is no uniform means of obtaining the children
>>of a node in the parse tree (e.g. a binary operator node structure has
>>different fields to a unary operator node structure, etc.) So if I
>>wanted to:
>> a) Take a look at the children of the current node.
>> b) Possibly do something to them.
>>I would have to first find out which of various structure types the node
>>was (in order to look at its children), and /then/ find out which of
>>various structure types its children were (in order to work out what to
>>do with them), which would result in massive code duplication.
>>
>>I could perhaps first build up a list of the children of the current
>>node (whatever its type may be) and then operate on that list, but of
>>course I would again need references to the nodes, bringing me back to
>>my original problem.
>
>
> I'm pretty sure I'm barking up the wrong tree here, since most of this
> isn't making sense to me. I'm confused as to why you have different
> structures for different aritys of operators, but I confess I've not
> done a lot with parsers. And I'm still rather confused as to how you
> would use locatives to solve this problem.
>
> It does sounds like you're describing dispatch issues, though. You
> might want to investigate CLOS if you wish to keep this tree format.
>
> (defgeneric traverse (node parent))
> (defmethod traverse ((node unary-node) parent)
> ;; operate on a unary node
> )
> (defmethod traverse ((node binary-node) parent)
> ;; operate on a binary node
> )
> (defmethod traverse ((node binary-node) (parent unary-node))
> ;; operate on a binary node with a unary parent
> )
>
> It sounds like you should really rethink your data structure, though.
>
> (Actually, I'd investigate CLOS even if you change data structures.)
>
> -bcd
Alex Drummond <··········@ucl.ac.uk> writes:
> > I'm pretty sure I'm barking up the wrong tree here, since most of this
> > isn't making sense to me. I'm confused as to why you have different
> > structures for different aritys of operators, but I confess I've not
> > done a lot with parsers. And I'm still rather confused as to how you
> > would use locatives to solve this problem.
>
> Well, let's say I was parsing C (which I'm not, but it will do as an
> example):
>
> void foo(int a, int b)
> {
> return (a + b);
> }
>
> Presumably, the node in the parse tree representing the function
> definition above would have a field containing a list of the
> function's arguments, and a field containing the body of the
> function.
One representation would be sexps. For the above sample, that would give:
(foo ((a int) (b int)) void ((return (+ a b))))
(defmacro fun-name (x) `(first ,x))
(defmacro fun-arguments (x) `(second ,x))
(defmacro fun-result-type (x) `(third ,x))
(defmacro fun-body (x) `(fourth ,x))
Then you can easily walk the syntax tree, because it's a pure lisp tree.
Another would be to add a children method to your nodes.
(defmethod children ((node unary-operator)) (list (argument node)))
(defmethod children ((node binary-operator)) (list (left-arg node)
(right-arg node)))
;; ...
(defmethod children ((node variadic-operator)) (arguments node))
(defmethod children ((node if-statement)) (list (condition node)
(then node) (else node)))
(defmethod children ((node while-statement)) (list (condition node)
(body node)))
;; ...
So you can get the list of children of a node just calling the
children generic function.
There's a lot of possibilities. For example, when you define
structures, you can specify the kind of implementation you want for
them. In particular you can ask for a list implementation so you
could use car/cdr on the "structure".
[19]> (defstruct (if-statement (:type list)) condition then else)
IF-STATEMENT
[20]> (make-if-statement :condition '(= a b) :then '(print a) :else '(print (- a b)))
((= A B) (PRINT A) (PRINT (- A B)))
[21]> (map nil (function print) (make-if-statement :condition '(= a b) :then '(print a) :else '(print (- a b))))
(= A B)
(PRINT A)
(PRINT (- A B))
NIL
> Both of these are "children" of the function definition
> node, but it's not obvious that they should be stored in the same way
> as the children of the node holding the expression (a + b). In
> retrospect it would have been nice to have a unified way of getting
> the children of a parse tree node, but it wasn't clear I'd need this
> when I wrote the parser.
>
> The CLOS idea is interesting though, thanks.
--
__Pascal Bourguignon__ http://www.informatimago.com/
There is no worse tyranny than to force a man to pay for what he does not
want merely because you think it would be good for him. -- Robert Heinlein
Alex Drummond wrote:
> Thanks for the reply,
>
> I take your point about recursion/iteration. The only reason I'm using
> iteration is because it's really no more difficult in this case, and it
> ought to scale better.
>
> The trouble is that there is no uniform means of obtaining the children
> of a node in the parse tree (e.g. a binary operator node structure has
> different fields to a unary operator node structure, etc.) So if I
> wanted to:
> a) Take a look at the children of the current node.
> b) Possibly do something to them.
> I would have to first find out which of various structure types the node
> was (in order to look at its children), and /then/ find out which of
> various structure types its children were (in order to work out what to
> do with them), which would result in massive code duplication.
>
> I could perhaps first build up a list of the children of the current
> node (whatever its type may be) and then operate on that list, but of
> course I would again need references to the nodes, bringing me back to
> my original problem.
>
> I should say that I'm quite prepared to get "tough luck" as an answer to
> my question. Probably I ought to use a better representation of parse
> trees or something. But it would be nice if there was a better quick and
> dirty solution than the closures method I explained in my last post. And
> it is a shame that there doesn't appear to be one in Common Lisp.
Would generic functions suffice? Nothing fancy either, just good old
single-dispatch polymorphism seems to be your goal:
(defmethod node-children ((opcode binary-operator))
...etc...)
If you expect a huge variety of types which cannot be determined at run
time, then you might want to look at using the MOP to define a new type
of metaclass, or (more simply) just kinda toss off a poor man's OO
representation which you can tailor to suit whatever generic handling
your application requires.
But vanilla CLOS generic functions have a ton of flexibility so you
might just get by with that.
I suggest you post any specific problem you have (eg, diff children for
diff operators was a good one) and then see if folks here can provide
specific solutions.
But there won't be any 'tough luck' remarks because at worst you toss
off in a few insanely easy and enjoyable hours your own little meta-info
hack using cool Lisp capabilities such as reflection (introspection?)
and macros and then you understand both famous quotes: "programmable
programming language" and Graham's Lisp-DNA comparison.
kenny
For
> all its elegance and power, one of the nicest things about the language
> in my experience is that since it isn't in thrall to a particular
> paradigm, you can almost always do things using whichever method seems
> most intuitive, rather than bending your mind to fit the language.
>
> Alex
>
> Brian Downing wrote:
>
>> In article <·············@uns-a.ucl.ac.uk>,
>> Alex Drummond <··········@ucl.ac.uk> wrote:
>>
>>> In case I'm barking up the wrong tree altogether, this is my actual
>>> problem. I'm traversing a parse tree, simulating recursion by looping
>>> and pushing nodes in the tree onto a stack. Most of the nodes in the
>>> tree I want to leave alone, but there are a few I want to modify.
>>> This would be much easier if there was some way to modify a node
>>> without knowing what its parent node is. (The nodes in the tree are
>>> represented as structures.)
>>
>>
>>
>> I wonder why you feel the need to use iteration to do an obviously
>> recursive process. Chances are if you're building a stack, you should
>> probably just write it recursively and let the language do it for you.
>>
>> As far as being able to change the parent, my first reading of your
>> question seems to indicate that what you're changing is a slot in the
>> current node. There's no reason to need the parent for that, just (setf
>> (slot node) new-value). If you need to change a slot in the parent, as
>> far as I know there are no locatives in Common Lisp, so you really will
>> have to hold onto a node's parent. However, even if you could get a
>> C-like pointer to a parent node's slot you'd still need to pass /that/
>> pointer, which seems like just as much work.
>>
>> Personally, I would do it like (in a binary tree):
>>
>> (defun traverse-internal (node parent)
>> (when node
>> (traverse-internal (left node) node)
>> ;; You can do stuff to node here or its parent.
>> ;; parent will be nil if node is the root of the tree.
>> (traverse-internal (right node) node)))
>>
>> (defun traverse (tree)
>> (traverse-internal tree nil))
>>
>> You can mangle that into iteration with an explicitly managed stack if
>> you feel the need.
>>
>> -bcd
--
Home? http://tilton-technology.com
Cells? http://www.common-lisp.net/project/cells/
Cello? http://www.common-lisp.net/project/cello/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
Can't seem to find the original article on my Newsreader:
> In article <·············@uns-a.ucl.ac.uk>,
> Alex Drummond <··········@ucl.ac.uk> wrote:
> > In case I'm barking up the wrong tree altogether, this is my actual
> > problem. I'm traversing a parse tree, simulating recursion by looping
> > and pushing nodes in the tree onto a stack. Most of the nodes in the
> > tree I want to leave alone, but there are a few I want to modify. This
> > would be much easier if there was some way to modify a node without
> > knowing what its parent node is. (The nodes in the tree are represented
> > as structures.)
Here's an interesting thought: If instead of using DEFSTRUCT
structures, perhaps you should use CLOS instances.
If you had to change the node, you could do either of the following:
(a) If all that is needed is to change slot values, you just set them.
(b) If more extensive changes are needed, you can invoke CHANGE-CLASS on
the instance representing the node. CLOS requires that the changed
instance be EQ to the original. In fact, you may be able to put most of
the logic for actually making the changes into the
UPDATE-INSTANCE-FOR-CHANGED-CLASS methods, since that is invoked with
the instance that has just had its class changed, as well as a copy of
what the instance looked like before the change.
Since the instance has to be EQ, any pointers to the instance from
anywhere in Lisp would still be valid. And you could make pretty much
any changes you wanted to the actual node. The only restriction is that
all of the objects you manipulate need to be CLOS objects. This would
mean you couldn't change a STRING into a FIXNUM, since they are not CLOS
objects.
--
Thomas A. Russ, USC/Information Sciences Institute
From: Marco Baringer
Subject: Re: Mutable reference to a structure field
Date:
Message-ID: <m2659oj8dp.fsf@convey.it>
Alex Drummond <··········@ucl.ac.uk> writes:
> So far, all I can think of is using a closure:
>
> (defvar foo-instance (make-foo))
> (setf (foo-field foo-instance) 1)
> (defvar ref (lambda (x) (setf (foo-field foo-instance) x)))
> (funcall ref 2)
> (foo-field foo-instance) => 2
personally i think a generic function approach would be better for
your specific problem, however implementing references (or places as
i've called them), is trivial:
(defmacro make-place (form)
"Returns an objecting representing the place FORM."
(with-unique-names (v)
`(cons (lambda () ,form)
(lambda (,v) (setf ,form ,v)))))
(defun value-of (place)
"Returns the value(s) associated with the place PLACE."
(funcall (car place)))
(defun (setf value-of) (new-value place)
"Sets the value of PLACE to NEW-VALUE."
(funcall (cdr place) new-value))
--
-Marco
Ring the bells that still can ring.
Forget your perfect offering.
There is a crack in everything.
That's how the light gets in.
-Leonard Cohen
Marco Baringer <··@bese.it> writes:
> personally i think a generic function approach would be better for
> your specific problem, however implementing references (or places as
> i've called them), is trivial:
Well yeah, if you disregard side effects in subforms of the
place, and VALUES forms as places.
(let ((x 0))
(make-place (aref "vector" (incf x)))
x)
;; should be 1; but is 0
(let* (x y (place (make-place (values x y))))
(setf (value-of place) (values 1 2))
(value-of place))
;; should be 1, 2; but is 1, NIL
I don't know whether the LispMs got these cases right.
Kalle Olavi Niemitalo <···@iki.fi> writes:
> Marco Baringer <··@bese.it> writes:
> > personally i think a generic function approach would be better for
> > your specific problem, however implementing references (or places as
> > i've called them), is trivial:
> Well yeah, if you disregard side effects in subforms of the
> place, and VALUES forms as places.
It's still not that hard to get it right:
http://www.hexapodia.net/pipermail/small-cl-src/2004-June/000016.html
--
Lars Brinkhoff, Services for Unix, Linux, GCC, HTTP
Brinkhoff Consulting http://www.brinkhoff.se/