Subject: + folding differs between compiler and interpreter

From: Zefram <[email-masked]>
Date: Thu, 16 Jan 2014 12:46:29 +0000

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