From 5ae010fef48cc2bf83a0d366d2a1cfa74ecce278 Mon Sep 17 00:00:00 2001 From: JJ Date: Thu, 13 Apr 2023 00:20:06 -0700 Subject: major cleanups: extend Type, refactor Term, and switch to String errs --- src/simple.rs | 140 ++++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 96 insertions(+), 44 deletions(-) (limited to 'src/simple.rs') diff --git a/src/simple.rs b/src/simple.rs index 6a40b67..c67fe2e 100644 --- a/src/simple.rs +++ b/src/simple.rs @@ -1,117 +1,117 @@ // Simple bidirectional type checking -#![allow(unused_variables)] - use crate::ast::*; +use std::collections::HashMap; -pub fn check(context: Context, expression: Expression, target: Type) -> Result<(), (&'static str, Context, Type)> { +pub fn check(context: &Context, expression: Expression, target: &Type) -> Result<(), String> { match expression { // fall through to inference mode Expression::Annotation { expr, kind } => { - let result = infer(context.clone(), Expression::Annotation { expr, kind })?; + let result = infer(context, Expression::Annotation { expr, kind })?; return match subtype(&result, &target) { true => Ok(()), - false => Err(("inferred type does not match target", context, target)) + false => Err(format!("inferred type {result} does not match target {target}")) } }, // Bt-CheckInfer - Expression::Constant { term } => match subtype(&term.kind, &target) { + Expression::Constant { term } => match subtype(&convert(&term)?, &target) { true => Ok(()), - false => Ok(()) // all our constants are Empty for now - // false => Err(("constant is of wrong type", context, target)) + false => Err(format!("constant is of wrong type, expected {target}")) + // false => Ok(()) // all our constants are Empty for now }, // Bt-CheckInfer Expression::Variable { id } => match context.get(&id) { - Some(term) if subtype(&term.kind, &target) => Ok(()), - Some(_) => Err(("variable is of wrong type", context, target)), - None => Err(("failed to find variable in context", context, target)) + Some(term) if subtype(&convert(term)?, &target) => Ok(()), + Some(_) => Err(format!("variable {id} is of wrong type")), + None => Err(format!("failed to find variable {id} in context")) }, // Bt-Abs Expression::Abstraction { param, func } => match target { Type::Function { from, to } => { - let mut context = context; - context.insert(param, Term { val: 0, kind: *from }); // hack - return check(context, *func, *to); + let mut context = context.clone(); + context.insert(param, default(from)?); + return check(&context, *func, &to); }, - _ => Err(("attempting to check an abstraction with a non-function type", context, target)) + _ => Err(format!("attempting to check an abstraction with a non-function type {target}")) }, // fall through to inference mode Expression::Application { func, arg } => { - let result = &infer(context.clone(), Expression::Application { func, arg })?; + let result = &infer(context, Expression::Application { func, arg })?; return match subtype(&result, &target) { true => Ok(()), - false => Err(("inferred type does not match target", context, target)) + false => Err(format!("inferred type {result} does not match {target}")) } }, // T-If Expression::Conditional { if_cond, if_then, if_else } => { - check(context.clone(), *if_cond, Type::Boolean)?; - check(context.clone(), *if_then, target.clone())?; - check(context.clone(), *if_else, target.clone())?; + check(context, *if_cond, &Type::Boolean)?; + check(context, *if_then, &target)?; + check(context, *if_else, &target)?; return Ok(()); } } } -pub fn infer(context: Context, expression: Expression) -> Result { +pub fn infer(context: &Context, expression: Expression) -> Result { match expression { // Bt-Ann - Expression::Annotation { expr, kind } => check(context, *expr, kind.clone()).map(|x| kind), + Expression::Annotation { expr, kind } => check(context, *expr, &kind).map(|x| kind), // Bt-True / Bt-False / etc - Expression::Constant { term } => Ok(term.kind), + Expression::Constant { term } => convert(&term), // Bt-Var Expression::Variable { id } => match context.get(&id) { - Some(term) => Ok(term.clone().kind), - None => Err(("failed to find variable in context", context, Type::Empty)) + Some(term) => infer(&Context::new(), Expression::Constant { term: term.clone() }), + None => Err(format!("failed to find variable in context {context:?}")) }, // Bt-App - Expression::Application { func, arg } => match infer(context.clone(), *func)? { - Type::Function { from, to } => check(context, *arg, *from).map(|x| *to), - _ => Err(("application abstraction is not a function type", context, Type::Empty)) + Expression::Application { func, arg } => match infer(context, *func)? { + Type::Function { from, to } => check(context, *arg, &*from).map(|x| *to), + _ => Err(format!("application abstraction is not a function type")) }, // inference from an abstraction is always an error // we could try and infer the func without adding the parameter to scope: // but this is overwhelmingly likely to be an error, so just report it now. Expression::Abstraction { param, func } => - Err(("attempting to infer from an abstraction", context, Type::Empty)), + Err(format!("attempting to infer from an abstraction")), // idk Expression::Conditional { if_cond, if_then, if_else } => { - check(context.clone(), *if_cond, Type::Boolean)?; - let if_then = infer(context.clone(), *if_then)?; - let if_else = infer(context.clone(), *if_else)?; + check(context, *if_cond, &Type::Boolean)?; + let if_then = infer(context, *if_then)?; + let if_else = infer(context, *if_else)?; if subtype(&if_then, &if_else) && subtype(&if_else, &if_then) { Ok(if_then) // fixme: should be the join } else { - Err(("if clauses of different types", context, Type::Empty)) + Err(format!("if clauses of different types: {if_then} and {if_else}")) } } } } /// Evaluates an expression given a context (of variables) to a term, or fails. -pub fn execute(context: Context, expression: Expression) -> Result { +pub fn execute(context: &Context, expression: Expression) -> Result { match expression { Expression::Annotation { expr, .. } => execute(context, *expr), Expression::Constant { term } => Ok(term), Expression::Variable { id } => match context.get(&id) { Some(term) => Ok(term.clone()), - None => Err(("no such variable in context", context)) + None => Err(format!("no such variable in context {context:?}")) }, - Expression::Abstraction { .. } => Err(("attempting to execute an abstraction", context)), + Expression::Abstraction { param, func } => + Err(format!("attempting to execute an abstraction ({}){}", param, func)), Expression::Application { func, arg } => match *func { Expression::Abstraction { param, func } => { - let value = execute(context.clone(), *arg)?; - let mut context = context; + let value = execute(context, *arg)?; + let mut context = context.clone(); context.insert(param, value); - return execute(context, *func); + return execute(&context, *func); } - _ => Err(("attempting to execute an application to nothing", context)) + _ => Err(format!("attempting to execute an application to non-abstraction {}", *func)) }, Expression::Conditional { if_cond, if_then, if_else } => { - match execute(context.clone(), *if_cond) { - Ok(Term { val: 1, .. }) => execute(context, *if_then), - Ok(Term { val: 0, .. }) => execute(context, *if_else), - _ => Err(("invalid type for a conditional", context)) + match execute(context, *if_cond)? { + Term::Boolean(true) => execute(context, *if_then), + Term::Boolean(false) => execute(context, *if_else), + term => Err(format!("invalid type {} for a conditional", convert(&term)?)) } } } @@ -145,3 +145,55 @@ pub fn subtype(is: &Type, of: &Type) -> bool { (_, _) => false } } + +/// Convert a term into its corresponding type. +pub fn convert(term: &Term) -> Result { + match term { + Term::Unit() => Ok(Type::Unit), + Term::Boolean(_) => Ok(Type::Boolean), + Term::Natural(_) => Ok(Type::Natural), + Term::Integer(_) => Ok(Type::Integer), + Term::Float(_) => Ok(Type::Float), + Term::String { len, cap, data } => Ok(Type::String), + Term::Enum { val, data } => data.get(*val) + .ok_or_else(|| "enum value out of range!".to_string()).cloned(), + Term::Record(data) => { + let mut result = HashMap::new(); + for (key, val) in data { + result.insert(key.clone(), convert(val)?); + } + return Ok(Type::Record(result)); + }, + Term::Function(func) => match infer(&Context::new(), *func.clone()) { + Ok(Type::Function { from, to }) => Ok(Type::Function { from, to }), + _ => Err("function term value not a function!".to_string()) + } + } +} + +/// Get the default value of a type. Throws an error if it doesn't exist. +pub fn default(kind: &Type) -> Result { + match kind { + Type::Empty => Err("attempting to take the default term for empty".to_string()), + Type::Error => Err("attempting to take the default term for error".to_string()), + Type::Unit => Ok(Term::Unit()), + Type::Boolean => Ok(Term::Boolean(false)), + Type::Natural => Ok(Term::Natural(0)), + Type::Integer => Ok(Term::Integer(0)), + Type::Float => Ok(Term::Float(0.0)), + Type::String => Ok(Term::String { len: 0, cap: 0, data: vec!()}), + Type::Enum(data) => match data.len() { + 0 => Err("attempting to get a default term of an enum with no variants!".to_string()), + _ => Ok(Term::Enum { val: 0, data: data.clone() }) + }, + Type::Record(data) => { + let mut result = HashMap::new(); + for (key, val) in data { + result.insert(key.clone(), default(&val)?); + } + return Ok(Term::Record(result)); + }, + Type::Function { from, to } => + Err("attempting to take the default term of a function type".to_string()), + } +} -- cgit v1.2.3-70-g09d2