Pavel.pa@XEROX.COM (11/23/89)
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
dorai@titan.rice.edu (Dorai Sitaram) (11/23/89)
In article <891122-121343-4098@Xerox> Pavel.pa@XEROX.COM writes: >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> \kill? > | ( <id>* ) > | ( <id>+ . <id> ) \kill? > | ( <id>* "arbitrary" <id> <id> ) > | ( <id>* "arbitrary" <id> <id> . <id> ) \kill? >[...] I _love_ this idea! Probably the only merit of the existing "rest list" situation is that it made me work real[ly] hard to try to rewrite my code so that I avoided using them, sometimes getting in the process better-looking and better code incidentally. But, of course, there are always some places where one needs must use "varargs," and though Ch*z Scheme's case-lambda [1] construct goes some way toward avoiding the nasty list-fixation, your solution is more general with probably little or no (?) loss in efficiency. Luckily, both strategies can be combined to good use (restricting case-lambda arglists to non-rest-lists of course). What's RRRS have to say to this? --dorai [1] Dybvig & Hieb, A Variable-Arity Procedural Interface, 1988 ACM Conf. on Lisp and Functional Programming. -- ------------------------------------------------------------------------------- It may be that the gulfs will wash us down; It may be we shall touch the Happy Isles. -------------------------------------------------------------------------------
gateley@m2.csc.ti.com (John Gateley) (11/27/89)
In article <891122-121343-4098@Xerox> Pavel.pa@XEROX.COM writes: >[An interesting idea for handling variable numbers of arguments] I like the idea, though it is a large change (if it is implemented efficiently). I do have one point to make against it: the intertia of the list data type. Not only is there apply, but also map(car) and for-each, (and if you like CL, mapcan, mapcon, map-the-world :^). I would like a clean integration with some sort of looping structure, but this might mean (re)designing a MIT style LOOP macro. Any ideas? >[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.] After some thought, strings don't sound so bad to me. Consider: identifiers are really objects which we know at compile time to be symbols. (Is this true in Scheme? Do there exist identifiers which have no symbol or vice versa? I've been using CL too long). Along the same lines, we could have C-Strings (compile-time strings) which appear in lambda lists. The only significance to the name "C-string" is that identifiers and symbols have different names. John gateley@m2.csc.ti.com
mkatz@GARLIC.STANFORD.EDU (Morris Katz) (11/28/89)
Date: Wed, 22 Nov 89 11:55:42 PST From: Pavel.pa@xerox.com 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. I believe that it would be much cleaner to only use the second of the two extra arguments. (i.e., the one which is bound to a procedure) The information about the number of optional arguments which are supplied can be aquired through the use of an arity function of the type previously discussed on the rrrs-authors mailing list during a discussion on multiple values. I support the arity approach because it is more general purpose and can be specified in a manner that is orthoginal to the rest of Scheme. Why put in a special purpose hack, when a more general solution is available. ------------------------------------------------------------------------------- Morry Katz katz@cs.stanford.edu -------------------------------------------------------------------------------
mkatz@GARLIC.STANFORD.EDU (Morris Katz) (11/28/89)
Date: Mon, 27 Nov 89 14:11:47 PST From: Pavel.pa@Xerox.COM To what procedure would you apply "arity" to get the answer? In retrospect it is clear that my original message on this subject was so cryptic as to be content free. I would propose having one extra argument which would be bound to a procedure which would return the optional arguments as multiple return values. For symetry reasons, a language which supports multiple return values would require two types of arity functions: call-arity and return-arity. (Please don't flame about the names. I just hate using foo and bar as names when I can think of something semantically more meaningful.) Call-arity is the procedure which is more commonly called arity and returns information about the number of parameters which a function expect. Return-arity is the procedure which returns information about the number of return values to be returned by a function. An application of return-arity to the special function which is bound to optional arguments would return information about the number of optionals which were supplied. I realize that this proposal goes far beyond Pavel's original question; but, I believe that multiple return values should be integrated into Scheme for good symetry reasons. I feel that this can be done in such a way that they will actually solve many more problems than they create. Pavel's application is only one of many examples where the multiple value approach actually leads to a quite elegant solution. ------------------------------------------------------------------------------- Morry Katz katz@cs.stanford.edu -------------------------------------------------------------------------------
gateley@m2.csc.ti.com (John Gateley) (11/29/89)
In article <8911272329.AA07264@garlic.Stanford.EDU> mkatz@GARLIC.STANFORD.EDU (Morris Katz) writes: >[...] >Return-arity is the procedure which returns information about the number of >return values to be returned by a function. This seems confusing: (return-arity (lambda (x) (values 1 2 3))) => 3 ((lambda (x) (values 1 2 3) 'dummy) => three values. A function which return-arity says returns three values actually returns 3 values. I forget the name of Pavel's rest arg indicator, call it "rest". (lambda ("rest" rest-fn) (return-arity rest-fn)) => the number of values passed as arguments ((lambda ("rest" rest-fn) (rest-fn 0)) arg1 arg2 arg3) => a single value! A function which return-arity says returns three values actually returns a single value. So, Pavel's new rest-functions have to be handled differently by your return-arity procedure. Or, I am missing something. John gateley@m2.csc.ti.com