C++ does have some very powerful generic programming features. I find,
however, that I can do the vast majority of useful generic programming
things that I might do with C++ templates by using functors and
higher-order functions in OCaml (or Standard ML).

Functors allow modules to be parameterized over other modules,
frequently data types and associated operations. Practically, this
allows you to have code which can operate over any structures/backends
that meet particular requirements, and the backend can be switched by
simply instantiating the functor over a different module. Further, you
have very strong typing guarantees which are far easier to debug than
C++ template error messages.

The OCamlGraph library is a very good example of how ML-style generic
programming can be implemented and used. It provides a variety of
graph-related algorithms, each functorized over a module interface
exposing the graph functionality it needs. It also provides a variety
of graph implementations. You can then piece together the pieces you
need. For example:

(* let's use persistent directed graphs *)
module G = Graph.Persistent.Digraph.Concrete(VertexModule)
(* everything has weight 1 *)
module W = struct
type label = unit
type t = int
let weight () = 1
let compare = Pervasives.compare
let add = (+)
let zero = 0
end
(* instantiate Dijkstra's algorithm with our graph and weight *)
module SP = Path.Dijkstra(G)(W)

Now we have access to Dijkstra's all-pairs shortest path over our choice
of graph implementation. Many other things don't even need the
syntactic overhead of modules and functors - passing around closures
will suffice.

- Michael

You might find these useful

"A Comparative Study of Language Support for Generic Programming"
Garcia et al
http://www.osl.iu.edu/publications/prints/2003/comparing_generic_programming03.pdf

"An Extended Comparative Study of Language Support for Generic
Programming" Garcia et al
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.110.122&rep=rep1&type=pdf

KHD

For most generic programming tasks the type system of standard Haskell
is totally sufficient. If you really need GHC extensions, you're
already doing something more sophisticated. Note that the type systems
of most other languages can't even express the most basic Haskell
constructs.

In fact, C++ isn't even a good choice, when it comes to generic
programming. Besides its ugly syntax, it also lacks type inference,
which can be very annoying. Further it has no support for anonymous or
at least lexically scoped functions, not to mention closures.

Another important fact is that C++ has no contracts, contexts,
interfaces or whatever you call them, so you need dynamic casts, which
are bad. A lot of problems are catched by them at compile time, but
because of the lack of them, most type errors in C++ can only be found
at run time, if the programmer doesn't forget to check for them.

Finally it's impossible to separate template interface and
implementation in a sane way. There is no module system of any kind.
You get header files and the classic dumb linker.

To see all of these problems in action at the same time, try to
implement Haskell's Functor class as a C++ template. It's about the
simplest example of useful generic programming, and C++ makes it a
nightmare.

No type inference means that you have to specify your container type all
the time. No anonymous functions, not even lexically scoped functions,
so your mapping function will be a named top-level function. No
contracts, so your fmap function doesn't even know whether your
container type is in fact a container type. It needs dynamic_cast, so
type errors are not catched at compile time. Furthermore it's
impossible to extend existing container classes to support your new
Functor template, not to mention primitive types like arrays. You need
to subclass existing classes and make a completely new class for arrays.


Greets
Ertugrul

There was a study by Garcia, Jarvi et al that Keith mentioned. A
working url is here:

http://www.osl.iu.edu/publications/prints/2005/garcia05:_extended_comparing05.pdf

It compared a bunch of different languages and Haskell basically came
out on top, except in one area, which was that it didn't support
associated types as well as could be done in C++ through template
programming. In response to the paper, SPJ et al added type families to
GHC:

http://haskell.org/haskellwiki/Simonpj/Talk:FunWithTypeFuns

and that took care of the weak spot. It mostly seems to me that we hear
more about generics in connection to C++ than to functional languages,
because the C++ community uses the term a lot more, and puts a lot of
energy into the template hacking needed to make it happen in C++. In
functional languages like ML or Haskell, it's just called "polymorphism"
and taken for granted. The Haskell community actually uses the term
"generic" to mean something different, i.e. the automatic derivation of
code from algebraic types, like the "deriving" mechanism or in libraries
like Scrap Your Boilerplate.

I only spent about a minute looking at the thesis about Scala that you
cited, but it looks interesting and I will put it on my reading list.
The thesis advisor, Jaakko Jarvi, is one of the co-authors of the
comparison paper that I linked to.

Unfortunately, I can't remember the exact quote, nor who said it, but:
people always use "generic" to refer to the kind of polymorphism their
favorite language does not have yet (or acquired late).

Perhaps this is not relevant to what you're interested in, but "generic
programming" has a relatively different (than in C++/Java/C#...) meaning in
the Haskell community (at least, and I suspect elsewhere as well), probably
because parametric polymorphism is so fundamental and almost trivial in a
Haskell (or ML, or...)-like language.

Anyhow, generic programming in Haskell is typically meant to refer to
functions that are able to work over multiple different structures, by
somehow using a description of how the structure is built from its
constituent parts. One basic way of doing this is to treat all data as fixed
points of functors, and so you get functions like:

cata :: forall f r. Functor f => (f r -> r) -> Mu f -> r
ana :: forall f s. Functor f => (s -> f s) -> s -> Nu f

which are in some sense parameterized by the shape of the structure (f),
rather than just being parameterized by what you can put in some fixed
structure. I think there is at least one framework building on the above
(the name of which escapes me), but there are others that use other ideas,
like Uniplate and Scrap Your Boilerplate.

Clean also has built-in support for this kind of generic programming, but
finding information on it is difficult, as I recall, because the section on
it in the Clean report is blank for some reason.

With regard to another message, GHC at least now implements associated
types, so that bubble can be filled in all the way for it now. :)

-- Dan

Everyone uses the term "generic programming" to refer to making definitions
more widely applicable (i.e. general) which seems to be indistinguishable
from code reuse and/or factoring to me. This is, in turn, strongly related
to brevity.

Lisp's macros were one of the earliest forms of generic programming and,
yet, modern uses of the term "generic programming" often refer specifically
to the expressiveness of static type systems. This seems to be particularly
prevalent in the context of Haskell where generic programming is conflated
with type constraints and any relevance to the true objective of code reuse
is lost.

For example, Haskellers Garcia et al. published a paper "An extended
comparative study of language support for generic programming" that was
actually more about static type constraints than it was about generalizing
definitions or improving brevity and reuse. Although they claimed to have
implemented graph theoretic code in several languages, their OCaml code
seems to have remained secret:

http://www.osl.iu.edu/research/comparing/

Garcia had published research on Haskell and apparently wrote great Haskell
solutions in this paper but I think their OCaml code leaves a lot to be
desired (and probably all of the other non-Haskell solutions as well) and
their relevant conclusions are simply wrong. Apparently they managed to get
this published without obtaining peer review from anyone familiar with the
other languages.

Even their first example (complete with superfluous parentheses and
semicolons):

class type comparable = object ('a) method better : 'a -> bool end

class apple init = object (self: 'a)
val value_ : int = init
method better (y: 'a) = self#value > y#value
method value = value_;
end

let pick ((x: #comparable as 'a), (y: 'a)) : 'a =
if x#better y then x else y

let a1 = (new apple 3);;
let a2 = (new apple 1);;
let a3 = pick (a1, a2);;

would normally be written:

let apple i = object
method better y = i > y#value
method value = i
end

let pick x y = if x#better y then x else y

let a1 = apple 3 and a2 = apple 1
let a3 = pick a1 a2

The essential difference is that OCaml can infer the relevant types and,
consequently, there is no need to define these types and their
relationships by hand. Ironically, their OCaml code inherited superfluous
definitions from the Haskell and they then concluded that these were a
disadvantage for OCaml because non-trivial combinations must be maintained
by hand (which is simply wrong: they are all automatically inferred).

Now look at their keystone OCaml solution for the graph theoretic problem:

class type ['vertex_t] vertex_list_graph = object
method vertices : 'vertex_t list
method num_vertices : int
end

class type ['vertex_t] edge = object
method source : 'vertex_t
method target : 'vertex_t
end

class type ['vertex_x, 'edge_t] incidence_graph = object
constraint 'edge_t = 'vertex_t #edge
method out_edges : 'vertex_t -> 'edge_t list
end

In the context of generic programming, these type definitions are entirely
superfluous. Sadly, they use these superfluous definitions to justify the
conclusion that OCaml is needlessly verbose.

They do give the following concrete implementation of an adjacency-list
based graph type in their paper:

class algraph_edge (s: int) (t: int) = object
val src = s
val tgt = t
method source = src
method target = tgt
end

class adjacency_list (num_vertices_) = object
val g = Array.make num_vertices_ []

method add_edge (src, tgt: int * int) = g.(src) <- (tgt::g.(src))

method vertices =
let rec floop (i: int) =
if i = num_vertices_ then [] else i::floop(i+1) in
floop 0

method num_vertices = num_vertices_

method out_edges v = List.map (fun n -> new algraph_edge v n) g.(v)

method adjacent_vertices v = g.(v)

method edges =
let (_, result) = Array.fold_left
(fun (src, (sofar: (algraph_edge) list)) (tgts: int list) ->
(src+1, List.append
(List.map (fun n -> new algraph_edge src n)
tgts) sofar))
(0, []) g in
result

method create_property_map : 'a. 'a -> 'a array =
fun def -> Array.make num_vertices_ def
end

let graph_search
(graph: (('vertex_t, 'edge_t) #incidence_graph) as 'graph_t)
(v: 'vertex_t)
(q: 'value_t #buffer)
(vis: ('graph_t, 'vertex_t, 'edge_t) #visitor)
(map: ('color_t, 'key_t) #color_map) = ...

This is just abhorrent and could not be less representative of a real OCaml
solution.

Why the superfluous immutable private data in the "algraph_edge" class?

Why are they defining classes that only have the effect of making the code
less generic?

Why are they mixing mutable (array) and immutable (list) data structures
like this?

Why the unnecessary nested function in the "vertices" method to create the
list [0..n-1]?

Why did they not annotate the type of "g" where it might actually help but
did annotate the arguments to the inner anonymous function in the "edges"
method?

You can rewrite their 46-line OCaml solution with the following 14-line
OCaml solution:

let edge s t = object method source = s method target = t end

let adjacency_list n = object
val g = Array.init n (fun _ -> Stack.create())

method add_edge (src, tgt) = Stack.push tgt g.(src)
method vertices = Array.init n id
method num_vertices = n
method out_edges v = g.(v)
method adjacent_vertices v = g.(v)
method edges =
let es = Stack.create() in
Array.iteri (fun u -> Stack.iter (fun v -> Stack.push (edge u v) es));
es
end

This uses more idiomatic data structures but that is irrelevant in this
context.

Finally, they claim that the OCaml solution cannot support separate
compilation. Is that true? I doubt it...
The problem with C++ (and Haskell) is that the Turing complete type system
gives you complete generality in some uselessly-impractical sense, i.e. it
is a Turing argument.
You must take into account the applicability of these "solutions" in real
programs. The .NET guys are acutely aware of many of the academic features
found in languages like Haskell but they choose not to adopt them because
they do not solve real problems.