Consider the following code snippet:
In Common Lisp:
(defun (forever) (* 2 (forever)))
In Scheme:
(define (forever) (* 2 (forever)))
In either of those lisps:
(if (forever) 2 2)
In either case it is legal for a compiler to emit code
that loops forever, blows the stack/heap, or invokes
an exception handler.
Should it also be legal for a compiler to emit code that
simply returns 2 (from the if expression), or should the
programmer be able to _rely_ on a function like forever
to transfer flow of control to an exception handler?
Bear
On 22 dic, 03:12, Ray Dillinger <····@sonic.net> wrote:
> Consider the following code snippet:
>
> In Common Lisp:
> (defun (forever) (* 2 (forever)))
>
> In Scheme:
> (define (forever) (* 2 (forever)))
>
> In either of those lisps:
> (if (forever) 2 2)
>
> In either case it is legal for a compiler to emit code
> that loops forever, blows the stack/heap, or invokes
> an exception handler.
>
> Should it also be legal for a compiler to emit code that
> simply returns 2 (from the if expression), or should the
> programmer be able to _rely_ on a function like forever
> to transfer flow of control to an exception handler?
>
> Bear
You may intent to execute "forever" for whatever the result would be,
so I think the compiler is in the obligation of executing it.
Otherwise, it will be lazy evaluation.
There are exceptions, for example with OR and AND.
In article <·························@news.sonic.net>,
Ray Dillinger <····@sonic.net> wrote:
> Consider the following code snippet:
>
> In Common Lisp:
> (defun (forever) (* 2 (forever)))
>
> In Scheme:
> (define (forever) (* 2 (forever)))
>
> In either of those lisps:
> (if (forever) 2 2)
>
>
> In either case it is legal for a compiler to emit code
> that loops forever, blows the stack/heap, or invokes
> an exception handler.
>
> Should it also be legal for a compiler to emit code that
> simply returns 2 (from the if expression), or should the
> programmer be able to _rely_ on a function like forever
> to transfer flow of control to an exception handler?
In the CL case it should never get to this point, since the function
definition is syntactically incorrect.
--
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 ***
On Dec 21, 6:12 pm, Ray Dillinger <····@sonic.net> wrote:
> Consider the following code snippet:
>
> In Common Lisp:
> (defun (forever) (* 2 (forever)))
I.e. (defun forever () (* 2 (forever)))
> In Scheme:
> (define (forever) (* 2 (forever)))
>
> In either of those lisps:
> (if (forever) 2 2)
>
> In either case it is legal for a compiler to emit code
> that loops forever, blows the stack/heap, or invokes
> an exception handler.
Whether is is legal depends on what is written in whatever licenses
you agreed to that accompany your Lisp implementation, and how those
would be interpreted in the courts where you live. How dumb are your
laws? :)
> Should it also be legal for a compiler to emit code that
> simply returns 2 (from the if expression), or should the
> programmer be able to _rely_ on a function like forever
> to transfer flow of control to an exception handler?
The FOREVER, as defined above, has no valuable side effects and can be
elided, because the function wasn't declared NOINLINE and the call is
presumably from the same file.
Blowing up such that the whole image terminates or a condition is
signaled is not a valuable side effect. It is a defect.
The proper job of a language implementation is to translate correct
abstract behaviors, including valuable side effects, into correct
actual behaviors.
It would be a wrongheaded design to require all abstract defects to be
preserved in translation where they would appear as some specific
actual behaviors.
Anyway, you can force your Lisp to generate the call to FOREVER. The
way to do this is to declare the function NOTINLINE.
See 3.2.2.3 of CLHS.
``A call within a file to a named function that is defined in the same
file refers to that function, unless that function has been declared
notinline . The consequences are unspecified if functions are
redefined individually at run time or multiply defined in the same
file.''
On Dec 22, 2:12 am, Ray Dillinger <····@sonic.net> wrote:
>
> Should it also be legal for a compiler to emit code that
> simply returns 2 (from the if expression), or should the
> programmer be able to _rely_ on a function like forever
> to transfer flow of control to an exception handler?
This problem is obviously not soluble in general because it's the
halting problem.
However, in the specific case where a compiler can prove that there
are no side-effects of a function and its result is not used, then it
certainly generally ought to be OK to elide calls to it.
However "no side effects" is an interesting question which is often
over simplified. Consider this:
(progn (sleep 10) (do-something))
Well, with an obvious definition, SLEEP has "no side effects". Except
it does: it waits for 10 seconds, and that's a very important real-
world side-effect. If I put the comments back in to this code, we can
see why:
(progn
(sleep 10) ; give user time to panic and interrupt
(do-something)) ; bounce system
I'd be pretty unhappy if the compiler elided that call to SLEEP.
Thinking of it this way, failure to halt is a pretty serious side-
effect. So (for a modified definition)
(defun forever () (loop))
(if (forever) (set-off-the-bomb) (set-off-the-bomb))
I'd kind of like it to be the case that a responsible compiler did
*not* elide that call.
So I think that really this is a subtle question. In my view a
compiler should elide code only if it can prove no side effects, where
"side effects" include intentional real-world side-effects, such as
pausing the program (and many other things), and in particular where
it can prove that the code halts.
One real-world side effect is exhausting the system's resources. For
your definition of FOREVER I find it hard to see that it would not do
that, because of the (* 2 (forever)) - either that's going to burst
the stack, or it's going to get a bignum overflow at some point I
think. If it does not do that, then it fails to halt, and I think
that is a side-effect (by my definition) for sure.
So I think these questions are very subtle in general, and working
from some theoretical model of computation does not tell you the
useful answer to give.
--tim
No hyphens were harmed in the production of this message
On Dec 22, 9:03 am, Tim Bradshaw <··········@tfeb.org> wrote:
> However "no side effects" is an interesting question which is often
> over simplified. Consider this:
>
> (progn (sleep 10) (do-something))
>
> Well, with an obvious definition, SLEEP has "no side effects".
Obviously it does have a side effect: it inserts a pause of some
hopefully more or less reliable duration between some previous side
effect and a future side effect. Timing of externally visible effects
is important, and is itself an effect.
> Except
> it does: it waits for 10 seconds, and that's a very important real-
> world side-effect.
> (progn
> (sleep 10) ; give user time to panic and interrupt
> (do-something)) ; bounce system
>
> I'd be pretty unhappy if the compiler elided that call to SLEEP.
>
> Thinking of it this way, failure to halt is a pretty serious side-
> effect.
Halting by infinite loop is a /defect/, not an /effect/.
If the compiler detects an infinite loop which contains on side
effects, it should replace it with (error "infinite loop detected").
Or at least a compile-time diagnostic.
The only piece of code in a system which has a right to halt by means
of spinning the CPU is something deep in the operating system for
handling a system halt (or a CPU halt for hot-swapping).
You'd want to handle this type of halt not necessarily by a naive loop
in the high level source code, but by taking advantage of whatever
instruction set feature is available for doing a proper halt.
E.g. on the Motorola 68000, you might write a loop around the STOP
instruction.
That instruction, by the way, is privileged. Good reason for that;
halting the machine needs to be virtualized. If a guest virtual OS
performs a proper STOP, the host OS gains control and suspends only
the guest OS. If the guest OS performs a stupid infinite loop, the
host OS suffers!
> (defun forever () (loop))
> (if (forever) (set-off-the-bomb) (set-off-the-bomb))
> I'd kind of like it to be the case that a responsible compiler did
> *not* elide that call.
The programmer is responsible here, not the compiler.
What about:
(if (forever)
(disarm-bomb)
(disarm-bomb))
What is the ``esponsible'' thing for the compiler to do now?
Moreover, what if setting off the bomb is a good thing, and disarming
it is a bad thing? Without more information, we don't know whether the
bomb blowing up is good or evil. What if the bomb is embedded in an
asteroid that is headed for a populated planet? :)
Finally, if it's really, really important that the machine halt at
some point, shouldn't that have been tested?
> So I think that really this is a subtle question. In my view a
> compiler should elide code only if it can prove no side effects, where
> "side effects" include intentional real-world side-effects, such as
> pausing the program (and many other things), and in particular where
> it can prove that the code halts.
What should it do if it can't prove that the code halts? And should
the performance of a side effect depend on what the compiler can and
cannot prove?
There are lost of examples of side-effect-free code that you might
want to elide during optimization, for which termination cannot be
proved. Any such code could be regarded as a potential infinite loop
in disguise which must be preserved. That suspicion then interferes
with legitimate optimization.
I would say that only the use of valid interfaces for halting the
program should be considered as expressing the true intent to halt:
making a halting system call, or executing some special instruction.
Since SLEEP is a side effect that can't be elided, then a good way of
halting would be (LOOP (SLEEP 42)).
> One real-world side effect is exhausting the system's resources. For
> your definition of FOREVER I find it hard to see that it would not do
> that, because of the (* 2 (forever)) - either that's going to burst
> the stack, or it's going to get a bignum overflow at some point I
> think. If it does not do that, then it fails to halt, and I think
> that is a side-effect (by my definition) for sure.
Everything that happens in the machine can be regarded as a side
effect. What we do is we separate the inessential or undesireable
ones (the ``bad'') from the necessary, useful ones (the ``good'').
It's a bad side effect that computation takes time and energy. We'd
like computation to take zero time and energy. That's not realistic,
but we can reduce the time, which we call optimization. To that aim,
we reorganize code, invent better algorithms and make faster
hardware. Storage use can be regarded in the same way; it is ineed a
real-world bad side effect that storage is required and that it can be
exhausted. We'd like a program to use less space, all else being
equal.
Since the use of computational time is regarded as a bad side effect,
then an endless loop (not based around a formal halting instruction)
is considered so bad that it's actually a defect!
These days, users have operating systems which can juggle multiple
processes and tell them how much CPU time each one is taking. If your
program hits 100% CPU while obviously doing no useful computational
work, users will report this as a bug. It's not uncommon even for
users without a computing background know that this is ``bad''.
> So I think these questions are very subtle in general, and working
> from some theoretical model of computation does not tell you the
> useful answer to give.
That's right; you have to work from a model where you take into
account the role of the computer in the rest of the world: its
purpose, its resource limitations, how it fits into human values, etc.
Kaz Kylheku wrote:
> On Dec 22, 9:03 am, Tim Bradshaw <··········@tfeb.org> wrote:
>
>>However "no side effects" is an interesting question which is often
>>over simplified. Consider this:
>>
>>(progn (sleep 10) (do-something))
>>
>>Well, with an obvious definition, SLEEP has "no side effects".
>
>
> Obviously it does have a side effect: it inserts a pause of some
> hopefully more or less reliable duration between some previous side
> effect and a future side effect.
More than that: It expresses the programmer's *intent* that
a certain amount of time should be taken.
Absent an expression of such intent, I think the compiler's
job is to make code run correctly, using the minimum of
computer resources, as fast as possible. And that means
when it sees an 'if' expression where the consequent and
alternate are indistinguishable and the predicate is "side
effect free", it should elide evaluation of the predicate
(and detection of possible errors in the predicate) unless
some kind of '-pedantic' switch is set.
But as Tim says, the definition of "side effect free" is
sometimes tricky, like the definition of equality.
The context here is deciding the semantics of a
homebrew lisp variant, not a question about what a
particular existing standard says.
The (forever) predicate sets no variables and contains no
clauses that express a programmer's intent to stop or
produce other visible effects like printing; The compiler
detects an infinite loop while attempting to do constant
propagation and force reduction optimizations, and
therefore replaces it with the expression (warning:
"Infinite loop executed") and emits a warning while
compiling the code. I would call that correct behavior,
although there will always be infinite loops that the
compiler cannot detect.
In compiled code, a call to "warning" returns an error
object, so actually _using_ the value it returns would
result in a call to "error" and a runtime halt. But a
call to "warning", by itself, does not express programmer
intent to halt, and does not produce any side effect
other than printing the warning message.
In the context of a two-armed 'if' where consequent and
alternate are identical, (and in other contexts where the
return value of an expression is not used) a side-effect-
free call can be optimized away. I've been treating
the emission of warning messages as a non-side-effect,
and the surprising result is that the warning message
"Infinite loop executed" in this case is not even being
issued at runtime because the call to "warning" has been
dropped. I still get a warning message at compile time
when the call to "warning" is inserted into the compiled
code, but it later gets optimized away. Although that is
surprising, I sort of like it and may declare it to be
The Right Thing, unless there is some compelling reason
not to.
Bear
On Sat, 22 Dec 2007 20:36:26 -0800, Ray Dillinger <····@sonic.net>
wrote:
>Kaz Kylheku wrote:
>> On Dec 22, 9:03 am, Tim Bradshaw <··········@tfeb.org> wrote:
>>
>>>However "no side effects" is an interesting question which is often
>>>over simplified. Consider this:
>>>
>>>(progn (sleep 10) (do-something))
>>>
>>>Well, with an obvious definition, SLEEP has "no side effects".
>>
>>
>> Obviously it does have a side effect: it inserts a pause of some
>> hopefully more or less reliable duration between some previous side
>> effect and a future side effect.
>
>More than that: It expresses the programmer's *intent* that
>a certain amount of time should be taken.
>
>Absent an expression of such intent, I think the compiler's
>job is to make code run correctly, using the minimum of
>computer resources, as fast as possible. And that means
>when it sees an 'if' expression where the consequent and
>alternate are indistinguishable and the predicate is "side
>effect free", it should elide evaluation of the predicate
>(and detection of possible errors in the predicate) unless
>some kind of '-pedantic' switch is set.
How often in reality are the consequent and alternate
"indistinguishable". That description certainly doesn't match the
semantics of any code I write.
>But as Tim says, the definition of "side effect free" is
>sometimes tricky, like the definition of equality.
Indeed. Even in the "sleep" example, the compiler would have to be
aware of the semantics of sleep. Whether in the predicate position or
not, in general the compiler isn't going to see all the code. Unless
there is a way to indicate whether external code is side effect free,
it is semantically wrong for the compiler to elide a call to it.
>The context here is deciding the semantics of a
>homebrew lisp variant, not a question about what a
>particular existing standard says.
That's fine.
>The (forever) predicate sets no variables and contains no
>clauses that express a programmer's intent to stop or
>produce other visible effects like printing; The compiler
>detects an infinite loop while attempting to do constant
>propagation and force reduction optimizations, and
>therefore replaces it with the expression (warning:
>"Infinite loop executed") and emits a warning while
>compiling the code. I would call that correct behavior,
>although there will always be infinite loops that the
>compiler cannot detect.
What about an infinite loop that does legitimate processing?
>In compiled code, a call to "warning" returns an error
>object, so actually _using_ the value it returns would
>result in a call to "error" and a runtime halt. But a
>call to "warning", by itself, does not express programmer
>intent to halt, and does not produce any side effect
>other than printing the warning message.
As I said in another message, looping without actually halting is one
method of error handling in the embedded world. Of course it's
perfectly fine not to care about supporting that special use. I agree
that the majority of software should not ever be looping indefinitely.
>In the context of a two-armed 'if' where consequent and
>alternate are identical, (and in other contexts where the
>return value of an expression is not used) a side-effect-
>free call can be optimized away. I've been treating
>the emission of warning messages as a non-side-effect,
>and the surprising result is that the warning message
>"Infinite loop executed" in this case is not even being
>issued at runtime because the call to "warning" has been
>dropped. I still get a warning message at compile time
>when the call to "warning" is inserted into the compiled
>code, but it later gets optimized away. Although that is
>surprising, I sort of like it and may declare it to be
>The Right Thing, unless there is some compelling reason
>not to.
>
> Bear
George
--
for email reply remove "/" from address
George Neuner wrote:
> How often in reality are the consequent and alternate
> "indistinguishable". That description certainly doesn't match the
> semantics of any code I write.
Doesn't happen in code I write either, but results with
surprising frequency from code generation, translation,
or macro transformation. This may be due to failures
to optimize that are actually located in other code, but
the general rule about if's with identical branches
is never wrong, even if those failures get fixed.
> Indeed. Even in the "sleep" example, the compiler would have to be
> aware of the semantics of sleep.
The compiler is not really aware of what the actual
side effect is: it is aware that the function, like
several other functions (write, halt, etc) is marked
as side effecting. That's enough, at least for now.
> Whether in the predicate position or
> not, in general the compiler isn't going to see all the code. Unless
> there is a way to indicate whether external code is side effect free,
> it is semantically wrong for the compiler to elide a call to it.
Doesn't matter; you still want it to do all
optimizations on whatever chunk of code it can
see.
> What about an infinite loop that does legitimate processing?
No such loop may exist without a side-effecting call in
it. "Legitimate processing" means returning a value that
gets used (hence not an infinite loop) or otherwise
communicating results (via a call to a function which
MUST, by definition, have a side effect).
> As I said in another message, looping without actually halting is one
> method of error handling in the embedded world. Of course it's
> perfectly fine not to care about supporting that special use. I agree
> that the majority of software should not ever be looping indefinitely.
How do the loops get broken? I suspect that these loops
couldn't be elided because the system could never prove
that they were looping forever with no side effects. But
I'd like an example so I can go and make sure that's true.
Bear
On Tue, 25 Dec 2007 07:15:36 -0800, Ray Dillinger <····@sonic.net>
wrote:
>> Whether in the predicate position or
>> not, in general the compiler isn't going to see all the code. Unless
>> there is a way to indicate whether external code is side effect free,
>> it is semantically wrong for the compiler to elide a call to it.
>
>Doesn't matter; you still want it to do all
>optimizations on whatever chunk of code it can
>see.
Ok.
>> As I said in another message, looping without actually halting is one
>> method of error handling in the embedded world. Of course it's
>> perfectly fine not to care about supporting that special use. I agree
>> that the majority of software should not ever be looping indefinitely.
>
>How do the loops get broken?
Usually by an external interrupt. The handler transfers control to a
resume or restart point if/when the interrupt occurs.
I forgot to mention that this method is also generally used for event
programming with PICs (Programmable Interrupt Controllers). The main
program sets up a bunch of interrupt handlers and then spins forever
leaving most or all of the processing to be done by the handlers.
But the interrupt/signal/condition/event programming model is more
generally useful for many chores. Obviously it is better to sleep or
suspend whenever possible rather than spin uselessly ... but the it
still requires that the compiler know the semantics of library calls
and external code to avoid changing the program's semantics.
>I suspect that these loops
>couldn't be elided because the system could never prove
>that they were looping forever with no side effects. But
>I'd like an example so I can go and make sure that's true.
>
> Bear
George
--
for email reply remove "/" from address
From: Kent M Pitman
Subject: Re: Should compilers elide errors when possible?
Date:
Message-ID: <ufxxum42a.fsf@nhplace.com>
Kaz Kylheku <········@gmail.com> writes:
> On Dec 22, 9:03 am, Tim Bradshaw <··········@tfeb.org> wrote:
> > SLEEP has "no side effects".
>
> Obviously it does have a side effect: it inserts a pause of some
> hopefully more or less reliable duration between some previous side
> effect and a future side effect. Timing of externally visible effects
> is important, and is itself an effect.
Well, uh, ... cringe..., yes, but, ... by this definition of
side-effect, the transformation of most common arithmetic operations
(among many other things) by so-called "identities" would not be
possible to call "side-effect free", since (by optimizing code flow)
they "change" (or, at least, risk changing) the return value of
subsequent calls to, for example, GET-INTERNAL-RUN-TIME and/or
GET-UNIVERSAL-TIME. I'm not exactly sure you want to go down that
terminological rathole.
In article <·············@nhplace.com>,
Kent M Pitman <······@nhplace.com> wrote:
> Kaz Kylheku <········@gmail.com> writes:
>
> > On Dec 22, 9:03 am, Tim Bradshaw <··········@tfeb.org> wrote:
> > > SLEEP has "no side effects".
> >
> > Obviously it does have a side effect: it inserts a pause of some
> > hopefully more or less reliable duration between some previous side
> > effect and a future side effect. Timing of externally visible effects
> > is important, and is itself an effect.
>
> Well, uh, ... cringe..., yes, but, ... by this definition of
> side-effect, the transformation of most common arithmetic operations
> (among many other things) by so-called "identities" would not be
> possible to call "side-effect free", since (by optimizing code flow)
> they "change" (or, at least, risk changing) the return value of
> subsequent calls to, for example, GET-INTERNAL-RUN-TIME and/or
> GET-UNIVERSAL-TIME. I'm not exactly sure you want to go down that
> terminological rathole.
But it's fairly easy to determine functions where the side effects are
purely incidental, and those where the side effects are intentional.
Arithmetic and accessor functions are used primarily for their return
values, assignments are used primarily for their effects on the store.
Then there are functions like PRINT and SLEEP that are used only for
their side effects.
Whether a user-defined function has side effects can be defined
recursively: it has side effects if it calls a built-in function with
side effects according to the above, or if it calls another user-defined
function with side effects.
According to this, a function that just implements an infinite loop or
recursion, without calling any side-effecting functions, doesn't have
any side effects. This leads us back to your point -- is the amount of
time something takes to run part of its side effects? Except for the
SLEEP function, the language spec never makes any claims about how long
anything takes, so it seems strange to include this. However, the
special case of infinite time seems like it should be different.
--
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 ***
On Sat, 22 Dec 2007 15:28:31 -0800 (PST), Kaz Kylheku
<········@gmail.com> wrote:
>
>Halting by infinite loop is a /defect/, not an /effect/.
>
Most embedded programs are infinite loops by design. In cases where
an external problem that halts processing might be corrected by a user
or another software agent, it is a typical tactic for a program to
spin waiting for a restart signal.
George
--
for email reply remove "/" from address
On Dec 22 2007, 11:28 pm, Kaz Kylheku <········@gmail.com> wrote:
>
> Obviously it does have a side effect: it inserts a pause of some
> hopefully more or less reliable duration between some previous side
> effect and a future side effect. Timing of externally visible effects
> is important, and is itself an effect.
But now you're basically doomed, because *everything* is now a side-
effect and no code can ever be elided (read on before responding to
this obviously silly point).
> Halting by infinite loop is a /defect/, not an /effect/.
I fairly frequently write programs which intentionally enter
relatively tight infinite loops. I'd be moderately unhappy if the
compiler eliminated these. These tend to be benchmark-type
applications, but they definitely are not deep in the OS (they are
typically trying to test the performance of multi core systems under
various kinds of resource contention).
Note that I do *not* consider entering an obviously infinite loop
halting for a user program: if I gave that impression I'm sorry. I
wasn't using "halt" in the "stop the processor" sense (obviously user-
level codes don't do that generally), but in the "terminate and return
to your caller" sense. There's not much difference really - if you
just replace any halt instruction by a call to exit(2) (on Unix or
derived systems) this would transform a program that (tries to) do one
into one that does the other.
> Everything that happens in the machine can be regarded as a side
> effect. What we do is we separate the inessential or undesireable
> ones (the ``bad'') from the necessary, useful ones (the ``good'').
That is pretty much my point. Or rather, my point is that what is, or
what is not, a side effect is a somewhat subtle question, and naïve
answers such as "just elide infinite loops" are often not the right
ones.
--tim
Tim Bradshaw wrote:
> I fairly frequently write programs which intentionally enter
> relatively tight infinite loops. I'd be moderately unhappy if the
> compiler eliminated these. These tend to be benchmark-type
> applications, but they definitely are not deep in the OS (they are
> typically trying to test the performance of multi core systems under
> various kinds of resource contention).
Aaand, you get results out of them _somehow_, yes?
Perhaps they send messages or write to a pipe (both
side effects)? Perhaps they read input (also a side
effect)? At the very least if they are testing
performance under resource contention they get locks
and do something (side effecting) with the resources,
right?
These loops may be "infinite" but for any sane purpose
there must be a way you can tell that they are running
- and that way is necessarily a side effect in the
sense the system would have to test for before eliding
"code that has no effect."
Otherwise - eg, if it's just using CPU and doing nothing
else, and you want it to run anyway - then you're doing
something very specialized and peculiar, and I think you
need to be okay with the idea that if your requirements
are that strange, you'll have to tell the compiler
explicitly *NOT* to elide it.
Bear
On Jan 3, 6:07 pm, Ray Dillinger <····@sonic.net> wrote:
>
> These loops may be "infinite" but for any sane purpose
> there must be a way you can tell that they are running
> - and that way is necessarily a side effect in the
> sense the system would have to test for before eliding
> "code that has no effect."
Well, I know they're running because they're using resources, which
means typically consuming some functional units on the system (hmm.
that sounds hugely pretentious: I'm not saying "CPU time" because one
of the systems I've been interested in, Niagara, has, in some
variants, less float units than cores and this was one of the things I
was interested in), and probably some memory/cache and memory/cache
bandwidth (though a sufficiently tight loop is probably not using much
main memory bandwidth of course)
> Otherwise - eg, if it's just using CPU and doing nothing
> else, and you want it to run anyway - then you're doing
> something very specialized and peculiar, and I think you
> need to be okay with the idea that if your requirements
> are that strange, you'll have to tell the compiler
> explicitly *NOT* to elide it.
>
I think I was doing something reasonably odd, yes I'd expect to have
to inform the compiler in some cases (though gcc seems not to elide
even very tight infinite loops).
But the more general point I'm trying to make is that the question of
side-effects is subtle - one person's side-effect is another person's
result. There are questions of intention which a compiler (or other
computational system) should not make simplistic judgements about.
Ray Dillinger wrote:
>
>
>
> Consider the following code snippet:
>
> In Common Lisp:
> (defun (forever) (* 2 (forever)))
>
> In Scheme:
> (define (forever) (* 2 (forever)))
>
> In either of those lisps:
> (if (forever) 2 2)
>
>
> In either case it is legal for a compiler to emit code
> that loops forever, blows the stack/heap, or invokes
> an exception handler.
>
> Should it also be legal for a compiler to emit code that
> simply returns 2 (from the if expression), or should the
> programmer be able to _rely_ on a function like forever
> to transfer flow of control to an exception handler?
Sure. Just wait until the halting problem is solved. ;)
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Ray Dillinger wrote:
> Consider the following code snippet:
>
> In Common Lisp:
> (defun (forever) (* 2 (forever)))
>
> In Scheme:
> (define (forever) (* 2 (forever)))
>
> In either of those lisps:
> (if (forever) 2 2)
>
>
> In either case it is legal for a compiler to emit code
> that loops forever, blows the stack/heap, or invokes
> an exception handler.
>
> Should it also be legal for a compiler to emit code that
> simply returns 2 (from the if expression), or should the
> programmer be able to _rely_ on a function like forever
> to transfer flow of control to an exception handler?
(defmacro vcond (&rest clauses)
(assert (every #'null (mapcar #'cddr clauses)))
(when clauses
(let ((first (gensym))
(others (gensym))
(current (gensym)))
`(loop with ,first = ,(second (first clauses))
with ,others = (vector ,@(mapcar #'second (rest clauses)))
for ,current across ,others
unless (eql ,first ,current)
return (cond
(,(first (first clauses)) ,first)
,@(loop for (pred) in (rest clauses)
for index from 0
collect `(,pred (svref ,others ,index))))
finally (return ,first)))))
(defmacro vif (pred then else)
`(vcond (,pred ,then) (t ,else)))
(vif (forever) 2 2) => 2
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
* Ray Dillinger<·························@news.sonic.net> :
Wrote on Fri, 21 Dec 2007 18:12:47 -0800:
| Consider the following code snippet:
| In Scheme:
| (define (forever) (* 2 (forever)))
| (if (forever) 2 2)
|
| In either case it is legal for a compiler to emit code
| that loops forever, blows the stack/heap, or invokes
| an exception handler.
Not only is it legal, it is the only interpretation possible for the
given source code --- The source code is explicitly coding an infinite
loop.
| Should it also be legal for a compiler to emit code that
| simply returns 2 (from the if expression), or should the
| programmer be able to _rely_ on a function like forever
| to transfer flow of control to an exception handler?
For the example you have given, in an `eager-evaluation' language, the
answer is clearly the second alternative you outlined: The if statement
WILL HAVE to evaluate the condition before returing the consequent or
alternative. So the program WILL HAVE to loop forever, and since it cant
do that raise an exception.
What is the actual context in which you are framing this question?
Perhaps you are trying to determine the behaviour of a compiler you are
writing when you have statically determined some behaviour?
I think there is a variant of the halting problem involved. If you are
taking an opinion poll, my vote is that both behaviours should be legal:
depending on how much a compiler can infer. Since in general, the
problem is that of determining whether a subroutine call will terminate
normally, or run out of resources, it will not be possible to do the
analysis for all cases and you cannot get an Yes/No answer.
Consider For example CMUCL, which lets this through in compiled code:
* (funcall (compile nil (lambda () (if (progn (/ 1 0) t) 1 2))))
But throws an error in interpreted code.
* (funcall (lambda () (if (progn (/ 1 0) t) 1 2)))
Both behaviours should be legal.
--
Madhu