[VM] Tail recursion and multiple values

[VM] Tail recursion and multiple values

[Ludovic Courtès]

Hello!

Use of multiple values breaks tail recursion in VM-compiled code:

  (let loop ((x 1000000))
    (and (> x 0)
         (call-with-values
             (lambda ()
               (values (1+ x) (1- x)))
           (lambda (next prev)
             (loop prev)))))

This example yields a stack overflow with the VM, whereas tail recursion
is correctly handled by the interpreter.  Tail recursion for
`call-with-values' is mandated by R5RS (info "(r5rs)Proper tail
recursion"):

  Certain built-in procedures are also required to perform tail calls.
  The first argument passed to `apply' and to
  `call-with-current-continuation', and the second argument passed to
  `call-with-values', must be called via a tail call.  Similarly, `eval'
  must evaluate its argument as if it were in tail position within the
  `eval' procedure.

I'll look into it and report back if no one beats me.  ;-)

Thanks,
Ludo'.

Re: [VM] Tail recursion and multiple values

[Ludovic Courtès]

ludo@gnu.org (Ludovic Courtès) writes:

> Use of multiple values breaks tail recursion in VM-compiled code:
> 
>   (let loop ((x 1000000))
>     (and (> x 0)
>          (call-with-values
>              (lambda ()
>                (values (1+ x) (1- x)))
>            (lambda (next prev)
>              (loop prev)))))

Actually no: it works with VM-compiled code, but it breaks when using
Guile-VM with `,o interp #t' (which appears to be the default, except at
the REPL).

In this case, `loop' is an interpreter procedure while
`call-with-values' is a program.  It's the implementation of `goto/args'
in this particular case that seems to break tail recursion:

  if (!SCM_FALSEP (scm_procedure_p (x)))
    {
      POP_LIST (nargs);
      SYNC_REGISTER ();
      sp[-1] = scm_apply (x, sp[0], SCM_EOL);

The `scm_apply ()' call introduces a new stack frame instead of re-using
the current one.

At this point I'm not sure how to fix it.  We need better integration of
calls from the VM to subrs/procedures anyway (notably removing
`POP_LIST ()' and argument consing before subr/procedure calls!) so
probably we could postpone this issue until then.  Andy?

Thanks,
Ludo'.

Re: [VM] Tail recursion and multiple values

[Andy Wingo]

Hey Ludo!

On Sat 28 Feb 2009 15:45, ludo@gnu.org (Ludovic Courtès) writes:

> ludo@gnu.org (Ludovic Courtès) writes:
>
>> Use of multiple values breaks tail recursion in VM-compiled code:
>> 
>>   (let loop ((x 1000000))
>>     (and (> x 0)
>>          (call-with-values
>>              (lambda ()
>>                (values (1+ x) (1- x)))
>>            (lambda (next prev)
>>              (loop prev)))))
>
> Actually no: it works with VM-compiled code, but it breaks when using
> Guile-VM with `,o interp #t' (which appears to be the default, except at
> the REPL).

This is a misunderstanding.

Last things first: code is not run through the VM unless it is compiled.
The REPL in the vm branch compiles expressions by default, though it has
an option to use the interpreter instead (,option interp #t).

So if you are running this code via e.g. guile -s foo.scm, the code in
foo.scm is evaluated with the interpreter. Sometimes this is faster, in
that the compiler doesn't have to be loaded up -- see the recent numbers
that I posted. It depends on what foo.scm does.

> In this case, `loop' is an interpreter procedure while
> `call-with-values' is a program.

Just as you cannot have tail recursion between interpreted code and
primitive (C-compiled) code, you cannot have tail recursion between
VM and interpreted (or primitive) code.

Multiple values actually doesn't have anything to do with this, except
for one thing -- r4rs.scm defines call-with-values like this:

    (define (call-with-values producer consumer)
      (@call-with-values producer consumer))

@call-with-values is a primitive understood to the interpreter. In this
way the interpreter preserves tail recursion, not only for calls to
call-with-values, but also (apply call-with-values ...). Indeed, call/cc
and even `apply' have similar definitions in this file.

So what I really mean to say is:

  1) It is expected that you don't have tail recursion between
     interpreted and VM code.

  2) This particular problem manifests itself in that call-with-values
     is VM code (when r5rs.scm is compiled).

  3) The strategy used by r5rs.scm is actually not bad, as it handles
     the `apply' case well.

If we really want to preserve tail recursion in this case, we could add
hacks to the interpreter, e.g. to recognize VM programs that are eq? to
call-with-values as being the same as @call-with-values; but the
interpreter already has enough hacks. Better to make loading the
compiler faster, so we can just compile by default.

Cheers,

Andy
-- 
http://wingolog.org/

Re: [VM] Tail recursion and multiple values

[Ludovic Courtès]

Hello!

Andy Wingo <wingo@pobox.com> writes:

> On Sat 28 Feb 2009 15:45, ludo@gnu.org (Ludovic Courtès) writes:

>> Actually no: it works with VM-compiled code, but it breaks when using
>> Guile-VM with `,o interp #t' (which appears to be the default, except at
>> the REPL).
>
> This is a misunderstanding.
>
> Last things first: code is not run through the VM unless it is compiled.
> The REPL in the vm branch compiles expressions by default, though it has
> an option to use the interpreter instead (,option interp #t).

Understood.

> So what I really mean to say is:
>
>   1) It is expected that you don't have tail recursion between
>      interpreted and VM code.
>
>   2) This particular problem manifests itself in that call-with-values
>      is VM code (when r5rs.scm is compiled).

(The latter is what I meant to say in my message.)

As for (1), I'm unsure.  The issue is that as long as running code with
the interpreter is the default, people may hit this kind of problem,
which is, well, problematic.  Now, I have no idea how this could be
solved without resorting to dirty hacks such as the one you suggested.

As a side note, I think it makes sense to keep the interpreter as the
default when evaluating `.scm' files since compilation can be costly and
may not pay off (e.g., if the compiler performs smart optimizations,
and/or the program is short-lived).

Thanks,
Ludo'.

Re: [VM] Tail recursion and multiple values

[Andy Wingo]

Heya,

On Mon 02 Mar 2009 00:48, ludo@gnu.org (Ludovic Courtès) writes:

>>   1) It is expected that you don't have tail recursion between
>>      interpreted and VM code.
>>
>>   2) This particular problem manifests itself in that call-with-values
>>      is VM code (when r5rs.scm is compiled).
>
> (The latter is what I meant to say in my message.)
>
> As for (1), I'm unsure.  The issue is that as long as running code with
> the interpreter is the default, people may hit this kind of problem,
> which is, well, problematic.  Now, I have no idea how this could be
> solved without resorting to dirty hacks such as the one you suggested.

Yeah. It is certainly a counterintuitive situation. The compiler
recognizes both call-with-values and @call-with-values, so we could just
not compile call-with-values; less nasty, but still nasty, and penalizes
the vm in the (apply call-with-values ...) case.

> As a side note, I think it makes sense to keep the interpreter as the
> default when evaluating `.scm' files

Sure, for now -- or we could do what python does, and automatically
create .go files as needed (and if possible). Then it would certainly
pay off over time, and the compilation time would probably be a wash
because in that case the .scm probably isn't even in the disk cache.

> the program is short-lived

This would be the normal case

> if the compiler performs smart optimizations,

Hahaahaha!

More seriously, I think that the bar for including optimizations in the
normal compilation path will be if they actually speed up the compiler
as well (since the compiler is self-compiled).

Cheers,

Andy
-- 
http://wingolog.org/

Re: [VM] Tail recursion and multiple values

[Ludovic Courtès]

Hello!

Andy Wingo <wingo@pobox.com> writes:

> On Mon 02 Mar 2009 00:48, ludo@gnu.org (Ludovic Courtès) writes:

>> As for (1), I'm unsure.  The issue is that as long as running code with
>> the interpreter is the default, people may hit this kind of problem,
>> which is, well, problematic.  Now, I have no idea how this could be
>> solved without resorting to dirty hacks such as the one you suggested.
>
> Yeah. It is certainly a counterintuitive situation. The compiler
> recognizes both call-with-values and @call-with-values, so we could just
> not compile call-with-values; less nasty, but still nasty, and penalizes
> the vm in the (apply call-with-values ...) case.

Yes, but OTOH that's an unusual case, no?

>> As a side note, I think it makes sense to keep the interpreter as the
>> default when evaluating `.scm' files
>
> Sure, for now -- or we could do what python does, and automatically
> create .go files as needed (and if possible). Then it would certainly
> pay off over time, and the compilation time would probably be a wash
> because in that case the .scm probably isn't even in the disk cache.

That's one possibility.  I think I prefer having to compile things
explicitly, though.

>> if the compiler performs smart optimizations,
>
> Hahaahaha!

To put it another way, the compiler may not be designed from the ground
up to minimize compilation time, whereas the interpreter (supposedly)
tries to achieve this.

> More seriously, I think that the bar for including optimizations in the
> normal compilation path will be if they actually speed up the compiler
> as well (since the compiler is self-compiled).

Hey, walking in Dybvig's footsteps?  ;-)

http://www.cs.indiana.edu/~dyb/pubs/hocs.pdf

Thanks,
Ludo'.

Re: [VM] Tail recursion and multiple values

[Andy Wingo]

Howdy howdy,

On Mon 02 Mar 2009 22:55, ludo@gnu.org (Ludovic Courtès) writes:

> Andy Wingo <wingo@pobox.com> writes:
>
>> The compiler
>> recognizes both call-with-values and @call-with-values, so we could just
>> not compile call-with-values; less nasty, but still nasty, and penalizes
>> the vm in the (apply call-with-values ...) case.
>
> Yes, but OTOH that's an unusual case, no?

Yes, it is.

>>> As a side note, I think it makes sense to keep the interpreter as the
>>> default when evaluating `.scm' files
>>
>> Sure, for now -- or we could do what python does, and automatically
>> create .go files as needed (and if possible). Then it would certainly
>> pay off over time, and the compilation time would probably be a wash
>> because in that case the .scm probably isn't even in the disk cache.
>
> I prefer having to compile things explicitly, though.

I prefer magic, if magic works ;-)

The compiler is almost to the point that it can replace the interpreter,
semantically. What is needed is to read and compile toplevel definitions
one at a time, so we can e.g. change the reader, or the other dynamic
things that people expect. Then if that's the case, then we can just hit
the user with the one-time cost, for the long-term benefit.

This would also allow us to move closer to having a single codepath,
which has its benefits, broader tail-recursion among them.

>>> if the compiler performs smart optimizations,
>>
>> Hahaahaha!
>
> To put it another way, the compiler may not be designed from the ground
> up to minimize compilation time, whereas the interpreter (supposedly)
> tries to achieve this.

I understand. I wish that we lived in a world in which (timewise)
compilation + running == interpretation, so we could just do the former,
but that is not yet our world. However both Chez and SBCL have the
former model, so in a software engineering sense it might be worth it,
in some future in which the compiler is faster.

So in that sense I'd really like to make sure that the compiler only
gets faster.

> Hey, walking in Dybvig's footsteps?  ;-)

I can only hope to do so ;-) That guy is smart!

Cheers,

Andy
-- 
http://wingolog.org/

Re: [VM] Tail recursion and multiple values

[Andreas Rottmann]

Andy Wingo <wingo@pobox.com> writes:

> I understand. I wish that we lived in a world in which (timewise)
> compilation + running == interpretation, so we could just do the former,
> but that is not yet our world. However both Chez and SBCL have the
> former model, so in a software engineering sense it might be worth it,
> in some future in which the compiler is faster.
>
Ikarus does so as well (i.e. having no interpreter).

Regards, Rotty

Re: [VM] Tail recursion and multiple values

[Eduardo Cavazos]

Ludovic Courtès writes:

>> Hey, walking in Dybvig's footsteps?  ;-)

Andy Wingo wrote:

> I can only hope to do so ;-) That guy is smart!

For those of us not lucky enough to attend his lectures at Indiana 
University, here's a good video presentation by Kent on the subject of 
macros:

     http://video.google.com/videoplay?docid=-6899972066795135270

Ed

Re: [VM] Tail recursion and multiple values

[Ludovic Courtès]

Hello,

Andy Wingo <wingo@pobox.com> writes:

> The compiler is almost to the point that it can replace the interpreter,
> semantically. What is needed is to read and compile toplevel definitions
> one at a time, so we can e.g. change the reader, or the other dynamic
> things that people expect. Then if that's the case, then we can just hit
> the user with the one-time cost, for the long-term benefit.
>
> This would also allow us to move closer to having a single codepath,
> which has its benefits, broader tail-recursion among them.

Yes, that's a significant benefit.  But I think we can only afford it
once the compiler is sufficiently fast.  IMO Guile targets short-lived
programs (aka. "scripts") more than, say, Ikarus, which is why
"compilation" (be it actual compilation or bare memoization) time
matters.

Thanks,
Ludo'.

Re: [VM] Tail recursion and multiple values

[Clinton Ebadi]

ludo@gnu.org (Ludovic Courtès) writes:

> Hello,
>
> Andy Wingo <wingo@pobox.com> writes:
>
>> The compiler is almost to the point that it can replace the interpreter,
>> semantically. What is needed is to read and compile toplevel definitions
>> one at a time, so we can e.g. change the reader, or the other dynamic
>> things that people expect. Then if that's the case, then we can just hit
>> the user with the one-time cost, for the long-term benefit.
>>
>> This would also allow us to move closer to having a single codepath,
>> which has its benefits, broader tail-recursion among them.
>
> Yes, that's a significant benefit.  But I think we can only afford it
> once the compiler is sufficiently fast.  IMO Guile targets short-lived
> programs (aka. "scripts") more than, say, Ikarus, which is why
> "compilation" (be it actual compilation or bare memoization) time
> matters.

Usually the scripts are still mostly static on disk--you only have to
compile automatically once per change to the source scheme file and so
if the script is ever used more than once there should be benefits (mmap
the .go and go!).

-- 
<captain_krunk> ntk is currently using "telnet fyodor 25" to send email