From 51dcf19eb6f8d2127f3dedfc1d7d5326d7a8017b Mon Sep 17 00:00:00 2001 From: Greg Brown Date: Tue, 27 Apr 2021 13:07:27 +0100 Subject: Start rewrite using query system. --- src/chomp/ast-old/error.rs | 52 +++++ src/chomp/ast-old/mod.rs | 325 +++++++++++++++++++++++++++++++ src/chomp/ast-old/substitute.rs | 412 ++++++++++++++++++++++++++++++++++++++++ 3 files changed, 789 insertions(+) create mode 100644 src/chomp/ast-old/error.rs create mode 100644 src/chomp/ast-old/mod.rs create mode 100644 src/chomp/ast-old/substitute.rs (limited to 'src/chomp/ast-old') diff --git a/src/chomp/ast-old/error.rs b/src/chomp/ast-old/error.rs new file mode 100644 index 0000000..9057ec3 --- /dev/null +++ b/src/chomp/ast-old/error.rs @@ -0,0 +1,52 @@ +use super::{Expression, Lambda, NamedExpression}; +use proc_macro2::Span; +use std::{ + error::Error, + fmt::{self, Display}, +}; + +#[derive(Debug)] +pub enum TranslateError { + CallNotAFunction { + on: Expression, + span: Option, + }, + WrongArgCount { + lambda: Lambda, + args: Vec, + span: Option, + }, +} + +impl From for syn::Error { + fn from(e: TranslateError) -> Self { + let msg = e.to_string(); + let span = match e { + TranslateError::CallNotAFunction { span, .. } + | TranslateError::WrongArgCount { span, .. } => span, + }; + + Self::new(span.unwrap_or_else(Span::call_site), msg) + } +} + +impl Display for TranslateError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + Self::CallNotAFunction { .. } => { + write!(f, "call expected a function") + } + Self::WrongArgCount { lambda, args, .. } => match (lambda.args.len(), args.len()) { + (1, n) => write!(f, "this function takes 1 argument but {} were supplied", n), + (m, _) => write!(f, "this function takes {} arguments but 1 was supplied", m), + (m, n) => write!( + f, + "this function takes {} arguments but {} were supplied", + m, n + ), + }, + } + } +} + +impl Error for TranslateError {} diff --git a/src/chomp/ast-old/mod.rs b/src/chomp/ast-old/mod.rs new file mode 100644 index 0000000..232381a --- /dev/null +++ b/src/chomp/ast-old/mod.rs @@ -0,0 +1,325 @@ +use std::fmt::{self, Display}; + +use proc_macro2::Span; + +use super::Name; + +pub mod error; +pub mod substitute; + +#[derive(Clone, Copy, Debug, Default, Eq, PartialEq, Hash)] +pub struct Epsilon; + +pub type Literal = String; + +#[derive(Clone, Debug)] +pub struct Cat { + pub first: Box, + pub rest: Vec<(Option, NamedExpression)>, +} + +impl Display for Cat { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "({}", self.first)?; + for (_, other) in &self.rest { + write!(f, " . {}", other)?; + } + write!(f, ")") + } +} + +impl PartialEq for Cat { + fn eq(&self, other: &Self) -> bool { + self.first == other.first + && self.rest.len() == other.rest.len() + && self + .rest + .iter() + .zip(other.rest.iter()) + .all(|((_, me), (_, them))| me == them) + } +} + +impl Eq for Cat {} + +#[derive(Clone, Debug)] +pub struct Alt { + pub first: Box, + pub rest: Vec<(Option, NamedExpression)> +} + +impl Display for Alt { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "({}", self.first)?; + for (_, other) in &self.rest { + write!(f, " | {}", other)?; + } + write!(f, ")") + } +} + +impl PartialEq for Alt { + fn eq(&self, other: &Self) -> bool { + self.first == other.first + && self.rest.len() == other.rest.len() + && self + .rest + .iter() + .zip(other.rest.iter()) + .all(|((_, me), (_, them))| me == them) + } +} + +impl Eq for Alt {} + +#[derive(Clone, Debug, Eq, PartialEq)] +pub struct Fix { + pub inner: Box, +} + +impl Display for Fix { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "!{}", self.inner) + } +} + +#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)] +pub struct Variable { + pub index: usize, +} + +impl Display for Variable { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "'{}", self.index) + } +} + +/// A function invocation. +#[derive(Clone, Debug, Eq, PartialEq)] +pub struct Call { + pub on: Box, + pub args: Vec, +} + +impl Display for Call { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "({}", self.on)?; + + for arg in self.args { + write!(f, " {}", arg)?; + } + + write!(f, ")") + } +} + +/// A function abstraction. +#[derive(Clone, Debug, Eq, PartialEq)] +pub struct Lambda { + pub args: Vec, + pub inner: Box, +} + +impl Display for Lambda { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "/")?; + let mut iter = self.args.iter(); + if let Some(arg) = iter.next() { + write!(f, "{}", arg)?; + + for arg in iter { + write!(f, ", {}", arg)?; + } + } + write!(f, "/ {}", self.inner) + } +} + +#[derive(Clone, Debug)] +pub enum Expression { + /// Matches the empty string. + Epsilon(Epsilon), + /// Matches the literal string. + Literal(Literal), + /// Matches one term followed by another. + Cat(Cat), + /// Matches either one term or another. + Alt(Alt), + /// The least fix point of a term. + Fix(Fix), + /// A fixed point variable. + Variable(Variable), + /// A function invocation. + Call(Call), + /// A function abstraction. + Lambda(Lambda), +} + +impl Expression { + pub fn try_into_lambda(self) -> Result { + if let Self::Lambda(l) = self { + Ok(l) + } else { + Err(self) + } + } +} + +impl Display for Expression { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match self { + Self::Epsilon(_) => write!(f, "_"), + Self::Literal(l) => l.fmt(f), + Self::Cat(c) => c.fmt(f), + Self::Alt(a) => a.fmt(f), + Self::Fix(x) => x.fmt(f), + Self::Variable(v) => v.fmt(f), + Self::Lambda(p) => p.fmt(f), + Self::Call(c) => c.fmt(f), + } + } +} + +impl PartialEq for Expression { + fn eq(&self, other: &Self) -> bool { + match self { + Self::Epsilon(_) => matches!(other, Self::Epsilon(_)), + Self::Literal(l) => { + if let Self::Literal(them) = other { + l == them + } else { + false + } + } + Self::Cat(c) => { + if let Self::Cat(them) = other { + c == them + } else { + false + } + } + Self::Alt(a) => { + if let Self::Alt(them) = other { + a == them + } else { + false + } + } + Self::Fix(f) => { + if let Self::Fix(them) = other { + f == them + } else { + false + } + } + Self::Variable(v) => { + if let Self::Variable(them) = other { + v == them + } else { + false + } + } + Self::Lambda(p) => { + if let Self::Lambda(them) = other { + p == them + } else { + false + } + } + Self::Call(c) => { + if let Self::Call(them) = other { + c == them + } else { + false + } + } + } + } +} + +impl Eq for Expression {} + +impl From for Expression { + fn from(eps: Epsilon) -> Self { + Self::Epsilon(eps) + } +} + +impl From for Expression { + fn from(lit: Literal) -> Self { + Self::Literal(lit) + } +} + +impl From for Expression { + fn from(cat: Cat) -> Self { + Self::Cat(cat) + } +} + +impl From for Expression { + fn from(alt: Alt) -> Self { + Self::Alt(alt) + } +} + +impl From for Expression { + fn from(fix: Fix) -> Self { + Self::Fix(fix) + } +} + +impl From for Expression { + fn from(var: Variable) -> Self { + Self::Variable(var) + } +} + +impl From for Expression { + fn from(lambda: Lambda) -> Self { + Self::Lambda(lambda) + } +} + +impl From for Expression { + fn from(call: Call) -> Self { + Self::Call(call) + } +} + +#[derive(Clone, Debug)] +pub struct NamedExpression { + pub name: Option, + pub expr: Expression, + pub span: Option, +} + +impl Display for NamedExpression { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match &self.name { + Some(name) => write!(f, "({} : {})", self.expr, name), + None => self.expr.fmt(f), + } + } +} + +impl PartialEq for NamedExpression { + fn eq(&self, other: &Self) -> bool { + self.expr == other.expr + } +} + +impl Eq for NamedExpression {} + +#[derive(Clone, Debug, Eq, PartialEq)] +pub struct Let { + pub name: Name, + pub val: NamedExpression, + pub inner: Box, +} + +#[derive(Clone, Debug, Eq, PartialEq)] +pub enum TopLevel { + Let(Let), + Goal(NamedExpression), +} diff --git a/src/chomp/ast-old/substitute.rs b/src/chomp/ast-old/substitute.rs new file mode 100644 index 0000000..80df588 --- /dev/null +++ b/src/chomp/ast-old/substitute.rs @@ -0,0 +1,412 @@ +use super::{ + error::TranslateError, Alt, Call, Cat, Epsilon, Fix, Lambda, Literal, NamedExpression, Variable, +}; +use crate::chomp::{ + visit::{Folder, Mapper, Visitable}, + Name, +}; +use proc_macro2::Span; + +struct Deepen { + pub depth: usize, + pub by: usize, +} + +impl Mapper for Deepen { + type Out = (); + + fn map_epsilon( + &mut self, + _name: &mut Option, + _span: Option, + _eps: &mut Epsilon, + ) -> Self::Out { + } + + fn map_literal( + &mut self, + _name: &mut Option, + _span: Option, + _lit: &mut Literal, + ) -> Self::Out { + } + + fn map_cat( + &mut self, + _name: &mut Option, + _span: Option, + cat: &mut Cat, + ) -> Self::Out { + cat.first.map(self); + for (_, other) in &mut cat.rest { + other.map(self); + } + } + + fn map_alt( + &mut self, + _name: &mut Option, + _span: Option, + alt: &mut Alt, + ) -> Self::Out { + alt.first.map(self); + for (_, other) in &mut alt.rest { + other.map(self); + } + } + + fn map_fix( + &mut self, + _name: &mut Option, + _span: Option, + fix: &mut Fix, + ) -> Self::Out { + fix.inner.map(self); + } + + fn map_variable( + &mut self, + _name: &mut Option, + _span: Option, + var: &mut Variable, + ) -> Self::Out { + if var.index >= self.depth { + var.index += self.by; + } + } + + fn map_call( + &mut self, + _name: &mut Option, + _span: Option, + call: &mut Call, + ) -> Self::Out { + call.on.map(self); + for arg in &mut call.args { + arg.map(self); + } + } + + fn map_lambda( + &mut self, + _name: &mut Option, + _span: Option, + lambda: &mut Lambda, + ) -> Self::Out { + self.depth += lambda.args.len(); + lambda.inner.map(self); + self.depth -= lambda.args.len(); + } +} + +pub struct Substitute { + pub index: usize, + pub expr: NamedExpression, +} + +impl Folder for Substitute { + type Out = NamedExpression; + + fn fold_epsilon(&mut self, name: Option, span: Option, eps: Epsilon) -> Self::Out { + NamedExpression { + name, + expr: eps.into(), + span, + } + } + + fn fold_literal(&mut self, name: Option, span: Option, lit: Literal) -> Self::Out { + NamedExpression { + name, + expr: lit.into(), + span, + } + } + + fn fold_cat(&mut self, name: Option, span: Option, mut cat: Cat) -> Self::Out { + cat.first = Box::new(cat.first.fold(self)); + cat.rest = cat + .rest + .into_iter() + .map(|(span, e)| (span, e.fold(self))) + .collect(); + NamedExpression { + name, + expr: cat.into(), + span, + } + } + + fn fold_alt(&mut self, name: Option, span: Option, mut alt: Alt) -> Self::Out { + alt.first = Box::new(alt.first.fold(self)); + alt.rest = alt + .rest + .into_iter() + .map(|(span, e)| (span, e.fold(self))) + .collect(); + NamedExpression { + name, + expr: alt.into(), + span, + } + } + + fn fold_fix(&mut self, name: Option, span: Option, mut fix: Fix) -> Self::Out { + fix.inner = Box::new(fix.inner.fold(self)); + NamedExpression { + name, + expr: fix.into(), + span, + } + } + + fn fold_variable( + &mut self, + name: Option, + span: Option, + var: Variable, + ) -> Self::Out { + if var.index == self.index { + self.expr.clone() + } else { + NamedExpression { + name, + expr: Variable { + index: if var.index > self.index { + var.index - 1 + } else { + var.index + }, + } + .into(), + span, + } + } + } + + fn fold_call(&mut self, name: Option, span: Option, mut call: Call) -> Self::Out { + call.on = Box::new(call.on.fold(self)); + call.args = call.args.into_iter().map(|e| e.fold(self)).collect(); + NamedExpression { + name, + expr: call.into(), + span, + } + } + + fn fold_lambda( + &mut self, + name: Option, + span: Option, + mut lambda: Lambda, + ) -> Self::Out { + self.index += lambda.args.len(); + lambda.inner = Box::new(lambda.inner.fold(self)); + self.index -= lambda.args.len(); + NamedExpression { + name, + expr: lambda.into(), + span, + } + } +} + +pub struct Translate { + changed: bool, +} + +impl Translate { + pub fn new() -> Self { + Self { changed: false } + } +} + +impl Default for Translate { + fn default() -> Self { + Self::new() + } +} + +impl Folder for Translate { + type Out = Result; + + fn fold_epsilon(&mut self, name: Option, span: Option, eps: Epsilon) -> Self::Out { + Ok(NamedExpression { + name, + expr: eps.into(), + span, + }) + } + + fn fold_literal(&mut self, name: Option, span: Option, lit: Literal) -> Self::Out { + Ok(NamedExpression { + name, + expr: lit.into(), + span, + }) + } + + fn fold_cat(&mut self, name: Option, span: Option, cat: Cat) -> Self::Out { + Ok(NamedExpression { + name, + expr: cat.into(), + span, + }) + } + + fn fold_alt(&mut self, name: Option, span: Option, alt: Alt) -> Self::Out { + Ok(NamedExpression { + name, + expr: alt.into(), + span, + }) + } + + fn fold_fix(&mut self, name: Option, span: Option, fix: Fix) -> Self::Out { + Ok(NamedExpression { + name, + expr: fix.into(), + span, + }) + } + + fn fold_variable( + &mut self, + name: Option, + span: Option, + var: Variable, + ) -> Self::Out { + Ok(NamedExpression { + name, + expr: var.into(), + span, + }) + } + + fn fold_call(&mut self, name: Option, span: Option, call: Call) -> Self::Out { + let mut on = *call.on; + self.changed = true; + while self.changed { + self.changed = false; + on = on.fold(self)?; + } + + let lambda = on + .expr + .try_into_lambda() + .map_err(|on| TranslateError::CallNotAFunction { on, span })?; + + if lambda.args.len() != call.args.len() { + return Err(TranslateError::WrongArgCount { + lambda, + args: call.args, + span, + }); + } + + let mut out = *lambda.inner; + + for ((i, mut arg), name) in call.args.into_iter().enumerate().zip(lambda.args).rev() { + arg.name = arg.name.or(Some(name)); + arg.map(&mut Deepen { depth: 0, by: i }); + out = out.fold(&mut Substitute { + index: 0, + expr: arg, + }); + } + + self.changed = true; + while self.changed { + self.changed = false; + out = out.fold(self)?; + } + + self.changed = true; + out.name = name.or(out.name); + out.span = span.or(out.span); + Ok(out) + } + + fn fold_lambda(&mut self, name: Option, span: Option, lambda: Lambda) -> Self::Out { + Ok(NamedExpression { + name, + expr: lambda.into(), + span, + }) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + /// Returns (/x/ x) 'index + fn make_expr(index: usize) -> NamedExpression { + let var = NamedExpression { + name: None, + expr: Variable { index: 0 }.into(), + span: None, + }; + + let lambda = NamedExpression { + name: None, + expr: Lambda { + args: vec!["x".to_owned().into()], + inner: Box::new(var), + } + .into(), + span: None, + }; + + let var = NamedExpression { + name: None, + expr: Variable { index }.into(), + span: None, + }; + + NamedExpression { + name: None, + expr: Call { + on: Box::new(lambda), + args: vec![var], + } + .into(), + span: None, + } + } + + #[test] + fn deepen_lambda() { + let mut expr = make_expr(0); + expr.map(&mut Deepen { depth: 0, by: 1 }); + assert_eq!(expr, make_expr(1)) + } + + #[test] + fn substitute_renames_bigger() { + let expr = make_expr(1); + let expr = expr.fold(&mut Substitute { + index: 0, + expr: NamedExpression { + name: None, + expr: Epsilon.into(), + span: None, + }, + }); + assert_eq!(expr, make_expr(0)) + } + + #[test] + fn translate_lambda() { + let expr = make_expr(1); + let expr = expr.fold(&mut Translate::new()).unwrap(); + assert_eq!( + expr, + NamedExpression { + name: Some("x".to_owned().into()), + expr: Variable { index: 1 }.into(), + span: None + } + ) + } +} -- cgit v1.2.3