[Larceny-users] Ticket 638

[William D Clinger]

Aziz Ghuloum quoting me:
> > It appears to me that Andre van Tonder and Aziz Ghuloum
> > agree implementations are allowed to raise an exception
> > for that test
> 
> I actually don't know.

I apologize for mischaracterizing your position.  For
reasons explained below, I still think it was best to
remove the controversial test.

> It's not clear to me from the
> description of free-identifier=? in the report that it
> is allowed to raise any exception given that its two
> arguments are indeed identifiers.  Can you point it out?

Although the R6RS documents are quite vague concerning
the semantics of identifiers and phase levels, and the
vagueness was partly deliberate, they do contain a few
statements that can be interpreted in favor of one
argument or the other.

The following paragraph of R6RS 7.2 appears to suggest
that one purpose of negative phases is to require the
phase of an identifier to be used only at some shifted
phase, and the word "must" suggests that implementations
that support negative phases for this purpose are
allowed, or arguably required, to raise exceptions if
there is a phase mismatch:

    Macro expansion within a library can introduce a
    reference to an identifier that is not explicitly
    imported into the library.  In that case, the phase
    of the reference must match the identifier's level
    as shifted by the difference between the phase of
    the source library (i.e., the library that supplied
    the identifier's lexical context) and the library
    that encloses the reference.  For example, suppose
    that expanding a library invokes a macro transformer,
    and the evaluation of the macro transformer refers to
    an identifier that is exported from another library
    (so the phase-1 instance of the library is used);
    suppose further that the value of the binding is a
    syntax object representing an identifier with only a
    level-n binding; then, the identifier must be used
    only at phase n + 1 in the library being expanded.
    This combination of levels and phases is why
    negative levels on identifiers can be useful, even
    though libraries exist only at non-negative phases.

Two paragraphs later, R6RS 7.2 explicitly says that
implementations are allowed to raise exceptions when
there is a phase mismatch:

    When an identifier appears as an expression in a
    phase that is inconsistent with the identifier's
    level, then an implementation may raise an exception
    either at expand time or run time, or it may allow
    the reference.

That reduces the question to one of whether the R6RS
was actually meant to allow the particular phase levels
implemented by Andre van Tonder's macro expander.

In the full text of Andre's message that was truncated
by a Mailman bug, he quoted R6RS 7.2 [1]:

    A level is a lexical property of an identifier that
    determines in which phases it can be referenced.

Andre went on to say:

> In the absence of a definition of what it means to
> "reference" an identifier (despite a formal comment by
> me on this precise point, asking for clarification,
> that was ignored), and whether literal uses count as
> identifiers, the interpretation assumed by the
> expander in Larceny is just as valid as any other.

I am not certain of the formal comment to which Andre
is referring, but the R6RS editors' response to Andre's
formal comment 92 states [2]:

    ....A precise specification of the library system
    remains elusive, partly because different
    implementors still have different ideas about how
    the library system should work....

    The different opinions are supported by two
    different reference implementations of R6RS
    libraries: one by Van Tonder and one by Ghuloum and
    Dybvig.  In addition, PLT Scheme implements a
    library system...

    Despite the differences in the reference
    implementations, it appears that many programs will
    run the same in both variants of the library system.
    The overlap appears to be large enough to support
    practical portability between the variants.

    Under the assumption that the overlap is useful, and
    given the lack of consensus and relative lack of
    experience with the two prominent variants of draft
    R6RS libraries, the R6RS specification of libraries
    should be designed to admit both of the reference
    implementations.  As a design process, this
    implementation-driven approach leaves something to
    be desired, but it seems to be the surest way forward.

I would not argue that the R6RS editors had this particular
issue in mind when they made those remarks, but it is clear
that (1) they wished to allow different implementations
that reflect different opinions, (2) they regarded the
overlap between van Tonder's system and others as "large
enough to support practical portability", and (3) they
felt that the R6RS specification should admit van Tonder's
reference implementation.

In response to Andre's formal comment 135, which requested
a less operational description that would clarify the
distinction between accidental properties of the expansion
algorithm described by the R6RS document and the properties
that were meant to be required of actual implementations,
the editors noted that the operational description "is not
incompatible" with whatever semantics they were attempting
to express [3].

In my opinion, the editors' response to formal comment 135
signalled their intention to stay out of the business of
specifying corner cases that have little relevance to
practical portability.

Note also that the editors' response to formal comment 135
effectively declined to consider Andre's implementation
non-conformant, which was an alternative that Andre had
explicitly offered as part of his formal comment.

The specifications of the syntax special form and of the
free-identifier=? procedure that appear within R6RS library
section 12.4 and 12.6 are amazingly unhelpful, partly due
to the operational flavor of the specifications that Andre
had complained about in formal comment 135.  Neither says
anything about phase levels, even though the syntax special
form is said to be analogous to the quote special form,
which is generally believed to have the following genuinely
radical interaction with phase levels: it ignores them and
converts identifiers into symbols.

Of course, the R6RS specification of quote says no such
thing.  An R6RS-conforming implementation could presumably
arrange for quoted identifiers to evaluate to identifiers,
not to symbols.  The apparent fact that legalistic reading
of the R6RS would allow such implementations illustrates
the folly of demanding that implementors justify every
corner case by citing chapter and verse of the R6RS.  At
some point, we just have to rely on our interpretations
of what the editors were attempting to say.

With respect to the semantics of macro expansion and
associated features such as syntax and free-identifier=?,
it is a matter of record that the R6RS editors knew their
semantics was ambiguous, and that one of the reasons for
the ambiguities was that they wished to allow Andre van
Tonder's reference implementation.

The non-binding, largely unvetted, and never-ratified
R6RS rationale section 7.5 supports that interpretation:

    Opinions vary on how libraries should be instantiated
    and initialized during the expansion and execution of
    library bodies, whether library instances should be
    distinguished across phases, and whether levels should
    be declared so that they constrain identifier uses to
    particular phases.  This report therefore leaves
    considerable latitude to implementations, while
    attempting to provide enough guarantees to make
    portable libraries feasible.

Characteristically, the very next paragraph undermines
that statement by making what appears to be a factually
incorrect claim:

    Note that, if each right-hand side of the keyword
    definition and keyword binding forms appearing in a
    program is a syntax-rules or identifier-syntax form,
    syntax-rules and identifier-syntax forms do not appear
    in any other contexts, and no import form employs for
    to override the default import phases, then the program
    does not depend on whether instances are distinguished
    across phases, and the phase of an identifier's use
    cannot be inconsistent with the identifier's level.

If that were true, then a program that uses syntax-case
only as a top-level expression, outside of any binding
form, and satisfies the other conditions, could not have
phasing errors.  That's nuts.  I think it's pretty clear
that the R6RS editors mostly thought about syntax forms
as things that would never be used except in connection
with a syntax-case form.  I also suspect that's part of
why the R6RS doesn't give a coherent semantics for the
syntax special form when used at level 0.

Aziz wrote:
> Now just because Chez and MzScheme disagree on something
> (as they often do) does not by itself justify for a third
> implementation to raise an exception (despite the good
> intentions).  Otherwise, it would be okay for, say, Ikarus
> to raise an exception when asked (fixnum? 536870912) on
> the ground that any program that's blessed by it will be
> maximally portable.  Right?

Wrong.  The specification of fixnum? unambiguously states
that it returns #t or #f.  Furthermore the R6RS definition
of fixnums explicitly refers to an implementation-dependent
range, so the implementation-dependence was deliberate and
anticipated.

The R6RS clearly says that implementations may raise
exceptions when identifiers are used inconsistently with
their level.  That phase levels are at least partially
implementation-dependent is alluded to within the R6RS
documents, and is even more clearly attested by the
historical record.  The R6RS editors have stated several
times that this lack of clarity was partially deliberate,
and was motivated in part by a desire to allow a variety
of implementations.  Furthermore, they explicitly named
van Tonder's reference implementation as one they wished
to allow.

Andre and I may be wrong about what the R6RS documents say
about this, but I have now wasted enough time on this to
believe that the burden of proof lies with those who wish
to maintain that the R6RS forbids Larceny's behavior on
that test case.  Even if that were so, it is such a bizarre
corner case that I do not foresee any practical consequences
that would be likely to result from leaving such a thing
unfixed, and would probably be inclined to leave it unfixed
in Larceny until such time as the R6RS is superseded by some
other standard.

Will


[1] http://lists.ccs.neu.edu/pipermail/larceny-users/2009-April/000649.html
[2] http://www.r6rs.org/formal-comments/comment-92.txt
[3] http://www.r6rs.org/formal-comments/comment-135.txt