Maxima/Ecl on 32-bit machine cannot evaluate "apply(union, listify({{..}}))"

On Tue, Sep 02, 2008 at 02:44:21PM -0400, Stavros Macrakis wrote:
> On Tue, Sep 2, 2008 at 2:03 PM, Oliver Kullmann <O.Kullmann at swansea.ac.uk>wrote:
> 
> > 1) I did run
> > for N step 10 thru 5000 do (print(N), apply(union, create_list({},i,1,N)));
> > on all machines (32 / 64 bits), with ECL (5.16.3) and CLisp (5.15.0,
> > 5.16.3),
> > and none showed any problems.
> >
> 
> Interesting.  Maxima 5.15.0/GCL fails at 71.  Another interesting fact: it
> fails differently if you use the interpretive version of nset, presumably
> because it is using a different function call mechanism.
> 
> 
> > This would have surprised me anyway, since set-operations are the
> > bread-and-butter
> > of my library, and I'm typically performing much larger unions,
> > intersections etc.
> > (in Maxima).
> >
> 
> I'd still recommend you use xreduce rather than apply....  Are you sure your
> results are correct?  Can you share code with us which performs much larger
> unions and intersections?
>

Hm, the simplest example (from my "OKlibrary", at http://www.ok-sat-library.org/):

--------------

var_l(x) := abs(x)$ 
var_sl(C) := map(var_l, C)$
var_cs(F) := var_sl(apply(union,listify(F)))$
nvar_cs(F) := length(var_cs(F))$

corr_cartesian_product([S]) := if emptyp(S) then {[]}
 else apply(cartesian_product,S)$
setn(n) := setify(create_list(i,i,1,n))$

all_tass(V) := map(setify,apply(corr_cartesian_product, 
 map(lambda([v],{-v,v}),listify(V))))$

full_fcs_v(V) := [V,all_tass(V)]$
full_fcs(n) := full_fcs_v(setn(n))$

-----------------------

(For the example we consider, one can simplify these definitions,
but that's a "real life example".)

Here "nvar_cs(F)" computes the number of variables in clause-set F, where
a clause-set (in the simplest case) is a set of sets of integers. 

full_fcs(n) for natural number n is the "formal clause-set" (a pair [V,F],
where V is a set of variables, and F is a clause-set over V) consisting
of all clauses of length n over {1, ..., n}.

E.g.:

(%i10) full_fcs(3);
Evaluation took 0.0000 seconds (0.0013 elapsed) using 12.562 KB.
(%o10) [{1,2,3},{{-3,-2,-1},{-3,-2,1},{-3,-1,2},{-3,1,2},{-2,-1,3},{-2,1,3},{-1,2,3},{1,2,3}}]

So full_fcs(n) has 2^n clauses, and when computing nvar_cs(full_fcs(n)[2]) = n,
2^n clauses are union-ed. Now with ECL on my 64-bit machine (I don't have
a 32-bit machine at hand in my office) one can go up to n=16 (for bigger n
one gets "CALL-ARGUMENTS-LIMIT exceeded").
CLisp is not that restricted, and for example
(%i3) length(var_cs(full_fcs(20)[2]));
Evaluation took 847.3130 seconds (851.3753 elapsed) using 2800.066 MB.
(%o3) 20

----------------------------------


> 
> > Remark: One should deprecate "makelist", since
> >  - create_list is much more powerful
> >
> 
> create_list has a design flaw in the multi-index case; see the discussion
> archive under "[Maxima] makelist vs create_list" from 4/6/07
>

The example given is obvious, and thus doesn't cause any design problem with me
--- finally we are using Lisp here, where such things in my opinion are
absolutely common.

A "real" design flaw is only exposed by user experience, and I use create_list
all over the place (while makelist is abolished), and I never experienced any
problems.
 
> 
> >  - makelist has a bug when the loop is empty
> 
> 
> What is this bug (has it been reported?)?  Can't it be fixed?  Or is it a
> design flaw?  As far as I can tell, makelist(print(i),i,0,-1) and
> makelist(print(i),i,[])

(%i7) makelist(i,i,0,-2);
If 4 arguments are given to MAKELIST, the difference of the 3rd and 4th arguments should evaluate to a non-negative integer:
-2
 -- an error.  To debug this try debugmode(true);

A list should be, like the empty sum, empty when the upper bound is smaller than the lower bound.
So one had already to write a wrapper for makelist, to protect against that failure.
create_list doesn't have such problems.

> 
> 
> >   - create_list is quite a bit faster when it comes to big
> >   lists (while not being slower for small lists).
> >
> 
> Let's get the semantics right first, then we can figure out efficient
> implementations.
>

The semantics of create_list are correct (the above discussion is about the
user interface). And with make_list no "serious" list-creations are possible,
consider just such trivial examples:

(%i4) makelist(makelist(i,i,1,100),j,1,1000)$
Evaluation took 14.3929 seconds (14.3908 elapsed) using 103.287 MB.
(%i5) create_list(create_list(i,i,1,100),j,1,1000)$
Evaluation took 0.2640 seconds (0.2649 elapsed) using 4.746 MB.
(%i6) makelist(makelist(i,i,1,1000),j,1,1000)$
Evaluation took 142.8049 seconds (144.8713 elapsed) using 1023.392 MB.
(%i7) create_list(create_list(i,i,1,1000),j,1,1000)$
Evaluation took 2.5162 seconds (2.5166 elapsed) using 45.944 MB.

makelist is absolute useless, and a trap! It cost my group altogether, say,
10 hours to reliably(!) remove all occurrences of makelist once we become
aware of what a resource hog it is (time and space).
 
------------------------------------------------

Back to the case at hand ;-)

> This probably loads the interpretive version, which in many Lisp
> implementations handles function calling slightly differently, notably not
> having the same limitations on number of arguments. Perhaps CLisp does not
> handle >63 arguments correctly, but doesn't trigger an error, but instead
> continues computing with rubbish?
>

I have a quite extensive test system, and Maxima/CLisp works alright (w.r.t. these
operations).

Oliver