I am not sure if the term "closed loop" is correct, but here is the
essence:
As my calculation proceeds through its iteration, I would like to
collect the results (a result being a vector, for example) in a stack,
but so that once the stack is full, I overwrite the first stored
element, than the second, and so on, until I stop the calculation.
(well, it actually crashes, so I would like to capture the events
prior to the crash).
I am pretty sure I can come up with a list and a pointer and use mod
and nth. But there has to be a better way. Like setting the last cdr
to point to the first car. But I would prefer to see someone else do
that before embarking on debugging infinite loops in my code.
So yes, I am looking to steal someones code. But from where?
Thank you,
Mirko
·············@gmail.com writes:
> I am not sure if the term "closed loop" is correct, but here is the
> essence:
>
> As my calculation proceeds through its iteration, I would like to
> collect the results (a result being a vector, for example) in a stack,
> but so that once the stack is full, I overwrite the first stored
> element, than the second, and so on, until I stop the calculation.
> (well, it actually crashes, so I would like to capture the events
> prior to the crash).
You could take a look at my response to another thread from June 9th,
cited here from Google Groups: <http://tinyurl.com/4wg25h>
--
Thomas A. Russ, USC/Information Sciences Institute
> As my calculation proceeds through its iteration, I would like to
> collect the results (a result being a vector, for example) in a stack,
> but so that once the stack is full, I overwrite the first stored
> element, than the second, and so on, until I stop the calculation.
> (well, it actually crashes, so I would like to capture the events
> prior to the crash).
If you are just doing this for debugging purposes you might want to
look at using the lisp function TRACE to monitor your calls directly.
This might be all you need, depending on what your actual problem is.
> I am pretty sure I can come up with a list and a pointer and use mod
> and nth. But there has to be a better way. Like setting the last cdr
> to point to the first car. But I would prefer to see someone else do
> that before embarking on debugging infinite loops in my code.
The data structure you are referring to is typically called a "Ring
Queue" or a "Ring Buffer". (Googling that with "lisp" should find you
some good examples.) And you can also trivially create a circular
list in lisp by doing as you say and setting the last cdr back to the
head of a list. Just make sure you look at setting/letting *PRINT-
CIRCLE* to T before you think about printing it out. What you are
talking about here is data -- creating circular structures in data
isn't a problem and also frequently needed, and not an "infinite
loop". An "infinite loop" is when your computer is stuck doing the
same things over and over again incorrectly**. (For example,
typically trying to print a circular list without *print-circle* set.)
Kevin
** some times this is the correct/desired behavior. (I'm reminded of
a Simpsons where Homer rigged a drinking bird to keep pecking a key on
his keyboard.)
On Jun 23, 5:15 pm, K Livingston <······················@gmail.com>
wrote:
> > As my calculation proceeds through its iteration, I would like to
> > collect the results (a result being a vector, for example) in a stack,
> > but so that once the stack is full, I overwrite the first stored
> > element, than the second, and so on, until I stop the calculation.
> > (well, it actually crashes, so I would like to capture the events
> > prior to the crash).
>
> If you are just doing this for debugging purposes you might want to
> look at using the lisp function TRACE to monitor your calls directly.
> This might be all you need, depending on what your actual problem is.
>
> > I am pretty sure I can come up with a list and a pointer and use mod
> > and nth. But there has to be a better way. Like setting the last cdr
> > to point to the first car. But I would prefer to see someone else do
> > that before embarking on debugging infinite loops in my code.
>
> The data structure you are referring to is typically called a "Ring
> Queue" or a "Ring Buffer". (Googling that with "lisp" should find you
> some good examples.) And you can also trivially create a circular
> list in lisp by doing as you say and setting the last cdr back to the
> head of a list. Just make sure you look at setting/letting *PRINT-
> CIRCLE* to T before you think about printing it out. What you are
> talking about here is data -- creating circular structures in data
> isn't a problem and also frequently needed, and not an "infinite
> loop". An "infinite loop" is when your computer is stuck doing the
> same things over and over again incorrectly**. (For example,
> typically trying to print a circular list without *print-circle* set.)
>
> Kevin
>
> ** some times this is the correct/desired behavior. (I'm reminded of
> a Simpsons where Homer rigged a drinking bird to keep pecking a key on
> his keyboard.)
Thanks to all the posters for the pointers and correcting my
terminology.
But Kevin, I now myself: with hardware, it is either a short, or a
vacuum leak, or some arcing. With computers, ... , infinite loops,
divisions by zero, ... :-)
On Jun 23, 8:52 pm, ·············@gmail.com wrote:
> I am not sure if the term "closed loop" is correct, but here is the
> essence:
>
> As my calculation proceeds through its iteration, I would like to
> collect the results (a result being a vector, for example) in a stack,
> but so that once the stack is full, I overwrite the first stored
> element, than the second, and so on, until I stop the calculation.
> (well, it actually crashes, so I would like to capture the events
> prior to the crash).
>
> I am pretty sure I can come up with a list and a pointer and use mod
> and nth. But there has to be a better way. Like setting the last cdr
> to point to the first car. But I would prefer to see someone else do
> that before embarking on debugging infinite loops in my code.
>
> So yes, I am looking to steal someones code. But from where?
>
> Thank you,
>
> Mirko
Gene wrote a ladder.
can be found by searching on 'demented deque' in this NG.
In article
<····································@z66g2000hsc.googlegroups.com>,
·············@gmail.com wrote:
> I am not sure if the term "closed loop" is correct, but here is the
> essence:
The usual terms are "circular buffer" and "ring buffer". Google for
them and you'll find some good descriptions, although I didn't find any
CL source code right away.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
From: Steve Allan
Subject: Re: looking for a data structure: closed loop
Date:
Message-ID: <uy743hs5z.fsf@attachmate.com>
Barry Margolin <······@alum.mit.edu> writes:
> In article
> <····································@z66g2000hsc.googlegroups.com>,
> ·············@gmail.com wrote:
>
>> I am not sure if the term "closed loop" is correct, but here is the
>> essence:
>
> The usual terms are "circular buffer" and "ring buffer". Google for
> them and you'll find some good descriptions, although I didn't find any
> CL source code right away.
PaulG implements a ring buffer in his book 'Ansi Common Lisp'. I
think it's in the character matching example.
--
-- Steve
·············@gmail.com writes:
> I am not sure if the term "closed loop" is correct, but here is the
> essence:
>
> As my calculation proceeds through its iteration, I would like to
> collect the results (a result being a vector, for example) in a stack,
> but so that once the stack is full, I overwrite the first stored
> element, than the second, and so on, until I stop the calculation.
> (well, it actually crashes, so I would like to capture the events
> prior to the crash).
>
> I am pretty sure I can come up with a list and a pointer and use mod
> and nth. But there has to be a better way. Like setting the last cdr
> to point to the first car. But I would prefer to see someone else do
> that before embarking on debugging infinite loops in my code.
>
> So yes, I am looking to steal someones code. But from where?
This is called a circular buffer.
If the size of your buffer is fixed, you can use a vector.
Usually, we have two indices, one to the head another to the queue.
But since there is no order in ℤ/n we cannot distinguish an empty
buffer from a full buffer on the two indices alone.
But for your application, in stationary regime, the buffer will be
full. So we can fill the buffer with initial values, and keep only
the index of the last entry.
(defmacro incf-mod (&environment env place modulo)
"INCF modulo MODULO"
(multiple-value-bind (vars vals store-vars writer-form reader-form)
(get-setf-expansion place env)
(when (cdr store-vars) (error "Can't expand this."))
`(let* (,@(mapcar (function list) vars vals))
(let ((,(car store-vars) (mod (+ ,reader-form 1) ,modulo)))
,writer-form))))
(defstruct (circular-buffer (:constructor %make-circular-buffer))
data
(tail 0))
(defun make-circular-buffer (size &key (initial-element nil))
(%make-circular-buffer
:data (make-array size :initial-element initial-element)))
(defun enter (buffer item)
(setf (aref (circular-buffer-data buffer)
(incf-mod (circular-buffer-tail buffer)
(length (circular-buffer-data buffer)))) item))
(defun get-contents (buffer)
(let ((result (make-array (length (circular-buffer-data buffer)))))
(replace result (circular-buffer-data buffer)
:start1 0 :start2 (1+ (circular-buffer-tail buffer)))
(replace result (circular-buffer-data buffer)
:start1 (- (length (circular-buffer-data buffer))
(1+ (circular-buffer-tail buffer)))
:start2 0)
result))
(let ((b (make-circular-buffer 3 :initial-element nil)))
(enter b 1) (enter b 2) (print (get-contents b))
(enter b 3) (enter b 4) (enter b 5) (get-contents b))
prints:
#(NIL 1 2)
--> #(3 4 5)
In the case of a circular list, the code is simplier:
(defun make-circular (list)
(setf (cdr (last list)) list))
(defun make-circular-list (size &key initial-element)
(make-circular (make-list size :initial-element initial-element)))
(defun circular-length (list)
"LIST must be either a proper-list or a circular-list, not a dotted-list.
RETURN: the total length ; the length of the stem ; the length of the circle.
"
(let ((indexes (make-hash-table)))
(loop
:for i :from 0
:for current :on list
:do (let ((index (gethash current indexes)))
(if index
;; found loop
(return (values i index (- i index)))
(setf (gethash current indexes) i)))
:finally (return (values i)))))
(defstruct (circular-buffer (:constructor %make-circular-buffer))
data)
(defun make-circular-buffer (size &key (initial-element nil))
(%make-circular-buffer
:data (make-circular-list size :initial-element initial-element)))
(defun enter (buffer item)
(setf (circular-buffer-data buffer) (cdr (circular-buffer-data buffer))
(car (circular-buffer-data buffer)) item))
(defun get-contents (buffer)
(let ((result (make-array (circular-length (circular-buffer-data buffer)))))
(map-into result (function identity) (cdr (circular-buffer-data buffer)))
result))
(let ((b (make-circular-buffer 3 :initial-element nil)))
(enter b 1) (enter b 2) (print (get-contents b))
(enter b 3) (enter b 4) (enter b 5) (get-contents b))
prints:
#(NIL 1 2)
--> #(3 4 5)
--
__Pascal Bourguignon__ http://www.informatimago.com/
READ THIS BEFORE OPENING PACKAGE: According to certain suggested
versions of the Grand Unified Theory, the primary particles
constituting this product may decay to nothingness within the next
four hundred million years.
On Tue, 24 Jun 2008 00:46:07 +0200, Pascal J. Bourguignon wrote:
> Usually, we have two indices, one to the head another to the queue. But
> since there is no order in ℤ/n we cannot distinguish an empty buffer
> from a full buffer on the two indices alone.
care to elaborate on this ?
alien_guy <·@l.org> writes:
> On Tue, 24 Jun 2008 00:46:07 +0200, Pascal J. Bourguignon wrote:
>
>> Usually, we have two indices, one to the head another to the queue. But
>> since there is no order in ℤ/n we cannot distinguish an empty buffer
>> from a full buffer on the two indices alone.
>
> care to elaborate on this ?
Assume the index head points to the first item in the buffer, and the
index tail points to the first free slot.
We start with an empty buffer: head=tail
[ ]
^
| head
|
tail
We add some items:
[ xxxxxxxxxxxxx ]
^ ^
| head | tail
We add some more. While the buffer is not full and not empty,
head /= tail:
[xxxxx xxxxxxxxxxxxxxxxxxxxx]
^^
|| head
|
tail
But when you fill the buffer, we get again head=tail
[xxxxxxxxxxxxxxxxxxxxxxxxxxx]
^
| head
|
tail
Unfortunately, it's the same state as when the buffer is empty.
So we need to add a bit somewhere to distinguish an empty circular
buffer from a full circular buffer.
We could for example add one slot to the buffer (thus never filling it
completely). Or we could add a flag to the structure. Another
possibility would be to use an index for the head, and the number of
items in the buffer.
(defstruct (circular-buffer (:constructor %make-circular-buffer))
data
(head 0)
(number 0))
(defun make-circular-buffer (size &key (initial-element nil))
(%make-circular-buffer
:data (make-array size :initial-element initial-element)))
(defun circular-buffer-put (buffer item)
(if (< (circular-buffer-number buffer)
(length (circular-buffer-data buffer)))
(progn
(setf (aref (circular-buffer-data buffer)
(mod (+ (circular-buffer-head buffer)
(circular-buffer-number buffer))
(length (circular-buffer-data buffer))))
item)
(incf (circular-buffer-number buffer))
item)
(error "Circular buffer is full")))
(defun circular-buffer-get (buffer)
(if (zerop (circular-buffer-number buffer))
(error "Circular buffer is empty")
(prog1
(aref (circular-buffer-data buffer) (circular-buffer-head buffer))
(incf-mod (circular-buffer-head buffer)
(length (circular-buffer-data buffer)))
(decf (circular-buffer-number buffer)))))
--
__Pascal Bourguignon__ http://www.informatimago.com/
NEW GRAND UNIFIED THEORY DISCLAIMER: The manufacturer may
technically be entitled to claim that this product is
ten-dimensional. However, the consumer is reminded that this
confers no legal rights above and beyond those applicable to
three-dimensional objects, since the seven new dimensions are
"rolled up" into such a small "area" that they cannot be
detected.
On Jun 23, 8:40 pm, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> alien_guy <····@l.org> writes:
> > On Tue, 24 Jun 2008 00:46:07 +0200, Pascal J. Bourguignon wrote:
>
> >> Usually, we have two indices, one to the head another to the queue. But
> >> since there is no order in ℤ/n we cannot distinguish an empty buffer
> >> from a full buffer on the two indices alone.
>
> > care to elaborate on this ?
>
> Assume the index head points to the first item in the buffer, and the
> index tail points to the first free slot.
>
> We start with an empty buffer: head=tail
>
> [ ]
> ^
> | head
> |
> tail
>
> We add some items:
>
> [ xxxxxxxxxxxxx ]
> ^ ^
> | head | tail
>
> We add some more. While the buffer is not full and not empty,
> head /= tail:
>
> [xxxxx xxxxxxxxxxxxxxxxxxxxx]
> ^^
> || head
> |
> tail
>
> But when you fill the buffer, we get again head=tail
>
> [xxxxxxxxxxxxxxxxxxxxxxxxxxx]
> ^
> | head
> |
> tail
>
> Unfortunately, it's the same state as when the buffer is empty.
>
> So we need to add a bit somewhere to distinguish an empty circular
> buffer from a full circular buffer.
>
> We could for example add one slot to the buffer (thus never filling it
> completely). Or we could add a flag to the structure. Another
> possibility would be to use an index for the head, and the number of
> items in the buffer.
>
> (defstruct (circular-buffer (:constructor %make-circular-buffer))
> data
> (head 0)
> (number 0))
>
> (defun make-circular-buffer (size &key (initial-element nil))
> (%make-circular-buffer
> :data (make-array size :initial-element initial-element)))
>
> (defun circular-buffer-put (buffer item)
> (if (< (circular-buffer-number buffer)
> (length (circular-buffer-data buffer)))
> (progn
> (setf (aref (circular-buffer-data buffer)
> (mod (+ (circular-buffer-head buffer)
> (circular-buffer-number buffer))
> (length (circular-buffer-data buffer))))
> item)
> (incf (circular-buffer-number buffer))
> item)
> (error "Circular buffer is full")))
>
> (defun circular-buffer-get (buffer)
> (if (zerop (circular-buffer-number buffer))
> (error "Circular buffer is empty")
> (prog1
> (aref (circular-buffer-data buffer) (circular-buffer-head buffer))
> (incf-mod (circular-buffer-head buffer)
> (length (circular-buffer-data buffer)))
> (decf (circular-buffer-number buffer)))))
>
> --
> __Pascal Bourguignon__ http://www.informatimago.com/
>
> NEW GRAND UNIFIED THEORY DISCLAIMER: The manufacturer may
> technically be entitled to claim that this product is
> ten-dimensional. However, the consumer is reminded that this
> confers no legal rights above and beyond those applicable to
> three-dimensional objects, since the seven new dimensions are
> "rolled up" into such a small "area" that they cannot be
> detected.
Thanks Pascal. That helped me understand Thomas' code as well.
Mirko