Hello all,
I'm pretty new to lisp, coming from a C++ background, and I can't figure
out how to not clobber the value of RESULT in HEAP-POP:
(Sorry for the formatting, it's hard to fit in USENET preferred columns)
(defstruct (heap (:constructor make-heap (&key (test #'<=)
(key #'identity)
(size 10) &aux (count 0) (elements (make-array
size :adjustable t :fill-pointer 0)))))
count elements test key size)
(defun heap-push (heap obj)
"Push a new OBJ onto a HEAP"
(declare (type heap heap))
(with-slots (key test elements count) heap
(if (< (fill-pointer elements) (array-dimension elements 0))
(vector-push nil elements)
(vector-push-extend nil elements))
(do* ((j (1+ count))
(i (floor (/ j 2)) (floor (/ j 2)))
(done nil))
(done t)
(if (or (eql i 0) (funcall test (funcall key (aref elements (1- i)))
(funcall key obj)))
(setf (aref elements (1- j)) obj count (1+ count) done t)
(setf (aref elements (1- j)) (aref elements (1- i)) j i)))))
(defun heap-top (heap)
"Get the topmost object from HEAP, without removing it"
(declare (type heap heap))
(if (> (heap-count heap) 0)
(aref (heap-elements heap) 0)
nil))
(defun heap-pop (heap)
"Remove the topmost object from HEAP, returning it"
(declare (type heap heap))
(with-slots (key test elements count) heap
(when (eql count 0)
(return-from heap-pop nil))
(decf count)
(setf (aref elements 0) (aref elements count))
(decf (fill-pointer elements))
(let ((key-object (aref elements count))
(i 1) (j 1) (done nil)
(result (heap-top heap)))
(loop while (null done) do
(setf i j j (* j 2))
(if (> j count)
(setf done t)
(progn
(when (and (/= j count)
(funcall test (funcall key (aref elements j))
(funcall key (aref elements (1- j)))))
(incf j))
(if (funcall test (funcall key key-object)
(funcall key (aref elements (1- j))))
(setf done t)
(setf (aref elements (1- i))
(aref elements (1- j)))))))
(setf (aref elements (1- i)) key-object)
result)))
SKIRMISH> h
#S(HEAP
:COUNT 0
:ELEMENTS #()
:TEST #<FUNCTION <=>
:KEY #<FUNCTION IDENTITY>
:SIZE 10)
SKIRMISH> (dotimes (i 1000) (heap-push h (random 1000)))
NIL
SKIRMISH> (heap-top h)
3
SKIRMISH> (heap-pop h)
464
What am I doing wrong to have RESULT be overwritten? I guess it's because
the LET only stores a reference to (aref elements 0), rather than the
value. How do I extract the value to keep it separate from the array
reference?
("use CELLS" is not a proper answer)
Thanks
Adam
On Sun, 18 May 2008 01:04:10 -0500, Paul Donnelly wrote:
[binary heap snipped]
>
> Isn't this more of a stack?
Not really, it's meant to be a binary heap (priority queue)
> And what's wrong with PUSHing and POPing a list?
If you don't mind O(N) performance for insertion, then a priority queue
can be made out of an alist fairly easily. And the code won't be so
nasty!
A
awhite <·······@iinet.net.au> writes:
> On Sun, 18 May 2008 01:04:10 -0500, Paul Donnelly wrote:
>
> [binary heap snipped]
>>
>> Isn't this more of a stack?
>
> Not really, it's meant to be a binary heap (priority queue)
>
>
>> And what's wrong with PUSHing and POPing a list?
>
> If you don't mind O(N) performance for insertion, then a priority queue
> can be made out of an alist fairly easily. And the code won't be so
> nasty!
Ah, I saw the array and assumed it was a stack of some sort.
Adam White wrote:
> Hello all,
>
> I'm pretty new to lisp, coming from a C++ background, and I can't
> figure out how to not clobber the value of RESULT in HEAP-POP:
Oh crap I'm an idiot.
Please disregard. I should have used cells.
A
Adam White wrote:
> Hello all,
>
> I'm pretty new to lisp, coming from a C++ background, and I can't figure
> out how to not clobber the value of RESULT in HEAP-POP:
>
> (Sorry for the formatting, it's hard to fit in USENET preferred columns)
>
> (defstruct (heap (:constructor make-heap (&key (test #'<=)
> (key #'identity)
> (size 10) &aux (count 0) (elements (make-array
> size :adjustable t :fill-pointer 0)))))
> count elements test key size)
>
> (defun heap-push (heap obj)
> "Push a new OBJ onto a HEAP"
> (declare (type heap heap))
> (with-slots (key test elements count) heap
> (if (< (fill-pointer elements) (array-dimension elements 0))
> (vector-push nil elements)
> (vector-push-extend nil elements))
> (do* ((j (1+ count))
> (i (floor (/ j 2)) (floor (/ j 2)))
> (done nil))
> (done t)
> (if (or (eql i 0) (funcall test (funcall key (aref elements (1- i)))
> (funcall key obj)))
> (setf (aref elements (1- j)) obj count (1+ count) done t)
> (setf (aref elements (1- j)) (aref elements (1- i)) j i)))))
>
> (defun heap-top (heap)
> "Get the topmost object from HEAP, without removing it"
> (declare (type heap heap))
> (if (> (heap-count heap) 0)
> (aref (heap-elements heap) 0)
> nil))
>
> (defun heap-pop (heap)
> "Remove the topmost object from HEAP, returning it"
> (declare (type heap heap))
> (with-slots (key test elements count) heap
> (when (eql count 0)
> (return-from heap-pop nil))
> (decf count)
> (setf (aref elements 0) (aref elements count))
> (decf (fill-pointer elements))
> (let ((key-object (aref elements count))
> (i 1) (j 1) (done nil)
> (result (heap-top heap)))
> (loop while (null done) do
> (setf i j j (* j 2))
> (if (> j count)
> (setf done t)
> (progn
> (when (and (/= j count)
> (funcall test (funcall key (aref elements j))
> (funcall key (aref elements (1- j)))))
> (incf j))
> (if (funcall test (funcall key key-object)
> (funcall key (aref elements (1- j))))
> (setf done t)
> (setf (aref elements (1- i))
> (aref elements (1- j)))))))
> (setf (aref elements (1- i)) key-object)
> result)))
>
>
> SKIRMISH> h
> #S(HEAP
> :COUNT 0
> :ELEMENTS #()
> :TEST #<FUNCTION <=>
> :KEY #<FUNCTION IDENTITY>
> :SIZE 10)
>
> SKIRMISH> (dotimes (i 1000) (heap-push h (random 1000)))
> NIL
>
> SKIRMISH> (heap-top h)
> 3
>
> SKIRMISH> (heap-pop h)
> 464
>
>
>
> What am I doing wrong to have RESULT be overwritten? I guess it's because
> the LET only stores a reference to (aref elements 0), rather than the
> value. How do I extract the value to keep it separate from the array
> reference?
>
> ("use CELLS" is not a proper answer)
Not to worry! That code is terrifying -- I am going to have nightmares
for a week.
What does it do? That j = 2 * j was pretty wild.
kt
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
ECLM rant:
http://video.google.com/videoplay?docid=-1331906677993764413&hl=en
ECLM talk:
http://video.google.com/videoplay?docid=-9173722505157942928&q=&hl=en
On Sun, 18 May 2008 15:12:32 -0400, Ken Tilton wrote:
> Adam White wrote:
>> Hello all,
>>
>> I'm pretty new to lisp, coming from a C++ background, and I can't
>> figure out how to not clobber the value of RESULT in HEAP-POP:
>>
>> (Sorry for the formatting, it's hard to fit in USENET preferred
>> columns)
>>
>> (defstruct (heap (:constructor make-heap (&key (test #'<=)
>> (key #'identity)
>> (size 10) &aux (count 0) (elements (make-array size
>> :adjustable t :fill-pointer 0))))) count elements test
>> key size)
>>
>> (defun heap-push (heap obj)
>> "Push a new OBJ onto a HEAP"
>> (declare (type heap heap))
>> (with-slots (key test elements count) heap
>> (if (< (fill-pointer elements) (array-dimension elements 0))
>> (vector-push nil elements)
>> (vector-push-extend nil elements))
>> (do* ((j (1+ count))
>> (i (floor (/ j 2)) (floor (/ j 2)))
>> (done nil))
>> (done t)
>> (if (or (eql i 0) (funcall test (funcall key (aref elements (1-
>> i)))
>> (funcall key obj)))
>> (setf (aref elements (1- j)) obj count (1+ count) done t) (setf
>> (aref elements (1- j)) (aref elements (1- i)) j i)))))
>>
>> (defun heap-top (heap)
>> "Get the topmost object from HEAP, without removing it" (declare
>> (type heap heap))
>> (if (> (heap-count heap) 0)
>> (aref (heap-elements heap) 0)
>> nil))
>>
>> (defun heap-pop (heap)
>> "Remove the topmost object from HEAP, returning it" (declare (type
>> heap heap))
On Sun, 18 May 2008 15:12:32 -0400, Ken Tilton wrote:
[snip heap implementation]
>> ("use CELLS" is not a proper answer)
>
> Not to worry! That code is terrifying -- I am going to have nightmares
> for a week.
>
> What does it do? That j = 2 * j was pretty wild.
Implements a binary heap on top of an adjustable vector.
Is it really that nasty? It's a straight-forward implementation of
Knuth's algorithm. I guess it would have been lispier to use recursion to
"sift up" the old value rather than a loop, but it works!
I left out the testing code because it wasn't relevant to my problem.
A
awhite wrote:
> On Sun, 18 May 2008 15:12:32 -0400, Ken Tilton wrote:
>
>
>>Adam White wrote:
>>
>>>Hello all,
>>>
>>>I'm pretty new to lisp, coming from a C++ background, and I can't
>>>figure out how to not clobber the value of RESULT in HEAP-POP:
>>>
>>>(Sorry for the formatting, it's hard to fit in USENET preferred
>>>columns)
>>>
>>>(defstruct (heap (:constructor make-heap (&key (test #'<=)
>>> (key #'identity)
>>> (size 10) &aux (count 0) (elements (make-array size
>>> :adjustable t :fill-pointer 0))))) count elements test
>>> key size)
>>>
>>>(defun heap-push (heap obj)
>>> "Push a new OBJ onto a HEAP"
>>> (declare (type heap heap))
>>> (with-slots (key test elements count) heap
>>> (if (< (fill-pointer elements) (array-dimension elements 0))
>>> (vector-push nil elements)
>>> (vector-push-extend nil elements))
>>> (do* ((j (1+ count))
>>> (i (floor (/ j 2)) (floor (/ j 2)))
>>> (done nil))
>>> (done t)
>>> (if (or (eql i 0) (funcall test (funcall key (aref elements (1-
>>> i)))
>>> (funcall key obj)))
>>> (setf (aref elements (1- j)) obj count (1+ count) done t) (setf
>>> (aref elements (1- j)) (aref elements (1- i)) j i)))))
>>>
>>>(defun heap-top (heap)
>>> "Get the topmost object from HEAP, without removing it" (declare
>>> (type heap heap))
>>> (if (> (heap-count heap) 0)
>>> (aref (heap-elements heap) 0)
>>> nil))
>>>
>>>(defun heap-pop (heap)
>>> "Remove the topmost object from HEAP, returning it" (declare (type
>>> heap heap))
>
> On Sun, 18 May 2008 15:12:32 -0400, Ken Tilton wrote:
>
> [snip heap implementation]
>
>
>>>("use CELLS" is not a proper answer)
>>
>>Not to worry! That code is terrifying -- I am going to have nightmares
>>for a week.
>>
>>What does it do? That j = 2 * j was pretty wild.
>
>
> Implements a binary heap on top of an adjustable vector.
Where is Scott Burson when we need him?:
http://common-lisp.net/project/fset/
Does that help?
>
> Is it really that nasty?
I saw more SETFs per LOC than I thought possible. But...
> It's a straight-forward implementation of
> Knuth's algorithm.
Oh, Knuth, the guy who saw thru the whole Lisp nonsense with "linked
lists are easy to implement" and then took ten years to create an
impenetrable typesetting DSL.
OK.
> ...I guess it would have been lispier to use recursion to
> "sift up" the old value rather than a loop,...
Nah, you did The Right Thing: transliterate and get on with your
Application. What's the application, btw?
> but it works!
Thx for the plug!:
http://smuglispweeny.blogspot.com/2008/03/tlop-worst-thing-you-can-say-about.html
kt
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
ECLM rant:
http://video.google.com/videoplay?docid=-1331906677993764413&hl=en
ECLM talk:
http://video.google.com/videoplay?docid=-9173722505157942928&q=&hl=en
On May 19, 10:09 am, Ken Tilton <···········@optonline.net> wrote:
> Oh, Knuth, the guy who (...) took ten years to create an
> impenetrable typesetting DSL
which still is the reference for the publication of scientific papers.
Evan
evan wrote:
> On May 19, 10:09 am, Ken Tilton <···········@optonline.net> wrote:
>
>>Oh, Knuth, the guy who (...) took ten years to create an
>>impenetrable typesetting DSL
>
>
> which still is the reference for the publication of scientific papers.
Yes, quite a success in that regard, tho I never heard anyone say it was
easy to use -- gonna have to take points off for that, world domination
or no. What is this deja vu feeling I am...oh, Java. But I should be the
last person to complain about an academic Actually Writing an
Application -- well, that's what separates the amateurs from the pros,
isn't it? The former can skimp on usability. Knuth did a helluva job on
functionality, tho, learned more about typesetting than he ever thought
he would, I wager. No skimping there, full marks for output quality.
Ended up writing a book on that alone... where was I? Right, binary heaps...
kt
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
ECLM rant:
http://video.google.com/videoplay?docid=-1331906677993764413&hl=en
ECLM talk:
http://video.google.com/videoplay?docid=-9173722505157942928&q=&hl=en
On May 19, 2:09 pm, Ken Tilton <···········@optonline.net> wrote:
> evan wrote:
> > On May 19, 10:09 am, Ken Tilton <···········@optonline.net> wrote:
>
> >>Oh, Knuth, the guy who (...) took ten years to create an
> >>impenetrable typesetting DSL
>
> > which still is the reference for the publication of scientific papers.
>
> Yes, quite a success in that regard, tho I never heard anyone say it was
> easy to use -- gonna have to take points off for that, world domination
> or no. What is this deja vu feeling I am...oh, Java. But I should be the
> last person to complain about an academic Actually Writing an
> Application -- well, that's what separates the amateurs from the pros,
> isn't it? The former can skimp on usability. Knuth did a helluva job on
> functionality, tho, learned more about typesetting than he ever thought
> he would, I wager. No skimping there, full marks for output quality.
> Ended up writing a book on that alone... where was I? Right, binary heaps...
I agree, it's not particularly pretty, and I'm looking forward to
improvements in this regard. It's not really a pain to use casually,
but it takes some nerve if you want to customize the layout or add
your own functionality.
Evan
evan wrote:
> On May 19, 2:09 pm, Ken Tilton <···········@optonline.net> wrote:
>
>>evan wrote:
>>
>>>On May 19, 10:09 am, Ken Tilton <···········@optonline.net> wrote:
>>
>>>>Oh, Knuth, the guy who (...) took ten years to create an
>>>>impenetrable typesetting DSL
>>
>>>which still is the reference for the publication of scientific papers.
>>
>>Yes, quite a success in that regard, tho I never heard anyone say it was
>>easy to use -- gonna have to take points off for that, world domination
>>or no. What is this deja vu feeling I am...oh, Java. But I should be the
>>last person to complain about an academic Actually Writing an
>>Application -- well, that's what separates the amateurs from the pros,
>>isn't it? The former can skimp on usability. Knuth did a helluva job on
>>functionality, tho, learned more about typesetting than he ever thought
>>he would, I wager. No skimping there, full marks for output quality.
>>Ended up writing a book on that alone... where was I? Right, binary heaps...
>
>
> I agree, it's not particularly pretty, and I'm looking forward to
> improvements in this regard. It's not really a pain to use casually,
> but it takes some nerve if you want to customize the layout or add
> your own functionality.
Let me know when it has a wysuwyg editor. :)
http://www.theoryyalgebra.com/demo-23.html
kenny
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
ECLM rant:
http://video.google.com/videoplay?docid=-1331906677993764413&hl=en
ECLM talk:
http://video.google.com/videoplay?docid=-9173722505157942928&q=&hl=en
On Mon, 19 May 2008 06:51:09 -0400, Ken Tilton wrote:
[on TeX]
>>
>> I agree, it's not particularly pretty, and I'm looking forward to
>> improvements in this regard. It's not really a pain to use casually,
>> but it takes some nerve if you want to customize the layout or add your
>> own functionality.
>
> Let me know when it has a wysuwyg editor. :)
It does.
http://www.lyx.org/Home
Adam
awhite wrote:
> On Mon, 19 May 2008 06:51:09 -0400, Ken Tilton wrote:
>
> [on TeX]
>
>
>>>I agree, it's not particularly pretty, and I'm looking forward to
>>>improvements in this regard. It's not really a pain to use casually,
>>>but it takes some nerve if you want to customize the layout or add your
>>>own functionality.
>>
>>Let me know when it has a wysuwyg editor. :)
>
>
> It does.
>
> http://www.lyx.org/Home
Cool, thx, downloading now. Looks like it is installing an entire
operating system and I just agreed to like my fourth unread license
agreement -- lord don't let me kick off another thread on the meaning of
the word "free".
But I kinda meant "let me know when Knuth does one", my theory being
that an academic can satisfy their keepers by doing something like TeX
while skimping on Actual Usability, at which academics down their noses
look.
kt
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
ECLM rant:
http://video.google.com/videoplay?docid=-1331906677993764413&hl=en
ECLM talk:
http://video.google.com/videoplay?docid=-9173722505157942928&q=&hl=en
Ken Tilton wrote:
>
>
> awhite wrote:
>
>> On Mon, 19 May 2008 06:51:09 -0400, Ken Tilton wrote:
>>
>> [on TeX]
>>
>>
>>>> I agree, it's not particularly pretty, and I'm looking forward to
>>>> improvements in this regard. It's not really a pain to use casually,
>>>> but it takes some nerve if you want to customize the layout or add your
>>>> own functionality.
>>>
>>>
>>> Let me know when it has a wysuwyg editor. :)
>>
>>
>>
>> It does.
>> http://www.lyx.org/Home
>
>
> Cool, thx, downloading now. Looks like it is installing an entire
> operating system and I just agreed to like my fourth unread license
> agreement -- lord don't let me kick off another thread on the meaning of
> the word "free".
PWUAHHAHAH.. I think it just installed Linux on my Windows box, good for
them!... it ran so long I forgot I was installing it! I also agreed to
five licenses and apparently subscribed to five years of Good
Housekeeping, lord knows I need it.
As for the editor: OK, it is wysiwyg, but... click on a fraction icon to
get a fraction? Well, I should shut up, maybe there is a keychord (not
sure what was wrong with just typing "/", tho.)
Thx again for the link.
kt
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
ECLM rant:
http://video.google.com/videoplay?docid=-1331906677993764413&hl=en
ECLM talk:
http://video.google.com/videoplay?docid=-9173722505157942928&q=&hl=en
evan wrote:
> On May 19, 10:09 am, Ken Tilton <···········@optonline.net> wrote:
>> Oh, Knuth, the guy who (...) took ten years to create an
>> impenetrable typesetting DSL
>
> which still is the reference for the publication of scientific papers.
Piffle! What is that compared to Cells?
Damien Kick wrote:
> evan wrote:
>
>> On May 19, 10:09 am, Ken Tilton <···········@optonline.net> wrote:
>>
>>> Oh, Knuth, the guy who (...) took ten years to create an
>>> impenetrable typesetting DSL
>>
>>
>> which still is the reference for the publication of scientific papers.
>
>
> Piffle! What is that compared to Cells?
That is a typesetting application compared to a programming paradigm.
Should be fun.
kenneth
Kenny wrote:
> Damien Kick wrote:
>> evan wrote:
>>> On May 19, 10:09 am, Ken Tilton <···········@optonline.net> wrote:
>>>> Oh, Knuth, the guy who (...) took ten years to create an
>>>> impenetrable typesetting DSL
>>> which still is the reference for the publication of scientific papers.
>> Piffle! What is that compared to Cells?
> That is a typesetting application compared to a programming paradigm.
> Should be fun.
Vern: You think Mighty Mouse could beat up Superman?
Teddy: What are you, cracked?
Vern: No, I saw him on TV the other day, he was holding five elephants
in one hand.
Teddy: Boy, you don't know nothing. Mighty Mouse is a cartoon.
Superman's a real guy. There's no way a cartoon could beat up a real guy.
Vern: I guess you're right. It'd be a good fight though.
On Sun, 18 May 2008 21:09:07 -0400, Ken Tilton wrote:
>> Implements a binary heap on top of an adjustable vector.
>
> http://common-lisp.net/project/fset/
> Does that help?
Interesting link. I won't do the obvious ("Why Wasn't I Told?")...
>> It's a straight-forward implementation of Knuth's algorithm.
>
> Oh, Knuth, the guy who saw thru the whole Lisp nonsense with "linked
> lists are easy to implement" and then took ten years to create an
> impenetrable typesetting DSL.
THE Programmer said that? Wow, and I thought the man could do no wrong!
>> ...I guess it would have been lispier to use recursion to "sift up" the
>> old value rather than a loop,...
>
> Nah, you did The Right Thing: transliterate and get on with your
> Application. What's the application, btw?
A rogue-like game. Another lispnik showed that cl is a good language for
the task.
A
awhite wrote:
> On Sun, 18 May 2008 21:09:07 -0400, Ken Tilton wrote:
>
>
>>>Implements a binary heap on top of an adjustable vector.
>>
>>http://common-lisp.net/project/fset/
>>Does that help?
>
>
> Interesting link. I won't do the obvious ("Why Wasn't I Told?")...
Scott must have his Spam-o-matic in for servicing, I'll try to pick up
the slack till he gets back on line.
>
>
>>>It's a straight-forward implementation of Knuth's algorithm.
>>
>>Oh, Knuth, the guy who saw thru the whole Lisp nonsense with "linked
>>lists are easy to implement" and then took ten years to create an
>>impenetrable typesetting DSL.
>
>
> THE Programmer said that? Wow, and I thought the man could do no wrong!
>
"Much of the material we will discuss is often called "List
processing," since a number of programming systems such as LISP have
been designed to facilitate working with general kinds of structures
called Lists.
...
Although List processing systems are useful in a large number of
situations, they impose constraints on the programmer that are often
unnecessary; it is usually better to use the methods of this chapter
directly in one's own programs, tailoring the data format and the
processing algorithms to the particular application. Many people
unfortunately still feel that List processing techniques are quite
complicated (so that it is necessary to use someone else's carefully
written interpretive system or a prefabricated set of subroutines), and
that List processing must be done only in a certain fixed way.
... "
-D.E.Knuth, TACP vol 1, Fundamental Algorithms
Chapter 2, Information Structures, 6th paragraph.
[Grace a Mr Summerhayes for digging that up back in March of 2003.]
Speaking of bad calls, I went searching on Knuth+Lisp came up with
Gabriel et al's Critique of Common Lisp based mostly on an anticipated
repeal of Moore's Law and saw a tempting citation:
"[Knuth 1965] Knuth, Donald E. Fourteen Hallmarks of a Good Programming
Language, Unpublished." Google offers no other mention from any of its
billyuns and billyuns of hard drives. :(
Love to see that. I bet he is describing Lisp.
>
>>>...I guess it would have been lispier to use recursion to "sift up" the
>>>old value rather than a loop,...
>>
>>Nah, you did The Right Thing: transliterate and get on with your
>>Application. What's the application, btw?
>
>
> A rogue-like game. Another lispnik showed that cl is a good language for
> the task.
Your SETFs are forgiven.
kenny
--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
ECLM rant:
http://video.google.com/videoplay?docid=-1331906677993764413&hl=en
ECLM talk:
http://video.google.com/videoplay?docid=-9173722505157942928&q=&hl=en
On May 17, 8:29 pm, Adam White <·······@iinet.net.au> wrote:
> (defstruct (heap (:constructor make-heap (&key (test #'<=)
> ...
> (defun heap-push (heap obj)
> ...
> (defun heap-top (heap)
> ...
> (defun heap-pop (heap)
> ...
That code's not compiling for me on sbcl.
(see below)
Why are you using with-slots? I've never heard
of it working with regular structs.
> the LET only stores a reference to (aref elements 0),
> rather than the value.
No, it stores a reference to the value.
> Oh crap I'm an idiot.
> Please disregard. I should have used cells.
?? Why/how so?
Just in case you're interested, I have a heap
library here:
http://www.prairienet.org/~dsb/mycode/cl/lib/array-heap.l
The code is somewhat old, so it may show some
of my early noobishness, which was even greater
than my current level of noobishness.
--Dan
------------------------------------------------
Dan Bensen http://www.prairienet.org/~dsb/
cl-match: expressive pattern matching in Lisp
http://common-lisp.net/project/cl-match/
; in: DEFUN HEAP-POP
; (SETF (AREF NEW-HEAP::ELEMENTS 0) (AREF NEW-HEAP::ELEMENTS
COUNT))
; --> SB-KERNEL:%ASET NEW-HEAP::ELEMENTS SLOT-VALUE
; --> SB-PCL::ACCESSOR-SLOT-VALUE LET TRULY-THE FUNCALL
; ==>
; (SB-C::%FUNCALL
; #'(SB-PCL::SLOT-ACCESSOR :GLOBAL NEW-HEAP::ELEMENTS SB-
PCL::READER) #:G126)
;
; caught STYLE-WARNING:
; undefined function: (SB-PCL::SLOT-ACCESSOR :GLOBAL ELEMENTS SB-
PCL::READER)
On Sun, 18 May 2008 20:02:20 -0700, danb wrote:
> That code's not compiling for me on sbcl. (see below)
Bugger. It worked on sbcl for me (I'm not at home, so can't remember the
version), as well as clisp and cmucl, so I assumed I wasn't doing
anything naughty.
> Why are you using with-slots? I've never heard of it working with
> regular structs.
WITH-SLOTS made the code more readable, a feature of macros I'm very much
enjoying.
Shouldn't WITH-SLOTS work for a struct? ISTR the PCL book briefly
mentioning that structs are also classes. Of course I could have made
HEAP be a class (and avoid the funky defstruct syntax using a custom
constructor) but I was (foolishly?) thinking of performance.
> On Sun, 18 May 2008 20:02:20 -0700, danb wrote:
> > That code's not compiling for me on sbcl.
Okay, it's compiling. I have no idea why, unless there's
a pre-existing package called :heap that I shouldn't have
dumped on.
(defun heap-pop (heap)
...
(setf (aref elements 0) (aref elements count))
...
(let ... (result (heap-top heap)))
> What am I doing wrong to have RESULT be overwritten?
It didn't get overwritten, you just swapped it out
before saving it.
--Dan
------------------------------------------------
Dan Bensen http://www.prairienet.org/~dsb/
cl-match: expressive pattern matching in Lisp
http://common-lisp.net/project/cl-match/
On Sun, 18 May 2008 23:43:32 -0700, danb wrote:
>> What am I doing wrong to have RESULT be overwritten?
>
> It didn't get overwritten, you just swapped it out before saving it.
Cheers - THAT's why I said that I'm an idiot (upthread).
I should have talked to the debugging teddy bear first.
A
From: Stanisław Halik
Subject: Re: Does WITH-SLOTS work with structs (was Re: LET value being clobbered)
Date:
Message-ID: <g0qvv0$mqr$1@news2.task.gda.pl>
thus spoke awhite <·······@iinet.net.au>:
>> Why are you using with-slots? I've never heard of it working with
>> regular structs.
> WITH-SLOTS made the code more readable, a feature of macros I'm very much
> enjoying.
Go for inlined accessors, they're O(1) unlike SLOT-VALUE at every call.
> Shouldn't WITH-SLOTS work for a struct? ISTR the PCL book briefly
> mentioning that structs are also classes.
Effectively works for introspection on structures here on sbcl:
> (defstruct foo bar baz)
> (sb-mop:class-slots (class-of (make-foo)))
(#<SB-PCL::STRUCTURE-EFFECTIVE-SLOT-DEFINITION BAR>
#<SB-PCL::STRUCTURE-EFFECTIVE-SLOT-DEFINITION BAZ>)
But SLOT-VALUE is O(log n) at best and you lose O(1) accessors - the
relative advantage of structures over classes with all the fancy MOP and
inheritance.
> Of course I could have made HEAP be a class (and avoid the funky
> defstruct syntax using a custom constructor) but I was (foolishly?)
> thinking of performance.
For a DWIM constructor, see `defclass-star'.
--
The great peril of our existence lies in the fact that our diet consists
entirely of souls. -- Inuit saying
P� Mon, 19 May 2008 05:02:20 +0200, skrev danb <·········@gmail.com>:
> On May 17, 8:29 pm, Adam White <·······@iinet.net.au> wrote:
>> (defstruct (heap (:constructor make-heap (&key (test #'<=)
>> ...
>> (defun heap-push (heap obj)
>> ...
>> (defun heap-top (heap)
>> ...
>> (defun heap-pop (heap)
>> ...
>
> That code's not compiling for me on sbcl.
> (see below)
> Why are you using with-slots? I've never heard
> of it working with regular structs.
>
There are 3 types of classes in CLOS. built-in-class (like integer),
structure-class (defstruct) and standard-class. structure-class has single
inheritance and does not allow redefinition. It does allow you to define
methods on it however. Thus with-slots and with-accessors should work.
(provided structure type isn't list)
Structures access is usually only inlined when bounds checking is turned
off at low levels of safely. On my compiler (LispWorks) at safety < 1.
with-accessors should allow inlining of structure access to happen. (Under
the hood it is just a makro-let that substitutes the name for the
accessor.)
Of cource when you use with-slots as here you might as well have defined
it as a defclass.
That said with-slots defeats the accessor abstraction by exposing internal
details and should only be used to define accessors. For other things use
with-accessors.
Example:
(defstruct my-struct one two three)
(defparameter *struct* (make-my-struct :one 1 :two 2 :three 3))
(defun test()
(with-slots (one two three) *struct*
(format t "~&one: ~d two: ~d three: ~d~%"
one two three))
(with-accessors ((one my-struct-one) (two my-struct-two) (three
my-struct-three))
*struct*
(format t "~&one: ~d two: ~d three: ~d~%"
one two three)))
CL-USER 1 > (test)
one: 1 two: 2 three: 3
one: 1 two: 2 three: 3
NIL
--------------
John Thingstad
P� Mon, 19 May 2008 05:02:20 +0200, skrev danb <·········@gmail.com>:
> On May 17, 8:29 pm, Adam White <·······@iinet.net.au> wrote:
>> (defstruct (heap (:constructor make-heap (&key (test #'<=)
>> ...
>> (defun heap-push (heap obj)
>> ...
>> (defun heap-top (heap)
>> ...
>> (defun heap-pop (heap)
>> ...
>
> That code's not compiling for me on sbcl.
> (see below)
> Why are you using with-slots? I've never heard
> of it working with regular structs.
I could also add that CLOS caches slot accessors. So it does a lot better
than O(log2 n).
O(1) can safely be assumed in most cases.
--------------
John Thingstad
Adam White <·······@iinet.net.au> wrote:
> I'm pretty new to lisp, coming from a C++ background, and I can't figure
> out how to not clobber the value of RESULT in HEAP-POP:
I hope you don't mind some general comments on style. Overall, it's not
bad; I think it just shows a lack of familiarity with some of the less
obvious parts of the language, which you'll pick up as you go.
> (Sorry for the formatting, it's hard to fit in USENET preferred
> columns)
Hmm.
> (defstruct (heap (:constructor make-heap (&key (test #'<=)
> (key #'identity)
> (size 10) &aux (count 0) (elements (make-array
> size :adjustable t :fill-pointer 0)))))
> count elements test key size)
Gnaah!
(defstruct (heap
(:constructor
make-heap
(&key (test #'<=)
(key #'identity)
(size 10)
&aux (count 0)
(elements (make-array size
:adjustable t
:fill-pointer 0)))))
count
elements
test
key
size)
A little more readable, n'est-ce pas?
Is there some reason you want the SIZE slot there? You don't use it for
anything. (You're allowed constructor arguments which don't have slots
associated with them.)
I think TEST is a poor name for the comparison predicate. Usually a
TEST function takes a single argument and answers whether it ought to be
processed. I'd suggest something like PRECEDES-P if you want to be
verbose; but this is Lisp, and it's fine to have variables (or structure
slots) called <.
What's the difference between your COUNT slot and the fill-pointer of
ELEMENTS? To be honest, I'd recommend dropping both the fill-pointer
and adjustableness of your ELEMENTS vector, leaving it a simple-vector
and giving you the right to call SVREF. The COUNT works perfectly fine
for tracking the size of the heap, and you can still call ADJUST-ARRAY
to resize as long as you store the return value. Doing this isn't
particularly onerous -- I think it's an extra couple of lines in
HEAP-PUSH.
> (defun heap-push (heap obj)
> "Push a new OBJ onto a HEAP"
> (declare (type heap heap))
> (with-slots (key test elements count) heap
> (if (< (fill-pointer elements) (array-dimension elements 0))
> (vector-push nil elements)
> (vector-push-extend nil elements))
> (do* ((j (1+ count))
> (i (floor (/ j 2)) (floor (/ j 2)))
> (done nil))
> (done t)
> (if (or (eql i 0) (funcall test (funcall key (aref elements (1- i)))
> (funcall key obj)))
> (setf (aref elements (1- j)) obj count (1+ count) done t)
> (setf (aref elements (1- j)) (aref elements (1- i)) j i)))))
Flush DONE and just say RETURN when you mean RETURN.
You're calling KEY on your OBJ many times. Is it likely to change? I'd
have thought you'd be better off calling it once and caching the answer.
When I was writing a heap, I found it useful to say
(declaim (inline parent left-child right-child))
(deftype index () '(and unsigned-byte fixnum))
(defun parent (i)
(declare (type index i))
(the index (floor (- i 1) 2)))
(defun left-child (i)
(declare (type index i))
(the index (+ (* 2 i) 1)))
(defun right-child (i)
(declare (type index i))
(the index (+ (* 2 i) 2)))
which retains the performance of writing the heap navigation longhand
(that's what the INLINE is for) but looks prettier, at least to me.
Also note that (floor j 2) means the same as (floor (/ j 2)) but avoids
computing with rational numbers.
> (defun heap-top (heap)
> "Get the topmost object from HEAP, without removing it"
> (declare (type heap heap))
> (if (> (heap-count heap) 0)
> (aref (heap-elements heap) 0)
> nil))
You can spell (> mumble 0) as (PLUSP mumble). If I wanted the above
effect, I'd write it as just
(defun heap-top (heap)
"Get the topmost object from HEAP, without removing it"
(declare (type heap heap))
(and (plusp (heap-count heap))
(aref (heap-elements heap) 0)))
though as a matter of style, I'd prefer a separate HEAP-EMPTY-P
function, and have HEAP-TOP and friends signal an error on an empty
heap. If you don't want to do that, then at least provide a way to
distinguish an empty heap from a non-empty one with NIL at the top;
e.g.,
(defun heap-top (heap)
"Get the topmost object from HEAP, without removing it"
(declare (type heap heap))
(and (plusp (heap-count heap))
(values (aref (heap-elements heap) 0) t)))
Now I can say
(multiple-value-bind (top anyp) (heap-top heap)
(when anyp ...))
and know that I really did find something.
> (defun heap-pop (heap)
> "Remove the topmost object from HEAP, returning it"
> (declare (type heap heap))
> (with-slots (key test elements count) heap
> (when (eql count 0)
> (return-from heap-pop nil))
> (decf count)
> (setf (aref elements 0) (aref elements count))
> (decf (fill-pointer elements))
> (let ((key-object (aref elements count))
> (i 1) (j 1) (done nil)
> (result (heap-top heap)))
> (loop while (null done) do
> (setf i j j (* j 2))
> (if (> j count)
> (setf done t)
> (progn
> (when (and (/= j count)
> (funcall test (funcall key (aref elements j))
> (funcall key (aref elements (1- j)))))
> (incf j))
> (if (funcall test (funcall key key-object)
> (funcall key (aref elements (1- j))))
> (setf done t)
> (setf (aref elements (1- i))
> (aref elements (1- j)))))))
> (setf (aref elements (1- i)) key-object)
> result)))
Don't use NULL when you mean NOT. You really do mean NOT up there. Or,
actually, you mean (loop until done do ...). So say that instead.
This is really suffering from unpleasant flow control. Common Lisp has
some really good and powerful flow-control operators: it's a shame not
to use them. In particular:
* Use MULTIPLE-VALUE-PROG1 (to return the additional actually-did-
something value) rather than messing about with RESULT.
* (if (> j count) (setf done t) (progn #| rest of the loop |#))
is really nasty. Replace it with (when (> j count) (return)); then
you can prevent the loop body marching over to the right of the
screen. Kill DONE; the LOOP can then become a simple one.
* Alternatively, stay with complex LOOP, and really use it.
(loop with key-object = (setf (aref elements 0)
(aref elements count))
for i = 1 then j
and j = 1 then (* j 2)
while (< j count)
when (and (/= j count)
(funcall test (funcall key (aref elements j))
(funcall key (aref elements (1- j)))))
do (incf j)
until (funcall test (funcall key key-object)
(funcall key (aref elements (1- j))))
do (setf (aref elements (1- i)) (aref elements (1- j))))
Your indentation of the WHEN clause is confusing: it suggests that TEST
has one argument, and the AND macro has three branches to test. This is
wrong: TEST has two arguments; AND has two branches. I've reindented to
show this, and to bring out the symmetry more clearly.
(Again, the repeated calls to KEY are wasteful. Some basic caching will
eliminate them, and also many of the AREFs.)
You have a tendency to have big SETF calls with lots of arguments strung
together. It's hard to pick out the argument pairing visually. I'd
suggest:
* Spread the call over a few lines, e.g.,
(setf i j
j (* j 2))
* Add more horizontal space between pairs, e.g.,
(setf i j j (* j 2))
* In this case, the repetition of J suggests that you just use SHIFTF!
(shiftf i j (* j 2))
> What am I doing wrong to have RESULT be overwritten? I guess it's because
> the LET only stores a reference to (aref elements 0), rather than the
> value. How do I extract the value to keep it separate from the array
> reference?
You clobber (aref elements 0) before grabbing RESULT. My proposed
restyling (using complex LOOP and MULTIPLE-VALUE-PROG1) will fix this.
-- [mdw]
On Mon, 19 May 2008 23:26:12 +0000, Mark Wooding wrote:
> I hope you don't mind some general comments on style. Overall, it's not
> bad; I think it just shows a lack of familiarity with some of the less
> obvious parts of the language, which you'll pick up as you go.
Thanks Mark, I really appreciate it.
>> (Sorry for the formatting, it's hard to fit in USENET preferred
>> columns)
>
> Hmm.
Yah, I copy-pasted, but my editor mangled the code horribly. I re-indented
it, and it didn't work well
> Is there some reason you want the SIZE slot there? You don't use it for
> anything. (You're allowed constructor arguments which don't have slots
> associated with them.)
Good point.
> I think TEST is a poor name for the comparison predicate. Usually a
> TEST function takes a single argument and answers whether it ought to be
> processed. I'd suggest something like PRECEDES-P if you want to be
> verbose; but this is Lisp, and it's fine to have variables (or structure
> slots) called <.
Yes. I was thinking of symmetry with MEMBER and others, but '<=' is a
better name.
> The COUNT works perfectly fine
> for tracking the size of the heap, and you can still call ADJUST-ARRAY
> to resize as long as you store the return value. Doing this isn't
> particularly onerous -- I think it's an extra couple of lines in
> HEAP-PUSH.
ADJUST-ARRAY scares me. I looked it up in the hs at the time and thought
that it looked Way Too Hard For Now.
> Flush DONE and just say RETURN when you mean RETURN.
Good point. I was literally transliterating Knuth's algorithm.
>
> You're calling KEY on your OBJ many times. Is it likely to change? I'd
> have thought you'd be better off calling it once and caching the answer.
Doh! ::whacks forehead::
> When I was writing a heap, I found it useful to say
>
> (declaim (inline parent left-child right-child)) (deftype index () '(and
> unsigned-byte fixnum)) (defun parent (i)
> (declare (type index i))
> (the index (floor (- i 1) 2)))
> (defun left-child (i)
> (declare (type index i))
> (the index (+ (* 2 i) 1)))
> (defun right-child (i)
> (declare (type index i))
> (the index (+ (* 2 i) 2)))
>
> which retains the performance of writing the heap navigation longhand
> (that's what the INLINE is for) but looks prettier, at least to me.
Initially I did that, but since I only called them once, it seemed
pointless.
> Also note that (floor j 2) means the same as (floor (/ j 2)) but avoids
> computing with rational numbers.
Wow. That I did not know.
>> (defun heap-top (heap)
>> "Get the topmost object from HEAP, without removing it" (declare
>> (type heap heap))
>> (if (> (heap-count heap) 0)
>> (aref (heap-elements heap) 0)
>> nil))
>
> You can spell (> mumble 0) as (PLUSP mumble). If I wanted the above
> effect, I'd write it as just
>
> (defun heap-top (heap)
> "Get the topmost object from HEAP, without removing it" (declare (type
> heap heap))
> (and (plusp (heap-count heap))
> (aref (heap-elements heap) 0)))
>
> though as a matter of style, I'd prefer a separate HEAP-EMPTY-P
> function, and have HEAP-TOP and friends signal an error on an empty
> heap. If you don't want to do that, then at least provide a way to
> distinguish an empty heap from a non-empty one with NIL at the top;
> e.g.,
>
> (defun heap-top (heap)
> "Get the topmost object from HEAP, without removing it" (declare (type
> heap heap))
> (and (plusp (heap-count heap))
> (values (aref (heap-elements heap) 0) t)))
>
> Now I can say
>
> (multiple-value-bind (top anyp) (heap-top heap)
> (when anyp ...))
>
> and know that I really did find something.
Good idea - coming from C++ I keep forgetting about multiple values!
> * Alternatively, stay with complex LOOP, and really use it.
>
> (loop with key-object = (setf (aref elements 0)
> (aref elements count))
> for i = 1 then j
> and j = 1 then (* j 2)
> while (< j count)
> when (and (/= j count)
> (funcall test (funcall key (aref elements j))
> (funcall key (aref elements (1- j)))))
> do (incf j)
> until (funcall test (funcall key key-object)
> (funcall key (aref elements (1- j))))
> do (setf (aref elements (1- i)) (aref elements (1- j))))
whoah. I like.
> Your indentation of the WHEN clause is confusing: it suggests that TEST
> has one argument, and the AND macro has three branches to test. This is
> wrong: TEST has two arguments; AND has two branches. I've reindented to
> show this, and to bring out the symmetry more clearly.
Nasty indentation was an artificial artifact of fitting in 71 columns.
[stupid thinko snipped]
> You clobber (aref elements 0) before grabbing RESULT. My proposed
> restyling (using complex LOOP and MULTIPLE-VALUE-PROG1) will fix this.
Yeah, I realised the error about 2.5 seconds after posting!
Thanks Mark, I appreciate your comments.
A