1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283
//! Hindley–Milner type inference for arithmetic expressions parsed //! by the [`arithmetic-parser`] crate. //! //! This crate allows parsing type annotations as a part of a [`Grammar`], and to infer //! and check types for expressions / statements produced by `arithmetic-parser`. //! Type inference is *partially* compatible with the interpreter from [`arithmetic-eval`]; //! if the inference algorithm succeeds on a certain expression / statement / block, //! it will execute successfully, but not all successfully executing items pass type inference. //! (An exception here is [`Type::Any`], which is specifically designed to circumvent //! the type system limitations. If `Any` is used too liberally, it can result in code passing //! type checks, but failing during execution.) //! //! # Type system //! //! The type system corresponds to types of `Value`s in `arithmetic-eval`: //! //! - Primitive types are customizeable via [`PrimitiveType`] impl. In the simplest case, //! there can be 2 primitive types: Booleans (`Bool`) and numbers (`Num`), //! as ecapsulated in [`Num`]. //! - There are two container types - [tuples](Tuple) and [objects](Object). //! - Tuple types can be represented either //! in the tuple form, such as `(Num, Bool)`, or as a slice, such as `[Num; 3]`. //! As in Rust, all slice elements must have the same type. Unlike Rust, tuple and slice //! forms are equivalent; e.g., `[Num; 3]` and `(Num, Num, Num)` are the same type. //! - Object types are represented in a brace form, such as `{ x: Num }`. Objects can act as //! either specific types or type constraints. //! - Functions are first-class types. Functions can have type and/or const params. //! Const params always specify tuple length. //! - Type params can be constrained. Constraints are expressed via [`Constraint`]s. //! As an example, [`Num`] has a few known constraints, such as type [`Linearity`]. //! //! [`Constraint`]: crate::arith::Constraint //! [`Num`]: crate::arith::Num //! [`Linearity`]: crate::arith::Linearity //! //! # Inference rules //! //! Inference mostly corresponds to [Hindley–Milner typing rules]. It does not require //! type annotations, but utilizes them if present. Type unification (encapsulated in //! [`Substitutions`]) is performed at each variable use or assignment. Variable uses include //! function calls and unary and binary ops; the op behavior is customizable //! via [`TypeArithmetic`]. //! //! Whenever possible, the most generic type satisfying the constraints is used. In particular, //! this means that all type / length variables not resolved at the function definition site become //! parameters of the function. Likewise, each function call instantiates a separate instance //! of a generic function; type / length params for each call are assigned independently. //! See the example below for more details. //! //! [Hindley–Milner typing rules]: https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system#Typing_rules //! [`Substitutions`]: crate::arith::Substitutions //! [`TypeArithmetic`]: crate::arith::TypeArithmetic //! //! # Operations //! //! ## Field access //! //! See [`Tuple` docs](Tuple#indexing) for discussion of indexing expressions, such as `xs.0`, //! and [`Object` docs](Object) for discussion of field access, such as `point.x`. //! //! ## Type casts //! //! [A type cast](arithmetic_parser::Expr::TypeCast) is equivalent to introducing a new var //! with the specified annotation, assigning to it and returning the new var. That is, //! `x as Bool` is equivalent to `{ _x: Bool = x; _x }`. As such, casts are safe (cannot be used //! to transmute the type arbitrarily), unless `any` type is involved. //! //! # Examples //! //! ``` //! use arithmetic_parser::grammars::{F32Grammar, Parse}; //! use arithmetic_typing::{defs::Prelude, Annotated, TypeEnvironment, Type}; //! //! # fn main() -> anyhow::Result<()> { //! let code = "sum = |xs| xs.fold(0, |acc, x| acc + x);"; //! let ast = Annotated::<F32Grammar>::parse_statements(code)?; //! //! let mut env = TypeEnvironment::new(); //! env.insert("fold", Prelude::Fold); //! //! // Evaluate `code` to get the inferred `sum` function signature. //! let output_type = env.process_statements(&ast)?; //! assert!(output_type.is_void()); //! assert_eq!(env["sum"].to_string(), "([Num; N]) -> Num"); //! # Ok(()) //! # } //! ``` //! //! Defining and using generic functions: //! //! ``` //! # use arithmetic_parser::grammars::{F32Grammar, Parse}; //! # use arithmetic_typing::{defs::Prelude, Annotated, TypeEnvironment, Type}; //! # fn main() -> anyhow::Result<()> { //! let code = "sum_with = |xs, init| xs.fold(init, |acc, x| acc + x);"; //! let ast = Annotated::<F32Grammar>::parse_statements(code)?; //! //! let mut env = TypeEnvironment::new(); //! env.insert("fold", Prelude::Fold); //! //! let output_type = env.process_statements(&ast)?; //! assert!(output_type.is_void()); //! assert_eq!( //! env["sum_with"].to_string(), //! "for<'T: Ops> (['T; N], 'T) -> 'T" //! ); //! // Note that `sum_with` is parametric by the element of the slice //! // (for which the linearity constraint is applied based on the arg usage) //! // *and* by its length. //! //! let usage_code = r#" //! num_sum: Num = (1, 2, 3).sum_with(0); //! tuple_sum: (Num, Num) = ((1, 2), (3, 4)).sum_with((0, 0)); //! "#; //! let ast = Annotated::<F32Grammar>::parse_statements(usage_code)?; //! // Both lengths and element types differ in these invocations, //! // but it works fine since they are treated independently. //! env.process_statements(&ast)?; //! # Ok(()) //! # } //! ``` //! //! [`arithmetic-parser`]: https://crates.io/crates/arithmetic-parser //! [`Grammar`]: arithmetic_parser::grammars::Grammar //! [`arithmetic-eval`]: https://crates.io/crates/arithmetic-eval #![doc(html_root_url = "https://docs.rs/arithmetic-typing/0.3.0")] #![warn(missing_docs, missing_debug_implementations)] #![warn(clippy::all, clippy::pedantic)] #![allow( clippy::missing_errors_doc, clippy::must_use_candidate, clippy::module_name_repetitions, clippy::similar_names, // too many false positives because of lhs / rhs clippy::option_if_let_else // too many false positives )] use std::{fmt, marker::PhantomData, str::FromStr}; use arithmetic_parser::{ grammars::{Features, Grammar, Parse, ParseLiteral}, InputSpan, NomResult, }; pub mod arith; pub mod ast; pub mod defs; mod env; pub mod error; mod types; pub mod visit; pub use self::{ env::TypeEnvironment, types::{ DynConstraints, FnWithConstraints, Function, FunctionBuilder, LengthVar, Object, Slice, Tuple, TupleIndex, TupleLen, Type, TypeVar, UnknownLen, }, }; use self::{arith::ConstraintSet, ast::TypeAst}; /// Primitive types in a certain type system. /// /// More complex types, like [`Type`] and [`Function`], are defined with a type param /// which determines the primitive type(s). This type param must implement [`PrimitiveType`]. /// /// [`TypeArithmetic`] has a `PrimitiveType` impl as an associated type, and one of the required /// operations of this trait is to be able to infer type for literal values from a [`Grammar`]. /// /// # Implementation Requirements /// /// - [`Display`](fmt::Display) and [`FromStr`] implementations must be consistent; i.e., /// `Display` should produce output parseable by `FromStr`. `Display` will be used in /// `Display` impls for `Type` etc. `FromStr` will be used to read type annotations. /// - `Display` presentations must be identifiers, such as `Num`. /// - While not required, a `PrimitiveType` should usually contain a Boolean type and /// implement [`WithBoolean`]. This allows to reuse [`BoolArithmetic`] and/or [`NumArithmetic`] /// as building blocks for your [`TypeArithmetic`]. /// /// [`Grammar`]: arithmetic_parser::grammars::Grammar /// [`TypeArithmetic`]: crate::arith::TypeArithmetic /// [`WithBoolean`]: crate::arith::WithBoolean /// [`BoolArithmetic`]: crate::arith::BoolArithmetic /// [`NumArithmetic`]: crate::arith::NumArithmetic /// /// # Examples /// /// ``` /// # use std::{fmt, str::FromStr}; /// use arithmetic_typing::PrimitiveType; /// /// #[derive(Debug, Clone, Copy, PartialEq)] /// enum NumOrBytes { /// /// Numeric value, such as 1. /// Num, /// /// Bytes value, such as 0x1234 or "hello". /// Bytes, /// } /// /// // `NumOrBytes` should correspond to a "value" type in the `Grammar`, /// // for example: /// enum NumOrBytesValue { /// Num(f64), /// Bytes(Vec<u8>), /// } /// /// impl fmt::Display for NumOrBytes { /// fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result { /// match self { /// Self::Num => formatter.write_str("Num"), /// Self::Bytes => formatter.write_str("Bytes"), /// } /// } /// } /// /// impl FromStr for NumOrBytes { /// type Err = anyhow::Error; /// /// fn from_str(s: &str) -> Result<Self, Self::Err> { /// match s { /// "Num" => Ok(Self::Num), /// "Bytes" => Ok(Self::Bytes), /// _ => Err(anyhow::anyhow!("expected `Num` or `Bytes`")), /// } /// } /// } /// /// impl PrimitiveType for NumOrBytes {} /// ``` pub trait PrimitiveType: Clone + PartialEq + fmt::Debug + fmt::Display + FromStr + Send + Sync + 'static { /// Returns well-known constraints for this type. These constraints are used /// in standalone parsing of type signatures. /// /// The default implementation returns an empty set. fn well_known_constraints() -> ConstraintSet<Self> { ConstraintSet::default() } } /// Grammar with support of type annotations. Works as a decorator. /// /// # Examples /// /// ``` /// use arithmetic_parser::grammars::{F32Grammar, Parse}; /// use arithmetic_typing::Annotated; /// /// # fn main() -> anyhow::Result<()> { /// let code = "x: [Num] = (1, 2, 3);"; /// let ast = Annotated::<F32Grammar>::parse_statements(code)?; /// # assert_eq!(ast.statements.len(), 1); /// # Ok(()) /// # } /// ``` #[derive(Debug)] pub struct Annotated<T>(PhantomData<T>); impl<T: ParseLiteral> ParseLiteral for Annotated<T> { type Lit = T::Lit; fn parse_literal(input: InputSpan<'_>) -> NomResult<'_, Self::Lit> { <T as ParseLiteral>::parse_literal(input) } } impl<'a, T: ParseLiteral> Grammar<'a> for Annotated<T> { type Type = TypeAst<'a>; fn parse_type(input: InputSpan<'a>) -> NomResult<'a, Self::Type> { use nom::combinator::map; map(TypeAst::parse, |ast| ast.extra)(input) } } /// Supports all syntax features. impl<T: ParseLiteral> Parse<'_> for Annotated<T> { type Base = Self; const FEATURES: Features = Features::all(); }