i was inspired by the fibonacci function which came up in one of the
threads and decided to write my own.
here is what i came up with as a first cut (yes, it makes a list of
length n+2 but i'll fix that eventually...)
(defun fib-list (n)
"make a list of fibonacci numbers"
(let ((acc '(1 1)))
(dotimes (i n)
(let ((c (+ (car acc) (cadr acc))))
(push c acc)))
(nreverse acc)))
when i go to run this beast, i get
> (fib-list 4)
(1 1 2 3 5 8)
and think so far so good. but then i run it again and get
> (fib-list 4)
(8 5 3 2 1 3 4 7 11)
what is going on here?
i try to debug by inserting a prin1 and running it again
(defun fib-list (n)
"make a list of fibonacci numbers"
(let ((acc '(1 1)))
(prin1 acc)
(dotimes (i n)
(let ((c (+ (car acc) (cadr acc))))
(push c acc)))
(nreverse acc)))
now i am getting this
FIB-LIST ; <- run the defun
> (fib-list 4)
(1 1) ; <- acc being initialized correctly
(1 1 2 3 5 8)
> (fib-list 4)
(1 2 3 5 8) ; <- wtf?!
(8 5 3 2 1 3 4 7 11)
> (fib-list 4)
(1 3 4 7 11)
(11 7 4 3 1 4 5 9 14)
have i totally misunderstood the meaning of let here? do i have some
sort of closure situation i am not seeing?
ok, let me try and force the issue and explicitly setf the wayward acc
(defun fib-list (n)
"make a list of fibonacci numbers"
(let ((acc '(1 1)))
(setf acc '(1 1))
(prin1 acc)
(dotimes (i n)
(let ((c (+ (car acc) (cadr acc))))
(push c acc)))
(nreverse acc)))
still the same. swapping setf for setq also gives no change.
when i swap nreverse for reverse, this whole problem goes away. how
does nreverse differ from reverse besides trashing its arg? how far
does its swath of destruction extend?
i am using clisp. is this some sort of a clisp bug? i shall try this
at with ACL later tonight.
thanks for any elightenment.
--
johan kullstam
Johan Kullstam wrote:
>
> i was inspired by the fibonacci function which came up in one of the
> threads and decided to write my own.
>
> here is what i came up with as a first cut (yes, it makes a list of
> length n+2 but i'll fix that eventually...)
>
> (defun fib-list (n)
> "make a list of fibonacci numbers"
> (let ((acc '(1 1)))
> (dotimes (i n)
> (let ((c (+ (car acc) (cadr acc))))
> (push c acc)))
> (nreverse acc)))
Try the below. See if you can figure out why this *little* change makes
a difference. If you can't figure it out, I'll tell you. Here is a clue:
of constants and destructive operations!
(defun fib-list (n)
"make a list of fibonacci numbers"
(let ((acc (list 1 1)))
(dotimes (i n)
(let ((c (+ (car acc) (cadr acc))))
(push c acc)))
(nreverse acc)))
--
Christopher J. Vogt - http://members.home.com/vogt/
"Christopher J. Vogt" <····@computer.org> writes:
> Johan Kullstam wrote:
> >
> > i was inspired by the fibonacci function which came up in one of the
> > threads and decided to write my own.
> >
> > here is what i came up with as a first cut (yes, it makes a list of
> > length n+2 but i'll fix that eventually...)
> >
> > (defun fib-list (n)
> > "make a list of fibonacci numbers"
> > (let ((acc '(1 1)))
> > (dotimes (i n)
> > (let ((c (+ (car acc) (cadr acc))))
> > (push c acc)))
> > (nreverse acc)))
>
>
>
> Try the below. See if you can figure out why this *little* change makes
> a difference. If you can't figure it out, I'll tell you. Here is a clue:
> of constants and destructive operations!
>
> (defun fib-list (n)
> "make a list of fibonacci numbers"
> (let ((acc (list 1 1)))
> (dotimes (i n)
> (let ((c (+ (car acc) (cadr acc))))
> (push c acc)))
> (nreverse acc)))
thanks for the prompt answer. thanks to gareth and nick as well.
i see now that '(1 1) was not being copied but it got pointed to by
acc. i see i can avoid the problem by using (list 1 1) or (copy-list
'(1 1)).
hmm that was subtle, but i am learning.
now i have a new conundrum. here is my 2nd attempt where i avoid
(n)reverse altogether (not sure if it doesn't cons so hard that it's
not worth it but anyhow)
(defun fib-list-2 (n)
(let ((acc '(1 1)))
(labels ((rec (i k a)
(setf (cdr a) (list (+ k (car a))))
(when (> i 0)
(rec (- i 1) (car a) (cdr a)))))
(rec (- n 3) (car acc) (cdr acc)))
acc))
running this at home in ACL i get
USER(5): (fib-list-2 5)
(1 1 2 3 5)
USER(6): (fib-list-2 5)
(1 1 2 3 5)
USER(7): (fib-list-2 7)
(1 1 2 3 5 8 13)
somehow '(1 1) does *not* get altered despite my attacking the cdr.
acc does in fact accumulate the whole thing. why is this? by analogy
to the pointer mechanism exhibited by my earlier attempt, i expected
'(1 1) to get extended.
USER(8): (setq *foo* '(1 2))
(1 2)
USER(9): (setq *bar* *foo*)
(1 2)
USER(10): (setf (cddr *bar*) '(3))
(3)
USER(11): *bar*
(1 2 3)
USER(12): *foo*
(1 2 3)
here *foo* gets hit. i am not sure what happens to the '(1 2) in USER(8).
--
Johan Kullstam [········@ne.mediaone.net] Don't Fear the Penguin!
Johan Kullstam wrote:
>
> "Christopher J. Vogt" <····@computer.org> writes:
>
> > Johan Kullstam wrote:
> [...]
>
> i see now that '(1 1) was not being copied but it got pointed to by
> acc. i see i can avoid the problem by using (list 1 1) or (copy-list
> '(1 1)).
>
> hmm that was subtle, but i am learning.
Indeed it is subtle, and just about every Lisp programmer has been bit
by this when she was learning Lisp, and will never forget the lesson.
>[...]
>
> USER(8): (setq *foo* '(1 2))
> (1 2)
*foo* is now a pointer to the list: '(1 2)
> USER(9): (setq *bar* *foo*)
> (1 2)
*bar* is now a pointer TO THE SAME LIST as *foo*, not a copy
> USER(10): (setf (cddr *bar*) '(3))
> (3)
You have just replaced the cddr of the list that *bar* points to with '(3)
so now the list that *bar* points to (which is the exact same list that
*foo* points to, now has a list of three elements: (1 2 3)
> USER(11): *bar*
> (1 2 3)
> USER(12): *foo*
> (1 2 3)
>
> here *foo* gets hit. i am not sure what happens to the '(1 2) in USER(8).
you seem surprised ;-)
--
Christopher J. Vogt - http://members.home.com/vogt/
"Christopher J. Vogt" <····@computer.org> writes:
> Johan Kullstam wrote:
> >
> > "Christopher J. Vogt" <····@computer.org> writes:
> >
> > > Johan Kullstam wrote:
>
> > [...]
>
> >
> > i see now that '(1 1) was not being copied but it got pointed to by
> > acc. i see i can avoid the problem by using (list 1 1) or (copy-list
> > '(1 1)).
> >
> > hmm that was subtle, but i am learning.
>
> Indeed it is subtle, and just about every Lisp programmer has been bit
> by this when she was learning Lisp, and will never forget the lesson.
>
> >[...]
> >
> > USER(8): (setq *foo* '(1 2))
> > (1 2)
>
> *foo* is now a pointer to the list: '(1 2)
>
> > USER(9): (setq *bar* *foo*)
> > (1 2)
>
> *bar* is now a pointer TO THE SAME LIST as *foo*, not a copy
>
> > USER(10): (setf (cddr *bar*) '(3))
> > (3)
>
> You have just replaced the cddr of the list that *bar* points to with '(3)
> so now the list that *bar* points to (which is the exact same list that
> *foo* points to, now has a list of three elements: (1 2 3)
>
> > USER(11): *bar*
> > (1 2 3)
> > USER(12): *foo*
> > (1 2 3)
> >
> > here *foo* gets hit. i am not sure what happens to the '(1 2) in USER(8).
>
> you seem surprised ;-)
it's not the *foo* *bar* game that surprises me. it was the function
you deleted.
(defun fib-list-2 (n)
(let ((acc '(1 1)))
(labels ((rec (i k a)
(setf (cdr a) (list (+ k (car a))))
(when (> i 0)
(rec (- i 1) (car a) (cdr a)))))
(rec (- n 3) (car acc) (cdr acc)))
acc))
i managed to figuret it out later this time.
this one works - it gives the right result. but is ugly and has a
flaw. again the constant '(1 1) gets altered just like *foo* and
*bar*. however, rec is getting passed the car and cdr and it ignores
the rest of the list. it proceeds to construct over top of the cddr
of the `constant' '(1 1). the flaw is that 1) i am destroying a
constant and worse 2) the constant can be rather large, can't be
accessed and i assume won't be GC'd.
thanks again. i really appreciate the help. btw this is not a
homework. i am not taking a class and people at work think i am
insane for trying to learn lisp. apparently C++ is the one true
language. well maybe fortran is acceptible, but lisp out.
this is just me fiddling around with my own exercises to get up to
speed. i am slowly beginning to appreciate lisp. i am hoping for a
lisp resurgence. it's not just for ai anymore.
--
Johan Kullstam [········@ne.mediaone.net] Don't Fear the Penguin!
Christopher J. Vogt wrote:
> > i see now that '(1 1) was not being copied but it got pointed to by
> > acc. i see i can avoid the problem by using (list 1 1) or (copy-list
> > '(1 1)).
> >
> > hmm that was subtle, but i am learning.
>
> Indeed it is subtle, and just about every Lisp programmer has been bit
> by this when she was learning Lisp, and will never forget the lesson.
>
I thought I'd add that even this experienced lisp programmer was
bitten by the destructive operation of #'sort
spending many hours tracking down the bug it caused.
The problem was that AllegroStore copies a list every
time you access an objects slot, so doing a #'sort on the
list didn't have any effect on the persistent data.
But with my OODB, slot-access just returns a pointer to the list,
and thus sorting the list destructively modifies it in the DB.
The problem manifests itself by items disappearing from the list,
as referenced by the old head of the list, which is no longer
the head of the list after the sort.
And of course, the bug doesn't show up if the list was sorted
already, so the pointers don't get reshuffled.
I think #'sort should be renamed #'nsort ...
-Kelly Murray ···@intellimarket.com http://www.intellimarket.com
From: Christopher J. Vogt
Subject: Re: Sort is destructive (was Re: how to use nreverse?)
Date:
Message-ID: <36C1F606.553468CC@computer.org>
Kelly Murray wrote:
> I think #'sort should be renamed #'nsort ...
I couldn't agree more! In fact I'll go you one more, not only should the
existing sort functionality be renamed nsort, there ought to be a new sort
that is non-destructive. I believe that this change could be made without
impacting any existing code.
--
Christopher J. Vogt - http://members.home.com/vogt/
Johan Kullstam wrote:
> (defun fib-list (n)
> "make a list of fibonacci numbers"
> (let ((acc '(1 1)))
> (dotimes (i n)
> (let ((c (+ (car acc) (cadr acc))))
> (push c acc)))
> (nreverse acc)))
You're modifying that quoted thing that ACC gets bound to. That's
not allowed; it can cause chaos, as you've discovered. If you replace
line 3 with
(let ((acc (list 1 1)))
then all will be well.
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.
Johan Kullstam wrote:
> i was inspired by the fibonacci function which came up in one of the
> threads and decided to write my own.
>
> here is what i came up with as a first cut (yes, it makes a list of
> length n+2 but i'll fix that eventually...)
>
> (defun fib-list (n)
> "make a list of fibonacci numbers"
> (let ((acc '(1 1)))
> (dotimes (i n)
> (let ((c (+ (car acc) (cadr acc))))
> (push c acc)))
> (nreverse acc)))
>
> when i go to run this beast, i get
>
> > (fib-list 4)
> (1 1 2 3 5 8)
>
> and think so far so good. but then i run it again and get
>
> > (fib-list 4)
> (8 5 3 2 1 3 4 7 11)
>
> what is going on here?
The call to nreverse is destructively modifying not just your data but the
program itself.
Let me repeat that. The '(1 1) is a program constant. By nreversing a list
which has that constant as its tail, you are authorizing your lisp to
destructively modify the cons cells which make up that '(1 1). Next time
you look at those cells, they may legitimately point somewhere else.
So:
> (defun fib-list (n)
"make a list of fibonacci numbers"
(let ((acc '(1 1)))
(dotimes (i n)
(let ((c (+ (car acc) (cadr acc))))
(push c acc)))
(nreverse acc)))
FIB-LIST
> (pprint (function-lambda-expression 'FIB-LIST))
(LAMBDA (N)
(BLOCK FIB-LIST
(LET ((ACC '(1 1)))
(DOTIMES (I N)
(LET ((C (+ (CAR ACC) (CADR ACC)))) (PUSH C ACC)))
(NREVERSE ACC))))
> (FIB-LIST 4)
(1 1 2 3 5 8)
> (pprint (function-lambda-expression 'FIB-LIST))
(LAMBDA (N)
(BLOCK FIB-LIST
(LET ((ACC '(1 2 3 5 8)))
(DOTIMES (I N)
(LET ((C (+ (CAR ACC) (CADR ACC)))) (PUSH C ACC)))
(NREVERSE ACC))))
>
(Note: exact behaviour of function-lambda-expression can be
implementation-dependent.)
> [.....]
> have i totally misunderstood the meaning of let here? do i have some
> sort of closure situation i am not seeing?
No and no. Just be aware that your let binds acc to some list squirreled
away in memory. Change that list somehow, and you change what acc will
bind to next time you run that code.
> when i swap nreverse for reverse, this whole problem goes away. how
> does nreverse differ from reverse besides trashing its arg? how far
> does its swath of destruction extend?
Purely that nreverse may change the cons cells handed to it, and reverse
may not.
An alternative would be to copy the starting list, so that you are
destructively modifying a list which is not a program literal:
(defun fib-list (n)
"make a list of fibonacci numbers"
(let ((acc (copy-list '(1 1))))
(dotimes (i n)
(let ((c (+ (car acc) (cadr acc))))
(push c acc)))
(nreverse acc)))
> i am using clisp. is this some sort of a clisp bug? i shall try this
> at with ACL later tonight.
No, it looks like clisp did the right thing.
- nick