From 78751b29953f786878549955c050ba38cb514d52 Mon Sep 17 00:00:00 2001 From: Joel Kronqvist Date: Mon, 4 Aug 2025 01:22:15 +0300 Subject: Implemented generic substitution (tested) for use in inferring generics. --- src/type/mod.rs | 1 + src/type/subst.rs | 44 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 45 insertions(+) create mode 100644 src/type/subst.rs (limited to 'src') diff --git a/src/type/mod.rs b/src/type/mod.rs index 6c4be97..37081a1 100644 --- a/src/type/mod.rs +++ b/src/type/mod.rs @@ -3,6 +3,7 @@ pub mod util; pub mod display; pub mod check; +pub mod subst; use crate::sexp::SExp; diff --git a/src/type/subst.rs b/src/type/subst.rs new file mode 100644 index 0000000..6e92584 --- /dev/null +++ b/src/type/subst.rs @@ -0,0 +1,44 @@ + +use crate::r#type::{Type, Type::*, util::*}; + +impl Type { + /// Performs substitution on the type. + /// + /// Replaces all free occurrences of generics + /// named `name` with the given type `value` + /// in the type. + /// ```rust + /// use melisp::r#type::{Type::*, util::*}; + /// + /// assert_eq!( + /// List(vec![Integer, arr(Integer, VarType("A".to_string())), VarType("B".to_string())]) + /// .subst("A", &Integer), + /// List(vec![Integer, arr(Integer, Integer), VarType("B".to_string())]) + /// ); + /// + /// assert_eq!( + /// List(vec![Integer, arr(Integer, VarType("A".to_string())), VarType("B".to_string())]) + /// .subst("B", &arr(Integer, Integer)), + /// List(vec![Integer, arr(Integer, VarType("A".to_string())), arr(Integer, Integer)]) + /// ); + /// ``` + pub fn subst(self, name: &str, value: &Type) -> Type { + match self { + + Arrow(a, b) => arr((*a).subst(name, value), (*b).subst(name, value)), + + List(v) => List( + v.into_iter() + .map(|t| t.subst(name, value)) + .collect() + ), + + VarType(s) if s == name => value.clone(), + + VarType(s) => VarType(s), + + Integer => Integer, + + } + } +} -- cgit v1.2.3