LEVIATHAN v962456e · 962456eee1

Standard Library

namespace expr

The expression-reification tree: runtime, walkable descriptions of lambda bodies.

since 0.1.0-alpha.1linuxwindowswasm

Overview

When a lambda literal is passed where an expr::Expr<F> is expected, the compiler keeps the lambda as an ordinary closure and also builds a tree of expr::Node values that mirrors its body, so library code can read the expression instead of only calling it. The node classes are plain data: Field, Lit, Bind, Bin, Un, Call and Assign, all derived from Node. Behaviour lives in the code that walks the tree, usually with a match.

Description

The expr namespace contains the classes that make up a reified lambda. Every node class derives from the empty base class expr::Node. They are reference classes that hold data only; their sole members are fields and a constructor. All behavior lives in the code that walks the tree, normally a match over the node's class.

class fields meaning
expr::Field Array<string> path a member chain rooted at a lambda parameter: u.name is ["name"], u.address.city is ["address", "city"]
expr::Lit string | int | float | bool | None v a literal; an enum member is its integer value
expr::Bind int slot a captured value, by index into the binds array
expr::Bin string op, Node l, Node r a binary operation; op is the operator as written
expr::Un string op, Node e "!" or "-" applied to e
expr::Call string name, Node recv, Array<Node> args a call of one of the allowed methods on recv
expr::Assign Field target, Node value u.field = value, the "set" shape

expr::Expr<F> ties the representations together:

member meaning
F fn the lambda as a closure
expr::Node tree the root of the tree
Array<string | int | float | bool | None> binds the captured values, in slot order
int siteId the site number of the lambda

The classes can be constructed by hand, which is useful for building a tree in a test, but the compiler builds every tree that comes from a lambda.

Building and walking a tree by hand

string show(expr::Node n) {
    match (n) {
        expr::Bin => {
            expr::Bin b = n;
            return "(${show(b.l)} ${b.op} ${show(b.r)})";
        }
        expr::Field => {
            string p = n.path.joinToString(".");
            return p;
        }
        expr::Bind => { return "$${n.slot}"; }
        else => { return "?"; }
    }
}

expr::Node tree = expr::Bin("&&",
    expr::Bin(">", expr::Field(["age"]), expr::Bind(0)),
    expr::Field(["active"]));
console.writeln(show(tree));
Run it ▶
((age > $0) && active)

Examples

The interpreter below evaluates the tree of a reified lambda against real objects. The path of a Field is looked up by field, a Bind reads the binds array, and the operators are handled by evalNode itself. The same lambda is then called as a closure, and the two answers agree. A consumer that translates the tree to SQL or another language is structured the same way, with a match over the node classes.

A tree interpreter

class User {
    string name;
    int age;
    bool active;
    new User(string n, int a, bool act) { name = n; age = a; active = act; }
}

string | int | float | bool | None field(User u, Array<string> path) {
    if (path[0] == "name") { return u.name; }
    if (path[0] == "age") { return u.age; }
    return u.active;
}

bool truth(string | int | float | bool | None v) {
    match (v) {
        bool => { return v; }
        else => { return false; }
    }
}

string text(string | int | float | bool | None v) {
    match (v) {
        string => { return v; }
        else => { return ""; }
    }
}

int num(string | int | float | bool | None v) {
    match (v) {
        int => { return v; }
        else => { return 0; }
    }
}

string | int | float | bool | None evalNode(expr::Node n, User u, Array<string | int | float | bool | None> binds) {
    match (n) {
        expr::Field => { return field(u, n.path); }
        expr::Lit => { return n.v; }
        expr::Bind => { return binds[n.slot]; }
        expr::Un => {
            expr::Un un = n;
            return !truth(evalNode(un.e, u, binds));
        }
        expr::Call => {
            expr::Call c = n;
            string s = text(evalNode(c.recv, u, binds));
            string arg = text(evalNode(c.args[0], u, binds));
            return c.name == "like" ? s.like(arg) : s.startsWith(arg);
        }
        expr::Bin => {
            expr::Bin b = n;
            string | int | float | bool | None l = evalNode(b.l, u, binds);
            string | int | float | bool | None r = evalNode(b.r, u, binds);
            if (b.op == "&&") { return truth(l) && truth(r); }
            if (b.op == "||") { return truth(l) || truth(r); }
            if (b.op == ">=") { return num(l) >= num(r); }
            if (b.op == "<") { return num(l) < num(r); }
            if (b.op == "+") { return num(l) + num(r); }
            if (b.op == "==") { return text(l) == text(r) && num(l) == num(r); }
            throw RuntimeException("unsupported operator ${b.op}");
        }
        else => { throw RuntimeException("unhandled node"); }
    }
}

int minAge = 18;
expr::Expr<(User) => bool> adult = (u) => u.age >= minAge && u.name.like("A%");
User ada = User("Ada", 36, true);
User al = User("Al", 12, true);
User bob = User("Bob", 40, true);
for (User u in [ada, al, bob]) {
    bool viaTree = truth(evalNode(adult.tree, u, adult.binds));
    console.writeln("${u.name}: tree=${viaTree} closure=${adult.fn(u)}");
}
Run it ▶
Ada: tree=true closure=true
Al: tree=false closure=false
Bob: tree=false closure=false

Notes

A Bin operator is one of ==, !=, <, <=, >, >=, &&, ||, +, -, *, / and %. Operands are never reordered: None != u.name stays a Bin("!=", Lit(None), Field(["name"])). A Field path carries no marker for which lambda parameter it belongs to.

Examples

Walking a hand-built tree

expr::Node tree = expr::Bin("&&", expr::Field(["active"]), expr::Lit(true));
match (tree) {
    expr::Bin => { expr::Bin b = tree; console.writeln("binary ${b.op}"); }
    else => { console.writeln("other"); }
}
Run it ▶
binary &&

Types

  • Assign — A field assignment, u.field = value, which is the whole body of a "set" lambda.
  • Bin — A binary operation: l op r.
  • Bind — A captured value, referred to by its position in the binds array of the enclosing expr::Expr.
  • Call — A method call on a receiver, such as u.name.like("A%").
  • Expr — A lambda together with a walkable description of its body.
  • Field — A member access rooted at a lambda parameter, such as u.address.city.
  • Lit — A literal value in the expression: a string, an integer, a float, a boolean, or None.
  • Node — The base class of every node in the reification tree.
  • Un — A unary operation: !e or -e.

See also

  • Expr — A lambda together with a walkable description of its body.
  • Expression reification — lambdas as data — A lambda literal in a position typed expr::Expr<F> compiles to an ordinary closure plus a walkable tree of its checked body, which is what query builders translate to other languages.
  • The reifiable subset — The expressions that may appear in a reified lambda and the tree node each one becomes.