Lisp type list, recursion and tail call optimisation 
Author Message
 Lisp type list, recursion and tail call optimisation

I just implemented a Lisp or Scheme style of list collection, which I
find extremely useful and elegant for certain applications. One
interesting problem is that the semantics for this kind of list are
very different than Smalltalk. For example, list changing operations
are non-destructive. So for example, on a #remove: , if the element is
in the first position, then the answer is simply the sublist starting
at the 2nd position. So this means that #remove: implemented this way
cannot return the object being removed (not necessarily identical to
the argument), like in Smalltalk, since it must return the new list.
More of a functional approach.

Most of the usual operations on lists in Scheme utilize recursion
instead of iteration. For example, #remove: would have an recursive
invocation for each element it visited until it hit the element to
remove. I'm sure Dolphin doesnt do tail-call optimisation (do any
smalltalks?). So I am curious as to how practical it would be
performance-wise, to implement functions like this recursively in
Dolphin, ie what is the cost of an activation and what are the
practical limits on the depth. (Actually I think the number of
activations would be roughly the same as an iterative version, but in
the recursive version (without tail-call optimization) they are all in
the stack at the same time).

Tue, 17 Aug 2004 07:40:36 GMT  
 [ 1 post ] 

 Relevant Pages 

1. Tail recursion optimisation?

2. Free Lisp with proper tail recursion?

3. Tail call recursion in Haskell?

4. Tail recursion and complete recursion?

5. Tail Calls and Mutual Recursion

6. implicit tail optimisation

7. OO, lexical scope, closure, tail-recursion, continuation

8. Tail recursion ???

9. Tail recursion

10. Thanks for the tail recursion

11. How is tail-recursion optimized in Smalltalk?

12. Any Smalltalk supporting tail recursion optimization ?


Powered by phpBB® Forum Software