[Scheme-reports] Post-plebiscite issue #3: structure-sharing for mapping

[will@x]

(I'm posting as a random member of the Scheme community who knows some
of the relevant history and engineering tradeoffs associated with this
issue.)

John Cowan wrote:

> Alexey writes:
> 
> > - Do map and friends [pp.50-51] always return newly allocated results? 
> >   For example, it's not too hard to write an otherwise-valid 
> >   definition of map where 
> >     (let ((one '(1 6 1 8 0 3)) 
> >           (two '(1 4 1 4 2 1))) 
> >       (eqv? one (map (lambda (x y) x) one two))) 
> >      ==> #t 
> >   and one might even want that, to save space.  There are of course 
> >   more complicated examples where the result of a map could share list 
> >   structure with the tail of one of its inputs, as long as the 
> >   procedure being mapped returned those elements unchanged. 
> 
> Currently, the draft just says "returns a list", "returns a string", and
> "returns a vector", without saying "newly allocated".  I believe nothing
> needs to be added.  Does any WG1 member disagree?  Does any member of
> the Scheme community disagree?  Silence gives consent.

You need to be careful here, lest you write a specification that requires

    (eq? '() (map values '()))

to return false.

Note also that (eq? '#() (vector-map values '#())) returns false in some
current implementations, but returns true in others.  R7RS should continue
to allow that behavior.  (All conforming implementations return true when
the eq? is changed to eqv?, but some implementations achieve that using a
Singleton pattern while others achieve it by making eqv? more complicated.)

This gets back to the fact that eqv? is an actual equivalence predicate,
while eq? is best viewed as a potentially faster version of eqv? that
behaves the same the same as eqv? on some types of arguments but may
behave differently on others.

In fact, eq? is guaranteed to behave as an equivalence predicate only when
its domain is restricted to certain types of arguments.  From R5RS 6.1:

    Eq?'s behavior on numbers and characters is implementation-dependent,
    but it will always return either true or false, and will return true
    only when eqv? would also return true.  Eq? may also behave differently
    from eqv? on empty vectors and empty strings.

R6RS section 11.5 says almost the same thing:

    The behavior of eq? on number objects and characters is
    implementation-dependent, but it always returns either #t or #f, and
    returns #t only when eqv? would also return #t. The eq? predicate may
    also behave differently from eqv? on empty vectors, empty bytevectors,
    and empty strings.

The flakiness of eq? on numbers and characters was intended to allow leeway
with respect to boxing and unboxing.  Under rare circumstances, boxing and
unboxing can prevent the fast (pointer comparison) implementation of eq?
from appearing to be an equivalence predicate when given numbers or characters
as arguments.  This flakiness goes back to the earliest Scheme compilers, when
the flakiness of eq? was inherited from boxing/unboxing optimizations in the
MacLisp compiler.  The flakiness became explicit in the Scheme reports after
it became explicit in Common Lisp.

In my opinion, the R5RS, R6RS, and R7RS draft 9 all err when they say eq? is
an equivalence predicate without alluding to the restricted domain of values
for which it is an equivalence predicate.

IMO, the R6RS also erred by requiring eq? and eqv? to behave exactly the same
on procedure arguments.  That rules out implementations in which

    (let ((p (lambda (x) x)))
      (eqv? p p))

is always true but not always true when eq? is substituted for eqv?.  As a
result, implementations that try to exploit the additional freedom granted
by the R6RS with respect to eqv? on procedures are likely to do so by failing
to recognize two otherwise equivalent procedures, when the more natural and
desirable semantics would allow eqv? to identify procedures that may not have
the same location tags but would otherwise behave identically.

Will

_______________________________________________
Scheme-reports mailing list
Scheme-reports@x
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports