Rex Documentation

Rex (short for Rush Expressions) is a strongly-typed, pure functional language built to be an excellent target for LLM-generated programs, with a focus on data processing. At a high level, you write transformations over lists, records, ADTs, and other values using familiar functional building blocks like map, filter, folds, pattern matching, and composition. The language is designed to make dataflow clear and predictable, with types and pure expressions doing most of the heavy lifting.

Rex is designed first and foremost to be embedded inside Rust applications. In that model, your Rust program acts as the host runtime and injects native functions into Rex so scripts can orchestrate real work while staying in a concise, declarative style. This makes Rex a practical scripting layer for workflow-style systems where you want strong typing and explicit control at the host boundary.

Because Rex programs are pure and free of side effects in the language itself, the runtime can safely execute host-provided async functions in parallel when it is valid to do so. In practice, that means users can write straightforward functional code and still benefit from concurrency without directly managing threads, locks, or low-level async orchestration.

Rex examples marked as interactive can be edited and run directly in the documentation. Reference snippets and Rust embedding examples are displayed as static code. A good place to start is the interactive sample below.

If you are using Rex as a code-generation target, read LLMs early. It covers the LLM-first semantic workflow, syntax pitfalls, and validation steps that reduce iteration time.

Try editing and running this intro data-processing demo:

let
  values = [3, 12, 7, 20, 15, 4],
  selected = filter (\n -> n >= 10) values,
  adjusted = map (\n -> n - 2) selected,
  total = foldl (\acc n -> acc + n) 0 adjusted
in
  (values, selected, adjusted, total)

This documentation is organized into several sections:

• Tutorial — A guided walk-through of writing Rex code
• Demos — Interactive algorithm demos
• Language Reference — Compact reference for Rex syntax and features
• Specification — Locked semantics and edge cases
• Architecture — System architecture and design
• Memory Management — Memory management implementation
• Embedding — Embedding Rex in other applications
• Contributing — How to contribute to Rex
• LLMs — LLM-first semantic workflow and generation guidance

Rex as a target for LLMs

Rex is the world’s first parallel functional language explicitly designed to be a useful target for LLMs. Its strong static type system gives rapid, high-signal feedback on generated programs, so both users and models can quickly identify mismatches and converge on correct code.

That typechecking loop works especially well with Rex’s functional, expression-oriented style. Because programs are written as pure data transformations, LLM-generated code tends to be easier to inspect, reason about, and refine than imperative scripts with hidden state or side effects.

Together, these properties make Rex a strong fit for LLM-generated data analysis pipelines and scientific workflows. Models can generate high-level orchestration in Rex, while host-provided Rust functions handle domain-specific execution, giving a clean split between deterministic workflow logic and host capabilities.

Rex Tutorial

This tutorial is a guided walk-through of writing Rex code.

Examples marked as interactive can be edited and run in the docs. Some explanatory snippets are static, including deliberately incomplete or invalid code used to illustrate type errors.

If you want a compact reference instead, see the Language Reference. For locked semantics and edge cases, see the Specification.

The tutorial is divided into three sections:

• Section 1 — Basics — Core language features and syntax
• Section 2 — Advanced Topics — Type system, polymorphism, and typeclasses
• Section 3 — Worked Examples — Practical examples and patterns

Section 1 — Basics

This section covers the fundamental concepts and syntax of the Rex language.

Chapters

1. Getting Started
2. Expressions
3. Let Bindings
4. Functions
5. Operators
6. Collections
7. Dictionaries
8. Algebraic Data Types
9. Pattern Matching
10. Records
11. Types and Annotations
12. Debugging and CLI
13. Prelude Tour

Getting Started

Small Rex programs can be written as one expression, optionally preceded by top-level declarations:

• type — algebraic data types (ADTs)
• class / instance — type classes and instances
• fn — top-level functions

Note: This tutorial focuses on writing Rex code. If you want to embed Rex in Rust, see Embedding.

Running Rex

A runnable Rex file either defines main or ends with a final expression. The examples in this tutorial usually use final expressions because they keep small programs compact.

From this repository, you can run a Rex file:

cargo run -p rex-cli --bin rex_cli -- rex-cli/examples/record_update.rex

Or evaluate a small snippet inline:

cargo run -p rex-cli --bin rex_cli -- -c 'map ((*) 2) [1, 2, 3]'

What you should see

The CLI prints the evaluated value of the program entry point in JSON format. If something fails, you’ll get a parse/type/eval error (often with a span).

What “one expression” means

Even with declarations, a program without main uses the final expression as its result:

fn inc x: i32 -> i32 = x + 1;

let xs = [1, 2, 3] in
  map inc xs

The program above:

1. Declares a top-level function inc.
2. Creates a list xs.
3. Evaluates map inc xs as the program’s result.

Comments

Comments use // ... for line comments and /* ... */ for block comments:

/* This is a comment */
1 + 2

Whitespace

Most whitespace is insignificant, and indentation has no syntactic meaning. Multi-line expressions are often easier to read:

let
  x = 1,
  y = 2
in
  x + y

Commas between let bindings are required. Top-level function declarations end with semicolons, so multi-line bodies do not depend on indentation. The parser also accepts many one-line forms, but multi-line formatting tends to be easier to debug.

Type-class and instance method blocks use explicit braces and semicolon-separated methods:

class Size a where {
  size : a -> i32;
}

An empty marker class or instance uses a semicolon:

class Marker a;
instance Marker i32;

Your first “real” Rex file

Create a file hello.rex:

let
  greet = \name -> "hello, " + name
in
  greet "world"

Run it:

cargo run -p rex-cli --bin rex_cli -- hello.rex

Lambda and Arrow Spelling

Rex uses ASCII-only syntax for lambdas and arrows:

• \ and ->

The Unicode lambda and right-arrow glyphs are not accepted.

Expressions: Values and Control Flow

Rex is expression-oriented: everything produces a value.

This page introduces the “everyday” expression forms you’ll use constantly.

Literals

( true
, false
, 123
, 3.14
, 'λ'
, "hello"
)

Common primitive types are Bool, i32, f32, Char, and String (plus UUID, Hash, DateTime if enabled by the host). A character literal uses single quotes and contains exactly one Unicode scalar value; strings use double quotes.

Integers vs floats

123 is an integer literal. It can specialize to any Integral type from context, and defaults to i32 when ambiguous. 3.14 is a float literal and defaults to f32.

If you need to force a different numeric type, you can use an annotation (covered later).

( (4 is u8)
, (4 is i64)
, (-3 is i32)
)

When the target type is already known, Rex can widen primitive integers without losing information: an i8 value can flow into an i32 parameter. Mixed-width arithmetic still needs a single operator type; Rex does not guess a common type for (1 is i8) + (2 is i32).

Negative numbers

Rex supports negative integer literals:

-420

Negative literals require a signed numeric type. For example, (-3 is u8) is a type error, while (-3 is i16) is valid.

When you’re unsure about parsing, you can always write subtraction explicitly:

0 - 1

If / then / else

if is an expression and must have an else:

let x = 10 in
  if x < 0 then "neg" else "non-neg"

A common mistake

if requires both branches and they must have the same type:

// Not OK: the branches disagree ("String" vs "i32")
if true then "yes" else 0

Equality and comparisons

Comparisons are ordinary functions (usually from the prelude type classes):

( 1 == 2
, 1 != 2
, 1 < 2
, 2 >= 2
)

If you try to compare a type without an Eq / Ord instance, typechecking will fail.

Working with strings

String concatenation uses + (via AdditiveMonoid String):

"Rex " + "rocks"

Because + is type-class-based, the same syntax also works for numeric addition.

Grouping: parentheses are your friend

When in doubt, add parentheses—especially when mixing application and infix operators:

let f = \x -> x + 1 in
  f (1 + 2)

Let Bindings and Scope

let ... in ... introduces local bindings.

Think of let as: “name some sub-expressions so you can reuse them and make types clearer”.

One binding

let x = 1 + 2 in x * 10

Multiple bindings

Bindings can be written on separate lines (typically separated by commas):

let
  x = 1 + 2,
  y = x * 3
in
  (x, y)

Local helper functions

Because functions are values, let is the normal way to define local helpers:

let
  inc = \x -> x + 1,
  double = \x -> x * 2
in
  double (inc 10)

Scope

Bindings are visible only in the in body (and later bindings):

let
  x = 10,
  y = x + 1
in
  y

Recursive bindings

Rex supports writing recursive helpers via let rec. This is the easiest way to write loops:

let rec
  sum = \xs ->
    match xs with {
      case [] -> 0;
      case x::xs -> x + sum xs;
    }
in
  sum [1, 2, 3, 4]

Mutually-recursive helpers use comma-separated bindings:

let rec
  even = \n -> if n == 0 then true else odd (n - 1),
  odd = \n -> if n == 0 then false else even (n - 1)
in
  even 10

Tip: If you’re coming from languages with for loops, think “write a recursive function + match on a list” in Rex.

Let-polymorphism (preview)

Let bindings are generalized (HM let-polymorphism), so one binding can be used at multiple types:

let id = \x -> x in (id 1, id true, id "hi")

This is one of the core reasons to use let: it lets you build small reusable utilities without constantly writing type annotations.

Functions and Lambdas

Functions are values. The most common way to write one is a lambda.

Lambdas

\x -> x + 1

Lambdas can take multiple arguments:

\x y -> x + y

Rex only accepts the ASCII spellings \ and ->.

Annotating lambda parameters

You can annotate parameters when you need to force a specific type:

\(x: i32) -> x + 1

Application

Function application is left-associative:

f x y

is parsed as:

(f x) y

This is why parentheses are important when an argument is itself an application.

Functions returning functions (currying)

let add = \x -> (\y -> x + y) in
  (add 1) 2

Partial application

Because functions are curried, you can supply fewer arguments to get a new function back:

let add1 = (+) 1 in add1 41

Top-level functions (fn)

Top-level functions require parameter types, a return type, and a semicolon terminator. The recommended form puts each parameter name next to its type in the fn header:

fn add x: i32 -> y: i32 -> i32 = x + y;

This declares a function that takes an i32 and returns another function i32 -> i32. The semicolon terminates the top-level declaration, so multi-line bodies do not depend on indentation.

Top-level fn declarations are mutually recursive, so they can reference each other:

fn even n: i32 -> Bool =
  if n == 0 then true else odd (n - 1);

fn odd n: i32 -> Bool =
  if n == 0 then false else even (n - 1);

even 10

Alternative fn forms

Rex also accepts a parenthesized parameter in the header:

fn inc (x: i32) -> i32 = x + 1;

You can also write the full function type after the function name and provide a lambda body:

fn add : i32 -> i32 -> i32 = \x y -> x + y;

These are equivalent alternatives. The named-parameter header form is recommended because it keeps parameter names and types adjacent to each other.

fn constraints with where

Top-level functions can also have type-class constraints:

fn sum_list xs: List i32 -> i32 where Foldable List = foldl (+) 0 xs;

If you haven’t seen where constraints before, Section 2 covers them in detail.

Operators and Precedence

Operators like + and == are just functions with infix syntax.

Using an operator as a value

Parentheses turn an operator into a function value:

(+) 1 2

This enables partial application:

map ((*) 2) [1, 2, 3]

Operators come from type classes

Many operators are methods on prelude classes:

• + / zero from AdditiveMonoid
• * / one from MultiplicativeMonoid
• == / != from Eq
• ordering from Ord

This is why you can write + for both numbers and strings.

Precedence

Rex has a fixed precedence table (see Language Reference). A good habit is to use parentheses whenever you mix application with multiple infix operators.

(1 + 2) * 3

Record projection is not an operator

x.field is field projection syntax, not an operator you can partially apply:

type User = User { name: String };

let u: User = User { name = "Ada" } in u.name

Tuples, Lists, and Dictionaries

Rex supports several lightweight data shapes.

Tuples

Tuples group fixed-position values:

(1, "hi", true)

Rex supports tuple patterns in match and let. For indexing, use numeric projection like .0 and .1.

Indexing tuples with .

let t = (1, "hi", true) in t.1

Lists

List literals use square brackets:

[1, 2, 3]

Under the hood, lists are a prelude ADT List a with constructors Empty and Cons.

You can construct cons cells either as Cons h t (normal constructor call style) or with h::t sugar.

let xs = 1::2::3::[] in xs

match [1, 2, 3] with {
  case Empty -> 0;
  case Cons h t -> h;
}

List patterns (sugar)

Rex also supports list-pattern sugar:

match [1, 2, 3] with {
  case [] -> 0;
  case [x] -> x;
  case x::xs -> x;
}

Lists At Host Boundaries

Rex exposes one ordered collection type: List a. User-written list literals, list constructors, pattern matching, and Rust host Vec<T> values all use this same type.

Internally, the runtime may store a list as linked Cons / Empty cells or as a slice over contiguous heap data. Rex code does not need to choose or convert between those representations.

let
  data = [1, 2, 3]
in
  match data with {
    case x::xs -> x;
    case [] -> -1;
  }

For embedders, a Rust function returning Vec<i32> is exposed in Rex as returning List i32, and a Rust parameter of type Vec<i32> accepts any Rex List i32.

Dictionaries (records / dict values)

Dictionary literals use braces:

{ a = 1, b = 2 }

These are “record-like” values. Depending on context they may be treated as a record type ({ a: i32, b: i32 }) or as a dictionary-like value; either way, you can project fields when the field is known to exist:

type R = R { a: i32, b: i32 };

let r: R = R { a = 1, b = 2 } in r.a

Forcing a dictionary type

If you want a polymorphic “dictionary” (instead of a specific record type), use type ascription with is:

({ a = 1, b = 2 }) is Dict i32

Dict a has String keys and values of one uniform type a. Dictionary literals use identifier keys, while functions such as dict_insert and dict_from_entries also accept arbitrary runtime strings.

For a complete, function-by-function dictionary reference with signatures and runnable examples, see Dictionaries.

Dictionary operations

Lookup is option-based, and updates return new dictionaries:

let
  d0 = dict_singleton "alpha" 1,
  d1 = dict_insert "beta" 2 d0,
  d2 = dict_update "alpha" (\old -> map ((+) 10) old) d1,
  d3 = dict_remove "beta" d2
in
  (dict_get "alpha" d3, dict_has "beta" d3)

dict_keys, dict_values, and dict_entries return lists in lexicographic key order. dict_from_entries performs the inverse conversion; if a key occurs more than once, its last entry wins.

The ordinary map, filter, and filter_map functions operate on dictionary values while preserving their keys. When the key is also needed, use dict_map or dict_filter; their callbacks receive a (String, a) tuple:

let
  d = (({ a = 1, b = 2 }) is Dict i32),
  renamed = dict_map
    (\entry -> match entry with {
      case (key, value) -> ("prefix_" + key, value * 10);
    })
    d,
  selected = dict_filter
    (\entry -> match entry with {
      case (key, value) -> key != "b" && value > 0;
    })
    d
in
  (renamed, selected)

dict_map may produce the same output key from multiple input entries. Results are applied in the input dictionary’s lexicographic key order, so the result produced for the latest input key wins.

Matching dictionaries

Dictionary patterns check for key presence and bind those keys to variables:

let d = ({ a = 1, b = 2 }) is Dict i32 in
match d with {
  case {a, b} -> a + b;
  case {a} -> a;
  case {} -> 0;
}

{} is useful as a fallback: it requires no keys, so it matches any dict.

Dictionaries

A dictionary in Rex is an immutable mapping from String keys to values. Its type is Dict a, where a is the type of every value in the dictionary:

• Keys are always String.
• All values in one dictionary have the same type.
• Operations return new dictionaries; they do not change their inputs.

For example, a Dict i32 can contain any number of integer values, but it cannot mix integers, strings, or other value types:

let scores = ({ alice = 10, bob = 12 }) is Dict i32 in scores

Dictionary literals use identifier-shaped keys. Functions such as dict_singleton, dict_insert, and dict_from_entries accept arbitrary String values as keys, including strings containing spaces.

Dictionary order

Rex stores dictionary entries in ascending lexicographic key order. This determines the order returned by dict_keys, dict_values, and dict_entries. It also makes collision handling in dict_map deterministic.

Function argument order

Rex functions are curried. Dictionary operations conventionally take the dictionary as their last argument, which makes partial application straightforward. For example:

let get_alice = dict_get "alice" in
get_alice (({ alice = 10, bob = 12 }) is Dict i32)

In the signatures below, a and b are type variables. Every occurrence of the same variable must be the same type.

Every example below is a complete executable Rex expression. You can edit it in place and run it to see the resulting value.

Quick reference

Construction

dict_empty

Type: dict_empty : Dict a

dict_empty is an empty dictionary. Because it contains no values, its value type normally comes from the surrounding context or an explicit annotation.

let numbers: Dict i32 = dict_empty in numbers

dict_singleton

Type: dict_singleton : String -> a -> Dict a

dict_singleton key value constructs a dictionary containing exactly one entry.

dict_singleton "request id" "req-123"

dict_from_entries

Type: dict_from_entries : List (String, a) -> Dict a

dict_from_entries entries constructs a dictionary from a list of key/value tuples. It processes the list from first to last. If a key appears more than once, its last value wins. The resulting dictionary is stored in lexicographic key order, not list order.

dict_from_entries
  [("beta", 2), ("alpha", 1), ("beta", 20)]

Lookup and inspection

dict_get

Type: dict_get : String -> Dict a -> Option a

dict_get key dictionary returns Some value when the key exists and None when it does not. Lookup does not fail merely because a key is absent.

let scores = dict_from_entries [("alice", 10), ("bob", 12)] in
(dict_get "alice" scores, dict_get "carol" scores)

dict_has

Type: dict_has : String -> Dict a -> Bool

dict_has key dictionary reports whether the key exists, without retrieving its value.

let scores = dict_from_entries [("alice", 10), ("bob", 12)] in
(dict_has "bob" scores, dict_has "carol" scores)

dict_is_empty

Type: dict_is_empty : Dict a -> Bool

dict_is_empty dictionary is true only when the dictionary has no entries.

let empty: Dict String = dict_empty in
(dict_is_empty empty, dict_is_empty (dict_singleton "name" "Rex"))

dict_keys

Type: dict_keys : Dict a -> List String

dict_keys dictionary returns all keys in ascending lexicographic order.

dict_keys (dict_from_entries [("z", 1), ("alpha", 2), ("middle", 3)])

dict_values

Type: dict_values : Dict a -> List a

dict_values dictionary returns the values ordered by their corresponding keys. It does not sort the values themselves.

dict_values (dict_from_entries [("z", 1), ("alpha", 2), ("middle", 3)])

The result is [2, 3, 1], corresponding to keys alpha, middle, and z.

dict_entries

Type: dict_entries : Dict a -> List (String, a)

dict_entries dictionary returns key/value tuples in ascending lexicographic key order.

dict_entries (dict_from_entries [("z", 1), ("alpha", 2), ("middle", 3)])

Immutable updates

dict_insert

Type: dict_insert : String -> a -> Dict a -> Dict a

dict_insert key value dictionary returns a new dictionary. It adds an absent key or replaces the value of a present key. The input dictionary remains unchanged.

let
  original = dict_singleton "a" 1,
  added = dict_insert "b" 2 original,
  replaced = dict_insert "a" 99 original
in
  (original, added, replaced)

dict_remove

Type: dict_remove : String -> Dict a -> Dict a

dict_remove key dictionary returns a new dictionary without that key. Removing an absent key returns an equivalent dictionary and is not an error.

let original = dict_from_entries [("a", 1), ("b", 2)] in
(original, dict_remove "b" original, dict_remove "missing" original)

dict_update

Type: dict_update : String -> (Option a -> Option a) -> Dict a -> Dict a

dict_update key update dictionary calls update with Some current_value when the key is present or None when it is absent. The callback’s result controls the new dictionary:

• Some new_value inserts or replaces the key.
• None removes the key.

let
  original = dict_singleton "visits" 2,
  incremented = dict_update
    "visits"
    (\current -> match current with {
      case Some count -> Some (count + 1);
      case None -> Some 1;
    })
    original,
  removed = dict_update "visits" (\_ -> None) incremented
in
  (original, incremented, removed)

Transforming entries

The dict_map and dict_filter callbacks receive a two-element (String, a) tuple, so they can inspect both the key and value. Use a tuple pattern in a match expression to name both parts.

Callback applications for different entries may run in parallel. Rex functions are pure, so this does not change the result.

dict_map

Type: dict_map : ((String, a) -> (String, b)) -> Dict a -> Dict b

dict_map transform dictionary transforms both keys and values. The callback must return a (String, b) tuple, which becomes an entry in the result.

let
  input = (({ c = 3, a = 1, b = 2 }) is Dict i32),
  renamed = dict_map
    (\entry -> match entry with {
      case (key, value) -> ("item_" + key, value * 10);
    })
    input
in
  renamed

Multiple callbacks may return the same output key. Rex applies completed results in the input dictionary’s original lexicographic key order, regardless of callback completion order. Therefore, the result from the latest input key wins:

dict_map
  (\entry -> match entry with {
    case (key, value) -> ("same", key + ":" + show value);
  })
  (({ c = 3, a = 1, b = 2 }) is Dict i32)

The input order is a, b, c, so the final dictionary contains "c:3" at key same.

dict_filter

Type: dict_filter : ((String, a) -> Bool) -> Dict a -> Dict a

dict_filter predicate dictionary keeps each original entry for which the predicate returns true. The predicate can inspect both key and value. Accepted entries keep their original keys and values.

dict_filter
  (\entry -> match entry with {
    case (key, value) -> key != "draft" && value >= 2;
  })
  (({ draft = 10, first = 1, second = 2, third = 3 }) is Dict i32)

Transforming values with typeclass functions

Dict implements Functor and Filterable. Their generic functions operate on values only; the callback does not receive a key. These functions preserve every retained entry’s original key.

Like the entry-aware functions, callback applications for different values may run in parallel.

map on dictionaries

Type: map : (a -> b) -> Dict a -> Dict b

map transform dictionary transforms every value and preserves every key. Use dict_map instead when the callback needs the key or must produce new keys.

map
  (\score -> "score=" + show score)
  (({ alice = 10, bob = 12 }) is Dict i32)

filter on dictionaries

Type: filter : (a -> Bool) -> Dict a -> Dict a

filter predicate dictionary tests values only and preserves the keys of accepted values. Use dict_filter when filtering depends on a key.

filter
  (\score -> score >= 10)
  (({ alice = 10, bob = 7, carol = 12 }) is Dict i32)

Choosing the right transformation

For dictionary literal syntax and dictionary pattern matching, see Collections.

Algebraic Data Types (ADTs)

ADTs let you define your own sum types. Top-level type declarations end with semicolons.

You’ll use ADTs to model “this or that” choices: optional values, tagged unions, trees, results, etc.

Simple ADT

type Maybe a = Just a | Nothing;

Constructors are values:

type Maybe a = Just a | Nothing;

let v = Just 1 in
  (v, Nothing)

Using ADTs is all about match

Defining an ADT is only half the story; consuming it is done with pattern matching:

type Maybe a = Just a | Nothing;

let
  fromMaybe = \d m ->
    match m with {
      case Just x -> x;
      case Nothing -> d;
    }
in
  fromMaybe 0 (Just 5)

Constructors with multiple fields

type Pair a b = Pair a b;

let v = Pair 1 "hi" in
  v

This is a single-constructor ADT (a “product type”). In many programs you’ll use record-carrying constructors instead because they self-document field names.

Record-carrying constructors

Variants can carry a record payload:

type User = User { name: String, age: i32 };

let u = User { name = "Ada", age = 36 } in
  u

This style works well with field projection and update (covered later).

Multi-variant and recursive ADTs

You can define sum types with multiple constructors, including recursive ones:

type Tree
  = Leaf { value: i32 }
  | Node { left: Tree, right: Tree };

Recursive ADTs are the foundation for ASTs, expression trees, and many structured data problems.

Pattern Matching with match

Use match to branch on the shape of values.

match is the “workhorse” control flow construct in Rex. You’ll use it for:

• consuming ADTs (Option, Result, your own types),
• splitting lists ([] vs x::xs),
• checking key presence in dicts ({a, b}),
• refining record-carrying variants so projection/update typecheck.

Matching ADTs

type Maybe a = Just a | Nothing;

let fromMaybe = \d m ->
  match m with {
    case Just x -> x;
    case Nothing -> d;
  }
in
  fromMaybe 0 (Just 5)

Rex checks matches for exhaustiveness on ADTs and reports missing constructors.

Inline match syntax

You’ll often see compact “inline” matches in examples:

match (Some 1) with { case Some x -> x; case None -> 0; }

Common patterns

Wildcards:

match [1, 2, 3] with {
  case Empty -> 0;
  case Cons _ _ -> 1;
}

List patterns:

match [1, 2] with {
  case [] -> 0;
  case [x] -> x;
  case [x, y] -> x + y;
  case _ -> 0;
}

Cons patterns:

match [1, 2, 3] with {
  case h::t -> h;
  case [] -> 0;
}

h::t is equivalent to Cons h t; both expression forms are valid.

Record patterns on record-carrying constructors:

type Point = Point { x: i32, y: i32 };

let p = Point { x = 1, y = 2 } in
match p with {
  case Point { x: x, y: y } -> x + y;
}

Dict key presence patterns:

let d = ({ a = 1, b = 2 }) is Dict i32 in
match d with {
  case {a, b} -> a + b;
  case {a} -> a;
  case {} -> 0;
}

Arrow spelling

Match arms use ->:

type Bit = T | F;

let v = T in
match v with {
  case T -> 1;
  case F -> 0;
}

Ordering and fallbacks

Match arms are tried top-to-bottom. Put specific patterns first and broad patterns (like _ or {}) last.

Records: Projection and Update

Records are key/value structures with named fields. Rex supports:

• field projection: base.field
• record update: { base with { field = expr } }

At the value level, “record” literals are written like dicts:

{ x = 1, y = 2 }

At the type level, record types are written with ::

let p: { x: i32, y: i32 } = { x = 1, y = 2 } in
  p

Give a record shape a reusable name with a transparent alias. The alias does not introduce a constructor; its values are still ordinary records:

type Point = { x: i32, y: i32 };

let p: Point = { x = 1, y = 2 } in p

Projection

type Point = { x: i32, y: i32 };

let p: Point = { x = 1, y = 2 } in p.x

Projection is accepted when the field is definitely available on the type (see Specification).

Tip: If you get a “field not definitely available” type error, it usually means the typechecker can’t prove which ADT variant you have. A match often fixes it.

Update

type Point = { x: i32, y: i32 };

let p: Point = { x = 1, y = 2 } in
  { p with { x = p.x + 10 } }

Updates can set multiple fields at once:

type Point = { x: i32, y: i32 };

let p: Point = { x = 1, y = 2 } in
  { p with { x = 100, y = 200 } }

Updating record-carrying ADT variants

This is a common pattern:

type Sum = A { x: i32 } | B { x: i32 };

let s: Sum = A { x = 1 } in
match s with {
  case A {x} -> { s with { x = x + 1 } };
  case B {x} -> { s with { x = x + 2 } };
}

The match arms refine which constructor s has, allowing the update to typecheck.

Types and Annotations

Rex uses Hindley–Milner type inference, but you can (and often should) add annotations.

This page is about the “tools” you use to make types explicit when inference isn’t enough.

Type names

Examples of primitive and constructed types:

• Bool, i32, f32, Char, String
• (a, b) for tuples
• List a, Option a, Promise a, Result a e (prelude/built-in constructors)

Lowercase names in type positions are type parameters only after a surrounding form declares them:

fn id<a> x: a -> a = x;

id 1

The same rule applies to let, declare fn, class methods, and instances:

let id<a>: a -> a = \x -> x in id "hello"

Function types are right-associative:

i32 -> i32 -> i32

means:

i32 -> (i32 -> i32)

Record types

Record types use ::

{ x: i32, y: i32 }

Record values use =:

{ x = 1, y = 2 }

Let annotations

let x: i32 = 1 in x

Lambda parameter annotations

\(x: i32) -> x + 1

Annotating expressions

You can also annotate via a let-binding when you want to force a particular type:

let xs: List i32 = [1, 2, 3] in xs

Type ascription with is

Rex also supports an expression-level “ascription” form:

({ a = 1, b = 2 }) is Dict i32

You’ll see is used in examples for two common reasons:

1. To force a dictionary type (Dict a) instead of a specific record type.
2. To disambiguate overloaded values (similar to adding a let-annotation).

Warning: Use is when it helps clarity, but don’t overuse it: most of the time, simple let annotations are easier to read.

Debugging: CLI Tips and Common Errors

Rex is prepared and evaluated in stages:

1. Parsing
2. Import/declaration preparation
3. Type inference / checking
4. Evaluation

Most debugging is about figuring out which stage is failing and adding just enough information to make the problem obvious.

Useful CLI flags

Run a Rex file:

cargo run -p rex-cli --bin rex_cli -- path/to/file.rex

Run a file with JSON inputs for its entry point:

cargo run -p rex-cli --bin rex_cli -- path/to/program.rex --inputs path/to/inputs.json

The inputs file is a top-level JSON object. Each field name must match a parameter of main; runnable files without main use their final expression and have the empty input shape {}.

Inspect the entry point type metadata:

cargo run -p rex-cli --bin rex_cli -- path/to/program.rex --manifest

Run an inline snippet:

cargo run -p rex-cli --bin rex_cli -- -c 'let x = 1 in x + 2'

Show the parsed AST and exit:

cargo run -p rex-cli --bin rex_cli -- --emit-ast -c '1 + 2'

Show the entry point result type and exit:

cargo run -p rex-cli --bin rex_cli -- --emit-type -c 'map ((*) 2) [1, 2, 3]'

Print a string result without JSON quotes:

cargo run -p rex-cli --bin rex_cli -- --raw-output -c '"hello"'

“Parse error”: start small

If you hit a parse error:

1. Reduce the program to the smallest failing snippet.
2. Add parentheses to disambiguate application vs infix operators.
3. Prefer multi-line let/match while debugging.

“Missing typeclass impl”

This usually means you called a type-class method at a type that has no instance.

Typical fixes:

• use a different type (List vs Option, Option vs Result, …),
• add an instance (Section 2),
• add a type annotation so the intended instance is selected.

“Ambiguous overload”

This happens when an overloaded value doesn’t have enough information to pick an instance.

Typical fixes:

• add a let-annotation: let z: i32 = zero in z
• add is ascription: (zero) is i32 (if you prefer expression ascription style)
• use the value in a context that forces a type (e.g. zero + 1).

The exact defaulting rules are described in Specification.

A Tour of the Prelude

Rex ships with a small “prelude” of standard types, type classes, and instances.

The source of truth in this repository is:

• type classes + instances: rex-engine/src/prelude/typeclasses.rex
• runtime builtins + helper wiring: rex-engine/src/prelude/mod.rs
• standard type-system construction: rex-engine/src/prelude/type_system.rs

This page is a guided map so you know what to reach for while writing Rex.

Core data types

These are available by default:

• List a (with constructors Empty and Cons)
• Option a (constructors Some and None)
• Result a e (constructors Err and Ok)
• Dict a

Core classes (selected)

Numeric-like classes

• AdditiveMonoid a (zero, +)
• MultiplicativeMonoid a (one, *)
• Ring a, Field a, Integral a (and friends)

Equality and ordering

• Eq a (==, !=)
• Ord a (cmp, <, <=, >, >=)
• Default a (default)

Default gives you a value-level default for a type. It is separate from Rex’s defaulting pass, which resolves ambiguous type variables for defaultable classes.

Collections and effects

• Functor f (map)
• Applicative f (pure, ap)
• Monad m (bind)
• Foldable t (foldl, foldr, fold)
• Filterable f (filter, filter_map)
• Sequence f (take, skip, zip, unzip)

A few useful helper functions

The prelude also exposes some generic helpers (type-class-based):

• sum, mean, length, min, max
• first, last, slice for strict list range extraction
• list_get, list_slice, list_find, and other total list helpers
• is_some, is_none (for Option)
• is_ok, is_err (for Result)

How to learn what something is

When you see an unfamiliar function:

1. Ask the CLI for its type: cargo run -p rex-cli --bin rex_cli -- --emit-type -c 'the_name'
2. If it’s a type-class method, find the class in rex-engine/src/prelude/typeclasses.rex
3. If it’s a Rust-backed helper or primitive, find the runtime wiring in rex-engine/src/prelude/mod.rs

This workflow is especially helpful when you’re building your own abstractions.

Section 2 — Advanced Topics

This section covers advanced type system features, polymorphism, and functional programming patterns.

Chapters

1. Type Inference
2. Polymorphism
3. Typeclasses
4. Instances
5. Constraints and Where
6. Resolution and Coherence
7. Functor
8. Applicative
9. Monad
10. Writing Instances
11. Defaulting
12. Higher-Kinded Types

Type Inference (Hindley–Milner)

Rex infers types for most expressions. You get type errors when constraints can’t be satisfied or when the program would require ambiguous instance selection.

This section is intentionally practical: it’s about recognizing when the typechecker needs help, and what kinds of help work best.

A simple inference example

\x -> x

This is polymorphic: it can be used at any type (a -> a).

Try it

Ask the CLI for the type:

cargo run -p rex-cli --bin rex_cli -- --emit-type -c '\\x -> x'

Inference plus operators

\x -> x + 1

This adds constraints (here, a numeric type class for +).

What changed?

The expression no longer works at “any type” because + only exists for types with an AdditiveMonoid instance (numbers and strings in the prelude).

When inference fails

You’ll see errors when:

• branches of an if don’t match types,
• you call a type-class method with no applicable instance,
• you use an overloaded value without enough type information (ambiguity).

For details on ambiguity and defaulting, see Specification.

The most common “fixes”

1. Add a type annotation to a let binding.
2. Use expression ascription with is.
3. Restructure code so an argument forces a type (e.g. apply a polymorphic function).

Polymorphism and Let-Generalization

The most visible “HM feature” in Rex is that let bindings can be reused at multiple types.

If you’re new to HM languages, this is the big shift from “everything has one type” to “some definitions are generic”.

A polymorphic helper

let id = \x -> x in
  (id 1, id true, id "hi")

Why lambdas aren’t generalized

Inside a lambda body, parameters are monomorphic unless you explicitly abstract:

\f ->
  let x = f 1 in
    f x

If f were required to work at multiple unrelated types, that would be rejected.

Practical implication

If you want something reusable, let-bind it at the outer level:

let
  id = \x -> x,
  use = \x -> (id x, id x)
in
  use 1

Practical tip

If a definition should be reusable, prefer let-binding it and giving it a clear name (and often a type annotation).

In practice, you’ll use:

• let for reusable helpers,
• lambdas for “inline glue” (callbacks passed to map, foldl, bind, …),
• fn for API-like top-level functions with stable signatures.

Type Classes: Defining Overloads

Type classes define a set of operations that can be implemented for many types.

Rex type classes are similar to Haskell’s: they are compile-time constraints with runtime dictionary resolution.

Defining a class

class Size a where {
  size : a -> i32;
}

Method signatures can mention the class parameter a and any other types in scope.

Empty Classes

Classes with methods use where { ... }. Marker classes with no methods use a semicolon:

class Marker a;

Operators as methods

class Eq a where {
  == : a -> a -> Bool;
  != : a -> a -> Bool;
}

Superclasses

Superclasses use <= (read “requires”):

class Ord a <= Eq a where {
  < : a -> a -> Bool;
}

If you have an Ord a, you also must have an Eq a instance.

Multi-parameter classes (tupled)

User-defined classes may take multiple type parameters. For example:

In Rex source you write:

class Convert a b where {
  convert : a -> b;
}

In where constraints, multi-parameter classes are written using a tuple:

where Convert (a, b) -> ...

This matches the implementation model described in Specification.

Instances: Implementing Type Classes

Instances attach method implementations to a concrete “head” type.

An instance has three parts:

1. The class name (Show, Size, Functor, …)
2. The instance head type (what you’re implementing it for)
3. An optional instance context (<= ...) of required constraints

A monomorphic instance

class Show a where {
  show : a -> String;
}
instance Show i32 where {
  show = \_ -> "<i32>";
}

Class names in instance headers can be module-qualified when imported via alias:

import dep as D;

instance D.Show i32 where {
  show = \_ -> "<i32>";
}

A polymorphic instance with context

Instance contexts use <=:

instance<a> Show (List a) <= Show a where {
  show = \xs ->
    let
      step = \out x ->
        if out == "["
          then out + show x
          else out + ", " + show x,
      out = foldl step "[" xs
    in
      out + "]";
}

Read this as: “Show (List a) exists as long as Show a exists”.

Why the context matters

Inside show for lists, we call show x. That requires Show a, so we must list it in the instance context.

Non-overlap (coherence)

Rex rejects overlapping instance heads for the same class. This keeps method lookup deterministic.

In practical terms: you can’t have two different Show (List a) instances in scope at once.

Constraints and where

Sometimes a function is only valid when certain type-class constraints hold. In Rex you’ll see those constraints in type signatures (for fn) and in where clauses (commonly for lambdas).

Constrained lambdas

This example is from rex-cli/examples/type_classes.rex:

let
  use_classes<f,a> =
    \ (x: List a) (y: f a) (z: a) where Foldable f ->
    let
      first = unwrap (list_get 0 x),
      total = foldl (\acc _ -> acc) z y
    in
      (first, total, z)
in
  let result: (i32, i32, i32) = use_classes [10, 20, 30] [1, 2, 3] 0 in result

Notes:

• where ... -> attaches constraints to the lambda.
• Constraints can use module-qualified class names when imported via alias (for example where M.ClassName t -> ...).

Constrained top-level functions

Top-level functions can also have a where clause:

fn sum_list : List i32 -> i32 where Foldable List = \xs -> foldl (+) 0 xs;

Constraints appear after the type signature and before =.

Multiple constraints

Constraints are comma-separated:

fn demo : List i32 -> i32 where Foldable List, AdditiveMonoid i32 = \xs -> foldl (+) 0 xs;

Note: In many cases you don’t need to write constraints for concrete prelude types (List, Option, etc.) because the argument type already forces instance selection. where becomes more important when you want polymorphic constraints (e.g. “for any f with Foldable f”).

Resolution, Coherence, and Ambiguity

Type-class methods in Rex are resolved based on the inferred type at the call site.

This page answers “why did the typechecker complain?” when you’re using overloaded methods.

Coherence: why overlap is rejected

If two instances could match the same call, the runtime wouldn’t know which method to pick. Rex rejects such overlaps per class.

Deferred resolution for function values

Rex can keep an overloaded function value around and resolve it later when you apply it:

let f = map ((+) 1) in
  ( f [1, 2, 3]
  , f (Some 41)
  )

Here map is a Functor method. The engine picks the right map implementation when it sees the argument type (List i32 vs Option i32).

Why this works

map ((+) 1) is still a function, so Rex can defer selecting the Functor instance until the function is applied to a concrete container.

Ambiguity for non-function values

If you use an overloaded method as a non-function value and the type is not determined, resolution can be ambiguous and Rex will error.

For example, pure 1 is ambiguous by itself because it could be List i32, Option i32, List i32, Result i32 e, etc.

Fix it by forcing a type:

let x: Option i32 = pure 1 in x

For the exact rules, see Specification (“Type Classes: Coherence, Resolution, and Ambiguity”).

Functors

The prelude defines:

class Functor f where {
  map<a,b> : (a -> b) -> f a -> f b;
}

map applies a pure function inside a container f.

If you can describe an operation as “change the values without changing the structure”, it’s a good fit for map.

Mapping over lists

map ((*) 2) [1, 2, 3]

Mental model

Each element is transformed independently; list length stays the same.

Mapping over Option

( map ((+) 1) (Some 41)
, map ((+) 1) None
)

None acts like “no value to transform”.

Mapping over Result

( map ((*) 2) (Ok 21)
, map ((*) 2) (Err "boom")
)

map transforms Ok values but leaves Err unchanged.

A useful pattern: composing transforms

Instead of branching on shapes early, keep your code “in the functor”:

let inc = \x -> x + 1 in
  map inc (Some 1)

Applicatives

An Applicative is a Functor that can inject values and apply wrapped functions:

class Applicative f <= Functor f where {
  pure<a> : a -> f a;
  ap<a,b> : f (a -> b) -> f a -> f b;
}

Applicatives are great when you want to combine independent computations that live “in a container”.

pure

let x: Option i32 = pure 1 in x

The type depends on context. For example, this forces Option:

let x: Option i32 = pure 1 in x

A common pattern: building up computations

Because functions are curried, you can apply step-by-step. For Option:

ap (ap (pure (\x y -> x + y)) (Some 1)) (Some 2)

ap with Option

ap (Some ((+) 1)) (Some 41)

If either side is “missing”, the result is missing:

( ap None (Some 1)
, ap (Some ((+) 1)) None
)

Applicative style

You can build up multi-argument computations by applying step-by-step:

ap (ap (pure (\x y -> x + y)) (Some 1)) (Some 2)

Monads

Monads are about sequencing computations where the next step depends on the previous result.

In Rex, the core monad operation is bind:

class Monad m <= Applicative m where {
  bind<a,b> : (a -> m b) -> m a -> m b;
}

Note the argument order: function first, then the monadic value.

If you come from Haskell: Rex’s bind corresponds to (>>=) but with the arguments flipped.

Option as a Monad

let
  safe_inc = \x -> Some (x + 1),
  step = \x -> bind safe_inc x
in
  step (Some 1)

More realistically, you inline the next step:

bind (\x -> Some (x + 1)) (Some 41)

Why monads matter

With Option, monadic sequencing means “stop early if something is missing” without deeply nested match expressions.

Result as a Monad

Result a e is useful for short-circuiting on the first Err:

let
  ok = Ok 1,
  boom = Err "boom"
in
  ( bind (\x -> Ok (x + 1)) ok
  , bind (\x -> Ok (x + 1)) boom
  )

“Do notation” without syntax

Rex doesn’t require special syntax. You can write sequencing explicitly with bind and lambdas:

bind (\x ->
  bind (\y ->
    pure (x + y)
  ) (Some 2)
) (Some 1)

Tip: When your bind chains get hard to read, consider extracting the steps into named let bindings.

For example, the same logic with named steps:

let
  add_x_y = \x y -> pure (x + y),
  step_y = \x -> bind (add_x_y x) (Some 2),
  run = \mx -> bind step_y mx
in
  run (Some 1)

Writing Your Own Instances (Including Functor/Applicative/Monad)

This page is a hands-on guide to defining your own instances for custom ADTs.

We’ll build a tiny container type and give it Functor, Applicative, and Monad instances.

Note: Functor, Applicative, and Monad are provided by the Rex prelude. The examples below assume those classes already exist (so we only write type/instance).

Step 1: define a container ADT

type Box a = Box a;

This is a single-variant ADT that “wraps” a value.

Step 2: make it a Functor

type Box a = Box a;

instance Functor Box where {
  map = \f bx ->
    match bx with {
      case Box x -> Box (f x);
    };
}

Now you can:

type Box a = Box a;

instance Functor Box where {
  map = \f bx ->
    match bx with {
      case Box x -> Box (f x);
    };
}
map ((+) 1) (Box 41)

Step 3: make it an Applicative

type Box a = Box a;

instance Functor Box where {
  map = \f bx ->
    match bx with {
      case Box x -> Box (f x);
    };
}
instance Applicative Box <= Functor Box where {
  pure = \x -> Box x;
  ap = \bf bx ->
    match bf with {
      case Box f -> map f bx;
    };
}

Try:

type Box a = Box a;

instance Functor Box where {
  map = \f bx ->
    match bx with {
      case Box x -> Box (f x);
    };
}
instance Applicative Box <= Functor Box where {
  pure = \x -> Box x;
  ap = \bf bx ->
    match bf with {
      case Box f -> map f bx;
    };
}
ap (Box ((*) 2)) (Box 21)

Step 4: make it a Monad

type Box a = Box a;

instance Functor Box where {
  map = \f bx ->
    match bx with {
      case Box x -> Box (f x);
    };
}
instance Applicative Box <= Functor Box where {
  pure = \x -> Box x;
  ap = \bf bx ->
    match bf with {
      case Box f -> map f bx;
    };
}
instance Monad Box <= Applicative Box where {
  bind = \f bx ->
    match bx with {
      case Box x -> f x;
    };
}

Try:

type Box a = Box a;

instance Functor Box where {
  map = \f bx ->
    match bx with {
      case Box x -> Box (f x);
    };
}
instance Applicative Box <= Functor Box where {
  pure = \x -> Box x;
  ap = \bf bx ->
    match bf with {
      case Box f -> map f bx;
    };
}
instance Monad Box <= Applicative Box where {
  bind = \f bx ->
    match bx with {
      case Box x -> f x;
    };
}
bind (\x -> Box (x + 1)) (Box 41)

Common pitfalls

• Overlapping instances: Rex rejects overlap for the same class; keep instance heads distinct.
• Missing context constraints: if your method body calls another overloaded method, you often need to list the required class in the instance context.
• Wrong argument order for bind: Rex’s bind is (a -> m b) first, then m a.

Default: Typeclass and Defaulting

In Rex, “default” can mean two different things:

• The Default typeclass method default : a
• The defaulting pass that resolves ambiguous type variables for defaultable classes

1) Default Typeclass (default : a)

The prelude provides Default and a set of built-in instances.

Built-in types with Default:

• Bool
• u8, u16, u32, u64
• i8, i16, i32, i64
• f32, f64
• String
• List a
• Option a
• Result a e (when Default a is available)

Implementing Default for custom ADTs

You can implement Default for many ADT shapes.

Single constructor with unnamed fields:

type Pair = Pair i32 Bool;

instance Default Pair where {
    default = Pair 42 true;
}

Single constructor with named fields:

type Config = Config { retries: i32, enabled: Bool };

instance Default Config where {
    default = Config { retries = 3, enabled = false };
}

Multiple variants (enum) with no fields:

type Mode = Fast | Safe | Debug;

instance Default Mode where {
    default = Safe;
}

Multiple variants with mixed payload shapes:

type Token = Eof | IntLit i32 | Meta { line: i32, col: i32 };

instance Default Token where {
    default = Meta { line = 1, col = 1 };
}

Generic ADTs with constraints:

type Box a = Box a | Missing;

instance<a> Default (Box a) <= Default a where {
    default = Box default;
}

Constructing named options with selected overrides

For a single-constructor ADT with named fields, the constructor itself can request the type’s default and override only the fields you supply:

type Config = Config { retries: i32, enabled: Bool, label: String };

instance Default Config where {
    default = Config { retries = 3, enabled = false, label = "standard" };
}

Config { retries = 9 }

This evaluates to a Config with retries = 9, enabled = false, and label = "standard". Use Config {} when you want the default value while keeping its type explicit.

Omitted fields come from Default Config as a whole. Rex does not default each field separately, so manually chosen and interdependent defaults are preserved. Complete construction still works without a Default instance, while partial construction requires one.

This shorthand is intentionally limited to single-variant record ADTs. For an ADT with multiple variants, a type-level default might produce a different variant from the constructor you named.

Ambiguous default calls and is

When multiple Default instances are in scope, default may be ambiguous until you pin the type. Record updates require a definitely known base type.

Failing example:

type A = A { x: i32, y: i32 };
type B = B { x: i32, y: i32 };

instance Default A where {
    default = A { x = 1, y = 2 };
}
instance Default B where {
    default = B { x = 10, y = 20 };
}
{ default with { x = 9 } }

In the editor/playground, use the quick fix on this error to insert is for the intended ADT. Try it on the example above.

Passing example (same setup, with explicit is):

type A = A { x: i32, y: i32 };
type B = B { x: i32, y: i32 };

instance Default A where {
    default = A { x = 1, y = 2 };
}
instance Default B where {
    default = B { x = 10, y = 20 };
}
{ (default is A) with { x = 9 } }

Another failing example (same ambiguity in a let binding):

type A = A { x: i32, y: i32 };
type B = B { x: i32, y: i32 };

instance Default A where {
    default = A { x = 1, y = 2 };
}
instance Default B where {
    default = B { x = 10, y = 20 };
}
let
    a = { default with { x = 9 } },
    b = { default with { y = 8 } }
in
    (a, b)

For this let-binding form, quick fixes offer two styles: add is to the default call, or add a type annotation on the binding (for example a: A = ...). These same quick fixes are also exposed through LSP code actions and can be used by LLM-driven tooling.

2) Type Defaulting (Ambiguous Types)

Some overloaded prelude operations (such as zero) only require class constraints:

zero

If nothing else forces a concrete type, Rex runs defaulting to pick a concrete type from the defaulting candidates that satisfy the required class constraints.

If you see an “ambiguous overload” error around numeric expressions, force a type:

let z: i32 = zero in z

Or use the value in a way that constrains it:

zero + 1

Integer literals are also overloaded (over Integral) and become concrete from context:

let
  x = 4,
  f: u16 -> u16 = \n -> n
in
  f x

Negative literals must resolve to a signed type:

let
  x: i32 = -3,
  f: i32 -> i32 = \n -> n
in
  f x

let x: u32 = -3 in x is a type error.

The defaulting algorithm is specified in Specification (“Defaulting”).

Higher-Kinded Types (and Partial Application)

This page explains the “advanced” type shape behind Functor, Applicative, and Monad.

What is a “type constructor”?

Some types take type parameters:

• List a
• Option a
• Promise a
• Result a e

The bare names List, Option, and Promise are type constructors (they still need an a).

In informal kind notation:

• List : * -> *
• Option : * -> *
• Promise : * -> *
• Result : * -> * -> *

Why Functor talks about f a

The class is defined as:

class Functor f where {
  map<a,b> : (a -> b) -> f a -> f b;
}

f here stands for a unary type constructor like List, Option, or Promise.

Result is binary — so how can it be a Functor?

The prelude has an instance:

instance<e> Functor (Result e) where {
  map = prim_map;
}

Result e means: “fix the error type to e, leaving one type parameter for the Ok value”. Written fully (with both parameters), that’s Result a e.

So Result e behaves like a unary type constructor:

• Result a e is “a result with Ok type a and Err type e”
• map transforms the Ok value and leaves Err alone

Recognizing partial application in types

Whenever you see something like (Result e) or (Either e) in other languages, think:

“We pinned one type parameter to turn a multi-parameter type into a unary constructor.”

This idea shows up again for Applicative (Result e) and Monad (Result e).

Section 3 — Worked Examples

These examples are interactive in the docs: edit and run them directly on each page.

Tip: You can also run many examples inline with:

cargo run -p rex-cli --bin rex_cli -- -c '<paste rex expression here>'

For larger multi-line experiments, saving to a .rex file is often easier.

Chapters

1. Lists
2. Folds
3. Match and ADTs
4. Records
5. Functor Polymorphism
6. Option Pipelines
7. Result Workflows
8. Custom Show Printing
9. Custom Size
10. List Helpers
11. Small Standard Module
12. Mini Project

Example: List Basics

This page is a hand-held tour of the most common list workflow in Rex:

• start with a list value
• transform it with map
• keep only what you want with filter
• (optionally) reduce it with foldl (see the next page)

If you’re new to functional programming, think of map as “for each element, compute a new element”, and filter as “keep only elements where the predicate is true”.

Goal

Take a list of integers and produce new lists by applying simple rules (double, keep even, increment).

The simplest transform

Double everything

map ((*) 2) [1, 2, 3, 4]

What to notice

• map comes from Functor List.
• (*) is just a function; ((*) 2) is a partially applied function.

Step-by-step: naming intermediate values

The one-liner above is idiomatic, but while learning it helps to name each step:

let
  xs = [1, 2, 3, 4],
  doubled = map ((*) 2) xs
in
  doubled

This style also makes it easier to debug by temporarily returning an intermediate.

Filter then map

Filtering needs a predicate a -> Bool. Let’s define one:

let
  is_even = \x -> (x % 2) == 0
in
  filter is_even [1, 2, 3, 4, 5, 6]

Now combine filter and map:

let
  xs = [1, 2, 3, 4, 5, 6],
  is_even = \x -> (x % 2) == 0
in
  map ((+) 1) (filter is_even xs)

Variations

Try changing the predicate to keep odd numbers instead:

let is_odd = \x -> (x % 2) != 0 in filter is_odd [1, 2, 3, 4, 5, 6]

Common beginner mistake: missing parentheses

Because application is left-associative, nesting calls without parentheses does not do what you want. Prefer:

let
  xs = [1, 2, 3, 4, 5, 6],
  is_even = \x -> (x % 2) == 0
in
  map ((+) 1) (filter is_even xs)

over trying to “read it as English” without grouping.

Worked examples

Example: triple_then_keep_big

Problem: triple each element, then keep only elements greater than 10.

let
  xs = [1, 2, 3, 4, 5],
  tripled = map ((*) 3) xs
in
  filter (\x -> x > 10) tripled

Why this works: map ((*) 3) transforms each element first, then filter keeps only values that pass the predicate.

Example: between lo hi x with filter

Problem: keep only values in an inclusive range.

let
  between = \lo hi x -> x >= lo && x <= hi
in
  filter (between 3 5) [1, 2, 3, 4, 5, 6]

Why this works: between 3 5 is a predicate function i32 -> Bool, which is exactly what filter expects.

Example: naming inc in let

Problem: replace ((+) 1) with a named helper.

let
  inc = \x -> x + 1
in
  map inc [1, 2, 3, 4]

Why this works: inc has type i32 -> i32, so it can be passed directly to map.

Example: Folding

Foldable gives you foldl and foldr-style iteration.

If map changes values, folds reduce a collection down to a single result.

Goal

Learn to take a list and reduce it to:

• a number (sum, product, count)
• a string (joining)

A mental model: accumulator + step

foldl has the shape:

foldl : (b -> a -> b) -> b -> t a -> b

Read it as:

1. Start with an accumulator of type b
2. For each element of type a, update the accumulator
3. Return the final accumulator

Sum a list

foldl (+) 0 [1, 2, 3, 4]

How to read it

• Start with accumulator 0
• For each element, add it to the accumulator
• Return the final accumulator

The same thing, spelled out

let
  step = \acc x -> acc + x
in
  foldl step 0 [1, 2, 3, 4]

When debugging, spelling out step makes it easier to reason about types.

Build a string

let
  step = \out x ->
    if out == "" then x else out + ", " + x
in
  foldl step "" ["a", "b", "c"]

Worked example: bracketed join

Problem: join strings with commas and wrap the result in brackets.

let
  step = \out x ->
    if out == "" then x else out + ", " + x,
  joined = foldl step "" ["a", "b", "c"]
in
  "[" + joined + "]"

Why this works: the fold builds "a, b, c" from left to right, then the final expression adds the outer brackets.

Using folds to compute “length”

You can compute list length by ignoring elements and incrementing a counter:

foldl (\n _ -> n + 1) 0 [10, 20, 30, 40]

When to prefer match recursion vs foldl

Both are fine. Rules of thumb:

• Use foldl when you’re “reducing” to a single value (sum, count, join).
• Use explicit match recursion when you need more complex control flow.

Worked examples

Example: product with foldl

Problem: multiply all numbers in a list, starting from 1.

foldl (*) 1 [2, 3, 4]

Why this works: 1 is the multiplicative identity, so each element is accumulated by multiplication.

Example: all over booleans

Problem: check whether every boolean in a list is true.

let
  all = \xs -> foldl (\acc x -> acc && x) true xs
in
  (all [true, true, true], all [true, false, true])

Why this works: once acc becomes false, acc && x stays false for the rest of the fold.

Example: any over booleans

Problem: check whether at least one boolean in a list is true.

let
  any = \xs -> foldl (\acc x -> acc || x) false xs
in
  (any [false, false, true], any [false, false, false])

Why this works: the accumulator starts false and flips to true as soon as any element is true.

Example: ADTs + match

This example shows the usual pattern:

1. define an ADT
2. consume it with match

Goal

Build a tiny “Maybe” API:

• fromMaybe (extract with default)
• mapMaybe (transform inside Just)
• isJust (check which constructor you have)

Define an ADT

type Maybe a = Just a | Nothing;

Use it

type Maybe a = Just a | Nothing;

let
  fromMaybe = \d m ->
    match m with {
      case Just x -> x;
      case Nothing -> d;
    }
in
  ( fromMaybe 0 (Just 5)
  , fromMaybe 0 Nothing
  )

Next steps

The next example implements mapMaybe, which applies a function to Just x and leaves Nothing unchanged.

A worked mapMaybe

type Maybe a = Just a | Nothing;

let
  mapMaybe = \f m ->
    match m with {
      case Just x -> Just (f x);
      case Nothing -> Nothing;
    }
in
  ( mapMaybe ((+) 1) (Just 41)
  , mapMaybe ((+) 1) Nothing
  )

Testing constructors with match

There’s no special “isJust” operator — you write it with match:

type Maybe a = Just a | Nothing;

let
  isJust = \m ->
    match m with {
      case Just _ -> true;
      case Nothing -> false;
    }
in
  (isJust (Just 1), isJust Nothing)

Common mistake: missing arms

When matching on an ADT, Rex checks exhaustiveness. If you forget an arm, you’ll get an error that names the missing constructors.

Worked examples

Example: orElse

Problem: return the first Just value, otherwise return the fallback Maybe.

type Maybe a = Just a | Nothing;

let
  orElse = \ma mb ->
    match ma with {
      case Just x -> Just x;
      case Nothing -> mb;
    }
in
  (orElse (Just 1) (Just 2), orElse Nothing (Just 2))

Why this works: match chooses ma when it is Just, and only uses mb when ma is Nothing.

Example: andThen (Maybe bind)

Problem: chain a function that returns Maybe, failing early on Nothing.

type Maybe a = Just a | Nothing;

let
  andThen = \f ma ->
    match ma with {
      case Just x -> f x;
      case Nothing -> Nothing;
    },
  step = \x -> if x > 0 then Just (x + 1) else Nothing
in
  (andThen step (Just 3), andThen step Nothing, andThen step (Just (0 - 1)))

Why this works: Just unwraps and continues with f; Nothing short-circuits immediately.

Example: adding Unknown and handling exhaustiveness

Problem: extend Maybe and still keep matches exhaustive.

type Maybe a = Just a | Nothing | Unknown;

let
  fromMaybe = \d m ->
    match m with {
      case Just x -> x;
      case Nothing -> d;
      case Unknown -> d;
    }
in
  (fromMaybe 0 (Just 5), fromMaybe 0 Unknown)

Why this works: the Unknown arm makes the match complete for all constructors.

Example: Records and Updates

This example focuses on record-carrying ADTs, because that’s where you most often use:

• projection (x.field)
• update ({ x with { field = ... } })

Goal

Model a User record, read its fields, and produce an updated copy.

Step 1: define and update

type User = User { name: String, age: i32 };

let
  u: User = User { name = "Ada", age = 36 },
  older = { u with { age = u.age + 1 } }
in
  (u.age, older.age)

What to notice

• User { ... } constructs a record-carrying ADT value.
• u.age is field projection.
• { u with { age = ... } } updates the record payload and re-wraps the constructor.

Step 2: update multiple fields

type User = User { name: String, age: i32 };

let
  u: User = User { name = "Ada", age = 36 },
  updated =
    { u with
        { age = u.age + 1
        , name = u.name + "!"
        }
    }
in
  (u, updated)

Step 3: why match sometimes matters

Projection/update is only allowed when a field is definitely available on the type. With a multi-variant ADT, you often refine it with match first:

type Sum = A { x: i32 } | B { x: i32 };

let s: Sum = A { x = 1 } in
match s with {
  case A {x} -> { s with { x = x + 1 } };
  case B {x} -> { s with { x = x + 2 } };
}

Worked examples

Example: birthday applied twice

Problem: define birthday : User -> User and apply it two times.

type User = User { name: String, age: i32 };

let
  birthday = \u -> { u with { age = u.age + 1 } },
  u0: User = User { name = "Ada", age = 36 },
  u2 = birthday (birthday u0)
in
  (u0.age, u2.age)

Why this works: each birthday call returns a new User with age incremented by one.

Example: add admin and promote

Problem: add a boolean field and set it to true.

type User = User { name: String, age: i32, admin: Bool };

let
  promote = \u -> { u with { admin = true } },
  u0: User = User { name = "Ada", age = 36, admin = false }
in
  promote u0

Why this works: record update changes only admin, preserving other fields.

Example: add constructor C and update the match

Problem: extend Sum with C { x: i32 } and keep updates valid.

type Sum = A { x: i32 } | B { x: i32 } | C { x: i32 };

let s: Sum = C { x = 1 } in
match s with {
  case A {x} -> { s with { x = x + 1 } };
  case B {x} -> { s with { x = x + 2 } };
  case C {x} -> { s with { x = x + 3 } };
}

Why this works: each arm refines s to a definite constructor, so the update is type-safe.

Example: One map, many containers

This demonstrates deferred resolution of a Functor method value.

Goal

Understand why one definition of f can work for lists, options, and results, and how to avoid ambiguity when working with overloaded methods.

let f = map ((+) 1) in
  ( f [1, 2, 3]
  , f (Some 41)
  , f (Ok 21)
  )

Why this is cool

f is a single definition that can be applied to different container types. Rex defers selecting the Functor instance until you apply f to a concrete container.

Step-by-step

Start by binding the method value:

let f = map ((+) 1) in f

At this point, f is still a function, so Rex can keep it “overloaded”.

Now apply it to a list:

let f = map ((+) 1) in f [1, 2, 3]

At this call site, f must be List i32 -> List i32, so Rex selects Functor List.

Contrast: ambiguous non-function values

Some overloaded values are ambiguous if you don’t force a type. For example, pure 1 could be a List i32, Option i32, Result i32 e, etc.

Fix it by forcing a type:

let x: Option i32 = pure 1 in x

Worked examples

Example: mapping over Err

Problem: verify that map does not change the error branch.

map ((+) 1) (Err "boom")

Why this works: Functor (Result e) maps only the Ok value, leaving Err unchanged.

Example: one g, list and option

Problem: define g = map (\x -> x * x) once and apply it to multiple containers.

let g = map (\x -> x * x) in
  (g [1, 2, 3], g (Some 4))

Why this works: instance resolution for map is deferred until each concrete call site.

Example: fixing ambiguous pure 1

Problem: choose a concrete container for pure 1.

let x: Option i32 = pure 1 in x

Why this works: the annotation forces pure to use the Applicative Option instance.

Example: Option pipelines (Applicative + Monad)

Option a represents “a value that might not exist”.

Goal

Write a multi-step computation that:

• fails early by producing None
• otherwise returns a final value wrapped in Some

Then rewrite it in three styles:

1. plain match
2. bind chaining (monadic)
3. ap application (applicative)

Applicative: apply a wrapped function

ap (Some ((*) 2)) (Some 21)

If either side is None, the result is None.

Monad: sequence steps with bind

let
  step1 = \x -> if x < 0 then None else Some (x + 1),
  step2 = \x -> Some (x * 2)
in
  bind step2 (bind step1 (Some 10))

Refactoring tip

If you have many steps, name them:

let
  step1 = \x -> if x < 0 then None else Some (x + 1),
  step2 = \x -> Some (x * 2),
  run = \x -> bind step2 (bind step1 x)
in
  run (Some 10)

The same logic using match

bind is convenience. Under the hood, it’s the same “if None, stop” flow you would write with match:

let
  step1 = \x -> if x < 0 then None else Some (x + 1),
  step2 = \x -> Some (x * 2)
in
  match (Some 10) with {
    case None -> None;
    case Some v1 ->
      match (step1 v1) with {
        case None -> None;
        case Some v2 -> step2 v2;
      };
  }

When to use ap vs bind

• Use ap when you have independent optional pieces and want to apply a function if all exist.
• Use bind when the next step depends on the previous result.

Worked examples

Example: fail step1 on x == 0 too

Problem: update step1 so non-positive input fails.

let
  step1 = \x ->
    if x < 0 then None else
    if x == 0 then None else
      Some (x + 1)
in
  (step1 10, step1 0, step1 (0 - 1))

Why this works: the additional guard handles zero before success.

Example: add2opt via ap and pure

Problem: add two optional integers when both are present.

let
  add2opt = \ox oy -> ap (ap (pure (\x y -> x + y)) ox) oy
in
  (add2opt (Some 1) (Some 2), add2opt None (Some 2))

Why this works: pure lifts the function, then each ap applies one argument inside Option.

Example: validate list values with filter_map

Problem: keep only non-negative values and increment them.

let
  validate = \x -> if x < 0 then None else Some (x + 1)
in
  filter_map validate [3, (0 - 1), 0, 5]

Why this works: filter_map drops None results and unwraps Some values into the output list.

Example: Result workflows

Result a e short-circuits on Err.

Goal

Model a computation that can fail with a useful error, while keeping “happy path” code easy to read.

let
  step1 = \x -> if x < 0 then Err "negative" else Ok (x + 1),
  step2 = \x -> Ok (x * 2)
in
  ( bind step2 (bind step1 (Ok 10))
  , bind step2 (bind step1 (Ok (0 - 1)))
  )

What to notice

• When step1 returns Err, the second bind is skipped.
• This lets you write “happy path” code without deeply nested match.

Step-by-step: name the pipeline

let
  step1 = \x -> if x < 0 then Err "negative" else Ok (x + 1),
  step2 = \x -> Ok (x * 2),
  run = \x -> bind step2 (bind step1 x)
in
  (run (Ok 10), run (Ok (0 - 1)))

map vs bind

Use map when your function does not fail and does not change the container:

map ((+) 1) (Ok 41)

Use bind when your function returns another Result (and might fail):

bind (\x -> if x < 0 then Err "negative" else Ok x) (Ok 1)

Worked examples

Example: fail step2 when value is too large

Problem: make the second step return Err above a threshold.

let
  step1 = \x -> if x < 0 then Err "negative" else Ok (x + 1),
  step2 = \x -> if x > 20 then Err "too-large" else Ok (x * 2),
  run = \x -> bind step2 (bind step1 x)
in
  (run (Ok 10), run (Ok 25))

Why this works: bind short-circuits on either error source, including the new step2 condition.

Example: custom error ADT

Problem: replace string errors with structured errors.

type Err = Negative | TooLarge;

let
  step1 = \x -> if x < 0 then Err Negative else Ok (x + 1),
  step2 = \x -> if x > 20 then Err TooLarge else Ok (x * 2),
  run = \x -> bind step2 (bind step1 x)
in
  (run (Ok 10), run (Ok 25), run (Ok (0 - 1)))

Why this works: error constructors carry precise machine-readable failure categories.

Example: and_then synonym

Problem: define a helper that reads like “then”.

let
  and_then = \mx f -> bind f mx,
  safe_inc = \x -> if x < 0 then Err "negative" else Ok (x + 1)
in
  and_then (Ok 1) safe_inc

Why this works: and_then is just argument-reordered bind, so behavior is identical.

Example: Custom Show type class

This mirrors rex-cli/examples/typeclasses_custom_show.rex.

Goal

Define your own show-printing API that turns values into String without baking formatting into every call site.

We’ll build it up in layers:

1. define the class
2. add a base instance (i32)
3. add a structured type (Point)
4. (optional) add a container instance (List a)

class DemoShow a where {
  demo_show : a -> String;
}
type Point = Point { x: i32, y: i32 };

instance DemoShow i32 where {
  demo_show = \_ -> "<i32>";
}
instance DemoShow Point where {
  demo_show = \p -> "Point(" + demo_show p.x + ", " + demo_show p.y + ")";
}
demo_show (Point { x = 1, y = 2 })

Extending it

Add an instance DemoShow (List a) <= DemoShow a (see rex-cli/examples/typeclasses_custom_show.rex) and call demo_show [Point { x = 1, y = 2 }].

A worked DemoShow (List a) instance

Here is the list instance from the repo example, with commentary:

class DemoShow a where {
  demo_show : a -> String;
}
instance DemoShow i32 where {
  demo_show = \_ -> "<i32>";
}
instance<a> DemoShow (List a) <= DemoShow a where {
  demo_show = \xs ->
    let
      step = \out x ->
        if out == "["
          then out + demo_show x
          else out + ", " + demo_show x,
      out = foldl step "[" xs
    in
      out + "]";
}

Why the <= DemoShow a constraint?

Because the implementation calls demo_show x for list elements, so it requires DemoShow a.

Worked examples

Example: use "; " as the list separator

Problem: format list output with semicolons.

class DemoShow a where {
  demo_show : a -> String;
}
instance DemoShow i32 where {
  demo_show = \_ -> "<i32>";
}
instance<a> DemoShow (List a) <= DemoShow a where {
  demo_show = \xs ->
    let
      step = \out x ->
        if out == "["
          then out + demo_show x
          else out + "; " + demo_show x,
      out = foldl step "[" xs
    in
      out + "]";
}
demo_show [1, 2, 3]

Why this works: only the separator string changed; the fold structure stays the same.

Example: DemoShow Bool

Problem: add show-print support for booleans.

class DemoShow a where {
  demo_show : a -> String;
}
instance DemoShow Bool where {
  demo_show = \b -> if b then "true!" else "false!";
}
(demo_show true, demo_show false)

Why this works: the instance defines one method body specialized to Bool.

Example: DemoShow (Option a)

Problem: print Some(...) and None for options.

class DemoShow a where {
  demo_show : a -> String;
}
instance DemoShow i32 where {
  demo_show = \_ -> "<i32>";
}
instance<a> DemoShow (Option a) <= DemoShow a where {
  demo_show = \ox ->
    match ox with {
      case Some x -> "Some(" + demo_show x + ")";
      case None -> "None";
    };
}
(demo_show (Some 1), demo_show None)

Why this works: pattern matching distinguishes constructors and delegates formatting of payloads.

Example: Custom Size type class

This mirrors rex-cli/examples/typeclasses_custom_size.rex.

Goal

Use a type class to define a common “size” operation across different data types, without hard-coding the type at every call site.

class Size a where {
  size : a -> i32;
}
type Blob = Blob { bytes: List i32 };

instance<t> Size (List t) where {
  size = \xs ->
    match xs with {
      case Empty -> 0;
      case Cons _ t -> 1 + size t;
    };
}
instance Size Blob where {
  size = \b -> size b.bytes;
}
size (Blob { bytes = [1, 2, 3, 4] })

What this demonstrates

• defining a class with one method,
• writing an instance for a prelude type (List),
• writing an instance for your own ADT (Blob),
• using match for recursion.

Calling size generically

Once you have a class, you can write functions that work for any type that has an instance:

class Size a where {
  size : a -> i32;
}
instance<t> Size (List t) where {
  size = \xs ->
    match xs with {
      case Empty -> 0;
      case Cons _ t -> 1 + size t;
    };
}
let
  bigger<a>: a -> i32 = \(x: a) where Size a -> size x + 1
in
  bigger [1, 2, 3]

The where Size a constraint says: “this function is valid as long as Size a exists”.

Worked examples

Example: is_empty

Problem: write a generic emptiness check from size.

class Size a where {
  size : a -> i32;
}
instance<t> Size (List t) where {
  size = \xs ->
    match xs with {
      case Empty -> 0;
      case Cons _ t -> 1 + size t;
    };
}
let
  is_empty<a>: a -> Bool = \(x: a) where Size a -> size x == 0
in
  (is_empty ([] is List i32), is_empty [1, 2, 3])

Why this works: any type with a Size instance can reuse the same is_empty logic.

Example: Blob with name

Problem: add a name field and keep size based on bytes only.

class Size a where {
  size : a -> i32;
}
instance<t> Size (List t) where {
  size = \xs ->
    match xs with {
      case Empty -> 0;
      case Cons _ t -> 1 + size t;
    };
}
type Blob = Blob { name: String, bytes: List i32 };

instance Size Blob where {
  size = \b -> size b.bytes;
}
size (Blob { name = "payload", bytes = [1, 2, 3, 4] })

Why this works: Size Blob delegates to the bytes list, so metadata does not affect size.

Example: total_size

Problem: sum sizes of a list of values.

class Size a where {
  size : a -> i32;
}
instance<t> Size (List t) where {
  size = \xs ->
    match xs with {
      case Empty -> 0;
      case Cons _ t -> 1 + size t;
    };
}
let
  total_size = \(xs: List a) where Size a ->
    foldl (\acc x -> acc + size x) 0 xs
in
  total_size [[1, 2], [], [3]]

Why this works: foldl accumulates per-element sizes using the shared Size a method.

Example: List Helpers

List-specific helpers complement the generic map, filter, folds, and Sequence operations. They use u64 positions and return Option when indexing or slicing can fail.

Safe access

( list_get 1 [10, 20, 30]
, list_get 3 [10, 20, 30]
, list_slice 1 3 [10, 20, 30]
, list_slice 3 1 [10, 20, 30]
)

list_get uses a zero-based index. list_slice uses a half-open range and returns None when either bound is invalid or the end precedes the start.

Constructing and reshaping lists

( list_reverse [1, 2, 3]
, list_concat [[1, 2], [], [3, 4]]
, list_repeat 3 "rex"
)

list_concat removes exactly one layer of nesting. list_repeat 0 value returns an empty list.

Searching

let even = \x -> x % 2 == 0 in
( list_any even [1, 3, 4, 5]
, list_all even [2, 4, 6]
, list_find even [1, 3, 4, 6]
, list_find_index even [1, 3, 4, 6]
, list_count even [1, 2, 3, 4, 5, 6]
)

The any, all, and find helpers inspect elements from left to right and stop when their answer is known. The find helpers return the first match. On an empty list, list_any is false, list_all is true, and both find helpers return None.

Partitioning

list_partition (\x -> x < 0) [3, negate 1, 0, negate 4, 2]

The first output list contains matching elements and the second contains rejected elements. Both retain their relative order from the input.

Example: Small Standard Module Helpers

It’s common to build small helpers with let and reuse them.

Goal

Practice building tiny “glue” functions that keep your code readable, especially when composing many operations.

let
  compose = \f g x -> f (g x),
  inc = \x -> x + 1,
  double = \x -> x * 2,
  inc_then_double = compose double inc
in
  inc_then_double 10

Worked example: double_then_inc

Problem: define double_then_inc and show it differs from inc_then_double.

let
  compose = \f g x -> f (g x),
  inc = \x -> x + 1,
  double = \x -> x * 2,
  inc_then_double = compose double inc,
  double_then_inc = compose inc double
in
  (inc_then_double 10, double_then_inc 10)

Why this works: function composition order changes the final result (22 vs 21).

A more “pipeline” style

Sometimes it’s clearer to read left-to-right:

let
  pipe = \x f -> f x,
  pipe2 = \x f g -> g (f x),
  inc = \x -> x + 1,
  double = \x -> x * 2
in
  pipe2 10 inc double

This is the same logic as double (inc 10), just easier to extend when you have many steps.

Worked examples

Example: pipe3

Problem: apply three transforms in left-to-right style.

let
  pipe3 = \x f g h -> h (g (f x)),
  inc = \x -> x + 1,
  double = \x -> x * 2,
  square = \x -> x * x
in
  pipe3 3 inc double square

Why this works: each function consumes the previous output, so the pipeline is explicit.

Example: compose square then add one

Problem: build a reusable function that squares and then increments.

let
  compose = \f g x -> f (g x),
  square = \x -> x * x,
  add1 = \x -> x + 1,
  square_then_add1 = compose add1 square
in
  square_then_add1 5

Why this works: compose add1 square creates \x -> add1 (square x).

Example: map a composed function

Problem: combine map with composition for list transforms.

let
  compose = \f g x -> f (g x),
  square = \x -> x * x,
  add1 = \x -> x + 1,
  square_then_add1 = compose add1 square
in
  map square_then_add1 [1, 2, 3, 4]

Why this works: one composed function encapsulates the per-element transform applied by map.

Mini Project: Validating and Transforming Records

This example combines records, match, and Result.

Goal

Build a small “workflow” in Rex:

1. validate a User
2. transform it (birthday)
3. return either a useful error or the transformed user

This is a pattern you can scale up: each step is a function returning a Result, and you connect steps with bind.

type User = User { name: String, age: i32 };

let
  validate = \u ->
    if u.age < 0
      then Err "age must be non-negative"
      else Ok u,
  birthday = \u -> { u with { age = u.age + 1 } }
in
  bind (\u -> Ok (birthday u)) (validate (User { name = "Ada", age = 36 }))

Worked extensions

Example: update birthday to change name too

Problem: increment age and append "!" to the user name in one transform.

type User = User { name: String, age: i32 };

let
  birthday = \u ->
    { u with
        { age = u.age + 1
        , name = u.name + "!"
        }
    }
in
  birthday (User { name = "Ada", age = 36 })

Why this works: one record update can set multiple fields at once.

Example: reject empty names during validation

Problem: make validation fail when name == "".

type User = User { name: String, age: i32 };

let
  validate = \u ->
    if u.age < 0 then Err "age must be non-negative" else
    if u.name == "" then Err "name must be non-empty" else
      Ok u
in
  ( validate (User { name = "Ada", age = 36 })
  , validate (User { name = "", age = 36 })
  )

Why this works: the second guard introduces an additional failure branch before success.

Example: structured error ADT

Problem: replace free-form strings with typed error constructors.

type UserError = NegativeAge | EmptyName;
type User = User { name: String, age: i32 };

let
  validate = \u ->
    if u.age < 0 then Err NegativeAge else
    if u.name == "" then Err EmptyName else
      Ok u
in
  validate (User { name = "", age = 36 })

Why this works: callers can pattern-match on error constructors without string parsing.

A worked “structured error” version

Instead of strings, define an error ADT:

type UserError = NegativeAge | EmptyName;
type User = User { name: String, age: i32 };

let
  validate = \u ->
    if u.age < 0 then Err NegativeAge else
    if u.name == "" then Err EmptyName else
      Ok u,
  birthday = \u -> { u with { age = u.age + 1 } },
  run = \u -> bind (\ok -> Ok (birthday ok)) (validate u)
in
  ( run (User { name = "Ada", age = 36 })
  , run (User { name = "", age = 36 })
  , run (User { name = "Ada", age = (0 - 1) })
  )

What to notice

• validate returns early with the first error it finds.
• run uses bind to only call birthday when validation succeeded.

Worked examples

Example: add an upper-age validation rule

Problem: reject ages greater than 150.

type UserError = NegativeAge | EmptyName | TooOld;
type User = User { name: String, age: i32 };

let
  validate = \u ->
    if u.age < 0 then Err NegativeAge else
    if u.age > 150 then Err TooOld else
    if u.name == "" then Err EmptyName else
      Ok u
in
  ( validate (User { name = "Ada", age = 36 })
  , validate (User { name = "Ada", age = 200 })
  )

Why this works: the additional guard catches out-of-range ages before success.

Example: chain a second transform step with bind

Problem: run two transforms (birthday then normalize_name) after validation.

type User = User { name: String, age: i32 };

let
  validate = \u -> if u.age < 0 then Err "negative-age" else Ok u,
  birthday = \u -> Ok ({ u with { age = u.age + 1 } }),
  normalize_name = \u -> Ok ({ u with { name = u.name + "!" } }),
  run = \u ->
    bind normalize_name
      (bind birthday
        (validate u))
in
  run (User { name = "Ada", age = 36 })

Why this works: each bind feeds a successful result into the next transform.

Example: split validation into smaller validators

Problem: compose independent validators with bind.

type User = User { name: String, age: i32 };

let
  check_age = \u -> if u.age < 0 then Err "negative-age" else Ok u,
  check_name = \u -> if u.name == "" then Err "empty-name" else Ok u,
  validate = \u -> bind check_name (check_age u)
in
  ( validate (User { name = "Ada", age = 36 })
  , validate (User { name = "", age = 36 })
  )

Why this works: each validator has the same User -> Result User e shape, so they compose cleanly.

Interactive Demos

These demos are meant to be edited and run directly in the docs.

• Factorial — classic recursion over natural numbers
• Fibonacci — recursive sequence generation
• Merge Sort — classic divide-and-conquer sorting
• Binary Search Tree — insertion and lookup in a recursive ADT
• Expression Evaluator — evaluate a tiny arithmetic AST
• Dijkstra Lite — shortest-path relaxation on a tiny weighted graph
• 0/1 Knapsack — dynamic-programming row updates
• Union-Find — disjoint-set connectivity on a small graph
• Prefix Parser + Evaluator — recursive-descent parsing of prefix tokens
• Topological Sort — Kahn-style ordering on a DAG
• N-Queens — backtracking with diagonal pruning

Demo: Factorial

This demo computes n! using direct recursion: it multiplies n by the factorial of n - 1 until it reaches the base case 0, which returns 1. It is a minimal example of structural recursion over integers and shows how a simple mathematical definition maps directly to Rex function syntax.

Related reading: Factorial.

The implementation is centered on fact, which uses an if expression to separate the base case from the recursive case. The final line evaluates fact 6, so the output is a single integer result; this keeps the demo focused on call structure and termination rather than data modeling.

fn fact : i32 -> i32 = \n ->
  if n == 0
  then 1
  else n * fact (n - 1);

fact 6

Demo: Fibonacci

This demo generates Fibonacci numbers with the classic recursive recurrence: each value is the sum of the previous two, with base cases at 0 and 1. It illustrates branching recursion and builds a small prefix of the sequence so you can see the growth pattern directly in the output.

Related reading: Fibonacci number.

The fib function mirrors the mathematical recurrence directly: when n is 0 or 1 it returns immediately, otherwise it performs two recursive calls and adds their results. Instead of evaluating just one input, the demo computes a list from fib 0 through fib 10, which makes it easy to confirm correctness across multiple cases in one run.

fn fib : i32 -> i32 = \n ->
  if n <= 1
  then n
  else fib (n - 1) + fib (n - 2);

[fib 0, fib 1, fib 2, fib 3, fib 4, fib 5, fib 6, fib 7, fib 8, fib 9, fib 10]

Demo: Merge Sort

This demo implements merge sort, a divide-and-conquer algorithm that splits a list into halves, recursively sorts each half, and then merges the two sorted results. The implementation highlights recursive split_alt and merge helpers together with the prelude’s cmp function, and demonstrates how recursive decomposition can produce deterministic, stable ordering over immutable lists.

Related reading: Merge sort.

cmp returns the prelude’s Ordering ADT (Less, Equal, or Greater), and split_alt peels off pairs to partition input into two sublists without mutation. mergesort handles the empty and singleton base cases, then recursively sorts both halves and combines them with merge, which pattern-matches on two lists and emits the smaller head first. On equality, it takes from the left sublist first to keep the sort stable.

fn split_alt : List i32 -> (List i32, List i32) = \xs ->
  match xs with {
    case [] -> ([], []);
    case [x] -> ([x], []);
    case x::y::rest ->
      let (xs1, ys1) = split_alt rest in (Cons x xs1, Cons y ys1);
  };

fn merge : List i32 -> List i32 -> List i32 = \xs ys ->
  match (xs, ys) with {
    case ([], _) -> ys;
    case (_, []) -> xs;
    case (x::xt, y::yt) ->
      match (cmp x y) with {
        case Less -> Cons x (merge xt ys);
        case Equal -> Cons x (merge xt ys);
        case Greater -> Cons y (merge xs yt);
      };
  };

fn mergesort : List i32 -> List i32 = \xs ->
  match xs with {
    case [] -> [];
    case [x] -> [x];
    case _ ->
      let (left, right) = split_alt xs in
      merge (mergesort left) (mergesort right);
  };

let
  input = [9, 1, 7, 3, 2, 8, 6, 4, 5]
in
  mergesort input

Demo: Binary Search Tree

This demo builds and queries a binary search tree, where values smaller than a node go left and larger values go right. It shows insertion, membership testing, and size calculation over a custom recursive ADT, illustrating how ordered data structures can be expressed with pure pattern-matching functions.

Related reading: Binary search tree.

The Tree type has Empty and Node constructors, and each operation recursively follows tree structure. insert descends left or right based on key order and rebuilds the path back up, contains follows the same branching logic to test membership, and size traverses both subtrees to count nodes; the final let block builds an example tree and returns a tuple of summary queries.

type Tree = Empty | Node { key: i32, left: Tree, right: Tree };

fn insert : i32 -> Tree -> Tree = \k t ->
  match t with {
    case Empty -> Node { key = k, left = Empty, right = Empty };
    case Node {key, left, right} ->
      if k < key then
        Node { key = key, left = insert k left, right = right }
      else if k > key then
        Node { key = key, left = left, right = insert k right }
      else
        t;
  };

fn contains : i32 -> Tree -> Bool = \k t ->
  match t with {
    case Empty -> false;
    case Node {key, left, right} ->
      if k == key then true
      else if k < key then contains k left
      else contains k right;
  };

fn size : Tree -> i32 = \t ->
  match t with {
    case Empty -> 0;
    case Node {left, right} -> 1 + size left + size right;
  };

let
  t0: Tree = Empty
in
  let
    t1 = insert 7 (insert 2 (insert 9 (insert 1 (insert 5 t0)))),
    t2 = insert 8 t1
  in
    (size t2, contains 5 t2, contains 4 t2)

Demo: Expression Evaluator

This demo evaluates arithmetic expressions represented as an AST with constructors for literals, addition, multiplication, and negation. Alongside evaluation, it computes expression depth and performs a small simplification pass, showing how one tree structure can support multiple independent recursive analyses and transformations.

Related reading: Abstract syntax tree.

The code defines one ADT (Expr) and then reuses it across three traversals: eval computes numeric meaning, depth computes structural height, and simplify_once applies a local rewrite rule for double negation. In the final expression block, two sample trees are built, one is simplified once, and the output tuple shows evaluation and depth results side-by-side.

type Expr = Lit i32 | Add Expr Expr | Mul Expr Expr | Neg Expr;

fn eval : Expr -> i32 = \e ->
  match e with {
    case Lit n -> n;
    case Add a b -> eval a + eval b;
    case Mul a b -> eval a * eval b;
    case Neg x -> 0 - eval x;
  };

fn depth : Expr -> i32 = \e ->
  match e with {
    case Lit _ -> 1;
    case Add a b ->
      if depth a > depth b then 1 + depth a else 1 + depth b;
    case Mul a b ->
      if depth a > depth b then 1 + depth a else 1 + depth b;
    case Neg x -> 1 + depth x;
  };

fn simplify_once : Expr -> Expr = \e ->
  match e with {
    case Neg (Neg x) -> x;
    case _ -> e;
  };

let
  expr1 = Add (Lit 2) (Mul (Lit 3) (Lit 4)),
  expr2 = Neg (Neg (Add (Lit 5) (Mul (Lit 1) (Lit 9))))
in
  let simplified = simplify_once expr2 in
  (eval expr1, depth expr1, eval simplified)

Demo: Dijkstra Lite

This demo models a minimal shortest-path problem and applies the core relaxation idea behind Dijkstra-style algorithms: compare a direct edge with an indirect path through an intermediate node and keep the smaller distance. It uses a small Dist ADT (Inf or Finite) to make unreachable and reachable cases explicit and type-safe.

Related reading: Dijkstra’s algorithm.

add_weight and min_dist isolate the distance algebra, so shortest_a_to_b can read clearly as “direct path versus via-C path, then pick minimum.” The sample graphs in the final let block exercise both outcomes: one where routing through C wins and one where the direct edge is best, with as_i32 converting the ADT into plain output numbers for display.

type Dist = Inf | Finite i32;
type Graph = Graph { ab: i32, ac: i32, cb: i32 };

fn add_weight : Dist -> i32 -> Dist = (\d w ->
  match d with {
    case Inf -> Inf;
    case Finite x -> Finite (x + w);
  }
);

fn min_dist : Dist -> Dist -> Dist = (\a b ->
  match (a, b) with {
    case (Inf, x) -> x;
    case (x, Inf) -> x;
    case (Finite x, Finite y) ->
      if x <= y then Finite x else Finite y;
  }
);

fn shortest_a_to_b : Graph -> Dist = (\g ->
  let
    direct = Finite g.ab,
    via_c = add_weight (Finite g.ac) g.cb
  in
    min_dist direct via_c
);

fn as_i32 : Dist -> i32 = (\d ->
  match d with {
    case Inf -> -1;
    case Finite x -> x;
  }
);

let
  g1 = Graph { ab = 10, ac = 3, cb = 4 },
  g2 = Graph { ab = 5, ac = 9, cb = 9 },
  d1 = shortest_a_to_b g1,
  d2 = shortest_a_to_b g2
in
  (as_i32 d1, as_i32 d2)

Demo: 0/1 Knapsack

This demo solves the 0/1 knapsack optimization problem with dynamic programming: each item can be taken at most once, and the algorithm computes the best achievable value for every capacity from 0 to max_cap. The table is represented as immutable rows, and each new row is derived from the previous one by choosing between “take” and “skip” for the current item.

Related reading: Knapsack problem.

zeros initializes the base DP row, build_row computes one new row for a single item, and go folds this process across the full item list. For each capacity, build_row compares without (skip item) and with_item (take item plus best compatible remainder), then stores the maximum; solve returns the final cell at max_cap.

type Item = Item { w: i32, v: i32 };

fn nth : List i32 -> i32 -> i32 = \xs i ->
  match xs with {
    case [] -> 0;
    case x::rest ->
      if i == 0 then x else nth rest (i - 1);
  };

fn zeros : i32 -> i32 -> List i32 = \i max_cap ->
  if i > max_cap then [] else Cons 0 (zeros (i + 1) max_cap);

fn build_row : Item -> List i32 -> i32 -> i32 -> List i32 = \item prev cap max_cap ->
  if cap > max_cap then
    []
  else
    let
      without = nth prev cap,
      with_item =
        if item.w <= cap then
          item.v + nth prev (cap - item.w)
        else
          0,
      best = if without >= with_item then without else with_item
    in
      Cons best (build_row item prev (cap + 1) max_cap);

fn go : List Item -> List i32 -> i32 -> List i32 = \remaining row max_cap ->
  match remaining with {
    case [] -> row;
    case item::rest ->
      let next = build_row item row 0 max_cap in
      go rest next max_cap;
  };

fn solve : List Item -> i32 -> i32 = \items max_cap ->
  nth (go items (zeros 0 max_cap) max_cap) max_cap;

let
  items = [
    Item { w = 2, v = 3 },
    Item { w = 3, v = 4 },
    Item { w = 4, v = 5 },
    Item { w = 5, v = 8 }
  ],
  cap_5 = solve items 5,
  cap_8 = solve items 8
in
  (cap_5, cap_8)

Demo: Union-Find

This demo implements core union-find operations for tracking connected components in a small graph. It maintains parent links, finds set representatives, and merges sets with union, then checks connectivity; together these operations demonstrate how incremental edge additions can be answered with near-constant-time component queries.

Related reading: Disjoint-set data structure.

get_parent and set_parent provide indexed access over a fixed-size parent record, while find follows parent pointers recursively until it reaches a representative. union links one representative to another when sets differ, and connected compares representatives; the final block performs a few unions and returns both connectivity checks and representatives to show resulting components.

type UF = UF { p0: i32, p1: i32, p2: i32, p3: i32, p4: i32 };

fn get_parent : UF -> i32 -> i32 = \uf x ->
  if x == 0 then uf.p0
  else if x == 1 then uf.p1
  else if x == 2 then uf.p2
  else if x == 3 then uf.p3
  else uf.p4;

fn set_parent : UF -> i32 -> i32 -> UF = \uf x p ->
  if x == 0 then { uf with { p0 = p } }
  else if x == 1 then { uf with { p1 = p } }
  else if x == 2 then { uf with { p2 = p } }
  else if x == 3 then { uf with { p3 = p } }
  else { uf with { p4 = p } };

fn find : UF -> i32 -> i32 = \uf x ->
  let px = get_parent uf x in
  if px == x then x else find uf px;

fn union : UF -> i32 -> i32 -> UF = \uf a b ->
  let
    ra = find uf a,
    rb = find uf b
  in
    if ra == rb then uf else set_parent uf rb ra;

fn connected : UF -> i32 -> i32 -> Bool = \uf a b -> find uf a == find uf b;

let
  uf0 = UF { p0 = 0, p1 = 1, p2 = 2, p3 = 3, p4 = 4 },
  uf1 = union uf0 0 1,
  uf2 = union uf1 1 2,
  uf3 = union uf2 3 4
in
  (
    connected uf3 0 2,
    connected uf3 0 4,
    find uf3 2,
    find uf3 4
  )

Demo: Prefix Parser + Evaluator

This demo performs recursive-descent parsing over a prefix token stream to build an expression tree, then evaluates that tree. It separates syntax (Tok) from semantics (Expr) and returns both the parsed expression and unconsumed tokens, which is a common parser design for composing larger grammars.

Related reading: Polish notation and Recursive descent parser.

parse_expr is the parser entrypoint and consumes tokens according to constructor shape: numbers produce leaf nodes, while operators recursively parse the required subexpressions. eval then interprets the produced AST, and is_empty checks whether parsing consumed all tokens; the two sample token streams demonstrate both parsing and evaluation in one result tuple.

type Tok = TNum i32 | TPlus | TMul | TNeg;
type Expr = Num i32 | Add Expr Expr | Mul Expr Expr | Neg Expr;

fn parse_expr : List Tok -> (Expr, List Tok) = \toks ->
  match toks with {
    case [] -> (Num 0, []);
    case TNum n::rest -> (Num n, rest);
    case TPlus::rest ->
      let
        (lhs, rest1) = parse_expr rest,
        (rhs, rest2) = parse_expr rest1
      in
        (Add lhs rhs, rest2);
    case TMul::rest ->
      let
        (lhs, rest1) = parse_expr rest,
        (rhs, rest2) = parse_expr rest1
      in
        (Mul lhs rhs, rest2);
    case TNeg::rest ->
      let (inner, rest1) = parse_expr rest in
      (Neg inner, rest1);
  };

fn eval : Expr -> i32 = \expr ->
  match expr with {
    case Num n -> n;
    case Add a b -> eval a + eval b;
    case Mul a b -> eval a * eval b;
    case Neg x -> 0 - eval x;
  };

fn is_empty<a> : List a -> Bool = \xs ->
  match xs with {
    case [] -> true;
    case _::_ -> false;
  };

let
  toks1 = [TPlus, TNum 2, TMul, TNum 3, TNum 4],
  toks2 = [TPlus, TNeg, TNum 3, TNum 10],
  (ast1, rest1) = parse_expr toks1,
  (ast2, rest2) = parse_expr toks2
in
  (eval ast1, is_empty rest1, eval ast2, is_empty rest2)

Demo: Topological Sort (Kahn Style)

This demo computes a topological ordering of a directed acyclic graph using a Kahn-style process: repeatedly select nodes with zero in-degree, output them, and remove their outgoing edges. It demonstrates dependency resolution in graph form and returns an empty list when edges remain but no valid next node exists.

Related reading: Topological sorting.

The helpers break the algorithm into pure list operations: in_degree counts incoming edges, remove_outgoing deletes edges from a chosen node, and enqueue_zeros updates the processing queue with newly unlocked nodes. kahn drives the main loop by consuming the queue and accumulating output order, with a final reversal because nodes are prepended during recursion.

type Node = A | B | C | D;
type Edge = Edge Node Node;

fn node_eq : Node -> Node -> Bool = \a b ->
  match (a, b) with {
    case (A, A) -> true;
    case (B, B) -> true;
    case (C, C) -> true;
    case (D, D) -> true;
    case _ -> false;
  };

fn contains : List Node -> Node -> Bool = \xs x ->
  match xs with {
    case [] -> false;
    case y::ys -> if node_eq y x then true else contains ys x;
  };

fn append : List Node -> List Node -> List Node = \xs ys ->
  match xs with {
    case [] -> ys;
    case h::t -> Cons h (append t ys);
  };

fn reverse_go : List Node -> List Node -> List Node = \rest acc ->
  match rest with {
    case [] -> acc;
    case h::t -> reverse_go t (Cons h acc);
  };

fn reverse : List Node -> List Node = \xs ->
  reverse_go xs [];

fn is_empty<a> : List a -> Bool = \xs ->
  match xs with {
    case [] -> true;
    case _::_ -> false;
  };

fn remove_outgoing : List Edge -> Node -> List Edge = \edges n ->
  match edges with {
    case [] -> [];
    case Edge from to::rest ->
      if node_eq from n then remove_outgoing rest n
      else Cons (Edge from to) (remove_outgoing rest n);
  };

fn in_degree : List Edge -> Node -> i32 = \edges n ->
  match edges with {
    case [] -> 0;
    case Edge from to::rest ->
      let tail = in_degree rest n in
      if node_eq to n then 1 + tail else tail;
  };

fn push_unique : List Node -> Node -> List Node = \queue n ->
  if contains queue n then queue else append queue [n];

fn enqueue_zeros : List Node -> List Node -> List Node -> List Edge -> List Node = \nodes queue seen edges ->
  match nodes with {
    case [] -> queue;
    case n::rest ->
      let queue1 =
        if contains seen n then
          queue
        else if in_degree edges n == 0 then
          push_unique queue n
        else
          queue
      in
        enqueue_zeros rest queue1 seen edges;
  };

fn kahn : List Node -> List Node -> List Node -> List Edge -> List Node -> List Node = \queue seen order edges nodes ->
  match queue with {
    case [] ->
      if is_empty edges then
        reverse order
      else
        [];
    case n::rest ->
      let
        edges1 = remove_outgoing edges n,
        seen1 = Cons n seen,
        queue1 = enqueue_zeros nodes rest seen1 edges1
      in
        kahn queue1 seen1 (Cons n order) edges1 nodes;
  };

let
  nodes = [A, B, C, D],
  edges = [Edge A B, Edge A C, Edge B D, Edge C D],
  initial = enqueue_zeros nodes [] [] edges
in
  kahn initial [] [] edges nodes

Demo: N-Queens Backtracking

This demo counts valid placements of queens on an N x N chessboard using backtracking with pruning. It places one queen per row, rejects positions that share a column or diagonal with prior queens, and recursively explores only safe continuations, which makes it a compact example of constraint search.

Related reading: N-queens problem.

is_safe checks a candidate column against previously placed queens, carrying a diagonal distance counter so both diagonal directions can be tested with abs_i32. try_cols iterates candidate columns within a row and accumulates solution counts, while count_from advances to the next row after each safe placement; solve just seeds the recursion with row 0 and an empty placement list.

fn abs_i32 : i32 -> i32 = \x ->
  if x < 0 then 0 - x else x;

fn is_safe : i32 -> List i32 -> i32 -> Bool = \col placed dist ->
  match placed with {
    case [] -> true;
    case c::rest ->
      if col == c then
        false
      else if abs_i32 (col - c) == dist then
        false
      else
        is_safe col rest (dist + 1);
  };

fn count_from : i32 -> i32 -> List i32 -> i32 = \row n placed ->
  if row == n then
    1
  else
    try_cols row n placed 0;

fn try_cols : i32 -> i32 -> List i32 -> i32 -> i32 = \row n placed col ->
  if col == n then
    0
  else
    let rest = try_cols row n placed (col + 1) in
    if is_safe col placed 1 then
      count_from (row + 1) n (Cons col placed) + rest
    else
      rest;

fn solve : i32 -> i32 = \n ->
  count_from 0 n [];

(solve 4, solve 5)

Built-in types & functions

This page is auto-generated from the prelude source. Run cargo run -p rex-cli --bin gen_prelude_docs to refresh it.

Built-in Types

Reading Function Entries

Rex functions are curried, so f first second can be partially applied as f first. The Call paragraph gives every parameter a stable, descriptive name. The Type paragraph gives the inferred Rex type; type variables begin with an apostrophe. For overloaded functions, Available for lists the built-in types and type constructors that provide the operation.

Boolean Operations

Boolean operators combine two Bool values.

&&

Call: left && right

Type: Bool -> Bool -> Bool

Returns true only when both left and right are true.

||

Call: left || right

Type: Bool -> Bool -> Bool

Returns true when either left or right is true.

Comparison Operations

Equality is available for all listed equality-comparable types. Ordering operations are available for numbers, characters, and strings.

==

Call: left == right

Type: 'a -> 'a -> Bool

Available for: u8, u16, u32, u64, i8, i16, i32, i64, f32, f64, Bool, Char, String, UUID, Hash, DateTime, List 'a, Option 'a, Result 'a 'e

Returns true when left and right are equal. Lists, options, and results require their contained types to support equality.

!=

Call: left != right

Type: 'a -> 'a -> Bool

Available for: u8, u16, u32, u64, i8, i16, i32, i64, f32, f64, Bool, Char, String, UUID, Hash, DateTime, List 'a, Option 'a, Result 'a 'e

Returns true when left and right are not equal. Lists, options, and results require their contained types to support equality.

<

Call: left < right

Type: 'a -> 'a -> Bool

Available for: u8, u16, u32, u64, i8, i16, i32, i64, f32, f64, Char, String

Returns true when left is less than right.

<=

Call: left <= right

Type: 'a -> 'a -> Bool

Available for: u8, u16, u32, u64, i8, i16, i32, i64, f32, f64, Char, String

Returns true when left is less than or equal to right.

>

Call: left > right

Type: 'a -> 'a -> Bool

Available for: u8, u16, u32, u64, i8, i16, i32, i64, f32, f64, Char, String

Returns true when left is greater than right.

>=

Call: left >= right

Type: 'a -> 'a -> Bool

Available for: u8, u16, u32, u64, i8, i16, i32, i64, f32, f64, Char, String

Returns true when left is greater than or equal to right.

cmp

Call: cmp left right

Type: 'a -> 'a -> Ordering

Available for: u8, u16, u32, u64, i8, i16, i32, i64, f32, f64, Char, String

Returns Less, Equal, or Greater according to the ordering of left relative to right.

Ordering Values

cmp returns one of these Ordering values. The bare names are convenient aliases for the type-qualified constructors.

Ordering.Less

Call: Ordering.Less

Type: Ordering

The type-qualified Ordering value returned when the left value is less than the right value.

Ordering.Equal

Call: Ordering.Equal

Type: Ordering

The type-qualified Ordering value returned when two values are equal.

Ordering.Greater

Call: Ordering.Greater

Type: Ordering

The type-qualified Ordering value returned when the left value is greater than the right value.

Less

Call: Less

Type: Ordering

The Ordering value returned when the left value is less than the right value.

Equal

Call: Equal

Type: Ordering

The Ordering value returned when two values are equal.

Greater

Call: Greater

Type: Ordering

The Ordering value returned when the left value is greater than the right value.

Arithmetic and Aggregation

Arithmetic operators work on the numeric types listed for each operation. Some operations are also overloaded for lists or strings where noted.

zero

Call: zero

Type: 'a

Available for: List 'a, String, u8, u16, u32, u64, i8, i16, i32, i64, f32, f64

Returns the additive identity for the inferred result type.

one

Call: one

Type: 'a

Available for: u8, u16, u32, u64, i8, i16, i32, i64, f32, f64

Returns the multiplicative identity for the inferred result type.

+

Call: left + right

Type: 'a -> 'a -> 'a

Available for: List 'a, String, u8, u16, u32, u64, i8, i16, i32, i64, f32, f64

Adds left and right; for lists and strings, concatenates left with right.

-

Call: left - right

Type: 'a -> 'a -> 'a

Available for: u8, u16, u32, u64, i8, i16, i32, i64, f32, f64

Subtracts right from left.

*

Call: left * right

Type: 'a -> 'a -> 'a

Available for: u8, u16, u32, u64, i8, i16, i32, i64, f32, f64

Multiplies left by right.

/

Call: left / right

Type: 'a -> 'a -> 'a

Available for: u8, u16, u32, u64, i8, i16, i32, i64, f32, f64

Divides left by right.

%

Call: left % right

Type: 'a -> 'a -> 'a

Available for: u8, u16, u32, u64, i8, i16, i32, i64

Returns the remainder after dividing left by right.

negate

Call: negate value

Type: 'a -> 'a

Available for: i8, i16, i32, i64, f32, f64

Returns the additive inverse of value.

sum

Call: sum values

Type: 'f 'a -> 'a

Available for: List 'a and Option 'a, where 'a is a numeric type, String, or another List type

Combines all elements in values using addition, beginning with that element type’s additive identity.

mean

Call: mean values

Type: 'f 'a -> 'a

Available for: List f32, List f64, Option f32, and Option f64

Returns the arithmetic mean of values; raises an error when values is empty.

min

Call: min values

Type: 'f 'a -> 'a

Available for: List 'a and Option 'a, where 'a is a numeric type, Char, or String

Returns the least element in values according to its ordering; raises an error when values is empty.

max

Call: max values

Type: 'f 'a -> 'a

Available for: List 'a and Option 'a, where 'a is a numeric type, Char, or String

Returns the greatest element in values according to its ordering; raises an error when values is empty.

General Value Functions

Functions for constructing defaults, parsing strings, and rendering values.

default

Call: default

Type: 'a

Available for: Bool, u8, u16, u32, u64, i8, i16, i32, i64, f32, f64, Char, String, List 'a, Option 'a, Result 'a 'e

Returns the canonical default value for the inferred result type. For Result a e, the success type a must also have a default.

parse

Call: parse input

Type: String -> Option 'a

Available for: Bool, u8, u16, u32, u64, i8, i16, i32, i64, f32, f64, Char, UUID, Hash, DateTime

Attempts to convert input to the result type selected by context, returning Some value on success or None for malformed or out-of-range input.

show

Call: show value

Type: 'a -> String

Available for: Bool, u8, u16, u32, u64, i8, i16, i32, i64, f32, f64, Char, String, UUID, Hash, DateTime, List 'a, Option 'a, Result 'a 'e

Renders value as a human-readable string. Lists, options, and results require their contained types to be renderable.

Collection and Container Functions

Generic operations shared by lists, options, results, dictionaries, or strings. Check the availability list on each function.

length

Call: length value

Type: 'a -> u64

Available for: List 'a, Dict 'a, String

Returns the number of list elements, dictionary entries, or string Unicode scalar values in value.

map

Call: map transform container

Type: ('a -> 'b) -> 'f 'a -> 'f 'b

Available for: List, Option, Result 'e, Dict

Applies transform to every value in container while preserving its structure.

filter

Call: filter predicate container

Type: ('a -> Bool) -> 'f 'a -> 'f 'a

Available for: List, Option, Dict

Keeps each value in container for which predicate returns true.

filter_map

Call: filter_map transform container

Type: ('a -> Option 'b) -> 'f 'a -> 'f 'b

Available for: List, Option, Dict

Applies transform to each value in container and drops every result that is None.

foldl

Call: foldl step initial container

Type: ('b -> 'a -> 'b) -> 'b -> 't 'a -> 'b

Available for: List, Option

Strictly reduces container from left to right by applying step to the accumulator and each value, beginning with initial.

foldr

Call: foldr step initial container

Type: ('a -> 'b -> 'b) -> 'b -> 't 'a -> 'b

Available for: List, Option

Reduces container from right to left by applying step to each value and the accumulator, beginning with initial.

fold

Call: fold step initial container

Type: ('b -> 'a -> 'b) -> 'b -> 't 'a -> 'b

Available for: List, Option

Reduces container from left to right by applying step to the accumulator and each value, beginning with initial.

pure

Call: pure value

Type: 'a -> 'f 'a

Available for: List, Option, Result 'e

Wraps value in the inferred container type.

ap

Call: ap functions values

Type: 'f ('a -> 'b) -> 'f 'a -> 'f 'b

Available for: List, Option, Result 'e

Applies the wrapped functions in functions to the wrapped values in values.

bind

Call: bind transform container

Type: ('a -> 'm 'b) -> 'm 'a -> 'm 'b

Available for: List, Option, Result 'e

Applies transform to each successful value in container and flattens the resulting container layer.

or_else

Call: or_else fallback value

Type: ('f 'a -> 'f 'a) -> 'f 'a -> 'f 'a

Available for: List, Option, Result 'e

Returns value when it is non-empty, present, or successful; otherwise applies fallback to value.

List Functions

Construct, index, slice, and combine List values.

List.Empty

Call: List.Empty

Type: List 'a

The type-qualified empty list constructor.

List.Cons

Call: List.Cons head tail

Type: 'a -> List 'a -> List 'a

Constructs a non-empty list whose first element is head and whose remaining elements are tail.

Empty

Call: Empty

Type: List 'a

The empty list constructor.

Cons

Call: Cons head tail

Type: 'a -> List 'a -> List 'a

Constructs a non-empty list whose first element is head and whose remaining elements are tail.

list_get

Call: list_get index list

Type: u64 -> List 'a -> Option 'a

Returns the element at zero-based index, or None when index is out of bounds.

list_slice

Call: list_slice start end list

Type: u64 -> u64 -> List 'a -> Option (List 'a)

Returns the half-open range start..end, or None for invalid bounds.

list_reverse

Call: list_reverse list

Type: List 'a -> List 'a

Returns the elements of list in reverse order.

list_concat

Call: list_concat lists

Type: List (List 'a) -> List 'a

Concatenates the nested lists into one list while preserving their order.

list_repeat

Call: list_repeat count value

Type: u64 -> 'a -> List 'a

Returns a list containing count copies of value.

list_any

Call: list_any predicate list

Type: ('a -> Bool) -> List 'a -> Bool

Returns whether predicate is true for any element, stopping at the first true result.

list_all

Call: list_all predicate list

Type: ('a -> Bool) -> List 'a -> Bool

Returns whether predicate is true for every element, stopping at the first false result.

list_find

Call: list_find predicate list

Type: ('a -> Bool) -> List 'a -> Option 'a

Returns the first element for which predicate returns true, or None when no element matches.

list_find_index

Call: list_find_index predicate list

Type: ('a -> Bool) -> List 'a -> Option u64

Returns the zero-based index of the first matching element, or None when no element matches.

list_count

Call: list_count predicate list

Type: ('a -> Bool) -> List 'a -> u64

Returns the number of elements for which predicate returns true.

list_partition

Call: list_partition predicate list

Type: ('a -> Bool) -> List 'a -> (List 'a, List 'a)

Returns matching and non-matching elements as a pair of lists, preserving their relative order.

take

Call: take count list

Type: u64 -> 'f 'a -> 'f 'a

Available for: List

Returns at most the first count elements from list.

skip

Call: skip count list

Type: u64 -> 'f 'a -> 'f 'a

Available for: List

Drops the first count elements from list; when count exceeds its length, returns an empty list.

first

Call: first count list

Type: i32 -> List 'a -> List 'a

Returns the first count elements of list; raises an error when count is out of range.

last

Call: last count list

Type: i32 -> List 'a -> List 'a

Returns the last count elements of list; raises an error when count is out of range.

slice

Call: slice start end list

Type: i32 -> i32 -> List 'a -> List 'a

Returns elements in the half-open range start..end from list; raises an error for out-of-range bounds or when end < start.

zip

Call: zip left right

Type: 'f 'a -> 'f 'b -> 'f ('a, 'b)

Available for: List

Pairs elements from left and right by position, stopping when either list ends.

unzip

Call: unzip pairs

Type: 'f ('a, 'b) -> ('f 'a, 'f 'b)

Available for: List

Splits the list of pairs into a pair of lists containing their first and second components.

Dict Functions

Dictionary-specific operations. Keys are strings, dictionaries are immutable, and operations that modify a dictionary return a new value.

dict_empty

Call: dict_empty

Type: Dict 'a

Constructs an empty dictionary.

dict_singleton

Call: dict_singleton key value

Type: String -> 'a -> Dict 'a

Constructs a dictionary containing the single association from key to value.

dict_get

Call: dict_get key dictionary

Type: String -> Dict 'a -> Option 'a

Looks up key in dictionary, returning Some value when present or None when absent.

dict_has

Call: dict_has key dictionary

Type: String -> Dict 'a -> Bool

Returns whether dictionary contains key.

dict_insert

Call: dict_insert key value dictionary

Type: String -> 'a -> Dict 'a -> Dict 'a

Returns dictionary with key associated with value, replacing the previous value when the key exists.

dict_remove

Call: dict_remove key dictionary

Type: String -> Dict 'a -> Dict 'a

Returns dictionary without key.

dict_update

Call: dict_update key update dictionary

Type: String -> (Option 'a -> Option 'a) -> Dict 'a -> Dict 'a

Calls update with the optional current value for key; returning Some value inserts or replaces the entry, while returning None removes it.

dict_is_empty

Call: dict_is_empty dictionary

Type: Dict 'a -> Bool

Returns whether dictionary has no entries.

dict_keys

Call: dict_keys dictionary

Type: Dict 'a -> List String

Returns the keys from dictionary in lexicographic order.

dict_values

Call: dict_values dictionary

Type: Dict 'a -> List 'a

Returns the values from dictionary in lexicographic key order.

dict_entries

Call: dict_entries dictionary

Type: Dict 'a -> List (String, 'a)

Returns the key/value tuples from dictionary in lexicographic key order.

dict_from_entries

Call: dict_from_entries entries

Type: List (String, 'a) -> Dict 'a

Constructs a dictionary from entries; when a key occurs more than once, its later value wins.

dict_map

Call: dict_map transform dictionary

Type: ((String, 'a) -> (String, 'b)) -> Dict 'a -> Dict 'b

Applies transform to each (key, value) tuple in dictionary; later collisions in input-key order win.

dict_filter

Call: dict_filter predicate dictionary

Type: ((String, 'a) -> Bool) -> Dict 'a -> Dict 'a

Keeps the entries from dictionary for which predicate returns true; predicate receives each (key, value) tuple.

String Functions

String indexing and positions count Unicode scalar values, not UTF-8 bytes. Functions with selector or modifier arguments place those arguments before the input string.

string_get

Call: string_get index input

Type: u64 -> String -> Option Char

Returns the character at zero-based Unicode scalar index in input, or None when index is out of bounds.

string_slice

Call: string_slice start end input

Type: u64 -> u64 -> String -> Option String

Returns the half-open Unicode scalar range start..end from input, or None for invalid bounds.

string_contains

Call: string_contains needle haystack

Type: String -> String -> Bool

Returns whether haystack contains needle as a substring.

string_starts_with

Call: string_starts_with prefix input

Type: String -> String -> Bool

Returns whether input starts with prefix.

string_ends_with

Call: string_ends_with suffix input

Type: String -> String -> Bool

Returns whether input ends with suffix.

string_find

Call: string_find needle haystack

Type: String -> String -> Option u64

Finds needle in haystack, returning its first Unicode scalar index or None.

string_split

Call: string_split separator input

Type: String -> String -> List String

Splits input at each non-overlapping occurrence of separator.

string_join

Call: string_join separator parts

Type: String -> List String -> String

Joins parts, inserting separator between adjacent strings.

string_replace

Call: string_replace needle replacement input

Type: String -> String -> String -> String

Returns input with every non-overlapping occurrence of needle replaced by replacement.

string_trim

Call: string_trim input

Type: String -> String

Removes Unicode whitespace from both ends of input.

string_trim_start

Call: string_trim_start input

Type: String -> String

Removes Unicode whitespace from the start of input.

string_trim_end

Call: string_trim_end input

Type: String -> String

Removes Unicode whitespace from the end of input.

string_to_lower

Call: string_to_lower input

Type: String -> String

Converts input using the Unicode lowercase mapping.

string_to_upper

Call: string_to_upper input

Type: String -> String

Converts input using the Unicode uppercase mapping.

string_to_chars

Call: string_to_chars input

Type: String -> List Char

Returns the Unicode scalar values in input as a character list.

chars_to_string

Call: chars_to_string chars

Type: List Char -> String

Concatenates the Unicode scalar values in chars into a string.

string_to_utf8

Call: string_to_utf8 input

Type: String -> List u8

Encodes input as its UTF-8 byte sequence.

utf8_to_string

Call: utf8_to_string bytes

Type: List u8 -> Option String

Decodes bytes as UTF-8, returning None when the byte sequence is invalid.

Option and Result Functions

Construct, inspect, and extract optional values and success-or-error results. The bare constructor names are convenient aliases for the type-qualified forms.

Option.None

Call: Option.None

Type: Option 't

The type-qualified empty Option constructor.

Option.Some

Call: Option.Some value

Type: 't -> Option 't

Constructs a present Option containing value using its type-qualified name.

None

Call: None

Type: Option 't

The empty Option constructor.

Some

Call: Some value

Type: 't -> Option 't

Constructs a present Option containing value.

is_none

Call: is_none option

Type: Option 'a -> Bool

Returns whether option is None.

is_some

Call: is_some option

Type: Option 'a -> Bool

Returns whether option is Some.

Result.Err

Call: Result.Err error

Type: 'e -> Result 't 'e

Constructs a failed Result containing error using its type-qualified name.

Result.Ok

Call: Result.Ok value

Type: 't -> Result 't 'e

Constructs a successful Result containing value using its type-qualified name.

Err

Call: Err error

Type: 'e -> Result 't 'e

Constructs a failed Result containing error.

Ok

Call: Ok value

Type: 't -> Result 't 'e

Constructs a successful Result containing value.

is_err

Call: is_err result

Type: Result 't 'e -> Bool

Returns whether result is Err.

is_ok

Call: is_ok result

Type: Result 't 'e -> Bool

Returns whether result is Ok.

unwrap

Call: unwrap value

Types: Option 'a -> 'a; Result 't 'e -> 't

Extracts the value from Some or Ok; raises an error when value is None or Err.

Rex Language Guide

Rex is a small, strongly-typed functional DSL with:

• Hindley–Milner type inference (let-polymorphism)
• algebraic data types (ADTs), including record-carrying constructors
• Haskell-style type classes (including higher-kinded classes like Functor)

This guide is meant for users and embedders. For locked/production-facing semantics and edge cases, see SPEC.md.

Source Forms

A Rex source is parsed as a compilation unit containing:

• zero or more declarations (type, class, instance, fn, import)
• optionally followed by a single expression

Sources with a final expression are snippets or program entry points. Declaration-only sources are modules.

Example snippet:

fn inc : i32 -> i32 = \x -> x + 1;

let
  xs = [1, 2, 3]
in
  map inc xs

Program Entry Points

When a source is run as a program, Rex uses one entry point:

• If the source defines fn main, main is the entry point. The same source must not also contain a final expression.
• If the source does not define main, the final expression is treated as an implicit zero-argument entry point.
• If there is no main and no final expression, running the source as a program is an error.

The CLI passes arguments to main from a JSON file supplied with --inputs. The JSON file is a top-level object whose fields match the parameter names:

fn main scale: i32 -> offset: i32 -> i32 =
  scale + offset;

{
  "scale": 3,
  "offset": 4
}

The values are converted to Rex values using the parameter types. Runnable files without main use their final expression as the entry point, so their input shape is {}.

Modules and Imports

Rex modules are named entries in an abstract module namespace. Imports are semicolon-terminated top-level declarations. Source-backed modules are declaration-only: they do not have a top-level expression result. To evaluate an expression, run a source as a program entry point.

In embedded applications, the host decides how module names are resolved. An importer can map a module name to Rex source, a prebuilt compilation unit, a database row, hard-coded strings, or a Rust-backed module. The core language does not require a module to be a file.

Supported forms:

import foo.bar as Bar;
import foo.bar (*);
import foo.bar (x, y as z);
import ./foo/bar (x);
import ../../foo/bar as FB;

Semantics:

• import foo.bar as Bar imports a module alias; use qualified access (Bar.name).
• Alias-qualified lookup is namespace-aware:
  • expression/pattern positions use exported values and constructors (Bar.value).
  • type positions use exported types (Bar.Type).
  • class-constraint positions use exported classes (Bar.Class).
• import foo.bar (*) imports every exported name into local unqualified scope.
• import foo.bar (x, y as z) imports selected exported names; y is bound locally as z.
• Unqualified imports are context-sensitive:
  • expression/pattern positions use the imported value facet
  • type positions use the imported type facet
  • class-constraint positions use the imported class facet
• Importing a name does not invent missing facets. For example, importing a type name does not make it usable as a value unless the module also exports a value with that same spelling.
• A single exported name may carry multiple facets at once. ADTs commonly do this: Boxed can be both a type name and a constructor value.
• Module alias imports and clause imports are mutually exclusive in one import declaration.
• Only pub names are importable.
• If two imports introduce the same unqualified name (including via (*)), resolution fails with a module error.
• Importing a name that conflicts with a local top-level declaration is a module error.
• Lexical bindings (let, lambda params, pattern bindings) can shadow imported names.
• For binder forms with annotations, the annotation is resolved before the new binder name enters expression scope.

Examples:

import sample (Boxed);

let id: Boxed -> Boxed = \x -> x in
id (Boxed 1)

Here Boxed is imported once, but it can be used in both type position and expression position.

import sample (Status, Ready);

let id: Status -> Status = \x -> x in
id Ready

This only works if sample exports Status as a type and Ready as a value. Importing Status alone does not make Status available as an expression unless the module also exports a value named Status.

Path resolution:

• Module IDs are qualified names such as foo.bar, std.prelude, or ffmpeg.formats.av1.
• Each module-name segment must start with a letter or _, followed by letters, digits, or _.
• foo.bar requests module ID foo.bar; it does not inherently mean foo/bar.rex.
• The CLI installs a filesystem importer that maps module IDs to .rex files. Other embedders can resolve the same module ID from any backing store.
• Relative-looking import spellings such as ./foo/bar and ../../foo/bar are parsed into module path segments and resolved by importer policy using the importing module as context.
• Imports name modules only; URL imports and content-hash suffixes are not part of the syntax.

Lexical Structure

Whitespace and Comments

• Whitespace, including newlines, is generally insignificant and indentation has no syntactic meaning. Top-level type, fn, and declare fn declarations, marker classes/instances, and class/instance items use explicit semicolon terminators.
• Comments use // ... for line comments and /* ... */ for block comments. They are stripped before parsing.
• Nested block comments are not supported in current Rex builds.

Identifiers and Operators

• Identifiers start with a letter or _, followed by letters/digits/underscores.
• Operators are non-alphanumeric symbol sequences (+, *, ==, <, …).
• Operators can be used as values by parenthesizing: (+), (==), (<).

Lambdas

The lambda syntax is \x -> expr. Rex only accepts the ASCII spellings \ and ->.

Expressions

Literals

• true, false
• integers and floats (integer literals are overloaded over Integral and default to i32 when ambiguous)
• strings: "hello"
• UUID and datetime literals, when enabled by the parser

Examples:

( (4 is u8)
, (4 is u64)
, (4 is i16)
, (-3 is i16)
)

Negative literals only specialize to signed types. For example, (-3 is u8) is a type error.

Rex can implicitly widen primitive integers when the target type is already known and the conversion is lossless. For example, an i8 value can be passed to an i32 parameter, but Rex will not guess a common type for (1 is i8) + (2 is i32).

Function Application

Application is left-associative: f x y parses as (f x) y.

let add = \x y -> x + y in add 1 2

Let-In

Let binds one or more definitions and then evaluates a body:

let
  x = 1 + 2,
  y = 3
in
  x * y

Let bindings are polymorphic (HM “let-generalization”):

let id = \x -> x in (id 1, id true, id "hi")

Integer-literal bindings are a special case: unannotated let x = 4 is kept monomorphic so use sites can specialize it through context.

let
  x = 4,
  f: u8 -> u8 = \y -> y
in
  f x

Recursive Let (let rec)

Use let rec for self-recursive and mutually-recursive bindings.

let rec
  even = \n -> if n == 0 then true else odd (n - 1),
  odd = \n -> if n == 0 then false else even (n - 1)
in
  (even 10, odd 11)

Notes:

• Bindings in let rec are separated by commas.
• A binding whose right-hand side is a lambda is treated as a recursive function binding.
• Other bindings are initialized like sequential let values and can only reference earlier bindings in the same group.
• Function bodies can reference any binding in the same group.
• A value binding is rejected if it calls an earlier function whose body can reach a binding that has not been initialized yet.

If-Then-Else

if 1 < 2 then "ok" else "no"

Tuples, Lists, Dictionaries

(1, "hi", true)
[1, 2, 3]
{ a = 1, b = 2 }

Notes:

• Lists are implemented as a List a ADT (Empty/Cons) in the prelude.
• Cons expressions use :: (for example x::xs), equivalent to Cons x xs.
• Cons is used with normal constructor-call syntax (Cons head tail), while :: is infix sugar.
• Dictionary literals { k = v, ... } build record/dict values. They become records when used as the payload of an ADT record constructor, or when their type is inferred/annotated as a record.

:: is right-associative, so 1::2::[] means 1::(2::[]).

let
  xs = 1::2::3::[]
in
  xs

Pattern Matching

match performs structural matching. The scrutinee is followed by with, then one or more semicolon-terminated case arms inside a braced arm block:

match xs with {
  case Empty -> 0;
  case Cons h t -> h;
}

Patterns include:

• wildcards: _
• variables: x
• constructors: Ok x, Cons h t, Pair a b
• qualified constructors via module alias: Sample.Right x
• list patterns: [], [x], [x, y]
• cons patterns: h::t (equivalent to Cons h t)
• dict key presence: {foo, bar} (keys are identifiers)
• record patterns on record-carrying constructors: Bar {x, y}

match [1, 2, 3] with {
  case h::t -> h;
  case [] -> 0;
}

Rex checks ADT matches for exhaustiveness and reports missing constructors.

Types

Primitive Types

Common built-in types include:

• Bool
• i32 (default integer-literal fallback type)
• f32 (float literal type)
• Char (one Unicode scalar value, written with single quotes)
• String
• UUID
• Hash
• DateTime

Function Types

Functions are right-associative: a -> b -> c means a -> (b -> c).

Tuples, Lists, Dicts

• Tuple type: (a, b, c)
• List type: List a (prelude)
• Dict type: Dict a (prelude; keys are strings and all values have type a)
• Promise type: Promise a (built-in unary type constructor; embedders may attach their own operations)

ADTs

Define an ADT with type. Each top-level type declaration is terminated by a semicolon:

type Maybe a = Just a | Nothing;

Constructors are values (functions) in the prelude environment:

Just 1
Nothing

Record-Carrying Constructors

ADT variants can carry a record payload:

type User = User { name: String, age: i32 };

let u: User = User { name = "Ada", age = 36 } in u

Named Record Aliases

Use type Name = { ... }; to give a structural record type a reusable name without introducing an ADT constructor:

type User = { name: String, age: i32 };

let u: User = { name = "Ada", age = 36 } in u.name

Aliases may have type parameters and remain transparent:

type Tagged a = { tag: String, value: a };

let item: Tagged i32 = { tag = "answer", value = 42 } in item.value

Type Annotations

Annotate let bindings, lambda parameters, and function declarations:

let x: i32 = 1 in x

Annotations can mention ADTs and prelude types:

let xs: List i32 = [1, 2, 3] in xs

They can also use module-qualified type names:

import dep as D;
fn id x: D.Boxed -> D.Boxed = x;

Records: Projection and Update

Rex supports:

• projection: x.field
• record update: { base with { field = expr } }

Projection and update are valid when the field is definitely available on the base:

• on plain record types { field: Ty, ... }
• on named record aliases, which expand to plain record types
• on single-variant ADTs whose payload is a record
• on multi-variant ADTs only after the constructor has been proven (typically by match)

Example (multi-variant refinement via match):

type Sum = A { x: i32 } | B { x: i32 };

let s: Sum = A { x = 1 } in
match s with {
  case A {x} -> { s with { x = x + 1 } };
  case B {x} -> { s with { x = x + 2 } };
}

Declarations

Functions (fn)

Top-level functions are declared with an explicit type signature and a value (typically a lambda). Each top-level fn declaration is terminated by a semicolon:

fn add x: i32 -> y: i32 -> i32 = x + y;

Top-level fn declarations are mutually recursive, so they can refer to each other in the same module:

fn even n: i32 -> Bool =
  if n == 0 then true else odd (n - 1);

fn odd n: i32 -> Bool =
  if n == 0 then false else even (n - 1);

even 10

Type Classes (class)

Type classes declare overloaded operations. Method signatures live in the class:

class Size a where {
  size : a -> i32;
}

Classes with no methods are terminated with a semicolon:

class Marker a;

Methods can be operators (use parentheses to refer to them as values if needed):

class Eq a where {
  == : a -> a -> Bool;
}

Superclasses use <= (read “requires”):

class Ord a <= Eq a where {
  < : a -> a -> Bool;
}

Instances (instance)

Instances attach method implementations to a concrete head type, optionally with constraints:

class Size a where {
  size : a -> i32;
}
instance<t> Size (List t) where {
  size = \xs ->
    match xs with {
      case Empty -> 0;
      case Cons _ rest -> 1 + size rest;
    };
}

Instances with no method implementations are also terminated with a semicolon:

instance Marker i32;

The class in an instance header may be module-qualified:

import dep as D;

instance D.Pick i32 where {
  pick = 7;
}

Instance contexts use <=:

class Show a where {
  show : a -> String;
}
instance Show i32 where {
  show = \_ -> "<i32>";
}
instance<a> Show (List a) <= Show a where {
  show = \xs ->
    let
      step = \out x ->
        if out == "["
          then out + show x
          else out + ", " + show x,
      out = foldl step "[" xs
    in
      out + "]";
}

Notes:

• Instance heads are non-overlapping per class (overlap is rejected).
• Inside instance method bodies, the instance context is the only source of “given” constraints.

Prelude Type Classes (Selected)

Rex ships a prelude with common abstractions and instances. Highlights:

• numeric hierarchy: AdditiveMonoid, Semiring, Ring, Field, …
• Default (default) for common scalar and container types
• Eq / Ord
• Functor / Applicative / Monad for List, Option, Result
• Foldable, Filterable, Sequence
• list range helpers: first n xs, last n xs, and half-open slice n m xs
• total list access and query helpers such as list_get, list_slice, list_find, and list_partition

Example: Functor across different container types:

( map ((*) 2) [1, 2, 3]
, map ((+) 1) (Some 41)
, map ((*) 2) (Ok 21)
)

Example: safe list indexing:

list_get 0 [10, 20, 30]

Defaulting (Ambiguous Types)

Rex supports defaulting for variables constrained by defaultable classes (for example AdditiveMonoid). This matters for expressions like zero where no concrete type is otherwise forced.

This defaulting pass is separate from the Default type class method default.

Example:

zero

With no other constraints, zero defaults to a concrete candidate type. See SPEC.md for the exact algorithm and candidate order.

Rex Spec (Locked Semantics)

This document records the intended, production-facing semantics of the current Rex implementation. When behavior changes, this file and the corresponding regression tests should be updated together.

Regression tests live in:

• rex/tests/spec_semantics.rs
• rex/tests/record_update.rs
• rex/tests/typeclasses_system.rs
• rex/tests/negative.rs

Notation

• Γ ⊢ e : τ means “under type environment Γ, expression e has type τ”.
• C τ means a typeclass predicate (constraint) for class C at type τ.
• “Ground” means “contains no free type variables” (ftv(τ) = ∅).
• Rex’s multi-parameter classes are represented internally by packing the parameters into tuples:
  • unary C a is Predicate { class: C, typ: a }
  • binary C t a is Predicate { class: C, typ: (t, a) }
  • etc.

Lexical Comments

Rex comments are lexical trivia and are removed before parsing:

• // starts a line comment that runs to the next newline or end of file.
• /* ... */ starts a block comment. Block comments may span lines.
• Nested block comments are not supported.
• The legacy {- ... -} spelling is ordinary syntax, not a comment.

Character and String Literals

Character and string literals are decoded during lexing.

• Double-quoted ("...") literals produce String values.
• Single-quoted ('...') literals produce Char values and must decode to exactly one Unicode scalar value. Char has the same value domain as Rust’s char: surrogate code points and values above U+10FFFF are rejected, while every valid Unicode scalar value is accepted.
• C-style simple escapes are supported: \a, \b, \f, \n, \r, \t, \v, \\, \", \', and \?.
• Octal escapes use one to three octal digits (\0 through \777).
• Hex escapes use \x followed by one or more hexadecimal digits.
• Unicode escapes use \u followed by exactly four hexadecimal digits, or \U followed by exactly eight hexadecimal digits.
• Backslash-newline is a line continuation and produces no character.
• Unsupported or malformed escape sequences are lexical errors.
• At JSON boundaries, Char is represented by a JSON string containing exactly one Unicode scalar value.

String Operations

String operations put selectors and modifiers first and the primary input value last, matching the rest of the collection API. For example, string_contains needle haystack, string_split separator input, and string_replace needle replacement input can be partially applied to form reusable predicates or transformations.

• String positions are zero-based Unicode scalar indices, never UTF-8 byte offsets. string_get index input returns the scalar at index, while string_slice start end input uses a half-open start..end range. string_get returns None for an out-of-bounds index. string_slice returns None unless 0 <= start <= end <= length input; an empty in-bounds range returns Some "".
• string_contains needle haystack, string_starts_with prefix input, and string_ends_with suffix input perform literal substring tests. string_find needle haystack returns the first matching Unicode scalar index or None; an empty needle is found at index zero.
• string_split separator input splits at non-overlapping literal matches and preserves empty segments, including trailing segments. An empty separator produces an empty segment at each end and one string for every Unicode scalar in between. string_join separator parts inserts the separator only between adjacent elements.
• string_replace needle replacement input replaces every non-overlapping literal match. An empty needle inserts the replacement at every Unicode scalar boundary, including both ends.
• string_trim, string_trim_start, and string_trim_end remove Unicode whitespace as classified by Rust’s char::is_whitespace. string_to_lower and string_to_upper apply Unicode case mappings and may change the number of scalar values.
• string_to_chars and chars_to_string convert losslessly between strings and lists of Unicode scalar values. string_to_utf8 returns the UTF-8 bytes of a string. utf8_to_string returns Some for valid UTF-8 and None for an invalid byte sequence.

Length

length returns a u64 and is implemented for lists, dictionaries, and strings:

• Lists return their number of elements.
• Dictionaries return their number of entries.
• Strings return their number of Unicode scalar values, not their UTF-8 byte length or number of user-perceived grapheme clusters. For example, length "h\u00e9\U0001F600" == 3 and length "e\u0301" == 2.

Option does not implement Length.

Dictionaries

Dict a is an immutable mapping from String keys to values of one uniform type a. Runtime dictionary and record field maps store keys as strings; compiler identifiers and statically known record field names remain symbols only inside the compiler.

Dictionary iteration order is ascending lexicographic string order. This order is observable in dict_keys, dict_values, dict_entries, and the collision behavior of dict_map.

The core operations have these semantics:

• dict_get returns Some value for a present key and None for an absent key.
• dict_has tests key presence.
• dict_insert, dict_remove, and dict_update return new dictionaries without changing their inputs. dict_update key f calls f with the current optional value; Some value in the result inserts or replaces the key, while None removes it.
• dict_keys, dict_values, and dict_entries return lexicographically ordered lists.
• dict_from_entries processes its input list from first to last, so the last tuple for a duplicate key wins.

Dict implements Functor and Filterable. map, filter, and filter_map apply their callbacks to values only and preserve the corresponding input keys. Callback applications for different entries may evaluate in parallel; callback completion order does not affect the result.

dict_map has type ((String, a) -> (String, b)) -> Dict a -> Dict b. Its callback applications may evaluate in parallel. After every callback completes, results are applied in the original dictionary’s lexicographic key order. If multiple callbacks return the same output key, the result from the latest input key in that order wins.

dict_filter has type ((String, a) -> Bool) -> Dict a -> Dict a. Its callback applications may also evaluate in parallel. It preserves each accepted entry’s original key and value.

Primitive Host Types

The zero-arity primitive types are u8, u16, u32, u64, i8, i16, i32, i64, f32, f64, Bool, Char, String, UUID, Hash, and DateTime. Char corresponds exactly to Rust’s char and implements RexType, IntoRex, and FromRex. The Hash type corresponds to a blake3::Hash in Rust. At JSON boundaries, hash values are exactly 32 bytes encoded as hexadecimal strings; Rex emits the canonical lowercase 64-character representation. show uses the same representation. The Parse Hash instance accepts the same representation and returns None for invalid input.

Program Entry Points

A Rex source is a compilation unit with zero or more declarations and an optional final expression. Entry-point execution uses a single program entry point:

• If the source defines a top-level fn main, that function is the entry point. It is an error for the same source to also contain a final expression.
• If the source does not define main, the final expression is treated as an implicit zero-argument entry point.
• If the source does not define main and has no final expression, entry-point execution is an error.

The CLI supplies arguments to an explicit main from a JSON object passed with --inputs. The object keys must exactly match the main parameter names, and each value is converted with json_to_rex using the corresponding parameter type. JSON inputs require concrete parameter types. A runnable source without main uses its final expression as an implicit entry point and conceptually has the empty input object {}.

Module Imports

Rex distinguishes between:

• program entry-point execution, and
• modules loaded by the import system.

When Rex source is loaded as a module via the module system, it must not contain a top-level expression result. Host-backed Rust modules may also be returned by importers; they expose their declared interface and native implementations without a Rex source body.

Syntax

Top-level imports support three forms:

import foo.bar as Bar;
import foo.bar (*);
import foo.bar (x, y, z as q);

Rules:

• Import declarations are terminated by explicit semicolons.
• import <module> as <Alias> imports the module namespace and requires qualified access (Alias.member).
• import <module> (*) imports all exported values, types, and classes into unqualified scope.
• import <module> (x, y as z) imports selected exported values, types, and classes into unqualified scope.
• as <Alias> on the module and (...) import clauses are mutually exclusive.
• A module identity is a validated qualified name with one or more segments. Each segment starts with a letter or _ and then contains only letters, digits, or _.
• The engine treats module identities as names in an abstract namespace. Mapping those names to .rex files, generated source, parsed ASTs, databases, or Rust host modules is importer policy.
• Imports are module names, not URLs, filesystem paths owned by the engine, or content hashes.

Visibility and Exports

Only exported (pub) values, types, and classes are importable through (*) and item clauses.

Module aliases expose all export namespaces for qualified lookup:

• Alias.value resolves against exported values.

• Alias.Type resolves against exported type names in type positions.

• Alias.Type.Variant resolves an ADT constructor owned by an exported type.

• Alias.Class resolves against exported class names in class-constraint positions.

• Missing requested exports are module errors.

• Private (non-pub) values are not importable.

Name Binding and Conflicts

• Imported unqualified names participate in lexical shadowing.
• Lexically bound names (lambda params, let vars, pattern bindings) shadow imported names.
• Importing a name that conflicts with a local top-level declaration is a module error.
• Importing the same unqualified name more than once (including via aliasing) is a module error.

Importing an ADT type also makes its constructor namespace available. For example, import dep (Status) permits Status.Ready, while import dep as D permits D.Status.Ready. Constructor namespaces are type-owned, so two imported types may both define a variant named Ready without creating an ambiguity. For compatibility, variants also retain their legacy value aliases; an ambiguous legacy alias still requires the type-owned spelling.

Type/class rewrites run with declaration ordering semantics:

• In binder forms that carry type syntax (\ (x : T) -> ..., let rec f : T = ...), the binder being introduced does not suppress alias resolution inside its own annotation.
• Missing alias members used in type/class positions (function signatures, annotations, where constraints, instance headers, and superclass clauses) are reported as module errors.

Module Initialization

• Importing a module does not execute arbitrary top-level expressions.
• Module initialization is declaration-driven: exported values/types/classes are registered from declarations, and import resolution rewrites references to canonical internal symbols.
• Source imports are parsed as CompilationUnits, then converted into CompilationPackages for module processing. Source-derived and prebuilt CompilationPackage imports are loaded through strongly connected component (SCC) loading of module interfaces, so cyclic source imports are supported.
• Rust modules returned by importers are installed lazily through the same named-module machinery as eager Builder::inject_module. They must be named modules matching the resolved module identity, not root/global modules, and they do not run nested Rex import graph loading.

Let Rec Bindings

Syntax

Recursive bindings use let rec with comma-separated entries:

let rec
  a = ...,
  b = ...
in
  body

Rules:

• let rec entries are separated by commas.
• let rec bindings must bind variables (not arbitrary patterns).
• A syntactic lambda binding is a recursive function binding. Type annotations around the lambda do not change this classification.
• Non-lambda bindings are value bindings. They are initialized sequentially and may only reference earlier bindings in the same let rec group.
• Function bodies may reference any binding in the same let rec group.
• A value binding is rejected if it depends on itself, a later binding, or an earlier function whose body can reach a binding that is not initialized yet.

Top-Level Declaration Terminators

Top-level type, fn, declare fn, and import declarations are terminated by explicit semicolons:

import math.core as Math;
type Box a = Box a;
type Point = { x: i32, y: i32 };
fn inc x: i32 -> i32 = x + 1;
declare fn host_value : i32;

Rules:

• The semicolon terminates the declaration, not a nested type or expression itself.
• The terminating semicolon is found at top-level expression/type depth; semicolons nested inside parentheses, brackets, braces, or blocks do not terminate the declaration.
• Indentation and newlines do not delimit declarations.

Explicit Type Parameters

Type variables used in annotations, constraints, class heads, or instance heads must be declared by the syntactic form that binds them.

Examples:

type Box a = Box a;
fn id<a> x: a -> a = x;
declare fn host_id<a> x: a -> a;
let id<a>: a -> a = \x -> x in id 1
class Size a where { size : a -> i32; }
instance<a> Show (List a) <= Show a where { show = prim_show; }

Rules:

• A bare unknown type name is an error, even when it starts with a lowercase letter.
• Top-level fn, declare fn, named let, class methods, and instance methods bind type parameters with <...> after the value name.
• type and class declarations bind type parameters with whitespace after the declaration head.
• instance declarations bind type parameters with <...> immediately after instance.

Algebraic Data Type Constructors

Each ADT owns a constructor namespace named after the type:

type Direction = North | South;
type Status = Ready | Waiting;

let direction = Direction.North in
match direction with {
    case Direction.North -> Status.Ready;
    case Direction.South -> Status.Waiting;
}

The same Type.Variant spelling is used in expressions and constructor patterns. Constructor names are distinct from record projection: when the left-hand name resolves to an ADT type, the member resolves in that type’s variant namespace. The runtime constructor tag remains the variant name, so this source-level qualification does not change ADT JSON encoding or Rust conversion.

Unqualified constructor aliases remain available for source compatibility. They may be overloaded when multiple ADTs define the same variant; Type.Variant is the canonical, unambiguous spelling.

Named Record Aliases

Syntax

A type declaration whose right-hand side begins with a record type declares a transparent record alias rather than an ADT:

type Point = { x: i32, y: i32 };
type Tagged a = { tag: String, value: a };

Typing and Runtime Representation

• Applying a record alias is equivalent to writing its expanded record type. Alias names do not make otherwise identical record shapes distinct.
• Alias parameters are substituted structurally, so Tagged i32 expands to { tag: String, value: i32 }.
• Aliases may refer to other aliases and ADTs. Cyclic aliases are rejected.
• A record alias introduces no value-level constructor and no runtime tag. Its values are ordinary record/dict values.
• A record literal checked against a record type receives the expected type of each field. This permits heterogeneous and nested literals such as let user: { name: String, age: i32 } = { name = "Ada", age = 36 } in user.

Default-Backed Record Construction

Syntax and Application Precedence

A record-carrying ADT constructor may be followed directly by its named fields:

Config.Config { retries = 9, enabled = true }

An uppercase constructor reference and its following record literal bind as one expression before surrounding function application. This also applies to qualified constructors, so the final argument below does not require parentheses:

run_tool input Tools.Options { retries = 9 }

Complete Construction

When every declared field is supplied, construction has the ordinary ADT semantics and does not require a Default instance:

type Config = Config { retries: i32, enabled: Bool };
Config.Config { retries = 9, enabled = true }

Partial Construction

Fields may be omitted when all of these conditions hold:

1. The constructor belongs to a single-variant ADT.
2. Its only argument is a record payload.
3. A Default instance is available for the resulting ADT type.

The constructor fixes the result type and complete field schema before supplied fields are checked. Therefore partial construction does not rely on row polymorphism or infer a smaller record type. Unknown fields remain errors.

For a qualifying constructor T.C, this expression:

T.C { field = value }

is semantically equivalent to evaluating default once at T.C’s result type and updating that value’s field. Omitted fields come from the whole ADT’s Default implementation, not from independent Default instances for each field. T.C {} is an explicitly typed default value.

Partial construction is rejected for multi-variant ADTs because Default T does not guarantee that it produces the named variant. Supporting such construction would require a constructor-specific default rather than the type-level Default instance.

Top-Level fn Recursion

Top-level fn declarations are mutually recursive within a module.

This means:

• A top-level fn may reference itself.
• A top-level fn may reference other top-level fn declarations in the same module, regardless of declaration order.

Operationally, top-level fn recursion follows the same fixed-point semantics as recursive bindings in let rec, but at declaration scope.

Record Projection

Syntax

Field projection is an expression:

base.field

Typing (Definite Fields)

Let Γ ⊢ base : T. Projection is well-typed iff the field is definitely available on T:

1. If T is a record type { ..., field : τ, ... }, then Γ ⊢ base.field : τ.
2. If T is a single-variant ADT whose payload is a record containing field : τ, then Γ ⊢ base.field : τ.
3. If T is a multi-variant ADT, projection is accepted only if the typechecker can prove the current constructor is a specific record-carrying variant (typically via match refinement or by tracking known constructors through let-bound variables).

If the typechecker cannot prove the constructor for a multi-variant ADT, the field is considered “not definitely available”, and projection is rejected.

Evaluation

Evaluation is strict in base. At runtime, projection reads the field out of the record payload:

• for plain records/dicts, it indexes the map by the field symbol.
• for record-carrying ADT values, it indexes the payload record/dict.

Missing fields are a runtime error (EngineError::UnknownField) when projection is attempted on a non-record-like value.

Record Update

Syntax

Record update is an expression:

{ base with { field1 = e1, field2 = e2 } }

Typing (Definite Fields)

Let Γ ⊢ base : T. Record update is well-typed iff:

1. Each updated field exists on the definite record shape of T.
2. T is one of:
   • a record type { field: Ty, ... }, OR
   • a single-variant ADT whose payload is a record, OR
   • a multi-variant ADT after the expression has been refined to a specific record-carrying constructor (the typechecker tracks this refinement).
3. For each update fieldᵢ = eᵢ, the update expression unifies with the declared field type.

If the base type is a multi-variant ADT and the typechecker cannot prove the current constructor, record update is rejected (the field is “not definitely available”).

Typing: Known-Constructor Refinement

The typechecker refines “which constructor is known” via two mechanisms:

1. Pattern matching: within a case K { ... } -> ... arm, the scrutinee is known to be K.
2. Let-bound known constructors: when a variable is bound to a value constructed with a record-carrying constructor, the variable may carry “known variant” information forward.

This enables the common pattern:

type Sum = A { x: i32 } | B { x: i32 };

let s: Sum = Sum.A { x = 1 } in
match s with {
  case Sum.A {x} -> { s with { x = x + 1 } };
  case Sum.B {x} -> { s with { x = x + 2 } };
}

Evaluation

Evaluation is strict:

1. Evaluate base to a value.
2. Evaluate all update expressions (left-to-right in the implementation’s map iteration order).
3. Apply updates:
   • If base is a plain record/dict value, updates replace existing fields.
   • If base is an ADT whose payload is a record/dict, updates replace fields in the payload and re-wrap the constructor tag.

Runtime errors:

• Updating a non-record-like runtime value is EngineError::UnsupportedExpr.

Type Classes: Coherence, Resolution, and Ambiguity

Instance Coherence (No Overlap)

For each class C, instance heads are non-overlapping:

• When injecting a new instance head H, it is rejected if it unifies with any existing head for the same class C.

This forbids overlap and preserves deterministic method resolution.

Regression: spec_typeclass_instance_overlap_is_rejected (rex/tests/spec_semantics.rs).

Qualified Class Names in instance Headers

The class name in an instance header may be qualified through a module alias:

import dep as D;

instance D.Pick i32 where {
  pick = 7;
}

The alias member must be an exported class from the referenced module; otherwise import-use validation fails before typechecking/evaluation.

Method Resolution (Runtime)

At runtime, class methods are resolved by unification against the inferred call type.

Let m be a class method, and let its call site be typed with monomorphic call type τ_call.

Resolution:

1. Determine the “instance parameter type” for the method by unifying τ_call with the method’s scheme and extracting the predicate corresponding to the method’s defining class.
2. If the instance parameter type is still headed by a type variable (not ground enough to pick an instance), the use is ambiguous:
   • If m is used as a function value (i.e. τ_call is a function type), the engine returns an overloaded function value and defers resolution until the function is applied with concrete arguments.
   • If m is used as a value (non-function), the engine errors (EngineError::AmbiguousOverload).
3. If exactly one instance head unifies with the instance parameter type, its method body is specialized and evaluated.
4. If none match, the engine errors (EngineError::MissingTypeclassImpl).
5. If more than one match (should not occur given non-overlap), the engine errors (EngineError::AmbiguousTypeclassImpl).

Regression: spec_typeclass_method_value_without_type_is_ambiguous (rex/tests/spec_semantics.rs).

Prelude Parsing

The prelude class Parse a provides parse : String -> Option a. It has instances for Bool, u8, u16, u32, u64, i8, i16, i32, i64, f32, f64, Char, UUID, Hash, and DateTime. A successful conversion returns Some value; malformed or out-of-range input returns None rather than raising an evaluation error. Parsing a Char succeeds only when the input contains exactly one Unicode scalar value.

The desired result type must be determined by context so that the corresponding Parse instance can be selected, for example:

let port: Option u16 = parse "8080" in port

Regressions: parse_returns_some_for_every_supported_type and parse_returns_none_for_every_supported_type (rex/tests/typeclasses_system.rs).

Overloaded Method Values (Deferred Resolution)

If a class method is used as a function value, the engine may defer instance selection until the function is applied with concrete argument types. This supports idioms like:

let f = map ((+) 1) in
  ( f [1, 2, 3]
  , f (Some 41)
  )

Here f is polymorphic over the Functor dictionary; at each call site, the engine resolves map using the argument type (List i32 vs Option i32) and dispatches to the corresponding instance method body.

Prelude List Additive Monoid

The prelude defines AdditiveMonoid (List a) for every element type a, with no constraint on a. Its identity zero is [], and xs + ys concatenates xs and ys in that order.

[1, 2, 3] + [4, 5, 6]

Regression: additive_monoid_list_concatenates_in_order and additive_monoid_list_requires_no_element_constraint (rex/tests/typeclasses_system.rs).

Prelude Ordering

The prelude defines the algebraic data type Ordering with exactly three unit variants: Ordering.Less, Ordering.Equal, and Ordering.Greater. The Ord method cmp : a -> a -> Ordering returns the variant that describes the left operand relative to the right operand. Floating-point comparisons involving NaN remain runtime type errors.

Regression: ord_cmp_returns_ordering_variants and ordering_variants_can_be_pattern_matched (rex/tests/typeclasses_system.rs).

Prelude List Ranges

The prelude exposes strict list range helpers:

• first n xs returns the first n visible elements of xs.
• last n xs returns the last n visible elements of xs.
• slice n m xs returns the half-open visible range n..m.

For all three helpers, list positions are counted from the Rex-level list view, independent of whether the runtime stores the list as cons cells, a vector-backed slice, or cons cells followed by a vector-backed slice. Bounds are checked at runtime. Negative bounds, bounds greater than the list length, and slice n m xs with m < n are runtime errors. n == length/m == length is valid for empty suffixes and half-open slice endpoints.

The Sequence methods take and skip use a u64 count. Counts greater than the list length are clamped to the list length, so take returns the whole list and skip returns an empty list.

The list-specific operations use u64 positions and return ordinary data failures as options:

• list_get index xs returns Some for an in-bounds zero-based index and None otherwise.
• list_slice start end xs returns Some of the half-open range start..end when 0 <= start <= end <= length xs, including Some [] for an empty valid range, and None for invalid bounds.
• list_reverse, list_concat, and list_repeat preserve element values and construct a new list in the order implied by their names. list_repeat 0 value returns [].
• list_any, list_all, list_find, and list_find_index evaluate predicates from left to right and stop once their result is known. On an empty list, list_any is false, list_all is true, and both find operations return None.
• list_count and list_partition evaluate every predicate application. Independent applications may run concurrently. list_partition returns matching elements first and rejected elements second, preserving relative input order in both lists.

Instance-Method Checking (Static)

Inside an instance method body, only the instance context is available as “given” constraints:

• Given predicates start with the instance’s explicit context.
• The superclass closure of that context is added (repeat until fixed point).
• The instance head itself is also considered given (dictionary recursion).

Rules:

• Ground predicates required by the method body must be entailed by the given set (via instance search).
• Non-ground predicates are not resolved by instance search (that would be unsound); they must appear explicitly in the instance context.

This is what makes instance methods predictable and prevents “magical” selection based on unifying type variables with arbitrary instance heads.

Integer Literals

Integer literals are overloaded over integral types.

• A literal like 4 introduces a fresh type variable α with predicate Integral α.
• A negative literal like -3 introduces α with predicates Integral α and AdditiveGroup α (so it can only specialize to signed numeric types).
• Binary subtraction uses Subtractive, which includes unsigned integer types. Unary negation still requires AdditiveGroup.
• Division uses Divisive, which includes primitive integer and floating-point types. Integer division follows Rust’s integer division semantics.
• Integer +, -, *, /, and % are checked at runtime for primitive integer types. Arithmetic overflow raises integer overflow (T) and arithmetic underflow raises integer underflow (T), where T is the concrete integer type.
• Context can specialize α (for example, let x: u64 = 4 in x).
• Unannotated let bindings whose definition is an integer literal are kept monomorphic. This lets use sites specialize the binding consistently in that scope (for example, let x = 4 in (x + 1, x + 2)).
• If α remains ambiguous, normal defaulting rules apply.

Examples:

let x: u8 = 4 in x
let f: i64 -> i64 = \x -> x in f 4
let x = 4 in (x is u16)
let x: i16 = -3 in x

Attempting to use a negative literal at an unsigned type is a type error (for example let x: u8 = -3 in x).

Implicit Integer Widening

Rex inserts an implicit integer widening conversion only when the surrounding expression context already requires a concrete primitive integer type.

• The source and target must both be primitive integer types.
• The conversion must be lossless for every value of the source type.
• The target type must already be known; Rex does not infer a common numeric type for unconstrained mixed-width expressions.

Allowed widening conversions are:

• i8 -> i16, i8 -> i32, i8 -> i64
• i16 -> i32, i16 -> i64
• i32 -> i64
• u8 -> u16, u8 -> u32, u8 -> u64, u8 -> i16, u8 -> i32, u8 -> i64
• u16 -> u32, u16 -> u64, u16 -> i32, u16 -> i64
• u32 -> u64, u32 -> i64

Examples:

fn f : i32 -> i32 = \x -> x;
fn g : i8 -> i8 = \x -> x;

let x: i32 = (7 is i8) in (f (g 5), x)

Mixed operators remain homogeneous unless an enclosing context fixes the target type. For example, (1 is i8) + (2 is i32) is a type error.

Float Literals

Float literals are overloaded over primitive floating-point types.

• A literal like 3.0 introduces a fresh type variable α with predicate Field α.
• Context can specialize α to f32 or f64 (for example, let x: f64 = 3.0 in x).
• If α remains ambiguous, normal defaulting rules choose f32.
• Unannotated let bindings whose definition is a float literal are kept monomorphic, matching integer literal bindings.
• Float literals do not imply integer-to-float coercions. A mixed expression such as 1 + 2.0 is still a type error unless the values are explicitly converted by user code.

Examples:

let x: f64 = 3.0 in x
let f: f64 -> f64 = \x -> x in f 3.0
let x = 3.0 in (x is f32)

Defaulting

Defaulting runs after type inference and before evaluation.

Eligible Variables

A type variable α is eligible for defaulting iff:

• α appears in at least one simple predicate of the form C α, and at least one such C is in the numeric defaultable set: AdditiveMonoid, MultiplicativeMonoid, Subtractive, AdditiveGroup, Ring, Divisive, Field, Integral; and
• every simple predicate involving α is either in that numeric set or is an allowed companion.

Eq and Ord are allowed as companion predicates when a numeric defaultable predicate is also present. They do not make a type variable defaultable on their own. This lets expressions like if x == 0.0 then ... default through the float literal’s Field predicate without making unconstrained equality default to an arbitrary numeric type.

Compound predicates do not make a variable eligible for defaulting. They also do not prevent an otherwise eligible numeric variable from defaulting, provided that substituting a candidate makes each compound predicate ground and the resulting predicate is satisfied. A candidate is rejected if substitution leaves another unresolved variable in one of those predicates.

Candidate Types (Order Matters)

The candidate list is constructed in this order:

1. Traverse the typed expression (depth-first) and collect every concrete (ground) 0-arity type constructor that appears as the type of a subexpression (unique, in first-seen order).
2. Append (if not already present): f32, i32, String.

Choosing a Default

For an eligible variable α, choose the first candidate type T such that substituting T for α makes every predicate involving α ground and satisfied in the empty context:

entails([], Pᵢ[α := T]) for every predicate Pᵢ involving α

If no candidate satisfies all predicates, α remains ambiguous.

Example: zero (type α with AdditiveMonoid α) defaults to f32 when no other concrete type is present:

zero

Regression: spec_defaulting_picks_a_concrete_type_for_numeric_classes (rex/tests/spec_semantics.rs).

For example, the integer literals below provide the simple predicate Integral α, while list addition provides the compound predicate AdditiveMonoid (List α). Substituting i32 satisfies both, so the result type is List i32:

[1, 2, 3] + [4, 5, 6]

Regressions: spec_defaulting_accepts_satisfied_compound_predicates and spec_defaulting_requires_a_simple_numeric_predicate (rex/tests/spec_semantics.rs).

Architecture

Rex is implemented as a small set of focused crates that form a pipeline:

1. Parsing (rex-parser): converts source text into a rex_ast::CompilationUnit { decls, body }.
2. Typing (rex-typesystem): Hindley–Milner inference + ADTs + type classes; produces a rex_typesystem::TypedExpr.
3. Execution (rex-engine): builds the host environment, prepares typed code into a CompiledProgram, and evaluates it to an owned rex_engine::Value.

The crates are designed so you can use them independently (e.g. parser-only tooling, typechecking-only checks, or embedding the full evaluator).

Crates

• rex-ast: shared AST types (Expr, Pattern, Decl, TypeExpr, CompilationUnit, symbols, spans).
• rex-parser: source parser. Entry point: rex_parser::parse.
  • Parsing enforces a fixed cap on AST nesting.
• rex-typesystem: type system. Entry points:
  • TypeSystem::new() to create an explicit typing environment.
  • infer_typed(&mut ts, expr) / infer(&mut ts, expr) for type inference.
  • The inference implementation itself lives in rex-typesystem/src/inference.rs; typesystem.rs now holds the shared core types, environments, and registration logic.
  • For untrusted code, set rex_typesystem::TypeSystemLimits::safe_defaults() before inference.
  • RegisteredValue carries a scheme, Rex-visible parameter names, and optional Markdown docs. TypeBundle is the JSON-facing persistence format for those registrations and their referenced, documented ADTs.
• rex-engine: host environment builder, compiler, and runtime evaluator. Entry points:
  • Builder::with_prelude(state)? to inject runtime constructors and builtin implementations (state can be ()).
  • standard_type_system()? to create a typing environment with the rex-engine standard prelude.
  • Builder::build_compiler() to consume the prepared builder into a compilation view.
  • Compiler::compile_program to consume the compiler and prepare a parsed program entry point into (CompiledProgram, Evaluator). Compiler::infer_* consumes the compiler for type-only checks.
  • Evaluator::run(compiled, inputs).await to execute one prepared program. inputs is a BTreeMap<String, Value> for the program’s external main interface; run consumes the evaluator, compiled program, and input map and returns a Value.
  • Builder carries host state as Builder<State> (State: Clone + Send + Sync + 'static); typed export callbacks receive an owned clone of State and return Result<T, EngineError>, typed export_async callbacks receive an owned clone of State and return Future<Output = Result<T, EngineError>>, while dynamic native APIs (export_native*) receive Context<State>, an instantiated type, and owned Values.
  • compile and evaluation APIs return EngineError; convenience entry points that cross phases return ExecutionError.
  • Host module injection API: Module + Export + Builder::inject_module for eager registration, or Importer<State> returning ResolvedModuleContent::module(...) for lazy Rust-backed modules. Named modules accept optional Markdown docs in Module::new.
• rex-proc-macro: #[derive(Rex)], #[rex::export], and #[rex::module] bridge documented Rust types, functions, and modules into Rex registrations.
• rex: top-level facade for embedding the pipeline in Rust applications. Its workflow module provides typed workflow modules, CAS artifacts, and mandatory OCI tool execution. Semantic tool plans become logical OciJob values; Docker is the supplied backend and OciJobExecutor is the provider extension point. See OCI Executor Protocol.
• rex-cli: rex_cli command-line front-end around the pipeline.
• rex-lsp / rex-vscode: editor tooling.

rex-engine is organized internally around the same phases:

• builder/ owns builder-facing host/module registration.
• compiler/ owns program preparation, import rewriting, typechecking, module loading state, and CompiledProgram construction.
• evaluator/ owns execution, scheduling, native dispatch, Context, and the runtime core.
• modules/, memory/, and config.rs hold shared module identities, heap values/GC roots, and runtime options.

Runtime Ownership and GC Boundaries

rex-engine uses a moving copying collector. Heap has one owner and moves exactly once through Builder -> Compiler -> Evaluator; there is no heap mutex or public heap capability. Private heap cells contain moving edges, while evaluator frames, environments, scheduler work, and compiler state contain stable runtime-root tokens. The evaluator traverses and relocates those roots only at actual collection safepoints, not around every work item.

The public boundary is an owned Value tree. Before a host call starts, the evaluator performs a type-directed copy from internal roots to Value; the host future contains only those values and host state. On completion, the evaluator validates and imports the result while it again has exclusive heap access. Internal prelude intrinsics are deliberately separate: they operate synchronously through the private runtime/root scope and never use the host Value ABI.

This separation also leaves the internal representation free for a future LLVM backend and custom binary heap. Generated code can eventually use private tagged values and participate in the same GC safepoint/root protocol without changing host handlers or treating Value as a JIT ABI.

See Memory Management for the reference categories, allowed conversions, and collector invariants.

Design Notes

• Typed preparation: rex-engine prepares code into a typed form before execution. The current CompiledProgram stores a typed AST plus the environment snapshot needed to run it.
• Single-shot execution: evaluation is intentionally one-shot. CompiledProgram is moved into Evaluator::run with its runtime input map, consuming the evaluator as well. Prepare all required declarations/modules before constructing or consuming the evaluator.
• Single-use preparation: Builder::build_compiler(), Compiler::compile_program, and the Compiler::infer_* APIs consume their receivers. Each program run should create a fresh builder/compiler/evaluator lineage.
• Same-lineage runtime model: a CompiledProgram is intended to run on the evaluator produced from the same compiler. Rex programs are supplied as source and compiled per run, so Rex does not expose a portable compiled-artifact or cross-runtime linking model.
• Phase ownership: Builder owns embedder configuration only until build_compiler(). Compiler then owns preparation state: the type environment, runtime declaration environment, runtime registries, heap, module loader caches, and execution policy snapshot. Evaluator is built only by consuming that compiler, so runtime code cannot mutate modules or compile new declarations.
• Prelude ownership: rex-engine owns the standard prelude source, standard typing environment, and runtime contract. The split is:
  • typeclass and instance declarations written in Rex at rex-engine/src/prelude/typeclasses.rex
  • rex-engine/src/prelude/type_system.rs builds the prelude-enabled TypeSystem, including ADTs, parsed declarations, and primop schemes
  • rex-engine/src/prelude/mod.rs parses the Rex source and injects runtime method bodies/native implementations for Builder::with_prelude(state)?
  • rex-typesystem exposes generic registration/inference APIs and does not own the standard prelude
• Depth bounding: Some parts of the pipeline are naturally recursive (parsing deeply nested parentheses, matching deeply nested terms). The parser enforces a fixed AST-depth cap, and the typechecker-limit API provides bounded recursion for production/untrusted workloads.
• Import-use rewrite/validation: module processing resolves import aliases across expression vars, constructor patterns, type references, and class references; unresolved qualified alias members are rejected as module errors before runtime.
• Abstract module namespace: a ModuleId is a validated qualified Rex name such as std.prelude or ffmpeg.formats.av1. It does not encode a filesystem path, origin kind, URL, or content hash. Importers decide whether a module name maps to a file, database row, in-memory string, open editor buffer, generated AST, or Rust host module.
• Importer payloads and caching: importers are generic over host state and can return Rex source, a prebuilt CompilationPackage, or a Rust-backed Module<State>. Source imports are parsed into CompilationUnit values, then converted into CompilationPackage for compiler module processing. Source-derived and prebuilt packages are loaded through the SCC module graph path. Rust-backed modules are installed lazily through the same internal module installer used by eager inject_module, and are self-contained host modules rather than Rex source modules with nested import loading. Importer results are cached for one compile so the same request is not resolved repeatedly.

Intentional String Boundaries

Rex now prefers structured internal representations (for example NameRef, BuiltinTypeId, CanonicalSymbol, and module/type/class maps) across parser, type system, evaluator, and LSP rewrite paths. Remaining string usage is intentional in these boundary layers:

• Source text and parsing: the parser accepts source strings by definition.
• Human-facing diagnostics and display: error messages, hover text, CLI rendering, and debug output stringify symbols/types for readability.
• Protocol/serialization boundaries: JSON/LSP payloads are string-based and convert structured internal symbols/types at the edge.
• Module specifiers: parsed import names are textual before being resolved into validated ModuleId values and handed to importer policy.

Non-goal for this pass:

• Eliminating all .to_string() calls globally. The design target is to avoid stringly-typed core semantics, not to remove string conversion at UI/protocol boundaries.

OCI Executor Protocol

Rex compiles typed external-tool requests into ToolExecutionPlan values and then resolves them to executor-neutral OciJob values. Docker is the only production backend shipped by Rex. The protocol exists so a host can add a remote OCI service without changing Rex modules or exposing host execution.

An OciJob contains only:

• a host-selected OCI image and target os/architecture[/variant];
• a trusted command supplied by the installed tool and symbolic arguments;
• declared CAS blob or tree inputs and declared output slots;
• mandatory resource and result limits; and
• an explicit isolation policy.

It cannot carry a developer-machine path, arbitrary mount, environment override, backend option, device, or secret.

Logical workspace and CAS transfer

Input and output paths are logical slot numbers. A backend chooses its private filesystem paths or service objects after dispatch. Declared blob inputs are transferred by bytes. Tree inputs are transferred recursively while preserving entry names, kinds, and BLAKE3 identities.

After completion, a backend returns only hashes assigned to declared output slots. The caller verifies their kinds, total size, and CAS identities before making them visible to the workflow. Missing completion records, undeclared slots, wrong object kinds, changed hashes, excessive output, and malformed provenance are result-protocol failures. A nonzero tool exit remains an ordinary ToolExecution result.

Required capabilities

OciExecutorCapabilities declares controls a target can actually enforce. The shared validator rejects a job before dispatch if the target cannot provide any requested guarantee. The secure default requires:

• disabled networking;
• a read-only image root and read-only inputs;
• non-root execution, dropped capabilities, and no-new-privileges behavior;
• no devices, secrets, or additional mounts; and
• execution, stream, output, temporary-storage, memory, CPU, and PID limits.

A managed container product that cannot enforce a required control is not a conforming target for that job. An adapter must return Unsupported; it must never silently weaken policy.

Platform, images, and provenance

The executor reports its target platform. Every selected image must target that exact platform. Production image configuration requires a digest-qualified OCI reference; mutable tags are restricted to explicit local image development.

Every successful OCI execution includes ToolExecutionProvenance identifying the executor, target platform, immutable image digest, declared input hashes, and output hashes. This record makes the execution and data boundary auditable; it is not service attestation by itself.

Implementing a backend

A provider adapter implements OciJobExecutor. It owns authentication, submission, scheduling, polling, cancellation, private workspace or object storage, CAS transfer, and service cleanup. It must call or reproduce the shared validation contract before starting work and must pass workflow_oci_executor_conformance.

FakeRemoteOciExecutor is an in-memory protocol test double. It uses a CAS separate from the caller and proves that the boundary does not depend on Docker bind mounts. It is not a cloud executor: it provides no transport, authentication, multi-tenant isolation, durable remote storage, or service attestation.

Installable tool binaries

rex::workflow discovers typed tool modules at runtime. Give the CLI a directory with --tool-dir DIRECTORY or REX_TOOL_DIR; an import of tools.NAME looks for the executable rex-tool-NAME in that directory. Tools that are not imported are neither inspected nor started. When neither setting is present, the CLI searches beside its own executable.

Installing a tool means copying its executable into that directory. Removing it makes the module unavailable on the next workflow compilation. rex does not link to tool crates, so this does not require recompiling the workflow host.

Binary contract

Every tool is a separate Rust crate named rex-tool-NAME and its binary implements two commands:

rex-tool-NAME manifest
rex-tool-NAME execute FUNCTION [JSON]

If the JSON argument to execute is omitted, the binary reads it from standard input. Arguments may be an object keyed by the documented parameter names or a positional array. A successful command writes only JSON to standard output; diagnostics go to standard error and failures return a nonzero status.

manifest returns protocol version 1, the exact Rex module ID, and a stable TypeBundle:

{
  "protocolVersion": 1,
  "module": "tools.example",
  "typeBundle": {
    "docs": "Module documentation.",
    "values": {
      "ping": [{
        "scheme": { "type": {
          "kind": "fun",
          "params": [{ "kind": "builtin", "name": "String" }],
          "ret": { "kind": "builtin", "name": "String" }
        } },
        "params": ["message"],
        "docs": "Function documentation."
      }]
    },
    "adts": []
  },
  "defaults": []
}

The bundle contains every public function scheme, Rex-facing parameter name, module/function/type documentation, and every ADT owned by the module. defaults preserves concrete host-backed Default instances used by record construction and update. Protocol version 1 requires each function to have one non-overloaded, concrete type scheme because JSON cannot represent unresolved type variables.

For execute, the shared runner uses json_to_rex for every argument, invokes the ordinary typed module handler, and uses rex_to_json for its result. The generated handler therefore performs the normal FromRex conversions before entering Rust and IntoRex conversion on return. The proxy in The rex::workflow proxy uses the same two JSON conversion functions, so direct binary calls and calls from a workflow have identical representations.

Authoring a tool

A tool crate depends on rex, defines an ordinary Rust-backed module, and gives that module factory to the shared command runner:

use rex::{
    engine::{EngineError, Module},
    workflow::state::State,
};

fn module() -> Result<Module<State>, EngineError> {
    // Usually generated by #[rex::module] and #[rex::export].
    api::rex_module()
}

#[tokio::main]
async fn main() -> Result<(), Box<dyn std::error::Error>> {
    rex::workflow::tool_protocol::run_tool_cli(
        module,
        || rex::workflow::tool_protocol::default_tool_state(
            "example",
            "REX_TOOL_EXAMPLE_IMAGE",
            "rex-tool-example:local",
        ),
    )
    .await
}

The bundled examples are the six workspace crates rex-tool-ffmpeg, rex-tool-gnuplot, rex-tool-graphviz, rex-tool-imagemagick, rex-tool-poppler, and rex-tool-qpdf. Their Rust types derive Rex; exported async functions receive State, convert typed requests into OCI jobs, and return typed results.

Use State::store and the helpers in rex::storage for content-addressed blobs and trees. Use State::execute_tool with a ToolExecutionPlan containing the tool’s trusted command. A tool can instead construct an OciJob and invoke an OciJobExecutor such as DockerOciJobExecutor; the public job boundary provides the same CAS staging, output validation, limits, and isolation controls.

default_tool_state opens the filesystem CAS named by REX_STORE and configures the Docker OCI backend for the tool name, image variable, and development default supplied by that tool crate. Embedding hosts with a different deployment model may supply a different state factory to run_tool_cli.

Trust boundary

An installed tool binary is native code and is therefore trusted to the same degree as the Rex workflow host. The directory must not be writable by untrusted workflow authors. Rex source cannot select an arbitrary binary: the requested module ID determines one filename, and the binary’s manifest must declare that exact module and a supported protocol version.

The native binary is only the typed protocol adapter. External media, plotting, document, or scientific programs should still run through the OCI executor rather than directly on the host. Workflow source controls typed function arguments, not image references, mounts, executable paths, or Docker options.

Memory Management

rex-engine stores evaluator data in a private moving heap. The builder creates Heap, then ownership moves through the single-use pipeline:

Builder -> Compiler -> Evaluator

There is no public heap capability and no heap mutex. At any moment one task owns the complete runtime and has exclusive access to allocation and collection. The owning evaluator future may migrate between executor threads, but two threads cannot access the same heap concurrently.

Representation boundaries

The runtime deliberately separates three concerns:

Value is a host interchange model, not the evaluator’s internal value or a future JIT ABI. Its collection variants recursively own other Values. Evaluator-only states such as closures, native and overloaded functions, and uninitialized cells cannot be exported.

Value::List represents ordinary Rex lists. Value::Bytes is the canonical host representation of Rex List U8. Type-directed conversion returns Bytes for every physical list layout, including empty lists, cons chains, data-backed slices, binary-data slices, and mixed cons/slice values.

Runtime roots

An InternalPtr contains a heap identity, slot, and collection generation. It is valid only until an allocation that may collect unless it is already a traced cell edge or represented by a runtime root.

A RootedPtr is a stable generational token into the runtime root table. It does not expose a cell address. Collection rewrites the table entry when an object moves, allowing evaluator frames, environments, scheduler work, module values, and compiler state to retain the token. RootScope provides exclusive synchronous access for inspecting and allocating values and explicitly roots temporary results.

Machine-owned roots remain registered while they are present in evaluator or compiler state. At a collection safepoint the runtime traverses the current frames, environments, and scheduler state, removes stale root tokens, and then runs the collector. This traversal occurs only when collection is required; the evaluator does not persist and reconstruct its complete state around each ready work item.

Copying collection

Collection begins from the live runtime-root table. It traces private InternalPtr edges through reachable cells, copies reachable cells, and rewrites cell edges and runtime-root entries to the new generation. Debug builds verify that copied slots have the current generation, contain valid children, and remain reachable.

The object allocation path also protects child edges already placed in a pending cell. It temporarily registers those edges as runtime roots, collects, rewrites the pending cell from the relocated roots, releases the temporary entries on both success and failure, and only then installs the cell.

Extreme GC stress is available through a builder test setting. It collects at every evaluator safepoint and randomizes destinations so tests exercise root relocation rather than relying on stable slot numbers.

Host calls

Public host functions never receive Heap, RootScope, RootedPtr, or a capability that can obtain them. Public Context retains only host state and type-system metadata, not runtime registries or their root tokens. The call boundary is:

private heap --type-directed copy--> owned Value
owned Value --host work/future-----> owned Value
owned Value --validate and import--> private heap

Arguments are converted before a host callback is invoked. A synchronous dynamic callback owns Vec<Value>; an async callback future owns the same heap-independent data plus host state. When the result completes, the evaluator validates it against the instantiated Rex result type and imports it while it again has exclusive runtime access. Cancellation drops the owning runtime and host futures without acquiring a lock or unregistering roots from another thread.

The conversion kernel validates scalar and composite shapes, tuple and ADT arity, record fields, constructor identity, and concrete element types. It uses an explicit work stack for recursive data, so deeply nested ADTs do not consume the Rust call stack. List traversal is specialized and iterative.

Host-provided constants are imported once during module installation and retained as internal rooted constants. Looking one up does not schedule a host call or reconvert an owned Value.

Internal intrinsics

Prelude operations and generated constructors are not host functions. They use a crate-private intrinsic ABI that receives an active root scope and may inspect or allocate internal values directly. Higher-order intrinsics may return evaluator-managed work that applies Rex closures. This distinction is important: only genuinely external host work pays for conversion to and from Value.

Future runtimes

The current heap uses Rust cells, but no public API exposes their layout. Future LLVM-generated sequential regions can use private tagged values and a custom binary heap while preserving the same host boundary. Compiled code that may allocate will need to report live references at safepoints through stack maps, statepoints, or a compatible shadow-root mechanism. Value will remain the host interchange tree rather than becoming the generated-code calling convention.

No unsafe code is used by the current memory model.

Embedding Rex in Rust

Rex is designed as a small pipeline you can embed at whatever stage you need:

1. rex-parser: source → CompilationUnit { decls, body }
2. rex-typesystem: HM inference + type classes → TypedExpr (plus predicates/type)
3. rex-engine: build host modules, compile typed code into CompiledProgram, then run it → rex_engine::Value

This document focuses on common embedding patterns.

Running Untrusted Rex Code (Production Checklist)

This repo provides language-level parsing limits and a pure evaluator suitable for embedding. Your production server is responsible for enforcing hard resource limits (process isolation, wall-clock timeouts, memory limits).

Recommended defaults for untrusted input:

• Parsing enforces a fixed AST-depth cap.
• Run evaluation in an isolation boundary you can hard-kill (separate process/container), with CPU/RSS/time limits.

Evaluation API:

• Evaluation is async via Evaluator.

Compile Then Run

rex-engine now has an explicit preparation boundary:

• Builder builds the host environment.
• Compiler prepares user code into a CompiledProgram.
• Evaluator owns the runtime core and runs one prepared program with runtime inputs for main.

The whole builder/compiler/evaluator lineage is single-use. Builder::build_compiler() consumes the builder, Compiler::compile_program and Compiler::infer_* consume the compiler, and Evaluator::run consumes the evaluator, the compiled program, and a BTreeMap<String, Value> of inputs. Programs are compiled with Rex’s singular external interface semantics: an explicit fn main ... defines named runtime inputs, while a final expression without main is treated as an implicit zero-input main.

use rex::{
    engine::{CompileOptions, Builder},
    parser::parse,
};

let builder = Builder::with_prelude(())?;
let compiler = builder.build_compiler();

let parsed = parse("let x = 1 + 2 in x * 3").map_err(|errs| format!("{errs:?}"))?;
let (program, evaluator) = compiler
    .compile_program(&parsed, CompileOptions::for_module("workflow.main")?)
    .await?;
assert_eq!(program.result_type().to_string(), "i32");
let value = evaluator.run(program, Default::default()).await?;

What “compiled” means in the current design:

• parsing, import rewriting, declaration injection, and typechecking have already happened
• CompiledProgram carries a typed expression plus the environment snapshot needed to run it
• CompiledProgram::main_signature() reports input names/types and the external result type
• Evaluator owns the runtime core needed for execution
• Evaluator::run consumes the evaluator, compiled program, and runtime input map; use a new builder/compiler/evaluator lineage for another generated workflow

What is captured:

• Rex declarations that are part of the prepared program are captured into the compiled env snapshot
• host-provided exports registered through export, export_async, export_native, export_native_async, or export_value are carried by the evaluator produced from the same compiler
• typeclass method bindings are carried by that same evaluator runtime

That means a CompiledProgram is intended to be run by the evaluator created from the same compiler. Rex does not currently expose a portable compiled artifact or cross-runtime linking model.

Phase-specific errors:

• Compiler APIs return EngineError
• Evaluator::run returns EngineError
• APIs that parse, compile, and run in one call return ExecutionError because they cross phase boundaries

Runtime Values and Heap Ownership

Rex uses a moving copying collector, but the heap is entirely private and has one owner. External main inputs and evaluation results are owned Value trees containing no heap references. Composite variants recursively contain Value; closures, native functions, overloaded functions, and uninitialized cells cannot cross this boundary and produce a conversion error.

Value::List represents ordinary lists. Value::Bytes is the required representation for Rex List U8, including empty lists and lists whose internal representation mixes cons cells and vector-backed slices. Bytes is an embedding optimization, not a distinct Rex language type.

Host functions receive owned values before they start and return owned values that are validated and imported only after completion. Async host futures therefore contain no heap capability. See Memory Management for the complete internal ownership model.

Compile parsed Rex sources with Compiler::compile_program and pass the resulting CompiledProgram to Evaluator::run.

Evaluate Rex Code Directly

use rex::{
    engine::{Builder, CompileOptions},
    parser::parse,
};

let program = parse("let x = 1 + 2 in x * 3").map_err(|errs| format!("{errs:?}"))?;

let builder = Builder::with_prelude(())?;
let compiler = builder.build_compiler();
let (program, evaluator) = compiler
    .compile_program(&program, CompileOptions::for_module("workflow.main")?)
    .await?;
let value = evaluator.run(program, Default::default()).await?;
println!("{value}");

Rex source modules loaded via importers must be declaration-only. To run an expression, use snippet or program entry points. Qualified alias members used in type/class positions (annotations, where constraints, instance headers, superclass clauses) are validated against module exports during module processing; missing exports fail early with module errors.

Builder Initialization and Default Imports

Builder::with_prelude(state) is shorthand for Builder::with_options(state, EngineOptions::default()).

• Prelude is enabled by default.
• std.prelude is default-imported.
• Default imports are weak: they fill missing names, but never override local declarations or explicit imports.

If you want full control:

use rex::engine::{Builder, EngineOptions, PreludeMode};

let mut builder = Builder::with_options(
    (),
    EngineOptions {
        prelude: PreludeMode::Disabled,
        default_imports: vec![],
    },
)?;

Inject Modules (Embedder Patterns)

This is fully supported in rex-engine. You can compose module loading from:

• the bundled std.prelude virtual module
• modules injected with Builder::inject_module
• Rust modules returned lazily by importers
• custom async importers (for DB/object-store/in-memory modules)

1) Use an Explicit Importer

rex-engine does not read module files from disk by default. File-backed loading is a host policy decision; the CLI installs its own filesystem importer, while embedded applications should provide an importer that matches their trust boundary. Use DenyImporter when you need an explicit importer implementation that rejects every module request.

Notes:

• importers receive an ImportRequest with the requested ModuleId and optional importing module id.
• a ModuleId is a qualified namespace name, not a filesystem path; the CLI’s filesystem mapping is one importer policy, not a core engine rule.
• snippets and parsed programs load Rex source modules through the compiler’s import rewriting path; source-backed modules remain declaration-only.
• importer results are cached for one compile, so the same request is not sent through the importer chain repeatedly.
• import clauses ((*) / item lists) import exported names into unqualified scope.
• unqualified imports are context-sensitive: expression positions use values, type positions use types, and class/constraint positions use classes.
• module aliases (import x as M) provide qualified access to exported values, types, and classes.
• importing a name only brings in the facets that actually exist under that name.

2) Inject In-Memory Rex Modules

For host-managed modules, either call Builder::inject_module or add an importer that maps module IDs to source text or prebuilt compilation units.

use futures::future::BoxFuture;
use rex::{
    engine::{
        CompileOptions, Builder, ImportRequest, Importer, ResolvedModule, ResolvedModuleContent,
    },
    parser::parse,
};
use std::collections::HashMap;
use std::sync::Arc;

let mut builder = Builder::with_prelude(())?;

let modules = Arc::new(HashMap::from([
    (
        "acme.math".to_string(),
        "pub fn inc : i32 -> i32 = \\x -> x + 1;".to_string(),
    ),
    (
        "acme.main".to_string(),
        "import acme.math (inc);\npub fn main : i32 = inc 41;".to_string(),
    ),
]));

struct MapImporter {
    modules: Arc<HashMap<String, String>>,
}

impl Importer for MapImporter {
    fn import<'a>(
        &'a self,
        req: ImportRequest,
    ) -> BoxFuture<'a, Result<Option<ResolvedModule>, rex::engine::EngineError>> {
        Box::pin(async move {
            let module_name = req.module_id.to_string();
            let Some(source) = self.modules.get(&module_name) else {
                return Ok(None);
            };
            Ok(Some(ResolvedModule {
                id: req.module_id,
                content: ResolvedModuleContent::Source(source.clone()),
            }))
        })
    }
}

builder.add_importer(Arc::new(MapImporter { modules }));
let compiler = builder.build_compiler();
let parsed = parse("import acme.main (main);\nmain").map_err(|errs| format!("{errs:?}"))?;
let (program, evaluator) = compiler
    .compile_program(&parsed, CompileOptions::for_module("workflow.main")?)
    .await?;
let value = evaluator.run(program, Default::default()).await?;
println!("{value}");

3) Host-Provided Rust Functions, Exposed as Modules

This is the common embedder case.

Use Module + Builder::inject_module(...):

1. Create a Module.
2. Add exports:
   • typed exports with export / export_async
   • runtime/native exports with export_native / export_native_async
   • optional structured declarations with add_rex_adt / add_adt_decl
   • optional typeclass instances for existing classes with add_instance
3. Inject it into the builder.

Module::add_rex_adt::<T>() now stages the full acyclic ADT family reachable from T. This is driven by RexType::collect_rex_family(...): ADT types contribute declarations there, while leaf Rex types inherit a no-op default. For example, if Label contains a Side, staging Label is enough; you do not need to stage Side separately. Cyclic ADT families are still rejected.

Module is intentionally narrower than a general Rex declaration package. Embedders can stage host-provided ADTs, host exports, and instances of existing typeclasses. Arbitrary Rex declarations belong in CompilationPackage, not Module. Type declarations come from the staged ADTs; call Module::declarations() when you need the derived Declarations package view used by the compiler.

export handlers are fallible and must return Result<T, EngineError>. If a handler returns Err(...), evaluation fails with that engine error. export_async handlers follow the same rule, but return Future<Output = Result<T, EngineError>>.

Both forms receive owned arguments copied from the evaluator heap. The returned owned value is validated and imported in a later evaluator cycle. Synchronous handlers resume through an immediately-ready native completion; they do not consume async-native permits or pass through AsyncCallPolicy. They run on the evaluator task, so blocking or long-running work belongs in an asynchronous export.

use rex::{
    engine::{CompileOptions, Builder, Module},
    parser::parse,
};

let mut builder = Builder::with_prelude(())?;

let mut math = Module::new(
    "acme.math",
    Some("Arithmetic operations provided by the host.".to_owned()),
);
math.export("inc", |_state: (), x: i32| { Ok(x + 1) })?;
math.export_async("double_async", |_state: (), x: i32| async move { Ok(x * 2) })?;
builder.inject_module(math)?;
let compiler = builder.build_compiler();
let parsed = parse("import acme.math (inc, double_async as d);\ninc (d 20)")
    .map_err(|errs| format!("{errs:?}"))?;
let (program, evaluator) = compiler
    .compile_program(&parsed, CompileOptions::for_module("workflow.main")?)
    .await?;
let value = evaluator.run(program, Default::default()).await?;
println!("{value}");

For API surfaces primarily consumed by agents, use the registration attributes so Rust doc comments become Rex metadata automatically:

/// Arithmetic tools exposed by this host.
#[rex::module(name = "acme.math", defaults(Input))]
mod math {
    use rex::engine::EngineError;

    /// A value supplied to arithmetic operations.
    #[derive(Clone, Default, rex::Rex)]
    #[rex(export)]
    pub struct Input {
        /// The integer to operate on.
        pub value: i32,
    }

    /// Increment an input by one.
    #[rex::export(name = "inc")]
    pub fn increment(_state: (), input: Input) -> Result<Input, EngineError> {
        Ok(Input { value: input.value + 1 })
    }
}

let mut builder = rex::engine::Builder::with_prelude(())?;
builder.inject_module(math::rex_module()?)?;

#[rex::module] generates rex_module(). It copies the module’s Rust doc comments, collects functions marked #[rex::export], and stages non-generic derived ADTs marked #[rex(export)]. #[rex::export] supports synchronous and asynchronous functions, preserves the function’s Rust doc comments and Rex-visible parameter names, and generates a <function>_rex_export() helper. Every derived ADT reachable through an exported function’s argument or result types is staged automatically, including ADTs nested inside standard containers.

The optional defaults(Type, ...) module argument stages a qualified Rex Default instance for each listed concrete Rust type. A listed type must implement RexDefault<State> and IntoRex; ordinary Rust Default types receive RexDefault through its blanket implementation. The native value producer is private, while the instance becomes available when the named module is imported. This permits explicitly typed option construction such as tool Options {} or tool Options { retries = 3 }. Omitted fields come from the registered default.

Rust does not allow #[doc] attributes or doc comments on individual function parameters. Parameter descriptions therefore belong in the function-level doc comment; Rex metadata stores only each parameter’s Rust identifier. The host-state parameter is not part of the Rex signature or its parameter-name metadata.

The lower-level APIs remain available for dynamic registration. Pass module documentation as the second argument to Module::new; use Export::with_docs and Export::with_param_names for an export; set AdtDecl::docs; and pass variant documentation to AdtDecl::add_variant. AdtParam, AdtArgument, and AdtField carry documentation for the corresponding parts of an ADT. Repeated ADT registrations merge missing documentation and reject contradictory documentation for the same declaration. Named modules preserve generic-parameter documentation through their intermediate TypeDecl using documented TypeParam entries. Rustdoc itself does not render generic-parameter documentation, so put #[allow(unused_doc_comments)] on a documented generic parameter when warnings are denied. Module::global() keeps its no-argument signature and creates the root module without module-level documentation.

Before injection, metadata can be inspected through Module::docs, Module::exports (using each export’s docs() and params() methods), and Module::adts. After registration, the same function and ADT metadata lives on RegisteredValue and AdtDecl entries in the builder or compiler’s TypeSystem.

Documentation is also preserved in the JSON-facing TypeBundle wire format. A bundle can carry explicit bundle-level docs, documented overloads and parameter names, and documented ADTs down to type parameters, variants, constructor arguments, and record fields. TypeBundle::from_registered_values preserves the value docs and parameter names in its RegisteredValue inputs, but leaves the bundle-level docs field unset; call TypeBundle::with_docs when the bundle itself needs docs. TypeBundle::from_schemes has no value docs to preserve and generates names such as arg0 for function parameters. The manifest builder currently uses this latter path. Wire parameter metadata is a list of strings because individual parameters have no documentation of their own. The wire format intentionally has no schema-version constant or schemaVersion field. When persisting a virtual module as a bundle, its module-level docs can be stored in this top-level bundle field. TypeBundle::into_parts returns a DecodedTypeBundle with named docs, adts, and values fields. TypeBundle::register_into installs those ADTs and returns a RegisteredTypeBundle with named docs and values fields.

You can declare ADTs directly inside an injected host module:

use rex_ast::Symbol;
use rex_engine::{Builder, Module};
use rex_typesystem::types::{AdtArgument, BuiltinTypeId, Type};

let mut builder = Builder::with_prelude(())?;

let mut m = Module::new(
    "acme.status",
    Some("Status values returned by host operations.".to_owned()),
);
let mut status = builder.adt_decl("Status", &[]);
status.docs = Some("The state of a host operation.".to_owned());
status.add_variant(
    Symbol::intern("Ready"),
    vec![],
    Some("The operation completed successfully.".to_owned()),
);
status.add_variant(
    Symbol::intern("Failed"),
    vec![AdtArgument::Positional {
        typ: Type::builtin(BuiltinTypeId::String),
        docs: Some("A human-readable failure message.".to_owned()),
    }],
    Some("The operation failed.".to_owned()),
);
m.add_adt_decl(status)?;
builder.inject_module(m)?;

Then Rex code can import and use those names from the module:

import acme.status (Status, Failed);

let fail: String -> Status = \msg -> Failed msg in
match (fail "boom") with {
  case Failed msg -> length msg;
  case _ -> 0;
}

Status is used here in type position, while Failed is used in expression/pattern positions. They are imported through the same name-based mechanism.

Internally this generates module declarations and injects host implementations under qualified module export symbols.

If you need to construct exports separately (for example to build a module from plugin metadata), you can use:

• Export::from_handler / Export::from_async_handler (typed handlers)
• Export::from_native / Export::from_native_async (value-based native handlers)

These constructors initially use generated parameter names such as arg0 and have no docs. Chain Export::with_param_names and Export::with_docs when supplying API metadata, then add the export with Module::add_export. Adding it also stages any derived ADT family required by the export’s Rust signature.

This example shows how to use Rust enums and structs as Rex-facing types with ADTs declared inside the module itself. The host function accepts a Rust Label (containing a Rust Side enum), and Rex code calls it through sample.render_label.

Example:

use rex::{
    Rex,
    engine::{CompileOptions, Builder, EngineError, Module},
    parser::parse,
};

#[derive(Clone, Debug, PartialEq, Rex)]
enum Side {
    Left,
    Right,
}

#[derive(Clone, Debug, PartialEq, Rex)]
struct Label {
    text: String,
    side: Side,
}

fn render_label(label: Label) -> String {
    match label.side {
        Side::Left => format!("{:<12}", label.text),
        Side::Right => format!("{:>12}", label.text),
    }
}

let mut builder = Builder::with_prelude(())?;

let mut m = Module::new("sample", None);
m.add_rex_adt::<Label>()?;
m.export("render_label", |_state: (), label: Label| {
    Ok::<String, EngineError>(render_label(label))
})?;
builder.inject_module(m)?;
let compiler = builder.build_compiler();
let parsed = parse(
    r#"
    import sample (Label, Left, Right, render_label);
    (
        render_label (Label { text = "left", side = Left }),
        render_label (Label { text = "right", side = Right })
    )
    "#,
)
.map_err(|errs| format!("{errs:?}"))?;
let (program, evaluator) = compiler
    .compile_program(&parsed, CompileOptions::for_module("workflow.main")?)
    .await?;
let value = evaluator.run(program, Default::default()).await?;
println!("{value}"); // ("left        ", "       right")

In that example:

• Label is imported once and then used as both a type name and a constructor value.
• Left and Right are imported as constructor values.
• render_label is imported as a value.

3a) Runtime-Defined Signatures (Value APIs)

If your host determines function signatures/behavior at runtime, use the native module export APIs and provide an explicit Scheme + arity:

• Module::export_native
• Module::export_native_async

These callbacks receive Context<State> (not just &State), so they can:

• read state via ctx.state()
• inspect typed call information via the explicit &Type / Type callback parameter

Async native callbacks receive owned argument vectors and return Send + 'static futures. The host scheduler owns and polls those futures while the evaluator retains exclusive heap ownership. Context retains only shared host state and type-system metadata; it does not retain evaluator registries, runtime roots, or another indirect heap capability. Synchronous native callbacks use the same Context/Value boundary and completion machinery, but produce an immediately-ready result. They are not subject to async admission or executor policy and should remain short and nonblocking.

A callback owns its Vec<Value> arguments and may move an argument directly into its result. It may also construct a new owned Value; it cannot inspect or allocate in the evaluator heap.

use futures::FutureExt;
use rex_engine::{Builder, Context, Module, Value};
use rex::typesystem::{BuiltinTypeId, Scheme, Type};

let mut builder = Builder::with_prelude(())?;

let mut m = Module::new("acme.dynamic", None);
let scheme = Scheme::new(vec![], vec![], Type::fun(Type::builtin(BuiltinTypeId::I32), Type::builtin(BuiltinTypeId::I32)));

m.export_native("id_value", scheme.clone(), 1, |_ctx: Context<()>, _typ: &Type, mut args: Vec<Value>| {
    Ok(args.remove(0))
})?;

m.export_native_async("answer_async", Scheme::new(vec![], vec![], Type::builtin(BuiltinTypeId::I32)), 0, |_ctx: Context<()>, _typ: Type, _args: Vec<Value>| {
    async move { Ok(Value::I32(42)) }.boxed()
})?;

builder.inject_module(m)?;

Scheme and arity must agree. Registration returns an error if the type does not accept the provided number of arguments.

3b) Lazy Rust Modules From Importers

If many Rust modules are available but most programs import only a few, an importer can build and return a Module<State> on demand. This keeps Builder::inject_module as the eager path, while letting embedders defer expensive module construction until Rex code actually imports that module.

use futures::future::BoxFuture;
use rex::{
    engine::{
        Builder, CompileOptions, EngineError, ImportRequest, Importer, Module, ModuleId,
        ResolvedModule, ResolvedModuleContent,
    },
    parser::parse,
};
use std::sync::Arc;

#[derive(Clone)]
struct ToolImporter {
    tools_id: ModuleId,
}

impl Importer for ToolImporter {
    fn import<'a>(
        &'a self,
        req: ImportRequest,
    ) -> BoxFuture<'a, Result<Option<ResolvedModule>, EngineError>> {
        Box::pin(async move {
            if req.module_id != self.tools_id {
                return Ok(None);
            }

            let mut tools = Module::new(self.tools_id.to_string(), None);
            tools.export("inc", |_state: (), x: i32| Ok(x + 1))?;

            Ok(Some(ResolvedModule {
                id: self.tools_id.clone(),
                content: ResolvedModuleContent::module(tools),
            }))
        })
    }
}

let mut builder = Builder::with_prelude(())?;
let tools_id = ModuleId::parse("workflow.tools")?;
builder.add_importer(Arc::new(ToolImporter { tools_id }));

let compiler = builder.build_compiler();
let parsed = parse("import workflow.tools (inc);\ninc 41")
    .map_err(|errs| format!("{errs:?}"))?;
let (program, evaluator) = compiler
    .compile_program(&parsed, CompileOptions::for_module("workflow.main")?)
    .await?;
let value = evaluator.run(program, Default::default()).await?;
println!("{value}");

Lazy Rust-module rules:

• the returned Module<State> must use the same State type as the builder/compiler.
• the module must be a named module, not Module::global().
• the module’s qualified name must match the returned ResolvedModule.id.
• lazy Rust modules are installed through the same internal path as eager named Builder::inject_module, so exports, module-local ADTs, type declarations, caches, and native runtime registrations behave the same.
• a lazy Rust module is self-contained host code; the engine does not run the Rex source SCC loader over imports inside it.

4) Custom Importer Contract (Advanced)

If you need dynamic/nonstandard module loading behavior, implement Importer<State>.

Importer contract:

• return Ok(Some(ResolvedModule { ... })) when you can satisfy the module.
• return Ok(None) to let the next importer try.
• return Err(...) for hard failures (invalid module payload, policy violations, etc.).

ResolvedModule<State> can carry:

• ResolvedModuleContent::Source(...) for Rex source text.
• ResolvedModuleContent::CompilationPackage(...) for preconstructed structured Rex modules.
• ResolvedModuleContent::module(...) for a Rust-backed Module<State> installed lazily.

5) Snippets That Import Relative Modules

If you evaluate ad-hoc Rex snippets that contain imports, give the snippet an explicit module name in CompileOptions. Importers receive that name as ImportRequest::importer and decide how requested module IDs map to files, databases, in-memory source, Rust modules, or any other backing store. The core engine treats module IDs as names in an abstract namespace; filesystem-relative behavior is an importer policy.

use rex::{
    engine::{CompileOptions, Builder},
    parser::parse,
};

let builder = Builder::with_prelude(())?;
let compiler = builder.build_compiler();
let parsed = parse("import foo.bar as Bar;\nBar.add 1 2")
    .map_err(|errs| format!("{errs:?}"))?;
let (program, evaluator) = compiler
    .compile_program(&parsed, CompileOptions::for_module("workflow.snippet")?)
    .await?;
let value = evaluator.run(program, Default::default()).await?;

Builder State

Builder is generic over host state: Builder<State>, where State: Clone + Send + Sync + 'static. The state is owned by the builder, moved into the compiler/runtime lineage, and shared across all injected functions.

• Use Builder::with_prelude(())? if you do not need host state.
• If you do, pass your state struct into Builder::new(state) or Builder::with_prelude(state).
• export / export_async callbacks receive an owned clone of State as their first parameter.
• Value-based native APIs (export_native*) receive Context<State> so they can read ctx.state(); the context deliberately exposes no heap access.

use rex_engine::{Builder, Module};

#[derive(Clone)]
struct HostState {
    user_id: String,
    roles: Vec<String>,
}

let mut builder: Builder<HostState> = Builder::with_prelude(HostState {
    user_id: "u-123".into(),
    roles: vec!["admin".into(), "editor".into()],
})?;

let mut globals = Module::global();
globals.export("have_role", |state, role: String| {
    Ok(state.roles.iter().any(|r| r == &role))
})?;
builder.inject_module(globals)?;

List Interop at Host Boundaries

Rex exposes one collection type to user code: List a. Rust Vec<T> values convert to and from List T, so host functions can accept list literals and return list values without explicit representation conversions.

accept_bytes [1, 2, 3]

where accept_bytes is exported from Rust with a Vec<u8> parameter.

Internally, lists may be represented either as linked Cons/Empty cells or as a slice over contiguous heap data. That choice is not exposed to Rex code: list constructors, list literals, pattern matching, and prelude collection functions all operate on the same List a abstraction.

For Vec<u8>, Rex uses a binary data backing so host byte buffers do not need one heap allocation per byte. The Rex type is still List u8, and host functions accepting Vec<u8> can read lists backed by binary data, ordinary list data, or cons cells followed by either backing.

match bytes with {
    case Cons head _ -> head;
    case Empty -> 0;
}

Typecheck Without Evaluating

use rex::{
    engine::standard_type_system,
    parser::parse,
    typesystem::infer,
};

let program = parse("map (\\x -> x) [1, 2, 3]").map_err(|errs| format!("{errs:?}"))?;

let mut ts = standard_type_system()?;
for decl in &program.decls {
    match decl {
        rex_ast::Decl::Type(d) => ts.register_type_decl(d)?,
        rex_ast::Decl::Class(d) => ts.register_class_decl(d)?,
        rex_ast::Decl::Instance(d) => {
            ts.register_instance_decl(d)?;
        }
        rex_ast::Decl::Fn(d) => ts.register_fn_decls(std::slice::from_ref(d))?,
    }
}

let body = program
    .body
    .as_ref()
    .expect("snippet must contain a final expression");
let (preds, ty) = infer(&mut ts, body.as_ref())?;
println!("type: {ty}");
if !preds.is_empty() {
    println!(
        "constraints: {}",
        preds.iter()
            .map(|p| format!("{} {}", p.class, p.typ))
            .collect::<Vec<_>>()
            .join(", ")
    );
}

Type Classes and Instances

Users can declare new type classes and instances directly in Rex source. As the host, you:

1. Parse Rex source into CompilationUnit { decls, body }.
2. Inject Decl::Class / Decl::Instance into the type system (if you’re typechecking without running).
3. Compile the full program through Compiler (if you’re running), so instance method bodies are available at runtime.

Typecheck: Inject Class/Instance Decls into TypeSystem

use rex::{
    engine::standard_type_system,
    parser::parse,
    typesystem::infer,
};

let code = r#"
class Size a where {
    size : a -> i32;
}
instance<t> Size (List t) where {
    size = \xs ->
        match xs {
            case Empty -> 0;
            case Cons _ rest -> 1 + size rest;
        };
}
size [1, 2, 3]
"#;

let program = parse(code).map_err(|errs| format!("{errs:?}"))?;

let mut ts = standard_type_system()?;
for decl in &program.decls {
    match decl {
        rex_ast::Decl::Type(d) => ts.register_type_decl(d)?,
        rex_ast::Decl::Class(d) => ts.register_class_decl(d)?,
        rex_ast::Decl::Instance(d) => {
            ts.register_instance_decl(d)?;
        }
        rex_ast::Decl::Fn(d) => ts.register_fn_decls(std::slice::from_ref(d))?,
    }
}

let body = program
    .body
    .as_ref()
    .expect("snippet must contain a final expression");
let (_preds, ty) = infer(&mut ts, body.as_ref())?;
assert_eq!(ty.to_string(), "i32");

Evaluate: Inject Decls into Builder

use rex_engine::{Builder, CompileOptions};
use rex::parser::parse;

let code = r#"
class Size a where {
    size : a -> i32;
}
instance<t> Size (List t) where {
    size = \xs ->
        match xs {
            case Empty -> 0;
            case Cons _ rest -> 1 + size rest;
        };
}
(size [1, 2, 3], size [])
"#;

let program = parse(code).map_err(|errs| format!("{errs:?}"))?;

let builder = Builder::with_prelude(())?;
let compiler = builder.build_compiler();
let (compiled, evaluator) = compiler
    .compile_program(&program, CompileOptions::for_module("workflow.main")?)
    .await?;
let _ty = compiled.result_type().clone();
let value = evaluator.run(compiled, Default::default()).await?;
println!("{value}");

Inject Native Values and Functions

rex-engine is the boundary where Rust provides implementations for Rex values.

For host-provided modules, prefer Module + inject_module (above). For root-scope values or functions, use Module::global() and inject that staged module into the builder.

use rex_engine::{Builder, Module};

let mut builder = Builder::with_prelude(())?;
let mut globals = Module::global();
globals.export_value("answer", 42i32)?;
globals.export("inc", |_state, x: i32| { Ok(x + 1) })?;
builder.inject_module(globals)?;

Owned constants are converted and imported once when their module is installed. Reading a constant does not invoke a host callback or repeat the Value boundary conversion.

Integer Literal Overloading with Host Natives

Integer literals are overloaded (Integral a) and can specialize at call sites. This works for direct calls, let bindings, and lambda wrappers:

use rex::parser::parse;
use rex_engine::{Builder, CompileOptions, Module};

for code in [
    "num_u8 4",
    "let x = 4 in num_u8 x",
    "let f = \\x -> num_i64 x in f 4",
] {
    let mut builder = Builder::with_prelude(())?;
    let mut globals = Module::global();
    globals.export("num_u8", |_state: (), x: u8| Ok(format!("{x}:u8")))?;
    globals.export("num_i64", |_state: (), x: i64| Ok(format!("{x}:i64")))?;
    builder.inject_module(globals)?;

    let program = parse(code).map_err(|errs| format!("parse error: {errs:?}"))?;
    let compiler = builder.build_compiler();
    let (compiled, evaluator) = compiler
        .compile_program(&program, CompileOptions::for_module("workflow.main")?)
        .await?;
    let _ty = compiled.result_type().clone();
    let value = evaluator.run(compiled, Default::default()).await?;
    println!("{value}");
}

Negative literals specialize only to signed numeric types. For example, num_i32 (-3) is valid, while num_u32 (-3) is a type error.

Float literals are similarly context-sensitive for primitive float widths. A literal such as 3.0 defaults to f32 when unconstrained, but specializes to f64 when passed to a native or Rex function whose argument type is f64.

Async Natives

If your host functions are async, stage them in a module with export_async and run the compiled program with Evaluator::run.

use rex::parser::parse;
use rex_engine::{Builder, CompileOptions, Module};

let mut builder = Builder::with_prelude(())?;
let mut globals = Module::global();
globals.export_async("inc", |_state, x: i32| async move { Ok(x + 1) })?;
builder.inject_module(globals)?;

let program = parse("inc 1").map_err(|errs| format!("parse error: {errs:?}"))?;
let compiler = builder.build_compiler();
let (compiled, evaluator) = compiler
    .compile_program(&program, CompileOptions::for_module("workflow.main")?)
    .await?;
let _ty = compiled.result_type().clone();
let v = evaluator.run(compiled, Default::default()).await?;
println!("{v}");

By default, admitted async host futures are polled inline by the evaluator. This keeps the runtime portable and avoids assuming a particular runtime, which is important for wasm embedders. Inline polling is fine for futures that are naturally non-blocking, but CPU-heavy or blocking work should be moved onto an executor supplied by the embedding application.

Admission, callback invocation, and future polling occur without lending out the evaluator heap. Arguments and completed results are owned Values throughout suspension, so an async callback may retain or move them without depending on a heap location.

Use set_parallelism_controller to decide when async host callbacks may be invoked. A ParallelismController grants a NativeAsyncPermit for each admitted async native call; the permit is held until that call completes. Controllers can therefore enforce process-local limits, shared limits across several evaluators, or externally coordinated limits backed by a cluster scheduler.

ExecutionBounds remains available as a fixed controller. Its max_ready_work value is only an internal evaluator queue-pressure guard: it limits how many already-created Rex frames sit in the active ready queue, but it does not reserve external compute capacity. Native async permits are the backpressure mechanism for host jobs.

Use set_async_call_policy to wrap futures after they have been admitted. The policy decides where an admitted future runs; the parallelism controller decides whether the host callback is allowed to start yet.

use futures::FutureExt;
use rex_engine::{AsyncCallPolicy, Builder, EngineError, Module};

let mut builder = Builder::with_prelude(())?;
builder.set_async_call_policy(AsyncCallPolicy::executor_fn(|future| {
    async move {
        tokio::spawn(future)
            .await
            .map_err(|err| EngineError::Internal(format!("async host task failed: {err}")))?
    }
    .boxed()
}));

let mut globals = Module::global();
globals.export_async("inc", |_state, x: i32| async move { Ok(x + 1) })?;
builder.inject_module(globals)?;

The executor hook is intentionally generic rather than Tokio-specific. Native applications can use Tokio or any other Rust executor; wasm applications can keep the inline policy or adapt to browser task primitives in the host crate.

Parsing Limits

Parsing enforces a fixed AST-depth cap:

use rex::parser::parse;

let program = parse("(((1)))")
    .map_err(|errs| format!("parse error: {errs:?}"))?;

Bridge Rust Types with #[derive(Rex)]

The derive:

• implements RexType
• implements RexAdt
• implements Rex
• implements IntoRex
• implements FromRex
• provides injection helpers through Rex
• provides ADT declaration helpers through RexAdt
• declares an ADT in the Rex type system
• injects runtime constructors (so Rex can build values)
• discovers and registers the full acyclic ADT family needed by the root type

The derive does not implement RexDefault; inject_rex_with_default is available only when the type already provides that trait.

Rust doc comments on the derived type, type parameters, enum variants, tuple fields, and named fields are copied into the generated AdtDecl. For a struct, the type’s docs also document its single generated constructor variant.

Fields of type Vec<T> are exposed as List T and convert to/from Rex lists. When constructing or updating derived records from Rex code, use list literals directly for these fields.

Rust char is a built-in bridge type corresponding to Rex Char; it can be used directly in injected function signatures and fields of derived types.

That means MyType::inject_rex(&mut builder)? is enough for acyclic graphs of derived ADTs. You do not need to manually register dependencies in topological order. Cyclic ADT families are still not supported by this registration path.

If a field uses a Rust type that participates in Rex value conversion but is not itself a Rex ADT (for example a leaf type with manual RexType / IntoRex / FromRex impls), no extra field annotation is required. Such leaf types inherit the default no-op family collection from RexType, so derived ADTs can contain them without trying to register them as ADTs.

use rex::{
    Rex,
    engine::{Builder, EngineError, FromRex, IntoRex, Value},
    typesystem::{RexType, Type},
};

#[derive(Debug, PartialEq)]
struct AtomRef(i32);

impl RexType for AtomRef {
    fn rex_type() -> Type {
        i32::rex_type()
    }
}

impl IntoRex for AtomRef {
    fn into_rex(self) -> Result<Value, EngineError> {
        self.0.into_rex()
    }
}

impl FromRex for AtomRef {
    fn from_rex(value: Value) -> Result<Self, EngineError> {
        Ok(Self(i32::from_rex(value)?))
    }
}

#[derive(Rex, Debug, PartialEq)]
struct Fragment(Vec<AtomRef>);

let mut builder = Builder::with_prelude(())?;
Fragment::inject_rex(&mut builder)?;

use rex::{
    Rex,
    engine::{Builder, CompileOptions, FromRex},
    parser::parse,
};

#[derive(Rex, Debug, PartialEq)]
enum Maybe<T> {
    Just(T),
    Nothing,
}

let mut builder = Builder::with_prelude(())?;
Maybe::<i32>::inject_rex(&mut builder)?;

let program = parse("Just 1").map_err(|errs| format!("parse error: {errs:?}"))?;
let compiler = builder.build_compiler();
let (compiled, evaluator) = compiler
    .compile_program(&program, CompileOptions::for_module("workflow.main")?)
    .await?;
let _ty = compiled.result_type().clone();
let v = evaluator.run(compiled, Default::default()).await?;
assert_eq!(Maybe::<i32>::from_rex(&v)?, Maybe::Just(1));

Register ADTs Without Derive

If your type metadata is data-driven (for example loaded from JSON), you can build ADTs without #[derive(Rex)].

• Use Builder::adt_decl_from_type(...) to seed an ADT declaration from a Rex type head.
• Add variants with AdtDecl::add_variant(name, args, docs), where args is a Vec<AdtArgument> and docs is an Option<String>.
• Stage it with Module::add_adt_decl(...), then inject that module with Builder::inject_module(...).

Module::add_adt_decl(...) is the low-level single-ADT staging primitive. If you are building several ADTs manually, prefer batching them in one module with add_adt_family(...).

use rex::{
    ast::Symbol,
    engine::{Builder, Module},
    typesystem::{AdtArgument, RexType, Type},
};

let mut builder = Builder::with_prelude(())?;
let mut globals = Module::global();

let mut adt = builder.adt_decl_from_type(&Type::con("PrimitiveEither", 0))?;
adt.add_variant(
    Symbol::intern("Flag"),
    vec![AdtArgument::positional(bool::rex_type())],
    None,
);
adt.add_variant(
    Symbol::intern("Count"),
    vec![AdtArgument::positional(i32::rex_type())],
    None,
);
globals.add_adt_decl(adt)?;
builder.inject_module(globals)?;

If you have a Rust type with manual RexType/IntoRex/FromRex impls, implement RexAdt and provide rex_adt_decl(). Then Builder::inject_rex_adt::<T>() gives manual types the same registration workflow that #[derive(Rex)] exposes as T::inject_rex(...).

If the manual Rust type is itself an ADT, override RexType::collect_rex_family(...) and add its AdtDecl there. Leaf types can inherit the default no-op implementation.

use rex::{
    ast::Symbol,
    engine::Builder,
    typesystem::{AdtArgument, AdtDecl, RexAdt, RexType, Type, TypeError, TypeVarSupply},
};

struct PrimitiveEither;

impl RexType for PrimitiveEither {
    fn rex_type() -> Type {
        Type::con("PrimitiveEither", 0)
    }

    fn collect_rex_family(out: &mut Vec<AdtDecl>) -> Result<(), TypeError> {
        out.push(<Self as RexAdt>::rex_adt_decl()?);
        Ok(())
    }
}

impl RexAdt for PrimitiveEither {
    fn rex_adt_decl() -> Result<AdtDecl, TypeError> {
        let mut supply = TypeVarSupply::new();
        let mut adt = AdtDecl::new(&Symbol::intern("PrimitiveEither"), &[], &mut supply);
        adt.add_variant(
            Symbol::intern("Flag"),
            vec![AdtArgument::positional(bool::rex_type())],
            None,
        );
        adt.add_variant(
            Symbol::intern("Count"),
            vec![AdtArgument::positional(i32::rex_type())],
            None,
        );
        Ok(adt)
    }
}

let mut builder = Builder::with_prelude(())?;
builder.inject_rex_adt::<PrimitiveEither>()?;

Depth Limits

Some workloads (very deep nesting) can exhaust parser/typechecker recursion depth. Prefer bounded limits for untrusted code:

• parser AST depth
• rex_typesystem::TypeSystemLimits::safe_defaults

Embedding workflow tool execution

The rex::workflow module does not execute operating-system tools directly on the host. Workflow hosts must configure OCI images and either the supplied Docker backend or an implementation of OciJobExecutor. There is no host-process executor.

Provider implementations receive logical CAS inputs and output declarations, not host paths or Docker arguments. They must enforce the requested platform, isolation, resource limits, cancellation, result validation, and provenance contract described in OCI Executor Protocol.

Contributing

Workspace Layout

Rex is a Cargo workspace. The most important crates are:

• rex-parser: source parsing into a CompilationUnit { decls, body }
• rex-ast: AST nodes, symbols, and spans
• rex-typesystem: Hindley–Milner inference + type classes + ADTs
• rex-engine: host environment building, compilation, evaluation, and native injection
• rex-proc-macro: derives and registration attributes for documented Rust types, functions, and modules exposed to Rex
• rex: top-level embedding facade and integration tests
• rex-cli: rex_cli command-line binary

Architecture overview: ARCHITECTURE.md.

Development

Run the full test suite:

cargo test

There is also a lightweight “fuzz smoke” test that runs a deterministic parse→infer→eval loop. You can scale iterations with REX_FUZZ_ITERS:

REX_FUZZ_ITERS=2000 cargo test -p rex --test fuzz_smoke

Fuzz Harnesses

For end-to-end fuzzing with external fuzzers (AFL++, honggfuzz, custom mutational drivers), the workspace includes rex-fuzz, a set of stdin-driven harness binaries:

cargo build -p rex-fuzz --bins
printf '1 + 2' | cargo run -q -p rex-fuzz --bin e2e
printf '(' | cargo run -q -p rex-fuzz --bin parse

Tuning knobs (environment variables):

• REX_FUZZ_STACK_MB: stack size (MiB) for the harness thread

If you edit Rust code, also run:

cargo fmt
cargo clippy

Lockfiles

This repo commits:

• Cargo.lock (workspace lockfile)
• rex-vscode/package-lock.json (VS Code extension)

Other lock-like files (for example under target/ or node_modules/) are build artifacts and should not be committed.

LLMs

Introduction and Rationale

Rex includes a semantic assistance layer designed first for machine clients that generate code, especially LLM agents, and second for humans using an editor. This ordering is deliberate. LLMs are fast at proposing code but weak at maintaining a precise internal model of a language’s static semantics over many edits. A practical system therefore externalizes semantic reasoning into stable, tool-facing interfaces that can be queried repeatedly. Human users still benefit from the same machinery, but the core design target is iterative machine control: propose code, observe structured feedback, apply a constrained repair, and repeat.

A key design decision is to prioritize structured outputs over prose. Natural-language diagnostics are useful for people, but brittle for agents. Rex exposes semantic information and quick-fix data through explicit command contracts so that an LLM can operate as a controller over the typechecker and editor transformations rather than as a parser of unstructured text.

Typed Holes as a Control Primitive

The center of the workflow is the typed hole, written as ?. A hole allows partial programs to be represented directly in source code. Instead of treating incompleteness as a syntax error, Rex keeps the program parseable and infers constraints around the missing expression.

This shifts generation from “write final code in one pass” to “write a scaffold, then solve local obligations.” For LLMs, this is a better fit: the model can produce a coarse structure, ask for the expected type at the hole, retrieve candidate repairs, and select one.

fn parse_ph : String -> Result f32 String = \raw ->
  if raw == "7.3" then Ok 7.3 else Err "bad reading";

fn classify_ph : f32 -> String = \ph ->
  if ph < 6.8 then "acidic"
  else if ph > 7.8 then "alkaline"
  else "stable";

fn qc_label_from_sensor : String -> Result String String = \raw ->
  match (parse_ph raw) with {
    case Ok ph -> Ok (classify_ph ph);
    case Err e -> Err e;
  };

let sensor_reading = "7.3" in
let qc_label : Result String String = ? in
qc_label

In an LSP-enabled editor (including the browser playground), placing the cursor on ? exposes hole-filling actions and semantic candidates such as qc_label_from_sensor sensor_reading. The expected type at the hole is Result String String, so the model can fill a semantically meaningful real-world step without guessing. The same machinery is consumed by VS Code and by external LLM tooling.

Semantic Loop Endpoints

Rex provides semantic commands that return JSON-shaped data for program state at a position. The most important operation is a single semantic loop step, which reports expected and inferred types, in-scope values, candidate functions and adapters, local diagnostics, quick-fixes, and hole metadata.

From a control-systems viewpoint, this is an observation function over the current text. Separate commands apply an immutable quick-fix proposal bound to that text snapshot, or repeatedly apply best-ranked quick-fixes in bulk mode. Bulk mode also supports a dry-run option so agents can preview predicted text without committing edits.

The intended loop is simple: observe, choose, apply, re-observe. This structure is robust because it avoids fragile prompt-only planning and continuously re-anchors decisions in the compiler’s current state.

Candidate Narrowing and Adapter-Aware Repair

Candidate generation is hole-targeted and type-directed. Rex prefers functions whose result type can satisfy the local expected type and attempts to satisfy function arguments from in-scope values. When no direct value exists for an argument, Rex can propose single-step adapter expressions derived from in-scope functions.

This does not prove semantic correctness. It proves local type plausibility and improves search efficiency. The mechanism narrows the action space; it does not replace domain reasoning.

fn mk : i32 -> String = \n -> "value";
let x = 1 in
let y : String = ? in
y

In the editor, the hole can be filled with a candidate such as mk x, generated from local type compatibility and in-scope bindings.

Bulk Repair, Dry Runs, and Contracts

Rex supports multi-step quick-fix application around a cursor location. Bulk repair is useful for agents because it can reduce several local errors in one command while returning telemetry about what changed at each step. Dry-run mode computes the same sequence but reports predicted output without mutating source text.

The semantic endpoints use a stable JSON contract with regression tests. This matters operationally: agents are software clients, and software clients break when response schemas drift. Contract tests convert “it usually works” into “it remains parseable across refactors.”

Resource Bounds and Adversarial Inputs

Semantic assistance can become expensive when scope size is large. To keep the system usable under load and safer for embedded deployments, Rex enforces explicit limits in semantic candidate pipelines, including caps on scanned environment schemes, in-scope values, candidate list sizes, and hole-report counts. This is a pragmatic defense against unbounded CPU and output growth in LSP-side analysis.

These bounds are not a complete security model. They should be combined with host-level timeouts, concurrency limits, memory limits, and request-rate controls in production embeddings.

Trying the Workflow in the Browser Playground

The interactive playground has full LSP support, so this chapter can be exercised directly in the browser. Paste a snippet with a hole, place the cursor on the hole, and inspect available quick-fixes and semantic suggestions.

fn parse_i32 : String -> Result String i32 = \s ->
  if s == "42" then Ok 42 else Err "bad-int";

fn plus1 : i32 -> i32 = \n -> n + 1;

let input = "42" in
let out : Result String i32 = ? in
out

A useful exercise is to fill out in multiple ways, observe type errors, then invoke semantic quick-fixes and compare outcomes.

Related Work and Positioning

The ideas used here are mostly established. Typed holes and goal-directed development are prominent in systems such as GHC (Haskell) and dependently typed environments like Agda and Idris. Live, structure-aware editor semantics have been explored in research systems such as Hazel. Type-directed code search and synthesis has a long line of work, including tools like InSynth and later synthesis frameworks.

Rex does not claim conceptual novelty in these foundations. Its contribution is engineering integration: one semantics pipeline serving both human editor workflows and LLM control loops, with contract-stable machine interfaces, regression coverage, and bounded candidate generation.

Reference: Semantic Assists

Rex exposes the following assists through LSP execute commands. Each assist is intended to be used in a short observe-then-act loop rather than as a one-shot oracle.

The argument forms below use JSON types and a 0-based Position.

Common types:

type UriArg =
  | { uri: string }
  | [uri: string];

type PosArg =
  | { uri: string; line: u32; character: u32 }
  | [uri: string, line: u32, character: u32];

type DiagnosticLite = {
  message: string;
  line: u32;
  character: u32;
};

type QuickFixPrecondition = {
  uri: string;
  contentHash: string;
  documentVersion: i32 | null;
};

type QuickFixProposal = {
  protocolVersion: 2;
  id: string;
  title: string;
  kind: string | null;
  edit: WorkspaceEdit;
  precondition: QuickFixPrecondition;
};

type HoleInfo = {
  name: string;
  line: u32;
  character: u32;
  expectedType: string;
};

rex.expectedTypeAt

args: PosArg
returns: null | { expectedType: string }

rex.functionsProducingExpectedTypeAt

args: PosArg
returns: { items: string[] } // each item rendered as "name : type"

rex.functionsAcceptingInferredTypeAt

args: PosArg
returns: {
  inferredType: string | null;
  items: string[];
}

rex.adaptersFromInferredToExpectedAt

args: PosArg
returns: {
  inferredType: string | null;
  expectedType: string | null;
  items: string[];
}

rex.functionsCompatibleWithInScopeValuesAt

args: PosArg
returns: { items: string[] } // concrete call-style suggestions

rex.holesExpectedTypes

args: UriArg
returns: { holes: HoleInfo[] }

rex.semanticLoopStep

args: PosArg
returns: {
  expectedType: string | null;
  inferredType: string | null;
  inScopeValues: string[];
  functionCandidates: string[];
  holeFillCandidates: Array<{ name: string; replacement: string }>;
  functionsAcceptingInferredType: string[];
  adaptersFromInferredToExpectedType: string[];
  functionsCompatibleWithInScopeValues: string[];
  localDiagnostics: DiagnosticLite[];
  quickFixes: QuickFixProposal[];
  quickFixTitles: string[];
  holes: HoleInfo[];
}

rex.semanticLoopApplyQuickFixAt

args:
  | { uri: string; quickFix: QuickFixProposal }
  | [uri: string, quickFix: QuickFixProposal]

returns:
  | { status: "applied"; quickFix: QuickFixProposal }
  | {
      status: "stale";
      reason: "documentContentChanged" | "documentVersionChanged";
      expectedContentHash: string;
      actualContentHash: string;
      expectedDocumentVersion: i32 | null;
      actualDocumentVersion: i32 | null;
    }
  | {
      status: "rejected";
      reason: string;
      detail?: string | null;
      failedChange?: u32 | null;
    }

Quick-fixes are immutable proposals bound to the document content and LSP version observed during rex.semanticLoopStep. Applying a proposal validates its ID and snapshot preconditions, then asks the editor to apply the exact versioned WorkspaceEdit returned by discovery. The server does not regenerate candidates during application. A changed document therefore produces an explicit stale result instead of applying a different edit or returning an ambiguous null.

rex.semanticLoopApplyBestQuickFixesAt

args:
  | {
      uri: string;
      line: u32;
      character: u32;
      maxSteps?: u64;
      strategy?: "conservative" | "aggressive";
      dryRun?: bool;
    }
  | [
      uri: string,
      line: u32,
      character: u32,
      maxSteps?: u64,
      strategy?: string,
      dryRun?: bool
    ]
// maxSteps is clamped to [1, 20]

returns: {
  strategy: "conservative" | "aggressive";
  dryRun: bool;
  appliedQuickFixes: QuickFixProposal[];
  appliedCount: u64;
  steps: Array<{
    index: u64;
    quickFix: QuickFixProposal;
    diagnosticsBefore: DiagnosticLite[];
    diagnosticsAfter: DiagnosticLite[];
    diagnosticsBeforeCount: u64;
    diagnosticsAfterCount: u64;
    diagnosticsDelta: i64;
    noImprovementStreak: u64;
  }>;
  updatedText: string;
  localDiagnosticsAfter: DiagnosticLite[];
  stoppedReason: string;
  stoppedReasonDetail: string;
  lastDiagnosticsDelta: i64;
  noImprovementStreak: u64;
  seenStatesCount: u64;
}

Practical Generation Guidance (Legacy Checklist)

The remainder of this chapter preserves the practical generation checklist that was previously a standalone LLM guidance page. It remains useful when an LLM is emitting Rex directly rather than running a semantic loop command at each step.

Recommended Context Order

When building or revising Rex code, read docs in this order:

1. This chapter (LLMS.md) for semantic-loop workflow and generation pitfalls.
2. LANGUAGE.md for syntax and everyday feature usage.
3. SPEC.md for locked behavior when edge cases matter.

High-Value Rules

1. Use fn for top-level reusable functions; use let and let rec for local helpers.
2. For local mutual recursion, use comma-separated let rec bindings.
3. Use x::xs for list cons in both patterns and expressions (x::xs is equivalent to Cons x xs).
4. Validate snippets with the Rex CLI before shipping docs.

Quick Generation Checklist

Before returning generated Rex code:

1. Put top-level reusable functions in fn declarations (they are mutually recursive).
2. Use let rec only for local recursive helpers inside expressions.
3. Add annotations where constructor or numeric ambiguity is likely (Empty, zero, overloaded methods).
4. Ensure the final expression returns a visible result (often a tuple for demos).
5. Run cargo run -p rex-cli --bin rex_cli -- /tmp/snippet.rex and fix all parse and type errors.

Syntax Pitfalls

1) Recursion model

• Top-level fn declarations are mutually recursive.
• Top-level type and fn declarations end with ;; indentation and newlines do not terminate them.
• Single recursive local helper: let rec
• Mutually recursive local helpers: let rec with commas between bindings.

Top-level mutual recursion:

fn even : i32 -> Bool = \n ->
  if n == 0 then true else odd (n - 1);

fn odd : i32 -> Bool = \n ->
  if n == 0 then false else even (n - 1);

even 10

let rec
  even = \n -> if n == 0 then true else odd (n - 1),
  odd = \n -> if n == 0 then false else even (n - 1)
in
  even 10

If you define local helpers in plain let and reference each other, you will get unbound-variable errors. Use let rec for local recursion.

2) List construction and list patterns

• Pattern matching: x::xs is valid in case patterns.
• Expression construction: x::xs and Cons x xs are equivalent (list literals are also valid). Cons uses normal constructor and function call style (Cons head tail).

Equivalent:

x::xs
Cons x xs

3) ADT equality is not implicit

Do not assume custom ADTs automatically implement Eq. For example, comparing Node values with == can fail with a missing-instance type error.

For small enums and ADTs, write an explicit equality helper:

node_eq = \a b ->
  match (a, b) with {
    case (A, A) -> true;
    case (B, B) -> true;
    case _ -> false;
  }

Related: avoid checking list emptiness with direct equality like xs == [] in generic code. Prefer an explicit matcher helper.

4) Ambiguous constructors (for example Empty)

Constructors like Empty can be ambiguous when multiple ADTs define the same constructor name (for example List.Empty and Tree.Empty).

Disambiguate with an annotation at the binding site:

type Tree = Empty | Node { key: i32, left: Tree, right: Tree };

let
  t0: Tree = Empty
in
  match t0 with {
    case Empty -> 0;
    case Node {key, left, right} -> key;
  }

5) Reserved identifiers

Avoid bindings that collide with keywords (for example as). Use alternatives like xs1, lefts, rest1, and similar.

6) Constructor patterns with literals

Some forms like Lit 1 inside nested patterns can fail to parse. Prefer simpler constructor patterns and do literal checks in expression logic if needed.

Also avoid relying on tuple and list patterns that include numeric literals in one branch (for example (x::_, 0)); match structurally first, then use an if guard in expression code.

Validation Workflow

Before emitting generated Rex snippets in docs:

1. Save the snippet to a temporary .rex file.
2. Run cargo run -p rex-cli --bin rex_cli -- /tmp/snippet.rex.
3. If parse or type errors appear, fix and re-run until clean.

For mdBook interactive demos, also run:

cd docs
mdbook build