Recursive iteration of a function getting stack overflows

Question

I'm trying to write a Maxima function that iterates another function provided as an argument. The goal is basically...

iter(f,0) ........ gives the identity function lambda([x],x)
iter(f,1) ........ gives f
iter(f,2) ........ gives lambda([x],f(f(x))
iter(f,3) ........ gives lambda([x],f(f(f(x)))

The reason is trying to figure out how an iterated polynomial behaves - similar to the Robert May population equation, but a different polynomial.

Anyway, I'm very new to Maxima (at least to things that seem more like simple programming than just asking for a solution) and after some time trying to figure out what I'm doing wrong, I think I've eliminated all silly mistakes and I must have a more fundamental misunderstanding of how Maxima works.

What I have...

iter(f,n) := if is (n=0)
  then lambda ([x], x)
  else block ([n2: floor (n/2),
               nr: is (n2*2#n),
               ff: iter (f,n2) ], if nr then lambda ([x],f(ff(ff(x))))
                                        else lambda ([x],  ff(ff(x)) ));

Maxima accepts this. Now as a simple example function to iterate...

inc(x):=x+1;

And some tests - first the base case...

iter(inc,0);

That works - it gives lambda([x],x) as expected. Next, "iterating" one time...

iter(inc,1);

I'm expecting something equivalent to inc, but because of the way this is written, more like lambda([x],inc(identity(identity(x))) but with more clutter. What I'm actually getting is a stack overflow...

Maxima encountered a Lisp error:
Control stack exhausted (no more space for function call frames).
This is probably due to heavily nested or infinitely recursive function
calls, or a tail call that SBCL cannot or has not optimized away.
...

I can't see why the is (n=0) base-case check would fail to spot that in the recursive call, so I can't see why this iter function would be entered more than twice for n=1 - it seems pretty extreme for that the exhaust the stack.

Of course once I have the basic idea working I'll probably special-case n=1 as effectively another base case for efficiency (a less cluttered resulting function definition) and add more checks, but I just want something that doesn't stack-overflow in trivial cases for now.

What am I misunderstanding?

Answer 1

What if you do everything with expressions?

(%i1) iter(e, n):= block([ans: e], thru n - 1 do ans: subst('x = e, ans), ans) $

(%i2) iter(x^2 + x, 1);
                                     2
(%o2)                               x  + x
(%i3) iter(x^2 + x, 2);
                                2     2    2
(%o3)                         (x  + x)  + x  + x
(%i4) iter(x^2 + x, 3);
                     2     2    2     2     2     2    2
(%o4)             ((x  + x)  + x  + x)  + (x  + x)  + x  + x

You can define a function at the end:

(%i5) define(g(x), iter(x^2 + x, 3));

Answer 2

Here's what I came up with. It's necessary to substitute into the body of lambda since the body is not evaluated -- I guess you have encountered this important point already.

(%i3) iter(f, n) := if n = 0 then identity elseif n = 1 then f
            else subst([ff = iter(f, n - 1),'f = f],
                       lambda([x], f(ff(x)))) $
(%i4) iter(inc, 0);
(%o4)                       identity
(%i5) iter(inc, 1);
(%o5)                          inc
(%i6) iter(inc, 2);
(%o6)               lambda([x], inc(inc(x)))
(%i7) iter(inc, 3);
(%o7)             lambda([x], inc(inc(inc(x))))
(%i8) iter(inc, 4);
(%o8)          lambda([x], inc(inc(inc(inc(x)))))
(%i9) inc(u) := u + 1 $
(%i10) iter(inc, 4);
(%o10)               lambda([x], inc(x + 3))
(%i11) %(10);
(%o11)                         14
(%i12) makelist (iter(cos, k), k, 0, 10);
(%o12) [identity, cos, lambda([x], cos(cos(x))), 
lambda([x], cos(cos(cos(x)))), lambda([x], 
cos(cos(cos(cos(x))))), lambda([x], cos(cos(cos(cos(cos(x)))))), 
lambda([x], cos(cos(cos(cos(cos(cos(x))))))), 
lambda([x], cos(cos(cos(cos(cos(cos(cos(x)))))))), 
lambda([x], cos(cos(cos(cos(cos(cos(cos(cos(x))))))))), 
lambda([x], cos(cos(cos(cos(cos(cos(cos(cos(cos(x)))))))))), 
lambda([x], cos(cos(cos(cos(cos(cos(cos(cos(cos(cos(x)))))))))))]
(%i13) map (lambda([f], f(0.1)), %);
(%o13) [0.1, 0.9950041652780257, 0.5444993958277886, 
0.8553867058793604, 0.6559266636704799, 0.7924831019448093, 
0.7020792679906703, 0.7635010336918854, 0.7224196362389732, 
0.7502080588752906, 0.731547032044224]

Maxima is almost good at stuff like this -- since it is built on top of Lisp, the right conceptual elements are present. However, the lack of lexical scope is a serious problem when working on problems like this, because it means that when you refer to f within a function definition, it is the same f which might exist outside of it. When the solution depends on carefully distinguishing which f you mean, that's a problem.

Anyway as it stands I hope this solution is useful to you in some way.

Answer 3

Earlier, after a moment of inspiration, I tried the following in Maxima...

block([a:1,b:a],b);

This gave me a where I was expecting 1, which suggests that the b:a variable definition cannot see the a:1 variable definition earlier in the same block. I had assumed that later variable definitions in a block would be able to see earlier definitions, and that affects two variable definitions in my iter function - in particular, iter (f,n2) cannot see the definition of n2 which breaks the base-case check in the recursion.

What I have now (WARNING - NOT A WORKING SOLUTION) is...

iter(f,n) := if is (n=0)
  then lambda ([x], x)
  else block ([n2: floor (n/2)],
           block ([g: iter (f,n2)],
               if is (n2*2#n) then lambda ([x],f(g(g(x))))
                              else lambda ([x],  g(g(x)) )));

I'm nesting one block inside another so that the later variable definition can see the earlier one. There is no nr (n was rounded?) variable, though TBH keeping that wouldn't have required a third nested block. I replaced ff with g at some point.

This solves the stack overflow issue - the base case of the recursion seems to be handled correctly now.

This still isn't working - it seems like the references to g now cannot see the definition of g for some reason.

iter(inc,0) ................. lambda([x],x)
iter(inc,1) ................. lambda([x],f(g(g(x))))
iter(inc,2) ................. lambda([x],g(g(x)))
...

When the recursive half-size iteration g is needed, for some reason it's not substituted. Also noticable - neither is f substituted.

As a best guess, this is probably due to the function calls being by-name in the generated lambda, and due to nothing forcing them to be substituted in or forcing the overall expression to be simplified.

(update - This SO question suggests I've understood the problem, but the solution doesn't appear to work in my case - what I'm trying to substitute is referenced via a variable no matter what.)

But it's also a different question (it's not a recursion/stack overflow issue) so I'll come back and ask another question if I can't figure it out. I'll also add a working solution here if/when I figure it out.

---

I tried a few more approaches using subst and the double-quote notation, but Maxima stubbornly kept referring to f and g by name. After a little thought, I switched approach - instead of generating a function, generate an expression. The working result is...

iter(v,e,n) := if is (n=0)
  then ''v
  else block ([n2: floor (n/2)],
           block ([g: iter (v,e,n2)],
               block ([gg: subst([''v=g], g)],
                   if is (n2*2#n) then subst([''v=e], gg)
                                  else gg                )));

The three nested block expressions are annoying - I'm probably still missing something that's obvious to anyone with any Maxima experience. Also, this is fragile - it probably needs some parameter checks, but not on every recursive call. Finally, it doesn't simplify result - it just builds an expression by applying direct substitution into itself.