Instruction selection in the OCaml compiler: Modules or classes?

Instruction selection in the OCaml compiler: Modules or classes?

[Joel Reymont]

Folks,

I'm reading through the icfp99 slides on classes vs modules in OCaml.  
The part that I'm interested in starts on p27 where instruction  
selection in the OCaml compiler is discussed.

I'm not well-versed in the OCaml compiler code yet so I thought I  
would ask the list: does the compiler use a module or class solution?

The slides seem to favor the class-based solution but then I hear  
that classes in OCaml are slow and people like Markus Mottl just  
plain despise them :-). What does everyone else opine?

	Thanks, Joel

--
http://wagerlabs.com/

Re: [Caml-list] Instruction selection in the OCaml compiler: Modules or classes?

[Tom]

[-- Attachment #1: Type: text/plain, Size: 922 bytes --]

Classes in OCaml are indeed slow, but that is because they are incredibly
different from modules. A class has fields, that is, meathods, that are
"named" and searched by comparing hashes. Modules also have fields,
functions and values, but they are named only as far as the programmer in
concerned - in compiled code, they are indexed (by an integer), and
actually, the native compiler can actually optimise even that (so only a
plain function call remains). In contrast, everytime you call a method of an
object, it is searched in the method list of that class (well, I think there
is some caching too).

But this "slowness" is expected - objects are also more adaptable than
modules. If you have a function
    # let f o = o#some_method ();;
    val f : < some_method : unit -> 'a; .. > -> 'a = <fun>
you can pass to it any object with method "some_method" of type unit -> 'a.
That's called structural subtyping.

- Tom

[-- Attachment #2: Type: text/html, Size: 1048 bytes --]

Re: [Caml-list] Instruction selection in the OCaml compiler: Modules or classes?

[Xavier Leroy]

> I'm reading through the icfp99 slides on classes vs modules in OCaml.
> The part that I'm interested in starts on p27 where instruction
> selection in the OCaml compiler is discussed.
>
> I'm not well-versed in the OCaml compiler code yet so I thought I  would
> ask the list: does the compiler use a module or class solution?

It uses classes, inheritance and overriding (of generic code by
processor-dependent code) for a few passes: instruction selection,
reloading of spilled registers, and instruction scheduling.  The other
passes are either processor-independent or can be parameterized in a
simpler way (e.g. register allocation, which is parameterized by the
number of hardware registers in each register class).

> The slides seem to favor the class-based solution but then I hear  that
> classes in OCaml are slow and people like Markus Mottl just  plain
> despise them :-). What does everyone else opine?

Method dispatch is slightly slower than calls to unknown functions,
but the compiler passes that use objects are not speed-critical anyway
(most of the compilation time is spent elsewhere).

I don't despise objects and classes: it's just that the kind of code
that I usually write does not need them often.  But there are some
cases where they work better than other forms of parameterization
available in OCaml.  Ensuring that the native-code compiler is not
polluted all over the place by Intel x86-specific hacks is one of them.

- Xavier Leroy

Re: [Caml-list] Instruction selection in the OCaml compiler: Modules or classes?

[Chris King]

On 2/22/07, Joel Reymont <joelr1@gmail.com> wrote:
> I'm reading through the icfp99 slides on classes vs modules in OCaml.
> The part that I'm interested in starts on p27 where instruction
> selection in the OCaml compiler is discussed.

I've never seen these slides before; very interesting!  Personally I prefer modules, but find classes useful for the typing tricks you can do with them: the ability to hide type variables via subtyping is one of the prime benefits.  (The comparison in the slides between objects and closures I thought was particularly elucidating, since function closures are the other (clunkier) way of accomplishing the same thing.)

Also of note, the slides talk about late binding being possible with classes but not with modules, but thanks to recursive modules late binding is in fact possible with (some) modules by simply having a "class" module accept a "Self" module as a parameter, whose members are used when late binding is desired.  The final "object" module can then be created by recursively applying the (post-inheritance) "class" module to the "object" module.  The power of Caml's module system continues to amaze me... :)

- Chris

Re: [Caml-list] Instruction selection in the OCaml compiler: Modules or classes?

[Markus Mottl]

On 2/22/07, Joel Reymont <joelr1@gmail.com> wrote:
> The slides seem to favor the class-based solution but then I hear
> that classes in OCaml are slow and people like Markus Mottl just
> plain despise them :-). What does everyone else opine?

Well, I think it needs to be said here that I don't "despise classes",
which are still much better in OCaml than in any mainstream language,
but I certainly prefer modules for almost all purposes (as most
ML-programmers seem to), and this is not for speed reasons.

Regards,
Markus

-- 
Markus Mottl        http://www.ocaml.info        markus.mottl@gmail.com

Re: [Caml-list] Instruction selection in the OCaml compiler: Modules or classes?

[brogoff]

On Thu, 22 Feb 2007, Joel Reymont wrote:
> The slides seem to favor the class-based solution but then I hear
> that classes in OCaml are slow and people like Markus Mottl just
> plain despise them :-). What does everyone else opine?

It's one of the most interesting issues in the OCaml language design.

There is a lot of overlap between the module system, the object system,
and to some degree, records. One would think that a language design with
fewer features could provide the same powers of parameterization, but
modules aren't first class (and the recursive module extension is still
an "experimental" feature) and don't support inheritance, records in
OCaml are rather weak, and classes don't have type components.

I use classes less frequently (but as Markus points out they are for the
most part much more pleasant than Java or C++ classes) so my gut feeling
is that their abilities should be subsumed in the module system (mixin
modules?) and the record system. But that will probably be a new
language, ML2040, given the current rate of change of ML :-(.

-- Brian

Re: [Caml-list] Instruction selection in the OCaml compiler: Modules or classes?

[Tom]

[-- Attachment #1: Type: text/plain, Size: 2125 bytes --]

>
>
> I use classes less frequently (but as Markus points out they are for the
> most part much more pleasant than Java or C++ classes) so my gut feeling
> is that their abilities should be subsumed in the module system (mixin
> modules?) and the record system.


I think you should take a look at another currently active thread  -
"Feature request : Tuples vs. records". One of the red lines there is the
comparison of structural versus nominal typing - classes and objects
belonging to the former, and modules and records to the latter. Some say
that structural typing features (objects, along with Polymorphic Variants)
are an appreciated alternative to the "rigid" nominal typing of OCaml
(variants, records, modules). That is why I believe that classes should
exist as a separate entity (I'm not that much in favour of polymorphic
variants - they weaken the type checking process too much in my opinion, and
I have yet to see a good use for them), so that one can use them when one
needs sharing - which records (and conventional inheritance-based object
systems) don't provide.

A criticism of OOP (available at
http://www.geocities.com/tablizer/oopbad.htm) addresses the issue that
although conventional class systems (that is, having nominal typing, not
structural) are supposed to be "nature like" (OO proponents claim that
objects are more suitable to modelling things as they are in nature), they
often lack the dynamic aspect of the nature, the adaptability - for example,
they cannot change class, and are usually adapted to one function only, or
model a functionality forcefully "adapted" to the tree-like
inheritance-based structure. OCaml objects seem a great alternative for
that.

The way I see things, or rather the way I dream things, is having modules
simply as namespaces, having extensible records (records that have nominal
subtyping - inheritance, so that parts of records can be shared - very
useful in GUI implementation, in my opinion) with multiple dispatch, and
having structurally typed object system, like the one in OCaml. I hope I
will succeed in implementing such a system one day.

- Tom

[-- Attachment #2: Type: text/html, Size: 2438 bytes --]

Re: [Caml-list] Instruction selection in the OCaml compiler: Modulesor classes?

[Andreas Rossberg]

Tom <tom.primozic@gmail.com> wrote:
>
> I think you should take a look at another currently active thread  -
> "Feature request : Tuples vs. records". One of the red lines there is the
> comparison of structural versus nominal typing - classes and objects
> belonging to the former, and modules and records to the latter.

Not exactly: ML modules employ fully structural typing and subtyping. That 
is their big strength, in contrast to comparable features in most other 
languages (particularly typical notions of class).

- Andreas

Re: [Caml-list] Instruction selection in the OCaml compiler: Modulesor classes?

[skaller]

On Fri, 2007-02-23 at 20:28 +0100, Andreas Rossberg wrote:
> Tom <tom.primozic@gmail.com> wrote:
> >
> > I think you should take a look at another currently active thread  -
> > "Feature request : Tuples vs. records". One of the red lines there is the
> > comparison of structural versus nominal typing - classes and objects
> > belonging to the former, and modules and records to the latter.
> 
> Not exactly: ML modules employ fully structural typing and subtyping. That 
> is their big strength, in contrast to comparable features in most other 
> languages (particularly typical notions of class).

I wonder if more explanation could be given here? I admit continuing
to be confused by the status of modules.

It seems like a module functor allows both anonymous 
signatures (structural) and also anonymous argument 
modules (structural), yet you cannot have
anonymous functor applications: you have to bind the application to
a module name. If we really had structural typing that name would
simply be an alias. Why can't we eliminate that name? ***

C++ template applications can be anonymous, and that gives them
a major edge over Ocaml modules. Similarly, when you're lucky
enough to be able to use non-modular functor (a function with
polymorphic type) it is much more convenient. For example Hashtbl
provides both alternatives, whereas Set and Map do not (a fact
many people complain about).

*** more precisely, we probably don't want to eliminate the name
most of the time, but we would like to be able to use a 
'Set of int' in several modules without having to *export* 
the type in another module so it can be reused.

This is particularly annoying when it is intractable: for
example I have variant terms some of which contain sets
of terms .. the recursion is easy to represent with
lists but you can't do it with modular data structures.
The way I do it is make sets of integers instead and 
keep a term table indexed by the integers. But this isn't
really safe. There's probably a better way but the fact
remains if I want the type safety I have to use lists
or some other non-modular data structure: the modules
actually get in the way of type safety instead of 
enhancing it. I guess the 'recursive modules' stuff will
help fix this?


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Instruction selection in the OCaml compiler: Modulesor classes?

[David Baelde]

On 2/24/07, skaller <skaller@users.sourceforge.net> wrote:
> It seems like a module functor allows both anonymous
> signatures (structural) and also anonymous argument
> modules (structural), yet you cannot have
> anonymous functor applications: you have to bind the application to
> a module name. If we really had structural typing that name would
> simply be an alias. Why can't we eliminate that name? ***

One worthy remark here might be that side-effects can occur at functor
instantiation. Then, forcing the user to think about when the
instantiation occurs is useful...

--David

[Caml-list] Instruction selection in the OCaml compiler: Modulesor classes?

[Lukasz Stafiniak]

[I'm sorry, I forgot to send to the list!]

On 2/24/07, David Baelde <david.baelde@gmail.com> wrote:
> On 2/24/07, skaller <skaller@users.sourceforge.net> wrote:
> > It seems like a module functor allows both anonymous
> > signatures (structural) and also anonymous argument
> > modules (structural), yet you cannot have
> > anonymous functor applications: you have to bind the application to
> > a module name. If we really had structural typing that name would
> > simply be an alias. Why can't we eliminate that name? ***
>
> One worthy remark here might be that side-effects can occur at functor
> instantiation. Then, forcing the user to think about when the
> instantiation occurs is useful...
>
Yet OCaml already has trouble with some nasty patterns of effects at
functor instantiation.

Taken from one of the slides at http://www.cs.cmu.edu/~rwh/courses/modules/

This is good (Skaller: does it solve your problem?):

module type DICT = functor (Key : Set.OrderedType) -> sig
 type 'a dict
 val domain : 'a dict -> Set.Make(Key).t
end;;

module type PRIO_QUEUE = functor (Elt : Set.OrderedType) -> sig
 type queue
 val contents : queue -> Set.Make(Elt).t
end;;

module QueuedDict (Data : Set.OrderedType)
 (MyDict : DICT) (MyPrioQueue : PRIO_QUEUE) =
struct
 module Dict = MyDict (Data)
 module PQ = MyPrioQueue (Data)
 module DataSet = Set.Make (Data)
 let queued_domain dict pq =
   DataSet.equal (Dict.domain dict) (PQ.contents pq)
end;;

This is bad:

let moonFull = let v = ref false in fun () -> v := not !v; !v
;;

module type S = sig
 type t
 val x : t
 val f : t -> t
 val g : t -> t -> bool
end;;

module Weird (Top : sig end) = (struct
 type t = int
 let x = if moonFull () then 1 else 2
 let f x = x + 2
 let g x y = (3*x + 2*y) / (x - y + 1) = 7
end : S);;

module Gen (X : functor (Top : sig end) -> S) = X (struct end);;

module W1 = Gen (Weird);; (* moon full now *)
module W2 = Gen (Weird);; (* moon no longer full now *)
W1.g W1.x W2.x;;

Re: [Caml-list] Instruction selection in the OCaml compiler:Modulesor classes?

[Andreas Rossberg]

"skaller" <skaller@users.sourceforge.net>:
>
> It seems like a module functor allows both anonymous
> signatures (structural) and also anonymous argument
> modules (structural), yet you cannot have
> anonymous functor applications: you have to bind the application to
> a module name.

Not at all. For instance, given

  module Id(X : sig type t end) = X
  module A = struct type t = int end

it is perfectly legal to write:

  module A' = Id(Id(Id(A)))

Obviosuly, the inner applications of Id are all "anonymous".

Likewise, you can say

  (3 : Id(Id(A)).t)

Also purely anonymous applications.

> C++ template applications can be anonymous, and that gives them
> a major edge over Ocaml modules.

This is not really an issue of anonymity, but rather a matter of implicit 
vs. explicit sharing. In C++, all "equivalent" applications of the same 
template are - at least semantically - implicitly shared (where "equivalent" 
is rather ill-defined when it comes to non-type template arguments). In 
OCaml, all type instantiations are shared (sharing is based on a purely 
syntactic notion of module expression equivalence that is rather weak). But 
for the value part, which might involve state, you have to be explicit about 
sharing, and thus explicit about separate instantiation. After all, it makes 
a crucial semantic difference if you copy the state, and multiple 
instantiations may be desired. C++ cannot express this directly.

(As an aside, module theorists argue that it is incoherent to share types 
across instantiations of functors that are stateful. In such cases you 
rather want so-called generative functors, which OCaml does not have. SML 
has the latter, but in turn does not offer OCaml-style "applicative" 
functors, which is just as bad. More recent type theories for modules 
incorporate both.)

> Similarly, when you're lucky
> enough to be able to use non-modular functor (a function with
> polymorphic type) it is much more convenient. For example Hashtbl
> provides both alternatives, whereas Set and Map do not (a fact
> many people complain about).

Yes, the fact that there is an overlap between functors and core-language 
polymorphism is a bit unfortunate. It is one of the advantages of 
Haskell-style type classes over ML modules that they blend seamlessly with 
polymorphism. Of course, they have other disadvantages instead, implicit 
sharing being one of them.

> *** more precisely, we probably don't want to eliminate the name
> most of the time, but we would like to be able to use a
> 'Set of int' in several modules without having to *export*
> the type in another module so it can be reused.

You can more or less do that already, as long as you introduce a suitable 
global module to host the integer type:

  module Int = struct type t = int let compare = compare end

  signature A = sig ... val foo : u -> Set.Make(Int).t -> unit ... end
  signature B = sig ... val bar : v -> w -> Set.Make(Int).t ... end

Admittedly, the type looks a bit ugly, and it would be even nicer if Int was 
in the stdlib. But that are merely a questions of library design.

Due to the "weak syntactic notion of module equivalence" I was mentioning 
earlier you have to make sure that all these type expressions really refer 
to the same Int module. This is a limitation of OCaml's module type system, 
and may be what sometimes gives the impression of "nominal" typing. The 
limitation has long been solved in theory, but a full-fledged theory has not 
made it into any concrete ML implementation yet. Moscow ML probably comes 
closest.

> This is particularly annoying when it is intractable: for
> example I have variant terms some of which contain sets
> of terms .. the recursion is easy to represent with
> lists but you can't do it with modular data structures.
> The way I do it is make sets of integers instead and
> keep a term table indexed by the integers. But this isn't
> really safe. There's probably a better way but the fact
> remains if I want the type safety I have to use lists
> or some other non-modular data structure: the modules
> actually get in the way of type safety instead of
> enhancing it. I guess the 'recursive modules' stuff will
> help fix this?

Yes, with recursive modules you should be able to express this. Something 
like:

  module rec Term : Set.OrderedType = struct type t = A | B of TermSet.t let 
compare = compare end
  and TermSet : (Set.S with type elt = Term.t) = Set.Make(Term)

or even:

  module rec Term : Set.OrderedType = struct type t = A | B of 
Set.Make(Term).t let compare = compare end

- Andreas

Re: [Caml-list] Instruction selection in the OCaml compiler:Modulesor classes?

[skaller]

On Sat, 2007-02-24 at 15:58 +0100, Andreas Rossberg wrote:
> "skaller" <skaller@users.sourceforge.net>:
> >
> > It seems like a module functor allows both anonymous
> > signatures (structural) and also anonymous argument
> > modules (structural), yet you cannot have
> > anonymous functor applications: you have to bind the application to
> > a module name.
> 
> Not at all. For instance, given
> 
>   module Id(X : sig type t end) = X
>   module A = struct type t = int end
> 
> it is perfectly legal to write:
> 
>   module A' = Id(Id(Id(A)))
> 
> Obviosuly, the inner applications of Id are all "anonymous".
> 
> Likewise, you can say
> 
>   (3 : Id(Id(A)).t)
> 
> Also purely anonymous applications.

I had no idea you could do that!


> You can more or less do that already, as long as you introduce a suitable 
> global module to host the integer type:
> 
>   module Int = struct type t = int let compare = compare end
> 
>   signature A = sig ... val foo : u -> Set.Make(Int).t -> unit ... end
>   signature B = sig ... val bar : v -> w -> Set.Make(Int).t ... end
> 
> Admittedly, the type looks a bit ugly, and it would be even nicer if Int was 
> in the stdlib. But that are merely a questions of library design.

[..]

> Due to the "weak syntactic notion of module equivalence" I was mentioning 
> earlier you have to make sure that all these type expressions really refer 
> to the same Int module. This is a limitation of OCaml's module type system, 
> and may be what sometimes gives the impression of "nominal" typing. 

Yes .. I think I see. Two such modules 'Int' would have the same type,
but not the same 'identity'. In a similar way that

module Int' = struct type t = int let compare = mycompare end

has the same type as Int .. but it's a different module because
the value of 'compare' member is different.

I think what you're saying also explains some of the weird
sharing constraints sometimes seen.

[When I tried to implement modular functors in Felix I couldn't
figure out what was going on and had to give up .. typeclasses
were easier, but it's discouraging to find you can only have
one total order defined for integers.. :]


-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net