Re: [Caml-list] OCaml troll on Slashdot

[Jon Harrop <jon@ffconsultancy.com>]

On Thursday 17 March 2005 03:48, Yaron Minsky wrote:
> On Wed, 16 Mar 2005 19:35:17 -0800 (PST), brogoff
> <brogoff@speakeasy.net> wrote:
> > Anyways, long lists do occur, and Stack_overflow at the customer site
> > sucketh bigtime.
>
> I completely agree.  As someone who makes extensive use of OCaml in a
> business setting, the fact that the standard libraries throw
> exceptions on large data structures is a real pain.

I believe the Stack_overflow exception is not necessarily thrown - the process 
may simply die. IIRC, I found this on x86 Debian Linux when swap was turned 
off.

> It's a violation 
> of the principle of least surprise, and I've run into it in practice
> quite a few times.

I understand your (and Brian's) concern but I think the solution is to be more 
careful when programming, rather than to replace all of the library 
functions. That seems like a sledgehammer to crack a nut to me...

> Our solution was to just rewrite the list module 
> with tail-recursive versions.

I would recommend using and making documentation instead, as 
non-tail-recursive functions can be very useful. In non-trivial code I would 
recommend putting the asymptotic complexity of stack use in the docs.

> We're happy to make the performance 
> tradeoff.  If we really want things to be fast, List.map is no good
> anyway, due to the lack of inlining of the function parameter.

Yes, if your program uses non-tail-recursive functions with very deep 
recursion then it will be much slower anyway. Consequently, you are likely to 
fix this whilst optimising anyway.

As Brian has said before, users can throw you a sideball by giving input which 
requires deep recursion by a non-tail-recursive function which had not been 
expected by the programmer. Provided you are thorough, this shouldn't happen 
though.

I must say that I've had fewer stack problems with my OCaml code than with 
code I've used in other languages...

> I do think that it would be a great thing if the tail-recursive list
> functions were moved into the standard library.

I would not like to see trivial tail-recursive alternatives put into the 
library (e.g. let map f l = rev_map f (rev l)). I think it would bloat the 
library unnecessarily and they are often not the best solution, particularly 
in combination. For example, writing these functions yourself makes a rev rev 
and the following deforestation obvious. Given that these are likely to be 
performance-critical functions, this is obviously useful.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists