A programming language combining affine types, dependent types, row polymorphism, and extensible effects.
AffineScript is designed for safe, efficient systems programming with:
-
Affine Types: Rust-style ownership ensuring memory safety without GC
-
Dependent Types: Types that depend on values (e.g.,
Vec[n, T]) -
Row Polymorphism: Extensible records with compile-time field tracking
-
Extensible Effects: User-defined, tracked side effects
-
WASM Target: Compiles to WebAssembly for portable execution
lower_ident = [a-z][a-zA-Z0-9_]*
upper_ident = [A-Z][a-zA-Z0-9_]*
row_var = ".." lower_identfn let const extern mut own ref type struct enum trait impl effect handle
resume handler match if else while for return break continue in
true false where total module use pub as unsafe assume transmute
forget Nat Int Bool Float String Type Rowint_lit = [0-9]+ | 0x[0-9a-fA-F]+ | 0b[01]+ | 0o[0-7]+
float_lit = [0-9]+ "." [0-9]+ ([eE][+-]?[0-9]+)?
char_lit = "'" (escape | [^'\\]) "'"
string_lit = '"' (escape | [^"\\])* '"'
bool_lit = "true" | "false"
unit_lit = "()"Arithmetic: + - * / %
Comparison: == != < > <= >=
Logical: && || !
Bitwise: & | ^ ~ << >>
Type-level: -> => : /
Special: \ (row restriction)program = [module_decl] {import_decl} {top_level}
top_level = fn_decl | type_decl | trait_decl | impl_block | effect_decl
| const_decl | extern_fn_decl | extern_type_decltype_decl = [visibility] "type" UPPER_IDENT [type_params] "=" type_body
type_params = "[" type_param {"," type_param} "]"
type_param = [quantity] IDENT [":" kind]
kind = "Type" | "Nat" | "Row" | "Effect" | kind "->" kind
type_body = type_expr (* alias *)
| struct_body (* record *)
| enum_body (* variant *)
struct_body = "{" field {"," field} "}"
enum_body = ["|"] variant {"|" variant}
variant = UPPER_IDENT ["(" type_expr {"," type_expr} ")"] [":" type_expr]type_expr = type_atom
| type_expr "->" type_expr ["/" effects] (* function *)
| "(" [quantity] IDENT ":" type_expr ")" "->" type_expr ["/" effects]
| type_expr "where" "(" predicate ")" (* refinement *)
type_atom = PRIM_TYPE | UPPER_IDENT | TYPE_VAR
| UPPER_IDENT "[" type_arg {"," type_arg} "]"
| "own" type_atom | "ref" type_atom | "mut" type_atom
| "{" row_fields "}" (* record *)
| "(" type_expr {"," type_expr} ")" (* tuple *)
row_fields = field_type {"," field_type} ["," row_var]
| row_var
effects = effect_term {"+" effect_term}
effect_term = UPPER_IDENT ["[" type_arg {"," type_arg} "]"]fn_decl = [visibility] ["total"] "fn" LOWER_IDENT
[type_params] "(" [param_list] ")"
["->" type_expr] ["/" effects]
[where_clause] fn_body
param_list = param {"," param}
param = [quantity] [ownership] IDENT ":" type_expr
ownership = "own" | "ref" | "mut"
where_clause = "where" constraint {"," constraint}
constraint = predicate | TYPE_VAR ":" trait_bounds
fn_body = block | "=" exprexpr = let_expr | if_expr | match_expr | fn_expr
| handle_expr | return_expr | binary_expr
let_expr = "let" ["mut"] pattern [":" type_expr] "=" expr ["in" expr]
if_expr = "if" expr block ["else" (if_expr | block)]
match_expr = "match" expr "{" {match_arm} "}"
match_arm = pattern ["if" expr] "=>" expr [","]
fn_expr = "|" [param_list] "|" expr
| "fn" "(" [param_list] ")" fn_body
handle_expr = "handle" expr "with" "{" {handler_arm} "}"
handler_arm = "return" pattern "=>" expr [","]
| LOWER_IDENT "(" [pattern {"," pattern}] ")" "=>" expr [","]
block = "{" {statement} [expr] "}"
binary_expr = unary_expr {BINARY_OP unary_expr}
unary_expr = [UNARY_OP] postfix_expr
postfix_expr = primary_expr {postfix}
postfix = "." IDENT | "." INT | "[" expr "]" | "(" [args] ")"
| "::" UPPER_IDENT | "\\" IDENT
primary_expr = literal | IDENT
| "(" expr ")" | "(" expr {"," expr} ")"
| "[" [expr {"," expr}] "]"
| "{" [field_init {"," field_init}] [".." expr] "}"
| "resume" "(" [expr] ")"pattern = "_" (* wildcard *)
| IDENT (* binding *)
| literal (* literal match *)
| UPPER_IDENT ["(" pattern {"," pattern} ")"]
| "(" pattern {"," pattern} ")" (* tuple *)
| "{" field_pat {"," field_pat} [".." ] "}"
| pattern "|" pattern (* or-pattern *)
| IDENT "@" pattern (* binding with pattern *)effect_decl = [visibility] "effect" UPPER_IDENT [type_params]
"{" {effect_op} "}"
effect_op = "fn" LOWER_IDENT "(" [param_list] ")" ["->" type_expr] ";"trait_decl = [visibility] "trait" UPPER_IDENT [type_params]
[":" trait_bounds] "{" {trait_item} "}"
trait_bounds = UPPER_IDENT {"+" UPPER_IDENT}
trait_item = fn_sig ";" | fn_decl | assoc_type
impl_block = "impl" [type_params] [trait_ref "for"] type_expr
[where_clause] "{" {impl_item} "}"const_decl = [visibility] "const" LOWER_IDENT ":" type_expr "=" expr ";"A top-level const binding compiles to an immutable WebAssembly global. The
initializer expression must reduce to a Wasm constant expression (a literal
or a constant arithmetic combination thereof); non-constant initializers are
not yet supported by the linear-memory backend.
Both function names and const names are registered in the same codegen name environment so that later top-level declarations may refer to either kind of binding by name. See §8 (Codegen Module Environment) for the encoding and the current single-pass population order.
extern_fn_decl = [visibility] "extern" "fn" LOWER_IDENT
[type_params] "(" [param_list] ")"
["->" type_expr] ["/" effects] ";"
extern_type_decl = [visibility] "extern" "type" UPPER_IDENT
[type_params] ";"extern fn declares a function whose implementation is supplied by the host
environment at link time. The linear-memory WebAssembly backend lowers each
extern fn to an (import "env" "<name>" (func …)) entry; the import slot
is registered in the codegen name environment so call sites resolve through
call k exactly as for locally-defined functions (see §8).
extern type declares an opaque, host-provided type. It carries no runtime
representation and generates no Wasm artifact; the typechecker treats the
name as a nominal opaque type whose internal structure is unknown.
Both forms are terminated by ; and carry no body.
Γ ⊢ e : τ / ε Expression e has type τ with effects ε
Γ ⊢ τ : κ Type τ has kind κ
Γ ⊢ P true Predicate P is satisfied| Quantity | Meaning | Usage |
|---|---|---|
|
Erased |
Compile-time only, no runtime cost |
|
Linear |
Must use exactly once |
|
Unrestricted |
Use any number of times |
Algebra:
0 + q = q 0 * q = 0
1 + 1 = ω 1 * q = q
ω + ω = ω ω * ω = ω| Modifier | Meaning |
|---|---|
|
Owned value - caller transfers ownership |
|
Immutable borrow - cannot modify |
|
Mutable borrow - exclusive access |
Rules:
-
Owned values are consumed on use
-
Multiple
refborrows allowed simultaneously -
Only one
mutborrow at a time -
Borrows cannot outlive owner
Functions declare effects after /:
fn pure_fn(x: Int) -> Int / Pure { x + 1 }
fn io_fn() -> () / IO { println("hello") }
fn fallible() -> Int / Exn[Error] { throw(Error::new()) }
fn combined() -> () / IO + Exn[Error] { ... }Partial by Default:
-
Functions are partial by default (may not terminate)
-
totalfunctions must provably terminate
Types can depend on values:
type Vec[n: Nat, T: Type] =
| Nil : Vec[0, T]
| Cons(T, Vec[n, T]) : Vec[n + 1, T]
// Can only call on non-empty vectors
fn head[n: Nat, T](v: Vec[n + 1, T]) -> TConstrain types with predicates:
type PosInt = Int where (self > 0)
fn safeDiv(a: Int, b: Int where (b != 0)) -> IntExtensible records with row variables:
// Works on any record with 'name' field
fn greet[..r](person: {name: String, ..r}) -> String {
"Hello, " ++ person.name
}
// Add fields
fn addAge[..r](rec: {..r}) -> {age: Int, ..r} {
{age: 0, ..rec}
}
// Remove fields
fn removeName[..r](rec: {name: String, ..r}) -> {..r} {
rec \ name
}Γ, x :q τ₁ ⊢ e : τ₂ / ε
────────────────────────────────
Γ ⊢ fn(x: τ₁) => e : τ₁ -> τ₂ / εΓ ⊢ f : τ₁ -> τ₂ / ε₁ Γ ⊢ e : τ₁ / ε₂
──────────────────────────────────────────
Γ ⊢ f(e) : τ₂ / ε₁ + ε₂Γ ⊢ e : {ℓ: τ, ..r} / ε
────────────────────────
Γ ⊢ e.ℓ : τ / ε
Γ ⊢ e : {..r} / ε
───────────────────────────────
Γ ⊢ {ℓ: v, ..e} : {ℓ: τ, ..r} / εtype Nat // Natural numbers (0, 1, 2, ...)
type Int // 64-bit signed integers
type Float // 64-bit floats
type Bool // true | false
type String // UTF-8 string
type Char // Unicode scalar value
type Never // Uninhabited typeeffect IO {
fn print(s: String);
fn println(s: String);
fn readLine() -> String;
}
effect Exn[E] {
fn throw(err: E) -> Never;
}
effect State[S] {
fn get() -> S;
fn put(s: S);
}effect IO {
fn println(s: String);
}
fn main() -> () / IO {
println("Hello, AffineScript!")
}type Vec[n: Nat, T: Type] =
| Nil : Vec[0, T]
| Cons(head: T, tail: Vec[n, T]) : Vec[n + 1, T]
total fn head[n: Nat, T](v: Vec[n + 1, T]) -> T / Pure {
match v { Cons(h, _) => h }
}
total fn append[n: Nat, m: Nat, T](
a: Vec[n, T], b: Vec[m, T]
) -> Vec[n + m, T] / Pure {
match a {
Nil => b,
Cons(h, t) => Cons(h, append(t, b))
}
}type File = own { fd: Int }
fn open(path: ref String) -> Result[own File, IOError] / IO
fn read(file: ref File) -> Result[String, IOError] / IO
fn close(file: own File) -> Result[(), IOError] / IO
fn withFile[T](
path: ref String,
action: (ref File) -> Result[T, IOError]
) -> Result[T, IOError] / IO + Exn[IOError] {
let file = open(path)?;
let result = action(ref file);
close(file)?;
result
}fn greet[..r](person: {name: String, ..r}) -> String / Pure {
"Hello, " ++ person.name
}
fn addField[..r](rec: {..r}, age: Int) -> {age: Int, ..r} / Pure {
{age: age, ..rec}
}
fn main() -> () / Pure {
let alice = {name: "Alice", role: "Engineer"};
let bob = {name: "Bob", dept: "Sales"};
// Both work despite different shapes
greet(alice); // "Hello, Alice"
greet(bob); // "Hello, Bob"
}effect State[S] {
fn get() -> S;
fn put(s: S);
}
fn counter() -> Int / State[Int] {
let n = State.get();
State.put(n + 1);
n
}
fn runState[S, T](init: S, comp: () -> T / State[S]) -> (T, S) / Pure {
handle comp() with {
return x => (x, init),
get() => resume(init),
put(s) => resume(())
}
}| AffineScript | WASM |
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
This section describes how the WebAssembly code generator (lib/codegen.ml)
builds its name environment. It is implementation documentation aimed at
contributors; the language semantics are fully specified in §2–4.
The codegen context maintains a single association list
func_indices : (string * int) listthat maps every top-level name visible at later declaration sites to an integer key. Two distinct kinds of binding share this table:
| Source declaration | Key value | Meaning |
|---|---|---|
|
|
WebAssembly function index (imports + defined functions, combined) |
|
|
Negative sentinel reserved for constants |
Sign-based partitioning is deliberate: k ≥ 0 decodes directly as a Wasm
funcidx, and k < 0 recovers the global index as g = -(k + 1). A
single integer per name keeps the lookup uniform across both kinds of binding.
Population. Top-level declarations are visited in source order by
gen_decl, which is folded over prog.prog_decls from generate_module.
The relevant cases are:
-
TopFn fdwithfd.fd_body <> FnExtern— picks the next Wasm function index (import_func_count ctx + List.length ctx.funcs), registers(fd.fd_name.name, func_idx)infunc_indicesbefore generating the body so the body may recursively refer to its own name, then appends the emitted function toctx.funcs. -
TopFn fdwithfd.fd_body = FnExtern— emits a Wasm import (module"env", namefd.fd_name.name) and registers(fd.fd_name.name, import_func_idx)infunc_indices, whereimport_func_idxis the number of imports before adding this one. No function body is generated. See §8.2. -
TopConst tc— generates the global initializer, appends the global toctx.globals, then registers(tc.tc_name.name, -(global_idx + 1))infunc_indices.
Because population is strictly single-pass and in declaration order, forward references (to either functions or constants declared later in the file) are not supported by the current backend.
Call-site lookup. The ExprApp (ExprVar id, _) branch of gen_expr
consults func_indices to translate a direct call into a Wasm call k
instruction. Decoding the negative sentinel back to a global.get —
needed to make a bare const identifier usable inside another top-level
declaration’s body — is tracked as a known gap in issue #73. The encoding
documented in this section is the data layout the fix relies on; the
call-site decode path will land alongside that fix.
An extern fn name(…) → Ret; declaration produces a TopFn with
fd_body = FnExtern. Codegen lowers it to a Wasm import:
(import "env" "<name>" (func (param …) (result …)))The resulting import function index is positive (it counts among the
combined "imports + defined functions" view used by every other call
site), so the name is registered in func_indices with k ≥ 0 and call
sites resolve through call k indistinguishably from a locally-defined
function. The Wasm module name is currently hard-coded to "env",
matching the convention adopted by the Node-CJS host shim.
An extern type Name; declaration produces a TopType with
td_body = TyExtern. It generates no Wasm artifact — opaque types are
purely a typechecker concern — and the codegen TopType TyExtern case
returns the unchanged context.