Hi, I'm practicing common lisp by trying to write a binary tree with
nodes in the form (key left right . data). What I'd like to write
looks something like this,
<code>
(defun insert (key data &optional (node *root*))
(progn
(if (null *root*)
(setf *root* (make-node key data)))
(destructuring-bind (k l r . d) node
(if (funcall test k key)
(setf node (make-node key data l r))
(insert key data (if (funcall cmp k key)
l
r))))))
</code>
but obviously this isn't working. In the places where I'm using setf,
I know that all I'm doing is re-setting the variable in the local
scope, but I'm wondering if there's some way to pass around the place
of the node (like passing around handles (pointers to pointers)) in
c? Maybe there's a more lispy way of doing this, if so I'd love to
see it.
From: Ari Johnson
Subject: Re: newbie question: is there something analogous to handles in CL?
Date:
Message-ID: <m2hcfvgmaz.fsf@hermes.theari.com>
jc <··········@gmail.com> writes:
> Hi, I'm practicing common lisp by trying to write a binary tree with
> nodes in the form (key left right . data). What I'd like to write
> looks something like this,
>
> <code>
> (defun insert (key data &optional (node *root*))
> (progn
> (if (null *root*)
> (setf *root* (make-node key data)))
> (destructuring-bind (k l r . d) node
> (if (funcall test k key)
> (setf node (make-node key data l r))
> (insert key data (if (funcall cmp k key)
> l
> r))))))
> </code>
>
> but obviously this isn't working. In the places where I'm using setf,
> I know that all I'm doing is re-setting the variable in the local
> scope, but I'm wondering if there's some way to pass around the place
> of the node (like passing around handles (pointers to pointers)) in
> c? Maybe there's a more lispy way of doing this, if so I'd love to
> see it.
This isn't all of your code, of course, but to answer your concerns
you have a few good options.
One thing to consider is using structs. That's what they're there
for. Another thing to think about is how NREVERSE works. It
destructively reverses a list and then returns the new head of the
list. That's why you do (setf x (nreverse x)) instead of just
(nreverse x).
Consider:
(defstruct (node (:constructor %make-node)) key data left-child right-child)
(defun make-node (key data)
(%make-node :key key :data data))
(defun node-leaf-p (node)
(declare (type (node node)))
(and (not (node-left-child node)) (not (node-right-child node))))
(defun insert-node (node tree &key (compare #'<) (equalp #'=))
(declare (type (node node))
(type ((or node nil) tree)))
(assert (or (not tree)
(not (funcall equalp (node-key node) (node-key tree)))))
(cond ((null tree) node)
((funcall compare (node-key node) (node-key tree))
(setf (node-left-child tree)
(insert-node node (node-left-child tree)))
tree)
(t
(setf (node-right-child tree)
(insert-node node (node-right-child tree)))
tree)))
(defvar *root* nil)
(setf *root* (insert-node (make-node 3 "three") *root*))
(setf *root* (insert-node (make-node 2 "two") *root*))
(pprint *root*)
==>
#S(NODE :KEY 3 :DATA "three"
:LEFT-CHILD #S(NODE :KEY 2 :DATA "two" :LEFT-CHILD NIL
:RIGHT-CHILD NIL)
:RIGHT-CHILD NIL)
This is almost certainly wordier than needed. I'll defer to the
experts who respond to say so.
On Feb 26, 6:33 pm, Ari Johnson <·········@gmail.com> wrote:
> jc <··········@gmail.com> writes:
> > Hi, I'm practicing common lisp by trying to write a binary tree with
> > nodes in the form (key left right . data). What I'd like to write
> > looks something like this,
>
> > <code>
> > (defun insert (key data &optional (node *root*))
> > (progn
> > (if (null *root*)
> > (setf *root* (make-node key data)))
> > (destructuring-bind (k l r . d) node
> > (if (funcall test k key)
> > (setf node (make-node key data l r))
> > (insert key data (if (funcall cmp k key)
> > l
> > r))))))
> > </code>
>
> > but obviously this isn't working. In the places where I'm using setf,
> > I know that all I'm doing is re-setting the variable in the local
> > scope, but I'm wondering if there's some way to pass around the place
> > of the node (like passing around handles (pointers to pointers)) in
> > c? Maybe there's a more lispy way of doing this, if so I'd love to
> > see it.
>
> This isn't all of your code, of course, but to answer your concerns
> you have a few good options.
>
> One thing to consider is using structs. That's what they're there
> for. Another thing to think about is how NREVERSE works. It
> destructively reverses a list and then returns the new head of the
> list. That's why you do (setf x (nreverse x)) instead of just
> (nreverse x).
>
> Consider:
>
> (defstruct (node (:constructor %make-node)) key data left-child right-child)
>
> (defun make-node (key data)
> (%make-node :key key :data data))
>
> (defun node-leaf-p (node)
> (declare (type (node node)))
> (and (not (node-left-child node)) (not (node-right-child node))))
>
> (defun insert-node (node tree &key (compare #'<) (equalp #'=))
> (declare (type (node node))
> (type ((or node nil) tree)))
> (assert (or (not tree)
> (not (funcall equalp (node-key node) (node-key tree)))))
> (cond ((null tree) node)
> ((funcall compare (node-key node) (node-key tree))
> (setf (node-left-child tree)
> (insert-node node (node-left-child tree)))
> tree)
> (t
> (setf (node-right-child tree)
> (insert-node node (node-right-child tree)))
> tree)))
>
> (defvar *root* nil)
>
> (setf *root* (insert-node (make-node 3 "three") *root*))
> (setf *root* (insert-node (make-node 2 "two") *root*))
> (pprint *root*)
> ==>
> #S(NODE :KEY 3 :DATA "three"
> :LEFT-CHILD #S(NODE :KEY 2 :DATA "two" :LEFT-CHILD NIL
> :RIGHT-CHILD NIL)
> :RIGHT-CHILD NIL)
>
> This is almost certainly wordier than needed. I'll defer to the
> experts who respond to say so.
Those are great suggestions, but just as an exercise I'm trying pare
things down to the bare minimum. I was trying to avoid non-list data
structures, parent links, and non-tail recursion, maybe making the
algorithm impossible? I'm not sure.
On Feb 26, 8:06 pm, jc <··········@gmail.com> wrote:
> On Feb 26, 6:33 pm, Ari Johnson <·········@gmail.com> wrote:
>
>
>
> > jc <··········@gmail.com> writes:
> > > Hi, I'm practicing common lisp by trying to write a binary tree with
> > > nodes in the form (key left right . data). What I'd like to write
> > > looks something like this,
>
> > > <code>
> > > (defun insert (key data &optional (node *root*))
> > > (progn
> > > (if (null *root*)
> > > (setf *root* (make-node key data)))
> > > (destructuring-bind (k l r . d) node
> > > (if (funcall test k key)
> > > (setf node (make-node key data l r))
> > > (insert key data (if (funcall cmp k key)
> > > l
> > > r))))))
> > > </code>
>
> > > but obviously this isn't working. In the places where I'm using setf,
> > > I know that all I'm doing is re-setting the variable in the local
> > > scope, but I'm wondering if there's some way to pass around the place
> > > of the node (like passing around handles (pointers to pointers)) in
> > > c? Maybe there's a more lispy way of doing this, if so I'd love to
> > > see it.
>
> > This isn't all of your code, of course, but to answer your concerns
> > you have a few good options.
>
> > One thing to consider is using structs. That's what they're there
> > for. Another thing to think about is how NREVERSE works. It
> > destructively reverses a list and then returns the new head of the
> > list. That's why you do (setf x (nreverse x)) instead of just
> > (nreverse x).
>
> > Consider:
>
> > (defstruct (node (:constructor %make-node)) key data left-child right-child)
>
> > (defun make-node (key data)
> > (%make-node :key key :data data))
>
> > (defun node-leaf-p (node)
> > (declare (type (node node)))
> > (and (not (node-left-child node)) (not (node-right-child node))))
>
> > (defun insert-node (node tree &key (compare #'<) (equalp #'=))
> > (declare (type (node node))
> > (type ((or node nil) tree)))
> > (assert (or (not tree)
> > (not (funcall equalp (node-key node) (node-key tree)))))
> > (cond ((null tree) node)
> > ((funcall compare (node-key node) (node-key tree))
> > (setf (node-left-child tree)
> > (insert-node node (node-left-child tree)))
> > tree)
> > (t
> > (setf (node-right-child tree)
> > (insert-node node (node-right-child tree)))
> > tree)))
>
> > (defvar *root* nil)
>
> > (setf *root* (insert-node (make-node 3 "three") *root*))
> > (setf *root* (insert-node (make-node 2 "two") *root*))
> > (pprint *root*)
> > ==>
> > #S(NODE :KEY 3 :DATA "three"
> > :LEFT-CHILD #S(NODE :KEY 2 :DATA "two" :LEFT-CHILD NIL
> > :RIGHT-CHILD NIL)
> > :RIGHT-CHILD NIL)
>
> > This is almost certainly wordier than needed. I'll defer to the
> > experts who respond to say so.
>
> Those are great suggestions, but just as an exercise I'm trying pare
> things down to the bare minimum. I was trying to avoid non-list data
> structures, parent links, and non-tail recursion, maybe making the
> algorithm impossible? I'm not sure.
Wait, I just answered my own question. The function can keep track of
the parent node instead of making it part of the data. But still,
I've run into this situation where I'm wishing for pointers (god
forbid) while messing around with other things in lisp. For instance,
some way to do
(setq x 'a)
(setq (the-name-inside x) 25)
a
==> 25
On Feb 26, 8:28 pm, jc <··········@gmail.com> wrote:
> On Feb 26, 8:06 pm, jc <··········@gmail.com> wrote:
>
>
>
>
>
> > On Feb 26, 6:33 pm, Ari Johnson <·········@gmail.com> wrote:
>
> > > jc <··········@gmail.com> writes:
> > > > Hi, I'm practicing common lisp by trying to write a binary tree with
> > > > nodes in the form (key left right . data). What I'd like to write
> > > > looks something like this,
>
> > > > <code>
> > > > (defun insert (key data &optional (node *root*))
> > > > (progn
> > > > (if (null *root*)
> > > > (setf *root* (make-node key data)))
> > > > (destructuring-bind (k l r . d) node
> > > > (if (funcall test k key)
> > > > (setf node (make-node key data l r))
> > > > (insert key data (if (funcall cmp k key)
> > > > l
> > > > r))))))
> > > > </code>
>
> > > > but obviously this isn't working. In the places where I'm using setf,
> > > > I know that all I'm doing is re-setting the variable in the local
> > > > scope, but I'm wondering if there's some way to pass around the place
> > > > of the node (like passing around handles (pointers to pointers)) in
> > > > c? Maybe there's a more lispy way of doing this, if so I'd love to
> > > > see it.
>
> > > This isn't all of your code, of course, but to answer your concerns
> > > you have a few good options.
>
> > > One thing to consider is using structs. That's what they're there
> > > for. Another thing to think about is how NREVERSE works. It
> > > destructively reverses a list and then returns the new head of the
> > > list. That's why you do (setf x (nreverse x)) instead of just
> > > (nreverse x).
>
> > > Consider:
>
> > > (defstruct (node (:constructor %make-node)) key data left-child right-child)
>
> > > (defun make-node (key data)
> > > (%make-node :key key :data data))
>
> > > (defun node-leaf-p (node)
> > > (declare (type (node node)))
> > > (and (not (node-left-child node)) (not (node-right-child node))))
>
> > > (defun insert-node (node tree &key (compare #'<) (equalp #'=))
> > > (declare (type (node node))
> > > (type ((or node nil) tree)))
> > > (assert (or (not tree)
> > > (not (funcall equalp (node-key node) (node-key tree)))))
> > > (cond ((null tree) node)
> > > ((funcall compare (node-key node) (node-key tree))
> > > (setf (node-left-child tree)
> > > (insert-node node (node-left-child tree)))
> > > tree)
> > > (t
> > > (setf (node-right-child tree)
> > > (insert-node node (node-right-child tree)))
> > > tree)))
>
> > > (defvar *root* nil)
>
> > > (setf *root* (insert-node (make-node 3 "three") *root*))
> > > (setf *root* (insert-node (make-node 2 "two") *root*))
> > > (pprint *root*)
> > > ==>
> > > #S(NODE :KEY 3 :DATA "three"
> > > :LEFT-CHILD #S(NODE :KEY 2 :DATA "two" :LEFT-CHILD NIL
> > > :RIGHT-CHILD NIL)
> > > :RIGHT-CHILD NIL)
>
> > > This is almost certainly wordier than needed. I'll defer to the
> > > experts who respond to say so.
>
> > Those are great suggestions, but just as an exercise I'm trying pare
> > things down to the bare minimum. I was trying to avoid non-list data
> > structures, parent links, and non-tail recursion, maybe making the
> > algorithm impossible? I'm not sure.
>
> Wait, I just answered my own question. The function can keep track of
> the parent node instead of making it part of the data. But still,
> I've run into this situation where I'm wishing for pointers (god
> forbid) while messing around with other things in lisp. For instance,
> some way to do
>
> (setq x 'a)
Always use DEFVAR or DEFPARAMETER to define a global variable.
> (setq (the-name-inside x) 25)
> a
There is a classic Lisp function which does this called SET.
(defvar a)
(defvar x 'a)
(set x 25)
a -> 25
Set is a function that takes a symbol object its argument, and
modifies the SYMBOL-VALUE slot of that symbol to the given value. It
doesn't honor lexical scopes.
This isn't anything that you can trivally do in many programming
languages, particularly ones typified by C and the like. You're
passing around a name of a variable and using that to assign to it. In
C, names disappear when you compile (except if they are retained in a
limited way for debugging).
In Lisp, pointers are used implicitly to represent any object that
needs to be ``boxed''. But storage locations are not first-class
objects; you cannot have direct references to them. There is no
uniform access to storage locations; it depends what kind they are.
E.g. assigning to an array slot is different from assigning to a
variable: (setf variable value) versus (setf (aref array ...) value).
However, in Lisp you /can/ ``take the address'' of all of the lexical
variables in scope by making a closure. You can think of closures as
disciplined pointers to local variables. The pointers cannot be used
directly. They are encapsulated together with code represented as an
anonymous function:
(defvar *x*
(let ((a 1)) ;; locals
;; list of two closures, a getter and setter
(list
(lambda () a)
(lambda (value) (setf a value)))))
*x* -> (#<function ...> #<function ...>)
(funcall (first *x*)) -> 1
(funcall (second *x*) 42)
(funcall (first *x*)) -> 42
With closures and macros, you can create a framework of ``locative''
objects, which support evaluation and assignment, but which act as
proxies for storing and retrieving values in some place: an array
slot, local variable, CLOS object slot, etc. You'd take the address of
the place by constructing a suitable locative of the right kind for
handing that place. Then pass the locative around in the program. The
locatives could have an API like (deref l) to get the value of the
locative and (setf (deref l) val) to store the value: uniform access
to any kind of place encapsulated therein. A bit heavyweight compared
to pointers, but at the same time, without a lot of the pitfalls.
On Feb 26, 11:40 pm, Kaz Kylheku <········@gmail.com> wrote:
> On Feb 26, 8:28 pm, jc <··········@gmail.com> wrote:
>
>
>
> > On Feb 26, 8:06 pm, jc <··········@gmail.com> wrote:
>
> > > On Feb 26, 6:33 pm, Ari Johnson <·········@gmail.com> wrote:
>
> > > > jc <··········@gmail.com> writes:
> > > > > Hi, I'm practicing common lisp by trying to write a binary tree with
> > > > > nodes in the form (key left right . data). What I'd like to write
> > > > > looks something like this,
>
> > > > > <code>
> > > > > (defun insert (key data &optional (node *root*))
> > > > > (progn
> > > > > (if (null *root*)
> > > > > (setf *root* (make-node key data)))
> > > > > (destructuring-bind (k l r . d) node
> > > > > (if (funcall test k key)
> > > > > (setf node (make-node key data l r))
> > > > > (insert key data (if (funcall cmp k key)
> > > > > l
> > > > > r))))))
> > > > > </code>
>
> > > > > but obviously this isn't working. In the places where I'm using setf,
> > > > > I know that all I'm doing is re-setting the variable in the local
> > > > > scope, but I'm wondering if there's some way to pass around the place
> > > > > of the node (like passing around handles (pointers to pointers)) in
> > > > > c? Maybe there's a more lispy way of doing this, if so I'd love to
> > > > > see it.
>
> > > > This isn't all of your code, of course, but to answer your concerns
> > > > you have a few good options.
>
> > > > One thing to consider is using structs. That's what they're there
> > > > for. Another thing to think about is how NREVERSE works. It
> > > > destructively reverses a list and then returns the new head of the
> > > > list. That's why you do (setf x (nreverse x)) instead of just
> > > > (nreverse x).
>
> > > > Consider:
>
> > > > (defstruct (node (:constructor %make-node)) key data left-child right-child)
>
> > > > (defun make-node (key data)
> > > > (%make-node :key key :data data))
>
> > > > (defun node-leaf-p (node)
> > > > (declare (type (node node)))
> > > > (and (not (node-left-child node)) (not (node-right-child node))))
>
> > > > (defun insert-node (node tree &key (compare #'<) (equalp #'=))
> > > > (declare (type (node node))
> > > > (type ((or node nil) tree)))
> > > > (assert (or (not tree)
> > > > (not (funcall equalp (node-key node) (node-key tree)))))
> > > > (cond ((null tree) node)
> > > > ((funcall compare (node-key node) (node-key tree))
> > > > (setf (node-left-child tree)
> > > > (insert-node node (node-left-child tree)))
> > > > tree)
> > > > (t
> > > > (setf (node-right-child tree)
> > > > (insert-node node (node-right-child tree)))
> > > > tree)))
>
> > > > (defvar *root* nil)
>
> > > > (setf *root* (insert-node (make-node 3 "three") *root*))
> > > > (setf *root* (insert-node (make-node 2 "two") *root*))
> > > > (pprint *root*)
> > > > ==>
> > > > #S(NODE :KEY 3 :DATA "three"
> > > > :LEFT-CHILD #S(NODE :KEY 2 :DATA "two" :LEFT-CHILD NIL
> > > > :RIGHT-CHILD NIL)
> > > > :RIGHT-CHILD NIL)
>
> > > > This is almost certainly wordier than needed. I'll defer to the
> > > > experts who respond to say so.
>
> > > Those are great suggestions, but just as an exercise I'm trying pare
> > > things down to the bare minimum. I was trying to avoid non-list data
> > > structures, parent links, and non-tail recursion, maybe making the
> > > algorithm impossible? I'm not sure.
>
> > Wait, I just answered my own question. The function can keep track of
> > the parent node instead of making it part of the data. But still,
> > I've run into this situation where I'm wishing for pointers (god
> > forbid) while messing around with other things in lisp. For instance,
> > some way to do
>
> > (setq x 'a)
>
> Always use DEFVAR or DEFPARAMETER to define a global variable.
>
> > (setq (the-name-inside x) 25)
> > a
>
> There is a classic Lisp function which does this called SET.
>
> (defvar a)
> (defvar x 'a)
> (set x 25)
> a -> 25
>
> Set is a function that takes a symbol object its argument, and
> modifies the SYMBOL-VALUE slot of that symbol to the given value. It
> doesn't honor lexical scopes.
>
> This isn't anything that you can trivally do in many programming
> languages, particularly ones typified by C and the like. You're
> passing around a name of a variable and using that to assign to it. In
> C, names disappear when you compile (except if they are retained in a
> limited way for debugging).
>
> In Lisp, pointers are used implicitly to represent any object that
> needs to be ``boxed''. But storage locations are not first-class
> objects; you cannot have direct references to them. There is no
> uniform access to storage locations; it depends what kind they are.
> E.g. assigning to an array slot is different from assigning to a
> variable: (setf variable value) versus (setf (aref array ...) value).
>
> However, in Lisp you /can/ ``take the address'' of all of the lexical
> variables in scope by making a closure. You can think of closures as
> disciplined pointers to local variables. The pointers cannot be used
> directly. They are encapsulated together with code represented as an
> anonymous function:
>
> (defvar *x*
> (let ((a 1)) ;; locals
> ;; list of two closures, a getter and setter
> (list
> (lambda () a)
> (lambda (value) (setf a value)))))
>
> *x* -> (#<function ...> #<function ...>)
>
> (funcall (first *x*)) -> 1
>
> (funcall (second *x*) 42)
>
> (funcall (first *x*)) -> 42
>
> With closures and macros, you can create a framework of ``locative''
> objects, which support evaluation and assignment, but which act as
> proxies for storing and retrieving values in some place: an array
> slot, local variable, CLOS object slot, etc. You'd take the address of
> the place by constructing a suitable locative of the right kind for
> handing that place. Then pass the locative around in the program. The
> locatives could have an API like (deref l) to get the value of the
> locative and (setf (deref l) val) to store the value: uniform access
> to any kind of place encapsulated therein. A bit heavyweight compared
> to pointers, but at the same time, without a lot of the pitfalls.
Thanks for the great explanation. One thing I'm curious about,
though, is what kind of memory and cpu cost closures have. For
instance, with reference to BSTs, if I'm accessing a closure for each
n of an O(nlgn) operation (assuming n is rather large), will I take a
significant performance hit? I know I could rig some kind of test of
this myself, but if it's common knowledge I'd rather be told...
And on re-reading this it seems like "significant performance hit" is
rather vague. Let's say significant is something noticeable if you're
running timings over large data sets, but not something that's
necessarily more complex algorithmically.
From: Maciej Katafiasz
Subject: Re: newbie question: is there something analogous to handles in CL?
Date:
Message-ID: <fq8m27$q74$4@news.net.uni-c.dk>
Den Thu, 28 Feb 2008 23:22:11 -0800 skrev jc:
>> With closures and macros, you can create a framework of ``locative''
>> objects, which support evaluation and assignment, but which act as
>> proxies for storing and retrieving values in some place: an array slot,
>> local variable, CLOS object slot, etc. You'd take the address of the
>> place by constructing a suitable locative of the right kind for handing
>> that place. Then pass the locative around in the program. The locatives
>> could have an API like (deref l) to get the value of the locative and
>> (setf (deref l) val) to store the value: uniform access to any kind of
>> place encapsulated therein. A bit heavyweight compared to pointers, but
>> at the same time, without a lot of the pitfalls.
>
> Thanks for the great explanation. One thing I'm curious about, though,
> is what kind of memory and cpu cost closures have. For instance, with
> reference to BSTs, if I'm accessing a closure for each n of an O(nlgn)
> operation (assuming n is rather large), will I take a significant
> performance hit? I know I could rig some kind of test of this myself,
> but if it's common knowledge I'd rather be told...
>
> And on re-reading this it seems like "significant performance hit" is
> rather vague. Let's say significant is something noticeable if you're
> running timings over large data sets, but not something that's
> necessarily more complex algorithmically.
The cost is pretty much negligible. If you structure your closures
properly, funcalling a lambda closed over a value amounts to little more
than a pointer dereference and a function call, which is what you'd have
done anyway, and compilers are really good at making closures go fast.
Generally speaking, their performance varies from really fast to
obscenely fast. Just recently I was benchmarking some closure-happy tree
traversal code, and for the cheap case (ie. a flat list) processing a
single item, which included type dispatch, two calls to closures and
advancing to the next element in the list, was around 14 cycles or so,
and that's really freaking fast. Very tall trees were less optimistic, as
each level involved setting up a bunch of new closures and several extra
funcalls, but again, if you need to do it, even assembler ain't gonna
remove that need.
Cheers,
Maciej
PS. Please trim your quotes to retain only the relevant context. It makes
reading much easier.
From: Pascal J. Bourguignon
Subject: Re: newbie question: is there something analogous to handles in CL?
Date:
Message-ID: <7cmypkx7cc.fsf@pbourguignon.anevia.com>
jc <··········@gmail.com> writes:
> Thanks for the great explanation. One thing I'm curious about,
> though, is what kind of memory and cpu cost closures have. For
> instance, with reference to BSTs, if I'm accessing a closure for each
> n of an O(nlgn) operation (assuming n is rather large), will I take a
> significant performance hit? I know I could rig some kind of test of
> this myself, but if it's common knowledge I'd rather be told...
>
> And on re-reading this it seems like "significant performance hit" is
> rather vague. Let's say significant is something noticeable if you're
> running timings over large data sets, but not something that's
> necessarily more complex algorithmically.
Closures have 0 additionnal cost. They're the bread and butter of
lisp. The basic building block. All functions are actually closures.
LET itself is defined in terms of LAMBDA.
(defmacro let (bindings &body body)
`((lambda ,(mapcar (lambda (binding) (if (atom binding) binding (first binding))) bindings)
,@body) ,@(mapcar (lambda (binding) (if (atom binding) 'nil (second binding))) bindings)))
(macroexpand '(let ((a 1) (b) c) (print (list a b c))))
--> ((LAMBDA (A B C) (PRINT (LIST A B C))) 1 NIL NIL) ;
T
Hence a profusion of closures:
(defmacro let* (bindings &body body)
(if (endp bindings)
`(progn ,@body)
`(let* ,(butlast bindings) (let ,(last bindings) ,@body))))
(macroexpand '(let* ((a 1) (b 2) (c 3)) (+ a b c)))
--> (PROGN (LET ((A 1)) (LET ((B 2)) (LET ((C 3)) (+ A B C))))) ;
T
which in turn expands to:
#+clisp (ext:expand-form '(PROGN (LET ((A 1)) (LET ((B 2)) (LET ((C 3)) (+ A B C))))))
--> ((LAMBDA (A) ((LAMBDA (B) ((LAMBDA (C) (+ A B C)) 3)) 2)) 1) ;
T
An innocent LET* --> 3 closures!
But the most interesting is how it gets compiled:
C/USER1[165]> (disassemble (lambda () (let* ((a 1) (b 2) (c 3)) (+ a b c))))
Disassembly of function :LAMBDA
(CONST 0) = 1
(CONST 1) = 2
(CONST 2) = 3
0 required arguments
0 optional arguments
No rest parameter
No keyword parameters
5 byte-code instructions:
0 (CONST&PUSH 0) ; 1
1 (CONST&PUSH 1) ; 2
2 (CONST&PUSH 2) ; 3
3 (CALLSR 3 53) ; +
6 (SKIP&RET 1)
NIL
That said, it's not the whole thruth. These closures can be collapsed
easily. Normal closures, like:
(let ((a 1))
(defun my-clo (c)
(incf a c)))
do have a little over head above a simple function like:
(defvar *a* 1)
(defun my-fun (c) (incf *a* c))
Since a reference to my-clo can be passed anywhere (do-something
(function my-clo)), to call it we need a reference to the free
bindings of the closed function, which means we need actually two
pointers for my-clo instead of only one for my-fun. But an
implementation could do the same for 'normal' functions, just for the
sake of homogeneity.
Disassembly of function MY-CLO
(CONST 0) = #(A 1 NIL)
(CONST 1) = 1
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
10 byte-code instructions:
0 (CONST&PUSH 0) ; #(A 1 NIL)
1 (CONST 1) ; 1
2 (SVREF)
3 (PUSH)
4 (LOAD&PUSH 2)
5 (CALLSR&PUSH 2 53) ; +
8 (CONST&PUSH 0) ; #(A 1 NIL)
9 (CONST 1) ; 1
10 (SVSET)
11 (SKIP&RET 2)
NIL
C/USER1[171]> (disassemble (compile (defun my-fun (c) (incf *a* c))))
Disassembly of function MY-FUN
(CONST 0) = *A*
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
reads special variable: *A*
writes special variable: *A*
5 byte-code instructions:
0 (GETVALUE&PUSH 0) ; *A*
2 (LOAD&PUSH 2)
3 (CALLSR 2 53) ; +
6 (SETVALUE 0) ; *A*
8 (SKIP&RET 2)
NIL
C/USER1[172]> (disassemble (compile (let ((a 1))
(defun my-clo (c)
(incf a c)))))
But these additionnal instructions in my-clo are needed (do to the
same in C you would have to pass an additionnal reference to my_clo),
and GETVALUE&PUSH and SETVALUE applied on dynamic variables such as
*A* are probably costlier than references to closed-on variables.
--
__Pascal Bourguignon__
jc wrote:
> On Feb 26, 8:06 pm, jc <··········@gmail.com> wrote:
>> On Feb 26, 6:33 pm, Ari Johnson <·········@gmail.com> wrote:
...
> Wait, I just answered my own question. The function can keep track of
> the parent node instead of making it part of the data. But still,
> I've run into this situation where I'm wishing for pointers (god
> forbid) while messing around with other things in lisp. For instance,
> some way to do
>
> (setq x 'a)
> (setq (the-name-inside x) 25)
> a
> ==> 25
How's this?
(defparameter a 5)
(defparameter name 'a)
a=>5
name=>'a
(setf (symbol-value name) 6)
a=>6
name=>'a
You don't want pointers; you want their functionality, but without
their pain.[1]
- Daniel
[1] Ugh! And this is just the beginning.
http://en.wikipedia.org/wiki/Aliasing_(computing)
From: Ari Johnson
Subject: Re: newbie question: is there something analogous to handles in CL?
Date:
Message-ID: <m2fxvf2bd7.fsf@hermes.theari.com>
jc <··········@gmail.com> writes:
> On Feb 26, 8:06 pm, jc <··········@gmail.com> wrote:
>> On Feb 26, 6:33 pm, Ari Johnson <·········@gmail.com> wrote:
>>
>>
>>
>> > jc <··········@gmail.com> writes:
>> > > Hi, I'm practicing common lisp by trying to write a binary tree with
>> > > nodes in the form (key left right . data). What I'd like to write
>> > > looks something like this,
>>
>> > > <code>
>> > > (defun insert (key data &optional (node *root*))
>> > > (progn
>> > > (if (null *root*)
>> > > (setf *root* (make-node key data)))
>> > > (destructuring-bind (k l r . d) node
>> > > (if (funcall test k key)
>> > > (setf node (make-node key data l r))
>> > > (insert key data (if (funcall cmp k key)
>> > > l
>> > > r))))))
>> > > </code>
>>
>> > > but obviously this isn't working. In the places where I'm using setf,
>> > > I know that all I'm doing is re-setting the variable in the local
>> > > scope, but I'm wondering if there's some way to pass around the place
>> > > of the node (like passing around handles (pointers to pointers)) in
>> > > c? Maybe there's a more lispy way of doing this, if so I'd love to
>> > > see it.
>>
>> > This isn't all of your code, of course, but to answer your concerns
>> > you have a few good options.
>>
>> > One thing to consider is using structs. That's what they're there
>> > for. Another thing to think about is how NREVERSE works. It
>> > destructively reverses a list and then returns the new head of the
>> > list. That's why you do (setf x (nreverse x)) instead of just
>> > (nreverse x).
>>
>> > Consider:
>>
>> > (defstruct (node (:constructor %make-node)) key data left-child right-child)
>>
>> > (defun make-node (key data)
>> > (%make-node :key key :data data))
>>
>> > (defun node-leaf-p (node)
>> > (declare (type (node node)))
>> > (and (not (node-left-child node)) (not (node-right-child node))))
>>
>> > (defun insert-node (node tree &key (compare #'<) (equalp #'=))
>> > (declare (type (node node))
>> > (type ((or node nil) tree)))
>> > (assert (or (not tree)
>> > (not (funcall equalp (node-key node) (node-key tree)))))
>> > (cond ((null tree) node)
>> > ((funcall compare (node-key node) (node-key tree))
>> > (setf (node-left-child tree)
>> > (insert-node node (node-left-child tree)))
>> > tree)
>> > (t
>> > (setf (node-right-child tree)
>> > (insert-node node (node-right-child tree)))
>> > tree)))
>>
>> > (defvar *root* nil)
>>
>> > (setf *root* (insert-node (make-node 3 "three") *root*))
>> > (setf *root* (insert-node (make-node 2 "two") *root*))
>> > (pprint *root*)
>> > ==>
>> > #S(NODE :KEY 3 :DATA "three"
>> > :LEFT-CHILD #S(NODE :KEY 2 :DATA "two" :LEFT-CHILD NIL
>> > :RIGHT-CHILD NIL)
>> > :RIGHT-CHILD NIL)
>>
>> > This is almost certainly wordier than needed. I'll defer to the
>> > experts who respond to say so.
>>
>> Those are great suggestions, but just as an exercise I'm trying pare
>> things down to the bare minimum. I was trying to avoid non-list data
>> structures, parent links, and non-tail recursion, maybe making the
>> algorithm impossible? I'm not sure.
>
> Wait, I just answered my own question. The function can keep track of
> the parent node instead of making it part of the data. But still,
> I've run into this situation where I'm wishing for pointers (god
> forbid) while messing around with other things in lisp. For instance,
> some way to do
>
> (setq x 'a)
> (setq (the-name-inside x) 25)
> a
> ==> 25
Think about what SETQ stands for, and the answer you seek will appear.
On Feb 26, 9:53 pm, Ari Johnson <·········@gmail.com> wrote:
> jc <··········@gmail.com> writes:
> > On Feb 26, 8:06 pm, jc <··········@gmail.com> wrote:
> >> On Feb 26, 6:33 pm, Ari Johnson <·········@gmail.com> wrote:
>
> >> > jc <··········@gmail.com> writes:
> >> > > Hi, I'm practicing common lisp by trying to write a binary tree with
> >> > > nodes in the form (key left right . data). What I'd like to write
> >> > > looks something like this,
>
> >> > > <code>
> >> > > (defun insert (key data &optional (node *root*))
> >> > > (progn
> >> > > (if (null *root*)
> >> > > (setf *root* (make-node key data)))
> >> > > (destructuring-bind (k l r . d) node
> >> > > (if (funcall test k key)
> >> > > (setf node (make-node key data l r))
> >> > > (insert key data (if (funcall cmp k key)
> >> > > l
> >> > > r))))))
> >> > > </code>
>
> >> > > but obviously this isn't working. In the places where I'm using setf,
> >> > > I know that all I'm doing is re-setting the variable in the local
> >> > > scope, but I'm wondering if there's some way to pass around the place
> >> > > of the node (like passing around handles (pointers to pointers)) in
> >> > > c? Maybe there's a more lispy way of doing this, if so I'd love to
> >> > > see it.
>
> >> > This isn't all of your code, of course, but to answer your concerns
> >> > you have a few good options.
>
> >> > One thing to consider is using structs. That's what they're there
> >> > for. Another thing to think about is how NREVERSE works. It
> >> > destructively reverses a list and then returns the new head of the
> >> > list. That's why you do (setf x (nreverse x)) instead of just
> >> > (nreverse x).
>
> >> > Consider:
>
> >> > (defstruct (node (:constructor %make-node)) key data left-child right-child)
>
> >> > (defun make-node (key data)
> >> > (%make-node :key key :data data))
>
> >> > (defun node-leaf-p (node)
> >> > (declare (type (node node)))
> >> > (and (not (node-left-child node)) (not (node-right-child node))))
>
> >> > (defun insert-node (node tree &key (compare #'<) (equalp #'=))
> >> > (declare (type (node node))
> >> > (type ((or node nil) tree)))
> >> > (assert (or (not tree)
> >> > (not (funcall equalp (node-key node) (node-key tree)))))
> >> > (cond ((null tree) node)
> >> > ((funcall compare (node-key node) (node-key tree))
> >> > (setf (node-left-child tree)
> >> > (insert-node node (node-left-child tree)))
> >> > tree)
> >> > (t
> >> > (setf (node-right-child tree)
> >> > (insert-node node (node-right-child tree)))
> >> > tree)))
>
> >> > (defvar *root* nil)
>
> >> > (setf *root* (insert-node (make-node 3 "three") *root*))
> >> > (setf *root* (insert-node (make-node 2 "two") *root*))
> >> > (pprint *root*)
> >> > ==>
> >> > #S(NODE :KEY 3 :DATA "three"
> >> > :LEFT-CHILD #S(NODE :KEY 2 :DATA "two" :LEFT-CHILD NIL
> >> > :RIGHT-CHILD NIL)
> >> > :RIGHT-CHILD NIL)
>
> >> > This is almost certainly wordier than needed. I'll defer to the
> >> > experts who respond to say so.
>
> >> Those are great suggestions, but just as an exercise I'm trying pare
> >> things down to the bare minimum. I was trying to avoid non-list data
> >> structures, parent links, and non-tail recursion, maybe making the
> >> algorithm impossible? I'm not sure.
>
> > Wait, I just answered my own question. The function can keep track of
> > the parent node instead of making it part of the data. But still,
> > I've run into this situation where I'm wishing for pointers (god
> > forbid) while messing around with other things in lisp. For instance,
> > some way to do
>
> > (setq x 'a)
> > (setq (the-name-inside x) 25)
> > a
> > ==> 25
>
> Think about what SETQ stands for, and the answer you seek will appear.
Q as in quoted? I don't follow. But you're absolutely right, I need
to give up on lists.
You could do something similar to the following, but probably
shouldn't:
(defun foo ()
(let ((a (list 1)))
(bar a)
(car a)))
(defun bar (p)
(setf (car p) 10))
(foo) => 10
From: Pascal J. Bourguignon
Subject: Re: newbie question: is there something analogous to handles in CL?
Date:
Message-ID: <7cmypmz5oo.fsf@pbourguignon.anevia.com>
Brian <··············@gmail.com> writes:
> You could do something similar to the following, but probably
> shouldn't:
>
> (defun foo ()
> (let ((a (list 1)))
> (bar a)
> (car a)))
>
> (defun bar (p)
> (setf (car p) 10))
>
> (foo) => 10
Or nicely packaged as locatives:
http://groups.google.com/group/comp.lang.lisp/msg/2645808b80037216
(defun foo ()
(let ((a 1))
(bar (& a))
a))
(defun bar (*p)
(setf (ref *p) 10))
(foo)
--> 10
--
__Pascal Bourguignon__
jc wrote:
> On Feb 26, 6:33 pm, Ari Johnson <·········@gmail.com> wrote:
>> jc <··········@gmail.com> writes:
>>> Hi, I'm practicing common lisp by trying to write a binary tree with
>>> nodes in the form (key left right . data). What I'd like to write
>>> looks something like this,
>>> <code>
>>> (defun insert (key data &optional (node *root*))
>>> (progn
>>> (if (null *root*)
>>> (setf *root* (make-node key data)))
>>> (destructuring-bind (k l r . d) node
>>> (if (funcall test k key)
>>> (setf node (make-node key data l r))
>>> (insert key data (if (funcall cmp k key)
>>> l
>>> r))))))
>>> </code>
>>> but obviously this isn't working. In the places where I'm using setf,
>>> I know that all I'm doing is re-setting the variable in the local
>>> scope, but I'm wondering if there's some way to pass around the place
>>> of the node (like passing around handles (pointers to pointers)) in
>>> c? Maybe there's a more lispy way of doing this, if so I'd love to
>>> see it.
>> This isn't all of your code, of course, but to answer your concerns
>> you have a few good options.
>>
>> One thing to consider is using structs. That's what they're there
>> for. Another thing to think about is how NREVERSE works. It
>> destructively reverses a list and then returns the new head of the
>> list. That's why you do (setf x (nreverse x)) instead of just
>> (nreverse x).
>>
>> Consider:
...
>
> Those are great suggestions, but just as an exercise I'm trying pare
> things down to the bare minimum. I was trying to avoid non-list data
> structures, parent links, and non-tail recursion, maybe making the
> algorithm impossible? I'm not sure.
Are you familiar with C? Think of Lisp variables as pointers that
automatically dereference to return their value. Then a variable
passed to a function will create a new pointer to the old value.
Assigning the variable inside the function changes where it points,
not what it pointed to. The only way to modify the original value is
to setf a location *inside* it.
This is generally a good thing. For scalar values, there is no reason
to modify a passed value; lisp makes it easy to return multiple values
(and even inline speed-critical functions). For structures where
copying becomes expensive, you pass the whole structure anyway, and
the function can write inside it.
Since you are using make-node, you already have a node structure
somewhere. Have you tried something like
(setf (node-key node) key
(node-data node) data)
instead of
(setf node (make-node ...))
?
- Daniel
From: Ari Johnson
Subject: Re: newbie question: is there something analogous to handles in CL?
Date:
Message-ID: <m2k5kr2bi0.fsf@hermes.theari.com>
jc <··········@gmail.com> writes:
> On Feb 26, 6:33 pm, Ari Johnson <·········@gmail.com> wrote:
>> jc <··········@gmail.com> writes:
>> > Hi, I'm practicing common lisp by trying to write a binary tree with
>> > nodes in the form (key left right . data). What I'd like to write
>> > looks something like this,
>>
>> > <code>
>> > (defun insert (key data &optional (node *root*))
>> > (progn
>> > (if (null *root*)
>> > (setf *root* (make-node key data)))
>> > (destructuring-bind (k l r . d) node
>> > (if (funcall test k key)
>> > (setf node (make-node key data l r))
>> > (insert key data (if (funcall cmp k key)
>> > l
>> > r))))))
>> > </code>
>>
>> > but obviously this isn't working. In the places where I'm using setf,
>> > I know that all I'm doing is re-setting the variable in the local
>> > scope, but I'm wondering if there's some way to pass around the place
>> > of the node (like passing around handles (pointers to pointers)) in
>> > c? Maybe there's a more lispy way of doing this, if so I'd love to
>> > see it.
>>
>> This isn't all of your code, of course, but to answer your concerns
>> you have a few good options.
>>
>> One thing to consider is using structs. That's what they're there
>> for. Another thing to think about is how NREVERSE works. It
>> destructively reverses a list and then returns the new head of the
>> list. That's why you do (setf x (nreverse x)) instead of just
>> (nreverse x).
>>
>> Consider:
>>
>> (defstruct (node (:constructor %make-node)) key data left-child right-child)
>>
>> (defun make-node (key data)
>> (%make-node :key key :data data))
>>
>> (defun node-leaf-p (node)
>> (declare (type (node node)))
>> (and (not (node-left-child node)) (not (node-right-child node))))
>>
>> (defun insert-node (node tree &key (compare #'<) (equalp #'=))
>> (declare (type (node node))
>> (type ((or node nil) tree)))
>> (assert (or (not tree)
>> (not (funcall equalp (node-key node) (node-key tree)))))
>> (cond ((null tree) node)
>> ((funcall compare (node-key node) (node-key tree))
>> (setf (node-left-child tree)
>> (insert-node node (node-left-child tree)))
>> tree)
>> (t
>> (setf (node-right-child tree)
>> (insert-node node (node-right-child tree)))
>> tree)))
>>
>> (defvar *root* nil)
>>
>> (setf *root* (insert-node (make-node 3 "three") *root*))
>> (setf *root* (insert-node (make-node 2 "two") *root*))
>> (pprint *root*)
>> ==>
>> #S(NODE :KEY 3 :DATA "three"
>> :LEFT-CHILD #S(NODE :KEY 2 :DATA "two" :LEFT-CHILD NIL
>> :RIGHT-CHILD NIL)
>> :RIGHT-CHILD NIL)
>>
>> This is almost certainly wordier than needed. I'll defer to the
>> experts who respond to say so.
>
> Those are great suggestions, but just as an exercise I'm trying pare
> things down to the bare minimum. I was trying to avoid non-list data
> structures, parent links, and non-tail recursion, maybe making the
> algorithm impossible? I'm not sure.
Why obsess about lists? Note that I avoided parent links already, as
they are unnecessary to binary tree data structures generally.
Eliminating non-tail recursion is an exercise for the reader. It will
make the code much uglier.
On Feb 26, 5:34 pm, jc <··········@gmail.com> wrote:
> Hi, I'm practicing common lisp by trying to write a binary tree with
> nodes in the form (key left right . data). What I'd like to write
> looks something like this,
>
> <code>
> (defun insert (key data &optional (node *root*))
> (progn
> (if (null *root*)
> (setf *root* (make-node key data)))
> (destructuring-bind (k l r . d) node
> (if (funcall test k key)
> (setf node (make-node key data l r))
> (insert key data (if (funcall cmp k key)
> l
> r))))))
> </code>
>
> but obviously this isn't working. In the places where I'm using setf,
> I know that all I'm doing is re-setting the variable in the local
> scope, but I'm wondering if there's some way to pass around the place
You have a few bugs. Firstly, the L and R fields of the node can be
NIL. Your recursion won't handle that.
You should forget about the *ROOT* variable, that's a bad idea anyway.
Your approach is to replace a node when a key is found. Nowhere do you
actually have a destructive operation to replace the L or R fields of
the node, which suggests you are trying to do this in the style of
functional programming.
The thing to do with this approach is to have each recursive level
return the new tree to its caller. It's a filtering operation: the old
tree, key and datum go in. A new tree comes out which is the old tree
with the key and datum added to it. The old tree continues to exist;
it is not modified in any way.
Here is some pseudocode. I'm going to use a backquote expression
instead of the MAKE-TREE abstraction:
(defun tree-insert (tree key datum &key (test #'eql) (less #'<) &rest
rest)
(if (null tree)
`(,key ,datum nil nil))
(destructuring-bind (tkey tdatum left right) tree
(cond
((funcall less key tkey)
`(,tkey ,tdatum ,(apply #'insert left key datum
rest) ,right))
((funcall test key tkey)
`(,key ,datum ,left ,right))
(t
`(,tkey ,tdatum ,left ,(apply #'insert right key datum
rest))))))
In other words:
1. If the tree is nil, return a new one-node tree with key and datum.
2. Otherwise:
2. a) If the key is less than the root key of the tree,
- insert the node into the left tree, and hang on to the
tree which the insertion returns.
- make a new node just like the current tree
(same key, same value, same right subtree), except
substitute the returned tree for the left subtree.
- return this new node.
b) Otherwise if the key is equal:
- make a new tree just like this one, except substitute a
new key and datum. Use the same left and right subtree.
c) Otherwise the key is greater than the root key:
- left-right mirror image of 2 a) steps.
- make a new node like this one, same key and datum,
where the right subtree is filtered through the insertion.
With this functional approach, you can keep all versions of the tree.
The pointers are downward only. When you lose your last reference to
any part of any version of the tree, it becomes garbage and is
eventually reclaimed.
> of the node (like passing around handles (pointers to pointers)) in
> c? Maybe there's a more lispy way of doing this, if so I'd love to
> see it.
That's one Lispy way of doing it. Ideally, you want to be doing this
with structures, not lists. Lists are good for rapidly prototyping
this. And of course you can implement destructive algorithm also, and
one which is iterative rather than recursive.
In a serious (non-pseudocode!) implementation of the functional
approach, I would do the recursion using an internal function
introduced by LABELS, to avoid passing down the invariant arguments:
the key, datum and comparison functions:
(defun tree-insert (tree key datum &key (test #'eql) (less #'<) &rest
rest)
(labels ((insert (tree) #| simplified inner recursive function |#))
(insert tree)))
Most textbook descriptions of binary search trees do not rely on
pointers to pointers. They assume you have a node, and that you can
assign to its fields. So the tree is constructed using assignments
like
node.left := new node(key, datum)
node.left.parent := node;
This type of pseudocode translates quite readily to Lisp. Lisp is
quite ideal for transcribing textbook algorithms, because you can
almost just transliterate the pseudocode to Lisp and it Just Works.
Textbook algorithms tend not to be concerned with static typing, nor
with memory management. The datum can be of any type, etc.
So I would suggest to find a good description of these algorithms and
transcribe them carfully to Lisp.