Hello,
The current implementation of scan over list uses the following
defined in FLAGG2:
scan(fn, l, ident) ==
empty? l => empty()
val := fn(first l, ident)
concat(val, scan(fn, rest l, val))
The recursion implementation will exhaust stack when the input data is
large. For instance:
(18) -> l := [i for i in 1..20000];
Type: List PositiveInteger
(19) -> scan(+, l,0);
INFO: Control stack guard page unprotected
Control stack guard page temporarily disabled: proceed with caution
>> System 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.
PROCEED WITH CAUTION.
Therefore, I'm proposing the following iterative implementation
scan(fn, l, ident) ==
w := empty()$B
empty? l => w
vl := ident
for a in entries l repeat
vl := fn(a, vl)
w := concat(w, vl)
w
which is similar to the one used by vectors, except I don't use
qsetelt! since the scan over list is defined under the predicate
B has ListAggregate(R) or not(B has shallowlyMutable)
Testing result:
(17) -> l := [i for i in 1..20000];
Type: List PositiveInteger
(18) -> scan(+, l, 0);
Type: List NonNegativeInteger
This computation takes about 15 seconds.
Comments are welcome!
Best,
Yue
------------------------------------------------------------------------------
The Palm PDK Hot Apps Program offers developers who use the
Plug-In Development Kit to bring their C/C++ apps to Palm for a share
of $1 Million in cash or HP Products. Visit us here for more details:
http://p.sf.net/sfu/dev2dev-palm
_______________________________________________
open-axiom-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/open-axiom-devel
