gjc@mitech.COM (04/04/91)
Odd numbered arguments right to left and even ones left to right? Of course that was proposed as just about the most stupid thing that anybody could think of. (What if somebody said, *yes*?) But lets be practical. Undefined order of evaluation, (undefined *anything* really) is one of the big things that gets in the way of most people learning a computer language. OK. Order of evaluation may be undefined. However, I ASK: *What* useful thing has the person who learns this fact of (some) computer languages REALLY LEARNED? Is it a reasonable stepping stone in intelectual developement? (To never trust the computer? To always be on the look out for ways it might screw you?) [Come to think of it. That is why it it took me only 10 minutes to learn how to program effectively in MACLISP. There were no special cases and exceptions to learn, nothing that got in the way of my previous experience of western/mathematical culture. Subtle implementation artifacts came up only in the more advanced areas.] Do most people who may be able to use a computer language give a tinkers damn about what some compiler-writing person knows? Or what some group of language implementors think they know about programming style? Face it. People understand the written word, and written directions are given to people in this format: LEFT-TO-RIGHT, TOP-TO-BOTTOM. Period, fact of life. (Yes, there are some right-to-left languages, but no bottom-to-top languages. And even our common western experience includes a NUMERIC representation stolen from an Arabic culture, which is right-to-left. And the confusion this has caused is even reflected in our COMPUTER HARDWARE, the silly Big-Endian, Little-Endian crap.) Does the community of Scheme programmers really gain enough from having an undefined order of evaluation of arguments to a procedure? Does it gain enough to make up for the losses faced as people learn the language. (Or in the long run, less usage of the language). I could be convinced! -gjc p.s. For example, in a spread-sheet the "order-of-evaluation" could very well be undefined, or at least be something that it is not a good idea to make use of in a complex program.
markf@zurich.ai.mit.edu (Mark Friedman) (04/05/91)
In article <9104041629.AA19876@schizo> gjc@mitech.COM writes:
But lets be practical. Undefined order of evaluation, (undefined
*anything* really) is one of the big things that gets in the way of
most people learning a computer language.
OK. Order of evaluation may be undefined. However,
I ASK: *What* useful thing has the person who learns this fact of
(some) computer languages REALLY LEARNED? Is it a reasonable
stepping stone in intelectual developement?
They may have learned that Scheme (as intended by most of its
designers) is a mostly functional language with imperative features
which should be used in carefully controlled ways. Ways are provided
to control order of evaluation but the evaluation of procedure
arguments is not one of them.
Note that having the the order of evaluation of procedure arguments be
undefined is not zero knowledge; it tells you not to depend on any
particular order.
Do most people who may be able to use a computer language give a
tinkers damn about what some compiler-writing person knows? Or what
some group of language implementors think they know about
programming style?
Implicitly they do. Real users want their programs to run efficiently.
That means that compiler writers had better know something.
One of the reasons the user of any particular programming language
chooses it is because he wants to write his programs in a style that
is well supported by the language.
Face it. People understand the written word, and written directions
are given to people in this format: LEFT-TO-RIGHT, TOP-TO-BOTTOM.
Period, fact of life.
Although our (western) eyes may move LEFT-TO-RIGHT, TOP-TO-BOTTOM, the
cognitive parsing is more complex, especially for some other languages
(Latin, for instance).
In any case, I assume that you are not proposing that we program in
English (or even COBOL).
(Yes, there are some right-to-left languages, but no bottom-to-top
languages...)
This may be true for natural languages, but not computer languages in
general. How about:
foo
(bar
(baz
(grumble (x))))
which in most computer languages (including your exemplar C) evaluates
pretty much bottom up. And, of course, we have:
x + ((y * (z - (n / k) + a)) - 6)
which evaluates inside out, left to right, right to left and does the
hokey pokey.
Does the community of Scheme programmers really gain enough from having
an undefined order of evaluation of arguments to a procedure?
That's the key question. I don't know the answer.
-Mark
--
Mark Friedman
MIT Artificial Intelligence Lab
545 Technology Sq.
Cambridge, Ma. 02139
markf@zurich.ai.mit.edumatthias@leto.rice.edu (Matthias Felleisen) (04/05/91)
In article <9104041629.AA19876@schizo> gjc@mitech.com writes: >Odd numbered arguments right to left and even ones left to right? >Of course that was proposed as just about the most stupid thing that >anybody could think of. (What if somebody said, *yes*?) No, let's say yes. I'd rather have some order than none! >Face it. People understand the written word, and written directions >are given to people in this format: LEFT-TO-RIGHT, TOP-TO-BOTTOM. I am so happy to see that somebody finally said this: that's the way it should be, and yes, PERIOD. Left-to-right is how we READ. And then we PARSE. And then we UNDERSTAND. If we can't even read, how are we going to understand? People want a simple mental model of program execution because that's the basis for programming. Unordered evaluation of application expressions is a major obstacle to a simple model. Ask students who learn to program in PURE SCHEME (the functional subset). They assume left-to-right and hand/head-simulate execution that way. When they get an error message or the program gets into an infinite loop, they look for sources of errors and loops in that fashion. Worst of all, we always claim that (PURE) Scheme is a deterministic language. But given that a compiler can choose an arbitrary order of evaluation for every application expression during every compilation, the "same" Pure Scheme program may never reproduce the same error or infinite-loop behavior. Don't bother to argue that errors or infinite loops are not proper behavior because if you ever programmed, you know it's not true. Whatever the benefits of an unspecified order of evaluation for compiler writers are, the costs are too high a price to pay. We all program with some mental model of program execution, and unorderedness and potential non-determinism for something as simple as PURE SCHEME is too weird. Scheme is about having-fun-with-programming, not about fun-for-compiler-writers. Let's fix the order of evaluation! GO LEFT-TO-RIGHT! :-) -- Matthias
harlan@copper.ucs.indiana.edu (Pete Harlan) (04/05/91)
<A number of people> writes: >Does the community of Scheme programmers really gain enough from having >an undefined order of evaluation of arguments to a procedure? Yes! I have to read and understand other people's code a lot. When I look at a combination they've written, I currently don't have to think about whether the order of the arguments matters (unless there is a bug in the program; this sort of bug occurs *rarely*, in my experience). Do the proponents of fixed-order really think this is unimportant information? >Does it gain enough to make up for the losses faced as people learn >the language. (Or in the long run, less usage of the language). Are the 'losses' really that great? The amazing thing to the student, I think, is discovering how rarely it matters what the order is, and the nature of those cases where it does. Do you really want to take that away? Pete Harlan harlan@iuvax.cs.indiana.edu
jaffer@zurich.ai.mit.edu (Aubrey Jaffer) (04/05/91)
gjc and others suggest fixing the order of evaluation. If this order is fixed Scheme will lose the ability to be easily run on multiple processors. This will confine scheme to the dustbin of history. As was pointed out earlier, the order of evaluation of only occasionally trips up programmers. I think this is a reasonable price to pay for Schemeing into the 21st century. The difference between the current situation and totally unspecified order (possibly simultaneous) for arguments seems like not to jarring a change. Someone posted an article a while ago about doing this and introducing semaphore primitives to Scheme. I think this is the way we should be going; not fixed order.
moore%defmacro.utah.edu@cs.utah.edu (Tim Moore) (04/05/91)
In article <JAFFER.91Apr5002735@chamarti.ai.mit.edu> jaffer@zurich.ai.mit.edu (Aubrey Jaffer) writes: >gjc and others suggest fixing the order of evaluation. If this order >is fixed Scheme will lose the ability to be easily run on multiple >processors. This will confine scheme to the dustbin of history. > As was pointed out earlier, the unspecified order of evaluation has almost no effect, pro or con, on running Scheme on multi-processors. Arguments can be evaluated in any order, but evaluation cannot be interleaved. -- Tim Moore moore@cs.utah.edu {bellcore,hplabs}!utah-cs!moore "Ah, youth. Ah, statute of limitations." -John Waters
mkatz@garlic.stanford.EDU (Morris Katz) (04/06/91)
Date: 5 Apr 91 02:14:22 GMT From: Matthias Felleisen <matthias@leto.rice.edu> Organization: Rice University, Houston In article <9104041629.AA19876@schizo> gjc@mitech.com writes: >Odd numbered arguments right to left and even ones left to right? >Of course that was proposed as just about the most stupid thing that >anybody could think of. (What if somebody said, *yes*?) No, let's say yes. I'd rather have some order than none! >Face it. People understand the written word, and written directions >are given to people in this format: LEFT-TO-RIGHT, TOP-TO-BOTTOM. I am so happy to see that somebody finally said this: that's the way it should be, and yes, PERIOD. Left-to-right is how we READ. And then we PARSE. And then we UNDERSTAND. If we can't even read, how are we going to understand? People want a simple mental model of program execution because that's the basis for programming. Unordered evaluation of application expressions is a major obstacle to a simple model. Ask students who learn to program in PURE SCHEME (the functional subset). They assume left-to-right and hand/head-simulate execution that way. When they get an error message or the program gets into an infinite loop, they look for sources of errors and loops in that fashion. Worst of all, we always claim that (PURE) Scheme is a deterministic language. But given that a compiler can choose an arbitrary order of evaluation for every application expression during every compilation, the "same" Pure Scheme program may never reproduce the same error or infinite-loop behavior. Don't bother to argue that errors or infinite loops are not proper behavior because if you ever programmed, you know it's not true. Whatever the benefits of an unspecified order of evaluation for compiler writers are, the costs are too high a price to pay. We all program with some mental model of program execution, and unorderedness and potential non-determinism for something as simple as PURE SCHEME is too weird. Scheme is about having-fun-with-programming, not about fun-for-compiler-writers. Let's fix the order of evaluation! GO LEFT-TO-RIGHT! :-) -- Matthias It seems to me that the logical extension of your argument is that we should return to pure scheme by removing all of the imperative constructs from Scheme since their value does not offset the loss of referential transparency. Please explain what differentiates these two arguments. I have yet to hear from your side a real cost/benefit analysis. What I have heard is that you (collectively) do not have a good feel for the benefits of unspecified order of evaluation and see a cost to it, so it should go. This is not a cost/benefit analysis. I personally see some real benefits to unordered evaluation order, an have not found the costs to students nearly as extreme as you seem to have. As some of you may know, my current research involves automatic parallelization of scheme through optimistic concurrency plus rollback. The ability to choose the effective order of evaluation of arguments at runtime can greatly reduce the amount of rollback required in a system like mine and thereby markedly improve performance. Here is a REAL benefit. I would like to see serious programs people desire to write that a seriously hampered by unspecified order of evaluation so I can better appreciate that category of costs. I have no idea how to get a handle on the cognitive dissonance problem your students have experienced as I have not seen it in practice. -------------------- Morry Katz katz@cs.stanford.edu --------------------
carlton@husc10.harvard.edu (david carlton) (04/06/91)
In article <9104041629.AA19876@schizo> gjc@mitech.COM writes:
But lets be practical. Undefined order of evaluation, (undefined *anything*
really) is one of the big things that gets in the way of most people learning
a computer language.
OK. Order of evaluation may be undefined. However,
I ASK: *What* useful thing has the person who learns this
fact of (some) computer languages REALLY LEARNED? Is it a reasonable stepping
stone in intelectual developement?
(To never trust the computer? To always be on the look out for ways it might
screw you?)
Face it. People understand the written word, and written directions
are given to people in this format: LEFT-TO-RIGHT, TOP-TO-BOTTOM.
Period, fact of life. (Yes, there are some right-to-left languages,
but no bottom-to-top languages. And even our common western experience
includes a NUMERIC representation stolen from an Arabic culture,
which is right-to-left. And the confusion this has caused is even
reflected in our COMPUTER HARDWARE, the silly Big-Endian, Little-Endian
crap.)
Does the community of Scheme programmers really gain enough from having
an undefined order of evaluation of arguments to a procedure?
Does it gain enough to make up for the losses faced as people learn
the language. (Or in the long run, less usage of the language).
I could be convinced!
I think that learning Scheme can, for many people, be as much a
process of unlearning as a process of learning. For example, in many
other programming languages, functions aren't first class objects. In
Scheme, they are. I submit that this should be looked at as a process
of unlearning, since in Scheme objects are treated more uniformly,
while in other languages some kinds of objects are treated specially.
Similarly, in many other languages the function position of a function
call is evaluated differently than the other positions, while in
Scheme it is not - again, we have a special case to "unlearn". And I
think that an undefined order of evaluation is another such things -
you have to "unlearn" the idea that arguments should be evaluated in
some order.
So we have the question "*What* useful thing has somebody who has
learned this fact of (some) computer languages REALLY LEARNED? Is it
a reasonable stepping stone in intellectual development?" My
nomination for the useful thing is the principle of simplicity. Don't
add rules when you don't have to. Don't specify something when it is
not clear how it should be specified, unless there is some overriding
reason to specify it in some manner. This is a very useful concept,
and is the way that lots of progress has been made - advances in
mathematics, for example, often come about by looking at an old
problem in a newer, more general manner, which can be considered to be
the same sort of unlearning that I am talking about here.
As to the order of left-right being "natural": this is a very
Anglo-centric viewpoint, I think. (Of course, calling your
conditional "if" is also Anglo-centric - but you have to call your
conditional _something_, whereas you don't have to specify your order
of evaluation, and at any rate I am only trying to lay arguments about
the way the brain is wired or how western brains are taught to rest.)
As has been pointed out, many writing systems work from right to left.
And many work from top to bottom. (Signs painted on streets can even
be written from bottom to top - for example, you sometimes see signs
CROSSING
SCHOOL
SLOW
and the like on roads.) Some even alternate going from right to left
and left to right (early Greek inscriptions sometimes do this, and
they reverse the letters when going right to left), or even weirder
things than that. (For example, cuneiform was often written left to
right, then flipping the tablet over (writing on the edge) and writing
until you reach the end of the other side, then writing right to left,
flipping the tablet over and writing on the edge again.) And, as gjc
pointed out, even within our own cozy English world, not everything is
done left to right, numerals being the obvious example. (Depending on
how you look at it. For that matter, the German way of pronouncing
numbers is somewhat reminiscent of Jinx's proposal for order of
evaluation. And, to bring in another example, at some point in the
development of Old Irish every other syllable of words got deleted,
also a bit reminiscent of Jinx's proposal.) This is not to say that
there isn't an argument to be made for doing things left to right,
since there is - Scheme parsers work from left to right, after all,
with multiple expressions in a file being evaluated from left to right
and top to bottom, and the same for the order of evaluation of
statements within a begin expression, so if you are going to impose an
order of evaluation for the procedure and arguments of a function call
then it should certainly be left to right (with the procedure
evaluated before everything else) - but please don't make arguments
about it being something universal to western culture.
david carlton,
who thinks that function application should be written with the
function on the _right_ since that makes function composition work out
more neatly.lavinus@csgrad.cs.vt.edu (04/07/91)
Hello! The idea behind not having a fixed order of evaluation is largely on principle. Scheme, like Lisp, has an applicative, i.e. functional, language as its core. In general, it is encouraged to do Scheme (and Lisp) programming in such a way as to maximize this applicative style, that is, to minimize side-effects. If you're concerned about order of application, then the only reason must be because one function depends on the side effects of another (with the exception of things like "and", where you might not want one argument to be evaluated if a previous one returns T). So, unspecified order of evaluation encourages you to program in a non- side-effecting way, by saying that you can't depend on any particular order of evaluation. In the big picture, this gains you things like easy parallelization. Anyway, I prefer things that way, but of course, I approach Scheme from the point of view of an applicative language afficionado, and of course, I'm not trying to learn it anew, either :-). Joe -- _________________________________ \ ___________________________________ Joseph W. Lavinus, Virginia Tech \ email: lavinus@csgrad.cs.vt.edu 1204-A University Terrace /\ phone: (703) 552-0241 Blacksburg, VA 24060 / \ (703) 231-5853
matthias@titan.rice.edu (Matthias Felleisen) (04/08/91)
"No amount of language design can {\it force} a programmer to
write clear programs."
LAMBDA: The Ultimate Imperative,
Guy Steele and Gerald Sussman, MIT 1976
-- Matthias Felleisenxerox@cs.vu.nl (J. A. Durieux) (04/08/91)
((lambda (a b) -X-) -A- -B-) = ((lambda (b a) -X-) -B- -A-). Or at least it should be. We had a real good reason to give up refential transparency, and for me it would require an (almost) equally good reason to give up the above property (of which I don't know the name). Biep.
jeff@aiai.edinburgh.ac.UK (Jeff Dalton) (04/08/91)
From: Pete Harlan <harlan@copper.ucs.indiana.edu> I have to read and understand other people's code a lot. When I look at a combination they've written, I currently don't have to think about whether the order of the arguments matters (unless there is a bug in the program; this sort of bug occurs *rarely*, in my experience). Do the proponents of fixed-order really think this is unimportant information? Do you think that if the order were defined you would have to be more concerned about whether the order matters? My experience has been the opposite. When I read code in a language where the order is defined (e.g., Common Lisp), I almost never have to think about whether the order matters. And if something turns out to depend on the order, so what? It will get the same order in every implementation. From: Aubrey Jaffer <jaffer@zurich.ai.mit.edu> gjc and others suggest fixing the order of evaluation. If this order is fixed Scheme will lose the ability to be easily run on multiple processors. This will confine scheme to the dustbin of history. This presupposes that multiple processors are the only future, which is far from clear, and that compilers can't do a sufficient analysis of side effects (or at least not in a way that counts as "easily"), etc. From: Mark Friedman <markf@zurich.ai.mit.edu> I believe that there is an expressiveness argument in favor of keeping the order of evaluation of combinations unspecified. Scheme has a number of mechanisms for indicating a specific order of evaluation (e.g. LET* and BEGIN). Scheme also has some mechanisms for indicating that the order of evaluation is unimportant (e.g. combinations and LET). The language is more expressive currently than if order of evaluation where always specified because a programmer would have no way to express the fact that order of evaluation was not important. I think that is a valid point, although I would also note that it may be harder to understand LET* now because it is used for two things: order of evaluation and dependence between variables. From: Vincent Manis <manis@cs.ubc.ca> Some people propose a fairly radical change to Scheme, moving its behaviour away from the norm in modern programming languages. I seem to recall that the order is defined in ML, which is a modern language. The reason was to reduce the number of ways in which different behavior could result. They do so on the fairly vague basis that `it would be more consistent' or `it's more natural' or some such thing. I disagree. There are real benefits to be had from specifying an order. There are additional benefits to be had from specifying a "natural" order. These benefits have not been quantified, but neither are they vague. -- jeff
mkatz@garlic.stanford.EDU (Morris Katz) (04/08/91)
Date: Sat, 6 Apr 91 15:48:09 CST
From: matthias@rice.edu (Matthias Felleisen)
It seems to me that the logical extension of your argument is that we
should return to pure scheme by removing all of the imperative
constructs from Scheme since their value does not offset the loss of
referential transparency.
(1) I want a simple mental model for what I have and in particular an
expressive language. That includes call/cc, side-effects, ...
(2) You're wrong about referential transparency. Talcott, Mason, and I
have shown that side-effects have equational theories, in which you
can substitute equals for equals.
While I am perfectly willing to believe that this theory fulfills the technical
definition of referential transparency (based on substitution), I continue to
believe until convinced otherwise that languages with side effects of the type
present in Scheme lack an intuitive property which has coloquially refered to
as referential transparency.
I have yet to hear from your side a real cost/benefit analysis. What
I have heard is that you (collectively) do not have a good feel for
the benefits of unspecified order of evaluation and see a cost to it,
so it should go.
I was hoping that Scheme would be a semantics like ML, which has a
simple semantics that can be used to prove meta-properties about the
language. And in which simplicity and elegance ALWAYS (empahsis added by
mjk) takes priority over ease of implementation.
I never understood the goals of the Scheme community to be such that the word
always would be appropriate in the above sentence. I would substitute often,
usually, or normally.
my current research involves automatic parallelization of scheme
through optimistic concurrency plus rollback. The ability to choose
the effective order of evaluation of arguments at runtime can greatly
reduce the amount of rollback required in a system like mine and
thereby markedly improve performance.
I am not an expert but notice that left-to-right does not mean that
the assembly code goes from left to right. It only means that any
effects that happen will always occur from left to right.
My calculi always begin the evaluation in expressions in some
arbitrary order. But the axiom for discharging a beta and side-effects
forces left-to-right. I strongly believe that compilers could do that
too. And quite a few compiler writers tell me that I am probably
right.
I would like to see serious programs people desire to write that a
seriously hampered by unspecified order of evaluation so I can better
appreciate that category of costs.
I hope that the above made it clear that this is not my kind of
argument. Just because I do have an order of evaluation does not mean
that my code will rely on it. Ever. It only means that I rely on it
when mentally tracing execution. And my mind just cannot imagine
unordered execution.
For metally tracing execution of a program written in a language with
unspecified order of evaluation, one should be able to chose any arbitrary
order of evaluation in order to determine what the program does. I do not see
the problem with tracing correct programs. There is a potential problem in
tracing incorrect programs which unintensionally depend on evaluation order,
but this seems to me to be more of a problem in debugging and development
environment technology than of language design. What exactly is troubling you
here?
--------------------
Morry Katz
katz@cs.stanford.edu
--------------------matthias@rice.EDU (Matthias Felleisen) (04/09/91)
.. languages with side effects of the type present in Scheme lack an
intuitive property which has coloquially refered to as referential
transparency ..
They are not side-effect free :-).
More seriously, if you remember my talk on expressiveness at Stanford,
the correct idea is the following: there are "natural" equalities that
hold for expressions that have some mathematical feel to them, e.g., a
+ b = b + a, (lambda (f) ((f 1) Omega)) = (lambda (f) Omega), etc, and
these equations are no longer true in a world with side-effects. The
expressions a and b may have side-effects, the parameter f may be a
continuation. My conclusion in the expressiveness talk was that "when
expressiveness goes up "natural equalities" go away." That's not a
word, but the right idea.
I was hoping that Scheme would be a language like ML, which has a
simple semantics that can be used to prove meta-properties about the
language. And in which simplicity and elegance ALWAYS (empahsis added by
mjk) takes priority over ease of implementation.
I never understood the goals of the Scheme community to be such that the word
always would be appropriate in the above sentence. I would substitute often,
usually, or normally.
Sorry, I am an idealist and I washoping Schemer's were going for the
best. Indeed, in heart I am an "Iswimer" much more than a Schemer.
But as Jinx said, the Scheme community needs some idealists too keep
the pragmaticioners :-) in check.
.. one should be able to chose any arbitrary
order of evaluation in order to determine what the program does.
This is impssible in the presence of errors, exceptions, handlers,
side-effects and so on. It leads to non-determinism and that is more
difficult than Scheme wants to be. Not even in Pure Scheme (with
errors) is it possible, albeit only for incorrect programs. But these
are programs too and (their execution) must be analyzed in a students
mind, indeed, more so than correct ones. A tool is only as helpful as
the semantics ...
-- Matthiaskers@hplb.hpl.hp.com (Chris Dollin) (04/09/91)
J. A. Durieux says: ((lambda (a b) -X-) -A- -B-) = ((lambda (b a) -X-) -B- -A-). Or at least it should be. [1] We had a real good reason to give up refential transparency, and for me it would require an (almost) equally good reason to give up the above property (of which I don't know the name). [2] [1] But, in an imperative language, it *already* isn't; never mind the lambda's, the arguments have to be evaluated in *some* order, and different orders may may a difference. So [1] is a lost cause. [2] I think property [1] is just a consequence of referential transparency, which we've already lost. Incidentally, should anyone think I (or Steve Knight) has something against ``functional programming'' - here meaning programming without side-effects, ie, declarative or ``pure'' functional programming - they'd be wrong. I just think that trying to treat an imperative language (here, Scheme) as though it was pure makes life unnecessarily complex. -- Regards, Kers. | "You're better off not dreaming of the things to come; Caravan: | Dreams are always ending far too soon."
jonl%kuwait@lucid.COM (Jon L White) (04/10/91)
In issue Scheme Digest V3 #182, matthias@titan.rice.edu quotes:
"No amount of language design can {\it force} a programmer to
write clear programs."
LAMBDA: The Ultimate Imperative,
Guy Steele and Gerald Sussman, MIT 1976
Put another way, Academie Francaise notwithstanding you can still
say a lot of idiotic things in French (or write some convoluted,
inelegant programs in Lisp/Scheme.) But just because fixed-order
evaluation won't cure code opacity doesn't mean that nondeterminism
is always A GOOD THING . . .
-- JonL --mkatz@garlic.stanford.EDU (Morris Katz) (04/10/91)
Date: 9 Apr 91 07:25:05 GMT
From: Chris Dollin <kers@hplb.hpl.hp.com>
Organization: Hewlett-Packard Laboratories, Bristol, UK.
J. A. Durieux says:
((lambda (a b) -X-) -A- -B-) = ((lambda (b a) -X-) -B- -A-).
Or at least it should be.
[1]
We had a real good reason to give up refential transparency, and for me
it would require an (almost) equally good reason to give up the above
property (of which I don't know the name).
[2]
[1] But, in an imperative language, it *already* isn't; never mind the
lambda's, the arguments have to be evaluated in *some* order, and different
orders may may a difference. So [1] is a lost cause.
Not true! If argument evaluation order is unspecified then only an incorrect
program will file to meet property [1]
--------------------
Morry Katz
katz@cs.stanford.edu
--------------------Robert Hieb <hieb@heston.cs.indiana.edu> (04/11/91)
mkatz@garlic.stanford.EDU (Morris Katz) writes: > ((lambda (a b) -X-) -A- -B-) = ((lambda (b a) -X-) -B- -A-). > [1] But, in an imperative language, it *already* isn't; never mind the > lambda's, the arguments have to be evaluated in *some* order, and different > orders may may a difference. So [1] is a lost cause. >Not true! If argument evaluation order is unspecified then only an incorrect >program will file to meet property [1] Not not true! I find no such stipulation in R^3.99RS. It simply says that the order of evaluation of the operator and operand expressions of a procedure call is unspecified. So, for instance, assuming a pseudo-random number generator, ((lambda (a b) (cons a b)) (random) (random)) may be perfectly "correct" without being equivalent to ((lambda (b a) (cons a b)) (random) (random)) Presumably one does not care exactly what one gets for "a" and "b." Yet one might still wish to get the same thing when one runs the program on different Scheme systems, or different versions of the same Scheme system. In the end, the strongest argument for complete language specification is verification by testing, rather than verification by proof. If one is trying to prove a program is correct by more or less formal methods, one can start by establishing that the program doesn't rely on unspecified behavior. Then one can proceed with a simpler proof that doesn't take into account argument evaluation order, or other such unpleasant realities. However, such techniques are finally unsatisfactory, no matter how formal. There is no reason to assume that a proof will be simpler than a program, after all. One must prove the proof, prove that the program is implemented as specified, etc. And do so again each time the program is modified. There is no substitute for testing a program. The confidence attained by testing is proportional to the completeness of the language specification. I guess no one will ever want to use Scheme to control airplanes or power plants so we don't have to worry about that...
xerox@cs.vu.nl (J. A. Durieux) (04/13/91)
I said: > ((lambda (a b) -X-) -A- -B-) = ((lambda (b a) -X-) -B- -A-). > Or at least it should be. >[1] > We had a real good reason to give up refential transparency, and for me > it would require an (almost) equally good reason to give up the above > property (of which I don't know the name). >[2] Chris Dollin answers: >[1] But, in an imperative language, it *already* isn't; never mind the >lambda's, the arguments have to be evaluated in *some* order, and different >orders may may a difference. So [1] is a lost cause. No. Currently the evaluation order is undefined, so if the meaning of the expressions somehow depend on the evaluation order, they are *both* undefined. If they don't, they are the same. Even more specific: if they depend, each expression represents a collection of meanings. Again, both represent the same collection. In practice, this means that I can automatically rewrite code in this way (e.g. from one Scheme extension to another, or during partial evaluation), and that I am not forced to read code from left to right (which is *not* necessarily the most "natural" way to read code!), >[2] I think property [1] is just a consequence of referential transparency, >which we've already lost. Referential transparency is a sufficient, but not a necessary condition for this property. I think it deserves a name. Perhaps "order freedom"? Actually, I would like even weaker order requirements to be imposed on Scheme: [a] (f (g a) (h b)) may be evaluated in *any* order, e.g. a-b-f-g-h. [b] The body of a procedure is not guaranteed to be executed after all the arguments to the application are evaluated. I realise *some* requirement should remain (while I am not quite sure which exactly), but e.g. a much stronger requirement of stack efficiency can me made if procedures are allowed to "get rid of" their bodies before starting on a (non-tail-recursive) call. E.g. naive append can execute in constant stack space that way. I am not sure whether I want let* to keep its order-retaining nature. Biep.