Design patterns as higher-order datatype-generic programs

Well, I got side-tracked from working directly on the book. One of the sidetracks was working on my paper Design Patterns as Higher-Order Datatype-Generic Programs from the Workshop on Generic Programming in 2006, revising and extending it for a journal; I’ve put the revised version online. In my defence, I offer that although this isn’t directly content for the book, it is indirectly so.

The central argument of the paper is that current mainstream programming languages such as Java and C# are not expressive enough to allow one to capture the code parts of design patterns such as the Visitor pattern. However, functional languages such as Haskell are sufficiently expressive—which I demonstrate in the paper by providing Haskell representations of four of the GOF patterns.

As the title of the paper suggests, the specific concepts that Haskell provides but current mainstream languages do not are higher-order (parametrization by a function, sometimes called a “lambda” or a “closure”) and datatype-generic (parametrization by a type functor) features. I’ve taken to calling programs exploiting these features “HODGPs”, and languages providing them as “HODGP languages”. A HODGP language lets you capture the code of design patterns as highly flexible reusable software components. Interestingly, Scala also provides HODGP features, together with everything you’d expect from an OO language; I’m hopeful that Java and C# will follow Scala’s lead (or that Scala will supercede them!). Bruno Oliveira‘s DPhil thesis Genericity, Extensibility and Type-Safety in the Visitor Pattern explored using Scala for HODGPs.

Of course, I admit that “capturing the code parts of a pattern” is not the same as capturing the pattern itself. There is more to the pattern than just the code; the “prose, pictures, and prototypes” form an important part of the story, and are not captured in a HODGP representation of the pattern. So the HODGP isn’t a replacement for the pattern.

The four GOF patterns I discuss in the paper are Composite, Iterator, Visitor and Builder. My claim is that Composite (hierarchical structures) amounts to recursive datatypes, Iterator (linear traversals over the elements of a collection) to maps, Visitor (structured traversals also exploiting the shape of a collection) to folds, and Builder (separating the construction of an object from its representation) to unfolds and builds. This is a simplification, both of the patterns and the paper; take a read if you want the full story!

Advertisements

About jeremygibbons

Jeremy is Professor of Computing in Oxford University Department of Computer Science, and a fan of functional programming and patterns of computation.
This entry was posted in Uncategorized. Bookmark the permalink.

6 Responses to Design patterns as higher-order datatype-generic programs

  1. Brian Hurt says:

    This is something I’ve been contemplating for a while- are the popular type classes of Haskell- monads, monoids, arrows, iteratees, etc., the design patterns of the functional world? In other words, does the isomorphism between design patterns and (some) type classes work both ways?

    • I think I’d say that type classes are just the Haskell way of capturing (the interfaces of) abstract datatypes. Design patterns (some of them, at least, and only their code parts too – not the accompanying backstory) amount to patterns of computation, and my argument here is that the Haskell way of capturing those is as datatype-generic higher-order functions. So in answer to your second question, “design patterns” to a functional programmer are just (highly generic) “code”, because the tools for abstraction are so much richer than in conventional OO languages.

  2. nuttycom says:

    While folding is a common use of the Visitor pattern, the essence of the pattern is multiple dispatch. In fact, the common pattern of having the ‘accept’ and ‘visit’ methods return void is a serious design error. In Java, Visitor is correctly implemented thus:

      interface I {
         <B> B accept(Visitor<B> v);
      }
    
      class J implements I {
        <B> B accept(Visitor<B> v) {
          return v.visit(this);
        }
      }
    
      class K implements I {
         // you know the drill
      }
    
      interface Visitor<A> {
        A visit(J j);
        A visit(K k);
      }
    

    Visitor is essentially a function from I to the polymorphic A. As such, it also can be implemented to form an instance of the Reader monad: http://logji.blogspot.com/2009/12/reader-monad-for-visitor-pattern.html

    • nuttycom says:

      Damn it, looks like all my generic type signatures got stripped. Should have implemented it in Scala. Can you please fix? 🙂

    • Yin Wang says:

      I agree with you. Visitor patterns are type-pattern dispatch. We can also achieve the same without using visit and accept. Just write a method in each subclass (of an abstract class) will be okay, and it saves some clutter too. For example, an interpreter can be written in Java as a series of methods of this signature:

      Value interp(Env e)

      If you use Eclipse to navigate through multiple files, this way will be much more efficient to code, also more readable than accept and visit. I used this trick when I wrote an abstract interpreter for Python in Java 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s