Wednesday, 29 December 2010

Extensibility in functional programming languages

Most software developers are now familiar with inheritance and virtual methods as common techniques for extensibility from the object oriented paradigm. When faced with functional programming for the first time, these developers often ask how to write extensible code in this alien paradigm.

The functional paradigm actually only provides a single form of extensibility: higher-order functions. These allow you to factor out "inner" functions. For example, code that often appears with the same first and last code blocks:

let f x =
first x
stuff1 x
last x

let g x =
first x
stuff2 x
last x

can be factored into a general higher order function that is reused from the specific cases:

let hof stuff x =
first x
stuff x
last x

let f = hof stuff1 x

let g = hof stuff2 x

Applying this aggressively leads to design patterns such as parser combinators and is a very powerful and lightweight technique for making code extensible. However, it does not make data types extensible.

Consequently, functional programming languages almost always include language features to help with extensibility:

  • Common Lisp has the Common Lisp Object System (CLOS) and a macro system.
  • Standard ML has parametric polymorphism and a higher-order module system.
  • OCaml added polymorphic variants, objects, optional arguments and the Camlp4 macro system.
  • Haskell has parametric polymorphism and type classes, and Template Haskell adds macros.
  • Scala has Java-style OOP with some added features.

Read Chris Okasaki's excellent monograph Purely functional data structures for some great examples using higher-order modules in Standard ML and type classes in Haskell. Read Code reuse through polymorphic variants by Jacques Garrigue for a description of how that language feature can be used to attack the expression problem. However, these solutions are quite rare in the wild and, in particular, you can get a long way without them (e.g. in F#).

Historically, this diversity appeared because most functional programming languages were research projects and, consequently, they existed to add novel features. Therefore, we now have a wide variety of disparate forms of extensibility in today's functional programming languages.

F# is a different beast compared to its predecessors like OCaml and Haskell because its design requirements were seamless interoperability with the rest of .NET (which imposes .NET-style OOP) and pragmatism. Consequently, F# keeps the ML core with parametric polymorphism and adds .NET's object system. So you can benefit from the easy extensibility offered by generic higher-order functions and conventional OOP but not from any of the more esoteric features like higher-order modules, type classes and macros.

The only form of extensibility F# has pioneered is active patterns. These allow you to separate code that destructures via pattern matching from the concrete data representation. This is an important way to decouple code from data and, therefore, make it more reusable.


peter said...

In object oriented programming inheritance and basic methods are the accepted book for creating adaptable code. Consequently, F# keeps the ML core with parametric polymorphism and adds .NET's object system.

toshiba direct coupon code

jay paul said...

Nice post! Can’t wait for the next one. Keep stuff like this coming.

HP - ENVY 15.6" Laptop - 8GB Memory - 1TB Hard Drive - Silver

HP - Pavilion 15.6" Laptop - 4GB Memory - 750GB Hard Drive - Black (15-n030us)