Coalton is an open-source, statically typed functional programming language that is embedded within Common Lisp. Developed primarily by Robert A. Strandh and contributors, Coalton extends Common Lisp with a Hindley–Milner type system, supporting algebraic data types, pattern matching, and higher-order functions while retaining full interoperability with the host Lisp environment. It is designed to bring the benefits of strong typing and modern functional idioms to the Common Lisp ecosystem without abandoning its dynamic flexibility.
1 History
1.1 Origins and Motivation (circa 2018)
Coalton was conceived around 2018 as a response to the perceived gap in the Common Lisp ecosystem: the absence of a practical, strongly typed functional language that could seamlessly interoperate with existing Lisp code. Robert A. Strandh, a long‑time Common Lisp developer and contributor to SBCL, sought to create a language that combined the expressiveness of Haskell‑style type systems with the pragmatic, incremental development style of Common Lisp. The project was initially a research exploration into embedding a typed λ‑calculus within a host Lisp.
1.2 Development and Maturity
After its initial release, Coalton evolved through community feedback and iterative design. Early versions focused on core type inference and basic algebraic data types. By the early 2020s, the language reached a level of stability suitable for experimental use in small to medium‑sized programs. Development continues with regular releases, and the language is considered production‑ready for projects that benefit from static typing alongside Lisp’s metaprogramming capabilities.
1.3 Key Contributors
Robert A. Strandh remains the primary architect and maintainer. Other notable contributors include developers from the Common Lisp community who have added features such as improved pattern‑matching syntax, standard library modules, and integration with the ASDF build system. The project is hosted on GitHub under an MIT license, encouraging open collaboration.
2 Design and Architecture
2.1 Type System
Coalton’s type system is the cornerstone of its design, providing compile‑time safety while preserving the dynamic flexibility of the host Lisp.
2.1.1 Hindley–Milner Type Inference
Coalton employs a Hindley–Milner type inference algorithm (also known as Damas–Milner). This allows the compiler to deduce the types of most expressions without explicit type annotations. The system supports parametric polymorphism (generic types) and let‑polymorphism, enabling functions such as map to operate over lists of any element type. Type inference is performed on entire Coalton programs (or modules) before any Common Lisp code is generated.
2.1.2 Algebraic Data Types
Coalton supports algebraic data types (ADTs), which are composite types built from product types (tuples, records) and sum types (tagged unions). ADTs are declared using a syntax similar to Haskell, with type constructors and optional parameters.
2.1.2.1 Product and Sum Types
Product types represent combinations of values — e.g., a pair (Cons Integer String) or a record (Person name age). Sum types represent alternatives — e.g., (Maybe a) with constructors (Some a) and None. Pattern matching on these types is exhaustive, ensuring that all branches are handled at compile time.
2.2 Integration with Common Lisp
Coalton is not a standalone compiler but a language embedded in Common Lisp. All Coalton code is compiled into Common Lisp forms that can be executed by any conforming Lisp implementation.
2.2.1 Interoperability via Lisp Forms
Any Coalton function or value can be directly called from Common Lisp using its compiled Lisp symbol, and vice versa. For example, a Coalton function (my-function x y) becomes a Lisp function coalt/my-function. Lisp code can pass arbitrary objects into Coalton, but static typing is enforced only within Coalton scopes; dynamic checks are added at the boundary if needed.
2.2.2 Macros and Metaprogramming
Because Coalton is embedded in Common Lisp, it inherits the full power of Lisp macros. Developers can write macros that generate Coalton code, or use Lisp macros to wrap Coalton definitions. This enables domain‑specific languages that mix typed and untyped code seamlessly.
2.3 Compilation Pipeline
2.3.1 From Coalton to Common Lisp
The compilation process proceeds in three stages:
- Parsing: The Coalton source is read by the Lisp reader (using special reader macros) and converted into an abstract syntax tree (AST).
- Type checking and inference: The AST undergoes Hindley–Milner type inference. Any type errors are reported at this stage.
- Code generation: The typed AST is translated into a Common Lisp representation, typically using
defun,lambda, and other Lisp constructs. Algebraic data types are compiled into Lisp structures or vectors with type tags.
2.3.2 Optimization and Runtime Overhead
Coalton’s generated code generally carries minimal overhead. Type information is erased after checking, so runtime operations are largely those of the underlying Lisp. The compiler can perform some optimizations (e.g., unboxing for primitive types) but relies on the host Lisp’s native compiler for further optimization. The primary cost is the compile‑time type inference step.
3 Language Features
3.1 Core Syntax
3.1.1 Function Definition and Application
Functions are defined using a let‑style syntax or top‑level define. For example:
(define (add x y) (+ x y))Application is expressed by juxtaposition: (add 3 4). Currying is supported but not enforced; partial application may require explicit lambda.
3.1.2 Pattern Matching
The match form allows pattern matching on algebraic data types. Patterns can be nested, and the compiler warns on non‑exhaustive patterns. Matching can also destructure product types and bind variables.
(match expr
((Cons x xs) (…))
(Nil (…)))3.2 Modules and Namespaces
Coalton organizes code into packages that mirror Common Lisp packages. Each .lisp file containing Coalton code typically starts with a package declaration. Visibility is controlled by the host Lisp’s package system, allowing selective export of types and functions. Coalton also provides a coalton package that exports all standard language primitives.
3.3 Standard Library
The standard library is relatively small but covers common functional programming needs. It is distributed as part of the Coalton repository.
3.3.1 Collections and Data Structures
Includes lists (with standard operations cons, car, cdr, map, filter, fold), tuples, and a limited set of vector‑like structures. Work on immutable maps and sets is ongoing.
3.3.2 Control Flow Utilities
Provides when, unless, cond, and pattern‑matching combinators. Iteration is expressed via recursion or library functions like map and fold, though explicit recursion is common.
3.4 Error Handling
Coalton does not have a built‑in exception system for typed errors. Instead, it relies on the host Lisp’s condition system for runtime errors. Functions that may fail are typically coded to return (Maybe a) or include an error sentinel. Type‑safe error handling via sum types (e.g., (Either error a)) is idiomatic.
4 Usage and Ecosystem
4.1 Installation and Setup
Coalton is available via Quicklisp and can be loaded with (ql:quickload "coalton"). It requires a Common Lisp implementation that supports the ASDF build system and a recent version of SBCL, CCL, or ABCL. The project provides a quickstart guide and example configurations for Emacs/Slime.
4.2 Example Programs
4.2.1 Hello World
(in-package coalton)
(define (main)
(lisp (write-line "Hello, World!")))Invoke from Lisp: (coalton:coalton main) then (main).
4.2.2 A Simple Algebraic Type
(coalton:coalton)
(data Color Red Green Blue)
(define (complement color)
(match color
(Red Green)
(Green Blue)
(Blue Red)))4.3 Integrating with Existing Lisp Projects
Because Coalton compiles to Lisp symbols in a designated package, integration is straightforward. A Lisp library can export functions that Coalton code calls, and Coalton functions can be exported back. The only requirement is that the Coalton code be compiled after its dependencies are loaded.
4.4 Community and Resources
The community gathers on the Common Lisp subreddit, the Lisp Discord server, and a dedicated GitHub repository (github.com/coalton-lang/coalton). Documentation includes a reference manual, a tutorial, and several blog posts by the author.
5 Comparison with Other Languages
5.1 Typed Racket
Typed Racket is another embedded typed language, but within the Racket ecosystem. Like Coalton, it allows mixing typed and untyped code. However, Typed Racket uses a larger type system (with occurrence typing) and employs a gradual typing approach, whereas Coalton is fully static within its scope. Coalton’s syntax is closer to Lisp than Racket’s.
5.2 Haskell
Haskell is a standalone purely functional language with lazy evaluation and a richer type system (including type classes and higher‑kinded types). Coalton is stricter about laziness (eager evaluation in the Lisp host) and lacks type classes. However, Coalton benefits from seamless integration with Lisp’s imperative features and macros.
5.3 Standard ML
Standard ML (SML) is a strict, statically typed language with a module system. Coalton’s type inference and ADTs are similar, but SML uses a different syntax and does not embed into a dynamic host. Coalton’s module system is weaker but compensates with Lisp’s package system.
5.4 Shen
Shen is a functional language that runs on many platforms (including Common Lisp). It provides a complex type system (including dependent types) and pattern‑matching. Coalton emphasizes simplicity and tight Lisp integration, whereas Shen aims for a more portable, novel type system.
6 Limitations and Future Directions
6.1 Current Known Issues
- No type classes: Generic programming requires explicit polymorphism or Lisp generic functions.
- Limited standard library: Compared to Haskell, the library is minimal.
- Performance: Some Coalton idioms (e.g., persistent data structures) rely on Lisp’s mutable lists, leading to less efficient code than specialized data structures.
- Error messages: Type errors can be cryptic, especially when interacting with untyped Lisp code.
6.2 Planned Enhancements
- Introduction of type classes (or a similar mechanism) for ad‑hoc polymorphism.
- A richer set of immutable data structures (e.g.,
HashMap,Set). - Better integration with Lisp’s type system via type declarations.
- Improved error messages and IDE support.
6.3 Role in the Common Lisp Renaissance
Coalton is part of a broader revival of interest in Common Lisp, often called the “Common Lisp Renaissance.” By providing a modern type system without abandoning the interactive development model, Coalton lowers the barrier for functional programmers to explore Lisp and for Lisp veterans to adopt stronger static guarantees. It serves as a bridge between dynamic and static worlds, contributing to the ongoing reinvigoration of the Common Lisp ecosystem.