Thread Subject: Recursive anonymous function

Hello,

I have been playing with anonymous functions.
As you cannot have if or while statements, I am trying to see if I can emulate them.

An if statement can be done with boolean logic
(I believe this construct is called a binary switch)
iff = @(cond,t,f)((cond==true).*t + (cond==false).*f);

As with a m-file version of iff, the downside is that both the true and false conditions need to be evaluated.

Now my thoughts for doing a while loop is to use recursion.
my example program is
function res = sumval(x,i)
    if i == 1
       res = x(i);
    else
       res = x(i) + sumval(x,i-1);
    end
end

thus sumval(1:5,5) => 15

As an anonymous function I have got:
sumval = @(x,i)(x(i) + eval(char(iff(i==1,'0', 'sumval(x,i-1)'))));

Now my problem is that the anonymous function works inside an m-file

eg:

function res = sumv()
    iff = @(cond,t,f)((cond==true).*t + (cond==false).*f);
    sumval = @(x,i)(x(i) + eval(char(iff(i==1,'0', 'sumval(x,i-1)'))));
    res = sumval(1:5,5);
end

sumv() => 15

but just running the 3 statements in the workspace causes an error:
??? Error using ==> eval
Undefined function or method 'sumval' for input arguments of type 'double'.

This tells me that the scope of the sumval function does not include the workspace scope. However, even if I define iff and sumval to be global, the error still happens.

How can I make a global anonymous function which is recursive?
That is: I want to define an anonymous function in the workspace and have it be globally accessable to itself

Brandon

"Brandon" <bnavra.remove.this@student.usyd.edu.au.remove.this> wrote in message <gp22jh$sif$1@fred.mathworks.com>...

> iff = @(cond,t,f)((cond==true).*t + (cond==false).*f);
>

This barely returns the right output but far from imitating the if-else branching (or logical short cut operator). This property is needed to fold and unfold the recursion correctly.

I don't even look at the rest of your post.

Bruno

Bruno

I encourage you to read the entire post.
The recursion does work when declared inside an m-file
(My query is about scope and declaration)

As for the iff function, I agree that branching and logical short cuts will not happen; but excluding that, it functions as a decision statement

eg:
iff(10>5,7,8) => 7
iff(10<5,7,8) => 8
char(iff(strmatch('max','maximum'),'inside','not in')) =>'inside'

as can be seen with the last example, the iff function is not perfect but for the example recursion i am using it is fine

Brandon

On Mar 9, 9:49=A0am, "Brandon"
<bnavra.remove.t...@student.usyd.edu.au.remove.this> wrote:
> Bruno
>
> I encourage you to read the entire post.
> The recursion does work when declared inside an m-file
> (My query is about scope and declaration)
>
> As for the iff function, I agree that branching and logical short cuts wi=
ll not happen; but excluding that, it functions as a decision statement
>
> eg:
> iff(10>5,7,8) =3D> 7
> iff(10<5,7,8) =3D> 8
> char(iff(strmatch('max','maximum'),'inside','not in')) =3D>'inside'
>
> as can be seen with the last example, the iff function is not perfect but=
 for the example recursion i am using it is fine
>
> Brandon


No it will not fine for recursion. You the branching is fundamental,
because otherwise the computer will try to evaluate both expressions
and there is nothing to stop it.


% Try this one, I bet it doesn't work

function res =3D sumval(x,i)
    ieq1 =3D i=3D=3D1;
    res =3D ieq1.*x(i) + (~ieq1).*x(i) + sumval(x,i-1);
end

Bruno

Hi Bruno,

I see where you are having issues with iff and its use for recursion.
You are correct that iff will evaluate both conditions and hence there would be no termination for recursion.

I did encounter this issue and make my conditions strings and used eval.
Let me explain my sumval anonymous function so we don't get stuck on the iff.
(Sorry about the length of the explanation)

sumval = @(x,i)(x(i) + eval(char(iff(i==1,'0', 'sumval(x,i-1)'))));

if x = [1 2] and i = 2

Round1
----------
x(i) = x(2) = 2
eval(
      char(
             iff(i==1,'0', 'sumval(x,i-1)')
            )
      )

the iff statement will evaluate:
iff(2==1, '0', 'sumval(x,i-1)')
=> ((2==1)==true).*'0' + ((2==1)==false).*'sumval(x,i-1)'
=> (0==true).*'0' + (0==false).*'sumval(x,i-1)'
as true = 1 and false = 0
=> (0).*'0' + (1).*'sumval(x,i-1)'
=> 0 + 'sumval(x,i-1)'
now the adding a number to a string produces a vector of values representing the ascii value of the string: [115 117 109 118 97 108 40 120 44 105 45 49 41]

but char([115 117 109 118 97 108 40 120 44 105 45 49 41])
=> 'sumval(x,i-1)'
and eval('sumval(x,i-1)') will cause the second round of recursion

Round2 (i is now 1)
----------
x(i) = x(1) = 1
eval(
      char(
             iff(i==1,'0', 'sumval(x,i-1)')
            )
      )

the iff statement will evaluate:
iff(1==1, '0', 'sumval(x,i-1)')
=> ((1==1)==true).*'0' + ((1==1)==false).*'sumval(x,i-1)'
=> (1==true).*'0' + (1==false).*'sumval(x,i-1)'
=> (1).*'0' + (0).*'sumval(x,i-1)'
=> '0' + 0
=> 48

but char(48) => '0'
and eval('0') will end the recursion

hence sumval([1 2], 2) => 2 + 1 + 0 = 3

As I mentioned previously, there is nothing wrong with the recursion itself;
the problem is that it doesn't work unless declared in an m-file

On Mar 9, 10:50=A0am, "Brandon"
<bnavra.remove.t...@student.usyd.edu.au.remove.this> wrote:

>
> sumval =3D @(x,i)(x(i) + eval(char(iff(i=3D=3D1,'0', 'sumval(x,i-1)'))));
>
>
> As I mentioned previously, there is nothing wrong with the recursion itse=
lf;
> the problem is that it doesn't work unless declared in an m-file

Stop right there. Yes there is something wrong, but you need to know
the way Matlab stores anonymous function to see what is going on.

When parsing the expression with new declared anonymous function,
Matlab captures and stores all local workspace context in a structure-
like. SUMVAL statement inside the expression has not yet set (when it
was declaring), and it cannot be captured. Consequence: the eval
fails, because SUMVAL is unknown when recursion is expected. End of
the story.

I recommend to focus your effort on something else rather than abusing
anonymous function and EVAL. Those two are bad enough on it own, let
alone when combining them. I have a hard time to see what advantage
you can draw by programming in that way. Probably the only good thing
is it teaches us how thing work internally.

Bruno

Bruno Luong <b.luong@fogale.fr> wrote
> SUMVAL statement inside the expression has not yet set (when it
> was declaring), and it cannot be captured. Consequence: the eval
> fails, because SUMVAL is unknown when recursion is expected. End of
> the story.
>

Bruno,
Please create an m-file and put the following code in it

function res = sumv()
    x = 1:5;
    i=5;
    iff = @(cond,t,f)((cond==true).*t + (cond==false).*f);
    sumval = @(x,i)(x(i) + eval(char(iff(i==1,'0', 'sumval(x,i-1)'))));
    res = sumval(x,i);
end

then run it. I get an answer of 15, which means that the function worked.

> I recommend to focus your effort on something else rather than abusing
> anonymous function and EVAL...I have a hard time to see what advantage
> you can draw by programming in that way.

Please don't be dismissive of my query just because you do not see a point to it.
I am experimenting with matlab and trying to learn some of its limitations.
I read that anonymous functions can't have if statements nor while loops and I am trying to see if I can prove that otherwise.

now back to the analysis
you said:
>...new declared anonymous function,
>Matlab captures and stores all local workspace context...

that implies that anonymous functions are closures. If this is the case it seems odd that the code works inside another function.

Brandon

On Mar 9, 1:06=A0pm, "Brandon"
<bnavra.remove.t...@student.usyd.edu.au.remove.this> wrote:
> Bruno Luong <b.lu...@fogale.fr> wrote
>
> > SUMVAL statement inside the expression has not yet set (when it
> > was declaring), and it cannot be captured. Consequence: the eval
> > fails, because SUMVAL is unknown when recursion is expected. End of
> > the story.
>
> Bruno,
> Please create an m-file and put the following code in it
>
> function res =3D sumv()
> =A0 =A0 x =3D 1:5;
> =A0 =A0 i=3D5;
> =A0 =A0 iff =3D @(cond,t,f)((cond=3D=3Dtrue).*t + (cond=3D=3Dfalse).*f);
> =A0 =A0 sumval =3D @(x,i)(x(i) + eval(char(iff(i=3D=3D1,'0', 'sumval(x,i-=
1)'))));
> =A0 =A0 res =3D sumval(x,i);
> end
>
> then run it. I get an answer of 15, which means that the function worked.
>
> > I recommend to focus your effort on something else rather than abusing
> > anonymous function and EVAL...I have a hard time to see what advantage
> > you can draw by programming in that way.
>
> Please don't be dismissive of my query just because you do not see a poin=
t to it.
> I am experimenting with matlab and trying to learn some of its limitation=
s.
> I read that anonymous functions can't have if statements nor while loops =
and I am trying to see if I can prove that otherwise.
>
> now back to the analysis
> you said:
>
> >...new declared anonymous function,
> >Matlab captures and stores all local workspace context...
>
> that implies that anonymous functions are closures. If this is the case i=
t seems odd that the code works inside another function.
>
> Brandon

You are right, I shouldn't discourage you to pursue of exploring. If
you want to know how MATLAB captures the workspace context, use
function FUNCTIONS on anonymous function.

Good luck,

Bruno

Bruno Luong <b.luong@fogale.fr> wrote
> If you want to know how MATLAB captures the workspace context, use
> function FUNCTIONS on anonymous function.

Bruno

Thank you for pointing me to this function.
It has actually answered my question.

An anonymous function is a closure which takes a snapshot of the workspace on creation.

So when sumval is run in the command window, as you said, there is no sumval for it to call (hence eval will fail).

When I ran the m-file version again to try and determine why it works

function [res WS] = sumv()
    iff = @(cond,t,f)((cond==true).*t + (cond==false).*f);
    sumval = @(x,i)(x(i) + eval(char(iff(i==1,'0', 'sumval(x,i-1)'))));
    WS = functions(sumval);
    x = 1:5;
    i=5;
    res = sumval(x,i);
end

When examining WS there are 2 workspaces

As for why it works when in an m-file I think the following happens:
1) The caller workspace is stored
2) The function is created in the caller workspace
3) The caller workspace is stored a second time

Now, the above doesn't look right but its the only way I can make sense of it.
Anyone know why?

Brandon

Brandon,

Functions are always preparsed by Matlab, scripts are are not (only parsed at the runtime).

Bruno

Brandon,

Trying to perform recursion with anonymous functions seems very odd. However, I understand your curiosity to try it out anyway. Here's an anonymous function formulation I came up with for computing factorials. It actually uses 2 anonymous functions, one for each "branch" of the recursion:

>> fact = @(val,branchFcns) val*feval(branchFcns{(val == 1)+1},val-1,branchFcns);
>> returnOne = @(val,branchFcns) 1;
>> branchFcns = {fact returnOne};
>> fact(4,branchFcns)

ans =

    24

>> fact(5,branchFcns)

ans =

   120

As you can see, it works. It is, however, Rube-Goldberg-esque. =)

Ken

Actually, here's a new way to declare FACT without using feval:

>> fact = @(val,branchFcns) val*branchFcns{(val <= 1)+1}(val-1,branchFcns);

Ken

Brandon wrote:
> Hello,
>
> I have been playing with anonymous functions.
> As you cannot have if or while statements, I am trying to see if I can emulate them.
>
> An if statement can be done with boolean logic
> (I believe this construct is called a binary switch)
> iff = @(cond,t,f)((cond==true).*t + (cond==false).*f);
>
> As with a m-file version of iff, the downside is that both the true and false conditions need to be evaluated.
>
> Now my thoughts for doing a while loop is to use recursion.
> my example program is
> function res = sumval(x,i)
> if i == 1
> res = x(i);
> else
> res = x(i) + sumval(x,i-1);
> end
> end
>
> thus sumval(1:5,5) => 15
>
> As an anonymous function I have got:
> sumval = @(x,i)(x(i) + eval(char(iff(i==1,'0', 'sumval(x,i-1)'))));
>
> Now my problem is that the anonymous function works inside an m-file
>
> eg:
>
> function res = sumv()
> iff = @(cond,t,f)((cond==true).*t + (cond==false).*f);
> sumval = @(x,i)(x(i) + eval(char(iff(i==1,'0', 'sumval(x,i-1)'))));
> res = sumval(1:5,5);
> end
>
> sumv() => 15
>
> but just running the 3 statements in the workspace causes an error:
> ??? Error using ==> eval
> Undefined function or method 'sumval' for input arguments of type 'double'.
>
> This tells me that the scope of the sumval function does not include the workspace scope. However, even if I define iff and sumval to be global, the error still happens.
>
> How can I make a global anonymous function which is recursive?
> That is: I want to define an anonymous function in the workspace and have it be globally accessable to itself
>
> Brandon

There is an answer to this question that is, on the one hand, worth
understanding if you want to know more about the theory of programming
languages, and on the other, is not really a pragmatic solution. First,
start with the conditional part. They way to do this generically,
addressing the problem pointed out by Bruno Luong, is to turn a boolean
value into an index. The following function handle is designed to take
three arguments, the first a boolean value, and the second two, function
handles taking no arguments and yielding a desired result. Taking these
arguments via varargin provides a cell that can be indexed:

 >> ifthenelse = @(b,varargin) varargin{2-b}();

You with me?

Now comes the heavy lifting, the part about the theory of programming
languages. As background, recall that the "fixed point" x of a function
F has the property that F(x) = x. That's easy. The deep part, which I
won't explain here, is that recursion can be view as the fixed point of a
function that takes a functional argument. The idea is to obtain
recursion by applying a fixed point operator to a more or less obvious
encoding of the recursive function. The traditional name for the fixed
point operator in this context is Y, so for factorial, one would write:

 >> fact = Y(@(fct)@(n)ifthenelse(n==0 ,@()1, @()n*fct(n-1)));

In other words, Y is given a function @(fct)<defn. of factorial>, where
the <defn. of factorial> just uses the argument fct as if it is a
function. It is not too hard to see that, given the above ifthenelse,
the above encodes the recursive definition of factorial in the obvious way.

Now comes the astonishing part: it is possible to write Y using
anonymous functions (both of which must be defined at the prompt
_before_ the assignment to fact. The first of these functions is
essentially feval, just renamed to show that all you really need is
application of function handles:

 >> apply = @(f,x) f(x);

The Y operator itself is completely unscrutable, at least to me:

 >> Y = @(f) apply(@(g)g(g), @(h)f(@(y) apply(h(h), y)));

I just typed these definitions to R2009a (in the order first, third,
fourth, second), followed by:

 >> fact(5)

The result, as you would expect, is the same as gamma(6).

Not pretty anonymous functions, not a fast implementation, but some very
elegant mathematics.

for your enjoyment,
mike

Mike Karr <mkarr@mathworks.com> wrote in message <gp3jed$42m$1@fred.mathworks.com>...
>
> Not pretty anonymous functions, not a fast implementation, but some very
> elegant mathematics.
>
> for your enjoyment,

Indeed, and we wouldn't enjoy the thread if Matlab had a similar C-like conditional-expression (cond? foo : bar)

Bruno

Morning all,

Bruno:
The preparsing makes sense, so I believe I see what is happening.

Kenneth:
Thanks for your examples. Its interesting to see others have tried similar
attempts at recursion.


Mike:
Thank you for your thorough explanation.
I recall the Y-combinator from a lambda calculus course I have previously
done.
It never occured to me to use this method but it makes perfect sense.

It has also got me thinking if one was to implement most of the lambda
calculus contructs as anonymous functions, it might be possible to create a
lisp-like calculation system using anonymous functions.

Thanks all

Brandon

"Brandon" <bnavra.removethis@student.usyd.edu.au.removethis> wrote
> a lisp-like calculation system using anonymous functions.
>
Actually, the description lisp-like is not correct. Maybe lambda expression evaluator is a better one

"Brandon" <bnavra.remove.this@student.usyd.edu.au.remove.this> wrote in message <gp425t$b6k$1@fred.mathworks.com>...
> "Brandon" <bnavra.removethis@student.usyd.edu.au.removethis> wrote
> > a lisp-like calculation system using anonymous functions.
> >
> Actually, the description lisp-like is not correct. Maybe lambda expression evaluator is a better one

Mike, et al.,

A very interesting thread, but I thought that the point of a fixed point combinator such as the Y combinator was that it transformed a recursive function to a non-recursive function. Yet when I enter the following at the Matlab R2009a prompt:

ifthenelse = @(b,varargin) varargin{2-b}();
apply = @(f,x) f(x);
Y = @(f) apply(@(g)g(g), @(h)f(@(y) apply(h(h), y)));
fact = Y(@(fct)@(n)ifthenelse(n==0 ,@()1, @()n*fct(n-1)));

and then type:

fact(100)

I get the following error:

??? Maximum recursion limit of 500 reached. Use set(0,'RecursionLimit',N)
to change the limit. Be aware that exceeding your available stack space
can crash MATLAB and/or your computer.
Error in ==> @(h)f(@(y)apply(h(h),y))


What's the deal? Is there a bug in the code above or does this have to do with how Matlab is handling function calls and anonymous functions? My eyes hurt from trying to parse this, but it looks like the apply function is calling itself in the definition for Y.

Cheers,
-- Andrew