Hacker News Reader

> I'd say most of the time, you just failed to capture the commonalities. More specifically, you seek generality through exhaustiveness, when you should use genericness instead.

THIS is one of the most important things I've ever learned from programming Haskell[0]. The way to make things generic is to whittle away all of the sharp edges and implement them as compositions atop base patterns. Those base patterns arise out of polymorphism, not exhaustiveness.

You don't make lists generic by realizing that you need a list type to have all the properties of a string, a tree, a vector... You make it generic by realizing that much of its structure arises by forgetting what's inside.

[0] Which is not to say you can't learn it elsewhere, or that you cannot do it elsewhere. Instead, Haskell has the facility, the philosophy, and the community to do it really effectively all the time and so if you read Haskell code you'll be floored by some of the great examples possible there.

Fun fact: I have known this intuitively since forever, but only recently realized that when I say "generic", most programmers I know tend to hear "exhaustive", and recoil in horror; while I really meant "generic".

Now, I also know why I like parametric polymorphism, and dislike subclass polymorphism: the first is generic, while the second is exhaustive.

> Now, I also know why I like parametric polymorphism, and dislike subclass polymorphism: the first is generic, while the second is exhaustive.

I'm going to steal that. I love it.

What's the difference between "generic" and "exhaustive," and where can I read more about all this stuff?

Imagine you want to process a list of foobarbaz, where elements can be foos, bars, or bazes.

Exhaustion is when you write foo specific code, bar specific code, and baz specific code. Then your list-processing facility is general because it handles all the cases. A typical way to do that in practice is to use subtype polymorphism, with the class inheritance mechanism: have a foobarbaz interface, a foo class that implements it, a bar class that implements it, and a baz class that implements it. Each with their own code.

Genericness is when you ignore the foobarbaz specifics altogether: your code doesn't even mention the types. A typical way to do that in practice is to use parametric polymorphism (generics in Java, templates in C++). See C++'s Algorithm library for an example, or the standard Prelude from Haskell, or the OCaml standard library.

The gang of four book predates Java the language. FYI. The book's written in Smalltalk.

Now that is a surprise. Lemme check… https://en.wikipedia.org/wiki/Design_Patterns Indeed. Written in 1994, and includes examples in Smaltalk… and C++.

Now I know why it didn't rely on first class functions.

It wasn't written in Smaltalk. It was written in the intersection of Smaltalk and C++. Sounds like Java, even though it didn't exit yet. Come to think of it, I wonder if they didn't have hints about this upcoming language from Sun. Java came out in 1995, but was in the works since 1991…

So my point stands.

If it were really written in Smaltalk, it wouldn't have needed insanities such as the Visitor pattern to work around the lack of closures. It would have used Smaltalk Blocks directly.

Well, I'm glad you've concluded that you're still right.

Lose the sarcasm, please. If you still believe I'm wrong despite my documented arguments, I suggest you put forth documented counter-arguments. It will have two benefits:

1: You may convince me. I'm serious. I do not anticipate any strong counter arguments, but if they come, I will listen. (I did listen to your first argument. It troubled me, really, I was certain the book was written in Java. So I checked.)

2: You may show the other readers the error of my ways. Since my arguments are documented and relatively articulate, they will likely sway anyone who isn't committed to a particular position. You wouldn't want me to put false ideas in their heads.

The book really was written with Smalltalk in mind with the C++ examples added for marketing reasons. If you want to go argue with Ralph Johnson (aka the god of Smalltalk) about it, be my guest.

Actually, I'm starting to want to read this book, if only to see how far down the rabbit hole goes. Depending on what I find, I may want to demolish it. I don't care if the authors are gods, this glimpse of their work does not look good.

This interview with 3 of the gang of 4 (Vlissides unfortunately passed away a few years ago) might help you get it:

http://www.informit.com/articles/article.aspx?p=1404056

The visitor pattern is about doing different things to objects based on their class. What would make it redundant would be multi-methods, or pattern matching, not blocks. Smalltalk doesn't have a good alternative to the visitor pattern.

Okay, let's read https://en.wikipedia.org/wiki/Visitor_pattern

Oh, my. This is even worse than I had thought. The motivating section makes me want to grab my closure hammer, especially the "reuse of iteration code" motivation. I don't know how I would handle it of the top of my head, but the way the Wikipedia article present it feels wrong.

The Java example looks more explicit. Oh, crap. This is Bad, Wrong, Horrible design. Sure, now the compiler can help you not forget cases, but you're still on the wrong side of the Expression Problem: for every single subtype you add, you still need to add a case to each of your visitors.

Is this the kind of price one has to pay for class hierarchies?

Why are you talking about Java? You obviously don't know much about it. I don't even say this to defend Java, because I don't like it. But you're apparently just repeating secondhand information about it.

I wasn't referring to the Java code. I stopped at the UML diagram. It was horrible enough by itself. Just look at it: https://en.wikipedia.org/wiki/Visitor_pattern#Diagram

For each class, you basically need to write an "accept" method to call the visitor. Fine for now. But then, the visitor specializes depending on the type of the object! Couldn't we just inline the appropriate visit method directly at the call site? It would get rid of all the boilerplate introduced by the visitor pattern, without duplicating more code. It would still suck[1], but it would suck less.

[1]: https://news.ycombinator.com/item?id=7589623

It's just that you made a comment about design patterns being tailored for Java, then apparently later actually investigated the visitors example. You should do those things in the opposite order.

Not necessarily.

I've written about how "OO" as is commonly done in Java/C++ is a mistake: http://loup-vaillant.fr/articles/classes-suck I know of the closure/object duality, and have some understanding of the tradeoffs involed, here: http://loup-vaillant.fr/articles/classes-as-syntactic-sugar so my opinion isn't totally uninformed.

So why should I waste my time with yet another OO book? Plus, I know it from reputation, which told me closures greatly simplify or even eliminates many patterns in this book. Languages with a GC and no closures should not exist, and so should books who teach how to work around their absence.

But I have just learned some interesting things about this book right now. Like, it was written in Smaltalk primarily, and merely translated to C++. Before Java came out, no less. So maybe its use isn't limited to class based, single dispatch, statically typed languages that don't have closures nor generics (like the first versions of Java).

But if the book is limited to such braindead languages, then patterns are just a symptom of bad language design, and I'd like to demonstrate that.

But first, I'll read the book. At least, I will know my enemy. I'll probably learn a thing or two along the way. And who knows, maybe I will finally "get OO"?

If you read the "Details" section of that very Wikipedia article, you'll see why you can't just inline the accept method. You need both visit and accept in order to simulate double dispatch. accept performs one dispatch, visit performs the second. I suspect you could further generalize the pattern to k dispatches for some arbitrary but fixed value of k, though it would be very tedious.

Some algorithms, like collision detection for example, are readily described with double dispatch. So in a language that only offers single dispatch, like C++ or Java for example, the visitor pattern actually leads to more elegant code for such algorithms.

I'm not saying I particularly like this way of doing things (I'd rather the language had direct support for multiple dispatch, really), but it's certainly not a dumb way of doing things as you seem to think. In fact it's rather clever, and in some cases the best option.

> If you read the "Details" section […], you'll see why you can't just inline the accept method.

Oops.

Still, it makes me feel very uneasy: the accept methods dispatch over behaviours, and the visit methods dispatch over the object. This means highly non-local code.

Collision detection looks like a good example. Okay. Now even with multiple dispatch, I can't suffer the idea of having up to n² methods, for n different classes to dispatch over. In the case of collision detection, I would try very hard to have no more than 3 or 4 types of collision volumes. Just one if I can help it.

Personally, I'm not sure I like multiple dispatch at all. When you need it, you expose yourself to combinatorial explosion. It's only polynomial, but it still scales poorly.

For something like collision detection, you're always going to have n² cases to handle, even with something like pattern matching. The question then becomes whether you have n² methods or n² branches. There's a "combinatorial explosion" regardless; you just can't avoid it for some things. Then it's just a question of how you structure the code.

Consider the multimethod approach:

    (defgeneric collide? (a b))
    (defmethod collide? ((a bus) (b person)) ...)
    (defmethod collide? ((a person) (b bus)) ...)
    (defmethod collide? ((a bus) (b bus)) ...)
    (defmethod collide? ((a person) (b person)) ...)

Versus the pattern-matching approach (abusing CL's case expression for clarity):

    (defun collide? (a b)
      (case (list (type-of a) (type-of b))
        ((bus person) ...)
        ((person bus) ...)
        ((bus bus) ...)
        ((person person) ...)))

Beside potential performance implications of implementing one way or the other, you also have an open-closed conundrum. Multimethods leave the set of behaviors open, while the pattern-matching leaves it closed. That is, if a library wanted to define a new kind of collidable entity, it's trivial to add with a new library method. Not so easy with the pattern-matching approach. For some applications, this doesn't matter; for some it does.

You can avoid the n² problem if every object uses the same type of collision mesh (or bounding box, or bitmap, or whatever). Now the problem is to get from the object to the collision mesh, and that's O(n).

The bigger question is, is it practical at all for everyone to use the same type of collision object?

The answer to the bigger question is: not always. But let's assume that in our case, the answer is yes, and we can use a bounding box for everything. Let's also assume that when a collision is detected between two objects, the results of that collision vary depending on what those objects are. How do we handle that? Well, we're back at the n² problem again.

I once wrote a version of Asteroids in C++ in which every object had a particular bounding shape that was used for the detection. For the logic, I still had n² cases to determine the result of that collision. Looking back, I contend that it would have been cleaner to use the visitor pattern, since all the logic in my game was contained in various game objects except for the collision handling logic. [1]

It's good to be skeptical of design patterns. I've worked at several companies where liberal application of patterns really mucked up the code base. But in some cases, they really can be the best solution -- when used conservatively and carefully.

[1]: Looking back I also would have used an entity system rather than "classic" OOP, but that would not have solved the n² case dilemma.

for every single subtype you add, you still need to add a case to each of your visitors.

Why is this a problem? If you have N visitors, that's N different behaviors for every type, and you'll have to define those N behaviors for a new type somewhere. In this case, you do it on each Visitor (since each Visitor defines a behavior). Without using the Visitor pattern, you might put the behaviors somewhere else, but you would put them somewhere.

With M objects and N behaviours, it's okay to write M plus N pieces of code. With the Visitor pattern as I saw described, I have to write M times N pieces of code. It doesn't scale.

The obvious way out of this is intermediate representation. Typically, you would have the objects present themselves in the same way to any incoming behaviour. Now the behaviours don't have to know about each and every object. They just need to know about the intermediate representation. And that pattern is trivially solved with first class functions and parametric polymorphism.

With M objects and N behaviours, it's okay to write M plus N pieces of code. With the Visitor pattern as I saw described, I have to write M times N pieces of code.

It's actually the same amount of code in either case. With N different behaviors and M classes or types, you'll either implement the N behaviors as N methods on a class (and you do this for M classes - still M * N) or you'll have N visitors and add one method to each visitor to define the behaviors for a type (and you'll do this for M types as well - still M * N).

Consider the 2D-CAD example in the Wikipedia article: there are some M shapes and N different file formats to implement. If you add a new shape, you need define how it is represented in all N file formats. You can't get away with anything less than O(M * N) code. All the Visitor pattern does is change where you put it.

Typically, you would have the objects present themselves in the same way to any incoming behaviour. Now the behaviours don't have to know about each and every object.

If this is possible (which is very problem-dependent), then it's just as easily solved with inheritance. Since each subtype would have the same external interface (presenting themselves identically to incoming behaviors), the base class defines the external interface and subclasses override base class methods to define the implementation.

> It's actually the same amount of code in either case.

Which cases are you comparing? I was just saying M+N ≠ M×N, and that solutions that forces M×N are bogus.

> If this is possible (which is very problem-dependent), then it's just as easily solved with inheritance.

True. Then again, you don't need the visitor pattern.

I was just saying M+N ≠ M×N, and that solutions that forces M×N are bogus.

Agreed. I was clarifying that converting your code to use visitors does not force an order of magnitude increase in the amount of code. If you start out with O(M+N) without visitors, you'll still have O(M+N) code after converting to visitors. Although, visitors are generally better appreciated when managing O(M*N) code than when managing O(M+N) code.

Yep.

> Those specs suck. Whoever asked you this don't understand their own needs, or are struggling with a legacy behemoth that should eventually be replaced.

That may or may not be true, but presumably you're not suggesting that Haskell is unsuitable for writing software for users whose specs suck, or don't understand their needs?

No language is suitable for writing badly specked software. And whatever language you are using, you'll get into troubles if not technical people start to make too many requirements about the way you organize your code (but don't despair, the first such requirement will be to not use Haskell).

This doesn't really excuse the fact that Haskell is a harsh mistress that demands elegance. Many production languages are much more pragmatic about the quality of the spec, the quality of the developer, time constraints, and so on.

One of my favorite quotes about Haskell is "We cannot afford QA teams, so we use a sadistic compiler".

This doesn't really excuse the fact that Haskell is a harsh mistress that demands elegance.

I don't know how true that remains for expert Haskell programmers, but I agree that it's the way most introductory to intermediate material comes across.

In academia, you are often looking for the most elegant tool in clean situations.

In industry, you are often looking for the least clumsy tool in messy situations.

Perhaps Haskell is a good choice in one context but a poor choice in the other, at least for those first learning it.

"Badly specced" can be a number of things. Some domains have naturally well specified domains, others do not. The business rules of a company, a countries' tax code or building code usually is not an elegant business domain. It's usually a horrible mess of incremental decisions accumulated over decades. Often even logically incomplete or inconsistent.

Here is an excellent example of a design-by-committe specification for a domain that is incoherent, illogical and complex (Part of a modern day building code): http://www.fierabolzano.it/bauschau2005/congress/EN_1995-1-1...

Of course no implementation can be more elegant than the underlying business logic, the question is: how does the language help me write an implementation that is as nice as possible when the business domain is horrible?

I think Haskell code often looks beautiful but I attribute that not only to it being functional/pure/compact/elegant but also to the code usually being examples of "clean" domains (mathematics, etc.) being implemented in a way that is suited for demonstration, and the fact that it is usually written by excellent developers (who are the ones who tend to preach FP, for good reason).

What I'd like to see are some large-ish real world examples of FP architecture for horrible business problems, not nice ones.

The law is the prime example of horribly messy domains. Thankfully, the law is also human-made, which means it can be changed (at least in principle). We have wasted enough human-millenia already.

> The Gang of Four pattern you mention most likely work around weaknesses of Java.

Except it was written with Smalltalk and C++ in mind.

...which, for relevant purposes, have the same basic flaws as Java.