hayleigh's description of extensible expression language combination with cata - Elm Slack 2022-04-07

elm-extensible-expressions-with-cata

hayleigh  5 hours ago
so say your base expression language looks like this
module Expr.Base exposing (..)

type BaseF expr
  = Add expr expr
  | Sub expr expr
  | Val Float

map : (a -> b) -> BaseF a -> BaseF b
map f expr =
  case expr of
    Add lhs rhs -> Add (f lhs) (f rhs)
    Sub lhs rhs -> Sub (f lhs) (f rhs)
    Val n       -> Val n

eval : BaseF Float -> Float
eval expr =
  case expr of
    Add lhs rhs -> lhs + rhs
    Sub lhs rhs -> lhs - rhs
    Val n       -> n
and then we define an extension
module Expr.Ext exposing (..)

type ExtF expr expr
  = Mul expr expr
  | Div expr expr

map : (a -> b) -> ExtF a -> ExtF b
map f expr =
  case expr of
    Mul lhs rhs -> Mul (f lhs) (f rhs)
    Div lhs rhs -> Div (f lhs) (f rhs)

eval : ExtF Float -> Float
eval expr =
  case expr of
    Mul lhs rhs -> lhs * rhs
    Div lhs rhs -> lhs / rhso
note how neither the base language or the extension one know anything about each other. now we can put them together:
module Expr exposing (..)

import Expr.Base exposing (BaseF)
import Expr.Ext exposing (ExtF)

type Expr = Expr (ExprF Expr)

type ExprF expr
  = Base (BaseF expr)
  | Ext (ExtF expr)

map : (a -> b) -> ExprF a -> ExprF b
map f expr =
  case expr of
    Base base -> Base <| Expr.Base.map f base
    Ext  ext  -> Ext  <| Expr.Ext.map  f ext

cata : (ExprF Float -> a) -> Expr -> a
cata f (Expr expr) =
  expr |> map (cata f) |> f

eval : Expr -> Float
eval =
  cata <|
    \expr ->
      case expr of
        Base base -> Expr.Base.eval base
        Ext  ext  -> Expr.Ext.eval  ext
you can think of cata as a way of defining foldl for our expression type, that is cata allows us to fold an expression down into some other value, and we’ll use that to define eval!
Again note how neither the base or extension expression. languages need to know anything about each other for this to work. This is excellent because each extension to the expression language can be defined in isolation, as long as it adheres to the pattern shown above. There are two downsides:
You can’t extend it once you define the main Expr type, you’re essentially back to your initial problem. This leads to…
Requiring the consuming code to define the Expr type (so they can decide which extensions to include). Now this isn’t complicated, it is all boilerplate, but it is tedious.
:+1::+1::skin-tone-2:
2


hayleigh  5 hours ago
Here is an ellie implementing the above: https://ellie-app.com/h8PNpbqXqYka1 although in this examples I chose to had a “base” language and an “extension” one, you can take this idea to it’s logically conclusion and make every single AST node its own type:
type AddF expr = Add expr expr
type SubF expr = Sub expr expr
...
the idea is the same. Eventually you’d have
type Expr = Expr (ExprF Expr)
type ExprF expr
  = Add (AddF expr)
  | Sub (SubF expr)
  | ...