This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

RE: [Caml-list] @, List.append, and tail recursion
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2003-01-24 (15:35) From: Andrew Kennedy Subject: RE: [Caml-list] @, List.append, and tail recursion
```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.
>
> 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
>        [] -> []
> ;;
>
> 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

```