[Dirk Herrmann <address@hidden>]

[Marius Vollmer]

I'm forwarding this on behalf of Dirk.

---------- Forwarded message ----------
Date: Sat, 14 Dec 2002 13:10:01 +0100 (CET)
From: Dirk Herrmann <address@hidden>
To: address@hidden
cc: Neil Jerram <address@hidden>, address@hidden
Subject: Re: goops and memoization
In-Reply-To: <address@hidden>
Message-ID: <address@hidden>

Hi Mikael,

sorry for the late answer, but I was ill the last week.

On Wed, 4 Dec 2002, Mikael Djurfeldt wrote:

> Dirk Herrmann <address@hidden> writes:
> 
> > As stated in my previous mail the output of procedure-source is not the
> > full scheme code that is necessary to re-memoize the code:
> >   guile> (define foo (let ((bar 1)) (lambda () bar)))
> >   guile> (procedure-source foo)
> >   --> (lambda () bar)
> > That is, trying to re-translate this output is not as clean a separation
> > as you claim.  You depend on the fact that during execution there is
> > sufficient information available to reliably re-compile any code such that
> > it fits into the rest of the compiled code around it.  That is a strong
> > assumption and it may prove to be expensive to guarantee it.
> 
> Could you explain this to me?  Why is it such a strong assumption?
> 
> My obvious counter example is:
> 
> (define foo2 (local-eval (procedure-source foo) (procedure-environment foo)))
> (foo2) --> 1
> 
> [There is a need here to treat the first `lambda' specially, but
>  that is a trivial problem.]
> 
> Which do you think puts the heavier constraint, procedure-source or
> procedure-environment?  Note that there is no assumption needed that
> procedure-source returns the verbatim source expression from which the
> closure was created.  And an environment is simply a mapping of
> variables to bindings.
> 
> Note that there is nothing "around" the method into which it should
> fit.  The method has it's own closed environment.

My concerns arise from the fact, that advanced compiler optimizations
(which also could be used during memoization) can span across several
functions and thus may have effects on not only one single function and
its environment.  The following code may give the idea:
  (let ((func1 (arg) some-code)
        (func2 (arg) some-other-code))
    (func1 some-arg)
    (func2 some-other-arg))
Since it can be seen that the result of func1 is not used, it may be
possible to eliminate code in func1 that is needed to compute func1's
output value.  Since it can be seen that func1 and func2 don't call each
other, there may be the possibility to perform some optimizations, like
using shared locations for the argument values and local variables.
Further, in order to reduce code size or improve instruction cache
performance, the optimization may extract common code into a common
sub-function.  That is, each function's memoized code 'fits' into the
whole of the memoized code, since the optimizer or the memoizer may
introduce dependencies between different parts of the memoized code.  
This, at least, is common for code optimization for other languages.

If we assume that such optimizations should also be possible for guile,
then I fear that the pair procedure-source and procedure-environment will
not be sufficient to re-memoize a function (say, func1) from its code and
environment such that it fits into the rest of the compiled code around
it.  Maybe it is possible to generate correct code from re-memoization
without disturbing the rest of the code around, but some of the previously
gained optimization achievements may be lost for the re-memoized code.

I admit that the example is not fully thought out and that this very
example may not show a situation that applies to the goops optimization
case, but I hope that it demonstrates the idea and explains my "strong
assumption" statement above.

> That is fine.  Can you share your current source?

I will prepare a patch in the next couple of days.

Best regards
Dirk Herrmann

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405