Eval, tail calls, (current-module), and backward compatibility

Eval, tail calls, (current-module), and backward compatibility

[Mark H Weaver]

Hello all,

There's a problem with Guile's `eval'.  It doesn't do proper tail
recursion as mandated by R5RS et al, and unfortunately we can't fix this
without changing its behavior in a potentially incompatible way.

The problem is that `eval' uses dynamic-wind to temporarily set
(current-module) during the dynamic extent of the expansion and
evaluation of its form.  Ideally, it should set (current-module) only
during expansion, _not_ during evaluation.

It is worthwhile to consider what (current-module) is for, and how it
should be used.  This seems to be an area of great confusion.

(current-module) should be relevant only at the beginning of
macro-expansion: before any program transformations are performed,
(current-module) is "baked" into every symbol of the top-level form.
(psyntax actually does this lazily, but the effect is the same).

After that, (current-module) should be completely irrelevant to the rest
of compilation and evaluation.  After expansion has begun, the expanded
code is in general a patchwork of code fragments from many different
modules, and thus it no longer makes sense to talk about "the current
module".

Instead, the compiler looks at the modules that were baked into the
identifier.  For example, each top-level variable reference refers to
the module that was baked into its corresponding source identifier
before macro expansion.

It sometimes makes sense for the user to (set-current-module <module>).
This can be done within an REPL for example.  It can also be done in a
compiled file within (eval-when (compile) ...), which will cause
subsequent top-level forms to be expanded within the newly changed
(current-module).  This is implicitly done by `define-module'.

Pretty much the only proper use of (current-module) is to implement
REPLs and things of that sort.  It has nothing to do with the code that
is currently running.  It doesn't even really have to do with the code
that is currently being expanded, so it's almost never the right thing
to look at within procedural macros.

* * * * *

Can we fix this?

Ideally, I think that `eval' should set (current-module) during
expansion, but _not_ during evaluation.  Then it can be properly tail
recursive.  However, some code out there might depend on the existing
behavior, so I guess we can't change this, at least not in 2.0.  Bummer.

  (BTW, `local-eval' accepts a module as its second argument, and
   conforms to the R5RS requirements of `eval', so it can serve as a
   proper replacement for Guile's broken `eval')

Similarly, (compile '<expr> #:env <module>) should set (current-module)
during expansion but _not_ during evaluation.  Then it can be properly
tail recursive and have cleaner semantics.  It might not be too late to
fix this in 2.0.

  (Note that `local-compile' also conforms to the R5RS requirements of
   `eval', so can also serve as a proper `eval' replacement)

What do other people think?

    Best,
     Mark

Re: Eval, tail calls, (current-module), and backward compatibility

[David Kastrup]

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

> (current-module) should be relevant only at the beginning of
> macro-expansion: before any program transformations are performed,
> (current-module) is "baked" into every symbol of the top-level form.
> (psyntax actually does this lazily, but the effect is the same).
>
> After that, (current-module) should be completely irrelevant to the rest
> of compilation and evaluation.

It isn't if you call it in the code.  Personally, I am not sure that it
should reflect the second argument of eval if that is different from the
current module in which eval has been called.

Does R5RS have an opinion on modules and eval?

> Ideally, I think that `eval' should set (current-module) during
> expansion, but _not_ during evaluation.  Then it can be properly tail
> recursive.  However, some code out there might depend on the existing
> behavior, so I guess we can't change this, at least not in 2.0.
> Bummer.

I am not sure.  If you rebind current-module itself during expansion,
you might be able to retain the currently visible behavior while being
in tail-call position during execution.  Of course, if any user meddles
with the value of current-module other than just calling it, he is going
to be in for surprises.

-- 
David Kastrup

Re: Eval, tail calls, (current-module), and backward compatibility

[Mark H Weaver]

David Kastrup <dak@gnu.org> writes:

> Mark H Weaver <mhw@netris.org> writes:
>
>> (current-module) should be relevant only at the beginning of
>> macro-expansion: before any program transformations are performed,
>> (current-module) is "baked" into every symbol of the top-level form.
>> (psyntax actually does this lazily, but the effect is the same).
>>
>> After that, (current-module) should be completely irrelevant to the rest
>> of compilation and evaluation.
>
> It isn't if you call it in the code.

Indeed, and that's potentially a problem.

> Personally, I am not sure that it
> should reflect the second argument of eval if that is different from the
> current module in which eval has been called.
>
> Does R5RS have an opinion on modules and eval?

The R5RS has no module system, but it does mandate that `eval' requires
a second parameter: the "environment-specifier".  It says almost nothing
about these environment-specifiers other than to mandate a few standard
procedures that must return them: (scheme-report-environment <version>),
(null-environment <version>), and optionally (interactive-environment).
<version> is the exact integer <n> in R<n>RS, e.g. 5 means the R5RS.

The R5RS has no notion of a user-specified "current environment".
Indeed, there is no need for such a concept if it must always be passed
as an explicit parameter to `eval'.  Therefore, there's no need to
save/restore the current environment (or anything like it) in the R5RS.

The fact that the R5RS requires `eval' to be properly tail-recursive
implies that it cannot do _anything_ after evaluation of the provided
expression, because the continuation of the expression must be
semantically equivalent to the continuation of `eval' itself.

Therefore, the R5RS leaves no possible way for a complaint `eval' to
restore the previous value of (current-module) after evaluation.
Indeed, this is prohibited at a semantic level.

      Mark

Re: Eval, tail calls, (current-module), and backward compatibility

[Andy Wingo]

On Tue 17 Jan 2012 22:02, Mark H Weaver <mhw@netris.org> writes:

> Therefore, the R5RS leaves no possible way for a complaint `eval' to
> restore the previous value of (current-module) after evaluation.
> Indeed, this is prohibited at a semantic level.

FWIW, Racket circumvents this problem nicely, with what they call
"continuation marks".  We might be able to reuse their strategy in our
with-fluids implementation.

Andy
-- 
http://wingolog.org/

Re: Eval, tail calls, (current-module), and backward compatibility

[Mark H Weaver]

Andy Wingo <wingo@pobox.com> writes:

> On Tue 17 Jan 2012 22:02, Mark H Weaver <mhw@netris.org> writes:
>
>> Therefore, the R5RS leaves no possible way for a complaint `eval' to
>> restore the previous value of (current-module) after evaluation.
>> Indeed, this is prohibited at a semantic level.
>
> FWIW, Racket circumvents this problem nicely, with what they call
> "continuation marks".  We might be able to reuse their strategy in our
> with-fluids implementation.

I don't see how continuation marks could solve this problem.  They avoid
adding more frames to the stack, but that's not enough.  The R5RS says:

  A Scheme implementation is properly tail-recursive if it supports an
  unbounded number of active tail calls.  A call is _active_ if the
  called procedure may still return.

Therefore, even if you save the old value of (current-module) cleverly
somewhere other than the stack, these old values would still in general
use O(n) space, where N is the number of active calls to `eval'.

On the other hand, if `eval' stores the saved (current-module) within
the continuation outside of `eval', overwriting whatever value might
already be stored there (thus avoiding the O(n) problem), this would be
incorrect, because that outer continuation might have been stored
somewhere, and it should _not_ restore (current-module).

Fundamentally, if `eval' wishes to restore the former (current-module)
after evaluation of the expression, then the inner continuation of the
expression _must_ be semantically different than `eval's outer
continuation: the inner one _must_ restore (current-module), and the
outer one _must_ _not_ modify (current-module).

Or am I missing something?

    Thanks,
      Mark

Re: Eval, tail calls, (current-module), and backward compatibility

[Andy Wingo]

On Wed 18 Jan 2012 20:58, Mark H Weaver <mhw@netris.org> writes:

> Andy Wingo <wingo@pobox.com> writes:
>
>> "continuation marks".  We might be able to reuse their strategy in our
>> with-fluids implementation.
>
> I don't see how continuation marks could solve this problem.  They avoid
> adding more frames to the stack, but that's not enough.  The R5RS says:
>
>   A Scheme implementation is properly tail-recursive if it supports an
>   unbounded number of active tail calls.  A call is _active_ if the
>   called procedure may still return.
>
> Therefore, even if you save the old value of (current-module) cleverly
> somewhere other than the stack, these old values would still in general
> use O(n) space, where N is the number of active calls to `eval'.

There's the rub!  I believe that the way this works is to consider every
continuation as having "marks" associated with them.  For example in

  (+ (eval '(eval 'bar mod2) mod1))

the continuation may be written as

  (+ [ ])

where [ ] signifies a hole.  (Consider it to be a previous frame
pointer, coupled with a return address, if you like.)

(current-module) looks at the 'module continuation mark (or equivalent)
on a continuation.  Call-with-continuation-marks does create a new
continuation to pop marks, but only if marks are not set on that
continuation already.  If the continuation already has marks,
call-with-continuation-marks just adds/sets marks on the existing
continuation, instead of creating a new one.

So to translate it back to our world, something like

  (with-fluids ((a 2)) (with-fluids ((a 3)) (tail)))
                       ^ this doesn't create a new continuation, it just
                       overrides the marks on the previous one

It seems to be a dynamic construct (i.e., at runtime, not compile-time),
but it works for the purposes of proper tail calls.

AIUI anyway :)

Andy
-- 
http://wingolog.org/

Re: Eval, tail calls, (current-module), and backward compatibility

[Ludovic Courtès]

Hi Mark,

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

> The problem is that `eval' uses dynamic-wind to temporarily set
> (current-module) during the dynamic extent of the expansion and
> evaluation of its form.

Excuse my ignorance, but where is this?  :-)

What I see doesn’t seem to correspond to this description:

        (('apply (f args))
         (apply (eval f env) (eval args env)))


> Can we fix this?
>
> Ideally, I think that `eval' should set (current-module) during
> expansion, but _not_ during evaluation.  Then it can be properly tail
> recursive.  However, some code out there might depend on the existing
> behavior, so I guess we can't change this, at least not in 2.0.  Bummer.

Why?

How does 1.8’s CEVAL behave?

It would be good to have test cases written against 1.8 that illustrate
the behavior of (current-module) in different contexts.  Then we could
see whether/how the same behavior can be achieved in 2.0.

WDYT?

Thanks,
Ludo’.

Re: Eval, tail calls, (current-module), and backward compatibility

[Andy Wingo]

On Wed 18 Jan 2012 22:18, ludo@gnu.org (Ludovic Courtès) writes:

>         (('apply (f args))
>          (apply (eval f env) (eval args env)))

This is in primitive-eval (and here, `eval' is locally bound).  Mark is
talking about R5RS `eval' (`scm_eval').

> How does 1.8’s CEVAL behave?

CEVAL isn't relevant, because it's part of a lower level than `eval'.
1.8 also has this same problem with `eval'.

> It would be good to have test cases written against 1.8 that illustrate
> the behavior of (current-module) in different contexts.  Then we could
> see whether/how the same behavior can be achieved in 2.0.
>
> WDYT?

It's a good idea (for someone else to do ;-)))

Cheers,

Andy
-- 
http://wingolog.org/

Re: Eval, tail calls, (current-module), and backward compatibility

[Ludovic Courtès]

Hello!

Andy Wingo <wingo@pobox.com> skribis:

> On Wed 18 Jan 2012 22:18, ludo@gnu.org (Ludovic Courtès) writes:
>
>>         (('apply (f args))
>>          (apply (eval f env) (eval args env)))
>
> This is in primitive-eval (and here, `eval' is locally bound).  Mark is
> talking about R5RS `eval' (`scm_eval').

OK, but ‘scm_eval’ is not recursive, so no wonder it’s not
tail-recursive.  :-)

(I’m confident I’m missing something, but I just fail to see what.  ;-))

Ludo’.

Re: Eval, tail calls, (current-module), and backward compatibility

[Andy Wingo]

On Wed 18 Jan 2012 23:21, ludo@gnu.org (Ludovic Courtès) writes:

> Andy Wingo <wingo@pobox.com> skribis:
>
>> On Wed 18 Jan 2012 22:18, ludo@gnu.org (Ludovic Courtès) writes:
>>
>>>         (('apply (f args))
>>>          (apply (eval f env) (eval args env)))
>>
>> This is in primitive-eval (and here, `eval' is locally bound).  Mark is
>> talking about R5RS `eval' (`scm_eval').
>
> OK, but ‘scm_eval’ is not recursive, so no wonder it’s not
> tail-recursive.  :-)
>
> (I’m confident I’m missing something, but I just fail to see what.  ;-))

Hee hee :)  The point is that this should loop indefinitely:

  (define (loop)
    (eval '(loop) (current-module)))
  (loop)

It doesn't, because the function that "eval" resolves to is implemented
in C.  If we implemented it in Scheme, it still wouldn't work, because
it would be like:

  (define (loop)
    (with-fluids ((%%%current-module (current-module)))
      (primitive-eval '(loop))))
  (loop)

and the with-fluids makes it not tail recursive.

Andy
-- 
http://wingolog.org/

Re: Eval, tail calls, (current-module), and backward compatibility

[Ludovic Courtès]

Andy Wingo <wingo@pobox.com> skribis:

> On Wed 18 Jan 2012 23:21, ludo@gnu.org (Ludovic Courtès) writes:
>
>> Andy Wingo <wingo@pobox.com> skribis:
>>
>>> On Wed 18 Jan 2012 22:18, ludo@gnu.org (Ludovic Courtès) writes:
>>>
>>>>         (('apply (f args))
>>>>          (apply (eval f env) (eval args env)))
>>>
>>> This is in primitive-eval (and here, `eval' is locally bound).  Mark is
>>> talking about R5RS `eval' (`scm_eval').
>>
>> OK, but ‘scm_eval’ is not recursive, so no wonder it’s not
>> tail-recursive.  :-)
>>
>> (I’m confident I’m missing something, but I just fail to see what.  ;-))
>
> Hee hee :)  The point is that this should loop indefinitely:
>
>   (define (loop)
>     (eval '(loop) (current-module)))
>   (loop)

OK, got it.

TBH, I’d be happy to document the limitation and live with it,
especially since it’s not a regression.

Thanks,
Ludo’.

Re: Eval, tail calls, (current-module), and backward compatibility

[Andy Wingo]

On Wed 18 Jan 2012 23:47, ludo@gnu.org (Ludovic Courtès) writes:

> TBH, I’d be happy to document the limitation and live with it,
> especially since it’s not a regression.

Me too, but if a tail-recursive with-fluids happened to solve it for us,
that would be a pleasant outcome.

Regards,

Andy
-- 
http://wingolog.org/

Re: Eval, tail calls, (current-module), and backward compatibility

[David Kastrup]

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

> Ideally, I think that `eval' should set (current-module) during
> expansion, but _not_ during evaluation.  Then it can be properly tail
> recursive.  However, some code out there might depend on the existing
> behavior, so I guess we can't change this, at least not in 2.0.
> Bummer.

It just occured to me that the _only_ way of getting and setting
variables under a computed name (apart from using macros) is using
(module-set! (current-module) (compute a symbol))
since symbol-set! apparently has been deprecated.

Not sure what the implications of that are.

-- 
David Kastrup

Re: Eval, tail calls, (current-module), and backward compatibility

[Mark H Weaver]

David Kastrup <dak@gnu.org> writes:

> Mark H Weaver <mhw@netris.org> writes:
>
>> Ideally, I think that `eval' should set (current-module) during
>> expansion, but _not_ during evaluation.  Then it can be properly tail
>> recursive.  However, some code out there might depend on the existing
>> behavior, so I guess we can't change this, at least not in 2.0.
>> Bummer.
>
> It just occured to me that the _only_ way of getting and setting
> variables under a computed name (apart from using macros) is using
> (module-set! (current-module) (compute a symbol))
> since symbol-set! apparently has been deprecated.

If you want to get or set a top-level variable with a computed name,
then you need to know which module to use.  Otherwise, how could Guile
possibly know which module you intended?

Remember, (current-module) is a compile-time concept, not a run-time
concept.  It is probably not the right choice except in something like a
REPL, and only if you specifically want the same module that's being
used to compile new top-level forms (using `primitive-eval').

It's unfortunate, but just as support for multiple string encodings
forces us now to think clearly about which encoding to use for a given
bytevector in our code (and there's really no way around this), the same
is also true of modules.  For non-computed variable references, there is
a robust automatic answer: use the module that was baked into the source
identifier before macro expansion.  However, this cannot be done for
computed variable names.

    Thanks,
      Mark

Re: Eval, tail calls, (current-module), and backward compatibility

[David Kastrup]

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

> Remember, (current-module) is a compile-time concept, not a run-time
> concept.

Then current-module should probably be a macro, not a function.  In
which case the tail call problem would take care of itself.

-- 
David Kastrup

Re: Eval, tail calls, (current-module), and backward compatibility

[Mark H Weaver]

David Kastrup <dak@gnu.org> writes:

> Mark H Weaver <mhw@netris.org> writes:
>
>> Remember, (current-module) is a compile-time concept, not a run-time
>> concept.

I should clarify this statement.  (current-module) is used by the code
that's doing the compiling (e.g. the REPL), _not_ by the code that's
being compiled.  It is a run-time variable used by REPLs and compilers
to keep track of which module should be used to compile the next form.

> Then current-module should probably be a macro, not a function.  In
> which case the tail call problem would take care of itself.

A core syntax form to retrieve the module name baked into a given
identifier (a constant) would probably be useful, and indeed I suspect
we'll have it in 2.0.4 because it'll be needed for Andy's implementation
of `local-eval'.

However, that's a different concept from (current-module), therefore it
would need a different name.  To understand (current-module), please
read my first post in this thread.  It would make no sense as a macro.

    Mark

Re: Eval, tail calls, (current-module), and backward compatibility

[Andy Wingo]

On Tue 17 Jan 2012 04:28, Mark H Weaver <mhw@netris.org> writes:

> Ideally, I think that `eval' should set (current-module) during
> expansion, but _not_ during evaluation.  Then it can be properly tail
> recursive.  However, some code out there might depend on the existing
> behavior, so I guess we can't change this, at least not in 2.0.
> Bummer.

Dunno.  There are lots of instances of (current-module) in our current
code, and in code from lots of external projects.  I think if we changed
it, it would break a lot of stuff, subtly.

Andy
-- 
http://wingolog.org/