IWETHEY v. 0.3.0 | TODO
1,095 registered users | 0 active users | 0 LpH | Statistics
Login | Create New User
IWETHEY Banner

Welcome to IWETHEY!

New Re: ML Functors
Functors are basically modules parameterized with other modules.
This is an incredible boon to expressiveness, because it lets
you turn a combinatorial growth in the number of implementations
into linear growth.

This is best seen with an example. I'll use Objective Caml because
that's the dialect I know the best. Suppose that we have an interface
for priority queues. This might look like the following


module type Q =
sig
type key
type q

val empty : q

val add : key -> q -> q (* Add an element to the queue *)
val max : q -> key (* Get the highest priority element *)
val del : q -> q (* Delete the highest priority element *)
end


When actually implementing the queue, there are two dimensions
of implementation: the data structure used to represent the
priority queue, and the order relation on the elements of the
queue.

In a Java-like language, the way one would do this is to first
define an interface for the priority queue, and then for
each different data structure you would define an abstract
method for the comparison routine. Then, you'd specialize
each class with concrete implementations.

So if you had (say) 5 different queue structures, and 10 different
comparison routines, then there would need to be 5 x 10 = 50
concrete implementation classes. Worse, there would be a lot
of duplication, since every comparison would have to be textually
repeated 5 times.

Functors let you break that problem, and write just the 5
different data structures and the 10 comparisons, and then
combine them. That's 5 + 10 = 15 bits of code you need to
write, and there's no duplication whatsoever.

So what you'd do is define an interface for the comparisons,
like this:


module type ORD =
sig
type t

val cmp : t -> t -> int (* An ordering relation; when two elements
x & y are compared, return

{ -1, if x < y
cmp x y = { 0, if x = y
{ +1, if x > y
*)
end



And writing some parameterized modules -- functors. Here are two
implementing priority queues as sorted lists and as binary trees:



module ListQueue(Elt : ORD) : Q with type key = Elt.t =
struct
type key = Elt.t
type q = key list

let empty = []

let rec add x q =
match q with
[] -> [x]
| x' :: q' when Elt.cmp x x' < 0 ->
x' :: (add x q')
| _ -> x :: q

let max q = List.hd q

let del q = List.tl q
end

module TreeQueue(Elt : ORD) : Q with type key = Elt.t =
struct
type key = Elt.t

type q = Nil | Node of q * key * q

let empty = Nil

let rec add key q =
match q with
Nil ->
Node(Nil, key, Nil)
| Node(left, key', right) when Elt.cmp key key' < 0 ->
Node(add key left, key', right)
| Node(left, key', right) when Elt.cmp key key' > 0 ->
Node(left, key, add key right)
| Node(left, key', right) ->
Node(left, key, right)

let rec max q =
match q with
Nil ->
raise Not_found
| Node(left, key, Nil) ->
key
| Node(left, key, right) ->
max right

let rec del q =
match q with
Nil ->
raise Not_found
| Node(left, key, Nil) ->
left
| Node(left, key, right) ->
Node(left, key, del right)
end



Note that some of the capabilities of functors are provided
by multiple inheritance used in a mixin style. However, this
is quite fragile vis-a-vis functors because all the internals
of each mixin class are visible in the subclass, whereas with
functors only the specified interface is available, /and/ it's
in another namespace. Also, the benefits of functors get larger
and larger as the number of possible ways to combine your
program grow.

New C++ templates?
Is it just me or functors are similar to C++ templates?
New Re: C++ templates?
They are a bit similar, but not precisely the same thing.

The difficulty in comparing them is mostly due to the fact that the
C++ standards committee was careless in the template specification
and accidentally got something a lot more powerful than they expected.
As a result, templates are a very weird language construct -- they
were intended to make parametric polymorphism easier to do but
are actually capable of a lot more than that.

Parametric polymorphism is the ability to write a function that
operates the same way on multiple types. The simplest example is
the identity function


# let identity x = x
val identity : 'a -> 'a


The function identity simply returns its argument, and the type 'a -> 'a
indicates that it can accept any type argument. Similarly, you can
write a polymorphic length function for lists like this:


# let rec len x =
match x with
[] -> 0
| x :: xs -> 1 + len xs

val len: 'a list -> int


Here, you can see that len operates on lists of any element -- that's what
the type 'a list means. The translations for identity and len in C++ are
two of the first examples people see when using templates.

Note that there are no type declarations in the OCaml code; the compiler
automatically infers the most general typing for every expression
submitted to the compiler, and will signal a compile error if there is
no correct type for the code. This is different from C++, where every
type has to be explicitly declared, and every polymorphic function
needs to be enclosed in an explicit template expression.

Note that parametric polymorphism is a very specific kind of polymorphim:
a polymorphic function does exactly the same thing regardless of the
types of the arguments. Sometimes you need to parameterize your code
so that it does different things at different types. This is what ML
offers functors for -- they let you write modules that are parameterized
with other modules.

C++ uses templates plus inheritance to model this case, plus some linking games. This is IME rather complicated, and doesn't map to how people
think about it. Not a fatal problem, but definitely an annoyance. The
real killer argument for me is that functors and parametric polymorphism
do not break separate compilation and do not cause code bloat. Due to
the way they are specified, a compiler can generate a single piece of
code for each polymorphic function and each functor.
New Re: C++ templates?
After I tried to rewrite your example in C++, I think I understand what you mean. Unless I use inheritance, the classes that implement Q will not have the same interface from compiler's point of view. Then again, what is the relationship between Q and ListQueue in your example?
New Re: C++ templates?
Yeah, this is a really interesting thread, but I'm having a issue translating in my head to C++...

Arkadiy, any chance you can post your translated code? That'd be quite helpful.


-Jason
----

My pid is Inigo Montoya. You "killed -9" my parent process. Prepare to vi.
New Re: C++ templates?
The Q signature is a module signature, and ListQueue and TreeQueue are the concrete implementations. In C++ terms, Q would be a fully abstract base class, and ListQueue and TreeQueue would be the distinct roots of concrete implementation hierarchies that each have Q as a superclass.

ListQueue and TreeQueue would also be template classes, with the template parameter controlling the element type. There would also have to be a method to compare different elements, either as part of the Queue implementation or the element implementation. (This is what the functor argument Elt : ORD means; it says that elements have to have a comparison operation.)

I'd appreciate it if you could post your C++ translations. The last time I wrote any C++ was ~5 years ago, so while I can read it I can't write it anymore. :)
New Re: C++ templates?
Actually, I suspect that STL is just such a translation. map versus set versus multimap is about the same as your queue implementations.

>>>>>>>
There would also have to be a method to compare different elements, either as part of the Queue implementation or the element implementation. (This is what the functor argument Elt : ORD means; it says that elements have to have a comparison operation.)
<<<<<<<<

And therein lies an error. The comparison does not have to be a member in either queue or element. It can be another template parameter.

So, you'd have something like

template <class Element>
class less
{
/*operator () is used for lots of things in STL, ini this context it's just a comparison function */
bool operator()(const Element &e1, const Element &e2) {
return e1 < e2;
}
}

template <class Element>
class more
bool operator()(const Element &e1, const Element &e2) {
return e1 > e2;
}
}


class customCompare
{
bool operator()(const MyVeryOwnType &e1, const MyVeryOwnType &e2) {
return e1.field1 < e2.field1;
}
}


template <class Element, class Comparison>
class set
{

set() {};

/* use this constructor when comparison depends on external data (almost never) */
set(Comparison &comp) : less(comp) {}

/* here in the set I can use less(e1, e2) (which is actually less.operator()(e1, e2) */

Comparison less;
}



typedef set <int, less<int> > ascendingSet

typedef set <int, more<int> > descendingSet

typedef set <MyVeryOwnType, customCompare> customSortedSet



New Re: ML Functors
Just a note, I think the normal way to do it in Java would be to use java.util.Comparator objects in a 'comparable' way to your use of Functors. The queues could accept a Comparator in their constructors, and use its "int compare(Object a, Object b)" method for ordering - perhaps handled in an abstract base class.

It's entirely possible that I'm not appreciating the ML code (not familiar with it), but the Java version could/should/would be neatly done without the "combinatorial explosion".
New Re: ML Functors
Passing an explicit comparison function/object would work in ML too, but I left it out of the list of possibilities because it's not as type-safe a solution, and I wanted to compare maximally safe solutions in both languages.

Eg, two priority queues with different ordering schemes would have the same signature, which means that it's possible to (for example) incorrectly merge two queues with different ordering schemes. If each kind of ordering is a queue with a different type, then this error can get caught at compile-time. With the signature I outlined it's not a big deal, but for things like a Set class (which have union and intersection methods) it becomes a more significant problem.
     ML Functors - (CrisR) - (9)
         Re: ML Functors - (neelk) - (8)
             C++ templates? - (Arkadiy) - (5)
                 Re: C++ templates? - (neelk) - (4)
                     Re: C++ templates? - (Arkadiy) - (3)
                         Re: C++ templates? - (jlalexander)
                         Re: C++ templates? - (neelk) - (1)
                             Re: C++ templates? - (Arkadiy)
             Re: ML Functors - (luke) - (1)
                 Re: ML Functors - (neelk)

I can say "where's the bathroom", "how much is that" and "those aren't my drugs" in 187 languages.
316 ms