summaryrefslogtreecommitdiff
path: root/src/chomp/ast
diff options
context:
space:
mode:
Diffstat (limited to 'src/chomp/ast')
-rw-r--r--src/chomp/ast/error.rs64
-rw-r--r--src/chomp/ast/mod.rs36
-rw-r--r--src/chomp/ast/substitute.rs447
3 files changed, 255 insertions, 292 deletions
diff --git a/src/chomp/ast/error.rs b/src/chomp/ast/error.rs
index 9e4282b..9057ec3 100644
--- a/src/chomp/ast/error.rs
+++ b/src/chomp/ast/error.rs
@@ -1,68 +1,52 @@
+use super::{Expression, Lambda, NamedExpression};
+use proc_macro2::Span;
use std::{
error::Error,
fmt::{self, Display},
};
-use proc_macro2::Span;
-
-use crate::chomp::Name;
-
-use super::{Call, Parameter};
-
#[derive(Debug)]
-pub enum SubstituteError {
- FreeParameter {
- param: Parameter,
+pub enum TranslateError {
+ CallNotAFunction {
+ on: Expression,
span: Option<Span>,
- name: Option<Name>,
},
WrongArgCount {
- call: Call,
- expected: usize,
+ lambda: Lambda,
+ args: Vec<NamedExpression>,
span: Option<Span>,
},
}
-impl From<SubstituteError> for syn::Error {
- fn from(e: SubstituteError) -> Self {
+impl From<TranslateError> for syn::Error {
+ fn from(e: TranslateError) -> Self {
let msg = e.to_string();
let span = match e {
- SubstituteError::FreeParameter { span, .. }
- | SubstituteError::WrongArgCount { span, .. } => span,
+ TranslateError::CallNotAFunction { span, .. }
+ | TranslateError::WrongArgCount { span, .. } => span,
};
Self::new(span.unwrap_or_else(Span::call_site), msg)
}
}
-impl Display for SubstituteError {
+impl Display for TranslateError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
- Self::FreeParameter { param, name, .. } => {
- if let Some(name) = name {
- write!(f, "unbound parameter: `{}`", name)
- } else {
- write!(f, "unbound parameter: '{}", param.index)
- }
- }
- Self::WrongArgCount { call, expected, .. } => {
- if call.args.len() == 1 {
- write!(
- f,
- "this function takes {} arguments but 1 was supplied",
- expected
- )
- } else {
- write!(
- f,
- "this function takes {} arguments but {} were supplied",
- expected,
- call.args.len()
- )
- }
+ 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 SubstituteError {}
+impl Error for TranslateError {}
diff --git a/src/chomp/ast/mod.rs b/src/chomp/ast/mod.rs
index d833da4..232381a 100644
--- a/src/chomp/ast/mod.rs
+++ b/src/chomp/ast/mod.rs
@@ -116,16 +116,20 @@ impl Display for Call {
/// A function abstraction.
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Lambda {
- pub first: Name,
- pub rest: Vec<Name>,
+ pub args: Vec<Name>,
pub inner: Box<NamedExpression>,
}
impl Display for Lambda {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
- write!(f, "/{}", self.first)?;
- for name in self.rest {
- write!(f, ", {}", name)?;
+ 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)
}
@@ -151,6 +155,16 @@ pub enum Expression {
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 {
@@ -297,23 +311,15 @@ impl PartialEq for NamedExpression {
impl Eq for NamedExpression {}
-#[derive(Clone, Debug)]
+#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Let {
pub name: Name,
pub val: NamedExpression,
pub inner: Box<TopLevel>,
}
-#[derive(Clone, Debug)]
+#[derive(Clone, Debug, Eq, PartialEq)]
pub enum TopLevel {
Let(Let),
Goal(NamedExpression),
}
-
-impl PartialEq for Function {
- fn eq(&self, other: &Self) -> bool {
- self.name == other.name && self.params == other.params && self.expr == other.expr
- }
-}
-
-impl Eq for Function {}
diff --git a/src/chomp/ast/substitute.rs b/src/chomp/ast/substitute.rs
index 2008a15..80df588 100644
--- a/src/chomp/ast/substitute.rs
+++ b/src/chomp/ast/substitute.rs
@@ -1,21 +1,18 @@
-use proc_macro2::Span;
-
+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;
-use super::{
- error::SubstituteError, Alt, Call, Cat, Epsilon, Fix, Function, Literal, NamedExpression,
- Parameter, Variable,
-};
-
-#[derive(Clone, Copy, Debug, Default)]
-pub struct DeepenVars {
+struct Deepen {
pub depth: usize,
+ pub by: usize,
}
-impl Mapper for DeepenVars {
+impl Mapper for Deepen {
type Out = ();
fn map_epsilon(
@@ -41,10 +38,8 @@ impl Mapper for DeepenVars {
cat: &mut Cat,
) -> Self::Out {
cat.first.map(self);
- cat.second.map(self);
-
- for (_, term) in &mut cat.rest {
- term.map(self);
+ for (_, other) in &mut cat.rest {
+ other.map(self);
}
}
@@ -55,10 +50,8 @@ impl Mapper for DeepenVars {
alt: &mut Alt,
) -> Self::Out {
alt.first.map(self);
- alt.second.map(self);
-
- for (_, term) in &mut alt.rest {
- term.map(self);
+ for (_, other) in &mut alt.rest {
+ other.map(self);
}
}
@@ -68,9 +61,7 @@ impl Mapper for DeepenVars {
_span: Option<Span>,
fix: &mut Fix,
) -> Self::Out {
- self.depth += 1;
fix.inner.map(self);
- self.depth -= 1;
}
fn map_variable(
@@ -80,194 +71,93 @@ impl Mapper for DeepenVars {
var: &mut Variable,
) -> Self::Out {
if var.index >= self.depth {
- var.index += 1;
+ var.index += self.by;
}
}
- fn map_parameter(
- &mut self,
- _name: &mut Option<Name>,
- _span: Option<Span>,
- _param: &mut Parameter,
- ) -> Self::Out {
- }
-
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)
+ arg.map(self);
}
}
-}
-
-#[derive(Clone, Copy, Debug, Default)]
-pub struct ShallowVars {
- pub depth: usize,
-}
-
-impl Mapper for ShallowVars {
- 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(
+ fn map_lambda(
&mut self,
_name: &mut Option<Name>,
_span: Option<Span>,
- cat: &mut Cat,
- ) -> Self::Out {
- cat.first.map(self);
- cat.second.map(self);
-
- for (_, term) in &mut cat.rest {
- term.map(self);
- }
- }
-
- fn map_alt(
- &mut self,
- _name: &mut Option<Name>,
- _span: Option<Span>,
- alt: &mut Alt,
- ) -> Self::Out {
- alt.first.map(self);
- alt.second.map(self);
-
- for (_, term) in &mut alt.rest {
- term.map(self);
- }
- }
-
- fn map_fix(
- &mut self,
- _name: &mut Option<Name>,
- _span: Option<Span>,
- fix: &mut Fix,
- ) -> Self::Out {
- self.depth += 1;
- fix.inner.map(self);
- self.depth -= 1;
- }
-
- fn map_variable(
- &mut self,
- _name: &mut Option<Name>,
- _span: Option<Span>,
- var: &mut Variable,
- ) -> Self::Out {
- if var.index >= self.depth {
- var.index -= 1;
- }
- }
-
- fn map_parameter(
- &mut self,
- _name: &mut Option<Name>,
- _span: Option<Span>,
- _param: &mut Parameter,
- ) -> Self::Out {
- }
-
- fn map_call(
- &mut self,
- _name: &mut Option<Name>,
- _span: Option<Span>,
- call: &mut Call,
+ lambda: &mut Lambda,
) -> Self::Out {
- for arg in &mut call.args {
- arg.map(self)
- }
+ self.depth += lambda.args.len();
+ lambda.inner.map(self);
+ self.depth -= lambda.args.len();
}
}
-#[derive(Clone, Debug)]
-pub struct SubstituteParams {
- pub params: Vec<NamedExpression>,
+pub struct Substitute {
+ pub index: usize,
+ pub expr: NamedExpression,
}
-impl Folder for SubstituteParams {
- type Out = Result<NamedExpression, SubstituteError>;
+impl Folder for Substitute {
+ type Out = NamedExpression;
fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out {
- Ok(NamedExpression {
+ NamedExpression {
name,
expr: eps.into(),
span,
- })
+ }
}
fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out {
- Ok(NamedExpression {
+ 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.second = Box::new(cat.second.fold(self)?);
+ cat.first = Box::new(cat.first.fold(self));
cat.rest = cat
.rest
.into_iter()
- .map(|(p, term)| Ok((p, term.fold(self)?)))
- .collect::<Result<_, _>>()?;
- Ok(NamedExpression {
+ .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.second = Box::new(alt.second.fold(self)?);
+ alt.first = Box::new(alt.first.fold(self));
alt.rest = alt
.rest
.into_iter()
- .map(|(p, term)| Ok((p, term.fold(self)?)))
- .collect::<Result<_, _>>()?;
- Ok(NamedExpression {
+ .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 {
- for param in &mut self.params {
- param.map(&mut DeepenVars::default());
- }
-
- fix.inner = Box::new(fix.inner.fold(self)?);
-
- for param in &mut self.params {
- param.map(&mut ShallowVars::default());
- }
-
- Ok(NamedExpression {
+ fix.inner = Box::new(fix.inner.fold(self));
+ NamedExpression {
name,
expr: fix.into(),
span,
- })
+ }
}
fn fold_variable(
@@ -276,50 +166,69 @@ impl Folder for SubstituteParams {
span: Option<Span>,
var: Variable,
) -> Self::Out {
- Ok(NamedExpression {
+ 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: var.into(),
+ expr: call.into(),
span,
- })
+ }
}
- fn fold_parameter(
+ fn fold_lambda(
&mut self,
name: Option<Name>,
span: Option<Span>,
- param: Parameter,
+ mut lambda: Lambda,
) -> Self::Out {
- let mut expr = self
- .params
- .get(param.index)
- .cloned()
- .ok_or_else(|| SubstituteError::FreeParameter { param, span, name: name.clone() })?;
- expr.name = expr.name.or(name);
- expr.span = expr.span.or(span);
- Ok(expr)
- }
-
- fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, mut call: Call) -> Self::Out {
- call.args = call
- .args
- .into_iter()
- .map(|arg| arg.fold(self))
- .collect::<Result<_, _>>()?;
- Ok(NamedExpression {
+ self.index += lambda.args.len();
+ lambda.inner = Box::new(lambda.inner.fold(self));
+ self.index -= lambda.args.len();
+ NamedExpression {
name,
- expr: call.into(),
+ expr: lambda.into(),
span,
- })
+ }
}
}
-#[derive(Clone, Debug)]
-pub struct InlineCalls {
- pub function: Function,
+pub struct Translate {
+ changed: bool,
}
-impl Folder for InlineCalls {
- type Out = Result<NamedExpression, SubstituteError>;
+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 {
@@ -337,15 +246,7 @@ impl Folder for InlineCalls {
})
}
- 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.second = Box::new(cat.second.fold(self)?);
- cat.rest = cat
- .rest
- .into_iter()
- .map(|(punct, term)| Ok((punct, term.fold(self)?)))
- .collect::<Result<_, _>>()?;
-
+ fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Out {
Ok(NamedExpression {
name,
expr: cat.into(),
@@ -353,15 +254,7 @@ impl Folder for InlineCalls {
})
}
- 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.second = Box::new(alt.second.fold(self)?);
- alt.rest = alt
- .rest
- .into_iter()
- .map(|(punct, term)| Ok((punct, term.fold(self)?)))
- .collect::<Result<_, _>>()?;
-
+ fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Out {
Ok(NamedExpression {
name,
expr: alt.into(),
@@ -369,9 +262,7 @@ impl Folder for InlineCalls {
})
}
- fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, mut fix: Fix) -> Self::Out {
- fix.inner = Box::new(fix.inner.fold(self)?);
-
+ fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Out {
Ok(NamedExpression {
name,
expr: fix.into(),
@@ -392,48 +283,130 @@ impl Folder for InlineCalls {
})
}
- fn fold_parameter(
- &mut self,
- name: Option<Name>,
- span: Option<Span>,
- param: Parameter,
- ) -> Self::Out {
+ 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: param.into(),
+ expr: lambda.into(),
span,
})
}
+}
- fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, mut call: Call) -> Self::Out {
- call.args = call
- .args
- .into_iter()
- .map(|arg| arg.fold(self))
- .collect::<Result<_, _>>()?;
-
- if call.name != self.function.name {
- Ok(NamedExpression {
- name,
- expr: call.into(),
- span,
- })
- } else if call.args.len() == self.function.params.len() {
- let mut expr = self
- .function
- .expr
- .clone()
- .fold(&mut SubstituteParams { params: call.args })?;
- expr.name = Some(name.or(expr.name).unwrap_or(call.name));
- expr.span = span.or(expr.span);
-
- Ok(expr)
- } else {
- Err(SubstituteError::WrongArgCount {
- call,
- expected: self.function.params.len(),
- 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 15:39:38 +0000