Suppose I want to keep track of the current element in a {singly,
doubly}-linked list (that might be circular) and at some point cleanly
advance it by one or more steps.
In C I'd do something like that:
list* p = LIST; /* let p initially point to the list head */
p++; /* might also be p += 5; */
/* assertion: p always points at the current element of the list */
And would walk it by just saying
while (p++); /* this obviously doesn't work out for circular lists,
but let's keep things simple */
What's the idiom for this stuff in Lisp? I'm sure there must be some
smug solution
that, as usual, eludes me. Thanks, folks.
Leslie
Leslie P. Polzer wrote:
> By the way, I know I could do something like
> (nth p LIST)
> to achieve a similar thing, but I'd like to access the element
> directly.
The only think I can think of is that you want this:
(setf list (nth n list))
--
Dan
www.prairienet.org/~dsb/
"Leslie P. Polzer" <·············@gmx.net> writes:
> Suppose I want to keep track of the current element in a {singly,
> doubly}-linked list (that might be circular) and at some point cleanly
> advance it by one or more steps.
>
> In C I'd do something like that:
>
> list* p = LIST; /* let p initially point to the list head */
> p++; /* might also be p += 5; */
> /* assertion: p always points at the current element of the list */
>
> And would walk it by just saying
>
> while (p++); /* this obviously doesn't work out for circular lists,
> but let's keep things simple */
Are you sure you aren't referring to arrays instead of lists? Where
is the link that you referred to?
On 2007-06-24 09:25:46 -0400, "Leslie P. Polzer" <·············@gmx.net> said:
> In C I'd do something like that:
>
> list* p = LIST; /* let p initially point to the list head */
> p++; /* might also be p += 5; */
> /* assertion: p always points at the current element of the list */
>
> And would walk it by just saying
>
> while (p++); /* this obviously doesn't work out for circular lists,
> but let's keep things simple */
You want vectors, not lists. In C, list * p is a vector (a.k.a. a one
dimensional array) of node (or element) structs. Lisp has vectors and
multidimensional arrays as well. If you really want to work with lisp
lists as such, you would have to either walk the list each time as you
note, or cache variables that point to various elements of the list
while assuring that nothing else you did modified the list struture in
between cache accesses, or ensure that functions that do mutation also
invalidate the necessary cache(s).
But for the idiom above you could write it in lisp in pretty much the
same way as in C - just define a node struct, and define your lists as
vectors of node structs. See the hyperspec for defstruct, make-array,
aref, and vector-push/vector-push-extend (assuming you'll want to be
able to add elements to your `list').
The usual question here is "what are your *really* trying to do?" IOW,
what higher level problem are you trying to solve? There's probably an
idiomatic lisp way of doing that which may not involve the approach
you're used to in C.
Leslie P. Polzer wrote:
> Suppose I want to keep track of the current element in a {singly,
> doubly}-linked list (that might be circular) and at some point cleanly
> advance it by one or more steps.
>
> In C I'd do something like that:
>
> list* p = LIST; /* let p initially point to the list head */
> p++; /* might also be p += 5; */
> /* assertion: p always points at the current element of the list */
>
> And would walk it by just saying
>
> while (p++); /* this obviously doesn't work out for circular lists,
> but let's keep things simple */
>
> What's the idiom for this stuff in Lisp? I'm sure there must be some
> smug solution
> that, as usual, eludes me. Thanks, folks.
Lisp lists are singly-linked cons structures; their C equivalent is roughly.
struct CONS { void * data; struct CONS * next; };
or more accurately
struct CONS { void * CAR; void * CDR; };
Doubly-linked lists are not provided as standard part of Common Lisp; I
rarely find them useful by themselves (though prev and next often do
appear as part of another data structure).
The "Lisp way" prefers to use functions like mapc to walk lists.
Here's a direct Lisp translation of the C (array/dense list traversal)
idiom.
(let ((LIST '(1 2 s d)))
(do ((p LIST ; p=&LIST[0];
(cdr p))) ; p++
((not p)) ; while(p)
(format t "*p is ~A~%" (car p)))) ; car ~= dereference operator
Later,
Daniel
On 2007-06-24 11:23:58 -0400, D Herring <········@at.tentpost.dot.com> said:
>
> Here's a direct Lisp translation of the C (array/dense list traversal) idiom.
> (let ((LIST '(1 2 s d)))
> (do ((p LIST ; p=&LIST[0];
> (cdr p))) ; p++
> ((not p)) ; while(p)
> (format t "*p is ~A~%" (car p)))) ; car ~= dereference operator
Right, but the OP said "and at some point cleanly advance it by one or
more steps." IOW, he wants to hold a pointer into a list and continue
his traversal at some arbitrary future time - unless he's just
expressed himself awkwardly.
On Jun 24, 5:26 pm, Raffael Cavallaro wrote:
> Right, but the OP said "and at some point cleanly advance it by one or
> more steps." IOW, he wants to hold a pointer into a list and continue
> his traversal at some arbitrary future time - unless he's just
> expressed himself awkwardly.
That's exactly what I want.
The answers given so far have been very helpful (special thanks to
Daniel Herring who gave me an excellent analogy for CAR and CDR!), and
I'd like to explain what I have in mind in a more high-level basis:
Let's assume a pictorial animation stored as a sequence of still
images that are showed one after another in regular not necessarily
equidistant intervals.
What's an elegant way to track the image we need to show next (or have
shown last, which is practically the same)?
In C I would have used the mentioned list structure with DATA and
NEXT*.
Leslie
"Leslie P. Polzer" <·············@gmx.net> writes:
> On Jun 24, 5:26 pm, Raffael Cavallaro wrote:
>
> > Right, but the OP said "and at some point cleanly advance it by one or
> > more steps." IOW, he wants to hold a pointer into a list and continue
> > his traversal at some arbitrary future time - unless he's just
> > expressed himself awkwardly.
>
> That's exactly what I want.
>
> The answers given so far have been very helpful (special thanks to
> Daniel Herring who gave me an excellent analogy for CAR and CDR!), and
> I'd like to explain what I have in mind in a more high-level basis:
>
> Let's assume a pictorial animation stored as a sequence of still
> images that are showed one after another in regular not necessarily
> equidistant intervals.
>
> What's an elegant way to track the image we need to show next (or have
> shown last, which is practically the same)?
>
> In C I would have used the mentioned list structure with DATA and
> NEXT*.
It depends on whether you ever want to either back up or jump by large
amounts. In those cases, you probably want to manage the elements in
an array rather than a list, and just actually count. But assuming
you're using a list for its intended use, which is to tend to move
through all the elements, possibly skipping some, without backing up,
lists will do what you want reasonably elegantly.
Here's the kind of thing you might do...
;;; This creates an abstraction so you have lots of options...
;;; It works like dolist, but within the body you can
;;; (ADVANCE x) to immediately move the pointer.
;;; (SKIP x) to move the pointer and go back to the top of the loop
;;; (SKIP-NEXT x) to note that the pointer needs be nudged
(defmacro dolist-maybe-skipping ((var value) &body forms)
(let ((tail-var (gensym "TAIL"))
(skip-tag (gensym "SKIP"))
(skipping-var (gensym "SKIPPING")))
`(let ((,tail-var ,value))
(loop while ,tail-var do
(let ((,skipping-var 1) (,var (first ,tail-var)))
(block ,skip-tag
(labels ((advance (&optional (n 1))
(dotimes (i n) (setq ,var (pop ,tail-var))))
(skip-next (&optional (n 1))
(setq ,skipping-var n))
(skip (&optional (n 1))
(setq ,skipping-var n)
(return-from ,skip-tag)))
(progn ,@forms)))
(dotimes (i ,skipping-var) (pop ,tail-var)))))))
=> DOLIST-MAYBE-SKIPPING
;;; - - - -
;;; Note that the above implementation does not guard against you
;;; changing your mind by doing a SKIP-NEXT before you iterate with
;;; a different value; it would be easy to modify this to make the
;;; effect additive rather than overwriting.
;;; - - - -
;;; This shows some sample uses
(dolist-maybe-skipping (x '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18))
(when (zerop (mod x 3)) (skip-next x))
(print x))
1
2
3
6
12
=> NIL
(dolist-maybe-skipping (x '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18))
(when (zerop (mod x 3)) (skip x))
(print x))
1
2
=> NIL
(dolist-maybe-skipping (x '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18))
(when (zerop (mod x 3)) (advance x))
(print x))
1
2
5
7
8
17
=> NIL
;;; Here's a macro expansion of that last example, just to illustrate:
(pprint (macroexpand-1 '(dolist-maybe-skipping (x '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18))
(when (zerop (mod x 3)) (advance x))
(print x))))
(LET ((#:TAIL698 '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18)))
(LOOP WHILE #:TAIL698
DO (LET ((#:SKIPPING700 1)
(X (FIRST #:TAIL698)))
(BLOCK #:SKIP699
(LABELS ((ADVANCE (&OPTIONAL (N 1))
(DOTIMES (I N) (SETQ X (POP #:TAIL698))))
(SKIP-NEXT (&OPTIONAL (N 1))
(SETQ #:SKIPPING700 N))
(SKIP (&OPTIONAL (N 1))
(SETQ #:SKIPPING700 N) (RETURN-FROM #:SKIP699)))
(PROGN (WHEN (ZEROP (MOD X 3)) (ADVANCE X)) (PRINT X))))
(DOTIMES (I #:SKIPPING700) (POP #:TAIL698)))))
;;; Note that if you'd written that last one by hand, since not all the
;;; features were used, you might have preferred just:
(LET ((LIST '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18)))
(LOOP WHILE LIST
DO (LET ((X (FIRST LIST)))
(WHEN (ZEROP (MOD X 3))
(DOTIMES (I X) (SETQ X (POP LIST))))
(PRINT X))
(POP LIST)))
1
2
5
7
8
17
=> NIL
On 2007-06-24 11:52:44 -0400, "Leslie P. Polzer" <·············@gmx.net> said:
> Let's assume a pictorial animation stored as a sequence of still
> images that are showed one after another in regular not necessarily
> equidistant intervals.
>
> What's an elegant way to track the image we need to show next (or have
> shown last, which is practically the same)?
If you never need random access but will always be accessing frames
sequentially then use a circular list and nthcdr. Hopefully this
solution is suitably `smug' ;^)
CL-USER 1 > (defvar *animation-list* (list 'frame-0 'frame-1 'frame-2
'frame-3))
*ANIMATION-LIST*
CL-USER 2 > *animation-list*
(FRAME-0 FRAME-1 FRAME-2 FRAME-3)
CL-USER 3 > (setf *print-circle* t)
T
;; or else the lisp printer will loop infinitely
CL-USER 4 > (setf (cdr (last *animation-list*)) *animation-list*)
#1=(FRAME-0 FRAME-1 FRAME-2 FRAME-3 . #1#)
;; make it circular
CL-USER 5 > *animation-list*
#1=(FRAME-0 FRAME-1 FRAME-2 FRAME-3 . #1#)
CL-USER 6 > (defvar *current-cdr* (nthcdr 0 *animation-list*))
*CURRENT-CDR*
;; hold on to a circular list whose head is the current frame
CL-USER 7 > *current-cdr*
#1=(FRAME-0 FRAME-1 FRAME-2 FRAME-3 . #1#)
CL-USER 8 > (defun advance-frame ()
(setf *current-cdr* (nthcdr 1 *current-cdr*)))
ADVANCE-FRAME
;; just set the var *current-cdr* to the next cdr of the circular list
CL-USER 9 > (defun current-frame () (car *current-cdr*))
CURRENT-FRAME
;; the frame itself is just the car of the current cdr
CL-USER 10 > (current-frame)
FRAME-0
CL-USER 11 > (advance-frame)
#1=(FRAME-1 FRAME-2 FRAME-3 FRAME-0 . #1#)
CL-USER 12 > (current-frame)
FRAME-1
CL-USER 13 > (advance-frame)
#1=(FRAME-2 FRAME-3 FRAME-0 FRAME-1 . #1#)
CL-USER 14 > (current-frame)
FRAME-2
CL-USER 15 >
Raffael Cavallaro wrote:
> If you never need random access but will always be accessing frames
> sequentially then use a circular list and nthcdr. Hopefully this
> solution is suitably `smug' ;^)
>
> [...]
Very nice! Thanks a bunch, I guess I'm going to use this.
Kent: your solution seems to be too complicated for the task I have in
mind; but thanks for posting it, too. I appreciate it.
Leslie
"Leslie P. Polzer" <·············@gmx.net> writes:
> Raffael Cavallaro wrote:
>
> > If you never need random access but will always be accessing frames
> > sequentially then use a circular list and nthcdr. Hopefully this
> > solution is suitably `smug' ;^)
> >
> > [...]
>
> Very nice! Thanks a bunch, I guess I'm going to use this.
>
> Kent: your solution seems to be too complicated for the task I have in
> mind; but thanks for posting it, too. I appreciate it.
Not a problem.
The thing you want to be alert to is "repeated boilerplate code". In
static languages, with templates, digging yourself out of that is very
hard because templates are another language that is a pain to write
and often just as much of a pain later to read. In Lisp, it's very
easy to just dash off a macro abstraction because the implementation
is simple (just lists and symbols). And then you never think again
about how the abstraction is implemented because the syntax is quite
natural.
A lot of repetitiveness in other languages is tolerated for lack of this.
Raffael Cavallaro wrote:
> On 2007-06-24 11:23:58 -0400, D Herring <········@at.tentpost.dot.com>
> said:
>
>>
>> Here's a direct Lisp translation of the C (array/dense list traversal)
>> idiom.
>> (let ((LIST '(1 2 s d)))
>> (do ((p LIST ; p=&LIST[0];
>> (cdr p))) ; p++
>> ((not p)) ; while(p)
>> (format t "*p is ~A~%" (car p)))) ; car ~= dereference operator
>
> Right, but the OP said "and at some point cleanly advance it by one or
> more steps." IOW, he wants to hold a pointer into a list and continue
> his traversal at some arbitrary future time - unless he's just expressed
> himself awkwardly.
So this would look more like
(defun list+= (start count)
(nth count start))
(defparameter my-list '(1 2 s d))
(defparameter p my-list) ; p=&my_list[0];
(car p) ; *p
(setf p (cdr p)) ; p++
(setf p (list+= p 2)) ; p+=2
On Jun 24, 5:48 pm, D Herring <········@at.tentpost.dot.com> wrote:
> So this would look more like
> (defun list+= (start count)
> (nth count start))
>
> (defparameter my-list '(1 2 s d))
> (defparameter p my-list) ; p=&my_list[0];
> (car p) ; *p
> (setf p (cdr p)) ; p++
> (setf p (list+= p 2)) ; p+=2
Thanks, that's the solution for the low-level problem I posed.
It seems pretty ugly (i.e. not of the smugp kind) to me, though.
On Jun 25, 5:37 am, Dan Bensen <··········@cyberspace.net> wrote:
> Leslie P. Polzer wrote:
> > It seems pretty ugly (i.e. not of the smugp kind) to me, though.
>
> How about this:
> (defmacro += (p n) `(setf ,p (nthcdr ,n ,p)))
>
> [...]
Also nice. Any specific reason (excluding performance) for using a
macro here instead of a function?
Leslie P. Polzer wrote:
> On Jun 25, 5:37 am, Dan Bensen <··········@cyberspace.net> wrote:
>> (defmacro += (p n) `(setf ,p (nthcdr ,n ,p)))
> Also nice. Any specific reason (excluding performance) for using a
> macro here instead of a function?
A function call would pass the value of p to the function, but not
its address. SETF is a macro that needs to know where to find the
variable, so += has to be a macro for SETF to put a reference to
the new value in the right place.
It's the same reason ++ and += have to be operators in C if you don't
want to mess with pointers. The only way to make += a function would be
to pass the address of the variable, and you can't do that explicitly
in Lisp.
--
Dan
www.prairienet.org/~dsb/
Dan Bensen wrote:
> The only way to make += a function would be
> to pass the address of the variable, and you can't do that explicitly
> in Lisp.
What Dan is trying to say is that "there is no need to commit this kind
of insanity in (Common) Lisp."
If you think you need something like this, you're not yet programming
in Lisp; you're programming in C without infix notation...
On 25 jun, 16:05, Dan Bensen <··········@cyberspace.net> wrote:
> Leslie P. Polzer wrote:
> > On Jun 25, 5:37 am, Dan Bensen <··········@cyberspace.net> wrote:
> >> (defmacro += (p n) `(setf ,p (nthcdr ,n ,p)))
> > Also nice. Any specific reason (excluding performance) for using a
> > macro here instead of a function?
>
> A function call would pass the value of p to the function, but not
> its address. SETF is a macro that needs to know where to find the
> variable, so += has to be a macro for SETF to put a reference to
> the new value in the right place.
> It's the same reason ++ and += have to be operators in C if you don't
> want to mess with pointers. The only way to make += a function would be
> to pass the address of the variable, and you can't do that explicitly
> in Lisp.
>
> --
> Danwww.prairienet.org/~dsb/
why lisp doesn't have an address operator?
In this example it would be very useful to pass the address of p to
the function.
Any of you have an idea for this behaviour?
That is, why address opererator is forbidden?
On 28 jun, 22:59, ·············@yahoo.es wrote:
> On 25 jun, 16:05, Dan Bensen <··········@cyberspace.net> wrote:
>
>
>
> > Leslie P. Polzer wrote:
> > > On Jun 25, 5:37 am, Dan Bensen <··········@cyberspace.net> wrote:
> > >> (defmacro += (p n) `(setf ,p (nthcdr ,n ,p)))
> > > Also nice. Any specific reason (excluding performance) for using a
> > > macro here instead of a function?
>
> > A function call would pass the value of p to the function, but not
> > its address. SETF is a macro that needs to know where to find the
> > variable, so += has to be a macro for SETF to put a reference to
> > the new value in the right place.
> > It's the same reason ++ and += have to be operators in C if you don't
> > want to mess with pointers. The only way to make += a function would be
> > to pass the address of the variable, and you can't do that explicitly
> > in Lisp.
>
> > --
> > Danwww.prairienet.org/~dsb/
>
> why lisp doesn't have an address operator?
>
> In this example it would be very useful to pass the address of p to
> the function.
>
> Any of you have an idea for this behaviour?
>
> That is, why address opererator is forbidden?
Anyway, here is a defun for the += operator:
(defun +=(p n) (set p (nthcdr n (symbol-value p))))
example:
(setq a '(1 2 3 4 5 6 7 8 9 10))
(+= 'a 3) ----------> (4 5 6 7 8 9 10)
·············@yahoo.es wrote:
> why lisp doesn't have an address operator?
Because they're evil :)
The consensus in the software industry seems to be that
pointers are a huge source of bugs. Without pointers,
the only way a program can segfault is if there's a bug
in the compiler.
·············@yahoo.es wrote:
> Anyway, here is a defun for the += operator:
> (defun +=(p n) (set p (nthcdr n (symbol-value p))))
> (+= 'a 3) ----------> (4 5 6 7 8 9 10)
Right. This works because p is a symbol, and the SET function
doesn't really change the value of p, even though it appears to.
(set p x) is equivalent to (setf (symbol-value p) x),
so what it really changes is (symbol-value p), which is one of
the slots inside p. Only a macro can change p itself.
--
Dan
www.prairienet.org/~dsb/
On 28 Jun, 22:30, ·············@yahoo.es wrote:
> On 28 jun, 22:59, ·············@yahoo.es wrote:
>
>
>
> > On 25 jun, 16:05, Dan Bensen <··········@cyberspace.net> wrote:
>
> > > Leslie P. Polzer wrote:
> > > > On Jun 25, 5:37 am, Dan Bensen <··········@cyberspace.net> wrote:
> > > >> (defmacro += (p n) `(setf ,p (nthcdr ,n ,p)))
> > > > Also nice. Any specific reason (excluding performance) for using a
> > > > macro here instead of a function?
>
> > > A function call would pass the value of p to the function, but not
> > > its address. SETF is a macro that needs to know where to find the
> > > variable, so += has to be a macro for SETF to put a reference to
> > > the new value in the right place.
> > > It's the same reason ++ and += have to be operators in C if you don't
> > > want to mess with pointers. The only way to make += a function would be
> > > to pass the address of the variable, and you can't do that explicitly
> > > in Lisp.
>
> > > --
> > > Danwww.prairienet.org/~dsb/
>
> > why lisp doesn't have an address operator?
>
> > In this example it would be very useful to pass the address of p to
> > the function.
>
> > Any of you have an idea for this behaviour?
>
> > That is, why address opererator is forbidden?
>
> Anyway, here is a defun for the += operator:
>
> (defun +=(p n) (set p (nthcdr n (symbol-value p))))
>
> example:
>
> (setq a '(1 2 3 4 5 6 7 8 9 10))
>
> (+= 'a 3) ----------> (4 5 6 7 8 9 10)
(let ((x '(1 2 3 4 5)))
(+= 'x 2))
Error: The variable X is unbound.
[Condition of type UNBOUND-VARIABLE]
>From The hyperspec:
Notes:
The function set is deprecated.
set cannot change the value of a lexical variable.
On 28 Jun, 21:59, ·············@yahoo.es wrote:
> On 25 jun, 16:05, Dan Bensen <··········@cyberspace.net> wrote:
>
>
>
> > Leslie P. Polzer wrote:
> > > On Jun 25, 5:37 am, Dan Bensen <··········@cyberspace.net> wrote:
> > >> (defmacro += (p n) `(setf ,p (nthcdr ,n ,p)))
> > > Also nice. Any specific reason (excluding performance) for using a
> > > macro here instead of a function?
>
> > A function call would pass the value of p to the function, but not
> > its address. SETF is a macro that needs to know where to find the
> > variable, so += has to be a macro for SETF to put a reference to
> > the new value in the right place.
> > It's the same reason ++ and += have to be operators in C if you don't
> > want to mess with pointers. The only way to make += a function would be
> > to pass the address of the variable, and you can't do that explicitly
> > in Lisp.
>
> > --
> > Danwww.prairienet.org/~dsb/
>
> why lisp doesn't have an address operator?
>
> In this example it would be very useful to pass the address of p to
> the function.
>
> Any of you have an idea for this behaviour?
>
> That is, why address opererator is forbidden?
Because then it wouldn't be a function, it would be a procedure and
significantly limit the situations you can apply it in.
Consider an iterator, A, in C++, now assume you want to assign to B
A's successor without moving A.
You have to write:
B = A;
++B;
Rather than:
B=next(A);
In c, incremental change of a given value tends to be the default
option and the language is optimised around that.
In lisp the focus is on arbitrary functional transforms of data
instead.
If you want to fake this ability you can do so by wrapping the data in
a cons cell or an array of length 1.
·············@yahoo.es writes:
> why lisp doesn't have an address operator?
The short answer is that it would allow a gateway to violating Lisp's
memory integrity.
Memory leaks and related phenomena make it impossible to prove program
correctness, since any program anywhere is at risk of its memory being
corrupted by a stray pointer.
In the past, specially-hardware-supported Lisp implementations have
offered this capability, but it involves a lot of bookkeeping in the
memory model to keep it safe, and it adds little or no expressive
power if you measure expressive power by the metric of "capable of
solving problems that can't be solved by other means".
> In this example it would be very useful to pass the address of p to
> the function.
I'd find it useful to drive on the right hand side of the street in
England, too. Sometimes the internal consistency of a system, and the
ways those things come together to offer a coherent whole, has to
dominate the momentary urge to add a feature of convenience for the
convenience of an individual's desire to solve a problem in one way
that can be solved in others.
> Any of you have an idea for this behaviour?
>
> That is, why address opererator is forbidden?
It's not forbidden, it's not offered. You're free to make a Lisp that
offers it and no one will fail to call it not a Lisp. Asking the
question this way around is like asking why restaurants that give out
free food are forbidden. They aren't. It just doesn't lead to a very
good result for the owner. And when the owner can't keep it going, even
the users start to agree that it didn't do very well by them either.
Kent M Pitman <······@nhplace.com> writes:
> It's not forbidden, it's not offered. You're free to make a Lisp that
> offers it and no one will fail to call it not a Lisp. Asking the
> question this way around is like asking why restaurants that give out
> free food are forbidden. They aren't. It just doesn't lead to a very
> good result for the owner. And when the owner can't keep it going, even
> the users start to agree that it didn't do very well by them either.
Another example of the failure of prescriptive ontologies. In France
there are restaurants that give out free food, like the "Restaurants
du Coeur". Unfortunately, they keep going, which is a sign of failure
(but not of the restaurant itself).
;-)
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
"Leslie P. Polzer" <·············@gmx.net> writes:
> On Jun 25, 5:37 am, Dan Bensen <··········@cyberspace.net> wrote:
> > Leslie P. Polzer wrote:
> > > It seems pretty ugly (i.e. not of the smugp kind) to me, though.
> >
> > How about this:
> > (defmacro += (p n) `(setf ,p (nthcdr ,n ,p)))
> >
> > [...]
>
> Also nice. Any specific reason (excluding performance) for using a
> macro here instead of a function?
Lisp isn't call-by-reference. (Strictly, it is call-by-value on pointer
types, but it's easier to perceive as call-by-object-identity.) In any
case, a function can't change the value of a lexical variable in a calling
function.
But while it's useful to complete the analogy in your head by this
naming, please don't call the function this. It just perpetuates a
conceptual crutch that isn't very helpful for Lisp. Hopefuly it's only
the mechanism and not the name you're resonating to.
I don't have time this morning, but someone else reading on can follow
with an explanation of how and why to write a function named NTHCDRF,
if this is the kind of thing you like.
Hi again,
> (defun list+= (start count)
> (nth count start))
^^^ replace NTH with NTHCDR?
Anyway, just to make you aware of the possibility, you could, of
course, define your own macro that acts just like the ++ and +=
operators in C (actually, I don't know whether += does what I think it
should on pointers, but you know what I mean).
CL-USER> (defun list+ (start n)
(nthcdr n start))
LIST+
CL-USER> (define-modify-macro cdrf (&optional (n 1)) list+)
CDRF
CL-USER> (let ((a '(a b c d e f)))
(values a
(cdrf a)
(cdrf a 2)
(cdrf a)))
(A B C D E F)
(B C D E F)
(D E F)
(E F)
Whether that's a good idea is a different question, though.
Bye-bye,
Matthias
"Leslie P. Polzer" <·············@gmx.net> writes:
> Suppose I want to keep track of the current element in a {singly,
> doubly}-linked list (that might be circular) and at some point cleanly
> advance it by one or more steps.
>
> In C I'd do something like that:
>
> list* p = LIST; /* let p initially point to the list head */
> p++; /* might also be p += 5; */
> /* assertion: p always points at the current element of the list */
>
> And would walk it by just saying
>
> while (p++); /* this obviously doesn't work out for circular lists,
> but let's keep things simple */
>
> What's the idiom for this stuff in Lisp? I'm sure there must be some
> smug solution that, as usual, eludes me. Thanks, folks.
I can't speak to the elusive smugp predicate, though it does sound
like the kind of thing that could tolerate some wide-ranging
arguments, but as to the rest of your query:
(loop while list do
... (car list) ... (pop list) ... (dotimes (i 5) (pop list)))
;; In the following, note it's not "in" but "on". See CLHS for details.
(loop for (item . more-items) on list do ...)
(mapl function list)
(maplist function list)
But it's actually more uncommon than you might think to actually need
the backbone. An awful lot of common idioms are covered by the
sequence functions such that you just don't need this. Functions like
mapcar or macros like dolist accommodate quite a lot of these
situations. And many idiomatic uses are covered by functions like remove,
delete, substitute, etc. and reduce.
Also, though some people don't use it as much these days as they once
did, I think because of LOOP has gained more foothold than it once had,
the DO macro is also sometimes useful, since it allows access to a
similar programming style to Scheme's letrec.
(do ((tail list (cdr tail)))
((null tail))
(let ((first (car tail)))
...))
On 24 Jun, 14:25, "Leslie P. Polzer" <·············@gmx.net> wrote:
> Suppose I want to keep track of the current element in a {singly,
> doubly}-linked list (that might be circular) and at some point cleanly
> advance it by one or more steps.
>
> In C I'd do something like that:
>
> list* p = LIST; /* let p initially point to the list head */
> p++; /* might also be p += 5; */
> /* assertion: p always points at the current element of the list */
>
> And would walk it by just saying
>
> while (p++); /* this obviously doesn't work out for circular lists,
> but let's keep things simple */
>
> What's the idiom for this stuff in Lisp? I'm sure there must be some
> smug solution
> that, as usual, eludes me. Thanks, folks.
>
> Leslie
It depends what you're doing.
(dolist (p list)
....operation)
Is equivalent to what you seem to want the C code to do, although
unless you're working in c++ and have overloaded ++ your code is only
suitable for traversing a one dimensional array not a linked list.
If you're mapping the list to another sequence use map, mapcar,
mapcans or one of the many other map functions.
To `shrink' the list down to a single element by repeatedly applying a
single function use reduce.
Alternatively, if you want to manipulate the list by hand, use first,
rest, push, and pop.
The above only hold for singly linked lists, but should keep you going
for a while.
On Jun 24, 4:07 pm, Chris Russell <·····················@gmail.com>
wrote:
> It depends what you're doing.
> (dolist (p list)
> ....operation)
>
> Is equivalent to what you seem to want the C code to do, although
> unless you're working in c++ and have overloaded ++ your code is only
> suitable for traversing a one dimensional array not a linked list.
>
> If you're mapping the list to another sequence use map, mapcar,
> mapcans or one of the many other map functions.
> To `shrink' the list down to a single element by repeatedly applying a
> single function use reduce.
>
> Alternatively, if you want to manipulate the list by hand, use first,
> rest, push, and pop.
Ah, yes -- that would do for walking the list from start to end, but
it doesn't
let me *save a pointer* to some element in between, which is the
central problem
I want to solve in a Lisp way.
Hi,
> Ah, yes -- that would do for walking the list from start to end, but
> it doesn't
> let me *save a pointer* to some element in between, which is the
> central problem
> I want to solve in a Lisp way.
I'm not sure I understand the problem well, but might you by chance be
looking for the functions MAPLIST and MAPL, which map over the cons
cells of a list rather than its elements?
http://www.lispworks.com/documentation/HyperSpec/Body/f_mapc_.htm#maplist
http://www.lispworks.com/documentation/HyperSpec/Body/f_mapc_.htm#mapl
[1]> (mapcar #'identity '(1 2 3 4))
(1 2 3 4)
[2]> (maplist #'identity '(1 2 3 4))
((1 2 3 4) (2 3 4) (3 4) (4))
LOOP is, of course, capable of the same:
[3]> (loop for x in '(1 2 3 4) collect x)
(1 2 3 4)
[4]> (loop for x on '(1 2 3 4) collect x)
((1 2 3 4) (2 3 4) (3 4) (4))
Bye-bye,
Matthias
On 24 Jun, 15:20, "Leslie P. Polzer" <·············@gmx.net> wrote:
> On Jun 24, 4:07 pm, Chris Russell <·····················@gmail.com>
> wrote:
>
> > It depends what you're doing.
> > (dolist (p list)
> > ....operation)
>
> > Is equivalent to what you seem to want the C code to do, although
> > unless you're working in c++ and have overloaded ++ your code is only
> > suitable for traversing a one dimensional array not a linked list.
>
> > If you're mapping the list to another sequence use map, mapcar,
> > mapcans or one of the many other map functions.
> > To `shrink' the list down to a single element by repeatedly applying a
> > single function use reduce.
>
> > Alternatively, if you want to manipulate the list by hand, use first,
> > rest, push, and pop.
>
> Ah, yes -- that would do for walking the list from start to end, but
> it doesn't
> let me *save a pointer* to some element in between, which is the
> central problem
> I want to solve in a Lisp way.
I'm not sure what you want. Can you give us an example?
On 24 Jun, 15:54, Chris Russell <·····················@gmail.com>
wrote:
> On 24 Jun, 15:20, "Leslie P. Polzer" <·············@gmx.net> wrote:
>
>
>
> > On Jun 24, 4:07 pm, Chris Russell <·····················@gmail.com>
> > wrote:
>
> > > It depends what you're doing.
> > > (dolist (p list)
> > > ....operation)
>
> > > Is equivalent to what you seem to want the C code to do, although
> > > unless you're working in c++ and have overloaded ++ your code is only
> > > suitable for traversing a one dimensional array not a linked list.
>
> > > If you're mapping the list to another sequence use map, mapcar,
> > > mapcans or one of the many other map functions.
> > > To `shrink' the list down to a single element by repeatedly applying a
> > > single function use reduce.
>
> > > Alternatively, if you want to manipulate the list by hand, use first,
> > > rest, push, and pop.
>
> > Ah, yes -- that would do for walking the list from start to end, but
> > it doesn't
> > let me *save a pointer* to some element in between, which is the
> > central problem
> > I want to solve in a Lisp way.
>
> I'm not sure what you want. Can you give us an example?
Oh sorry, I think I get it, you want to save a sublist at a given
point.
Use maplist, or something like
(do ((new-list (cons nil list))) ;Protects existing list
((not (setf new-list (rest new-list))))
expression)))
if you favour an imperative expression.
On Sun, 24 Jun 2007 07:20:58 -0700,
"Leslie P. Polzer" <·············@gmx.net> wrote:
>On Jun 24, 4:07 pm, Chris Russell <·····················@gmail.com>
>wrote:
>> It depends what you're doing.
>> (dolist (p list)
>> ....operation)
>>
>> Is equivalent to what you seem to want the C code to do [...]
>
> Ah, yes -- that would do for walking the list from start to end, but
> it doesn't let me *save a pointer* to some element in between, which
> is the central problem I want to solve in a Lisp way.
There are no 'pointers' in Lisp. Once you get past the terminology gap
which separates the two worlds -- the one of C, and the one of Lisp --
you will realize that any Lisp symbol can refer to arbitrary places
within the list, i.e.:
CL-USER> (defparameter *foo* (list 1 2 3))
*FOO*
CL-USER> (defparameter *bar* (member 2 *foo*))
*BAR*
CL-USER> *foo*
(1 2 3)
CL-USER> (cdr *foo*)
(2 3)
CL-USER> (eq (cdr *foo*) *bar*)
T
CL-USER>
At this point, stand back for a while and try to find out why *bar* is
equal to (cdr *foo*). You will see that there is something like this
underneath:
+-----+-----+
*foo* ----> | 1 | #--:----.
+-----+-----+ |
|
.--------------------'
|
`-> +-----+-----+
*bar* ----> | 2 | #--:----.
+-----+-----+ |
|
.--------------------'
|
`-> +-----+-----+
| 3 | |
+-----+-----+
To traverse a list, you just need a symbol to 'point' somewhere inside
the list. This symbol doesn't have to be bound with `defparameter'. It
can be bound with `let' or any other binding construct.
You can even create circular references inside a list by `pointing' to
specific places within the list through a symbol binding:
CL-USER> *print-circle*
NIL
CL-USER> (setf *print-circle* t)
T
CL-USER> (let ((foo (cons 1 2)))
foo)
(1 . 2)
CL-USER> (let ((foo (cons 1 2)))
(setf (cdr foo) foo))
#1=(1 . #1#)
CL-USER>
To use a similar notation with the previous diagram, the above Lisp
expressions evaluate to something like:
+-----+-----+
foo -----> | 1 | #--:----.
.--> +-----+-----+ |
| |
`---------------------'
hence the need to set *print-circle* to T to avoid looping forever when
the Lisp REPL tries to print the value of the last expression.
To summarize, in Lisp, you don't need `pointers' in the C sense, because
every symbol is essentially a pointer to a particular value, and an
arbitrary number of symbols can be bound to the same value.
Giorgos Keramidas wrote:
> "Leslie P. Polzer" <·············@gmx.net> wrote:
>> it doesn't let me *save a pointer* to some element in between, which
>> is the central problem I want to solve in a Lisp way.
>
> There are no 'pointers' in Lisp. Once you get past the terminology gap
> which separates the two worlds -- the one of C, and the one of Lisp --
> you will realize that any Lisp symbol can refer to arbitrary places
> within the list
Getting past the 'terminology gap' is not necessary. All the C pro-
grammer has to remember is that all Lisp variables are references,
i.e. implicit pointers with no C-style pointer arithmetic allowed.
> To traverse a list, you just need a symbol to 'point' somewhere inside
> the list.
I think that's what the OP meant by
>> it doesn't let me *save a pointer* to some element in between
> To summarize, in Lisp, you don't need `pointers' in the C sense, because
> every symbol is essentially a pointer to a particular value, and an
> arbitrary number of symbols can be bound to the same value.
The OP explicitly asked for the "Lisp way" of solving the problem,
which does require implicit pointers in the Lisp sense, and every
C programmer knows that multiple references can point to the same
memory location. So all the OP really needed to know was how to
do what they were describing.
--
Dan
www.prairienet.org/~dsb/
Dan Bensen <··········@cyberspace.net> writes:
> The OP explicitly asked for the "Lisp way" of solving the problem,
> which does require implicit pointers in the Lisp sense, and every
> C programmer knows that multiple references can point to the same
> memory location. So all the OP really needed to know was how to
> do what they were describing.
Well, I hesitated to answer to the OP because he blatantly lied us,
since he mentionned singly and doubly linked lists, but the code he
showed cannot be list processing code in C (it could be in C++, but
he only mentionned C).
"Leslie P. Polzer" <·············@gmx.net> wrote:
> Suppose I want to keep track of the current element in a {singly,
> doubly}-linked list (that might be circular) and at some point cleanly
> advance it by one or more steps.
>
> In C I'd do something like that:
>
> list* p = LIST; /* let p initially point to the list head */
> p++; /* might also be p += 5; */
> /* assertion: p always points at the current element of the list */
>
> And would walk it by just saying
>
> while (p++); /* this obviously doesn't work out for circular lists,
> but let's keep things simple */
>
> What's the idiom for this stuff in Lisp? I'm sure there must be some
> smug solution
> that, as usual, eludes me. Thanks, folks.
Now, if we ignore almost totally the request of the OP, we could say
that one can easily walk a list in lisp. After all, LISP means LISt
Processing.
In the case of a simple singly-linked list:
(let ((p (list 1 2 3 4 5)))
(loop
:while p
:do (process (car p))
:do (pop p)))
or:
(let ((p (list 1 2 3 4 5)))
(loop
:for item :in p
:do (process item)))
or:
(let ((p (list 1 2 3 4 5)))
(dolist (item p)
(process item)))
or:
(map nil (function process) (list 1 2 3 4 5))
etc... There is no single idiom in lisp....
In the case of a circular singly-linked list:
(defun make-circular (list) (setf (cdr (last list)) list))
(let ((p (make-circular (list 1 2 3 4 5))))
(loop
:while (some-condition)
:do (process p)
:do (pop p)))
In the case of doubly-linked lists, it would depend on the data
structure used for them.
For example, with a non-circular dll:
(defstruct dll next previous item)
(defun dll-first (dll)
(loop
:until (null (dll-previous dll))
:do (setf dll (dll-first (dll-previous dll)))
:finally (return dll)))
(defun dll-list (&rest items)
(loop
:with dll = (make-dll)
:while items
:do (setf (dll-next dll) (make-dll :item (car items) :previous dll)
dll (dll-next dll))
:finally (return (dll-first dll))))
Then you can write:
(let ((p (dll-list 1 2 3 4 5)))
(loop
:while p
:do (process (dll-item p))
:do (setf p (dll-next p))))
or:
(let ((p (dll-list 1 2 3 4 5)))
(loop
:for cur = p :then (dll-next cur)
:do (process (dll-item cur))))
etc...
I still don't see the point of the OP's question...
On the other hand, in C I'd write something like:
{ dll* p=dll_list(5,1,2,3,4,5);
while(!dll_empty_p(p)){
process(dll_item(p));
p=dll_next(p); }}
so...
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
> "Leslie P. Polzer" <·············@gmx.net> wrote:
>> Suppose I want to keep track of the current element in a {singly,
>> doubly}-linked list (that might be circular) and at some point
>> cleanly advance it by one or more steps.
Pascal Bourguignon wrote:
> Well, I hesitated to answer to the OP because he blatantly lied us,
> since he mentionned singly and doubly linked lists, but the code he
> showed cannot be list processing code in C
With all due respect, Pascal, that's the most ridiculous thing I've
heard this month. To use such strong language in response to a simple
technical issue, it's no wonder many people are put off by the Lisp
community. The logic of the question has nothing to do with the
presence or absence of a "previous" link.
>> In C I'd do something like that:
>> p++; /* might also be p += 5; */
>> What's the idiom for this stuff in Lisp? I'm sure there must be
>> some smug solution that, as usual, eludes me. Thanks, folks.
> I still don't see the point of the OP's question...
Assuming "this stuff" refers to "p++" and "p += 5", the question
would seem to be how one implements that functionality in Lisp.
Perhaps you didn't like the "smug" descriptor? I don't think it was
meant seriously. I sort of like it :)
--
Dan
www.prairienet.org/~dsb/
Dan Bensen <··········@cyberspace.net> writes:
>> "Leslie P. Polzer" <·············@gmx.net> wrote:
>>> Suppose I want to keep track of the current element in a {singly,
>>> doubly}-linked list (that might be circular) and at some point
>>> cleanly advance it by one or more steps.
>
> Pascal Bourguignon wrote:
>> Well, I hesitated to answer to the OP because he blatantly lied us,
>> since he mentionned singly and doubly linked lists, but the code he
>> showed cannot be list processing code in C
>
> With all due respect, Pascal, that's the most ridiculous thing I've
> heard this month. To use such strong language in response to a simple
> technical issue, it's no wonder many people are put off by the Lisp
> community. The logic of the question has nothing to do with the
> presence or absence of a "previous" link.
Indeed, and my reasoning doesn't involve presence or absence of a
"previous" link, but the presence of absence of ANY link, vs the
pointer arithmetic used. When you follow links, you don't do pointer
arithmetic in C. When you do pointer arithmetic in C you aren't
dealing with lists, but with vectors (what they call "arrays").
>>> In C I'd do something like that:
>>> p++; /* might also be p += 5; */
>>> What's the idiom for this stuff in Lisp? I'm sure there must be
>>> some smug solution that, as usual, eludes me. Thanks, folks.
>
>> I still don't see the point of the OP's question...
>
> Assuming "this stuff" refers to "p++" and "p += 5", the question
> would seem to be how one implements that functionality in Lisp.
> Perhaps you didn't like the "smug" descriptor? I don't think it was
> meant seriously. I sort of like it :)
>
> --
> Dan
> www.prairienet.org/~dsb/
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
On Jun 27, 9:40 pm, Pascal Bourguignon <····@informatimago.com> wrote:
> Indeed, and my reasoning doesn't involve presence or absence of a
> "previous" link, but the presence of absence of ANY link, vs the
> pointer arithmetic used. When you follow links, you don't do pointer
> arithmetic in C. When you do pointer arithmetic in C you aren't
> dealing with lists, but with vectors (what they call "arrays").
You are right, of course; I should have been more careful.
This might have happened because arrays, pointers and lists
kind of mix up in my head (on a high level). Iterators
from C++ might have lumbered in the back of my head, too.
Who knows, some days have passed since :)
The main focus of my OP was to convey the idea of saving pointers
between function calls, though (as opposed to saving indices to
an array/vector).
I'll try to be more rigorous in my coming posts.
Thanks for slapping me around with a large trout.
Best,
Leslie
Pascal Bourguignon wrote:
> Dan Bensen <··········@cyberspace.net> writes:
>> The logic of the question has nothing to do with the
>> presence or absence of a "previous" link.
>
> Indeed, and my reasoning doesn't involve presence or absence of a
> "previous" link, but the presence of absence of ANY link, vs the
> pointer arithmetic used. When you follow links, you don't do pointer
> arithmetic in C. When you do pointer arithmetic in C you aren't
> dealing with lists, but with vectors (what they call "arrays").
You're right, the OP could have been more careful about that. I just
assumed the ++ operator was overloaded to follow cdr links for a
list pointer type. Even though it's not valid C, you could always
add a "++" to the C and discuss that :)
--
Dan
www.prairienet.org/~dsb/
On Wed, 27 Jun 2007 21:40:59 +0200, Pascal Bourguignon wrote:
> Indeed, and my reasoning doesn't involve presence or absence of a
> "previous" link, but the presence of absence of ANY link, vs the
> pointer arithmetic used. When you follow links, you don't do pointer
> arithmetic in C. When you do pointer arithmetic in C you aren't
> dealing with lists, but with vectors (what they call "arrays").
Those aren't usually circular, though, so while I think that the OP was
probably just being unreasonably flip, perhaps he's using some magic C++
iterator juju and calling it C by mistake.
Where's the harm in asking for more information, or just jumping straight
to offering caddr or nth as options?
Cheers,
--
Andrew
On Wed, 27 Jun 2007 06:11:42 -0500, Dan Bensen <··········@cyberspace.net> wrote:
>Giorgos Keramidas wrote:
>> "Leslie P. Polzer" <·············@gmx.net> wrote:
>>> it doesn't let me *save a pointer* to some element in between, which
>>> is the central problem I want to solve in a Lisp way.
>>
>> There are no 'pointers' in Lisp. Once you get past the terminology gap
>> which separates the two worlds -- the one of C, and the one of Lisp --
>> you will realize that any Lisp symbol can refer to arbitrary places
>> within the list
>
> Getting past the 'terminology gap' is not necessary. All the C pro-
> grammer has to remember is that all Lisp variables are references,
> i.e. implicit pointers with no C-style pointer arithmetic allowed.
I don't really like the confusion which may result from treating Lisp
``symbols'' are C ``pointers''. Mostly because then the need arises for
clarifications of the sort you just mentioned (``implicit pointers with
no C-style pointer arithmetic allowed''). Referring to Lisp symbols as
``pointers'' is not exactly correct. There is a perfectly fine way to
refer to them, and that is by using the word ``symbols'', so that's why
I mentioned terminology. Sometimes, getting the wording correct
facilitates better understanding, but YMMV since we are human after all,
and everyone has their own way of understanding something :)
>> To traverse a list, you just need a symbol to 'point' somewhere inside
>> the list.
>
> I think that's what the OP meant by
>
>>> it doesn't let me *save a pointer* to some element in between
Right. I just rephrased the original text in a more ``Lispy way'' :-)
>> To summarize, in Lisp, you don't need `pointers' in the C sense, because
>> every symbol is essentially a pointer to a particular value, and an
>> arbitrary number of symbols can be bound to the same value.
>
> The OP explicitly asked for the "Lisp way" of solving the problem,
> which does require implicit pointers in the Lisp sense, and every C
> programmer knows that multiple references can point to the same memory
> location. So all the OP really needed to know was how to do what they
> were describing.
Which I demonstrated with an example of two symbols pointing to parts of
the same Lisp object. I don't see what you found wrong about my post,
but if you have a better idea to do what the OP asked, then please feel
free to post a better example. I'm not really a Lisp guru, so it may be
educational for me too.
- Giorgos
>>> "Leslie P. Polzer" <·············@gmx.net> wrote:
>>>> it doesn't let me *save a pointer* to some element in between,
>>>> which is the central problem I want to solve in a Lisp way.
>> Giorgos Keramidas wrote:
>>> There are no 'pointers' in Lisp. Once you get past the terminology gap
>>> which separates the two worlds -- the one of C, and the one of Lisp --
>>> you will realize that any Lisp symbol can refer to arbitrary places
>>> within the list
> Dan Bensen <··········@cyberspace.net> wrote:
>> Getting past the 'terminology gap' is not necessary. All the C pro-
>> grammer has to remember is that all Lisp variables are references,
>> i.e. implicit pointers with no C-style pointer arithmetic allowed.
Giorgos Keramidas wrote:
> I don't really like the confusion which may result from treating
> Lisp ``symbols'' are C ``pointers''.
There's no confusion for C programmers, and it's variables that are
pointers, not symbols. As Pascal said,
> A symbol can conceptually be considered as a structure of 5 slots:
> (defstruct symbol package name function value plist)
This description makes perfect sense to a C programmer. A variable
can point to a symbol, and the slots in the symbol point to data.
> Mostly because then the need arises for clarifications
> of the sort you just mentioned (``implicit pointers
> with no C-style pointer arithmetic allowed'').
Again, that's not a problem for a C programmer.
> Referring to Lisp symbols as ``pointers'' is not exactly correct.
It's not even close to correct, but I think we've covered that now.
> There is a perfectly fine way to refer to them, and that is by
> using the word ``symbols'', so that's why I mentioned terminology.
That's not familiar to a C programmer. C programmers understand
pointers very well, but not symbols.
> Sometimes, getting the wording correct facilitates better understanding
That applies to all of us. Here's what I said:
> All the C programmer has to remember is that
> all Lisp ***variables*** are references
> but YMMV since we are human after all, and everyone
> has their own way of understanding something :)
Yes, that's true, and I understand that what you're saying probably
makes sense to a long-time Lisper who may not know C. The OP isn't
an experienced Lisper though, so using their language is probably
more helpful.
>>> To summarize, in Lisp, you don't need `pointers' in the C sense, because
>>> every symbol is essentially a pointer to a particular value, and an
>>> arbitrary number of symbols can be bound to the same value.
>> The OP explicitly asked for the "Lisp way" of solving the problem,
>> which does require implicit pointers in the Lisp sense, and every C
>> programmer knows that multiple references can point to the same memory
>> location. So all the OP really needed to know was how to do what they
>> were describing.
> Which I demonstrated with an example of two symbols pointing to parts of
> the same Lisp object. I don't see what you found wrong about my post
The "terminology gap" comment ("you will realize") suggested that
(1) the OP didn't know that more than one reference can point to the
same object, and (2) the only way to cure that ignorance was to submit
to the Lisp Way (TM).
"At this point, stand back ... You will see ..."
Again, this comment suggests that the reader must Behold the
Magnificence of Lisp to understand. Note, btw, that your little arrows
seem to be *pointing* at the data structures, as you yourself even
mentioned:
"To traverse a list, you just need a symbol to 'point'
somewhere inside the list."
Where, to beat an already-dead horse, "symbol" should read "variable".
I understand that symbols are obviously an integral part of Lisp,
but there really are other ways to describe things that people with
other backgrounds will understand better. To more fully address
this comment at the beginning of your post:
"There are no 'pointers' in Lisp."
Lisp is ALL pointers. EVERY variable, EVERY slot in EVERY object
or structure, is a reference to a piece of data. In Lisp, there's
no such thing as directly embedding one object inside another,
as is done in C and C++. There's no such thing as actually
passing an object to a function. The only thing you can contain in
an object or pass to a function is an implicit pointer to the object.
If you want to pass a new copy of the object, you have to explicitly
create the copy, and pass a reference to it.
--
Dan
www.prairienet.org/~dsb/
Dan Bensen <··········@cyberspace.net> wrote:
+---------------
| Lisp is ALL pointers. EVERY variable, EVERY slot in EVERY object
| or structure, is a reference to a piece of data. In Lisp, there's
| no such thing as directly embedding one object inside another,
| as is done in C and C++. There's no such thing as actually
| passing an object to a function. The only thing you can contain in
| an object or pass to a function is an implicit pointer to the object.
+---------------
This is conceptually true as far as it goes, and I certainly agree
that it is is indeed the best way to present it to new users. And
in fact, for some (small) Lisp implementations [the original SIOD
Scheme comes to mind], it's the *exact* truth.
But, as with many esoterica, there is sometimes a further level
of truth, which in this instance is that *if* a particular Lisp
data type is immutable [has no components with setters] *and*
if a datum in that type can be represented in the same amount of
space as a generic Lisp reference without conflict [perhaps by
using a few bits of the "reference" as a "tag" or discriminator],
*then* the implementation is permitted to pass [copies of] the
entire object around, store them inside other [mutable] objects,
and so on. Such objects are usually called "immediates", and
many Lisps use such immediates for FIXNUMs, BASE-CHARs [though
not Unicode characters], and other small constants [e.g., an
"unbound" marker, perhaps NIL, and Schemes often use them for
#F, #T, #EOF, & #VOID (a.k.a. a zero-values marker)].
But this is merely an efficiency hack, and is not even normally
*observable* by the Lisp programmer, with one exception -- two
freshly created instances of such an "immediate" type may compare
as EQ, whereas for non-immediates EQ would fail but EQUAL [or
maybe EQL] would succeed. E.g.:
> (let ((a (eval (read-from-string "(+ 2 3)")))
(b (parse-integer "000101" :radix 2)))
(eq a b))
T
>
So in the implementation I used to run that example,
FIXNUMs are probably encoded as immediates.
+---------------
| If you want to pass a new copy of the object, you have to explicitly
| create the copy, and pass a reference to it.
+---------------
Again, except for immediates, where a copy of the "reference" *is*
a new copy of the "object".
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) writes:
> But this is merely an efficiency hack, and is not even normally
> *observable* by the Lisp programmer, with one exception -- two
> freshly created instances of such an "immediate" type may compare
> as EQ, whereas for non-immediates EQ would fail but EQUAL [or
> maybe EQL] would succeed. E.g.:
>
> > (let ((a (eval (read-from-string "(+ 2 3)")))
> (b (parse-integer "000101" :radix 2)))
> (eq a b))
>
> T
> >
>
> So in the implementation I used to run that example,
> FIXNUMs are probably encoded as immediates.
But in others they might not be. And without talking to the vendor or
reading the source code, I don't think you could so easily infer the
truth. Your analysis might be right in some cases, but perhaps not in
others.
In Maclisp, almost all fixnums were heap-consed (except in specific
immediate communication), BUT in order to save space [we only had 18
bits of word-addressed data, or 256K words = 1.25 MB], "small" fixnums
were interned. Consequently, (eq (eval '(+ 1 1)) (eval '(- 3 1))) was
likely to return T in Maclisp, for example, even though
(eq (eval '(+ 5000 1)) (eval '(- 5002 1))) would return NIL, and even
though numbers up to well over 5000 were still fixnums [as a 36-bit
machine, fixnums went to 2^35-1, I believe].
Now, Maclisp was not CL. But my point is that there are legitimate
implementation strategies that could decide to "intern" or "coalesce"
or "EQ-ify" fixnums. So I don't agree that EQ exposes immediate
data--it exposes some form of address gaming, but the nature of that
address gaming is sometimes tricky to infer merely from its effects.
> +---------------
> | If you want to pass a new copy of the object, you have to explicitly
> | create the copy, and pass a reference to it.
> +---------------
>
> Again, except for immediates, where a copy of the "reference" *is*
> a new copy of the "object".
I think the right way to understand integers and characters is that
they are not immediates or non-immediates, but are rather things that
have no side-effecting operators, and hence are permitted to have
loose identities. I haven't thought about this issue in a while, so
maybe I just have some important bit of info paged out of my brain,
but I don't think there is no way to either reliably copy them OR
reliably NOT copy them in a portable way. In general, people who are
uncomfortable with that should use EQL and simply ignore the presence
of EQ.
But calling them immediates when talking about Lisp-level abstractions
probably confuses matters, even though subprimitively indeed
representing them as immediates is a possible implementation choice
that would have various consequences on the Lisp-visible side.
I just think we should avoid that. It's ok to do by analogy, to help
someone get a vague handhold on the fact that the world over here
might be different than in other languges, but not to lead anyone to
think that we just have a contorted way of saying immediate without
owning up to it. It isn't that. We have a way of allowing immediates
and pointers to be used freely and interchangeably in some contexts as
implementation strategies, and a language that is defined such that
these things don't matter.
Kent M Pitman <······@nhplace.com> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) writes:
| > But this is merely an efficiency hack, and is not even normally
| > *observable* by the Lisp programmer, with one exception -- two
| > freshly created instances of such an "immediate" type may compare
| > as EQ, whereas for non-immediates EQ would fail but EQUAL [or
| > maybe EQL] would succeed. E.g.:
| > > (let ((a (eval (read-from-string "(+ 2 3)")))
| > (b (parse-integer "000101" :radix 2)))
| > (eq a b))
| > T
| > >
| > So in the implementation I used to run that example,
| > FIXNUMs are probably encoded as immediates.
|
| But in others they might not be. And without talking to the vendor or
| reading the source code, I don't think you could so easily infer the
| truth. Your analysis might be right in some cases, but perhaps not in
| others.
+---------------
True. I was not trying to say that EQ is any kind of reliable test
for immediates. Rather, I was saying that the use by an implementation
of immediates for some data types *might* be observable by the Lisp
programmer, even without poking under the hood [reading the source
or "peek"ing at memory].
+---------------
| In Maclisp, almost all fixnums were heap-consed (except in specific
| immediate communication), BUT in order to save space [we only had 18
| bits of word-addressed data, or 256K words = 1.25 MB], "small" fixnums
| were interned. Consequently, (eq (eval '(+ 1 1)) (eval '(- 3 1))) was
| likely to return T in Maclisp, for example, even though
| (eq (eval '(+ 5000 1)) (eval '(- 5002 1))) would return NIL, and even
| though numbers up to well over 5000 were still fixnums [as a 36-bit
| machine, fixnums went to 2^35-1, I believe].
+---------------
Just so. Indeed, SIOD Scheme (which I mentioned as an example of a
Lisp in which *all* values are references to objects) also pre-interned
some number of small positive integers[1] at startup time. Early versions
defaulted to only 100, but later versions defaulted to 2048 (but all
allowed changing that on the comamnd line). All arithmetic operators
checked to see if the current value being returned was an integer[1]
within the (currently-)interned range, and if so, calculated a reference
to the pre-interned value, else consed up a new one from the heap.
[1] Well, SIOD actually had only double floats, but it would pre-intern
objects for 0.0d0, 1.0d0, 2.0d0, etc., and then the arithmetic
would check to see if for some double float result "x" whether
(x - (n = (long)x)) == 0 were true and if 0 <= n < inums_dim
were also true, and if so return inums[n].
+---------------
| Now, Maclisp was not CL. But my point is that there are legitimate
| implementation strategies that could decide to "intern" or "coalesce"
| or "EQ-ify" fixnums. So I don't agree that EQ exposes immediate
| data--it exposes some form of address gaming, but the nature of that
| address gaming is sometimes tricky to infer merely from its effects.
+---------------
No argument. So let me try to rephrase a bit. The person I was
replying to suggested that we tell Lisp newbies that *all* Lisp
values are references to objects. I was pointing out that while
that is a good thing in general [and is even literally true in
some Lisps], some values *might* be immediate data rather than
heap references per se, and that those *might* be detectable
without "going under the covers".
You have now pointed out that (pre-)interned data values (either
statically-allocated or heap objects) might be indistinguishable
from immediate data values, at least with respect to EQ, which I
certainly *should* have mentioned, given that I had already made
refernce to SIOD!! D'oh! ;-} ;-}
In fact, I can't immediately [pardon the pun] think of any way
[without "going under the covers"] for the Lisp programmer to
*ever* distinguish values implemented as immediates from values
implemented as references to (continually re-)interned objects.[2]
Can you?
[2] I use the nonce term "continually re-interned objects" to
include not only the possible re-interning of arithmetic
results, as in the above, but also other possible object
types which might behave similarly. E.g., I'm told that in
Java the [immutable] String is such a type (i.e., that the
results of, e.g., StringAppend are automatically interned),
while mutable arrays of characters are not.
+---------------
| > +---------------
| > | If you want to pass a new copy of the object, you have to
| > | explicitly create the copy, and pass a reference to it.
| > +---------------
| >
| > Again, except for immediates, where a copy of the "reference"
| > *is* a new copy of the "object".
|
| I think the right way to understand integers and characters is that
| they are not immediates or non-immediates...
+---------------
Sorry, I didn't mean to fixate on small integers or characters.
It's just that those were examples that were close at hand on
my favorite CL implementation. Indeed, I already noted that in
Unicode-aware implementations characters are probably *not*
immediates [though they *might* be interned, and if so, indis-
tinguishable from immediates]. I was just trying make sure that
a crack was left open in the "all Lisp objects are references"
teaching, so that newbies wouldn't feel lied to if/when they
eventually learned that it wasn't *always* true. Maybe I went
a bit too far, I dunno.
+---------------
| But calling them immediates when talking about Lisp-level abstractions
| probably confuses matters, even though subprimitively indeed
| representing them as immediates is a possible implementation choice
| that would have various consequences on the Lisp-visible side.
|
| I just think we should avoid that. It's ok to do by analogy, to help
| someone get a vague handhold on the fact that the world over here
| might be different than in other languges, but not to lead anyone to
| think that we just have a contorted way of saying immediate without
| owning up to it. It isn't that. We have a way of allowing immediates
| and pointers to be used freely and interchangeably in some contexts as
| implementation strategies, and a language that is defined such that
| these things don't matter.
+---------------
Yes, that's all I was trying to convey: "All Lisp objects are
references, all the time... [except that if you plan to become
an implementor (or an FFI designer) some day you should know
that under the covers they might not always all be references
to heap objects]".
I was also exploring the extent to which the "immediate"
optimization might be programmer-visible but I think you've
probably convinced me that it's indistiguishable from
continually re-interned heap object types.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) writes:
> [...] I was not trying to say that EQ is any kind of reliable test
> for immediates. Rather, I was saying that the use by an implementation
> of immediates for some data types *might* be observable by the Lisp
> programmer, even without poking under the hood [reading the source
> or "peek"ing at memory].
Right. Observable does not imply "can be inverted". I agree.
Although I felt a little guilty provoking such a long-answer reply, when
we're probably in agreement in the first place, I do think it's worth
underscoring it for readers who might be confused.
And I did enjoy the read, since I haven't looked in detail at SIOD. I
didn't know that (but am not surprised that) SIOD had these interned
numbers. If I recall, George Carrette wrote SIOD. He was part of the
Maclisp community, too, and was surely quite familiar with this practice
of Maclisp's, so probably brought that idea from there.
> SIOD Scheme (which I mentioned as an example of a
> Lisp in which *all* values are references to objects) also pre-interned
> some number of small positive integers[1] at startup time. Early versions
> defaulted to only 100, but later versions defaulted to 2048 (but all
> allowed changing that on the comamnd line).
In Maclisp, as I recall, the number was not hard wired. It was a
fixed number (a few hundred, I think) plus the number of extra words
at the end of the last code page... so as not to waste any of the
space in that ridiculously small address space. The issue there was
not equality, it was compactness. I suppose it meant the possibility
that code that ran in one release wouldn't run in another due to
unrelated changes. ;)
Giorgos Keramidas <········@ceid.upatras.gr> writes:
> On Wed, 27 Jun 2007 06:11:42 -0500, Dan Bensen <··········@cyberspace.net> wrote:
>>Giorgos Keramidas wrote:
>>> "Leslie P. Polzer" <·············@gmx.net> wrote:
>>>> it doesn't let me *save a pointer* to some element in between, which
>>>> is the central problem I want to solve in a Lisp way.
>>>
>>> There are no 'pointers' in Lisp. Once you get past the terminology gap
>>> which separates the two worlds -- the one of C, and the one of Lisp --
>>> you will realize that any Lisp symbol can refer to arbitrary places
>>> within the list
>>
>> Getting past the 'terminology gap' is not necessary. All the C pro-
>> grammer has to remember is that all Lisp variables are references,
>> i.e. implicit pointers with no C-style pointer arithmetic allowed.
>
> I don't really like the confusion which may result from treating Lisp
> ``symbols'' are C ``pointers''. Mostly because then the need arises for
> clarifications of the sort you just mentioned (``implicit pointers with
> no C-style pointer arithmetic allowed''). Referring to Lisp symbols as
> ``pointers'' is not exactly correct. There is a perfectly fine way to
> refer to them, and that is by using the word ``symbols'', so that's why
> I mentioned terminology. Sometimes, getting the wording correct
> facilitates better understanding, but YMMV since we are human after all,
> and everyone has their own way of understanding something :)
Indeed.
Assuming this purpose is legit, using symbols for it is not even the
best way to do it, for example memory wise.
A symbol can conceptually be considered as a structure of 5 slots:
(defstruct symbol package name function value plist)
A cons which can conceptually be considered as a structure of only 2
slots: (defstruct cons car cdr)
would be more memory efficient to do the same.
Using a mere vector or structure of one slot would seem to be even
more efficient than a cons cell, but internally the type of one slot
vectors or structure will probably take at least one additionnal slot
and be at least as big as a cons cell.
But really, this kind of "boxing" would really be needed only if one
would like to modify a binding to a number or character. All the
other lisp objects are potentially mutable by themselves and are
always accessed via implicit references so you don't need any explicit
pointer: just bind them to your variables or parameters.
>>> To traverse a list, you just need a symbol to 'point' somewhere inside
>>> the list.
>>
>> I think that's what the OP meant by
>>
>>>> it doesn't let me *save a pointer* to some element in between
>
> Right. I just rephrased the original text in a more ``Lispy way'' :-)
>
>>> To summarize, in Lisp, you don't need `pointers' in the C sense, because
>>> every symbol is essentially a pointer to a particular value, and an
>>> arbitrary number of symbols can be bound to the same value.
>>
>> The OP explicitly asked for the "Lisp way" of solving the problem,
>> which does require implicit pointers in the Lisp sense, and every C
>> programmer knows that multiple references can point to the same memory
>> location. So all the OP really needed to know was how to do what they
>> were describing.
>
> Which I demonstrated with an example of two symbols pointing to parts of
> the same Lisp object. I don't see what you found wrong about my post,
> but if you have a better idea to do what the OP asked, then please feel
> free to post a better example. I'm not really a Lisp guru, so it may be
> educational for me too.
I would not call a list a lisp object. NIL is a symbol is a lisp
object. A CONS cell is a lisp object. But a list, when you consider
the set of ordered elements in it, is not a single lisp object, but
several lisp objects chained in a sequence of CONS cells. That's why
you can easily refer to tails of a list: you just need to refer to the
CONS cell, lisp object, you're interested in.
You can bind several different variables to the same lisp object,
including the same CONS cell in the middle of a list.
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
Leslie P. Polzer wrote:
> What's the idiom for this stuff in Lisp?
Sounds like you'll be needing tail recursion...
--
Dr Jon D Harrop, Flying Frog Consultancy
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?usenet