Compatibility questions
Jay Osako
months earlier in DrScheme, and decided to try and vett it on some
other interpreters (Bigloo, MIT, SCM, and Petite Chez) to see how
portable it was. As it happens, there were only a handful of issues -
SCM did not implement (port?), Chez Scheme did not parse escaped
newlines in strings ("\n") but *did* work with a #\newline character
made into a string using (make-string), etc. The real surprise was
that the following function,
;; (read-dump-line port integer) => list
;; read in a line of data
;;
;; Side Effects: reads data from port src
;; Requirements: none
(define (read-dump-line src width)
(let read-data ((count width))
(if (or (>= 0 count)
(eof-object? (peek-char src))) ; check to see if its EOF
'()
(cons (read-char src) (read-data (- count 1))))))
when run under MIT Shceme would return the list of characters in
*reverse* order from how they were in the file.
All other interpreters ran the code as I expected it would. I cannot
see any logical error, so I can only wonder why the MIT interpreter
would give such an odd result. While reversing the list to the correct
order would be trivial (I could even set it up so that on the first
function call, it would detect which interpreter it was running under,
generate the appropriate subfunction, and apply it on each subsequent
call), I was less concerned with running the program itself and more
with why there would be this discrepancy. Does anyone have any ideas?
I was also curious if anyone could give any advice as to improving the
program at hand. The work I was doing was simply an exercise program
optimization - I was using the program as a demonstration, and I'd
wanted it to be reasonably efficient as well as reasonably clear - and
I was hoping for some input by a few more experienced Schemers. The
code for the program (a simple hex dump utility) can be found at
http://www.mega-tokyo.com/forum/attachments/uploaded_files/dump-file.scm.txt
Thank you for considering these questions.
--
Jay Osako aka Schol-R-LEA;2
If the phone rings today, water it!
Lauri Alanko
> (define (read-dump-line src width)
> (let read-data ((count width))
> (if (or (>= 0 count)
> (eof-object? (peek-char src))) ; check to see if its EOF
> '()
> (cons (read-char src) (read-data (- count 1))))))
At the last line the semantics of your program depend on the evaluation
order of the arguments to cons. As you can see in
http://schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-7.html#%_sec_4.1.3
the evaluation order is undefined. You'd better change your program so
that the desired evaluation order is explicit.
Lauri Alanko
l...@iki.fi
Matthias Felleisen
> I was recently working on a small program which I had written a few
> months earlier in DrScheme, and decided to try and vett it on some
> other interpreters (Bigloo, MIT, SCM, and Petite Chez) to see how
> portable it was. As it happens, there were only a handful of issues -
> SCM did not implement (port?), Chez Scheme did not parse escaped
> newlines in strings ("\n") but *did* work with a #\newline character
> made into a string using (make-string), etc. The real surprise was
> that the following function,
>
> ;; (read-dump-line port integer) => list
> ;; read in a line of data
> ;;
> ;; Side Effects: reads data from port src
> ;; Requirements: none
> (define (read-dump-line src width)
> (let read-data ((count width))
> (if (or (>= 0 count)
> (eof-object? (peek-char src))) ; check to see if its EOF
> '()
> (cons (read-char src) (read-data (- count 1))))))
Try
(define (read-dump-line src width)
(let read-date ((count width))
(let ([next (read-char)])
(if (eof-object? next)
'()
(cons next (read-data (- count 1)))))))
1. A program with peek-char is almost always broken. The other MF.
2. You want to perform effect-full actions only once via let. (A
lesson from monads.)
3. The Scheme Report imposes an undecidable correctness criteria on
programs -- that they don't depend on the order of evaluation -- without
(naturally) asking implementations to check it. Go figure; and that language
supposedly has a semantics.
-- Matthias
Matthias Blume
> 3. The Scheme Report imposes an undecidable correctness criteria on
> programs -- that they don't depend on the order of evaluation -- without
> (naturally) asking implementations to check it. Go figure; and that language
> supposedly has a semantics.
Right on. This is, IMO, the bigger problem with Scheme's "fully
formalized semantics". Leaving evaluation order unspecified is a big
mistake (buys nearly nothing -- regardless of what some people will
tell you -- and comes with correctness headaches such as those
demonstrated by this example), and the formal semantics section in
RnRS does not even handle it properly.
Everyone would be better off fixing the order of evaluation:
- The programmer does not have to make sure that her program works
under circumstances that she cannot test today but which might be
a fact tomorrow (when the new compiler comes out).
- The writer of the formal semantics section of RnRS does not have
to do a hack job ("permute"/"unpermute").
- The compiler writer does not need to wonder if there is a way of
squeezing out another ounce of performance by "cleverly" fiddling
with evaluation order. (Been there, done that. (*))
(*) Of course, a good compiler will still try to rearrange parts of
the computation. But the rules are much simpler if they uniformely
say: "Don't rearrange if you cannot prove that doing so does not alter
the observable outcome of the overall computation."
(the other) Matthias
Abdulaziz Ghuloum
> Matthias Felleisen <matt...@ccs.neu.edu> writes:
>
>
>>3. The Scheme Report imposes an undecidable correctness criteria on
>>programs -- that they don't depend on the order of evaluation -- without
>>(naturally) asking implementations to check it. Go figure; and that language
>>supposedly has a semantics.
>
>
> Right on. This is, IMO, the bigger problem with Scheme's "fully
> formalized semantics". Leaving evaluation order unspecified is a big
> mistake (buys nearly nothing -- regardless of what some people will
> tell you -- and comes with correctness headaches such as those
> demonstrated by this example), and the formal semantics section in
> RnRS does not even handle it properly.
>
> Everyone would be better off fixing the order of evaluation:
>
> - The programmer does not have to make sure that her program works
> under circumstances that she cannot test today but which might be
> a fact tomorrow (when the new compiler comes out).
> - The writer of the formal semantics section of RnRS does not have
> to do a hack job ("permute"/"unpermute").
> - The compiler writer does not need to wonder if there is a way of
> squeezing out another ounce of performance by "cleverly" fiddling
> with evaluation order. (Been there, done that. (*))
You are suggesting a fixed evaluation order (probably left to right).
The implications of that are:
1. Either `let' should have the same semantics as `let*'.
2. Or `let' is not semantically equivalent to `left left lambda'.
3. Or some other option that I'm not aware of.
Would you please elaborate on your opinion a little more.
Aziz,,,
Allosemantic Petrofsky
> You are suggesting a fixed evaluation order (probably left to right).
> The implications of that are:
> 1. Either `let' should have the same semantics as `let*'.
> 2. Or `let' is not semantically equivalent to `left left lambda'.
> 3. Or some other option that I'm not aware of.
(let ((- +) (n (- 1))) n) => -1
(let* ((- +) (n (- 1))) n) => 1
Marcin 'Qrczak' Kowalczyk
> You are suggesting a fixed evaluation order (probably left to right).
> The implications of that are:
> 1. Either `let' should have the same semantics as `let*'.
> 2. Or `let' is not semantically equivalent to `left left lambda'.
> 3. Or some other option that I'm not aware of.
No, fixing evaluation order doesn't imply changing scope rules.
Let would be precisely equivalent to applied lambda.
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Matthias Blume
Not at all. Let should evaluate left-to-right, but the scoping is
still that of let -- which is different from let*.
> 2. Or `let' is not semantically equivalent to `left left lambda'.
> 3. Or some other option that I'm not aware of.
>
> Would you please elaborate on your opinion a little more.
Notice that fixing the evaluation order is completely consistent with
today's Scheme definition. Doing so just makes life easier for
everyone.
Joe Marshall
> 3. The Scheme Report imposes an undecidable correctness criteria on
> programs -- that they don't depend on the order of evaluation -- without
> (naturally) asking implementations to check it. Go figure; and that language
> supposedly has a semantics.
The issue is that MIT Scheme does right to left by default in the
interpreter where other Schemes do left to right. MIT Scheme and Chez
Scheme also re-order the arguments when compiling (for optimization).
MIT strongly disagreed with l2r, and the ones doing r2l strongly
disagreed with MIT and no one wanted to force the issue.
There is another issue, though. In the presence of macros the order
of evaluation may no longer be left to right (in the untransformed
source code). Should only function calls have the order enforced?
(By the way, how about removing that correctness criteria from the
report...)
Scott G. Miller
> Matthias Felleisen <matt...@ccs.neu.edu> writes:
>
>
>>3. The Scheme Report imposes an undecidable correctness criteria on
>>programs -- that they don't depend on the order of evaluation -- without
>>(naturally) asking implementations to check it. Go figure; and that language
>>supposedly has a semantics.
>
>
> The issue is that MIT Scheme does right to left by default in the
> interpreter where other Schemes do left to right. MIT Scheme and Chez
> Scheme also re-order the arguments when compiling (for optimization).
>
> MIT strongly disagreed with l2r, and the ones doing r2l strongly
> disagreed with MIT and no one wanted to force the issue.
>
continuation protection algorithm relies currently on a right to left
order. Other systems take advantage of an unspecified order for other
optimizations.
Scott
Marcin 'Qrczak' Kowalczyk
> There is another issue, though. In the presence of macros the order
> of evaluation may no longer be left to right (in the untransformed
> source code). Should only function calls have the order enforced?
Yes, it's obvious for me than a macro can make the evaluation order
different.
Matthias Blume
> Other systems take advantage of an unspecified order for other
> optimizations.
How much do they actually buy? I can always reorder by hand if it is
so important to the efficiency of my code.
I say it again: Leaving the order unspecified, for whatever reason, is
a huge mistake.
Matthias
Joe Marshall
> "Scott G. Miller" <scgm...@freenetproject.org> writes:
>
>> Other systems take advantage of an unspecified order for other
>> optimizations.
>
> How much do they actually buy?
According to Will Clinger:
``As compiled by Twobit for the SPARC, this optimization reduces the
code size for Larceny v0.24 from 489456 to 452872 bytes, a savings
of 7.5%.''
See:
http://compilers.iecc.com/comparch/article/95-08-080
> I say it again: Leaving the order unspecified, for whatever reason, is
> a huge mistake.
Probably (I haven't heard a truly persuasive argument, yet).
However, *relying* on the order of evaluation is also a huge mistake,
and if your code doesn't rely on the order of evaluation, then it
doesn't matter that it is unspecified.
If you write code that does not depend on order of evaluation, then
the order of evaluation makes no difference. Logically, therefore, if
the order of evaluation makes a difference, it must be that you write
code that depends on it, right?
Thant Tessman
[...]
> If you write code that does not depend on order of evaluation, then
> the order of evaluation makes no difference. Logically, therefore, if
> the order of evaluation makes a difference, it must be that you write
> code that depends on it, right?
Patient: Doctor, doctor! It hurts when I do this.
Doctor: Well then don't do that no more.
Not a very satisfying argument.
-thant
--
Reports that say that something hasn't happened are always interesting
to me,
because as we know, there are known knowns; there are things we know we
know.
We also know there are known unknowns; that is to say we know there are
some
things we do not know. But there are also unknown unknowns - the ones we
don't know we don't know. -- Secretary of Defense Donald Rumsfeld
Matthias Blume
> > How much do they actually buy?
>
> According to Will Clinger:
>
> ``As compiled by Twobit for the SPARC, this optimization reduces the
> code size for Larceny v0.24 from 489456 to 452872 bytes, a savings
> of 7.5%.''
>
> See:
> http://compilers.iecc.com/comparch/article/95-08-080
I would like to see a more detailed account of this, in particular,
what "this optimization" refers to, precisely, i.e., what exactly was
being measured. In particular, when turning off "this optimization"
were any other things turned off (or on) as well?
(In any case, if the savings are significant enough to want them, then
one can always recoup them by reordering by hand.)
> However, *relying* on the order of evaluation is also a huge mistake,
Well, I would not call it a mistake if the language mandates some
fixed order. But granted, I would always call it bad style.
[In some idiomatic cases it might not even be bad style. For example,
the "before" operation in SML can be defined as
infix before
fun x before y = x
thereby relying on evaluation order.]
> and if your code doesn't rely on the order of evaluation, then it
> doesn't matter that it is unspecified.
The trouble is that it is hard to know that it does not rely on
evaluation order -- and even testing won't find out unless you have a
test compiler generates all possible permutations.
> If you write code that does not depend on order of evaluation, then
> the order of evaluation makes no difference. Logically, therefore, if
> the order of evaluation makes a difference, it must be that you write
> code that depends on it, right?
Yes, all languages with side effects have the inherent problem that
order of evaluation matters. Counting non-termination as a side
effect, there are very few languages that are truly side-effect free.
The above line of reasoning can be used to "defend" all kinds of
language misfeatures: If you carefully program around them they won't
matter, therefore, if they do matter, you didn't carefully program
around them. This sort of argument is especially harmful if knowing
whether one has actually "carefully programmed around them" is very
hard.
Matthias
Shriram Krishnamurthi
> However, *relying* on the order of evaluation is also a huge mistake,
> and if your code doesn't rely on the order of evaluation, then it
> doesn't matter that it is unspecified.
>
> If you write code that does not depend on order of evaluation, then
> the order of evaluation makes no difference. Logically, therefore, if
> the order of evaluation makes a difference, it must be that you write
> code that depends on it, right?
I feel like I'm falling for a troll even as I write this, but....
The problem with your comment is that it assumes programmers are aware
of when they are relying on a particular order. Often they aren't
(especially if they call into a third-party library that uses effects
such as mutation or continuations). Unless they test on multiple
Scheme systems with different orders of evaluation, and construct the
right test cases, they'll never find out, either.
Shriram
Matthias Felleisen
about compilers. I am *not* a compiler expert. When I need to know something
about compilers I ask people like Kent, Will, and for low level things, Keith
Cooper. Kent and Will have repeatedly told me that a free order of evaluation
for function applications buys some performance and possibly space. I actually
trust their judgment.
But ... for the sake of a language standard that avoids bad and difficult to
debug surprises when you move from one dialect to another, I am willing to
sacrifice performance for well-definedness.
I also believe that well-definedness for the entire language would benefit the
community as a whole. That includes academic researchers (Will), commercial
outfits (scheme.com), and people in between (PLT). For researchers, it is
important that you can point to a standard document that stands out from the
riff-raff (Java and C#). Scheme has lost the egde there. SML and Haskell have
set a new standard to which we need to live up yet. A well-defined standard is
also the basis for good scripting languages. If mzscheme is your scripting tool
of choice today, you need to keep in mind that PLT may move on to ML tomorrow
and you will need to use Phantom Scheme the day after. Only a well-defined
standard helps here.
Let's face it: if you are that dependent on performance, use high performance
fortran. Develop in Scheme. Translate. But don't give up mathematical
foundations for Scheme. You wouldn't do that for your mathematics or product
either.
-- Matthias
Scott G. Miller
> My criticism of Scheme's evaluation order is *not* based on any deep knowledge
> about compilers. I am *not* a compiler expert. When I need to know something
> about compilers I ask people like Kent, Will, and for low level things, Keith
> Cooper. Kent and Will have repeatedly told me that a free order of evaluation
> for function applications buys some performance and possibly space. I actually
> trust their judgment.
>
> But ... for the sake of a language standard that avoids bad and difficult to
> debug surprises when you move from one dialect to another, I am willing to
> sacrifice performance for well-definedness.
>
Perhaps, but I agree with Joe that those surprises are really exposing
yet undiscovered bugs in a program. One of Scheme's great advantages in
my opinion is the flexibility it give implementations by leaving certain
things unspecified. Some of these make portable programming difficult,
but I would argue that the order of evaluation is so low level and
transparent to 90% of programs that the gain in compiler flexibility
outweighs the ambiguity to programs.
Besides, we have constructs for fixing an order of evaluation for
expressions which have side effects. This is no worse than say the
undefined behavior of multithreaded programs when the programmer doesn't
use a mutex construct to protect a critical region.
Scott
Lauri Alanko
> One of Scheme's great advantages in my opinion is the flexibility it
> give implementations by leaving certain things unspecified.
Golly, what an advanced language C must then be.
Lauri Alanko
l...@iki.fi
Matthias Radestock
> This is no worse than say the
> undefined behavior of multithreaded programs when the programmer doesn't
> use a mutex construct to protect a critical region.
That's a great analogy except it illustrates the exact opposite of what
you intended. Multithreaded programs are incredibly hard to get right
and a nightmare to debug. Fortunately they are also rare, in no small
part precisely *because* they are so difficult to write. By contrast,
nearly everything in Scheme involves function application. Eliminating
any behaviour-altering non-determinism in such a crucial area is
definitely a worthwhile goal.
Matthias.
Matthias Blume
> Matthias Felleisen wrote:
>
> Perhaps, but I agree with Joe that those surprises are really exposing
> yet undiscovered bugs in a program.
Wrong. The particular problem here is that the problem won't get
exposed anytime soon (unless you are doing your testing with N
different implementations -- and there is still no guarantee that it
won't break on the N+1st, or even on the 1st when you upgrade to the
latest version).
The worst kind of bug is the one you get away with for a long time.
> One of Scheme's great advantages in my opinion is the flexibility it
> give implementations by leaving certain things unspecified.
I found this particular "flexibility" not so terribly useful from an
implementor's point of view, and from a language user's point of view
it is simply terrible.
> Some of these make portable programming
> difficult, but I would argue that the order of evaluation is so low
> level and transparent to 90% of programs that the gain in compiler
> flexibility outweighs the ambiguity to programs.
Again, there is hardly any useful gain (not in my experience, and all
positive reports that I have seen leave me very unconvinced), while
the expense is huge.
> Besides, we have constructs for fixing an order of evaluation for
> expressions which have side effects.
Yes, and those constructs can be used for fixing the order differently
than what is the (fixed) default order when performance really
matters.
> This is no worse than say the
> undefined behavior of multithreaded programs when the programmer
> doesn't use a mutex construct to protect a critical region.
Now you want to throw all the complexity of concurrent programming
even at simple sequential programs?!?
Matthias
Shriram Krishnamurthi
> By contrast, nearly everything in Scheme involves function
> application. Eliminating any behaviour-altering non-determinism in
> such a crucial area is definitely a worthwhile goal.
You mean "indeterminacy", not "non-determinism".
(First thread on c.l.s to feature all three Matthias's? How about in
a single day?)
Shriram
Shriram Krishnamurthi
> Perhaps, but I agree with Joe that those surprises are really exposing
> yet undiscovered bugs in a program.
The problem is that they are *yet* *undiscovered*. We're not talking
about programmers who knowingly, willfully insert bugs. We're talking
about protecting the innocent.
Shriram
Matthias Radestock
> Matthias Radestock <matt...@sorted.org> writes:
>
>
>>By contrast, nearly everything in Scheme involves function
>>application. Eliminating any behaviour-altering non-determinism in
>>such a crucial area is definitely a worthwhile goal.
>
>
> You mean "indeterminacy", not "non-determinism".
indeterminacy
n : the quality of being vague and poorly defined
nondeterminism
<algorithm> A property of a computation which may have more
than one result.
I definitely meant the latter. RnRS is not at all vague about evaluation
order - it defines the rules very precisely. The problem is that the
rules permit nondeterminism - calling a procedure twice with exactly the
same inputs (i.e. args, external inputs, state of heap etc) can produce
different results.
Matthias.
David Rush
And it is. For low-level programming there hasn't really been anything
much better. Even the Fox project, which is impressive, hasn't produced
a competing OS to Linux. This surely has to say something about the
efficacy of the ideas embodied in C.
Mind you, C has it's problems, but my favorite thought experiments these
days involve recasting C in s-expressions with first-class functions, full
TCO, and automatic memory management. Oh...that sounds a lot like Scheme
with machine-oriented types...hmmm
david rush
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
David Rush
wrote:
> "Scott G. Miller" <scgm...@freenetproject.org> writes:
>
>> Perhaps, but I agree with Joe that those surprises are really exposing
>> yet undiscovered bugs in a program.
>
> The problem is that they are *yet* *undiscovered*. We're not talking
> about programmers who knowingly, willfully insert bugs.
STR: I'm going to program me a BMW!
> We're talking about protecting the innocent.
STR: Everyone's guilty of something.
Joe Marshall
> Joe Marshall <j...@ccs.neu.edu> writes:
>
>> However, *relying* on the order of evaluation is also a huge mistake,
>> and if your code doesn't rely on the order of evaluation, then it
>> doesn't matter that it is unspecified.
>>
>> If you write code that does not depend on order of evaluation, then
>> the order of evaluation makes no difference. Logically, therefore, if
>> the order of evaluation makes a difference, it must be that you write
>> code that depends on it, right?
>
> I feel like I'm falling for a troll even as I write this, but....
I need to work on being more subtle. You weren't supposed to notice.
> The problem with your comment is that it assumes programmers are aware
> of when they are relying on a particular order.
Yes, that is a problem. One (facetious) suggestion was to vary the
order on each and every call.
> Often they aren't (especially if they call into a third-party
> library that uses effects such as mutation or continuations).
> Unless they test on multiple Scheme systems with different orders of
> evaluation, and construct the right test cases, they'll never find
> out, either.
But if all Scheme systems have the same order of evaluation, they'll
never find out. Isn't this a case of masking the problem rather than
solving it?
Matthias Blume
> > Often they aren't (especially if they call into a third-party
> > library that uses effects such as mutation or continuations).
> > Unless they test on multiple Scheme systems with different orders of
> > evaluation, and construct the right test cases, they'll never find
> > out, either.
>
> But if all Scheme systems have the same order of evaluation, they'll
> never find out. Isn't this a case of masking the problem rather than
> solving it?
No. It is turning the problem into a non-problem because relying on
evaluation order is then no longer a bug but merely poor style.
Matthias
Joe Marshall
> Joe Marshall <j...@ccs.neu.edu> writes:
>
>> If you write code that does not depend on order of evaluation, then
>> the order of evaluation makes no difference. Logically, therefore, if
>> the order of evaluation makes a difference, it must be that you write
>> code that depends on it, right?
>
> The above line of reasoning can be used to "defend" all kinds of
> language misfeatures: If you carefully program around them they won't
> matter, therefore, if they do matter, you didn't carefully program
> around them.
`Programming around them' implies that there is a desire to do things
one way and that is being prohibited by the language.
Contrast Interlisp, which does not do arity checking (arguments
default to NIL if not supplied, extra arguments are silently ignored),
with MacLisp, which does. When you write code in MacLisp, you must
ensure that every call site matches the arity of the callee. So you
have to carefully program around the arity checking so that your code
does not depend on argument defaulting or discarding.
The reasoning is sound, it is the premise that is at fault.
> This sort of argument is especially harmful if knowing whether one
> has actually "carefully programmed around them" is very hard.
And this is the fault in the premise.
Note that requiring a particular order of evaluation makes it *harder*
to find places where you depend on it.
I'm really not invested leaving it unspecified. I don't much care.
But the only valid reason I've seen for specifying it is that it will
cut the number of bugs reported that are caused by dependence upon a
particular order. (Of course, it will make it much harder to explain
*why* one shouldn't depend on the order of evaluation.)
Neither C nor C++ define a particular order of evaluation and they
seem to be popular. I even hear that C can be useful.
--
~jrm
Bradd W. Szonye
>> But if all Scheme systems have the same order of evaluation, they'll
>> never find out. Isn't this a case of masking the problem rather than
>> solving it?
Matthias Blume <fi...@my.address.elsewhere> wrote:
> No. It is turning the problem into a non-problem because relying on
> evaluation order is then no longer a bug but merely poor style.
And I think it's a mistake to "bless" a poor style by making it
"well-defined but discouraged," because sloppy programmers will ignore
the "but discouraged" part, instead claiming that the well-definedness
justifies their style. If anything, I'd rather go in the other
direction, requiring a diagnostic for code that breaks the constraint --
except, of course, the constraint is non-decidable in this case.
Furthermore, an explicit evaluation order removes some expressiveness
from a language. In general, only some steps of a procedure need to
happen in a particular order. Good designers know this and make it
explicit in their designs. It's not just about optimization either; it
also affects maintainability. It's much harder to maintain code when you
don't know which sequences are semantically important and which are just
an artifact of coding.
In other words, explicit sequencing is important any time there's *any*
reason to reorganize the code, whether it's a machine or a human doing
it. Hand-tuning, compiler optimization, parallelism (including the
automatic kind now found in many CPUs with multiple logic units),
maintenance -- all of these tasks need to know when the order is
important and when it isn't.
Overspecifying the order of evaluation takes away expressiveness because
it makes the ordering implicit rather than explicit. It's one more place
where a programmer needs to rely on comments rather than the actual
procedure to explain what's going on. Personally, I'd rather see *more*
constructs that allow a programmer to say "the order doesn't matter,"
rather than fewer of them. So I'm strongly opposed to changing order of
evaluation from "unspecified" to "implicitly specified."
--
Bradd W. Szonye
http://www.szonye.com/bradd
Lauri Alanko
> And I think it's a mistake to "bless" a poor style by making it
> "well-defined but discouraged," because sloppy programmers will ignore
> the "but discouraged" part,
How's that worse than having sloppy programmers ignore the current
"undefined" part?
Lauri Alanko
l...@iki.fi
Matthias Blume
> > Joe Marshall <j...@ccs.neu.edu> writes:
> >> But if all Scheme systems have the same order of evaluation, they'll
> >> never find out. Isn't this a case of masking the problem rather than
> >> solving it?
>
> Matthias Blume <fi...@my.address.elsewhere> wrote:
> > No. It is turning the problem into a non-problem because relying on
> > evaluation order is then no longer a bug but merely poor style.
>
> And I think it's a mistake to "bless" a poor style by making it
> "well-defined but discouraged," because sloppy programmers will ignore
> the "but discouraged" part, instead claiming that the well-definedness
> justifies their style.
Well, that's fine. They are not committing a factual error, they are
just writing poor code. "Poor" is, of course, in the eye of the
beholder, whereas "factually wrong" is not.
> If anything, I'd rather go in the other
> direction, requiring a diagnostic for code that breaks the constraint --
> except, of course, the constraint is non-decidable in this case.
If it were decidable, and if a diagnostic were required, then I would
have no problem with it. Precisely because it is NOT decidable I am
against leaving the order unspecified.
> It's much harder to maintain code when you don't know which
> sequences are semantically important and which are just an artifact
> of coding.
... and which non-sequences are outright bugs that just haven't been
discovered yet.
> Overspecifying the order of evaluation takes away expressiveness because
> it makes the ordering implicit rather than explicit. It's one more place
> where a programmer needs to rely on comments rather than the actual
> procedure to explain what's going on. Personally, I'd rather see *more*
> constructs that allow a programmer to say "the order doesn't matter,"
Well, if you really want that, there are plenty of languages that let
you *explicitly* say "do these things in any order you like". Usually
such features make it much harder to get one's code correct. For that
reason, making this part of a feature as ubiquitous as procedure calls
is a big mistake. All the arguments about "expressiveness" are red
herrings.
People in this newsgroup often like to waffle about the "freedom" that
is granted by a language. Making the evaluation order unspecified
*takes away* such freedom. Proof: Every program that is a valid
program under unspecified order is also a valid program under fixed
evaluation order. But not vice versa. Therefore, there are fewer
correct programs under "unspecified" order. Unlike with type systems,
though, whether or not a program is invalid because of reliance on
evaluation order is not decidable (either at compile or at runtime).
I really don't see anything in your argument that is the least bit
convincing. Unspecified evaluation order is bad for everyone
involved. There is no upside to it.
> rather than fewer of them. So I'm strongly opposed to changing order of
> evaluation from "unspecified" to "implicitly specified."
We'll have to agree to disagree then.
Matthias (one of the three)
Bradd W. Szonye
>> And I think it's a mistake to "bless" a poor style by making it
>> "well-defined but discouraged," because sloppy programmers will
>> ignore the "but discouraged" part,
Lauri Alanko <l...@iki.fi> wrote:
> How's that worse than having sloppy programmers ignore the current
> "undefined" part?
The sloppy programmers part doesn't get any worse, but it doesn't get
any better either. Meanwhile, optimization, parallelization, and
maintenance become more difficult. There's no gain and a significant
loss, therefore, it's a bad idea.
Matthias Blume
> Meanwhile, optimization, parallelization, and
> maintenance become more difficult.
Nonsense. Optimization does not get any harder, the thing has
absolutely nothing to do with parallelization (read what the
definition actually says!), and maintenance becomes *easier*.
> There's no gain and a significant
> loss, therefore, it's a bad idea.
You have it upside down. There is no loss and a significant gain,
therefore it is an excellent idea.
Bradd W. Szonye
>>> No. It is turning the problem into a non-problem because relying on
>>> evaluation order is then no longer a bug but merely poor style.
> "Bradd W. Szonye" <bradd...@szonye.com> writes:
>> And I think it's a mistake to "bless" a poor style by making it
>> "well-defined but discouraged," because sloppy programmers will
>> ignore the "but discouraged" part, instead claiming that the
>> well-definedness justifies their style.
> Well, that's fine. They are not committing a factual error, they are
> just writing poor code. "Poor" is, of course, in the eye of the
> beholder, whereas "factually wrong" is not.
Why bless poor code? It encourages the errors.
>> Overspecifying the order of evaluation takes away expressiveness
>> because it makes the ordering implicit rather than explicit. It's one
>> more place where a programmer needs to rely on comments rather than
>> the actual procedure to explain what's going on. Personally, I'd
>> rather see *more* constructs that allow a programmer to say "the
>> order doesn't matter,"
> Well, if you really want that, there are plenty of languages that let
> you *explicitly* say "do these things in any order you like". Usually
> such features make it much harder to get one's code correct.
Only if you're sloppy about design (i.e., you haven't carefully
considered which sequences are important and which are coincidental).
Generally, I'm all for protecting programmers from making careless
mistakes, but not when it actually obscures the design.
> For that reason, making this part of a feature as ubiquitous as
> procedure calls is a big mistake. All the arguments about
> "expressiveness" are red herrings.
No, the big mistake is conflating the concepts of "argument list" and
"sequence of operations." That's a fundamental design error, not just a
bit of sloppy programming, and a programming language should *not*
encourage the error.
> People in this newsgroup often like to waffle about the "freedom" that
> is granted by a language. Making the evaluation order unspecified
> *takes away* such freedom.
Not when there's a trivial, alternate way that lets you write it.
(let* ((arg1 ...) (arg2 ...)) (f arg1 arg2))
If you use that pattern a lot, you can even write a macro to simplify
the syntax, e.g. (sequential-args f arg1 arg2). But that's a one-way
trip. Once you require sequential evaluation for all procedure calls,
you remove all possibility of automatic optimization. Only hand-tuning
is possible then, and I think we all know how error-prone that is.
> Proof: Every program that is a valid program under unspecified order
> is also a valid program under fixed evaluation order. But not vice
> versa. Therefore, there are fewer correct programs under
> "unspecified" order.
Refutation: Every program that is not valid under unspecified order has
a trivial transformation that makes it valid (and that makes the
ordering *explicit*, which is an aid to maintainers). Meanwhile, the
fixed order precludes many automatic optimizations, which encourages
premature hand-tuning. (Yes, it actually encourages more than one poor
coding style.)
> Unlike with type systems, though, whether or not a program is invalid
> because of reliance on evaluation order is not decidable (either at
> compile or at runtime).
Which is why it's a bad idea to conflate evaluation order with other
concepts, like argument lists. When order matters, it's not enough to
just throw code at a compiler and hope that it works.
> I really don't see anything in your argument that is the least bit
> convincing. Unspecified evaluation order is bad for everyone
> involved. There is no upside to it.
Allowing automatic optimization and discouraging poor coding styles is
not an upside? Meanwhile, fixed evaluation order has several concrete
drawbacks. It effectively shifts the ambiguity from initial coding to
maintenance. The original developer knows that he can rely on the order
of evaluation, but maintainers can't tell whether they've actually done
so. By conflating the two ideas, you lose information.
I don't know how much maintenance work you've done, but it's a huge part
of the software lifecycle, typically over 50%. By blessing a poor design
and coding style, you make maintenance more difficult and increase the
overall cost of the software. It's a quadruple loss: it encourages
sloppiness, it encourages premature hand-tuning, it precludes
optimization, and it loses information about the program.
Bradd W. Szonye
>> Meanwhile, optimization, parallelization, and
>> maintenance become more difficult.
Matthias Blume <fi...@my.address.elsewhere> wrote:
> Nonsense. Optimization does not get any harder ....
By constraining the order of evaluation, you reduce the set of possible
optimizations. On some architectures (e.g., IA-64), those constraints go
all the way down to the hardware level.
> the thing has absolutely nothing to do with parallelization (read what
> the definition actually says!) ....
"Although the order of evaluation is otherwise unspecified, the effect
of any concurrent evaluation of the operator and operand expressions is
constrained to be consistent with some sequential order of evaluation."
Evaluating arguments in parallel can be consistent with some sequential
order of evaluation. If you tighten the constraints on evaluation order,
however, you reduce the opportunities for parallelization. For example,
consider a call with three arguments. The first and last arguments are
purely functional, but the middle argument is not. With unspecified
order, the system can parallelize evaluation of the purely-functional
arguments. With fixed order, it cannot, because the middle argument
creates a "sequence point" that you cannot cross without breaking
consistency with the abstract model.
This sort of thing is especially important now that "superscalar"
machine architectures are ubiquitous. For example, on an IA-64 system,
unnecessary sequence points have *major* performance implications. Why
introduce unnecessary sequence points just to bless a poor design and
coding style?
> and maintenance becomes *easier*.
No, a few bugs become non-bugs. But overall maintenance becomes more
expensive, because the fixed evaluation order removes information about
the procedure. Specifically, it removes a guarantee that "order doesn't
matter here," and replaces it with "order may or may not be important."
That increases the cost of diagnosis and code rework.
It does eliminate a few situations where a programmer relied on order
where he shouldn't have, but that kind of activity is *much* less common
than code review and diagnosis.
Joan Estes
> [] I am willing to
> sacrifice performance for well-definedness.
>
> I also believe that well-definedness for the entire language would benefit the
> community as a whole.
Does this necessarily require fixed evaluation order? A quick perusal
of the literature shows various candidate techniques for giving a precise,
well-defined semantics to unspecified evaluation order. Powerdomains
come up most often, but there are others.
J.E.
Joe Marshall
You have it sideways: there is insignificant loss and insignificant
gain and therefore an excellent topic for a usenet flamefest.
So....
Left to right, right to left, or something more original?
Is the function position evaluated first or last?
Does this apply to LETREC?
Should library syntax be required to have a particular order?
What about syntax introduced by extensions or SRFI's?
Shriram Krishnamurthi
> indeterminacy
> n : the quality of being vague and poorly defined
>
> nondeterminism
> <algorithm> A property of a computation which may have more
> than one result.
You're way too smart to pull this dumb dictionary trick on me. The
function application has only one result. It may be chosen from a set
of multiple results.
Put otherwise: leaving the order of evaluation undefined does not turn
Scheme into a mini-Prolog.
Shriram
Matthias Blume
> "Although the order of evaluation is otherwise unspecified, the effect
> of any concurrent evaluation of the operator and operand expressions is
> constrained to be consistent with some sequential order of evaluation."
>
> Evaluating arguments in parallel can be consistent with some sequential
> order of evaluation.
But only if you know what side-effects occur -- in which case you can
do that optimization even in the case of mandatory fixed order.
> If you tighten the constraints on evaluation order,
> however, you reduce the opportunities for parallelization. For example,
> consider a call with three arguments. The first and last arguments are
> purely functional, but the middle argument is not. With unspecified
> order, the system can parallelize evaluation of the purely-functional
> arguments. With fixed order, it cannot, because the middle argument
> creates a "sequence point" that you cannot cross without breaking
> consistency with the abstract model.
False. If the compiler actually knows that the first and third
arguments are purely functional, then it can ignore the conceptional
sequence point and go ahead with parallelization. If it does not know
it, then it cannot parallelize regardless of whether or not the order
is fixed by the language definition.
> > and maintenance becomes *easier*.
>
> No, a few bugs become non-bugs. But overall maintenance becomes more
> expensive, because the fixed evaluation order removes information about
> the procedure.
> Specifically, it removes a guarantee that "order doesn't
> matter here,"
There is no such "guarantee" unless the compiler proves it. If the
compiler can prove it, it can rearrange anyway because the proof means
that nobody will be able to tell the differenc.
Matthias
Matthias Blume
> You have it sideways: there is insignificant loss and insignificant
> gain and therefore an excellent topic for a usenet flamefest.
Yes, apparently. In any case, to *me* the gain is very significant,
and I speak for myself here.
> So....
> Left to right, right to left, or something more original?
I don't really care, but left-to-right might be favorable under the
principle of least surprise. (But my own VSCM implementation uses
right-to-left, which at the time I found cute. I wouldn't do it that
way anymore.)
> Is the function position evaluated first or last?
It depends. For example, under l2r I'd say first, under r2l: last.
> Does this apply to LETREC?
Yes.
> Should library syntax be required to have a particular order?
Yes. That should be part of the library spec. (As a general
principle, I don't like macros very much, though.)
> What about syntax introduced by extensions or SRFI's?
Specified by the spec of the extension or the SRFI.
Ray Dillinger
Bradd W. Szonye wrote:
> > If you tighten the constraints on evaluation order,
> > however, you reduce the opportunities for parallelization. For example,
> > consider a call with three arguments. The first and last arguments are
> > purely functional, but the middle argument is not. With unspecified
> > order, the system can parallelize evaluation of the purely-functional
> > arguments. With fixed order, it cannot, because the middle argument
> > creates a "sequence point" that you cannot cross without breaking
> > consistency with the abstract model.
>
> False. If the compiler actually knows that the first and third
> arguments are purely functional, then it can ignore the conceptional
> sequence point and go ahead with parallelization. If it does not know
> it, then it cannot parallelize regardless of whether or not the order
> is fixed by the language definition.
You are right that, with pure functional arguments it doesn't
matter and the compiler can resequence them anyway if it proves
they are pure functional.
But the definition of pure functional has two parts; a pure
functional expression is non-side effecting and it is not
affected by any side effects. Consider instead the case of
three non-side effecting expressions. Even if they aren't
pure functional (ie, they can be affected by side effects)
the compiler can schedule them arbitrarily because it knows
that none of them will affect the outcome of any of the others.
But if you insert a side-effecting expression as the second
argument, and the compiler is unable to prove that its side
effects don't affect the other two functions, then it
introduces a sequence point that dictates the evaluation
order of all three expressions.
This was probably the situation Bradd was thinking of.
Bear
Shriram Krishnamurthi
> Left to right, right to left, or something more original?
Since the primes are the building blocks of the natural numbers, do
the primes in order first, then the others, also in order.
A really clever program could then use the execution time as a
primality test.
Since 1 is neither prime nor non-prime, the order in which the first
argument is evaluated is left undefined. <-;
Okay, I'll get back to work now.
Shriram
Joe Marshall
> Joe Marshall <j...@ccs.neu.edu> writes:
>
>> Left to right, right to left, or something more original?
>
> Since the primes are the building blocks of the natural numbers, do
> the primes in order first, then the others, also in order.
Ok, but what do you mean by `in order'?
> A really clever program could then use the execution time as a
> primality test.
>
> Since 1 is neither prime nor non-prime, the order in which the first
> argument is evaluated is left undefined. <-;
Relative to the function itself?
Bradd W. Szonye
>> "Although the order of evaluation is otherwise unspecified, the
>> effect of any concurrent evaluation of the operator and operand
>> expressions is constrained to be consistent with some sequential
>> order of evaluation."
>>
>> Evaluating arguments in parallel can be consistent with some
>> sequential order of evaluation.
Matthias Blume <fi...@my.address.elsewhere> wrote:
> But only if you know what side-effects occur -- in which case you can
> do that optimization even in the case of mandatory fixed order.
The former is true, but the latter is false.
>> If you tighten the constraints on evaluation order, however, you
>> reduce the opportunities for parallelization. For example, consider a
>> call with three arguments. The first and last arguments are purely
>> functional, but the middle argument is not. With unspecified order,
>> the system can parallelize evaluation of the purely-functional
>> arguments. With fixed order, it cannot, because the middle argument
>> creates a "sequence point" that you cannot cross without breaking
>> consistency with the abstract model.
> False. If the compiler actually knows that the first and third
> arguments are purely functional, then it can ignore the conceptional
> sequence point and go ahead with parallelization ....
Not if the the last argument depends on a side-effect of the middle
argument. The compiler has no way to tell whether that will change the
meaning of the evaluation.
You may be thinking that such code would be invalid under the
unspecified-order model, but that isn't generally true, because
side-effects do not always change the abstract meaning of a procedure.
For a concrete example, consider what happens if all three arguments
refer to a splay tree, and the middle argument is a splay-tree find. It
*will* have side-effects, because splay-find mutates the tree. However,
the evaluation order does not change the meaning of the program, because
the mutation is entirely below the abstraction barrier. A C++ programmer
would call it a "mutable const" procedure.
Unfortunately, the compiler has no way of knowing what's "below the
abstraction barrier." All it can see is the mutation. Therefore, it sets
a sequence point, and it can't parallelize the first and last arguments.
Are these situations common? I'm not sure. It can happen any time an
argument has a side-effect below the abstraction barrier.
>> ... overall maintenance becomes more expensive, because the fixed
>> evaluation order removes information about the procedure.
>> Specifically, it removes a guarantee that "order doesn't matter
>> here" ....
> There is no such "guarantee" unless the compiler proves it.
The Scheme standard provides the guarantee. If a programmer ignores it,
that's a bug. Therefore, if a maintainer does notice that a procedure
call depends on a particular order, he immediately knows that it's a
design bug.
I'm curious: What's your main programming experience -- development,
maintenance, teaching, etc.? Your views on this suggest to me that you
work mainly on new development, or maybe with student programmers in a
teaching environment. I work more in coding standards, reviews, best
practices, maintenance, and other QA type stuff. To me, "fixing" the
language instead of the designs seems like exactly the wrong thing to
do.
Bradd W. Szonye
introduces a "sequence point" under a fixed argument evaluation order.
> Matthias Blume wrote:
>> False. If the compiler actually knows that the first and third
>> arguments are purely functional, then it can ignore the conceptional
>> sequence point and go ahead with parallelization. If it does not
>> know it, then it cannot parallelize regardless of whether or not the
>> order is fixed by the language definition.
Ray Dillinger <be...@sonic.net> wrote:
> You are right that, with pure functional arguments it doesn't matter
> and the compiler can resequence them anyway if it proves they are pure
> functional. But the definition of pure functional has two parts; a
> pure functional expression is non-side effecting and it is not
> affected by any side effects.
I was using a less strict definition, functions that produce no side
effects. However, my concrete example also fits your definition:
Consider two functions, SPLAY-FIND and INORDER-TRAVERSE. The first
function has side effects, but they're below the abstraction barrier.
The second function is a purely-functional tree walker. Even though
SPLAY-FIND mutates the tree, they don't affect INORDER-TRAVERSE, because
all the side effects are below the abstraction barrier.
> Consider instead the case of three non-side effecting expressions.
> Even if they aren't pure functional (ie, they can be affected by side
> effects) the compiler can schedule them arbitrarily because it knows
> that none of them will affect the outcome of any of the others.
Right.
> But if you insert a side-effecting expression as the second argument,
> and the compiler is unable to prove that its side effects don't affect
> the other two functions, then it introduces a sequence point that
> dictates the evaluation order of all three expressions.
Right. Part of the problem is that the compiler doesn't know about
abstraction barriers. It has no way to know that SPLAY-FIND doesn't
change the external behavior at all.
Another example that might make this more obvious to Schemers: CONS has
side effects. With a copying collector, it can completely rearrange a
program's memory layout. However, those side effects are behind an
abstraction barrier such that Scheme programs aren't even aware of it.
Consider what happens, though, if you re-implement CONS so that it's
above the compiler's abstraction barrier. Now, almost every function,
even purely-functional ones, appear to have "side effects," thus
introducing more sequence points. While the programmer may realize that
CONS's side effects are irrelevant to the abstract program, the compiler
has no way to determine that.
Or, to put it another way, if you make SPLAY-FIND a primitive, and you
put a hard abstraction barrier over it, the compiler can treat it as
"purely functional." But a compiler can't figure that out for itself. It
must be much more conservative about side-effects and sequence points,
because it doesn't know where the abstraction barriers lie.
Matthias Blume
Sure, there is no use in denying that there are some (rather obscure)
corner cases where the restriction gives some additional power to a
compiler. I suspect, though, that most of the measured benefits are
of the "we trust the programmer" nature.
On average, the gains in efficiency achieved by the restriction on
what the programmer can write reeks of institutionalized premature
micro-optimization. If the presence of B between A and C prevents A
and C from being parallelized, and if this *really* matters, and if
you know that B could be pulled in front, then *just do it*:
(let ((b B)) (f A b C))
instead of writing
(f A B C)
and then relying on questionable, potentially semantics-altering
"optimizations" done by a compiler.
Matthias
Matthias Blume
> Another example that might make this more obvious to Schemers: CONS has
> side effects. With a copying collector, it can completely rearrange a
> program's memory layout. However, those side effects are behind an
> abstraction barrier such that Scheme programs aren't even aware of it.
Scheme's CONS has a side-effect even if you ignore what happens behind
that particular abstraction barrier: it allocates state. (But that's
an entirely separate story.)
Matthias
Bradd W. Szonye
> Sure, there is no use in denying that there are some (rather obscure)
> some additional power to a compiler.
Obscure? I'd expect it to be systematic, actually. At the very least, I
would expect a small but significant difference from switching between
left to right and right to left according to the machine's stack
architecture. (For example, right-to-left seems like it would be more
efficient if the machine uses a downward-growing stack for arguments.)
And I'd also expect the implicit sequence points to make a noticeable
difference on "superscalar" CPUs like the Pentium and Itanium, where the
CPU itself parallelizes instructions. Compilers would need to insert a
lot more NOPs or stop bits to guarantee correct ordering, which
interferes with pipelining and increases code size.
> I suspect, though, that most of the measured benefits are of the "we
> trust the programmer" nature.
Dunno what you mean by this.
> On average, the gains in efficiency achieved by the restriction on
> what the programmer can write reeks of institutionalized premature
> micro-optimization.
How so? If you shave a bit off each procedure call, especially in a
language as procedure-happy as Scheme, you see systematic improvements.
Also, the more you let the compiler optimize code, the less you need
programmers doing expensive hand-tuning. It's the very opposite of
premature micro-optimization.
> If the presence of B between A and C prevents A and C from being
> parallelized, and if this *really* matters, and if you know that B
> could be pulled in front, then *just do it*:
>
> (let ((b B)) (f A b C))
>
> instead of writing
>
> (f A B C)
>
> and then relying on questionable, potentially semantics-altering
> "optimizations" done by a compiler.
But the compiler *doesn't* alter semantics. R5RS doesn't permit it, and
the suggested change wouldn't either. Currently, the semantics are only
"changed" when programmers rely on unspecified behavior, which is a
design/coding error, not a compiler error.
Thant Tessman
> Matthias Blume <fi...@my.address.elsewhere> wrote:
[...]
>>On average, the gains in efficiency achieved by the restriction on
>>what the programmer can write reeks of institutionalized premature
>>micro-optimization.
>
>
> How so? If you shave a bit off each procedure call, especially in a
> language as procedure-happy as Scheme, you see systematic improvements.
> Also, the more you let the compiler optimize code, the less you need
> programmers doing expensive hand-tuning. It's the very opposite of
> premature micro-optimization.
If this kind of optimization is so important, why not go with a static
type system? That's going to buy you much more of an improvement in
performance than allowing for arbitrary evaluation order.
-thant
Matthias Blume
> But the compiler *doesn't* alter semantics. R5RS doesn't permit it, and
> the suggested change wouldn't either. Currently, the semantics are only
> "changed" when programmers rely on unspecified behavior, which is a
> design/coding error, not a compiler error.
That's just sophistry. This thread started with a real example of
someone observing unexpected behavior when moving to a different
compiler. So effectively the semantics changed on his program -- even
though, as you correctly note, the standard did not say what the
semantics were supposed to be. Every particular implementation
provides a particular semantics, and I find it to be a mistake if the
standard permits different implementations to provide different
semantics for a language construct as fundamental as procedure
application in Scheme.
All the talk about possible optimizations that can or cannot be done,
while certainly valid, is still no good argument if
a) the alleged benefits are not realized in real-world implementations
(or are so small that they are not worth the trouble)
b) they come at the expense of having major pitfalls in the language
which we are unable to detect reliably
Matthias
Joe Marshall
> "Bradd W. Szonye" <bradd...@szonye.com> writes:
>
>> But the compiler *doesn't* alter semantics. R5RS doesn't permit it, and
>> the suggested change wouldn't either. Currently, the semantics are only
>> "changed" when programmers rely on unspecified behavior, which is a
>> design/coding error, not a compiler error.
>
> That's just sophistry. This thread started with a real example of
> someone observing unexpected behavior when moving to a different
> compiler. So effectively the semantics changed on his program -- even
> though, as you correctly note, the standard did not say what the
> semantics were supposed to be.
That's weird. You expect all implementations to provide the *same*
semantics for *undefined* behavior?
> Every particular implementation provides a particular semantics, and
> I find it to be a mistake if the standard permits different
> implementations to provide different semantics for a language
> construct as fundamental as procedure application in Scheme.
The standard permits different implementations to provide different
semantics for mismatched arity, too.
Besides, the standard als permits different implementations to provide
different semantics for bad types, unbound variables, multiple
occurrances of variables in binding lists, use of macro keywords which
don't match patterns, assignment to unbound variables, using inexact
numbers as indices, CAR and CDR on empty lists, etc.
The standard also says that ``One restriction on LETREC is very
important: it must be possible to evaluate each <init> without
assigning or referring to the value of any <variable>. If this
restriction is violated, then it is an error.''
Do you expect implementations to detect this error? Or would you
prefer to define some sort of standard semantics to this case?
The same situation applies to shadowing syntactic keywords that may be
necessary to delimit internal definitions, mutation of symbol->string
results.
Matthias Blume
> Matthias Blume <fi...@my.address.elsewhere> writes:
>
> > "Bradd W. Szonye" <bradd...@szonye.com> writes:
> >
> >> But the compiler *doesn't* alter semantics. R5RS doesn't permit it, and
> >> the suggested change wouldn't either. Currently, the semantics are only
> >> "changed" when programmers rely on unspecified behavior, which is a
> >> design/coding error, not a compiler error.
> >
> > That's just sophistry. This thread started with a real example of
> > someone observing unexpected behavior when moving to a different
> > compiler. So effectively the semantics changed on his program -- even
> > though, as you correctly note, the standard did not say what the
> > semantics were supposed to be.
>
> That's weird. You expect all implementations to provide the *same*
> semantics for *undefined* behavior?
No. I expect that there is no "undefined behavior". If the program
is accepted, it should have well-defined behavior.
> > Every particular implementation provides a particular semantics, and
> > I find it to be a mistake if the standard permits different
> > implementations to provide different semantics for a language
> > construct as fundamental as procedure application in Scheme.
>
> The standard permits different implementations to provide different
> semantics for mismatched arity, too.
>
> Besides, the standard als permits different implementations to provide
> different semantics for bad types, unbound variables, multiple
> occurrances of variables in binding lists, use of macro keywords which
> don't match patterns, assignment to unbound variables, using inexact
> numbers as indices, CAR and CDR on empty lists, etc.
I would definitely prefer standard semantics for all of these or
otherwise have them rejected as errors. In terms of practical
importance, though, I would rate the evaluation order problem higher
than most of these issues. Also, most of these things are -- unlike
the ordering problem -- easy to deal with, at least at runtime. (Of
course, as you know, I would like it even better if all of these are
dealt with at compile time.)
> The standard also says that ``One restriction on LETREC is very
> important: it must be possible to evaluate each <init> without
> assigning or referring to the value of any <variable>. If this
> restriction is violated, then it is an error.''
>
> Do you expect implementations to detect this error? Or would you
> prefer to define some sort of standard semantics to this case?
Implementations that detect this (at runtime) exist.
> The same situation applies to shadowing syntactic keywords that may be
> necessary to delimit internal definitions, mutation of symbol->string
> results.
Yes, unfortunately there is more than one dark corner in the language.
Matthias
Thant Tessman
[...]
> The standard permits different implementations to provide different
> semantics for mismatched arity, too.
>
> Besides, the standard als permits different implementations to provide
> different semantics for bad types, unbound variables, multiple
> occurrances of variables in binding lists, use of macro keywords which
> don't match patterns, assignment to unbound variables, using inexact
> numbers as indices, CAR and CDR on empty lists, etc.
[...]
Now I remember why I liked ML better.
-thant
Joe Marshall
> No. I expect that there is no "undefined behavior". If the program
> is accepted, it should have well-defined behavior.
I'm not sure how this could be made compatible with language
extensions, so I think that *some* undefined behavior must be
acceptable.
Thant Tessman
Goddammit. Earlier today I found out there's a serious possibility I'm
gonna have to do a serious project in C in the not-too-distant future
and it's put me in a grumpy mood and I wanna fight about something and
no one is taking the bait.
-thant
Matthias Blume
Simple: language extensions make previously illegal programs legal.
In other words, you no longer get error messages for certain things.
Matthias
Bradd W. Szonye
>> If you shave a bit [of time] off each procedure call, especially in a
>> language as procedure-happy as Scheme, you see systematic
>> improvements. Also, the more you let the compiler optimize code, the
>> less you need programmers doing expensive hand-tuning. It's the very
>> opposite of premature micro-optimization.
Thant Tessman <th...@acm.org> wrote:
> If this kind of optimization is so important, why not go with a static
> type system? That's going to buy you much more of an improvement in
> performance than allowing for arbitrary evaluation order.
Because it's a major change in semantics. Dynamic type systems provide a
different level of expressiveness. Order of argument evaluation does
not, since Scheme does have (trivial!) ways to specify it if you really
need it.
Matthias Felleisen
> Ray Dillinger <be...@sonic.net> wrote:
>
>>> You are right that, with pure functional arguments it doesn't matter
>>> and the compiler can resequence them anyway if it proves they are pure
>>> functional. But the definition of pure functional has two parts; a
>>> pure functional expression is non-side effecting and it is not
>>> affected by any side effects.
>
>
> I was using a less strict definition, functions that produce no side
> effects. However, my concrete example also fits your definition:
> Consider two functions, SPLAY-FIND and INORDER-TRAVERSE. The first
> function has side effects, but they're below the abstraction barrier.
> The second function is a purely-functional tree walker. Even though
> SPLAY-FIND mutates the tree, they don't affect INORDER-TRAVERSE, because
> all the side effects are below the abstraction barrier.
>
If you really want to specify this properly, you need
- no exceptions
- no errors
- no effect from free vars
- no effect on free vars
- no infinite loops
- no allocation effects
In other words, your compiler needs to prove something really strong.
For someone in Q&A, I am surprised to hear any argument in favor of a
language that doesn't specify decidable criteria for discovering when
a program diverges from standards. Are all programmers in your organization
perfect?
-- Matthias
Lauri Alanko
[On non-determinism]
> Put otherwise: leaving the order of evaluation undefined does not turn
> Scheme into a mini-Prolog.
Please. The concept of determinism has been around for far longer than
Prolog has. To my mind, "non-determinism" means _primarily_
"impredictability", and only secondarily the CS-specific concept of
"returning multiple alternative values" or "backtracking". Do you really
insist that the latter is the only valid usage for the word?
Lauri Alanko
l...@iki.fi
Bradd W. Szonye
>> But the compiler *doesn't* alter semantics. R5RS doesn't permit it,
>> and the suggested change wouldn't either. Currently, the semantics
>> are only "changed" when programmers rely on unspecified behavior,
>> which is a design/coding error, not a compiler error.
Matthias Blume <fi...@my.address.elsewhere> wrote:
> That's just sophistry. This thread started with a real example of
> someone observing unexpected behavior when moving to a different
> compiler. So effectively the semantics changed on his program ....
No, he got undefined behavior either way, because he didn't follow the
rules. Now, I'm generally inclined to protect newbies and naive users,
but where do people get the idea that it's OK to rely on evaluation
order in procedure calls anyway? It's something that *most* languages
IME leave unspecified, because a fixed order isn't very useful, because
it obscures meaning (by conflating the notions of argument evaluation
and sequencing), and because it inhibits optimization. It isn't good for
much of anything except protecting students from mistakes, and even that
isn't a very good idea, because those same students will have the same
problem (only worse) once they start using a systems language like C.
> All the talk about possible optimizations that can or cannot be done,
> while certainly valid, is still no good argument if
>
> a) the alleged benefits are not realized in real-world implementations
> (or are so small that they are not worth the trouble)
A source cited earlier claimed a 7% performance improvement by
optimizing argument eval order. That's an impressive gain; I've worked
in the perf world. Unfortunately, there wasn't enough data to explain
the conclusion. I too would like to see more, because that's better than
even I expected.
Then again, it's not totally surprising. If it was a Scheme compiler for
i386, using the hardware stack, I would expect a major improvement in
speed and code size by using right-to-left arg eval. That's because the
i386 has a downward-growing stack, and the PUSH instruction is *very*
efficient in time and space. (IIRC, it's a 1-byte opcode with a 1-cycle
running time.) Therefore, it works best if you push the args in last to
first order, and *that* is easier to do when you eval the args
"backwards."
This brings up another important point: I don't think just *any*
evaluation order will do. If you define it as anything but
left-to-right, you'll screw up the English-speaking newbies just as
badly. And left-to-right is exactly the wrong way to do it in a
native-code Scheme compiler for the i386.
> b) they come at the expense of having major pitfalls in the language
> which we are unable to detect reliably
It's not a major pitfall. And it's not like Scheme is alone in this
behavior. There's a reason why most languages leave it unspecified!
Several reasons, actually, and I've been trying to explain them to you.
Bradd W. Szonye
>> That's weird. You expect all implementations to provide the *same*
>> semantics for *undefined* behavior?
Matthias Blume <fi...@my.address.elsewhere> wrote:
> No. I expect that there is no "undefined behavior". If the program
> is accepted, it should have well-defined behavior.
What, you don't like extensions to programming languages? Or do you just
prefer O(2^n) compilers? Most undefined behavior in language standards,
IME, is because (1) the correctness of some construct is undecidable, or
(2) there are potential extensions to handle "error" cases, but the
standards body doesn't want to mandate them.
felix
> Bradd W. Szonye wrote:
>> Matthias Blume <fi...@my.address.elsewhere> wrote:
>
> [...]
>
>>
>> How so? If you shave a bit off each procedure call, especially in a
>> language as procedure-happy as Scheme, you see systematic improvements.
>> Also, the more you let the compiler optimize code, the less you need
>> programmers doing expensive hand-tuning. It's the very opposite of
>> premature micro-optimization.
>
> If this kind of optimization is so important, why not go with a static
> type system? That's going to buy you much more of an improvement in
> performance than allowing for arbitrary evaluation order.
>
Statically typed languages are evil. They restrict expressiveness,
and kill all the fun of programming. It's for people who like to be
patronized by their compilers.
felix
Lauri Alanko
> >> ... overall maintenance becomes more expensive, because the fixed
> >> evaluation order removes information about the procedure.
> >> Specifically, it removes a guarantee that "order doesn't matter
> >> here" ....
>
> > There is no such "guarantee" unless the compiler proves it.
>
> The Scheme standard provides the guarantee. If a programmer ignores it,
> that's a bug. Therefore, if a maintainer does notice that a procedure
> call depends on a particular order, he immediately knows that it's a
> design bug.
That's a _huge_ "if". The property is non-decidable also for humans
(provided you don't refute the Church-Turing thesis).
So let's see. The current situation on depending the evaluation order of
arguments is:
- It is discouraged
- The machine cannot reliably detect it
- A human cannot reliably detect it
- A program that nevertheless depends on it is unreliable
+ If someone reading the code does detect it, then there does not
need to be a comment stating "this is intentional" for the reader to
know whethere it is a bug or not.
If the order were specified then depending on it would mean that:
- It is discouraged
- The machine cannot reliably detect it
- A human cannot reliably detect it
+ A program that nevertheless depends on it is still reliable
- _If_ someone reading the code does detect it, then there needs
to be a comment stating "this is intentional" for the reader to
know whethere it is a bug or not.
Now which is the bigger plus, which is the bigger minus?
Lauri Alanko
l...@iki.fi
Bradd W. Szonye
>> I was using a less strict definition, functions that produce no side
>> effects. However, my concrete example also fits your definition:
>> Consider two functions, SPLAY-FIND and INORDER-TRAVERSE. The first
>> function has side effects, but they're below the abstraction barrier.
>> The second function is a purely-functional tree walker. Even though
>> SPLAY-FIND mutates the tree, they don't affect INORDER-TRAVERSE,
>> because all the side effects are below the abstraction barrier.
Matthias Felleisen <matt...@ccs.neu.edu> wrote:
> If you really want to specify this properly, you need
> - no exceptions
> - no errors
> - no effect from free vars
> - no effect on free vars
> - no infinite loops
> - no allocation effects
> In other words, your compiler needs to prove something really strong.
If it wants to move an evaluation past a sequence point, that's true,
because it must prove that the optimization will not affect the
program's semantics. That's *why* the fixed sequencing is a bad idea --
it's rarely important, there's a trivial way to specify it when it is
important, and it interferes with automated optimization.
With the unspecified sequencing, there is no problem. The compiler can
reorganize argument evaluation freely. That also increases the chances
of useful parallelization, because there are more ways to combine the
procedures.
> For someone in Q&A, I am surprised to hear any argument in favor of a
> language that doesn't specify decidable criteria for discovering when
> a program diverges from standards.
Which program diverged from standards? It's not an *error* for the
evaluation of two arguments to interact. Indeed, that's exactly what
happens in the splay find & traverse example above. Since R5RS
guarantees that it's equivalent to *some* sequence, you're OK so long as
all the side-effects are below some abstraction barrier.
It's only a problem when a programmer naively expects left-to-right
sequential behavior. And "don't do that!" gets drummed into most
programmers very early, because most languages IME leave arg eval order
unspecified.
> Are all programmers in your organization perfect?
No, certainly not. That's why we hold design and code reviews. It
doesn't catch all of the bugs, but it's the best way to find a certain
class of errors, like "does this program halt?" Sequencing errors are
exactly the kind of thing that you look for in design & code reviews,
not in compilers, because humans have the domain knowledge to answer
"undecidable" problems in a reasonable amount of time. Human programmers
are good at using abstraction barriers to break the problems into small,
modular chunks, proving correctness one unit at a time. Compilers don't
(yet) know how to do that.
Thant Tessman
[...]
> Statically typed languages are evil. They restrict expressiveness,
> and kill all the fun of programming. It's for people who like to be
> patronized by their compilers.
Thanks, I needed that.
-thant
Matthias Felleisen
in Scheme should be
(<identifier> <identifier>*)
and we're done. -- Matthias
Bradd W. Szonye
>> it, that's a bug. Therefore, if a maintainer does notice that a
>> procedure call depends on a particular order, he immediately knows
>> that it's a design bug.
Lauri Alanko <l...@iki.fi> wrote:
> That's a _huge_ "if". The property is non-decidable also for humans
> (provided you don't refute the Church-Turing thesis).
True. However, remember that "undecidable" doesn't mean that analysis
necessarily takes forever. In particular, while the general problem is
undecidable, many specific examples are tractable. Humans use
abstraction barriers and similar self-imposed constraints to keep the
analysis tractable. However, compilers don't (yet) understand those
things, so they're stuck solving the general problem, which is much
harder.
> So let's see. The current situation on depending the evaluation order
> of arguments is:
>
> - It is discouraged
> - The machine cannot reliably detect it
> - A human cannot reliably detect it
That depends on what you mean by "reliably." If the programmer did it
intentionally, because he *wanted* the args to evaluate in a particular
order, I'd expect any decent code reviewer to catch it. (That's exactly
what happened in this case.) And I wouldn't expect many competent
programmers to make the mistake in the first place; knowing which
instructions are sequenced and which aren't is an important part of
learning any programming language. Yes, student programmers will make
the mistake, usually pretty early, and usually because a teacher or
textbook sternly warned them not to do it. Yes, even competent
programmers will occasionally make the mistake, but then it's no more
serious than any other brain fart, and it should never make it past
review.
That leaves the cases where a programmer *unintentionally* used
arguments that interact badly. Those cases *are* difficult to find, and
humans won't reliably detect it. However, fixing the arg eval order
doesn't fix that problem. Sure, you may get more consistent behavior,
but it's still a design error. I'd expect a fixed eval order to
partially mask the problem such that it only shows up in corner cases.
(It might be useful to have a "perverse" option on the compiler to
jumble up the eval order -- it could help to unmask this kind of bug.)
So I really don't expect a fixed eval order to help with anything but
intentional misuse of the feature, and that's easy enough to prevent
with training and code reviews.
> - A program that nevertheless depends on it is unreliable
> + If someone reading the code does detect it, then there does not
> need to be a comment stating "this is intentional" for the reader to
> know whethere it is a bug or not.
Also:
+ Permits more compiler optimizations, including very basic but very
effective "optimizations" like evaluating args from left to right or
right to left according to what works best with the machine's
hardware stack.
> If the order were specified then depending on it would mean that:
>
> - It is discouraged
I disagree. If you make it well-defined, that will just encourage
programmers to insist that it *is* a good idea. Seriously, how do you
explain that it's "discouraged" when it's legal? Would you also
discourage (let* ((arg1 ...) (arg2 ...)) (f arg1 arg2))? Why?
> - The machine cannot reliably detect it
> - A human cannot reliably detect it
> + A program that nevertheless depends on it is still reliable
If the programmer intentionally depends on it, it's reliable. If it
happens by accident (which is more likely, if you have competent
programmers and reviewers), the fixed order doesn't help much at all.
> - _If_ someone reading the code does detect it, then there needs
> to be a comment stating "this is intentional" for the reader to
> know whethere it is a bug or not.
Now add:
- Inhibits significant optimizations.
- Encourages bad programming practices that *will* bite you on the ass
when you switch to one of the many other languages that leave the
order unspecified.
> Now which is the bigger plus, which is the bigger minus?
Your "plus" isn't a plus at all, and you omitted some of the advantages
and disadvantages.
Bradd W. Szonye
Heh, that would do it. Of course, that's just shifting the problem onto
the binding constructs (which would need to become primitives instead of
macros that expand into applications).
Bradd W. Szonye
>>> No. I expect that there is no "undefined behavior". If the program
>>> is accepted, it should have well-defined behavior.
> Joe Marshall <j...@ccs.neu.edu> writes:
>> I'm not sure how this could be made compatible with language
>> extensions, so I think that *some* undefined behavior must be
>> acceptable.
> Simple: language extensions make previously illegal programs legal. In
> other words, you no longer get error messages for certain things.
Not so simple: If the standard requires that the program signal an
error, you can't just ignore the condition. If the standard doesn't
require the diagnostic, then you're effectively back to "undefined
behavior." Fully-defined languages and extensions just don't mix well,
not if they want to claim standards conformance, anyway.
Matthias Blume
> > [ ... ] This thread started with a real example of
> > someone observing unexpected behavior when moving to a different
> > compiler. So effectively the semantics changed on his program ....
>
> No, he got undefined behavior either way, because he didn't follow the
> rules.
He got behavior not defined *by the language standard*. The concrete
compiler, however, did provide a defined semantics (even though it
might not have been documented). And that is precisely the problem:
compiler's have a hard time not completely defining the semantics of
language constructs they implement.
> Now, I'm generally inclined to protect newbies and naive users,
> but where do people get the idea that it's OK to rely on evaluation
> order in procedure calls anyway?
It is certainly not ok in a language that does not define that order.
(But I'd say that the problem is with the language, not with the
people here.) In other languages it is quite ok, but many (myself
included) might not consider it good style. Leaving gaping holes in
language definitions, however, is definitely not ok.
> It's something that *most* languages IME leave unspecified, because
> a fixed order isn't very useful, because it obscures meaning (by
> conflating the notions of argument evaluation and sequencing), and
> because it inhibits optimization.
If you count by usage, then you are probably right since C and C++ are
in the "order unspecified" camp. But other than that I would not be
so sure. And given all the known problems with these languages, I
would hardly consider them benchmarks in good language design.
> It isn't good for much of anything except protecting students from
> mistakes,
No, it is not just students. I have seen very experienced programmers
make this mistake (and then proceed to spend days trying to chase down
the resulting bugs).
> and even that isn't a very good idea, because those same students
> will have the same problem (only worse) once they start using a
> systems language like C.
Well, if we only could get students to stop moving to ill-defined and
unsafe languages like C. Look at the recent deluge of compromised
Linux systems and you know what I mean...
> > All the talk about possible optimizations that can or cannot be done,
> > while certainly valid, is still no good argument if
> >
> > a) the alleged benefits are not realized in real-world implementations
> > (or are so small that they are not worth the trouble)
>
> A source cited earlier claimed a 7% performance improvement by
> optimizing argument eval order. That's an impressive gain; I've worked
> in the perf world.
7% is barely above the threshold where some people call optimizations
worthwhile. In any case, it is not clear at all how much of those 7%
are due to optimizations that would not be possible at all under fixed
order. Some of them might simply require more compiler effort to
prove them safe. It is really hard to tell without seeing a very
detailed study.
> Unfortunately, there wasn't enough data to explain the conclusion. I
> too would like to see more, because that's better than even I
> expected.
The real question is how much of this could have been recovered in
very short time by profiling and fixing the hotspots by hand.
I have actually seen far higher savings when (effectively) switching
from l2r to r2l under certain circumstances. Under other
circumstances, l2r is far better than r2l. But with fixed order of
evaluation it is fairly easy to reason about this, and just a little
bit of linguistic support is enough to give the programmer the tools
to deal with the problem the right way: by explicitly writing the code
in such a way that evaluation proceeds in the order that is less
expensive.
> Then again, it's not totally surprising. If it was a Scheme compiler for
> i386, using the hardware stack, I would expect a major improvement in
> speed and code size by using right-to-left arg eval. That's because the
> i386 has a downward-growing stack, and the PUSH instruction is *very*
> efficient in time and space. (IIRC, it's a 1-byte opcode with a 1-cycle
> running time.) Therefore, it works best if you push the args in last to
> first order, and *that* is easier to do when you eval the args
> "backwards."
You can get the same benefit by simply changing the calling
conventions. There are other issues with l2r that are far more
detrimental to performance when one is not careful with them. But see
above, even those are not difficult to deal with.
> > b) they come at the expense of having major pitfalls in the language
> > which we are unable to detect reliably
>
> It's not a major pitfall. And it's not like Scheme is alone in this
> behavior.
Just because several language designs get this wrong does not mean
that it is suddenly right.
> There's a reason why most languages leave it unspecified!
Sure. The important question is whether the reasoning behind those
"reasons" is sound, and whether it considered all consequences.
> Several reasons, actually, and I've been trying to explain them to you.
Thank you very much. But you know, I'm a bit dense, so your efforts
at patronizing me aren't doing any good. (Actually, all of the people
here who have argued against leaving the order unspecified are known
to be completely clueless when it comes to PL questions. So don't
listen to us.)
Matthias
Matthias Blume
That's a red herring. Programs that signal errors (in the sense: "I
give up because the program has an error", not in the sense: "I raise
an exception at runtime that gets handled elsewhere by the program")
are hardly useful. The error message is there precisely to signal
that such a non-useful program has been detected. I see no harm in
making more programs useful by not signalling some of these errors.
(Of course, I also prefer such errors to be signalled at compile time
-- in which case the "gets handled at runtime by an exception
hanndler" part becomes trivially irrelevant.)
Bradd W. Szonye
>> If the standard requires that the program signal an error, you can't
>> just ignore the condition. If the standard doesn't require the
>> diagnostic, then you're effectively back to "undefined behavior."
>> Fully-defined languages and extensions just don't mix well, not if
>> they want to claim standards conformance, anyway.
Matthias Blume wrote:
> That's a red herring. Programs that signal errors (in the sense: "I
> give up because the program has an error", not in the sense: "I raise
> an exception at runtime that gets handled elsewhere by the program")
> are hardly useful. The error message is there precisely to signal that
> such a non-useful program has been detected. I see no harm in making
> more programs useful by not signalling some of these errors.
A standard where all of the errors are optional is a joke. It doesn't
have any teeth in it. A language standard where all of the behavior is
well-defined is also a joke, unless (1) you intend to use only a single
implementation on a single system, or (2) you can get a large government
to fund the development. No undefined or implementation-defined behavior
leaves little room for alternate implementation strategies, and it makes
porting to some platforms *very* difficult.
Language standards leave some behavior unspecified *exactly* because
there's more than one good way to do it, and because existing
implementations have user communities that don't want to give up their
way. They also leave some behavior unspecified because some behavior
just doesn't translate well to all systems.
However, for the things a language does define, it's important that you
do get diagnostics when you run a non-comforming program. Without them,
it's too easy to get hooked by an unadvertised language extension.
That's why C, as loose as it is, strictly requires that every
implementation document *all* of the implementation-defined behavior.
That's why standards certification bodies require a waiver for every
deviation before they'll grant use of the "approved" trademark.
I'm even more curious about your background now, because your
suggestions keep getting farther and farther from the reality I'm
familiar with. It may be that we come from different places with very
different ideas of standards and best practices.
Matthias Blume
> However, for the things a language does define, it's important that you
> do get diagnostics when you run a non-comforming program.
Since programs that rely on order of evaluation are non-conforming,
shouldn't we then require a diagnostic?
> I'm even more curious about your background now, because your
> suggestions keep getting farther and farther from the reality I'm
> familiar with.
My background is easy to find out.
What is yours?
Feuer
>
> "Scott G. Miller" <scgm...@freenetproject.org> writes:
>
> > Besides, we have constructs for fixing an order of evaluation for
> > expressions which have side effects.
>
> Yes, and those constructs can be used for fixing the order differently
> than what is the (fixed) default order when performance really
> matters.
A better argument for you would be to claim that non-side-effecting
functions can be reordered at will, so the compiler actually can
reorder almost anything it wants, given the right information.
> > This is no worse than say the
> > undefined behavior of multithreaded programs when the programmer
> > doesn't use a mutex construct to protect a critical region.
>
> Now you want to throw all the complexity of concurrent programming
> even at simple sequential programs?!?
A program running on Unix or some such is concurrent whether
or not it wants to be.
David
Feuer
"Bradd W. Szonye" wrote:
> Evaluating arguments in parallel can be consistent with some sequential
> order of evaluation. If you tighten the constraints on evaluation order,
> however, you reduce the opportunities for parallelization. For example,
> consider a call with three arguments. The first and last arguments are
> purely functional, but the middle argument is not. With unspecified
> order, the system can parallelize evaluation of the purely-functional
> arguments. With fixed order, it cannot, because the middle argument
> creates a "sequence point" that you cannot cross without breaking
> consistency with the abstract model.
You _could_ fix this in the code by replacing
(let ((a (pure 1))
(b (impure))
(c (pure 2)))
foo)
with
(let ((a (pure 1))
(c (pure 2)))
(let ((b (impure)))
foo))
but that may be too much to expect?
David
Jay Osako
> 1. A program with peek-char is almost always broken. The other MF.
>
> 2. You want to perform effect-full actions only once via let. (A
> lesson from monads.)
>
> 3. The Scheme Report imposes an undecidable correctness criteria on
> programs -- that they don't depend on the order of evaluation -- without
> (naturally) asking implementations to check it. Go figure; and that language
> supposedly has a semantics.
Thank you very much for both the corrected function and the
explanation. While it did need two minor changes - you dropped the
test on the count variable, and the port variable was missing in the
read-char call - the function as you rewrote it works fine now on all
the implementations I've tested it with. I'm surprised I didn't think
to replace peek-char with read-char and save the result rather than
doing the read twice, but the order of operations issue was one I had
missed. I'll have to pay closer attention to that.
I am still curious whether anyone had taken a chance to look at the
rest of the program (a link to it was given in the TLP), and what they
thought of it, but given the way that this thread ignited over issue
of defined-vs-undefined order of operations, and some of the other
discussions I've seen here, I suspect I am out of my depth in this
newsgroup... I'll probably lurk a while before any further posting,
except for responding to any specific followups on my existing posts.
--
Jay Osako aka Schol_R-LEA;2
If the phone rings today, water it!
Feuer
Matthias Blume wrote:
> False. If the compiler actually knows that the first and third
> arguments are purely functional
Which is hard to do in Scheme because every Scheme variable and
cons cell is mutable.
David
Matthias Blume
Matthias Blume
> Why bless poor code? It encourages the errors.
Why make code that is merely poor but not incorrect incorrect without
also providing a means of finding out that the code is now, in fact,
incorrect?
> No, the big mistake is conflating the concepts of "argument list" and
> "sequence of operations." That's a fundamental design error, not just a
> bit of sloppy programming, and a programming language should *not*
> encourage the error.
I don't see why this should be a "design error". It certainly is not
a "fundamental" design error.
> > People in this newsgroup often like to waffle about the "freedom" that
> > is granted by a language. Making the evaluation order unspecified
> > *takes away* such freedom.
>
> Not when there's a trivial, alternate way that lets you write it.
>
> (let* ((arg1 ...) (arg2 ...)) (f arg1 arg2))
That's not what I meant. Sure, you can fix the order by hand. The
problem is that if you don't, you are now required to prove (to
yourself) that the program is correct under every possible permutation
in the evaluation order. With long enough argument lists, this is a
lot of proving. With fixed order, you have to prove this only for one
possible order. And, of course, every program that would be correct
under all possible permutations is also correct in the fixed-order
scenario.
> If you use that pattern a lot, you can even write a macro to simplify
> the syntax, e.g. (sequential-args f arg1 arg2). But that's a one-way
> trip. Once you require sequential evaluation for all procedure calls,
> you remove all possibility of automatic optimization.
No, you do not remove the possibility, at least not in general. It
can still be done whenever the compiler can prove that it does not
matter to the outcome of the program, i.e., if the reordering is not
observable. (Granted, in languages like Scheme or C doing so is very
hard because there are side effects left and right wherever you look.
That is another weakness of these languages. Even LAMBDA is effectful
in Scheme -- something which popular systems such as DrScheme quietly
ignore because it makes life just too damn difficult without providing
adequate benefit.)
> Only hand-tuning is possible then, and I think we all know how
> error-prone that is.
I don't think it is all that error-prone, especially not compared to
having a major pitfall in the language such as the one we are
discussing here. I actually have hand-tuned code that exhibited bad
performance under one particular evaluation order, but this didn't
happen very frequently, and the fix was very straightforward and
without danger of messing things up.
> > Proof: Every program that is a valid program under unspecified order
> > is also a valid program under fixed evaluation order. But not vice
> > versa. Therefore, there are fewer correct programs under
> > "unspecified" order.
>
> Refutation: Every program that is not valid under unspecified order has
> a trivial transformation that makes it valid (and that makes the
> ordering *explicit*, which is an aid to maintainers).
This is not a "refutation".
> Meanwhile, the fixed order precludes many automatic optimizations,
> which encourages premature hand-tuning. (Yes, it actually encourages
> more than one poor coding style.)
Not at all, in my experience. These days I exclusively program in
languages with fixed evaluation order, and there certainly is no
problem with "premature" tuning. The little tuning that has been done
was always after the program already worked and the fragment in
question had been singled out as performing poorly.
> > Unlike with type systems, though, whether or not a program is invalid
> > because of reliance on evaluation order is not decidable (either at
> > compile or at runtime).
>
> Which is why it's a bad idea to conflate evaluation order with other
> concepts, like argument lists. When order matters, it's not enough to
> just throw code at a compiler and hope that it works.
Nobody is saying "throw code at a compiler and hope that it works".
In languages where fixed evaluation order doing so is not necessary as
"hope" does not need to come in anywhere. That's precisely because
the rules are unambiguous and fully determine the program's outcome.
There are other places where the same "conflation" as you call it is
done, and nobody complains about it: Why are arguments evaluated
before the function is invoked? Why does the condition of an
if-expression get to run before the branch(es)? Why are the arguments
to AND evaluated strictly from left to right?
Well, your answer will probably contain the words "call by value",
"short-circuiting behavior", and so on. It all comes down to the fact
that in languages with effects order matters. And it matters not just
in some places, it matters everywhere.
> Allowing automatic optimization and discouraging poor coding styles is
> not an upside?
No. Once again: Turning correct but perhaps poor coding style into
downright incorrect code without a way of detecting that this has
happened is definitely not an upside. Allowing automatic optimization
is good, but only as long as "optimization" means "preserving
semantics" and "having a well-defined semantics in the first place".
> Meanwhile, fixed evaluation order has several concrete
> drawbacks. It effectively shifts the ambiguity from initial coding to
> maintenance. The original developer knows that he can rely on the order
> of evaluation, but maintainers can't tell whether they've actually done
> so. By conflating the two ideas, you lose information.
I wouldn't call that a "concrete" drawback. As I said, I program in a
language with fixed evaluation order on a daily basis, and I deal with
a very large code basis, much of which has been written by other
people years ago. I have not once run into the sort of problem that
you allude to. On the other hand, I have accidentally run into the
problem with unspecified evaluation order in Scheme and C, and I have
seen it happen to other people as well on several occasions.
> I don't know how much maintenance work you've done, but it's a huge part
> of the software lifecycle, typically over 50%.
Well, see above.
> By blessing a poor design and coding style, you make maintenance
> more difficult and increase the overall cost of the software.
But is is not really "blessing poor design". People don't do this
sort of stuff all that much -- not more than they do accidentially or
out of ignorance in C or Scheme. [Here I am ignoring a few idiomatic
uses such as the SML "before" operator that I mentioned earlier.
These definitely do not count as "poor style".]
Matthias
Daniel C. Wang
> This sort of thing is especially important now that "superscalar"
> machine architectures are ubiquitous. For example, on an IA-64 system,
> unnecessary sequence points have *major* performance implications. Why
> introduce unnecessary sequence points just to bless a poor design and
> coding style?
1. The IA-64 despite all the marketing from Intel is not a "ubiquitous"
architecture
2. All existing architectures that allow for parallel execution
dynamically schedule instructions on the fly.
(i.e. Pentium 4, PowerPCs, Transmeta, AMD x86-64, UltraSparc ...)
The only performance number that has been discussed in this thread is a 7%
cost for strict left-right evaluation. I'd hardly call 7% a major cost.
Most paralleism left in applications is not fine grain instruction level,
but at the thread level. If you want to exploit paralleism I'd personally be
writing programs in the Pi-calculus or Erlang. :)
Daniel C. Wang
"Bradd W. Szonye" <bradd...@szonye.com> writes:
> Matthias Blume <fi...@my.address.elsewhere> wrote:
> > Sure, there is no use in denying that there are some (rather obscure)
> > corner cases where the [unspecified argument evaluation order] gives
> > some additional power to a compiler.
>
> Obscure? I'd expect it to be systematic, actually. At the very least, I
> would expect a small but significant difference from switching between
> left to right and right to left according to the machine's stack
> architecture. (For example, right-to-left seems like it would be more
> efficient if the machine uses a downward-growing stack for arguments.)
If typically, you pass arguments in registers rather than on the stack,
which is what you ought to be doing with all the registers anyway it doesn't
matter.
> And I'd also expect the implicit sequence points to make a noticeable
> difference on "superscalar" CPUs like the Pentium and Itanium, where the
> CPU itself parallelizes instructions. Compilers would need to insert a
> lot more NOPs or stop bits to guarantee correct ordering, which
> interferes with pipelining and increases code size.
The Pentium *dynamically* schedules code at runtime. The Itanium must do it
at compile time, which basically makes it a real PITA to compile for. You
would think that now that you've made the compiler work really hard you
could throw away all the complicated dynamic instruction scheduling logic
and use those transitors for something else like a bigger cache or a simpler
pipeline.
From what I know about the Itanium its a monster peice of power hungry
hardware that requires sophsiticated compilers to get decent
performance. Many, people believe the Itanium will end up being a
multi-billion dollar disaster for Intel. Luckily for Intel is one of the
few compaines that can surive such a mistake.
David Rush
> Left to right, right to left, or something more original?
How about writing argmuent expressions with indelible ink on
indigestible sheets of plastic and feeding them to your yak?
The first expression to come out the other end is the one to
get evaluated. This method has been found to discourage
optimizations due to the necessity of slicing open the
pre-processor, which makes the code far more predictable...
> Is the function position evaluated first or last?
Well first you have to get the yak into kneeling position...
> Should library syntax be required to have a particular order?
The library yak won't arrive until the 25th. I'm hoping for a
copy of SICY (Structure and Interpretation of Crap from Yaks) to
be available this time so I can finish my thesis...
> What about syntax introduced by extensions or SRFI's?
You can't surf with a yak.
david rush
--
going into hiding from the maniacs at the Nepalese Journal of
Deconstruction Sociologists and Sheep-herders
David Rush
wrote:
> Joe Marshall <j...@ccs.neu.edu> writes:
>> Besides, the standard als permits different implementations to provide
>> different semantics for bad types, unbound variables, multiple
>> occurrances of variables in binding lists, use of macro keywords which
>> don't match patterns, assignment to unbound variables, using inexact
>> numbers as indices, CAR and CDR on empty lists, etc.
>
> I would definitely prefer standard semantics for all of these or
> otherwise have them rejected as errors.
What? You *don't* like bats flying out your nose whenever your program
has a run-time error? It's those charming personal touches which make
Scheme implementations so attractive...
david rush
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
David Rush
> Goddammit. Earlier today I found out there's a serious possibility I'm
> gonna have to do a serious project in C in the not-too-distant future
> and it's put me in a grumpy mood and I wanna fight about something and
> no one is taking the bait.
That's because Scheme and ML are the same language, even if Matthias
doesn't want to admit it...
<duck>
Joe Marshall
> Shriram Krishnamurthi <s...@cs.brown.edu> virkkoi:
> [On non-determinism]
>> Put otherwise: leaving the order of evaluation undefined does not turn
>> Scheme into a mini-Prolog.
>
> Please. The concept of determinism has been around for far longer than
> Prolog has. To my mind, "non-determinism" means _primarily_
> "impredictability", and only secondarily the CS-specific concept of
> "returning multiple alternative values" or "backtracking". Do you really
> insist that the latter is the only valid usage for the word?
In any subgroup of the `comp' hierarchy I think it is reasonable to
assume that `non-deterministic' means the CS-specific concept.
Do you think that `NP-complete' means that you simply can't
predict when an answer will be forthcoming? Is a `non-deterministic
Turing machine' simply one with a time-varying clock rate?
Thant Tessman
>
>
> That's because Scheme and ML are the same language, even if Matthias
> doesn't want to admit it...
SML is Scheme with a type system and all that that implies. Scheme is
SML with macros and all that that implies.
But Matthias is absolutely right about the evaluation order thing.
And the mutability thing...
And the environment thing...
-thant
Joe Marshall
If it were up to me, I'd probably just specify r2l and be done with
it. `Compiler optimization' just isn't a compelling argument.
Matthias Blume <fi...@my.address.elsewhere> writes:
> It is certainly not ok in a language that does not define that order.
> (But I'd say that the problem is with the language, not with the
> people here.) In other languages it is quite ok, but many (myself
> included) might not consider it good style. Leaving gaping holes in
> language definitions, however, is definitely not ok.
Why do you think this is `a gaping hole'? In my opinion it seems a
rather trivial bit of untidiness.
> No, it is not just students. I have seen very experienced programmers
> make this mistake (and then proceed to spend days trying to chase down
> the resulting bugs).
I make these mistakes, too.
But the most recent time I made this kind of mistake was in a Common
Lisp program, which defines l2r evaluation. Specifying the order of
evaluation doesn't reduce the rate at which people depend on it, it
simply gives them a guarantee that *sometimes* they'll be lucky. This
is a truly lame `improvement'.
> Well, if we only could get students to stop moving to ill-defined and
> unsafe languages like C. Look at the recent deluge of compromised
> Linux systems and you know what I mean...
If only C had a fixed order of argument evaluation, we could stop all
those viruses that exploit the ambiguity.
> 7% is barely above the threshold where some people call
> optimizations worthwhile.
I'd say 10% is minimum, but only if you can get the savings
trivially.
> But you know, I'm a bit dense, so your efforts at patronizing me
> aren't doing any good. (Actually, all of the people here who have
> argued against leaving the order unspecified are known to be
> completely clueless when it comes to PL questions. So don't listen
> to us.)
What? Did you say something?
Joe Marshall
> On Thu, 04 Dec 2003 12:31:43 -0500, Joe Marshall <j...@ccs.neu.edu> wrote:
>> Left to right, right to left, or something more original?
>
> How about writing argmuent expressions with indelible ink on
> indigestible sheets of plastic and feeding them to your yak?
> The first expression to come out the other end is the one to
> get evaluated. This method has been found to discourage
> optimizations due to the necessity of slicing open the
> pre-processor, which makes the code far more predictable...
>
>> Is the function position evaluated first or last?
>
> Well first you have to get the yak into kneeling position...
This explains why my yak is walking funny.
Next time, please experiment on your own yak first.
Matthias Blume
> What? You *don't* like bats flying out your nose whenever your program
> has a run-time error?
The bats are fine. I just don't like my hard drive catching fire.
Bradd W. Szonye
>> I would definitely prefer standard semantics for all of these or
>> otherwise have them rejected as errors.
David Rush <ku...@gofree.indigo.ie> wrote:
> What? You *don't* like bats flying out your nose whenever your program
> has a run-time error? It's those charming personal touches which make
> Scheme implementations so attractive...
Ha! Scheme programmers are wimps! When a C++ programmer screws up,
*demons* fly out of his nose.
Scott G. Miller
Actually, by using a reverse order of operations, SISC gains 35% in
continuation capture/application. So large gains can be had for some
operations. You can get pretty sizeable gains by reordering the
application of math operations on bignums too for example, though
arguably you can still do that by 'cheating' if the order is fixed by
the standard and reording anyway.
Scott
Daniel C. Wang
> Actually, by using a reverse order of operations, SISC gains 35% in
> continuation capture/application. So large gains can be had for some
> operations. You can get pretty sizeable gains by reordering the
> application of math operations on bignums too for example, though
> arguably you can still do that by 'cheating' if the order is fixed by
> the standard and reording anyway.
Fair, but I doubt the sizeable performance wins are going to show up because
of the underlying machine micro-architecture.
BTW is this optimization explained in detail anywhere?
Scott G. Miller
It depends. Its very possible that reordering can strongly affect
memory usage enough to influence cache performance, which can be a huge
win. Granted, the compiler must be smart enough to do so.
>
> BTW is this optimization explained in detail anywhere?
Matthias R. and I have been meaning to write it up in a paper but
neither of us seem to have much free time these days.
Scott
David Rush
> David Rush wrote:
>> On Thu, 04 Dec 2003 14:42:45 -0700, Thant Tessman <th...@acm.org> wrote:
>>
>>> [...] and no one is taking the bait.
>>
>> That's because Scheme and ML are the same language, even if Matthias
>> doesn't want to admit it...
>
> SML is Scheme with a type system and all that that implies. Scheme is
> SML with macros and all that that implies.
Oooh good. My .sigmonster is licking it's bits^Wchops
> But Matthias is absolutely right about the evaluation order thing.
Surprisingly (to me), I think that he is not. And I actually do get bitten
by the lack of specification fairly regularly (since I regularly run my
Scheme code on at least 3 different implementations). Nearly *every* time
I make the evaluation order mistake, fixing it improves the code. Sometimes
rather dramatically.
> And the mutability thing...
I'm pretty sure I agree with this one.
> And the environment thing...
Not sure what this one is.
And you forgot winding continuations...
Thant Tessman
> On Fri, 05 Dec 2003 09:09:46 -0700, Thant Tessman <th...@acm.org> wrote:
[...]
>> But Matthias is absolutely right about the evaluation order thing.
>
>
> Surprisingly (to me), I think that he is not. And I actually do get bitten
> by the lack of specification fairly regularly (since I regularly run my
> Scheme code on at least 3 different implementations). Nearly *every* time
> I make the evaluation order mistake, fixing it improves the code. Sometimes
> rather dramatically.
Surprisingly (to me), I've *never* been bitten by this issue in any
language. (Don't get me wrong, I've been bitten by a lot of stupid
stuff. I once spent a day chasing down a bug that turned out to be a
type-o in an include guard.) It's just that leaving evaluation order
unspecified is the Wrong Thing (TM) in a language that otherwise prides
itself on doing the Right Thing (TM) given a certain Scheme aesthetic.
[...]
>> And the environment thing...
>
> Not sure what this one is.
(define (bar) foo) ; should be an error because foo isn't defined yet
(define foo 23)
(define (bar) foo)
(define foo 5)
(bar) => 5
; should be 23, the value of foo when bar was defined
I suppose this is related to the mutability thing, but not only is this
semantically awkward, but isn't it actually a performance hit to support
this kind of functionality?
-thant
Andre
> Leaving gaping holes in
> language definitions, however, is definitely not ok.
>
But pluggin the hole does not necessary require fixing the evaluation order.
See, for example, this old article by Christian Queinnec:
http://zurich.ai.mit.edu/pipermail/rrrs-authors/1993-May/001634.html
Matthias Blume
Sure, you can "plug" the whole by making things explicitly
non-deterministic in the semantics, the same way this has to be done
for, e.g., a concurrent language. I find it offensive, though, to
throw all the complexity of concurrency on a sequential language. In
practical terms, this is *not* a solution as it changes nothing from
the point of view of the programmer. Returning some random element
from a denotation in Answer* is just as bad as not returning a
well-defined result. (The two things are the same.)
As far as the above article is concerned, I am not sure whether it is
correct in the details. Getting the details right on this stuff is
very hard. In fact, after reading the article a bit more closely, I
think it is wrong.
One way of correctly dealing with Scheme's unspecified evaluation
order involves using an infinite stream of random bits that becomes an
additional parameter to the program. Each pair of corresponding
permute/unpermute calls then consumes some of the random bits. I
program has a deterministic outcome if you can prove that it has the
same outcome for all possible input tapes of random bits.
Anyway, these things are nice mental exercises, but they do not change
the situation as the programmer sees it.
Matthias
David Rush
> David Rush wrote:
>> On Fri, 05 Dec 2003 09:09:46 -0700, Thant Tessman <th...@acm.org> wrote:
>>> And the environment thing...
>>
>> Not sure what this one is.
>
> (define (bar) foo) ; should be an error because foo isn't defined yet
Ah you mean the squidgy-top-level-specification-because-we-dont-know-how-
to-bootstrap-a-mutable-toplevel-when-it-shouldn't-*be*-mutable-in-the-first-
place thingy. Yes, I agree 100% that this is a serious problem. set! *is* a
bitch, ain't it? It'sjust so convenient sometimes to have...
never mind.
david rush
--
(\x.(x x) \x.(x x)) -> (s i i (s i i))
-- aki helin (on comp.lang.scheme)
Bradd W. Szonye
> Surprisingly (to me), I've *never* been bitten by this issue in any
> language. (Don't get me wrong, I've been bitten by a lot of stupid
> stuff. I once spent a day chasing down a bug that turned out to be a
> type-o in an include guard.) It's just that leaving evaluation order
> unspecified is the Wrong Thing (TM) in a language that otherwise
> prides itself on doing the Right Thing (TM) given a certain Scheme
> aesthetic.
In contrast, I believe that unspecified evaluation order is the Right
Thing. Implicit sequencing is sometimes helpful to newbies, but to
experienced programmers, it doesn't make much difference, and it can get
in the way (by masking design flaws and inhibiting optimization). Scheme
has plenty of sequencing forms if you need them; it doesn't need another
one. I personally wouldn't mind if Scheme cut out all implicit
sequencing, so that the only sequencing features were procedure calls
(to preserve by-value semantics) and those elements which exist
specifically to provide sequencing, like LET*, BEGIN, IF, AND, OR.
One thing I dislike about implicit sequencing is that it gives a false
sense of security. Scheme has a few implicit sequences, so newbies
expect arg eval to work that way too. Oops! OK, we make arg eval
sequential too. Newbies expect library macros to work the same way --
they look just like other function calls, after all. Oops! OK, we put
requirements on standard macros. Newbies expect third-party macros to
work the same way. Oops! Unless you really want to handcuff Scheme
implementors and library providers, there will always be some Oops!
where the newbie expects sequential evaluating and doesn't get it.
Yes, that's a slippery-slope argument. I personally feel that Scheme is
already a step or two down the slope. Adding fixed arg eval goes further
down the slope, doesn't really fix anything, and does hurt some things.
Furthermore, macros make it dead simple to create a syntax for
fixed-order arg eval, if you *really* want it. (Maybe it should even be
in the standard Scheme library.) If your Scheme has something like PLT's
#%apply, you can even redefine primitive combinations.