polytype/types.rs
1use itertools::Itertools;
2use std::collections::{HashMap, VecDeque};
3use std::fmt;
4
5use crate::{Context, Name};
6
7/// Represents a [type variable][1] (an unknown type).
8///
9/// [1]: https://en.wikipedia.org/wiki/Hindley–Milner_type_system#Free_type_variables
10pub type Variable = usize;
11
12/// Represents [polytypes][1] (uninstantiated, universally quantified types).
13///
14/// The primary ways of creating a `TypeScheme` are with the [`ptp!`] macro or
15/// with [`Type::generalize`].
16///
17/// [1]: https://en.wikipedia.org/wiki/Hindley–Milner_type_system#Polytype
18/// [`ptp!`]: macro.ptp.html
19/// [`Type::generalize`]: enum.Type.html#method.generalize
20#[derive(Debug, Clone, Hash, PartialEq, Eq)]
21pub enum TypeScheme<N: Name = &'static str> {
22 /// Non-polymorphic types (e.g. `α → β`, `int → bool`)
23 Monotype(Type<N>),
24 /// Polymorphic types (e.g. `∀α. α → α`, `∀α. ∀β. α → β`)
25 Polytype {
26 /// The [`Variable`] being bound
27 ///
28 /// [`Variable`]: type.Variable.html
29 variable: Variable,
30 /// The type in which `variable` is bound
31 body: Box<TypeScheme<N>>,
32 },
33}
34impl<N: Name> TypeScheme<N> {
35 /// Checks whether a variable is bound in the quantification of a polytype.
36 ///
37 /// # Examples
38 ///
39 /// ```
40 /// # use polytype::{ptp, tp};
41 /// let t = ptp!(0; @arrow[tp!(0), tp!(1)]); // ∀α. α → β
42 /// assert!(t.is_bound(0));
43 /// assert!(!t.is_bound(1));
44 /// ```
45 pub fn is_bound(&self, v: Variable) -> bool {
46 match *self {
47 TypeScheme::Monotype(_) => false,
48 TypeScheme::Polytype { variable, .. } if variable == v => true,
49 TypeScheme::Polytype { ref body, .. } => body.is_bound(v),
50 }
51 }
52 /// Returns a set of each [`Variable`] bound by the [`TypeScheme`].
53 ///
54 /// # Examples
55 ///
56 /// ```
57 /// # use polytype::{ptp, tp};
58 /// let t = ptp!(0, 1; @arrow[tp!(1), tp!(2), tp!(3)]); // ∀α. ∀β. β → ɣ → δ
59 /// assert_eq!(t.bound_vars(), vec![0, 1]);
60 /// ```
61 ///
62 /// [`Variable`]: type.Variable.html
63 /// [`TypeScheme`]: enum.TypeScheme.html
64 pub fn bound_vars(&self) -> Vec<Variable> {
65 let mut t = self;
66 let mut bvs = Vec::new();
67 while let TypeScheme::Polytype { variable, ref body } = *t {
68 bvs.push(variable);
69 t = body
70 }
71 bvs
72 }
73 /// Returns a set of each free [`Variable`] in the [`TypeScheme`].
74 ///
75 /// # Examples
76 ///
77 /// ```
78 /// # use polytype::{ptp, tp};
79 /// let t = ptp!(0, 1; @arrow[tp!(1), tp!(2), tp!(3)]); // ∀α. ∀β. β → ɣ → δ
80 /// let mut free = t.free_vars();
81 /// free.sort();
82 /// assert_eq!(free, vec![2, 3]);
83 /// ```
84 /// [`Variable`]: type.Variable.html
85 /// [`TypeScheme`]: enum.TypeScheme.html
86 pub fn free_vars(&self) -> Vec<Variable> {
87 let mut vars = vec![];
88 self.free_vars_internal(&mut vars);
89 vars.sort_unstable();
90 vars.dedup();
91 vars
92 }
93 fn free_vars_internal(&self, vars: &mut Vec<Variable>) {
94 match *self {
95 TypeScheme::Monotype(ref t) => t.vars_internal(vars),
96 TypeScheme::Polytype { variable, ref body } => {
97 body.free_vars_internal(vars);
98 *vars = vars.iter().filter(|&v| v != &variable).cloned().collect();
99 }
100 }
101 }
102 /// Instantiate a [`TypeScheme`] in the context by removing quantifiers.
103 ///
104 /// All type variables will be replaced with fresh type variables.
105 ///
106 /// # Examples
107 ///
108 /// ```
109 /// # use polytype::{ptp, tp, Context};
110 /// let mut ctx = Context::default();
111 ///
112 /// let t1 = ptp!(3; list(tp!(3)));
113 /// let t2 = ptp!(3; list(tp!(3)));
114 ///
115 /// let t1 = t1.instantiate(&mut ctx);
116 /// let t2 = t2.instantiate(&mut ctx);
117 /// assert_eq!(t1.to_string(), "list(t0)");
118 /// assert_eq!(t2.to_string(), "list(t1)");
119 /// ```
120 ///
121 /// [`TypeScheme`]: enum.TypeScheme.html
122 pub fn instantiate(&self, ctx: &mut Context<N>) -> Type<N> {
123 self.instantiate_internal(ctx, &mut HashMap::new())
124 }
125 fn instantiate_internal(
126 &self,
127 ctx: &mut Context<N>,
128 substitution: &mut HashMap<Variable, Type<N>>,
129 ) -> Type<N> {
130 match *self {
131 TypeScheme::Monotype(ref t) => t.substitute(substitution),
132 TypeScheme::Polytype { variable, ref body } => {
133 substitution.insert(variable, ctx.new_variable());
134 body.instantiate_internal(ctx, substitution)
135 }
136 }
137 }
138 /// Like [`instantiate`], but works in-place.
139 ///
140 /// [`instantiate`]: #method.instantiate
141 pub fn instantiate_owned(self, ctx: &mut Context<N>) -> Type<N> {
142 self.instantiate_owned_internal(ctx, &mut HashMap::new())
143 }
144 fn instantiate_owned_internal(
145 self,
146 ctx: &mut Context<N>,
147 substitution: &mut HashMap<Variable, Type<N>>,
148 ) -> Type<N> {
149 match self {
150 TypeScheme::Monotype(mut t) => {
151 t.substitute_mut(substitution);
152 t
153 }
154 TypeScheme::Polytype { variable, body } => {
155 substitution.insert(variable, ctx.new_variable());
156 body.instantiate_owned_internal(ctx, substitution)
157 }
158 }
159 }
160}
161impl<N: Name> fmt::Display for TypeScheme<N> {
162 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
163 match *self {
164 TypeScheme::Polytype { variable, ref body } => write!(f, "∀t{}. {}", variable, body),
165 TypeScheme::Monotype(ref t) => t.fmt(f),
166 }
167 }
168}
169
170/// Represents [monotypes][1] (fully instantiated, unquantified types).
171///
172/// The primary ways to create a `Type` are with either the [`tp!`] macro or
173/// [`TypeScheme::instantiate`]. [`Type::arrow`] constructs function types (i.e. `α → β`), as does
174/// conversion (`Type::from`) with `Vec` and `VecDeque` for curried arrows.
175///
176/// [`tp!`]: macro.tp.html
177/// [`TypeScheme::instantiate`]: enum.TypeScheme.html#method.instantiate
178/// [`Type::arrow`]: enum.TypeScheme.html#method.instantiate
179/// [1]: https://en.wikipedia.org/wiki/Hindley–Milner_type_system#Monotypes
180#[derive(Debug, Clone, Hash, PartialEq, Eq)]
181pub enum Type<N: Name = &'static str> {
182 /// Primitive or composite types (e.g. `int`, `List(α)`, `α → β`)
183 ///
184 /// # Examples
185 ///
186 /// Primitives have no associated types:
187 ///
188 /// ```
189 /// # use polytype::Type;
190 /// let tint = Type::Constructed("int", vec![]);
191 /// assert_eq!(tint.to_string(), "int")
192 /// ```
193 ///
194 /// Composites have associated types:
195 ///
196 /// ```
197 /// # use polytype::Type;
198 /// let tint = Type::Constructed("int", vec![]);
199 /// let tlist_of_ints = Type::Constructed("list", vec![tint]);
200 /// assert_eq!(tlist_of_ints.to_string(), "list(int)");
201 /// ```
202 ///
203 /// With the macro:
204 ///
205 /// ```
206 /// # use polytype::tp;
207 /// let t = tp!(list(tp!(int)));
208 /// assert_eq!(t.to_string(), "list(int)");
209 /// ```
210 ///
211 /// Function types, or "arrows", are constructed with either [`Type::arrow`], two
212 /// implementations of `Type::from` — one for [`Vec<Type>`] and one for [`VecDeque<Type>`] — or
213 /// the macro:
214 ///
215 /// ```
216 /// # use polytype::{tp, Type};
217 /// let t = Type::arrow(tp!(int), tp!(bool));
218 /// assert_eq!(t.to_string(), "int → bool");
219 ///
220 /// let t = Type::from(vec![tp!(int), tp!(int), tp!(bool)]);
221 /// assert_eq!(t.to_string(), "int → int → bool");
222 ///
223 /// let t = tp!(@arrow[tp!(int), tp!(int), tp!(bool)]); // prefer this over Type::from
224 /// assert_eq!(t.to_string(), "int → int → bool");
225 /// ```
226 ///
227 /// [`Type::arrow`]: enum.Type.html#method.arrow
228 /// [`Vec<Type>`]: enum.Type.html#impl-From<Vec<Type<N>>>
229 /// [`VecDeque<Type>`]: enum.Type.html#impl-From<VecDeque<Type<N>>>
230 Constructed(N, Vec<Type<N>>),
231 /// Type variables (e.g. `α`, `β`).
232 ///
233 /// # Examples
234 ///
235 /// ```
236 /// # use polytype::{tp, Type};
237 /// // any function: α → β
238 /// let t = tp!(@arrow[Type::Variable(0), Type::Variable(1)]);
239 /// assert_eq!(t.to_string(), "t0 → t1");
240 /// ```
241 ///
242 /// With the macro:
243 ///
244 /// ```
245 /// # use polytype::tp;
246 /// // map: (α → β) → [α] → [β]
247 /// let t = tp!(@arrow[
248 /// tp!(@arrow[tp!(0), tp!(1)]),
249 /// tp!(list(tp!(0))),
250 /// tp!(list(tp!(1))),
251 /// ]);
252 /// assert_eq!(t.to_string(), "(t0 → t1) → list(t0) → list(t1)");
253 /// ```
254 Variable(Variable),
255}
256impl<N: Name> Type<N> {
257 /// Construct a function type (i.e. `alpha` → `beta`).
258 ///
259 /// # Examples
260 ///
261 /// ```
262 /// # use polytype::{tp, Type};
263 /// let t = Type::arrow(tp!(int), tp!(bool));
264 /// assert_eq!(t.to_string(), "int → bool");
265 /// ```
266 pub fn arrow(alpha: Type<N>, beta: Type<N>) -> Type<N> {
267 Type::Constructed(N::arrow(), vec![alpha, beta])
268 }
269 /// If the type is an arrow, get its associated argument and return types.
270 ///
271 /// # Examples
272 ///
273 /// ```
274 /// # use polytype::{ptp, tp};
275 /// let t = tp!(@arrow[tp!(int), tp!(int), tp!(bool)]);
276 /// if let Some((left, right)) = t.as_arrow() {
277 /// assert_eq!(left.to_string(), "int");
278 /// assert_eq!(right.to_string(), "int → bool");
279 /// } else { unreachable!() }
280 /// ```
281 pub fn as_arrow(&self) -> Option<(&Type<N>, &Type<N>)> {
282 match *self {
283 Type::Constructed(ref n, ref args) if n.is_arrow() => Some((&args[0], &args[1])),
284 _ => None,
285 }
286 }
287 pub(crate) fn occurs(&self, v: Variable) -> bool {
288 match *self {
289 Type::Constructed(_, ref args) => args.iter().any(|t| t.occurs(v)),
290 Type::Variable(n) => n == v,
291 }
292 }
293 /// Supplying `is_return` helps arrows look cleaner.
294 pub(crate) fn show(&self, is_return: bool) -> String {
295 match *self {
296 Type::Variable(v) => format!("t{}", v),
297 Type::Constructed(ref name, ref args) => {
298 if args.is_empty() {
299 name.show()
300 } else if name.is_arrow() {
301 Type::arrow_show(args, is_return)
302 } else {
303 format!(
304 "{}({})",
305 name.show(),
306 args.iter().map(|t| t.show(true)).join(",")
307 )
308 }
309 }
310 }
311 }
312 /// Show specifically for arrow types
313 fn arrow_show(args: &[Type<N>], is_return: bool) -> String {
314 if is_return {
315 format!("{} → {}", args[0].show(false), args[1].show(true))
316 } else {
317 format!("({} → {})", args[0].show(false), args[1].show(true))
318 }
319 }
320 /// If the type is an arrow, recursively get all curried function arguments.
321 ///
322 /// # Examples
323 ///
324 /// ```
325 /// # use polytype::tp;
326 /// let t = tp!(@arrow[tp!(int), tp!(int), tp!(bool)]);
327 /// if let Some(args) = t.args() {
328 /// assert_eq!(args.len(), 2);
329 /// assert_eq!(args[0].to_string(), "int");
330 /// assert_eq!(args[1].to_string(), "int");
331 /// } else { unreachable!() }
332 /// ```
333 pub fn args(&self) -> Option<VecDeque<&Type<N>>> {
334 match *self {
335 Type::Constructed(ref n, ref args) if n.is_arrow() => {
336 let mut tps = VecDeque::with_capacity(1);
337 tps.push_back(&args[0]);
338 let mut tp = &args[1];
339 loop {
340 match *tp {
341 Type::Constructed(ref n, ref args) if n.is_arrow() => {
342 tps.push_back(&args[0]);
343 tp = &args[1];
344 }
345 _ => break,
346 }
347 }
348 Some(tps)
349 }
350 _ => None,
351 }
352 }
353 /// If the type is an arrow, recursively get all curried function arguments.
354 pub fn args_destruct(self) -> Option<Vec<Type<N>>> {
355 match self {
356 Type::Constructed(n, mut args) if n.is_arrow() => {
357 let mut tps = Vec::with_capacity(1);
358 let mut tp = args.pop().unwrap();
359 tps.push(args.pop().unwrap());
360 loop {
361 match tp {
362 Type::Constructed(n, mut args) if n.is_arrow() => {
363 tp = args.pop().unwrap();
364 tps.push(args.pop().unwrap());
365 }
366 _ => break,
367 }
368 }
369 Some(tps)
370 }
371 _ => None,
372 }
373 }
374 /// If the type is an arrow, get its ultimate return type.
375 ///
376 /// # Examples
377 ///
378 /// ```
379 /// # use polytype::tp;
380 /// let t = tp!(@arrow[tp!(int), tp!(int), tp!(bool)]);
381 /// if let Some(ret) = t.returns() {
382 /// assert_eq!(ret.to_string(), "bool");
383 /// } else { unreachable!() }
384 /// ```
385 pub fn returns(&self) -> Option<&Type<N>> {
386 match *self {
387 Type::Constructed(ref n, ref args) if n.is_arrow() => {
388 let mut tp = &args[1];
389 loop {
390 match *tp {
391 Type::Constructed(ref n, ref args) if n.is_arrow() => {
392 tp = &args[1];
393 }
394 _ => break,
395 }
396 }
397 Some(tp)
398 }
399 _ => None,
400 }
401 }
402 /// Applies the type in a [`Context`].
403 ///
404 /// This will substitute type variables for the values associated with them
405 /// by the context.
406 ///
407 /// # Examples
408 ///
409 /// ```
410 /// # use polytype::{tp, Context};
411 /// let mut ctx = Context::default();
412 /// ctx.unify(&tp!(0), &tp!(int)).expect("unifies");
413 ///
414 /// let t = tp!(list(tp!(0)));
415 /// assert_eq!(t.to_string(), "list(t0)");
416 /// let t = t.apply(&ctx);
417 /// assert_eq!(t.to_string(), "list(int)");
418 /// ```
419 ///
420 /// [`Context`]: struct.Context.html
421 pub fn apply(&self, ctx: &Context<N>) -> Type<N> {
422 match *self {
423 Type::Constructed(ref name, ref args) => {
424 let args = args.iter().map(|t| t.apply(ctx)).collect();
425 Type::Constructed(name.clone(), args)
426 }
427 Type::Variable(v) => {
428 let maybe_tp = ctx
429 .path_compression_cache
430 .read()
431 .get(&v)
432 .or_else(|| ctx.substitution.get(&v))
433 .cloned();
434 maybe_tp
435 .map(|mut tp| {
436 tp.apply_mut(ctx);
437 let mut cache = ctx.path_compression_cache.write();
438 let is_hit = cache.get(&v) == Some(&tp);
439 if !is_hit {
440 cache.insert(v, tp.clone());
441 }
442 tp
443 })
444 .unwrap_or_else(|| self.clone())
445 }
446 }
447 }
448 /// Like [`apply_compress`], but works in-place.
449 ///
450 /// [`apply_compress`]: #method.apply_compress
451 pub fn apply_mut(&mut self, ctx: &Context<N>) {
452 match *self {
453 Type::Constructed(_, ref mut args) => {
454 for t in args {
455 t.apply_mut(ctx)
456 }
457 }
458 Type::Variable(v) => {
459 let maybe_tp = ctx
460 .path_compression_cache
461 .read()
462 .get(&v)
463 .or_else(|| ctx.substitution.get(&v))
464 .cloned();
465 *self = maybe_tp
466 .map(|mut tp| {
467 tp.apply_mut(ctx);
468 ctx.path_compression_cache.write().insert(v, tp.clone());
469 tp
470 })
471 .unwrap_or_else(|| self.clone());
472 }
473 }
474 }
475 /// Generalizes the type by quantifying over free variables in a [`TypeScheme`].
476 ///
477 /// Variables specified by `bound` remain unquantified.
478 ///
479 /// # Examples
480 ///
481 /// ```
482 /// # use polytype::{tp, Context};
483 /// let t = tp!(@arrow[tp!(0), tp!(1)]);
484 /// assert_eq!(t.to_string(), "t0 → t1");
485 ///
486 /// let mut ctx = Context::default();
487 /// ctx.extend(0, tp!(int));
488 ///
489 /// let t_gen = t.apply(&ctx).generalize(&[]);
490 /// assert_eq!(t_gen.to_string(), "∀t1. int → t1");
491 ///
492 /// let t_gen = t.apply(&ctx).generalize(&[1]);
493 /// assert_eq!(t_gen.to_string(), "int → t1");
494 /// ```
495 ///
496 /// [`TypeScheme`]: enum.TypeScheme.html
497 pub fn generalize(&self, bound: &[Variable]) -> TypeScheme<N> {
498 let fvs = self
499 .vars()
500 .into_iter()
501 .filter(|x| !bound.contains(x))
502 .collect::<Vec<Variable>>();
503 let mut t = TypeScheme::Monotype(self.clone());
504 for v in fvs {
505 t = TypeScheme::Polytype {
506 variable: v,
507 body: Box::new(t),
508 };
509 }
510 t
511 }
512 /// Compute all the variables present in a type.
513 ///
514 /// # Examples
515 ///
516 /// ```
517 /// # use polytype::tp;
518 /// let t = tp!(@arrow[tp!(0), tp!(1)]);
519 /// assert_eq!(t.to_string(), "t0 → t1");
520 ///
521 /// let mut vars = t.vars();
522 /// vars.sort();
523 /// assert_eq!(vars, vec![0, 1]);
524 /// ```
525 pub fn vars(&self) -> Vec<Variable> {
526 let mut vars = vec![];
527 self.vars_internal(&mut vars);
528 vars.sort_unstable();
529 vars.dedup();
530 vars
531 }
532 fn vars_internal(&self, vars: &mut Vec<Variable>) {
533 match *self {
534 Type::Constructed(_, ref args) => {
535 for arg in args {
536 arg.vars_internal(vars);
537 }
538 }
539 Type::Variable(v) => vars.push(v),
540 }
541 }
542 /// Perform a substitution. This is analogous to [`apply`].
543 ///
544 /// # Examples
545 ///
546 /// ```
547 /// # use polytype::tp;
548 /// # use std::collections::HashMap;
549 /// let t = tp!(@arrow[tp!(0), tp!(1)]);
550 /// assert_eq!(t.to_string(), "t0 → t1");
551 ///
552 /// let mut substitution = HashMap::new();
553 /// substitution.insert(0, tp!(int));
554 /// substitution.insert(1, tp!(bool));
555 ///
556 /// let t = t.substitute(&substitution);
557 /// assert_eq!(t.to_string(), "int → bool");
558 /// ```
559 ///
560 /// [`apply`]: #method.apply
561 pub fn substitute(&self, substitution: &HashMap<Variable, Type<N>>) -> Type<N> {
562 match *self {
563 Type::Constructed(ref name, ref args) => {
564 let args = args.iter().map(|t| t.substitute(substitution)).collect();
565 Type::Constructed(name.clone(), args)
566 }
567 Type::Variable(v) => substitution.get(&v).cloned().unwrap_or(Type::Variable(v)),
568 }
569 }
570 /// Like [`substitute`], but works in-place.
571 ///
572 /// [`substitute`]: #method.substitute
573 pub fn substitute_mut(&mut self, substitution: &HashMap<Variable, Type<N>>) {
574 match *self {
575 Type::Constructed(_, ref mut args) => {
576 for t in args {
577 t.substitute_mut(substitution)
578 }
579 }
580 Type::Variable(v) => {
581 if let Some(t) = substitution.get(&v) {
582 *self = t.clone()
583 }
584 }
585 }
586 }
587}
588impl<N: Name> fmt::Display for Type<N> {
589 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
590 write!(f, "{}", self.show(true))
591 }
592}
593impl<N: Name> From<VecDeque<Type<N>>> for Type<N> {
594 fn from(mut tps: VecDeque<Type<N>>) -> Type<N> {
595 match tps.len() {
596 0 => panic!("cannot create a type from nothing"),
597 1 => tps.pop_front().unwrap(),
598 2 => {
599 let alpha = tps.pop_front().unwrap();
600 let beta = tps.pop_front().unwrap();
601 Type::arrow(alpha, beta)
602 }
603 _ => {
604 let alpha = tps.pop_front().unwrap();
605 Type::arrow(alpha, tps.into())
606 }
607 }
608 }
609}
610impl<N: Name> From<Vec<Type<N>>> for Type<N> {
611 fn from(mut tps: Vec<Type<N>>) -> Type<N> {
612 let mut beta = tps
613 .pop()
614 .unwrap_or_else(|| panic!("cannot create a type from nothing"));
615 while let Some(alpha) = tps.pop() {
616 beta = Type::arrow(alpha, beta)
617 }
618 beta
619 }
620}