Hacker News Reader

Comment by captainmuon | Hacker News Reader

At some point I realized I don't really need OOP itself, but I like a couple of bits it provides. Mostly:

- The syntax. I like to be able to say thing.doSomething(). It doesn't always make sense, but sometimes subject-verb syntax is more natural than a function call.

- Polymorphic dispatch (is that the term?) to replace if blocks. Instead of `if (thing is Car) thing.drive() else if (thing is Boat) thing.swim()` its just thing.move(). Pattern matching in functional languages solves this in a different way.

- Interfaces are nice.

I guess I could be happy in a language that just has structs and functions, and some help in form of pattern matching, multimethods and so on.

View on HN

Exactly.

As in any situation, to understand what someone is saying, you have to know who they are talking to.

People who hate OO always refer to overly bloated systems that treat OO as a philosophical foundation, something to be religiously adhered to. I'm sure those systems exist and I'm sure that they're horrible. But, y'know, it's just awfully nice to have an easy way to define structures and functions that operate on them, and the ability to use some structures interchangeably with other, related ones.

Objects or Haskell-like records, I'm happy with either. I like multiple inheritance but mixins are pretty neat too. Encapsulation is a good thing, but I could probably learn to live with any kind of decent modularity and separation of concerns. Et cetera.

Monads, modules, and type classes (the bare essentials) make me never want to go back to Object Oriented Programming. That's not to mention all of the really clean and elegant software now blossoming in the Haskell community (Lens, Applicatives, Monoids, GADTS, pipes, etc...)

So far, it seems that a well-designed OO language can get you closer to the best of both worlds than if you start from ML-style functional languages.

Consider that C# let's you have all three of your essentials:

It doesn't have higher-kinded types, but it does have monad comprehensions (LINQ + SelectMany)… the special syntax is nice but not necessary.

It has type classes in the form of implicit conversions.

It has modules in the form of static classes.

C# even lets you do Smalltalk-style OO without too much fuss.

The biggest problem with C# and pethaps OO in general is the lack of intellectual curiosity.

"It has type classes in the form of implicit conversions."

Could you expand on this?

Agreed. What I see as the core principles of OO (ad-hoc polymorphic dispatch and abstract data types) are present, useful and important in the FP world too. OO helped to bring attention to these ideas even if it didn't capture them in their purest and most general form. So I think we should be careful not the throw the baby out with the bathwater when criticising OO.

> Pattern matching in functional languages solves this [polymorphic dispatch] in a different way.

Pattern-matching doesn't give you late binding / ad-hoc polymorphism though, so while it's useful to replace static if statements or case statements, it's not a full replacement for OO's polymorphic dispatch. For that you need things like typeclasses in Haskell or multimethods in lisps.

Wadler's famous expression problem is quite relevant here: http://homepages.inf.ed.ac.uk/wadler/papers/expression/expre...

Logically, closed extension and open extension are different things. OO conflates them together for no reason other than having the polymorphic dispatch hammer. FP equivalents for polymorphic dispatch are pattern matching for closed extension and plain old first class functions for open extension.

> I guess I could be happy in a language that just has structs and functions, and some help in form of pattern matching, multimethods and so on.

So pretty much Rust you mean?

Good points.

The D language has a way of providing your first point without resorting to objects. Basically, the compiler just transforms a statement like `str.length()` into `length(str)`.

The other two seem harder to do in a simple way, but I'm sure someone has come up with something.

Also: polymorphic dispatch is faster with OO (which is what Rust/Servo people have been figuring out recently).

What does 'faster with OO' mean? Is there some implementation detail that is tied to, or heavily associated with, OO?

I assume it's based on (this is a bit hand wavy) the fact that in an OO language, calling the method merely needs to resolve the address space of the method. With pattern matching, you first have to perform the pattern match to figure out what instruction to execute, and then that resolves to an address.

That is, because your data and function are bundled together, having the data means you also know what function to call. Decoupling them, as in a functional paradigm, and passing the data into a pattern match, you have to perform some logic upon the data to figure out what function to apply to it.

But, a series of pattern matching expressions can compile down to a bunch of sealed/final classes that descend from a common base class. In that case, it would still end up using a vtable[1]. I think this is how it works in F# and Scala.

[1] I think that the JITs for the CLR and JVM can do better than vtables in the cases of sealed/final classes.

I am sure it doesn't work with way in either scala or F#. You can use classes to represent structure, but the matching is still extrinsic and can't use a table given the flexibility of both languages (you don't just match on class).

Just curious… why not? Isn't a class definition just a type constructor? For instance, if I have a class, Foo, with three types of fields: int, bool, and string, isn't that the same as:

    Foo of int * bool * string

I don't have a full PC handy, but, while learning F# a few years ago, I remember using Reflector to analyze an assembly generated by FSC.exe and the pattern match turned into a class hierarchy.

It may not work for all kinds of pattern matching, but that seems like the most straightforward way of handling sum types. What am I missing?

I doubt that was what was going on, but I can't find any documentation right now on how F# optimizes case matches. If it was doing that, it would have to apply those classes to all instances of the patterns, which seems unlikely in the face of separate compilation as "Foo of int * bool * string" could be constructed in a far away place. Well, if Foo was a local type that wouldn't escape, perhaps they could optimize it in the module, but it still seems unlikely.

OO languages have trouble optimizing constructs such as interfaces (and other forms of multiple inheritance) because the v-table is no longer very linear. Now throw in arbitrary predicates and you are pretty much back to linear search. Probably the state of the art can be found in GHC, but even they probably fall back to linear in a lot of cases.

Looks like you're correct; I just examined some F# code in LINQPad 4, and the IL has a bunch of `isinst` instructions to check the type at runtime, and no `callvirts` to the one pattern matching expression that I created.

https://gist.github.com/noblethrasher/af1b382fa6e0423bf8bd

Method dispatch using a vtable (a pointer, embedded in the object, pointing to a record of methods) is way faster than practically any other form of dynamic dispatch (except calls of known functions, of course). To support it, you pretty much need some form of single inheritance/subtyping (C++ does support multiple inheritance, but it significantly complicates the implementation). Rust's single-dispatch type-classes and Go's interfaces are dispatched in a similar way, but the record of functions is passed along the pointer to object as a "fat pointer". Servo people figured out that that is too wasteful/slow compared to C++-style vtable approach.

Yes. If you can generate code on the fly [1], you can handle a subset of cases very efficiently.

[1]: JIT. Just in case some people confuse concepts, I'm not talking about JVM, virtual machines and such. Just plain runtime machine language generation.

The problem with JIT is that it's not very simple. Sure, you can write your own single-purpose runtime-code-generating routine. But the beauty of OO is that it's widely applicable. If you want to achieve comparable speeds with JIT, you pretty much need some sort of a virtual machine; in particular, simple method-at-a-time JITs are not very efficient; you need some sort of measuring or tracing, so that you know what code to compile and how to optimize it.

Sure high performance generic JITs are not simple.

NOTE: Following is meant for dynamically dispatched lightweight methods, like those that just read (or compare) or store (or modify) some simple field value or do other simple operations where dispatch and call frame setup costs dominate. In inner loops which are executed enough many times that the codegen overhead is less.

The rationale is that branches are very expensive on modern CPUs, especially indirect subroutine (= method or function) calls. Consistently 14-20 clock cycles lost in addition to whatever time call frame setup takes, pushing and popping registers from stack. If inner loop cost is otherwise just a cycle or two and the dispatched method is trivial, it's easy to see how branch mispredict and call setup costs can dominate. In some cases some unrolling and prefetching could be done in addition.

In this case I envision routines that fuse (inline) dynamically dispatched (function pointer, message passing, pattern recognition) method inside a loop. A compiler could generate the rules and runtime system can do the actual composition. The method would then be dynamically inlined within the loop. No call, no function pointer call (=vtable), no full pattern recognition, no message dispatch, etc. Just fused, inlined code.

Pattern match can't be completely resolved early? Just generate code inside the loop that does the rest of the work with tests and branches. Try the most likely case always first (may require some profiling). Same with other dynamic dispatch.

Many cases, but known exponential distribution of probabilities? Inline some most likely cases, dynamically dispatch the rest. Like before, most likely first and some profiling may be required.

This way very expensive (data dependent) indirect function call is avoided. Call frame setup and teardown is avoided. The savings can be an order of magnitude for short dispatched methods.

Definitely no complete virtual machine needed.

Note: Edited multiple times.

Hm... not sure if I agree (if I understand this correctly).

If in the inner loop, the same method is called (of the same class), this means that the target of the indirect function call is always the same, and I assume that the CPU can predict that. If not, the compiler can hoist the lookup out of the loop. In certain languages, e.g. in Objective C (where lookups are dynamic, and much more expensive than vtable approach), it's a common programming pattern to manually hoist the lookup out of the loop, get the method descriptor (i.e. the jump target) and call the descriptor in the loop, without going through the lookup again.

If the inner loop loops over objects of different class (i.e. you're looping over an array of objects, each can be a different sub-class, and you're calling a virtual method), I don't think there is any way to improve vtable based approach.

Well, last I checked, the cost for an indirect function call for simple operations was about 5-10x compared to inlining. Each function call constitutes of at least two branches - the call and return. Caller needs to preserve any registers that may be altered by the callee according to ABI conventions. Same for callee.

That is for correctly branch predicted calls.

Far worse for mispredicted calls.

> If the inner loop loops over objects of different class (i.e. you're looping over an array of objects, each can be a different sub-class, and you're calling a virtual method), I don't think there is any way to improve vtable based approach.

Say 90% of the objects are of certain same type and the code generator knows that. Codegen puts the test for this case as first one and inlines the code directly in the loop body. Then you can at least have those 5-10x savings in 90% of cases and have branch mispredicts for the rest of the time. That can still be a significant saving.

Not really. At best, dynamic dispatch might be faster with inheritance, but even that's kind of a stretch. Most of the slowness with using trait objects in Rust has little to do with the dispatch itself, but with casting between the types being relatively inefficient and/or unsafe (for a whole host of reasons which also affect other parts of the language).

In any case, dynamic dispatch, polymorphic or not, is considerably slower than static polymorphic dispatch, which Rust excels at. Servo's biggest performance wins over Gecko (outside of pervasive parallelism) have come by greatly reducing dynamic dispatch.

But, how often is it that dynamic dispatch can be optimized into static dispatch? I imagine it probably cannot be done with most of DOM handling... Isn't Rust's static polymorphic dispatch more-or-less equivalent to what you can do in C++ with templates?

For a long time there were Servo devs pushing for Rust to feature struct inheritance in order to safely and efficiently implement the DOM. Various proposals were written and prototypes implemented, but they all received criticism from the community (often of the form "this seems like a feature that solves a problem that only Servo will ever have") and no single proposal was a clear winner over the others. Today the Servo devs hack around the issue via `unsafe` blocks and transmuting things willy-nilly, but they're still dissatisfied with it.

I expect the issue to be revisited post-1.0. In the meantime, if you'd like to familiarize yourself with some of the proposals, here's a recent-ish summary and discussion: http://discuss.rust-lang.org/t/summary-of-efficient-inherita...

Right... I'm partially familiar with the development, but AFAIK, the basic goals are basically thin pointers and cheap dynamic dispatch using v-tables, not elimination of dynamic dispatch in favor of static dispatch.

My goal was to emphasize that you are correct that not all useful instances of dynamic dispatch can be reduced to static dispatch. With regard to the DOM specifically, however, there is some concern that the structure itself was designed and standardized such that it can only be implemented efficiently by assuming some sort of inheritance scheme, effectively baking the typical OO approach into the web standard. Opponents of inheritance being added to Rust have claimed that this is a unique case, and that such a feature would not pull its weight in any non-DOM scenarios (or worse, that it would be redundant with Rust's trait system and that you would fall into C++'s trap of nobody agreeing on which subsets of the language to use). Given the nebulousness of the proposals in this space, I have no dog in this fight at the moment.

My other goal was to show that Rust gives you enough tools to manually emulate an efficient inheritance-style dynamic dispatch scheme, even if it can't fully prove that your implementation is safe.

> Polymorphic dispatch (is that the term?) to replace if blocks.

It looks like you're talking about Predicate Dispatch. http://c2.com/cgi-bin/wiki?PredicateDispatching

Polymorphic dispatch is the specific reason for polymorphism in Object-Oriented Programming. It is more generically known as "dynamic dispatch": http://en.wikipedia.org/wiki/Dynamic_dispatch

You'll encounter the term in Bertrand Meyer's Object-Oriented Software Construction for example: http://www.goodreads.com/book/show/946106.Object_Oriented_So...

Dynamic dispatch is a special case of predicate dispatch. In particular, captainmuon pointed out that:

>Pattern matching in functional languages solves this in a different way.

captainmuon wanted a more flexible way of dispatching on types similar to what can be done with Pattern matching (which is also a special case of predicate dispatch).

In the post I linked to above this example is given:

Basically, instead of basing the dispatch on an "is_a" check, you check whether a general predicate is valid on the argument. So, in imaginary syntax instead of writing

  int foo( int a, int b):
  if a > 0 
	return a
  else
	return b-a

you'd write:

  int foo ( gt_zero? a, int b): return a
  int foo ( int a, int b): return b

I think you'd be quite happy in Rust, if you substitute trait methods for multimethods too.

Regarding your second point, what would be the functional equivalent?

Infix notation in Haskell is close, except that most of the time if verb syntax is convenient you're expecting side-effects.

He means pattern matching functions, which are idiomatic in Erlang but "dirty" in Haskell (where you would want to solve it better with a type class, or something else more general).

Erlang

    myfun({duck, "My Duck's Name"}) ->
        dosomething;
    myfun({dog,  "My Dog's Name"})  ->
        dosomething;
    myfun({cat,  "My Cat's Name"})  ->
        dosomething.

Erlang also has arity matching (this function is different than the one above it):

    myfun({cat,  "My Cat's Name"}, cage) ->
        dosomething.

Case statements are one way of doing that but those are considered a messy style in Erlang because they end up nesting so deeply - keeping it all out in small little functions and using pattern and arity matching is the "right" way.

You can do the same (except for arity matching) in Haskell with function arg pattern matching and Haskell also has some very nice projection tools for it too:

Haskell

    newtype Name = Name { unwrapName :: String }
    data Animal = Cat | Dog | Duck deriving (Eq, Show, Ord)

    myfun :: Maybe Animal -> Name -> String
    myfun (Just a) (unwrapName -> name) = (show a) ++ "'s name is: " ++ name
    myfun Nothing _                     = "No animal given!"

    > let n = Name "Fido"
    > myfun (Maybe Cat) n
    > "Cat's name is: Fido"
    >
    > myfun Nothing n
    > "No animal given!"

There are many problems with that function and I could probably eliminate the multiple function clauses and reduce it to one clause by getting rid of the pattern matching and using the maybe function:

    myfun :: Maybe Animal -> Name -> String
    myfun a (unwrapName -> n) = maybe default formatAnimal a
      where
        default = "No animal given!"
        formatAnimal t = printf "%s's name is: %s" (show t) n

That would be the more idiomatic way I would do it - pattern matching isn't "bad" in Haskell and you'll see it used quite often in utilities and libraries. It's considered good form to move stuff like that into a utility and give it a clear name (like the maybe function above that takes our formatAnimal function) then use that in your application code so it becomes obvious what's going on.

Pattern matching, deeply nested ifs and cases, etc... are somewhat hard to parse for the eye.

Just getting into Erlang right now, this is very helpful.

What is concept is the:

    newtype Name = Name { unwrapName :: String }
   (unwrapName -> name)

I'm not familiar with this, are you pattern matching on a function type?

It's the View Patterns extension: https://ghc.haskell.org/trac/ghc/wiki/ViewPatterns

You would pass in a function or datatype containing a function, which is exactly what the OO code does. No language features beyond first class functions necessary.

I was thinking of something like in F# (disclaimer: I've never used it and copied this from MSDN):

    type Shape =
    | Rectangle of height : float * width : float
    | Circle of radius : float

    let matchShape shape =
        match shape with
        | Rectangle(height = h) -> printfn "Rectangle with length %f" h
        | Circle(r) -> printfn "Circle with radius %f" r

Admittedly, this is not too far from a simple `if`, but I believe the language ensures that you handle all cases.

The difference to OOP is that the code is in one place, with the function, instead of distributed, with all objects. It makes it easier to add functions, but harder to add new types. Often, this is the better option, but if you are writing truely extensible code (a library that gets passed custom objects, or an application with add-ins) then you want to go the OOP way.

Reply on news.ycombinator.com