summaryrefslogtreecommitdiff
path: root/src/chomp/ast-old
diff options
context:
space:
mode:
Diffstat (limited to 'src/chomp/ast-old')
-rw-r--r--src/chomp/ast-old/error.rs52
-rw-r--r--src/chomp/ast-old/mod.rs325
-rw-r--r--src/chomp/ast-old/substitute.rs412
3 files changed, 789 insertions, 0 deletions
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<Span>,
+ },
+ WrongArgCount {
+ lambda: Lambda,
+ args: Vec<NamedExpression>,
+ span: Option<Span>,
+ },
+}
+
+impl From<TranslateError> 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<NamedExpression>,
+ pub rest: Vec<(Option<Span>, 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<NamedExpression>,
+ pub rest: Vec<(Option<Span>, 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<NamedExpression>,
+}
+
+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<NamedExpression>,
+ pub args: Vec<NamedExpression>,
+}
+
+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<Name>,
+ pub inner: Box<NamedExpression>,
+}
+
+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<Lambda, Self> {
+ 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<Epsilon> for Expression {
+ fn from(eps: Epsilon) -> Self {
+ Self::Epsilon(eps)
+ }
+}
+
+impl From<Literal> for Expression {
+ fn from(lit: Literal) -> Self {
+ Self::Literal(lit)
+ }
+}
+
+impl From<Cat> for Expression {
+ fn from(cat: Cat) -> Self {
+ Self::Cat(cat)
+ }
+}
+
+impl From<Alt> for Expression {
+ fn from(alt: Alt) -> Self {
+ Self::Alt(alt)
+ }
+}
+
+impl From<Fix> for Expression {
+ fn from(fix: Fix) -> Self {
+ Self::Fix(fix)
+ }
+}
+
+impl From<Variable> for Expression {
+ fn from(var: Variable) -> Self {
+ Self::Variable(var)
+ }
+}
+
+impl From<Lambda> for Expression {
+ fn from(lambda: Lambda) -> Self {
+ Self::Lambda(lambda)
+ }
+}
+
+impl From<Call> for Expression {
+ fn from(call: Call) -> Self {
+ Self::Call(call)
+ }
+}
+
+#[derive(Clone, Debug)]
+pub struct NamedExpression {
+ pub name: Option<Name>,
+ pub expr: Expression,
+ pub span: Option<Span>,
+}
+
+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<TopLevel>,
+}
+
+#[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<Name>,
+ _span: Option<Span>,
+ _eps: &mut Epsilon,
+ ) -> Self::Out {
+ }
+
+ fn map_literal(
+ &mut self,
+ _name: &mut Option<Name>,
+ _span: Option<Span>,
+ _lit: &mut Literal,
+ ) -> Self::Out {
+ }
+
+ fn map_cat(
+ &mut self,
+ _name: &mut Option<Name>,
+ _span: Option<Span>,
+ 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<Name>,
+ _span: Option<Span>,
+ 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<Name>,
+ _span: Option<Span>,
+ fix: &mut Fix,
+ ) -> Self::Out {
+ fix.inner.map(self);
+ }
+
+ fn map_variable(
+ &mut self,
+ _name: &mut Option<Name>,
+ _span: Option<Span>,
+ var: &mut Variable,
+ ) -> Self::Out {
+ if var.index >= self.depth {
+ var.index += self.by;
+ }
+ }
+
+ fn map_call(
+ &mut self,
+ _name: &mut Option<Name>,
+ _span: Option<Span>,
+ 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<Name>,
+ _span: Option<Span>,
+ 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<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out {
+ NamedExpression {
+ name,
+ expr: eps.into(),
+ span,
+ }
+ }
+
+ fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out {
+ NamedExpression {
+ name,
+ expr: lit.into(),
+ span,
+ }
+ }
+
+ fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, 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<Name>, span: Option<Span>, 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<Name>, span: Option<Span>, 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<Name>,
+ span: Option<Span>,
+ 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<Name>, span: Option<Span>, 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<Name>,
+ span: Option<Span>,
+ 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<NamedExpression, TranslateError>;
+
+ fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out {
+ Ok(NamedExpression {
+ name,
+ expr: eps.into(),
+ span,
+ })
+ }
+
+ fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out {
+ Ok(NamedExpression {
+ name,
+ expr: lit.into(),
+ span,
+ })
+ }
+
+ fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Out {
+ Ok(NamedExpression {
+ name,
+ expr: cat.into(),
+ span,
+ })
+ }
+
+ fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Out {
+ Ok(NamedExpression {
+ name,
+ expr: alt.into(),
+ span,
+ })
+ }
+
+ fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Out {
+ Ok(NamedExpression {
+ name,
+ expr: fix.into(),
+ span,
+ })
+ }
+
+ fn fold_variable(
+ &mut self,
+ name: Option<Name>,
+ span: Option<Span>,
+ var: Variable,
+ ) -> Self::Out {
+ Ok(NamedExpression {
+ name,
+ expr: var.into(),
+ span,
+ })
+ }
+
+ fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, 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<Name>, span: Option<Span>, 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
+ }
+ )
+ }
+}
generated by cgit v1.2.3 (git 2.49.0) at 2025-04-30 11:59:13 +0000