Re: overloaded function handles

[Jaroslav Hajek]

On Wed, Jul 29, 2009 at 9:14 AM, Judd Storrs<address@hidden> wrote:
> On Wed, Jul 29, 2009 at 1:34 AM, Jaroslav Hajek <address@hidden> wrote:
>>
>> No, probably not. I was a little confused about what you were trying
>> to say. Were you suggesting to change the implementation?
>
> Let me preface this by saying that I have no idea how handles are
> implemented in Octave and it may well be that you've already implemented it
> this way. What I am trying to do is outline an implementation that I belive
> works differently from what is described in the patent but that I feel gets
> very close to Matlab's behavior.
>
> To my understanding of the patent, the core claims revolve around:
>
> 1) Function handles are data structures that contain a dispatch list of
> overloaded function implementations.
>

Yes, that is currently true. It is also true for the internal fcn_info class.

> 2) When evaluated each handle's data list is searched for the appropriate
> overloaded function implementation instead of searching the implementations
> available in the current environment.
>

In Octave, the handle's list is searched first, and if nothing is
found, a global lookup is performed.

>
> 3) The handles are somewhat isolated from changes in the environment that
> add or remove overloaded implementations.
>

I'm not sure what you mean; the handle will perform the standard
out_of_date_check (symtab.h) on the found function,
that possibly reloads the source if it has been changed prior to last
prompt time. If the result of the lookup is not cached, it will be
performed via symbol table.

>
> So first lets say what this is not. It is not about managing a central
> database/cache of overloaded function definitions.
>

It depends. It seems to me that symbol_table::fcn_info pretty well
matches 1 and possibly 2.

>
> My suggestion is that perhaps a lot of this may be unnecessary in real code
> because in many cases it is obvious which of the overloaded functions is
> meant by the programmer. In those cases no dispatch list is needed and the
> handle can refer always to that one specific implementation. i.e. no data
> structure. These cases are immune to changes in environment by definition
> because they have already been fully resolved.
>

It is possible to omit the lookup cache, but I'd expect a rather
significant impact on performance.

>
> That leaves the remaining cases where it isn't necessarily obvious which
> implementation is desired. My question is how much real, working code would
> it break if instead of searching the scope that the handle was created in,
> we instead search the handle is applied in.
>

That's like the str2func issue again. You really don't want to hit the
caller's subfunctions or private functions. At least you'd need a
mechanism to skip those.

>
> If the function can be found via the regular path mechanism, then a central
> cache of available functions is sufficient and that can be created/querried
> any time. So we just need to identify those cases where the central cache
> doesn't apply.
>

Except the performance...

>
> So when you create a handle to an overloaded function if the implementation
> is "immediate" based on some simple rules/heuristics (i.e. anonymous
> functions, functions defined in the same file) the handle is fully resolved
> at creation and refers to that specific implementation. Because there is no
> list created and attached to the handle at creation the claims of the patent
> shouldn't apply.
>
> Class methods are a little trickier but could be handled by type matching of
> the first argument at the time of evaluation. This should allow derived
> classes to override parent methods, I think.
>

It's more complicated than just checking the first argument. Check out
get_dispatch_type in symtab.cc.

>
> On the otherhand, if you create a handle and the implementation is not
> "immediate" then a list of overloaded implementations would not be created
> and no dispatch list is attached to the handle--instead the handle just
> holds the function name. Because a dispatch list is not attached to the
> handle at the time of creation, the patent doesn't apply. At evaluation
> instead of searching the creation scope we search the calling scope. This
> would differ from the described behavior in the patent. From my reading, the
> core octave dispatch engine would be free to cache whatever it wants at the
> time handle application as long as it does not attach multiple
> implementations to the handle at the time of handle creation.
>
> Because the dispatch tree is created at the time of evaluation instead of at
> the time of creation it can conceivably result in different behavior between
> Matlab and Octave because the scopes are different. The hope would be that
> the "immediacy" rules can be designed to cover most if not all of the useful
> cases where functions disappear.
>
> What I'm having trouble thinking of are examples where someone could make
> good use of the difference between what Matlab does and what I'm describing.
>

The problem is that I don't want the feature to slow down things a lot
for the common cases, like applying, say, @sum via cellfun.
Pre-caching the built-in classes is necessary so that you can fairly
quickly tell whether they're overloaded (Octave uses overloading in
its library much less than Matlab, so the result is usually negative)
and skip querying symbol_table. That way you get to only 20% penalty,
as I demonstrated by the benchmark a couple of days ago. Omitting
out-of-date check would further speed it; but currently I see no good
way to optimize it out only partially and on general I think that the
out-of-date checking is good.

If you want to propose an alternative implementation, go ahead. I'm
fairly sure that the idea of dropping the cache would result in
inferior performance, but maybe you can manage something I just don't
see.

-- 
RNDr. Jaroslav Hajek
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz