RE: [Caml-list] @, List.append, and tail recursion

["Andrew Kennedy" <akenn@microsoft.com>]

Brian,

The optimization you describe is sometimes known as
"tail modulo cons", and is an example of "destination-passing
style". In other words, the place to put the result (in
this case, the address of the tail of a just-constructed 
cons cell) is passed on in a tail-recursive call.

See "A Functional Representation of Data Structures with a Hole"
by Minamide in POPL'98.

http://www.score.is.tsukuba.ac.jp/~minamide/index.html

Although Minimide formalizes the problem in the context of
a typed intermediate language, it's probably quite easy to 
spot special cases quite far down the compiler pipeline.
- Andrew.

> -----Original Message-----
> From: Brian Hurt [mailto:brian.hurt@qlogic.com] 
> Sent: Friday, January 24, 2003 12:48 AM
> To: Ocaml Mailing List
> Subject: [Caml-list] @, List.append, and tail recursion
> 
> 
> 
> I hit a bug recently wiith @ and List.append.  Since they're 
> recursive, 
> not tail-recursive, on long enough lists Ocaml thinks you've gone 
> infinitely recursive and aborts.  The code:
> 
> 
> let longlist len =
>     let rec longlist_int v c acc =
>         if (c == 0) then acc else longlist_int (v + 1) (c - 
> 1) (v :: acc)
>     in
>     longlist_int 0 len []
> ;;
> 
> let x = longlist 65536 ;;
> 
> List.append x [] ;;
> 
> Exits with:
> 
> Stack overflow during evaluation (looping recursion?).
> 
> So does:
> x @ [] ;;
> 
> You can work around this like:
> 
> let append' a b =
>    List.rev_append (List.rev a) b
> ;;
> 
> Since both rev_append and rev are tail recursive (looping) and not 
> recursive, this works.  But some ad-hoc testing says that 
> this method is 
> about 50% slower than normal append for lists short enough 
> not to abort.
> 
> Thinking about this, I realized that my code is doing stuff 
> like this all over the place.  I'm basically doing sparse 
> vector/matrix stuff, handling
> (effectively) (colno * value) list for vectors, and (rowno * 
> vector) list for matrix.  And I may be hitting lists long 
> enough to trip the problem.
> 
> Which means I'm currently doing a lot of recursion of the form:
> 
> let rec foo x = 
>    match x with
>        [] -> []
>        | head :: tail -> (expr head) :: (foo tail)
> ;;
> 
> for various complexities.  And it has occured to me that all of these 
> forms *should* be optimizable into loops.  The general case 
> would work 
> something like this in C:
> 
> struct list_t {
>     void * datum;
>     struct list_t * next_p;
> }
> 
> struct list_t * foo (struct list_t * x) {
>     struct list_t * retval = NULL;
>     struct list_t ** ptr_pp = &retval;
> 
>     while (x != NULL) {
>         struct list_t * temp = alloc(sizeof(struct list_t));
>         *ptr_pp = temp;
>         temp->datum = expr(x->datum);
>         temp->next_p = NULL; /* be nice to the GC */
>         ptr_pp = &(temp->next_p);
>         x = x->next_p;
>     }
>     return retval;
> }
> 
> If expr() returned a list, the only change necessary would be 
> to find the 
> end of the list before moving on, like:
> 
> struct list_t * foo (struct list_t * x) {
>     struct list_t * retval = NULL;
>     struct list_t ** ptr_pp = &retval;
> 
>     while (x != NULL) {
>         *ptr_p = expr(x->datum); /* expr allocates the list */
>         /* We assume the last element of the list expr() returned has
>          * NULL for next_p.
>          */
>         while (*ptr_p != NULL) {
>            ptr_p = &((*ptr_p)->next_p);
>         }
>         x = x->next_p;
>     }
>     return retval;
> }
> 
> Rather than just looking at making @ an inline C function, I 
> think we (the 
> Ocaml community) should be looking at adding this more general 
> optimization in.
> 
> So now we get to my two questions:
> a) is anyone working on this/intending to work on this RSN?
> b) if the answer to (a) is no, can anyone give me some 
> pointers on where 
> to start looking at code, so I can add it in?
> 
> Brian
> 
> 
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr Archives: 
http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs
FAQ: http://caml.inria.fr/FAQ/ Beginner's list:
http://groups.yahoo.com/group/ocaml_beginners
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners