Received: from void (TCP 2206400236) by MC.LCS.MIT.EDU 11 Jul 88 12:28:05 EDT
Received: by VOID.AI.MIT.EDU; Mon, 11 Jul 88 12:27:28 edt
Date: Mon, 11 Jul 88 12:27:28 edt
From: jar@VOID.AI.MIT.EDU (Jonathan Rees)
Message-Id: <8807111627.AA09064@void>
To: willc%tekchips.crl.tek.com@relay.cs.net
Cc: hal@VOID.AI.MIT.EDU, rrrs-authors@mc.lcs.mit.edu
Subject: duplicated formals
Reply-To: JAR@ZURICH.AI.MIT.EDU

Proposed:

The list of formal variables in LAMBDA, LET, LETREC, and DO (but not
LET*) should not contain duplications.  E.g. (LAMBDA (X Y X) ...) is
illegal.

In the case of named LET, the formals in the initial bindings list
should be distinct, but it's OK (useless, however) if the "name"
is also a formal.  E.g., (LET FOO ((X 1) (FOO 2)) ...) is legal.

Rationale: the constraints on the derived expression types should all
derive from the primitive expression type (namely LAMBDA) from which
they derive.

Received: from iuvax.cs.indiana.edu (TCP 30003147300) by MC.LCS.MIT.EDU 10 Jul 88 17:03:36 EDT
Received: by iuvax.cs.indiana.edu; id AA19175; Sun, 10 Jul 88 15:36:50 EST
Received: by iuvax.cs.indiana.edu (5.54/1.5) 
Date: Sun, 10 Jul 88 15:36:50 EST
From: Chris Haynes <chaynes@iuvax.cs.indiana.edu>
To: rrrs-authors@mc.lcs.mit.edu
Subject: Re: Multiple values, Version 1

Subject: Re: Multiple values, Version 1

It would be clearer if

    Most continuations ignore all but the first return value, ...

read instead

    Most continuations expect one value and ignore all but the first of
    multiple values, ...

Also, it would help if there were an example that makes clear the relation
between tail-recursion and multiple values, such as:

    (define return123 (lambda () (values 1 2 3)))
    (with-values (lambda () (return123)) list) ==> (1 2 3)


I also second the proposal to make <init>s optional in
LET, LET*, named LET, and LETREC (but not DO).

Received: from chamarti (TCP 2206400253) by MC.LCS.MIT.EDU  8 Jul 88 01:41:21 EDT
Received: by CHAMARTIN.AI.MIT.EDU; Fri, 8 Jul 88 01:39:53 edt
Date: Fri, 8 Jul 88 01:39:53 edt
From: jinx@CHAMARTIN.AI.MIT.EDU (Guillermo J. Rozas)
Message-Id: <8807080539.AA07652@chamarti>
To: hieb@iuvax.cs.indiana.edu
Cc: rrrs-authors@mc.lcs.mit.edu, jinx@CHAMARTIN.AI.MIT.EDU
In-Reply-To: Robert Hieb's message of Fri, 24 Jun 88 09:26:39 EST
Subject: informal proposal: A Modified Procedural Interface (LONG)
Reply-To: jinx@zurich.ai.mit.edu

I think your proposal for variable arity procedures is quite neat, but
it suffers from some problems that we have observed at MIT with our
current optional argument extension.  The most noticeable, which
motivated the "default objects" in Will's proposal, arises from cases
like

(define (make-bracket-unparser core)
  (lambda (object #!optional port radix)
    (write-char #\[ port)
    (core object port radix)
    (write-char #\] port)))

which in the context of your proposal would be written as

(define (make-bracket-unparser core)
  (lambda*

      ((object)
       (write-char #\[)
       (core object)
       (write-char #\]))

      ((object port)
       (write-char #\[ port)
       (core object port)
       (write-char #\] port))

      ((object port radix)
       (write-char #\[ port)
       (core object port radix)
       (write-char #\] port))))

There is a lot of replicated code, and it only gets worse when there
are more "optional" parameters whose values the programmer wants to
default in the procedures invoked.


A related problem is that it is hard to default "intermediate"
parameters.  For example, it is cleaner (I think) to write

((make-bracket-unparser write-number-heuristically)
 23
 (make-default-object)		; = ((lambda (#!optional x) x))
 #x10)

than to write

((make-bracket-unparser write-number-heuristically)
 23
 (current-output-port)
 #x10)

since the latter has only the desired effect if in fact the default
port is the value of (current-output-port).

In other words, the proposal with default objects allows specification
of only those parameters for which we do not want to use the default,
while your proposal forces the user to specify all parameters to the
LEFT of those which s/he REALLY wants to provide.  This is a serious
breach of abstraction, since s/he must know which way these parameters
are defaulted in order to obtain the same effect as if they had not
been provided.


Some other comments with respect to your proposal and your message:

1) You mention that the same objections that hold for returning
multiple values in a list should hold for passing "multiple arguments"
in a list, but you are really confusing two issues here.

One issue is whether the argument passing mechanism and the value
return mechanism (which is merely passing arguments to the
continuation) inherently involves lists, and the answer to this should
clearly be no.  Returning a fixed number of values to a continuation
expecting that number of values should not be very different from
passing a fixed number of arguments to a procedure expecting that
number of arguments.  Implementations are free to use lists of values
(and lists of arguments), but this fact should not be apparent to the
user.

The other issue is how to RECEIVE (by a procedure or a continuation)
arbitrary numbers of values while providing a fixed finite list of
formal parameter names.  Lists happen to be convenient and natural
data structures to "bundle up" many objects into a single object from
which the individual objects can be extracted, yet allowing simple
manipulation of the aggregate.  Many other data structures would do
nicely, but lists are (arguably) the most appropriate for Lisp.


2) Introducing multiple-value locations, and in particular, making
assignment work "correctly" with them makes the implementation of
variables in the language considerably less efficient.  Consider
carefully the implications of the following ugly fragment of code:

(let* ((x 'unspecified)
       (test
	(lambda ()
	  (if x
	      'yes
	      'no)))
       (first
	(begin (set! x 4)
	       (test)))
       (second
	(begin (set! x (mumble))
	       (test))))
  (list first second))

under the following possible definitions of mumble not available at
compile time

;; version 1

(define (mumble)
  3)

;; version 2

(define (mumble)
  (values 3 4))


3) I agree with you that programmers can incur a substantial
algorithmic cost by carelessly using lists in procedures expecting an
arbitrary number of arguments.  For example,

(define plus
  (lambda all
    (if (null? all)
	0
	(binary-plus (car all)
		     (apply plus (cdr all))))))

is quadratic in space (and therefore time), but any clever programmer
will realize that this is a bad program and rewrite it to be linear.

However, the equivalent program

(define plus
  (lambda*
      (() 0)
      ((x & rest)
       (binary-plus x (plus & rest)))))

will probably also be quadratic in space (and time), but it is much less
obvious how to rewrite it to avoid this cost.  To obtain linear
behavior the programmer must rely on a clever implementation (which I
haven't discovered) and is helpless if the implementation is not
clever enough.

Received: from iuvax.cs.indiana.edu (TCP 30003147300) by MC.LCS.MIT.EDU  7 Jul 88 22:26:53 EDT
Received: by iuvax.cs.indiana.edu; id AA01837; Thu, 7 Jul 88 19:27:55 EST
Received: by iuvax.cs.indiana.edu (5.54/1.5) 
Date: Thu, 7 Jul 88 19:27:55 EST
From: Chris Haynes <chaynes@iuvax.cs.indiana.edu>
To: rrrs-authors@mc.lcs.mit.edu
Subject: Re: Multiple values, Version 1

Subject: Re: Multiple values, Version 1

It would be clearer if

    Most continuations ignore all but the first return value, ...

read instead

    Most continuations expect one value and ignore all but the first of
    multiple values, ...

Also, it would help if there were an example that makes clear the relation
between tail-recursion and multiple values, such as:

    (define return123 (lambda () (values 1 2 3)))
    (with-values (lambda () (return123)) list) ==> (1 2 3)


I also second the proposal to make <init>s optional in
LET, LET*, named LET, and LETREC (but not DO).

Received: from Think.COM (TCP 1201000006) by MC.LCS.MIT.EDU  6 Jul 88 18:41:15 EDT
Return-Path: <gls@Think.COM>
Received: from brigit.think.com by Think.COM; Wed, 6 Jul 88 17:45:03 EDT
Received: by brigit.think.com; Wed, 6 Jul 88 18:39:51 EDT
Date: Wed, 6 Jul 88 18:39:51 EDT
From: gls@Think.COM
Message-Id: <8807062239.AA25126@brigit.think.com>
To: willc@tekchips.crl
Cc: rrrs-authors@mc.lcs.mit.edu, willc@tekchips.crl
In-Reply-To: willc@tekchips.crl's message of 06 Jul 88 11:29:02 PDT (Wed) <8807061829.AA07253@tekchips.CRL.TEK.COM>
Subject: sanity check: <=, >=

   Date: 06 Jul 88 11:29:02 PDT (Wed)
   From: willc@tekchips.crl

   R3RS says that (<= x y) is #t if x and y are "monotonically nondecreasing"
   and that (>= x y) is #t if x and y are "monotonically nonincreasing".  I
   interpret this to mean that (<= x y) is equivalent to (not (> x y)), and
   that the following transcript shows correct behavior with respect to the
   unordered case in IEEE standard floating point arithmetic.  Comments?

   >>> (define x (expt 10.0 500.0))
   x
   >>> x
   #<INFINITY>
   >>> (define y (- x x))
   y
   >>> y
   #<NOT A NUMBER>
   >>> (< 3 y)
   #f
   >>> (= 3 y)
   #f
   >>> (> 3 y)
   #f
   >>> (<= 3 y)
   #t
   >>> (>= 3 y)
   #t


I think (<= y 3) and (>= y 3) being #f is more appealing.

(1) This is consistent with the recommended treatment of .GE. and .LE.
    by IEEE standard 754.

(2) "monotonically nondecreasing" does not mean the same thing as
    "not monotonically decreasing".  At least, I didn't think they meant
    the same thing when I put the former in CLtL.

--Guy

Received: from RELAY.CS.NET (TCP 1201000005) by MC.LCS.MIT.EDU  6 Jul 88 17:31:44 EDT
Received: from relay2.cs.net by RELAY.CS.NET id aa22662; 6 Jul 88 15:52 EDT
Received: from tektronix.tek.com by RELAY.CS.NET id aa12538; 6 Jul 88 15:34 EDT
Received: by tektronix.TEK.COM (5.51/6.24)
	id AA14086; Wed, 6 Jul 88 11:27:51 PDT
Received: by tekchips.CRL.TEK.COM (5.51/6.24)
	id AA07253; Wed, 6 Jul 88 11:29:04 PDT
Message-Id: <8807061829.AA07253@tekchips.CRL.TEK.COM>
To: rrrs-authors@mc.lcs.mit.edu
Cc: willc@tekchips.crl
Subject: sanity check: <=, >=
Date: 06 Jul 88 11:29:02 PDT (Wed)
From: willc@tekchips.crl

R3RS says that (<= x y) is #t if x and y are "monotonically nondecreasing"
and that (>= x y) is #t if x and y are "monotonically nonincreasing".  I
interpret this to mean that (<= x y) is equivalent to (not (> x y)), and
that the following transcript shows correct behavior with respect to the
unordered case in IEEE standard floating point arithmetic.  Comments?

>>> (define x (expt 10.0 500.0))
x
>>> x
#<INFINITY>
>>> (define y (- x x))
y
>>> y
#<NOT A NUMBER>
>>> (< 3 y)
#f
>>> (= 3 y)
#f
>>> (> 3 y)
#f
>>> (<= 3 y)
#t
>>> (>= 3 y)
#t

Received: from STONY-BROOK.SCRC.Symbolics.COM (TCP 20024224620) by MC.LCS.MIT.EDU 27 Jun 88 10:34:54 EDT
Received: from RIO-DE-JANEIRO.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 425028; Mon 27-Jun-88 10:24:47 EDT
Date: Mon, 27 Jun 88 10:24 EDT
From: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>
Subject: (define x)
To: rhh@VX.LCS.MIT.EDU, JAR@AI.AI.MIT.EDU
cc: RRRS-Authors@MC.LCS.MIT.EDU, KMP@STONY-BROOK.SCRC.Symbolics.COM
In-Reply-To: <880625174633.1.RHH@ASPEN.LCS.MIT.EDU>
Message-ID: <880627102432.2.KMP@RIO-DE-JANEIRO.SCRC.Symbolics.COM>

    Date: Sat, 25 Jun 88 17:46 EDT
    From: Robert Halstead <rhh@VX.LCS.MIT.EDU>

	From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>

	I would hate to see some functionality become available through define
	that was not available through letrec, so I would advise adopting
	(define x) ONLY if letrec is also extended so that
	  (letrec ((x) ...) ...)
	means
	  (letrec ((x <unassigned>) ...) ...).

	For orthogonality's sake, this should also, I believe, require
	  (let ((x) ...) ...)
	to mean
	  (let ((x <unassigned>) ...) ...),
	and similarly for let*, named let (?), and do (??).  Consider this proposed,
	and please talk me out of this madness.

    I would like to support the proposal as a perspicuous way to introduce a
    variable whose purpose in life is to be side-effected.    -Bert Halstead

That's one possible use, but another (unforunately incompatible) use also
presents itself:

This morning I heard a news announcement the Louisiana had passed a law
banning a set of "obscene" words (about five in all, I think) from appearing
on bumper stickers (except in typefaces 1/8 inch high or smaller!).

I suggest that (define <name>) introduce a variable whose purpose in life
should be to -never- be assigned or referenced in any way. That way, when
Louisiana lawmakers figure out what words are inappropriate for use in
programs, they can just DEFINE them away...

:-}

Received: from RELAY.CS.NET (TCP 1201000005) by MC.LCS.MIT.EDU 26 Jun 88 05:31:41 EDT
Received: from relay2.cs.net by RELAY.CS.NET id ac14159; 26 Jun 88 5:24 EDT
Received: from cs.brandeis.edu by csnet-relay.CS.NET id ac10120;
          26 Jun 88 5:18 EDT
Received: from mephi.earth1.com by cs.brandeis.edu (13.1/6.0.GT)
	id AA04760; Sat, 25 Jun 88 15:59:32 edt
Posted-Date: Sat, 25 Jun 88 15:59:06 EDT
Received: by mephi.earth1.com (3.2/SMI-3.2)
	id AA01231; Sat, 25 Jun 88 15:59:06 EDT
Date: Sat, 25 Jun 88 15:59:06 EDT
From: James Miller <jmiller%mephi%cs.brandeis.edu@RELAY.CS.NET>
Message-Id: <8806251959.AA01231@mephi.earth1.com>
To: willc%tekchips.crl@RELAY.CS.NET
Cc: tiedeman.2@cs.brandeis.edu, hudak-paul.2@cs.brandeis.edu, 
    hieb.2@cs.brandeis.edu, rrrs-authors.2@cs.brandeis.edu
In-Reply-To: willc@tekchips.crl's message of 17 Jun 88 13:13:40 PDT (Fri) <8806172013.AA20610@tekchips.CRL.TEK.COM>
Subject: More on Full Specification

While I agree with most of Will's comments on underspecification, I
would like to defend underspecifying the returned value of
side-effecting constructs.  I have tried to make MultiScheme a direct
extension to the RnRS standard where possible while adding as few new
special forms as possible.  By having the standard deliberately
understate the value returned by SET!  (and SET-CAR!, etc.), I have
avoided the need to introduce separate atomic swap operations for
these cases (although I do provide Halstead's more powerful
conditional side-effect operations).

I think this case again indicates the importance of
underspecification: in doing research into a new application area
(parallel programming) the deliberate underspecification allows a
legitimate alternative implementation.  Users are NOT encouraged to
use the returned value of SET! et al, but can do so when necessary for
concurrency control.

--Jim

Received: from ZERMATT.LCS.MIT.EDU (CHAOS 17316) by MC.LCS.MIT.EDU 25 Jun 88 17:47:32 EDT
Received: from ASPEN.LCS.MIT.EDU by ZERMATT.LCS.MIT.EDU via CHAOS with CHAOS-MAIL id 167575; Sat 25-Jun-88 17:46:25 EDT
Date: Sat, 25 Jun 88 17:46 EDT
From: Robert Halstead <rhh@VX.LCS.MIT.EDU>
Subject: (define x)
To: JAR@AI.AI.MIT.EDU
cc: rrrs-authors@MC.LCS.MIT.EDU
In-Reply-To: <402290.880623.JAR0@AI.AI.MIT.EDU>
Message-ID: <880625174633.1.RHH@ASPEN.LCS.MIT.EDU>

    From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>

    I would hate to see some functionality become available through define
    that was not available through letrec, so I would advise adopting
    (define x) ONLY if letrec is also extended so that
      (letrec ((x) ...) ...)
    means
      (letrec ((x <unassigned>) ...) ...).

    For orthogonality's sake, this should also, I believe, require
      (let ((x) ...) ...)
    to mean
      (let ((x <unassigned>) ...) ...),
    and similarly for let*, named let (?), and do (??).  Consider this proposed,
    and please talk me out of this madness.

I would like to support the proposal as a perspicuous way to introduce a
variable whose purpose in life is to be side-effected.    -Bert Halstead

Received: from iuvax.cs.indiana.edu (TCP 30003147300) by MC.LCS.MIT.EDU 24 Jun 88 10:28:12 EDT
Received: by iuvax.cs.indiana.edu; id AA07968; Fri, 24 Jun 88 09:26:39 EST
Received: by iuvax.cs.indiana.edu (5.54/1.5) 
Date: Fri, 24 Jun 88 09:26:39 EST
From: Robert Hieb <hieb@iuvax.cs.indiana.edu>
To: rrrs-authors@mc.lcs.mit.edu
Subject: informal proposal: A Modified Procedural Interface

This is a response to Will Clinger's optional argument and multiple return value
proposals:
   Date: Tue Jun 21 12:23:01 1988
   Subject: Optionals, version 1
   From: willc@tekchips.crl

   Date: Tue Jun 21 12:23:15 1988
   Subject: Multiple values, version 1
   From: willc@tekchips.crl

I particularly dislike the optional argument mechanism, which I find clumsy. In
response to its original appearance (following the R*S meeting last summer), I
posted a critical note.  If someone does not have a copy, I would be glad to
send it on request.  In summary, the proposed mechanism:
   complicates an already complicated lambda list,
   is aesthetically unappealing,
   is clumsy to use,
   introduces a special default value,
   does not provide error checking on (mis)use of the optional value, and
   is not simple to optimally implement.
I am just not pleased with the code that results from its use.

However, I do agree that some sort of improved optional argument mechanism is
desirable, since Scheme is committed to procedures that accept variable numbers
of arguments.  I also agree that the |.| in the argument list is a mistake, and
would like to move away from it (but don't much care for |#!rest|, or
#!anything, in fact).

Kent Dybvig and I will present a paper at the Lisp Conference this summer that
addresses both optional arguments and multiple return values (``A Variable-Arity
Procedural Interface''---also available as Indiana University Computer Science
Department Technical Report No. 247).  We had meant to let it speak first, but
perhaps it should be summarized here, now that Will has made specific proposals.
The paper is mainly concerned with variable-arity procedures, but also shows how
the mechanism can be adapted to allow multiple return values.  I have worked our
proposal into a revision of key sections of the R*S, but it spreads across so
many sections that the intent and scope of the proposal is hard to follow (not
to mention the difficulty of reading raw TEXed material).  Consequently I have
decided to post two notes: this informal (and hopefully more coherent)
discussion and the R*S revision.

It is based on two notions:
  (1) a procedure should automatically select an action based on the
      number of arguments it receives, and
  (2) procedures that accept an indefinite number of arguments and expressions
      that return multiple values can be related by allowing variables to refer
      to multiple values (more precisely, using the language of the R*S,
      allowing zero or more values to be stored in the location to which a
      variable is bound).

Our proposal depends upon the conception that there are problems with the
existing R* Scheme parameter mechanism, which sticks ``extra'' arguments in a
list.  There seems to be a widely perceived need for a better way to handle
optional arguments, so I won't argue that here.  However, there are also
problems inherent in bundling up extra arguments in a list in those cases where
a procedure may receive an indefinite number of arguments.  Our paper spends a
good deal of time on this topic, so I don't want to flog it here.  It is worth
noting, however, that arguments against using lists to return multiple values
can be turned against using lists to receive multiple arguments.  Consequently,
it is pleasing to discover that the two notions can also be related in a simple
manner.

The key idea is that variable locations may be allowed to contain multiple
values.  Referencing a multiple-valued variable simply results in the return of
its values, as with the evaluation of any other multiple-valued expression.
Extracting multiple values from a variable location or any other multiple-valued
expression is most naturally accomplished by using the procedure call mechanism,
which can extract and name the desired values.

Here is a R*S version of the syntax we proposed.  It introduces two key words,
|lambda*| and |&|, and modifies part of the R*S syntax.

   <lambda* expression> --> (lambda* <clause> <clause> ...)
               <clause> --> (<formals> <body>)
              <formals> --> (<variable> ...) |
                            (<variable> ... & <variable>)
       <procedure call> --> (<expression> <expression> ...) |
                            (<expression> <expression> ... & <expression>)

<body>, <variable> and <expression> are as in the R*S, with the addition of
<lambda* expression> to the <expression> category.  A <lambda* expression> is an
extended <lambda expression> that selects a <clause> based on the number of
arguments it receives.  Thus a <lambda expression> (without the list-interface)
may be expressed as a <lambda* expression>:

   (lambda (<variable> ...) <body>) ==> (lambda* ((<variable> ...) <body>))

|&| may be thought of as a multiple value context marker.  In a <formals>, |&|
precedes a <variable> whose location can contain zero or more values.  It will
receive whatever arguments are left over after each preceding <variable>
receives its argument (much like |.| in a <lambda expression>, except that the
values are not put into a list).  In a <procedure call>, |&| precedes an
<expression> that may return zero or more values (this may be compared to the
action of |apply|, except, once again, the values are not in a list).

The first <clause> whose formal parameters accept the actual parameters is
selected, and thereafter the binding of its <formals> and evaluation of its
<body> proceeds as for a <lambda expression>.  Each ordinary <variable> accepts
exactly one actual parameter; a <variable> following |&| accepts zero or more
actual parameters.  It is an error if no <clause> accepts the actual parameters.

Simple examples:

   (define -
      (lambda*
         ((x) (binary- 0 x))
         ((x y) (binary- x y)))))

   (define list
      (lambda*
         (() '())
         ((x & r) (cons x (list & r)))))

   (define maximum
      (lambda*
         ((x y) (if (> x y) x y))
         ((x y & r) (maximum (maximum x y) & r))))

Generalized multiple return values can be introduced by adding a |values|
primitive, as Will suggests.  We avoided introducing |values| in the paper by
letting the values of all expressions in a <body> be returned.  However that may
not be a viable solution for R* Scheme, since a <body> is considered to contain
an implicit |begin| in other contexts.  The expanded procedure call mechanism
does remove the need for introducing |with-values| as a special primitive:

   (define with-values (lambda (thunk proc) (proc & (thunk))))

We suggest that the return of other than a single value to a singular context be
an error.  It is simple enough to strip off one value if desired, and enforcing
it can only aid the clarity and correctness of programs:

   (define first (lambda* ((x & r) x)))

Of course one must decide what to do about other expressions that might receive
multiple values.  In R* Scheme, that means conditionals (|if|) and assignments
(|set!|).  It is reasonable to enforce single values for the test expression of
a conditional and allow the branches to be transparent to multiple values. 
Since variable locations can contain multiple values, multiple-valued
assignments can be allowed.  Derived forms should derive their behavior with
respect to multiple values from the behavior of their base forms.

This proposal is in the spirit of Scheme in that it adds a lot of power for a
little bit of syntax.  It is possible to stop with variable-arity procedures and
not proceed to multiple return values, but integration of the notions of
returning variable numbers of values and receiving variable numbers of arguments
is pleasing, particularly since we seem to be moving toward adopting some form
of multiple return value mechanism anyway.

Bob Hieb

Received: from iuvax.cs.indiana.edu (TCP 30003147300) by MC.LCS.MIT.EDU 24 Jun 88 10:27:45 EDT
Received: by iuvax.cs.indiana.edu; id AA07930; Fri, 24 Jun 88 09:25:37 EST
Received: by iuvax.cs.indiana.edu (5.54/1.5) 
Date: Fri, 24 Jun 88 09:25:37 EST
From: Robert Hieb <hieb@iuvax.cs.indiana.edu>
To: rrrs-authors@mc.lcs.mit.edu
Subject: formal proposal: A Modified Procedural Interface

% formal proposal: A Modified Procedural Interface
% [to provide for variable-arity procedures and multiple return values]

% See the accompanying note entitled
% ``informal proposal: A Modified Procedural Interface''
% for a more coherent discussion of the intent of this proposal.

% The following tex commands are derived from r4rs.tex.
% They allow this section to be latexed separately
% (although section numbers are lost or mutilated in the process).
% (You will still need commands.tex)

\documentstyle[twoside]{algol60}
\pagestyle{headings}
\showboxdepth=0
\input{commands}     
\def\theevenhead{Revised$^{3.5}$ Scheme}
\begin{document}
\hfil {\bf *** DRAFT --- \today{} ***}

% This is a patch to commands.tex to kill indexing for separate latexing:

\global\def\reallyindex#1#2#3{}

% The following should be added to commands.tex:

\newcommand{\lambdastarexp}{lambda* expression}
\newcommand{\Lambdastarexp}{Lambda* expression}
\newcommand{\ampersand}{{\bf \&}}

% The modifications begin at the start of chapter 3.  Unmodified sections have
% been omitted, so it must be correlated with the full report.

\chapter{Basic concepts}

\section{Variables and regions}

\label{specialformsection}

\label{variablesection}

Any identifier that is not a syntactic keyword \index{keyword} (see
section~\ref{keywordsection})  may be used as a variable. \index{syntactic
keyword}\index{identifier}\mainindex{variable} A variable may name a location
where zero or more values can be stored.  A variable that does so is said to be
{\em bound} to the location.  The set of all such bindings \mainindex{binding}
in effect at some point in a program is known as the {\em environment} in effect
at that point.  The values stored in the location to which a variable is bound
are called the variable's values. By abuse of terminology, the variable is
sometimes said to name the values or to be bound to the values.  This is not
quite accurate, but confusion rarely results from this practice.

\vest Certain expression types are used to create new locations and to bind
variables to those locations.  The most fundamental of these {\em binding
constructs} \mainindex{binding construct} is the \lambdastarexp{}
\index{\lambdastarexp{}}, because all other binding constructs can be explained
in terms of \lambdastarexp{}s. The other binding constructs are \ide{lambda},
\ide{let}, \ide{let*}, \ide{letrec}, and \ide{do} expressions (see
sections~\ref{lambdastar}, \ref{letrec}, and \ref{do}).

\vest Like Algol and Pascal, and unlike most other dialects of Lisp except for
Common Lisp, Scheme is a statically scoped language with block structure.  To
each place where a variable is bound in a program there corresponds a
\defining{region} of the program text within which the binding is effective. 
The region is determined by the particular binding construct that establishes
the binding.  Every reference to or assignment of a variable refers to the
binding of the variable that established the innermost of the regions containing
the use.  If there is no binding of the variable whose region contains the use,
then the use refers to the binding for the variable in the top level
environment, if any (section~\ref{initialenv}); if there is no binding for the
identifier, it is said to be \defining{unbound}. 
\mainindex{bound}\index{top level environment}


\chapter{Expressions}
\label{expressionchapter}

\newcommand{\syntax}{{\em Syntax: }}
\newcommand{\semantics}{{\em Semantics: }}

A Scheme expression is a construct that returns zero or more values, such as a
variable reference, literal, procedure call, or conditional.

Expression types are categorized as {\em primitive} or {\em derived}.  Primitive
expression types include variables and procedure calls.  Derived expression
types are not semantically primitive, but can instead be explained in terms of
the primitive constructs as in section ~\ref{derivedsection}.  They are
redundant in the strict sense of the word, but they capture common patterns of
usage, and are therefore provided as convenient abbreviations.

\section{Primitive expression types}
\label{primitivexps}

\subsection{Variable references}\unsection

\begin{entry}{%
\pproto{\hyper{variable}}{essential \exprtype}}

An expression consisting of a variable \index{variable}
(section~\ref{variablesection}) is a variable reference.  The  values of the
variable reference are the values stored in the location to which the variable
is bound.  It is an error to reference an unbound \index{unbound} variable.

\begin{scheme}
(define x 28)
x   \ev  28%
\end{scheme}
\end{entry}

\subsection{Procedure calls}\unsection

\begin{entry}{%
\pproto{(\hyper{operator} \hyperi{operand} \dotsfoo)}{essential \exprtype}
\pproto{(\hyper{operator} \hyperi{operand} \dotsfoo \hyper{operand$_{n-1}$} \ampersand\ \hypern{operand})}{essential \exprtype}}

A procedure call is written by simply enclosing in parentheses expressions for
the procedure to be called and the arguments to be passed to it.  The operator
and operand expressions are evaluated (in an indeterminate order) and the
resulting procedure is passed the resulting arguments.
\mainindex{call}\mainindex{procedure call}

\begin{scheme}%
(+ 3 4)                          \ev  7
((if \schfalse + *) 3 4)         \ev  12%
\end{scheme}

Only an expression following an \ampersand{} may evaluate to an indefinite
number of values; an error is signalled if exactly one value is not returned for
any other expressions in a procedure call. All of the values returned by an
expression following an \ampersand{} are passed to the called procedure.

\begin{note} In contrast to other dialects of Lisp, the order of
evaluation is unspecified, and the operator expression and the operand
expressions are always evaluated with the same evaluation rules.
\end{note}
\end{entry}

\subsection{Multiple return values}\unsection
\begin{entry}{%
\proto{values}{ \hyperi{operand} \dotsfoo}{essential procedure}}

The special procedure \ide{values} is used to return indefinite numbers of
values.  It follows the ordinary evaluation rules for procedures, and is a
first-class object like other procedures, but returns all of the values it
receives as arguments. It can be thought of as the multiple value identity
operator.

\begin{scheme}%
(list 1 2 \& (values))                 \ev (1 2)
(list 1 2 \& (values 3 4))             \ev (1 2 3 4)
(list 1 2 (values 3))                  \ev (1 2 3)
(list 1 2 (values 3 4))                \ev \scherror%
\end{scheme}

\begin{note}%
A description of \ide{values} is probably more properly placed in the section on
special control features.
\end{note}
\end{entry}

\subsection{\Lambdastarexp{}s}\unsection

\label{lambastar}

\begin{entry}{%
\proto{lambda*}{ \hyperi{clause} \hyper{clause$_2$} \dotsfoo}{essential \exprtype}}

\syntax
Each \hyper{clause} should be of the form
\begin{scheme}
(\hyper{formals} \hyper{body}).%
\end{scheme}
\hyper{Formals} should be a formal arguments list as described below, and
\hyper{body} should be a sequence of one or more expressions.

\semantics
\vest A \lambdastarexp{} evaluates to a procedure.  The environment in effect
when the \lambdastarexp{} was evaluated is remembered as part of the procedure. 
When the procedure is later called with some actual arguments, the appropriate
\hyper{clause} will be selected, and the environment in which the
\lambdastarexp{} was evaluated will be extended by binding the variables in its
formal argument list to fresh locations, the corresponding actual argument
values will be stored in those locations, and the expressions in the
\hyper{body} of the \hyper{clause} will be evaluated sequentially in the
extended environment.  The values returned by last expression in the
\hyper{body} will be returned as the result of the procedure call.  The first
\hyper{clause} whose \hyper{formals} accepts the actual arguments received by
the procedure is selected. An error is signaled if no \hyper{formals} accepts
the arguments received by a procedure.

\hyper{Formals} should have one of the following forms:

\begin{itemize}
\item {\tt(\hyperi{variable} \dotsfoo\ \hypern{variable})}:
The \hyper{clause} accepts exactly $n$ arguments. The arguments will be stored
in the bindings of the corresponding variables, and the \hyper{body} of the
\hyper{clause} will be evaluated.

\item {\tt(\hyperi{variable} \dotsfoo\ \hypern{variable} \ampersand\ \hyper{variable$_{n+1}$})}:
The \hyper{clause} accepts $n$ or more arguments. The first $n$ arguments will
be stored in the bindings of the first $n$ corresponding variables; all
arguments left over will be stored in the binding of the variable following the
\ampersand{}. These values may be referenced by using the variable following an
\ampersand{} in a procedure call.
\end{itemize}

\begin{scheme}%
(lambda* ((x) x))         \ev  {\em{}a procedure}
((lambda* ((x) x)) 0)     \ev 0
((lambda* ((\& r) (list \& r)))
 1 2 3)                   \ev (1 2 3)
(define list
  (lambda*
    (() '())
    ((x \& r) (cons x (list \& r)))))%
\end{scheme}
\end{entry}

\subsection{Conditionals}\unsection

\begin{entry}{%
\proto{if}{ \hyper{test} \hyper{consequent} \hyper{alternate}}{essential \exprtype}
\proto{if}{ \hyper{test} \hyper{consequent}}{\exprtype}}  %\/ if hyper = italic

\syntax
\hyper{Test}, \hyper{consequent}, and \hyper{alternate} may be arbitrary
expressions.

\semantics
An \ide{if} expression is evaluated as follows: first, \hyper{test} is
evaluated.  If it yields a true value\index{true} (see
section~\ref{booleansection}),then \hyper{consequent} is evaluated and its
values are returned.  Otherwise\hyper{alternate} is evaluated and its values are
returned.  If \hyper{test}yields a false value and no \hyper{alternate} is
specified, then the result of the expression is unspecified.  An error will be
signaled if \hyper{test} does not evaluate to exactly one value.

\begin{scheme}
(if (> 3 2) 'yes 'no)           \ev  yes
(if (> 2 3) 'yes 'no)           \ev  no
(if (> 3 2)
    (- 3 2)
    (+ 3 2))                    \ev  1
(list \& (if \#t (values) 0))   \ev  ()
(if (values) 0 1)               \ev  \scherror%
\end{scheme}

\end{entry}


\subsection{Assignments}\unsection

\begin{entry}{%
\proto{set!}{ \hyper{variable} \hyper{expression}}{essential \exprtype}}

\hyper{Expression} is evaluated, and the resulting values are stored in the
location to which \hyper{variable} is bound.  \hyper{Variable} must be bound
either in some region \index{region} enclosing the \ide{set!} expressionor at
top level.  The result of the \ide{set!} expression is unspecified.

\begin{scheme}
(define x 2)
(+ x 1)                 \ev  3
(set! x 4)              \ev  \unspecified
(+ x 1)                 \ev  5
(set! x (values 1 2))   \ev  \unspecified
(+ \& x)                \ev  3%
\end{scheme}

\end{entry}

\end{document}

% Other modifications remain to be made, particularly in the syntax and
% semantics.


Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 23 Jun 88 12:31:41 EDT
Date: Thu, 23 Jun 88 12:31:36 EDT
From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Sender: JAR0@AI.AI.MIT.EDU
Subject:  (define x)
To: rrrs-authors@MC.LCS.MIT.EDU
In-reply-to: Msg of Thu 23 Jun 88 10:25:23 EST from R. Kent Dybvig <dyb@iuvax.cs.indiana.edu>
Message-ID: <402290.880623.JAR0@AI.AI.MIT.EDU>


I think I agree with Kent Dybvig that if (define x) is allowed at top
level, then it should be allowed internally.

I would hate to see some functionality become available through define
that was not available through letrec, so I would advise adopting
(define x) ONLY if letrec is also extended so that
  (letrec ((x) ...) ...)
means
  (letrec ((x <unassigned>) ...) ...).

For orthogonality's sake, this should also, I believe, require
  (let ((x) ...) ...)
to mean
  (let ((x <unassigned>) ...) ...),
and similarly for let*, named let (?), and do (??).  Consider this proposed,
and please talk me out of this madness.


Received: from iuvax.cs.indiana.edu (TCP 30003147300) by MC.LCS.MIT.EDU 23 Jun 88 11:51:41 EDT
Received: by iuvax.cs.indiana.edu; id AA11128; Thu, 23 Jun 88 10:25:23 EST
Received: by iuvax.cs.indiana.edu (5.54/1.5) 
Date: Thu, 23 Jun 88 10:25:23 EST
From: R. Kent Dybvig <dyb@iuvax.cs.indiana.edu>
To: rrrs-authors@mc.lcs.mit.edu
Subject: Re:  (define x)

	From: David Bartley <bartley@mips.csc.ti.com>
	Subject: (define x)
	
	I think internal (DEFINE X) has much less justification than top-level
	ones, so I'd rather avoid the mess of allowing (LETREC ((X) (Y)) ...).
	
	--db--

I disagree.  If it is going to be allowed at top-level, and it probably
should be, then it should be allowed internally.  We can show the
expansion as "(letrec ((x <undefined>)) ...)", if we want, as with the
derived expansion for letrec in the formal semantics section.  It makes
no sense to have a different syntax for internal defines from that of
external defines.  I would use "(define x)" internally just as much as
I would use it externally, and for the same reasons.

Received: from RELAY.CS.NET (TCP 1201000005) by MC.LCS.MIT.EDU 22 Jun 88 22:31:43 EDT
Received: from helios.northeastern.edu by RELAY.CS.NET id aa27150;
          22 Jun 88 19:08 EDT
Received: from corwin.ccs.northeastern.edu by helios.northeastern.edu
          id aa23454; 22 Jun 88 18:53 EDT
Received: by corwin.CCS.Northeastern.EDU (5.51/SMI-3.2+CCS-main-2.4)
	id AA15343; Mon, 20 Jun 88 13:49:22 EDT
Date: Mon, 20 Jun 88 13:49:22 EDT
From: Mitchell Wand <wand%corwin.ccs.northeastern.edu@RELAY.CS.NET>
Message-Id: <8806201749.AA15343@corwin.CCS.Northeastern.EDU>
To: gls@THINK.COM
Cc: KMP@SCRC-STONY-BROOK.ARPA, JAR@mc.lcs.mit.edu, 
    willc%tekchips.tek.com@RELAY.CS.NET, KMP@SCRC-STONY-BROOK.ARPA, 
    rrrs-authors@mc.lcs.mit.edu
In-Reply-To: gls@think.com's message of Fri, 17 Jun 88 18:20:58 EDT <8806172220.AA14999@kali.think.com>
Subject: new wording for eqv?

   Date: Fri, 17 Jun 88 18:20:58 EDT
   From: gls@think.com
   Subject: new wording for eqv?
   To: KMP@scrc-stony-brook.arpa
   Cc: JAR@mc.lcs.mit.edu, willc%tekchips.tek.com@relay.cs.net,
	   KMP@scrc-stony-brook.arpa, rrrs-authors@mc.lcs.mit.edu

      Date: Fri, 17 Jun 88 16:09 EDT
      From: Kent M Pitman <KMP@stony-brook.scrc.symbolics.com>

      I observe as an aside also that your description is somewhat
      meta-circular, though perhaps not enough to worry about here. You
      effectively begin by saying that EQV? computes whether two things
      are distinct (for which i read "not the same"), and yet the
      terminology uses the word "the same" all over the place.

   Plus ca change, plus c'est la meme chose.

In making this observation, have you adequately considered the granularity of
time, multiprocessing, and the effects of quantum gravitation?  

Note also that the preceding question, along with this observation,
presupposes temporal concepts as well :-)  --Mitch




Received: from RELAY.CS.NET (TCP 1201000005) by MC.LCS.MIT.EDU 22 Jun 88 19:22:43 EDT
Received: from relay2.cs.net by RELAY.CS.NET id ab26915; 22 Jun 88 18:52 EDT
Received: from tektronix.tek.com by RELAY.CS.NET id aa12333; 22 Jun 88 18:39 EDT
Received: by tektronix.TEK.COM (5.51/6.24)
	id AA09378; Wed, 22 Jun 88 10:12:45 PDT
Received: by tekchips.CRL.TEK.COM (5.51/6.24)
	id AA07114; Wed, 22 Jun 88 10:13:54 PDT
Message-Id: <8806221713.AA07114@tekchips.CRL.TEK.COM>
To: bartley%mips.csc.ti.com@RELAY.CS.NET, Alan@mc.lcs.mit.edu, 
    jeff%aiva.edinburgh.ac.uk@NSS.CS.UCL.AC.UK, 
    uunet.uu.net!mcvax!diku.dk!danvy@tekcrl.crl, kend@tekchips.crl, 
    dfried@iuvax.cs.indiana.edu, RPG@SAIL.STANFORD.EDU, 
    cph%kleph.ai.mit.edu@RELAY.CS.NET, mkatz@A.ISI.EDU, 
    kranz@WHEATIES.AI.MIT.EDU, emo@iuvax.cs.indiana.edu, 
    philbin-jim@YALE.ARPA, uwe@tekchips.crl, 
    jinx%chamartin.ai.mit.edu@RELAY.CS.NET, 
    wand%corwin.ccs.northeastern.edu@RELAY.CS.NET
Cc: rrrs-authors@mc.lcs.mit.edu
Subject: List of attendees (tentative)
Date: 22 Jun 88 10:13:52 PDT (Wed)
From: willc@tekchips.crl

The following people have told me that they are coming to the RRRS meeting
on Sunday before LFP:

David H Bartley
Alan Bawden
Will Clinger
Jeff Dalton
Olivier DANVY
Ken Dickey
Dan Friedman
Dick Gabriel
Chris Hanson
Morry Katz
David Kranz
Eric Ost
Jim Philbin
Uwe Pleban
Guillermo J Rozas
Mitchell Wand

I assume that Hal Abelson (chair) and Jonathan Rees (editor) are coming
also, for a total of eighteen people so far.  If you intend to attend but
your name is not on this list, please let me know.

Please let me know also if your name is on this list but I've gotten your
electronic mailing address wrong.  (If you're on the rrrs-authors mailing
list, you should receive two copies of this message.)

Peace, Will

Received: from ti.com (TCP 1201600056) by MC.LCS.MIT.EDU 22 Jun 88 16:47:07 EDT
Received: by ti.com id AA08480; Wed, 22 Jun 88 15:44:14 CDT
Received: from mips by tilde id AA25692; Tue, 21 Jun 88 10:28:54 CDT
Received: by mips id AA15531; Tue, 21 Jun 88 10:28:47 CDT
Date: Tue, 21 Jun 88 10:28:47 CDT
From: David Bartley <bartley@mips.csc.ti.com>
Message-Id: <8806211528.AA15531@mips>
To: JAR@mc.lcs.mit.edu
Cc: Pavel.pa@XEROX.COM, rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Jonathan A Rees's message of Mon, 13 Jun 88 17:44:35 EDT <396821.880613.JAR@AI.AI.MIT.EDU>
Subject: (define x)

>We need to decide whether this is to make sense only for top-level
>defines or for internal defines as well.  If for internal defines, the
>desugaring into LETREC has to be given; that would probably mean that
>LETREC would have to be extended (e.g. (letrec ((x) (y)) ...)); and that
>seems like a bad idea to me, although I don't feel strongly; so I'd
>suggest making it a special case for top level.  Top level defines are
>already sufficiently different from internal ones (e.g. they are
>evaluated sequentially, and may be interspersed with expressions) that
>this doesn't seem too terrible.

I think internal (DEFINE X) has much less justification than top-level
ones, so I'd rather avoid the mess of allowing (LETREC ((X) (Y)) ...).

--db--

Received: from ti.com (TCP 1201600056) by MC.LCS.MIT.EDU 22 Jun 88 16:47:06 EDT
Received: by ti.com id AA08491; Wed, 22 Jun 88 15:44:33 CDT
Received: from mips by tilde id AA26292; Tue, 21 Jun 88 10:55:43 CDT
Received: by mips id AA16088; Tue, 21 Jun 88 10:55:32 CDT
Date: Tue, 21 Jun 88 10:55:32 CDT
From: David Bartley <bartley@mips.csc.ti.com>
Message-Id: <8806211555.AA16088@mips>
To: rrrs-authors@mc.lcs.mit.edu
Subject:  More on Full Specification

From: Paul Hudak <hudak-paul@YALE.ARPA>
>[Concerning indeterminate argument evaluation order:]
>I wasn't around when the decision was made, so can't say whether it
>was "deliberate" or not, but in what sense is it "desireable"?
>Presumably the motivation for this was to allow implementation
>freedom, so why only stop half-way?  My guess is that the intent was
>as Robert Hieb states, except for the concurrency part (but maybe that
>was in somebody's mind too).  I wonder how many current
>implementations permute the arguments in different ways depending on
>context?  Seems useful to me ... and fully within the motivation for
>underspecification in the first place.

We certainly do, and it is indeed useful.

From: Robert Hieb <hieb@iuvax.cs.indiana.edu>
>Finally a note about implementation issues.  Although, as one greatly involved
>with implementing Scheme, I can understand their seduction, I think
>we should fight it.  First-class procedures and continuations combined with
>lexical scoping, assignments and indefinite extent for variables appeared 
>to deliver a knockout blow to implementation efficiency.  The fact that 
>good implementation techniques have appeared anyway is good reason not to
>be too quick to worry about implementations.  After all, an implementation
>can do what it pleases as long as no one can tell the difference.  Thus
>if it can prove that order of evaluation doesn't matter, or that variables
>can't be referenced before definition, it can make appropriate optimizations.
>The next great step in Scheme efficiency will require extensive program
>analysis anyway.  I think people are still attracted to Scheme by the
>structure and semantics of its powerful features, and that is what we should 
>concentrate on.

I don't think those features "appeared to deliver a knockout blow to
implementation efficiency."  What they did do (in combination) was
force us to look at compiling in new ways.  I was pleased, but not
terribly surprised, when we found efficient ways to cope with them.

It's a different story with your suggestions.  Fixing the order of
evaluation of arguments, for instance, has problems for optimising
compilers that are well known.  I could win with global analysis in
Pascal because I could see the entire program at a time and didn't
have real first-class procedures to deal with, but I'm stymied in
Scheme most of the time.

I agree with the spirit of your argument, though.  We shouldn't cast
in concrete only those language features that we already know how to
do well.

From: willc@tekchips.crl
>		 [...] I generally agree with Robert Hieb's analysis.
>I happen to think, however, that the three concrete underspecifications
>that Hieb proposed to fix (value returned by side-effecting procedures,
>order of evaluation of arguments, order of evaluation of definitions)
>are among the most justified underspecifications in all of Scheme.  Each
>of these underspecifications concerns something that programmers ordinarily
>do not care about because it doesn't matter; they have the effect of
>requiring programmers to write some explicit code in the exceptional case
>when they do want to use a specific value or order of evaluation.  If
>these underspecifications were "fixed", programs would be harder to read
>because you would have to assume that the order matters whenever you see
>a procedure call or internal definitions.  As things stand now, you know
>the order doesn't matter and this fact makes it easier to understand the
>program.

I think Will has summarized my thinking beautifully, so I'll leave it
at this: I agree that we should tighten up inadvertant or lazy
underspecification, but there are places, such as these, where it is
appropriate.

--db--



Received: from RELAY.CS.NET (TCP 1201000005) by MC.LCS.MIT.EDU 21 Jun 88 12:37:39 EDT
Received: from relay2.cs.net by RELAY.CS.NET id ag06129; 21 Jun 88 10:44 EDT
Received: from tektronix.tek.com by RELAY.CS.NET id aa00211; 21 Jun 88 10:28 EDT
Received: by tektronix.TEK.COM (5.51/6.24)
	id AA11287; Mon, 20 Jun 88 14:26:45 PDT
Received: by tekchips.CRL.TEK.COM (5.51/6.24)
	id AA07941; Mon, 20 Jun 88 14:28:01 PDT
Message-Id: <8806202128.AA07941@tekchips.CRL.TEK.COM>
To: rrrs-authors@mc.lcs.mit.edu
Subject: eqv? version 2
Date: 20 Jun 88 14:27:59 PDT (Mon)
From: willc@tekchips.crl

The following is my second version of the eqv? proposal, with the following
changes to address issues raised by Kent Pitman:

    eqv? on symbols is now defined in terms of string=? and symbol->string?
    instead of how the symbols print.

    eqv? on pairs, vectors, and strings is now defined in terms of the
    locations referred to by these objects instead of their creation.  This
    makes the description more precise but requires people to understand the
    domain equations and semantic equations.

(Incidentally, the formal semantics is incomplete in that it lacks axioms,
for example, that say that for any two pairs pair1 = <car1, cdr1> and
pair2 = <car2, cdr2>, one of the following must be true:

    1.  car1 = car2 & cdr1 = cdr2 & car1 != cdr1
    2.  car1 != car2 & cdr1 != cdr2 & car1 != cdr1 & car2 != cdr2

The formal semantics also lacks axioms to guarantee that, for example,
pairs never overlap with vectors.  I realized all this when I was writing
down the formal semantics, but didn't try to put it in because I felt
that people wanted the formal semantics to serve as an aid to
understanding the English descriptions rather than as a specification
in its own right.  Jonathan simplified the semantics further while preparing
it for SIGPLAN Notices.)

-------------------------------------------------------------------------------
Eliminate the second and third paragraphs of section 6.2, and
eliminate the seven bullet items that follow them.

Change the description of eqv? as follows.



(eqv? obj1 obj2)                          essential procedure

The eqv? procedure defines a useful equivalence relation on
objects.  Briefly, it returns #t if obj1 and obj2 should normally
be regarded as the same object and returns #f if they should
normally be regarded as distinct objects.  This relation is left
slightly open to interpretation, but the following partial
specification of eqv? holds for all implementations of Scheme.

The eqv? procedure returns #t if:

obj1 and obj2 are both #t or both #f.

obj1 and obj2 are both symbols and
(string=? (symbol->string obj1) (symbol->string obj2))
is true.  (Note: This assumes that neither obj1 nor obj2 is an ``uninterned
symbol'' as alluded to in section 6.4.  This report does not presume to
specify the behavior of eqv? on implementation-dependent extensions.)

obj1 and obj2 are both numbers, are numerically equal
(see =, section 6.5.4), and are either both exact or
both inexact (see section 6.5.2).

obj1 and obj2 are both characters and are the same
character according to the char=? procedure (section
6.6).

both obj1 and obj2 are the empty list.

obj1 and obj2 are pairs that refer to the same locations in the store
(see section 7.2.2).

obj1 and obj2 are vectors that refer to the same locations in the store
(see section 7.2.2).

obj1 and obj2 are strings that refer to the same locations in the store
(see section 7.2.2).

obj1 and obj2 are procedures whose location tags are equal
(see section 7.2.2).


The eqv? procedure returns #f if:

one of obj1 and obj2 is a boolean but the other is not.

one of obj1 and obj2 is a symbol but the other is not.

one of obj1 and obj2 is a number but the other is not.

one of obj1 and obj2 is a pair but the other is not.

one of obj1 and obj2 is a vector but the other is not.

one of obj1 and obj2 is a string but the other is not.

one of obj1 and obj2 is a procedure but the other is not.

one of obj1 and obj2 is #t but the other is #f.

obj1 and obj2 are symbols but
(string=? (symbol->string obj1) (symbol->string obj2)) is false.

one of obj1 and obj2 is an exact number and the other is an
inexact number.

obj1 and obj2 are numbers for which the = procedure returns
#f.

obj1 and obj2 are characters for which the char=? procedure
returns #f.

one of obj1 and obj2 is the empty list but the other is not.

obj1 and obj2 are pairs that refer to distinct locations
(see section 7.2.2).

obj1 and obj2 are vectors that refer to distinct locations
(see section 7.2.2).

obj1 and obj2 are strings that refer to distinct locations
(see section 7.2.2).

obj1 and obj2 are procedures that would behave differently
(return a different value or have different side effects)
for some arguments.

[The first block of examples goes here, omitting the
(eq? "" "") example, which should be added to the second
block of examples.]

The following examples illustrate cases in which the above
rules do not fully specify the behavior of eqv?.  In every
case, the value returned by eqv? is either #t or #f, but
which one it returns is implementation-dependent.

[The second block of examples goes here, following by the
paragraph beginning "The next set of examples shows...",
followed by the gen-counter and gen-loser examples.]

Objects of distinct types must never be regarded as the same
object, except that #f and the empty list are permitted
to be identical, and the character type need not be disjoint
from other types.

[The fourth block of examples goes here, followed by the
paragraph beginning "Since it is an error...", followed by
the fifth block of examples, followed by the note.]

Received: from RELAY.CS.NET (TCP 1201000005) by MC.LCS.MIT.EDU 21 Jun 88 12:37:28 EDT
Received: from relay2.cs.net by RELAY.CS.NET id af06129; 21 Jun 88 10:44 EDT
Received: from tektronix.tek.com by RELAY.CS.NET id aa00209; 21 Jun 88 10:28 EDT
Received: by tektronix.TEK.COM (5.51/6.24)
	id AA11303; Mon, 20 Jun 88 14:28:48 PDT
Received: by tekchips.CRL.TEK.COM (5.51/6.24)
	id AA07985; Mon, 20 Jun 88 14:30:05 PDT
Message-Id: <8806202130.AA07985@tekchips.CRL.TEK.COM>
To: JAR@mc.lcs.mit.edu
Cc: rrrs-authors@mc.lcs.mit.edu
Subject: Multiple values, version 1
Date: 20 Jun 88 14:30:02 PDT (Mon)
From: willc@tekchips.crl

This probably goes in section 6.9, "Control features".

(values obj1 ...)                                                    procedure

Returns its arguments as "multiple return values".  Most continuations ignore
all but the first return value, but the with-values procedure can create a
continuation that will use all the values being returned.  It is an error to
return zero values to an continuation that expects one.  See with-values.

  (let ((x (values 'a 'b 'c 'd))) x)                        ==>  a
  (let ((x (values))) x)                                    ==>  error


(with-values thunk proc)                                             procedure

Thunk must be a procedure of no arguments and proc must be a procedure.  The
thunk is called with no arguments, and all of its return values, not just the
first, are passed as arguments to proc.  See values.

  (with-values (lambda () (values 3 4 5)) +)                ==>  12
  (with-values (lambda () (values 'a 'b 'c)) list)          ==>  (a b c)
  (with-values (lambda () (values 'a)) list)                ==>  (a)
  (with-values (lambda () (values)) list)                   ==>  ()
  (with-values (lambda () (values))
               (lambda (x) (list x)))                       ==>  error
  (letrec ((stats (lambda (name)
                    (case name
                      ((henry)  (values 480 100 14 0 4))
                      ((george) (values 400 90 20 2 5))
                      (else     (values 0 0 0 0 0))))))
    (with-values (lambda () (stats 'henry))
                 (lambda (atbats singles doubles triples homeruns)
                   (/ (+ singles (* 2 doubles) (* 3 triples) (* 4 homeruns))
                      (max 1 atbats)))))
                                                            ==>  3/10

Received: from RELAY.CS.NET (TCP 1201000005) by MC.LCS.MIT.EDU 21 Jun 88 12:37:20 EDT
Received: from relay2.cs.net by RELAY.CS.NET id ae06129; 21 Jun 88 10:44 EDT
Received: from tektronix.tek.com by RELAY.CS.NET id aa00203; 21 Jun 88 10:27 EDT
Received: by tektronix.TEK.COM (5.51/6.24)
	id AA11349; Mon, 20 Jun 88 14:30:34 PDT
Received: by tekchips.CRL.TEK.COM (5.51/6.24)
	id AA08006; Mon, 20 Jun 88 14:31:51 PDT
Message-Id: <8806202131.AA08006@tekchips.CRL.TEK.COM>
To: JAR@mc.lcs.mit.edu
Cc: rrrs-authors@mc.lcs.mit.edu
Subject: Optionals, version 1
Date: 20 Jun 88 14:31:48 PDT (Mon)
From: willc@tekchips.crl

This should be added to section 4.1.4, "Lambda expressions".

[At the end of the list of forms that the <Formals> may take:]

Some implementations support three more alternatives for the <Formals>:

\item{$\bullet$}{
(<variable_1> ... <variable_k> #!optional <variable_{k+1}> ...):
The variables that precede the special #!optional flag are {\it required}
formal arguments, and the variables that follow the #!optional flag are
{\it optional} formal arguments.  There must be at least as many actual
arguments as there are required arguments, and there must be no more actual
arguments than there are required and optional arguments together.  The actual
arguments are matched against the formal arguments from left to right, and are
stored in the bindings of the corresponding variables.  If optional formal
arguments are left over after the actual arguments have been matched up against
the other formal arguments, then a special default object is stored in the
bindings of those left-over variables.  See the default-object? procedure.
}

\item{$\bullet$}{
(<variable_1> ... <variable_k> #!optional <variable_{k+1}> ...
<variable_{n-1}> . <variable_n>):
The #!optional flag may be used in combination with a space-delimited period
before the last variable.  In this case there must be at least as many actual
arguments as there are required arguments, but there is no upper limit on the
number of actual arguments.  If the number of actual arguments is less than n,
then an empty list will be stored in the binding of <variable_n>.  Otherwise
a newly allocated list of the actual arguments left over after all the other
actual arguments have been matched up against the other formal arguments will
be stored in the binding of <variable_n>.
}

\item{$\bullet$}{
A #!rest flag may be used in place of a space-delimited period before the
last variable.  The #!rest flag is equivalent to a space-delimited period
in such a context.
}

  (let ((f (lambda (x #!optional base)
             (expt (if (default-object? base) 2 base) x))))
    (list (f 10) (f 4 3)))                                    ==>  (1024 81)



[The following probably goes in section 6.9, "Control features".]

(default-object? obj)                                           procedure

Returns #t if obj is a default object such as is supplied for optional
arguments that have no corresponding actual argument.  (See lambda, section
4.1.4.)  Otherwise returns #f.

  ((lambda (#!optional x y z) (default-object? z)) 1 4)               ==>  #t
  ((lambda (#!optional x y z) (default-object? z)) 1 4 9)             ==>  #f

Received: from SAIL.Stanford.EDU (TCP 1200000013) by MC.LCS.MIT.EDU 20 Jun 88 11:07:36 EDT
Message-ID: <77793@SAIL.Stanford.EDU>
Date: 20 Jun 88  0807 PDT
From: Dick Gabriel <RPG@SAIL.Stanford.EDU>
Subject: Meetings  
To:   rrrs-authors@MC.LCS.MIT.EDU

I will attend the Sunday Scheme meeting but not the IEEE meeting.
			-rpg-


Received: from acf3.NYU.EDU (TCP 20036500015) by MC.LCS.MIT.EDU 18 Jun 88 07:15:21 EDT
Received:  by acf3.NYU.EDU (5.54/25-eef)
	id AA20656; Sat, 18 Jun 88 07:13:58 EDT
Date: Sat, 18 Jun 88 07:13:58 EDT
From: Eric S. Tiedemann <tiedeman@acf3.NYU.EDU>
Message-Id: <8806181113.AA20656@acf3.NYU.EDU>
To: ramsdell%linus@MITRE-BEDFORD.ARPA, tiedeman@ACF3.NYU.EDU,
        willc@tekchips.crl
Subject: Re: Dependency analysis on internal DEFINE's
Cc: rrrs-authors@mc.lcs.mit.edu


	From: willc@tekchips.crl
	
	I guess I don't understand what is being proposed, because it doesn't 
	look computable to me.  Here are the proposals, followed by a couple 
	of examples that illustrate my lack of understanding.
	
	  [Tiedeman:]
	  This can also be made to work by having LETREC's implement an 
	  applicative order fixpoint rather than the restriction of it 
	  specified in R3RS.  This amounts to performing dependency analysis 
	  to transform the above into a LET*.  Alas, this requires static 
	  analysis which an interpreter can't afford.  Some compilers, however,
	  already do it.

I wasn't actually making a proposal, just using the idea for purposes of 
conceptual ellucidation.  However, I'd like to try to answer your questions.

I used the term "the applicative order fixpoint" because I think what I have 
in mind is the most general fixpoint allowed by applicative order evaluation 
(I could well be wrong.) and I'll continue to use it in describing what I 
meant.  I'll refer to the behavior specified in the report as a "R3RS 
fixpoint."

The only place I fault R3RS fixpoints is where they are used for LETREC's that 
don't involve mutual recursion among all the bindings.  Such LETREC's can be 
broken up into subsets of mutually recursive bindings (i.e. the condensation 
of the LETREC's dependency graph.)  These subsets can further be ordered by 
their interdependencies (by topologically sorting the condensation) and then 
implemented as nested LETREC's (or LET's when they have but one binding which 
is non-recursive.)  Since all the LETREC's now represent true recursions we 
can safely treat them as R3RS fixpoints.  This treatment of LETREC's is a 
generalization of R3RS fixpoints.

Here's an example of a applicative order fixpoint which R3RS wouldn't handle:

	(letrec ((x 2)
	         (y (+ x 2)))
	 ....)

which, by the above method, is the same as:

	(let ((x 2))
	 (let ((y (+ x 2)))
	  ....)

In both of your examples the DEFINE's are mutually recursive and so R3RS 
semantics would be followed.

Note, however...

	Example 2:
	
	  (let ((x '(a b c)))
	    (define y
	      (map (lambda (a) (cons a z)) x))
	    (define z
	      (map (lambda (a) (cons y a)) x))
	    (append y z))
	
	  This is not allowed by the wording in the R3RS.

According to R3RS this is "undefined, and an error may be signalled."  Is 
"undefined" defined in the report?  Presumably the wording was designed to 
leave room for the plethora of "compatible extensions" out there--sometimes 
more than one in the same implementation.  Ceteris paribus I would prefer that 
it were "an error."

	                                                            ...The
	thing I don't understand is how an "applicative order" fixed point can
	be a generalization of the current state of affairs while remaining
	computable through static analysis.

I hope I've made this clear.  Whether the applicative order fixpoint is
actually defined for any given LETREC is, of course, not computable.  You can,
however, always set it up in linear time.

Eric
	

Received: from RELAY.CS.NET (TCP 1201000005) by MC.LCS.MIT.EDU 17 Jun 88 20:36:33 EDT
Received: from relay2.cs.net by RELAY.CS.NET id aa18716; 17 Jun 88 19:49 EDT
Received: from tektronix.tek.com by RELAY.CS.NET id aa01620; 17 Jun 88 19:44 EDT
Received: by tektronix.TEK.COM (5.51/6.24)
	id AA02104; Fri, 17 Jun 88 12:22:39 PDT
Received: by tekchips.CRL.TEK.COM (5.51/6.24)
	id AA20045; Fri, 17 Jun 88 12:23:56 PDT
Message-Id: <8806171923.AA20045@tekchips.CRL.TEK.COM>
To: ramsdell%linus@MITRE-BEDFORD.ARPA
Cc: rrrs-authors@mc.lcs.mit.edu
Subject: Re: days-after-J2000.0
In-Reply-To: Your message of Fri, 17 Jun 88 08:21:53 EDT.
	     <8806171221.AA20941@darwin.sun.uucp>
Date: 17 Jun 88 12:23:54 PDT (Fri)
From: willc@tekchips.crl

Tongue-in-cheek implementation note to be added to the days-after-J2000.0
proposal:

  On systems that lack time-keeping hardware, this procedure may query
  an operator interactively.  Authors of portable code should be aware
  that this is likely to be an slow operation.

Received: from RELAY.CS.NET (TCP 1201000005) by MC.LCS.MIT.EDU 17 Jun 88 20:26:49 EDT
Received: from relay2.cs.net by RELAY.CS.NET id ab18657; 17 Jun 88 19:42 EDT
Received: from tektronix.tek.com by RELAY.CS.NET id aa01566; 17 Jun 88 19:38 EDT
Received: by tektronix.TEK.COM (5.51/6.24)
	id AA06635; Fri, 17 Jun 88 13:12:27 PDT
Received: by tekchips.CRL.TEK.COM (5.51/6.24)
	id AA20610; Fri, 17 Jun 88 13:13:42 PDT
Message-Id: <8806172013.AA20610@tekchips.CRL.TEK.COM>
To: tiedeman@ACF3.NYU.EDU, hudak-paul@YALE.ARPA, hieb@iuvax.cs.indiana.edu
Cc: rrrs-authors@mc.lcs.mit.edu
Subject: Re: More on Full Specification
In-Reply-To: Your message of Thu, 16 Jun 88 03:45:26 EDT.
	     <8806160745.AA03130@acf3.NYU.EDU>
Date: 17 Jun 88 13:13:40 PDT (Fri)
From: willc@tekchips.crl

	    No, not concurrently.  E*, in the semantics, always evaluates in
	    *some* order.  This isn't overspecification, as Paul Hudak suggests
	    ,but rather a deliberate and desirable design decision.
	
	I wasn't around when the decision was made, so can't say whether it
	was "deliberate" or not, but in what sense is it "desireable"?

The decision was made deliberately, and the argument that carried the day
for requiring that the evaluation happen in some unspecified but sequential
order is the fact that code such as Eric's splay-tree example would break in
the presence of concurrent evaluation unless it was protected by critical
sections, which nobody wanted to deal with.  I was the pretty much the only
person at Brandeis who really wanted to allow concurrent evaluation.

My reading of the report is that the requirement for sequential execution
makes it illegal to evaluate the common subexpression (car x) only once in
the following expression unless it can be proved that at least one of the
procedures goo and moo do not change the car field of x:

  (foo (goo (car x)) (moo (car x)))

  My bet is that Will, when designing the denotational semantics,
  specified the underspecification in the simplest deterministic way he
  could think of, and that's to use something like PERMUTE.  If there
  was a clean way to specify non-determinism, including the
  inter-leaving of evaluations, then perhaps he would have chosen that.

This is correct.  I felt that Scheme is so close to a deterministic
language that the greater accuracy of a non-deterministic semantics
was less important that the greater clarity of a deterministic semantics.

    I guess the bottom line is that we should be VERY careful about what
    things we choose to underspecify, and how.  These decisions can have
    radical effects on portability and correctness.  I think that the
    default should be full specification, and that anything left
    underspecified should have a very good rationale.

I agree with this and I generally agree with Robert Hieb's analysis.
I happen to think, however, that the three concrete underspecifications
that Hieb proposed to fix (value returned by side-effecting procedures,
order of evaluation of arguments, order of evaluation of definitions)
are among the most justified underspecifications in all of Scheme.  Each
of these underspecifications concerns something that programmers ordinarily
do not care about because it doesn't matter; they have the effect of
requiring programmers to write some explicit code in the exceptional case
when they do want to use a specific value or order of evaluation.  If
these underspecifications were "fixed", programs would be harder to read
because you would have to assume that the order matters whenever you see
a procedure call or internal definitions.  As things stand now, you know
the order doesn't matter and this fact makes it easier to understand the
program.

In my opinion, the language would be improved if side-effecting procedures
had to return #!unspecified.  This issue is a little different from the
order of evaluation of arguments and the order of definitions because it
is often (i.e. except for tail-recursive positions) obvious that the value
returned by a side-effecting procedure is just thrown away.  Furthermore we
probably could standardize on some useless value like #!unspecified or 34
if only we could agree, but the perceived need for compatibility with
previous implementations or with Common Lisp makes it difficult for us to
agree.

Peace, Will

Received: from RELAY.CS.NET (TCP 1201000005) by MC.LCS.MIT.EDU 17 Jun 88 20:15:55 EDT
Received: from relay2.cs.net by RELAY.CS.NET id ab18564; 17 Jun 88 19:35 EDT
Received: from tektronix.tek.com by RELAY.CS.NET id aa01518; 17 Jun 88 19:30 EDT
Received: by tektronix.TEK.COM (5.51/6.24)
	id AA14094; Fri, 17 Jun 88 14:39:52 PDT
Received: by tekchips.CRL.TEK.COM (5.51/6.24)
	id AA21656; Fri, 17 Jun 88 14:41:03 PDT
Message-Id: <8806172141.AA21656@tekchips.CRL.TEK.COM>
To: ramsdell%linus@MITRE-BEDFORD.ARPA, tiedeman@ACF3.NYU.EDU
Cc: rrrs-authors@mc.lcs.mit.edu, willc@tekchips.crl
Subject: Re: Dependency analysis on internal DEFINE's
In-Reply-To: Your message of Thu, 16 Jun 88 07:35:25 EDT.
	     <8806161135.AA19943@darwin.sun.uucp>
Date: 17 Jun 88 14:41:01 PDT (Fri)
From: willc@tekchips.crl

I guess I don't understand what is being proposed, because it doesn't look
computable to me.  Here are the proposals, followed by a couple of examples
that illustrate my lack of understanding.

  [Tiedeman:]
  This can also be made to work by having LETREC's implement an applicative
  order fixpoint rather than the restriction of it specified in R3RS.  This 
  amounts to performing dependency analysis to transform the above into a LET*.
  Alas, this requires static analysis which an interpreter can't afford.  Some
  compilers, however, already do it.

  [Ramsdell:]
  I strongly agree that a dependency analysis should be done on local
  defines.  One simply finds the strong component of the dependency
  graph and then does a topological sort on the graph in which a strong
  component has been replaced by a single node.

Example 1:

  (let ((x '(a b c)))
    (define y
      (list (lambda (a) (cons a z)) x))
    (define z
      (list (lambda (a) (cons y a)) x))
    (append y z))

  This is allowed by the wording in the R3RS, and returns
  (#<PROCEDURE> (a b c) #<PROCEDURE> (a b c)).  Presumably it would
  also be allowed by the new proposal and would return the same thing.
  If not, the new proposal would not be a generalization of the current
  state of affairs since it would be less general in this case.

Example 2:

  (let ((x '(a b c)))
    (define y
      (map (lambda (a) (cons a z)) x))
    (define z
      (map (lambda (a) (cons y a)) x))
    (append y z))

  This is not allowed by the wording in the R3RS.  It signals an error
  in MacScheme, and probably does something similar in most other
  implementations.  I do not know whether it would be allowed by the
  proposal.  If it would be allowed, what would it return?  If it is
  not allowed, then how can the proposal possibly be implemented while
  still allowing separate compilation for procedures like list and map?


  [Ramsdell:]
  PS. By the way, many pure functional programming languges do the above
  analysis; see Simon L. Peyton Jones' recent book on implementing
  functional programming languages.

I understand how to implement general fixed points for non-strict
languages, which are the kind that Peyton Jones is concerned with.  The
thing I don't understand is how an "applicative order" fixed point can
be a generalization of the current state of affairs while remaining
computable through static analysis.

Peace, Will

Received: from Think.COM (TCP 1201000006) by MC.LCS.MIT.EDU 17 Jun 88 18:15:06 EDT
Return-Path: <gls@Think.COM>
Received: from kali.think.com by Think.COM; Fri, 17 Jun 88 18:21:03 EDT
Received: by kali.think.com; Fri, 17 Jun 88 18:20:58 EDT
Date: Fri, 17 Jun 88 18:20:58 EDT
From: gls@Think.COM
Message-Id: <8806172220.AA14999@kali.think.com>
To: KMP@stony-brook.scrc.symbolics.com
Cc: JAR@ai.ai.mit.edu, willc%tekchips.tek.com@relay.cs.net,
        KMP@stony-brook.scrc.symbolics.com, rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Kent M Pitman's message of Fri, 17 Jun 88 16:09 EDT <880617160937.3.KMP@RIO-DE-JANEIRO.SCRC.Symbolics.COM>
Subject: new wording for eqv?

   Date: Fri, 17 Jun 88 16:09 EDT
   From: Kent M Pitman <KMP@stony-brook.scrc.symbolics.com>

   I observe as an aside also that your description is somewhat
   meta-circular, though perhaps not enough to worry about here. You
   effectively begin by saying that EQV? computes whether two things
   are distinct (for which i read "not the same"), and yet the
   terminology uses the word "the same" all over the place.

Plus ca change, plus c'est la meme chose.

Received: from Think.COM (TCP 1201000006) by MC.LCS.MIT.EDU 17 Jun 88 16:38:49 EDT
Return-Path: <gls@Think.COM>
Received: from kali.think.com by Think.COM; Fri, 17 Jun 88 16:45:37 EDT
Received: by kali.think.com; Fri, 17 Jun 88 16:45:34 EDT
Date: Fri, 17 Jun 88 16:45:34 EDT
From: gls@Think.COM
Message-Id: <8806172045.AA14888@kali.think.com>
To: ramsdell%linus@mitre-bedford.arpa
Cc: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: John D. Ramsdell's message of Wed, 15 Jun 88 13:33:24 EDT <8806151733.AA20022@orbit.sun.uucp>
Subject: days-after-J2000.0

   Posted-From: The MITRE Corp., Bedford, MA
   From: John D. Ramsdell <ramsdell%linus@MITRE-BEDFORD.ARPA>
   Posted-Date: Wed, 15 Jun 88 13:33:24 EDT
   Date: Wed, 15 Jun 88 13:33:24 EDT

   I meant UT1.  Here is a proposal for adding the function
   days-after-J2000.0.  Forget seconds-after-J2000.0.

Here is a proposal for seconds-after-J2000.0 (inspired by Hal):

(seconds-after-J2000.0)					procedure
seconds-after-J2000.0 returns a real number equal to -946684800 plus
whatever time(0) feels like returning on your Unix system that day.


--Quux

Received: from STONY-BROOK.SCRC.Symbolics.COM (TCP 20024224620) by MC.LCS.MIT.EDU 17 Jun 88 16:11:17 EDT
Received: from RIO-DE-JANEIRO.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 421293; Fri 17-Jun-88 16:09:56 EDT
Date: Fri, 17 Jun 88 16:09 EDT
From: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>
Subject: new wording for eqv?
To: JAR@AI.AI.MIT.EDU, willc%tekchips.tek.com@RELAY.CS.NET
cc: KMP@STONY-BROOK.SCRC.Symbolics.COM, rrrs-authors@mc.lcs.mit.edu
In-Reply-To: <8806160031.AA18571@tekchips.CRL.TEK.COM>,
             <399349.880617.JAR@AI.AI.MIT.EDU>
Message-ID: <880617160937.3.KMP@RIO-DE-JANEIRO.SCRC.Symbolics.COM>

    Date: 15 Jun 88 17:31:29 PDT (Wed)
    From: willc@tekchips.crl

    ... obj1 and obj2 are pairs created at the same time by
    the same call to cons, ...
    ... obj1 and obj2 are vectors created at the same time by
    the same call to make-vector, ...
    etc.

If an object satisfied all other properties of a vector but was not
created by make-vector (eg, was pre-allocated with the system or created
by some internal routine in the process of loading or some such) would
EQV? not be required to return T?  I feel funny about defining things in
terms of the operator that does the creation unless you say that no
other operator is permitted to do such creation.

I am also uncomfortable with the phrase "at the same time".  Either it
is redundant with "by the same call" or else it is insufficient. If "the
same call" means the dynamic invocation of a function at runtime as
opposed to the lexical reference to the call on paper, then I assert
that "by the same call" is simply redundant. We often speak loosely of a
function returning "more than once" when people play fun games with
generalized catch but I don't think we ever talk about two calls to the
same continuation as being the same "call".

On the other hand, if you think "call" refers to a lexical reference
(which i hope you don't), then if you worry about multiprocessing (and
yes, here i'm for once being careful about my wording), there is a
concern about whether two calls can really occur at the same time (ie,
what is the granularity of time and/or does it matter that temporal
coincidence cannot be observed and you have to just always worry that it
might have happened), so you need to speak about control threads or "the
same place" (ie, same processor) or something more.

Also, even with Jonathan's fixes to the symbol clause to remove the
reference to printing, you still need to address gensyms. I suggest
that once you figure out how to correct the wordings I'm grumbling about
above, you do the same thing for symbols as you did with lists, etc.
That is:

 If the symbols are interned, then <<stuff with jonathan's fixes>>
 If the symbols are not interned, then <<something about how they
 were created by the same call to the function which makes an
 uninterned symbol>>.

I observe as an aside also that your description is somewhat
meta-circular, though perhaps not enough to worry about here. You
effectively begin by saying that EQV? computes whether two things
are distinct (for which i read "not the same"), and yet the
terminology uses the word "the same" all over the place. That is,
you talk about "the same time" and "the same call". In my mind,
flags go up as I try to decide what these phrases mean since I'm
in the middle of defining what that means. Fortunately, I have other
knowledge to appeal to, but it does leave me wondering whether if
people can be relied on to use such other knowledge, perhaps they
could also be relied upon to just understand just the first 
paragraph in the absence of all the elaboration. I'm not proposing
any change here -- I'm just being amused. This is the sort of things
that must have driven Webster and his successors nuts...

Received: from iuvax.cs.indiana.edu (TCP 30003147300) by MC.LCS.MIT.EDU 17 Jun 88 14:40:28 EDT
Received: by iuvax.cs.indiana.edu; id AA18003; Fri, 17 Jun 88 13:07:39 EST
Received: by iuvax.cs.indiana.edu (5.54/1.5) 
Date: Fri, 17 Jun 88 13:07:39 EST
From: R. Kent Dybvig <dyb@iuvax.cs.indiana.edu>
To: rrrs-authors@mc.lcs.mit.edu
Subject: Re:  char-ready? => read-char-ready?

The only references to TYI-NO-HANG I can find in my archive, which I
believe goes all the way back, is contained in the following note
from Will Clinger, who quotes from an earlier note from Kent Pitman:

>KMP:
>    Also on p30, it seems to me that the notion of CHAR-READY? is not a
>    useful one.  It's subject to timing errors in multi-processed systems
>    and/or systems which allow asynchronous interrupts. The Lisp Machine's
>    TYI-NO-HANG paradigm is much better, since it has a more test-and-set
>    feel to it and is more easy to use reliably. I suggest that CHAR-READY?
>    should be flushed and replaced by a READ-CHAR? which returns either a
>    character if one is ready, or NIL otherwise.  This gets you out of the
>    bind with rubbing out stuff that CHAR-READY? has noticed, which is really
>    an awful crock. I believe that TYI-NO-HANG will interact satisfactorily
>    with Lispm-style rubout handlers.
>
>To some extent I agree with this, but I don't think READ-CHAR? by itself
>is any better for multi-processing than CHAR-READY?.
>
>Peace, Will

I am in favor of the change, and I like Jonathan's suggestion to use the
name "read-char-if-ready".

Kent

Received: from iuvax.cs.indiana.edu (TCP 30003147300) by MC.LCS.MIT.EDU 17 Jun 88 14:39:51 EDT
Received: by iuvax.cs.indiana.edu; id AA18514; Fri, 17 Jun 88 13:16:09 EST
Received: by iuvax.cs.indiana.edu (5.54/1.5) 
Date: Fri, 17 Jun 88 13:16:09 EST
From: R. Kent Dybvig <dyb@iuvax.cs.indiana.edu>
To: rrrs-authors@mc.lcs.mit.edu
Subject: Re:  char-ready? => read-char-ready?

>I am in favor of the change, and I like Jonathan's suggestion to use the
>name "read-char-if-ready".
>
>Kent

Oops---Carl Bruggeman just pointed out that this does not generalize
easily to "read-if-ready".   At least, "read-if-ready" would require
an additional argument, namely an object to return if nothing is
ready.  So, the change to "read-char-if-ready" is acceptable to me
based on Pitman's comments, though it isn't as nice as I thought at
first.  Will seemed to be refuting Kent's claim that "read-char?" is
better for multiprocessing---Will, if you remember your thoughts,
maybe you can explain a little bit further.

Kent

Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 17 Jun 88 13:50:39 EDT
Date: Fri, 17 Jun 88 13:51:49 EDT
From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Subject:  new wording for eqv?
To: "WILLC@TEKCHIPS.CRL"@AI.AI.MIT.EDU
cc: rrrs-authors@MC.LCS.MIT.EDU
In-reply-to: Msg of 15 Jun 88 17:31:29 PDT (Wed) from willc@tekchips.crl
Message-ID: <399349.880617.JAR@AI.AI.MIT.EDU>

I approve of this.  I'm not sure it's complete, but I suspect it's close
enough for all practical purposes.

Nothing is said about quoted structure; is this because the description
of QUOTE says enough?

I'm not happy about "print the same way", because printing is poorly
defined.  I'd rather say "STRING=? of SYMBOL->STRING of obj1 and obj2 is
true".

Also, I don't think it specifies to what the following MAY evaluate:

  (letrec ((f (lambda () (if (eqv? f g) 'both 'f)))
	   (g (lambda () (if (eqv? f g) 'both 'g))))
    (eqv? f g))

Certainly, if F and G have different behavior, then the call to EQV? must
return false; but the question of whether they have different behavior
depends on what EQV? does.  If I consider the report as a predicate to be
applied to <implementation, program, program's-input> tuples to
determine whether a particular implementation conforms on that program
with that input, then the report itself is underspecified.  (Of course
conformance may not be a computable function, but that doesn't
bother me.)

Note that
  (letrec ((f (lambda () (if (eqv? f g) 'f 'both)))
	   (g (lambda () (if (eqv? f g) 'g 'both))))
    (eqv? f g))
isn't a problem since a proof by contradiction gives the answer:
if they are EQV?, then they do the same thing [def. of EQV?], which means
they do different things [def. of F & G], contradiction; therefore they
cannot be EQV?.

Should we add a caveat somewhere to the effect that if conformance
cannot be refuted, then it holds?  Hmm, then if refutability cannot
be refuted, then, uhh...


Received: from ZERMATT.LCS.MIT.EDU (CHAOS 17316) by MC.LCS.MIT.EDU 17 Jun 88 13:10:50 EDT
Received: from ASPEN.LCS.MIT.EDU by ZERMATT.LCS.MIT.EDU via CHAOS with CHAOS-MAIL id 164930; Fri 17-Jun-88 13:09:50 EDT
Date: Fri, 17 Jun 88 13:12 EDT
From: Robert Halstead <rhh@VX.LCS.MIT.EDU>
Subject: Re: parallel argument evaluation
To: hudak-paul@YALE.ARPA
cc: rhh@VX.LCS.MIT.EDU, tiedeman@acf3.NYU.EDU,
    rrrs-authors@MC.LCS.MIT.EDU
In-Reply-To: <8806171519.AA25761@ATHENA.CS.YALE.EDU>
Message-ID: <880617131203.5.RHH@ASPEN.LCS.MIT.EDU>

    Yes, this is a good example, as was Tiedeman's.  But a very small 
    change to your example:

	(- (rand) (rand))

    makes even sequential programs unportable!  Sigh ... :-(

True, depending slightly, I suppose, as to whether you consider drawing
different elements out of the same statistical distribution to be a
violation of portability!  Seriously, though, if you have procedures
that, as a side effect, count the number of times they are called, or
perform similar side effects that may not even affect what is returned
directly as a value, evaluating arguments genuinely in parallel requires
a much tighter coding style than just evaluating them sequentially
according to some unspecified permutation...		-Bert

Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 17 Jun 88 13:02:16 EDT
Date: Fri, 17 Jun 88 13:03:18 EDT
From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Subject:  char-ready? => read-char-ready?
To: dyb@IUVAX.CS.INDIANA.EDU
cc: rrrs-authors@MC.LCS.MIT.EDU
In-reply-to: Msg of Tue 14 Jun 88 22:21:30 EST from R. Kent Dybvig <dyb@iuvax.cs.indiana.edu>
Message-ID: <399322.880617.JAR@AI.AI.MIT.EDU>

I wouldn't mind changing the name, but READ-CHAR-READY? isn't good
English; READY-TO-READ-CHAR? would be better.  (Or how about ((READY-TO?
READ-CHAR) port)?  Just kidding.)  However, I agree with KMP that the
functionality is wrong and that a TYI-NO-HANG-like procedure is
preferable.  I can't remember why we didn't do that back when it would
have been easy.  Maybe a resonable name for that would be
READ-CHAR-IF-READY.

I would check the archives now, but the disk drive that carries that
pack has been having troubles.  I'll get them off of backup tape, unless
either someone remembers, or someone has access to the archives and can
do a search.


Received: from ELI.CS.YALE.EDU (TCP 30006454001) by MC.LCS.MIT.EDU 17 Jun 88 12:44:04 EDT
Received: by ELI.CS.YALE.EDU; Fri, 17 Jun 88 12:42:44 EDT
From: Paul Hudak <hudak-paul@YALE.ARPA>
Full-Name: Paul Hudak
Message-Id: <8806171642.AA17986@ELI.CS.YALE.EDU>
Received: by yale-ring (node-add2/ADD2) 
          via WIMP-MAIL (Version 1.3/1.5) ; Fri Jun 17 12:40:15
Date: Fri, 17 Jun 88 12:40:08 EDT
Subject: Re: parallel argument evaluation
To: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Cc: rrrs-authors@MC.LCS.MIT.EDU
In-Reply-To: Jonathan A Rees <JAR@AI.AI.MIT.EDU>, Fri, 17 Jun 88 12:05:02 EDT

    There's a big difference between "deterministic" and "portable".

Yes, good point, which I agree with.

  -Paul
-------


Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 17 Jun 88 12:04:30 EDT
Date: Fri, 17 Jun 88 12:05:02 EDT
From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Subject:  parallel argument evaluation
To: hudak-paul@YALE.ARPA
cc: tiedeman@ACF3.NYU.EDU, rrrs-authors@MC.LCS.MIT.EDU,
    rhh@VX.LCS.MIT.EDU
Message-ID: <399279.880617.JAR@AI.AI.MIT.EDU>

    Date: Fri, 17 Jun 88 11:26:01 EDT
    From: Paul Hudak <hudak-paul@YALE.ARPA>

    But a very small change to your example:

        (- (rand) (rand))

    makes even sequential programs unportable!  Sigh ... :-(

There's a big difference between "deterministic" and "portable".  If
this program is only specified to return the difference of two random
numbers, then the above works fine with indeterminate order, but not
with parallel argument evaluation.  Similarly, a program that
accumulates results by doing (set! foo (cons result foo)) variable may
not care in what order the results appear, so long as they do appear in
some order.  So it's okay for the results to be so accumulated as side
effects of argument computations.


Received: from ATHENA.CS.YALE.EDU (TCP 20011000033) by MC.LCS.MIT.EDU 17 Jun 88 11:30:29 EDT
Received: by ATHENA.CS.YALE.EDU; Fri, 17 Jun 88 11:19:40 EDT
From: Paul Hudak <hudak-paul@YALE.ARPA>
Full-Name: Paul Hudak
Message-Id: <8806171519.AA25761@ATHENA.CS.YALE.EDU>
Received: by yale-ring (node-add2/ADD2) 
          via WIMP-MAIL (Version 1.3/1.5) ; Fri Jun 17 11:26:09
Date: Fri, 17 Jun 88 11:26:01 EDT
Subject: Re: parallel argument evaluation
To: Robert Halstead <rhh@VX.LCS.MIT.EDU>
Cc: tiedeman@acf3.NYU.EDU, rrrs-authors@MC.LCS.MIT.EDU
In-Reply-To: Robert Halstead <rhh@VX.LCS.MIT.EDU>, Fri, 17 Jun 88 11:05 EDT

    I would agree; on the other hand, the degree is quite significant.
    Suppose you define a random-number-generator rand by
    	(define rand
    	  (let ((seed (initial-random-seed)))
    	    (lambda ()
    	      (set! seed (random-update seed))
    	      seed)))
    and then you write programs like
    	(+ (rand) (rand))
    
Yes, this is a good example, as was Tiedeman's.  But a very small 
change to your example:

    (- (rand) (rand))

makes even sequential programs unportable!  Sigh ... :-(

    -Paul
-------


Received: from ZERMATT.LCS.MIT.EDU (CHAOS 17316) by MC.LCS.MIT.EDU 17 Jun 88 11:05:13 EDT
Received: from ASPEN.LCS.MIT.EDU by ZERMATT.LCS.MIT.EDU via CHAOS with CHAOS-MAIL id 164873; Fri 17-Jun-88 11:03:17 EDT
Date: Fri, 17 Jun 88 11:05 EDT
From: Robert Halstead <rhh@VX.LCS.MIT.EDU>
Subject: parallel argument evaluation
To: hudak-paul@YALE.ARPA
cc: tiedeman@acf3.NYU.EDU, rrrs-authors@MC.LCS.MIT.EDU
In-Reply-To: <8806162005.AA10637@ELI.CS.YALE.EDU>
Message-ID: <880617110528.3.RHH@ASPEN.LCS.MIT.EDU>

	... It seems unreasonable to insist that all Scheme programmers must 
	follow Multilisp style standards if their code is to be portable, and 
	doubly so when we aren't providing any synchronization constructs.

    I'm inclined to agree, but we're already doing that to some extent, by
    requiring that portable code not depend on order-of-sequential-evaluation 
    of arguments.  So you see it's really a matter of degree.

I would agree; on the other hand, the degree is quite significant.
Suppose you define a random-number-generator rand by

	(define rand
	  (let ((seed (initial-random-seed)))
	    (lambda ()
	      (set! seed (random-update seed))
	      seed)))

and then you write programs like

	(+ (rand) (rand))

This works fine for any sequential argument evaluation order, but the
updating of the random number seed is not safe if multiple calls to rand
are active concurrently.  Lots of other cases of procedure arguments
whose evaluation involves side effects (but not in a way that breaks if
a different sequential evaluation order is used) are analogous.

If you're writing genuinely parallel code (as in Multilisp or Qlisp)
then you probably want to strongly encourage people to change their
random number generators so that it is safe for multiple random number
generations to be active concurrently.  But I suspect that the Scheme
community would balk at having to do this in order to make their
programs "truly" portable.				-Bert Halstead

Received: from mitre-bedford.ARPA (TCP 3200600102) by MC.LCS.MIT.EDU 17 Jun 88 08:27:09 EDT
Posted-From: The MITRE Corp., Bedford, MA
Received: from darwin.sun.uucp by linus.MENET (3.2/4.7)
	id AA24517; Fri, 17 Jun 88 08:22:26 EDT
From: John D. Ramsdell <ramsdell%linus@mitre-bedford.ARPA>
Posted-Date: Fri, 17 Jun 88 08:21:53 EDT
Received: by darwin.sun.uucp (3.2/SMI-3.0DEV3)
	id AA20941; Fri, 17 Jun 88 08:21:53 EDT
Date: Fri, 17 Jun 88 08:21:53 EDT
Message-Id: <8806171221.AA20941@darwin.sun.uucp>
To: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Hal Abelson's message of Wed, 15 Jun 88 12:11:42 edt <8806151611.AA03404@murren>
Subject: days-after-J2000.0
Church: Our Lady of Balanced Parentheses

Another try....


(days-after-J2000.0)					procedure
days-after-J2000.0 returns a real number giving the current universal
time (UT1) minus the universal time at Noon of January 1, 2000 GMT.
Small time differences are accurate to within a second.  The unit of
universal time is a mean solar day.  The universal time UT1 is the
siderial time corrected to mean solar time and corrected for polar
movement.  J2000.0 is the Julian epoch of the time origin.



Received: from acf3.NYU.EDU (TCP 20036500015) by MC.LCS.MIT.EDU 16 Jun 88 17:09:19 EDT
Received:  by acf3.NYU.EDU (5.54/25-eef)
	id AA06337; Thu, 16 Jun 88 17:08:20 EDT
Date: Thu, 16 Jun 88 17:08:20 EDT
From: Eric S. Tiedemann <tiedeman@acf3.NYU.EDU>
Message-Id: <8806162108.AA06337@acf3.NYU.EDU>
To: hudak-paul@YALE.ARPA
Subject: Re:  More on Full Specification
Cc: rrrs-authors@mc.lcs.mit.edu


	From: Paul Hudak <hudak-paul@YALE.ARPA>
	
	I think you missed the point -- I wasn't arguing for parallel 
	semantics.  The question was whether or not PERMUTE was overspecified,
	which I claim only goes half-way even in the sequential case.
	
Well, someone missed the point.  The record speaks for itself.  Anyhow, I'm 
glad to see that we don't really disagree. 

	[In the matter of an implementation's permuting different ways at
	 different times when useful...]    
	    	
	Are you aware then that you are not in conformance with the report?

No, I'm in conflict with the denotational semantics which the report describes
as "a closer approximation to the intended semantics than a left-to-right
evaluation would be."  The discrepancy is in the report and I think everyone
would like to see it fixed.	

Eric
	
	
	

Received: from RELAY.CS.NET (TCP 1201000005) by MC.LCS.MIT.EDU 16 Jun 88 16:24:38 EDT
Received: from relay2.cs.net by RELAY.CS.NET id aq29344; 16 Jun 88 14:02 EDT
Received: from tektronix.tek.com by RELAY.CS.NET id ab00726; 16 Jun 88 13:45 EDT
Received: by tektronix.TEK.COM (5.51/6.24)
	id AA21777; Wed, 15 Jun 88 17:38:24 PDT
Received: by tekchips.CRL.TEK.COM (5.51/6.24)
	id AA18639; Wed, 15 Jun 88 17:39:43 PDT
Message-Id: <8806160039.AA18639@tekchips.CRL.TEK.COM>
To: rrrs-authors@mc.lcs.mit.edu
Subject: formal semantics of numeric constants
Date: 15 Jun 88 17:39:41 PDT (Wed)
From: willc@tekchips.crl

Someone said they'd be interested in seeing a formal semantics for numeric
constants.  I'd like to see a semantics for numeric constants added to RnRS,
but I think a formal semantics is overkill.  Anyway, here's my first shot
at what a formal semantics might look like.  Let me know of any bugs you
find -- it hasn't been tested, or even proofread!

For those who, like me, don't really want to read this thing, the idea is
that constants are inexact if they contain any of the following:

  an explicit inexactness prefix
  an at-sign indicating polar representation
  a decimal point
  a sharp sign indicating a "don't care" digit, as in 123##

A constant may also be inexact if it contains a negative exponent;
this is implementation-dependent.  Otherwise the constant is exact.

  Issue:  3@0     (inexact by above rules)
  Issue:  1e5     (exact by above rules)
  Issue:  1e-5    (implementation-dependent by above rules)




A denotational semantics for numeric constants

There are two properties of a numeric constant in Scheme
that matter:  its value (a complex number) and its exactness.
These properties correspond to the valuation functions V and
E below.

V [ <prefix R> <complex R> ]  =  V [ <complex R> ]

V [ <real1 R> @ <real2 R> ]
  =  V [ <real1 R> ] * (cos V [ <real2 R> ] + i sin V [ <real2 R> ])

V [ <real1 R> + i <real2 R> ] = V [ <real1 R> ] + i V [ <real2 R> ]

V [ <real1 R> - i <real2 R> ] = V [ <real1 R> ] - i V [ <real2 R> ]

V [ <real1 R> + i ] = V [ <real1 R> ] + i

V [ <real1 R> - i ] = V [ <real1 R> ] - i

V [ + i <real2 R> ] = i V [ <real2 R> ]

V [ - i <real2 R> ] = - i V [ <real2 R> ]

V [ + i ]  =  i

V [ - i ]  =  - i

V [ <uinteger 10> <suffix> ]  =  V [ <uinteger 10> ] * 10 ^ X [ <suffix> ]

V [ . <digit>+ #* <suffix> ]  =  (W [ . <digit>+ ] / 10) * 10 ^ X [ <suffix> ]

V [ <digit>+ . <digit>* #* <suffix> ]  =  W [ <digit>+ . <digit>* ] * 10 ^ X [ <suffix> ]

V [ <digit>+ #* . #* <suffix> ]  =  W [ <digit>+ #* ] * 10 ^ X [ <suffix> ]

V [ <uinteger1 R> / <uinteger2 R> ]  =  V [ <uinteger1 R> ] / V [ <uinteger2 R> ]

V [ + <ureal R> ]  =  V [ <ureal R> ]

V [ - <ureal R> ]  =  - V [ <ureal R> ]

V [ <digit R>+ #* # ]  =  R * V [ <digit R>+ #* ]

V [ <digit R>* <digit R> ]  =  R * V [ <digit R>* ] + Y [ <digit R> ]

V [ ]  =  0


W [ <digit>+ #* # ]  =  10 * W [ <digit>+ #* ]

W [ <digit>* <digit> ]  =  10 * W [ <digit>* ] + Y [ <digit> ]

W [ ]  =  0

W [ <digit(s)1>* . <digit(s)2>* ]  =  W [ <digit(s)1>* ] + W [ . <digit(s)2>* ]

W [ . <digit> <digit>* ]  =  (Y [ <digit> ] + W [ . <digit>* ]) / 10

W [ . ]  =  0


X [ <exponent marker> + <digit>+ ]  =  W [ <digit>+ ]

X [ <exponent marker> - <digit>+ ]  =  - W [ <digit>+ ]

X [ <exponent marker> <digit>+ ]  =  W [ <digit>+ ]


Y [ 0 ]  =  0
Y [ 1 ]  =  1
Y [ 2 ]  =  2
Y [ 3 ]  =  3
Y [ 4 ]  =  4
Y [ 5 ]  =  5
Y [ 6 ]  =  6
Y [ 7 ]  =  7
Y [ 8 ]  =  8
Y [ 9 ]  =  9
Y [ a ]  =  10
Y [ b ]  =  11
Y [ c ]  =  12
Y [ d ]  =  13
Y [ e ]  =  14
Y [ f ]  =  15




E [ <radix R> #e <complex R> ]  =  exact

E [ <radix R> #i <complex R> ]  =  inexact

E [ #e <radix R> <complex R> ]  =  exact

E [ #i <radix R> <complex R> ]  =  inexact

E [ <radix R> <complex R> ]  =  E [ <complex R> ]

E [ <real1 R> @ <real2 R> ]  =  inexact (issue: exception for <real R>@0 ?)

E [ <real1 R> + i <real2 R> ]  =  E [ <real1 R> ] % E [ <real2 R> ]

E [ <real1 R> - i <real2 R> ]  =  E [ <real1 R> ] % E [ <real2 R> ]

E [ <real1 R> + i ]  =  E [ <real1 R> ]

E [ <real1 R> - i ]  =  E [ <real1 R> ]

E [ + i <real2 R> ]  =  E [ <real2 R> ]

E [ - i <real2 R> ]  =  E [ <real2 R> ]

E [ + i ]  =  exact

E [ - i ]  =  exact

E [ <uinteger 10> <exponent marker> + <digit>+ ]  =  exact

E [ <uinteger 10> <exponent marker> - <digit>+ ]  =  unspecified

E [ . <digit>+ #* <suffix> ]  =  inexact

E [ <digit>+ . <digit>* #* <suffix> ]  =  inexact

E [ <digit>+ #* . #* <suffix> ]  =  inexact

E [ <uinteger1 R> / <uinteger2 R> ]  =  exact

E [ + <ureal R> ]  =  E [ <ureal R> ]

E [ - <ureal R> ]  =  E [ <ureal R> ]

E [ <digit R>+ #* # ]  =  inexact

E [ <digit R>* <digit R> ]  =  exact


exact % exact      =  exact
exact % inexact    =  inexact
inexact % exact    =  inexact
inexact % inexact  =  inexact


Exactness is not specified for constants such as:

    1000e-2

Otherwise numbers are inexact if they contain

  an explicit inexactness prefix
  an at-sign indicating polar representation
  a decimal point
  a sharp sign indicating a "don't care" digit

Received: from RELAY.CS.NET (TCP 1201000005) by MC.LCS.MIT.EDU 16 Jun 88 16:23:55 EDT
Received: from relay2.cs.net by RELAY.CS.NET id ap29344; 16 Jun 88 14:02 EDT
Received: from tektronix.tek.com by RELAY.CS.NET id aa00723; 16 Jun 88 13:43 EDT
Received: by tektronix.TEK.COM (5.51/6.24)
	id AA21507; Wed, 15 Jun 88 17:30:13 PDT
Received: by tekchips.CRL.TEK.COM (5.51/6.24)
	id AA18571; Wed, 15 Jun 88 17:31:31 PDT
Message-Id: <8806160031.AA18571@tekchips.CRL.TEK.COM>
To: rrrs-authors@mc.lcs.mit.edu
Subject: new wording for eqv?
Date: 15 Jun 88 17:31:29 PDT (Wed)
From: willc@tekchips.crl

Eliminate the second and third paragraphs of section 6.2, and
eliminate the seven bullet items that follow them.

Change the description of eqv? as follows.



(eqv? obj1 obj2)                          essential procedure

The eqv? procedure defines a useful equivalence relation on
objects.  Briefly, it returns #t if obj1 and obj2 should normally
be regarded as the same object and returns #f if they should
normally be regarded as distinct objects.  This relation is left
slightly open to interpretation, but the following partial
specification of eqv? holds for all implementations of Scheme.

The eqv? procedure returns #t if:

obj1 and obj2 are both #t or both #f.

obj1 and obj2 are both symbols and both print the same
way (provided neither obj1 nor obj2 is an ``uninterned
symbol'' as alluded to in section 6.4).

obj1 and obj2 are both numbers, are numerically equal
(see =, section 6.5.4), and are either both exact or
both inexact (see section 6.5.2).

obj1 and obj2 are both characters and are the same
character according to the char=? procedure (section
6.6).

both obj1 and obj2 are the empty list.

obj1 and obj2 are pairs created at the same time by
the same call to cons, so that a set-car! operation
on obj1 will change the contents of the car field of
obj2 and vice versa, and similarly for set-cdr!.

obj1 and obj2 are vectors created at the same time by
the same call to make-vector, so that a vector-set!
operation on obj1 will change the contents of the
corresponding element of obj2 and vice versa.

obj1 and obj2 are strings created at the same time by
the same call to make-string, so that a string-set!
operation on obj1 will change the character stored at
the corresponding position of obj2 and vice versa.

obj1 and obj2 are procedures created at the same time
from the same lambda expression, so that they behave
identically.


The eqv? procedure returns #f if:

one of obj1 and obj2 is a boolean but the other is not.

one of obj1 and obj2 is a symbol but the other is not.

one of obj1 and obj2 is a number but the other is not.

one of obj1 and obj2 is a pair but the other is not.

one of obj1 and obj2 is a vector but the other is not.

one of obj1 and obj2 is a string but the other is not.

one of obj1 and obj2 is a procedure but the other is not.

one of obj1 and obj2 is #t but the other is #f.

obj1 and obj2 are symbols that do not print the same way.

one of obj1 and obj2 is an exact number and the other is an
inexact number.

obj1 and obj2 are numbers for which the = procedure returns
#f.

obj1 and obj2 are characters for which the char=? procedure
returns #f.

one of obj1 and obj2 is the empty list but the other is not.

obj1 and obj2 are pairs created at different times by
distinct calls to cons.

obj1 and obj2 are vectors created at different times by
distinct calls to make-vector, and at least one of them
has vector-length greater than zero.

obj1 and obj2 are strings created at different times by
distinct calls to make-string, and at least one of them
has string-length greater than zero.

obj1 and obj2 are procedures that would behave differently
(return a different value or have different side effects)
for some arguments.

[The first block of examples goes here, omitting the
(eq? "" "") example, which should be added to the second
block of examples.]

The following examples illustrate cases in which the above
rules do not fully specify the behavior of eqv?.  In every
case, the value returned by eqv? is either #t or #f, but
which one it returns is implementation-dependent.

[The second block of examples goes here, following by the
paragraph beginning "The next set of examples shows...",
followed by the gen-counter and gen-loser examples.]

Objects of distinct types must never be regarded as the same
object, except that #f and the empty list are permitted
to be identical, and the character type need not be disjoint
from other types.

[The fourth block of examples goes here, followed by the
paragraph beginning "Since it is an error...", followed by
the fifth block of examples, followed by the note.]

Received: from ELI.CS.YALE.EDU (TCP 30006454001) by MC.LCS.MIT.EDU 16 Jun 88 16:06:29 EDT
Received: by ELI.CS.YALE.EDU; Thu, 16 Jun 88 16:05:17 EDT
From: Paul Hudak <hudak-paul@YALE.ARPA>
Full-Name: Paul Hudak
Message-Id: <8806162005.AA10637@ELI.CS.YALE.EDU>
Received: by yale-ring (node-add2/ADD2) 
          via WIMP-MAIL (Version 1.3/1.5) ; Thu Jun 16 16:02:49
Date: Thu, 16 Jun 88 16:02:45 EDT
Subject: Re:  More on Full Specification
To: Eric S. Tiedemann <tiedeman@acf3.NYU.EDU>
Cc: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Eric S. Tiedemann <tiedeman@acf3.NYU.EDU>, Thu, 16 Jun 88 03:45:26 EDT

    	Presumably the motivation for this was to allow implementation
    	freedom, so why only stop half-way? 
    
    It would sure be nice if we could get an implicit PCALL without causing any 
    damage, but going the rest of the way will invalidate currently valid code.  

I think you missed the point -- I wasn't arguing for parallel semantics.
The question was whether or not PERMUTE was overspecified, which I claim
only goes half-way even in the sequential case.

        I wonder how many current implementations permute the arguments in 
        different ways depending on context?  Seems useful to me ... and fully 
        within the motivation for underspecification in the first place.
    
    It is useful.  My current compiler project uses it.
    	
Are you aware then that you are not in conformance with the report?

    ... It seems unreasonable to insist that all Scheme programmers must 
    follow Multilisp style standards if their code is to be portable, and 
    doubly so when we aren't providing any synchronization constructs.

I'm inclined to agree, but we're already doing that to some extent, by
requiring that portable code not depend on order-of-sequential-evaluation 
of arguments.  So you see it's really a matter of degree.

    -Paul
-------


Received: from mitre-bedford.ARPA (TCP 3200600102) by MC.LCS.MIT.EDU 16 Jun 88 13:38:20 EDT
Posted-From: The MITRE Corp., Bedford, MA
Received: from darwin.sun.uucp by linus.MENET (3.2/4.7)
	id AA25836; Thu, 16 Jun 88 13:33:44 EDT
From: John D. Ramsdell <ramsdell%linus@mitre-bedford.ARPA>
Posted-Date: Thu, 16 Jun 88 13:33:14 EDT
Received: by darwin.sun.uucp (3.2/SMI-3.0DEV3)
	id AA20338; Thu, 16 Jun 88 13:33:14 EDT
Date: Thu, 16 Jun 88 13:33:14 EDT
Message-Id: <8806161733.AA20338@darwin.sun.uucp>
To: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Hal Abelson's message of Wed, 15 Jun 88 12:11:42 edt <8806151611.AA03404@murren>
Subject: days-after-J2000.0
Church: Our Lady of Balanced Parentheses

Let us limit the accuracy to about one seconds worth of time.

(days-after-J2000.0)					procedure
days-after-J2000.0 returns a real number giving the current universal
time (UT1) minus the universal time at Noon of January 1, 2000
accurate to within a second.  The unit of universal time is a mean
solar day.  The universal time UT1 is the siderial time corrected to
mean solar time and corrected for polar movement.  J2000.0 is the
Julian epoch of the time origin.

Received: from mitre-bedford.ARPA (TCP 3200600102) by MC.LCS.MIT.EDU 16 Jun 88 07:40:42 EDT
Posted-From: The MITRE Corp., Bedford, MA
Received: from darwin.sun.uucp by linus.MENET (3.2/4.7)
	id AA13523; Thu, 16 Jun 88 07:35:55 EDT
From: John D. Ramsdell <ramsdell%linus@mitre-bedford.ARPA>
Posted-Date: Thu, 16 Jun 88 07:35:25 EDT
Received: by darwin.sun.uucp (3.2/SMI-3.0DEV3)
	id AA19943; Thu, 16 Jun 88 07:35:25 EDT
Date: Thu, 16 Jun 88 07:35:25 EDT
Message-Id: <8806161135.AA19943@darwin.sun.uucp>
To: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Eric S. Tiedemann's message of Wed, 15 Jun 88 17:58:57 EDT <8806152158.AA02650@acf3.NYU.EDU>
Subject:  Dependency analysis on internal DEFINE's

>This can also be made to work by having LETREC's implement an applicative
>order fixpoint rather than the restriction of it specified in R3RS.  This 
>amounts to performing dependency analysis to transform the above into a LET*.
>Alas, this requires static analysis which an interpreter can't afford.  Some
>compilers, however, already do it.

I strongly agree that a dependency analysis should be done on local
defines.  One simply finds the strong component of the dependency
graph and then does a topological sort on the graph in which a strong
component has been replaced by a single node.  A strong component
with no cycles (a single node) maps to a LET, and other strong
components map to a LETREC.  Thus both:

	    (define y (z))
	    (define x (car y))

and

	    (define x (car y))
	    (define y (z))

map to:

	    (let ((y (z)))
	      (let ((x (car y))) .....

There are linear algorithms for both topological sorting and finding
strong components.
John
PS. By the way, many pure functional programming languges do the above
analysis; see Simon L. Peyton Jones' recent book on implementing
functional programming languages.

Received: from acf3.NYU.EDU (TCP 20036500015) by MC.LCS.MIT.EDU 16 Jun 88 05:09:30 EDT
Received:  by acf3.NYU.EDU (5.54/25-eef)
	id AA03130; Thu, 16 Jun 88 03:45:26 EDT
Date: Thu, 16 Jun 88 03:45:26 EDT
From: Eric S. Tiedemann <tiedeman@acf3.NYU.EDU>
Message-Id: <8806160745.AA03130@acf3.NYU.EDU>
To: hudak-paul@YALE.ARPA, tiedeman@acf3.NYU.EDU
Subject: Re:  More on Full Specification
Cc: rrrs-authors@mc.lcs.mit.edu


	From: Paul Hudak <hudak-paul@YALE.ARPA>
	    	
	    From: Eric S. Tiedemann <tiedeman@acf3.NYU.EDU>
	
	    No, not concurrently.  E*, in the semantics, always evaluates in
	    *some* order.  This isn't overspecification, as Paul Hudak suggests
	    ,but rather a deliberate and desirable design decision.
	
	I wasn't around when the decision was made, so can't say whether it
	was "deliberate" or not, but in what sense is it "desireable"?
	Presumably the motivation for this was to allow implementation
	freedom, so why only stop half-way? 

It would sure be nice if we could get an implicit PCALL without causing any 
damage, but going the rest of the way will invalidate currently valid 
code.  Most of the code which would be endangered is certainly in bad style 
already.  Let me offer, however, a real-life example that doesn't seem too 
unnatural:

	(EQV? (SPLAY-TREE-ACCESS T KEY-1)
	      (SPLAY-TREE-ACCESS T KEY-2))

where splay trees are, of course, self-adjusting trees that may be 
destructively modified when an item is retrieved.  I invite you to imagine the 
result of interleaving two splays on the same tree!  It seems unreasonable to 
insist that all Scheme programmers must follow Multilisp style standards if 
their code is to be portable, and doubly so when we aren't providing any 
synchronization constructs.
 
	                                           I wonder how many current
	implementations permute the arguments in different ways depending on
	context?  Seems useful to me ... and fully within the motivation for
	underspecification in the first place.

It is useful.  My current compiler project uses it.
	
	                                            I think that the
	default should be full specification, and that anything left
	underspecified should have a very good rationale.
	
Yes, it seems that underspecification is never "free."

	
	
Eric

Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 15 Jun 88 22:54:40 EDT
Date: Wed, 15 Jun 88 22:54:46 EDT
From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Subject:  days-after-J2000.0
To: ramsdell%linus@MITRE-BEDFORD.ARPA
cc: rrrs-authors@MC.LCS.MIT.EDU
In-reply-to: Msg of Wed 15 Jun 88 13:33:24 EDT from John D. Ramsdell <ramsdell%linus@mitre-bedford.ARPA>
Message-ID: <398372.880615.JAR@AI.AI.MIT.EDU>

    Date: Wed, 15 Jun 88 13:33:24 EDT
    From: John D. Ramsdell <ramsdell%linus@mitre-bedford.ARPA>

    >How do the denotational semantics people handle calendar time, since
    >we all know that anything they do is obviously the right decision in
    >language design?

The same way you handle I/O (e.g. files and network connections), I
presume.  I have seen descriptions that pass around a file system as
well as a store, but since they never seem to part company, I don't
really see the point; and anyhow, that doesn't address the nondeterminism
of external agents.  Are we supposed to put quantum mechanics in our
model?

I don't think it's worth worrying about at the moment; how could any
real-life harm result from just imagining that the time and file system
are in the store, and making it an imaginary side effect to read the
time?  I can't conceive of how this could be consequential, and I'd love
to know if anyone does any reasoning using a formal specification that
could get screwed up by this.


Received: from ELI.CS.YALE.EDU (TCP 30006454001) by MC.LCS.MIT.EDU 15 Jun 88 22:49:23 EDT
Received: by ELI.CS.YALE.EDU; Wed, 15 Jun 88 22:38:58 EDT
From: Paul Hudak <hudak-paul@YALE.ARPA>
Full-Name: Paul Hudak
Message-Id: <8806160238.AA03954@ELI.CS.YALE.EDU>
Received: by yale-ring (node-add2/ADD2) 
          via WIMP-MAIL (Version 1.3/1.5) ; Wed Jun 15 22:36:31
Date: Wed, 15 Jun 88 22:36:24 EDT
Subject: Re:  More on Full Specification
To: Eric S. Tiedemann <tiedeman@acf3.NYU.EDU>
Cc: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Eric S. Tiedemann <tiedeman@acf3.NYU.EDU>, Wed, 15 Jun 88 17:58:57 EDT

    	From: Robert Hieb <hieb@iuvax.cs.indiana.edu>
    	
    	I think the current ``arbitrary permutation'' in the semantics
    	is terrible, since it really doesn't reflect the intent, 
    	which I understand to be that procedure calls may be evaluated in 
    	different orders within the same program, and perhaps even 
    	concurrently.
    	
    From: Eric S. Tiedemann <tiedeman@acf3.NYU.EDU>

    No, not concurrently.  E*, in the semantics, always evaluates in
    *some* order.  This isn't overspecification, as Paul Hudak suggests,
    but rather a deliberate and desirable design decision.

I wasn't around when the decision was made, so can't say whether it
was "deliberate" or not, but in what sense is it "desireable"?
Presumably the motivation for this was to allow implementation
freedom, so why only stop half-way?  My guess is that the intent was
as Robert Hieb states, except for the concurrency part (but maybe that
was in somebody's mind too).  I wonder how many current
implementations permute the arguments in different ways depending on
context?  Seems useful to me ... and fully within the motivation for
underspecification in the first place.

My bet is that Will, when designing the denotational semantics,
specified the underspecification in the simplest deterministic way he
could think of, and that's to use something like PERMUTE.  If there
was a clean way to specify non-determinism, including the
inter-leaving of evaluations, then perhaps he would have chosen that.
(Actually, there are a couple of ways to make PERMUTE dynamic, rather
than fixed, but it gets a little bit messy...)

I guess the bottom line is that we should be VERY careful about what
things we choose to underspecify, and how.  These decisions can have
radical effects on portability and correctness.  I think that the
default should be full specification, and that anything left
underspecified should have a very good rationale.

    -Paul

-------


Received: from STONY-BROOK.SCRC.Symbolics.COM (TCP 20024224620) by MC.LCS.MIT.EDU 15 Jun 88 21:48:20 EDT
Received: from RIO-DE-JANEIRO.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 420360; Wed 15-Jun-88 21:48:01 EDT
Date: Wed, 15 Jun 88 21:47 EDT
From: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>
Subject: A couple more details
To: RRRS-AUTHORS@MC.LCS.MIT.EDU
Message-ID: <880615214746.9.KMP@RIO-DE-JANEIRO.SCRC.Symbolics.COM>

While I'm breaking my silence, I might as well note a couple of other
things that have been on my mind. (I'm pretty busy with X3J13 right now
so haven't had the time to devote to this that I might otherwise, but 
maybe something here will spark some interest in someone who does have
some more time.)

 * Rename "char=?" to "char=", etc.

   Rationale: 
    a. `Symmetry' with "="
    b. I think of "=" as short for "equal?", so "char=?" looks like
       "char-equal??" to my eyes.

 * Rename "set!" to "set".

   Rationale:
    It's redundant. The operation already says in English that the
    operator is destructive. If you have "append" and you make a
    destructive version, it makes some sense to call it either
    "destructive append" or "append!". In the original T manual, I
    specified that "!" was pronounced " destructively" just as I
    specified that "?" was pronounced "-pee". That way people would
    pronounce "zero?" as "zero-pee" and "append!" as
    "append destructively" for verbal compatibility with Lisp
    programmers. In the case of set, though, it feels funny to me
    to say "set destructively" since there is no non-destructive
    version of set.

 * Rename "set-car!" to "set-car", etc.

   Rationale:
    As for "set!", but in these cases I would withdraw the objection
    if someone proposed "set-car", etc. as a non-destructive variant
    in order to motivate the destructively part:

	(DEFINE (SET-CAR X Y) (CONS (CAR Y) X))
	(DEFINE (SET-CDR X Y) (CONS (CAR X) Y))
	...	

    Note: The same argument doesn't make sense for SET! above since
     the non-destructive variant is not appropriately compelling
     (for what I claim are deep reasons):
	(DEFINE (SET X Y) Y)

 * Add essential syntax:
	(CALL procedure . arguments)
	(STATIC identifier)

   Rationale:
    Among other things (I have a few more reasons I might pull out if
    people took this idea seriously), these would allow the entire language
    to be described in terms of a much simpler primitive syntax. eg,
	  (LAMBDA (X) (+ X 3))
    would be shorthand for:
	  (LAMBDA (X) (CALL (STATIC +) (STATIC X) (QUOTE 3)))

    This would be useful as we move into the time when we start doing
    macro expansion, because you could provide a macroexpansion
    facility that guaranteed to always give you the longhand form,
    making it much easier to dispatch off of things because you would
    know that every valid primitive expression in the language was
    represented by a list whose car was a keyword identifying the
    operation. No more of this troublesome stuff, which comes up
    a lot in user code walkers:
	 (LET ((X (MACROEXPAND Y)))
	   (COND ((SYMBOL? X) ...)
		 ((ATOM? X) ...)
		 ((NOT (ATOM (CAR X))) ...)
		 ((MEMBER X '(LAMBDA ...)) ...)
		 (ELSE ;procedure
		  ...)))
    Instead, assuming that (MACROEXPAND 'X) => (STATIC X),
    (MACROEXPAND '3) => (QUOTE 3), etc., then:
	 (LET ((X (MACROEXPAND Y)))
	   (CASE (CAR X)
	    ((QUOTE) ...)
	    ((STATIC) ...)
	    ((CALL) ...)
	    ...))

Received: from acf3.NYU.EDU (TCP 20036500015) by MC.LCS.MIT.EDU 15 Jun 88 19:40:41 EDT
Received:  by acf3.NYU.EDU (5.54/25-eef)
	id AA02650; Wed, 15 Jun 88 17:58:57 EDT
Date: Wed, 15 Jun 88 17:58:57 EDT
From: Eric S. Tiedemann <tiedeman@acf3.NYU.EDU>
Message-Id: <8806152158.AA02650@acf3.NYU.EDU>
To: hieb@iuvax.cs.indiana.edu, rrrs-authors@mc.lcs.mit.edu
Subject: Re:  More on Full Specification


	Date: Wed, 15 Jun 88 13:59:06 EST
	From: Robert Hieb <hieb@iuvax.cs.indiana.edu>
	To: rrrs-authors@mc.lcs.mit.edu
	Subject: More on Full Specification
	
	
	I think the current ``arbitrary permutation'' in the semantics
	is terrible, since it really doesn't reflect the intent, 
	which I understand to be that procedure calls may be evaluated in 
	different orders within the same program, and perhaps even 
	concurrently.
	
No, not concurrently.  E*, in the semantics, always evaluates in *some* order.
This isn't overspecification, as Paul Hudak suggests, but rather a deliberate
and desirable design decision.  If we could get DAYS-AFTER-J2000.0 into the
denotational semantics our problems with PERMUTE would be gone--we could make
it truely POM-dependent.

	such uses as
	    (define x (car y))
	cannot really be considered invalid, 

No one called it invalid, just bad style.

	and something like
	    (define y (z))
	    (define x (car y))
	looks perfectly reasonable, given that all other expressions in a body
	are evaluated in order.
	
This can also be made to work by having LETREC's implement an applicative
order fixpoint rather than the restriction of it specified in R3RS.  This 
amounts to performing dependency analysis to transform the above into a LET*.
Alas, this requires static analysis which an interpreter can't afford.  Some
compilers, however, already do it.

Eric


Received: from kleph (TCP 2206400254) by MC.LCS.MIT.EDU 15 Jun 88 19:33:46 EDT
Received: by kleph.AI.MIT.EDU; Wed, 15 Jun 88 19:08:47 edt
Date: Wed, 15 Jun 88 19:08:47 edt
From: cph@kleph.AI.MIT.EDU (Chris Hanson)
Message-Id: <8806152308.AA04566@kleph>
To: KMP@STONY-BROOK.SCRC.Symbolics.COM
Cc: dyb@iuvax.cs.indiana.edu, rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Kent M Pitman's message of Wed, 15 Jun 88 18:08 EDT <880615180828.6.KMP@RIO-DE-JANEIRO.SCRC.Symbolics.COM>
Subject: alternate track on the char-ready? issue
Reply-To: cph@zurich.ai.mit.edu

   Date: Wed, 15 Jun 88 18:08 EDT
   From: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>

   I strongly believe that CHAR-READY? should not be part of any Scheme standard.

   It is an embarrassing timing error waiting to happen that does not do justice
   to the very careful design of most other parts of this language.

I agree.  However, I want to point out that we already had this
argument, when we originally drafted the standard, and it was decided
that `char-ready?' was preferable to what you call `read-char?' (Jinx
fought on the side you are advocating, as I recall).  I don't remember
why the decision was made as it was but I suggest that someone check
the archives so we don't fight exactly the same battle again.

Received: from STONY-BROOK.SCRC.Symbolics.COM (TCP 20024224620) by MC.LCS.MIT.EDU 15 Jun 88 18:54:30 EDT
Received: from RIO-DE-JANEIRO.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 420262; Wed 15-Jun-88 18:08:46 EDT
Date: Wed, 15 Jun 88 18:08 EDT
From: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>
Subject: alternate track on the char-ready? issue
To: cph@zurich.ai.mit.edu, dyb@iuvax.cs.indiana.edu
cc: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: <8806151410.AA04278@kleph>
Message-ID: <880615180828.6.KMP@RIO-DE-JANEIRO.SCRC.Symbolics.COM>

    Date: Wed, 15 Jun 88 10:10:14 edt
    From: cph@kleph.AI.MIT.EDU (Chris Hanson)

       Date: Tue, 14 Jun 88 22:21:30 EST
       From: R. Kent Dybvig <dyb@iuvax.cs.indiana.edu>

       I proposed this a while back, but my proposal met with little or no
       response.  I propose that the name of the optional procedure
       "char-ready?" be changed to "read-char-ready?", to allow for
       generalization to "read-ready?", "write-char-ready?", and maybe even
       "write-ready?".

    I don't know about the other three, but I agree with your proposal to
    rename `char-ready?'.  I should have seconded this proposal the last
    time -- we blew it when we originally named that procedure.

I strongly believe that CHAR-READY? should not be part of any Scheme standard.

It is an embarrassing timing error waiting to happen that does not do justice
to the very careful design of most other parts of this language.

It presupposes a particular model of stream use that is not always appropriate
in a shared memory multi-tasking environment. For example, on the Lisp Machine,
if you type Function Clear-Input (asynchronous clear input buffer) between the
time you do the CHAR-READY? is done and the time you try to read a character,
the attempt to read the character will hang.

I strongly think we should flush CHAR-READY? and replace it with the following
primitive:

  (READ-CHAR?)
  (READ-CHAR? port)

  If a character is immediately available from the input PORT,
  that character is returned and the PORT is updated to point
  to the following character (if any). If characters are expected
  to become available but none are immediately available at the
  time of the call, #f is returned. If no more characters
  are available, an end of file object is returned. PORT may be
  omitted, in which case it defaults to the value returned by
  CURRENT-INPUT-PORT.

Some other possible names are READ-CHAR-NOW, READ-CHAR-IMMEDIATELY,
MAYBE-READ-CHAR, and READ-CHAR-IF-ANY. I'm not adamant about the details
of the proposal other than that a LISTEN primitive is just plain
wrong and a TYI-NO-HANG is much more defensible...

Received: from iuvax.cs.indiana.edu (TCP 30003147300) by MC.LCS.MIT.EDU 15 Jun 88 15:18:25 EDT
Received: by iuvax.cs.indiana.edu; id AA01250; Wed, 15 Jun 88 13:59:06 EST
Received: by iuvax.cs.indiana.edu (5.54/1.5) 
Date: Wed, 15 Jun 88 13:59:06 EST
From: Robert Hieb <hieb@iuvax.cs.indiana.edu>
To: rrrs-authors@mc.lcs.mit.edu
Subject: More on Full Specification

    This reader sees sharks in the water...
       
	    Pavel

Me too.

There are those who like the idea of a simple, powerful, and dangerous,
language.  My introduction to Scheme was via the Dan Friedman approach.
Immersed in a sea of closures, continuations, assignments and macros,
I felt very much like shark bait.

I have grown to love the simple and powerful aspects of Scheme, and realize
that danger will always lurk where there be simple, powerful beasts.
However we should do what we can to tame them without declawing them.

Paul Hudak's response made many of the points I meant to imply.

I think we should recognize forthrightly that Scheme is not a
``functional'' language.  Along with first-class procedures, a feature now
shared with several languages, Scheme also has assignments and continuations.
This combination makes Scheme special.  It also makes Scheme dangerous,
in the sense that they can interact in surprising ways.

Because of its power, Scheme needs a complete and understandable semantics.
Because of its simplicity, Scheme can have one.

We have approached it, but fallen shy of the mark in key areas.  I should
like to see us head back in that direction ``before it is too late.''

I am not so much arguing for my specific proposals (although I did mean them 
seriously), as for a move toward full specification, whatever it entails.
I think it can lead us towards simplification.  As Hudak points out, the
unspecified must be specified as such.

It would perhaps be nice if procedures (and forms) done for effect did not
return values, as Pavel suggests.  This however does introduce real
command procedures into Scheme, and we should then enforce their no value 
status.  Is it better to deal with that complication or simply let them
return reasonable values?  At any rate I think it should be clear what is
returned.  One possibility, if one wants to preserve the for-effect-only status
of such procedures, would be for them to all return the same useless value: 
#f or #t or something new like #n (for no-value).

Would we ever really want to allow the evaluation of procedural expressions
to occur simultaneously?  I am not sure there is such a thing as 
``a small piece of nondeterminism,'' as Pavel also suggests.  
Do we want a non-deterministic semantics?  
I think the current ``arbitrary permutation'' in the semantics
is terrible, since it really doesn't reflect the intent, 
which I understand to be that procedure calls may be evaluated in different 
orders within the same program, and perhaps even concurrently.

As for internal definitions, one of the disturbing things about them is
that they look like top-level definitions but don't act like them.
One should remember that one of the big arguments for internal definitions
was convenience, particularly in lowering nesting levels.
Consequently such uses as
    (define x (car y))
cannot really be considered invalid, and something like
    (define y (z))
    (define x (car y))
looks perfectly reasonable, given that all other expressions in a body
are evaluated in order.

Finally a note about implementation issues.  Although, as one greatly involved
with implementing Scheme, I can understand their seduction, I think
we should fight it.  First-class procedures and continuations combined with
lexical scoping, assignments and indefinite extent for variables appeared 
to deliver a knockout blow to implementation efficiency.  The fact that 
good implementation techniques have appeared anyway is good reason not to
be too quick to worry about implementations.  After all, an implementation
can do what it pleases as long as no one can tell the difference.  Thus
if it can prove that order of evaluation doesn't matter, or that variables
can't be referenced before definition, it can make appropriate optimizations.
The next great step in Scheme efficiency will require extensive program
analysis anyway.  I think people are still attracted to Scheme by the
structure and semantics of its powerful features, and that is what we should 
concentrate on.

Received: from mitre-bedford.ARPA (TCP 3200600102) by MC.LCS.MIT.EDU 15 Jun 88 13:37:42 EDT
Posted-From: The MITRE Corp., Bedford, MA
Received: from orbit.sun.uucp by linus.MENET (3.2/4.7)
	id AA09236; Wed, 15 Jun 88 13:33:36 EDT
From: John D. Ramsdell <ramsdell%linus@mitre-bedford.ARPA>
Posted-Date: Wed, 15 Jun 88 13:33:24 EDT
Received: by orbit.sun.uucp (3.2/SMI-3.0DEV3)
	id AA20022; Wed, 15 Jun 88 13:33:24 EDT
Date: Wed, 15 Jun 88 13:33:24 EDT
Message-Id: <8806151733.AA20022@orbit.sun.uucp>
To: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Hal Abelson's message of Wed, 15 Jun 88 12:11:42 edt <8806151611.AA03404@murren>
Subject: days-after-J2000.0

I meant UT1.  Here is a proposal for adding the function
days-after-J2000.0.  Forget seconds-after-J2000.0.

(days-after-J2000.0)					procedure
days-after-J2000.0 returns a real number giving the current universal
time (UT1) minus the universal time at Noon of January 1, 2000.  The
unit of universal time is a mean solar day.  The universal time UT1 is
the siderial time corrected to mean solar time and corrected for polar
movement.  J2000.0 is the Julian epoch of the time origin.

------------------------------------------
I just want to be able to write calendar programs that would be
insensitive to the differences between UT0, UT1, and UT2.

>How do the denotational semantics people handle calendar time, since
>we all know that anything they do is obviously the right decision in
>language design?

I do not know.

John

Received: from murren (TCP 2206400263) by MC.LCS.MIT.EDU 15 Jun 88 12:08:17 EDT
Received: by MURREN.AI.MIT.EDU; Wed, 15 Jun 88 12:11:42 edt
Date: Wed, 15 Jun 88 12:11:42 edt
From: hal@MURREN.AI.MIT.EDU (Hal Abelson)
Message-Id: <8806151611.AA03404@murren>
To: ramsdell%linus@mitre-bedford.ARPA
Cc: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: John D. Ramsdell's message of Wed, 15 Jun 88 10:46:52 EDT <8806151446.AA19221@darwin.sun.uucp>
Subject: seconds-after-J2000.0
Reply-To: hal@ai.ai.mit.edu



   Posted-From: The MITRE Corp., Bedford, MA
   From: John D. Ramsdell <ramsdell%linus@mitre-bedford.ARPA>
   Posted-Date: Wed, 15 Jun 88 10:46:52 EDT
   Date: Wed, 15 Jun 88 10:46:52 EDT

   I propose adding the function seconds-after-J2000.0.

   (seconds-after-J2000.0)					procedure
   seconds-after-J2000.0 returns a real number giving the number of
   seconds after Noon of January 1, 2000.  J2000.0 is the Julian epoch of
   the time origin.


I object to this function on the grounds that it is woefully
underspecified: do you mean UT0 (siderial time corrected to mean solar
time), UT1 (UT0 corrected for polar movement), or UT2 (UT1 corrected
for seasonal variations)?  All are subject to variations from
deceleration and uneveness of the earth's rotation.  Or perhaps you
mean ephemeris time?  Maybe you can fix this with appropriate optional
arguments.

Even so, will be dificult to implement this in a way that admits a
complete, unambiguous specification for Scheme.  Scheme programmers
who use this procedure on high-velocity spacecraft or near black holes
may encounter different timing behavior due to relativistic effects
and therefore have difficulty sharing their programs with people on
Earth.  It would be difficult to prove any theorems about Scheme
programs that use this procedure.

How do the denotational semantics people handle calendar time, since
we all know that anything they do is obviously the right decision in
language design?

 
-- Hal


	

Received: from mitre-bedford.ARPA (TCP 3200600102) by MC.LCS.MIT.EDU 15 Jun 88 10:51:39 EDT
Posted-From: The MITRE Corp., Bedford, MA
Received: from darwin.sun.uucp by linus.MENET (3.2/4.7)
	id AA04071; Wed, 15 Jun 88 10:47:36 EDT
From: John D. Ramsdell <ramsdell%linus@mitre-bedford.ARPA>
Posted-Date: Wed, 15 Jun 88 10:46:52 EDT
Received: by darwin.sun.uucp (3.2/SMI-3.0DEV3)
	id AA19221; Wed, 15 Jun 88 10:46:52 EDT
Date: Wed, 15 Jun 88 10:46:52 EDT
Message-Id: <8806151446.AA19221@darwin.sun.uucp>
To: rrrs-authors@mc.lcs.mit.edu
Subject: seconds-after-J2000.0

I propose adding the function seconds-after-J2000.0.

(seconds-after-J2000.0)					procedure
seconds-after-J2000.0 returns a real number giving the number of
seconds after Noon of January 1, 2000.  J2000.0 is the Julian epoch of
the time origin.

Received: from kleph (TCP 2206400254) by MC.LCS.MIT.EDU 15 Jun 88 10:08:08 EDT
Received: by kleph.AI.MIT.EDU; Wed, 15 Jun 88 10:10:14 edt
Date: Wed, 15 Jun 88 10:10:14 edt
From: cph@kleph.AI.MIT.EDU (Chris Hanson)
Message-Id: <8806151410.AA04278@kleph>
To: dyb@iuvax.cs.indiana.edu
Cc: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: R. Kent Dybvig's message of Tue, 14 Jun 88 22:21:30 EST
Subject: char-ready? => read-char-ready?
Reply-To: cph@zurich.ai.mit.edu

   Date: Tue, 14 Jun 88 22:21:30 EST
   From: R. Kent Dybvig <dyb@iuvax.cs.indiana.edu>

   I proposed this a while back, but my proposal met with little or no
   response.  I propose that the name of the optional procedure
   "char-ready?" be changed to "read-char-ready?", to allow for
   generalization to "read-ready?", "write-char-ready?", and maybe even
   "write-ready?".

I don't know about the other three, but I agree with your proposal to
rename `char-ready?'.  I should have seconded this proposal the last
time -- we blew it when we originally named that procedure.

Received: from ZERMATT.LCS.MIT.EDU (CHAOS 17316) by MC.LCS.MIT.EDU 15 Jun 88 09:26:54 EDT
Received: from ASPEN.LCS.MIT.EDU by ZERMATT.LCS.MIT.EDU via CHAOS with CHAOS-MAIL id 164038; Wed 15-Jun-88 09:26:23 EDT
Date: Wed, 15 Jun 88 09:28 EDT
From: Robert Halstead <rhh@VX.LCS.MIT.EDU>
Subject: (define x)
To: JAR@AI.AI.MIT.EDU
cc: Pavel.pa@XEROX.COM, rrrs-authors@MC.LCS.MIT.EDU
In-Reply-To: <396821.880613.JAR@AI.AI.MIT.EDU>
Message-ID: <880615092831.6.RHH@ASPEN.LCS.MIT.EDU>

    Date: Mon, 13 Jun 88 17:44:35 EDT
    From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
    Subject:  (define x)
    To: Pavel.pa@XEROX.COM

    We need to decide whether this is to make sense only for top-level
    defines or for internal defines as well.  If for internal defines, the
    desugaring into LETREC has to be given; that would probably mean that
    LETREC would have to be extended (e.g. (letrec ((x) (y)) ...)); and that
    seems like a bad idea to me ...

I don't find anything especially distasteful about it -- it strikes me
as useful for precisely the same purposes as the top-level (define x).
In fact, I would encourage (laziness prevents me from getting up and
checking the RRRS to see if it's already permitted) the form
(let ((x) (y)) ...) also, following the same argument.	-Bert Halstead

Received: from iuvax.cs.indiana.edu (TCP 30003147300) by MC.LCS.MIT.EDU 14 Jun 88 23:25:36 EDT
Received: by iuvax.cs.indiana.edu; id AA29293; Tue, 14 Jun 88 22:21:30 EST
Received: by iuvax.cs.indiana.edu (5.54/1.5) 
Date: Tue, 14 Jun 88 22:21:30 EST
From: R. Kent Dybvig <dyb@iuvax.cs.indiana.edu>
To: rrrs-authors@mc.lcs.mit.edu
Subject: char-ready? => read-char-ready?

I proposed this a while back, but my proposal met with little or no
response.  I propose that the name of the optional procedure
"char-ready?" be changed to "read-char-ready?", to allow for
generalization to "read-ready?", "write-char-ready?", and maybe even
"write-ready?".  Does anyone object to changing the name of
"char-ready?"?  Note that I am not advocating that we add "read-ready?"
or the others, just that we change the name of "char-ready?" to
"read-char-ready?".

An additional justification for this proposal is that "char-ready?"
sounds too much like a character predicate (e.g., "char-upper-case?",
"char-numeric?") and does not sound like it has anything to do with
I/O.

Kent

Received: from mitre-bedford.ARPA (TCP 3200600102) by MC.LCS.MIT.EDU 14 Jun 88 14:45:42 EDT
Posted-From: The MITRE Corp., Bedford, MA
Received: from darwin.sun.uucp by linus.MENET (3.2/4.7)
	id AA19448; Tue, 14 Jun 88 08:19:06 EDT
From: John D. Ramsdell <ramsdell%linus@mitre-bedford.ARPA>
Posted-Date: Tue, 14 Jun 88 08:18:27 EDT
Received: by darwin.sun.uucp (3.2/SMI-3.0DEV3)
	id AA17963; Tue, 14 Jun 88 08:18:27 EDT
Date: Tue, 14 Jun 88 08:18:27 EDT
Message-Id: <8806141218.AA17963@darwin.sun.uucp>
To: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Jonathan A Rees's message of Mon, 13 Jun 88 10:44:01 EDT <396501.880613.JAR@AI.AI.MIT.EDU>
Subject: Scheme modules using HERALD, MODULE, and IMPORT.

I think the major difference between the Rees/ML proposal and mine
(call it the Ramsdell/Modula-II proposal) is Rees/ML has quasi first
class environments, and my proposal has no environment like values.
My proposal was built on a modest extension of the lexical structure
of Scheme.  The Rees/ML approach is more ambitious.  As I see it, the
big question is "should a module design for the language Scheme
include adding environment values or should environment values only be
part of the debugging environment?"  Jonathan has obviously given his
vote. 

JAR:
>One thing that always bugs me is that it is often assumed that
>interfaces and modules are in 1-1 correspondence.  Doesn't Modula-II have
>that bug?  I prefer the ML- or Mesa-like approach where the interface is
>specified independently and can be used by several different modules,
>and perhaps clients as well.  That's what I was getting at with
>DEFINE-SIGNATURE.

Yeah, that is a good point.

John

Received: from ATHENA.CS.YALE.EDU (TCP 20011000033) by MC.LCS.MIT.EDU 14 Jun 88 13:50:14 EDT
Received: by ATHENA.CS.YALE.EDU; Tue, 14 Jun 88 12:23:01 EDT
From: Paul Hudak <hudak-paul@YALE.ARPA>
Full-Name: Paul Hudak
Message-Id: <8806141623.AA03523@ATHENA.CS.YALE.EDU>
Received: by yale-ring (node-add2/ADD2) 
          via WIMP-MAIL (Version 1.3/1.5) ; Tue Jun 14 12:29:33
Date: Tue, 14 Jun 88 12:29:27 EDT
Subject: Re: Full Specification
To: cph@zurich.ai.mit.edu
Cc: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: cph@kleph.AI.MIT.EDU (Chris Hanson), Tue, 14 Jun 88 04:07:17 edt

I understand the desire for underspecification in certain places (for 
example order-of-evaluation of arguments) but don't forget probably the 
most critical advantage of full specification:  portability.  To take 
the order-of-evaluation example, one can only say: "this program is portable 
as long as none of the arguments induce any side-effects."  Every place you 
decide to admit underspecification, you have to make this kind of qualifying 
remark.  People who want a STANDARD aren't going to like it.

Another comment, concerning Chris Hanson's comment:

    3. Full specification is a never ending game.  When have we finished
    specifying everything?  People will be forever noticing new details
    that we have missed and forcing us to specify some behavior for them.
    In fact, most of those details are uninteresting.
    
    In contrast, underspecification is automatic.  By overlooking some
    behavior, we have "underspecified" it.  This is appropriate, since the
    kind of thing that is likely to be overlooked is precisely the thing
    least interesting to specify.

The flip side of this argument is that many of those overlooked behaviors 
are VERY interesting; in fact critical.  The whole purpose in giving a formal 
semantics to a language is to uncover those subtle unspecified behaviors that 
raise havoc with users.  If you choose to underspecify something, then at least 
specify that you have chosen to underspecify!  In other words, make it a formal 
part of the language semantics.  

And by the way, if one *really* believes in underspecification, then I should 
point out that in the Scheme report the order of evaluation of arguments is 
not underspecified enough!  In particular, the order is informally said to
be "indeterminate" and in the formal semantics it is said to be dictated
by a fixed function called PERMUTE.  This is overspecified in two ways:

1) PERMUTE being fixed implies that for a given program a compiler must
   use the *same* (although arbitrary) evaluation order for every call.
2) Even without that constraint, the implementation is forced to perform
   the evaluations *sequentially*, thus precluding parallel evaluation
   of the arguments, unless the compiler can prove non-interference or
   guarantee correctness with respect to PERMUTE.

Both of these overspecifications constrain the implementor.  But I should
point out that fixing them in the formal semantics requires a shift from
a deterministic semantics to a non-deterministic one, most likely requiring
powerdomains, and not something to be taken lightly.

    -Paul
-------


Received: from kleph (TCP 2206400254) by MC.LCS.MIT.EDU 14 Jun 88 04:06:12 EDT
Received: by kleph.AI.MIT.EDU; Tue, 14 Jun 88 04:07:17 edt
Date: Tue, 14 Jun 88 04:07:17 edt
From: cph@kleph.AI.MIT.EDU (Chris Hanson)
Message-Id: <8806140807.AA03267@kleph>
To: hieb@iuvax.cs.indiana.edu
Cc: Pavel.pa@Xerox.COM, rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Pavel.pa@Xerox.COM's message of Mon, 13 Jun 88 19:29:24 PDT <880613-192945-10499@Xerox>
Subject: Full Specification
Reply-To: cph@zurich.ai.mit.edu

   Date: Mon, 13 Jun 88 19:29:24 PDT
   From: Pavel.pa@Xerox.COM

   You say ``one really expects the definitions in a body to be
   accomplished in order''.  I don't.

   Requiring the implementation of internal defines to signal an error if
   <undefined> is referenced is quite possibly too expensive for many
   applications.  In addition, I dislike the notion of encouraging people
   to write series of internal defines that are sensitive to evaluation
   order.  It goes against what I consider to be the clean and readable
   purpose of such defines: binding local procedures.

Hear, hear!  Internal defines, just like `letrec', should be used ONLY
when the value is something that can possibly need mutual recursion.
In other words: lambda expressions and `delay' expressions.  In both
those cases there is no order of evaluation dependendence.
Defining an order implies that internal definitions can and should be
used for other values as well -- a terrible idea.

   A significant source of first-level optimization is the lack of a
   defined argument-evaluation order in the language.

Again, I agree.  MIT's compiler takes advantage of this to produce
significantly better code than it could otherwise -- and we intend to
build more optimizations in the future that depend on this
underspecification.

I think it is a good idea to understand why we need
underspecification, and where.  But full specification has some
serious problems:

1. It ties the hands of the implementer.  My comments on order of
argument evaluation are an example.  Another: MIT Scheme foolishly
allowed the value of `set!' to become defined -- without ever saying
it in print anywhere -- thus requiring the compiler to generate code
for that value whenever it couldn't prove that the value was not used.
I'm seriously considering changing that behavior despite the fact that
some people depend on it.

2. Underspecification is useful.  My comments on internal definitions
are an example.  Here we are trying to encourage a style, without
requiring all implementations to enforce it.  Full specification in
this case would DISCOURAGE that style, while encouraging a different
one.

3. Full specification is a never ending game.  When have we finished
specifying everything?  People will be forever noticing new details
that we have missed and forcing us to specify some behavior for them.
In fact, most of those details are uninteresting.

In contrast, underspecification is automatic.  By overlooking some
behavior, we have "underspecified" it.  This is appropriate, since the
kind of thing that is likely to be overlooked is precisely the thing
least interesting to specify.

Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU 13 Jun 88 22:39:28 EDT
Received: from Cabernet.ms by ArpaGateway.ms ; 13 JUN 88 19:29:45 PDT
Date: Mon, 13 Jun 88 19:29:24 PDT
From: Pavel.pa@Xerox.COM
Subject: Re: Full Specification
In-reply-to: "hieb@iuvax.cs.indiana.edu's message of Mon, 13 Jun 88 16:16:54
 EST"
To: Robert Hieb <hieb@iuvax.cs.indiana.edu>
Cc: rrrs-authors@mc.lcs.mit.edu
Message-ID: <880613-192945-10499@Xerox>

``Full compliance with a semantic model'' does not necessarily imply that, for
example, the SET! form must have a defined return value.  It simply means that
the semantics must show a small piece of nondeterminism, in the same way that it
now uses the ``implementation-dependent'' function ``permute'' in order to dodge
the question of argument evaluation order.

You say ``one really expects the definitions in a body to be accomplished in
order''.  I don't.  Maybe I'm strange, but I've never considered using internal
define's for anything but local procedures, whose order of evaluation is
irrelevant.

I am opposed strongly to all three of your proposals.

I have never believed that the return value of things like ``write'' and
``set-car!'' had a reasonable justification in languages like Common Lisp and it
makes more sense for these procedures (and the set! expression) to return no
value at all.  I find code that uses the return value of such constructs
considerably harder to read.  Code that does not do this is, yes, frequently
more verbose, but always more readable.

A significant source of first-level optimization is the lack of a defined
argument-evaluation order in the language.  It is almost always more convenient,
for example, to evaluate the function form last, after all of the arguments have
been evaluated.  Also, in my experience, code that depends upon left-to-right
order (in those languages that guarantee it) is again always harder to read.

Requiring the implementation of internal defines to signal an error if
<undefined> is referenced is quite possibly too expensive for many applications.
In addition, I dislike the notion of encouraging people to write series of
internal defines that are sensitive to evaluation order.  It goes against what I
consider to be the clean and readable purpose of such defines: binding local
procedures.

       ``And of course there are more, but that is enough to test the water.''

This reader sees sharks in the water...

	Pavel

Received: from ti.com (TCP 1201600056) by MC.LCS.MIT.EDU 13 Jun 88 19:46:05 EDT
Received: by ti.com id AA04686; Mon, 13 Jun 88 18:42:55 CDT
Received: from mips by tilde id AA03639; Mon, 13 Jun 88 18:43:10 CDT
Received: by mips id AA16890; Mon, 13 Jun 88 18:43:04 CDT
Date: Mon, 13 Jun 88 18:43:04 CDT
From: David Bartley <bartley@mips.csc.ti.com>
Message-Id: <8806132343.AA16890@mips>
To: hieb@iuvax.cs.indiana.edu
Cc: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Robert Hieb's message of Mon, 13 Jun 88 16:16:54 EST <8806132217.AA02371@tilde>
Subject: Full Specification

>Three sources of underspecification:
>
>   1. Failure to achieve consensus on what a full specification should be.
>   2. A desire to not unduly impede implementations.
>   3. Attempting to simplify the specification by ignoring accidental or
>      unessential details.
>
>The first is unfortunate, and we should do better.
>
>The second is reasonable but not compelling.  Language designers
>should don their user hats.  From the standpoint of the user implementation
>considerations are significant only if they greatly affect speed, memory
>usage or reliability.  Thus implementation considerations should have veto
>power and perhaps be allowed to vote in case of a tie, but otherwise
>stay in the background (like a good implementation).

Yeah, but...  For a relatively new language like Scheme, we can't
always predict which language "features" will greatly affect
performance.  In my experience, the more I look at alternative
computer architectures (e.g., parallel processing) and alternative
compilation/optimization techniques, the more important under-
specification can become.  Still, our use of under-specification in
the document is often ad hoc and subjective, and I agree that we could
use some discussion on the topic.

Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 13 Jun 88 17:45:17 EDT
Date: Mon, 13 Jun 88 17:44:35 EDT
From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Subject:  (define x)
To: Pavel.pa@XEROX.COM
cc: rrrs-authors@MC.LCS.MIT.EDU
In-reply-to: Msg of Mon 13 Jun 88 12:24:39 PDT from Pavel.pa@Xerox.COM
Message-ID: <396821.880613.JAR@AI.AI.MIT.EDU>

    Date: Mon, 13 Jun 88 12:24:39 PDT
    From: Pavel.pa@Xerox.COM
    To:   Jonathan A Rees <JAR@AI.AI.MIT.EDU>
    cc:   rrrs-authors@MC.LCS.MIT.EDU
    Re:   (define x)

    Presumably the only use for this is to avoid having to pick a value
    in those cases where it will not be used?

Presumably.

Also, I forgot to mention:  in order to allow implementations to signal
errors when the variable is referenced after such a DEFINE but before a
SET! of the variable, it needs to be specified that it is an error to so
refer to the variable.

We need to decide whether this is to make sense only for top-level
defines or for internal defines as well.  If for internal defines, the
desugaring into LETREC has to be given; that would probably mean that
LETREC would have to be extended (e.g. (letrec ((x) (y)) ...)); and that
seems like a bad idea to me, although I don't feel strongly; so I'd
suggest making it a special case for top level.  Top level defines are
already sufficiently different from internal ones (e.g. they are
evaluated sequentially, and may be interspersed with expressions) that
this doesn't seem too terrible.


Received: from iuvax.cs.indiana.edu (TCP 30003147300) by MC.LCS.MIT.EDU 13 Jun 88 17:18:05 EDT
Received: by iuvax.cs.indiana.edu; id AA19062; Mon, 13 Jun 88 16:16:54 EST
Received: by iuvax.cs.indiana.edu (5.54/1.5) 
Date: Mon, 13 Jun 88 16:16:54 EST
From: Robert Hieb <hieb@iuvax.cs.indiana.edu>
To: rrrs-authors@mc.lcs.mit.edu
Subject: Full Specification

Date: Tue 24 May 88 13:13:21-EDT
From: Morris Katz <MKATZ at A.ISI.EDU>

    Overspecification should be avoided as it artificially
    prohibits reasonable implementations.

Date: Thu May 26 07:49:42 1988
From: Jonathan A Rees <JAR@mc.lcs.mit.edu>

    Underspecification effectively amounts to giving an axiomatic semantics
    (proof system) for the language, as opposed to a denotational one (a
    model).  The problem with underspecification is that one can have a
    program that works fine in one implementation and fails in another, so
    the only way to produce portable code is by reasoning about it, and
    testing doesn't help you a bit.  While I agree that some
    underspecifications are important, I believe you can go too far in
    underspecifying things that really don't make much difference, requiring
    reasoning in situations where testing ought to be sufficient.

    Underspecifications makes the language harder to learn and use, since an
    implementation cannot teach them very well.  One must be aware of all
    underspecifications all the time.  I think they should be minimized, not
    maximized.


This debate should be carried further.  Currently I don't see a coherent 
policy on full specification (one might say it is underspecified).

Three sources of underspecification:

   1. Failure to achieve consensus on what a full specification should be.
   2. A desire to not unduly impede implementations.
   3. Attempting to simplify the specification by ignoring accidental or
      unessential details.

The first is unfortunate, and we should do better.

The second is reasonable but not compelling.  Language designers
should don their user hats.  From the standpoint of the user implementation
considerations are significant only if they greatly affect speed, memory
usage or reliability.  Thus implementation considerations should have veto
power and perhaps be allowed to vote in case of a tie, but otherwise
stay in the background (like a good implementation).

The third is the touchy one.  It is a counter argument to Rees' claim
that underspecification makes a language easier to learn.  Leaving out
incidental details may actually make it easier to understand and use a feature.
For example, assignments are used mainly for effect---the value returned
is usually not important.  However, once specified, it will be used.
Thus users will in the end be forced to learn and remember all specified 
details (if you don't use them someone whose code you must read will).

The other side---reasons for full specification:

   1. Consistency across implementations, allowing one to test and port
      programs with reasonable assurance.
   2. Full compliance with a semantic model.
   2. Use of the specified details.

Number one is a large win.  We are still at the point (and undoubtably always
will be, at least for the life of Scheme as a living programming language)
where large programs can only [reasonably] be shown to be correct by testing.
The argument that correct programs do not rely on unspecified features is
not reasonable for large programs.  Programmers make mistakes, and will
write programs that happen to rely on unspecified features of a given
implementation.  Some of these mistakes are so easy to make one could call
them traps.  For instance, one really expects the definitions in a body to be
accomplished in order.

Number two: the history of Scheme has been intimately tied with denotational
semantics---the value of a full formal semantics for Scheme should not be
underestimated.

Number three is the least compelling.  Typically one has no use for the
unspecified aspects and can provide for them when necessary, arguably in
a clearer fashion.
                                 
Conclusion: full specification is best.  In most cases there are reasonable,
consistent specifications that are as easy to remember (and specify) as
``not specified.''  If it is an error to rely on something that will 
in fact end up being specified in a given implementation we should make it a 
signaled error.

Following are some specification proposals:

Procedures with side effects return the value of the ``source'' expression.
For instance, all of the following would return the value of e:
   (set! x e)
   (set-car! x e)
   (write e p)
There are of course other possibilities; the above has the advantage
of naturalness and symmetry across a broad class of expressions.

The expressions in a procedure call are evaluated from left to right.
This is perhaps the trickiest underspecification in Scheme.  It can be
extremely difficult to verify that order of evaluation has no effect in a large
program.  A reasonable order is left to right, since that's the way bodies
are evaluated.

Definitions are also evaluated left to right.
    (let () (define x e) (define y f))
means
   (let ((x <undefined>) (y <undefined>)) (set! x e) (set! y f))
where referencing <undefined> signals an error.

And of course there are more, but that is enough to test the water.

Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU 13 Jun 88 15:32:45 EDT
Received: from Cabernet.ms by ArpaGateway.ms ; 13 JUN 88 12:24:58 PDT
Date: Mon, 13 Jun 88 12:24:39 PDT
From: Pavel.pa@Xerox.COM
Subject: Re: (define x)
In-reply-to: <396508.880613.JAR@AI.AI.MIT.EDU>
To: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Cc: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <880613-122458-9409@Xerox>

Presumably the only use for this is to avoid having to pick a value in those
cases where it will not be used?

	Pavel

Received: from ti.com (TCP 1201600056) by MC.LCS.MIT.EDU 13 Jun 88 12:30:53 EDT
Received: by ti.com id AA02103; Mon, 13 Jun 88 11:27:52 CDT
Received: from mips by tilde id AA02096; Mon, 13 Jun 88 11:20:08 CDT
Received: by mips id AA06701; Mon, 13 Jun 88 11:19:55 CDT
Date: Mon, 13 Jun 88 11:19:55 CDT
From: David Bartley <bartley@mips.csc.ti.com>
Message-Id: <8806131619.AA06701@mips>
To: JAR@mc.lcs.mit.edu
Cc: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Jonathan A Rees's message of Mon, 13 Jun 88 10:51:01 EDT <396508.880613.JAR@AI.AI.MIT.EDU>
Subject: (define x)

We are using "(define x)" here at TI as you specified it.  It seems
to be preferable to requiring something like "(define x 'garbage)"
because the latter is unnecessarily overspecific and might complicate
life for, say, a type inferencer.

Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 13 Jun 88 10:51:22 EDT
Date: Mon, 13 Jun 88 10:51:01 EDT
From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Subject:  (define x)
To: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <396508.880613.JAR@AI.AI.MIT.EDU>


Does anyone have an objection to the syntax "(define x)" meaning that
the variable is to be bound, but its location is to be either left
unassigned or assigned an unspecified value?  This is already
implemented in MIT Scheme, I think.

Consider it proposed.


Received: from mitre-bedford.ARPA (TCP 3200600102) by MC.LCS.MIT.EDU 11 Jun 88 22:51:17 EDT
Posted-From: The MITRE Corp., Bedford, MA
Received: from darwin.sun.uucp by linus.MENET (3.2/4.7)
	id AA22801; Sat, 11 Jun 88 22:46:38 EDT
From: John D. Ramsdell <ramsdell%linus@mitre-bedford.ARPA>
Posted-Date: Sat, 11 Jun 88 22:46:07 EDT
Received: by darwin.sun.uucp (3.2/SMI-3.0DEV3)
	id AA15269; Sat, 11 Jun 88 22:46:07 EDT
Date: Sat, 11 Jun 88 22:46:07 EDT
Message-Id: <8806120246.AA15269@darwin.sun.uucp>
To: rrrs-authors@MC.LCS.MIT.EDU
In-Reply-To: Jonathan A Rees's message of Fri, 27 May 88 01:13:52 EDT <386391.880527.JAR@AI.AI.MIT.EDU>
Subject: Scheme modules using HERALD, MODULE, and IMPORT.

Here is a crack at the kind of module system I envision.  It was
motivated by worrying about the multiple definition problem.  Consider
the problem of writing a random number generator.  You would like to
hide the seed, but provide a means to set the seed as well as compute
the next pseudo-random number.  One would like to write:

	(DEFINE-MANY (set-seed! random)
	   (DEFINE seed 42)
	   (DEFINE (set-seed! value) (SET! seed value))
	   (DEFINE (random) ....))

Since you would like to be able to use DEFINE-MANY where ever local
DEFINE's can be used, it is not clear how to expand DEFINE-MANY, but
at top-level, it might expand into:

	(DEFINE set-seed! '())
	(DEFINE random '())
	(LET ((seed 42))
	   (SET! set-seed! (LAMBDA (value) (SET! seed value)))
	   (SET! random (LAMBDA () ....)))

DEFINE-MANY makes its export list explicit, and augments the current
environment with the exported values.  Its body is defined in the
current environment augmented by all the definitions within the body.

All good module systems separate a module's interface description from
its implementation.  Hence we abandon DEFINE-MANY for HERALD, MODULE,
and IMPORT.

The HERALD form defines a module's interface, and may appear where
ever a DEFINE appears.

	(HERALD module-id id*)

The environment in which the module is defined is given by the
position of the HERALD form.  The form also lists the identifiers
exported by the module.

The implementation of a module is declared by using MODULE, and its
body simply follows the MODULE form. 

	(MODULE module-id) definition*

Another property of any good module system is the ability to separate
the definition environment from the elaboration environment.  The
form

	(IMPORT module-id)

simply imports the module's exports into the current lexical
environment.  It cannot change the definition of a module.

The structure of a Scheme program becomes:
--------------------------------------
program		::= definition* expression module*

definition	::= (DEFINE ....)		; Usual definition.
		 |  (IMPORT module-id)		; module import.
		 |  (HERALD module-id id*)	; module interface.

expression	::= id
		 |  constant
		 |  (LAMBDA (id*)
		       definition*
		       expression+)
		 |  (IF expression expression expression)
		 |  (SET! id expression)
		 |  (expression+)		; call

module		::= (MODULE module-id) definition*
--------------------------------------

While each module has exactly one HERALD and MODULE
form, there may be any number of IMPORT forms which reference that
module.  The three module forms return unspecified values just like
DEFINE. 

For a program contained in one file, the module-id can simply be a
symbol.  For multi-file programs, a module-id could be a list of
symbols interpreted in a machine dependent way.  As an example, the
module-id "(tsystem sources sys gc two-finger)" on a Unix machine
might reference the module named "two-finger" in the file
"$TSYSTEM/source/sys/gc.scm".

The MODULE form could be used to specify read tables and syntax tables
as is done in T.  The HERALD form would give a compiler its early
binding environment.

I have not thought out the details of an implementation of this module
system.  The implementation would have to handle circular module
references, but I see no obvious difficulties.
John




Received: from chamarti (TCP 2206400253) by MC.LCS.MIT.EDU  8 Jun 88 13:09:25 EDT
Received: by CHAMARTIN.AI.MIT.EDU; Wed, 8 Jun 88 12:32:20 edt
Date: Wed, 8 Jun 88 12:32:20 edt
From: jinx@CHAMARTIN.AI.MIT.EDU (Guillermo J. Rozas)
Message-Id: <8806081632.AA21677@chamarti>
To: JAR@AI.AI.MIT.EDU
Cc: hieb@IUVAX.CS.INDIANA.EDU, rrrs-authors@MC.LCS.MIT.EDU
In-Reply-To: Jonathan A Rees's message of Mon,  6 Jun 88 22:03:25 EDT <392964.880606.JAR@AI.AI.MIT.EDU>
Subject: report sources
Reply-To: jinx@zurich.ai.mit.edu

    Anonymous login works with PREP's FTP server; I don't know about zurich,
    but I don't think so.  If you can't use tar format, let me know and put
    the un-tarred files on PREP as well.

It should work on zurich too, except that the password may have to be
typed as "" on some systems.

The pathname there is pub/r4rs.tar



Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU  7 Jun 88 22:18:39 EDT
Received: from Cabernet.ms by ArpaGateway.ms ; 07 JUN 88 19:11:39 PDT
Date: Tue, 7 Jun 88 19:11:34 PDT
From: Pavel.pa@Xerox.COM
Subject: Re: opaque type proposal
In-reply-to: <19880608015223.6.ALAN@PIGPEN.AI.MIT.EDU>
To: Alan Bawden <Alan@AI.AI.MIT.EDU>
Cc: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <880607-191139-1601@Xerox>

I think that I'm not very worried about your ``more mundane'' kind of problem,
viz. upward-compatibility when or if we get around to adding
multiple-inheritance.  Isn't this entirely orthogonal to inheritance?  For
example, what about when we get around to specifying a mechanism for
type-specific print operations, or any of a hundred other little options that we
might later decide to add?  I don't see how the addition of these to
MAKE-RECORD-TYPE's argument list is likely to be any more painless/beautiful.

I'm also not convinced any longer that the issue of ``how not to make mistakes
now that hurt us when we later add multiple-inheritance'' is terribly important.
The notion of opaque types and sub-typing are reasonably well understood
entirely independently of any casual resemblance to an object-oriented
programming facility.  If we're really so concerned that the facility we're
talking about now be extendable into an object-oriented programming facility,
then I submit that we should never decide on such an extension that cannot
handle this very simple and useful semantics.

In short, I'm having a hard time seeing the importance of this
upward-compatibility argument.  All I want is this simple, straightforward
semantics for a very useful facility; it's just not clear to me that the
decision has the great weightiness of future impact that you perceive.  Can you
explain your concern more fully?

	Pavel

Received: from REAGAN.AI.MIT.EDU (CHAOS 13065) by MC.LCS.MIT.EDU  7 Jun 88 22:01:58 EDT
Received: from PIGPEN.AI.MIT.EDU by REAGAN.AI.MIT.EDU via CHAOS with CHAOS-MAIL id 117837; Tue 7-Jun-88 21:52:43 EDT
Date: Tue, 7 Jun 88 21:52 EDT
From: Alan Bawden <Alan@AI.AI.MIT.EDU>
Subject: Re: opaque type proposal
To: Pavel.pa@Xerox.COM
cc: JAR@AI.AI.MIT.EDU, rrrs-authors@MC.LCS.MIT.EDU
In-Reply-To: <880606-113918-5026@Xerox>
Message-ID: <19880608015223.6.ALAN@PIGPEN.AI.MIT.EDU>

    Date: Mon, 6 Jun 88 11:39:06 PDT
    From: Pavel.pa@Xerox.COM
    ...
    Alan is concerned that allowing single inheritance now might be a hinderance
    later if we decide to extend to multiple-inheritance.  I don't claim to be a big
    expert, but it seems to me that all of the multiple-inheritance facilities that
    I've seen have precisely the same simple single-inheritance semantics as a
    special case.  Alan (or anyone else), do you know of any exceptions to this?  If
    not, then I would think that we were fairly safe in going this far (and no
    more).

Well first off, they might all be wrong, and when the clearly right thing
emerges it might not have the single inheritance semantics that we expect.

(Actually, isn't there already division between those who thing that
children should automatically inherit all of their parents slots, and
those who think that you should have to explicitly import those slots that
the child wants to be able to directly access?)

But putting that kind of issue aside, I had a much more mundane kind of
problem in mind.  For example, if we decide now that single inheritance is
accomplished by calling 

  (MAKE-RECORD-TYPE <name> <slot-names> <parent-type-descriptor>)

then we have to decide later how to specify multiple superiors in an
upward-compatible way.  Do we let the third argument be -either- a single
record-type-descriptor or a list of record-type-descriptors?  That's only a
little ugly.  But perhaps it turns out that instead of an ordered sequence
of record-type-descriptors, we want to provide a procedure that you apply
to an operation, and it returns a record-type-descriptor.  Then do we
specify that the third argument is either a procedure or a record-type-
descriptor (where the latter is taken to be an abbreviation for the one
argument procedure that always returns that record-type-descriptor)?
Now the ugliness starts to mount.

Now I'm sure we can guard against this -particular- screw (or convince
ourselves that it isn't a problem).  But my point is that I feel that we
are unlikely to be able to start in the direction of inheritance without
inviting -some- problem like this.

Received: from Think.COM (TCP 1201000006) by MC.LCS.MIT.EDU  7 Jun 88 17:10:45 EDT
Return-Path: <gls@Think.COM>
Received: from kali.think.com by Think.COM; Tue, 7 Jun 88 17:05:53 EDT
Received: by kali.think.com; Tue, 7 Jun 88 17:05:48 EDT
Date: Tue, 7 Jun 88 17:05:48 EDT
From: gls@Think.COM
Message-Id: <8806072105.AA00556@kali.think.com>
To: jrl@vx.lcs.mit.edu
Cc: pavel.pa@xerox.com, rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Juan Loaiza's message of Sat, 4 Jun 88 00:20:23 edt <8806040636.AA18047@Think.COM>
Subject: Re: opaque type proposal

   Date: Sat, 4 Jun 88 00:20:23 edt
   From: Juan Loaiza <jrl@vx.lcs.mit.edu>



	 You still need the length check in order to make sure that the slot containing
	 the ``tag'' object actually exists before trying to fetch its value.

		   Pavel

   Think again about the trick I mentioned.  It is a dirty, underhanded,
   shameful, slimy trick; but I think it works.  If a token for a type T
   is only ever present in the N'th slot of an object of type T, then
   looking at the N'th slot of any other object will never get you that
   token.  It does not matter how many slots the other object has.  If it
   has less than N slots you, will get a random slot out of another
   object, but never the N'th slot (assuming no objects have zero
   length).

   For our young listeners out there, please don't try this trick at home.

Some care is needed near the end of memory, to make sure that the start of
the last object is as far from the end of the legitimate address space as
the greatest distance of any tag from the origin of its object.  Ugh,
bletch.  Also, having any kind of "raw array" representation could screw
things up.  Otherwise, it's a great, wonderful, slimy crock.
Congratulations.
--Guy


Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU  6 Jun 88 23:49:04 EDT
Received: from Cabernet.ms by ArpaGateway.ms ; 06 JUN 88 20:44:53 PDT
Date: Mon, 6 Jun 88 20:44:47 PDT
From: Pavel.pa@Xerox.COM
Subject: R(3.5)RS Question
To: RRRS-Authors@MC.LCS.MIT.Edu
Message-ID: <880606-204453-6217@Xerox>

I've just been looking over the differences between R3 and R3.5 and noticed
that, among a bunch of other number changes, the syntax of the written
representation of rectangular complex numbers has been changed to have the ``i''
before the coefficient rather than after it.  I can't see any reason based upon
parsing to do this and it's certainly against common mathematical practice, so
why is it being done?

The only thing I could find in the archives on this point is a desire for
syntaxes like ``3+i'' and ``-i'' to work.  It's not clear to me that satisfying
this implies a need to move the ``i'' around.  Does it?

	Pavel

Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU  6 Jun 88 23:10:01 EDT
Received: from Cabernet.ms by ArpaGateway.ms ; 06 JUN 88 20:05:12 PDT
Date: Mon, 6 Jun 88 20:05:02 PDT
From: Pavel.pa@Xerox.COM
Subject: On Modules in Scheme: Principles and Proposals
To: RRRS-Authors@MC.LCS.MIT.Edu
Message-ID: <880606-200512-6178@Xerox>

Well, after carefully reading and considering the comments I've received on the
environment proposal, and after having many many hours of talks with a variety
of people around here on the general subject of modules (be they in Scheme on
some other language), and after having gotten to the point in the development of
our compiler where I need more help than our proposal was offering, I formally
retract our previous proposal.

In its place, I offer the following ideas for discussion.  There are many
details left out (most of them intentionally), but I think that what's here is
the real core of what I believe about what a module facility can and should
provide and how it should be structured.  I have freely stolen ideas and names
from others, both on and off this list, but I have not always left those ideas
and names entirely intact.  Caveat lector.


Principles: There exist written and (at least partially) machine-understandable
statements of the contracts between different pieces of software.  These
``interfaces'' describe all paths of contact between separate pieces of
software; at the level of normal programming (as opposed to facilities provided
by the debugger, for example), no other access is possible.  In addition to
specifying the names of the values available in the interface, other properties
of the values might be given, such as type information, partial or complete
implementations (for integration by, or providing hints to, early evaluators),
formal or informal assertions of the semantics of the values, etc.

Proposals: There exist entities known as ``signatures'' containing at least a
set of names for values and possibly other information as stated above.  These
are not necessarily Scheme data objects.  Signatures have names representable as
Scheme values.  There is a mechanism by which a given signature name can be
associated with a particular signature.  This mechanism may or may not be a part
of the Scheme language.



Principles: It is recognized that interfaces will change over time as providers
and clients learn more about the desired models and paths of communication.  It
is also recognized that early evaluators must, for performance reasons, be
allowed to make certain assumptions about the interfaces (and the values they
represent).  We desire that there be a consistent, non-temporal model of the
semantics of programs, regardless of whether or not they have, at some point,
been partially evaluated.  Thus, it must be possible for an early evaluator to
``build in'' information from the interfaces and to store in the resulting
output some identification of the information used.  This stored identification
should then be used by later evaluators to guarantee that a consistent view of
the possibly-changed interfaces is being employed.

Proposals: Signatures have ``versions'', representable as Scheme values, drawn
from some partial order.  There is a procedure for comparing two versions
according to the partial order.  There is a ``least'' version according to the
partial order; we refer to this as the ``bottom'' version.



Principles: There must be some mechanism by which the code of a client of an
interface can refer to the values the interface represents.  Symmetrically,
there must be a mechanism by which the code of an interface provider can specify
values to be associated with names in that interface.  This should be possible
without either party needing to be aware of the identity or quantity of the
other.  It should be possible for client code to efficiently fetch the values
and for lambda-enclosed references to exist before provider code for the values
has been evaluated.  It should be possible for a provider to supply values for
only a part of an interface.

Proposals: There exist Scheme values called ``structures''.  Creating a
structure requires the name of a signature and values for some, none, or all of
the names in the named signature.  The given values must agree with the
information about them in the signature.  Some or all of that information may be
checked during structure creation.  There is an operation for fetching the
signature name and version from a structure.

There exist Scheme values called ``bindings''.  A binding contains a single
``value'' which may be specified at the time of binding creation; if it is not
specified, the value is said to be ``undefined''.  Structures map names into
bindings.  There are operations for getting the value of a binding, for testing
whether or not the value is undefined and for setting the value; the value may
only be set if it is currently undefined.



Principles: Code that is a client of a particular interface should be clearly
marked as such, for both documentation and semantic purposes.  It should be
possible for a given piece of code to be a client of many interfaces as well as
a (partial or complete) provider of many more.

Proposals: There exist Scheme values called ``modules''.  A module contains,
possibly among other things, an ordered list of signature names and versions
(its ``imports'') and a procedure (its ``body'').  The body takes exactly as
many arguments as there are signature name/version pairs in the imports.  Those
arguments should be structures formed from signatures with matching names and
greater than or equal versions; this assertion is tested by the body and an
error is signalled if the condition is not met.  The body may return any value
or values, as desired.  In particular, the body might return one or more
structures, intending that the invoker will treat them as the provision of
values for some signatures.



Principles: It should be possible for code to refer to the names from some
interfaces without having to qualify them with some identification of the
interface.  For example, the ``built-in'' facilties of the programming language
are a likely choice for such treatment.  However, this set of interfaces should
not be a constant; different programs should be allowed to specify different
sets.  In general, such ``opening'' of an interface can be confusing and
possibly dangerous; accordingly, most imported values should be referred to by
names that indicate the interface from which they are derived.

Proposals: There is a new kind of Scheme expression for the creation of a
module:

	(MODULE (<sig-name> ... (<identifier> <sig-name>) ...)
	   <program>)

where <sig-name> is a signature name.

The first set of names specifies the set of signatures whose names are to be
available without extra qualification.  These are called the ``open (or unnamed)
imports''.  An error is signalled if any two of these signatures share a name;
unqualified references should be unambiguous.

The identifier/signature-name pairs specify the other, ``closed (or named)
imports''.  In the resultant module body, these identifiers will be bound to the
structures passed as arguments to the body; an error will be signalled if any of
these identifiers are among the names in the open imports.

The imports of the module will be the given signature names in the given order.
The version information for the imports will be ``bottom'' unless some
early-evaluator has built in some assumptions about the signatures.

The program has the syntax given in R3RS and this semantics; it is as if all of
the names appearing in DEFINEs were bound in a single LET to unspecified values,
the body of the LET being the sequence of forms resulting from turning all of
the DEFINEs into SET!s.  This expression is evaluated whenever the module body
is invoked; the value(s) of the body invocation are the value(s) of this
expression.  The lexical environment of the body expression is that of the
MODULE expression as a whole, shadowed by bindings of all of the names in the
open imports.



On top of a facility like this, it would be easy to build some useful utilities.
For example, suppose that the LOAD procedure returned a list of the values of
the <command>s in a file.  Then one could imagine a different procedure, call it
FRIENDLY-LOAD, that worked as follows:

-- For each value returned by LOAD, test whether or not it is a module; if not
discard it.

-- For each module, acquire structures for each of its imports and apply the
body of the module to these structures.  FRIENDLY-LOAD maintains a table mapping
signature names and versions to structures.  For each signature named among the
imports for which there is no entry in the table, it creates a fresh structure,
giving no values for bindings, and adds it to the table.

-- If the values returned from the module body invocation are structures, these
are taken to be the ``exports'' of the module.  The signature-names of these
structures are looked up in the table as before, creating fresh structures if
necessary.  Finally, for those names whose bindings in the export structure are
not undefined, the values are copied into the corresponding bindings in the
table structure.

In this way, FRIENDLY-LOAD acts as a system-wide matchmaker, hooking together
the clients and suppliers of interfaces.  Of course, no one would have to use
this facility; one could put an entirely different one together out of the
primitives provided.



I've typed enough here.  Comments?

	Pavel


Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU  6 Jun 88 22:35:11 EDT
Received: from Cabernet.ms by ArpaGateway.ms ; 06 JUN 88 17:49:41 PDT
Date: Mon, 6 Jun 88 17:49:19 PDT
From: Pavel.pa@Xerox.COM
Subject: Re: A Proposal for Environments in Scheme
In-reply-to: <2790267567-12470112@RTS-10>
To: jrl@zermatt.lcs.mit.edu, jinx@chamartin.ai.mit.edu
Cc: rrrs-authors@mc.lcs.mit.edu
Message-ID: <880606-174941-5967@Xerox>

This is my response to comments made by Jinx and Juan.  I will try to simply
respond to their comments in this message; under separate cover I hope to send
out a more general message about module facilities.

Jinx asked whether or not the confusion generated by multiple inheritance (in
particular, the loss of the illusion of lexical scoping) is worthwhile.  Juan
correctly points out that this can be a modularity problem.  I believe that
there are circumstances in which the ability to share some names transparently
between compilation units is useful and desirable.  For example, suppose that
the implementation of a particular interface is quite large, comprising more
than one compilation unit.  It is awkward and, I contend, unreasonable to insist
that code in one compilation unit must explicitly reference through the
interface those items that are provided by a different compilation unit (I am
assuming here that such code can refer to items in the same compilation unit
without going through the interface).  Here is an illustration:

   Interface `Foo', a list of names:
   
     A
     B
     C
   
   Implementation of `Foo' (compilation unit one):
   
     (define A
        ...
        reference to B
        ...
        reference to C
        ...
        reference to X
        ...)
     
     (define B
        ...)
     
     (define X    ; an item private to this compilation unit
        ...)
   
   Implementation of `Foo' (compilation unit two):
   
     (define C
        ...)
     
     (define Y    ; an item private to this compilation unit
        ...)

I hope that no one would disagree that the reference to B in A should look any
different from the reference to X; that is, both are in the same scope as A and
so should be referenced transparently.  I would like to argue that references to
B and C could also be similar, by virtue of their shared presence in the
interface.  Naturally, A cannot refer to Y, since it is neither in the same
compilation unit nor exported to the interface.

Consider the environment in which compilation unit one should be evaluated.  I
would like (in some cases) for its environment to inherit both from the normal
language environment and from the environment represented by the interface.  One
way to get this would be to have the interface environment inherit from the
language environment.  This has the problem that the interface now ``contains''
too many names, more than the abstraction supports.  The only alternative is
multiple inheritance.

----------

Jinx has strong objections against read syntax and so does not like our ideas
for structured identifiers.  As far as I can tell, his difficulty is that
expressions like
		(set! a:b:c 17)
look like they should work, but they don't.  A simple response to this objection
is that perhaps such expressions should be defined to work.  Another response is
to remove the environment-set! primitive from the language and, perhaps, thus
remove the temptation to believe that such an expression might be correct in the
first place.

Jinx also asks ``What is wrong with (: a b1 b2 ... bk)?''  Well, I tried looking
at some code written using this and using modules to the degree that I'm used to
in Cedar (that is, module references are very common, averaging about one for
every three lines of code).  I still find this too verbose.

Juan objects to structured names at all, regardless of their syntax, stating
that their use tends to decrease modularity by wiring in a particular
organization of modules.  I claim that they only wire in a particular
organization of *interfaces* and that this is precisely the purpose of
interfaces.  Interfaces represent the contract between a provider and a client
and as such, it is intended that the client depend upon them.

In an example, Juan objects to the name MATH:SQRT because it specifies where I
want to find the square-root function.  Not only is that exactly my intention,
but it might be that I am using two different procedures named SQRT, one from
the MATH interface and one from some other interface.  The two might have very
different meanings and so qualified names are the only reasonable way to keep
them straight.  In general, I want to use qualified names for *everything except
the features of the language itself*.

Juan also says that it is impossible to abstract over or shadow a qualified
name.  Precisely; that is not their purpose.  Such abstraction and shadowing is
meaningless and thus I am relieved that it is impossible.

----------

Both Jinx and Juan object to what they call the ``absolute'' nature of the file
syntax/semantics I proposed.  I think that they are partially right, in that a
file (or, more generally, expression) should not attempt to specify anything
about the implementations of the interfaces it imports.  However, I do believe
that it should specify the interfaces themselves.  That is, the code should make
clear of what interfaces (and of what versions of them) it is a client and,
further, for what interfaces (in what versions) it is attempting to be a
(perhaps partial) provider.  It is then the responsibility of the user of this
code to supply proper implementations of the imported interfaces and to make the
code available as a provider of the exported ones.

	Pavel


Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU  6 Jun 88 22:03:45 EDT
Date: Mon,  6 Jun 88 22:03:25 EDT
From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Subject:  report sources
To: hieb@IUVAX.CS.INDIANA.EDU
cc: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <392964.880606.JAR@AI.AI.MIT.EDU>

    Date: Mon, 6 Jun 88 15:32:20 EST
    From: Robert Hieb <hieb@iuvax.cs.indiana.edu>
    To:   JAR@mc.lcs.mit.edu
    Re:   rrrs latex formats

    You mentioned you would make the rrrs source available via ftp.
    Have you got around to it?
    We have some proposals we would like to tex up in proper format.
    thanks, bob hieb

The sources are in
	ZURICH.AI.MIT.EDU: /u/jar/r4rs
Tar (Unix "tape archive") format files are in
	ZURICH.AI.MIT.EDU: /u/jar/r4rs.tar
	PREP.AI.MIT.EDU:   /u/jar/r4rs.tar
Anonymous login works with PREP's FTP server; I don't know about zurich,
but I don't think so.  If you can't use tar format, let me know and put
the un-tarred files on PREP as well.

Have fun.


Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU  6 Jun 88 14:47:52 EDT
Received: from Semillon.ms by ArpaGateway.ms ; 06 JUN 88 11:39:18 PDT
Date: Mon, 6 Jun 88 11:39:06 PDT
From: Pavel.pa@Xerox.COM
Subject: Re: opaque type proposal
In-reply-to: <391856.880604.JAR@AI.AI.MIT.EDU>
To: Jonathan A Rees <JAR@AI.AI.MIT.EDU>, Alan Bawden <ALAN@MC.LCS.MIT.EDU>
Cc: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <880606-113918-5026@Xerox>

I suppose that the idea of using the <id> argument upward-compatibly for a
handler procedure isn't too bad, so I guess I favor restricting the argument for
now, but let's restrict it to a string rather than a symbol; symbols have a
distinct purpose, providing unique representatives of certain names, while
strings are better suited to this job.  Actually, I don't care very much about
this.

I agree that ``record type descriptor'' is better than ``record type'' for the
reasons Jonathan puts forward.

Jonathan says, ``I would oppose anything resembling TYPE-OF, since whenever you
have subtyping or polymorphism, there's no such thing as THE type of an object.
I don't see why it would be useful either, since you can always put
type-specific information (like generic operation handlers) somewhere else; e.g.
in the case of records, you can put it in the type descriptor.''

I understand that ``THE type'' is not well-defined, but it is possible to define
a particular structure of type ``names'' such that every object has a
most-precise name in that space.  For example, having only one type-name for all
procedures effectively dodges the problem of polymorphism.

As for the idea of putting the type-specific information in the type descriptor,
this is something that only the implementation can do, not a specific user.

I think that a reasonable choice for type names is predicate procedures.
Suppose that RECORD-PREDICATE was required to always return the same, EQV?
procedure.  Then for each object, there would be a unique most-discriminating
predicate defined by the language.  Some procedure, perhaps called something
like VALUE-TYPE-PREDICATE, would map all objects into their distinguished type
predicates.

I don't see anything ill-defined or modularity-breaking in any of this.
Comments?

Alan is concerned that allowing single inheritance now might be a hinderance
later if we decide to extend to multiple-inheritance.  I don't claim to be a big
expert, but it seems to me that all of the multiple-inheritance facilities that
I've seen have precisely the same simple single-inheritance semantics as a
special case.  Alan (or anyone else), do you know of any exceptions to this?  If
not, then I would think that we were fairly safe in going this far (and no
more).

	Pavel

Date: Sat,  4 Jun 88 15:36:24 EDT
From: Alan Bawden <ALAN@MC.LCS.MIT.EDU>
Subject: opaque type proposal
To: RRRS-AUTHORS@MC.LCS.MIT.EDU
Message-ID: <431132.880604.ALAN@MC.LCS.MIT.EDU>

I'm still worried about letting inheritance slip into the opaque type
proposal.  It's not that I see any problem with Pavel's extension (I
don't), it's that I am worried that by deciding now on a semantics for
single inheritance we reduce our options if it ever becomes clear how
multiple inheritance should work.  I confess I don't have a good example of
how it might get us in trouble, but the transition from single to multiple
inheritance is such a hot topic these days that I don't think any of us can
really be certain where it might take us.

Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU  4 Jun 88 11:44:57 EDT
Date: Sat,  4 Jun 88 11:44:22 EDT
From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Subject:  opaque type proposal
To: Pavel.pa@XEROX.COM
cc: rrrs-authors@MC.LCS.MIT.EDU
In-reply-to: Msg of Fri 3 Jun 88 12:00:10 PDT from Pavel.pa@Xerox.COM
Message-ID: <391856.880604.JAR@AI.AI.MIT.EDU>

OK, I think I buy your arguments for single inheritance.  So how about
this: MAKE-RECORD-TYPE takes as an additional argument a descriptor for
the parent type, or #f if there is to be none.

About the identification argument to MAKE-RECORD-TYPE, the reason I
suggested it be a symbol was just to avoid overspecification: objects of
other types could mean different things.  E.g. at some point that
argument could (upward-compatibly) become some kind of handler procedure
for the record type.

The identification argument should probably be optional, or perhaps not
exist at all.  I don't know.

By the way, the object returned by MAKE-RECORD-TYPE ought to be called a
"record type descriptor", or anything other than "record type".  Calling
any object a "type" would be a bad precedent and would frustrate the
efforts of those using Scheme for teaching and designing statically
typed languages.

I would oppose anything resembling TYPE-OF, since whenever you have
subtyping or polymorphism, there's no such thing as THE type of an
object.  I don't see why it would be useful either, since you can always
put type-specific information (like generic operation handlers)
somewhere else; e.g. in the case of records, you can put it in the type
descriptor.


Received: from acf3.NYU.EDU (TCP 20036500015) by MC.LCS.MIT.EDU  4 Jun 88 04:01:59 EDT
Received:  by acf3.NYU.EDU (5.54/25-eef)
	id AA29747; Sat, 4 Jun 88 03:59:52 EDT
Date: Sat, 4 Jun 88 03:59:52 EDT
From: Eric S. Tiedemann <tiedeman@acf3.NYU.EDU>
Message-Id: <8806040759.AA29747@acf3.NYU.EDU>
To: jrl@VX.LCS.MIT.EDU, pavel.pa@xerox.com
Subject: sleazoid programming
Cc: rrrs-authors@mc.lcs.mit.edu


	Date: Sat, 4 Jun 88 00:20:23 edt
	From: Juan Loaiza <jrl@VX.LCS.MIT.EDU>
	To: pavel.pa@xerox.com
	Subject: Re: Re: opaque type proposal
	Cc: rrrs-authors@mc.lcs.mit.edu
	
	If it has less than N slots you, will get a random slot out of another
	object, but never the N'th slot (assuming no objects have zero length).

Or you may get a slice of object code or of a string that by a one-in-a-billion
chance looks just like the tag you're looking for.  Your approach depends on a
lack of local heterogeneity in the heap (e.g. BIBOP).

					Eric
	
	
	

Received: from VX.LCS.MIT.EDU by MC.LCS.MIT.EDU via Chaosnet; 4 JUN 88  00:21:06 EDT
Received: by VX.LCS.MIT.EDU with sendmail-4.12/4.8 id <AA01142@VX.LCS.MIT.EDU>; Sat, 4 Jun 88 00:20:23 edt
Date: Sat, 4 Jun 88 00:20:23 edt
From: Juan Loaiza <jrl@VX.LCS.MIT.EDU>
To: pavel.pa@xerox.com
Subject: Re: Re: opaque type proposal
Cc: rrrs-authors@mc.lcs.mit.edu



      You still need the length check in order to make sure that the slot containing
      the ``tag'' object actually exists before trying to fetch its value.

        	Pavel

Think again about the trick I mentioned.  It is a dirty, underhanded,
shameful, slimy trick; but I think it works.  If a token for a type T
is only ever present in the N'th slot of an object of type T, then
looking at the N'th slot of any other object will never get you that
token.  It does not matter how many slots the other object has.  If it
has less than N slots you, will get a random slot out of another
object, but never the N'th slot (assuming no objects have zero
length).

For our young listeners out there, please don't try this trick at home.


Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU  3 Jun 88 20:37:47 EDT
Received: from Semillon.ms by ArpaGateway.ms ; 03 JUN 88 17:28:22 PDT
Date: Fri, 3 Jun 88 17:28:02 PDT
From: Pavel.pa@Xerox.COM
Subject: Re: opaque type proposal
In-reply-to: <2790374204-2361923@RTS-10>
To: Juan Loaiza <jrl@ZERMATT.LCS.MIT.EDU>
Cc: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <880603-172822-3100@Xerox>

You still need the length check in order to make sure that the slot containing
the ``tag'' object actually exists before trying to fetch its value.

	Pavel

Received: from XX.LCS.MIT.EDU (CHAOS 2420) by MC.LCS.MIT.EDU  3 Jun 88 20:00:49 EDT
Received: from RTS-10.LCS.MIT.EDU by XX.LCS.MIT.EDU via Chaosnet; 3 Jun 88 20:01-EDT
Message-Id: <2790374204-2361923@RTS-10>
Sender: JRL@RTS-10
Date: Fri, 3 Jun 88  19:56:44 EDT
From: Juan Loaiza <jrl@ZERMATT>
To: Pavel.pa@Xerox.COM
Cc: Jonathan A Rees <JAR@AI.AI.MIT.EDU>, 
    rrrs-authors@MC.LCS.MIT.EDU
Subject: Re: opaque type proposal
In-Reply-To: Msg of Fri, 3 Jun 88 12:00:10 PDT from Pavel.pa@Xerox.COM


I think the opaque type proposal is excellent, and is sorely needed in order for
Scheme to become a language with real abstract data types.

However, I object to the fact that the constructor for a record initializes all
the fields of the record.  This is:

1) An unnecessary bundling of functionality.

2) An annoyance for large structures.

3) Inefficient if bogus values must be specified in the case where the
programmer does not care, especially for large structures.

4) Eliminates possible error checking of uninitialized fields.


An alternative is to have the RECORD-CONSTRUCTOR function take a list of fields
that the constructor it returns should initialize.  For example:

(define yow-record-type (make-record-type 'yow '(a b c)))

;;; This one initializes all three fields, as before.
(define yow-constructor (record-constructor yow-record-type '(a b c)))

;;; This one only initializes A and B. B is the first argument to the function.
;;; A is the second.
(define yow-constructor-no-c (record-constructor yow-record-type '(b a)))





Also, one comment on Pavel's implementation of single inheritence.  The check of
the length of the record can be eliminated by consing a new object to represent
the type of the record, and maintaining the invariant that this newly consed
object only ever appears in a record of that type.  Taking Pavel's example:

   
   	((record-constructor three) 1 2 3 4 5 6)
   
   would be a length 9 record like this:
   
   	Slot	Slot
   	Index	Value
   	-----	-----
   	  0	one-tag
   	  1	1		; value for the A slot
   	  2	2		; value for the B slot
   	  3	two-tag
   	  4	3		; value for the C slot
   	  5	4		; value for the D slot
   	  6	three-tag
   	  7	5		; value for the E slot
   	  8	6		; value for the F slot
   

TWO-TAG would be a newly consed object that is only ever present in the heap as
the third slot of a record of type TWO-TAG (note this implies that TWO-TAG could
not be the "record-type" since that is a first class object).  Now to check
whether a record is of type TWO-TAG, one need only check to see if its third
slot is EQ to TWO-TAG.  Implementing this is somewhat tricky, but definitely
possible.


Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU  3 Jun 88 15:10:22 EDT
Received: from Semillon.ms by ArpaGateway.ms ; 03 JUN 88 12:00:18 PDT
Date: Fri, 3 Jun 88 12:00:10 PDT
From: Pavel.pa@Xerox.COM
Subject: Re: opaque type proposal
In-reply-to: <391255.880603.JAR@AI.AI.MIT.EDU>
To: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Cc: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <880603-120018-2487@Xerox>

I don't consider either of Jonathan's two problems with single-inheritance to be
significant.  Here's why.

The claim is that single inheritance makes type-checking and predication slow.
I dispute this.  Certainly if you insist that, say, the first slot of every
opaque object should contain the special value identifying elements of its type,
then yes, indeed, you will have to check for several values.  However, this is
not necessarily so.  Consider this set of definitions:

	(define one (make-record-type 'one '(a b)))
	
	(define two (make-record-type 'two '(c d) one))
		; two inherits from one
	
	(define three (make-record-type 'three '(e f) two))
		; three inherits from two
	
Then I would expect to see the predicates for these types written as

	(define (one? x)
	   (and (record? x)
	        (>= (record-length x) 3)
	        (eq? (record-ref x 0) one-tag)))
	
	(define (two? x)
	   (and (record? x)
	        (>= (record-length x) 6)
	        (eq? (record-ref x 3) two-tag)))
	
	(define (three? x)
	   (and (record? x)
	        (>= (record-length x) 9)
	        (eq? (record-ref x 6) three-tag)))

Clearly, the result of

	((record-constructor three) 1 2 3 4 5 6)

would be a length 9 record like this:

	Slot	Slot
	Index	Value
	-----	-----
	  0	one-tag
	  1	1		; value for the A slot
	  2	2		; value for the B slot
	  3	two-tag
	  4	3		; value for the C slot
	  5	4		; value for the D slot
	  6	three-tag
	  7	5		; value for the E slot
	  8	6		; value for the F slot

Using this representation, no operation takes other than constant time or,
indeed, any longer than it would without any inheritance at all.

I thus conclude that single inheritance is not inefficient.

Jonathan's other problem was that constructor procedures are no non-modular.
This is only true to the extent that modules export their record-type objects to
the outside world.  The major uses for inheritance that I have in mind do not
involve cross-module use of record-type objects.  I claim that this
non-modularity is exactly as much a problem as for any other exported value; if
I change the number of arguments required for some exported procedure, I have
just the same kind and degree of problem as when I change the number of slots in
an exported record-type object.

I thus conclude that the modularity problem is not specific to opaque types thus
should not be an issue in this discussion.

	Pavel

Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU  3 Jun 88 14:00:55 EDT
Date: Fri,  3 Jun 88 14:00:03 EDT
From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Subject:  opaque type proposal
To: Pavel.pa@XEROX.COM
cc: rrrs-authors@MC.LCS.MIT.EDU
In-reply-to: Msg of Wed 1 Jun 88 19:40:22 PDT from Pavel.pa@Xerox.COM
Message-ID: <391255.880603.JAR@AI.AI.MIT.EDU>

    Date: Wed, 1 Jun 88 19:40:22 PDT
    From: Pavel.pa@Xerox.COM

    Of course, I forgot to mention my most important issue about this
    proposal:  inheritance.  I don't see any worm cans surrounding a
    single-inheritance facility.  It's simple (all other possibilities
    have this as a special case, all with the same semantics), useful
    (especially for the definition of an error system) and easily
    extendable to some hairy multiple-inheritance setup if that's found
    desirable in the future.

I see that nobody takes anything I say on faith.  OK, here are two problems:

- Single inheritance makes type checking and predication of inheritable-from
record types slow.  It is no longer possible to simply compare a slot in
the record against a descriptor representing "the" expected type of the
record, since there is no longer a single possible expected type, but
rather a set of them.

I would favor addressing this by providing a way of optionally
specifying that a record type cannot be subtyped; this could be realized
as a boolean argument to MAKE-RECORD-TYPE.  This vaguely corresponds to
the construct in the Larch specification language where one declares
that a sort (?) is "generated by" a given set of constructors.  E.g. the
natural numbers are generated by zero and successor; there ain't any
others.

- It's no longer clear what constructor procedures should do.  If the
constructor for the subtype takes initial values for all the fields,
including those of the supertype, then you have a serious modularity
violation -- changes to the implementation of the supertype require
changes to the implementation of every subtype.  I don't know how to fix
this, although I imagine there exists some solution involving passing
control between constructors, perhaps using continuations.  It would be
nice if records could be constructed without either copying an instance
of the parent type (as would happen if the new fields were adjoined --
assuming records are stored linearly in memory, and slots are mutable,
both of which seem important) or side-affecting slots (as would happen
if the larger record were created first, and the slots filled in
separately by procedures handling each layer).

We could probably argue of months about these issues, but I wanted to
avoid that for now.


Received: from XX.LCS.MIT.EDU (CHAOS 2420) by MC.LCS.MIT.EDU  2 Jun 88 15:51:28 EDT
Received: from RTS-10.LCS.MIT.EDU by XX.LCS.MIT.EDU via Chaosnet; 2 Jun 88 14:24-EDT
Message-Id: <2790267567-12470112@RTS-10>
Sender: JRL@RTS-10
Date: Thu, 2 Jun 88  14:19:27 EDT
From: Juan Loaiza <jrl@ZERMATT>
To: Pavel.pa@Xerox.COM
Cc: rrrs-authors@mc.lcs.mit.edu
Subject: Re: A Proposal for Environments in Scheme
In-Reply-To: Msg of Fri, 20 May 88 11:49:26 PDT from Pavel.pa@Xerox.COM

This is a reply to Pavel's message of almost two weeks ago proposing the
use of first class environments to define modules.  Sorry to take so long
replying, my mailbox runeth over...


Overall, I think that the idea of trying to standardize the environment
manipulation functions across the implementations that support them is a good
idea, although I am not sure that this belongs in the definition of the language.
However, after having spent a good deal of time lately thinking about modules, I
have come to the conclusion that implementing them using first class
environments directly is probably not the right thing.


First some comments on the proposal:


  MAKE-ENVIRONMENT <id> <parent> ...				[Procedure]

Unrestricted multiple inheritence is a TERRIBLE idea.  It breaks just about
every tenet of modularity that I can think of.  Inheriting from two parent
environments creates a dependence between the two parents where none previously
existed.  Making a safe change to either of the parents now requires detailed
knowledge of the other parent.  The presence of multiple inheritence encourages
the building of "brittle" systems, whereas a good module system should encourage
the building of robust systems.


   In addition to these procedures, We propose a change to the meanings of
   identifiers whose names include colons:


Using qualified names as you advocate tends to decrease the modularity of
systems by wiring in a particular organization of modules.  A qualified name
such as MATH:SQRT specifies both that you want a square root function and that
you want if from the MATH module.  Most of the time you would like to specify
that you want a square root function and you don't care where it comes from. The
place it comes from should be specified separately.  Also, it is impossible to
abstract over, or shadow a qualified name.


   THE SYNTAX AND SEMANTICS OF FILES


I share JINX's reservations about making files "absolute" rather than
"relative".  As a general rule I believe that all "global" or "absolute"
constructs are unmodular (with the possible exception of symbols).


  THE INITIAL ENVIRONMENT STRUCTURE


I think this is on the right track but I would like to see the procedures
related to each data type in their own separate modules.  For example, there
should be a separate module that defines the vector operations.  This is very
subjective though.


  (EXPORT <expression> <export-spec>+)


I don't understand something here.  If I export a variable X into an environment
E, does X act as if it was directly defined in E, or does it act as if it was
inherited by E?  In other words, what happens if I now DEFINE X in E?  Is a new
X created, or is the other one set!.  

Again I beleive that the EXPORT form is basically unmodular.  It specifies both
that a value is produced by this module, and where this value should be put.

As a concrete example of where this type of thing hurts you, suppose that an
environment had become trashed and I wished to re-create it from scratch.  I
would like to throw away the old environment, create a new one, and load into it
the file(s) that define the contents of the environent.  However, in order to
get the values that were exported into the environment, I must also load all the
files that exported into it.  This is likely to cause totally unrelated values
to be reloaded, possibly causing even more trouble.



Overall, I think that first class environments have their place, but the style
of modularization they encourage has some problems.  The kind of module system I
would like to see separately specifies: (1) what values a module needs, (2)
where those values come from, (3) what values a module produces, and (4) where
those values go.  A construct with these properties already exists in Scheme in
the form of procedures.  Consider this procedure:

	(lambda (sqrt draw-line)
	   (define (foo) ...)
	   (define (bar) ...)
	   (list foo bar))

This "imports" two values (sqrt and draw-line) and "exports" two values (foo and
bar).  What values actually get imported is determined by the combination the
function is applied in.  What is done with those values is determined by what is
done with the values returned by the combination.  The "module" defines a
behavior that can be instantiated many times with different values imported and
exported each time.

I am in the process of designing a module system that is based on using
procedures as modules, but that tries to avoid some of the pitfalls of doing so.
For example, it tries to avoid specifying large numbers of inputs and outputs
positionally since doing so tends to be tricky and error prone.  I have run into
some difficult issues that need to be resolved, but I hope to have a detailed
description ready in a couple of months.  The system I have in mind is somewhat
similar to the ML module system that Jonathan described.

The point I would like to emphasize is that a good module system should
encourage and facilitate a "clean" and "modular" style of programming.
Unfortunately, this can get pretty subjective so there may never be one system
that pleases everyone.

I hope you find these comments thought provoking and look forward to your reply.

Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU  1 Jun 88 22:42:45 EDT
Received: from Cabernet.ms by ArpaGateway.ms ; 01 JUN 88 19:40:30 PDT
Date: Wed, 1 Jun 88 19:40:22 PDT
From: Pavel.pa@Xerox.COM
Subject: Re: opaque type proposal
In-reply-to: <386085.880526.JAR@AI.AI.MIT.EDU>
To: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Cc: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <880601-194031-6239@Xerox>

Of course, I forgot to mention my most important issue about this proposal:
inheritance.  I don't see any worm cans surrounding a single-inheritance
facility.  It's simple (all other possibilities have this as a special case, all
with the same semantics), useful (especially for the definition of an error
system) and easily extendable to some hairy multiple-inheritance setup if that's
found desirable in the future.

I strongly support the inclusion of single-inheritance in the facility.

	Pavel

Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU  1 Jun 88 22:18:37 EDT
Received: from Cabernet.ms by ArpaGateway.ms ; 01 JUN 88 19:14:58 PDT
Date: Wed, 1 Jun 88 19:14:38 PDT
From: Pavel.pa@Xerox.COM
Subject: Re: opaque type proposal
In-reply-to: <386085.880526.JAR@AI.AI.MIT.EDU>
To: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Cc: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <880601-191458-6217@Xerox>

This looks fine modulo a couple of questions:

1 -- Why does the ``type-id'' argument have to be a symbol?  I could well
imagine wanting a name like "Compiled Function", which is a pain to have to
translate into a symbol first.

2 -- The point came up here that it would be useful to have a procedure that,
given any Scheme value, returns an object in some way representing the ``type''
of that object.  If two values have the same ``type'', then this hypothetical
procedure would return EQL objects on the two values.  This sort of thing would
be useful for packages that want to allow ``registration'' by clients of
type-specific operations.  The registration mechanism would associate an
operation with a ``type-object'' in some table.  When it came time to apply the
generic operation to a value, the type-object for the value would be mapped to
the type-specific operation, which could then be applied.

Of course, for some of the built-in types there are problems with this.  For
example, do 3 and #i3 return the same ``type-object''?  I think that there are
reasonable choices that can be made for such questions.

In essence, we'd be interested in a facility like the TYPEP and TYPE-OF
functions of Common Lisp but without the issue of type names.

Of course, an obvious choice for the ``type-object'' would be the ``record
type'' objects in your proposal, but, as you say, mapping from objects to their
``record type'' objects is an abstraction-breaker.


	Pavel

Received: from A.ISI.EDU (TCP 3200600147) by MC.LCS.MIT.EDU  1 Jun 88 18:08:41 EDT
Date: Wed 1 Jun 88 18:06:28-EDT
From: Morris Katz <MKATZ@A.ISI.EDU>
Subject: Bug in R3RS
To: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <12403060549.22.MKATZ@A.ISI.EDU>

I believe there is a bug in the R3RS specification of SET! (p. 8). It says that
"<Variable> must be bound in some region enclosing the SET! expression or at 
top level."  I believe that the reference to "top level" is either superfluos
or in error.  If the top level environment is a lexically enclosing environment
then the reference is superfluos, and if the "top level" environment is not 
lexically apparent (I am not even sure if this is possible given the current
environment semantics.) then it is presumably in error.  This definition 
becomes particularly onerous if we adopt some form of first-class environments
as then there is a distinct possibility that a SET! could be performed in an
environment that is not a child of "the top level" environment.  I therefore
propose substituing the following wording for the above sentence:
"<Variable> must be bound in an enclosing lexical environment."  Obviously,
adoption of first-class environments with multiple parents would require
yet further refinement of this sentence.
                                        Morry Katz
-------

Received: from NSS.Cs.Ucl.AC.UK (TCP 20012204403) by MC.LCS.MIT.EDU 27 May 88 09:07:45 EDT
Received: from aiva.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK   via Janet with NIFTP
           id aa05547; 27 May 88 13:52 BST
From: Jeff Dalton <jeff%aiva.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Date: Fri, 27 May 88 13:51:28 bst
Message-Id: <7509.8805271251@aiva.ed.ac.uk>
To: MKATZ@a.isi.edu
Subject: Re: Proposed modifications to RRRS
Cc: rrrs-authors@mc.lcs.mit.edu

> Date: Thu 26 May 88 14:27:49-EDT
> From: Morris Katz <MKATZ@edu.isi.a>
> Subject: Re: Proposed modifications to RRRS

> When one actually wants AND and OR to return the values currently specified
> instead of just being boolean predicates, there is a simple and efficient
> implementation in terms of the AND and OR semantics I advocate. 

What is it?


> Lastly, I must repeat that I just don't buy the argument that language 
> designers must repeat the mistakes of the past in order to maintain 
> compatibility.

To call what was done in the past a mistake is begging the question.  

Perhaps the problem is that AND and OR are called AND and OR, suggesting
that they really are simple boolean operations with some bogosity tacked
on.

You might try suggesting that only #t be considered true.  Then AND
and OR would have to change.

-- Jeff

Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 27 May 88 02:32:48 EDT
Date: Fri, 27 May 88 01:13:52 EDT
From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Subject:  modules
To: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <386391.880527.JAR@AI.AI.MIT.EDU>

Here is my answer to Pavel's request "could you be more concrete about
the kind of system you envision?".

Rather than try to say what I think is the right thing (I don't know),
I'll simply try to describe my understanding of the essence of the ML
module system.  This has been the point of departure in my own recent
ponderage of the topic of modules.  This message does NOT constitute a
proposal or endorsement of its content.

The names have been changed to offend the innocent (MacQueen et al.),
and other accomodations made to a schemish worldview.  Equivalent ML
constructs are given at right.

    <exp> ::= (STRUCTURE <sig> <form>*)           ; struct ... end
	    | (STRUCTURE-REF <struct> <id>)	  ; .
	    | ... the usual ...

    <form> ::= <exp>
	     | <definition>
	     | (OPEN-STRUCTURE <exp> <sig>)       ; open
	     | (DEFINE-SIGNATURE <name> <sig>)    ; signature ... = ...

    <sig> ::= <name>
	    | (SIGNATURE <id>*)                   ; sig ... end

A signature is a list of variable names.  Signature definitions, like
macro definitions, must be known at compile time.  If Scheme had a way
to write types, a signature would give types for the variables; but then
so would any binding construct, including LAMBDA, LETREC, and DEFINE; so
this is an orthogonal design issue.

A STRUCTURE-expression evaluates to a structure, which is something you
can do STRUCTURE-REF on.  The values exported by a structure are given
by the signature.  (A signature is like an interface decsription, and a
structure is like an implementation of that interface.)  The body of a
STRUCTURE-expression looks like the top level of a file.  Simple
example:
   (structure-ref (structure (signature a) (define a 5))
		  a)
        =>  5

The contents of a file that participates in the module system is
typically a single STRUCTURE expression, or a LAMBDA whose body is a
STRUCTURE (in ML, a "functor").  LOAD then returns a structure (or a
procedure that returns a structure).  This being a common case, a file
syntax could be invented (analogous to T's or Pavel's HERALD) that
doesn't leave that extra parenthesis dangling until the end.  The
merits of this are debatable.

(OPEN-STRUCTURE struct sig) is equivalent to a series of DEFINE forms
that transfer values from the given structure to the current
environment.  E.g.
    (open-structure foo (signature a b))
is equivalent to
    (define a (structure-ref foo a))
    (define b (structure-ref foo b))

Of course, one doesn't generally write out (SIGNATURE ...) forms in
STRUCTURE and OPEN-STRUCTURE forms, but instead does a DEFINE-SIGNATURE:
    (define-signature foo-sig (signature a b))
    (define foo (structure foo-sig
		  (open-structure bar bar-sig)
		  (define a ...)
		  (define b ...)))

Multiple definitions in the same block are in error, so in particular,
if I do
    (open-structure foo foo-sig)
    (open-structure bar bar-sig)
within the same STRUCTURE body, and foo-sig and bar-sig both list
an identifier a, then you lose.  (For the same reason that
(lambda (x x) ...) is an error -- and by the way, the report needs to
say that it is.)

If importing is by value rather than by reference, then all of this
mechanism can be implemented using macros.  (Left as an exercise.  Hint:
signatures are macros.)  If importing is by reference, then it can be
done in terms of two new special forms, one for getting a variable's
location (like Zetalisp LOCF or T LOCATIVE) and another for doing an
"identity declaration" (DEFINE-LOCATION var exp), which would bind var
to the value of evaluating exp, which value must be something returned
by a LOCATIVE form.  Of course, more sophisticated implementations are
possible.

Features of the this module system (and ML's) that make me like it
better than Pavel's:

- It's simple: really only four new things.

- File syntax is completely equivalent to some existing expression
  syntax; the existence of files is an artifact.  A call to LOAD
  returns the value of the expression to which the file is equivalent.
  (Actually ML doesn't work quite like this, but it's close.)

- A file is considered to be an expression that yields a value, rather
  than a block of code that has a side-effect on some environment.  Thus
  LOAD is not generally a side-effect, and does not add new bindings to
  any pre-existing environment.  If a client wants to get at the values,
  it has to fetch them itself using STRUCTURE-REF or OPEN-STRUCTURE;
  that's not the file's business.

- Similarly, it is up to the loader of a file to decide in which
  environment the file is to be closed.

- It certainly does not preclude the existence of more general
  first-class environments, but it treats that (and meta-tools
  generally) as an orthogonal question.

- Interfaces (signatures) are described centrally, so that multiple
  implementations and the clients of those implementations can all share
  a single definition.  This makes code more concise and easier to change
  than otherwise.

Things I don't want to talk about now:
  - structures resemble records (concrete vs. abstract types?)
  - importing could be by reference instead of by value
  - inheritance among signatures and implementations
  - signatures could be first class (echoes of PROGV)
  - what about interactive development & debugging
  - performance questions (e.g. how to avoid lots of copying) (I think Appel
    has written a paper about this)
  - open-structure is too powerful
  - maybe allow open-structure in other contexts, or disallow it except at
    top of a structure form, or banish it altogether
  - multiple "views" on a structure
  - syntactic file sugar to avoid dangling parentheses
  - where do macros fit in (put them in signatures?)
  - system configurations
  - functors
  - Felleisen & Friedman '85
  - etc.

I didn't promise that I was going to give constructive criticism.  Maybe
if you wait a few months I'll be able to answer these concerns and
propose something I like.


Received: from chamarti (TCP 2206400253) by MC.LCS.MIT.EDU 26 May 88 23:06:01 EDT
Received: by CHAMARTIN.AI.MIT.EDU; Thu, 26 May 88 23:02:23 edt
Date: Thu, 26 May 88 23:02:23 edt
From: jinx@CHAMARTIN.AI.MIT.EDU (Guillermo J. Rozas)
Message-Id: <8805270302.AA14916@chamarti>
To: Pavel.pa@Xerox.COM
Cc: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Pavel.pa@Xerox.COM's message of Fri, 20 May 88 11:49:26 PDT <880520-115000-2371@Xerox>
Subject: A Proposal for Environments in Scheme
Reply-To: jinx@zurich.ai.mit.edu

I have some problems with your proposal:

      MAKE-ENVIRONMENT <id> <parent> ...				[Procedure]

1) The <id> seems spurious, although harmless.

2) What is the purpose of multiple inheritance?  With single
inheritance there is still the "fiction" of lexical scoping: You can
picture the new environment as appearing virtually somewhere in its
parent, but with multiple inheritance this fiction goes away.
Is the confusion warranted?

    In addition to these procedures, We propose a change to the meanings of
    identifiers whose names include colons:

      -- No identifier may begin or end with a colon.
	 (Alternatively, such identifiers behave as they do now.)
      -- An identifier of the form a:b1:...:bk (k >= 1) is entirely equivalent to
	 the expression
		    (ENVIRONMENT-REF a:b1:...:bk-1 'bk)


I have strong objections against read syntax:

1) What is wrong with (ACCESS a b1 b2 ... bk)?  If it is too long, I'm
perfectly happy with (: a b1 b2 ... bk), which only adds 4 characters
to your proposal, and no read syntax.

2) Read syntax has the following problem:

(set! a:b:c 3)

expands into

(set! (environment-ref (environment-ref a 'b) 'c) 3)

which is not valid syntax for SET!  Clearly it would be desirable if
the above expanded into

(environment-set! (environment-ref a 'b) 'c 3)

but this is no longer read syntax.


    A file of Scheme code, under this proposal, may optionally begin with a piece of
    syntax, called a >herald<, that arranges for special treatment of the
    environmental context of the code in the file.  Heralds obey the following
    syntax:

		    (HERALD <option>+)

    etc.

I think this is not very well thought out.  By placing a HERALD in a
file you are making the file "absolute" rather than "relative".  I
can no longer load the file into multiple environments with different
contexts except by munging the loader (to change GLOBAL, or whatever,
temporarily).

I think you would be much better off separating the contents of the
file from the definition of the system that describes and creates the
context into which the file is supposed to be loaded.

Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 26 May 88 16:22:57 EDT
Date: Thu, 26 May 88 16:20:53 EDT
From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Subject:  opaque type proposal
To: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <386085.880526.JAR@AI.AI.MIT.EDU>

            Opaque types / record structures for R^4 Scheme

                     Draft #3, J. Rees, 26 May 1988

Norman Adams's message of 8 July 1987 to RRRS-Authors proposing record
types for Scheme met with a deafening silence.  Here is my reiteration
of his proposal.  This also is a counter-proposal to the
INJECT/PROJECT/IN?  opaque type facility that Will and/or I proposed a
while back.

The proposal consists of the following 5 procedures.  MAKE-RECORD-TYPE
creates a new "record type" object, and the other 4 procedures are
accessors for record types that return procedures.  The type of the
value returned for each procedure is given after a ":".

  (MAKE-RECORD-TYPE type-id field-names) : record-type
     where type-id is a symbol, and field-names is a list of symbols
  (RECORD-CONSTRUCTOR record-type)       : (object X ...) -> record
  (RECORD-PREDICATE record-type)         : object -> boolean
  (RECORD-ACCESSOR record-type name)     : record -> object
  (RECORD-UPDATER record-type name)	 : record X object -> unspecified

Example:

  (define yow-record-type (make-record-type 'yow '(a b c)))

  (define make-yow
    (let ((construct-yow (record-constructor yow-record-type)))
      (lambda (a-val other-val)
        (let ((b-val (compute-b other-val))
	      (c-val (compute-c a-val b-val other-val)))
          (construct-yow a-val b-val c-val)))))

  (define yow? (record-predicate yow-record-type))
  (define yow-a (record-accessor yow-record-type 'a))
  (define yow-b (record-accessor yow-record-type 'b))
  (define yow-c (record-accessor yow-record-type 'c))
  (define set-yow-c! (record-updater yow-record-type 'c))

  (yow? (make-yow 2 17))  =>  #t
  (yow-a (make-yow 2 17))  =>  2

It is an error to call an accessor or updater for a record type R on an
object that wasn't created by R's constructor.  MAKE-RECORD-TYPE is a
side effect, like CONS.  Every new record type is disjoint from every
old one and from other Scheme types such as pairs, vectors, and
procedures.  In particular, records must answer false to existing type
predicates, including PAIR?, VECTOR?, and PROCEDURE?.  Thus this
mechanism must be added primitively to Scheme.

The type-id argument to MAKE-RECORD-TYPE has no semantic content.  It is
solely for the use of the printer and related routines, to make records
easier to identify during debugging.  The field names are used only for
coordination between MAKE-RECORD-TYPE and RECORD-ACCESSOR/UPDATER.

-----

Notes: 

The use of the word "type" for an object that describes a type is
somewhat inappropriate, and would raise the hackles of people who
believe they know what types are.  The objects might better be called
"record type descriptors" even though that's a little long; the
constructor would then be MAKE-RECORD-TYPE-DESCRIPTOR.

This is essentially T's record package (MAKE-STYPE), except that the
constructor takes as arguments initial values for all the fields,
rather than for none of them.

No general record-type-defining macro is proposed.  Defining a good one
is difficult or impossible; I have tried many times and failed to come
up with something that's both elegant and flexible enough.  Once we have
macros, people can roll their own, so we shouldn't clutter the language
at this point.

Initial value arguments to constructors could be passed by keyword, as
in Common Lisp, but they're positional here for consistency with the
rest of Scheme, and for efficiency.

There is intentionally no way to go from a record to its record-type.
Clearly implementations can (and for debugging, would) provide such a
procedure, but it would have the same abstraction-breaking ability
that something like PROCEDURE-CODE have.

Question: should there be a (RECORD-COPIER record-type) as in CL?
  - Will Clinger says no; a copier for a particular record type
    can be written pretty easily.
  - Richard Kelsey says yes, for performance and convenience.

Issues purposely avoided: subtyping (a.k.a. inheritance); print methods
(a.k.a. object-oriented programming); integration with modules and/or
environments (a.k.a. Pascal WITH).  While these are all probably
desirable, they open many worm cans, and we should try to prevent the
consideration of such questions to slow the adoption of this proposal.

-----

Here is a sample implementation.  It is not minimal, but is instead
intended to be somewhat realistic.

A real implementation would require that records not satisfy VECTOR? (or
any other existing Scheme type predicate).

(define (make-record-type type-id field-names)

  (define (constructor . field-values)
    (if (= (length field-values) (length field-names))
	(apply vector the-record-type field-values)
	(error "wrong number of arguments to record constructor"
	       type-id field-values)))

  (define (predicate obj)
    (and (vector? obj)
	 (> (vector-length obj) 0)
	 (eq? (vector-ref obj 0) the-record-type)))

  (define (accessor name)
    (let ((i (field-index name)))
      (lambda (record)
	(if (predicate record)
	    (vector-ref record i)
	    (error "not a record" record name)))))

  (define (updater name)
    (let ((i (field-index name)))
      (lambda (record new-value)
	(if (predicate record)
	    (vector-set! record i new-value)
	    (error "not a record" record name)))))

  (define (field-index name)
    (let loop ((l field-names) (i 1))
      (if (null? l)
	  (error "bad field name" name)
	  (if (eq? name (car l))
	      i
	      (loop (cdr l) (+ i 1))))))

  (define the-record-type
    (lambda (request)
      (case request
	((constructor) constructor)
	((predicate) predicate)
	((accessor) accessor)
	((updater) updater))))

  the-record-type)

(define (record-constructor r-t) (r-t 'constructor))
(define (record-predicate r-t) (r-t 'predicate))
(define (record-accessor r-t field-name) ((r-t 'accessor) field-name))
(define (record-updater r-t field-name) ((r-t 'updater) field-name))


Received: from kleph (TCP 2206400254) by MC.LCS.MIT.EDU 26 May 88 15:00:06 EDT
Received: by kleph.AI.MIT.EDU; Thu, 26 May 88 14:59:05 edt
Date: Thu, 26 May 88 14:59:05 edt
From: cph@kleph.AI.MIT.EDU (Chris Hanson)
Message-Id: <8805261859.AA06488@kleph>
To: MKATZ@A.ISI.EDU
Cc: rrrs-authors@MC.LCS.MIT.EDU
In-Reply-To: Morris Katz's message of Thu 26 May 88 14:27:49-EDT <12401447879.26.MKATZ@A.ISI.EDU>
Subject: Proposed modifications to RRRS
Reply-To: cph@zurich.ai.mit.edu

Regarding your suggestions to change the semantics of AND and OR:

I find the current semantics useful and desirable.  I have long felt
that one of the good features of lisp was that, rather than having two
distinguished boolean values, there is only only one: #F.  I have
often found it useful that all other values are true.

My feeling is that AND and OR are extensions of that philosophy, in
that they do not canonicalize the truth value as #T.

While I agree with you that we should not retain these for historical
reasons, I disagree in that I feel these constructs, with their
current semantics, have value in a modern lisp.

Received: from A.ISI.EDU (TCP 3200600147) by MC.LCS.MIT.EDU 26 May 88 14:42:31 EDT
Date: Thu 26 May 88 14:39:27-EDT
From: Morris Katz <MKATZ@A.ISI.EDU>
Subject: Re: Proposed modifications to R3RS
To: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <12401449998.26.MKATZ@A.ISI.EDU>

>> b)  Overspecification should be avoided as it artificially
>>     prohibits reasonable implementations.
>> 3)  I believe that AND is overspecified as it states that "[...]
>>     If all the expressions evaluate to true values, the value of
>>     the last expression is returned."
>>     (A similar change should be made to OR.)
>Your complaint about AND is that it returns the value of the last form
>instead of simply true or false.  But calling that "overspecification"
>is just another way of saying it should return simply true or false,
>they overspecified.
If by true and false above the author meant #t and #f, this is not what I
advocated at all.  I carefully specified that AND and OR should return a true
value or a false value (by which I meant something that acted as a true or a
false when used by IF and COND.).  I strongly believe that specifying that 
AND and OR return either #t or #f would be overspecification in the oposite
direction.  My original specification makes all current implementations
adhere to the standard.  It just allows new implementations to perform
more effective optimizations of the uses of AND and OR.

					Morry Katz
-------

Received: from A.ISI.EDU (TCP 3200600147) by MC.LCS.MIT.EDU 26 May 88 14:31:14 EDT
Date: Thu 26 May 88 14:27:49-EDT
From: Morris Katz <MKATZ@A.ISI.EDU>
Subject: Re: Proposed modifications to RRRS
To: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <12401447879.26.MKATZ@A.ISI.EDU>

>> 3)  I believe that AND is overspecified [...]
>I see both sides of this one.  As an implementor, I hate for these
>things to be overspecified.  In fact, I have some logic in my compiler
>to look for chances to simplify the true value returned by AND and its
>kin.  However, AND has such a long history that the dusty deck (and
>dusty brain) factor can't be ignored.
When one actually wants AND and OR to return the values currently specified
instead of just being boolean predicates, there is a simple and efficient
implementation in terms of the AND and OR semantics I advocate.  However, the
reverse is not true.  One could wrap all all uses of AND and OR as predicates 
in a function which canonicalized the return values to #t and #f, but this
would be neither efficient nor esthetically pleasing.  Furthermore, this 
would add yet one more special case for the efficient compiler to worry about.
Lastly, I must repeat that I just don't buy the argument that language 
designers must repeat the mistakes of the past in order to maintain 
compatibility.  Bad ideas should be purged from or memories, not reenforced.

>> 1) and 2) Do and CASE

My original proposal advocated standardizing macros and then relegating
these features to library status.  I stand by this recommendation.  To me the 
distinction between essential and inessential is a bad one because those
attempting to write portable code can only depend on essential features, 
anyway.  This means that inessential features are effectively not part of the 
language and a really just commonly used portions of a library.  I therefore 
make the previously discussed suggestion again:

5)  Lets remove the distinction between essential and inessential features and
in each case decide that the feature either is or is not part of the language.
-------

Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 26 May 88 05:52:25 EDT
Date: Wed, 25 May 88 13:07:23 EDT
From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Subject:  Proposed modifications to R3RS
To: MKATZ@A.ISI.EDU
cc: rrrs-authors@MC.LCS.MIT.EDU
In-reply-to: Msg of Tue 24 May 88 13:13:21-EDT from Morris Katz <MKATZ at A.ISI.EDU>
Message-ID: <385117.880525.JAR@AI.AI.MIT.EDU>

    Date: Tue 24 May 88 13:13:21-EDT
    From: Morris Katz <MKATZ at A.ISI.EDU>

    a)  Syntactic sugar should only be added to the language if its
        usefulness far outweighs the complexity it introduces.

It's difficult to make objective arguments on this rounds, because
different people have uses for different things.

    b)  Overspecification should be avoided as it artificially
        prohibits reasonable implementations.

Underspecification effectively amounts to giving an axiomatic semantics
(proof system) for the language, as opposed to a denotational one (a
model).  The problem with underspecification is that one can have a
program that works fine in one implementation and fails in another, so
the only way to produce portable code is by reasoning about it, and
testing doesn't help you a bit.  While I agree that some
underspecifications are important, I believe you can go too far in
underspecifying things that really don't make much difference, requiring
reasoning in situations where testing ought to be sufficient.

Underspecifications makes the language harder to learn and use, since an
implementation cannot teach them very well.  One must be aware of all
underspecifications all the time.  I think they should be minimized, not
maximized.

    1)  The DO construct should be eliminated from the language as it
        is easily implemented using named-let's or letrec's.  

At first I thought I didn't make much use of it, but empirical evidence
shows that I think it's important to keep it.  I just checked one large
recently-written system of mine, and I wrote 47 out of 88 loops using
DO.

I can't believe this question is being raised again.  You would do us a
favpor by looking through the archives (in AI: LSPMAI; RRRS MAILnn) to
see how this issue was dealt with before.  It was also argued at the
1984 meeting, as I remember.

    2)  The CASE statement should be eliminated for the same reasons
        as DO.  How many of you have ever used a CASE?  
I use it all the time.
        Would it really have been less clear had you used a COND?
Yes.

    3)  I believe that AND is overspecified ...

It has been proposed to eventually eliminate the possibility of multiple
false values.  That would fix your complaint about AND.  Until that
time, AND should be symmetric with OR.  Thus in your arguments I would
prefer you use OR as your example rather than AND.  It seems somewhat
unprincipled that you start out by saying you think AND is
underspecified and say only as an afterthought that you think OR is.

I think that rather than take the half-way measure you propose, you
should instead be in favor of making it an error for the predicate of an
IF to be a non-boolean.  This would get you some of the results you
want for OR and AND, and it would get you many other beneficial
transformations as well.

By the way, it's clear that OR (and AND) must necessarily return the
value of the last form if previous forms evaluate to false (true);
otherwise you will lose tail recursion.  (Unless you imagine one
sophisticated continuation garbage collector.)

    4)  LAST-PAIR should be eliminated as it is gratuitous at best.
        After all, its tail-recursive implementation appears directly
        below it in R3RS.  Personally, I can see no performance
        reason for keeping it, which would be the only possible
        justification.  

OK, let's flush LENGTH, APPEND, REVERSE, ASSOC, CHAR=?, VECTOR->LIST,
and all other easily-definable procedures as well.  EQUAL? isn't so hard
to write either.  There is no performance advantage to having these.


Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 26 May 88 05:52:13 EDT
Date: Wed, 25 May 88 12:29:19 EDT
From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Subject:  Omission in R^3.5 LETREC description?
To: Ziggy@VX.LCS.MIT.EDU
cc: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <385093.880525.JAR@AI.AI.MIT.EDU>

    Date: Mon, 23 May 88  23:46:05 EDT
    From: Ziggy at VX
    To:   jar at ai
    Re:   Omission in R^3.5 LETREC description?

     Shouldn't the caveat: [p.10 or R^3.5]

     "...without referring to the value of any <variable>."

     read

     "...without referring to the value or location of any <variable>."

    -----
     Specifically, isn't the following a screw case:

     (LETREC ((wanna-be-a-doctor    'DOCTOR)
	      (imagine-my-surprise! (BEGIN (SET! wanna-be-a-doctor 'NURSE)
					   'ZOWIE!!)))
	wanna-be-a-doctor)  ==>  NURSE
    -----

    One could reasonably assume, based on the English description (and
    desugaring on page 36) that the RHSs will each be evaluated then
    their results will be stored thus the above should yield DOCTOR.
    Note that the value of WANNA-BE-A-DOCTOR is not referred to, but the
    location to which it is bound IS.

Yuck.  I'm not sure we want to be quite this anal about it, and I'm a
little worried about formal description and implementation of the kind
of error checking you suggest.  It would require making LETREC a
primitive, rather than derived, expression type, I think.  I'm cc'ing
rrrs-authors to see whether anyone else has thought about this and has
opinions.


Received: from Think.COM (TCP 1201000006) by MC.LCS.MIT.EDU 26 May 88 04:49:27 EDT
Return-Path: <gls@Think.COM>
Received: from kali.think.com by Think.COM; Wed, 25 May 88 13:03:13 EDT
Received: by kali.think.com; Wed, 25 May 88 13:03:07 EDT
Date: Wed, 25 May 88 13:03:07 EDT
From: gls@Think.COM
Message-Id: <8805251703.AA12183@kali.think.com>
To: jeff%aiva.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK
Cc: MKATZ@a.isi.edu, rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Jeff Dalton's message of Tue, 24 May 88 20:16:15 bst <15442.8805241916@aiva.ed.ac.uk>
Subject: Proposed modifications to R3RS

   From: Jeff Dalton <jeff%aiva.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
   Date: Tue, 24 May 88 20:16:15 bst
   ...
   I don't much mind the change in AND.  After all, only the last
   expression can return anything other than #f.  With OR, on the other
   hand, it's useful to know which true value was obtained. 

Actually, in the current confused state of affairs I believe that
#f and () might be distinct values but both treated as false?
In which case it might be useful with AND to know which false
value was obtained.  :-)

--Quux

Received: from NSS.Cs.Ucl.AC.UK (TCP 20012204403) by MC.LCS.MIT.EDU 25 May 88 11:55:27 EDT
Received: from aiva.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK   via Janet with NIFTP
           id aa09202; 24 May 88 20:18 BST
From: Jeff Dalton <jeff%aiva.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Date: Tue, 24 May 88 20:16:15 bst
Message-Id: <15442.8805241916@aiva.ed.ac.uk>
To: MKATZ@a.isi.edu, rrrs-authors@mc.lcs.mit.edu
Subject: Re: Proposed modifications to R3RS

> b)  Overspecification should be avoided as it artificially
>     prohibits reasonable implementations.

> 3)  I believe that AND is overspecified as it states that "[...]
>     If all the expressions evaluate to true values, the value of
>     the last expression is returned."

>     (A similar change should be made to OR.)

Your complaint about AND is that it returns the value of the last form
instead of simply true or false.  But calling that "overspecification"
is just another way of saying it should return simply true or false,
and so it is not an argument for returning true or false.

I guess what I'm trying to say is that it depends on what you want AND
and OR to be.  Only if you want logical operations and no more are
they overspecified.

I don't much mind the change in AND.  After all, only the last
expression can return anything other than #f.  With OR, on the other
hand, it's useful to know which true value was obtained. 

Jeff Dalton,                      JANET: J.Dalton@uk.ac.ed             
AI Applications Institute,        ARPA:  J.Dalton%uk.ac.ed@nss.cs.ucl.ac.uk
Edinburgh University.             UUCP:  ...!ukc!ed.ac.uk!J.Dalton

Received: from ti.com (TCP 1201600056) by MC.LCS.MIT.EDU 25 May 88 02:35:13 EDT
Received: by ti.com id AA08189; Tue, 24 May 88 16:01:37 CDT
Received: from mips by tilde id AA04707; Tue, 24 May 88 15:50:16 CDT
Received: by mips id AA07133; Tue, 24 May 88 15:50:08 CDT
Date: Tue, 24 May 88 15:50:08 CDT
From: David Bartley <bartley@mips.csc.ti.com>
Message-Id: <8805242050.AA07133@mips>
To: MKATZ@A.ISI.EDU
Cc: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Morris Katz's message of Tue 24 May 88 13:13:21-EDT <12400910036.32.MKATZ@A.ISI.EDU>
Subject: Proposed modifications to R3RS

> From: Morris Katz <MKATZ@A.ISI.EDU>
> Subject: Proposed modifications to R3RS
> [...]
> 1)  The DO construct should be eliminated from the language as it
>     is easily implemented using named-let's or letrec's.

DO is inessential and so is perhaps a good candidate for excision from
the IEEE standard, but it is probably too commonly used for most of us
to want to remove support for it from our existing or planned
implementations.  Thus it should remain in the informal standard to
ensure we all do it the same way.  (For example, someone may make it
re-ASSIGN rather than re-BIND the variables at each iteration if they
didn't know better.  That could introduce subtle portability bugs.)

> 2)  The CASE statement should be eliminated for the same reasons
>     as DO.  How many of you have ever used a CASE?  Would it
>     really have been less clear had you used a COND?  This should
>     be a library function if it is going to exist at all.

CASE is also inessential syntax.  I use CASE a lot, and find it to be
much more clear than COND when I use it.  CASE makes it clear that I
am dispatching on a value; I have to inspect all of the clauses of a
COND to see if they all fit the same pattern otherwise.  Since CASE is
syntax and not a function, we would need macros before we could demote
it to a library.

> 3)  I believe that AND is overspecified [...]

I see both sides of this one.  As an implementor, I hate for these
things to be overspecified.  In fact, I have some logic in my compiler
to look for chances to simplify the true value returned by AND and its
kin.  However, AND has such a long history that the dusty deck (and
dusty brain) factor can't be ignored.

> 4)  LAST-PAIR should be eliminated as it is gratuitous at best.

Definitely.

See, I tried to be agreeable!

Regards,
David Bartley

Received: from A.ISI.EDU (TCP 3200600147) by MC.LCS.MIT.EDU 24 May 88 13:17:02 EDT
Date: Tue 24 May 88 13:13:21-EDT
From: Morris Katz <MKATZ@A.ISI.EDU>
Subject: Proposed modifications to R3RS
To: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <12400910036.32.MKATZ@A.ISI.EDU>

The following is a series of proposed modifications to and
deletions from R3RS.  They are all based on the following two
principals: 
a)  Syntactic sugar should only be added to the language if its
    usefulness far outweighs the complexity it introduces
    (e.g., I believe that (define (<name> <vars>) <body) as
    syntactic sugar for (define <name> (lambda (vars) <body>))
    and named-let both fulfill this criterion.) or it is important
    for performance reasons that some construct which can be
    built from a few primitives be a primitive itself.
b)  Overspecification should be avoided as it artificially
    prohibits reasonable implementations.

In at least one case, a suggestion to follow has been mentioned
before; but, I feel it is important enough to justify further
flag waving.

1)  The DO construct should be eliminated from the language as it
    is easily implemented using named-let's or letrec's.  Its
    syntax is difficult to follow at best, and it is not powerful
    enough for many applications.  (e.g. One often has a <test>
    which is the disjunction of many different forms and wants to
    return a different result depending on which form is true.
    DO does not give a simple way of implementing this case short
    of repeating the conditionals in the <expressions>.)  If
    people really want DO because of dusty deck problems or
    compatibility with CL (Editorial comment: I think this is a
    really bad motivation.) lets settle on a macro standard and
    let those who want DO have it as a library function (special
    form). 

2)  The CASE statement should be eliminated for the same reasons
    as DO.  How many of you have ever used a CASE?  Would it
    really have been less clear had you used a COND?  This should
    be a library function if it is going to exist at all.

3)  I believe that AND is overspecified as it states that "The
    <test> expressions are evaluated from left to right, and the
    value of the first expression that evaluates to a false value
    is returned.  Any remaining expressions are not evaluated.
    If all the expressions evaluate to true values, the value of
    the last expression is returned."  This should be replaced by
    something like the following: "The <test> expressions are
    evaluated from left to right, with evaluation terminating
    with the first expression that evaluates to a false value.
    Any remaining expressions are not evaluated.  If some
    expression evaluates to false then a false value is returned,
    otherwise a true value is returned." (A similar change should
    be made to OR.
    A compiler should feel free to replace 
        (or (a) (not (a)))
    with #t if it can prove that A is side-effect free and
    terminates without generating an error.  Similarly,
        (and (fact n) (fact (-1+ n)))
    should be replaceable by #t if FACT is the standard recursive
    factorial function and N can be proven to be a nonnegative
    integer. (These transformations are not possible given the
    current specification.)
    Also, an implementor is not free to introduce unique true and
    false objects which are always returned by predicates.  
    If one actually wants the old semantics of AND they can
    always write 
        (let ((test1 <test1>))
          (if test1 
              test1
              <test2>))
    which I believe is much more transparent, anyway.

4)  LAST-PAIR should be eliminated as it is gratuitous at best.
    After all, its tail-recursive implementation appears directly
    below it in R3RS.  Personally, I can see no performance
    reason for keeping it, which would be the only possible
    justification.  

                                 Morry Katz

P.S. I erroneously stated in a previous message that MIT CScheme
has a feature like call-with-current-continuation for
environments.  It does NOT.  I was thinking at the time of its
IN-PACKAGE feature which allows one to evaluated an expression in
an existing environments and in my mind is a (loose) environment
analog to throwing to a continuation.  I will have to reread
Johnson and Duggan's paper, "Stores and Partial Continuations as
First-Class Objects in a Language and its Environment," from POPL
1988 before I can appropriately comment on the original question
as to whether we should introduce a call-with-current-environment.
-------

Received: from mitre-bedford.ARPA (TCP 3200600102) by MC.LCS.MIT.EDU 24 May 88 11:42:02 EDT
Posted-From: The MITRE Corp., Bedford, MA
Received: from darwin.sun.uucp by linus.MENET (3.2/4.7)
	id AA08685; Mon, 23 May 88 13:49:09 EDT
From: John D. Ramsdell <ramsdell%linus@mitre-bedford.ARPA>
Posted-Date: Mon, 23 May 88 13:49:04 EDT
Received: by darwin.sun.uucp (3.2/SMI-3.0DEV3)
	id AA04694; Mon, 23 May 88 13:49:04 EDT
Date: Mon, 23 May 88 13:49:04 EDT
Message-Id: <8805231749.AA04694@darwin.sun.uucp>
To: Pavel.pa@Xerox.COM
Cc: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Pavel.pa@Xerox.COM's message of Fri, 20 May 88 11:49:26 PDT <880520-115000-2371@Xerox>
Subject: A Proposal for Environments in Scheme

Thank you for your interesting environment proposal.  I am not sure
what I think of it, but I do have one question.

What exactly is an identifier?  Is it a symbol whose print name does
not end or begin with a colon?  If so, the print name determines the
interpretation of an identifier.  This mixes up the concept of how to
print a symbol with the concept of how to use it as an identifier.

Maybe colon is a read time macro, and no symbol is allowed to contain
colon.  

[1] a:b		==>  (eval (ENVIRONMENT-REF B (QUOTE A)))

[2] 'a:b	==>  (ENVIRONMENT-REF B (QUOTE A))

[3] (string->symbol "A:B")	==>	?

By your description [1] is true, what about [2]?  What is [3]?
John

Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU 23 May 88 22:05:22 EDT
Received: from Semillon.ms by ArpaGateway.ms ; 23 MAY 88 18:58:45 PDT
Date: Mon, 23 May 88 18:58:38 PDT
From: Pavel.pa@Xerox.COM
Subject: Re: A Proposal for Environments in Scheme
In-reply-to: <12400711603.24.MKATZ@A.ISI.EDU>
To: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <880523-185845-5883@Xerox>

Morry writes, ``It is precisely because the <id> is so often unnecessary, and
even possible misleading, that I feel it should not be required.''

I'm sorry; I misinterpreted your earlier comments.  Your point is well taken, in
that no other R3RS data object carries an identifier with it.  I suppose that I
have no problem with making the <id> optional, but I definitely want to be able
to specify it, since I always find it useful and never confusing or misleading.

I can't speak to your comments concerning the variable-caching mechanism in
C-Scheme.  I believe that the usual case involves only single-inheritance,
though, so no mechanisms that work well for that should break down in the new
world.  In particular, the normal environments that come up during the
evaluation of compound procedure applications (i.e., applications of the results
of lambda-expressions) will all have only single inheritance.

As for the environment analog of call-with-current-continuation, by which I
assume we mean something like THE-ENVIRONMENT in C-Scheme, I would truly
appreciate a clear, concise example.

	Pavel

Received: from A.ISI.EDU (TCP 3200600147) by MC.LCS.MIT.EDU 23 May 88 20:09:07 EDT
Date: Mon 23 May 88 19:03:20-EDT
From: Morris Katz <MKATZ@A.ISI.EDU>
Subject: Re: A Proposal for Environments in Scheme
To: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <12400711603.24.MKATZ@A.ISI.EDU>

    1)  I believe it is a big mistake to require that all environments have a
        name.  There was a good reason(s) for deciding that not all procedures
        in Lisp should have to be named, and I believe that those arguments
        apply equally well to this case.

    I think that you misunderstood the purpose of the <id> argument to
    MAKE-ENVIRONMENT.  It is not a name in the sense that a given name maps to
    a single environment.  Its only purpose is to be some nice thing to show as
    a part of the printed representation of the environment.  It also helps
    humans have a more reasonable handle for talking about environments.  The
    <id> has absolutely no semantic content except that it can be extracted
    from the environment with the procedure ENVIRONMENT-ID.  There are no
    guarantees that <id>'s are unique and no functions for mapping an <id> into
    the environments having it.

It is precisely because the <id> is so often unnecessary, and even possible
misleading, that I feel it should not be required.  I suspect that most people
in the Scheme community would baulk at a required syntax of
(lambda (<id> <args>) <body>) for lambda expressions.  Why should environments
be any different?

    2)  I have been interested in the semantics and use of multiple environment
        inheritance for some time; but, I am not sure that it is well enough
        understood to become part of R3RS.  (Maybe someone else understands it
        better than I do and can convince me otherwise.)  In particular, I am
        concerned about efficient implementations for interpreted code,
        difficulty in understanding code which utilizes this feature, and the
        development of suitable browser technology to make debugging of
        programs using it tractable.
 
    It is easy to implement multiple parents efficiently in the interpreter.
    In Cedar Scheme, environments have two field for parent information; one of
    the fields holds the first parent and the other holds a list of the other
    parents. In almost all cases, single inheritance is used and the
    otherParents field is NIL.  Thus, no consing of environment lists occurs in
    the interpreter.  The variable lookup procedure is straightforward and, in
    the case where otherParents is NIL, is precisely the same as the single
    inheritance case.
 
I am well aware of the obvious implementation of multiple inheritance presented
above.  I was more concerned about whether variable caching schemes like those
used by MIT Cscheme still work with multiple inheritance.  (i.e. Does one still
get the same performance benefits from caching?  If so, how much greater is the
cost of an incremental definition due to multiple inheritance?) 
 
        Should there be an environment analog of
        call-with-current-continuation?  
 
    I've not yet seen a good use for this.
 
MIT Cscheme has this feature and I have seen effective use made of it in the
past, although I don't seem to be able to come up with a clear, concise example
at this time.
					Morry Katz
-------

Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU 23 May 88 16:48:34 EDT
Received: from Semillon.ms by ArpaGateway.ms ; 23 MAY 88 13:41:36 PDT
Date: Mon, 23 May 88 13:41:18 PDT
From: Pavel.pa@Xerox.COM
Subject: Re: A Proposal for Environments in Scheme
In-reply-to: <19880523203243.9.ALAN@PIGPEN.AI.MIT.EDU>
To: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <880523-134136-5254@Xerox>

Alan points out that LET is not a variable, implying (I guess) that its
behaviour cannot depend upon the environment.

The point is well taken, but I submit that the statements still make sense in
some implementations, in which the sematics of special forms are in some way
attached to the environment, whether by a special kind of value bound to the
name of the special form (as in Cedar Scheme) or by a entry for that name in a
special ``syntax table'' associated with the environment.  In such
implementations, one would hope that the behaviour of the special forms would
obey the same kinds of environment inheritance rules as do normal names.  This
was the intent of the comments in the specification of the various initial
environments.

    Can you say:

      (SCHEME:LET ...)?

    Presumably not, if the ":" syntax is taken to be an abbreviation for a
    call on the ENVIRONMENT-REF procedure.

True, you cannot use this form.  Syntax must be directly inherited under the
proposal (in the kind of implementations I described above) and cannot be used
``remotely'' as shown above.

	Pavel

Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU 23 May 88 16:42:15 EDT
Received: from Semillon.ms by ArpaGateway.ms ; 23 MAY 88 13:31:10 PDT
Date: Mon, 23 May 88 13:30:45 PDT
From: Pavel.pa@Xerox.COM
Subject: Re: A Proposal for Environments in Scheme
In-reply-to: <383749.880523.JAR@AI.AI.MIT.EDU>
To: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <880523-133110-5223@Xerox>

Jonathan says, ``In particular, one should be able to modularize one's programs
without having to resort to a side-effecty style.''

I want to point out that the proposal I presented does not required any use at
all of the environment-manipulation facilities except for MAKE-ENVIRONMENT and
ENVIRONMENT-REF.  The other procedures are not provided for conventional use of
the facility but rather for more meta-level programming, such as a portable
interpreter or inspector.  None of the programs written in Cedar Scheme use the
other environment-manipulation procedures at all.

As for block compilation, the same kinds of optimizations can be applied here in
those cases where a new environment is being used for the file (the usual case).
All unexported names are entirely internal to the file and calls between them
can be optimized arbitrarily, in precisely the same way as the block compilation
of LETREC.

I, also, would like an official way to specify interfaces (though I disagree
that they must simply be lists of names; Scheme is *not* untyped, it is not
*statically* type-checked, a big difference).  This is no harder or easier with
the proposal I gave than with any other set-up.  One simply makes some
declaration about the names visible in the environment bound to a certain
identifier in a certain environment.  No facility can do any more than that and
it's clearly as feasible in our proposal as anywhere.

Jon, could you be more concrete about what kind of system you envision?  I'm not
asking for a complete proposal, but perhaps a small motivating example in the
style of your early system would be possible.  I'd like to understand the issues
that you perceive.

	Pavel

Received: from REAGAN.AI.MIT.EDU (CHAOS 13065) by MC.LCS.MIT.EDU 23 May 88 16:35:45 EDT
Received: from PIGPEN.AI.MIT.EDU by REAGAN.AI.MIT.EDU via CHAOS with CHAOS-MAIL id 113999; Mon 23-May-88 16:32:34 EDT
Date: Mon, 23 May 88 16:32 EDT
From: Alan Bawden <Alan@AI.AI.MIT.EDU>
Subject: A Proposal for Environments in Scheme
To: Pavel.pa@Xerox.COM
cc: rrrs-authors@MC.LCS.MIT.EDU
In-Reply-To: <880520-115000-2371@Xerox>
Message-ID: <19880523203243.9.ALAN@PIGPEN.AI.MIT.EDU>

    Date: Fri, 20 May 88 11:49:26 PDT
    From: Pavel.pa@Xerox.COM
    ...

      "SCHEME"
  
	Contains exactly those bindings described in the Scheme specification,
	except that a given implementation may not provide all of the optional
	features.  Thus, in this environment, APPEND may or may not accept an
	arbitrary number of arguments, LET may or may not allow the named variant,
	etc....

Except LET isn't a variable.

Can you say:

  (SCHEME:LET ...)?

Presumably not, if the ":" syntax is taken to be an abbreviation for a
call on the ENVIRONMENT-REF procedure.

Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 23 May 88 16:15:22 EDT
Date: Mon, 23 May 88 16:17:43 EDT
From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Subject:  [Pavel.pa: A Proposal for Environments in Scheme]
To: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <383755.880523.JAR@AI.AI.MIT.EDU>

A number of people seem to have not received this, so I am re-sending it.
- Jonathan

Date: Fri, 20 May 88 11:49:26 PDT
From: Pavel.pa at Xerox.COM
To:   rrrs-authors at mc.lcs.mit.edu
Re:   A Proposal for Environments in Scheme

I'd like to offer the following proposal for a facility for first-class
environments in Scheme.  We have found it to work quite cleanly and powerfully
in Cedar Scheme and thus believe that it is worthy of consideration for
inclusion in the standard language.

	Pavel Curtis
	Xerox PARC/CSL

INTRODUCTION

If Scheme is to grow and be used by more people, one of the problems it must
solve is the robust isolation of different pieces of the system and user code
from each other.  The system described in this section is an attempt to cleanly
and simply solve this problem, with an eye toward making the addition of a true
file-compiler a simple extension with clean semantics.  It is fully implemented
in Cedar Scheme.

Note that this system does not attempt to address the questions of interfaces
vs. implementations, interface-version compatibility checking, etc.  We simply
want it to be possible for normal users to write code that is insulated
reasonably well from the system and from other users.

The presented solution owes a debt to the designers of T (in many obvious ways)
and probably those of other Scheme dialects.  As well, it is influenced by our
extensive experience programming in the Cedar language and environment, with its
heavy emphasis on well-defined interfaces.  The proposal given here is not,
however, truly the same as any other system of which we're aware; in particular,
it departs strongly from T in some fundamental ways, so draw no premature
conclusions.

The proposal begins by specifying a Scheme interface to first-class
environments, a cornerstone of the new facility.  It then describes the initial
set of environments in the system; this arrangement is in place >before< the
first file of code is LOADed.  Next, it suggests a syntax and semantics for
files of Scheme code that allows fine-grained but convenient control over the
environment structure.  Finally, it presents an example of a file using the new
facility.

The proposal proper is followed by some answers to questions that we anticipate
conerning the proposal.


FIRST-CLASS ENVIRONMENTS

We propose the addition to Scheme of first-class environment values.  These are
precisely the environments currently used by the Scheme interpreter with one
cosmetic addition, a human-readable >identifier< for the environment.  The
procedures defined on environments are as follows:

  MAKE-ENVIRONMENT <id> <parent> ...				[Procedure]

    Creates and returns a new environment with the given <parents> (if any) and
    the given identifying value, <id>, usually a string.  <Id> is strictly for
    debugging purposes; it is output as a part of the printed representation of
    the new environment.  The <parents>, on the other hand, are of semantic
    interest, since variable-lookup in the resulting environment will continue
    into the parents if the requested symbol has no binding in the child
    environment.  Variable lookup is depth-first and left-to-right among
    multiple parents.

  ENVIRONMENT? <object>						[Procedure]

    Returns true if and only if <object> is an environment.

  ENVIRONMENT-ID <env>						[Procedure]

    Return the value specified for the <id> parameter to the call to
    MAKE-ENVIRONMENT that created <env>, or #F if none was specified.

  ENVIRONMENT-PARENTS <env>					[Procedure]

    Return a list of the values specified for the <parent> parameters to the
    call to MAKE-ENVIRONMENT that created <env>.  It is an error to perform
    destructive operations on this list.

  ENVIRONMENT-REF <env> <symbol>				[Procedure]

    Return the value bound to <symbol> in <env> (or its ancestors), signalling
    an error if no such binding exists.

  ENVIRONMENT-SET! <env> <symbol> <value>			[Procedure]

    Change the value bound to <symbol> in <env> (or its ancestors) to <value>,
    signalling an error if no such binding exists.

  ENVIRONMENT-DEFINE! <env> <symbol> <value>			[Procedure]

    Change the value bound to <symbol> in <env> (NOT its ancestors) to <value>,
    adding such a binding to <env> if none exists.  Note that
    ENVIRONMENT-DEFINE! never affects any ancestor of <env>, only <env> itself.

  ENVIRONMENT-BOUND? <env> <symbol>				[Procedure]

    Return true if and only if there exists a binding for <symbol> in <env>
    (or its ancestors).

  WALK-ENVIRONMENT <fn> <env>					[Procedure]

    <Fn> should be a procedure of two arguments, a symbol and a value.  It is
    applied to every binding in <env> itself, NOT including bindings in its
    ancestors.

In addition to these procedures, We propose a change to the meanings of
identifiers whose names include colons:

  -- No identifier may begin or end with a colon.
     (Alternatively, such identifiers behave as they do now.)
  -- An identifier of the form a:b1:...:bk (k >= 1) is entirely equivalent to
     the expression
     		(ENVIRONMENT-REF a:b1:...:bk-1 'bk)

This change allows convenient reference to the values of bindings in an
environment that is bound to some variable in the current environment.  For
example, the identifier STRINGS:COPY is equivalent to the expression

		(ENVIRONMENT-REF STRINGS 'COPY)

and the identifier CEDAR:IO:RESET is equivalent to the expression

		(ENVIRONMENT-REF (ENVIRONMENT-REF CEDAR 'IO) 'RESET)


THE INITIAL ENVIRONMENT STRUCTURE

The initial structure of environments, as seen by the first file LOADed into the
system, consists of at least the following four environments:

  "SCHEME-ESSENTIALS"
  
    Contains exactly those bindings described as "essential" in the Scheme
    specification, with the semantics given there.  Thus, in this environment,
    APPEND takes exactly two arguments, LET does not allow the "named-LET"
    variant, internal DEFINEs are not allowed, etc.
    
    In addition, the name SCHEME-ESSENTIALS is bound to the environment
    itself.
    
    This environment is intended for use by those laboring under severe
    portability constraints.

  "SCHEME"
  
    Contains exactly those bindings described in the Scheme specification,
    except that a given implementation may not provide all of the optional
    features.  Thus, in this environment, APPEND may or may not accept an
    arbitrary number of arguments, LET may or may not allow the named variant,
    etc.  The strongest statement that can be made about this environment is
    that it certainly contains no more than what is described in R3RS and no
    less than the "SCHEME-ESSENTIALS" environment.
    
    In addition, the names SCHEME-ESSENTIALS and SCHEME are bound to the
    "SCHEME-ESSENTIALS" environment and this environment itself, respectively.
    
    This environment is intended for those who want to work in a reasonably
    portable setting with no extras.
  
  Some implementation-dependent name
  
    Contains whatever the implementation considers the bindings of the
    language it implements.  It should contain everything found in the
    "SCHEME" environment, though some may have been extended upward-
    compatibly.  In addition, other facilities, not described in R3RS,
    may be visible here.
    
    Some name should be bound to the environment itself.  In addition, the names
    SCHEME-ESSENTIALS and SCHEME are bound to the "SCHEME-ESSENTIALS" and
    "SCHEME" environments, respectively.
    
    It is assumed that most code written in the implementation will be
    evaluated in an environment descended from this one.
    
    In the rest of this proposal, this environment will be called the "full-
    language" environment.

  "GLOBAL"
    
    Has as its only parent the full-language environment.  In addition, the name
    GLOBAL is bound to this environment itself.
    
    The GLOBAL environment is distinguished in the definition of the semantics
    of code files, below.
    
    By convention, most files of code are evaluated in environments descended
    from this one and most other "public" environments will be accessible
    through names in the GLOBAL environment.

Implementation Note: In Cedar Scheme, for example, the initial environment
structure is created by code like the following:

       (let* ((scheme-essentials (make-environment "SCHEME-ESSENTIALS"))
              (scheme (make-environment "SCHEME" scheme-essentials))
              (cedar-scheme (make-environment "CEDAR-SCHEME" scheme))
              (global (make-environment "GLOBAL" cedar-scheme)))
   
          (environment-define! scheme-essentials
                                            'scheme-essentials
                                                          scheme-essentials)
          (environment-define! scheme       'scheme       scheme)
          (environment-define! cedar-scheme 'cedar-scheme cedar-scheme)
          (environment-define! global       'global       global)
          
          ...)

Though it is not required by this proposal, all four environments in the initial
structure in Cedar Scheme form a chain through the parent relation.  Only the
GLOBAL and full-language environments are required to be so linked.
[End note]


THE SYNTAX AND SEMANTICS OF FILES

In the usual case, a file of Scheme code contains the definitions of a few
variables (most frequently bound to procedures) intended for use by clients of
the software and several more ``helper'' variables intended only for use by the
package itself.  The variables to be externally available usually belong in a
separate space of names from those in any other package.  The following syntax
and semantics of files, which is upwardly-compatible with what is currently in
use in most dialects of Scheme, is intended to make the usual case easy while
allowing more complex cases to be handled smoothly as well.

A file of Scheme code, under this proposal, may optionally begin with a piece of
syntax, called a >herald<, that arranges for special treatment of the
environmental context of the code in the file.  Heralds obey the following
syntax:

		(HERALD <option>+)

where each <option> is one of the following:

  (ENV <expression>)
  
    The given <expression> is evaluated in the GLOBAL environment described
    above before loading the rest of the file.  <Expression> should yield an
    environment in which the rest of the file will be evaluated.  This option
    may only appear once, if at all.  It it does not appear, LOAD behaves as if
    the option
    
    		(ENV (MAKE-ENVIRONMENT <file-name> GLOBAL))
    
    had been given, where <file-name> is a string naming the file from which the
    code is being loaded.  This default is proper for most single-file packages.
    Larger applications might have an initial file that creates a new
    environment and binds it to some name in the GLOBAL environment; later files
    would specify an ENV option naming that environment.  In this way, a multi-
    file application can share a single environment among many files.

  (EXPORT <expression> <export-spec>+)
  
    An <export-spec> is either a simple identifier (one without colons) or a
    list of two simple identifiers; an <export-spec> that is a simple identifier
    <id> is exactly equivalent to the <export-spec> (<id> <id>).  The given
    <expression> is evaluated in the same environment as the rest of the file
    (see the description of the ENV herald option, above) after the rest of the
    file has been loaded.  It should yield an environment, say <env>.  For each
    <export-spec> (<id>1 <id>2), the environment <env> is side-effected such
    that the binding for <id>1 in <env> is identical to that for <id>2 in the
    environment for this file.  Two bindings are ``identical'' if a change to
    the value of one produces the same change to the value of the other.  In
    denotational terms, the two environments map the corresponding identifiers
    to the very same location.
    
    This option may appear as many times as desired.  The intent is that during
    the course of loading a file, it will define a variable, local to the file,
    bound to a fresh environment.  An EXPORT option will be used to bind this
    environment to some name, either in the USER environment or in some other
    environment accessible from the GLOBAL environment.   Further EXPORT options
    will be used to share certain of the bindings in the file with that
    now-public environment.  Naturally, those bindings that are not mentioned in
    EXPORT options will remain entirely local to the environment of the file.

Further herald options might be added in the future, in particular to aid in the
specification of a compiler's early-evaluation environment.

If no herald appears at the beginning of a file of code, the LOAD procedure will
behave as if this herald had be given:

		(HERALD
		   (ENV GLOBAL))

That is, such files are evaluated in the normal global environment, as all files
are now.


AN EXAMPLE FILE UNDER THE PROPOSAL

Here is an skeletal example of a file that might be part of a Scheme
implementation of the standard string-handling functions.  In this ficticious
Scheme implementation, the full-language environment is named "FOO-SCHEME" and
is bound to that name as well.

Since it implements a low-level structure like strings, the code in the file
uses certain "sub-primitives" from an environment bound to the name PRIVATE in
the FOO-SCHEME environment.

After the file is loaded, the various procedures defined in the
Revised^3 Report will be bound both to their normal names in the
SCHEME-ESSENTIALS and SCHEME environments and also to more concise names
in a new STRINGS environment, itself bound to the name STRINGS in the
GLOBAL environment.

Thus, a client of the string-handling procedures can either use the
names described in the Revised^3 Report (e.g., STRING-REF, STRING-SET!,
STRING-COPY) or the more ``generic'' names from the STRINGS environment
(e.g., STRINGS:REF, STRINGS:SET!, STRINGS:COPY).  The latter might fit
in well with analogous procedures from environments named LISTS,
VECTORS, TABLES, ENVIRONMENTS, etc.

       (herald
          (env (make-environment "StringsImpl" global foo-scheme:private))
          (export scheme-essentials
             (string-ref ref) (string-set! set) ...)
          (export scheme
             (string-copy copy) ...)
          (export strings
             ref copy (set! set) ...)
          (export global
             strings))
       
       (define strings (make-environment "STRINGS"))
       
       (define (ref string index)
          ...)
       
       (define (copy string)
          ...)
       
       (define (set string index value)
          ...)
       
       ...


Q&A ON THE PROPOSAL

Q: Why is the GLOBAL environment separate from the full-language environment?
   Why not just load files into the full-language environment?

A: There are two answers to this, one based upon modularity and aesthetic
   considerations and the other on future plans for the facility.
   
   The modularity argument is that the full-language environment, like the
   SCHEME or SCHEME-ESSENTIALS environments, should present an unchanging
   interface.  Applications should be able to count on the documented behavior
   of the variables in these environments and should not be affected by the
   presence or absence of other applications except where explicitly arranged
   for.
   
   The future plans argument relates to an idea for eliminating the dependence,
   found in many Lisp implementations, of the semantics of code being compiled
   on the presence or absence of other applications in the system running the 
   compiler.  For example, it is frequently the case that macros defined
   globally in the running system are available to code files compiled in that
   system.  This can (and does) lead to confusing, hidden dependencies.  Within
   this proposal, a compiler could create a new GLOBAL environment (again with
   the full-language environment as its sole parent) and use some new herald
   option as a description of what files to load into that environment to
   establish the proper "early-evaluation" environment for the compilation of
   the file.  When the compilation is done, the ersatz GLOBAL environment can be
   discarded, taking with it any side-effects that might have occurred in the
   process of compilation.  Under such a scheme, we would expect that the
   various language environments would be "locked" against redefinition of any
   of their bindings before the time that any user code is loaded, thus ensuring
   that these environments do, indeed, present an unchanging interface.

Q: In what environment should an implementation's read-eval-print loop evaluate
   the forms typed to it?

A: Certainly any such facility should provide a mechanism whereby any
   environment can be used, but our advice for the choice of an initial or
   default environment would be a "scratch" environment (as it is called in T)
   whose sole parent is the GLOBAL environment.  The use of a separate
   environment here is intended to make it easier for a user to avoid
   accidentally redefining names in the GLOBAL environment, thus possibly
   breaking running applications.  Of course, the Scheme report (properly)
   avoids mention of read-eval-print loops, so no implementation is required to
   have one at all.

Q: Why does the EXPORT herald option share actual bindings, rather than simply
   sharing values?

A: This enables the use of shared, set!-able variables.  Code wishing to take
   advantage of this would simply specify an environment containing the binding
   as an ancestor of the file environment.

Q: Why isn't there an IMPORT herald option that shares bindings in the other
   direction?  It would make the use of such shared variables more controllable
   since one would not have to share all of the variables in the given
   environment.

A: Such an option would not be antithetical to this proposal.


Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 23 May 88 16:12:55 EDT
Date: Mon, 23 May 88 16:15:16 EDT
From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Subject:  A Proposal for Environments in Scheme
To: Pavel.pa@XEROX.COM
cc: rrrs-authors@MC.LCS.MIT.EDU
In-reply-to: Msg of Fri 20 May 88 11:49:26 PDT from Pavel.pa at Xerox.COM
Message-ID: <383749.880523.JAR@AI.AI.MIT.EDU>

A dissenting opinion:

I agree that Scheme sorely needs some kind of facility for controlling
visibility of names between program components.  However, I think it
would be a mistake to add first-class environments a la T or MIT Scheme.
They are too powerful and unconstrained.  I would rather see a module
facility of the more conventional kind, based on declarative scoping
constructs of the same quality as LAMBDA and LETREC, rather than on
procedures that manipulate environments by side effect.  In particular,
one should be able to modularize one's programs without having to resort
to a side-effecty style.  (This does not imply that modules should not
be first-class.)

I would like to some way to support block compilation (like what one has
now with LETREC), and an official way to specify interfaces (which in an
untyped world are simply lists of names).

I'm working on such a facility, inspired to some extent by ML's modules,
and have had some experience with an early version of it, but it's at
too early a stage to propose here.


Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU 23 May 88 14:48:44 EDT
Received: from Semillon.ms by ArpaGateway.ms ; 23 MAY 88 11:40:10 PDT
Date: Mon, 23 May 88 11:39:41 PDT
From: Pavel.pa@Xerox.COM
Subject: Re: A Proposal for Environments in Scheme
In-reply-to: <8805231513.AA27855@mips>
To: rrrs-authors@mc.lcs.mit.edu
Message-ID: <880523-114010-4967@Xerox>

I've received four responses to the environments proposal.  Let me try to answer
the questions posed in those responses.

    From: David Bartley <bartley@mips.csc.ti.com>

    -- Suppose we had (HERALD (EXPORT ENV (FOO BAR))).  What is the effect
    if FOO already has a binding in ENV?

In our current implementation of Cedar Scheme, the effect is to lose the old
binding for FOO.  This qoesn't quite feel right, but I don't see a way around it
if exporting is really going to share bindings.  It may be that exported
SET!-able variables are frowned upon enough that sharing bindings is not
considered worthwhile; it that case, we could just set the current binding of
FOO.  This has the pleasant implication that the binding of a symbol in an
environment is constant; thus code can look up that binding exactly once at
load-time and count on seeing changes to the name-value mapping that happen
later, such as by redefinition.

    What is the effect if BAR is
    bound in an ancestor of the current (file's) environment but not
    directly in the current environment?

There is no difference between this cad the usual case; the binding is shared.

    -- What is the effect of (HERALD (EXPORT ENV (A B) (C B)))?  Is this
    an error or are all three identifiers bound to the same location?

All three identifiers are bound to the same location.

    -- In your Q&A section, you mention "locking" of environments to
    protect them against change.  This is an intriguing idea.  Would this
    be done at the environment level or a binding at a time?

My intent was that the locking would happen at the environment level.  That is,
all bindings in the environment would be rendered un-SET!-able and no new
bindings would be allowed.

    Can one
    export a binding from an unlocked environment into a locked
    environment?

Since this would involve the addition of a new binding to the locked
environment, the answer is no.

    Likewise, what
    happens if you export a binding from a locked environment into an
    unlocked one?

Hmm.  I suppose that this would imply that that binding was un-SET!-able,
regardless of what environment you found it in.  This seems to imply that
locking is happening both at the environment level and at the level of the
individual bindings.

    -- The EXPORT mechanism doesn't require any hierarchical or other
    relationship between the specified environment and the
    current environment, so it is possible to inject a shared binding into
    any environment you can get your hands on.  Such a binding could be a
    trojan horse.  Perhaps it should be possible to "lock" an environment
    against being exported into (?!) as well?

This is precisely the question you asked earlier about exporting from an
unlocked environment into a locked one.

    -- Have you found it to be important to have the `:' notation as a
    short-hand for ENVIRONMENT-REF ?  My previous proposals to reserve the
    `:' character for CL-style package notation have been soundly drubbed.

We like to think about environments like STRINGS in the example as
``interfaces'' in the sense of languages like Cedar (surprise...) and Modula-2.
Thus, in general, we believe that programs will not have environments that
inherit from environments like STRINGS but will explicitly ``qualify'' all
references to names in such environments.  We have found that when systems like
this get going and there are a large number of environments/interfaces around,
inheriting from an interface environment (it's called OPENing the interface in
Cedar) is very confusing in general.  There are cases where it makes sense to
OPEN exactly one interface (for example, all of the Cedar code implementing the
Scheme interpreter and primitives OPENs the Scheme interface, which provides the
type declarations and useful procedures like LookupVariableValue), but the vast
majority of references to names in other environments are fully-qualified.  If
one had to use an explicit call to ENVIRONMENT-REF (or even ACCESS in C-Scheme,
which is shorter), then the typing/reading penalty for separating environments
would likely outweigh the modularity benefits.  Thus, we feel quite strongly
that some low-overhead notation for ``structured names'' is necessary.

    Just for grins, how would you react to a notation using curly braces, so
    your A:B1:B2 becomes {{A}B1}B2, and STRINGS:SET! becomes {STRINGS}SET! ?

Hmm.  Well, it's not entirely grotesque, but I think that the colons work
better.  Cedar uses periods where we use colons, but I think too many people use
periods to separate words in identifiers for this to go over well.  Besides, the
colons here have a purpose not entirely unlike colons in Common Lisp, though
they have much cleaner semantics here.

    From: Morris Katz <MKATZ@A.ISI.EDU>

    1)  I believe it is a big mistake to require that all environments have a
name.
    There was a good reason(s) for deciding that not all procedures in Lisp
should
    have to be named, and I believe that those arguments apply equally well to
this
    case.

I think that you misunderstood the purpose of the <id> argument to
MAKE-ENVIRONMENT.  It is not a name in the sense that a given name maps to a
single environment.  Its only purpose is to be some nice thing to show as a part
of the printed representation of the environment.  It also helps humans have a
more reasonable handle for talking about environments.  The <id> has absolutely
no semantic content except that it can be extracted from the environment with
the procedure ENVIRONMENT-ID.  There are no guarantees that <id>'s are unique
and no functions for mapping an <id> into the environments having it.

    2)  I have been interested in the semantics and use of multiple environment
    inheritance for some time; but, I am not sure that it is well enough
understood
    to become part of R3RS.  (Maybe someone else understands it better than I do
    and can convince me otherwise.)  In particular, I am concerned about
efficient 
    implementations for interpreted code, difficulty in understanding code which
    utilizes this feature, and the development of suitable browser technology to
    make debugging of programs using it tractable.

It is easy to implement multiple parents efficiently in the interpreter.  In
Cedar Scheme, environments have two field for parent information; one of the
fields holds the first parent and the other holds a list of the other parents.
In almost all cases, single inheritance is used and the otherParents field is
NIL.  Thus, no consing of environment lists occurs in the interpreter.  The
variable lookup procedure is straightforward and, in the case where otherParents
is NIL, is precisely the same as the single inheritance case.

As I pointed out above, extensive use of multiple parents can indeed make code
hard to read.  On the other hand, judicious and controlled use works quite well
to improve readability.  The best use is to include certain optional language
features that are kept in separate environments for just this purpose.  For
example, in Cedar Scheme, there is an environment called ITERATE that provides
the entry points for a fancy iteration facility.  Not everyone likes the
facility, so it is not a part of the full language we export.  However, programs
wishing to use the facility can include ITERATE as a parent of their
environments and thus get seamless access to it.

I have not found fancy browser technology necessary for debugging such code.
The fact that environments print with a useful name (like the name of the file
for most code) and the fact that our debugger prints out the environment of the
current expression has made it very reasonable to work with these environments.

    3)  It is my belief that the loader should load the contents of files into
the 
    environment of the REP LOOP from which the load was initiated, unless 
    specified otherwise in the load command.  (e.g., (load "foo" bar) would load
    the file "foo" into the environment bar.)  Making all files load into the 
    global environment unless specified otherwise in a herald seems artificial
and
    constraining.  What if one wants to load two slightly different copies of a
    system into two sets of environments and compare their execution?  Using the
    herald approach I believe this would require copying all of the files and 
    changing the heralds.  The logical extension of thiproach would be that 
    <expression> in (env <expresssion>) in a herald be evaluated in the load
    environment, rather than the global environment.

Please note that, under our proposal, any file containing a herald is loaded
into a *fresh* environment inheriting from the GLOBAL environment.  Thus,
programs in different files are protected from each other.  I have no objection
to an optional argument to LOAD that provided it with a different idea of what
the GLOBAL environment was.  This would allow you to load the same program into
multiple environments for the effect you ask for above.

We're trying, in this proposal, to make it possible for large numbers of
applications to coexist with some reasonable assurances about namespace
protection.  We envision systems the size of Cedar or the Symbolics Genera
system with many hundreds of software packages all loaded into the same address
space and working together well because of separate namespaces and well-defined
interfaces.  This level of modularity is new to Scheme and the other Lisp-like
languages but is now commonplace in systems like Cedar and Modula-2+.  The
proposal lets this happen while still allowing smaller systems the very same
flexibilities currently allowed in most implementations.

    4) I can't quite explain why, but the entire export section makes me feel a 
    little uneasy.  While there are some things that can be done convieniently 
    through the unification of two symbols in different environments, I get the 
    feeling that this feature can very quckly get one into trouble.  How do we
    build debuggers to help support its use?

In Cedar Scheme, the binding object contains more information that the value of
the binding.  It also contains the original name for the binding in the
environment in which it was created.  If we wished, we could also store that
original environment in there and any other information that one might care to
have around for debugging.  I don't see that this proposal makes debugging any
more difficult.

    What are the costs added to normal lexical lookup due to this feature?

The only cost is that ``top-level'' environments (the kind made by
MAKE-ENVIRONMENT) must use an extra level of indirection to get to the value for
a name.  Local environments, used by the interpreter for normal lambda-binding,
need not do this, since they can never be accessed by a program and can thus
never be named in an export clause.

    Does it interact pathologically with incremental definition, or is this
    just an erroneous gut level feeling?

As I described in answer to David's questions above, there is a funny
interaction here with REdefinition, but not with simple incremental definition.

    From: Andy Freeman <andy@polya.stanford.edu>
    
    In the herald, env is bad for the same reasons that exp would be.

Granted.  I would not object to the use of ``environment'' instead of ``env''.

    Regarding the presentation, it would be nice you mentioned using (or
    not, as appropriate) the scheme-essentials environment to implement
    the scheme and <implementation> environment.  At first reading, it
    looks like these environments have to have bindings for all of the
    language even if they could inherit it from scheme-essentials but your
    example makes it clear that they can use inheritance.

I wanted the semantics of the environments to be clear.  In particular, I did
not want to make it seem as if the various environments were required to inherit
in the obvious fashion.  The only required inheritance link is between the
GLOBAL and full-language environments.

    I understand why you didn't write much about the default environment
    in various situations, but someone should.

I'm not sure I understand what you mean here.  I think that I described all of
the environments in which evaluation takes place in R3RS Scheme.

    I know that it can be written, but it would be nice if one of the
    optional functions told which environment a symbol was bound in.  <I
    forget>-bound? tells you whether a symbol is bound in an environment
    or one of its ancestors, but knowing which one would be nice.  Argh,
    it might even be worth knowing all of the environments that a symbol
    is bound in.

I took the view of the rest of R3RS Scheme, that those things a user could write
for themself need not be included in the language.

    Should there be an environment analog of call-with-current-continuation?

I've not yet seen a good use for this.

    BTW - Why did you chose to use strings for identifying environments
    instead of say, symbols?

Let me point out that the <id> value can be any Scheme value at all, since it
has no semantics.  I chose strings instead of symbols in order to reduce
confusion of <id>'s with the names to which environments are bound in certain
other environments.  Thus the difference between the "SCHEME" environment and
the value bound to the symbol 'scheme in that environment.

    From: John D. Ramsdell <ramsdell%linus@mitre-bedford.ARPA>
    
    What exactly is an identifier?  Is it a symbol whose print name does
    not end or begin with a colon?  If so, the print name determines the
    interpretation of an identifier.  This mixes up the concept of how to
    print a symbol with the concept of how to use it as an identifier.

    Maybe colon is a read time macro, and no symbol is allowed to contain
    colon.  

    [1] a:b  ==>  (eval (ENVIRONMENT-REF B (QUOTE A)))

    [2] 'a:b  ==>  (ENVIRONMENT-REF B (QUOTE A))

    [3] (string->symbol "A:B")  ==>  ?

    By your description [1] is true, what about [2]?  What is [3]?

An identifier is a token precisely as described in R3RS.  Its internal
representation is less clear.  In the same way that R3RS waffles about what
happens when I type

		''foo

to my read-eval-print loop, I guess I'd better waffle about colon here.  I can
tell you that in Cedar Scheme, when the reader finds an identifer by R3RS
syntax, it looks for colons in the name and, if found, constructs an
ENVIRONMENT-REF expression to return.  Thus, in a sense, colons are treated as a
read macro in Cedar Scheme.

By the way, in your choices above, you've got the arguments to ENVIRONMENT-REF
backwards.  In both cases, the expression should be

		(ENVIRONMENT-REF A (QUOTE B))

This is all of the responses I've received so far.  Further comment?

	Pavel

Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU 23 May 88 13:47:44 EDT
Received: from Semillon.ms by ArpaGateway.ms ; 23 MAY 88 10:38:45 PDT
Date: Mon, 23 May 88 10:38:32 PDT
From: Pavel.pa@Xerox.COM
Subject: Re: A Proposal for Environments in Scheme
To: RRRS-Authors@MC.LCS.MIT.Edu
Message-ID: <880523-103845-4763@Xerox>

Forwarded by request.

Morris Katz  23 May 88 Re: A Proposal for Environments i ...
Return-Path: <MKATZ@A.ISI.EDU>
Received: from A.ISI.EDU by Xerox.COM ; 23 MAY 88 10:18:55 PDT
Date: Mon, 23 May 88 13:15:01 EDT
From: Morris Katz <MKATZ@A.ISI.EDU>
Subject: Re: A Proposal for Environments in Scheme
To: Pavel.pa
In-Reply-To: <880520-115000-2371@Xerox>
Message-ID: <12400648194.42.MKATZ@A.ISI.EDU>

I have a number of concerns about the environment proposal which I will
try to express as suscinctly as possible.  I will begin with the simple, 
syntactic ones and progress from there.

1)  I believe it is a big mistake to require that all environments have a name.
There was a good reason(s) for deciding that not all procedures in Lisp should
have to be named, and I believe that those arguments apply equally well to this
case.  Either there should be two forms (make-environment <parents>) and 
(make-named-environment <id> <parents>) or the order of the arguments should be
reversed and <id> should be made optional in dialects that support optional
arguemnts.  In the latter case, <parents> would either be an environment or a
list of environments.  

2)  I have been interested in the semantics and use of multiple environment
inheritance for some time; but, I am not sure that it is well enough understood
to become part of R3RS.  (Maybe someone else understands it better than I do 
and can convince me otherwise.)  In particular, I am concerned about efficient 
implementations for interpreted code, difficulty in understanding code which 
utilizes this feature, and the development of suitable browser technology to 
make debugging of programs using it tractable.

3)  It is my belief that the loader should load the contents of files into the 
environment of the REP LOOP from which the load was initiated, unless 
specified otherwise in the load command.  (e.g., (load "foo" bar) would load
the file "foo" into the environment bar.)  Making all files load into the 
global environment unless specified otherwise in a herald seems artificial and
constraining.  What if one wants to load two slightly different copies of a
system into two sets of environments and compare their execution?  Using the 
herald approach I believe this would require copying all of the files and 
changing the heralds.  The logical extension of thiproach would be that 
<expression> in (env <expresssion>) in a herald be evaluated in the load
environment, rather than the global environment.

4) I can't quite explain why, but the entire export section makes me feel a 
little uneasy.  While there are some things that can be done convieniently 
through the unification of two symbols in different environments, I get the 
feeling that this feature can very quckly get one into trouble.  How do we
build debuggers to help support its use?  What are the costs added to normal 
lexical lookup due to this feature?  Does it interact pathologically with 
incremental definition, or is this just an erroneous gut level feeling?  Maybe
those who are more familiar witsimilar features in CommonLisp can answer some 
of these questions.

					Morry Katz
-------



Received: from ti.com (TCP 1201600056) by MC.LCS.MIT.EDU 23 May 88 11:18:06 EDT
Received: by ti.com id AA27140; Mon, 23 May 88 10:14:39 CDT
Received: from mips by tilde id AA00645; Mon, 23 May 88 10:13:49 CDT
Received: by mips id AA27855; Mon, 23 May 88 10:13:45 CDT
Date: Mon, 23 May 88 10:13:45 CDT
From: David Bartley <bartley@mips.csc.ti.com>
Message-Id: <8805231513.AA27855@mips>
To: Pavel.pa@XEROX.COM
Cc: rrrs-authors@mc.lcs.mit.edu
In-Reply-To: Pavel.pa@XEROX.COM's message of Fri, 20 May 88 11:49:26 PDT <880520-115000-2371@Xerox>
Subject: A Proposal for Environments in Scheme

Thanks for your proposal; I imagine it will stimulate some discussion
on the topic.  Could you please clarify the following?

-- Suppose we had (HERALD (EXPORT ENV (FOO BAR))).  What is the effect
if FOO already has a binding in ENV?  What is the effect if BAR is
bound in an ancestor of the current (file's) environment but not
directly in the current environment?

-- What is the effect of (HERALD (EXPORT ENV (A B) (C B)))?  Is this
an error or are all three identifiers bound to the same location?

-- In your Q&A section, you mention "locking" of environments to
protect them against change.  This is an intriguing idea.  Would this
be done at the environment level or a binding at a time?  Can one
export a binding from an unlocked environment into a locked
environment?  If so, does the binding become locked?  If so, are uses
of both identifiers having that binding locked?  Likewise, what
happens if you export a binding from a locked environment into an
unlocked one?

-- The EXPORT mechanism doesn't require any hierarchical or other
structural relationship between the specified environment and the
current environment, so it is possible to inject a shared binding into
any environment you can get your hands on.  Such a binding could be a
trojan horse.  Perhaps it should be possible to "lock" an environment
against being exported into (?!) as well?

-- Have you found it to be important to have the `:' notation as a
short-hand for ENVIRONMENT-REF ?  My previous proposals to reserve the
`:' character for CL-style package notation have been soundly drubbed.

Just for grins, how would you react to a notation using curly braces, so
your A:B1:B2 becomes {{A}B1}B2, and STRINGS:SET! becomes {STRINGS}SET!.

Regards,
David Bartley

Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU 20 May 88 15:02:45 EDT
Received: from Cabernet.ms by ArpaGateway.ms ; 20 MAY 88 11:50:00 PDT
Date: Fri, 20 May 88 11:49:26 PDT
From: Pavel.pa@Xerox.COM
Subject: A Proposal for Environments in Scheme
To: rrrs-authors@mc.lcs.mit.edu
Message-ID: <880520-115000-2371@Xerox>

I'd like to offer the following proposal for a facility for first-class
environments in Scheme.  We have found it to work quite cleanly and powerfully
in Cedar Scheme and thus believe that it is worthy of consideration for
inclusion in the standard language.

	Pavel Curtis
	Xerox PARC/CSL

INTRODUCTION

If Scheme is to grow and be used by more people, one of the problems it must
solve is the robust isolation of different pieces of the system and user code
from each other.  The system described in this section is an attempt to cleanly
and simply solve this problem, with an eye toward making the addition of a true
file-compiler a simple extension with clean semantics.  It is fully implemented
in Cedar Scheme.

Note that this system does not attempt to address the questions of interfaces
vs. implementations, interface-version compatibility checking, etc.  We simply
want it to be possible for normal users to write code that is insulated
reasonably well from the system and from other users.

The presented solution owes a debt to the designers of T (in many obvious ways)
and probably those of other Scheme dialects.  As well, it is influenced by our
extensive experience programming in the Cedar language and environment, with its
heavy emphasis on well-defined interfaces.  The proposal given here is not,
however, truly the same as any other system of which we're aware; in particular,
it departs strongly from T in some fundamental ways, so draw no premature
conclusions.

The proposal begins by specifying a Scheme interface to first-class
environments, a cornerstone of the new facility.  It then describes the initial
set of environments in the system; this arrangement is in place >before< the
first file of code is LOADed.  Next, it suggests a syntax and semantics for
files of Scheme code that allows fine-grained but convenient control over the
environment structure.  Finally, it presents an example of a file using the new
facility.

The proposal proper is followed by some answers to questions that we anticipate
conerning the proposal.


FIRST-CLASS ENVIRONMENTS

We propose the addition to Scheme of first-class environment values.  These are
precisely the environments currently used by the Scheme interpreter with one
cosmetic addition, a human-readable >identifier< for the environment.  The
procedures defined on environments are as follows:

  MAKE-ENVIRONMENT <id> <parent> ...				[Procedure]

    Creates and returns a new environment with the given <parents> (if any) and
    the given identifying value, <id>, usually a string.  <Id> is strictly for
    debugging purposes; it is output as a part of the printed representation of
    the new environment.  The <parents>, on the other hand, are of semantic
    interest, since variable-lookup in the resulting environment will continue
    into the parents if the requested symbol has no binding in the child
    environment.  Variable lookup is depth-first and left-to-right among
    multiple parents.

  ENVIRONMENT? <object>						[Procedure]

    Returns true if and only if <object> is an environment.

  ENVIRONMENT-ID <env>						[Procedure]

    Return the value specified for the <id> parameter to the call to
    MAKE-ENVIRONMENT that created <env>, or #F if none was specified.

  ENVIRONMENT-PARENTS <env>					[Procedure]

    Return a list of the values specified for the <parent> parameters to the
    call to MAKE-ENVIRONMENT that created <env>.  It is an error to perform
    destructive operations on this list.

  ENVIRONMENT-REF <env> <symbol>				[Procedure]

    Return the value bound to <symbol> in <env> (or its ancestors), signalling
    an error if no such binding exists.

  ENVIRONMENT-SET! <env> <symbol> <value>			[Procedure]

    Change the value bound to <symbol> in <env> (or its ancestors) to <value>,
    signalling an error if no such binding exists.

  ENVIRONMENT-DEFINE! <env> <symbol> <value>			[Procedure]

    Change the value bound to <symbol> in <env> (NOT its ancestors) to <value>,
    adding such a binding to <env> if none exists.  Note that
    ENVIRONMENT-DEFINE! never affects any ancestor of <env>, only <env> itself.

  ENVIRONMENT-BOUND? <env> <symbol>				[Procedure]

    Return true if and only if there exists a binding for <symbol> in <env>
    (or its ancestors).

  WALK-ENVIRONMENT <fn> <env>					[Procedure]

    <Fn> should be a procedure of two arguments, a symbol and a value.  It is
    applied to every binding in <env> itself, NOT including bindings in its
    ancestors.

In addition to these procedures, We propose a change to the meanings of
identifiers whose names include colons:

  -- No identifier may begin or end with a colon.
     (Alternatively, such identifiers behave as they do now.)
  -- An identifier of the form a:b1:...:bk (k >= 1) is entirely equivalent to
     the expression
     		(ENVIRONMENT-REF a:b1:...:bk-1 'bk)

This change allows convenient reference to the values of bindings in an
environment that is bound to some variable in the current environment.  For
example, the identifier STRINGS:COPY is equivalent to the expression

		(ENVIRONMENT-REF STRINGS 'COPY)

and the identifier CEDAR:IO:RESET is equivalent to the expression

		(ENVIRONMENT-REF (ENVIRONMENT-REF CEDAR 'IO) 'RESET)


THE INITIAL ENVIRONMENT STRUCTURE

The initial structure of environments, as seen by the first file LOADed into the
system, consists of at least the following four environments:

  "SCHEME-ESSENTIALS"
  
    Contains exactly those bindings described as "essential" in the Scheme
    specification, with the semantics given there.  Thus, in this environment,
    APPEND takes exactly two arguments, LET does not allow the "named-LET"
    variant, internal DEFINEs are not allowed, etc.
    
    In addition, the name SCHEME-ESSENTIALS is bound to the environment
    itself.
    
    This environment is intended for use by those laboring under severe
    portability constraints.

  "SCHEME"
  
    Contains exactly those bindings described in the Scheme specification,
    except that a given implementation may not provide all of the optional
    features.  Thus, in this environment, APPEND may or may not accept an
    arbitrary number of arguments, LET may or may not allow the named variant,
    etc.  The strongest statement that can be made about this environment is
    that it certainly contains no more than what is described in R3RS and no
    less than the "SCHEME-ESSENTIALS" environment.
    
    In addition, the names SCHEME-ESSENTIALS and SCHEME are bound to the
    "SCHEME-ESSENTIALS" environment and this environment itself, respectively.
    
    This environment is intended for those who want to work in a reasonably
    portable setting with no extras.
  
  Some implementation-dependent name
  
    Contains whatever the implementation considers the bindings of the
    language it implements.  It should contain everything found in the
    "SCHEME" environment, though some may have been extended upward-
    compatibly.  In addition, other facilities, not described in R3RS,
    may be visible here.
    
    Some name should be bound to the environment itself.  In addition, the names
    SCHEME-ESSENTIALS and SCHEME are bound to the "SCHEME-ESSENTIALS" and
    "SCHEME" environments, respectively.
    
    It is assumed that most code written in the implementation will be
    evaluated in an environment descended from this one.
    
    In the rest of this proposal, this environment will be called the "full-
    language" environment.

  "GLOBAL"
    
    Has as its only parent the full-language environment.  In addition, the name
    GLOBAL is bound to this environment itself.
    
    The GLOBAL environment is distinguished in the definition of the semantics
    of code files, below.
    
    By convention, most files of code are evaluated in environments descended
    from this one and most other "public" environments will be accessible
    through names in the GLOBAL environment.

Implementation Note: In Cedar Scheme, for example, the initial environment
structure is created by code like the following:

       (let* ((scheme-essentials (make-environment "SCHEME-ESSENTIALS"))
              (scheme (make-environment "SCHEME" scheme-essentials))
              (cedar-scheme (make-environment "CEDAR-SCHEME" scheme))
              (global (make-environment "GLOBAL" cedar-scheme)))
   
          (environment-define! scheme-essentials
                                            'scheme-essentials
                                                          scheme-essentials)
          (environment-define! scheme       'scheme       scheme)
          (environment-define! cedar-scheme 'cedar-scheme cedar-scheme)
          (environment-define! global       'global       global)
          
          ...)

Though it is not required by this proposal, all four environments in the initial
structure in Cedar Scheme form a chain through the parent relation.  Only the
GLOBAL and full-language environments are required to be so linked.
[End note]


THE SYNTAX AND SEMANTICS OF FILES

In the usual case, a file of Scheme code contains the definitions of a few
variables (most frequently bound to procedures) intended for use by clients of
the software and several more ``helper'' variables intended only for use by the
package itself.  The variables to be externally available usually belong in a
separate space of names from those in any other package.  The following syntax
and semantics of files, which is upwardly-compatible with what is currently in
use in most dialects of Scheme, is intended to make the usual case easy while
allowing more complex cases to be handled smoothly as well.

A file of Scheme code, under this proposal, may optionally begin with a piece of
syntax, called a >herald<, that arranges for special treatment of the
environmental context of the code in the file.  Heralds obey the following
syntax:

		(HERALD <option>+)

where each <option> is one of the following:

  (ENV <expression>)
  
    The given <expression> is evaluated in the GLOBAL environment described
    above before loading the rest of the file.  <Expression> should yield an
    environment in which the rest of the file will be evaluated.  This option
    may only appear once, if at all.  It it does not appear, LOAD behaves as if
    the option
    
    		(ENV (MAKE-ENVIRONMENT <file-name> GLOBAL))
    
    had been given, where <file-name> is a string naming the file from which the
    code is being loaded.  This default is proper for most single-file packages.
    Larger applications might have an initial file that creates a new
    environment and binds it to some name in the GLOBAL environment; later files
    would specify an ENV option naming that environment.  In this way, a multi-
    file application can share a single environment among many files.

  (EXPORT <expression> <export-spec>+)
  
    An <export-spec> is either a simple identifier (one without colons) or a
    list of two simple identifiers; an <export-spec> that is a simple identifier
    <id> is exactly equivalent to the <export-spec> (<id> <id>).  The given
    <expression> is evaluated in the same environment as the rest of the file
    (see the description of the ENV herald option, above) after the rest of the
    file has been loaded.  It should yield an environment, say <env>.  For each
    <export-spec> (<id>1 <id>2), the environment <env> is side-effected such
    that the binding for <id>1 in <env> is identical to that for <id>2 in the
    environment for this file.  Two bindings are ``identical'' if a change to
    the value of one produces the same change to the value of the other.  In
    denotational terms, the two environments map the corresponding identifiers
    to the very same location.
    
    This option may appear as many times as desired.  The intent is that during
    the course of loading a file, it will define a variable, local to the file,
    bound to a fresh environment.  An EXPORT option will be used to bind this
    environment to some name, either in the USER environment or in some other
    environment accessible from the GLOBAL environment.   Further EXPORT options
    will be used to share certain of the bindings in the file with that
    now-public environment.  Naturally, those bindings that are not mentioned in
    EXPORT options will remain entirely local to the environment of the file.

Further herald options might be added in the future, in particular to aid in the
specification of a compiler's early-evaluation environment.

If no herald appears at the beginning of a file of code, the LOAD procedure will
behave as if this herald had be given:

		(HERALD
		   (ENV GLOBAL))

That is, such files are evaluated in the normal global environment, as all files
are now.


AN EXAMPLE FILE UNDER THE PROPOSAL

Here is an skeletal example of a file that might be part of a Scheme
implementation of the standard string-handling functions.  In this ficticious
Scheme implementation, the full-language environment is named "FOO-SCHEME" and
is bound to that name as well.

Since it implements a low-level structure like strings, the code in the file
uses certain "sub-primitives" from an environment bound to the name PRIVATE in
the FOO-SCHEME environment.

After the file is loaded, the various procedures defined in the Revised^3 Report
will be bound both to their normal names in the SCHEME-ESSENTIALS and SCHEME
environments and also to more concise names in a new STRINGS environment, itself
bound to the name STRINGS in the GLOBAL environment.

Thus, a client of the string-handling procedures can either use the names
described in the Revised^3 Report (e.g., STRING-REF, STRING-SET!, STRING-COPY)
or the more ``generic'' names from the STRINGS environment (e.g., STRINGS:REF,
STRINGS:SET!, STRINGS:COPY).  The latter might fit in well with analogous
procedures from environments named LISTS, VECTORS, TABLES, ENVIRONMENTS, etc.

       (herald
          (env (make-environment "StringsImpl" global foo-scheme:private))
          (export scheme-essentials
             (string-ref ref) (string-set! set) ...)
          (export scheme
             (string-copy copy) ...)
          (export strings
             ref copy (set! set) ...)
          (export global
             strings))
       
       (define strings (make-environment "STRINGS"))
       
       (define (ref string index)
          ...)
       
       (define (copy string)
          ...)
       
       (define (set string index value)
          ...)
       
       ...


Q&A ON THE PROPOSAL

Q: Why is the GLOBAL environment separate from the full-language environment?
   Why not just load files into the full-language environment?

A: There are two answers to this, one based upon modularity and aesthetic
   considerations and the other on future plans for the facility.
   
   The modularity argument is that the full-language environment, like the
   SCHEME or SCHEME-ESSENTIALS environments, should present an unchanging
   interface.  Applications should be able to count on the documented behavior
   of the variables in these environments and should not be affected by the
   presence or absence of other applications except where explicitly arranged
   for.
   
   The future plans argument relates to an idea for eliminating the dependence,
   found in many Lisp implementations, of the semantics of code being compiled
   on the presence or absence of other applications in the system running the 
   compiler.  For example, it is frequently the case that macros defined
   globally in the running system are available to code files compiled in that
   system.  This can (and does) lead to confusing, hidden dependencies.  Within
   this proposal, a compiler could create a new GLOBAL environment (again with
   the full-language environment as its sole parent) and use some new herald
   option as a description of what files to load into that environment to
   establish the proper "early-evaluation" environment for the compilation of
   the file.  When the compilation is done, the ersatz GLOBAL environment can be
   discarded, taking with it any side-effects that might have occurred in the
   process of compilation.  Under such a scheme, we would expect that the
   various language environments would be "locked" against redefinition of any
   of their bindings before the time that any user code is loaded, thus ensuring
   that these environments do, indeed, present an unchanging interface.

Q: In what environment should an implementation's read-eval-print loop evaluate
   the forms typed to it?

A: Certainly any such facility should provide a mechanism whereby any
   environment can be used, but our advice for the choice of an initial or
   default environment would be a "scratch" environment (as it is called in T)
   whose sole parent is the GLOBAL environment.  The use of a separate
   environment here is intended to make it easier for a user to avoid
   accidentally redefining names in the GLOBAL environment, thus possibly
   breaking running applications.  Of course, the Scheme report (properly)
   avoids mention of read-eval-print loops, so no implementation is required to
   have one at all.

Q: Why does the EXPORT herald option share actual bindings, rather than simply
   sharing values?

A: This enables the use of shared, set!-able variables.  Code wishing to take
   advantage of this would simply specify an environment containing the binding
   as an ancestor of the file environment.

Q: Why isn't there an IMPORT herald option that shares bindings in the other
   direction?  It would make the use of such shared variables more controllable
   since one would not have to share all of the variables in the given
   environment.

A: Such an option would not be antithetical to this proposal.



Received: from iuvax.cs.indiana.edu (TCP 30003147300) by MC.LCS.MIT.EDU 17 May 88 18:06:51 EDT
Received: by iuvax.cs.indiana.edu; id AA00423; Tue, 17 May 88 17:04:27 EST
Received: by iuvax.cs.indiana.edu (5.54/1.5) 
Date: Tue, 17 May 88 17:04:27 EST
From: Chris Haynes <chaynes@iuvax.cs.indiana.edu>
To: scheme@mc.lcs.mit.edu, rrrs-authors@mc.lcs.mit.edu
Subject: Scheme standardization meeting

The proposal to form an IEEE Working Group on Scheme (let's call it
the "working group" from now on) mentioned in my last note has been
approved by the Microprocessor Standards Committee (MSC).  There are a
few more administrative steps before it is completely official, but no
difficulty is expected.  The standardization process has begun; wish
us luck!

The first meeting of the working group will be on Wednesday, July
27th, 1988, from 1:00 pm to 5:00 pm (or later if really necessary)
following the Lisp and Functional Programming Conference at Snowbird,
Utah.  The meeting room will be posted at the conference facility.

The agenda for the first working group meeting should at least include
discussion of the following items:

   - introductions and brief remarks about the standards process
   - scope and purpose of standardization effort
   - expected time schedule for standard development
   - time and place of next meeting
   - netmail and other means of communicating between meetings
   - proposed ways for the standard to differ from the Revised^3 Report.

The last point is clearly the most important and should take most of
the time.  Specific proposals should be stated in advance and included
in the agenda if possible.

Very briefly, my current expectation (reflecting the wishes of the
study group mentioned in my last note) is that the working group will
serve to "filter" the work of the Revised^n Report authors, removing
features deemed too experimental for standardization and adding nothing
of substance to the language.  The following meeting will be in about
six months, at a place as yet unknown.  A "trial standard" should be 
completed in about two years, with a full standard perhaps two years
after that.

Let's use the general Scheme news group (now comp.lang.scheme) for
discussion of the agenda and related matters prior to the meeting.
At the meeting we may agree to form another news group for subsequent
communication.

Your suggestions on agenda items and candidates for filtering are
welcome.

-- Chris Haynes

Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 13 May 88 18:58:05 EDT
Date: Fri, 13 May 88 15:25:40 EDT
From: Jonathan A Rees <JAR@AI.AI.MIT.EDU>
Subject:  Change proposals
To: rrrs-authors@MC.LCS.MIT.EDU
Message-ID: <377357.880513.JAR@AI.AI.MIT.EDU>

    Date: 10 May 88 12:06:02 PDT (Tue)
    From: willc%tekchips.CRL%tektronix.tek.com@RELAY.CS.NET

    Detailed proposals for changes to the R3RS should be submitted to me
    by 15 June.  This should allow the agenda committee (Jonathan Rees and
    myself?) to collate and edit the proposals in time to distribute them
    two weeks before the meeting.  Participants should study these proposals
    before coming to Snowbird.

Please send your proposals to me, not to Will.  Proposals should be
submitted in LaTeX format, if possible, using the macros that are
already used in the report sources.  There is no documentation for these
macros, and some are very poorly designed, for which I make no
apologies.  (Improved versions are welcome.)  I'll mail partial or
complete R^3.5 Report sources to anyone who wants them (e.g. to learn
how to use the macros or to modify existing text), and I'll also make
them available by FTP shortly.

If you don't have a LaTeX with which to debug your source, then
just do the best you can and I'll cope with it.


Received: from iuvax.cs.indiana.edu (TCP 30003147300) by MC.LCS.MIT.EDU 13 May 88 06:35:13 EDT
Received: by iuvax.cs.indiana.edu; id AA20624; Thu, 12 May 88 23:03:28 EST
Received: by iuvax.cs.indiana.edu (5.54/1.5) 
Date: Thu, 12 May 88 23:03:28 EST
From: Dan Friedman <dfried@iuvax.cs.indiana.edu>
To: rrrs-authors@mc.lcs.mit.edu
Subject: Snowbird

I will be at the Sunday and Wednesday afternoon meetings.
Dan

Received: from RELAY.CS.NET (TCP 1201000005) by MC.LCS.MIT.EDU 12 May 88 10:18:46 EDT
Received: from [129.10.1.2] by RELAY.CS.NET id aa11146; 12 May 88 10:12 EDT
Received: from corwin.ccs.northeastern.edu by helios.northeastern.edu
          id aa04383; 12 May 88 10:11 EDT
Received: by corwin.CCS.Northeastern.EDU (5.51/SMI-3.2+CCS-main-2.4)
	id AA03810; Thu, 12 May 88 10:10:22 EDT
Date: Thu, 12 May 88 10:10:22 EDT
From: Mitchell Wand <wand%corwin.ccs.northeastern.edu@RELAY.CS.NET>
Message-Id: <8805121410.AA03810@corwin.CCS.Northeastern.EDU>
To: willc%tekchips.CRL%tektronix.tek.com@RELAY.CS.NET
Cc: rrrs-authors@mc.lcs.mit.edu, willc%tekchips.crl.tek.com@RELAY.CS.NET
In-Reply-To: willc%tekchips.CRL%tektronix.tek.com@relay.cs.net's message of 10 May 88 12:06:02 PDT (Tue) <8805101906.AA24380@tekchips.CRL.TEK.COM>
Subject: Meeting 24 July 1988

Yes, I am planning to come to the Sunday R*RS meeting.  (Also the IEEE
meeting).

--Mitch

Mitchell Wand
College of Computer Science
Northeastern University
360 Huntington Avenue #161CN
Boston, MA 02115

CSNet:  wand@corwin.ccs.northeastern.edu


Received: from RELAY.CS.NET (TCP 1201000005) by MC.LCS.MIT.EDU 11 May 88 20:26:11 EDT
Received: from relay2.cs.net by RELAY.CS.NET id ag02468; 11 May 88 14:53 EDT
Received: from tektronix.tek.com by RELAY.CS.NET id ew09393; 11 May 88 14:38 EDT
Received: by tektronix.TEK.COM (5.51/6.24)
	id AA14832; Tue, 10 May 88 12:05:29 PDT
Received: by tekchips.CRL.TEK.COM (5.51/6.24)
	id AA24380; Tue, 10 May 88 12:06:05 PDT
Message-Id: <8805101906.AA24380@tekchips.CRL.TEK.COM>
To: rrrs-authors@mc.lcs.mit.edu
Cc: willc%tekchips.crl.tek.com@RELAY.CS.NET
Subject: Meeting 24 July 1988
Date: 10 May 88 12:06:02 PDT (Tue)
From: willc%tekchips.CRL%tektronix.tek.com@RELAY.CS.NET

The third occasional meeting of the Revised^n Report authors will
take place on Sunday, 24 July 1988, at Snowbird, Utah.  This is the
day before the ACM Conference on Lisp and Functional Programming,
also at Snowbird.  The exact time and place will be announced later,
as will the registration fee (if any);  I have requested a room for
thirty people from 8:30 am to 5 pm.  Hal Abelson will chair the meeting.

Please let me know immediately if you intend to attend.  If it appears
that too many people are planning to come, we'll have to do something
about it.  If you are coming, please send me your address and telephone
number.

Detailed proposals for changes to the R3RS should be submitted to me
by 15 June.  This should allow the agenda committee (Jonathan Rees and
myself?) to collate and edit the proposals in time to distribute them
two weeks before the meeting.  Participants should study these proposals
before coming to Snowbird.

This meeting of the RRRS authors is entirely separate from the IEEE
Scheme standardization meeting that is planned for the afternoon of
Wednesday, 27 July 1988, following the conference.

William Clinger
Semantic Microsystems, Inc.
4470 SW Hall Blvd, Suite 340
Beaverton OR 97005
(503) 643-4539

Received: from Xerox.COM (TCP 1500006350) by MC.LCS.MIT.EDU 27 Apr 88 22:03:57 EDT
Received: from Cabernet.ms by ArpaGateway.ms ; 27 APR 88 17:47:40 PDT
Date: Wed, 27 Apr 88 17:47:33 PDT
From: Pavel.pa@Xerox.COM
Subject: Proposals for R4RS
To: RRRS-Authors@mc.lcs.mit.edu
Message-ID: <880427-174740-6396@Xerox>

1. It would be nice if R4RS provided the simplest possible support for a
portable implementation of hash-tables.  As far as I can tell, the only things
required are two procedures:

EQ-HASH object
  Returns an integer with the property that (EQ? a b) implies (= (EQ-HASH a)
(EQ-HASH b)).  Implementations are encouraged to make the converse true as well
in as many cases as possible.
  
EQV-HASH object
  Returns an integer with the property that (EQV? a b) implies (= (EQV-HASH a)
(EQV-HASH b)).  Implementations are encouraged to make the converse true as well
in as many cases as possible.

I think that with these as primitives, one can portably write the corresponding
EQUAL-HASH procedure and essentially any other equivalence-relation hashing
function.  Thus, this appears to be sufficient for an efficient implementation
of hashing, working in terms of normal vectors.

Note that no ``unhash'' procedures are provided, so none of the difficulties
that caused OBJECT-HASH and OBJECT-UNHASH to be removed exist here.


2. Is there any reason not to make ``.'' and ``{'' and ``}'' extended alphabetic
characters?  Dot, in particular, is useful for EXTEND-SYNTAX implementations or
other things in that style.  Perhaps someone could simply explain the criteria
for inclusion in or exclusion from that extended alphabetic characters list?

Comments?

Received: from iuvax.cs.indiana.edu (TCP 30003147300) by MC.LCS.MIT.EDU  8 Apr 88 18:41:34 EDT
Received: by iuvax.cs.indiana.edu; id AA13722; Fri, 8 Apr 88 11:08:49 EST
Received: by iuvax.cs.indiana.edu (iuvax/MX/4.5/02-10-87)
	id AA13722; Fri, 8 Apr 88 11:08:49 EST
Date: Fri, 8 Apr 88 11:08:49 EST
From: Chris Haynes <chaynes@iuvax.cs.indiana.edu>
To: scheme@mc.lcs.mit.edu, rrrs-authors@mc.lcs.mit.edu
Subject: Scheme standarization

On March 25, 1988, a majority of the authors of the "Revised^3 Report
on the Algorithmic Language Scheme" (SIGPLAN Notices, December, 1986),
together with representatives of IEEE and X3 standardization
committees, met at Indiana University as a study group to consider
initiation of a formal standardization effort for Scheme.  It was
concluded that a formal standard was desirable to improve code
portability, publication uniformity, and language visibility.  It was
recommended that a PAR be submitted through the IEEE Microprocessor
Standards Committee to initiate the formal standardization effort and
establish a Scheme Working Group.  Christopher Haynes and William
Clinger were nominated for Chair and Vice-Chair of the Working Group,
respectively.  It is expected that the Working Group will meet
approximately twice a year, with the first meeting to be held on July
27, 1988, following the ACM Conference on Lisp and Functional
Programming at Snowbird, Utah.

The study group felt strongly that the informal group that produced
the existing Scheme reports should continue its language design work
by holding workshops and publishing further revised reports.  While
these reports are likely to form the basis for future revisions of the
standard, they will probably be less conservative than is appropriate
for a standards document and may, for example, include experimental
features that should be withheld from standardization.

The study group also concluded that Scheme standardization does
not conflict in any way with existing or contemplated standardization
efforts for other members of the Lisp family, such as X3J13.  It was
recommended that liaison be maintained with these efforts, and in
particular that the views of the Scheme community be taken into
account by the ANSI delegate to the ISO ISLISP standardization
meetings, and that an observer from the Scheme community be present at
such meetings if possible.


-- Chris Haynes
   chaynes@iuvax.cs.indiana.edu

Received: from murren (TCP 2206400263) by MC.LCS.MIT.EDU  6 Apr 88 19:53:25 EDT
Received: by MURREN.AI.MIT.EDU; Wed, 6 Apr 88 19:56:19 edt
Date: Wed, 6 Apr 88 19:56:19 edt
From: hal@MURREN.AI.MIT.EDU (Hal Abelson)
Message-Id: <8804062356.AA06370@murren>
To: rrrs-authors@mc
Subject: forwarded message from Clyde Camp
Reply-To: hal@ai.ai.mit.edu



Date: Wed, 6 Apr 88 16:43:41 CDT
From: Clyde Camp <camp@mips.csc.ti.com>
To: hal@mc.lcs.mit.edu
Cc: camp@mips.csc.ti.com
In-Reply-To: Hal Abelson's message of Tue, 5 Apr 88 21:16:17 edt <8804060116.AA05307@murren>
Subject: Scheme


OOPS -

I sent Chris a status message to forward to the group, but it
evidently never got to him (or he hasn't forwarded it yet).  So will
you please forward this to the net for me.

The ballot was sent out this morning (I got the foil updates yesterday
from Chris) and I requested results back by the 22nd.  Chris did not
send the article, but it is not really needed for the ballot and I was
running out of time to allow time for response. It will be needed
before June.


- Clyde


Date: Mon, 4 Apr 88 11:44:27 EST
From: camp
To: iuvax!chaynes@EE.ECN.PURDUE.EDU
CC: camp@csc.ti.com
In-reply-to: Chris Haynes's message of Tue, 29 Mar 88 12:10:43 EST <8803291746.AA26210@ee.ecn.purdue.edu>
Subject: one more thing 


Chris, please forward this to the authors for me.  The enclosures
referred to are the 1-2 page article and whatever updates to the foils
you wish to make.

- Clyde

=============================

I finally (after several volleys of telephone ping-pong) talked with
Andrew Salem, Director of Standards for the IEEE.  He has no problems
with the plan we proposed - specifically that the Scheme community
churns out RnRS documents at some (non-specified) rate and that
selected versions become the basis from which the IEEE standard is
developed.  The IEEE retains copyright to the standard while the
Scheme community retains copyright (or lack thereof) to the report.
He felt that this was entirely appropriate. Although he also
questioned why the community would want to retain the report after the
standard was published, he had no problems with its doing so.

With that potential problem being a non-problem, we are ready to
start.  I have the mail ballot ready to go and will send it out as
soon as I get the enclosures from Chris.  The current voting
membership is 34, so I need to get back at least 26 returns with at
least 20 positive votes to get the PAR request in by the May 1st
deadline.  Assuming that it passes, there will probably be no need for
anyone to attend the May meeting.

I enjoyed meeting all of you who attended the March 26 meeting and I
look forward to a continued relationship.

Regards,

Clyde