Re: [Scheme-reports] multiple values module

["Aaron W. Hsu" <arcfide@x>]

On Tue, 24 May 2011 17:41:14 -0400, Eli Barzilay <eli@x> wrote:

>> What I meant was this: trivially any procedure that returns
>> multiple values could as well return a single value which is an
>> aggregate of some sort such as a list or general vector.  However,
>> it costs something to aggregate and disaggregate this value, a cost
>> which *some* implementations of multiple values need not pay.

> You can't avoid the extra cost.  Implementations vary with heap or
> stack allocation which is something that goes in a different level.
> In any case, your original statement of multiple values as some
> lightweight alternative is even more wrong given this.  (The
> historical context is first class continuations.)

I'm not sure what you mean by the above, but I believe what John is  
referencing in the above is the efficiencies claimed by Ashley and  
Dybvig's 1994 paper [1] with which I am relatively confident you are  
familiar. The claim is that multiple values allows implementations to  
efficiently pass values back to a continuation without incurring the cost  
of explicit reification, which is what an implementation would normally  
need to do without the multiple values interface. The example in the paper  
uses split:

(define (split ls)
   (if (or (null? ls) (null? (cdr ls)))
       (values ls '())
       (let-values ([(odds evens) (split (cddr ls))])
         (values (cons (car ls) odds)
                 (cons (cadr ls) evens)))))

(define (split-cons ls)
   (if (or (null? ls) (null? (cdr ls)))
       (cons ls '())
       (let ([odds/evens (split-cons (cddr ls))])
         (cons (cons (car ls) (car odds/evens))
               (cons (cadr ls) (cdr odds/events))))))

In the implementation described by Ashley, which, according to the paper,  
can be applied equally well to stack, heap, or CPS based compilers, the  
split procedure above runs more quickly and with less allocation than the  
split-cons version. John's point, I think, is that without a multiple  
values interface in the language, reification is the normal means of  
handling these situations. The CPS version of the above is also tested in  
the paper and also benchmarked as slower and more space intensive than the  
multiple values interface.

It should be noted, however, that the claim that multiple values are more  
efficient in all cases, a claim that I do not think John is making, is  
wrong, since even with the above mentioned implementation strategy, if the  
compiler is not able to recognize certain things about the formulation,  
the above speed gains will not be observed.

	Aaron W. Hsu

[1] "An efficient implementation of multiple return values in Scheme." J.  
Michael Ashley and R. Kent Dybvig. 1994 ACM Conference on LISP and  
Functional Programming, pp. 140-149, June 1994.  
<http://www.cs.indiana.edu/~dyb/pubs/mrvs.pdf>.

-- 
Programming is just another word for the lost art of thinking.

_______________________________________________
Scheme-reports mailing list
Scheme-reports@x
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports