Home     About     Download     Resources     Contact us

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

Browse thread
[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: -- (:) From: Brian Hurt 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

```