foldl generating Bind-stack overflow in Maxima

Question

I wrote a function that shall perform foldl similar to Haskell in Maxima,

  foldl(f,ac,li):=block([con:[],acc:ac],/*print("List=",li,ac),*/
                  if (is(li#[])) then 
                 (acc:apply(f,cons(acc,[first(li)])),
                  acc:foldl(f,acc,rest(li))),acc)$

And it works fine in folding the list from left side and evaluating along the way hence preventing any accumulation of long unevaluated expression in buffer.

The problem I am facing in running this with,

foldl(lambda([x,y],x+y),0,makelist(i,i,1,97));

Error in PROGN [or a callee]: Bind stack overflow.

But if I run it upto 96, it generates result appropriately. I don't understand why is this simple addition causing problem as I don't have any infinte loop or memory hungry task going on.

Answer 1

Well, foldl is defined as a recursive function, and it will call itself as many times as there are elements in the list. So whether it works depends on the Lisp implementation-specific limit for the function call stack. For GCL it seems the limit is relatively small. For other Lisp implementations, the limit is greater. But the only way to make it work for all sizes of the list is to write it iteratively.

There are built-in functions similar to foldl -- see lreduce, rreduce, xreduce, and tree_reduce.