[Ecls-list] [Suggestion] Caching expansion of type-specifier

[Gabriel Dos Reis]

On Sun, Nov 29, 2009 at 1:06 PM, Juan Jose Garcia-Ripoll
<juanjose.garciaripoll at googlemail.com> wrote:
> On Sun, Nov 29, 2009 at 7:20 PM, Gabriel Dos Reis
> <gdr at integrable-solutions.net> wrote:
>> Well, I'm not sure how frequent are those exotic cases, and why
>> they should weight more than the common cases.
>
> No, well, the question is not whether they should weight more, but
> whether they do count at all. If they count at all, then caching is
> impossible.
>
> "Clever" caching is not an option. How does one determine when caching
> is possible? I would say that determining when a DEFTYPE function is
> candidate for caching is an NP-complete problem by itself.

Yes, but the whole art and science of what we do in compiler construction
is not to solve that problem :-)

Let me explain what I understood by what the caching would do.
If a deftype is expanded for the first time, and it is know to be of the
restricted form above, then remember its expansion.
On subsequent expansion requests, if it is in the cache just return it.
Otherwise, proceed as before.  Why is that "clever", and therefore
would not be an option?

>
> The problem with DEFTYPE is that it is defined to be a rather generic
> function without constraints on side effects.

yes, agree.  That does not prevent a Lisp compiler from caching
those deftypes that behave -- a user program won't tell the difference.

> If we eliminate the
> possibility of side effects and dictate that the number of times that
> DEFTYPE is invoked is completely arbitrary and unspecified, then it is
> ok with caching. I would say that this is the spirit of the
> specification, though.

I suspect my previous use of the word "side-effect free" may be
side-tracking you.  What I meant wasn't that ECL should reject
those forms.  Rather, what was meant is that ECL can decide
that some forms are well-behaved and caceh their values.  I don't
think that is an incorrect implementation strategy.

>
> But there are other concerns. For instance the cost of caching. ECL
> does not do recursive expansion of DEFTYPE types right now.

Ah!

> All
> algorithms such as TYPEP are recursive and run through types expanding
> only the parts that are required. In this context caching the
> expansion of the type is too expensive when compared just to a
> function call which is needed to do a single expansion.

I understand that analysis; would you still come to the same conclusion
if ECL did full walk in TYPEP?

-- Gaby