Hi all,
Have I correctly concluded that it is impossible for a /single stack/
function interface to return an arbitrary number of multiple values
without consing?
My reasoning is thus:
1. The function caller places n arguments on the stack and informs the
function callee of their location and number. No problem so far.
2. The callee then reserves space on the stack "above" the arguments for
local lexical variables. The amount of space to reserve can be accurately
determined at compile time. Still no problem.
3. The number of values the callee returns may only be known at run time,
and crucially may only be known by the callee once it is time to return to
the caller. This is too late to reserve space on the stack when the caller
may itself call a function before returning. At the time it calls a
subfunction the callee needs to allocate space for its arguments. But it
can't allocate the arguments when it doesn't know how much space to
reserve for multiple return values.
Maintaining two stacks--one for arguments and local variables and the
other for multiple return values--seems natural but costly.
Another potential solution would be to only support a low number of
multiple return values, such as the minimum of 20 as specified by ANSI
Common Lisp (multiple-values-limit). At steps 1, 2 or 3 one would always
reserve space for up to 20 return values.
Has anyone ever found it useful to return more than a few multiple return
values? If you knew your implementation never consed multiple return
values would you start returning hundreds or thousands of values this way?
Or would you still just pass them by reference via, e.g. an array or list?
Regards,
Adam
From: Florian Weimer
Subject: Re: A non-consing arbitrary number of multiple return values?
Date:
Message-ID: <87ekg874bp.fsf@deneb.enyo.de>
* Adam Warner:
> Have I correctly concluded that it is impossible for a /single stack/
> function interface to return an arbitrary number of multiple values
> without consing?
You can return with an elevated stack pointer.
I believe there's a version of GNAT which implements this on MIPS, but
I fear that it this approach isn't very efficient on modern processors
with return stack caches.
In article <······························@consulting.net.nz>,
Adam Warner <······@consulting.net.nz> wrote:
> Hi all,
>
> Have I correctly concluded that it is impossible for a /single stack/
> function interface to return an arbitrary number of multiple values
> without consing?
I think it may be possible to solve this by converting to
continuation-passing style, like Scheme's multiple-value mechanism.
Note also that if the function is called from a MULTIPLE-VALUE-BIND
form, there's no problem, as the caller can allocate space on the stack
for the return values, tell the callee how many are expected, and the
callee will fill these in when it's returning.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***