Code reuse through polymorphic variants

Jacques Garrigue. In Workshop on Foundations of Software Engineering. Sasaguri, Japan, November 2000.

Abstract. Their support for code reuse has made object-oriented languages popular. However, they do not succeed equally in all areas, particularly when data has a complex structure, making hard to keep the parallel between data and code.

On the other hand, functional programming languages, which separate data from code, are better at handling complex structures, but they do not provide direct ways to reuse code for a different datatype.

We show here a way to achieve code reuse, even when data and code are separated. The method is illustrated by a detailed example.

You can get the A4 postscript or PDF version of this paper.

Here is the code for examples in the paper:
The evaluator presented in the paper. Updated for ocaml 3.04. (original version)
Full source of the sum type version of the evaluator, requires -rectypes.
Larger example, using objects to structure code. Recent changes to share more code.
Original example, encoded using polymorphic variants and recursive modules (ocaml 3.07). Much more verbose, but does not use polymorphism.
Same thing using normal sum types, without -rectypes.
An tentative solution(?), using polymorphic variant, recursive modules, and private rows (ocaml CVS/3.09). Quite verbose, but each extension can be writeen with only O(n+m) boilerplate, where n is the number of types involved in the recursion, and m the number of operation.
A purely object-oriented version (without variants), using immediate objects (ocaml 3.08).

JG 2005.02.24