Re: mathematical models

[Guillermo J. Rozas <gjr@martigny.ai.mit.edu>]

|   Subject: Re: mathematical models
|   From: ramsdell@linus.mitre.org (John D. Ramsdell)
|   Date: 05 Jun 1997 15:24:13 -0400
|   
|   I remember when Yale released a new version of T which included David
|   Kranz's new compiler.  The intepreter evaluated combinations in the
|   same order as the original compiler, but the new compiler used the
|   reverse order.  We found a variety of obscure bugs in code written by
|   people who knew that the order was unspecified.  (I was one of the
|   guilty parties.)  The code worked when interpreted and failed when
|   compiled.  That experience convinced me that having an unspecified
|   order of evaluation in an expression oriented language is an
|   invitation for trouble.  To be honest, I also favor specifying the
|   order of evaluation for theoretical reasons as well.

The MIT Scheme interpreter has used right-to-left for a very long time
partly to sniff out such bugs because people seem to implicitly rely
on left-to-right (maybe people whose first language is Arabic or
Hebrew would not -- I don't know).

If I recall correctly, both current MIT Scheme compilers (for versions
7.4 and 8.0, unreleased) use right-to-left as a default when they
can't come up with a better order.  However, they both choose other
orders when they deem it advantageous (different reasons).  Although
this might in general provide a small efficiency gain, in many of the
cases where the performance difference matters (to avoid register
shuffling or to have the computed procedure in the right place by
default), the compilers could prove that the semantics would not be
compromised by changing the order.

Because the MIT Scheme interpreter uses right-to-left by default, I
can't recall a case where code that worked interpreted did not work
compiled because of the order of argument evaluation.  However, the
freedom in the compiler (the version of MIT Scheme 7.x and earlier),
together with somewhat eager reclamation of space, has made debugging
the compiler itself painful at times.

In particular, at one point Chris Hanson had to make the choice of
order more deterministic than necessary, because we ran into the
following situation:

The code that chose the order of argument evaluation, partly depended
(in cases where there was no real preference) on the algorithm itself
on the version of the compiler used to compile the code.

This lead to a failure of the binary convergence test (the compiler
being its own fixed point, with equality being binary equality) which
took a long time to figure out.