Memoization, define and all that

[tomas]

On Sat, Nov 09, 2002 at 09:29:40AM +0100, Dirk Herrmann wrote:
> 
> Clinton Ebadi wrote:
> > > I don't care how memoization works.  [...]

[...]

> First, why wouldn't guile be scheme any more if conditional definitions
> are disallowed?  They are disallowed by R5RS, so actually, if you
> understand "being scheme" as "conforming to R5RS" then currently guile is
> not scheme and disallowing conditional definitions will bring it one step
> closer to "being scheme" :-)

Hrm. As marius pointed out elsewhere, this isn't just an issue with define,
but actually with any form which might get expanded before/at compile time.

> Second, certainly can code be memoized and compiled incrementally.
> However, this would have to be done every time the code was read in again,
> since in an expression like (if <condition> (define <foo> <bar)) the value
> of <condition> may change every time the code is read in.

Yes, as far as we can't make sure (e.g. by static code analysis) that
we have a fixed value for <condition>. As soon as <condition> is known,
things look better (and if <condition> isn't known, there might be a
reason to it, that is, the programmer is willing to pay for the overhead).

Of course I'm not favouring a thorough code analysis (is that decidable
at all?), but: if you *know* a thing to be constant -- go ahead and
memoize, if you *don't know* well, take with you a reference to the lexical
environment (you have to do this for macros, in some way or other, don't
you?) and leave things as they are.

With time you can get better by expanding the set of situations you *know*
about. This is what I had in mind when I was talking something about partial
evaluation.

Does this sound plausible?

> That is, we would reduce our possibility to pre-compile code.

But only in those cases which you are about to prohibit. You can always
pre-compile the ``goodies'' (e.g. those lexical spans where `define is
not redefined, etc.). May be I'm overlooking something here, but I tend
to view pre-compilation as a kind of constant folding.

> Pre compiling code, however, is one of our options to speed up guile's
> starting time (aside from optimizing guile's module system...).

Yep. And I think it a bearable burden for the programmer to keep some
things in mind if she intends to write well-compilable code. But as
long as we have eval around (and we won't like to miss this one do we?),
we'll have an instance of the compiler/interpreter around, so it
doesn't hurt postponing things (other than performance, that is). So
the trick might be to just postpone things ``when we don't know better'',
because someone is playing nasty tricks with our basic forms (whatever
they may be, I think define is just an example).

Thanks for your patience in reading my half-baked mumbling.

Regards
-- tomas