Re: caml (special) light and numerics

[Pierre Weis <weis@pauillac.inria.fr>]

> I guess what I'm looking for are also some examples, because the
> typical tutorials and textbooks stay away from numerical applications.
> 
> An example: the FORTRAN or C programmers in me sometimes want an
> array local to a function, which would be cheap, because it's
> allocated on the stack.  But CSL will allocate it on the heap if I use
> `Array.new' and I assume that this is expensive.  Is this true and are
> there any standard procedures around it?

There is no way to explicitely allocate on the stack in any Caml
implementation including CSL. This is just too low level and must be a
compiler optimization, not a user's concern. Unfortunately no Caml
compiler (except Bigloo in some cases) works as to allocate data on
the stack. Anyway, allocating in the heap is not too expansive,
especially since we have a very fast GC in CSL.

>  (Typical example)
> 
>   val f : float array -> float array
> 
> will certainly be expensive, but a `subroutine'
> 
>   val g : float array -> unit
> 
> modifying the vector in place will also (in general) need a temporary
> array to store either input or output.

If your code does not explicitely allocate a new array in the body of
the procedure, CAML won't allocate any temporary array. There is no
semantic feature in the language that assumes that some arrays have to
be copied (as in Pascal or Ada for instance): arrays are always
efficiently handled as pointers to some memory locations.

> Another example: how can I find out (without deciphering assembler
> code) if a particular recursive function has been recognized as tail
> recursive?

You cannot. Once more this is too low level to be of programmer's
concern (in the Caml philosophy). However, our compilers are rather
good at optimizing these tail calls (not only recursive ones). So if
it is reasonably evident, your Caml compiler must do it.

Remember that Caml is a functionnal programming language: so function
definitions and function calls are very heavily used, and the compiler
optimizes them as much as it can. For instance, some Caml compilers
may systematically turn imperative loops into recursive definitions of
functions, since they are able to recognize loops into those recursive
definitions, and to compile them as such.

Concerning CSL specifically, Xavier may probably tell you more ...

I would like to end this answer on efficiency considerations by
telling a little true story: somebody complains once that the Caml
Light system failed to execute his code with a fatal "Out of
memory..." error message, after having allocated more than 200
Megabytes of data. The supposed ``bug'' of Caml Light was that the
size of useful data was supposed to be strictly smaller than 200
Megabytes. The conclusion of the user was: ``Well, there's no problem,
I'm going to rewrite all this stuff in C, and use a huge malloc at the
beginning'' :(

After a look at the source code of his example, it appears that the
program got an exponential complexity anyway, and would not answer
before years regardless of the size of the available memory (in fact
the program needed hundred of Gigabytes of memory to complete, so that
a ``huge'' malloc was hopeless).
After a bit of brain storming, changing the algorithm leads to a
program that runs within 100 words of memory, runs exponentially
faster, and gives the result after a few minutes :)

So be sure that you really need to know this kind of very low level
details (such as the ``tail calls'' treatment for instance). My
feeling is that, if efficiency is a problem, you have to change the
complexity of the algorithm, not to try to change the code generated by
the compiler!
And if you need to test and change your programs rapidly, the
readibility and expressiveness of Caml programs may help you...

Pierre Weis
----------------------------------------------------------------------------
WWW Home Page: http://pauillac.inria.fr/~weis
Projet Cristal
INRIA, BP 105, F-78153 Le Chesnay Cedex (France)
E-mail: Pierre.Weis@inria.fr
Telephone: +33 1 39 63 55 98
Fax: +33 1 39 63 53 30
----------------------------------------------------------------------------