Lambda the Ultimate

To be honest,

I disagree with your (non-present) definition of non-intrusiveness. I have read your article on the blog, and while it's true that Ruby has a very clean syntax, such things can be non-intrusively in C++ as well. C++ does not only purely rely on OO, but instead relies on the much more powerful system of generics and templates which is what loki leverages to achieve strategies in a non-intrusive way. You could probably achieve similar effects with Java, standard naming of methods and introspection, however it's not done as often. Perhaps this is due to the fact that ruby and c++ rely more heavily on standard operators behaving in standard fashions.

At the level you're talking about in that blog entry, patterns used in one generation of languages become language features of the next generation. This has always happened. It's certainly not some "dirty secret" of the patterns community.

Patterns of assembly programming were implemented in 3GLs. Think of the way one used to implement subroutines by pushing arguments and return address onto the stack.

Patterns of programming in 3GLs were implemented in OO languages. Think of the way one used to implement polymorphic objects in C by storing function pointers in structs.

Now the patterns we use in the current generation of languages are getting implemented in the next generation.

My problem with this paper is that they are using functional languages to implement OO patterns. What's the point? Document the patterns that programmers use when doing functional programming. That's more interesting.

From: "Design Patterns for Functional Strategic Programming", Lämmel, Visser, RULE 2002:

"One might suppose that the powerful abstraction mechanisms of functional programming obviate the need for design patterns, since many pieces of program construction knowledge can be captured by reusable functions. This confusion of design patterns with reusable components misses the point: patterns start where components end, in the sense that the former describe how the latter can be constructed and used. Thus, additional abstraction *creates* the need for new design patterns."

Apart from this difference of perspective on the role of design patterns, I found Jeremy's paper a clear and interesting read. I wonder how strategic programming, or the scrap-your-boilerplate approach to generics (which, incidentally does work with mutual recursive types) would fit into the story.

I might be easily led, but that all sure sounds really good to me.

This is a great paper and it really helped me understand this topic as a whole. Gibbons covers hylomorphisms and suspensions in precisely the manner I've been thinking about them. Having good knowledge about the shape of the data you're operating against is critically important. What we want is to be able to write simple functions, and have the "right" thing done for us automatically when these simple functions are used with complex shapes. A complex shape in a vector language is an array, or a matrix. In an object-oriented language the complex shape results from a traversal over an object structure; if we can form dependent types on the traversals (even dynamic) then the compiler can still do a significant amount of reasoning about the results, and do optimizations around the resulting hylomorphism.

(note what follows is discussion following from the paper, not topics necessarily covered in the paper itself)

Much of this kind of work has been done already in the vector programming community, but limited to vectors. The APL/J/K family defines adverbs that modify functions to influence behavior on shapes, but defines well-known core behavior against compatible shapes of data.

With object-oriented and functional programming we need to move beyond the indexing that most vector languages provide -- we want our shapes to be dynamically created and very flexible. I might want to dynamically create tree shape from a flat list, and I could code that directly. But that kind of code appears over and over again; what I want is to be able to declare well-typed patterns, like "all Integer members of this object", or "all numeric array members of this object whose names start with 'external'" or "the first, fifth, and sixth members from the list of members that are strings".

This is precisely what Java code does when it engages in reflection, but we've completely thrown away the ability of the compiler to help out because it's all effectively typeless at that point, and hylomorphic optimizations are no longer possible (unless you write them in your own code -- or perhaps the runtime library supports them).

P.S. It would be way cool if the standard pattern matching devices (like Scala's cases) supported such navigational patterns and were able to optimize the hylomorphism directly. A single object matches against the case's pattern; the right hand side of the pattern matching statement is a builder in Gibbons' terminology (Gibbons' builders accept a stream of objects and construct a complex type as a result -- the unfold function is such a builder). It constructs the correctly typed result for the match. Yup, in my dreams. ;)

P.P.S. In the ideal, ideal world the builder would actually be a zipper (a la Kiselyov), allowing a complex building operation to take place complete with (pseudo) destructive modifications. Then for complete and utter coolness, the CPS style of pipelining could be used to push and pull data up and down through complex (chained) hylomorphisms.

Now I really need to read this paper...

I like the vision you're painting but as far as I can tell the fold/unfold formalism presented in this paper is restricted to datatypes that are not mutually recursive and are polymorphic in exactly one parameter (ie. having kind * -> *).
That's quite sufficient to demonstrate the four chosen design patterns but I think that a more general foundation would be needed in practice.

Absolutely correct -- I have something of a blur between what I've been thinking about and the contents of this paper in mind. The paper lays the foundation cleanly, I think. The lack of mutually recursive data types impairs generality, but not at the expense of the vast majority of usages. It's just good to see the vocabulary for all this stuff.

GOF patterns were all about giving names to things we mostly knew before, but didn't what to call. I think there are a new set of names for common functions based on datatype genericity. The vector languages give us a start on naming; fully general type-safe traversals handled by a compiler in hylomorphic form can yield both safety and high performance.

One of the most interesting aspects of this is the intersection between constraint programming and datatype genericity -- when conducting an algorithm over a list or pair is no different from folding it over the domain of a discrete constraint (and indeed being able to mix the two together) we get closer to a unified declarative and imperative world, where the expressiveness of both can be combined at will and brought into higher order form too.

Somebody is going to do the very hard work of figuring this intersection out. :)

I don't know Scala, but would your encoding for type abstraction & application allow for recursive type synonyms?
Especially:

type Fix s a = s a (Fix s a)

which is illegal in Haskell (though I wish it wasn't). Being able to do that would make it possible to define generic operations that don't require the "In" constructor to be interleaved everywhere.
fold, unfold and map can then be defined as:

fold :: Bifunctor s => (s a b -> b) -> Fix s a -> b
fold f = f . bimap id (fold f)

unfold :: Bifunctor s => (b -> s a b) -> b -> Fix s a
unfold f = bimap id (unfold f) . f

map :: Bifunctor s => (a -> b) -> Fix s a -> Fix s b
map f = fold (bimap f id)

and using List as an example:

data List' a b = Nil | Cons a b
type List a = List' a (List a)

map (* 3) (Cons 1 (Cons 2 (Cons 3 Nil)))     -->  Cons 3 (Cons 6 (Cons 9 Nil))

which is more natural I think. As an additional benefit the need for a build operator disappears (ie. build = id).
Just mentioning this, because if it's possible, your Scala version could improve upon rather than just translate the haskell code.

Interesting suggestion, but I couldn't devise an encoding that would typecheck. I tried to use this.type as a substitute for the f in type Fix s a = μ f. s a (f s a), which should correspond to the type you gave using recursive type synonyms.

I've included my attempt anyway (along with the compiler errors), hoping that someone else might be able to improve on it or explain why it won't work :-)

My guess is that you need structural subtyping, but I must admit that I don't understand it deeply enough to be sure. (s{type a = ua; type b = Fix[s,ua]} is not seen as equivalent to Fix[s,ua], while this does seem to be the case, structurally)

  trait TypeConstructor {type a; type b} 
  trait Bifunctor[s <: Bifunctor[s]] requires s extends TypeConstructor {
      // the argument of type 's a b' in the Haskell version is implicit as 'this'
    def bimap[c, d](f :a=>c, g :b=>d) :s{type a=c; type b=d}
  } 

  trait Fix[s <: Bifunctor[s] with Fix[s,aa], aa] requires s extends Bifunctor[s] {
    type a=aa
    type b=this.type{type a=s; type b=a}
    
    def fold[fb](f :s{type a=Fix.this.a; type b=fb}=>fb) : fb = f(bimap(id, .fold(f)))
       
    //def map[mb](f :a=>mb) : Fix[s,mb] = bimap[mb, Fix[s, mb]](f, .map(f))
    //def map[mb](f :a=>mb) : Fix[s,mb] = fold[Fix[s,mb]]( .bimap[mb, Fix[s, mb]](f,id))
    // error: type mismatch;  found   : s{type a = mb; type b = Fix[s,mb]}
    //                 required: Fix[s,mb] 
  }
 
  //def unfold[s <: Bifunctor[s], ua, ub](f :ub => s{type a=ua; type b=ub})(x : ub) :Fix[s, ua] = 
  //  f(x).bimap[ua, Fix[s,ua]](id[ua], x :ub => unfold[s,ua,ub](f)(x))
  // error: type mismatch;  found   : s{type a = ua; type b = Fix[s,ua]}
  //                 required: Fix[s,ua]

I've been thinking some more about how to approximate your solution (which used recursive type synonyms). While reading an excellent explanation of recursive types by Robert Harper, I finally realised that Scala's implicit conversions come in handy here:

implicit def unroll[s<: Bifunctor[s],ua](v :Fix[s,ua]) :s{type a=ua; type b=Fix[s,ua]} = v.out
implicit def roll[s<: Bifunctor[s],ra](v :s{type a=ra; type b=Fix[s,ra]}) : Fix[s,ra] = Fix(v)

When necessary, the compiler inserts calls to these methods, which witness the isomorphism between the recursive type and its unrolling, thus making the code about as easy to read as your approach; here's a snippet (more code on my homepage):

case class Fix[s <: Bifunctor[s], fa](val out :s{type a=fa; type b=Fix[s,fa]}) { 
      def map[mb](f :fa=>mb) :Fix[s,mb] = bimap(f, .map(f))
}

Two caveats, though: (1) there's currently a small bug in the Scala compiler so that implicit conversions are not applied when the target of a member selection is this. (2) Sometimes the compiler can't infer the types for a method invocation, so you have to provide those explicitly... I don't know if this is a bug or a known limit to Scala's type inference (e.g. the bimap-call should read bimap[mb,Fix[s,mb]](f, .map(f))).

Using implicit coercion to simulate equirecursive typing. I hadn't considered that possibility before (probably because Haskell doesn't offer the ability to define implicit coercions).

I must take a look at Scala.