I'm wondering why copylist in Arc 3.1 isn't tail-recursive. (def copylist (xs)
(if (no xs)
nil
(cons (car xs) (copylist (cdr xs)))))
sort copies lists, so sort requires a lot of stack space
also.MzScheme seems to deal with this really well, I suspect
it calls malloc() to make the stack bigger when needed. Unfortunately, Jarc falls over with a StackOverflowError. So I'm replacing copylist in Jarc with something like (def copylist2 (xs (o acch) (o acct))
(if (no xs)
acch
(no acch)
(do
(assign acch (cons (car xs) nil))
(copylist2 (cdr xs) acch acch))
(copylist2 (cdr xs) acch (scdr acct (cons (car xs) nil)))))
I tried the tail-recursive copylist2 in Arc 3.1 and it
runs 9 times slower than the original. arc> (let td (n-of 10000 t) (time (copylist td)) 1)
time: 3 msec.
1
arc> (let td (n-of 10000 t) (time (copylist2 td)) 1)
time: 27 msec.
1
The scdr solution is so slow that it's faster to
iterate the list twice and copy it twice! (def copylist4 (xs (o acc))
(if (no xs)
(rev acc)
(copylist4 (cdr xs) (cons (car xs) acc))))
arc> (let td (n-of 10000 t) (time (copylist4 td)) 1)
time: 7 msec.
The rev solution takes about twice as long
as the original. That makes sense since it does twice
as many cons calls.So copylist appears to be optimal as it is. Fortunately in Jarc, copylist2 is only twice as slow
as copylist. That seems reasonable since it does N scdr
calls in addition to the N cons calls, assuming the car
and cdr calls are much faster than cons and scdr. I can
live with that to avoid the StackOverflowError. | 
