Codata in action, or how to connect FP and OOP | Hacker News Reader

Codata in action, or how to connect FP and OOP

javiercasas.com

100 pointssiraben54 comments

This paper on "Object Algebras": https://www.cs.utexas.edu/~wcook/Drafts/2012/ecoop2012.pdf

is a great example of using ideas from functional programming and category theory to improve on the visitor pattern, such that the expresson problem can be solved.

The value of such mathematics is that it enables us to formalise some of these patterns and generalise them.

> such that the expresson problem can be solved.

I'll add this paper to my reading list (because this is very much something I'm interested in), but in the meantime could you explain what you mean by "solving" the expression problem?

My understanding has been that EP is more of a lens through which to evaluate the usefulness of solutions along the objects-or-functions spectrum, rather than an actual problem to be solved in a traditional sense. Does the paper you linked design a system in which the full breadth of that spectrum is made expressible with no concessions?

The "expression problem" from Wikipedia (quoting Phil Wadler):

"The expression problem is a new name for an old problem. The goal is to define a datatype by cases, where one can add new cases to the datatype and new functions over the datatype, without recompiling existing code, and while retaining static type safety (e.g., no casts)."

With a sufficiently expressive language, the expression problem can be solved, sometimes in multiple ways. However, the solutions often involve boilerplate, trickery or advanced type system features. A proposed solution to the expression problem may be impractical, but that is subjective and really a separate discussion.

I guess you could view the problem as a sort of lens with which to evaluate a language. E.g. Can this language solve the expression problem and what does the best solution look like?

This this just different parlance to describe type constructors or am I missing something?

Oh true! I've definitely read that definition before but I guess I just internalized it with a lossy interpretation. :) Thanks for reminding me what it was really about!

> Codata looks a lot like objects and methods, where the codata value is the object, and the eliminators are the methods. ... the usual Functional Programmer has been an Object Oriented Programmer before. Because of this, he is likely to know codatafrom OO, and now is starting to understand data from FP

To me Python, Java, C++ are about encapsulation of imperative effects, but article is not about that kind of OOP

I think article is talking about v.f() "eliminator" vs f(v) "constructor" and that objects and closures are equivalent, but I am missing the deep insight beyond that. I don't understand how this helps with the expression problem (lets me not recompile my code to add new match cases to add additional data constructors)

Functions (or closures) are the prototypical codata... a co-inductive codata can be presented as a function space from an inductive datatype into some other type. It has a coinduction principle, derived from the induction principle of the parameter type. Traditional imperative code can be represented through the use of a free monad over a functor representing some command language, and the free monad is a codata as well.

"Category Theory is a branch of Mathematics mainly used by haskellers to annoy everyone else." :)

he heheh, I guess that's is a good an application as anything else.

Last month there was a conference on applied category theory https://act2020.mit.edu and as part of it there were some excellent introductory tutorials, which I highly recommend for anyone interested in CT: https://www.youtube.com/playlist?list=PLCOXjXDLt3pYPE63bVbsV...

It's the first time I watch lectures on CT and I actually understand something ;)

Here is the article mentioned in the blog post (Open Access):

[ Codata in Action ] https://link.springer.com/chapter/10.1007/978-3-030-17184-1_...

Wow that whole issue is packed with interesting topics.

" (...) - In an OO language, you can add a new case by creating another subclass and implementing the methods. But, if you want to add a new function to a datatype, you have to add it to the superclass and implement it on all the existing subclasses, which means modifying a lot of files and recompiling most of the program.

- In a FP language you can add a new function to an existing datatype just by adding a function. But, if you want to add a new case, you have to add the constructor and modify all the functions that use the datatype, which means modifying a lot of files and recompiling most of the program.

(...)"

...and by using multiple dispatch (as in Julia) you can do both. And it just works. True code reuse. Why did it take us so long to recognise this?

Common Lisp Object System had multiple dispatch for ages. Some other religions do not like it.

A subtlety we've discovered through success and growth of Julia is that even if your language has some solution to the expression problem, if it's has non-zero cost and isn't the default then people won't actually use it, which undermines much of the benefit. Systems like CLOS, Clojure and even R, which have multimethods but where they're opt-in and use slow hash-based implementations, don't in practice see most of the benefits that we've seen in Julia from multiple dispatch in terms of code reuse and composability. Another way to say this is that if multiple dispatch is just a feature that you reach for when you need to do something fancy, then it looks like just another feature; when it's ubiquitous it becomes transformative.

I don't think multiple dispatch fixes this problem in any way.

The idea here is that you can have an opaque interface. Then, adding new implementations of that interface is very easy. But, if you want to extend the interface, you need to modify all of the existing implementations. Multiple dispatch suffers of this problem just as much as single dispatch.

In the other case, you have a transparent interface - anyone can build code based on your data type. But, if you add more cases to your data type, anyone who had functionality built on it needs to take into account the new cases.

I think that this is in inherently an unavoidable problem. You can of course expose both kinds of constructs in your language, but you can't make interface implementation easily modifiable, and you can't make sum types easily extensible. The programmer ultimately has to choose the one that they believe will best capture the domain and its probable evolution.

What multiple dispatch can do is take some cases where sum types are obviously preferable to single dispatch (operations on related objects) and apply the interface abstraction to those cases as well (without reaching for horrible solutions like the visitor pattern).

Edit: thinking a bit more about the article, what they are showing is that you can essentially use the visitor pattern (and multiple dispatch) to implement GADTs instead of using them for regular multiple dispatch with inheritance. Basically, you can use them bring completely disparate types under the same umbrella, just like a GADT. I'm not sure that this still allows subtyping of that GADT as if it were a regular class.

> I'm not sure that this still allows subtyping of that GADT as if it were a regular class.

It does, more or less, since any subtype will have to implement the "accept" method for the visitor, which has been defined to only 'accept' the values that can be represented by the GADT. Any subtype will need to define how its possible values map to that of the supertype.

Some Rust libraries use a trick to make sum types extensible without introducing breaking changes when a new invariant is added. There is a private/undocumented invariant in the type so every pattern match over the type must have a default/catch-all/wildcard branch (e.g. it is not possible to do an exhaustive match by naming all existing variants). By having a default branch, the match is always exhaustive and there will be no error if a new variant is added. For fields in a sum type something similar can be done: an undocumented, hidden field that cannot be used when the variant is destructed. Therefore it can be only partially destructed and in this case it doesn't matter how many other fields there are in the type variant.

Here is an example: https://github.com/rust-lang/regex/blob/master/regex-syntax/...

Forcing a default case is a big step back towards dynamic typing.

“Hey - we have a solution to your type problem; we just disabled type checking. Genious”

There is no need to modify existing implementations when extending an interface using multiple dispatch.

You would need to add the required implementations, but there's really no way around that since the logic has to go somewhere.

And as soon as you start actually dispatching on multiple arguments, using sum types to solve the same prolem quickly turns into spaghetti.

> There is no need to modify existing implementations when extending an interface using multiple dispatch.

Sure there is. If I have a function that takes a Foo and a Bar, and it calls a generic method on them, the generic method must have methods that cover the real subtypes of Foo and Bar. If someone had created subtypes of Foo and Bar and defined methods on all the generic methods that they knew about, and now you create a new generic method, you have absolutely broken the interface just as much as adding a new method to Iterable in Java.

It must have enough methods to get the behavior you want, that doesn't always mean all subtypes.

Assuming you're running a version of Java that supports default implementations, which may often be used to avoid breaking the interface.

Sum types are a different story, as you would have to dive into existing code.

> Why did it take us so long to recognise this?

It didn't take us long. Schemers did multiple dispatch at least 40 years ago. SICP explains how to do it.

(Arguably, both R and Julia are Lisp dialects under the hood, just disguised behind a more arcane syntax. Which goes to show that 'practioners' take Lisp seriously exactly as long as they don't know it's Lisp.)

Too many programmers (in my opinion) give up far too early due to surface level syntactical differences.

I have a friend who is like this, looked at some Rust code, saw closures with bars instead of parentheses and practically disregarded it on the spot. Took a lot of convincing that they wouldn’t notice after 15 minutes of actually using the language, and what do you know, I was right.

Any OOP with inheritance does multiple dispatch. Java, C++ vitual functions, python via ducktyping.

The article's concern is real but overstated in my opinion. When adding a new function in a hierarchy you'll either have a good default or you'll be implementing via type matching branches or 10 implementations in each type behind multiple dispatch.

The difference, to me, is minimal.

> Any OOP with inheritance does multiple dispatch. Java, C++ vitual functions, python via ducktyping.

Java, Python and C++ require Visitor machinery that you ahev to write, for each case, to implement multiple dispatch (and Visitor only works for double dispatch, if you want more than 2 arguments you need even more boilerplate). Julia and CLOS essentially have that machinery built in.

In case this is not clear, multiple dispatch refers to choosing which method implementation to call based on the specific runtime subtypes of all function arguments, not just the runtime type of `this` (which is all that Java, C++, and even Python can dispatch based on). It's basically like applying C++ function overloading rules at runtime.

> The article's concern is real but overstated in my opinion. When adding a new function in a hierarchy you'll either have a good default or you'll be implementing via type matching branches or 10 implementations in each type behind multiple dispatch.

That's assuming you can modify all existing implementations. If you can't (e.g. if you wanted to modify Iterable to add a new method) then the solution is just.. don't do that. Note that the article also doesn't offer a solution - they're just showing that multiple dispatch can be used to implement a different construct with different limitations (GADTs).

> Java, Python and C++ require Visitor machinery that you ahev to write, for each case, to implement multiple dispatch (and Visitor only works for double dispatch, if you want more than 2 arguments you need even more boilerplate). Julia and CLOS essentially have that machinery built in.

we're in 2020

     using value = std::variant<int, float, string>;
     void foo(value a, value b, value c) {
       struct {
          void operator(int, float, string) { }
          void operator(float, int, string) { }
          void operator(float, string, int) { }
          ///... etc... 
       } visitor;

       std::visit(visitor, a, b, c);
     }

works fine (and has worked fine since a long time with either boost.variant or in C++11 with eggs.variant, etc...)

Well, you can write Fortran in any language.

It's far from the same thing though, less convenient and less flexible.

Multiple dispatch doesn't require a centralized declaration of the possible types and allows putting implementations in different files.

Sure, it's 2020 and you have less boilerplate to write. It's still a little more than Julia or CL. Also, Java doesn't have anything similar in the std lib as far as I know.

More importantly, this is not as powerful as true multiple dispatch like in CLOS. There is no way to call other methods, there is no way to specialize partially (e.g. combine the variant with subtypes, and define methods only for some combinations of subtypes and super types on the parameters, and allow the implementation to choose the most specific one).

Edit: to add a few more details on my second point. CLOS (and I assume Julia too) allows you to call 'parent' implementations from a child implementation, similar to calling base type methods in virtual dispatch - you can call the next-most-specific method that would have matched the params, which you can't with the visitor. Also, say I have a generic function F(Foo, Bar). I could define methods for F(FooSubtype1, Bar) and F(Foo, BarSubtype1), and then call F(FooSubtype1() , BarSubtypeOfSubtype1() ) and have the right implementation get called (F(Foo, BarSubtype1)).

> Any OOP with inheritance does multiple dispatch. Java, C++ vitual functions

This is incorrect. C++ and Java are typical examples of languages that lack multiple dispatch, but are able to emulate it using the visitor pattern, as tsimionescu already mentioned.

https://en.wikipedia.org/wiki/Multiple_dispatch#Emulating_mu...

Ah, yea. I was confusing dynamic dispatch for multiple dispatch.

My bad!

Solving the expression problem requires maintaining static type safety. AFAIK Julia doesn’t do this because it’s dynamically typed.

People using Julia are quite happy how it alleviates the expression problem compared to languages they used before. Your argument, if I get it right, that Julia can't solve the expression problem because "the expression problem requires maintaining static type safety" reminds of the "Bumblebees can't fly" fable.

Most people using language X are quite happy how X does things compared to languages they used before. That's why they use the language X. That's also the reason why I consider this type of argument unhelpful.

No, not "most people" and not "happy how X does things" but specifically people who have thought about the expression problem's opinion about how Julia alleviates the expression problem compared to other languages they know.

Well, the expression problem is a clearly formulated question: how can we have three desirable things at the same time (no need to modify existing code, no need for code repetition and no need for runtime type errors [1])? See also the project management triangle: if you need something fast, good and cheap, then fast, good and expensive won't be a satisfactory answer, no matter how many millionaires are satisfied with the latter.

[1] https://link.springer.com/chapter/10.1007/978-3-540-24851-4_...

Honestly, if you want to discuss the progress made on the expression problem by a dynamical language whose power and extensibility partly comes from a collection of informal, consensus based interfaces you have to start from a different theory.

I don't think you can classify Julia like this.

It's kind of both.

Julia has types on bindings, in that sense it is statically typed.

“Julia is squarely in the dynamic camp” - Stefan Karpinski, Julia co-creator

https://stackoverflow.com/a/28096079

Well, that's like...his perspective.

It's a spectrum, not either or.

Julia and Common Lisp are somewhere in the middle.

...but you've ommited what I meant "(...) Unlike many dynamic languages, however, Julia has a fairly sophisticated language for talking about types, and you can annotate expressions with types. (...)"

Also other answers have some good information, ie:

" (...) It can also be useful to indicate the argument types to restrict the kind of parameters passed when calling. Our function header for floating point numbers would then look as function mult(x::Float64, y::Float64). When we call this function with mult(5, 6), we receive an error, ERROR: 'mult' has no method matching mult(::Int64, ::Int64 ), proving that Julia is indeed a strongly typed language. It does not accept integer parameters for the floating point arguments. (...) "

...in other words saying that "Julia is dynamic langauge, full stop." doesn't answer the question fully as for many readers it implies "weak typing", however it's dynamic, but strongly-typed, with state of art optimisations available as in statically typed languages, with proper multiple dispatch on all arguments (not single/this dispatch as in ie. java) etc.

It is definatelly worth playing with the language for people who hesiate on learning it - Julia provides some very interesting features not seen anywhere else.

Relevant presentation by one of the creators of Julia: https://www.youtube.com/watch?v=kc9HwsxE1OY

While we're on this subject, if we were to keep extending the syntax, is this what introProduct would have to look like?

        data Coproduct a b where
            InjL :: a -> Coproduct a b
            InjR :: b -> Coproduct a b

        elimCoproduct :: (a -> c) -> (b -> c) -> Coproduct a b -> c
        elimCoproduct f g (InjL x) = f x
        elimCoproduct f g (InjR y) = g y

        codata Product a b where
            ProjL :: Product a b -> a
            ProjR :: Product a b -> b

        introProduct :: (c -> a) -> (c -> b) -> c -> Product a b
        ProjL (introProduct f g z) = f z
        ProjR (introProduct f g z) = g z

Exactly! Maybe you've seen them before but what you just wrote are so-called "copatterns". See:

https://www.cs.mcgill.ca/~bpientka/papers/unnesting-copatter...

https://doi.org/10.1017/S0956796819000182

https://agda.readthedocs.io/en/latest/language/copatterns.ht...

Agda even has extra sugar on top for postfix projectors: you could write `myPair .ProjL` (as expression and as copattern). Syntax for pattern-matching anonymous function crucially uses that (yup, we have multi-clause anonymous functions!). You'd write:

  introProduct f g z .ProjL = f z
  introProduct f g z .ProjR = g z

  introProduct = λ { f g z .ProjL → f z
                   ; f g z .ProjR → g z }

Note that most languages already have that "codata" thing but it's usually called "record" or "struct".

I only found Setzers slides on this yesterday after trying to figure this out as I haven't been keeping up on Agda. So this is basically "copattern" matching on record projections. Records/structs are then the dual of variants/emums where we name and type the the destructors instead of the constructors. Thank you for confirming it. Agda's syntax then is meant to mimick descendants of C a little bit with that dot.

I'm still fuzzy but it seems like this can be directly translated into an underlying term rewriting system and would just work almost unmodified and all we've done is opened a second route for type checking terms based on orthogonal conditions? I'll have a look at the nested copatters paper as that probably answers my question. Thank for the resources. They seem much clearer than my search results. I wonder why people don't start explaining codata with records instead of coNats and coLists. The latter was confusing.

For a more concrete example, look at my nearly 5 year old post to Haskell reddit for embedding/faking copatterns in Haskell https://www.reddit.com/r/haskell/comments/4aju8f/simple_exam...

Was based off working to understand agdas notion of copatterns plus wanting to understand how to best mode protocols.

Def the case that copatterns capture the spirit and essence of oop done right. And with immutable or linear logic flavor codata, it becomes possible to also do stronger polymorphic updates than you can traditionally do with oop. Also you can nicely model type state varying apis for a single object

Edit : I also 2-3 years ago did a related live coding lecture which is related and some might Like https://github.com/cartazio/symmetric-monoidal/blob/master/s...

> This is no different to how car and cdr blow up in flames when you pass as parameter an empty list.

Depends on the Lisp in question, I guess. I don't know how it is in Scheme, but in both Common Lisp and Emacs Lisp CAR and CDR have well-defined behavior when used on an empty list: they return NIL, which in both Lisps is equivalent to an empty list.

Freely accessible paper cited in the OP: https://www.microsoft.com/en-us/research/uploads/prod/2020/0...

Cool :)

Sometimes seeing the same concept from different perspectives makes it easier to understand. For a scala treatment of the same topic see

https://underscore.io/blog/posts/2017/06/02/uniting-church-a...

Also in Scala; an interesting solution to the expression problem:

https://i.cs.hku.hk/~bruno/papers/Modularity2016.pdf

Its a paper, but its very light on dense academic prose and very heavy on copy pastable code :)

So if I have a Java value object, data is the constructors and codata is the getters ("eliminators")?

Aren’t typeclasses just a better version of codata?

I know people who are members of CODATA [1], didn't know they were working on this kind of thing. Maybe people could search for previous uses when they are picking a name for a concept, I think there are websites that let you do that /s.

[1] https://en.wikipedia.org/wiki/Committee_on_Data_for_Science_...

It's a polymorphic name.

Category theory, which is where the convention of using a "co-" prefix to refer to the "arrow-flipped" dual of a category comes from, predates CODATA by nearly twenty years. Maybe the CODATA folks shouldn't have presumed that they were the category-theoretic dual of data?

Reply on news.ycombinator.com