I think object algebras have huge potential to improve the way complex software is written but I’ve never seen them used in practice. I think one reason why is that the research paper which introduced them is pretty hard to read. This post is my attempt to change that.
I’ve been working on this post off and on for like two years so I’m really excited to share it with people. It is very long. There’s a lot of ground to cover.
This is a very common toy example we use in Haskell, though honestly this OOP version leaves a lot to be desired, comparatively
The issue is that it tries to shoehorn separation of data and functions on data into a paradigm that’s fundamentally about fusing those two things together.
Here’s the Haskell version. Note how much simpler it is because data and functions are separate:
data Expr = Lit Int | Add Expr Expr eval :: Expr -> Int eval expr = case expr of Lit n -> n Add a b -> eval a + eval b print :: Expr -> String print expr = case expr of Lit n -> show n Add a b -> "(" ++ print a ++ " + " ++ print b ++ ")"Typescript can do something similar:
type Expr = { kind: 'Lit', value: number } | { kind: 'Add', left: Expr, right: Expr } function eval(expr: Expr): number { switch(expr.kind){ case 'Lit': return expr.value; case 'Add': return eval(expr.left) + eval(expr.right); default: const _impossible: never = expr; return _impossible; } function print(expr: Expr): string { switch(expr.kind){ case 'Lit': return `${expr.value}`; case 'Add': return `(${print(expr.left)} + ${print(expr.right)})`; default: const _impossible: never = expr; return _impossible; }Both the OOP approach and Typescript itself struggle with additions to the algebra composed of different types, however. For example, imagine extending it to handle booleans as well, supporting equality operations. It’s difficult to make that well-typed using the techniques discussed thus far. In Haskell, we can handle that by making
Expra GADT, or Generalized Algebraic Data Type. That article actually already provides the code for this, so you can look there if you’re curious how it works.Yes, this pattern is covered in my post on algebraic data types (linked at the start of the object algebras post.) The problem you mention about adding new data variants is exactly what object algebras solves. With object algebras data and functions are only co-located at the smallest possible granularity, so the desired functions and the desired data types can be composed as needed.
Your post only showed adding functionality over the algebra, not new types on which the algebra operates (or “sorts”, as they are otherwise known). In other words, you can’t easily extend
Exprto support Boolean logic in addition to addition itself. For a concrete example, how could you represent ternary operators like in the expression2 + 2 == 4 ? 1 : 2, such that it’s well typed and will never result in an exception? With GADTs, this is very simple to do:data Expr a where Lit :: Int -> Expr Int Add :: Expr Int -> Expr Int -> Expr Int Eq :: Expr Int -> Expr Int -> Expr Bool If :: Expr Bool -> Expr Int -> Expr Int -> Expr Int eval :: Expr a -> a eval expr = case expr of Lit n -> n Add a b -> eval a + eval b Eq a b -> eval a == eval b If p a b -> if eval p then eval a else eval b -- >> eval example == 1 => true example :: Expr Int example = If ((Lit 2 `Add` Lit 2) `Eq` Lit 4) (Lit 1) (Lit 2)lemmy seems to have lost my response to this, so I’ll type it again and hope that it doesn’t show up twice
There’s three separate issues here:
-
The ability to express multi-sorted algebras
-
The ability to extend algebras with new sorts
-
The ability to extend a single sort of an algebra with new variants
For point 1, object algebras do support this even though I didn’t show it in the post:
interface ExprAlg<Num, Bool> { lit: (value: number) => Num; add: (left: Num, right: Num) => Num; eq: (left: Num, right: Num) => Bool; iff: (interrogee: Bool, then: Num, els: Num) => Num; } const evaluate: ExprAlg<number, boolean> = { lit: (value) => value, add: (left, right) => left + right, eq: (left, right) => left === right, iff: (interrogee, then, els) => interrogee ? then : els } function makeExample<Num, Bool>(alg: ExprAlg<Num, Bool>): Num { return alg.iff( alg.eq( alg.add(alg.lit(2), alg.lit(2)), alg.lit(4)), alg.lit(1), alg.lit(2)) } console.log(makeExample(evaluate)); // prints 1For point 2, you are correct that the original Java formulation of object algebras does not support data sort extensibility. I haven’t tried to see if TS’s more powerful generics change this or not.
For point 3, consider what happens if you want to add a new variant to the data type. In this case, add a
Multvariant for multiplication. With GADTs this is not possible without modifying or duplicating the existing evaluation code, but I can do it with object algebras:type ExtendedExprAlg<Num, Bool> = ExprAlg<Num, Bool> & { mult: (left: Num, right: Num) => Num; } const extendedEvaluate: ExtendedExprAlg<number, boolean> = Object.assign({}, evaluate, { mult: (left: number, right: number) => left * right }) function makeExtendedExample<Num, Bool>( alg: ExtendedExprAlg<Num, Bool>): Num { const one = alg.mult(alg.lit(1), alg.lit(1)); return alg.iff( alg.eq(one, makeExample(alg)), alg.lit(3), alg.mult(alg.lit(2), alg.lit(2)) ) } console.log(makeExtendedExample(extendedEvaluate)); // prints 3This is the point of object algebras. ADTs and GADTs can’t do this out of the box; this is the essence of the expression problem and is why more advanced techniques like final tagless encodings and datatypes a la carte exist.
-
This deserves an hour of reading. My first pass is a criticism too sadly. Addition is too trivial, and every example is pure - this needs a rubber meets the road example to really spell out the benefits.
Philip Wadler story for you though: he taught me first year at uni and his first lecture he rips open his shirt and proclaims himself “Lambda Man!” - Haskell was a fun first semester
deleted by creator
I should have marked mine more clearly as a “first pass” from the start.
Worked with too many hotshot folks to trust future/past humans quite that much.
Once in a while, I’ve even been that hotshot guy. Definitely not excluding my own “oh that was prod…” adventures when I worry about humans, didn’t mean to come off like I think I might have.
But interesting, and certainly worth kicking around.
I get the concern. I haven’t seen the pattern used in practice in an OO context, so I also can’t say for certain where this breaks down. Something to note, though, is that object algebras in an OOP context are equivalent to the final tagless pattern in an FP context, and it’s not uncommon for entire functional applications to be based around final tagless. This gives me some level of confidence that it would only take a reasonable amount of discipline to build a system based on object algebras.
That’s an understandable criticism. I do plan on writing a more involved example in the future, but this would be a two-hour-read if I had tried to include it. I’m hoping that introducing the basics on a very simple example will be a good stepping stone towards more involved ones.
In green fields projects, this makes a fair bit of sense at initial reading, tentatively.
But new code becomes old code, and then builds on the quality / discipline / cowboy status of the last person to touch the code, in a complex and interlocking way.
I can’t say I’d be excited to find a partially converted existing codebase of this. But in fairness, I’m on my couch on a Sunday and haven’t actually worked through your examples (or read the original paper). I see the benefit to having both types of extensibility, obviously. Just not sure it outweighs the real world risk once actual humans start getting involved.
I don’t know a single person who can’t say they’ve never taken a single “good enough” shortcut at work, ever, and it seems this only works (efficiently) if it’s properly and fully implemented.