Memoize an anonymous function with externally scoped variables

I am trying to memoize a function that takes an anonymous handle with an externally-scoped parameter as input. The problem is that no two anonymous functions are ever the same. Therefore, every time the memoization handle mf is invoked, it executes in its entirety and freshly cache's the results.

mf=memoize(@subfunc);

A=3;
for i=1:4
  mf(@(z)A*z)
end

Caching

ans = 15

Caching

ans = 15

Caching

ans = 15

Caching

ans = 15

I know that the Lord punisheth those who use eval(), but I can see no other alternative but to pass the anonymous function in char/string form and use evalin. This works fine when there are no externally-scoped variables. Caching indeed only occurs on the first call:

for i=1:4
  mf('@(z)3*z')
end

Caching

ans = 15

ans = 15

ans = 15

ans = 15

However, when the anonymous function does contain an externally-scoped variable A, the workaround fails.

A=3;
mf('@(z)A*z')

Caching

Unrecognized function or variable 'A'.

Error in solution>@(z)A*z

Error in solution>subfunc (line 27)
out=fun(5);

Error in matlab.lang.MemoizedFunction/execute (line 397)
[varargout{1:nargout}] = obj.Function(inputs{:});

Error in () (line 249)
[varargout{1:nargout}] = obj.execute(varargin);

So two questions,

1. Why does the workaround fail to find externally scoped variables?
2. Is there a more robust workaround?

function out = subfunc(argFun)

    disp 'Caching'

    if isa(argFun,'function_handle') %argFun is char or string
        fun=argFun;
    else
        fun=evalin('caller',argFun);
    end

    out=fun(5);

end

[Stephen23]

Just to clarify: is A supposed to be memoized? In other words, if A changes it should cache the result, otherwise if A is unchanged then no new cache?

[Matt J]

Yes, that's right.

Answer 1

[Paul]

[Matt J added:]

"... MATLAB® returns the associated cached output values if the following conditions are true.

1. The input arguments are numerically equal to cached inputs. When comparing input values, MATLAB treats NaNs as equal.
2. The number of requested output arguments matches the number of cached outputs associated with the inputs."

The equal NaN thing in condition (1) is important. This classdef worked:

classdef anonymous_function_container
    properties
        fun
    end

    methods
        function obj = anonymous_function_container(fun)
            obj.fun = fun;
        end

        %{
        function truefalse = isequal(anon_fun1,anon_fun2)
            truefalse = isequal(functions(anon_fun1.fun),functions(anon_fun2.fun));
        end
        %}
        
        function truefalse = isequaln(anon_fun1,anon_fun2)
            truefalse = isequaln(functions(anon_fun1.fun),functions(anon_fun2.fun));
        end

        function out = function_eval(obj,val)
            out = obj.fun(val);
        end

    end

end

[Matt J]

Hi @Paul,

That's pretty good. It's not quite robust yet, as the example below demonstrates, but I'm sure that can be remedied. Also, it won't work on older versions of Matlab, since functions(fun).workspace used to contain all kinds of extra junk, but I imagine that wouldn't exclude too many people.

clearAllMemoizedCaches; clear; clc

mf=memoize(@subfunc);

A=3;
f1 = anonymous_function_container( @(z) A*z );
f2 = makeContainer(A);

mf(f1)

Caching

ans = 15

mf(f2)

Caching

ans = 15

function out = subfunc(fun)

    disp 'Caching'

    out=function_eval(fun,5);

end

[Matt J]

The attached version seems to fix it (and is not exclusive to anonymous functions).

clearAllMemoizedCaches; clear; clc

mf=memoize(@subfunc);

A=3;
f1 = fcnContainer( @(z) A*z );
f2 = makeContainer(A);

mf(f1)

Caching

ans = 15

mf(f2)

ans = 15

function out = subfunc(fun)

    disp 'Caching'

    out=fun(5);

end

[Paul]

Glad you got it working the way you want.

I'm still annoyed at the documentation for not being clear on how it determines if the input argruments are already cached. BTW, the classdef also worked if defining isequalwithequalnans as a method instead of isequaln, for whatever that's worth.

Maybe when memoization first came out it only applied for numerical arguments, and then the functionality was improved but the doc wasn't updated?

Answer 2

[Matt J]

One solution is to rebuild the anonymous function inside the memoized function using a container class:

mf=memoize(@subfunc);

A=3;
 
for i=1:4
  mf(   afBuilder(@(z)A*z, A)  )
end

Caching

ans = 15

ans = 15

ans = 15

ans = 15

function out = subfunc(argFun)

    disp 'Caching'

    switch class(argFun)

        case 'function_handle'
            fun=argFun;

        case 'afBuilder'
            fun=argFun.build();
    end

    out=fun(5);

end

[Paul]

Hi Matt,

Did you figure out exactly how the memoization determines if the function inputs are equal to inputs that have been cached?

The doc states:

"... MATLAB® returns the associated cached output values if the following conditions are true.

1. The input arguments are numerically equal to cached inputs. When comparing input values, MATLAB treats NaNs as equal.
2. The number of requested output arguments matches the number of cached outputs associated with the inputs."

Regarding 1, what does "numerically equal" mean if the inputs are not .... numerical?

I assumed that isequal would be called under the hood and so thought that a simpler container class might suffice (thought it uses the non-recommended functions):

classdef anonymous_function_container
    properties
        fun
    end

    methods
        function obj = anonymous_function_container(fun)
            obj.fun = fun;
        end

        function truefalse = isequal(anon_fun1,anon_fun2)
            truefalse = isequal(functions(anon_fun1.fun),functions(anon_fun2.fun));
        end

        function out = function_eval(obj,val)
            out = obj.fun(val);
        end

    end

end

With this class defintion we have:

>> f1 = @(z) A*z;
>> f2 = @(z) A*z;
>> isequal(f1,f2)
ans =
  logical
   0
>> isequal(anonymous_function_container(f1),anonymous_function_container(f2))
ans =
  logical
   1

So I thought that the following would work:

mf=memoize(@subfunc);
A=3;
 
for i=1:4
  mf(anonymous_function_container(@(z) A*z))
end

function out = subfunc(argFun)
    disp 'Caching'
    out = argFun.function_eval(5);
end

Alas, the isequal method in the class was never called (I had a breakpoint in the debugger) and the output of the program was:

Caching
ans = 15
Caching
ans = 15
Caching
ans = 15
Caching
ans = 15

Seems like it's important to understand exactly how the memoization determines if the inputs are already cached, but I can't find any examples for anything other than numerical inputs, though I think other built-in types would typically apply like strings, structs, and cells, in addition to user-defined types. For the latter, what functionality needs to be implemented to meet the "is-already-cached" criterion?

Answer 3

[Walter Roberson]

h1 = @(z)A*z

h1 = function_handle with value:
    @(z)A*z

h2 = @(z)A*z

h2 = function_handle with value:
    @(z)A*z

isequal(h1, h2)

ans = logical
   0

Each time you execute the building of the anonymous function, you end up with a different result. This has nothing to do with memoizing the result. To get around this you would need to use something like

A=3;
Az = @(z)A*z;
for i=1:4
  mf(Az)
end

[Matt J]

Each time you execute the building of the anonymous function, you end up with a different result. This has nothing to do with memoizing the result.

Yes, the OP acknowledges that. But I really don't want to maintain my own separate cache of different possible Az inputs. The memoization engine is supposed to do that for me.

[Walter Roberson]

You are memoizing the call to subfunc. When the memoized function is presented with identical arguments, the cached value is to be returned. Different calls to building an anonymous function create different anonymous functions, so the memoized function is not being presented with identical arguments. The memoization engine is not supposed to do that for you.

This is not a failure of the memoization process; it is a limitation on the process of creating anonymous functions.

If we imagine that the process of anonymization must produce the same output handle given the same inputs, then we need to consider

global ABC
ABC = 123;
h1 = @(z)ABC*z

h1 = function_handle with value:
    @(z)ABC*z

ABC = 456;
h2 = @(z)ABC*z

h2 = function_handle with value:
    @(z)ABC*z

h1(1)

ans = 123

h2(1)

ans = 456

functions(h1).workspace{1}

ans = struct with fields:
    ABC: 123

functions(h2).workspace{1}

ans = struct with fields:
    ABC: 456

This establishes that the captured variable must lose its "global" status. If we were to "clear global" and then create a new ABC = 123 and h3 = @(z)ABC*z then should h1 be the same function handle as h3 ?

At the very least, for anonymous functions to return the same handles for the same inputs, it would be necessary to compare the contents of all captured variables.

format debug
ABC = 123

ABC = 
Structure address = 7ebc59524b10
m = 1
n = 1
pr = 7ebc505c3880

   123

functions(h1).workspace{1}.ABC

ans = 
Structure address = 7ebe298d17c0
m = 1
n = 1
pr = 7ebd4b2fc4e0

   123

we can see from this that a copy of the captured variables is made -- the pr is different between the two instances.

ABCD = struct('GHI', 789)

ABCD = struct with fields:
    GHI: 0

ABCD.GHI

ans = 
Structure address = 7ebc5952cb80
m = 1
n = 1
pr = 7ebd8c4456e0

   789

h4 = @(z)ABCD.GHI*z

h4 = function_handle with value:
    @(z)ABCD.GHI*z

functions(h4).workspace{1}.ABCD

ans = struct with fields:
    GHI: 0

ans.GHI

ans = 
Structure address = 7ebe6d95a470
m = 1
n = 1
pr = 7ebe5bb9fe60

   789

We can see from this that it is a deep copy

I can't be bothered at the moment. That implies that the hypothetical mechanism to detect duplicate functionality would have to check the contents of possibly large variables -- since, after all, ABC(1e8) in one case might differ from ABC(1e8) in another case.

[Matt J]

I agree with all of that, but it is still just a restatement of the problem, not a solution. The convenience that a user is looking for with memoization is for things to get faster when you repeatedly run the same code. When I run mf(@(z)A*z) multiple times in succession with no changes, it never gets any faster. We both understand why anonymous functions don't fulfill what I'm seeking, but the question was how to work around it.

You proposed computing the handle in advance instead of transiently, but that can get very inconvenient. For example, the call to a memoized function might be from a workspace deep in the function call stack. Any anonymous functions created transiently in that workspace could never be memoized, so you would need to compute all versions of Az that you want to memoize in advance and pass them down through the stack somehow. I suppose you could use persistent variables, but it's still ugly because you effectively end up building your own cache, duplicating the normal mechanics of memoization.

[Walter Roberson]

Question:

mf=memoize(@subfunc);

for K = 1:3
    A = randi(1);
    f{K} = @(z) A*z;
    mf(f{K})
end

We know through reasoning that A will be the same in each iteration. Should f{1} be isequal to f{2} ? Should mf(f{2}) invoke caching after mf(f{1}) has been executed?

How about

mf=memoize(@subfunc);

for K = 1:3
    A = randi(2);
    f{K} = @(z) A*z;
    mf(f{K})
end

We known through reasoning that at least two of the f{:} will use the same A value. Should those f{:} be isequal() ? Should those mf(f{K}) invoke caching upon matching A ?

[Matt J]

It would be nice if that were the behavior, yes. And I'm able to achieve that behavior with afBuilder() in my answer, but unfortunately that uses eval :-(