From: Deepak Goel
Subject: another macro that forces function to return in finite time.
Date:
Message-ID: <yz2z7kzchqrz.fsf@rac3.wam.umd.edu>
I am also looking to define a macro that forces a function to return
within, say 5 seconds.
Thus, (return-soon + 1 2 3)
either ends up returning 6, but if + does not compute within a few
seconds, the macro should yield nil.
Any help appreciated. I don;t know how to even start on this one.
How do you say to lisp: try running this expression for a max. of 5
seconds, and if no result, quit.
--Deepak, http://www.glue.umd.edu/~deego
From: Kent M Pitman
Subject: Re: another macro that forces function to return in finite time.
Date:
Message-ID: <sfw66evluhq.fsf@world.std.com>
Deepak Goel <·····@rac3.wam.umd.edu> writes:
> I am also looking to define a macro that forces a function to return
> within, say 5 seconds.
I'm not entirely sure this is a good idea. Most uses of this I've seen
substitute for poor design of some algorithm, and being to lazy to analyze
why it doesn't terminate or when it should terminate. That isn't to say
there can't be legit reasons to do this, but ...
Also, you shouldn't use this kind of thing really a lot since it's going
to do cause a lot of processes to get created. You need a globally
applied theory of how many processes is polite.
And, of course, you may find that for very short values, setting up the race
is itself expensive. It depends on whether you're heading off something that
would take merely "a little longer" or that "might not terminate".
So the use of the word "soon" below might be misguided.
> Thus, (return-soon + 1 2 3)
> either ends up returning 6, but if + does not compute within a few
> seconds, the macro should yield nil.
This is poor style for the design of a macro. You shouldn't write macros
where the args are shape-shifted forms of their underlying meaning. In
particular, you show + in a "value" position, not a "function" position.
But you really mean it in the "function" position. You should have your
macro take a shape like
(return-soon (+ 1 2 3)).
> Any help appreciated. I don;t know how to even start on this one.
> How do you say to lisp: try running this expression for a max. of 5
> seconds, and if no result, quit.
You need a multitasking Lisp to do this. Lots of them are. The syntax
varies, unfortunately. Many have an MP (multi-processing) package or
something similar. The Lisp Machine, for example, uses the PROCESS package.
And you should say what to return when it doesn't succeed, or else you
should signal. But returning NIL is very limiting.
e.g.,
(defmacro value-or-timeout (form timeout &optional (timeout-value nil))
`(race #'(lambda () ,form)
#'(lambda () (sleep ,timeout) ,timeout-value)))
(defun race (fn1 fn2 &optional (name "Race Partner"))
(let ((done nil))
(block done
(let ((other
(mp:process-run-function name '()
#'(lambda (other)
(let ((results2 (multiple-value-list (funcall fn2))))
(mp:without-preemption
(unless done
(setq done t)
(mp:process-interrupt other
#'(lambda () (return-from done
(values-list results2))))))))
mp:*current-process*)))
(unwind-protect
(funcall fn1)
(mp:without-preemption
(unless done
(setq done t)
(mp:process-kill other))))))))
(value-or-timeout (+ 1 1) 1.0 ;seconds
) => 2
(value-or-timeout (progn (sleep 2) ;seconds
(+ 1 1))
1.0 ;seconds
(values 3 "timed out")
) => 3, "timed out"
I didn't test this code beyond this very simple example, so I can't guarantee
you that it will stand up under heavy stress. But at least it should give
you an idea of the general shape that a solution to this problem would take
on.
Incidentally, note that the only reason this needs to be a macro is to delay
evaluation of the form to be raced. If you instead gave it a function instead
of a form, such as I do in the macro's expansion, which just calls RACE, an
ordinary function, then there would need to be no macro involved at all.
From: Deepak Goel
Subject: Re: another macro that forces function to return in finite time.
Date:
Message-ID: <yz2zsnhzx2cn.fsf@rac1.wam.umd.edu>
> I'm not entirely sure this is a good idea. Most uses of this I've seen
> substitute for poor design of some algorithm, and being to lazy to analyze
> why it doesn't terminate or when it should terminate. That isn't to say
> there can't be legit reasons to do this, but ...
I think mine is a legit reason. I am not doing this to be lazy and
ignore errors.
I am looking to define a general macro fuzzy-lisp. This will be an AI
application. I want to work with a population of lisp-programs that
get created by genetic-evolution operators.. And the entire
calculation by any one individual in the population would be wrapped
by a fuzzy-lisp macro. This fuzzy-lisp macro would force the function
to return in a finite time, and would rectify the errors.
> > Thus, (return-soon + 1 2 3)
> > either ends up returning 6, but if + does not compute within a few
> > seconds, the macro should yield nil.
>
> This is poor style for the design of a macro. You shouldn't write macros
> where the args are shape-shifted forms of their underlying meaning. In
> particular, you show + in a "value" position, not a "function" position.
> But you really mean it in the "function" position. You should have your
> macro take a shape like
> (return-soon (+ 1 2 3)).
Hmm.. i see.. in the final form of the fuzzy-lisp macro, i will
probably take this advice. The above was just an example.
> > Any help appreciated. I don;t know how to even start on this one.
> > How do you say to lisp: try running this expression for a max. of 5
> > seconds, and if no result, quit.
>
> You need a multitasking Lisp to do this. Lots of them are. The syntax
> varies, unfortunately. Many have an MP (multi-processing) package or
> something similar. The Lisp Machine, for example, uses the PROCESS package.
This is very surprising. I would have thought such a 'natural'
question should be solvable within ANSI standards and therefore,
should be solvable in a uniform way, across all common-lisps..
Disappointed :(
I will give your example a try. Thanks a ton.
From: Bulent Murtezaoglu
Subject: Re: another macro that forces function to return in finite time.
Date:
Message-ID: <87wv7bixcy.fsf@nkapi.internal>
[...]
DG> I am looking to define a general macro fuzzy-lisp. This will
DG> be an AI application. I want to work with a population of
DG> lisp-programs that get created by genetic-evolution
DG> operators.. And the entire calculation by any one individual
DG> in the population would be wrapped by a fuzzy-lisp macro.
DG> This fuzzy-lisp macro would force the function to return in a
DG> finite time, and would rectify the errors. [...]
Hmm, if you have an MP lisp maybe you could have a supervisor process
that spawns, checks up on, and -- if necessary -- kills a whole bunch
of these.
If you don't have MP facilities then you are left with whatever the
OS-CL interface provides for interrupts and timed alarms. In C what
you want can be handled by a setjump saving to a global and longjump
called from timer signal/interrupt handler (think how you'll need to
unwind the C call stack to restore the "environment" to the point
where you were just about to call the function you just interrupted).
This is implementation-dependent as the timer signals are not required
to be available by the C standard. In CL, the catch-throw facility is
all I can think of that comes close, even then it is unclear to me how
you can throw from an interrupt handler unless the implementation
guarantees that it will execute in the same environment as the
interrupted function. It probably will, but you'll need to experiment
or dig into whatever documentation is available.
cheers,
BM
From: Pierre R. Mai
Subject: Re: another macro that forces function to return in finite time.
Date:
Message-ID: <877kzbr4i0.fsf@orion.bln.pmsf.de>
Deepak Goel <·····@rac1.wam.umd.edu> writes:
> This is very surprising. I would have thought such a 'natural'
> question should be solvable within ANSI standards and therefore,
> should be solvable in a uniform way, across all common-lisps..
This depends on your definition of natural. One man's natural is
another man's (or woman's) artificial. As Kent has already pointed
out, there are only very few legitimate uses of such a timeout
mechanism, so this is one indiciation why it hasn't been standardized:
There is little user pressure to do so.
The second reason is that such a function presuposes either an MP
capability, or at least some time-driven asynchronous interrupt
capability. It is not clear that all implementations should be
constrained to have such a facility, which is another reason why
something like this isn't standardized.
Regs, Pierre.
--
Pierre R. Mai <····@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein
From: Kent M Pitman
Subject: Re: another macro that forces function to return in finite time.
Date:
Message-ID: <sfw1ypjimn9.fsf@world.std.com>
"Pierre R. Mai" <····@acm.org> writes:
> Deepak Goel <·····@rac1.wam.umd.edu> writes:
>
> > This is very surprising. I would have thought such a 'natural'
> > question should be solvable within ANSI standards and therefore,
> > should be solvable in a uniform way, across all common-lisps..
>
> This depends on your definition of natural. One man's natural is
> another man's (or woman's) artificial. As Kent has already pointed
> out, there are only very few legitimate uses of such a timeout
> mechanism, so this is one indiciation why it hasn't been standardized:
> There is little user pressure to do so.
>
> The second reason is that such a function presuposes either an MP
> capability, or at least some time-driven asynchronous interrupt
> capability. It is not clear that all implementations should be
> constrained to have such a facility, which is another reason why
> something like this isn't standardized.
Actually, I was thinking more about this, multiprocessing was on the
original list of tasks to be solved for ANSI CL. As I recall, it was
deemed not ripe for standardization (in the 1986-1988 timeframe)
because the vendors said there were subtle (and even sometimes
not-so-subtle) differences between the various vendors'
implementations such that all the vendors feared they would be badly
harmed by having to shoehorn into a common standard.
Part of this was that some implementations used the quantum model that
had things like sleep times and run quanta and all that; others were
moving to a semaphor model (explicit blocking and unblocking, etc.)
As I look at the interfaces these days, I see mostly the quantum model,
which I thought had been on the way out for some vendors. It's an aspect
of operating systems I haven't really tracked in a lot of detail, so I
can't say what happened in there. I'm hoping the guys from Franz can fill
in some stuff here, since I'm pretty sure they were quite vocal about
the idea that this was not ripe for standardization at one point along
the way.
From: Tim Bradshaw
Subject: Re: another macro that forces function to return in finite time.
Date:
Message-ID: <nkjvgmvuey6.fsf@tfeb.org>
Kent M Pitman <······@world.std.com> writes:
>
> Part of this was that some implementations used the quantum model that
> had things like sleep times and run quanta and all that; others were
> moving to a semaphor model (explicit blocking and unblocking, etc.)
> As I look at the interfaces these days, I see mostly the quantum model,
> which I thought had been on the way out for some vendors. It's an aspect
> of operating systems I haven't really tracked in a lot of detail, so I
> can't say what happened in there. I'm hoping the guys from Franz can fill
> in some stuff here, since I'm pretty sure they were quite vocal about
> the idea that this was not ripe for standardization at one point along
> the way.
Well, none of the CL MP systems I've seen are anything like ripe for
standardisation. I think you'd want to standardise something that
won't completely screw you on multiprocessors, and exporting stuff
like WITHOUT-PREEMPTION doesn't help there. Additionally the
wait-until-a-function-returns-true interface is pretty toxic if you
want to live on some native threading system. I've spend some time
thinking about what a less braindead interface would look like, but I
think it's fairly hard work. Looking at what Java does seems like a
reasonable start to me, but I'm not sure if it's a reasonable
interface.
--tim
Deepak Goel wrote:
>
> I am also looking to define a macro that forces a function to return
> within, say 5 seconds.
>
> Thus, (return-soon + 1 2 3)
> either ends up returning 6, but if + does not compute within a few
> seconds, the macro should yield nil.
>
> Any help appreciated. I don;t know how to even start on this one.
> How do you say to lisp: try running this expression for a max. of 5
> seconds, and if no result, quit.
It depends on the MP capabilities of your implementation. LispWorks has
ready usable timers that you can define. If you have nor timers but MP you
can create a thread that SLEEPs n seconds and then looks if the calculation
is ready and if not then MP:INTERRUPT-PROCESSes the calculation-process.
Regards,
Jochen
From: Deepak Goel
Subject: Re: another macro that forces function to return in finite time.
Date:
Message-ID: <yz2zr8xjx23u.fsf@rac1.wam.umd.edu>
>
> It depends on the MP capabilities of your implementation. LispWorks has
> ready usable timers that you can define. If you have nor timers but MP you
> can create a thread that SLEEPs n seconds and then looks if the calculation
> is ready and if not then MP:INTERRUPT-PROCESSes the calculation-process.
hmm.. Thanks. As in my response to Kent's response, i am very
surprised that such a 'natural' question should have an
implementation-dependent solution... and should not have a uniform
solution that would follow straight from lisp's ANSI specs..
Anyways, i still hope someone can provide help for the previous
question---a macro that rectifies the number of arguments that are to
be passed to the function. Basically, i can try to write the macro
myself, but am wondering what function one can use to examine the
definition of a given function so that one can determine the number
of arguments the given function expects..
--Deepak, http://www.glue.umd.edu/~deego
From: Frode Vatvedt Fjeld
Subject: Re: another macro that forces function to return in finite time.
Date:
Message-ID: <2hofsn3k2w.fsf@dslab7.cs.uit.no>
Deepak Goel <·····@rac3.wam.umd.edu> writes:
> I am also looking to define a macro that forces a function to return
> within, say 5 seconds.
In Allegro CL you express this by MP:WITH-TIMEOUT. For example,
(with-timeout (5 'slow-user)
(read))
will either return what is READ, or if nothing can be read for 5
seconds SLOW-USER is returned.
--
Frode Vatvedt Fjeld