Path: utzoo!censor!geac!lethe!tvcent!comspec!telly!attcan!uunet!van-bc!ubc-cs!manis From: manis@cs.ubc.ca (Vincent Manis) Newsgroups: comp.lang.scheme Subject: Re: Order of evaluation (was Re: evaluating () should be an error Message-ID: <1991Mar26.224805.23381@cs.ubc.ca> Date: 26 Mar 91 22:48:05 GMT References: <2977@kraftbus.cs.tu-berlin.de> <1991Mar26.155905.12906@daffy.cs.wisc.edu> Sender: usenet@cs.ubc.ca (Usenet News) Organization: Institute for Pure and Applied Eschatology Lines: 79 In article kiran@copper.ucs.indiana.edu (Kiran Wagle) writes: >>Of course going to far in this direction might lead to specifying the >>evaluation order of arguments to procedures, and I don't think that would be >>good. >Why not? Because it can substantially impair the ability of a compiler to produce high-quality code. If a compiler is required to honour a particular order of evaluation, then compiling expressions which require most of the registers available will almost inevitably result in register spills, which then slow the code down. If a compiler can choose the order of evaluation, it can evaluate arguments in whatever order requires the fewest number of registers. As an example, suppose that we want to evaluate (baz (foo 1) 2 3 (+ 4 (bar 5))) on a machine which has four available registers. If the language insists we evaluate from left to right, then about the best we can do is load r0,1 call foo ;; Assume args are passed in lowest numbered regs. load r1,2 load r2,3 load r3,4 store r0,temp ;; Register spill. load r0,5 call bar add r0,4 ;; Very smart compiler notices it can cheat here. load r4,r0 ;; Assume result is returned in r0. load r0,temp call baz If, on the other hand, the compiler is free to evaluate arguments in any order, it can generate load r0,5 call bar load r3,r0 load r0,1 call foo load r1,2 load r2,3 call baz Notice that the compiler had special knowledge that + is commutative and associative (of course, whoever told the compiler that was wrong: Scheme was designed by people who know something about numerical analysis!). But, in the absence of information from the programmer, the compiler had no way of knowing that foo, bar, and baz didn't have side-effects, ill-conditioned numerical properties, or other factors which would depend upon the order of evaluation. Of course, Scheme could be extended with declarations to help the compiler, but the history of such declarations is that they are not used except in desperation. There is almost nothing to be gained, and a lot to be lost, by prescribing order of evaluation. On the subject of what should be returned by set!, define, etc., let me put in a plug for a void object. PC Scheme has something called *THE-NON-PRINTING-OBJECT*, and the next edition of Chez Scheme is planned to have an object returned by (void). These are well-defined objects, except that they have no uses, other than a procedure which generates one, (void), and a type predicate (void?). Top levels don't have to print void results, and set!, define, etc., could return them as values. Note that void in this case is not the same as in C or ALGOL-68, where the implication is that the object requires 0 bits to be stored. Scheme void objects would be the same size as any other object; they would just be useful in indicating that no useful value is given. -- \ Vincent Manis "There is no law that vulgarity and \ Department of Computer Science literary excellence cannot coexist." /\ University of British Columbia -- A. Trevor Hodge / \ Vancouver, BC, Canada V6T 1W5 (604) 228-2394