Scheme Language Standardization Process: R6RS Progress Report

I am pleased to announce that the Scheme Language Editors Committee
has produced its first progress report. This report details the
progress made from appointment of the committee in January, 2004,
through its meetings at ICFP in September, 2004.

The progress report can be found at

http://www.schemers.org/Documents/Standards/Charter/

The Steering Committee has also made some small amendments to the
Charter. The updated charter can be found at the same location.

The members of the Scheme Language Editors Committee are:
Marc Feeley, editor in chief (Universite de Montreal)
Will Clinger (Northeastern University)
Kent Dybvig (Indiana University)
Matthew Flatt (University of Utah)
Richard Kelsey (Ember Corporation)
Manuel Serrano (INRIA)
Michael Sperber (DeinProgramm)

The members of the Scheme Language Steering Committee are:
Alan Bawden (Brandeis University)
Guy L. Steele Jr. (Sun Microsystems)
Mitch Wand (Northeastern University)

For the Steering Committee,
--Mitch Wand

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Cool!

I noticed that a module system is one of the top priorities for R6RS. How is it going to be specified? Specifically, are you guys going to write up an operational semantics for Scheme and specify the module system in terms of that? Or are you going to use a portable implementation of the module system as the spec?

Looks like a change for the good so far

Wondering, though, why express define in terms of letrec*? It seems simpler to express define as a primitive and not as a semantic equivalent to a less readily-understood operator. This is just considered from an instructional standpoint, but Scheme being an instructional language, I would consider such things important, myself.

Still, not a lot of changes in here I'd disagree with. Not like Java 1.5^H^H^H5.0 (although generics are needed, I wish there were a better syntax for it in the language)

Good work, everyone!

It's *internal* defines that are at stake

It certainly makes sense to make top-level define a primitive; it's the internal defines that the proposal is addressing. This is one of the little details of Scheme that has always baffled me a bit-- the meaning of a define form is different depending on whether there is an enclosing scope or not.

How the inner define got its tail

This is one of the little details of Scheme that has always baffled me a bit-- the meaning of a define form is different depending on whether there is an enclosing scope or not.

It's those (ex-)Lispers and their love of puns. :)

The most obvious alternative, especially w.r.t. Lisp, would have been to have "internal" defines affect the global environment, exactly the way top-level defines do. I'm sure that was considered inappropriate for a language in which lexical scope is so central.

If that possibility is ruled out, the remaining alternatives mostly don't behave exactly like top-level defines. An "extreme" solution would be to rewrite each scope into a single letrec*, so that the ability to intersperse DEFINEs and other expressions is possible within a scope, just as at top level. (You'd also need an extension to allow names to be re-DEFINEd.) But the end goal of such a change is essentially to allow the lexical structure of programs to be obscured, so again, this doesn't seem very appropriate for Scheme -- or at least certainly not for the standard, lexical-scope-oriented core.

Modules vs. SYNTAX-CASE

I have the very highest respect for the people who populate both the steering committee and the editors committee, but I have a nagging doubt about the whole process. Namely, AFAIK the technical work that needs to be carried out to be in a position to decide both what the right module system and the right macro system for scheme has not yet been carried out.

In particular, on the merits as they appear to me:
1. It seems to me that SYNTAX-CASE has the right blend of hygiene and expressiveness for the macro system, and whatever macro system R6RS gives should be compatible with a SYNTAX-CASE-like mechanism;
2. The scheme48 module system, although lacking in certain pieces of desirable expressiveness, possessed, say, by the PLT system, gives valuable guarantees through its separation of configuration language and programming language (see Rees' PhD thesis for some of these benefits, I also think it solves a thorny problem that came up on the rrrs-authors list), which the R6RS module system should emulate;
But:
3. The scheme48 module system is, on the face of it, incompatible with SYNTAX-CASE in a fundamental way.
Until we know the right way to introduce SYNTAX-CASE-like functionality into a Scheme with an S48-like module system, I think finalising the module system is premature.

POSTSCRIPT: I created a CLiki page on syntax-case that maybe of interest here.

What's the report to be called?

What do we call the Revised R6RS Status report? The RR6RSS report? :->

Module standardization

Certainly, I am no expert on this subject so please correct me when I'm wrong. That being said, I am confused about this report, and the fact that it focuses primarily on the goal of a standardized module system.

Could someone explain how the module system belongs in the language specification, when from here it seems that a module system is implementation dependant?

Is the goal to not only standardize the language, but also to define the One-True Scheme Interpreter?

I am certain, I am missing the obvious on this one.

Oh, also, how can (force) and (delay) be move out of the language core, and into a library? Don't those need to be language primitives, since (delay) creates a promise (which I thought needed to be a primitive type)?

There is definitely obvious u

There is definitely obvious utility to having a standardized module system. There is no particular reason why modules are implementation dependant; but having a standard module system is vital to portability as well as general sanity.

re: force and delay, (delay x) is equivalent to (lambda () x), and (force (delay x)) is just ((lambda () x))

careful

(delay x) is equivalent to (lambda () x), and (force (delay x)) is just ((lambda () x))

(BTW, you probably want a metavariable like exp in place of x there, to be clear that it's the result of applying delay to an arbitrary expression, not a variable.)

That's an implementation that will simulate the behavior of promises, but it does not distinguish promises from thunks. For example, (procedure? (delay exp)) will evaluate to #t, and this representation doesn't provide a clear implementation of promise?.

To be able to define promises well as a derived form, you actually want not just macros but also the ability to define new, disjoint data types. For example:

(define-struct promise (contents))
(define-struct memo (value))

(define-syntax delay
  (syntax-rules ()
    [(delay exp)
     (make-promise (lambda () exp))]))

(define (force p)
  (let ([contents (promise-contents p)])
    (cond
      [(memo? contents)
       (memo-value contents)]
      [(procedure? contents)
       (set-promise-contents! p (make-memo (contents)))
       (force p)]
      [else
       (error 'force "broken promise")])))

That's not something you can do in R5RS, because there's no way to create disjoint data types.

Actually...

R5RS doesn't require promise? to be implemented, and I don't think it requires a promise to be a distinct data type, but it does require semantics that aren't fulfilled by either your implementation or the one in the post you're replying to.

The simplistic implementation re-computes the calculation for every force, which is inefficient and incorrect for any useful definition of delayed evaluation.

Your version doesn't quite satisfy R5RS, either. R5RS requires that all invocations of force on the same promise evaluate to the result of the one that completes first, even if the invocations are recursive.

Your implementation could be fixed by replacing the form (set-promise-contents! ...) with:

(let ((result (contents)))
  (if (procedure? (promise-contents p))
      (set-promise-contents! p (make-memo result))))

Re: Actually

R5RS doesn't require promise? to be implemented, and I don't think it requires a promise to be a distinct data type...

My point is simply that R5RS is unspecific enough that you can implement promises in several ways, and in fact a robust implementation requires facilities that are not part of the standard. Jeff's post describes delay and force as "equivalent" to the procedural representation; my point is that the procedural representation is only a particular implementation technique.

Your version doesn't quite satisfy R5RS, either.

Oops! Quite right. As the following example demonstrates:

(let ([g 0])
  (letrec ([a (delay (begin (set! g (+ g 1))
                            (if (>= g 10)
                                g
                                (begin (force a)
                                       42))))])
    (force a)))

The result should be 10, not 42, because the innermost application of (force a) should be the first to memoize its result and no others should clobber it. Thanks for the correction.

Being picky, but (force (dela

Being picky, but (force (delay x)) is x, not (lambda () x).

Why Scheme is not my favorite programming language.

He said ((lambda() x)) not (lambda() x). Not being sufficiently scheme-literate, I think but am not sure that this evals in two stages to (x) and then to whatever x was bound to.

((lambda () x))

((lambda () x)) applies (lambda () x) to no arguments, evaluating to x.

Module system needed

By specifying a module system in R6RS, there will be a way of writing portable code that is structured by means of modules. This is desperately needed. SLIB provides more-or-less portable workarounds for module structure, but it's really not good enough.

Agreeing on a module system will cause a lot of pain though, since it is bound to be incompatible with a lot of code out there.