Hello everyone,
I spent a couple of hours trying to solve a small problem of mine: I'd
like to build a list in a fault-tolerant way. That is, if one of the
functions called to build the list decides that the computation must
be interrupted, 1) A partial list is returned, composed of all those
elements computed so far, and 2) no other forms are evaluated. Since
conditional evaluation is necessary a macro is needed, which I called
list* for lack of a better name.
In other words, if the computation is not interrupted, it should
behave exactly like (list ...). Otherwise, let's say function "irq"
interrupts the computation and returns 3. Then,
(list* 1 (+ 1 1) (irq) (/ 3 0))
should return
(1 2)
or
(1 2 3)
I couldn't decide whether list* should include the value returned by
the interrupting function or not. So the first question is: which do
you think is best?
Unfortunately I don't know if this kind of problem is already well-
known. I couldn't find anything on Google since I couldn't come up
with specific enough terms to search for. Maybe this is a specific
instance of a more general problem, who knows...
I came up with a working but hackish 10-line solution (will post if
asked), using a global variable to keep the interruption state. Even
though that solves my problem, I was wondering if there are more
elegant solutions.
Could you please provide a link discussing the problem and/or
providing a solution in lisp?
Maybe you can come up with your own original solution!
Please be aware that:
1) list* should be nestable. An interruption to an inner list* should
interrupt all outstanding list*s. A "firewall" mechanism could be also
implemented to override this behavior.
2) All interruption mechanisms are valid, but some are better than
others. My solution is horrible. Much better would be a using a catch/
trow or a block. Maybe you could wrap the body in a flet, capturing a
symbol. The roads to enlightenment truly are uncountable.
Thanks in advance for you help.
On Aug 21, 7:55 pm, icemaze <·······@gmail.com> wrote:
> Hello everyone,
> I spent a couple of hours trying to solve a small problem of mine: I'd
> like to build a list in a fault-tolerant way. That is, if one of the
> functions called to build the list decides that the computation must
> be interrupted, 1) A partial list is returned, composed of all those
> elements computed so far, and 2) no other forms are evaluated. Since
> conditional evaluation is necessary a macro is needed, which I called
> list* for lack of a better name.
>
Let's avoid the term "LIST*" since that it already taken. :)
http://www.lispworks.com/documentation/HyperSpec/Body/f_list_.htm
> Please be aware that:
> 1) list* should be nestable. An interruption to an inner list* should
> interrupt all outstanding list*s. A "firewall" mechanism could be also
> implemented to override this behavior.
> 2) All interruption mechanisms are valid, but some are better than
> others. My solution is horrible. Much better would be a using a catch/
> trow or a block. Maybe you could wrap the body in a flet, capturing a
> symbol. The roads to enlightenment truly are uncountable.
>
> Thanks in advance for you help.
Is this what you're looking for? It seems to pass the initial tests.
(define-condition interrupt (condition) ())
(defmacro listerrupt (&rest arguments &environment env)
(when arguments
(let ((arg (gensym "ARG-")))
`(let ((,arg (handler-case ,(first arguments)
(interrupt () nil))))
(if ,arg
(cons ,arg (listerrupt ,@(rest arguments)))
nil)))))
CL-USER> (defun irq () (signal 'interrupt))
IRQ
CL-USER> (listerrupt 1 2 3)
(1 2 3)
CL-USER> (listerrupt 1 2 (irq) 3)
(1 2)
CL-USER> (listerrupt 1 2 (listerrupt 'a 'b (irq) 'c) 3 (irq) 4)
(1 2 (A B) 3)
On Aug 21, 9:04 pm, Geoff Wozniak <·············@gmail.com> wrote:
> (defmacro listerrupt (&rest arguments &environment env)
> (when arguments
> (let ((arg (gensym "ARG-")))
> `(let ((,arg (handler-case ,(first arguments)
> (interrupt () nil))))
> (if ,arg
> (cons ,arg (listerrupt ,@(rest arguments)))
> nil)))))
>
*sigh* Nor do you need the &ENVIRONMENT arguments.
Teaches me for posting right after a few drinks at dinner...
Geoff Wozniak wrote:
> On Aug 21, 9:04 pm, Geoff Wozniak <·············@gmail.com> wrote:
>
>>(defmacro listerrupt (&rest arguments &environment env)
>> (when arguments
>> (let ((arg (gensym "ARG-")))
>> `(let ((,arg (handler-case ,(first arguments)
>> (interrupt () nil))))
>> (if ,arg
>> (cons ,arg (listerrupt ,@(rest arguments)))
>> nil)))))
So listerrupt can never collect nil as a valid value? Ick.
kt
--
http://www.theoryyalgebra.com/
"Algebra is the metaphysics of arithmetic." - John Ray
"As long as algebra is taught in school,
there will be prayer in school." - Cokie Roberts
"Stand firm in your refusal to remain conscious during algebra."
- Fran Lebowitz
"I'm an algebra liar. I figure two good lies make a positive."
- Tim Allen
Hi guys, sorry to keep you all waiting.
First of all, sorry for the "lisp*" gaffe. That's what I get for not
studying CLtLv2 before trying to solve moderately complex problems. I
guess my noob-ness shows... ^_^
I'll use the name "ilist", since this one seems to be unused.
Thanks to Geoff for posting a globals-less solution. It helped me a
lot as I gained that "slightly different" perspective and managed to
come up with a more functional solution (see below).
I think I didn't explain clearly one of the features of this macro, so
I'll try again: when I said that ilist should be nestable I meant that
interruptions must propagate down to outer ilists.
For example:
(ilist 1 2 (ilist 3 (function-that-interrupts) 4) 5)
should return
(1 2 (3))
and not
(1 2 (3) 5)
Looks like Geoff's solution cannot do that, as his own example
demonstrates.
So, first of all, let me introduce you to my own solution, that makes
use of multiple values:
(I guess you are all experienced enough to know about with-gensyms; mv-
bind is just an abbreviation for multiple-value-bind.)
=== BEGIN CODE
(defmacro ilist (&body body)
`(ilist* ,body))
(defmacro ilist* (forms)
(if (null forms)
(values nil nil)
(with-gensyms (value result interrupt interrupted?)
`(mv-bind (,value ,interrupt) ,(car forms)
(if ,interrupt
(values (list ,value) t)
(mv-bind (,result ,interrupted?)
(ilist* ,(cdr forms))
(values (cons ,value ,result)
,interrupted?)))))))
=== END CODE
The ilist macro is there only for convenience. The ilist* macro
returns two values: one is the partial result and the other is the
interruption state. This way interruptions can be obtained returning
true as the second value. That propagates down the stack and gives the
desired effect:
CL-USER[86]: (ilist 1 (ilist 10 20 30) 3)
(1 (10 20 30) 3)
CL-USER[87]: (ilist 1 (ilist 10 (values 20 t) 30) 3)
(1 (10 20))
Obviously, one should be very careful using functions that return
multiple values. That is, keep hyperspec handy! There's probably a
better solution, but this is good enough for me.
So... what can this be used for? Right now, I'm using nested lists to
generate HTML output the usual way. I didn't like CL-WHO approach so I
wrote my own function (not a macro) to generate tags at runtime, which
I like since it's more functional (i.e. I can call functions that
return a part of the page -- aka components). The problem was, of
course, how to interrupt processing in face of a problem or (as in my
case) other conditions. I needed to keep the "output" generated so far
and ilist solves that problem. So markup languages are a natural
application for ilist, maybe there are more. In general, it's useful
when you have to generate complex nested lists and need a way to stop.
I don't know if anyone will ever find this useful but here it is.
Thanks again. ;)
On Aug 22, 6:48 pm, icemaze <·······@gmail.com> wrote:
> Obviously, one should be very careful using functions that return
> multiple values. That is, keep hyperspec handy! There's probably a
> better solution, but this is good enough for me.
>
Here's another attempt that avoids the multiple value problem by using
signals, avoids the NIL problem of my other attempt and short-ciruits
in the way you want. It also accommodates the cases when the form
producing the interrupt does or does not produce a value.
(defparameter *special-macrolet*
(gensym "SPECIAL-MACROLET-"))
(define-condition interrupt (condition)
((value :initarg :value :initform nil :reader value)
(usedp :initarg :usedp :initform t :reader usedp)))
(defun irq (&optional value usedp)
(signal 'interrupt :value value :usedp usedp))
(defmacro %ilist (&rest arguments)
(let ((result (gensym "RESULT-")))
`(let (,result)
(handler-case
(progn ,@(loop
for arg in arguments
collect `(push ,arg ,result))
(nreverse ,result))
(interrupt (c)
(signal 'interrupt
:value (if (usedp c)
(nreverse (cons (value c) ,result))
(nreverse ,result))
:usedp t))))))
(defmacro ilist (&rest arguments &environment env)
(multiple-value-bind (expansion expanded-p)
(macroexpand-1 `(,*special-macrolet*) env)
(declare (ignore expansion))
(if expanded-p
`(%ilist ,@arguments)
`(macrolet ((,*special-macrolet* () t))
(handler-case (%ilist ,@arguments)
(interrupt (c) (value c)))))))
The MACROLET is used in an idomatic way: set up the environment for
subforms so that you know how to expand them. In this case, if you
didn't add something to the environment, nested ILIST forms would
behave in the way I originally defined the short-circuiting. Another
idiom (for me, anyway) is that of using a GENSYM to denote a name for
the speical macrolet to prevent name clashes.
CL-USER> (ilist 1 2 3)
(1 2 3)
CL-USER> (ilist (ilist))
(NIL)
CL-USER> (ilist (irq))
NIL
CL-USER> (ilist (irq nil t))
(NIL)
CL-USER> (ilist 1 2 (ilist (values 10 20) (irq)) 3 4)
(1 2 (10))
CL-USER> (ilist 1 2 (ilist (values 10 20) (irq 30 t)) 3 4)
(1 2 (10 30))
You may get some "deleting unreachable code" notes. This is likely a
result of the fact that IRQ just signals INTERRUPT and the compiler
can determine that some of the forms in the PROGN will not be
evaluated.
Sweet! :D You definitely have more experience with macros than I do.
Your solution is a little gem. ;) I'll have some good time trying to
understand the inner workings of your idiomatic use of macrolet, which
is new to me.
Thanks!
On Aug 21, 4:55 pm, icemaze <·······@gmail.com> wrote:
> Hello everyone,
> I spent a couple of hours trying to solve a small problem of mine: I'd
> like to build a list in a fault-tolerant way. That is, if one of the
> functions called to build the list decides that the computation must
> be interrupted, 1) A partial list is returned, composed of all those
> elements computed so far, and 2) no other forms are evaluated. Since
> conditional evaluation is necessary a macro is needed, which I called
> list* for lack of a better name.
>
> In other words, if the computation is not interrupted, it should
> behave exactly like (list ...). Otherwise, let's say function "irq"
> interrupts the computation and returns 3. Then,
> (list* 1 (+ 1 1) (irq) (/ 3 0))
> should return
> (1 2)
> or
> (1 2 3)
Okay. This clearly means that the LIST* construct (or let's call it
LISTERRUPT) in fact catches the interruption, recovers from it and
returns the partial result.
But ...
> Please be aware that:
> 1) list* should be nestable. An interruption to an inner list* should
> interrupt all outstanding list*s. A "firewall" mechanism could be also
> implemented to override this behavior.
Now here come the problems. This LISTERRUPT is nestable in such a way
that nested instances interact with each other. An interruption within
a LISTERRUPT is also visible to all of the enclosing LISTERRUPT. The
problem is that this is semantically at odds with the idea that
LISTERRUPT catches the interruption (and therefore contains it). It's
as if LISTERRUPT contains the interruption---and returns a partial
list to the enclosing expression---and yet it does not contain the
interruption, since the interruption is passed to the enclosing
LISTERRUPT.
The question is, what determines how much of the intermediate
computation should continue to take place?
Concretely, suppose you have:
(LISTERRUPT
'X
(LIST 'A
'B
(LISTERRUPT 1 (IRQ) 2)
'C)
'Y)
The innermost LISTERRUPT catches the interrupt, and returns (1). That
much is clear. This means that the evaluation if LIST does not see the
interrupt. All four the parameters are evaluated left to right and it
should return (A B (1) C). Yet, the interrupt is still somehow
pending; at the outer LISTERRUPT level, the 'Y is ignored so that (X
(A B (1) C)) is returned.
So /was/ the interrupt caught and handled or was it not? Will it ever
be handled?
The answer seems to be that the interrupt is more like a global flag,
not unlike a pending POSIX signal. When it this flag is true, the
interrupt situation is pending pending, and it tells all LISTERRUPT
forms (currently evaluating as well as future ones!) to stop
evaluating more forms and just return a list of what they have
evalauted so far. So for instance:
(progn
(irq) ;; interrupt flag set!
(list (listerrupt 1 2 3)
(listerrupt 'a 'b 'c)))
-> (nil nil)
Note how the newly evaluated LISTERRUPT forms simply bail out and
return an empty list, even though (irq) is not nested within them,
since the interrupt is simply pending.
Okay, this way it makes halfway sense. LISTERRUPT is basically a
conditional statement which evaluates forms only if an interrupt is
not pending; and if an interrupt becomes pending /while/ the forms are
being evaluated, then don't evaluate any more. Of course, at some
dynamically enclosing level, you would check that interrupt flag,
recover and clear it.
You could have an interrupt version of PROGN, a looping construct
which keeps re-evaluating a form until the interrupt is pending, etc.
Even:
(funcallinterrupt <funtion> <args> ...)
this evaluates the arguments left to right until they are all
evaluated or an interrupt happens. Then the function is called with
the collected argument list (and it better be a function that can
handle different argument list lengths!). LISTERRUPT could then be
implemented using
(funcallinterrupt #'list ...)
And of course
(mapcarinterrupt <function> <lists> ...)
which behaves like MAPCAR but stops when an interrupt happens, etc. :)