RE: [Caml-list] optimizing functors

RE: [Caml-list] optimizing functors

[Michael Hicks]

I believe that the MLton compiler, which is a whole-program compiler for SML, does this sort of optimization.  See http://www.sourcelight.com/MLton/.

Mike

> -----Original Message-----
> From: David Monniaux [mailto:David.Monniaux@ens.fr]
> Sent: Monday, February 04, 2002 7:50 AM
> To: Xavier Leroy
> Cc: Liste CAML
> Subject: Re: [Caml-list] optimizing functors
> 
> 
> On Sat, 2 Feb 2002, Xavier Leroy wrote:
> 
> > Yes, but not across functor applications.  More precisely, functions
> > that are passed through a functor parameter cannot be inlined nor
> > called with the optimized "direct" application scheme, they 
> always go
> > through the generic "indirect-through-closure" application scheme.
> 
> I realize that the current scheme of implementing modules as 
> records is
> (relatively) simple and allows easy separate compilation. However, it
> prevents optimizations, as you said.
> 
> In code containing many modules consisting of a few small 
> functions called
> by functions in functors, this lack of optimization may be costly.
> 
> I was thinking of implementing such functors similarly as C++ 
> templates
> (expanding the functor parameters). Has some work been done on this?
> 
>  
> David Monniaux            http://www.di.ens.fr/~monniaux
> Laboratoire d'informatique de l'École Normale Supérieure,
> Paris, France
> 
> 
> -------------------
> Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: 
http://caml.inria.fr/FAQ/
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/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] optimizing functors

[Francois Pottier]

On Mon, Feb 04, 2002 at 01:50:06PM +0100, David Monniaux wrote:
> 
> In code containing many modules consisting of a few small functions called
> by functions in functors, this lack of optimization may be costly.
> 
> I was thinking of implementing such functors similarly as C++ templates
> (expanding the functor parameters). Has some work been done on this?

I am also of the opinion that the current compilation scheme creates
a tension between modularity and efficiency, and that people (including
myself) are too often tempted to choose efficiency.

I have given some thought to writing a source-to-source defunctorizer, i.e. a
tool that expands functors and modules away, and produces a flat O'Caml
program, which can then be fed to the normal ocamlopt compiler. There are two
conceptually independent tasks to be performed: reducing functor applications
and flattening modules (i.e. removing nested modules). Perhaps the latter can
be neglected, as (I believe) ocamlopt produces good code for nested modules.

I quickly ran into problems when trying to define a source-level reduction
semantics for O'Caml functors. O'Caml's source syntax was clearly not meant to
express its own reduction semantics, and this shows through the lack of
alpha-conversion (renaming) facilities. Indeed, it is easy to rename a program
variable by introducing a `let' binding, but there is no or little provision
to rename types, data constructors, record labels, etc. Consider the following
example:

  (* functor definition site *)
  type t = A
  module F (X : sig ... end) = struct
    let x = A
  end

  ...

  (* functor application site *)
  type u = A | B
  module M = F (struct ... end)

Expanding the call to F causes the data constructor name A (in the definition
of x) to be captured, and there seems to be no simple way of avoiding it.

Another problem is caused by the current type system for `applicative'
functors. The type system is able to keep track of the fact that two modules
have the same type because they arise out of the same functor application. (In
other words, functor applications may appear in types.)  Expanding away
functor applications causes this information to be lost, which potentially
makes the program ill-typed. There may be a work-around, but it isn't
pretty. (All I could think of was to keep the functor around, and to use
explicit type equations to propagate the type information that was available
in the original program, e.g.

  module F = functor (...) struct type t = ... end
  module N = F(M) (* N.t == F(M).t *)

would become

  module F = functor (...) struct type t = ... end
  module N = struct type t = F(M).t = ... end

A bit ugly, but could be made to work, I believe.)

Given these difficulties, I haven't looked any further into source-to-source
defunctorization. Some defunctorizers have been written for Standard ML. One
is part of the BANE program analysis toolkit:

  http://www.cs.berkeley.edu/Research/Aiken/bane.html

Another defunctorizer was written by Martin Elsman:

  http://www.dina.kvl.dk/~mael/papers.html

See the paper `Static Interpretation of modules'. This one doesn't work at
the source level, however, I believe.

In light of the current syntax war on the caml-list, I would suggest, if a new
syntax is to be adopted, that it be able to express a reduction semantics for
the language. This would make source-to-source transformations a whole lot
easier.

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] optimizing functors

[David Monniaux]

On Sat, 2 Feb 2002, Xavier Leroy wrote:

> Yes, but not across functor applications.  More precisely, functions
> that are passed through a functor parameter cannot be inlined nor
> called with the optimized "direct" application scheme, they always go
> through the generic "indirect-through-closure" application scheme.

I realize that the current scheme of implementing modules as records is
(relatively) simple and allows easy separate compilation. However, it
prevents optimizations, as you said.

In code containing many modules consisting of a few small functions called
by functions in functors, this lack of optimization may be costly.

I was thinking of implementing such functors similarly as C++ templates
(expanding the functor parameters). Has some work been done on this?

 
David Monniaux            http://www.di.ens.fr/~monniaux
Laboratoire d'informatique de l'École Normale Supérieure,
Paris, France


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] optimizing functors

[Xavier Leroy]

> OCaml does inlining of functions in the same module. Does it also do it
> between different modules?

Yes, but not across functor applications.  More precisely, functions
that are passed through a functor parameter cannot be inlined nor
called with the optimized "direct" application scheme, they always go
through the generic "indirect-through-closure" application scheme.

> Would it optimize the following:
> 
> module M=
> struct
>   let f = function 0 -> true | _ -> false
> end
> 
> module N (D : sig val f: int->bool end) =
> struct
>   let f = D.f
> end
> 
> module P=N(M)
> 
> Does the compiler optimize the call to f in P, resolving it directly to
> M.f, or does it do multiple indirections?

It will do exactly one indirection: fetch a function closure from P.f (which
happens to be the closure of M.f), and call it indirectly (and without
inlining).  

- Xavier Leroy
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

[Caml-list] optimizing functors

[David Monniaux]

We are currently writing code containing lots of stacked functors. Most of
the implemented functions are simple manipulations (two lines) that invoke
functions in the functor's argument module.

OCaml does inlining of functions in the same module. Does it also do it
between different modules? Would it optimize the following:

module M=
struct
  let f = function 0 -> true | _ -> false
end

module N (D : sig val f: int->bool end) =
struct
  let f = D.f
end

module P=N(M)

Does the compiler optimize the call to f in P, resolving it directly to
M.f, or does it do multiple indirections?


David Monniaux            http://www.di.ens.fr/~monniaux
Laboratoire d'informatique de l'École Normale Supérieure,
Paris, France

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr