[self post] Extensible TypeScript with Object Algebras

jnkrtech · 4 months ago

[self post] Extensible TypeScript with Object Algebras

expr · 4 months ago

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 Expr a 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.

jnkrtech · 4 months ago

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.

expr · 3 months ago

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 Expr to support Boolean logic in addition to addition itself. For a concrete example, how could you represent ternary operators like in the expression 2 + 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)

jnkrtech · 3 months ago

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 1

For 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 Mult variant 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 3

This 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.

[self post] Extensible TypeScript with Object Algebras

[self post] Extensible TypeScript with Object Algebras

Extensible TypeScript with Object Algebras · Programming should be enjoyable