informal proposal: A Modified Procedural Interface

[Robert Hieb <hieb@iuvax.cs.indiana.edu>]

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