[R6RS] Ticket #110: Remove double phase semantics

[William D Clinger]

This message expands upon the concerns raised by the formal
comment described in Ticket #110: "Remove double phase semantics"
[1].

I too am concerned about the difficulty of writing portable
code when implementations are allowed to implement libraries
by using separate bindings for each phase and are allowed to
distinguish invocations of a library across different phases.

The problem involves an interaction between syntax-case macros
(or syntax-rules macros that use fenders) and libraries that
maintain a central registry of some sort; examples include
(r6rs base), which defines string->symbol; (r6rs records *),
which presumably maintain some sort of mapping from symbols
to non-generative record types; and all libraries that define
new record types, whether generative or non-generative (because
non-generative records depend upon the registry that maps
symbols to non-generative record types, which depend in turn
upon the symbol registry).  Examples of libraries that define
new record types include the R6RS reference implementations
for arithmetic, conditions, i/o, hash tables, and enumeration
sets.

The problem is that proper maintenance of central registries
involves a kind of allocation effect.  If an implementation
uses separate bindings for each phase, it will not preserve
the central registry across phases, and the symbols, records,
numbers, conditions, and so forth that are available at macro
expansion time will not be compatible with the symbols,
records, numbers, conditions, and so forth that exist at run
time.

Both Matthew Flatt and Andre van Tonder have confirmed that
the separate-binding semantics implies that macro-time values
cannot be compared with run-time values [2,3].  It follows
that the draft R6RS does not provide any way for a syntax-case
macro to insert a run-time value into its output [4].  In
particular, it appears to be impossible to write a portable
syntax-case macro m whose uses reliably expand into any
specific symbol or integer constant [4].  For example, the
following macro is apparently not portable under the weak
guarantees provided by the draft R6RS:

    (define-syntax m (lambda (e) 13))

According to the draft R6RS, a use of m may generate a syntax
error that complains about some #<WeirdObject> (the macro
time representation of 13) not being legal syntax (because
the run time representation of 13 is different).

This is not just a theoretical problem.  Several of the
reference implementations, including most critically the
reference implementation for generic arithmetic, define new
types.  With the draft R6RS semantics, there does not appear
to be any reliable way to write the reference implementation
for arithmetic as a set of portable R6RS libraries.

Symbols and arithmetic are more important to this discussion
than records, conditions, i/o ports, hash tables, enumeration
sets, and similar objects because symbols and numbers have
external representations and can appear as constants in the
macro-expanded code.  Scheme programmers expect their naive
attempts to insert a symbol or number into the output of a
macro to succeed; a programmer who writes the non-portable
macro shown above will be mystified by the syntax errors
he might receive.  Nonetheless, similar problems could arise
even for types that have no external representation, when a
syntax-case macro performs a comparison between values of
such types at macro time and tries to encode the value as a
number, string, or some other value that *does* have an
external representation but is not guaranteed to be
communicable from macro time to run time.

Since PLT Scheme has been using the separated binding semantics
for some time, one might ask why these problems have not been
observed in practice.  The answer, I believe, is that PLT Scheme
does not use the separated binding semantics consistently; it
escapes from that semantics by writing its basic libraries in
some other language (probably C or C++), and libraries written
in those other languages use a shared binding semantics.  In my
opinion, Scheme programmers should not have to resort to some
other programming language just to work around this misfeature
of the draft R6RS.

To fix this problem, I recommend the following.

  * Accept the recommendation of Ticket #110, and require
    implementations of R6RS Scheme to use the shared binding
    semantics.  (In addition to solving the problems explained
    in this note, requiring the shared binding semantics would
    greatly simplify the semantics of libraries and syntax-case
    macros.)

  * If there is some reason why we cannot require the shared
    binding semantics for all libraries, then we should add
    some way for libraries to declare that they must use the
    shared binding semantics, even if other libraries don't.

  * Ideally, the shared binding option would be the default,
    but it should be available as an option even if it is not
    the default.

  * If there is some reason why we cannot require the shared
    binding semantics for all libraries, and also cannot add
    some way for libraries to declare that they must use the
    shared binding semantics, then the R6RS should require
    all implementations that use the separated binding semantics
    to perform an automagical transformation of representation
    at each phase boundary, so macros like the one shown in this
    note will be guaranteed to work as programmers expect.

  * Requiring that automagical transformation would not be
    enough to make portable libraries possible in general,
    but it might become possible to write portable libraries
    provided they don't define any record types.

  * If there is some reason why we cannot require any semantics
    that makes macros like the one shown in this note work as
    programmers expect, then we should drop syntax-case macros
    from the report.

Will

[1] http://lists.r6rs.org/pipermail/r6rs-discuss/2006-November/000730.html
[2] http://lists.r6rs.org/pipermail/r6rs-discuss/2006-November/001176.html
[3] http://lists.r6rs.org/pipermail/r6rs-discuss/2006-November/001186.html
[4] http://lists.r6rs.org/pipermail/r6rs-discuss/2006-November/001194.html