Re: memoization and conditional defines

[Dirk Herrmann <dirk@sallust.ida.ing.tu-bs.de>]

On Thu, 7 Nov 2002, Rob Browning wrote:

> I'm not entirely clear on the issues involved here, but I'd like to
> be, so please bear with me.  Would it be possible (and make any sense)
> to arrange for something like like "just in time" memoization for
> top-level forms (as I think Clinton may have suggested), or would that
> overly complicate the code?  i.e. don't memoize top-level expressions
> until you're ready to execute them.  Such an approach might prevent
> those bits from being compiled efficiently, but I suppose the user
> could choose whether or not to write things that way.

On-the-fly memoization is what guile currently does.  This does, however,
slow down evaluation, it complicates the evaluator and it does not allow
us to write out pre-compiled code in order to speed up startup time.

> There's still the question of whether or not we should even allow
> non-top-level defines like this, although I can understand the
> impulse, esp for configuration related decisions.  I'd say if
> supporting them leads to really nasty semantic or implementational
> complexities, especially if given suitable alternatives, then perhaps
> we shouldn't.

As has been said in previous mails, there are suitable alternatives for
conditional defines.
* For the general case
    (if <test> (define <foo> <bar>))
  one can use eval:
    (if <test> (eval '(define <foo> <bar>) (current-module)))
* The special case
    (if (not (defined? <foo>)) (define <foo> <bar>))
  which is probably very common when dealing with configuration issues can
  be replaced by the following pattern:
    (define foo-was-defined-before? (defined? '<foo>))
    (define <foo> (if foo-was-defined-before? <foo> <bar>)
  Note that the helper-variable foo-was-defined-before? is necessary
  because within a define form the symbol is already bound to a location
  (according to R5RS), that is we have to remember whether it had been
  defined before outside of the define form itself.

It took me quite some time to understand the issues involved with
conditional definitions.  My current effort to separate memoization and
execution made it clearer to me, because it reflects itself in the code
for the evaluator if you want to do things right.  This made me see one
thing:  The design decisions hidden in R5RS are typically based on very
thorough investigations of potential problems.  Implementations have to be
very careful to deviate from these decisions.

I favor to force users to use 'eval when trying to realize conditional
definitions.  The use of eval does not solve the theoretical problem of
how in the following code
  (begin
    (if some-condition (eval '(define => #t) (current-module)))
    (define (foo x)
      (cond (x => some-function))))
the cond-expression should be memoized.  However, for eval it is IMO 
easier to communicate the problems involved when distinguishing
compilation and interpretation:  When using eval, people typically
understand that the evaluated expression can not be pre-compiled.  In
contrast, conditional definitions seem so natural that people will
probably not be aware of the problems that are involved.

> Also, would eval-when based defines still be OK?  I would presume so,
> since they're essentially a conditionally included "begin block".
> 
>   (eval-when (compile)
>     (define => bar))

Since I assume that eval-when uses 'eval to execute the definition, then
everything would be OK here.

> >  b) complicate the memoization process in order to get things right.  An
> >     option that we have here is the following:  Top-level forms are not
> >     memoized but interpreted.  Memoization is only done whenever a
> >     non-top-level scope is entered, like a let-form, or a
> >     lambda-expression. The cost of this solution is that in addition to
> >     the memoizer and the executor we would need an interpreter.
> 
> Why are let forms and lambda expressions excluded?

Because definitions within a let form and a lambda expression are not
top-level.  Internal definitions are re-written into a letrec form:
  (lambda foo
    (define => #t)
    (cond (#t => 'ok)))
is transformed into
  (lambda foo
    (letrec ((=> #t))
      (cond (#t => 'ok))))
and it is clear to the memoizer that the cond-expression is OK.

It should be noted that internal definitions may also only occur at a
restricted set of places.  For example, even the current guile (which
allows conditional defines on the top level) does not support the
following:
  (lambda foo
    (if <condition> (define <foo> <bar>)))

Best regards,
Dirk Herrmann



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel