polytype

A Hindley-Milner polymorphic typing system. Implements type inference via unification.

Usage

[dependencies]
polytype = "1.2"

Provided by polytype are the Type enum and Context struct, and the macros tp! and arrow! which help to concisely create types.

Unification:

let mut ctx = Context::default();

// t1: list(int → α) ; t2: list(β → bool)
let t1 = tp!(list(arrow![tp!(int), tp!(0)]));
let t2 = tp!(list(arrow![tp!(1), tp!(bool)]));
ctx.unify(&t1, &t2).expect("unifies");

let t1 = t1.apply(&ctx);
let t2 = t2.apply(&ctx);
assert_eq!(t1, t2); // list(int → bool)

Apply a type context:

let mut ctx = Context::default();
// assign t0 to int
ctx.unify(&tp!(0), &tp!(int)).expect("unifies");

let t = tp!(list(tp!(0)));
assert_eq!(format!("{}", &t), "list(t0)");
let t = t.apply(&ctx);
assert_eq!(format!("{}", &t), "list(int)");

Independent instantiation:

let mut ctx = Context::default();

let t1 = tp!(list(tp!(3)));
let t2 = tp!(list(tp!(3)));

let t1 = t1.instantiate_indep(&mut ctx);
let t2 = t2.instantiate_indep(&mut ctx);
assert_eq!(format!("{}", &t1), "list(t0)");
assert_eq!(format!("{}", &t2), "list(t1)");

Dependent instantiation:

use std::collections::HashMap;

let mut ctx = Context::default();

let t1 = tp!(list(tp!(3)));
let t2 = tp!(list(tp!(3)));

let mut bindings = HashMap::new();
let t1 = t1.instantiate(&mut ctx, &mut bindings);
let t2 = t2.instantiate(&mut ctx, &mut bindings);
assert_eq!(format!("{}", &t1), "list(t0)");
assert_eq!(format!("{}", &t2), "list(t0)");

See the documentation for more details.