Re: [VM] Tail recursion and multiple values

[Andy Wingo <wingo@pobox.com>]

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/