n-ary functions rfc

[Norman Adams <norman@parc.xerox.com>]

Here is Pavel's "Request for Comments: A new n-ary function construction"
which was sent to the `scheme' mailing list, not `rrrs-authors.'

-Norman
----------------------------------------------------------------
Date: Wed, 22 Nov 89 11:55:42 PST
From: Pavel.pa@xerox.com
Subject: Request for Comments: A new n-ary function construction
Message-ID: <891122-121343-4098@Xerox>

This note concerns an idea I've been kicking around for some time; I'm
probably going to implement the idea in Scheme Xerox and I'd like to get
comments on it from the community at large.  You can consider yourselves as
design consultants...

I would like to avoid using ``rest lists'' in my Scheme code, especially at
the lowest levels, for a number of reasons: they are usually difficult to
optimize and I don't like the language-level preference for the list type
over, for example, vectors.  To get around the problem, I thought of
extending the syntax of lambda-lists to the following:

<lambda-list> ::= <id>
                | ( <id>* )
                | ( <id>+ . <id> )
                | ( <id>* "arbitrary" <id> <id> )
                | ( <id>* "arbitrary" <id> <id> . <id> )

That is, you can now follow the ``required'' parameters by the marker
string "arbitrary" and two identifiers.  The first of these will, on
invocation of the procedure, be bound to the number of ``extra'' arguments,
those not accounted for by the required parameters; it is an exact integer.
The second new identifier will be bound to a procedure of one argument, an
exact non-negative integer less than the extra argument count; it returns
the extra argument with that index.

[Note: I'll point out right here that nobody I've shown this to has liked
having strings in the lambda-list.  It just seemed better to me than
&arbitrary or #!arbitrary.  Suggestions are solicited.]

Thus, for example, one could write Common Lisp's LIST* as follows:

	(define (list* first "arbitrary" n f)
	   (if (zero? n)
	      first
	      (cons first
	            (let loop ((i (- n 2))
	                       (result (f (- n 1)))) ; last argument
	               (if (negative? i)
	                  result
	                  (loop (- i 1)
	                        (cons (f i) result)))))))

The advantages of this approach are straightforward to see.  On the
practical side, it is easily optimized in the case where the
argument-fetching function does not escape: all invocations can be
implemented as simple indexes into the actual argument vector on the stack
(or wherever).  When the function does escape, its closure can probably be
allocated and filled in faster than the corresponding rest list.  On the
language purity side, this seems to me a cleaner approach, using the more
fundamental data types of integers and procedures, rather than lists.  It
also allows random access to the arguments when that's handy, as it was
above.  This is more difficult with lists.

Of course, one of the common uses of rest lists is as eventual arguments to
APPLY.  This is a fine idiom and so we should have a way to support a
corresponding idiom with this construct.  Suppose that we had a new
primitive, called APPLYF for lack of a good name, defined as follows:

	(APPLYF fn arg1 ... argK n f)

	Applies the procedure FN to (K + N) arguments:
		arg1 ... argK (f 0) ... (f n-1)

This new primitive can, of course, accept any N and F, not just those
acquired from the "arbitrary" mechanism:

	(define (iota k)
	   (applyf vector k (lambda (i) (+ i 1))))

In the case where F did come from the the "arbitrary" mechanism, it is easy
to optimize the resulting code as a cheap argument-copying loop.

Sometimes, with rest lists, one wants to pass along to APPLY a tail of the
original list:

	(define (foo . x)
	   (apply bar (cdr x)))

or some such.  This can also be done with APPLYF:

	(define (foo "arbitrary" n f)
	   (applyf bar (- n 1) (lambda (k) (f (+ k 1)))))

Granted, this isn't as concise, but the idea is more general.  We can as
easily pass a prefix of the arguments:
	(define (foo "arbitrary" n f)
	   (applyf bar (- n 1) f))

or just the even-indexed ones:

	(define (foo "arbitrary" n f)
	   (applyf bar (quotient (+ n 1) 2)
	               (lambda (k) (f (* k 2)))))

In all of these cases, it's easy to optimize the resulting code to contain
no procedure calls and no allocation.

Some of you with longer memories may recognize the old MacLisp LEXPR
mechanism (or Interlisp LAMBDA*) in this facility.  It's different in
important ways, though: the argument-fetching function is not a special
form taking a strange argument with dynamic scope, it is a normal Scheme
procedure with indefinite extent.

I've rambled enough for now; what do you folks think?

	Pavel Curtis
	Xerox PARC/CSL