Functors ...

Functors ...

[William Chesters]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1271 bytes --]

J'ai récemment dû faire un logiciel en C++, et j'ai saisi l'occasion
de me renseigner sur le librairie "STL".  Il était facile une fois que
je m'étais rendu compte que les templates sont essentiellement
identiques aux "functors" ML :).

---Alors, me dis-je, pourquoi ne pas écrire la même utilitaire en ML,
et peut-être le logiciel entier?  (Il s'agit d'une librairie petite
pour manipuler les "sparse vectors" au moyen des "iterators" .)

Mais il semble que ocaml implément les functors au moyen des
"dispatch tables"; ça marche donc un peu lentement.  Est-ce qu'il y a
une raison pour laquelle les fonctions dans les functors ne peuvent
pas être mise "inline"?




I recently had to write a program in C++, and I took the opportunity
to learn about the STL.  It was easy once I realised that templates
are essentially identical to ML functors :).

"OK", I thought, "why not write the same utility in ML, and perhaps
the whole program?"  (It's a little library for manipulating sparse
vectors using iterators.)

But it seems that ocaml implements functors with dispatch tables, so
it runs a bit slowly.  Is there some reason why functors cannot be
treated as normal code, much as C++ treats templates, and functions
from functors treated as candidates for inlining?

Re: Functors ...

[Xavier Leroy]

> But it seems that ocaml implements functors with dispatch tables, so
> it runs a bit slowly.  Is there some reason why functors cannot be
> treated as normal code, much as C++ treats templates, and functions
> from functors treated as candidates for inlining?

To be exact, functions defined by functors are candidates for direct
call and inlining; but it is true that functions taken from the
functor parameter are always called via their closures (what you call
"dispatch tables").  E.g. consider the following example:

     module F(X : sig val f : int -> int end) =
       struct
         let g x = 1 + X.f (x - 1)
       end

     module A = F(struct let f x = x * 2 end)

     ... A.g 10 ...

The function g can be inlined at point of call in (A.g 10), but the
call to function f (i.e. fun x -> x * 2) will not.

The only reasons for this behavior is that OCaml's flow analysis and
inline expander are fairly naive and concentrate on the most obvious
opportunities for direct calls and inline expansion.

In principle, the module language is terminating, so the compiler
could simply generate a copy of the functor body at each functor
application point, and work from here.  This would allow more direct
calls and inline expansion -- as much as if you'd written your code
without functors -- but results in loss of separate compilation
(the functor body is recompiled over and over again) and code bloat.
C++ templates have precisely those two problems.

So, I don't think we want to go all the way down to the C++ solution.
But it is true that more opportunities for inlining (as in the example
above) could certainly be exploited.

- Xavier Leroy

Re: Functors ...

[Thorsten Ohl]

Xavier Leroy <Xavier.Leroy@inria.fr> writes:

> In principle, the module language is terminating, so the compiler
> could simply generate a copy of the functor body at each functor
> application point, and work from here.  This would allow more
> direct calls and inline expansion -- as much as if you'd written
> your code without functors -- but results in loss of separate
> compilation (the functor body is recompiled over and over again)
> and code bloat.  C++ templates have precisely those two problems.

What about a compiler option (or directive) for selective functor
expansion?  This way one can use the profiler (or static information
about the program) to fight code bloat by expanding just the functor
applications in the compilation units that appear to produce the most
frequently executed code?

I agree that it is not a very elegant solution.  But why not, as long
as it helps to fight the misconception that functional programming is
slow?

Cheers,
-Thorsten
-- 
Thorsten Ohl, Physics Department, TU Darmstadt -- ohl@hep.tu-darmstadt.de
http://crunch.ikp.physik.tu-darmstadt.de/~ohl/ [<=== PGP public key here]