bug#16464: + folding differs between compiler and interpreter

bug#16464: + folding differs between compiler and interpreter

[Zefram]

The + procedure left-folds its arguments in interpreted code and
right-folds its arguments in compiled code.  This may or may not be a bug.

Obviously, with exact numbers the direction of folding makes no
difference.  But the difference is easily seen with flonums, as flonum
addition is necessarily non-associative.  For example, where flonums
are IEEE doubles:

scheme@(guile-user)> ,o interp #f
scheme@(guile-user)> (+ 1.0 (expt 2.0 -53) (expt 2.0 -53))
$1 = 1.0000000000000002
scheme@(guile-user)> (+ (expt 2.0 -53) (expt 2.0 -53) 1.0)
$2 = 1.0
scheme@(guile-user)> ,o interp #t
scheme@(guile-user)> (+ 1.0 (expt 2.0 -53) (expt 2.0 -53))
$3 = 1.0
scheme@(guile-user)> (+ (expt 2.0 -53) (expt 2.0 -53) 1.0)
$4 = 1.0000000000000002

Compiler and interpreter agree when the order of operations is explicitly
specified:

scheme@(guile-user)> (+ (+ 1.0 (expt 2.0 -53)) (expt 2.0 -53))
$5 = 1.0
scheme@(guile-user)> (+ 1.0 (+ (expt 2.0 -53) (expt 2.0 -53)))
$6 = 1.0000000000000002

If your flonums are not IEEE double then the exponent in the test case
has to be adapted.

R5RS and the Guile documentation are both silent about the order of
operations in cases like this.  I do not regard either left-folding or
right-folding per se as a bug.  A portable Scheme program obviously can't
rely on a particular behaviour.  My concern here is that the compiler
and interpreter don't match, making program behaviour inconsistent on
what is notionally a single implementation.  That mismatch may be a bug.
I'm not aware of any statement either way on whether you regard such
mismatches as bugs.  (An explicit statement in the documentation would
be most welcome.)

R6RS does have some guidance about the proper behaviour here.  The
description of the generic arithmetic operators doesn't go into such
detail, just describing it as generic.  It can be read as implying that
the behaviour on flonums should match the behaviour of the flonum-specific
fl+.  The description of fl+ (libraries section 11.3 "Flonums") says it
"should return the flonum that best approximates the mathematical sum".
That suggests that it shouldn't use a fixed sequence of dyadic additions
operations, and in my test case should return 1.0000000000000002
regardless of the order of operands.  Obviously that's more difficult
to achieve than just folding the argument list with dyadic addition.

Interestingly, fl+'s actual behaviour differs both from + and from the
R6RS ideal.  It left-folds in both compiled and interpreted code:

scheme@(guile-user)> (import (rnrs arithmetic flonums (6)))
scheme@(guile-user)> ,o interp #f
scheme@(guile-user)> (fl+ 1.0 (expt 2.0 -53) (expt 2.0 -53))
$7 = 1.0
scheme@(guile-user)> (fl+ (expt 2.0 -53) (expt 2.0 -53) 1.0)
$8 = 1.0000000000000002
scheme@(guile-user)> ,o interp #t
scheme@(guile-user)> (fl+ 1.0 (expt 2.0 -53) (expt 2.0 -53))
$9 = 1.0
scheme@(guile-user)> (fl+ (expt 2.0 -53) (expt 2.0 -53) 1.0)
$10 = 1.0000000000000002

fl+'s behaviour is not a bug.  The R6RS ideal is clearly not mandatory,
and the Guile documentation makes no stronger claim than that its fl+
conforms to R6RS.  As it is consistent between compiler and interpreter,
it is not subject to the concern that I'm raising in this ticket about
the generic +.

-zefram

bug#16464: + folding differs between compiler and interpreter

[Mark H Weaver]

tags 16464 notabug
thanks

Zefram <zefram@fysh.org> writes:

> The + procedure left-folds its arguments in interpreted code and
> right-folds its arguments in compiled code.  This may or may not be a
> bug.

[...]

> R5RS and the Guile documentation are both silent about the order of
> operations in cases like this.  I do not regard either left-folding or
> right-folding per se as a bug.  A portable Scheme program obviously can't
> rely on a particular behaviour.  My concern here is that the compiler
> and interpreter don't match, making program behaviour inconsistent on
> what is notionally a single implementation.  That mismatch may be a bug.

As you suggest, this is not a bug.  The compiler is free to apply a
different ordering to each '+' and '*' within a program, which can be
used to good effect by an optimizer.

> Obviously, with exact numbers the direction of folding makes no
> difference.  But the difference is easily seen with flonums, as flonum
> addition is necessarily non-associative.

Indeed, and if you need to explicitly order the operations (and this
_is_ often needed when working with inexacts to prevent things like
catastrophic annihilation), then you can do so using extra parentheses.

BTW, there are _many_ other cases like this, where certain aspects
behavior are left unspecified, and might not only differ between the
compiler and interpreter, but might even differ between two identical
subexpressions.  Most notably, the order in which the operand and
operands of a procedure call are evaluated is left unspecified, and
again, this can be used to good effect in a compiler for optimization
purposes.  Another is that the initializers in a 'let' or 'letrec' (but
not 'letrec*') can be evaluated in any order.

However, there _are_ some related bugs that you missed.  R5RS specifies
that '-' and '/' are left-associative, which implies that that (- x y z)
must evaluate as (- (- x y) z), and similiarly for '/', but in 2.0.9
(and afaik, in all existing 2.0.x releases), we transform (- x y z) to
(- x (+ y z)), which is incorrect.

I discovered and fixed these bugs in August in the git repository, and
they will be part of Guile 2.0.10.  I also changed the order of
operations of '+' and '*' to be left-associative while I was at it, but
I later realized that this is not required, and we reserve the right to
change the order in the future.

http://git.savannah.gnu.org/gitweb/?p=guile.git;a=commitdiff;h=71673fba930d735c09184d5ca115882239edabb3

I'm closing this bug now.

     Thanks,
       Mark