[r6rs-discuss] [Formal] Allow compilers to reject obvious violations

From: William D Clinger <will>
Date: Sun Feb 25 17:18:58 2007

I am posting this as an individual member of the Scheme
community. I am not speaking for the R6RS editors, and
this message should not be confused with the editors'
eventual formal response.

Pascal Costanza wrote:
> Just for clarification: What does it mean that the program is "not
> allowed to begin execution"? Does this mean that it would not be
> valid to implement R6RS as a plain metacircular interpreter, without
> performing some additional syntactic check beforehand, that is?

The language described by the draft R6RS cannot be
implemented by a pure interpreter (*). Lexical checking,
macro expansion, syntax checking, bound-variable checking,
and immutability checks are required before any part of a
program can begin its execution.

(*) The language describe by the draft R6RS cannot be
implemented, period, but that is presumably the result
of mistakes in the draft. The fact that the language
cannot be implemented by a pure interpreter appears to
have been deliberate.

While I'm at it, let me respond to Marcin 'Qrczak' Kowalczyk,
who wrote:
> I believe there should be defined a set of potential programs, called
> e.g. statically valid programs, such that:
>
> - It includes all programs which are intuitively correct.
>
> - It's easy to determine whether a program is statically valid,
> without running it.
>
> - A conforming Scheme implementation must accept all statically valid
> programs, and it must reject all programs which are not statically
> valid (modulo implementation extensions, resource constraints etc.).

That's a great idea, but it isn't implementable in a
useful way. You can't check the syntax until after
macro expansion, and you can't decide whether macro
expansion will terminate; hence you can't accept all
statically valid programs while rejecting all that
are not (unless you adopt some trivial definition of
statically valid, such as that all lexically correct
datums are statically valid programs).

The obvious way to repair the idea is to define the
notion of "statically valid" only for macro-expanded
programs. Here we run up against a technical detail:
the language in which macro-expanded programs are
expressed is explicitly left undefined by the draft
R6RS.

The formal semantics basically ignores this problem,
but defines its own language that could be regarded
as a proper superset of the language in which programs
are represented after macro expansion. The draft R6RS
could then require implementations to represent the
result of macro expansion in a way that can somehow
be related to the language assumed by the formal
semantics, and the notion of statically valid could
be defined on an appropriate subset of that language.

As a beneficial side effect, this approach would make
it possible for the semantics of macro expansion to be
defined more precisely.

Will
Received on Sun Feb 25 2007 - 17:18:55 UTC