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

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

[Brian Hurt]

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

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

[Olivier Andrieu]

 Brian Hurt [Thursday 23 January 2003] :
 > 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. 

 > List.append x [] ;;
 > Exits with:
 > Stack overflow during evaluation (looping recursion?).
 > 
 > So does:
 > x @ [] ;;
(not surprising, List.append 's definition is (@))

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

Well, all of this can be translated directly to caml, using the famous
Obj module. All you need is a lispish setcdr function :

,----
| let setcdr : 'a list -> 'a list -> unit = fun c v -> 
|   let c = Obj.repr c in
|   assert(Obj.is_block c) ;
|   Obj.set_field c 1 (Obj.repr v)
`----

Then one can write a tail-recursive append or a tail-recursive map :
,----
| let tr_append l1 l2 =
|   let rec proc cell = function
|     | [] ->
| 	setcdr cell l2
|     | x :: l -> 
| 	let nxt = [ x ] in
| 	setcdr cell nxt ;
| 	proc nxt l
|   in
|   match l1 with
|   | [] -> l2
|   | x :: l ->
|       let head = [ x ] in
|       proc head l ;
|       head
| 	
| let tr_map f l = 
|   let rec proc cell = function
|     | [] -> ()
|     | x :: l -> 
| 	let nxt = [ f x ] in
| 	setcdr cell nxt ;
| 	proc nxt l
|   in
|   match l with
|   | [] -> [] 
|   | x :: l ->
|       let head = [ f x ] in
|       proc head l ;
|       head
`----
This seems safe to me, as setcdr is only called on new cons cells, so
it shouldn't mess up the arguments.

Anyway, the hole abstraction thing is cleaner but needs compiler
support. 

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

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

[Brian Hurt]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 3095 bytes --]


For short lists, this is the worst performer overall.  I whipped up a 
quick microbenchmark to compare the various implementations- the three 
implementations are included in this email.  The three programs are:

list1.ml: lappend uses the @ operator to append the list

list2.ml: uses local rev_append and rev functions (similiar to those in 
List) to append the list

list3.ml: uses Olivier's set_cdr function.

The results I saw (compiling with ocamlopt -o list list.ml on a 1.4GHz P4
running Linux and ocaml 3.06) are:

list1: 1.462s
list2: 1.757s
list3: 1.824s

List2 is about 17% slower than list1, while list3 is almost 20% slower 
than list1, and 4% slower than list2.

Brian


On Thu, 30 Jan 2003, Olivier Andrieu wrote:

>  Brian Hurt [Thursday 23 January 2003] :
>  > 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. 
> 
>  > List.append x [] ;;
>  > Exits with:
>  > Stack overflow during evaluation (looping recursion?).
>  > 
>  > So does:
>  > x @ [] ;;
> (not surprising, List.append 's definition is (@))
> 
>  > 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;
>  > }
> 
> Well, all of this can be translated directly to caml, using the famous
> Obj module. All you need is a lispish setcdr function :
> 
> ,----
> | let setcdr : 'a list -> 'a list -> unit = fun c v -> 
> |   let c = Obj.repr c in
> |   assert(Obj.is_block c) ;
> |   Obj.set_field c 1 (Obj.repr v)
> `----
> 
> Then one can write a tail-recursive append or a tail-recursive map :
> ,----
> | let tr_append l1 l2 =
> |   let rec proc cell = function
> |     | [] ->
> | 	setcdr cell l2
> |     | x :: l -> 
> | 	let nxt = [ x ] in
> | 	setcdr cell nxt ;
> | 	proc nxt l
> |   in
> |   match l1 with
> |   | [] -> l2
> |   | x :: l ->
> |       let head = [ x ] in
> |       proc head l ;
> |       head
> | 	
> | let tr_map f l = 
> |   let rec proc cell = function
> |     | [] -> ()
> |     | x :: l -> 
> | 	let nxt = [ f x ] in
> | 	setcdr cell nxt ;
> | 	proc nxt l
> |   in
> |   match l with
> |   | [] -> [] 
> |   | x :: l ->
> |       let head = [ f x ] in
> |       proc head l ;
> |       head
> `----
> This seems safe to me, as setcdr is only called on new cons cells, so
> it shouldn't mess up the arguments.
> 
> Anyway, the hole abstraction thing is cleaner but needs compiler
> support. 
> 
> 


[-- Attachment #2: uses @ operator --]
[-- Type: TEXT/PLAIN, Size: 271 bytes --]


let lappend x y = x @ [ y ] ;;

let makelist c =
    let rec makelist_int c accum =
        if (c > 0) then
            makelist_int (c - 1) (lappend accum c)
        else 
            (lappend accum c)
in
    makelist_int c []
;;

let _ = makelist 5000;;

[-- Attachment #3: uses List.rev --]
[-- Type: TEXT/PLAIN, Size: 581 bytes --]


let rec rev_append x y =
    match x with
        [] -> y
        | h :: t -> rev_append t (h :: y)
;;

let rev x =
    let rec rev_int x accum =
        match x with
            [] -> accum
            | h :: t -> rev_int t (h :: accum)
    in
        rev_int x []
;;

let lappend x y = 
    rev_append (rev x) ( [ y ] ) ;;

let makelist c =
    let rec makelist_int c accum =
        if (c > 0) then
            makelist_int (c - 1) (lappend accum c)
        else 
            (lappend accum c)
in
    makelist_int c []
;;

let _ = makelist 5000;;

[-- Attachment #4: uses Olivier's set_cdr --]
[-- Type: TEXT/PLAIN, Size: 778 bytes --]



let setcdr : 'a list -> 'a list -> unit = fun c v -> 
    let c = Obj.repr c in
    assert(Obj.is_block c) ;
    Obj.set_field c 1 (Obj.repr v)
;;

let lappend l1 l2 =
    let rec proc cell = function
        | [] ->
            setcdr cell l2
        | x :: l -> 
            let nxt = [ x ] in
                setcdr cell nxt ;
                proc nxt l
    in
    match l1 with
        | [] -> l2
        | x :: l ->
            let head = [ x ] in
                proc head l ;
                head
;;

let makelist c =
    let rec makelist_int c accum =
        if (c > 0) then
            makelist_int (c - 1) (lappend accum [ c ])
        else 
            (lappend accum [ c ])
in
    makelist_int c []
;;

let _ = makelist 5000;;

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

[Olivier Andrieu]

 Brian Hurt [Thursday 30 January 2003] :
 > For short lists, this is the worst performer overall.  I whipped up a 
 > quick microbenchmark to compare the various implementations- the three 
 > implementations are included in this email.  The three programs are:
 > 
 > list1.ml: lappend uses the @ operator to append the list
 > 
 > list2.ml: uses local rev_append and rev functions (similiar to those in 
 > List) to append the list
 > 
 > list3.ml: uses Olivier's set_cdr function.
 > 
 > The results I saw (compiling with ocamlopt -o list list.ml on a 1.4GHz P4
 > running Linux and ocaml 3.06) are:
 > 
 > list1: 1.462s
 > list2: 1.757s
 > list3: 1.824s

There's an assert in setcdr : it's important because the first
argument mustn't be an empty list. It's never the case here, so you
can safely compile with -noassert.

On my hardware list3 seems to be a teeny bit faster than list1 but
anyway, since list2 is just barely slower, I'm not sure it's worth the
trouble. 

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

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

[Brian Hurt]

On Thu, 30 Jan 2003, Olivier Andrieu wrote:

>  > list1: 1.462s
>  > list2: 1.757s
>  > list3: 1.824s
> 
> There's an assert in setcdr : it's important because the first
> argument mustn't be an empty list. It's never the case here, so you
> can safely compile with -noassert.

Doh!  OK- now, compiling with -noassert drops the time to 1.457 seconds 
(same machine, same environment)- to slightly better than the recursive 
version.

And for the record, I just tested with appending to a list of 500,000 
elements, and it worked OK.

> 
> On my hardware list3 seems to be a teeny bit faster than list1 but
> anyway, since list2 is just barely slower, I'm not sure it's worth the
> trouble. 
> 

Correctness rates higher in my book than performance.  I think it's bad
that @/List.append die due to stack overflow if the lists are too long.  
I'd perfer the reversing solution- which works correctly so long as there
is enough memory- over the recursive solution for that reason alone.

Your code is even better.  It gives the performance of the recursive 
version and the correctness of the reversing code- better yet, it doesn't 
allocate two whole copies of the array, allowing the code to work 
correctly in even more cases (when there is enough memory for one copy of 
the list but not two).

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

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

[james woodyatt]

everyone--

Earlier in this thread, I suggested using a queue if you are spending 
too much time in List.append.  Lack of optimized tail recursion is not 
really a factor compared to the waste of cycles involved in 
constructing a whole new list just to append a single element on the 
end.

Apparently, nobody seemed to notice what I was talking about.  So I'm 
going to try to make my point again.  Sorry if you got it the first 
time.

On Thursday, Jan 30, 2003, at 13:57 US/Pacific, Brian Hurt wrote:
> On Thu, 30 Jan 2003, Olivier Andrieu wrote:
>
>>> list1: 1.462s
>>> list2: 1.757s
>>> list3: 1.824s
>>
>> There's an assert in setcdr : it's important because the first
>> argument mustn't be an empty list. It's never the case here, so you
>> can safely compile with -noassert.
>
> Doh!  OK- now, compiling with -noassert drops the time to 1.457 seconds
> (same machine, same environment)- to slightly better than the recursive
> version.

For grins, I wrote an equivalent test program.  It uses a functional 
deque instead of a list.  (I have written one.  It's a component of my 
Cf library, which remains unreleased at the moment.  Markus Mottl has 
translated several of Chris Okasaki's functional queue implementations 
into Ocaml, and you can find them on the Hump.)

To get started, I timed the 'benchmarks' by running them on my iBook 
(the 700 MHz G3 model) so I could get a baseline.  My little iBook is 
nowhere near as fast as your cool 1.6GHz P4, but I'm not complaining.

The results of my tests were:

	$ time ./list1
	3.690u 0.070s 0:04.14 90.8%     0+0k 0+0io 0pf+0w

	$ time ./list2
	4.180u 0.020s 0:05.01 83.8%     0+0k 0+0io 0pf+0w
	
	$ time ./list3
	3.700u 0.000s 0:04.49 82.4%     0+0k 0+0io 0pf+0w

Not real fast, but fast enough that I don't mind waiting for results.  
So, what difference does my functional deque implementation make?  Glad 
you asked.

My Cf_deque module matches the following signature:

	(* begin cf_deque.mli *)
	type 'a t

	val nil: 'a t

	module type Direction_T = sig
	    val pop: 'a t -> ('a * 'a t) option
	    val push: 'a -> 'a t -> 'a t
	end

	module A: Direction_T
	module B: Direction_T

	val cat: 'a t -> 'a t -> 'a t
	(* end file *)

(Actually, this isn't the complete interface.  I've written a variety 
of ancillary functions that make it convenient to work with the objects 
in a deque without having to translate them into lists, e.g. fold, 
iterate, etc.)

All the functions above are purely functional, and they perform with 
O(1) average complexity.  (Or at least, that's my untrained analysis.  
I'd like to provide proof of that assertion, and I'm working on getting 
some help in that effort-- but, I'll have more news on that when I have 
it.)

Here's a variant of the list1.ml test above, which uses my Cf_deque 
module instead:

	(* begin t-opt.deque.ml *)
	open Cf_deque

	let rec makelist_aux c accum =
	  let accum = B.push c accum in
	  if c > 0 then makelist_aux (pred c) accum else accum

	let makelist c = makelist_aux c nil

	;;
	let _ = makelist 5000;;
	(* end file *)

Here are the timing results on that same iBook:

	$ time ./t-opt.deque
	0.010u 0.010s 0:00.02 100.0%    0+0k 0+0io 0pf+0w

In other words, it's done before enough time passes even to measure it 
properly.

> And for the record, I just tested with appending to a list of 500,000
> elements, and it worked OK.

Here is the result of running my version of the test with 500,000 
elements:

	$ time ./t-opt.deque
	0.450u 0.080s 0:00.75 70.6%     0+0k 0+0io 0pf+0w

It took under a second of wall-clock time.  On the other hand, when I 
modified list3.ml for 500,000 elements, it took *forever* in wall-clock 
time.  I gave up after almost an hour and a half.  Ultimately, I killed 
it with SIGINT before it finished.  I have no idea how far it got.

Clearly, I need to push a lot more elements into my deque before I will 
get a timing result that I can measure in heartbeats.  Here is the 
result for 5,000,000 elements:

	$ time ./t-opt.deque
	5.160u 0.510s 0:06.69 84.7%     0+0k 0+0io 0pf+0w

At this stage, I noticed my little iBook was just starting to thrash 
when the program finished.    So, I bumped it up to 50,000,000 
elements, because I like punishing my computer from time to time-- just 
to teach it respect.

At around 15 seconds into the run, the program turned into the 
psychedelic pizza delivery service: the pager went into fear and 
loathing mode, and the pretty Aqua GUI started acting like it was 
sniffing glue.  If I had let it run to completion, it probably would 
have wedged the machine.  (Mac OS X is pretty stable, but it hates 
resource bombs as much as any other operating system.)

None of the listN.ml files were able to bring down the machine like 
that, no matter how long I let them run-- which should make sense, 
right?  The APPEND function is O(N) for lists.  Once N gets beyond a 
few hundred, the program spends almost all its cycles just copying list 
cells inside its innermost loop, only occasionally reaching the end of 
a list and tacking a new cell onto the end before starting over again.

The problem is not the language, or the compiler.  The problem is the 
design of the program.  The moral of this story: you really should 
consider using a queue if you find your programs are spending a lot of 
cycles appending things to very long lists.


-- 
j h woodyatt <jhw@wetware.com>
that's my village calling... no doubt, they want their idiot back.

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

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

[Diego Olivier Fernandez Pons]

    Bonjour,

Some comments on various contributions to this thread

Brian Hurt wrote :

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

If you are doing sparse matrix operations and you still hit lists long
enough to cause a stack overflow, then your matrix must be really
huge.

If the ordrer of the terms does not matter (or if you can manage with
the position information you keep in your sparse matrix) then you just
need to write tail recursive functions, not taking care of the list
being reversed

let rec rev_map f result = function
  | [] -> result
  | head :: tail -> rev_map (f head) tail

An other solution is to use a suitable data structure for your
application : join-lists, catenable lists, double-linked lists ...

There are not many applications in which you just can't work around in
a simple way... In fact, the only one I know is Grobner bases
computation, because :
- the ordering on monomials really matters
- you have to handle a huge amount of information, even for small
systems

In this case, the only solution is to write you program in
C/assembler, with your own memory manager

Here is a extract of FGb web-site
(http://calfor.lip6.fr/~jcf/Software/index.html)

Limitations
* The size of the matrix in the F4 are limited to 50 000 x 50 000.
* The size of the biggest coefficient in the result is limited to 9000
digits.
* All the input polynomials must be expanded

Most of reasonable computations (even in computer algebra) can be made
in a functional language. Many computer algebra systems are written in
Lisp, and FOC (Formal + OCaml + Coq) should be soon avaible (spring
2003)

That is why I suspect you may not be using the best data structures
and algorithms avaiable. Could you explain what you are working on ?

Christophe Raffalli wrote :

> May be rev_append could be added to the list module (despite the
> fact it is trivial to write it yoursleft) ?

???

        Objective Caml version 3.06

# List.rev_append;;
- : 'a list -> 'a list -> 'a list = <fun>

> I agree that this is recurring problem, I myself often get bit by
> List.map
>
> It makes it very easy to make non-scalable program, works for input
> less that 1000 elements, and the when applied to a large problem it
> fails without a trace. It is very difficult to find the location of
> the problem if you use the native compiler, and most of these
> programs doesn't even work using the byte-code compiler.
>
> So one of my coding guidelines is:
> - do not use List.map
>
> I would like a prefer other solutions

If your program does not work for input less than 1000, this probably
means a poor design. You may be using lists where other data structure
should be used.

Could you give me code examples ? I could then add an adequate data
structure to Baire.

James woodyatt wrote :

> For grins, I wrote an equivalent test program. It uses a functional
> deque instead of a list. (I have written one. It's a component of my
> Cf library, which remains unreleased at the moment. Markus Mottl has
> translated several of Chris Okasaki's functional queue
> implementations into Ocaml, and you can find them on the Hump.)

You will find in Chris Okasaki's thesis/book several implementations
of catenable lists and many references. One of them embedds a queue in
a tree which seems to be what you are looking for (head in O(1),
append in O(1))

I wrote a linearisation of Okasaki's data structure. It has not been
revised yet then there could be some bugs.


        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

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

[Brian Hurt]

On Fri, 31 Jan 2003, Diego Olivier Fernandez Pons wrote:

>     Bonjour,
> 
> Some comments on various contributions to this thread
> 
> Brian Hurt wrote :
> 
> > 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.
> 
> If you are doing sparse matrix operations and you still hit lists long
> enough to cause a stack overflow, then your matrix must be really
> huge.

It'd be more accurate to say I'm not sure my lists will stay short enough.  
On average they are short enough and sparse enough to make using lists 
worthwhile.  I expect on average the lists will be about 20 elements or so 
long.  I should be able to stop thinking here- OK, I'm saving more than 
enough computation time on the average case that being inefficient on the 
rare case, where the lists has 30K or more elements in it, is OK.

But I want the rare case to *work* correctly, even if inefficiently.  With 
the "naive" non-tail-recursive implementation doesn't.  Somewhere above 
32K elements in the list the recursion trips the stack overflow.  Change 
the problem in some minor way, and suddenly I'm not generating lists with 
32K elements in them, maybe just 30K elements in them, and everything 
works OK.

Optimization is the wrong word.  As Olivier's set_cdr shows, the cost of
recursion isn't signifigant (kudos to the compiler team).  It's a
correctness issue more than anything:  the code *should* work.

> 
> If the ordrer of the terms does not matter (or if you can manage with
> the position information you keep in your sparse matrix) then you just
> need to write tail recursive functions, not taking care of the list
> being reversed

I am keeping the items in order.  Because if they're in order, I can write 
add in O(n).  If they're not in order, the best (fastest running) way to 
write add is to first sort both lists O(n log n) and then do the in-order 
add.

> An other solution is to use a suitable data structure for your
> application : join-lists, catenable lists, double-linked lists ...

Several reasons, actually:

1) I want to stay as strictly functional as possible.  I'm comming from an 
imperitive background, and thus want to limit how much I fall back on old 
habits.  If it can be done functionally (purely applicative), I want to do 
it that way.

2) The only thing I'm doing with the list that is at all a problem is 
non-tail-recursion list construction.  And this *should* work correctly.  
So why should I use some other datastructure when the list primitives do 
everything I need?  In fact, linked lists of some sort are exactly what I 
want- not even arrays.  I want to be able to start creating a list of 
elements without having to know how long it is, and I'm doing a lot of 
walking the list and basically no accessing random elements.  And I'm 
always walking the list in the same direction.

3) I perfer to solve the general problem than have to resolve the specific 
problem every time I hit it.  This is even worse because the problem is 
only likely to show up in production.  Test cases with small sets of data 
won't trigger the problem.

> 
> There are not many applications in which you just can't work around in
> a simple way... 

I don't want to have to work around it.

> In this case, the only solution is to write you program in
> C/assembler, with your own memory manager

You should only be programming in assembler if it absolutely cannot be 
written in C.  You should only be programming in C if you're directly 
banging on hardware.

> 
> That is why I suspect you may not be using the best data structures
> and algorithms avaiable. Could you explain what you are working on ?

The short form: solving a system of nonlinear equations via
Newton-Kantoravich (sp?).  Basically, I compute the Jacobian F'(X) (a
matrix of the partial differentials) and the residual F(X) (a vector) and
solve F'(X) * Y = F(X) to get my new, improved guess X' = X - Y.  Lather,
rinse, repeat, until F(X) is close enough to 0.  This is basically
Newton's method extended to deal with multiple equations in multiple
variables.

In production I wouldn't be surprised to see systems of 30,000+ equations
in 30,000+ variables.  The Jacobian matrix is going to be very sparse- I
expect the average row to have 20 or fewer non-zero elements.  Thus the 
attraction to sparse vectors.  I'm going to be solving it via Gaussian 
elimination (the Jacobian is likely to be malformed in multiple ways, 
meaning I can't use any iterative method I know of.  And yes, I've looked 
at iterative methods as advanced as GMRES- they don't work).  I think that 
in general I can bound the size of vectors I'm producing.  But there are 
degenerate cases where I could get above 30K non-zero elements in a 
vector.

The problem can't be solved at a higher level.  Sparse vectors are the way 
to go, and I can't gaurentee that I won't get sparse vectors of greater 
than 30K elements.

> You will find in Chris Okasaki's thesis/book several implementations
> of catenable lists and many references. One of them embedds a queue in
> a tree which seems to be what you are looking for (head in O(1),
> append in O(1))

O(1), or O(log n)?  Most tree operations are O(log n).

This is one of the things I considered, implementing the sparse vectors as 
trees- maps, effectively.  The problem is that most of the time I want to 
walk in-order through all non-zero elements of the vector.  With a 
tree/map, this is O(n log n).  With a list, it's O(n).

I don't see what the resistance here is.  Were I jumping up and down 
demanding someone else do the work, I could see the response being "it's 
not worth it to us".  Which is why I'm doing the work myself.  There are, 
from your point of view, two possibilities:

1) I succeed.  In which case, a new set of behaviors become efficient.  
Since you weren't using those behaviors anyways, you don't care- as 
nothing else changes.  Note that I am not proposing to change the 
semantics of the language.

2) I fail.  In which case nothing changes.  This includes I come up 
with something which breaks other stuff, at which point Xavier & co. go 
"Thanks, but no thanks".

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

Linear systems (was Re: [Caml-list] @, List.append, and tail recursion)

[Diego Olivier Fernandez Pons]

    Bonjour,

Sorry for the buggy code, anyway you should be able to fix it.

> In production I wouldn't be surprised to see systems of 30,000+
> equations in 30,000+ variables.  The Jacobian matrix is going to be
> very sparse- I expect the average row to have 20 or fewer non-zero
> elements.  Thus the attraction to sparse vectors.  I'm going to be
> solving it via Gaussian elimination (the Jacobian is likely to be
> malformed in multiple ways, meaning I can't use any iterative method
> I know of.  And yes, I've looked at iterative methods as advanced as
> GMRES- they don't work).  I think that in general I can bound the
> size of vectors I'm producing.  But there are degenerate cases where
> I could get above 30K non-zero elements in a vector.

A 30 000 x 30 000 system of equations is not a toy program. Then, do
not expect to solve it straightforwardly. You will obviously hit all
system limits (stack, cache, ...). You have to understand that if you
really want a robuts program in all cases, you will have to work :

You will have to design several data structures for every operation
you want (to keep both efficiency and generality) and transformation
functions. That is the case for example in the Gröbner basis system I
pointed out : several monomial orderings with many transformation
functions ...

You will have to use all Caml properties (functional, imperative ...)

You also need to understand roughtly how does the Caml compiler work
(boxing/ unboxing, garbage collection, ...)

> But I want the rare case to *work* correctly, even if inefficiently.  With
> the "naive" non-tail-recursive implementation doesn't.  Somewhere above
> 32K elements in the list the recursion trips the stack overflow.  Change
> the problem in some minor way, and suddenly I'm not generating lists with
> 32K elements in them, maybe just 30K elements in them, and everything
> works OK.

Your main problem is that sometimes your lists may be too big for the
data structure you have chosen. Then, the best thing to do is to have
two data structures, one for small (most of all) systems, a second one
for huge (but rare) systems.

- lists for small sparse vectors
- (say) hashtables for huge sparse vectors

You just need to write you own hashtable data structure (because you
can then profit of Caml's float array unboxing optimisation by
separate collision resolution)

type size = int

type vector =
  | List of size * (int * float) list
  | Hashtable of myhashtbl

Most of your code will be purely functional and the program will not
break on large data.

One more point : floating arithmetic may produce incorrect value by
error propagation, even for small systems. If you do want you system
to work properly for all data (even not well scaled), you will have to
use specific algorithms (pivot choice rules, error bounding, ...).
Then, list representation may not be apropriate.

> O(1), or O(log n)?  Most tree operations are O(log n).

It is easy to design a data structure with O(log n) acces to any
element and O(1) acces to the first one : imagine a list of increasing
perfect trees of size 2^k

        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

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

[Issac Trotts]

On Fri, Jan 31, 2003 at 06:05:30PM +0100, Diego Olivier Fernandez Pons wrote:
>     Bonjour,
> 
> Some comments on various contributions to this thread
> 
> Brian Hurt wrote :
> 
> > 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.
> 
> If you are doing sparse matrix operations and you still hit lists long
> enough to cause a stack overflow, then your matrix must be really
> huge.
> 
> If the ordrer of the terms does not matter (or if you can manage with
> the position information you keep in your sparse matrix) then you just
> need to write tail recursive functions, not taking care of the list
> being reversed
> 
> let rec rev_map f result = function
>   | [] -> result
>   | head :: tail -> rev_map (f head) tail

This doesn't work on OCaml 3.06:

  "This expression has type 'a but is here used with type 'b -> 'a"

How about 

  let rec rev_map f result = function
    | [] -> result
    | head :: tail -> rev_map f (f head :: result) tail;; 

  # map ((+) 3) [] [1;2;3;4;5];;
  - : int list = [8; 7; 6; 5; 4]

Issac

[snip]

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

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

[Brian Hurt]

On Thu, 30 Jan 2003, james woodyatt wrote:

> everyone--
> 
> Earlier in this thread, I suggested using a queue if you are spending 
> too much time in List.append.  Lack of optimized tail recursion is not 
> really a factor compared to the waste of cycles involved in 
> constructing a whole new list just to append a single element on the 
> end.
> 
> Apparently, nobody seemed to notice what I was talking about.  So I'm 
> going to try to make my point again.  Sorry if you got it the first 
> time.

I did get it the first time.  I'm just using List.append to illustrate a 
problem I'm having.

The problem is *constructing* lists.  If you can construct your list 
backwards, fine- but if you can't, you end up either not being tail 
recursive (and blowing up for long lists) or allocating the list twice.

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 x y = (* return x + y *)
    match (x, y) with
        ([], _) -> y
        | (_, []) -> x
        | (((xidx, xval) as xhead) :: xtail, 
           ((yidx, yval) as yhead) :: ytail)
        ->
            if (xidx == yidx) then
                (xidx, xval +. yval) :: (add xtail ytail)
            else if (xidx < yidx) then
                xhead :: (add xtail y)
            else
                yhead :: (add x ytail)
;;

It's simple, and obvious in both what it does and how it does it.  Except
opps, this isn't tail recursive.  If your sparse vectors might be 65536
elements long, this will blow up.  So we rewrite to be tail recursive:
 
let add x y = (* return x + y *)
    let add_int x y accum =
        match (x, y) with
            ([], _) -> (List.rev_append accum y)
            | (_, []) -> (List.rev_append accum x)
            | (((xidx, xval) as xhead) :: xtail, 
               ((yidx, yval) as yhead) :: ytail)
            ->
            if (xidx == yidx) then
                add_int xtail ytail ((xidx, xval +. yval) :: accum)
            else if (xidx < yidx) then
                add_int xtail y (xhead :: accum)
            else
                add_int x ytail (yhead :: accum)
;;

This makes the function truely tail recursive, except now it's allocating 
most of the returned vector twice (once as accum, and once in 
List.rev_append) and it's signifigantly uglier IMHO.  Rewritting the code 
to use set_cdr is the best performaner, but the ugliest yet.

And the add function is truely simple.  It can handle minor increases in 
ugliness without losing much.  But now consider something rather more 
complicated- say matrix transposition or matrix multiplication with
matricies defined as:

type vector_t = (int * float) list ;; (* index * value list *)
type matrix_t = (int * vector_t) list ;; (* row index * row vector list *)

Now minor uglification becomes major uglification.  It'd be nicer just to 
be able to be able to construct lists forwards instead of backwards.

List.append is just an obvious example to be talking about, but the 
problem is signifigantly more general.

Brian



> 
> On Thursday, Jan 30, 2003, at 13:57 US/Pacific, Brian Hurt wrote:
> > On Thu, 30 Jan 2003, Olivier Andrieu wrote:
> >
> >>> list1: 1.462s
> >>> list2: 1.757s
> >>> list3: 1.824s
> >>
> >> There's an assert in setcdr : it's important because the first
> >> argument mustn't be an empty list. It's never the case here, so you
> >> can safely compile with -noassert.
> >
> > Doh!  OK- now, compiling with -noassert drops the time to 1.457 seconds
> > (same machine, same environment)- to slightly better than the recursive
> > version.
> 
> For grins, I wrote an equivalent test program.  It uses a functional 
> deque instead of a list.  (I have written one.  It's a component of my 
> Cf library, which remains unreleased at the moment.  Markus Mottl has 
> translated several of Chris Okasaki's functional queue implementations 
> into Ocaml, and you can find them on the Hump.)
> 
> To get started, I timed the 'benchmarks' by running them on my iBook 
> (the 700 MHz G3 model) so I could get a baseline.  My little iBook is 
> nowhere near as fast as your cool 1.6GHz P4, but I'm not complaining.
> 
> The results of my tests were:
> 
> 	$ time ./list1
> 	3.690u 0.070s 0:04.14 90.8%     0+0k 0+0io 0pf+0w
> 
> 	$ time ./list2
> 	4.180u 0.020s 0:05.01 83.8%     0+0k 0+0io 0pf+0w
> 	
> 	$ time ./list3
> 	3.700u 0.000s 0:04.49 82.4%     0+0k 0+0io 0pf+0w
> 
> Not real fast, but fast enough that I don't mind waiting for results.  
> So, what difference does my functional deque implementation make?  Glad 
> you asked.
> 
> My Cf_deque module matches the following signature:
> 
> 	(* begin cf_deque.mli *)
> 	type 'a t
> 
> 	val nil: 'a t
> 
> 	module type Direction_T = sig
> 	    val pop: 'a t -> ('a * 'a t) option
> 	    val push: 'a -> 'a t -> 'a t
> 	end
> 
> 	module A: Direction_T
> 	module B: Direction_T
> 
> 	val cat: 'a t -> 'a t -> 'a t
> 	(* end file *)
> 
> (Actually, this isn't the complete interface.  I've written a variety 
> of ancillary functions that make it convenient to work with the objects 
> in a deque without having to translate them into lists, e.g. fold, 
> iterate, etc.)
> 
> All the functions above are purely functional, and they perform with 
> O(1) average complexity.  (Or at least, that's my untrained analysis.  
> I'd like to provide proof of that assertion, and I'm working on getting 
> some help in that effort-- but, I'll have more news on that when I have 
> it.)
> 
> Here's a variant of the list1.ml test above, which uses my Cf_deque 
> module instead:
> 
> 	(* begin t-opt.deque.ml *)
> 	open Cf_deque
> 
> 	let rec makelist_aux c accum =
> 	  let accum = B.push c accum in
> 	  if c > 0 then makelist_aux (pred c) accum else accum
> 
> 	let makelist c = makelist_aux c nil
> 
> 	;;
> 	let _ = makelist 5000;;
> 	(* end file *)
> 
> Here are the timing results on that same iBook:
> 
> 	$ time ./t-opt.deque
> 	0.010u 0.010s 0:00.02 100.0%    0+0k 0+0io 0pf+0w
> 
> In other words, it's done before enough time passes even to measure it 
> properly.
> 
> > And for the record, I just tested with appending to a list of 500,000
> > elements, and it worked OK.
> 
> Here is the result of running my version of the test with 500,000 
> elements:
> 
> 	$ time ./t-opt.deque
> 	0.450u 0.080s 0:00.75 70.6%     0+0k 0+0io 0pf+0w
> 
> It took under a second of wall-clock time.  On the other hand, when I 
> modified list3.ml for 500,000 elements, it took *forever* in wall-clock 
> time.  I gave up after almost an hour and a half.  Ultimately, I killed 
> it with SIGINT before it finished.  I have no idea how far it got.
> 
> Clearly, I need to push a lot more elements into my deque before I will 
> get a timing result that I can measure in heartbeats.  Here is the 
> result for 5,000,000 elements:
> 
> 	$ time ./t-opt.deque
> 	5.160u 0.510s 0:06.69 84.7%     0+0k 0+0io 0pf+0w
> 
> At this stage, I noticed my little iBook was just starting to thrash 
> when the program finished.    So, I bumped it up to 50,000,000 
> elements, because I like punishing my computer from time to time-- just 
> to teach it respect.
> 
> At around 15 seconds into the run, the program turned into the 
> psychedelic pizza delivery service: the pager went into fear and 
> loathing mode, and the pretty Aqua GUI started acting like it was 
> sniffing glue.  If I had let it run to completion, it probably would 
> have wedged the machine.  (Mac OS X is pretty stable, but it hates 
> resource bombs as much as any other operating system.)
> 
> None of the listN.ml files were able to bring down the machine like 
> that, no matter how long I let them run-- which should make sense, 
> right?  The APPEND function is O(N) for lists.  Once N gets beyond a 
> few hundred, the program spends almost all its cycles just copying list 
> cells inside its innermost loop, only occasionally reaching the end of 
> a list and tacking a new cell onto the end before starting over again.
> 
> The problem is not the language, or the compiler.  The problem is the 
> design of the program.  The moral of this story: you really should 
> consider using a queue if you find your programs are spending a lot of 
> cycles appending things to very long lists.
> 
> 
> 

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

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

[brogoff]

On Fri, 31 Jan 2003, Brian Hurt wrote:
> On Thu, 30 Jan 2003, james woodyatt wrote:
> > Apparently, nobody seemed to notice what I was talking about.  So I'm 
> > going to try to make my point again.  Sorry if you got it the first 
> > time.
> 
> I did get it the first time.  I'm just using List.append to illustrate a 
> problem I'm having.

You don't even need to be mapping to a particularly long list, since your 
mapping function may be consuming stack space too. 

The stuff using set_cdr was only ugly if you look under the hood. No one 
complains about other hidden uses of Obj, so that aproach may make sense 
as an immediate fix. 

The main point to me is that since there appears to be a reasonable approach to 
doing all of this stuff in a safe way that extends the power of ML, it may be a 
good idea to consider removing this limitation in a future (Ca)ML. There are 
only a few places where the language itself has annoying limitations, and I'm 
beginning to believe that this is one of them. The implementation provides a 
workaround as Olivier demonstrated, but the inability to express this in OCaml 
is a hole that perhaps needs to be filled (pun intended :).

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

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

[Russ Ross]

I'd just like to agree with Brian on this.  We seem to have a split
in this thread and the two branches should be addressed separately:

1. Help with the specific case being mentioned.  I think this has
been addressed nicely with several helpful suggestions.

2. Discussions about solving this class of problems.

Practical workarounds are an essential part of writing software, but
eliminating the need for them is where the computer science comes
into play.  I was reading Paul Graham's "On Lisp" the other day and
came across an example that made me cringe.  He pointed to a simple
Lisp code fragment and then rewrote it for performance, proudly
pointing to the result as an example of what efficient Common Lisp
looks like and claiming that the result is competitive with C for
speed.

That's great that the capability is there, but whenever there is a
significant difference between the clean, simple way to do something
and the efficient way to do it (where the primary different is
language or compiler related, not a fundamental algorithm or data
structure change) it indicates an opportunity to improve the
language or compiler design.  If a systematic rewrite can transform
inefficient code into efficient code, why doesn't the language
and/or compiler just do it for you or prevent the problem in the
first place?  (the answers "because it is hard to do" and "I don't
see you doing it" are both equally valid, but let's consider the
question rhetorical for now)

In Graham's example (if I recall correctly) the solution involved
annotating variable types (Lisp is dynamically typed) and
transforming a recursive function to use an accumulator to allow
tail recursion.  Lisp is full of this pattern and it does make a big
different in performance.  ML is statically typed so one could argue
that it fixes the first problem already (annotating the types
effectively removes dynamic typing from the Lisp function) but the
second is still there.

Tail recursion is a powerful and efficient construct, but it still
requires care on the part of the programmer to make sure that the
calls are proper tail calls.  I think there are many recursive
functions which cannot be transformed easily into tail calls, but
there is a large class of functions that can be mechanically
transformed using techniques discussed here and elsewhere.  I would
be interested personally if anyone could point to papers or other
resources about this topic.  Right now I think there is some
low-hanging fruit to be plucked--recognizing and transforming a few
simple patterns (code that looks like List.map) would make a big
difference in a lot of code.  Handling more complex cases is
undoubtedly harder, but I think the potential benefits are
considerable.

I appreciate everyone's input on this subject so far.  I was
attracted to Caml in the first place because it seemed to be one of
the best examples of a language where writing code that is clean and
natural coincides with writing code that is efficient.  I hope that
discussions like this can bridge the gap even more.

- Russ

p.s. I don't mean to sound critical of Paul Graham here--in the
context of Common Lisp his examples were very valuable--he just
nicely illustrated my point for me so I picked on him.


On Fri, Jan 31, 2003 at 11:13:26AM -0600, Brian Hurt wrote:
> I did get it the first time.  I'm just using List.append to illustrate a 
> problem I'm having.
> 
> The problem is *constructing* lists.  If you can construct your list 
> backwards, fine- but if you can't, you end up either not being tail 
> recursive (and blowing up for long lists) or allocating the list twice.
<snip>
> Now minor uglification becomes major uglification.  It'd be nicer just to 
> be able to be able to construct lists forwards instead of backwards.
> 
> List.append is just an obvious example to be talking about, but the 
> problem is signifigantly more general.
> 
> 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

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

[Alexander V. Voinov]

Hi All,

Russ Ross wrote:

>resources about this topic.  Right now I think there is some
>low-hanging fruit to be plucked--recognizing and transforming a few
>simple patterns (code that looks like List.map) would make a big
>difference in a lot of code.  Handling more complex cases is
>undoubtedly harder, but I think the potential benefits are
>considerable.
>
Yes, yes, yes. And this is a matter of adoption as well. Even if the 
global compiler strategy can't be changed quickly (to accomodate 
'futures' or 'holes' or whatever), let's just make the List module 
completely and absolutely tail recursive, one way or another. So that 
any newcomer can quickly map his/her favorite interative patterns of 
construction of homogeneous data structures (lists, arrays) to maps and 
folds.

Alexander


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

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

[brogoff]

On Fri, 31 Jan 2003, Russ Ross wrote:
> Tail recursion is a powerful and efficient construct, but it still
> requires care on the part of the programmer to make sure that the
> calls are proper tail calls.  I think there are many recursive
> functions which cannot be transformed easily into tail calls, but
> there is a large class of functions that can be mechanically
> transformed using techniques discussed here and elsewhere.  I would
> be interested personally if anyone could point to papers or other
> resources about this topic.  Right now I think there is some
> low-hanging fruit to be plucked--recognizing and transforming a few
> simple patterns (code that looks like List.map) would make a big
> difference in a lot of code.  Handling more complex cases is
> undoubtedly harder, but I think the potential benefits are
> considerable.

For the particular case being discussed, there is a bit of theory, and if you 
read Minamide's paper you'll see that he comments that six functions from 
the SML Basis can take advantage of the hole abstraction to be written in 
tail recursive form: append, take, map, mapPartial, filter, and tabulate. 

For OCaml's list, we I think it's pretty clear that fold_right can't be written 
this way, since it doesn't necessarily construct lists. I think it's also clear 
that we can write map2, flatten, split, and combine with setcdr (I like 
replace_tl as a name for this :) in tail recursive form, since map2, split, and 
combine are all tweaks of map, likewise flatten is a tweak of append. I just 
hacked up tail recursive versions of all of these functions (including the 
SML ones Minamide mentioned) using setcdr, so it is doable.  

PS: As you may know, you can certainly make functions like fold_right 
tail recursive using a trick called the CPS transformation, like so, from 

let rec fold_right f l accu =
  match l with
      [] -> accu
    | a::l -> f a (fold_right f l accu)

to

let rec fold_rightk f l accu k = 
  match l with 
      [] -> k accu 
    | a::l -> fold_rightk f l accu (fun x -> k (f a x))

let fold_right f l accu = fold_rightk f l accu (fun x -> x)

but as you can see that doesn't help so much, because we create lots of 
closures. So just making things tail recursive isn't really enough, since we 
can make anything tail recursive. This hole abstraction stuff Minamide discusses 
is a bit more, and touches on such areas as linear types. I think "destination 
passing style" will give you a few good hits on Google, if you're looking for 
more refs, but the Minamide paper cited earlier is a good start.

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

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

[Issac Trotts]

On Fri, Jan 31, 2003 at 11:13:26AM -0600, Brian Hurt wrote:
> On Thu, 30 Jan 2003, james woodyatt wrote:
> 
> > everyone--
> > 
> > Earlier in this thread, I suggested using a queue if you are spending 
> > too much time in List.append.  Lack of optimized tail recursion is not 
> > really a factor compared to the waste of cycles involved in 
> > constructing a whole new list just to append a single element on the 
> > end.
> > 
> > Apparently, nobody seemed to notice what I was talking about.  So I'm 
> > going to try to make my point again.  Sorry if you got it the first 
> > time.
> 
> I did get it the first time.  I'm just using List.append to illustrate a 
> problem I'm having.
> 
> The problem is *constructing* lists.  If you can construct your list 
> backwards, fine- but if you can't, you end up either not being tail 
> recursive (and blowing up for long lists) or allocating the list twice.
> 
> 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 x y = (* return x + y *)
>     match (x, y) with
>         ([], _) -> y
>         | (_, []) -> x
>         | (((xidx, xval) as xhead) :: xtail, 
>            ((yidx, yval) as yhead) :: ytail)
>         ->
>             if (xidx == yidx) then
>                 (xidx, xval +. yval) :: (add xtail ytail)
>             else if (xidx < yidx) then
>                 xhead :: (add xtail y)
>             else
>                 yhead :: (add x ytail)
> ;;
> 
> It's simple, and obvious in both what it does and how it does it.  Except
> opps, this isn't tail recursive.  If your sparse vectors might be 65536
> elements long, this will blow up.  So we rewrite to be tail recursive:
>  
> let add x y = (* return x + y *)
>     let add_int x y accum =
>         match (x, y) with
>             ([], _) -> (List.rev_append accum y)
>             | (_, []) -> (List.rev_append accum x)
>             | (((xidx, xval) as xhead) :: xtail, 
>                ((yidx, yval) as yhead) :: ytail)
>             ->
>             if (xidx == yidx) then
>                 add_int xtail ytail ((xidx, xval +. yval) :: accum)
>             else if (xidx < yidx) then
>                 add_int xtail y (xhead :: accum)
>             else
>                 add_int x ytail (yhead :: accum)
> ;;

I get your meaning, but it has to be changed to something like this 

  let add x y = (* return x + y *)
            let rec  add_int x y accum =
                match (x, y) with
                    ([], _) -> (List.rev_append accum y)
                    | (_, []) -> (List.rev_append accum x)
                    | (((xidx, xval) as xhead) :: xtail, 
                      ((yidx, yval) as yhead) :: ytail)
                    ->
                    if (xidx == yidx) then
                        add_int xtail ytail ((xidx, xval +. yval) :: accum)
                    else if (xidx < yidx) then
                        add_int xtail y (xhead :: accum)
                    else
                        add_int x ytail (yhead :: accum)
          in   
          add_int x y []
    ;;

to work on OCaml 3.06.

> This makes the function truely tail recursive, except now it's allocating 
> most of the returned vector twice (once as accum, and once in 
> List.rev_append) and it's signifigantly uglier IMHO.  Rewritting the code 
> to use set_cdr is the best performaner, but the ugliest yet.
> 
> And the add function is truely simple.  It can handle minor increases in 
> ugliness without losing much.  But now consider something rather more 
> complicated- say matrix transposition or matrix multiplication with
> matricies defined as:
> 
> type vector_t = (int * float) list ;; (* index * value list *)
> type matrix_t = (int * vector_t) list ;; (* row index * row vector list *)
> 
> Now minor uglification becomes major uglification.  It'd be nicer just to 
> be able to be able to construct lists forwards instead of backwards.

Well, in your first example you are mapping ints to floats.  Why not use
a map for this?  You are keeping the keys sorted, so using a map should 
be at least as good asymptotically when you're constructing it.

  module Imap = Map.Make(struct type t=int let compare=compare end);;

  let rec vec_make = function 
    [] -> Imap.empty 
    | (a,b) :: tail -> Imap.add a b (vec_make tail);;

  let a = vec_make [(0, 1.0); (3, 3.0)] ;;    

  let b = vec_make [(1, 2.0); (3, 4.5); (4, 5.0)] ;;  

  let vec_add x y =
    Imap.fold
      (fun index value acc ->
        try 
          let acc_val = Imap.find index acc in
          let acc = Imap.remove index acc in
          Imap.add index (value +. acc_val) acc 
        with 
            Not_found -> Imap.add index value acc
      )
      x
      y
  ;;

 let result = vec_add a b;;

 Imap.iter (fun i v -> Printf.printf "%i : %9.6f\n" i v) result;;

0 :  1.000000
1 :  2.000000
3 :  7.500000
4 :  5.000000
- : unit = ()

For matrices, how about

  let mat_add x y =
    Imap.fold
      (fun index value acc ->
        try
          let acc_val = Imap.find index acc in
          let acc = Imap.remove index acc in
          Imap.add index (vec_add value acc_val) acc
        with
            Not_found -> Imap.add index value acc
      )
      x
      y
  ;;

Issac

> List.append is just an obvious example to be talking about, but the 
> problem is signifigantly more general.
> 
> Brian
> 
> 
> 
> > 
> > On Thursday, Jan 30, 2003, at 13:57 US/Pacific, Brian Hurt wrote:
> > > On Thu, 30 Jan 2003, Olivier Andrieu wrote:
> > >
> > >>> list1: 1.462s
> > >>> list2: 1.757s
> > >>> list3: 1.824s
> > >>
> > >> There's an assert in setcdr : it's important because the first
> > >> argument mustn't be an empty list. It's never the case here, so you
> > >> can safely compile with -noassert.
> > >
> > > Doh!  OK- now, compiling with -noassert drops the time to 1.457 seconds
> > > (same machine, same environment)- to slightly better than the recursive
> > > version.
> > 
> > For grins, I wrote an equivalent test program.  It uses a functional 
> > deque instead of a list.  (I have written one.  It's a component of my 
> > Cf library, which remains unreleased at the moment.  Markus Mottl has 
> > translated several of Chris Okasaki's functional queue implementations 
> > into Ocaml, and you can find them on the Hump.)
> > 
> > To get started, I timed the 'benchmarks' by running them on my iBook 
> > (the 700 MHz G3 model) so I could get a baseline.  My little iBook is 
> > nowhere near as fast as your cool 1.6GHz P4, but I'm not complaining.
> > 
> > The results of my tests were:
> > 
> > 	$ time ./list1
> > 	3.690u 0.070s 0:04.14 90.8%     0+0k 0+0io 0pf+0w
> > 
> > 	$ time ./list2
> > 	4.180u 0.020s 0:05.01 83.8%     0+0k 0+0io 0pf+0w
> > 	
> > 	$ time ./list3
> > 	3.700u 0.000s 0:04.49 82.4%     0+0k 0+0io 0pf+0w
> > 
> > Not real fast, but fast enough that I don't mind waiting for results.  
> > So, what difference does my functional deque implementation make?  Glad 
> > you asked.
> > 
> > My Cf_deque module matches the following signature:
> > 
> > 	(* begin cf_deque.mli *)
> > 	type 'a t
> > 
> > 	val nil: 'a t
> > 
> > 	module type Direction_T = sig
> > 	    val pop: 'a t -> ('a * 'a t) option
> > 	    val push: 'a -> 'a t -> 'a t
> > 	end
> > 
> > 	module A: Direction_T
> > 	module B: Direction_T
> > 
> > 	val cat: 'a t -> 'a t -> 'a t
> > 	(* end file *)
> > 
> > (Actually, this isn't the complete interface.  I've written a variety 
> > of ancillary functions that make it convenient to work with the objects 
> > in a deque without having to translate them into lists, e.g. fold, 
> > iterate, etc.)
> > 
> > All the functions above are purely functional, and they perform with 
> > O(1) average complexity.  (Or at least, that's my untrained analysis.  
> > I'd like to provide proof of that assertion, and I'm working on getting 
> > some help in that effort-- but, I'll have more news on that when I have 
> > it.)
> > 
> > Here's a variant of the list1.ml test above, which uses my Cf_deque 
> > module instead:
> > 
> > 	(* begin t-opt.deque.ml *)
> > 	open Cf_deque
> > 
> > 	let rec makelist_aux c accum =
> > 	  let accum = B.push c accum in
> > 	  if c > 0 then makelist_aux (pred c) accum else accum
> > 
> > 	let makelist c = makelist_aux c nil
> > 
> > 	;;
> > 	let _ = makelist 5000;;
> > 	(* end file *)
> > 
> > Here are the timing results on that same iBook:
> > 
> > 	$ time ./t-opt.deque
> > 	0.010u 0.010s 0:00.02 100.0%    0+0k 0+0io 0pf+0w
> > 
> > In other words, it's done before enough time passes even to measure it 
> > properly.
> > 
> > > And for the record, I just tested with appending to a list of 500,000
> > > elements, and it worked OK.
> > 
> > Here is the result of running my version of the test with 500,000 
> > elements:
> > 
> > 	$ time ./t-opt.deque
> > 	0.450u 0.080s 0:00.75 70.6%     0+0k 0+0io 0pf+0w
> > 
> > It took under a second of wall-clock time.  On the other hand, when I 
> > modified list3.ml for 500,000 elements, it took *forever* in wall-clock 
> > time.  I gave up after almost an hour and a half.  Ultimately, I killed 
> > it with SIGINT before it finished.  I have no idea how far it got.
> > 
> > Clearly, I need to push a lot more elements into my deque before I will 
> > get a timing result that I can measure in heartbeats.  Here is the 
> > result for 5,000,000 elements:
> > 
> > 	$ time ./t-opt.deque
> > 	5.160u 0.510s 0:06.69 84.7%     0+0k 0+0io 0pf+0w
> > 
> > At this stage, I noticed my little iBook was just starting to thrash 
> > when the program finished.    So, I bumped it up to 50,000,000 
> > elements, because I like punishing my computer from time to time-- just 
> > to teach it respect.
> > 
> > At around 15 seconds into the run, the program turned into the 
> > psychedelic pizza delivery service: the pager went into fear and 
> > loathing mode, and the pretty Aqua GUI started acting like it was 
> > sniffing glue.  If I had let it run to completion, it probably would 
> > have wedged the machine.  (Mac OS X is pretty stable, but it hates 
> > resource bombs as much as any other operating system.)
> > 
> > None of the listN.ml files were able to bring down the machine like 
> > that, no matter how long I let them run-- which should make sense, 
> > right?  The APPEND function is O(N) for lists.  Once N gets beyond a 
> > few hundred, the program spends almost all its cycles just copying list 
> > cells inside its innermost loop, only occasionally reaching the end of 
> > a list and tacking a new cell onto the end before starting over again.
> > 
> > The problem is not the language, or the compiler.  The problem is the 
> > design of the program.  The moral of this story: you really should 
> > consider using a queue if you find your programs are spending a lot of 
> > cycles appending things to very long lists.
> > 
> > 
> > 
> 
> -------------------
> 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