On 6/26/07, William D Clinger <will at ccs.neu.edu> wrote:
> Lynn Winebarger wrote:
> > By compile-time I take it you mean the compile-time of the top-level
> > program rather than the library as a stand-alone object.
>
> Yes, you may assume I meant the compile time of the
> top-level program. The current draft allows (but does
> not require) separate compilation, so the libraries
> might be compiled ahead of time, but this has no
> bearing on our discussion. For simplicity, we may
> assume that the top-level program and all its libraries
> are always compiled at the same time.
These statements from the beginning of chapter 6 of draft 5.95 appear to be
normative to me.
*Separate compilation and analysis* No two libraries have to be compiled at
the same time (i.e., the meanings of two libraries cannot depend on each
other cyclically, and compilation of two different libraries cannot rely on
state shared across compilations), and significant program analysis can be
performed without examining a whole program. *Independent
compilation/analysis of unrelated libraries* "Unrelated" means that neither
depends on the other through a transitive closure of imports. *Explicit
declaration of dependencies* The meaning of each identifier is clear at
compile time. Hence, there is no ambiguity about whether a library needs to
be executed for another library's compile time and/or run time. *Namespace
management* This helps prevent name conflicts.
The draft may not require an implementation compile libraries
separately, but it does appear that whatever the semantics are, compiling
separately or together must be equivalent.
As I reread these a few times, they appear to conflict. On the one
hand, "no two libraries must be compiled at the same time" implies that the
library specified in an import spec does not need to be compiled beforehand,
and that can be read as saying the imported identifiers are just parameters
to be resolved at top-level compile time.
On the other hand, it also says "the meaning of each identifier is
clear at compile time". It seems implied that it means the library compile
time. But this would go against reading imported identifiers as being mere
parameters and toward their having specific denotations at library compile
time. What's worse is that in many cases, meaningful compilation requires
macros to be known at compile time (this, too, could be deferred until
top-level compile-time, but it would make the notion of libraries being
separately compiled a hollow one).
At the very least, these issues should be clarified by the editors.
> > The only reason I can see for this assertion being implied is the
> > insistence on the "single-instantiation rule" for libraries (the root of
>
> > "multiple versions of a library not allowed"). But this could be
> > interpreted as merely forbidding the compilation of an aggregate rather
> than
> > prescribing a parameterization of the pre-compiled libraries. Is there
> > something else at work here?
>
> Yes.
>
> By "this assertion", you mean my assertion that
> libraries are compile-time parameters to the top-level
> program and also to other libraries that depend upon
> them.
Yes.
That is implied by the portability goal. If your
> top-level program is to work in both HerrScheme and
> Klepto, then it follows that your top-level program
> is parameterized to work with the wildly different
> versions of (rnrs base (6)) provided by HerrScheme
> and Klepto.
If you mean that the low-level operational semantics implemented by
the respective compilers is parameterized by the corresponding instantiation
of the low-level operational semantics of a given library, I agree. But I
don't believe that is the level at which things are meant to be portable,
either.
> While that concrete thing may be viewed as _a_ denotation of the
> > name, it surely must not be judged as _the_ denotation of the name.
>
> That concrete thing (the imported library) bears the
> same relationship to the name used to refer to it in
> the importing program that an actual parameter bears
> to the formal parameter of a lambda expression.
I disagree, at least with the notion of "the imported library" as you
use it.
I am talking about the denotational semantics that the standard should be
trying to (at least informally) specify. You appear to be talking about the
low-level operational semantics to which a compiler translates. Of course
that varies wildly by implementation. One deficiency of Scheme (and every
programming language) is that there is no safe way to specify low-level
operational semantics using the higher-level semantics. AFAIK, that is a
research problem. I don't think the draft even attempts to address this
issue, which is what you appear to be waving around as a red flag here. The
source code for the base libraries is very likely to be written in a way
that is inherently not portable.
Perhaps I should have strictly limited myself to programs written in the
base language?
> When discussing (lambda (x) (+ x 1)), we do not say
> 13 is _the_ denotation of x. You (not I) raised the
> subject of denotational semantics, which I happen to
> understand fairly well.
I know that.
In denotational semantics,
> the denotation of x is a function from environments
> to stores to expression continuations to answers, or
> something like that. In like manner, the denotation
> of a library is an extremely complex higher-order
> thing, much hairier than the denotation of x.
Yes, it is, and to the extent the standard is too vague for experts to
come to a common denotational semantics for this fundamental part of the
language proposed by R6RS, the draft falls short of a proper "standard."
> In like manner, when speaking informally, as we were,
> the name (rnrs base (6)) has no informal denotation
> until a concrete thing is supplied as parameter to the
> top-level program or library that imports (rnrs base (6)).
Where in the draft is this specified?
> By
> > creating a document called a "standard", a reasonable person would
> conclude
> > that there is _some_ intended (though perhaps inconsistent!)
> denotational
> > semantics through which any implementation should be expected to factor.
> > The well-specified-ness/consistency of that semantics may be in some
> doubt,
> > but failure even to intend something in this regard should disqualify
> the
> > document from being a "standard". If there is no intended semantics
> > whatsoever (even where the English has a plain meaning), then there is
> no
> > way to judge correctness of an implementation - all is permissible!
>
> No. The specification of + describes the kinds of
> arguments it accepts, and specifies its behavior
> on those arguments (with some leeway for inexact
> arguments). Similarly, a top-level program or
> library that imports (rnrs base (6)) is specifying
> the names it expects that library to supply, and
> the behavior of those names. Those expections are
> spelled out in the draft's specification of the
> (rnrs base (6)) library.
I really don't know why we seem to be disagreeing. In formal comment
87, you said:
The reports on Scheme amount to informal axiomatic specifications of
the language. Programmers can rely on any behavior that is implied by
the axioms, and cannot rely on any behavior that is not implied by the
axioms. Implementations of Scheme must satisfy the axioms, but may
exhibit arbitrary behavior for situations not covered by the axioms.
In model-theoretic words, an implementation is a model of the
axiomatic specification (not the other way around). The Scheme reports
are like the axioms of group theory or point set topology---and unlike
the axioms of Euclidean plane geometry or the second order axioms of
Peano arithmetic---in that they are intended to describe many models
(implementations), not just one.
Portable programs must rely only on behaviors that are guaranteed by
the axioms. One of the main reasons it has been so difficult to write
portable programs in Scheme is that the axiomatic specifications
expressed by previous reports were too weak. It is appropriate for the
R6RS to strengthen those specifications.
This is very much what I have been trying to express about the standard
informally specifying a denotational semantics.
An extremely important part of that specification
> that is only implicit in the draft R6RS is that all
> of the standard libraries are consistent. For
> example, HerrScheme's (rnrs base (6)) library is
> consistent with HerrScheme's (rnrs lists (6))
> library, and Klepto's (rnrs base (6)) library is
> consistent with Klepto's (rnrs lists (6)) library,
> but all bets are off if you try to run your program
> with HerrScheme's (rnrs base (6)) library and
> Klepto's (rnrs lists (6)) library. Implementors
> understand that it is their responsibility to keep
> you from doing that by accident, but you might be
> able to do it on purpose in some systems. That
> would be like passing a symbol as an argument to
> + to see what would happen.
>
> The above, of course, is already a simplification.
> Klepto might have three dozen different versions
> of its (rnrs base (6)) library, with another dozen
> versions of its (rnrs lists (6)) library, so the
> consistency issue arises even within a single
> implementation. Again, implementors worry about
> this so you won't have to.
>
> > > If the R6RS is anything other than a complete flop, then
> > > there will be multiple implementations of all standard
> > > libraries. With the current draft R6RS, these multiple
> > > implementations would all have to have the same name
> > > *and* the same version, but most of them would be wildly
> > > incompatible.
> >
> > On a binary level, yes, but that is irrelevant.
>
> No, I was talking about different versions at the
> source level.
The sources you are talking about are not in the base language of
Scheme. They are in a Scheme augmented with implementation-specific
operators and macros that interact with the low-level semantics implemented
by the implementation. When dealing with a source language such as these,
we might as well be talking about "on a binary level" for, as you have
pointed out, they are surely tied to the specifics of the low-level
semantics which are parameterized by the machine's operational semantics,
allocator/collector scheme, continuation representations, closure
representations, etc.
Lynn
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://lists.r6rs.org/pipermail/r6rs-discuss/attachments/20070627/fde94b2c/attachment-0001.htm
Received on Wed Jun 27 2007 - 11:35:21 UTC