Changeset 2409 for Papers/polymorphic-variants-2012/polymorphic-variants.tex

Timestamp:

Oct 19, 2012, 4:48:06 PM (9 years ago)

Author:

mulligan

Message:

Some text about algebraic data types and their limitations. Needs to be finished.

File:

• Papers/polymorphic-variants-2012/polymorphic-variants.tex (modified) (1 diff)

Papers/polymorphic-variants-2012/polymorphic-variants.tex

@@ -40 +40 @@
 \label{sect.introduction}
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% Section
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \section{Polymorphic variants}
+\label{sect.polymorphic.variants}
+
+In this section we provide a self-contained \emph{pr\'ecis} of polymorphic variants.
+For a more complete summary, we refer the reader to Garrigue's publications on the subject~\cite{dpm: todo}.
+
+Most mainstream functional programming languages, such as OCaml and Haskell, have mechanisms for inductively defining types through the use of \emph{algebraic data types}.
+Each algebraic data type can be described as a sum-of-products, wherein we associate a fixed number of distinct \emph{constructors} to the type being introduced, all of whom expect a product of arguments.
+Inductive data, modelled as an algebraic data type, is built incrementally from the ground-up using the constructors of that type.
+Quotidian data structures---such as lists, trees, heaps, zippers, and so forth---can all be introduced using this now familiar mechanism.
+
+Having built data using constructors, to complete the picture we now need some facility for picking said data apart.
+Functional languages employ \emph{pattern matching} for this task.
+Given any inhabitant of an inductive type, by the aforementioned sum-of-products property, we know that it must consist of some constructor of that type applied to various arguments.
+Using pattern matching we can therefore deconstruct algebraic data by performing a case analysis on the constructors of a given type.
+
+The combination of algebraic data types and pattern matching is powerful, and is arguably the main branching mechanism for most functional programming languages.
+Further, using pattern matching it is easy to define new functions that consume algebraic data---the set of operations that can be defined for any given algebraic type is unbounded.
+Unfortunately, when it comes to extending algebraic data types with new constructors these types are essentially `closed'.
+We cannot simply extend an algebraic type with a new constructor.
+We must introduce a new algebraic type with the additional constructor, lifting the old type---and any functions defined over it---into this type.
+
+Moving sideways, we can compare and contrast functional programming languages' use of algebraic data paired with pattern matching with the approach taken by object-oriented languages.
+In mainstream object-oriented languages such as Java algebraic data types correspond to class hierarchies, each constructor corresponding to a subclass in this hierarchy.
+Pattern matching is emulated using a dynamic dispatch mechanism.
+Using the object-oriented approach it is easy to add a new `case' to a given hierarchy: just introduce a new subclass.
+
+[dpm: reword the above --- hard to phrase precisely ]
+
+
 \begin{itemize}
  \item General introduction, motivations