caml-list - the Caml user's mailing list
 help / color / mirror / Atom feed
* RE: [Caml-list] @, List.append, and tail recursion
@ 2003-01-31 19:58 Harrison, John R
  2003-01-31 21:04 ` Brian Hurt
  0 siblings, 1 reply; 24+ messages in thread
From: Harrison, John R @ 2003-01-31 19:58 UTC (permalink / raw)
  To: caml-list; +Cc: Harrison, John R

How about the following policy?

  Don't place any limit on stack growth

The stack, like the heap, should be capable of expanding to
fill all available memory. I don't know much about the OS issues
involved in stack extension, but some such policy seems preferable
to building in a hard limit.

Users would then be free to write relatively inefficient and
stack-hungry recursive functions, and at least the implementation
would do its best to carry recursions as far as possible. The only
reason I can see for placing a limit on the stack size is that users
become aware of trivially looping recursions more quickly. But this
doesn't seem a particularly strong argument.

Since I sometimes use non-tail-recursive functions on lists, I often
start my OCaml code with the following line:

  Gc.set { (Gc.get()) with Gc.stack_limit = 16777216 };; (* Up the stack
size  *)

so that my program doesn't die when occasionally dealing with longish
lists, while being simple and efficient for the common case of short
ones. Of course, if this balance were different, I might use another
data structure and/or alternative algorithms.

John.
-------------------
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


^ permalink raw reply	[flat|nested] 24+ messages in thread
* RE: [Caml-list] @, List.append, and tail recursion
@ 2003-01-31 22:27 Harrison, John R
  0 siblings, 0 replies; 24+ messages in thread
From: Harrison, John R @ 2003-01-31 22:27 UTC (permalink / raw)
  To: 'Brian Hurt'; +Cc: caml-list, Harrison, John R

| Actually, recursion seems to be very cheap- the recursive append function 
| is signifigantly faster than the reversing append, and almost as fast as 
| the set_cdr function.

Yes indeed. This is why I think we shouldn't discourage people from using
recursion by imposing arbitrary depth limits.

| > and at least the implementation
| > would do its best to carry recursions as far as possible. The only
| > reason I can see for placing a limit on the stack size is that users
| > become aware of trivially looping recursions more quickly. But this
| > doesn't seem a particularly strong argument.
|
| I like becoming aware of problems in my code as quickly as possible.  It 
| lets me fix them quicker.

Surely looping recursions aren't such a common problem that it really
matters much? And one has other cues, like the excessive time taken by the
evaluation.

John.
-------------------
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


^ permalink raw reply	[flat|nested] 24+ messages in thread
* Re: [Caml-list] @, List.append, and tail recursion
@ 2003-01-31 17:32 Diego Olivier Fernandez Pons
  0 siblings, 0 replies; 24+ messages in thread
From: Diego Olivier Fernandez Pons @ 2003-01-31 17:32 UTC (permalink / raw)
  To: caml-list

    Bonjour,

Brian Hurt wrote :

> Here's an example I have run across.  I'm working with sparse vectors, and
> basically storing them as (int * float) lists.  Now, let's write the
> vector add function.  The naive implementation would be:

let rec add_rec result = fun a b ->
  match (a, b) with
    | ([], _) -> a @ result
    | (_, []) -> b @ result
    | ((n, x) :: a_tail, (m, y) :: b_tail) ->
       match compare m n with
         | k when k < 0 -> add_rec ((n, x) :: result) a_tail b
         | k when k > 0 -> add_rec ((m, y) :: result) a b_tail
         | _ -> add_rec ((n, x +. y) :: result) a_tail b_tail


This is a tail recursive version of your function. The main problem is
that it reverses the list every time it is called.

Your first idea is to define

let add = fun a b -> List.rev (add_rec a b)

and you are right when you say that you are allocating a lot of
memory. But you can do much better : add_rec only needs the two lists
to be sorted, not to be increasing.

Why don't you try

type vector =
  | Increasing of (int * float) list
  | Decreasing of (int * float) list

then you just have to write the 4 corresponding add functions

Here is a second idea : is there a way to implement add in such a way
that it does not need the two arguments to be sorted ? If you were
working with arrays this would not be difficult.

Then, just try functional random acces lists. They give you a O(1)
access to the head element (in case both list are sorted in the same
way) or O(log n) acces to any element.


        Diego Olivier


-------------------
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


^ permalink raw reply	[flat|nested] 24+ messages in thread
* RE: [Caml-list] @, List.append, and tail recursion
@ 2003-01-24 15:35 Andrew Kennedy
  2003-01-30  1:44 ` brogoff
  0 siblings, 1 reply; 24+ messages in thread
From: Andrew Kennedy @ 2003-01-24 15:35 UTC (permalink / raw)
  To: Brian Hurt, Ocaml Mailing List

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


^ permalink raw reply	[flat|nested] 24+ messages in thread
* [Caml-list] @, List.append, and tail recursion
@ 2003-01-24  0:48 Brian Hurt
  2003-01-30 18:10 ` Olivier Andrieu
  0 siblings, 1 reply; 24+ messages in thread
From: Brian Hurt @ 2003-01-24  0:48 UTC (permalink / raw)
  To: Ocaml Mailing List


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


^ permalink raw reply	[flat|nested] 24+ messages in thread
end of thread, other threads:[~2003-02-03  9:26 UTC | newest]

Thread overview: 24+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2003-01-31 19:58 [Caml-list] @, List.append, and tail recursion Harrison, John R
2003-01-31 21:04 ` Brian Hurt
  -- strict thread matches above, loose matches on Subject: below --
2003-01-31 22:27 Harrison, John R
2003-01-31 17:32 Diego Olivier Fernandez Pons
2003-01-24 15:35 Andrew Kennedy
2003-01-30  1:44 ` brogoff
2003-01-30  9:57   ` Christophe Raffalli
2003-01-30 16:03     ` Brian Hurt
2003-01-31 10:33     ` Mattias Waldau
2003-01-24  0:48 Brian Hurt
2003-01-30 18:10 ` Olivier Andrieu
2003-01-30 19:46   ` Brian Hurt
2003-01-30 20:52     ` Olivier Andrieu
2003-01-30 21:57       ` Brian Hurt
2003-01-31  2:16         ` james woodyatt
2003-01-31 17:05           ` Diego Olivier Fernandez Pons
2003-01-31 19:52             ` Brian Hurt
2003-01-31 21:34             ` Issac Trotts
2003-01-31 17:13           ` Brian Hurt
2003-01-31 17:42             ` brogoff
2003-01-31 19:18             ` Russ Ross
2003-01-31 19:32               ` Alexander V. Voinov
2003-02-01  2:30               ` brogoff
2003-01-31 23:12             ` Issac Trotts

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).