Question on mutability of argument lists

Question on mutability of argument lists

[Niels Möller]

Hi,

I discovered r7rs thanks to the recent guile release announcement. I
have one question (which likely applies also to earlier revisions). Not
sure what the right forum is, but I hope some of the guile people are
familiar with these things and if maybe even can push for some
clarification of the spec if needed. I tried mailing to
scheme-reports-owner@scheme-reports.org, but that list seems to be
member's only).

When specifying the use of rest arguments for procedures (r7rs, sec
4.1.4), it seems to imply that the passed argument list is mutable? This
is convenient in some ways, e.g., I think the following definition of
the list procedure should be correct

  (define (list . args) args) 

However, for a natural implementation which evaluates arguments and
conses the results up to a list, this seems to require an extra copy of
the argument list, after all values are evaluated and before the list is
bound to the rest parameter. To see why, assume that evaluation of one
of the arguments captures its continuation and returns several times. If
this isn't the first argument evaluated, without the extra copying, one
gets several calls to the procedure with the rest argument sharing
structure, and if the shared part is mutated, things go bad. And since
I'd expect that the vast majority of function calls with rest arguments
to *not* need any mutability of the argument list, this extra copying
seems like an undesirable overhead.

On the other hand, if the argument is specified as immutable, then no
copying is needed in the common case (as far as I understand, consing up
the evaluated arguments will give the correct results no matter how many
times the evaluation of a particular argument returns), but instead, the
implementation of procedures like list must explicitly construct a
new mutable copy of the argument list.

It's not obvious if the general description "All objects created by the
other procedures listed in this report are mutable." (sec 3.4) applies
to the constructed argument lists, so if argument lists for rest
parameters really are intended to be mutable, then I think that could be
made clearer.

I guess the formal semantics section ought to answer the question on
whether or not one can get shared structure in argument lists in case
evaluation of an argument returns multiple times, but I haven't tried to
figure that out...

Regards,
/Niels Möller

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

Re: Question on mutability of argument lists

[Marco Maggi]

Niels Möller wrote:
> When specifying  the use of rest  arguments for procedures
> (r7rs,  sec 4.1.4),  it  seems to  imply  that the  passed
> argument list is mutable?

Yes, because it states "the  sequence of actual arguments is
converted  into a  newly  allocated list,  and  the list  is
stored in  a fresh  location" and "The  value stored  in the
binding of the last variable will be a newly allocated list"
(PDF  version,   page  13,  right  column,   description  of
formals); it  is new at  every function  call, so we  can do
everything with it.

> This  is  convenient  in  some ways,  e.g.,  I  think  the
> following  definition  of  the list  procedure  should  be
> correct

>   (define (list . args) args)

Yes.  Vicare defines it as:

   (define list (lambda x x))

> However,  for  a  natural implementation  which  evaluates
> arguments and conses the results  up to a list, this seems
> to require an  extra copy of the argument  list, after all
> values are evaluated  and before the list is  bound to the
> rest parameter.

Yes,  but it  depends  on  what is  "natural"  for you.   In
Vicare, when  calling a  Scheme function, all  the arguments
are pushed on the Scheme stack segment (similar to calling a
C  function) and  then the  function is  called; the  callee
takes  the leftover  arguments and  puts them  into a  newly
allocated  list.    In  this  implementation  there   is  no
duplication of  list's spine (with heap  memory allocation),
just use of stack slots.

> To see why, assume that evaluation of one of the arguments
> captures its continuation and returns several times.  this
> isn't  the first  argument  evaluated,  without the  extra
> copying, one gets several calls  to the procedure with the
> rest argument sharing structure, and if the shared part is
> mutated, things go bad.

Yes it would go that way.   But the standard mandates that a
new list must be built at every call and stored into a fresh
location at every call; no shared structure is allowed.

HTH
-- 
"Now feel the funk blast!"
Rage Against the Machine - "Calm like a bomb"

Re: Question on mutability of argument lists

[Mark H Weaver]

Marco Maggi <marco.maggi-ipsu@poste.it> writes:

> Niels Möller wrote:
>> However,  for  a  natural implementation  which  evaluates
>> arguments and conses the results  up to a list, this seems
>> to require an  extra copy of the argument  list, after all
>> values are evaluated  and before the list is  bound to the
>> rest parameter.
>
> Yes,  but it  depends  on  what is  "natural"  for you.   In
> Vicare, when  calling a  Scheme function, all  the arguments
> are pushed on the Scheme stack segment (similar to calling a
> C  function) and  then the  function is  called; the  callee
> takes  the leftover  arguments and  puts them  into a  newly
> allocated  list.

Indeed, and Guile 2 also does this in compiled code.

     Mark

Re: Question on mutability of argument lists

[Niels Möller]

Mark H Weaver <mhw@netris.org> writes:

> Marco Maggi <marco.maggi-ipsu@poste.it> writes:
>
>> Yes,  but it  depends  on  what is  "natural"  for you.   In
>> Vicare, when  calling a  Scheme function, all  the arguments
>> are pushed on the Scheme stack segment (similar to calling a
>> C  function) and  then the  function is  called; the  callee
>> takes  the leftover  arguments and  puts them  into a  newly
>> allocated  list.
>
> Indeed, and Guile 2 also does this in compiled code.

I see. So the allocation of the new list is the responsibility of the
function prologue of functions defined with rest arguments.

Thanks for the explanation.

And somthing similar could be done even if the calling convention is the
"natural" one, that the caller conses the arguments onto a list as they
are evaluated, and passes that list to the implementation of the
procedure. The function prologue in the callee would then extract
arguments from that list, and only in the case that the function is
defined with a rest argument, the prologue calls list-copy. And the
compiler could even omit that list-copy in cases where it can infer that
the list cannot be subject to any mutations.

(It's long time since I played with lisp/scheme implementation, but then
I considered a calling convention where each procedure (and
continuation) would have two entry points, one with a single argument
passed in a register, and a second entry point where a pointer to an
argument list is passed in that register. The first entry point would be
used in the common case that there's a single argument or a single
return value. While the second entry point would be used when the number
of arguments is different from 1. Depending on number of arguments
accepted, one or the other of the entry points may point directly to
code raising an error).

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

[OT] Re: Question on mutability of argument lists

[Marco Maggi]

Niels Möller wrote:
> And somthing similar could be done even if the calling convention is the
> "natural" one, that the caller conses the arguments onto a list as they
> are evaluated, and passes that list to the implementation of the
> procedure. The function prologue in the callee would then extract
> arguments from that list, and only in the case that the function is
> defined with a rest argument, the prologue calls list-copy. And the
> compiler could even omit that list-copy in cases where it can infer that
> the list cannot be subject to any mutations.

Yes.  In some sense the  caller would use the arguments list
as "Scheme stack".

> (It's long time since I played with lisp/scheme implementation, but then
> I considered a calling convention where each procedure (and
> continuation) would have two entry points, one with a single argument
> passed in a register, and a second entry point where a pointer to an
> argument list is passed in that register. The first entry point would be
> used in the common case that there's a single argument or a single
> return value. While the second entry point would be used when the number
> of arguments is different from 1. Depending on number of arguments
> accepted, one or the other of the entry points may point directly to
> code raising an error).

Mh... I have very few functions accepting a single argument.
How  would  one  implement  continuations  when  a  function
argument is in a register  (rather than on the Scheme stack,
however implemented)?  In a complex way I presume.

  Something  similar can  be done  for return  values[1]; in
Vicare every function call site has 2 return points: one for
single return value; the other for 0, 2, more return values.
One return  point goes  on with  the computation,  the other
raises an exception.

  If the callee  returns a single value: it just  does a RET
to the address that was pushed  on the stack by CALL.  If it
returns multiple values: it  computes the other return point
address which  is at  a fixed  offset from  the single-value
return point.  It is complex to setup this thing...


[1]  Ashley and  Dybvig.   "An  Efficient Implementation  of
Multiple Return Values in  Scheme".  Proceedings of the 1994
ACM Conference on Lisp  and Functional Programming, 140-149,
Orlando, June 1994.
-- 
"Now feel the funk blast!"
Rage Against the Machine - "Calm like a bomb"

[OT] Re: Question on mutability of argument lists

[Niels Möller]

Marco Maggi <marco.maggi-ipsu@poste.it> writes:

> Mh... I have very few functions accepting a single argument.

I think there are lots of standard functions with a single argument,
including many accessor functions, predicates, and conversion functions.
And some functions which accept a variable number of arguments have
special behaviour for exactly one argument. 

Can't say if it really is a worthwhile optimization with a separate
entry point, but it is a nice symmetry given that the same optimization
*is* worthwhile for continuations/return addresses.

> How  would  one  implement  continuations  when  a  function
> argument is in a register  (rather than on the Scheme stack,
> however implemented)?  In a complex way I presume.

I planned to have no stack. Instead all activation records would be
allocated on the heap. With inspiration from Appel's "Compiling with
continuations", which describes a compiler for Standard ML. If I
remember the reported benchmarks correctly, it typically allocated one
word of storage for every 5 machine instructions executed, and it still
had reasonably low overhead from gc.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

Re: [OT] Re: Question on mutability of argument lists

[Andy Wingo]

On Thu 20 Mar 2014 11:06, Marco Maggi <marco.maggi-ipsu@poste.it> writes:

>   Something  similar can  be done  for return  values[1]; in
> Vicare every function call site has 2 return points: one for
> single return value; the other for 0, 2, more return values.
> One return  point goes  on with  the computation,  the other
> raises an exception.
>
> [1]  Ashley and  Dybvig.   "An  Efficient Implementation  of
> Multiple Return Values in  Scheme".  Proceedings of the 1994
> ACM Conference on Lisp  and Functional Programming, 140-149,
> Orlando, June 1994.

Incidentally I think this is not such a nice approach -- multiple-value
returns kill the return-branch buffer.  I suspect this is a very 1994
strategy.  For example, it's common to call a function and discard its
arguments.  This is trivial with a single return location.  With MV you
miss the return-branch buffer and you still play jump games.  The
single-value return is also very easy -- just check the
number-of-return-values register (or, if values are on the stack, check
the stack pointer) and branch to error if you didn't get the right
number.  Branch prediction helps here.

Andy
-- 
http://wingolog.org/