💻 computer science

Guard Analysis and Safe Erasure Gradual Typing: a Type System for Elixir

This paper introduces a novel gradual type system for Elixir that combines semantic subtyping with runtime guard analysis to enable sound static type checking and precise type refinement without modifying the language's compilation pipeline or runtime performance.

Original authors: Giuseppe Castagna, Guillaume Duboc

Published 2026-06-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Giuseppe Castagna, Guillaume Duboc

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a busy restaurant (the Elixir programming language). The kitchen is chaotic, fast-paced, and relies on the chefs (the Erlang Virtual Machine) to instinctively know if an ingredient is safe to use. If a chef tries to chop a rock instead of an onion, the machine stops the process and yells, "Hey, that's not food!" This is how Elixir works today: it's dynamic, meaning it doesn't check everything before you cook; it just checks while you're cooking.

The authors of this paper, Giuseppe Castagna and Guillaume Duboc, have built a new "Safety Inspector" for this kitchen. Their goal was to let the inspectors look at the recipes before cooking starts to catch mistakes, without slowing down the kitchen or changing how the chefs cook.

Here is how their system works, explained through simple analogies:

1. The "Safe Erasure" Strategy: Reading the Menu, Not Changing the Kitchen

Usually, when you add a safety inspector to a kitchen, you might force the chefs to wear extra safety gear or stop to get a second opinion before every chop. This slows everything down.

The authors' system is different. They call it "Safe Erasure."

The Metaphor: Imagine the inspector writes a detailed safety report on the recipe card. But, once the cooking starts, the inspector erases the report. The chefs don't wear extra gear; they just cook exactly as they always have.
Why it works: The authors realized that the kitchen machine (the VM) already has built-in safety checks. If a chef tries to add a rock to a soup, the machine stops it anyway. So, the inspector doesn't need to add new checks; it just needs to know which checks the machine already has. This allows the inspector to be very precise without slowing the kitchen down.

2. "Strong Functions": The Defensive Chef

Sometimes a recipe says, "Take any vegetable and chop it." If you give this recipe a rock, the machine will crash.
But, a "Strong Function" is like a defensive chef.

The Metaphor: This chef says, "I will chop any vegetable, but if you hand me a rock, I will immediately throw it away (fail) instead of trying to chop it."
The Result: Because this chef has a built-in safety net (a "guard" or a check), the inspector can confidently say, "If this chef returns a result, it will definitely be chopped vegetables." Even if the chef is handed a mystery ingredient (a "dynamic" type), the inspector knows the outcome will be safe because the chef is so careful.

3. Guard Analysis: The "Maybe/Definitely" Filter

In Elixir, chefs often use "guards" to decide what to do. For example: "If the ingredient is an onion, slice it; if it's a potato, mash it."

The Problem: Sometimes the rules are tricky. "If the ingredient is a red vegetable OR if it's the same size as the pan..." It's hard to know exactly what ingredients fit.
The Solution: The authors built a system that analyzes these rules and creates two lists for every rule:
1. The "Definitely Accepted" List: Ingredients that will definitely pass this rule (e.g., "Red onions").
2. The "Maybe Accepted" List: Ingredients that might pass, but we aren't 100% sure (e.g., "Red things that might be onions").
Why it matters: This allows the inspector to be super precise. If a recipe has multiple steps, the inspector can subtract the "Definitely Accepted" items from the first step to see exactly what is left for the second step. This prevents the inspector from guessing and missing errors.

4. The "Dynamic" Type: The Mystery Box

In programming, sometimes you don't know what an ingredient is until you open the box. This is called a "dynamic" type.

The Challenge: If you have a mystery box, a standard inspector would say, "I don't know what this is, so I can't tell you if the recipe is safe."
The Innovation: This system uses "Dynamic Propagation." It says, "Okay, this is a mystery box, but if the chef is a 'Strong Function' (the defensive chef), we know the result will be safe even if the box is a mystery."
The Analogy: It's like saying, "I don't know if this box contains a hammer or a screwdriver, but I know the tool I'm using will work safely with either one." This keeps the system flexible (gradual) but still safe.

5. Multi-Arity Functions: The "Number of Hands" Rule

In Elixir, a function can take one ingredient, two ingredients, or three.

The Problem: Old inspectors treated a "two-ingredient recipe" exactly the same as a "one-ingredient recipe" just by pretending the two ingredients were one big bundle. This confused the safety checks.
The Fix: The authors created a new way to count "hands" (arguments). They can now specifically say, "This recipe needs exactly two hands." This allows them to catch errors where a chef tries to use a two-hand recipe with only one ingredient, something previous systems missed.

The Real-World Test

The authors didn't just build this in theory; they put it into the actual Elixir language (starting with version 1.17).

The Result: They tested it on huge, real-world codebases (like the Phoenix web framework and the Hex package manager).
The Findings:
- It found bugs that had been hiding for years (like a recipe that tried to use a field that didn't exist).
- It found "dead code" (recipes that were written but never used).
- Crucially: It did all this without making the kitchen slower. The "inspection time" was a tiny fraction of the total cooking time (often less than 5%).

Summary

The paper presents a new way to add strict safety checks to a flexible, fast-paced programming language. By realizing that the language's engine already has safety brakes, the authors built a "smart inspector" that reads the recipes, predicts where the brakes will work, and warns you of mistakes—all without ever touching the engine or slowing down the car. It's a "safe erasure" system: the safety checks are erased from the final product, but the safety is guaranteed by the engine's own rules.

Technical Summary: Guard Analysis and Safe Erasure Gradual Typing for Elixir

1. Problem Statement

Elixir is a dynamic functional language running on the Erlang VM (BEAM), widely adopted for scalable, concurrent applications. While tools like Dialyzer exist, they lack a formal theoretical basis for a sound, expressive static type system. The challenge lies in introducing static typing to a dynamic language without modifying its compilation pipeline or runtime behavior (the "erasure" constraint), while maintaining soundness.

Standard gradual typing approaches face a dichotomy:

Runtime Checks: Inserting dynamic checks at runtime to enforce types (e.g., Reticulated Python). This is incompatible with Elixir's design, which relies on the BEAM's existing checks and aims for zero runtime overhead from type annotations.
Full Erasure: Removing type annotations entirely (e.g., TypeScript). This often leads to unsoundness or coarse approximations because the type system cannot leverage runtime guarantees.

The specific technical difficulties for Elixir include:

Guard Complexity: Elixir relies heavily on pattern matching and complex guards (e.g., is_integer(elem(x,1))) for control flow. Existing type systems struggle to precisely analyze these guards to refine types.
Multi-arity Functions: Elixir functions have explicit arity (e.g., f/2 vs f/3), which is part of their identity and testable via guards (is_function(f, 2)). Standard semantic subtyping theories often model functions as unary on tuples, failing to capture arity-specific properties.
Strong Functions: The system must distinguish between functions that are merely typed and those that are "strong"—functions that, even when applied to arguments outside their declared domain, either fail or return a value within their declared codomain due to runtime checks (either by the programmer via guards or by the BEAM).

2. Methodology

The authors formalize a type system for a core subset of Elixir (Core Elixir) and a "Featherweight" subset (FW-Elixir) that maps to the concrete syntax. The methodology relies on three pillars:

A. Safe Erasure Gradual Typing

The system adopts a "safe erasure" strategy where type annotations are erased before execution. Soundness is not enforced by inserting new runtime checks but by leveraging:

Implicit Checks: The BEAM's inherent type checks (e.g., arithmetic operations on integers).
Explicit Checks: Programmer-written guards.
The system introduces Strong Functions, which are assigned precise types even when applied to dynamic() (denoted ?) arguments, provided the function body guarantees a result in the codomain or a failure.

B. Semantic Subtyping with Set-Theoretic Types

The system utilizes semantic subtyping, interpreting types as sets of values. This allows the use of set-theoretic operators (union, intersection, difference) and provides a decidable subtyping relation.

Gradual Types: The dynamic() type is handled via consistent subtyping and materialization. A gradual type $t$ is equivalent to $t^\downarrow \lor (? \land t^\uparrow)$ , where $t^\downarrow$ and $t^\uparrow$ are the minimal and maximal static materializations.
Dynamic Propagation: To preserve the flexibility of gradual typing, the system propagates ? through results (e.g., int() and ?), allowing expressions to be used in contexts requiring either the static type or any dynamic type.

C. Guard Analysis

A novel analysis is developed to characterize the set of values accepted by guards.

Possibly/Surely Accepted Types: For a guard $g$ $g$ , the system computes:
- Possibly Accepted Type ( $\mathcal{I}g\mathcal{H}$ ): An over-approximation of values that might satisfy the guard.
- Surely Accepted Type ( $\mathcal{H}g\mathcal{I}$ ): An under-approximation of values that definitely satisfy the guard.
Refinement: The analysis partitions the input type based on guard clauses, subtracting surely accepted types of previous clauses to type subsequent branches. This handles complex guards involving boolean combinations, equality, and tuple projections.
Naive Type Narrowing: The system refines variable types within branches by intersecting the matched expression's skeleton with the guard's constraints.

D. Multi-Arity and Strong Arrows

Multi-Arity: The type system extends semantic subtyping to support $(t_1, \dots, t_n) \to t$ directly, rather than encoding them as unary functions on tuples. This enables precise typing of arity checks.
Strong Arrows: A new type constructor $(t_1 \to t_2)^\star$ denotes functions that are safe to apply to any argument, returning $t_2$ or failing, even if the argument is outside $t_1$ .

3. Key Contributions

Safe Erasure Gradual Typing: The paper defines what is claimed to be the first safe-erasure gradual type system. It achieves soundness without inserting runtime checks, relying instead on the existing guarantees of the BEAM and programmer guards.
Strong Functions: Formalization of "strong functions" and the propagation of dynamic() types. This allows the system to infer precise static types (e.g., integer()) for expressions involving dynamic() inputs, provided the function body contains sufficient checks.
Guard Analysis: A fine-grained analysis of Elixir guards that produces "surely" and "possibly" accepted types. This enables precise type refinement for case expressions and multi-clause function definitions, supporting type inference for unannotated code.
Semantic Subtyping Extension: A conservative extension of semantic subtyping theory to support multi-arity function spaces and strong arrows, including algorithms for deciding subtyping in these extended domains.
Type Inference: Techniques for inferring types for anonymous and multi-clause functions by leveraging guard analysis, reducing the need for explicit annotations.
Implementation and Evaluation: The system has been implemented in the Elixir compiler (starting v1.17). The paper presents empirical results on large industrial codebases (Phoenix, Livebook, etc.), demonstrating the detection of dead code and type errors without significant compilation overhead.

4. Results

Implementation Status: The type system is integrated into Elixir v1.17 through v1.20 (release candidates). It supports atoms, tuples, maps, lists, and function types, including protocol typing.
Performance: On large codebases (e.g., Remote with >1M lines of code), type-checking time constitutes a small percentage of total compilation time (ranging from ~1.6% to ~9.3% depending on the codebase and version). The overhead is comparable to existing ad-hoc checks in the compiler.
Precision and Error Detection:
- The system successfully identified dead code (unused clauses, unreachable paths) in major projects like Phoenix, Postgrex, and Flame.
- It detected runtime errors that were previously undetected by tests, such as a protocol call with a tuple argument in an error branch of the Phoenix framework.
- The guard analysis was shown to be highly effective in partitioning types for multi-clause functions, often inferring precise intersection types without annotations.
Comparison: The paper notes that while the current integration uses conservative, dynamic-heavy types to avoid false positives in existing code, the underlying system is capable of high precision when annotations are provided or when guards are explicit.

5. Significance and Claims

The authors position this work as the theoretical foundation for Elixir's new type system.

Theoretical Novelty: They claim to have established the first safe-erasure gradual type system, solving the tension between soundness and the lack of runtime instrumentation in a dynamic language.
Practical Impact: The work provides a blueprint for integrating set-theoretic types into existing dynamic languages with substantial codebases. It demonstrates that high-precision static analysis is possible without compromising the language's dynamic nature or performance.
Limitations: The authors are modest about current limitations:
- Type Narrowing: The system implements a "naive" form of type narrowing; it lacks the granularity of more advanced refinement systems.
- Type Reconstruction: Full ML-style type reconstruction for anonymous functions is not implemented due to computational costs, though the system supports inference based on guards.
- Scope: The current formalization and implementation focus on the core features (guards, strong functions, multi-arity); other aspects like parametric polymorphism and records are treated in companion works or future work.

In summary, the paper presents a rigorous, implemented, and evaluated type system that successfully bridges the gap between Elixir's dynamic runtime and the need for static safety, leveraging the unique properties of the BEAM and Elixir's guard syntax to achieve soundness without erasure penalties.