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.

All Rex code samples in this documentation are interactive. Edit them, run them, and use the output to learn by experimentation. A good place to start is the 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.

All code samples are interactive in the docs, so you can edit and run each snippet as you go.

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.

Getting Started

Rex programs are 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

From this repository, you can run a file:

cargo run -p rex -- run rex/examples/record_update.rex

Or evaluate a small snippet inline:

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

What you should see

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

What “one expression” means

Even with declarations, the program result is the final expression:

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

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

The program above:

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

Comments

Comments use {- ... -}:

{- This is a comment -}
1 + 2

Whitespace and layout

Most whitespace is insignificant, but some constructs are easiest to read in “layout style”:

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

Commas between let bindings are required. The parser also accepts many one-line forms, but multi-line layout tends to be easier to debug.

Type-class and instance method blocks are also written by indentation:

class Size a
  size : a -> i32

You may also see the optional where keyword in class/instance headers:

class Size a where
  size : a -> i32

Both forms are accepted.

Your first “real” Rex file

Create a file hello.rex:

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

Run it:

cargo run -p rex -- run hello.rex

Unicode (λ, →) versus ASCII

Rex accepts both:

\ and ->
λ and →

Use whichever your editor makes pleasant. The repo’s examples use a mix.

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, string (plus uuid, datetime if enabled by the host).

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)
)

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
      when [] -> 0
      when 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 also accepts the Unicode 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 an explicit type signature:

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

This declares a function that takes an i32 and returns another function i32 -> i32.

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

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

Legacy `fn` header forms

The parser still accepts older forms that put parameter names/types in the header:

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

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

For multiple parameters, the “named arrows” form looks like:

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

`fn` constraints with `where`

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

fn sum_list : List i32 -> i32 where Foldable List = \xs -> 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]
  when Empty -> 0
  when Cons h t -> h

List patterns (sugar)

Rex also supports list-pattern sugar:

match [1, 2, 3]
  when [] -> 0
  when [x] -> x
  when x::xs -> x

Lists vs Arrays

Rex supports both List a and Array a. They are related, but intentionally different.

List a is a linked, recursive ADT (Cons / Empty) and is the default collection shape in user-written Rex code.
Array a is a contiguous, indexed runtime container that maps naturally to host memory layouts (for example Rust Vec<T>).

Why both:

Lists are ideal for language-level programming patterns (pattern matching, recursive decomposition, and list syntax sugar like [] and x::xs).
Arrays are ideal for host interop and performance-sensitive data transfer.

In embedding scenarios, host functions commonly return arrays rather than lists. For example, a Rust host function that returns Vec<i32> is exposed in Rex as returning Array i32.

Matching host results: use `to_list`

Because list patterns ([], x::xs, Cons) are list-only, convert array results before matching:

let
  {- We use to_array here to simulate a host function result of type Array i32. -}
  data = to_array [1, 2, 3]
in
  match (to_list data)
    when x::xs -> x
    when [] -> -1

The same shape without to_list fails with a type mismatch (array vs list):

let
  {- We use to_array here to simulate a host function result of type Array i32. -}
  data = to_array [1, 2, 3]
in
  match data
    when x::xs -> x
    when [] -> -1

Use the quick fix on the error and choose Convert expression to list with to_list; this rewrites the mismatched expression for you, which is usually all that is needed.

Why `to_list` is explicit (not implicit)

Rex keeps this conversion explicit for cost visibility. Converting Array a to List a allocates new list nodes and copies references, so it is not a zero-cost operation.

If to_list were implicit, those allocations and copies could be inserted automatically in hot paths (inside loops, repeated matches, pipelines, or nested helper calls) without being obvious in source code. That would increase allocation rate, add GC/heap pressure, and make performance regressions harder to find.

At host boundaries this matters even more: arrays are often used for efficient transfer and memory locality. Keeping to_list explicit ensures the representation change happens only where you choose to pay for it.

LSP and LLM workflow

Because Rex exposes semantic diagnostics and code actions through LSP, an LLM-assisted workflow can fix this in one pass:

Run typecheck / request diagnostics.
Detect the array/list mismatch at the match expression.
Apply the to_list quick fix code action.
Re-check and continue.

This is stronger than raw text editing because the fix is selected from compiler-semantic information (actual inferred/expected types and targeted edits), not guessed from surface syntax.

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

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
  when {a, b} -> a + b
  when {a} -> a
  when {} -> 0

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

Algebraic Data Types (ADTs)

ADTs let you define your own sum types.

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
      when Just x -> x
      when 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
    when Just x -> x
    when 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)
  when Some x -> x
  when None -> 0

Common patterns

Wildcards:

match [1, 2, 3]
  when Empty -> 0
  when Cons _ _ -> 1

List patterns:

match [1, 2]
  when [] -> 0
  when [x] -> x
  when [x, y] -> x + y
  when _ -> 0

Cons patterns:

match [1, 2, 3]
  when h::t -> h
  when [] -> 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
  when Point { x: x, y: y } -> x + y

Dict key presence patterns:

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

Arrow spelling

Arms can use -> or →:

type Bit = T | F

let v = T in
match v
  when T → 1
  when 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

Projection

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

let p: Point = 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 = Point { x: i32, y: i32 }

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

Updates can set multiple fields at once:

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

let p: Point = 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
  when A {x} -> { s with { x = x + 1 } }
  when 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, string
(a, b) for tuples
List a, Option a, Result a e (prelude)

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:

To force a dictionary type (Dict a) instead of a specific record type.
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 compiled and evaluated in stages:

Lexing
Parsing
Type inference / checking
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 file:

cargo run -p rex -- run path/to/file.rex

Run an inline snippet:

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

Show the parsed AST and exit:

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

Show the inferred type and exit:

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

“Parse error”: start small

If you hit a parse error:

Reduce the program to the smallest failing snippet.
Add parentheses to disambiguate application vs infix operators.
Prefer layout-style 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 Array, 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: rexlang-typesystem/src/prelude_typeclasses.rex
built-in types + helper functions: rexlang-typesystem/src/prelude.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)
Array a
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)
Indexable t a (get)

For tuples, use numeric projection like .0 and .1 instead of get.

A few useful helper functions

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

sum, mean, count, min, max
is_some, is_none (for Option)
is_ok, is_err (for Result)

How to learn what something is

When you see an unfamiliar function:

Ask the CLI for its type: cargo run -p rex -- run --emit-type -c 'the_name'
If it’s a type-class method, find the class in rexlang-typesystem/src/prelude_typeclasses.rex
If it’s a helper function, find it in rexlang-typesystem/src/prelude.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

Type Inference
Polymorphism
Typeclasses
Instances
Constraints and Where
Resolution and Coherence
Functor
Applicative
Monad
Writing Instances
Defaulting
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 -- run --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”

Add a type annotation to a let binding.
Use expression ascription with is.
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
  size : a -> i32

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

Optional `where`

You may also see:

class Size a where
  size : a -> i32

Both forms are accepted.

Operators as methods

class Eq a
  == : a -> a -> bool
  != : a -> a -> bool

Superclasses

Superclasses use <= (read “requires”):

class Ord a <= Eq a
  < : a -> a -> bool

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

Multi-parameter classes (tupled)

Some prelude classes logically take multiple type parameters, such as Indexable t a.

In Rex source you write:

class Indexable t a
  get : i32 -> t -> a

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

where Indexable (t, a) -> ...

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:

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

A monomorphic instance

class Show a
  show : a -> string

instance Show i32
  show = \_ -> "<i32>"

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

import dep as D

instance D.Show i32
  show = \_ -> "<i32>"

A polymorphic instance with context

Instance contexts use <=:

instance Show (List a) <= Show a
  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/examples/type_classes.rex:

let
  use_classes = \ (x: t) (y: f a) (z: a) where Indexable (t, a), Foldable f ->
    let
      first = get 0 x,
      total = foldl (\acc _ -> acc) z y
    in
      (first, total, z)
in
  use_classes [10, 20, 30] [1, 2, 3] 0

Notes:

where ... -> attaches constraints to the lambda.
Multi-parameter classes like Indexable t a are written as Indexable (t, a) in the where list (internally they’re represented as tupled predicates).
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, Array 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
  map : (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
  pure : a -> f a
  ap : 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
  bind : (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
      when Box x -> Box (f x)

Now you can:

type Box a = Box a

instance Functor Box where
  map = \f bx ->
    match bx
      when 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
      when Box x -> Box (f x)

instance Applicative Box <= Functor Box where
  pure = \x -> Box x
  ap = \bf bx ->
    match bf
      when Box f -> map f bx

Try:

type Box a = Box a

instance Functor Box where
  map = \f bx ->
    match bx
      when Box x -> Box (f x)

instance Applicative Box <= Functor Box where
  pure = \x -> Box x
  ap = \bf bx ->
    match bf
      when 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
      when Box x -> Box (f x)

instance Applicative Box <= Functor Box where
  pure = \x -> Box x
  ap = \bf bx ->
    match bf
      when Box f -> map f bx

instance Monad Box <= Applicative Box where
  bind = \f bx ->
    match bx
      when Box x -> f x

Try:

type Box a = Box a

instance Functor Box where
  map = \f bx ->
    match bx
      when Box x -> Box (f x)

instance Applicative Box <= Functor Box where
  pure = \x -> Box x
  ap = \bf bx ->
    match bf
      when Box f -> map f bx

instance Monad Box <= Applicative Box where
  bind = \f bx ->
    match bx
      when 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
Array 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
    default = Pair 42 true

Single constructor with named fields:

type Config = Config { retries: i32, enabled: bool }

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

Multiple variants (enum) with no fields:

type Mode = Fast | Safe | Debug

instance Default Mode
    default = Safe

Multiple variants with mixed payload shapes:

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

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

Generic ADTs with constraints:

type Box a = Box a | Missing

instance Default (Box a) <= Default a
    default = Box default

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
    default = A { x = 1, y = 2 }

instance Default B
    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
    default = A { x = 1, y = 2 }

instance Default B
    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
    default = A { x = 1, y = 2 }

instance Default B
    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
Result a e

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

In informal kind notation:

List : * -> *
Option : * -> *
Result : * -> * -> *

Why `Functor` talks about `f a`

The class is defined as:

class Functor f
  map : (a -> b) -> f a -> f b

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

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

The prelude has an instance:

instance Functor (Result e)
  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 -- run -c '<paste rex expression here>'
For larger multi-line experiments, saving to a .rex file is often easier.

Chapters

Lists
Folds
Match and ADTs
Records
Functor Polymorphism
Option Pipelines
Result Workflows
Custom Show Printing
Custom Size
Indexable
Small Standard Library
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:

Start with an accumulator of type b
For each element of type a, update the accumulator
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:

define an ADT
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
      when Just x -> x
      when 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
      when Just x -> Just (f x)
      when 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
      when Just _ -> true
      when 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
      when Just x -> Just x
      when 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
      when Just x -> f x
      when 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
      when Just x -> x
      when Nothing -> d
      when 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
  when A {x} -> { s with { x = x + 1 } }
  when 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
  when A {x} -> { s with { x = x + 1 } }
  when B {x} -> { s with { x = x + 2 } }
  when 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, Array 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:

plain match
bind chaining (monadic)
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)
    when None -> None
    when Some v1 ->
      match (step1 v1)
        when None -> None
        when 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/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:

define the class
add a base instance (i32)
add a structured type (Point)
(optional) add a container instance (List a)

class DemoShow a
  demo_show : a -> string

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

instance DemoShow i32
  demo_show = \_ -> "<i32>"

instance DemoShow Point
  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/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
  demo_show : a -> string

instance DemoShow i32
  demo_show = \_ -> "<i32>"

instance DemoShow (List a) <= DemoShow a
  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
  demo_show : a -> string

instance DemoShow i32
  demo_show = \_ -> "<i32>"

instance DemoShow (List a) <= DemoShow a
  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
  demo_show : a -> string

instance DemoShow bool
  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
  demo_show : a -> string

instance DemoShow i32
  demo_show = \_ -> "<i32>"

instance DemoShow (Option a) <= DemoShow a
  demo_show = \ox ->
    match ox
      when Some x -> "Some(" + demo_show x + ")"
      when 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/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
  size : a -> i32

type Blob = Blob { bytes: List i32 }

instance Size (List t)
  size = \xs ->
    match xs
      when Empty -> 0
      when Cons _ t -> 1 + size t

instance Size Blob
  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
  size : a -> i32

instance Size (List t)
  size = \xs ->
    match xs
      when Empty -> 0
      when Cons _ t -> 1 + size t

let
  bigger = \(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
  size : a -> i32

instance Size (List t)
  size = \xs ->
    match xs
      when Empty -> 0
      when Cons _ t -> 1 + size t

let
  is_empty = \(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
  size : a -> i32

instance Size (List t)
  size = \xs ->
    match xs
      when Empty -> 0
      when Cons _ t -> 1 + size t

type Blob = Blob { name: string, bytes: List i32 }

instance Size Blob
  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
  size : a -> i32

instance Size (List t)
  size = \xs ->
    match xs
      when Empty -> 0
      when 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: `Indexable`

Indexable is a multi-parameter class in the prelude (so you can use get without defining the class yourself).

Goal

Learn how to pull elements out of common containers with a single API:

lists
arrays

Example uses:

( get 0 [10, 20, 30] , get 2 ["a", "b", "c"] )

How it works

Lists and arrays have Indexable (List a, a) / Indexable (Array a, a) instances.
Tuples use numeric projection like .0 and .1 instead of get.

A more guided example

let
  xs = [10, 20, 30],
  first = get 0 xs,
  third = get 2 xs,
  ys = [1, 2, 3],
  last = get 2 ys
in
  (first, third, last)

Note on out-of-bounds

get is generally expected to error if the index is out of bounds (depending on the host/runtime implementation). If you need safe indexing (returning Option/Result), write it with match on your container type (e.g. [] vs x::xs for lists).

Worked examples

Example: `head : List a -> Option a`

Problem: return the first list element safely.

let
  head = \xs ->
    match xs
      when [] -> None
      when x::_ -> Some x
in
  (head [] is Option i32, head [10, 20, 30])

Why this works: pattern matching handles empty and non-empty shapes explicitly.

Example: `get` on a larger list

Problem: read specific indices from [100, 200, 300, 400].

let
  xs = [100, 200, 300, 400]
in
  (get 0 xs, get 2 xs, get 3 xs)

Why this works: Indexable (List a, a) provides get for list element access.

Example: Small “stdlib” 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:

validate a User
transform it (birthday)
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.

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.

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 a full pipeline of helper functions (split, merge, compare) and demonstrates how recursive decomposition can produce deterministic, stable ordering over immutable lists.

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.

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.

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
    when Inf -> Inf
    when Finite x -> Finite (x + w)
)

fn min_dist : Dist -> Dist -> Dist = (\a b ->
  match (a, b)
    when (Inf, x) -> x
    when (x, Inf) -> x
    when (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
    when Inf -> -1
    when 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.

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
    when [] -> (Num 0, [])
    when TNum n::rest -> (Num n, rest)
    when TPlus::rest ->
      let
        (lhs, rest1) = parse_expr rest,
        (rhs, rest2) = parse_expr rest1
      in
        (Add lhs rhs, rest2)
    when TMul::rest ->
      let
        (lhs, rest1) = parse_expr rest,
        (rhs, rest2) = parse_expr rest1
      in
        (Mul lhs rhs, rest2)
    when TNeg::rest ->
      let (inner, rest1) = parse_expr rest in
      (Neg inner, rest1)

fn eval : Expr -> i32 = \expr ->
  match expr
    when Num n -> n
    when Add a b -> eval a + eval b
    when Mul a b -> eval a * eval b
    when Neg x -> 0 - eval x

fn is_empty : List a -> bool = \xs ->
  match xs
    when [] -> true
    when _::_ -> 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.

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.

Built-in types & functions

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

Built-in Types

Type	Description
`Array a`	Fixed-size indexed sequence.
`Dict a`	Dictionary/record-like mapping from field labels to values.
`List a`	Immutable singly linked list. Constructors: `Empty`, `Cons`.
`Option a`	Optional value (`Some` or `None`). Constructors: `Some`, `None`.
`Result a b`	Result value (`Ok` or `Err`) for success/failure flows. Constructors: `Err`, `Ok`.
`bool`	Boolean truth value.
`datetime`	UTC timestamp value.
`f32`	32-bit floating-point number.
`f64`	64-bit floating-point number.
`i16`	16-bit signed integer.
`i32`	32-bit signed integer.
`i64`	64-bit signed integer.
`i8`	8-bit signed integer.
`string`	UTF-8 string value.
`u16`	16-bit unsigned integer.
`u32`	32-bit unsigned integer.
`u64`	64-bit unsigned integer.
`u8`	8-bit unsigned integer.
`uuid`	UUID value.

Built-in Type Classes

`AdditiveGroup`

Types supporting additive inverse and subtraction.

Superclasses: Semiring

Methods:

negate: AdditiveGroup 'a => ('a -> 'a). Additive inverse.
-: AdditiveGroup 'a => ('a -> ('a -> 'a)). Subtraction.

`AdditiveMonoid`

Types with additive identity and associative addition.

Superclasses: none

Methods:

zero: AdditiveMonoid 'a => 'a. Additive identity.
+: AdditiveMonoid 'a => ('a -> ('a -> 'a)). Addition (or concatenation for strings).

`Alternative`

Applicative types with a fallback choice operation.

Superclasses: Applicative

Methods:

or_else: Alternative 'f => ((('f 'a) -> ('f 'a)) -> (('f 'a) -> ('f 'a))). Provide an alternative container value.

`Applicative`

Functors that can lift values and apply wrapped functions.

Superclasses: Functor

Methods:

pure: Applicative 'f => ('a -> ('f 'a)). Lift a plain value into an applicative context.
ap: Applicative 'f => (('f ('a -> 'b)) -> (('f 'a) -> ('f 'b))). Apply wrapped functions to wrapped values.

`Default`

Types with a canonical default value.

Superclasses: none

Methods:

default: Default 'a => 'a. Canonical default value for a type. For Result a e, this requires Default a.

`Eq`

Types supporting equality/inequality comparison.

Superclasses: none

Methods:

==: Eq 'a => ('a -> ('a -> bool)). Equality comparison.
!=: Eq 'a => ('a -> ('a -> bool)). Inequality comparison.

`Field`

Types supporting division in addition to ring operations.

Superclasses: Ring

Methods:

/: Field 'a => ('a -> ('a -> 'a)). Division.

`Filterable`

Functors supporting filtering and partial mapping.

Superclasses: Functor

Methods:

filter: Filterable 'f => (('a -> bool) -> (('f 'a) -> ('f 'a))). Keep elements that satisfy a predicate.
filter_map: Filterable 'f => (('a -> (Option 'b)) -> (('f 'a) -> ('f 'b))). Map and drop missing results in one pass.

`Foldable`

Containers that can be reduced with folds.

Superclasses: none

Methods:

foldl: Foldable 't => (('b -> ('a -> 'b)) -> ('b -> (('t 'a) -> 'b))). Strict left fold.
foldr: Foldable 't => (('a -> ('b -> 'b)) -> ('b -> (('t 'a) -> 'b))). Right fold.
fold: Foldable 't => (('b -> ('a -> 'b)) -> ('b -> (('t 'a) -> 'b))). Left-style fold over a container.

`Functor`

Type constructors that support structure-preserving mapping.

Superclasses: none

Methods:

map: Functor 'f => (('a -> 'b) -> (('f 'a) -> ('f 'b))). Apply a function to each value inside a functor.

`Indexable`

Containers that support indexed element access.

Superclasses: none

Methods:

get: Indexable ('t, 'a) => (i32 -> ('t -> 'a)). Get an element by index.

`Integral`

Integral numeric types supporting modulo.

Superclasses: none

Methods:

%: Integral 'a => ('a -> ('a -> 'a)). Remainder/modulo operation.

`Monad`

Applicatives supporting dependent sequencing (bind).

Superclasses: Applicative

Methods:

bind: Monad 'm => (('a -> ('m 'b)) -> (('m 'a) -> ('m 'b))). Monadic flat-map/sequencing operation.

`MultiplicativeMonoid`

Types with multiplicative identity and associative multiplication.

Superclasses: none

Methods:

one: MultiplicativeMonoid 'a => 'a. Multiplicative identity.
*: MultiplicativeMonoid 'a => ('a -> ('a -> 'a)). Multiplication.

`Ord`

Types with total ordering comparisons.

Superclasses: Eq

Methods:

cmp: Ord 'a => ('a -> ('a -> i32)). Three-way comparison returning negative/zero/positive i32.
<: Ord 'a => ('a -> ('a -> bool)). Less-than comparison.
<=: Ord 'a => ('a -> ('a -> bool)). Less-than-or-equal comparison.
>: Ord 'a => ('a -> ('a -> bool)). Greater-than comparison.
>=: Ord 'a => ('a -> ('a -> bool)). Greater-than-or-equal comparison.

`Ring`

Types supporting additive group plus multiplication.

Superclasses: AdditiveGroup, MultiplicativeMonoid

Methods:

`Semiring`

Types supporting additive and multiplicative monoid operations.

Superclasses: AdditiveMonoid, MultiplicativeMonoid

Methods:

`Sequence`

Ordered containers with slicing/zipping operations.

Superclasses: Functor, Foldable

Methods:

take: Sequence 'f => (i32 -> (('f 'a) -> ('f 'a))). Keep only the first n elements.
skip: Sequence 'f => (i32 -> (('f 'a) -> ('f 'a))). Drop the first n elements.
zip: Sequence 'f => (('f 'a) -> (('f 'b) -> ('f ('a, 'b)))). Pair elements from two containers by position.
unzip: Sequence 'f => (('f ('a, 'b)) -> (('f 'a), ('f 'b))). Split a container of pairs into a pair of containers.

`Show`

Types that can be converted to user-facing strings (Haskell-style naming).

Superclasses: none

Methods:

show: Show 'a => ('a -> string). Render a value as a human-readable string.

Built-in Functions

Overloaded (Type Class Methods)

Function	Signature	Implemented On	Description
`negate`	`('a -> 'a)`	`i8` `i16` `i32` `i64` `f32` `f64`	Additive inverse.
`-`	`('a -> ('a -> 'a))`	`i8` `i16` `i32` `i64` `f32` `f64`	Subtraction.
`zero`	`'a`	`string` `u8` `u16` `u32` `u64` `i8` `i16` `i32` `i64` `f32` `f64`	Additive identity.
`+`	`('a -> ('a -> 'a))`	`string` `u8` `u16` `u32` `u64` `i8` `i16` `i32` `i64` `f32` `f64`	Addition (or concatenation for strings).
`or_else`	`((('f 'a) -> ('f 'a)) -> (('f` `'a) -> ('f 'a)))`	`List` `Option` `Array` `(Result 'e)`	Provide an alternative container value.
`pure`	`('a -> ('f 'a))`	`List` `Option` `Array` `(Result 'e)`	Lift a plain value into an applicative context.
`ap`	`(('f ('a -> 'b)) -> (('f 'a)` `-> ('f 'b)))`	`List` `Option` `Array` `(Result 'e)`	Apply wrapped functions to wrapped values.
`default`	`'a`	`bool` `u8` `u16` `u32` `u64` `i8` `i16` `i32` `i64` `f32` `f64` `string` `(List 'a)` `(Array 'a)` `(Option 'a)` `(Result 'a 'e)`	Canonical default value for a type. For `Result a e`, this requires `Default a`.
`==`	`('a -> ('a -> bool))`	`u8` `u16` `u32` `u64` `i8` `i16` `i32` `i64` `f32` `f64` `bool` `string` `uuid` `datetime` `(List 'a)` `(Option 'a)` `(Array 'a)` `(Result 'a 'e)`	Equality comparison.
`!=`	`('a -> ('a -> bool))`	`u8` `u16` `u32` `u64` `i8` `i16` `i32` `i64` `f32` `f64` `bool` `string` `uuid` `datetime` `(List 'a)` `(Option 'a)` `(Array 'a)` `(Result 'a 'e)`	Inequality comparison.
`/`	`('a -> ('a -> 'a))`	`f32` `f64`	Division.
`filter`	`(('a -> bool) -> (('f 'a) ->` `('f 'a)))`	`List` `Option` `Array`	Keep elements that satisfy a predicate.
`filter_map`	`(('a -> (Option 'b)) -> (('f` `'a) -> ('f 'b)))`	`List` `Option` `Array`	Map and drop missing results in one pass.
`foldl`	`(('b -> ('a -> 'b)) -> ('b ->` `(('t 'a) -> 'b)))`	`List` `Option` `Array`	Strict left fold.
`foldr`	`(('a -> ('b -> 'b)) -> ('b ->` `(('t 'a) -> 'b)))`	`List` `Option` `Array`	Right fold.
`fold`	`(('b -> ('a -> 'b)) -> ('b ->` `(('t 'a) -> 'b)))`	`List` `Option` `Array`	Left-style fold over a container.
`map`	`(('a -> 'b) -> (('f 'a) -> ('f` `'b)))`	`List` `Option` `Array` `(Result 'e)`	Apply a function to each value inside a functor.
`get`	`(i32 -> ('t -> 'a))`	`((List 'a), 'a)` `((Array 'a), 'a)`	Get an element by index.
`%`	`('a -> ('a -> 'a))`	`u8` `u16` `u32` `u64` `i8` `i16` `i32` `i64`	Remainder/modulo operation.
`bind`	`(('a -> ('m 'b)) -> (('m 'a)` `-> ('m 'b)))`	`List` `Option` `Array` `(Result 'e)`	Monadic flat-map/sequencing operation.
`one`	`'a`	`u8` `u16` `u32` `u64` `i8` `i16` `i32` `i64` `f32` `f64`	Multiplicative identity.
`*`	`('a -> ('a -> 'a))`	`u8` `u16` `u32` `u64` `i8` `i16` `i32` `i64` `f32` `f64`	Multiplication.
`cmp`	`('a -> ('a -> i32))`	`u8` `u16` `u32` `u64` `i8` `i16` `i32` `i64` `f32` `f64` `string`	Three-way comparison returning negative/zero/positive `i32`.
`<`	`('a -> ('a -> bool))`	`u8` `u16` `u32` `u64` `i8` `i16` `i32` `i64` `f32` `f64` `string`	Less-than comparison.
`<=`	`('a -> ('a -> bool))`	`u8` `u16` `u32` `u64` `i8` `i16` `i32` `i64` `f32` `f64` `string`	Less-than-or-equal comparison.
`>`	`('a -> ('a -> bool))`	`u8` `u16` `u32` `u64` `i8` `i16` `i32` `i64` `f32` `f64` `string`	Greater-than comparison.
`>=`	`('a -> ('a -> bool))`	`u8` `u16` `u32` `u64` `i8` `i16` `i32` `i64` `f32` `f64` `string`	Greater-than-or-equal comparison.
`take`	`(i32 -> (('f 'a) -> ('f 'a)))`	`List` `Array`	Keep only the first `n` elements.
`skip`	`(i32 -> (('f 'a) -> ('f 'a)))`	`List` `Array`	Drop the first `n` elements.
`zip`	`(('f 'a) -> (('f 'b) -> ('f` `('a, 'b))))`	`List` `Array`	Pair elements from two containers by position.
`unzip`	`(('f ('a, 'b)) -> (('f 'a),` `('f 'b)))`	`List` `Array`	Split a container of pairs into a pair of containers.
`show`	`('a -> string)`	`bool` `u8` `u16` `u32` `u64` `i8` `i16` `i32` `i64` `f32` `f64` `string` `uuid` `datetime` `(List 'a)` `(Array 'a)` `(Option 'a)` `(Result 'a 'e)`	Render a value as a human-readable string.

Other Built-ins

Function	Signature	Description
`&&`	`(bool -> (bool -> bool))`	Boolean conjunction.
`Cons`	`('a -> ((List 'a) -> (List` `'a)))`	Construct a non-empty list from head and tail.
`Empty`	`(List 'a)`	The empty list constructor.
`Err`	`('e -> (Result 't 'e))`	Construct a failed `Result`.
`None`	`(Option 't)`	The empty `Option` constructor.
`Ok`	`('t -> (Result 't 'e))`	Construct a successful `Result`.
`Some`	`('t -> (Option 't))`	Construct a present `Option` value.
`count`	`Foldable 'f => (('f 'a) ->` `i32)`	Count elements in a foldable container.
`is_err`	`((Result 't 'e) -> bool)`	Check whether a `Result` is `Err`.
`is_none`	`((Option 'a) -> bool)`	Check whether an `Option` is `None`.
`is_ok`	`((Result 't 'e) -> bool)`	Check whether a `Result` is `Ok`.
`is_some`	`((Option 'a) -> bool)`	Check whether an `Option` is `Some`.
`max`	`Foldable 'f, Ord 'a => (('f` `'a) -> 'a)`	Maximum element by ordering.
`mean`	`Foldable 'f, Field 'a => (('f` `'a) -> 'a)`	Arithmetic mean over numeric foldables.
`min`	`Foldable 'f, Ord 'a => (('f` `'a) -> 'a)`	Minimum element by ordering.
`sum`	`Foldable 'f, AdditiveMonoid 'a` `=> (('f 'a) -> 'a)`	Sum all elements in a foldable container.
`to_array`	`((List 'a) -> (Array 'a))`	Convert a list to an array.
`to_list`	`((Array 'a) -> (List 'a))`	Convert an array to a list.
`		`

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.

A Program

A Rex program consists of:

zero or more declarations (type, class, instance, fn, import)
followed by a single expression (the program result)

Example:

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

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

Modules and Imports

Rex modules are .rex files. Imports are top-level declarations. Module files are declaration-only: they do not have a top-level expression result. To evaluate an expression, use snippet/REPL/program entrypoints.

Supported forms:

import foo.bar as Bar
import foo.bar (*)
import foo.bar (x, y as z)

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 all exported values into local unqualified scope.
import foo.bar (x, y as z) imports selected exported values; y is bound locally as z.
Module alias imports and clause imports are mutually exclusive in one import declaration.
Only pub values are importable into unqualified local scope via (*) / item clauses.
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.

Path resolution:

foo.bar resolves to foo/bar.rex.
Local module paths resolve relative to the importing file.
Leading super path segments walk up directories (for example super.core.calc).

Lexical Structure

Whitespace and Comments

Whitespace (including newlines) is generally insignificant.
Comments use {- ... -} and 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. Some docs/examples may also use Unicode λ 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 (if present in your lexer source)

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.

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.

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 with one or more when arms:

match xs
  when Empty -> 0
  when 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]
  when h::t -> h
  when [] -> 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)
string
uuid
datetime

Function Types

Functions are right-associative: a -> b -> c means a -> (b -> c).

Tuples, Lists, Arrays, Dicts

Tuple type: (a, b, c)
List type: List a (prelude)
Array type: Array a (prelude)
Dict type: Dict a (prelude; key type is a symbol/field label at runtime)

ADTs

Define an ADT with type:

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

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 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
  when A {x} -> { s with { x = x + 1 } }
  when 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):

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

Top-level fn declarations are mutually recursive, so they can refer to each other in the same module:

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

Type Classes (`class`)

Type classes declare overloaded operations. Method signatures live in the class:

class Size a
  size : a -> i32

Methods can be operators (use parentheses to refer to them as values if needed):

class Eq a
  == : a -> a -> bool

Superclasses use <= (read “requires”):

class Ord a <= Eq a
  < : a -> a -> bool

Instances (`instance`)

Instances attach method implementations to a concrete head type, optionally with constraints:

class Size a
  size : a -> i32

instance Size (List t)
  size = \xs ->
    match xs
      when Empty -> 0
      when Cons _ rest -> 1 + size rest

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
  show : a -> string

instance Show i32
  show = \_ -> "<i32>"

instance Show (List a) <= Show a
  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, Array, Option, Result
Foldable, Filterable, Sequence
multi-parameter Indexable t a with instances for lists/arrays

Example: Functor across different container types:

( map ((*) 2) [1, 2, 3]
, map ((+) 1) (Some 41)
, map ((*) 2) (Ok 21)
)

Example: Indexable:

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.

Module Imports

Rex distinguishes between:

program/snippet execution (declarations + one expression), and
module files used by the import system (declaration-only).

When a .rex file is loaded as a module via the module system, it must not contain a top-level expression result.

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 <module> as <Alias> imports the module namespace and requires qualified access (Alias.member).
import <module> (*) imports all exported values into unqualified scope.
import <module> (x, y as z) imports selected exported values into unqualified scope.
as <Alias> on the module and (...) import clauses are mutually exclusive.

Visibility and Exports

Only exported (pub) values are importable through (*) and item clauses.

Module aliases expose all export namespaces for qualified lookup:

Alias.value resolves against exported values (including constructors).
Alias.Type resolves against exported type names in type positions.
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.

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.
Cyclic imports are supported via strongly connected component (SCC) loading of module interfaces.

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

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:

If T is a record type { ..., field : τ, ... }, then Γ ⊢ base.field : τ.
If T is a single-variant ADT whose payload is a record containing field : τ, then Γ ⊢ base.field : τ.
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:

Each updated field exists on the definite record shape of T.
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).
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”).

The typechecker refines “which constructor is known” via two mechanisms:

Pattern matching: within a when K { ... } -> ... arm, the scrutinee is known to be K.
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 = A { x = 1 } in
match s
  when A {x} -> { s with { x = x + 1 } }
  when B {x} -> { s with { x = x + 2 } }

Evaluation

Evaluation is strict:

Evaluate base to a value.
Evaluate all update expressions (left-to-right in the implementation’s map iteration order).
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:

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.
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).
If exactly one instance head unifies with the instance parameter type, its method body is specialized and evaluated.
If none match, the engine errors (EngineError::MissingTypeclassImpl).
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).

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.

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

Defaulting

Defaulting runs after type inference and before evaluation.

Eligible Variables

A type variable α is eligible for defaulting iff:

α appears only in simple predicates of the form C α (not in compound types), and
every such C is in the defaultable set: AdditiveMonoid, MultiplicativeMonoid, AdditiveGroup, Ring, Field, Integral.

If α appears in any non-simple predicate or any non-defaultable class predicate, it is not defaulted.

Candidate Types (Order Matters)

The candidate list is constructed in this order:

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).
Append (if not already present): f32, i32, string.

Choosing a Default

For an eligible variable α with required predicates { C₁ α, ..., Cₙ α }, choose the first candidate type T such that all predicates are satisfied in the empty context:

entails([], Cᵢ T) for all i

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

Architecture

Rex is implemented as a small set of focused crates that form a pipeline:

Lexing (rexlang-lexer): converts source text into a Vec<Token> with spans.
Parsing (rexlang-parser): converts tokens into a rex_ast::expr::Program { decls, expr }.
Typing (rexlang-typesystem): Hindley–Milner inference + ADTs + type classes; produces a rex_ts::TypedExpr.
Evaluation (rexlang-engine): evaluates TypedExpr to a runtime 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, Program, symbols).
rexlang-lexer: tokenizer + spans (Span, Position).
rexlang-parser: recursive-descent parser. Entry point: rex_parser::Parser::parse_program.
- For untrusted code, set ParserLimits::safe_defaults before parsing.
rexlang-typesystem: type system. Entry points:
- TypeSystem::with_prelude()? to create a typing environment with standard types/classes.
- TypeSystem::infer_typed / TypeSystem::infer for type inference.
- For untrusted code, set TypeSystemLimits::safe_defaults before inference.
rexlang-engine: runtime evaluator. Entry points:
- Engine::with_prelude(state)? to inject runtime constructors and builtin implementations (state can be ()).
- Engine::inject_decls(&program.decls) to make user declarations available at runtime.
- Engine::eval_with_gas(&program.expr, &mut gas).await to evaluate.
- Engine carries host state as Engine<State> (State: Clone + Sync + 'static); typed export callbacks receive &State and return Result<T, EngineError>, typed export_async callbacks receive &State and return Future<Output = Result<T, EngineError>>, while pointer-level APIs (export_native*) receive &Engine<State>.
- Host module injection API: Module + Export + Engine::inject_module.
rexlang-proc-macro: #[derive(Rex)] bridge for Rust types ↔ Rex ADTs/values.
rex: CLI front-end around the pipeline.
rexlang-lsp / rexlang-vscode: editor tooling.

Design Notes

Typed evaluation: rexlang-engine always evaluates a TypedExpr; it typechecks first (via rexlang-typesystem) and then evaluates. This keeps runtime behavior predictable and makes native-function dispatch type-directed.
Prelude split: The type system prelude is a combination of:
- ADT/typeclass heads injected by TypeSystem::with_prelude()?
- typeclass method bodies (written in Rex) loaded from rexlang-typesystem/src/prelude_typeclasses.rex and injected by Engine::with_prelude(state)? (state can be ())
Depth bounding: Some parts of the pipeline are naturally recursive (parsing deeply nested parentheses, matching deeply nested terms). Parser/typechecker limit APIs provide 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.

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: lexer/parser operate on 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.
Filesystem/module specifiers: import specifiers and path labels are textual before being resolved into structured module identities.

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.

Memory Management

rexlang-engine uses a pointer-based runtime: evaluated values live in a central heap, and the rest of the runtime passes lightweight pointers to those heap entries.

This gives the engine a clear separation between identity (Pointer) and storage (Heap). It also makes behavior at host/native boundaries explicit: values are allocated once, referenced many times, and inspected through heap APIs.

Design goals and rationale

Support graph-shaped runtime data, including cycles.
Keep allocation and dereference rules explicit and centralized.
Make host integration predictable by using stable pointers rather than implicit deep copies.
Preserve strong runtime safety checks for pointer validity and heap ownership.
Keep diagnostics (type names, debug/display output, equality) correct for heap graphs.

Core runtime model

`Pointer` is an opaque stable pointer

A Pointer identifies a slot in a heap using:

heap_id
index
generation

Conceptually:

index selects a slot.
generation distinguishes different occupants of the same slot over time.
heap_id prevents accidental cross-heap usage.

Pointer is intentionally opaque to callers. The engine validates it on access, so stale pointers and cross-heap usage fail deterministically at runtime.

`Heap` stores all runtime values

Heap owns an internal HeapState:

slots: Vec<HeapSlot>
free_list: Vec<u32>

Each HeapSlot stores:

generation: u32
value: Option<Arc<Value>>

All runtime reads/writes go through heap methods (alloc_*, get, type_name, etc.). Pointer internals are not exposed in API shape.

Engine-owned heap lifecycle

Engine constructs and owns its own Heap (Engine::new, Engine::with_prelude).

Evaluation returns Pointer, not Value.
Callers can inspect via engine.heap() or extract ownership with engine.into_heap().

This keeps allocation authority clear: the engine is responsible for heap creation, and the heap is the single runtime store for values.

Read/write semantics

Reads return `ValueRef`

Heap::get returns ValueRef (an Arc<Value> wrapper), not a copied Value.

Why:

Avoid accidental deep clones in hot paths.
Make cloning explicit and local where it is actually needed.

Writes are controlled

Values are created through Heap::alloc_* methods.

There is also an internal overwrite operation used for recursive initialization patterns (placeholder first, then finalized value).

Equality, debug, and display are heap-aware

Structural operations are provided as heap-aware helpers:

value_debug(heap, value)
value_display(heap, value)
value_eq(heap, lhs, rhs)
pointer_eq(heap, lhs, rhs)
closure_debug / closure_eq

These functions dereference through the heap and are cycle-safe (visited-set based), so recursive graphs can be inspected and compared without infinite recursion.

Pointer-first host/native boundary

Runtime conversion traits are pointer-centric:

IntoPointer
FromPointer

Native injection and prelude paths pass pointers by default, including module runtime exports (export_native / export_native_async). These callbacks receive &Engine<State>, so they can allocate through engine.heap() and inspect host state via engine.state. Value is used where direct payload inspection is required.

This keeps ownership/allocation behavior centralized in the heap and limits implicit copying.

Safety and invariants

At runtime, the heap enforces:

Wrong-heap pointer rejection (heap_id mismatch).
Invalid/stale pointer rejection (index/generation mismatch).
Type-aware errors via heap-driven type_name.

No unsafe code is used for this memory model.

Scope and limitations

This is a pointer-based heap model, not a full garbage-collected runtime.
There is no public reclamation/GC API yet.
The pointer format includes generation and the heap tracks a free_list in state, but active slot-reuse/reclamation policy is intentionally not exposed as public behavior yet.

In short, memory management is centered on explicit heap ownership, validated pointers, and cycle-safe graph traversal, with reclamation strategy treated as a separate concern.

Embedding Rex in Rust

Rex is designed as a small pipeline you can embed at whatever stage you need:

rexlang-lexer: source → Tokens
rexlang-parser: tokens → Program { decls, expr }
rexlang-typesystem: HM inference + type classes → TypedExpr (plus predicates/type)
rexlang-engine: evaluate a TypedExpr → rexlang_engine::Value

This document focuses on common embedding patterns.

Running Untrusted Rex Code (Production Checklist)

This repo provides the mechanisms to safely run user-submitted Rex (gas metering, parsing limits, cancellation). Your production server is responsible for enforcing hard resource limits (process isolation, wall-clock timeouts, memory limits).

Recommended defaults for untrusted input:

Always cap parsing nesting depth with ParserLimits::safe_defaults() (or stricter).
Always run with a bounded GasMeter for parse + infer + eval (and calibrate budgets with real workloads).
Treat EngineError::OutOfGas and EngineError::Cancelled as normal user-visible outcomes.
Run evaluation in an isolation boundary you can hard-kill (separate process/container), with CPU/RSS/time limits.

Evaluation API:

Evaluation is async and gas-metered via Engine::eval_with_gas.

Evaluate Rex Code

#![allow(unused)]
fn main() {
use rexlang_engine::Engine;
use rex_lexer::Token;
use rex_parser::Parser;
use rex_util::{GasCosts, GasMeter};

let tokens = Token::tokenize("let x = 1 + 2 in x * 3")?;
let mut parser = Parser::new(tokens);
let program = parser.parse_program(&mut GasMeter::default()).map_err(|errs| format!("{errs:?}"))?;

let mut engine = Engine::with_prelude(())?;
engine.inject_decls(&program.decls)?;
let mut gas = GasMeter::default();
let value = engine
    .eval_with_gas(program.expr.as_ref(), &mut gas)
    .await?;
println!("{value}");
}

Module sources loaded via resolvers (and module files on disk) must be declaration-only. To run an expression, use snippet/repl 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.

Engine Initialization and Default Imports

Engine::with_prelude(state) is shorthand for Engine::with_options(state, EngineOptions::default()).

Prelude is enabled by default.
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:

#![allow(unused)]
fn main() {
use rexlang_engine::{Engine, EngineOptions, PreludeMode};

let mut engine = Engine::with_options(
    (),
    EngineOptions {
        prelude: PreludeMode::Disabled,
        default_imports: vec![],
    },
)?;
}

Inject Modules (Embedder Patterns)

This is fully supported in rexlang-engine. You can compose module loading from:

default resolvers (std.*, local filesystem, optional remote feature)
include roots
custom resolvers (for DB/object-store/in-memory modules)

1) Use Built-In Resolvers

#![allow(unused)]
fn main() {
use rexlang_engine::Engine;
use rex_util::GasMeter;

let mut engine = Engine::with_prelude(())?;
engine.add_default_resolvers();
engine.add_include_resolver("/opt/my-app/rex-modules")?;

let mut gas = GasMeter::default();
let value = engine
    .eval_module_file("workflows/main.rex", &mut gas)
    .await?;
println!("{value}");
}

Notes:

local imports are resolved relative to the importing module path.
include roots are searched after local-relative imports.
type-only workflows can use infer_module_file with the same resolver setup.
import clauses ((*) / item lists) import exported values only.
module aliases (import x as M) provide qualified access to exported values, types, and classes.

2) Inject In-Memory Rex Modules

For host-managed modules, add a resolver that maps module_name to source text.

use rexlang_engine::{Engine, ModuleId, ResolveRequest, ResolvedModule};
use rex_util::GasMeter;
use std::collections::HashMap;
use std::sync::Arc;

let mut engine = Engine::with_prelude(())?;
engine.add_default_resolvers();

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(),
    ),
]));

engine.add_resolver("host-map", {
    let modules = modules.clone();
    move |req: ResolveRequest| {
        let Some(source) = modules.get(&req.module_name) else {
            return Ok(None);
        };
        Ok(Some(ResolvedModule {
            id: ModuleId::Virtual(format!("host:{}", req.module_name)),
            source: source.clone(),
        }))
    }
});

let mut gas = GasMeter::default();
let value = engine
    .eval_snippet("import acme.main (main)\nmain", &mut gas)
    .await?;
println!("{value}");

3) Host-Provided Rust Functions, Exposed as Modules

This is the common embedder case.

Use Module + Engine::inject_module(...):

Create a Module.
Add exports:
- typed exports with export / export_async
- runtime/native exports with export_native / export_native_async
- optional Rex declarations with add_declaration (for example pub type ...)
Inject it into the engine.

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

#![allow(unused)]
fn main() {
use rexlang_engine::{Engine, Module};
use rex_util::GasMeter;

let mut engine = Engine::with_prelude(())?;
engine.add_default_resolvers();

let mut math = Module::new("acme.math");
math.export("inc", |_state: &(), x: i32| { Ok(x + 1) })?;
math.export_async("double_async", |_state: &(), x: i32| async move { Ok(x * 2) })?;
engine.inject_module(math)?;

let mut gas = GasMeter::default();
let value = engine
    .eval_snippet(
        "import acme.math (inc, double_async as d)\ninc (d 20)",
        &mut gas,
    )
    .await?;
println!("{value}");
}

You can declare ADTs directly inside an injected host module:

#![allow(unused)]
fn main() {
use rexlang_engine::{Engine, Module};

let mut engine = Engine::with_prelude(())?;
engine.add_default_resolvers();

let mut m = Module::new("acme.status");
m.add_declaration("pub type Status = Ready | Failed string")?;
engine.inject_module(m)?;
}

Then Rex code can import and use those constructors from the module:

import acme.status (Failed)
match (Failed "boom")
  when Failed msg -> length msg
  when _ -> 0

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 (runtime pointer handlers)

Then add them via Module::add_export.

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:

#![allow(unused)]
fn main() {
use rex::{Engine, EngineError, Module, Rex};
use rex_util::GasMeter;

#[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 engine = Engine::with_prelude(())?;
engine.add_default_resolvers();

let mut m = Module::new("sample");
m.inject_rex_adt::<Side>(&mut engine)?;
m.inject_rex_adt::<Label>(&mut engine)?;
m.export("render_label", |_state: &(), label: Label| {
    Ok::<String, EngineError>(render_label(label))
})?;
engine.inject_module(m)?;

let mut gas = GasMeter::default();
let value = engine
    .eval_snippet(
        r#"
        import sample (Label, Left, Right, render_label)
        (
            render_label (Label { text = "left", side = Left }),
            render_label (Label { text = "right", side = Right })
        )
        "#,
        &mut gas,
    )
    .await?;
println!("{value}"); // ("left        ", "       right")
}

3a) Runtime-Defined Signatures (`Pointer` 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 &Engine<State> (not just &State), so they can:

read state via engine.state
allocate new values via engine.heap
inspect typed call information via the explicit &Type / Type callback parameter

#![allow(unused)]
fn main() {
use futures::FutureExt;
use rexlang_engine::{Engine, Module, Pointer};
use rex_ts::{BuiltinTypeId, Scheme, Type};

let mut engine = Engine::with_prelude(())?;
engine.add_default_resolvers();

let mut m = Module::new("acme.dynamic");
let scheme = Scheme::new(vec![], vec![], Type::fun(Type::builtin(BuiltinTypeId::I32), Type::builtin(BuiltinTypeId::I32)));

m.export_native("id_ptr", scheme.clone(), 1, |_engine: &Engine<()>, _typ: &Type, args: &[Pointer]| {
    Ok(args[0].clone())
})?;

m.export_native_async("answer_async", Scheme::new(vec![], vec![], Type::builtin(BuiltinTypeId::I32)), 0, |engine: &Engine<()>, _typ: Type, _args: Vec<Pointer>| {
    async move { engine.heap.alloc_i32(42) }.boxed_local()
})?;

engine.inject_module(m)?;
}

Scheme and arity must agree. Registration returns an error if the type does not accept the provided number of arguments.

4) Custom Resolver Contract (Advanced)

If you need dynamic/nonstandard module loading behavior, you can still use raw resolvers.

Resolver contract:

return Ok(Some(ResolvedModule { ... })) when you can satisfy the module.
return Ok(None) to let the next resolver try.
return Err(...) for hard failures (invalid module payload, policy violations, etc.).

5) Snippets That Import Relative Modules

If you evaluate ad-hoc Rex snippets that contain imports, use eval_snippet_at (or infer_snippet_at) to provide an importer path anchor:

#![allow(unused)]
fn main() {
let mut gas = rex_util::GasMeter::default();
let value = engine
    .eval_snippet_at("import foo.bar as Bar\nBar.add 1 2", "/tmp/workflow/_snippet.rex", &mut gas)
    .await?;
}

Engine State

Engine is generic over host state: Engine<State>, where State: Clone + Sync + 'static. The state is stored as engine.state: Arc<State> and is shared across all injected functions.

Use Engine::with_prelude(())? if you do not need host state.
If you do, pass your state struct into Engine::new(state) or Engine::with_prelude(state).
export / export_async callbacks receive &State as their first parameter.
Pointer-level APIs (export_native*) receive &Engine<State> so they can use heap/runtime internals and read engine.state.

#![allow(unused)]
fn main() {
use rexlang_engine::Engine;

#[derive(Clone)]
struct HostState {
    user_id: String,
    roles: Vec<String>,
}

let mut engine: Engine<HostState> = Engine::with_prelude(HostState {
    user_id: "u-123".into(),
    roles: vec!["admin".into(), "editor".into()],
})?;

engine.export("have_role", |state, role: String| {
    Ok(state.roles.iter().any(|r| r == &role))
})?;
}

Array/List Interop at Host Boundaries

Rex keeps both List a and Array a because they serve different goals:

List a is ergonomic for user-authored functional code and pattern matching.
Array a is the host-facing contiguous representation (for example Vec<u8> from filesystem reads).

At host function call sites, Rex performs a narrow implicit coercion from List a to Array a in argument position. This means users can pass list literals to host functions that accept Vec<T> without writing conversions.

accept_bytes [1, 2, 3]

where accept_bytes is exported from Rust with a Vec<u8> parameter.

For the opposite direction, Rex exposes explicit helpers:

to_list : Array a -> List a
to_array : List a -> Array a

Why `to_list` Is Explicit (Not Implicit)

Array -> List conversion is intentionally explicit to keep runtime costs predictable in user code. Converting an array into a list allocates a new linked structure and changes performance characteristics for downstream operations.

If this conversion were implicit everywhere, the compiler could silently insert it in places where users do not expect allocation or complexity changes (for example inside control-flow joins, nested expressions, or polymorphic code). That would make performance harder to reason about and make type errors less transparent.

By requiring to_list explicitly, we keep intent and cost visible at the exact program point where representation changes. This preserves ergonomics while avoiding hidden work:

match (to_list bytes) with
    when Cons head _ -> head
    when Empty -> 0

Typecheck Without Evaluating

#![allow(unused)]
fn main() {
use rex_lexer::Token;
use rex_parser::Parser;
use rex_ts::TypeSystem;

let tokens = Token::tokenize("map (\\x -> x) [1, 2, 3]")?;
let mut parser = Parser::new(tokens);
let program = parser.parse_program(&mut GasMeter::default()).map_err(|errs| format!("{errs:?}"))?;

let mut ts = TypeSystem::with_prelude()?;
for decl in &program.decls {
    match decl {
        rex_ast::expr::Decl::Type(d) => ts.inject_type_decl(d)?,
        rex_ast::expr::Decl::Class(d) => ts.inject_class_decl(d)?,
        rex_ast::expr::Decl::Instance(d) => {
            ts.inject_instance_decl(d)?;
        }
        rex_ast::expr::Decl::Fn(d) => ts.inject_fn_decl(d)?,
    }
}

let (preds, ty) = ts.infer(program.expr.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:

Parse Rex source into Program { decls, expr }.
Inject Decl::Class / Decl::Instance into the type system (if you’re typechecking without running).
Inject all decls into the engine (if you’re running), so instance method bodies are available at runtime.

Typecheck: Inject Class/Instance Decls into `TypeSystem`

#![allow(unused)]
fn main() {
use rex_lexer::Token;
use rex_parser::Parser;
use rex_ts::TypeSystem;

let code = r#"
class Size a
    size : a -> i32

instance Size (List t)
    size = \xs ->
        match xs
            when Empty -> 0
            when Cons _ rest -> 1 + size rest

size [1, 2, 3]
"#;

let tokens = Token::tokenize(code)?;
let mut parser = Parser::new(tokens);
let program = parser.parse_program(&mut GasMeter::default()).map_err(|errs| format!("{errs:?}"))?;

let mut ts = TypeSystem::with_prelude()?;
for decl in &program.decls {
    match decl {
        rex_ast::expr::Decl::Type(d) => ts.inject_type_decl(d)?,
        rex_ast::expr::Decl::Class(d) => ts.inject_class_decl(d)?,
        rex_ast::expr::Decl::Instance(d) => {
            ts.inject_instance_decl(d)?;
        }
        rex_ast::expr::Decl::Fn(d) => ts.inject_fn_decl(d)?,
    }
}

let (_preds, ty) = ts.infer(program.expr.as_ref())?;
assert_eq!(ty.to_string(), "i32");
}

Evaluate: Inject Decls into `Engine`

#![allow(unused)]
fn main() {
use rexlang_engine::{Engine, EngineError};
use rex_lexer::Token;
use rex_parser::Parser;
use rex_util::{GasCosts, GasMeter};

let code = r#"
class Size a
    size : a -> i32

instance Size (List t)
    size = \xs ->
        match xs
            when Empty -> 0
            when Cons _ rest -> 1 + size rest

(size [1, 2, 3], size [])
"#;

let tokens = Token::tokenize(code)?;
let mut parser = Parser::new(tokens);
let program = parser.parse_program(&mut GasMeter::default()).map_err(|errs| format!("{errs:?}"))?;

let mut engine = Engine::with_prelude(())?;
engine.inject_decls(&program.decls)?;
let mut gas = GasMeter::default();
let value = engine
    .eval_with_gas(program.expr.as_ref(), &mut gas)
    .await?;
println!("{value}");
}

Inject Native Values and Functions

rexlang-engine is the boundary where Rust provides implementations for Rex values.

For host-provided modules, prefer Module + inject_module (above). The direct injection APIs below register exports into the root scope (the engine’s root module), which is useful for values or functions you want available without importing a host module.

#![allow(unused)]
fn main() {
use rexlang_engine::Engine;

let mut engine = Engine::with_prelude(())?;
engine.export_value("answer", 42i32)?;
engine.export("inc", |_state, x: i32| { Ok(x + 1) })?;
}

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:

#![allow(unused)]
fn main() {
use rexlang_engine::Engine;
use rex_util::GasMeter;

let mut engine = Engine::with_prelude(())?;
engine.export("num_u8", |_state: &(), x: u8| Ok(format!("{x}:u8")))?;
engine.export("num_i64", |_state: &(), x: i64| Ok(format!("{x}:i64")))?;

for code in [
    "num_u8 4",
    "let x = 4 in num_u8 x",
    "let f = \\x -> num_i64 x in f 4",
] {
    let tokens = rex_lexer::Token::tokenize(code)?;
    let mut parser = rex_parser::Parser::new(tokens);
    let program = parser
        .parse_program(&mut GasMeter::default())
        .map_err(|errs| format!("parse error: {errs:?}"))?;
    let mut gas = GasMeter::default();
    let value = engine.eval_with_gas(program.expr.as_ref(), &mut gas).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.

Async Natives

If your host functions are async, inject them with export_async and evaluate with Engine::eval_with_gas.

#![allow(unused)]
fn main() {
use rexlang_engine::Engine;
use rex_util::{GasCosts, GasMeter};

let mut engine = Engine::with_prelude(())?;
engine.export_async("inc", |_state, x: i32| async move { Ok(x + 1) })?;

let tokens = rex_lexer::Token::tokenize("inc 1")?;
let mut parser = rex_parser::Parser::new(tokens);
let program = parser
    .parse_program(&mut GasMeter::default())
    .map_err(|errs| format!("parse error: {errs:?}"))?;
let mut gas = GasMeter::default();
let v = engine.eval_with_gas(program.expr.as_ref(), &mut gas).await?;
println!("{v}");
}

Cancellation

Async natives can be cancelled. Cancellation is cooperative: you get a CancellationToken and trigger it from another thread/task, and the engine will stop evaluation with EngineError::Cancelled.

#![allow(unused)]
fn main() {
use futures::FutureExt;
use rexlang_engine::{CancellationToken, Engine, EngineError};
use rex_ts::{BuiltinTypeId, Scheme, Type};
use rex_util::{GasCosts, GasMeter};

let tokens = rex_lexer::Token::tokenize("stall")?;
let mut parser = rex_parser::Parser::new(tokens);
let expr = parser
    .parse_program(&mut GasMeter::default())
    .map_err(|errs| format!("parse error: {errs:?}"))?
    .expr;

let mut engine = Engine::with_prelude(())?;
let scheme = Scheme::new(vec![], vec![], Type::builtin(BuiltinTypeId::I32));
engine.export_native_async_cancellable(
    "stall",
    scheme,
    0,
    |engine, token: CancellationToken, _, _args| {
        async move {
            token.cancelled().await;
            engine.heap.alloc_i32(0)
        }
        .boxed_local()
    },
)?;

let token = engine.cancellation_token();
std::thread::spawn(move || {
    std::thread::sleep(std::time::Duration::from_millis(10));
    token.cancel();
});
let mut gas = GasMeter::default();
let res = engine.eval_with_gas(expr.as_ref(), &mut gas).await;
assert!(matches!(res, Err(EngineError::Cancelled)));
}

Gas Metering

To defend against untrusted/large programs, you can run the pipeline with a gas budget:

Parser::parse_program
TypeSystem::infer_with_gas / infer_typed_with_gas
Engine::eval_with_gas

Parsing Limits

For untrusted input, you can cap syntactic nesting depth during parsing:

#![allow(unused)]
fn main() {
use rex_parser::{Parser, ParserLimits};

let mut parser = Parser::new(rex_lexer::Token::tokenize("(((1)))")?);
parser.set_limits(ParserLimits::safe_defaults());
let program = parser.parse_program(&mut GasMeter::default())?;
}

Bridge Rust Types with `#[derive(Rex)]`

The derive:

declares an ADT in the Rex type system
injects runtime constructors (so Rex can build values)
implements FromPointer/IntoPointer for converting Rust ↔ Rex

#![allow(unused)]
fn main() {
use rex::{Engine, FromPointer, GasMeter, Parser, Token, Rex};

#[derive(Rex, Debug, PartialEq)]
enum Maybe<T> {
    Just(T),
    Nothing,
}

let mut engine = Engine::with_prelude(())?;
Maybe::<i32>::inject_rex(&mut engine)?;

let expr = Parser::new(Token::tokenize("Just 1")?)
    .parse_program(&mut GasMeter::default())
    .map_err(|errs| format!("parse error: {errs:?}"))?
    .expr;
let mut gas = GasMeter::default();
let (v, _ty) = engine.eval_with_gas(expr.as_ref(), &mut gas).await?;
assert_eq!(Maybe::<i32>::from_pointer(&engine.heap, &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 Engine::adt_decl_from_type(...) to seed an ADT declaration from a Rex type head.
Add variants with AdtDecl::add_variant(...).
Register with Engine::inject_adt(...).

#![allow(unused)]
fn main() {
use rex::{Engine, RexType, Type, sym};

let mut engine = Engine::with_prelude(())?;

let mut adt = engine.adt_decl_from_type(&Type::con("PrimitiveEither", 0))?;
adt.add_variant(sym("Flag"), vec![bool::rex_type()]);
adt.add_variant(sym("Count"), vec![i32::rex_type()]);
engine.inject_adt(adt)?;
}

If you have a Rust type with manual RexType/IntoPointer/FromPointer impls, implement RexAdt and provide rex_adt_decl(...). Then RexAdt::inject_rex(...) gives the same registration workflow as derived types.

#![allow(unused)]
fn main() {
use rex::{AdtDecl, Engine, EngineError, RexAdt, RexType, Type, sym};

struct PrimitiveEither;

impl RexType for PrimitiveEither {
    fn rex_type() -> Type {
        Type::con("PrimitiveEither", 0)
    }
}

impl RexAdt for PrimitiveEither {
    fn rex_adt_decl<State: Clone + Send + Sync + 'static>(
        engine: &mut Engine<State>,
    ) -> Result<AdtDecl, EngineError> {
        let mut adt = engine.adt_decl_from_type(&Self::rex_type())?;
        adt.add_variant(sym("Flag"), vec![bool::rex_type()]);
        adt.add_variant(sym("Count"), vec![i32::rex_type()]);
        Ok(adt)
    }
}

let mut engine = Engine::with_prelude(())?;
PrimitiveEither::inject_rex(&mut engine)?;
}

Depth Limits

Some workloads (very deep nesting) can exhaust parser/typechecker recursion depth. Prefer bounded limits for untrusted code:

rex_parser::ParserLimits::safe_defaults
rex_ts::TypeSystemLimits::safe_defaults

Contributing

Workspace Layout

Rex is a Cargo workspace. The most important crates are:

rexlang-lexer: tokenization + spans
rexlang-parser: parsing into a Program { decls, expr }
rexlang-typesystem: Hindley–Milner inference + type classes + ADTs
rexlang-engine: typed evaluation + native injection
rexlang-proc-macro: #[derive(Rex)] bridge for Rust types ↔ Rex types/values
rex: CLI 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 lex→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 rexlang-fuzz, a set of stdin-driven harness binaries:

cargo build -p rexlang-fuzz --bins
printf '1 + 2' | cargo run -q -p rexlang-fuzz --bin e2e
printf '(' | cargo run -q -p rexlang-fuzz --bin parse

Tuning knobs (environment variables):

REX_FUZZ_GAS: gas budget for the harness run
REX_FUZZ_MAX_NESTING: parser nesting cap (defaults to ParserLimits::safe_defaults())
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)
rexlang-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)
    when Ok ph -> Ok (classify_ph ph)
    when 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 a selected quick-fix by identifier, 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 gas budgets, timeouts, concurrency 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.

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 QuickFix = {
  id: string;
  title: string;
  kind: string | null;
  edit: WorkspaceEdit | null;
};

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: QuickFix[];
  quickFixTitles: string[];
  holes: HoleInfo[];
}

rex.semanticLoopApplyQuickFixAt

args:
  | { uri: string; line: u32; character: u32; id: string }
  | [uri: string, line: u32, character: u32, id: string]
returns: null | { quickFix: QuickFix }

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: QuickFix[];
  appliedCount: u64;
  steps: Array<{
    index: u64;
    quickFix: QuickFix;
    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:

This chapter (LLMS.md) for semantic-loop workflow and generation pitfalls.
LANGUAGE.md for syntax and everyday feature usage.
SPEC.md for locked behavior when edge cases matter.

High-Value Rules

Use fn for top-level reusable functions; use let and let rec for local helpers.
For local mutual recursion, use comma-separated let rec bindings.
Use x::xs for list cons in both patterns and expressions (x::xs is equivalent to Cons x xs).
Validate snippets with the Rex CLI before shipping docs.

Quick Generation Checklist

Before returning generated Rex code:

Put top-level reusable functions in fn declarations (they are mutually recursive).
Use let rec only for local recursive helpers inside expressions.
Add annotations where constructor or numeric ambiguity is likely (Empty, zero, overloaded methods).
Ensure the final expression returns a visible result (often a tuple for demos).
Run cargo run -p rex -- run /tmp/snippet.rex and fix all parse and type errors.

Syntax Pitfalls

1) Recursion model

Top-level fn declarations are mutually recursive.
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 when 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)
    when (A, A) -> true
    when (B, B) -> true
    when _ -> 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
    when Empty -> 0
    when Node {key, left, right} -> key

Save the snippet to a temporary .rex file.
Run cargo run -p rex -- run /tmp/snippet.rex.
If parse or type errors appear, fix and re-run until clean.

For mdBook interactive demos, also run:

cd docs
mdbook build

Keyboard shortcuts

Rex