[r6rs-discuss] reverse engineering a philosophy: portability

From: William D Clinger <will>
Date: Tue Oct 3 13:59:31 2006

reverse engineering a philosophy: portability



I am posting this as an individual member of the Scheme
community. I am not speaking for the R6RS editors.

It is hard for me to make sense of the draft R6RS
without imagining some guiding philosophy in more
detail than is provided by the guiding principles
of the last two status reports. I must imagine
these details because the editors have not written
them down. Even the editors' minutes and informal
email, from which some of these details might be
inferred, remain unavailable to the public so far
as I know.

In this message I will present a mythical guiding
philosophy, which I reconstructed by applying my
imagination to the guiding principles stated in
the last two status reports. I am making my
fevered imaginings public because it is conceivable
that someone else will find, as I do, that the draft
R6RS makes more sense when the reader imagines a
purpose to the details. I also hope to stimulate
discussion of guiding philosophies that make more
sense than the one I imagine here.

In this message, I will limit my imagination to
matters of portability, partly because I care about
portability and partly because the last two status
reports state that R6RS Scheme should:

    allow programmers to create and distribute
    substantial programs and libraries, e.g., SRFI
    implementations, that run without modification
    in a variety of Scheme implementations;

In the status report of June 2006, that was the first
of the four guiding principles that are new for the
R6RS, i.e. do not merely preserve some property of
the R5RS. The third of the new guiding principles
is that R6RS Scheme should:

    allow programmers to rely on a level of automatic
    run-time type and bounds checking sufficient to
    ensure type safety while also providing a standard
    way to declare whether such checks are desired;

There is little obvious connection between this third
principle and portability, but I believe the draft
R6RS becomes easier to understand if we imagine this
principle to be

    allow programmers to rely on a level of automatic
    run-time type and bounds checking sufficient to
    ensure type safety and to outlaw extensions while
    also providing a standard way to declare whether
    such checks and outlaws are desired;

Outlawing extensions contributes to portability by
discouraging programmers from relying on non-portable
extensions. In my experience with allegedly portable
R5RS programs, I found that many of the most common
impediments to portability were of this sort. Among
them were:

 1. use of square brackets in place of parentheses
 2. reliance upon case-sensitivity
 3. reliance upon other implementation-specific
    lexical syntax
 4. use of implementation-specific record facilities
 5. use of implementation-specific module facilities
 6. use of implementation-specific macro facilities
 7. reliance upon generic arithmetic
 8. reliance upon non-standard i/o procedures,
    notably delete-file and file-exists?
 9. reliance upon implementation-specific extended
        domains for standard procedures

The draft R6RS addresses the first two of those by
mandating the extension. It addresses the third by
forbidding almost all extensions to lexical syntax.
It addresses the fourth through sixth by mandating
specific record, library, and macro facilities that
were missing from the R5RS. The draft R6RS addresses
the seventh problem in the list above by mandating
the full tower of generic arithmetic.

The draft R6RS does not address the eighth problem
listed above.

Finally, the draft R6RS attempts to address the last
problem in the list above by forbidding extensions
to the domains of most standard procedures. It does
this by mandating a programmable exception facility,
and by requiring most of the standard procedures to
raise a &violation exception when their arguments lie
outside the specified domain. Portable programs can
rely on these exceptions being raised, and can handle
them in portable ways, which means an implementation
cannot ignore this aspect of the draft R6RS without
breaking portable programs.

By forbidding extensions to the domains of standard
procedures, the draft R6RS has made the precise
specifications of those domains more important than
they were in the R5RS. Furthermore the draft R6RS
made it more important to distinguish between the
responsibilities of programmers, who use standard
procedures, and the responsibilities of those who
implement the standard procedures.

In my view, the draft R6RS does not do a good job
of distinguishing between the responsibilities of
programmers and implementors. In my imagination,
some part of this failure derives from imagining
that the error situations of the R5RS, which occupy
the no-man's land between the boundary of portable
code (for which programmers are responsible) and
the boundary of errors that must be signalled (for
which implementors are responsible) could be
eliminated by specifying the domains of standard
procedures in so much detail that portable code
can rely on the entire domain, and can also rely
on an exception being raised whenever arguments
lie outside that domain. In reality, that degree
of coincidence between the domain of specification
and the complement of the domain of exception
can be achieved only for simple domains.

There are inescapable reasons, both theoretical
and practical, for wanting to have a gap between
the domain for which portable code can reliably
expect no exception to be raised and the domain
for which portable code can reliably expect an
exception to be raised. I intend to make a formal
comment on this matter before the six months are
up. In this message, it should suffice to explain
this point by example, and to imagine only the
consequences for portability.

Consider the map procedure. According to the R5RS,
the arguments to map must be lists, and they must
all have the same length. In code that is intended
to be portable, it is therefore the responsibility
of the programmer to ensure that all of the arguments
are (proper) lists and that they all have the same
(finite) length.

According to the R5RS, it is an error for map to
be passed arguments that are outside its specified
domain. That means R5RS-conforming implementations
are *not* required to detect the error of passing
a circular or improper pseudo-list to map, or to
detect the error of passing true lists that aren't
of the same length. It also means that SRFI-1 can
extend the domain of map to allow the lists to have
unequal length, and to allow circular pseudo-lists
as arguments so long as at least one argument is a
true list, without being in conflict with the R5RS.

The popularity of SRFI-1 thus created a portability
problem. Portable R5RS code cannot rely on SRFI-1
semantics, because R5RS-conforming implementations
are allowed to signal the error of passing non-lists
to map, and to signal the error of passing lists of
unequal length to map. Nonetheless the specification
of SRFI-1 clearly encourages clients of SRFI-1 to
write such non-portable code.

I can imagine several different guiding philosophies
that could be used to address this portability problem.
As usual, the simplest philosophies, which I will
characterize as follows, are the most extreme:

    R5RS Philosophy: Give the programmers simple
    but weak guarantees about the domain on which
    implementations are guaranteed to work. Give
    the implementations a great deal of discretion
    to choose which errors they will detect and
    signal.

    Maximize-the-domain Philosophy: Expand the
    domain of definition to make the procedures
    as useful as possible without compromising
    efficiency or simplicity of implementation.

    Minimize-the-domain Philosophy: Make the
    domain of definition as small as possible
    without making the procedures completely
    useless.

The R5RS follows the R5RS Philosophy, SRFI-1 follows
the Maximize-the-domain Philosophy, and (with respect
to the map procedure) the draft R6RS follows the
Minimize-the-domain Philosophy.

The draft R6RS would be easier to understand if it
were to follow the Minimize-the-domain Philosophy
consistently, but it does not. Consider, for
example, the memq procedure.

According to both the R5RS and SRFI-1, the second
argument to memq must be a list. That, at least,
is the programmers' responsibility. Implementations
have the freedom to detect non-lists or not, at their
whim. In particular, implementations are free to
detect non-list arguments only when the first argument
does not occur within the second.

Had the draft R6RS followed the Minimize-the-domain
Philosophy, it too would have required the second
argument to memq to be a list. With respect to memq,
however, the draft R6RS appears to have been guided
by a more moderate (and therefore more difficult to
understand) philosophy that resembles but is not
quite the Maximize-the-domain Philosophy. According
to the draft R6RS, the second argument to memq can be
a circular or improper pseudo-list, so long as the
first argument is found within the second, but the
second argument must be a list if it does not contain
the first argument.

The draft R6RS specification of memq is complex, and
becomes even more complex when pairs are mutable; see
the specification of memq in draft R6RS section 23.3.2.
Clearly the draft R6RS is not consistently guided by
any of the three extreme philosophies I have described
so far.

In my imagination, it is helpful to imagine yet another
philosophy by which the draft R6RS is not guided:

    Minimize-both-domain-and-exceptions Philosophy:
    Try to make the domain of definition as small as
    possible, while simultaneously making the domain
    for which exceptions are raised as small as possible.

The Minimize-both-domain-and-exceptions Philosophy is
similar to the R5RS Philosophy, and is not consistent
with the possibly imaginary goal of making the domain
of definition coincide with the complement of the domain
for which exceptions are raised. In my imagination,
that helps to explain why the draft R6RS is not guided
by it.

Having considered the four philosophies above, and
having found that the draft R6RS is not guided by any
of them, my creative imagination came up with this:

    Maximize-the-exceptions Philosophy: Make the domain
    of arguments for which exceptions must be raised as
    large as possible without making the procedures
    completely useless.

Attractive as this philosophy may be, it does not
explain the draft R6RS specification of memq. Had
the draft R6RS been designed to maximize exceptions,
memq would be required to raise an exception whenever
its second argument is not a list.

I imagine this was not required because it would have
been inefficient for memq to traverse its entire second
argument even when it finds its first argument near the
beginning of its second. Back to the imagining board,
I imagined a sixth philosophy:

    Maximize-exceptions-and-efficiency Philosophy:
    Make the domain of arguments for which exceptions
    must be raised as large as possible subject to the
    constraints that (1) checking for exceptional
    situations does not increase the asymptotic time
    required by procedures, and (2) the domain of
    arguments for which exceptions are not raised
    does not become so small as to make procedures
    completely useless.

After reading the rest of the draft R6RS, it appears
to me that the Maximize-the-exceptions-and-efficiency
Philosophy fits the facts about as well as any other
myth I can imagine. If anyone else can imagine a
working hypothesis that offers a better fit to the
observed facts, I hope they will publish it to this
mailing list.

The implications for portability should be obvious.
With the draft R6RS, programmers can write portable
code that depends upon efficient detection of
exceptional situations, and can rely upon those
situations being handled by whatever dynamic
exception handlers the portable program installs.
Assuming safe code, of course.

Furthermore programmers who attempt to write code
that depends upon non-portable extensions to the
standard procedures will find that such extensions
are few, which will make it harder to write
non-portable code. To obtain extended versions
of standard procedures, e.g. a version of map
that behaves as in SRFI-1, programs will have
to import those procedures from libraries not
specified by the draft R6RS.

Finally, I should imagine that all the portability
benefits promised by the draft R6RS depend upon its
widespread acceptance and implementation. Anything
that would increase its acceptance therefore has
the potential to increase portability. Since many
of the things that might increase acceptance might
also have some flavor of compromise about them, I
can imagine how a guiding philosophy might come into
conflict with practical portability.

Post-ultimately, I should repeat that what I have
written above is a figment of my imagination. In
particular, I am not speaking for the R6RS editors.

Will
Received on Tue Oct 03 2006 - 13:59:26 UTC