Hacker News new | past | comments | ask | show | jobs | submit login

I've been watching some talks online recently by Rich Hickey of Clojure fame, and he's a very interesting and convincing speaker. He basically makes the same argument that Armstrong makes here.

I'm not clear, however, how the pro-FP, anti-OO crowd address the Law of Demeter, which is often summarized as "One dot: good. Two dots: bad." The canonical example where the Law of Demeter serves us well comes from some of the original Demeter papers, which I actually read a long time ago when they were current. This canonical example is that of an object to represent a book.

One of the initial selling points of OO was that if you encapsulate the representation of an object from its interface, this ends up giving you a lot more flexibility. For the case of representing a book, pre-Demeter, a typical OO organization would have been to provide a method to give you chapters of the book as Chapter objects, and from there you could get Section objects, from which you could get Paragraph objects, from which you could get Sentence objects, from which you could extract the words as strings.

The Demeter proponents correctly argued that this OO organization of the Book rather defeats the goal of encapsulation, since with this organization you cannot restructure the internals of the Book object without breaking the API. E.g., if you decide to insert Subsections between Sections and Paragraphs, your API for extracting all the sentences of a book will change, and consequently, much of the client code will have to change.

The Demeter folks argued that instead of having to explicitly navigate to sentences, you should just be able to call a method on the Book object directly to get all the sentences. Without special tools, however, this is hard for the implementers of Book, since now they have to write tons of little delegation methods. I take it that people who are serious about following the Law of Demeter do do this, however. In the original Demeter system, Demeter would do this automatically for you. The problem with the original Demeter system is that few people actually ever used it, and it was rather complicated for Demeter to provide this automatic navigation.

So, back to FP: Rich Hickey argues to forgo damned objects and to just let the data be data. So if I follow Hickey's advice, how am I supposed to represent a book? As a vector of vectors of vectors of vectors of strings? If so, then how do I prevent a change in the representation of the Book from breaking client code? If I had followed the Law of Demeter with OO, then everything would be golden.

Sure, with this naive FP approach, I could also provide a zillion functions to fetch different sub-structures out of the book. E.g., I could have a function to return all the sections in a specified chapter, and another to return all of the sentences in the book. This, however, would end up being little different from the OO approach following the Law of Demeter, with the further downside that if you change the representation of the book, you don't know that you haven't broken the client code, because you have no guarantee that the client code isn't accessing the representation directly.

Please advise.




You can certainly achieve this in Clojure using deftype/defrecord, with methods that operated on those types.

But I think the point he's making here is a good one. Why exactly ARE you modeling a book as a series of chapter, section, paragraph, sentence, word objects? Just because you can? Or because it's actually a useful API to developers (the latter seems somewhat doubtful).

It's very tempting when you're working with an OO system to actually try and model the data as it corresponds to the real world equivalent, but it's rarely a good idea. Design your code around the API you want other developers to use.

In the case of a book, it's unlikely every book will follow that rigid chapter / section / paragraph / sentence / format (what about a book that doesn't have chapters at all? Or has pictures? Or is stream of consciousness). You'll want a more flexible system - I'd imagine it would end up looking like some kind of markup representation. And no surprise, markup is best dealt with as a nested data structure (XML, JSON), not a rigid set of container classes. So even in this trivial example, a bunch of encapsulated classes aren't really an appropriate representation.

This is true more often than not in practice. Rather than building a rigid class hierarchy, having functions that operate on data (and frequently that data _is_ typed) often yields better results.


Caveat. I never saw any mathematical formalization for Law of Demeter. Contrast this with the Substitution Principle, which is directly defined in terms of logical implication.

With the regard of the example presented, there is at least a trivial solution. There is a BookApi which is concerned with providing Book operations, and there are the Book/Section/Paragraph data types. List<Sentence> getAllSentences(Book) is defined by the BookApi. Changing the data types doesn't affect any client of the BookApi, only the implementation of the BookApi.

Conversely, coupling the methods to the actual data types results in inflexible designs. Should a Book know how to display itself in a gui widget? Which widget library? Should a Book also know how to save itself in a database? Which database api?


So, basically what you are saying, as far as I can tell, is that there is absolutely no difference between the OO approach using the Law of Demeter and the FP approach. (Though with an FP approach, you are perhaps more likely to make things immutable, which is a good thing.)

If so, perhaps this isn't surprising, as Demeter was layered upon Scheme.

Regarding writing to databases or to screens, decent OO programmers do not put methods to do this sort of thing into the domain objects. For i/o to a database the typical OO approach is to use a separate DAO class, and for GUI i/o the typical OO approach is to use an MVC framework, or some such.

Also, I'm not sure why anyone would want a mathematical formulation for the Law of Demeter. I think that anyone would be hard pressed to formalize every aspect of good design, as what is a good design isn't a mathematical property, but more one of cognitive psychology and the art of engineering. The Demeter system did, however, automate implementation for the Law of Demeter based on specifications you would give it, so The Law of Demeter isn't just some touchy/feely thing either.


Since the answer to the rhetorical questions is a resounding no, there is very little meaningful behavior to be attached to the "domain objects". "Domain objects" do not obey the "Law of Demeter" and they are nothing but the data types of OCaml or Haskell. The other side of the coin are abstract apis, which are polymorphic collections of stateless functions, aka modules. Indeed, modern OO is functional programming in disguise.

Regarding Demeter, naming an anecdotically supported observation "Law" is a bit of a stretch ;)


> naming an anecdotically supported observation "Law" is a bit of a stretch ;)

Maybe, but it's a common thing to do. C.f., the Law of Thirds.


Which may be why almost everyone calls it the "rule of thirds". [1]

[1]: http://www.google.com/trends/?q=%22rule+of+thirds%22,+%22law...


With the FP approach you can just write "show book as a widget" function yourself, without the whole inheritance hodge-podge. In case of real libraries the change of data structure probably won't be a problem as author would probably supply a function Book -> (Title, Chapters, Sentences, Strings) which would be guaranteed not to change and discourage the use of actual constructors.


Have you ever tried to read any Demeterized code? It's an idea that needs to die.

If I see book.line(n) and I want to know how it counts footnotes, and Book::line is defined as this.sectionWithLine(n).line(n) and those are defined in terms of Chapter::line and Page::line I'm going to need notepaper. And as I'm flipping among five nearly-identical functions with the same name, I'm going to have a terrible time finding which one has the footnote logic in it.


> Have you ever tried to read any Demeterized code?

What are you suggesting as an alternative?

It should be noted that the original Demeter system would fetch sentences (or whatever) based on a description of the data structure that was provided by the implementer of the data structure alongside its implementation. In this system, you wouldn't have to examine code to answer your question, but you would have to be able to understand some perhaps complex computer-understandable description. That, of course, might be about as fun as reading an XML Schema. Also, since the real Demeter system never caught on, these days we have to do the computer's job manually, which is surely a chore.

Regarding many functions that all have the same name obfuscating things, there's nothing in the Law that requires that, of course, though I can see how it might sometimes happen in reality.


I think the obvious solution is to stop worrying about what's perfect on paper and instead approach things from two very simple questions:

1) What are my use cases? and

2) What should be abstracted in order to create the cleanest interfaces with the most predictable behavior?

3) What should be exposed to ensure that debugging is easiest? The answer here is simple, "everything."

I think if we focus on clean interfaces based on use cases, we get something better.

The problem with the book example is that a book is something that is very hard to optimize both for reading and composition at the same time. If I am writing a book, the functionality I need access to is very different than if I am reading it. For reading, it's probably sufficient to have some methods to access the table of contents, list of tables, list of figures, etc. and the index, and a single method: get_page(int) which returns a page of text, which can then be processed, and if sentences move on to the next page, we just fetch the next page and process it too. For writing, however, you are going to have trees connected to linked lists, and it will be very different. I may want to change a paragraph, or add a new one.

But a book is a bad example, because it is internally structured in the way we think of it in order to be functional. In other words, with a book, the internal structure is the user interface along with helpful guides like the ToC and index. A better approach would be to note that the actual structure of the ToC, LoT, LoF, etc. doesn't need to correspond to the actual paper and so the data structures underneath could be very different, but the overall programming interface would probably mirror the actual paper structure pretty closely.

Now, if you were representing a book binding process, or book repair process programmatically that might be more interesting.


I should have added, not only is it internally structured in order to provide a good user interface, but we've had hundreds of years of perfecting that user interface, so printing and book conventions are remarkably useful to the reader and ignoring them is always at one's own peril.


For a book, I would keep the text itself as something very simple, such as a big old list of lines. A chapter is a range of lines. A section is also a range of lines. Adding subsections is a matter of adding a field to Book and it is (surprise) a range of lines, too.

You could implement this as a byte offset if you wanted, but you get the idea. If the text of the book is data, the rest is metadata. IMO it should live with the data, preferably in as lightweight a fashion as possible. Adding more metadata is a matter of adding fields, but as long as you stick to a basic form of representation, you should be fine.

Your helper methods help connect interrelated pieces of data. If you want all the chapters in a set of pages, you check for which chapters either overlap or are a subset of the page range you got.

If you want to add footnotes to pages, for example, you might define a footnotes field. That field has the text of the footnote and the line that it points to, perhaps with an offset to denote specifically which word it wants. (Maybe this is an argument for using byte offsets in the first place.)

Is this roughly what you had in mind, or have I completely missed the mark?


> Is this roughly what you had in mind, or have I completely missed the mark?

Maybe, but I'm not sure. If you don't encapsulate the data behind an API, then I suspect that you will eventually be sorry. And if you do encapsulate the data behind an API, then you're doing OO.

You may be right that your design for the representation of the book may be better than the typical naive OO representation, but there's nothing that forces an internal OO representation to be naive, or for an FP one to be sophisticated.

I guess what I'm saying is that I still don't understand how the FP approach is supposed to be different from the OO approach using the Law of Demeter. With the law of Demeter, methods only return data, not other objects ("two dots: bad"), so it's not as object-filled as a more naive OO approach. And in a case such as your FP representation for a book, where the representation is bound to be rather complicated, it seems that you will surely want to encapsulate it, in which case, the FP approach has adopted some OO. I.e., the FP approach and the OO approach have met in the middle and have become the same.


Incidentally I'm about done watching one of Rich Hickey's talks about complexity, the one called Simple Made Easy. Thanks for the recommendation; it has given a me a lot to think about. Are there more, or was that the one you were referring to originally?

"You may be right that your design for the representation of the book may be better than the typical naive OO representation, but there's nothing that forces an internal OO representation to be naive, or for an FP one to be sophisticated."

Well, there is, in that OO is inherently more complicated, in the most trivial sense; compare an idiomatic implementation of storing, incrementing, and displaying an integer in Java versus C. At a minimum, for Java, you're going to want an object. For C, you neither need nor want any such thing; a function or two and an integer are sufficient.

If the only thing that exists is a bag of data and code which pulls out that data, you have a much simpler system. I don't think this is controversial; an object is the same thing, in essence, except that due to language implementations and semantics, there are additional layers of complexity that are inherent and inextricable. Hickey goes on about this better than I could, although one of my favorite recent discoveries from C++ is the explicit keyword. The point is that with purity and referential transparency, it is far far easier to reason about you program. Pure functions are orthogonal, no?

I have heard of the Law of Demeter, but in practice, I'm not sure I see it obeyed that often if ever. APIs tend to return objects, or assume you'll chain method calls, or what have you. It's a fact of life, at least in my experience with Android development as well as vanilla Java. Maybe there's some subtlety that I'm missing out on? Otherwise it seems like a dud, if only because nobody wants to maintain those niggling chains of accessor calls.

I think that's really the crux of the issue: culturally, OO tends to value taxonomy in the form of object hierarchies; polymorphism; inheritance; and the like. All of that adds complexity. No, there's no reason why OO has to rely on mutable state and hierarchies. But the conventional wisdom about best practices is a powerful influence. You could compare theoretical implementations, but honestly, taking a look around would probably give you a better idea of how this theoretical scenario is likely to play out. That's the basis for comparison, here: Hickey is contrasting a simple approach with software development as it happens now, typically, not as it might or ought to happen.

Also, for what it's worth, I don't think encapsulation is irretrievably the province of OO. APIs are not a concept over which OO has exclusive ownership, right? The idea that you might want to sequester state goes hand in hand with concepts of purity and referential transparency. Or the idea that you should use a function which implements an algorithm as an entry-point to a data structure rather than muck about in it yourself (think of a heap).


> Are there more, or was that the one you were referring to originally?

That's the one. Though there are two with that name, I believe. One for Strange Loop and one for a Ruby conference. The two talks are mostly the same, but it's worth watching both. Then watch all other talks by Rich Hickey too, as they are all excellent.

> At a minimum, for Java, you're going to want an object

Java, if you ask me is a degenerate case. It's a language that pushes consistency at all costs, in the face of any common sense. Most other OO languages don't pressure you into programming this way. I.e., they give you normal functions in addition to methods.

Though when programming in Java, I am personally not averse at all to just putting functions into an empty utility class that exists solely for holding nothing but static methods. Scala actively encourages doing this, as it provides for a type of object called a "package object" that exists for this particular purpose.

> I have heard of the Law of Demeter, but in practice, I'm not sure I see it obeyed that often if ever.

Maybe people in the trenches don't typically obey "best practices", but the OO best practices gurus all seem to push the Law of Demeter these days. I'm sure it's difficult to figure out how to do well. But then again, so is figuring out how to apply Rich Hickey's advice on simplicity!

> nobody wants to maintain those niggling chains of accessor calls.

Nobody wants to be locked into an inflexible API either, but I agree that people are lured by what is easy!

Hickey is contrasting a simple approach with software development as it happens now, typically, not as it might or ought to happen.

It would be interesting to know how what Hickey would do is different from what OO best practices gurus recommend. Indeed it's clear that in the real world, people don't often follow either advice.

> Also, for what it's worth, I don't think encapsulation is irretrievably the province of OO.

For the most part, it's usually considered to be. API's surely existed before OO, but they were typically for one program to talk to another, not for communication within a program. Before OO, different parts of programs typically revealed all their data structures, and you were allowed to go to town on them. Though, it's true that for certain things you probably weren't supposed to do that. E.g., as you said, on the malloc heap in C.

I believe that encapsulation as we know it today was invented by the CLU programming language. It was certainly the first language to enforce encapsulation. CLU isn't necessarily what we would consider an to be OO language today, as it didn't have inheritance, but it considered itself an OO language at the time.


Just because it is Functional Programming it does not mean to "throw away encapsulation". Most languages still allow you to limit the extent to which a piece of data is exposed. And that is needed for large systems - otherwise you will have to change many many functions as your data representation changes. This is also true of loose coupling. Seeking to modularize your code is always a good idea - but it is not impossible to achieve in non-OO languages. After all they also have module systems for exactly that.

The trick is to have a small set of functions which are very generic. And then stack these on top of each other as a mini-language from which you build up the access pattern you desire. After all it is a functional language, so these kinds of constructions should be fairly simple.

As for representation, consider that a book is represented as a tree: chapter -> section -> subsection -> paragraph -> body_text. But nobody said that this was the natural representation in a machine. You could have made a database table - CREATE TABLE book (id SERIAL, chapter INT, section INT, ..., body_text TEXT). Now access is by a small mini-language, namely SQL SELECT statements. Another way is to represent Chapter, Subsection, ... as dimensions in a vector space. The body text is then a point at a coordinate of Chapter x Section x Subsection. This has a KD-tree representation because it has neat spatiality for instance.

We could represent the book as a list: [(chapter section subsection ... body_text) ...]. A list has a formal derivative called a "zipper". This structure allows us to go "forward and back" through the paragraphs of the book - one paragraph at a time. This is the perfect representation for a screen reader. If we need to go larger strides, we can probably consider a zipper of a Rope-structure or a finger tree.

Finally, we could use a trick where the book is represented as a function. That is, we simply call book(3, 12, 32, 4) to get Chapter 3, Section 12, Subsection 32 paragraph 4.

What I really don't like about OO is when it is taken as the assumption that physical objects in our world has an isomorphic representation in the machine. This is nearly never the case. Good OO programmers naturally know when to break away from an isomorphic representation - but sadly this is not always what is taught in schools. You know, a Cat is an animal and so is a dog. Hence they are both subclasses of the animal class :)


> Just because it is Functional Programming it does not mean to "throw away encapsulation".

Surely not, as even Clojure has support for OO programming. But Rich Hickey says that 90% of the time that encapsulation is used by OO programmers, it shouldn't have been. Instead, they should have just used a map or a list, etc.

So, does something as complex as representing a book fall into the 90% case or the 10% case?

Or maybe Hickey is really just alluding to the Law of Demeter and saying that methods should return data and not objects. It might very well be that if the Law of Demeter were religiously followed in OO programming, that the use of objects would fall by 90%.


The ML family of languages have structures, signatures and functors for encapsulation. Yet, it has little to do with OO in the traditional Javaesque kind of sense. Encapsulation does not require an object to achieve. Hickey says OO a'la carte and splits up the conflated concepts.

The reason he says to use a map or a list is because of another conflation danger. If you have an opaque book - you have a book but not its underlying representation - then if you want to represent multiple these, you should make the container "exposed". Because that choice is the modular one. All the functions which operate on my container can now be used. For instance (MAP spellcheck books). But I can also easily do (PARALLEL-MAP spellcheck books) right? Or even (MAP-REDUCE spellcheck id books) if I have petabytes of books and a cluster supporting MAP-REDUCE. This is why templates or generics are so powerful. They expose this modular relation.

But encapsulating the list into a "books" class will mean we have to write lots of extra code for each of the above 3 variants. We naturally don't want to do that.


Even more - encapsulation is not always mean OOP.

Erlang have encapsulation more strong than in any OOP language - all you have is server process and messages thrown to it.


How is that not OO then? OO is not defined by Java. The first OO languages and systems were descended from Lisp or built within Lisp, a functional programming language.

OO without inheritance is still OO. OO with immutability is sill OO. Encapsulation is the heart of OO. Polymorphism is also quite important. Inheritance is a distant third property of OO, but it is one common aspect of OO that is highly over-used. Most OO "best practices" gurus discourage rampant use of inheritance these days and say to prefer composition.

Back to the whole point of this thread, Rich Hickey says specifically NOT to use encapsulation (90% of the time). That would then not be OO. No encapsulation, no OO.


This is a pointless argument, since both views are "correct". Even Joe Armstrong says that "You can take two views, you can say that either erlang isn't object oriented... [or] you can say its more object oriented than all the object oriented languages."

But I do not think it's very useful to say that Erlang is object oriented, since it will confuse a lot of people, since it is not anything like the other "object oriented languages".

http://www.infoq.com/interviews/Erlang-Joe-Armstrong http://www.infoq.com/interviews/johnson-armstrong-oop


>>But I do not think it's very useful to say that Erlang is object oriented, since it will confuse a lot of people

I find it useful to instill this kind of confusion in people around me.

"You talk about encapsulation? Look at erlang"

"Polymorphism? Haskel"

"OOP? Javascript, CLOS"

"Static/dynamic typing? Look here - your java code is in fact dynamic, if you're really want to taste real static - look at ML-family or something near"


The standard lisp approach is to define your API first, and write code the meets the API. You define your API in a manner that makes the solution to the problem you're trying to solve obvious. So behind this API, you can change your data representation however you please -- just don't break the API.

As for your specific question, which representation of a book is the simplest solution? That's the one you should be using. Hickey's talk on simplicity really does a good job of explaining this point.


The funny thing is that most of these APIs wind up with what's essentially a "this" pointer at the front of every argument list so you're really doing OO anyway.

I'd like to read a persuasive critique of OO but so far I haven't found one. Time objects are a really bad example because time calculations are exactly the kind of hairy mess you want to hide behind some kind of abstract API.


The funny thing is that most of these APIs wind up with what's essentially a "this" pointer at the front of every argument list so you're really doing OO anyway.

Do you have much experience with non-OO programming? Or even OOP, for that matter? How can one honestly believe that every instance of passing data into functions is automatically OOP? Did you even consider the fact that this has nothing to do with objects?

Time objects are a really bad example because time calculations are exactly the kind of hairy mess you want to hide behind some kind of abstract API.

You miss his point here. Time not being an object would not imply that it can't be abstracted into an API. Just see Clojure's clj-time library for an example.


I'm sure that GP is referring to point number 2 of the article -- which explicitly says that time should (or at least could) just be data with no associated methods.

I winced at the naïveté in that section myself. It sure seems like he's arguing that OO programmers muddy the waters when they make something as "simple" as time and dates into an object with methods for storage and retrieval.

http://infiniteundo.com/post/25326999628/falsehoods-programm...


Except you can have many "thises" in a single scope. In OOP you'll write a.b(), in FP you'll write b a or b(a). Having "this" pointer is not OOP.


What we do in LedgerSMB usually is write our API's first in SQL which is decidedly not OO.

Then we write objects then flexibly encapsulate that.

Then we write UI and automation logic around that.

Now, long-run we're trying to find better ways to encasulate the behavior inside SQL. I don't think we've settled on a method yet but may do so sometime between 1.5 and 2.0 (a year or three).


Would an API be defined as "A set of functions that define the available operations common to that set?" If so, would those functions then delegate to progressively more concrete functions that work against data structures to perform their duties? I suppose it's obvious where I'm going here. I don't see how this is any different from just saying the word "Object."

Don't get me wrong, I'm not trying to come off too sarcastic here. I'm actually quite interested in challenging the OO norm that is obviously too easily accepted right now.


Each Module defines an api that talks about N different ValueTypes. Saying the word Object limits the api to expose exactly one ValueType.


As to coming up with the "simplest" representation, that's almost certainly excellent advice whether doing OO or FP. It should be noted that Hickey has a rather specific notion of "simple" that may be rather different from more typical intuitions. This is why Hickey had to differentiate between "simple" and "easy", where "simple" means not intertwined with other things, NOT what seems like the least amount of work. The least amount of work is what is "easy", not what is "simple".

If one is encapsulating the representation behind an API, this simplicity principle is much less important for the representation than it would otherwise be, however, as any complexity of the representation is fire-walled at the API. And the Law of Demeter is a good principle for helping to keep an API "simple", as functions of the API that follow The Law of Demeter should return only data and not objects.

I'm still not sure how this API business meshes with Hickey's advice, however. He seems to be rather adamant that hiding data behind an API is the wrong thing 90% of the time. I have no feel, however, for knowing if something as complex as a book falls into the 90% case or the 10% case.


Rich Hickey specifically says that his approach makes you more readily adaptable to future requirement changes, rather than less adaptable, as an OO die-hard might claim. I'm not sure I understand how the "get it right to begin with" approach fits into the adaptabile-to-future-requirement-changes promise.

I see how following OO, as long as you also follow the Law of Demeter, could live up to its promise of helping you adapt to future requirement changes. It has that unfortunate cost, however of requiring you to sometimes write a zillion little delegation methods upfront, which could be quite a combinatorial chore if you don't have the Demeter system automating this for you.

Also, I'm pretty sure from listening to a number of Rich Hickey's talks, that he is saying very specifically NOT to hide your data behind an API. Encapsulating the data behind an API would just be the same as the OO approach for all intents and purposes. Hickey is saying to let the data be data. I.e., just data.


Instead of giving you an example that anybody actually uses, I'm going to tell you about a cool idea I've been reading about that hasn't gotten much actual use.

The basic idea is to use a generalization of pattern matching. Languages like ML and Haskell support pattern matching, but in rather limited ways. Crucially, patterns are not first-class citizens of the language. (For Haskell, at least, there are some libraries to remedy this, but I don't know how effective they are.)

So how can we generalize pattern matching to help you solve your book problem? Normal patterns allow you to match data types in the form C x₁ x₂... where C is some constructor and x₁ x₂... are either matchable symbols or arbitrary patterns. An example of a pattern would be Chapter (Cons (Section content) rest). We differentiate between the matchable symbols and the constructors on case: lowercase means matchable, uppercase means constructor. This is somewhat limited: you cannot easily write code that is generic over the constructor at the head of the pattern. You could write a function that counts the sections in a chapter, but you could not write a function that counts the sections in anything.

So let's relax the restriction that patterns have to be headed by a constructor. We can now have patterns in the form x y. These are static patterns: you can match data against them without evaluating the pattern. With this, we can imagine writing a function to count sections generically:

    count_sections x = 0 -- If this is some terminal, it cannot be a section
    count_sections (Section content) = 1 + count_sections content
    count_sections (x rest) = count_sections rest
This goes through the entire data type you passed in and counts all the sections it sees. It assumes sections can be nested. This will let you count the sections in a Book or a Chapter or a Series or whatever you want.

So, this is generic over the data you pass in. However, if you wanted a function to count Chapters or Sentences or what have you, you would be forced to write it. This calls for another extension to pattern matching: dynamic patterns. Patterns are now in the form x ŷ where x is a variable and ŷ is a matchable symbol. Constructors are still uppercase, so Section is a constructor and not a variable.

A variable in a pattern can be instantiated with another pattern. So now we can write a truly generic count function:

    count constructor (constructor) = 1
    count constructor (constructor x̂) = 1 + count x̂
    count _ (x̂ ŷ) = count ŷ
So now if you want to count chapters in your book, you would just invoke count Chapter book. If you want to count sections in your chapter? Easy: count Section chapter.

You can also use patterns and constructors for polymorphism by overloading functions on different constructors. One interesting idea is to allow adding cases to functions after their definition. This way you could have an existing toString function and then, when you've defined a book, add a new case to it:

    toString += | Book title content -> "Book: " ++ title 
This way you can have a toString function that works on any type of data.

All my examples are obviously in pseudocode. (And hey, it looks nothing like Python! The whole "runnable pseudocode mantra annoys me.) I haven't covered all the edge-cases, and I haven't even begun talking about a type system for this mess. Happily, there's somebody who has, and wrote a book about it (that's where I got all these ideas): Pattern Calculus by Barry Jay[1].

[1]: http://www.amazon.com/Pattern-Calculus-Computing-Functions-S...

I'm also not sure whether this is the best possible approach. However, I think it's certainly very neat. If you like this idea, the book is definitely worth a look.


I started reading this comment and immediately knew you were talking about Pattern Calculus. Awesome to see someone else interested in the idea.

I live a couple of blocks over from UTS and went to a programming language event there. I only found out about pattern calculus after talking to Barry Jay. Turns out UTS students have been working on an implementation, called Bondi:

http://bondi.it.uts.edu.au/

If you're interested in playing around, Eric Torreborre posted some of the UTS lab tutorials online and some of his solutions:

https://github.com/etorreborre/bondi-tutorial


Hmmm, this might be kind of similar to what the Demeter system actually did. With Demeter, you would provide some sort of machine readable descriptions for your data structures. Once you implemented this description, you could ask Demeter to fetch you all sections of a book, or all sentences of it, or what have you. If you were to then change the representation of the book, you would't have to change any of the client code--you'd only have to change the machine-readable description of the data structure. Then when client code asked Demeter to fetch all the sentences, everything would still work fine.

Maybe the best solution is to just resuscitate Demeter! Though apparently nobody actually used it either.


This is the first time I've encountered this and what you wrote packs a lot of ideas in a small space so forgive me if I have misunderstood.

What you write seems like an even more powerful version of the Active Patterns in F#, which are already really powerful. Active Patterns are the closest thing to First class patterns in a production language * .

Haskell has a similar thing in views. But I think another concept, unique to and playing better to its strengths, while attacking this level of problem are Generalized Algebraic Datatypes. I mentions GADTs because it deals specifically with "This is somewhat limited: you cannot easily write code that is generic over the constructor at the head of the pattern. " Like I said, I've never heard of the pattern calculus - is there any problem it solves that could not be solved with GADTs with a similar level of effort?

* certainly biased but I see active pattern use more than I see extractors or views


I'm afraid that I'm not too familiar with either active patterns or GADTs at the moment. However, given the understanding that I do have, I think they are both unrelated to the basic dynamic pattern matching that I was talking about.

As far as I can tell, active patterns only affect the constructor. They let a constructor like Even to run an arbitrary function when it's matched. This lets you customize what a constructor actually means, which seems very useful, but is orthogonal to dynamic patterns. Dynamic patterns affect the patterns and not the constructors, where a pattern is the expression that is actually matched. That is, given a function f (Foo a b) the pattern is Foo a b. Active patterns would let me customize how Foo works, but the full pattern (Foo a b) still looks and acts the same.

Given this meaning of "pattern", I think active patterns do not constitute first-class patterns. You can't take a pattern and pass it into a function or make up a pattern of variables that can be any pattern. With first-class patterns, you should be able to take the pattern (Foo a b) and pass it into a function as a pattern. So a function like

    match pattern (pattern x̂) = x
would make sense in a system with first-class patterns. Here, a pattern is an argument to a function and then used to match against the next argument. Hopefully this clarifies the particular thing that dynamic patterns add to the language.

GADTs are also unrelated. For one, GADTs only affect the type of a constructor and not its behavior. I did not talk about types in my post at all--everything I talked about would make sense in a dynamically typed language that had pattern matching. It just so happens that dynamically typed languages tend not to have pattern matching like this, so it's associated with statically typed languages.

Also, GADTs, like active patterns, only affect the constructor. They do not change the actual patterns used to match against values (except by restricting possible types of the matched values).

So really both active patterns and GADTs are somewhat orthogonal to dynamic patterns. When I said a code that is generic over the head of the pattern, I meant a function like:

    doFoo (a b) = b
where doFoo will match both Foo x and Bar x and Baz x and extract x in every case. This function is generic over the constructor in the sense that it matches regardless of what the constructor actually is--the constructor becomes just another matchable term.

This sort of function, which just uses static patterns, is already something that a GADT cannot do. Dynamic patterns are even more flexible. My match function above lets you take an arbitrary pattern like (Foo a b) and match (Foo a b x) against some value to get x. You're passing a pattern into a function which then uses that pattern to match against its next argument. This feature has nothing to do with the type of the constructor.

I hope this cleared things up for you. However, it's almost 4 in the morning and I'm not entirely coherent. If you're still confused, or if I made some glaring errors, feel free to email me about this when I'm more awake :P.


Excellent! Thank you, yes I am clearer, the concept is even more awesome than I thought .

>I think active patterns do not constitute first-class patterns.

I agree, but like I said, they are the closest thing in active use, they extend the type of structures one can deconstruct to encapsulated ones while being more flexible in implementation. They fall in the class of techniques which extend and make matching more flexible, other examples would be multimethods and predicate dispatch. So very much orthogonal to approaches in pattern calculi but I think in a subspace in terms of matching.

>GADTs are also unrelated. For one, GADTs only affect the type of a constructor

Yes they are unrelated that's why I focused on expressitivity, and you are right, I misconstrued what you meant by generalizes on constructors. But everything has a cost - runtime, learning, cognitive overhead - what I was curious of is: how much does the pattern calculus buy you? GADTs are another concept that allow one to elegantly tackle problems where it looks like the pattern calculus would help. I was just looking for an example where something like GADTs fumbles in comparison.

It's clearer to me now that the pattern calculus is definitely more flexible in terms of match semantics but I can't think of any situation in practice where this would give an added advantage.

Also, Is this typically done via term rewriting and is there anything on the decidability of this?


I think the main advantage is what I pointed out before--being able write functions that work on a wide variety of data types. I think my count example is something that could not be done with GADTS:

    count constructor (constructor) = 1
    count constructor (constructor x̂) = 1 + count x̂
    count _ (x̂ ŷ) = count ŷ
Keep in mind that this is pseudocode, so some of the semantics may not be perfect. The basic idea is this: the first argument count takes is a pattern, like a constructor. The second argument is matched against the dynamic pattern (constructor x̂). This pattern has one matchable variable x̂ and one free variable constructor. This free variable is bound in the previous argument to the function.

So this lets you use the count function to count any sort of sub-pattern in its argument. Let's imagine you have some hierarchy like (Book (Cons (Chapter stuff) (Cons (Chapter stuff) nil))). You could use the count function to count the number of chapters like this:

    count Chapter book
Basically, you're parametrizing your count function on the pattern you want to count. So count can work on any data type and any pattern. If you wanted to count sections, you could:

    count Section book
Now lets pretend that sections have numbers. Instead of (Section content) we have (Section number content). You can now count something like how many sections have the number 5:

    count (Section 5) book
I think you could generalize this even further, but it would be more complicated.

I'm not sure how this is typically implemented, largely because it typically isn't :P. I think there's essentially one implementation in a language called bondi[1] but I don't know how it is implemented.

[1]: http://bondi.it.uts.edu.au/

As for decidability, I'm not sure. The entire pattern calculus--that is, an extension of lambda calculus supporting this sort of pattern matching--is Turing-complete. I don't know if just the pattern matching part is undecidable though.

As I said in my original post, there is a nice book on this called Pattern Calculus. I think you can read it online[2], which is nice because it turns out to be fairly expensive on Amazon.

[2]: http://www.springerlink.com/content/978-3-540-89184-0


Thanks for an excellent write up to the idea. That was very clear.

I am very intrigued and was looking at purchasing that book to learn more - but then I saw the price. I'll have to scrounge a copy from a library somewhere. I thought on demand printing was going to reduce the costs of books on the long tail!


Oh yeah, it's more expensive than I thought :/. Happily, I was lent it by a friend.

You might have some luck getting it as an ebook from the library. My university's library seems to only have it as an "electronic resource", and it's a pretty big library.

I like the book, but a good part of it is just background. It goes through a bunch of variations on the lambda calculus in building up to the "pattern calculus". If you're already familiar with the basics, you might be better off just reading some papers on it. (Hopefully there are some you can read for free, but I'm not sure.)


Oh hey, it seems that you can also read it online: http://www.springerlink.com/content/978-3-540-89184-0.

I'm not sure if there are any restrictions on this, and the format is annoying, but it might be worth looking into.


TBH, looks like the only hard bit here is fiting static typing into your system. I believe the dynamic languages with pattern matching facilities (erlang, echeme) should already be able to pass any symbol they want for the constructor name.


Yes, they can use any symbol. But I don't think they can match against a constructor (that is, write a pattern like (x y) where x can match any constructor).

Also, I don't think they can have dynamic patterns. That is, you can't take part of a pattern, pass it into another pattern and use the resulting combination of patterns to match against some value.

These two things are the interesting generalization of pattern matching that I was talking about.


Relevant: http://www.daimi.au.dk/~madst/tool/papers/expression.txt

The salient paragraph: "Whether a language can solve the Expression Problem is a salient indicator of its capacity for expression. One can think of cases as rows and functions as columns in a table. In a functional language, the rows are fixed (cases in a datatype declaration) but it is easy to add new columns (functions). In an object-oriented language, the columns are fixed (methods in a class declaration) but it is easy to add new rows (subclasses). We want to make it easy to add either rows or columns."


Isn't the whole question what you need to do to get a nice, clean interface?

Also wouldn't it be true that the ideal data structure of a book would depend on whether you were optimizing it for reading or for writing?

Wouldn't it be better to just say we should follow whatever creates nice, clean interfaces but allows the developer access to internals as needed for debugging purposes? The problem I have with the principle of least knowledge (the Law of Demeter) is that it is used to make objects opaque. I think that's what causes the biggest backlash.

I mean the whole point is to create clean interfaces, right?

The law of least knowledge is interesting though, provided it is not an excuse for opacity. Why should my program have to know beforehand what parameters a stored procedure takes? Why not discover them at run-time and map in properties or other variables?


Umm... Pseudo-code follows

     module Book = struct 
         type t = { sections: Section.t list; ... }
         ....
         get_paragraphs t = map (fun s -> Section.get_paragraphs s) t.sections  
         .....
     end
So it is not that hard to have both FP and DL


DOM is a tree. Tree traversal, filter, fold, query, search .. are well known.


So, there have been a few replies to this post, but as far as I can tell, you're asking about maintaining invariants ("not breaking the structure"), which nobody has addressed so far. Let's have a look how this is handled in different types of languages (^ means I have extensive experience with these, so I might have some of those without a ^ wrong - some languages are also tough to categorise, but bear with me):

1. statically-typed OOP: e.g. C#^, Java^, C++^, F#, OCaml, Scala, etc.; specifying the type of a field is a kind of invariant assertion (e.g. name must be a string not a number), and depending on the expressiveness of the type system, these static assertions can become arbitrarily specific. You might still need to do runtime checks in the mutating methods if certain invariants (e.g. length > 0) can't be expressed statically in the language. If internal state can be set to mutable objects (e.g. mutable strings) from outside, you can still break the invariants by mutating the objects after they've been checked. Some type systems (such as Java's generic types) are even notoriously weak, requiring extra care.

2. dynamically-typed OOP: e.g. JavaScript^, Objective-C^(see note), Ruby, Python, Io, etc.; generally, no invariants are maintained by default, and everything happens at runtime. So unless you specifically check invariants in the object's methods, invariants can often easily be broken by passing in data with unexpected structure. It is often trivial to pass in objects that satisfy the invariants, then change them in arbitrary ways to violate them afterwards. Encapsulation is frequently also easy to break by extending classes or prototypes.

3. statically-typed functional or procedural: C^, Haskell, ML, ATS, etc.; just as with the statically-typed OOPLs, you can explicitly encode many invariants in the type system. You can't set a number-typed field in a record to a string value. To maintain "softer" invariants, you will typically have runtime checks in the mutating functions. The languages with a pure functional bent typically encourage concentrating mutable state into a select few places in the code. Those places can be gatekeepers for enforcing invariants.

4. dynamically-typed functional or procedural: Lisps such as Clojure^, Scheme and CL^, Erlang, etc.; Where mutable state is allowed, or the default it's just as much a free-for-all as the dynamic OOPLs. You need to make your mutating functions aware of all your invariants, or they're trivially easy to break. In the pure-functional or immutable-by-default languages, again, since mutation is concentrated to a few hotspots (transactions in Clojure, messages in Erlang), those hotspots can easily be made to refuse performing mutations that break invariants.

Comparing 1 with 2, and 3 with 4 respectively, it's pretty obvious that the static languages make it easier to maintain invariants. The more expressive the type system, the more you can nail down the permitted structure. The culmination of this are theorem-proving languages. Interestingly, those tend to be functional.

So, if you compare 1 and 3, encapsulation buys you some safety in some cases, but realistically, it's just as easy to make a system that permits violation of invariants as it is in functional languages. Some of the more pure functional languages replace encapsulation with constrained mutability to help maintain invariants.

Comparing 2 and 4, I'd argue the functional languages actually do a better job helping you maintain invariants. The malleability of objects in (2) languages makes them hard nail down. Immutability on the other hand at least provides stability in time, if not in structure.

Note that I'm only evaluating the ability to maintain invariants here, not trying to come up with an overall judgement on languages. In some situations, maintaining invariants is very, very useful. In others, you don't really care that much.

(note on Objective-C): while you declare fields and variables with a specific static type, any object-typed field can point to an object of any run-time type. So the static types are mostly just annotations and affect ARC semantics, they're not actually enforced or safe, it basically relies on duck typing; Key-Value Observing in particular makes some pretty deep changes to the run-time types of objects, which wouldn't be possible in e.g. Java. Unlike some of the other dynamic languages, the non-object C types and mostly-fixed memory layout of objects give some level of structural safety. Still, there's nothing stopping you from creating a number class that returns YES for isKindOfClass:[NSString class], thus making it straightforward to fool most invariant checks.


Hmmmm, well I wasn't asking about invariants in the way that this term is typically used. I was asking about adapability to future changes. The lure of encapsulation has been that it places a firewall (i.e., the "interface" or "signature") between your representation for some information and the client code that needs access to this information so that you are free to change the representation without changing the client code. It is true that having an unvarying interface is a form of invariant. The problem is that adapting to future needs may involve varying this invariant.

Rich Hickey claims that 90% of the time, encapsulation has the opposite of its desired effect, however, due, in part, to breaking the client's ability to use generic functions on the encapsulated data.

I know that I have personally seen quite a bit of OO code that did not live up to the promise of adapability, and so I would like to know more precisely what the alternate approach that Rich Hickey (and I presume other FP advocates) proposes is, and how it would address the issue of adaptability with examples that bear on real-world situations.

Many responses here have been, You can do encapsulation in FP languages. Sure you can, but that's not the alternate approach! That's the OO appraoch! I know that you can take an OO appraoch in functional programming languages, just as you can take a functional approach in OO programming languages, but Hickey and the OP specifically say that encapulation is extremely over-used, and to think twice and then think twice again before doing it.

The talks I have seen by Rich Hickey are inspiring, but they demand a follow-up talk (or maybe book) that provides the gory details, rather than just more potentially dubious promises.


In most of your statically-typed OOP languages, a type declaration really is just an assertion like "the value bound to 'foo' is always a number". This falls far short of asserting that it has the intended properties. For example, "is a number" is miles away from "is the largest prime number less than n."

For most interesting programs, it is simply not enough to have something which is a number. So you must use some supplementary mechanism to verify all the interesting properties. In practice the supplementary mechanism is not as awkward as writing extended type theory proofs in your programs. Now if this supplementary mechanism is good enough to depend on for all the interesting correctness checks, why isn't it good enough for the basic stuff as well?

If you do make the type system expressive enough to verify everything, it is Turing complete, and many assertions are only verified by calculating them in the type system. But if you write a correct implementation in your Turing-complete type system, it is at least as easy to write a correct implementation in the ordinary way. So why not just write the same code twice, and raise an exception if a result does not get a quorum?

This might be a valid strategy for some cases. But in most cases, some kinds of errors are just much more important to cover than others.

Static vs. dynamic typing is not the issue. The first issue is what kind of system you have for annotating code with appropriate assertions - easier is better, assuming that more assertions are always better.

The second issue is how much of this annotation is mandatory. Push it to the limit and you get a "bondage and discipline" language. Pair it with a type system that is less than extraordinary and you spend a significant share of your time wrestling an awkward type system.

Some people seem to enjoy this activity. But unless you do most of your coding under the influence of heavy sedatives, the odds are that the majority of your errors are not simply passing the wrong primitive type. And unless something is really wrong with you, most of your errors are not due to your inability to put an unbreakable padlock on your own code to limit your own intentional malice. So it is certainly possible to emphasize these cases.

But that should be based on some understanding of costs. If a given class of error is infrequent and low-cost, there should be a burden to justify spending 50% more time always handling that class of error.

If the language understands those costs better than the human then that could be helpful (particularly applicable to DSLs). But if it does not then it is better for the human to be able to manage this for themselves.

The real argument seems to be about which classes of assertions should be mandatory, not anything about the internal type accounting. Seems to me that this should be a decision specific to the purpose. If you are teaching programming your requirements might be different from if you are writing missile guidance systems. Moreover, different people might have different tastes!

So I am getting pretty tired of the facile suggestion that static typing (in particular, as implemented in mainstream blub languages) is invariably safer and that this makes it an obvious choice. The only variable at hand is NOT how much you care about maintaining invariants. It is really not that simple. It is also very significant what kinds of invariants you mean to maintain and what amount of cost you are willing to absorb to maintain them.




Applications are open for YC Summer 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: