I am curious how compilers typically implement multiple return values
for LISP, and how I can implement it in my own compiler.
The problem I am having is that it is almost impossible to have
communication between the returner and the returnee about whether or not
multiple values have been returned or not, and so the management of
storage for the returned values becomes nearly impossible.
For example, if you store the extra returns in other registers or in a
global location, its impossible to determine is that information was
filled in by the function returning multiple values, or by some other
function (an argument to a
function, or something in a progn).
Any information appreciated.
CU
Dobes
In article <·················@mindless.com>,
Dobes Vandermeer <·····@mindless.com> wrote:
>I am curious how compilers typically implement multiple return values
>for LISP, and how I can implement it in my own compiler.
>
>The problem I am having is that it is almost impossible to have
>communication between the returner and the returnee about whether or not
>multiple values have been returned or not, and so the management of
>storage for the returned values becomes nearly impossible.
However, it's possible to have communication between the caller and callee
about how many return values are expected. In fact, the Lisp Machines had
specific CALL instructions, something like CALL-1 for single-value calls
(as in argument forms in a surrounding function call form), CALL-N for
calls via MULTIPLE-VALUE-BIND, and CALL-MULTIPLE for MULTIPLE-VALUE-LIST
and MULTIPLE-VALUE-BIND.
The code for returning from a function can check the field in the stack
frame that specifies how many values are expected, and do the right thing
pretty easily.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
In article <···················@burlma1-snr2>, Barry Margolin
<······@bbnplanet.com> wrote:
> In article <·················@mindless.com>,
> Dobes Vandermeer <·····@mindless.com> wrote:
> >I am curious how compilers typically implement multiple return values
> >for LISP, and how I can implement it in my own compiler.
> >
> >The problem I am having is that it is almost impossible to have
> >communication between the returner and the returnee about whether or not
> >multiple values have been returned or not, and so the management of
> >storage for the returned values becomes nearly impossible.
>
> However, it's possible to have communication between the caller and callee
> about how many return values are expected. In fact, the Lisp Machines had
> specific CALL instructions, something like CALL-1 for single-value calls
> (as in argument forms in a surrounding function call form), CALL-N for
> calls via MULTIPLE-VALUE-BIND, and CALL-MULTIPLE for MULTIPLE-VALUE-LIST
> and MULTIPLE-VALUE-BIND.
>
> The code for returning from a function can check the field in the stack
> frame that specifies how many values are expected, and do the right thing
> pretty easily.
Dobes:
Beware:
(multiple-value-list
(block nil
(unwind-protect
(return (values 1 2))
(return (values 1)))))
=>
(1)
I believe that initial abandoning of interveneing "exit points" as
described in X3J13 March 1989 <74> was ill considered. Most (all?)
implementations of the condition system use exit points for transfer of
control for handler cases, etc.
If cleanup forms of UNWIND-PROTECTS signal conditions that are handled by
cases reached by "exit points", and these handlers lie within the
abandoned range of a GO then what is the effect?
I have seen no information about reconciliation of possibly abandoned
"exit points" with extent of condition handlers.
The longer extents (traditional for some (most) implementations) allowed
by X3J13 make this a non-issue.
-----------
With or without longer extents for "exit points" there are several things
to consider when designing multiple value implementations.
1) MULTIPLE-VALUE-CALL and MULTIPLE-VALUE-LIST don't have fixed number of
values.
2) As in the example above, an initial number of values may be "returned"
and this may subsequently be replaced with fewer values. This can cause
the obvious problems if you initialize a receive area for the values, and
simply copy to the area.
3) If you use a stack for MV's, remember that other MV's may be generated
and consumed while a set is active on the MV stack. e.g.:
(multiple-value-list
(block nil
(unwind-protect
(return (values 1 2))
(block nil
(return (values 1))))))
=>
(1 2)
4) More I have forgotten...
d
P.S. As Barry said, haveing the caller signal that it accepts MV's is very
useful.
Consider:
(defun foo (x)
(truncate x 3))
(list (foo 2)) => (0)
(multiple-value-list (foo 2)) => (0 2)
FOO need know nothing about MV's, it can just pass along its caller's MV bit.
Barry Margolin wrote:
>
> In article <·················@mindless.com>,
> Dobes Vandermeer <·····@mindless.com> wrote:
> >I am curious how compilers typically implement multiple return values
> >for LISP, and how I can implement it in my own compiler.
> >
> >The problem I am having is that it is almost impossible to have
> >communication between the returner and the returnee about whether or not
> >multiple values have been returned or not, and so the management of
> >storage for the returned values becomes nearly impossible.
>
> However, it's possible to have communication between the caller and callee
> about how many return values are expected. In fact, the Lisp Machines had
> specific CALL instructions, something like CALL-1 for single-value calls
> (as in argument forms in a surrounding function call form), CALL-N for
> calls via MULTIPLE-VALUE-BIND, and CALL-MULTIPLE for MULTIPLE-VALUE-LIST
> and MULTIPLE-VALUE-BIND.
>
> The code for returning from a function can check the field in the stack
> frame that specifies how many values are expected, and do the right thing
> pretty easily.
Very interesting!
And it looks like the only case where this has to be propagated upwards
is in the last form of a progn, and a few other special cases. Almost
all other forms will only demand single values, as far as I know.
Thank you, this will probably solve it, although any other solutions are
still welcomed..
CU
Dobes
Dobes Vandermeer wrote:
>
> I am curious how compilers typically implement multiple return values
> for LISP, and how I can implement it in my own compiler.
>
> The problem I am having is that it is almost impossible to have
> communication between the returner and the returnee about whether or not
> multiple values have been returned or not, and so the management of
> storage for the returned values becomes nearly impossible.
>
> For example, if you store the extra returns in other registers or in a
> global location, its impossible to determine is that information was
> filled in by the function returning multiple values, or by some other
> function (an argument to a
> function, or something in a progn).
>
> Any information appreciated.
Returning functions tell the caller how many arguments they are returning.
In the typical case, the callee need not check, because at least one value
is returned (even in the case of (values)). If the callee needs more than
one value, they must check to see how many the caller returned.
You seem to indicate that it is hard to know how many values are being
returned, but I don't remember that as being a problem (although it has
been over 10 years since I did this)
"Christopher J. Vogt" wrote:
>
> Dobes Vandermeer wrote:
> >
> > "Christopher J. Vogt" wrote:
> > >
> > > Dobes Vandermeer wrote:
> > > >
> > > > "Christopher J. Vogt" wrote:
> > >
> > > > [...]
> > >
> > > > > Returning functions tell the caller how many arguments they are returning.
> > > > > In the typical case, the callee need not check, because at least one value
> > > > > is returned (even in the case of (values)). If the callee needs more than
> > > > > one value, they must check to see how many the caller returned.
> > > > >
> > > > > You seem to indicate that it is hard to know how many values are being
> > > > > returned, but I don't remember that as being a problem (although it has
> > > > > been over 10 years since I did this)
> > > >
> > > > I suppose that while I could do that, I would incur an extra overhead to
> > > > every function return (i.e. every return would be a multiple return)
> > > > that I consider unacceptable, and certainly not worth it in the light of
> > > > the number of occasions where *I* (and probably most people) use
> > > > multiple return values (not very often).
> > >
> > > I'd be interested to know what you are going to do, this multiple values stuff
> > > is riddled with screw cases. My design was for hardware and we were able to
> > > return a value and set the number of values being returned in a single cycle.
> > > I can see that without the special hardware support this would take extra
> > > cycles.
> > >
> > > It seems to me that you are going to have overhead in every caller
> > > or every callee. It may be the case that it is an equal amount of overhead.
> >
> > My function calling mechanism includes the number of arguments as the
> > first parameter, but since this is a 32-bit number, I believe it is safe
> > for me to use only the lower 16 bits for an instruction count, and the
> > upper to indicate the expectation of multiple returns. I can then make
> > (values ..) check for this indication, and return a special identifiable
> > multiple returns object that the receiver woudl check for. If the bit
> > is not set, values woudl return only one value. This only incurs
> > overhead in forms where multiple values can be successfully be
> > propagated backwards, which are limited in number... I believe only
> > conditional forms and progn, in fact, can pass multiple returns upwards,
> > function arguments certainly cannot. I can even allow for cases where
> > the apparent return of the values happens inside the calling function,
> > because values is it self a function, and woudl thus have the multiple
> > value expectation passed through to it. The only possible flaw is when
> > you use (return (values ..)) as the parameter to a function, thus
> > exiting before calling the function, and not actually being in one of
> > the forms that passes the multiple returns signal upwards. I would
> > merely have to handle this case specially.
>
> A caller does not always know if it needs multiple values or not (maybe this
> means it does need multiple values?) and it might not know how many it needs,
> e.g.
>
> (multiple-value-list (foo))
>
> (defun foo ()
> (bar))
>
> (defun bar ()
> (baz))
>
> (defun baz ()
> (values 1 2 3))
>
> USER(1): (foo)
> 1
> 2
> 3
>
> >From the callers perspective I think there are 4 cases:
> 1. I don't want any values
> 2. I want 1 value
> 3. I want N values
> 4. I don't know how many values I want because I'm just passing them on the the
> guy who called me.
>
> I think the screw cases all lie in number 4.
But a caller DOES always know if they need multiple values, because
their caller tells them. Only the multiple-value-* forms will request
multiple values, and all of the #4 cases will simply have to pass this
flag upwards... I will have to add extra overhead in the last form of a
progn, a return form, or the return from a conditional that will pass
the expected returns upwards.
A rough approximation of your example in C would be:
multiple_value_list(foo(0 | CALLFLAG_GET_MULTIPLE_RETURNS));
void foo(int numargs)
{
return bar(numargs & CALLFLAG_GET_MULTIPLE_RETURNS)
}
void baz(int numargs)
{
return values(3 | (numargs & CALLFLAG_GET_MULTIPLE_RETURNS), 1, 2, 3);
}
void values(int numargs, arg1, ...)
{
if(numargs & CALLFLAG_GET_MULTIPLE_RETURNS)
{
return multiple_value_object((short) numargs, &arg1);
}
else
{
return arg1;
}
}
... which I believe is doable, as long as I account for all cases where
the multiple return flag is propagated upwards, and I consistently
ignore the upper 16 bits of the argument count;
CU
Dobes
From: Howard R. Stearns
Subject: Re: Implementing multiple return values
Date:
Message-ID: <370253F0.A095E731@elwood.com>
In Eclipse, we want C programmers to be able to view Lisp functions as
if they were normal C functions. Accordingly, Lisp functions always
return their primary value in the usual C way, as opposed to returning
an integer indicating the number of returned values. Also, C callers
don't need to know anything about multiple values unless they want to
use them. With this in mind, here's two paragraphs from
a paper on Eclipse implementation
(http://www.elwood.com/eclipse/papers/lugm98/lisp-c.html):
Eclipse defines each generated C function to return the ``primary'' Lisp
value as an clObject value. Eclipse also defines a
globally known pointer to a buffer of multiple clObject values. Some
functions just return the values returned by other
functions (i.e., are tail calls). However, if a function returns a
single value (e.g., the value of a variable), then a macro from
``eclipse.h'' must be used to indicate in the multiple values buffer
that only one value is returned. The function clValues()
can also be used to fill the multiple value buffer with zero or more
values. Receiving multiple values is accomplished by
using a macro from ``eclipse.h'' that introduces a new multiple values
buffer as a local (automatic, stack) C variable. The
macro stores the location of this new buffer in the globally known
pointer.
....
Eclipse defines macros in ``eclipse.h'' for using the control stack to
establish dynamic bindings, blocks, tagbodies,
catchers, and cleanups. The header file also defines macros for
non-local transfers such as RETURN-FROM, GO, and THROW
that unwind the control stack as necessary. Besides using the
appropriate longjmp() machinery, these transfers take
care of unwinding dynamic bindings, executing UNWIND-PROTECT cleanup
forms, and manipulating the multiple value
machinery pointers.
Dobes Vandermeer wrote:
>
> I am curious how compilers typically implement multiple return values
> for LISP, and how I can implement it in my own compiler.
>
> The problem I am having is that it is almost impossible to have
> communication between the returner and the returnee about whether or not
> multiple values have been returned or not, and so the management of
> storage for the returned values becomes nearly impossible.
>
> For example, if you store the extra returns in other registers or in a
> global location, its impossible to determine is that information was
> filled in by the function returning multiple values, or by some other
> function (an argument to a
> function, or something in a progn).
>
> Any information appreciated.
>
> CU
> Dobes
"Howard R. Stearns" wrote:
>
> In Eclipse, we want C programmers to be able to view Lisp functions as
> if they were normal C functions. Accordingly, Lisp functions always
> return their primary value in the usual C way, as opposed to returning
> an integer indicating the number of returned values. Also, C callers
> don't need to know anything about multiple values unless they want to
> use them. With this in mind, here's two paragraphs from
> a paper on Eclipse implementation
> (http://www.elwood.com/eclipse/papers/lugm98/lisp-c.html):
This happens to be my goal as well.
> Eclipse defines each generated C function to return the ``primary'' Lisp
> value as an clObject value. Eclipse also defines a
> globally known pointer to a buffer of multiple clObject values. Some
> functions just return the values returned by other
> functions (i.e., are tail calls). However, if a function returns a
> single value (e.g., the value of a variable), then a macro from
> ``eclipse.h'' must be used to indicate in the multiple values buffer
> that only one value is returned. The function clValues()
> can also be used to fill the multiple value buffer with zero or more
> values. Receiving multiple values is accomplished by
> using a macro from ``eclipse.h'' that introduces a new multiple values
> buffer as a local (automatic, stack) C variable. The
> macro stores the location of this new buffer in the globally known
> pointer.
So basically every function thats is returning has to specify whether it
is returning one or multiple values, and thus if the caller has provided
a space to store multiple return values, then it will be erased by each
form executed right up until the returning form?
CU
Dobes
From: Howard R. Stearns
Subject: Re: Implementing multiple return values
Date:
Message-ID: <37038896.B2A18FAB@elwood.com>
Dobes Vandermeer wrote:
>
> "Howard R. Stearns" wrote:
> >
> > In Eclipse, we want C programmers to be able to view Lisp functions as
> > if they were normal C functions. Accordingly, Lisp functions always
> > return their primary value in the usual C way, as opposed to returning
> > an integer indicating the number of returned values. Also, C callers
> > don't need to know anything about multiple values unless they want to
> > use them. With this in mind, here's two paragraphs from
> > a paper on Eclipse implementation
> > (http://www.elwood.com/eclipse/papers/lugm98/lisp-c.html):
>
> This happens to be my goal as well.
>
> > Eclipse defines each generated C function to return the ``primary'' Lisp
> > value as an clObject value. Eclipse also defines a
> > globally known pointer to a buffer of multiple clObject values. Some
> > functions just return the values returned by other
> > functions (i.e., are tail calls). However, if a function returns a
> > single value (e.g., the value of a variable), then a macro from
> > ``eclipse.h'' must be used to indicate in the multiple values buffer
> > that only one value is returned. The function clValues()
> > can also be used to fill the multiple value buffer with zero or more
> > values. Receiving multiple values is accomplished by
> > using a macro from ``eclipse.h'' that introduces a new multiple values
> > buffer as a local (automatic, stack) C variable. The
> > macro stores the location of this new buffer in the globally known
> > pointer.
>
> So basically every function thats is returning has to specify whether it
> is returning one or multiple values, and thus if the caller has provided
> a space to store multiple return values, then it will be erased by each
> form executed right up until the returning form?
Yes and no. A function that has another function call in tail position
simply calls the referenced function. It doesn't bother with the
multiple values buffer at all. Forms that produce an ignored value
(i.e., are not in tail position) also do not mess with the multiple
value machinery. Only two things do write to the multiple values
buffer:
1. The function clValues(clObject, ...).
2. The macro clValues1(clObject), which is introduced by the compiler
only in
(possibly constant) variable references which happen to be in tail
position
in a function. (Actually, that's a lie. Some things that would
seem to be
function calls get transformed into C macros, and these, if in tail
position,
do end up gettring wrapped in clValues1().)
This is not to say that the multiple values buffer never gets written to
unnecessarilly. For example, a function that happens to be called from
the middle of a progn doesn't know that it's value is being ignored.
That ignored function (or the functions it calls) will eventually call
either clValues() or clValues1(), yet the value will never be used, in
fact, will end up getting overwritten. (When I get inlining working,
than inlined calls in non-tail position will be able to avoid this extra
clValues1() call.)
Note that there is always a valid multiple values buffer, even if we're
not in a context in which someone will read it. Thus clValues1/clValues
do not have to check to see if the multiple values buffer pointer is
valid before writing to it, they just unequivocally write to it. If I
understand modern architectures right, (which I probably don't), this
reduces pipeline turbulence (no conditionals) at the expense of
additional memory access (but at least the two locations referenced are:
1: the static variable that holds the pointer to the buffer, and 2: the
buffer itself, which is on the C execution stack and thus should be fast
memory.)
Also, although it doesn't effect what is said above, here's another
detail.
The clValues()/clValues1() utilities (particularly the latter) get
called a LOT more than anyone looks at multiple values, so we want them
to be fast, even if that means that looking at multiple values is
slower. Accordingly, these utilites don't actually count the number of
values or write a count anywhere. Instead, they just write a constant C
NULL after the last value. The multiple value READING machinery uses
values from the buffer up until the NULL. Multiple-value-call just
advances the buffer pointer to the location of that NULL in between each
call from which returned values are collected.
"Howard R. Stearns" wrote:
>
> This is not to say that the multiple values buffer never gets written to
> unnecessarilly. For example, a function that happens to be called from
> the middle of a progn doesn't know that it's value is being ignored.
> That ignored function (or the functions it calls) will eventually call
> either clValues() or clValues1(), yet the value will never be used, in
> fact, will end up getting overwritten.
Yes, and this is the kind of solution I have trouble justifying to
myself. The code to overwrite the multiple values buffer is probably
executed thousands of times more often than it is needed; of course, as
you describe below, the overhead in the short run is negligable, but
nevertheless I want to find a solution that dodges that additional
complication.
> If I
> understand modern architectures right, (which I probably don't), this
> reduces pipeline turbulence (no conditionals) at the expense of
> additional memory access
That sounds right to me, too. The memory access is fairly likely to be
on the cache as well, which means very few lost cycles.
> (but at least the two locations referenced are:
> 1: the static variable that holds the pointer to the buffer, and 2: the
> buffer itself, which is on the C execution stack and thus should be fast
> memory.)
What do you mean by "on the C execution stack"?
Do you mean you are storing the returns in a static buffer?
> Also, although it doesn't effect what is said above, here's another
> detail.
> The clValues()/clValues1() utilities (particularly the latter) get
> called a LOT more than anyone looks at multiple values, so we want them
> to be fast, even if that means that looking at multiple values is
> slower.
Yes, of course.
Well, it sounds sound.. but I am going to try the method suggested by
Barry Margolin, which seems to me like it can work and will certainly be
more friendly to my garbage collection scheme.
Thanks
Dobes
Dobes Vandermeer <·····@mindless.com> writes:
> The code to overwrite the multiple values buffer is probably
> executed thousands of times more often than it is needed
You can always put (values x) or (nth-value 0 x) around something to
mask it out if it matters to you at the user side. And then your
compiler will be able to infer the right number of return values at
all the join points. You can even make a nice macro to make this
look more "exprssional" and less "implementational".
Also, the compiler can do as much flow analysis as it wants if it
provides a block compilation mode, too.
The problem isn't as bad as it looks, I suspect. And I weight it against
the thousands of people hours spent laboriously linking and re-linking
code definitions in languages like Java because some inconsequential
transport function didn't properly declare its exceptions list or its
arg types when the arg types and exceptions just didn't matter to the
guy doing the coding. So it's a matter of what you value. When you
say that it's not "needed", you are using a world-view that doesn't
incorporate and value the programmer's time.
Of course, programmer time doesn't map one to one to user time, and it
might be that the programmer saving time isn't as valuable as the end
user saving time, but mostly I don't believe that. Most programs are
not in that kind of bottleneck where they need every last cycle,
especially any more with the bloat-o-rama releases we're getting out
of nearly every major program. Microsoft Word takes longer to start
on my 350MHz machine than Word took to start on my 512K Mac, and not
for any good reason I cna see. My PC takes longer to boot than my
Lisp Machine did in 1986. Emacs takes longer to start on a 350MHz
single-user PC than it did on a heavily loaded PDP10 in 1980. Lots of
programs that are used a lot don't care about speed as much as people
think. Customers put up with it. And if it takes another few weeks
or months to put out the release with the faster version, by then
you've lost market share to someone else who had better
time-to-market. So programmer time is important and customer time,
for better or worse, apparently is not.
That's not to say you can't make fast code in Lisp. (Everyone lately
seems to want to infer stuff from words I've left out, so I'm forced
to be pedantic and say the implications of things I've not said.)
That's just to say that making fast code in Lisp, as with other
languages, involves additional work by the programmer. The difference
is that Lisp programmers can sometimes get away with not doing the
extra work where it doesn't make any difference. Try leaving out
"unimportant/tedious declarations" in C or Java and see how far it gets you.
Kent M Pitman wrote:
>
> Dobes Vandermeer <·····@mindless.com> writes:
>
> > The code to overwrite the multiple values buffer is probably
> > executed thousands of times more often than it is needed
>
>
> Also, the compiler can do as much flow analysis as it wants if it
> provides a block compilation mode, too.
Unfortunately, I am programming a dynamic (compiling) environment, not a
LISP->EXE system,
so flow analysis is essentially impossible because every function has
the right to change how many values it returns at any time.
I am complimented by the suggestion, though, that I would be willing and
able to code that kind of in-depth code analysis.
> The problem isn't as bad as it looks, I suspect. And I weight it against
> the thousands of people hours spent laboriously linking and re-linking
> code definitions in languages like Java because some inconsequential
> transport function didn't properly declare its exceptions list or its
> arg types when the arg types and exceptions just didn't matter to the
> guy doing the coding. So it's a matter of what you value.
Your bitterness is very apparent, but perhaps you are wasting valuable
programmer time yourself writing out this enormous tirade against typed
languages? I myself am no advocate of Java or any other language in
particular, but I certainly hold no resentment towards their
implementations.
> When you
> say that it's not "needed", you are using a world-view that doesn't
> incorporate and value the programmer's time.
That is not the case at all. The issue at hand would have no effect
whatsoever on programmer time. In fact, regardless of which way I
implement it, the programmer's code will look exactly the same, and will
thus take the same amount of time to code.
> Most programs are
> not in that kind of bottleneck where they need every last cycle,
> especially any more with the bloat-o-rama releases we're getting out
> of nearly every major program.
Yes, almost any large-scale application will have a lot of overhead;
they need it to be user-friendly and maintain their large user
interface. On the other hand, if my compiler is generating bloated
code, then the bloated applications will be an order more bloated than
they could have been, because they are saturated with excessive writes
to a multiple returns buffer that is hardly being used.
You also have to consider the target application of your compiler, which
is my case does include the implied requirement that as few cycles be
wasted as possible. Any kind of loss caused by an insignificant feature
like multiple return values would be a total waste. Also, in the case
of Eclipse, it is beginning to appear that in fact programmer time may
also have been at stake, writing in extra calls to clear the multiple
return buffer where normally you could get away with only a return
(although I am not sure about this).
CU
Dobes
From: Howard R. Stearns
Subject: Re: Implementing multiple return values
Date:
Message-ID: <37053987.EA0C07FC@elwood.com>
Dobes Vandermeer wrote:
>
> Kent M Pitman wrote:
> ...
> That is not the case at all. The issue at hand would have no effect
> whatsoever on programmer time. In fact, regardless of which way I
> implement it, the programmer's code will look exactly the same, and will
> thus take the same amount of time to code.
I think the idea is that if you're compiler locks in any assumptions
about how something will be used, and then the programmer uses things
differently, a lot of programmer time will be wasted trying to track
down the problem. It's not that your compiler/implementation will
effect how the code looks, but rather how it is interacted with during
development.
>... Also, in the case
> of Eclipse, it is beginning to appear that in fact programmer time may
> also have been at stake, writing in extra calls to clear the multiple
> return buffer where normally you could get away with only a return
> (although I am not sure about this).
No. The compiler handles normal Common Lisp code: Common Lisp doesn't
make you do anything like this and neither does Eclipse. Perhaps I'm
missing your point, but it's not clear to me why you think that someone
writing Lisp code would have to insert additional anything into their
Lisp code in order to "clear the multiple return buffer".
"Howard R. Stearns" <······@elwood.com> writes:
> Dobes Vandermeer wrote:
> >
> > Kent M Pitman wrote:
> > ...
> > That is not the case at all. The issue at hand would have no effect
> > whatsoever on programmer time. In fact, regardless of which way I
> > implement it, the programmer's code will look exactly the same, and will
> > thus take the same amount of time to code.
>
> I think the idea is that if you're compiler locks in any assumptions
> about how something will be used, and then the programmer uses things
> differently, a lot of programmer time will be wasted trying to track
> down the problem. It's not that your compiler/implementation will
> effect how the code looks, but rather how it is interacted with during
> development.
Yes. And also that everything you have to remember about the language
is more complicated than it needs to be. For example, if I go and read
about a library of Lisp things, I can remember the argument conventions
because they make sense and aren't weighed down with stupid stuff.
Having to remember exceptions defeats the purpose of HAVING exceptions,
at least the purpose in Lisp, which is to insulate you from having
the unusual situations "in-your-fase". C-style of having to read a
char from a stream and then immediately check not only for a good value
but for an eof-value makes it impossible to prototype by just doing
the simple thing of not checking for EOF. In Lisp, if you omit the eof
check, you don't get a wrong answer, you get into the debugger, but you
also can get away with running programs in many cases and NOT end up
in the debugger. Java is better than C in that it doesn't let you get
wrong programs but it is worse than Lisp in that it forces you to do
massive tedium with respect to exceptions.
I wrote a whole paper on what exception handling was about back in 1990
pre-Java, citing a number of powerful things about the Lisp error system,
so I know it's not just sour grapes that Java is popular and Lisp is not.
Java objectively does not meet a number of the specific objectives
that I cited in that paper about what Lisp does. Java is a step back
to languages like CLU which preceded it where the joke was that you had
to write different functions to add octal numbers than to add decimal
numbers... typing information can be very useful, and every compiler
should have a way to provide it and should be willing to use it where
provided aggressively--however, there's really no excuse I can think of
for insisting on type declarations. Java would not be any weaker if it,
like XML, had a mode in which it ran in "loose" mode without requiring
such exacting line-up. People who wanted to reject running programs
that were not "proven" could still do so. But people who wanted to just
prototype could do so without having to be utterly rigorous on every detail
when the goal is to write throwaway code no one will ever see...
On Sat, 3 Apr 1999 07:26:00 GMT, Kent M Pitman <······@world.std.com> wrote:
>I wrote a whole paper on what exception handling was about back in 1990
>pre-Java, citing a number of powerful things about the Lisp error system,
>so I know it's not just sour grapes that Java is popular and Lisp is not.
I am sure I am not (nor will be) the first to ask for the reference...
Mark
--
Mark K. Gardner (········@cs.uiuc.edu)
University of Illinois at Urbana-Champaign
Real-Time Systems Laboratory
--
Mark K. Gardner <········@cs.uiuc.edu> wrote:
+---------------
| Kent M Pitman <······@world.std.com> wrote:
| >I wrote a whole paper on what exception handling was about back in 1990
|
| I am sure I am not (nor will be) the first to ask for the reference...
+---------------
See http://world.std.com/~pitman/Papers/index.html and scroll down
to the "March 1990" entry. [Unfortunately, the table indicates that
that particular paper is only available in hardcopy, but see the
footnote.]
-Rob
p.s. http://world.std.com/~pitman/PS/About-PS.html also has
a bunch of fun papers...
-----
Rob Warnock, 8L-855 ····@sgi.com
Applied Networking http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673
2011 N. Shoreline Blvd. FAX: 650-964-0811
Mountain View, CA 94043 PP-ASEL-IA
····@rigden.engr.sgi.com (Rob Warnock) writes:
> Mark K. Gardner <········@cs.uiuc.edu> wrote:
> +---------------
> | Kent M Pitman <······@world.std.com> wrote:
> | >I wrote a whole paper on what exception handling was about back in 1990
> |
> | I am sure I am not (nor will be) the first to ask for the reference...
> +---------------
>
> See http://world.std.com/~pitman/Papers/index.html and scroll down
> to the "March 1990" entry. [Unfortunately, the table indicates that
> that particular paper is only available in hardcopy, but see the
> footnote.]
I spent a couple hours this morning moving it to HTML. The URL you
cite will now find a webbed copy (you may have to reload the page if
you have it cached). Please report typos or confusions due to aging
of the document. Happy Easter.
> p.s. http://world.std.com/~pitman/PS/About-PS.html also has
> a bunch of fun papers...
I'm glad you liked them.
On 4 Apr 1999 08:59:40 GMT, Rob Warnock <····@rigden.engr.sgi.com> posted:
>p.s. http://world.std.com/~pitman/PS/About-PS.html also has
>a bunch of fun papers...
Definitely some good stuff; the page
<http://world.std.com/~pitman/Papers/index.html> seems to have some
problems in its referencing of the Parenthetically Speaking papers,
omitting the /PS/ separator.
E.g. - <http://world.std.com/~pitman/Papers/Name.html> should be
<http://world.std.com/~pitman/PS/Name.html>. Things are findable
through the PS page, though...
--
Those who do not understand Unix are condemned to reinvent it, poorly.
-- Henry Spencer <http://www.hex.net/~cbbrowne/lsf.html>
········@hex.net - "What have you contributed to free software today?..."
········@news.brownes.org (Christopher B. Browne) writes:
> Definitely some good stuff; the page
> <http://world.std.com/~pitman/Papers/index.html> seems to have some
> problems in its referencing of the Parenthetically Speaking papers,
> omitting the /PS/ separator.
Oh, sigh. These were reported before and I fixed them but not in
the master, which was offline at the time. Now I've overwritten the fixes.
I'll make a point to clean this up later when I'm home and have access
to the master... In the future, comments of this kind should just
be sent to me privately. Thanks.
> E.g. - <http://world.std.com/~pitman/Papers/Name.html> should be
> <http://world.std.com/~pitman/PS/Name.html>. Things are findable
> through the PS page, though...
Right. This is a "cut-and-paste error". I grabbed the URLs from
files in another directory without adjusting them for the motion into
the new file. Bleah.
Kent M Pitman <······@world.std.com> writes:
> I wrote a whole paper on what exception handling was about back in 1990
> pre-Java, citing a number of powerful things about the Lisp error system,
> so I know it's not just sour grapes that Java is popular and Lisp is not.
> Java objectively does not meet a number of the specific objectives
> that I cited in that paper about what Lisp does. Java is a step back
> to languages like CLU which preceded it where the joke was that you had
> to write different functions to add octal numbers than to add decimal
> numbers... typing information can be very useful, and every compiler
> should have a way to provide it and should be willing to use it where
> provided aggressively--however, there's really no excuse I can think of
> for insisting on type declarations. Java would not be any weaker if it,
> like XML, had a mode in which it ran in "loose" mode without requiring
^^^
> such exacting line-up. People who wanted to reject running programs
> that were not "proven" could still do so. But people who wanted to just
> prototype could do so without having to be utterly rigorous on every detail
> when the goal is to write throwaway code no one will ever see...
I assume you mean SML. It doesn't exactly have a loose mode. It will
always automatically try to infer the type of everything you give it
(using type variables if appropriate, so for CAR it would infer
list(alpha)->alpha where alpha is a type variable). It will only
complain when it can't infer something by its inferencing algorithm
(Hindley-Milner) or when you contradict the typing requirements of
something you use. When you tell it yourself what type something is it
still inferes it and complains when the two don't match.
What I find lacking in many "strongly typed" languages is, besides
type inferencing, genericity. Interestingly enough, SML also has that
in a very powerful way through its functors.
--
Lieven Marchand <···@bewoner.dma.be>
If there are aliens, they play Go. -- Lasker
Lieven Marchand <···@bewoner.dma.be> writes:
> Kent M Pitman <······@world.std.com> writes:
>
> > Java would not be any weaker if it,
> > like XML, had a mode in which it ran in "loose" mode without requiring
> ^^^
> > such exacting line-up.
>
> I assume you mean SML. It doesn't exactly have a loose mode.
No, I meant XML.
XML has effectively two levels of document compliance: syntactic and
semantic. Some XML processors require only the former to do useful
things with your document.
But thanks for the info on SML anyway.
From: Lars Marius Garshol
Subject: Re: Implementing multiple return values
Date:
Message-ID: <wk4smwl7o1.fsf@ifi.uio.no>
* Kent M. Pitman
|
| XML has effectively two levels of document compliance: syntactic and
| semantic. Some XML processors require only the former to do useful
| things with your document.
Actually, XML applications usually have three levels of compliance:
well-formed (your syntactic), valid (your semantic) and
application-defined. I suppose one could argue that there is a level
above that which is not verifiable algorithmically (that the contents
make sense and are correct in the sense that they correspond to some
other real-world entity).
I think it would be fair to say that only the last level (the
non-verifiable one) is semantic, and that the requirements for
well-formed and valid documents are both syntactical. The DTD can be
thought of as a BNF grammar operating on the element level, with
additional requirements for attributes (as well some other kinds of
declarations). To me there are no semantics here, just a higher-level
schema language.
In some cases this holds for the application-defined compliance as
well. Many XML applications require things like 'the contents of the
version element must be of the form "integer.integer"', which are, at
least in my book, syntactical requirements.
--Lars M.
Kent M Pitman <······@world.std.com> writes:
> Lieven Marchand <···@bewoner.dma.be> writes:
>
> > Kent M Pitman <······@world.std.com> writes:
> >
> > > Java would not be any weaker if it,
> > > like XML, had a mode in which it ran in "loose" mode without requiring
> > ^^^
> > > such exacting line-up.
> >
> > I assume you mean SML. It doesn't exactly have a loose mode.
>
> No, I meant XML.
>
I hadn't really connected XML with programming languages. But it's an
interesting view of the difference between SGML and XML. Some of the
regulars on the sgml newsgroup find it a weekness in XML that a DTD
and conformance checking are not mandatory. There are parallels there
with the strong typing crowd.
--
Lieven Marchand <···@bewoner.dma.be>
If there are aliens, they play Go. -- Lasker
From: Howard R. Stearns
Subject: Re: Implementing multiple return values
Date:
Message-ID: <3704E490.58BCA6E1@elwood.com>
Dobes Vandermeer wrote:
>
> "Howard R. Stearns" wrote:
> >...
> Yes, and this is the kind of solution I have trouble justifying to
> myself.
Remember the design criterion that I mentioned in my first posting, and
which I think you said you agreed with:
In Eclipse, we want C programmers to be able to view Lisp functions
as if they were normal C functions. ...Also, C callers
don't need to know anything about multiple values unless they want
to use them.
The mechanisms I described work exactly the same way regardless of
whether the function is being called by Lisp code, C code, Lisp code
compiled to C, etc. (This isn't to say that my mechanisms are the only
way to achieve this goal...)
> >...
> > (but at least the two locations referenced are:
> > 1: the static variable that holds the pointer to the buffer, and 2: the
> > buffer itself, which is on the C execution stack and thus should be fast
> > memory.)
>
> What do you mean by "on the C execution stack"?
>
> Do you mean you are storing the returns in a static buffer?
The C macros that set up buffers to receive multiple values do so by
declaring a local C variable, which, given its size and that there is a
pointer to it, ends up being on the C stack. The operating system
usually arranges things such that the C stack is in some sort of fast
memory so that references to it are quick.
Because there are several multiple value receiving buffers that may be
pending, there is a global C variable that points to the "current" such
buffer. Thus, to write something to this buffer, the machinery must
read this global variable, and write to the location (on the C stack)
that it points to.
"Howard R. Stearns" wrote:
>
> Dobes Vandermeer wrote:
> >
> > > (but at least the two locations referenced are:
> > > 1: the static variable that holds the pointer to the buffer, and 2: the
> > > buffer itself, which is on the C execution stack and thus should be fast
> > > memory.)
> >
> > What do you mean by "on the C execution stack"?
>
> The C macros that set up buffers to receive multiple values do so by
> declaring a local C variable, which, given its size and that there is a
> pointer to it, ends up being on the C stack. The operating system
> usually arranges things such that the C stack is in some sort of fast
> memory so that references to it are quick.
>
> Because there are several multiple value receiving buffers that may be
> pending, there is a global C variable that points to the "current" such
> buffer. Thus, to write something to this buffer, the machinery must
> read this global variable, and write to the location (on the C stack)
> that it points to.
OK, that makes sense.
Thanks
Dobes
"Howard R. Stearns" wrote:
>
> Dobes Vandermeer wrote:
> >
> > "Howard R. Stearns" wrote:
> > >...
> > Yes, and this is the kind of solution I have trouble justifying to
> > myself.
>
> Remember the design criterion that I mentioned in my first posting, and
> which I think you said you agreed with:
>
> In Eclipse, we want C programmers to be able to view Lisp functions
> as if they were normal C functions. ...Also, C callers
> don't need to know anything about multiple values unless they want
> to use them.
>
> The mechanisms I described work exactly the same way regardless of
> whether the function is being called by Lisp code, C code, Lisp code
> compiled to C, etc. (This isn't to say that my mechanisms are the only
> way to achieve this goal...)
Wait a minute.. but don't the C functions have to call clValues1() to
return their value? Or does Eclipse wrap C functions up with an
implicit clValues1() call?
CU
Dobes
I think clearly one should optimize that one-value case,
and incur overhead only if multiple-values are wanted
and returned. If I recall correctly, my implementation
had a flag on the call-frame indicating whether the caller
accepted multiple-values. If the caller did not want
multiple-values, then they do nothing special and the return
value comes back in register A0. If they can accept multiple,
they must check the return value in A0, if multiples were returned,
then A0 is a special MV value and the multiples are on the stack.
If not, then A0 will be the single value.
So overhead is really incurred only if multiple values
are acceptable, and if not given, little overhead
is also incurred (a register compare and branch-skip)
On the callee side, if no multiples are returned, no overhead
is incurred, just return the value.
If multiples can be returned, the callee must check the flag
in the call-stack, if it's not-multiple, return the first value
in a0. If it's multiple, store the values on the stack and
put the MV tag in a0.
So the callee only incurs overhead if it HAS multiple values,
and if only a single is wanted, there is very little overhead
(a stack-slot compare and branch-skip)
Passing multiple values "through" a chain of tail-calls
incurs a bit of overhead, as the values get re-copied
onto the stack through the return chain, but this is not
really much overhead, just a bit of a pain to code in assembly
without needing registers that are in-use.
This assumes a call-frame for each call, which could be avoided
in cases where the compiler knows something about what is being called,
which generally includes whether it returns multiples or not.
Note that multiple-values really need to be in the low-level
implementation as part of the language to be efficient.
-Kelly Murray ···@niclos.com
From: Howard R. Stearns
Subject: Re: Implementing multiple return values
Date:
Message-ID: <37054B4C.466AC01F@elwood.com>
I think what you've described looks good, but it hides the cost within
the call-frame creation.
Let me see if I have this straight:
A function being called:
+ Just returns its value in the normal way:
A variable reference being returned is just returned.
A tail call is just a tail call.
+ The function VALUES is the only thing that checks to see if multiple
values are being accumulated, by looking at some flag somewhere:
If values are not being accumulated, it just returns the primary value
in
the normal way.
Otherwise it puts the values someplace and returns a special
indicator that would not ordinarily be seen as a returned Lisp
value.
The caller:
+ If it actually wants multiple values, it sets a flag before the call
and checks the value returned by the call:
If it's the special indicator, than it gets the values from the
buffer.
Otherwise it just uses the one value received.
+ Ordinarilly, the caller just uses or ignores the value returned as
needed. If the caller is looking for one value it must make sure
the flag is clear during the call -- otherwise there's a chance that
the
returned value will be the special indicator. If you're creating a
call
frame, then this flag clearing is just part of the cost of creating
the
frame.
The catch is that the flag has to obey some sort of stack discipline,
which is why you kept it in the call frame. Lets leave the creation of
the call frame out of it for a moment and just think in terms of
clearing the flag.
I think this is the tradeoff: in this approach, the flag is cleared by
the caller, in what I described in an earlier post regarding Eclipse, it
is cleared by the callee.
There are more function call sites than functions, so it's less bulky
to
have the callee clear the flag.
However, there are a lot of places where the caller doesn't even care
about the value, and so it doesn't really have to include the code to
clear the flag before calling. Thus, having the caller do this only
when
it uses the value may result in fewer cycles used.
Because of my preocupation with integration with other languages, I tend
to think in terms of not having a Lisp call frame. I think that this mv
flag and buffers could be done like this:
When multiple values are required, a global flag is NULL.
When someone introduces a multiple value receiving context, a structure
on the stack is set up with a values-buffer and the old flag value. The
flag is set by making it point to this structure. If VALUES is ever
called, and this flag is non-NULL, the values are written to the buffer
that the flag/pointer points to. After the end of the context, the old
flag value is restored. Exit creation forms cache the current
flag/pointer value somewhere so that old values can be reset as the
control stack unwinds.
Anyone (either compiler generated code or hand-written C callers) which
want one value from a Lisp function will have to wrap the call in
something which temporarilly clears flag during the call. Otherwise,
we'd have to check the returned value, and that's bound to be more
tubulent.
I THINK that using this approach, nothing special needs to happen for
passing multiple values back through tail calls.
I'll have to think some more about whether this wrapping around code
generated for things like (setq x (foo)) is cheaper than having foo
unequivocaly write a flag. I'm also not sure I want to explain to C
programmers that they have to wrap something around calls to Lisp
functions.
Am I missing anything else?
This sounds right, similiar to my implementation,
(which I'm recalling from memory from 5-10 years ago..)
In the approach outlined, I can see
some complications in that the "mv-buffer" must be of static size,
so it must be large to accomodate a large number of values,
which "eats up" stack space reducing locality.
You'd have to save/restore the "mv-buffer-ptr" on each call,
except the tail calls, which just inherit the existing value.
struct mvbuf { struct mvbuf *mvptr; /* previous pointer */
void *val[32]; } /* static sized values
struct mvbuf *mvptr; /* MV pointer "register" */
Basically, what you're doing then is having a different "mv stack"
that is managed separate from the call stack.
By integrating this with the call stack as I do,
you eliminate the overhead, and I also can accept any number of
values since they just get pushed on the stack.
But it's true one must than HAVE a call stack frame, because
basically the call-frame-pointer does double-duty as mvbufptr.
One point though is after thinking about it,
I recall that there isn't any
extra overhead for setting/clearing the flag, because a call-frame
is created with a call-frame-tag, which can be either a mv-tag or
one-value-tag. These special tags are used by the GC and debugger
to identify open call-frames, which have uninitialized random
values within them.
To compile (multiple-value-setq (a b) (foo 1))
(decf SP call-frame-size-1) ;; allocate call-frame on stack minus tag
(push mv-call-tagl) ;; mark call-frame on stack.
(push 1) ;; push arg
(activate-call-1 'foo) ;; call foo with 1-arg
(if (eq A0 mv-tag) ;; check for <2 values elided.
then (set a = (pop)) (set b = (pop)) (pop-rest)
else (set a = A0) (set b = nil)
)
whereas to compile (set a (foo 1))
(decf SP call-frame-size-1) ;; allocate call-frame on stack minus tag
(push one-value-call-tag) ;; mark call-frame on stack.
(push 1)
(activate-call-1 'foo)
(set a = A0)
But if #'foo doesn't really need a call-frame because perhaps
it is a leaf-call (doesn't call other functions) and doesn't use
any registers that need saving, etc. you could get away without
a call-frame, and put the arguments in registers instead of on
the stack.
(set A0 = 1)
(jsb-to #'foo)
(set a = A0)
A faster implementation strategy which I didn't use
is to always compile the fast-call, and leave it to the callee
to build the call-frame if needed, which I'm sure all C compilers do.
In this case dealing with multiple-values incurs overhead
because it is incurring the call-frame machinery when it may
not be needed. But this also leads to having "live" values
kept in registers when a call occurs. In my implementation,
that was never the case, so I could interrupt and perform a GC
at every function call without resorting to "conservative"
garbage collection of random valued register contents,
and the call-frame-tag also identified random-valued stack contents.
-Kelly Murray ···@niclos.com
Howard R. Stearns wrote:
>
> I think what you've described looks good, but it hides the cost within
> the call-frame creation.
>
> Let me see if I have this straight:
>
> A function being called:
> + Just returns its value in the normal way:
> A variable reference being returned is just returned.
> A tail call is just a tail call.
> + The function VALUES is the only thing that checks to see if multiple
> values are being accumulated, by looking at some flag somewhere:
> If values are not being accumulated, it just returns the primary value
> in
> the normal way.
> Otherwise it puts the values someplace and returns a special
> indicator that would not ordinarily be seen as a returned Lisp
> value.
>
> The caller:
> + If it actually wants multiple values, it sets a flag before the call
> and checks the value returned by the call:
> If it's the special indicator, than it gets the values from the
> buffer.
> Otherwise it just uses the one value received.
> + Ordinarilly, the caller just uses or ignores the value returned as
> needed. If the caller is looking for one value it must make sure
> the flag is clear during the call -- otherwise there's a chance that
> the
> returned value will be the special indicator. If you're creating a
> call
> frame, then this flag clearing is just part of the cost of creating
> the
> frame.
>
> The catch is that the flag has to obey some sort of stack discipline,
> which is why you kept it in the call frame. Lets leave the creation of
> the call frame out of it for a moment and just think in terms of
> clearing the flag.
>
> I think this is the tradeoff: in this approach, the flag is cleared by
> the caller, in what I described in an earlier post regarding Eclipse, it
> is cleared by the callee.
>
> There are more function call sites than functions, so it's less bulky
> to
> have the callee clear the flag.
>
> However, there are a lot of places where the caller doesn't even care
> about the value, and so it doesn't really have to include the code to
> clear the flag before calling. Thus, having the caller do this only
> when
> it uses the value may result in fewer cycles used.
>
> Because of my preocupation with integration with other languages, I tend
> to think in terms of not having a Lisp call frame. I think that this mv
> flag and buffers could be done like this:
>
> When multiple values are required, a global flag is NULL.
>
> When someone introduces a multiple value receiving context, a structure
> on the stack is set up with a values-buffer and the old flag value. The
> flag is set by making it point to this structure. If VALUES is ever
> called, and this flag is non-NULL, the values are written to the buffer
> that the flag/pointer points to. After the end of the context, the old
> flag value is restored. Exit creation forms cache the current
> flag/pointer value somewhere so that old values can be reset as the
> control stack unwinds.
>
> Anyone (either compiler generated code or hand-written C callers) which
> want one value from a Lisp function will have to wrap the call in
> something which temporarilly clears flag during the call. Otherwise,
> we'd have to check the returned value, and that's bound to be more
> tubulent.
>
> I THINK that using this approach, nothing special needs to happen for
> passing multiple values back through tail calls.
>
> I'll have to think some more about whether this wrapping around code
> generated for things like (setq x (foo)) is cheaper than having foo
> unequivocaly write a flag. I'm also not sure I want to explain to C
> programmers that they have to wrap something around calls to Lisp
> functions.
>
> Am I missing anything else?