Forge is a statically typed functional language with type inference, polymorphism, pattern matching, and (via the standard prelude) traits/typeclasses.
The reference implementation in this repository is written in OCaml and includes both:
- an interpreter (evaluate programs directly), and
- an ahead-of-time compiler that lowers programs to Min IR, then LLVM IR, then assembly, and links a native executable with Clang using a small C runtime (
runtime/ls_runtime.c).
An experimental TypeScript implementation is maintained in a separate repository.
Run Forge without a local OCaml/opam/clang toolchain.
Build the image from the repository root:
docker build -t forge:local .Rebuild after changing sources (same command). For a clean rebuild that ignores the layer cache:
docker build --no-cache -t forge:local .Run a program that was copied into the image at build time (programs/ is available as /opt/forge/programs/):
docker run --rm forge:local run /opt/forge/programs/<file>.forgeRun your working tree (no rebuild needed; mount the repo and use /work):
docker run --rm -v "$PWD":/work -w /work forge:local run /work/programs/<file>.forgeOther entrypoints: docker run --rm forge:local help, docker run --rm -it forge:local repl, and compile/run native binaries as described under Installation (subsection Docker Quick Start).
- Docker (quick start)
- Overview
- Standard prelude
- Language Features
- Examples
- Installation
- Usage
- Native compilation
- Editor support: LSP hover
- Testing
- Language Semantics
- Documentation
- Project Structure
Forge is a statically-typed functional programming language inspired by OCaml and Haskell. It features:
- Static type system with Hindley-Milner style type inference
- Polymorphic types with type parameters
- Algebraic data types with pattern matching
- First-class functions with closures
- Recursive types for defining lists, trees, and other recursive structures
- Record types with field update syntax
- Type annotations for clarity and documentation
- Comprehensive built-in operators usable as first-class values
- Native compiler (LLVM IR + Clang) alongside the interpreter
- Traits / typeclasses (
trait/inter,impl … for …, dictionary passing in the compiler) macro_rules!token-tree macros with fragment matching and repetition (*,+)
By default, user programs are combined with prelude/prelude.forge (some tools, such as forge_hover, can opt out of prepending for a raw buffer):
- Interpreter and
compile_forge: the prelude source is prepended to your file (skipping self-prepend when you are editing the prelude itself). Resolution searchesprelude/prelude.forgefrom the current directory, the executable’s directory, and a few parent layouts—seesrc/prelude.ml. - REPL: the prelude is loaded once at startup into the environment (not re-prepended per line).
The prelude defines the canonical List/Option types, standard traits (Functor, Applicative, Monad, Foldable, …), and default Show / Eq / Ord instances for built-in types. You can still define your own traits using either trait … where (prelude style) or inter … (see programs/haskell_style_typeclasses.forge).
- Type Inference: Automatic type deduction using constraint-based type inference
- Polymorphism: Generic types with type parameters (
a,b, … — syntax<a>on type constructors) - Type Annotations: Optional type annotations for clarity
- Algebraic Data Types: Sum types with constructors
- Recursive Types: Self-referential type definitions
- Type Aliases: Named type definitions
- Records: Named rows with
{ field: ty, ... }, field accessr.field, update{ base with field = expr }
Basic Types: int, float, bool, string, char, unit
Composite Types: Functions (a -> b), lists ([a] or List<a> once the prelude is loaded), tuples ((a, b, c)), records
Forge’s traits are the surface syntax for typeclasses: named bundles of operations (methods) that types can implement. The compiler passes dictionaries at call sites so polymorphic code can use the right implementation for each type. The standard prelude defines the usual hierarchy (Functor, Applicative, Monad, Show, Eq, Ord, Semigroup, Monoid, …) and instances for built-ins; your own programs can add new traits and instances with trait (or inter) and impl.
A trait declaration introduces a class name, optional type parameters, optional supertrait constraints, and a body of method signatures (and optional default definitions):
- Shape:
trait Name<…> requires … where … end - Type parameters can be simple (
<a>,<a, b>) or higher-kinded (<f<_>>) for type constructors, as intrait Functor<f<_>> where …in the prelude. requireslists traits that must already be implemented for the same type parameters (e.g.trait Monoid<a> requires Semigroup<a> where …). That corresponds to a superclass constraint in Haskell-style typeclasses.- Inside
where … end, each method is introduced withvaland its type (val show : a -> String). You can add default implementations withletin the trait body so instances may omit them unless they override.
The keyword inter is an alternative, brace-oriented spelling for the same concept (see programs/haskell_style_typeclasses.forge and the small programs/typeclass_show.forge). Prefer trait … where … end in new code if you want to match the prelude style.
Source order: every trait must be declared above any impl that uses it in the same compilation unit. The parser/condenser resolves impl against traits seen earlier in the file (and, for the REPL, against traits from the prelude that were loaded at startup).
An instance is written impl Trait for Type where … end:
Typeis the implementing type: monomorphic (Int,Bool,String, …), a type constructor applied to parameters (List<a>,Option<a>), etc., as allowed by the typechecker.- Inside
where … end, you supply aletbinding for eachvalrequired by the trait (unless the trait gave a defaultletyou are happy to inherit). Operator methods use the same syntax as ordinary functions:let (++) x y = …. - Instances may be parameterized: for example,
impl Semigroup for List<a>in the prelude implements the trait for all element typesaat once.
Illustrative fragments (same ideas as prelude/prelude.forge):
trait Semigroup<a> where
val mappend : a -> a -> a
val (++) : a -> a -> a
end
trait Monoid<a> requires Semigroup<a> where
val empty : a
end
impl Semigroup for String where
let mappend x y = str_concat x y
let (++) x y = mappend x y
end
impl Monoid for String where
let empty = ""
end
- Prelude:
prelude/prelude.forgeis the canonical reference for trait definitions and instances. - Smaller demos:
programs/typeclass_show.forge,programs/functor_list.forge. - Native vs interpreter: some typeclass-heavy programs are still smoother in the interpreter or REPL than in the native compiler; see comments in
programs/haskell_style_typeclasses.forgeandprograms/typeclass_functor_native_list.forge.
Forge supports Rust-style declarative macros that expand before typechecking and evaluation/compilation.
macro_rules! add where
($a:expr, $b:expr) => $a + $b
end
let x = add!(1, 2)
let y = add![3, 4]
let z = add!{5, 6}
- Macros are declared with
macro_rules! name where ... end(same delimiters asmod/implbodies). - A macro can have multiple arms; expansion uses the first arm whose matcher fits.
- Invocation delimiters
(),[], and{}are all supported.
Matcher metavariables can be typed with:
exprpatty/typeidentitemttliteral/litpathblock
Example:
macro_rules! id1 where
($x:ident) => $x
end
macro_rules! use_path where
($p:path) => $p
end
macro_rules! show_ty where
($t:ty) => "ok"
end
Repetitions follow Rust-like syntax:
$( ... )*for zero or more$( ... )+for one or more- optional separator:
$( ... ),*,$( ... );+, etc.
Example passthrough:
macro_rules! passthrough where
($($x:expr),*) => vec!($($x),*)
end
Compatibility behavior currently implemented:
- If a repeated capture (for example
$xfrom($($x:expr),*)) is used directly (not inside a transcriber repetition), it expands to a list literal.- Example:
($($x:expr),*) => $xexpands to[ ... ].
- Example:
Forge currently includes these built-in macros:
count_args!(...)-> integer count of comma-separated argumentsvec!(...)-> list literalstringify!(...)-> string representation of argument expression ASTsconcat!(...)/concat_str!(...)-> concatenates string literal arguments
Example:
macro_rules! debug_expr where
($e:expr) => concat!("DBG(", stringify!($e), ")")
end
- Macros can be declared at top level, including inside modules.
macro_rules!definitions are not supported inside expression blocks.- Current macro expansion target is expressions (not arbitrary item generation).
- Literals: Integers, floats, booleans, strings, characters, unit
() - Variables: Named bindings
- Functions: Lambda expressions with
fn x -> expr - Function Application:
f x y - Let Bindings:
let x = expr in body - Recursive Functions:
let rec fact n = ... - Conditionals:
if condition then expr1 else expr2 - Pattern Matching:
case expr do | pattern -> result - Lists:
[1, 2, 3]or1 :: 2 :: 3 :: [] - List Ranges:
[1...10]or[1 ... 10](spaces optional) - List Comprehensions:
[x * 2 | x => [1...5], x > 2] - Tuples/Vectors:
(1, "hello", true) - Code Blocks:
{ expr1; expr2; result } - Macro Invocations:
name!(...),name![...],name!{...}
All operators can be used as first-class values by wrapping in parentheses: (+), (*), (::), etc.
Arithmetic: +, -, *, /, %
Strings: ^ (concatenation)
Comparison: ==, !=, <>, <, >, <=, >=
Logical: &&, ||, and not (prefix)
List: :: (cons)
Supports comprehensive pattern matching including:
- Literal patterns:
42,"hello",true - Variable binding:
x,name - Wildcard:
_ - Cons patterns:
h :: t - Tuple patterns:
(x, y, z) - Constructor patterns:
Just x,Left y - Record patterns:
{ name: "Alice" },{ x, y } - Nested patterns:
(x, y :: rest)
I/O:
print : string -> unit- print without newlineprintln : string -> unit- print with newline
Type Conversions:
int_to_str : int -> stringint_to_float : int -> floatfloat_to_int : float -> intstring_to_list : string -> [char]
String Operations:
str_length : string -> int- length of stringstr_concat : string -> string -> string- concatenate two stringsstr_slice : string -> int -> int -> string- substring (start, length)
List Operations:
list_length : [a] -> int- length of listlist_head : [a] -> a- first element (fails on empty)list_tail : [a] -> [a]- all but first elementlist_nth : [a] -> int -> a- nth element (0-indexed)
Tuple Operations:
tuple_fst : (a, b) -> a- first element of pairtuple_snd : (a, b) -> b- second element of pair
Higher-Order Functions:
map : (a -> b) -> [a] -> [b]filter : (a -> bool) -> [a] -> [a]reduce_left : (a -> b -> a) -> a -> [b] -> areduce_right : (a -> b -> b) -> [a] -> b -> bnot : bool -> bool
The snippets below are illustrative; runnable examples live under programs/, e.g. programs/minimal.forge, programs/builtins_test.forge, programs/record_update.forge, programs/red_black_tree_example.forge, and the typeclass demos linked in Typeclasses (traits).
Additional macro-focused examples:
programs/test.forgetest/macro_system_tests.ml(language-level macro coverage)
(* Integers *)
42
-17
(* Floats *)
3.14
-2.5
int_to_float 2
float_to_int 3.9
(* Booleans *)
true
false
(* Strings *)
"Hello, world!"
(* Characters *)
'a'
'Z'
(* Unit *)
()(* Simple binding *)
let x = 42 in x + 1
(* Result: 43 *)
(* Multiple bindings *)
let x = 5 in
let y = 10 in
x + y
(* Result: 15 *)
(* Type annotations *)
let (x: int) = 42 in x(* Lambda function *)
fn x -> x + 1
(* Named function *)
let add = fn x -> fn y -> x + y in
add 3 4
(* Result: 7 *)
(* Pattern matching in parameters *)
let first = fn (x, y) -> x in
first (5, 10)
(* Result: 5 *)
(* With type annotations *)
let increment = fn (x: int) : int -> x + 1 in
increment 41
(* Result: 42 *)
(* Recursive functions *)
let rec factorial = fn n ->
if n == 0 then 1
else n * factorial (n - 1)
in
factorial 5
(* Result: 120 *)(* Use operators as functions *)
let add = (+) in
add 3 4
(* Result: 7 *)
(* Partial application *)
let add5 = (+) 5 in
add5 10
(* Result: 15 *)
(* Pass to higher-order functions *)
map ((*) 2) [1, 2, 3]
(* Custom operator definitions *)
let (++) = fn a -> fn b -> a + b in
(++) 10 20
(* Result: 30 *)macro_rules! choose where
() => 0;
($x:expr) => $x
end
let a = choose!()
let b = choose!{42}
macro_rules! collect where
($($x:expr),*) => $x
end
let xs = collect!(1, 2, 3, 4)
let n = list_length xs
(* n == 4 *)
macro_rules! collect_and_count where
($($x:expr),*) => count_args!($($x),*)
end
let n0 = collect_and_count!()
let n3 = collect_and_count!(1, 2, 3)
(* Empty list *)
[]
(* List literals *)
[1, 2, 3, 4, 5]
(* Cons operator *)
1 :: 2 :: 3 :: []
(* Result: [1, 2, 3] *)
(* List ranges *)
[1...10]
(* Result: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] *)
(* List comprehensions *)
[x * x | x => [1...5]]
(* Result: [1, 4, 9, 16, 25] *)
(* With filter *)
[x | x => [1...10], x % 2 == 0]
(* Result: [2, 4, 6, 8, 10] *)(* Pairs *)
(1, 2)
(* Triples *)
(1, "hello", true)
(* Pattern matching tuples *)
let (x, y) = (5, 10) in x + y
(* Result: 15 *)(* if / then / else (both branches must match in type) *)
if 3 < 5 then "yes" else "no"
(* Short-circuiting logical operators *)
true && false
true || false
not true
(* Combining comparisons *)
let n = 7 in
if n > 0 && n % 2 == 0 then "positive even" else "other"(* Match on lists *)
let length = fn lst ->
case lst do
| [] -> 0
| h :: t -> 1 + length t
in
length [1, 2, 3]
(* Result: 3 *)
(* Match on integers *)
let sign = fn n ->
case n do
| 0 -> "zero"
| n -> if n > 0 then "positive" else "negative"
in
sign (-5)
(* Result: "negative" *)
(* Complex patterns *)
let get_second = fn lst ->
case lst do
| [] -> 0
| x :: [] -> 0
| x :: y :: rest -> y
in
get_second [1, 2, 3]
(* Result: 2 *)
(* Record patterns (fields can be literals or binders) *)
let person = { name: "John", age: 30, city: "New York" }
let tag = case person do
| { name: "Alex" } -> 1
| { name: "John" } -> 2
| _ -> 3
(* tag == 2 *)(* Record type and literals *)
type Point = { x: int, y: int }
let p1 : Point = { x: 10, y: 20 }
(* Field access *)
let sum_xy = p1.x + p1.y
(* Functional update (immutable: creates a new record) *)
let p2 = { p1 with x = 100 }
let p3 = { p2 with y = 50 }
let p4 = { p1 with x = 5, y = 15 }
(* Matching on record fields *)
type User = { login: string, active: bool }
let status = fn u ->
case u do
| { active: true } -> u.login ^ " is active"
| { login: name } -> name ^ " is inactive"
| _ -> "unknown"(* Map *)
let rec map = fn f -> fn lst ->
case lst do
| [] -> []
| h :: t -> f h :: map f t
in
map (fn x -> x * x) [1, 2, 3, 4, 5]
(* Result: [1, 4, 9, 16, 25] *)
(* Filter *)
let rec filter = fn pred -> fn lst ->
case lst do
| [] -> []
| h :: t ->
if pred h then h :: filter pred t
else filter pred t
in
filter (fn x -> x % 2 == 0) [1, 2, 3, 4, 5, 6]
(* Result: [2, 4, 6] *)
(* Fold/Reduce *)
let rec fold_left = fn op -> fn acc -> fn lst ->
case lst do
| [] -> acc
| h :: t -> fold_left op (op acc h) t
in
fold_left (+) 0 [1, 2, 3, 4, 5]
(* Result: 15 *)The standard environment includes the helpers listed under Built-in Functions. You can call them directly instead of re-implementing map, folds, and string helpers:
let () = print "no newline"
let () = println "with newline"
let () = println (int_to_str (str_length "hello"))
let () = println (str_concat "hello" " world")
let () = println (str_slice "hello" 1 3)
let () = println (int_to_str 99)
let () = println (int_to_str (list_length [1, 2, 3]))
let () = println (int_to_str (list_head [1, 2, 3]))
let () = println (int_to_str (list_head (list_tail [1, 2, 3])))
let () = println (int_to_str (list_nth [10, 20, 30] 2))
let () = println (int_to_str (tuple_fst (5, 10)))
let () = println (int_to_str (tuple_snd (5, 10)))
let squares = map (fn x -> x * x) [1, 2, 3, 4]
let evens = filter (fn x -> x % 2 == 0) [1, 2, 3, 4, 5, 6]
let sum = reduce_left (+) 0 [1, 2, 3, 4, 5]
let product = reduce_right (*) [1, 2, 3, 4] 1
let chars = string_to_list "hey"
let m = float_to_int 3.7
let x = int_to_float 42(* Type aliases *)
type IntPair = (int, int)
(* Sum types *)
type Option<a> =
| None
| Some of a
type Either<a, b> =
| Left of a
| Right of b
(* Recursive types *)
type rec List<a> =
| []
| (::) of (a, List<a>)
type rec Tree<a> =
| Leaf
| Node of (a, Tree<a>, Tree<a>)
(* Using custom types *)
let rec tree_size = fn t ->
case t do
| Leaf -> 0
| Node (value, left, right) ->
1 + tree_size left + tree_size right
in
tree_size (Node (5, Leaf, Node (3, Leaf, Leaf)))
(* Result: 2 *)(* Identity function *)
let id = fn x -> x
(* Type: a -> a *)
(* Composition *)
let compose = fn f -> fn g -> fn x -> f (g x)
(* Type: (b -> c) -> (a -> b) -> a -> c *)
(* Map for any type *)
let rec map = fn f -> fn lst ->
case lst do
| [] -> []
| h :: t -> f h :: map f t
(* Type: (a -> b) -> [a] -> [b] *){
let x = 5;
let y = 10;
let z = x + y;
z * 2
}
(* Result: 30 *)(* Variable annotations *)
let (x: int) = 42 in x
(* Function parameter annotations *)
let add = fn (x: int) -> fn (y: int) -> x + y in
add 3 4
(* Return type annotations *)
let increment = fn (x: int) : int -> x + 1 in
increment 5
(* Full function type annotation *)
let apply = fn (f: int -> int) -> fn (x: int) : int -> f x in
apply (fn x -> x * 2) 21
(* Result: 42 *)
(* Type variable in an annotation: a, b, … *)
let poly_id = fn (x: a) -> x
(* Type: a -> a *)If you want to try Forge without installing opam, ocaml, or clang locally, use Docker.
Build the image from this repository:
docker build -t forge:local .Run the bundled minimal program:
docker run --rm forge:local run /opt/forge/programs/minimal.forgeExpected output:
3
Start a REPL:
docker run --rm -it forge:local replRun a local source file (from your current host directory):
docker run --rm -it -v "$PWD":/work -w /work forge:local run /work/hello.forgeNative compile a local file:
docker run --rm -it -v "$PWD":/work -w /work forge:local compile /work/hello.forge
docker run --rm -v "$PWD":/work -w /work forge:local /work/a.outforge compile in the container always writes the executable to /work/a.out
(on your host this is ./a.out in the mounted directory).
If you publish this image (for example ghcr.io/<owner>/forge:latest), replace forge:local with that image tag in the commands above.
Forge needs OCaml, Dune, OPAM, and Clang.
macOS (Homebrew):
brew install opam
brew install llvm clang
opam init -a --disable-sandboxing
eval "$(opam env)"
opam switch create 5.1.1
opam install duneUbuntu / Debian:
sudo apt update
sudo apt install -y opam m4 pkg-config libgmp-dev clang
opam init -a
eval "$(opam env)"
opam switch create 5.1.1
opam install duneVerify:
ocamlc -version
dune --version
clang --versiongit clone https://github.com/LambdaAK/Forge
cd Forge
makeThis builds the interpreter, REPL, compiler (compile_forge), and other tools under bin/.
dune exec ./bin/interpreter.exe programs/minimal.forgeExpected output:
3
Start an interactive session:
make replOptionally preload a file after the prelude:
make repl FILE=programs/simple_test.forgeIn the REPL, you can type expressions and see their types and evaluated results immediately.
Execute a .forge file containing Forge code (from the repository root, with the prelude available as usual):
dune exec ./bin/interpreter.exe <filename>Example:
dune exec ./bin/interpreter.exe programs/minimal.forgeSource files use .forge.
The compiler parses and typechecks a Forge source file, lowers it to Min IR (.mir), emits LLVM IR (.ll), runs Clang to produce assembly (.s) and a linked executable. The C runtime in runtime/ls_runtime.c provides memory and runtime glue for the generated code.
From the repository root:
make compile-forge FILE=programs/minimal.forge
./a.outOptional output name:
make compile-forge FILE=programs/minimal.forge OUT=./my_program
./my_programEquivalent direct invocation:
dune exec ./bin/compile_forge.exe programs/minimal.forge ./my_programFinding the runtime: compilation searches upward from the current directory for runtime/ls_runtime.c. If you run the compiler from elsewhere, set FORGE_ROOT to the checkout path.
Inspecting IR without linking:
make dump-ir FILE=programs/minimal.forgeAdditional compiler integration tests and fixtures live in test/compiler_cases/.
bin/forge_hover.ml builds forge_hover, a small stdin/stdout tool meant to be driven by an LSP server for hover/type-at-point:
dune exec ./bin/forge_hover.exe path/to/file.forge 1 10 4 < path/to/file.forgeArguments: path, prelude (1/true to prepend the standard prelude, 0/false for raw buffer only), zero-based line, zero-based character. On success it prints the type string to stdout; on failure it prints ERROR: … and exits with a non-zero status. Query logic lives in src/hover_query.ml.
The project ships two main test entry points (the exact counts change as tests are added):
- Interpreter / typechecker / evaluator coverage — OUnit suite:
make suite
- Compiler end-to-end cases (compile, run native executable, compare output):
make compiler-suite
To run everything Dune knows about (when the tree builds cleanly):
dune testThat includes compiler_tests (see test/compiler_cases/) and hover_ident_tests (hover/type-at-point queries).
To run tests with coverage analysis:
make bisectThis will generate a coverage report showing which parts of the codebase are tested.
test/test.ml— large OUnit suite for the interpreter pipeline: type checking, inference, evaluation, pattern matching, ADTs, higher-order functions, builtins, and edge cases.test/macro_system_tests.ml—macro_rules!matching/expansion and builtin macro behavior.test/compiler_tests.ml+test/compiler_cases/— compile withcompile_forge, run the binary, compare stdout.test/hover_ident_tests.ml— hover / identifier typing viaHover_query.
The formal semantics live in LaTeX as documentation/Forge.tex. Build a PDF locally with pdflatex documentation/Forge.tex (or your usual LaTeX workflow) if you want a printable copy.
Note: The formal write-up may lag recent surface syntax (traits, prelude, macro system, compiler details).
Generate OCaml documentation for the codebase:
make docOpen the generated documentation in your browser:
make opendocThe repository includes a static website/docs app under website/, built with React + TypeScript + Vite (no backend).
npm --prefix website install
npm --prefix website run devThen open the local URL printed by Vite (usually http://localhost:5173).
npm --prefix website run build
npm --prefix website run previewnetlify.toml is configured to:
- run
npm ci --prefix website && npm --prefix website run build - publish
website/dist - rewrite SPA routes to
index.html - use Node.js
20
If you deploy from the Netlify control panel:
- Build command:
npm ci --prefix website && npm --prefix website run build - Publish directory:
website/dist - Base directory: leave empty (repo root)
Forge/ # repository root (language: Forge)
├── bin/ # interpreter, repl, compile_forge, dump_min_ir, forge_hover, …
├── src/ # lexer, parser, typecheck, interpreter, compiler pipeline
│ ├── compile_pipeline.ml # native driver (prelude, typecheck, IR, Clang)
│ ├── min_ir.ml, lower_min_ir.ml, llvm_emit.ml
│ ├── hover_query.ml # type-at-point for forge_hover / IDE integration
│ └── ...
├── prelude/ # prelude source (prepended or REPL-loaded)
├── runtime/ # ls_runtime.c (linked into native executables)
├── test/ # test.ml, compiler_tests, hover_ident_tests, compiler_cases/
├── programs/ # example .forge programs
├── documentation/ # Forge.tex (formal semantics)
└── website/ # React + TypeScript + Vite website/docs app