Skip to main content

Abstract Interpretation

Nudo’s goal is to let developers see variables close to runtime inside the source. Abstract interpretation is how that is computed: instead of running code with concrete values (like a test) or analyzing code without running it (like TypeScript), Nudo executes code on Abs (symbolic shape × term × pred × conf values). Execution itself produces what each intermediate will be — a literal, a shape, a constraint — which is what the IDE and nudo check display.

Three Approaches Compared​

ApproachInputWhat a variable showsCompleteness
Unit testsConcrete values (1, "hello")One concrete resultOnly test cases
NudoAbs (number(), string(), literals)Runtime-adjacent value / shape / constraintAll values in the abstract set
TypeScriptAST (no execution)Declared type nameAll syntactic paths

When Nudo executes transform(string()), the engine propagates string() through the function body. At typeof x === "string", the engine knows that branch is taken. At x.toUpperCase(), the engine knows the result is string(). The variable does not merely get a type name — it carries a computable Abs, which is what surfaces as an inlay or signature.


Evaluation Engine Architecture​

┌─────────────────────────────────────────────────────┐
│ Nudo Engine │
│ │
│ ┌───────────┐ ┌────────────┐ ┌──────────────┐ │
│ │ Parser │──▶│ Directive │──▶│ Evaluator │ │
│ │ (Babel) │ │ Extractor │ │ (evaluator/Abs) │ │
│ └───────────┘ └────────────┘ └──────┬───────┘ │
│ │ │
│ ┌───────────────────────┐│ │
│ │ algebra surface / ││ │
│ │ arithmetic / route │◀ │
│ └───────────────────────┘ │
│ │
│ ┌──────────────┐ ┌─────────────┐ ┌───────────┐ │
│ │ Environment │ │ Branch │ │ Type │ │
│ │ (Scope) │ │ Executor │ │ Emitter │ │
│ └──────────────┘ └─────────────┘ └───────────┘ │
└─────────────────────────────────────────────────────┘
ComponentResponsibility
ParserParse JS/TS source into AST (delegates to Babel)
Directive ExtractorExtract @nudo:* directives from comments
Evaluatorevaluator transpile+exec (single engine): evaluate each node with Abs
surface / arithmetic / objectsOperator semantics on Abs for arithmetic, comparison, unary, spread, and branch-merge join
EnvironmentManage variable scopes and bindings (name → Abs)
Branch ExecutorHandle conditional branches: fork, narrow, evaluate, merge
Type EmitterSerialize final Abs results (optionally to TypeScript types)

Evaluation Rules​

The evaluator executes the function body with Abs values. Source is transpiled and run with Abs operands (single evaluator engine). For each AST node type there is a corresponding lowering/evaluation rule.

Literals​

eval(NumericLiteral { value: 42 }) → numLit(42)
eval(StringLiteral { value: "hi" }) → strLit("hi")
eval(BooleanLiteral { value: true }) → boolLit(true)
eval(NullLiteral) → null Abs

Variables​

eval(Identifier { name: "x" }) → env.vars.get("x")

Binary Expressions​

eval(BinaryExpression { left, op, right }) → tryAbsBinary(op, eval(left), eval(right))

Assignment​

eval(AssignmentExpression { left: "x", right: expr })
→ env = withVar(env, "x", eval(expr))

Conditional (if-else)​

This is where the engine differs fundamentally from a normal interpreter. Instead of always choosing one branch, it forks when the test is not decidable — but note: it does not narrow abstract values. Both arms run with the same bindings:

eval(IfStatement { test, consequent, alternate }) →
condition = eval(test)

// Case 1: condition is definitely true/false
if isDefinitelyTrue(condition) → eval(consequent)
if isDefinitelyFalse(condition) → eval(alternate)

// Case 2: condition is abstract → run both branches with the same env
resultTrue = eval(consequent, env)
resultFalse = eval(alternate, env)
return joinAbs(resultTrue, resultFalse)

isDefinitelyTrue/False is what makes per-call-site narrowing possible: a concrete argument often makes the test fold to a literal, so only one branch runs for that call. An abstract argument cannot fold the test — both branches run and their results join.

Function Declaration​

eval(FunctionDeclaration { id: "foo", params, body })
→ env.fns.set("foo", absFunction(params, { body, closure: env }))

Function Call​

eval(CallExpression { callee: "foo", args })
→ fn = env.fns.get("foo")
argValues = args.map(eval)
fnEnv = fn.closure.extend(zip(fn.params, argValues))
eval(fn.body, fnEnv)

Narrowing Rules​

Narrowing happens per call site: a branch runs when the condition is definitely true or false for the concrete argument of that call. Each call@L… case is evaluated with that call's exact argument, so the matching branch runs and the other is eliminated. With abstract arguments (number(), union(...)) the condition cannot be decided — both branches run with the same value and their results join. There is no intersection/subtraction of abstract types.

PatternConcrete call (per call site)Abstract / symbolic argument
typeof x === "string"string call takes the branch; x.length foldsbranches join
x === null / x === <literal>matching call forks; the other falls throughbranches join
Array.isArray(x)array call forks; x.length / x[0] resolvebranches join
truthiness (x)literal arguments forkbranches join
discriminated object (x.kind === "a")the matching shape's branch runs for that callmembers are not filtered; branches join
switch(x) { case v: … }a concrete discriminant picks its clausebranches join
in / ?. / ??partial: see the table belowpartial

Other guards (instanceof, custom predicates) fork only when the test folds to a definite boolean for the call's argument — they are not in the verified set above. The verified per-pattern walkthrough with real nudo test output: Control Flow Narrowing.


Advanced Behaviors​

Loops (Bounded Unrolling)​

When the loop bound is concrete, the engine unrolls the loop that many times. When the bound is abstract, the condition is never definitely false, so the engine unrolls up to a bounded cap (DEFAULT_MAX_LOOP_ITERS = 8) — a termination guard for abstract conditions, not a fixed-point join. Within the cap, the loop exits early when the test becomes definitely false, or when two adjacent loop states stop changing (leqAbs).

Closures and Higher-Order Functions​

Functions are first-class Abs values (fn shape). When a function is passed as an argument, the engine evaluates calls through its Abs representation (parameters, body, closure environment):

map(number[], (x) => x + 1)
// Engine evaluates: fn(number) → number + lit(1) → number
// Result: number[]

Recursion (Call Budget)​

Recursion is bounded by a call budget (MAX_CALL_DEPTH = 64), not refined to a fixed point:

  1. A recursive call is evaluated with the current arguments.
  2. When a signature is re-entered past the budget, the call is truncated.
  3. The truncated result is widened to unknown, reported as nudo:recursion-truncated (a warning in nudo check).

Concrete base cases inside the budget still evaluate to literals; symbolic self-recursion widens to unknown rather than diverging.

Async / Promise​

Promises are modeled as an effect shape (eff):

  • await expr unwraps promise<V> to V
  • async function wraps the return value in promise<...>

Exception and throws Tracking​

Nudo treats exceptions as a first-class property of function types. Every function's inferred type includes both returns and throws:

engine-verifiedRun in Playground
function divide(a, b) {
if (b === 0) throw new Error("Division by zero");
return a / b;
}
// divide(number, number):
// returns: number
// throws: instance(Error)

try-catch absorbs thrown types. The catch parameter receives the union of all thrown types from the try block. If the function never throws, throws is never.

Mutability (Reference Semantics, Copy-on-Write)​

Object Abs values use reference semantics — assignment copies references, not values. Multiple variables can point to the same object Abs value.

When entering conditional branches, the engine deep-copies modified objects so each branch has its own copy. On merge, overlapping properties become unions. Without branching, mutations are applied in-place with no overhead.

Next​