Re: goops and memoization

[Mikael Djurfeldt]

Dirk Herrmann <address@hidden> writes:

> Certainly this could be done as a temporary solution, but it is still not
> a clean approach, since it still has dependencies on a lot of evaluator
> internals.  Even if my current implementation of the memoizer is closely
> related to the old way the evaluator works, it may make sense to change
> this in the future.  That is, the representation of environment frames
> during memoization and during execution may differ for good reasons.

Certainly.  As I've "confessed" in another letter, the assumptions on
the environment representation is a dirty hack.  One way of handling
this is to use an abstraction such as "lookup":
eval_environment_lookup (SYMBOL, ENV).

[Excellent suggestions for using different env representation during
memoization deleted.]

> I disagree that the result of procedure-source is an excellent
> representation of the logic of the method.  procedure-source does not
> provide the context of the lambda expression:
>   guile> (define foo (let ((bar 1)) (lambda () bar)))
>   guile> (procedure-source foo)
>   --> (lambda () bar)
> That is, the source of the procedure foo does not provide all that is
> needed to understand the logic of the method.  This is a principal problem
> of using procedure-source.  In order to compile the output of
> procedure-source correctly, you need more than the result of
> procedure-source, namely something like procedure-environment-info.

Well, I thought that was implicit in my argument.  compile-method
indeed uses the pair procedure-source, procedure-environment.  Of
course I never meant that the source without its environment is a
valid representation of the logic.  I hope the actual behavior of
goops methods proves that.

But I maintain that the pair of source and environment provides 100%
of the semantics.

> I have suggested this as a temporary fix, but not for performance
> reasons: Goops does already interfere at some places with the
> evaluator and the representation of the memoized code: First, there
> are three memoizer codes that are specifically added for goops.
> Second, the method dispatch code is copied verbatim into the
> evaluator.  Third, during execution of the code dispatch goops
> modifies the memoized code for storing hash tables for faster
> function dispatch.

(...the reason being performance (measured in benchmarks, BTW),
 but I think you make it sound worse than it is.  Two of the codes are
 very simple (object slot access).  The dispatch form does contain
 dependencies on the evaluator for the evaluation of operand forms,
 but the rest is a section of self-contained code operating on a data
 structure which is entirely "owned" and handled by goops.  It's not
 that a lot would need adaptation if the evaluator changes.)

> A cleaner approach to optimization would be to allow compiler
> optimizations in an earlier stage.  Personally I'd prefer a solution with
> five phases:  1) reading 2) macro expansion (scheme -> intermediate
> format) 3) optimization (intermediate format -> intermediate format) 4)
> memoization (intermediate format -> memoized code) 5) execution.  For the
> intermediate format I think of some very close to scheme format using
> keywords like #:if and such (see new-model.text) as Marius has suggested.
> This ought to be very stable.  The memoized code, in contrast could be
> somewhat less stable.  Goops would add its optimizations functions to step
> 3.

Well, this all sounds good.  But note that the use of
procedure-source/environment in no way put serious constraints on the
steps above.  For example, steps 1, 2 and 4 could be performed when
constructing the closure.  Then an unmemoization step (U) followed by
steps 3 and 4 would lead to 5.  Basically, the inserted extra 4 and U
are the only differences.

There are a couple of constraints which I should mention here:

1. The MOP currently specifies that a method is created from a list of
   specializers and a closure by a call to `make'.

   The main reason for using a closure is that it is a nice way of
   capturing the lexical environment without the need to use a
   non-R5RS form and introducing an explicit representation of the
   environment.  Another reason is that this pattern was used in
   Kiczales tiny-clos MOP---reflexive code which describes itself
   beautifully.  Even though goops has dark corners "under the hood",
   the goops MOP provides a conceptually simple model for its
   semantics.

   The MOP also allows us to specialize `make' to a subclass of
   <method>.  If we try to get around the problem of capturing the
   environment by limiting ourselves to the special form `method', we
   loose this aspect of the MOP.

   So, the only alternatives I see are either a closure or passing the
   source expression together with the result of a call to
   (the-environment).

2. Goops method optimizations should not be done in advance.  They are
   supposed to be performed at the exact instance when a generic
   function is called with a particular combination of argument types
   for the first time.  That is of course possible to reconcile with
   the steps above, although steps 3-4 will be folded into the
   execution.

> One could think of the possibility to add hooks for adding arbitrary
> optimization functions, but this is just an idea.

That is an exciting idea.  It would be wonderful to be able to specify
code re-writing rules such as:

  (map foo (map bar ls)) --> (map (lambda (x) (foo (bar x))))

> The reason why goops does not work with my changes is that goops
> relies not only on the working of procedure-source

Which should be of no problem to you unless you want to remove it.  If
you want that, there are other reasons than we discuss here for
keeping it.

> but also on the way environment frames are stored

Yes.

> and on the way the evaluator works.

Not sure what you mean here.

> As long as you don't have a perfect system, you have to build upon
> the things that are available to you.

Yes, unfortunately so.

> With "interactions" I meant holes in the abstraction barrier, where
> code relies on the behaviour of unmemoization

It does in no way depend on the behaviour of unmemoization, unless the
unmemoized source is semantically something different.  The unmemoized
source + the lexical environment is sufficient for full semantics.
Sorry for repeating this statement, but it is important that you prove
me wrong if I am wrong.

> the internal representation of environments

Yes, this is a hole.


> It becomes more and more clear to my why so many previous approaches to
> work on the evaluator have failed:  The dependencies between the evaluator
> and other parts of guile make it necessary to understand and work on quite
> a lot of different parts of guile.

You're absolutely right.  It is very important to work towards good
modularization, especially in this kind of collaborative project.
Don't think I'm not trying...  Although for many years there seemed to
be higher priorities than taking on the monolithic SCM evaluator.

Best regards,
Mikael