Introduce lambda expressions.

1 files changed, 149 insertions, 80 deletions

diff --git a/src/chomp/ast/substitute.rs b/src/chomp/ast/substitute.rs
index 80df588..c6d3ef6 100644
--- a/src/chomp/ast/substitute.rs
+++ b/src/chomp/ast/substitute.rs
@@ -1,24 +1,32 @@
+use std::array;
+
 use super::{
-    error::TranslateError, Alt, Call, Cat, Epsilon, Fix, Lambda, Literal, NamedExpression, Variable,
+    error::ReductionError, Alt, Call, Cat, Epsilon, Expression, Fix, Lambda, Let, Literal,
+    NamedExpression, Variable,
 };
 use crate::chomp::{
+    name::Name,
     visit::{Folder, Mapper, Visitable},
-    Name,
 };
 use proc_macro2::Span;
 
-struct Deepen {
-    pub depth: usize,
-    pub by: usize,
+enum Direction {
+    Deepen,
+    Shallow,
+}
+struct RenameVars {
+    depth: usize,
+    by: usize,
+    direction: Direction,
 }
 
-impl Mapper for Deepen {
+impl Mapper for RenameVars {
     type Out = ();
 
     fn map_epsilon(
         &mut self,
         _name: &mut Option<Name>,
-        _span: Option<Span>,
+        _span: Span,
         _eps: &mut Epsilon,
     ) -> Self::Out {
     }
@@ -26,7 +34,7 @@ impl Mapper for Deepen {
     fn map_literal(
         &mut self,
         _name: &mut Option<Name>,
-        _span: Option<Span>,
+        _span: Span,
         _lit: &mut Literal,
     ) -> Self::Out {
     }
@@ -34,7 +42,7 @@ impl Mapper for Deepen {
     fn map_cat(
         &mut self,
         _name: &mut Option<Name>,
-        _span: Option<Span>,
+        _span: Span,
         cat: &mut Cat,
     ) -> Self::Out {
         cat.first.map(self);
@@ -46,7 +54,7 @@ impl Mapper for Deepen {
     fn map_alt(
         &mut self,
         _name: &mut Option<Name>,
-        _span: Option<Span>,
+        _span: Span,
         alt: &mut Alt,
     ) -> Self::Out {
         alt.first.map(self);
@@ -58,7 +66,7 @@ impl Mapper for Deepen {
     fn map_fix(
         &mut self,
         _name: &mut Option<Name>,
-        _span: Option<Span>,
+        _span: Span,
         fix: &mut Fix,
     ) -> Self::Out {
         fix.inner.map(self);
@@ -67,18 +75,21 @@ impl Mapper for Deepen {
     fn map_variable(
         &mut self,
         _name: &mut Option<Name>,
-        _span: Option<Span>,
+        _span: Span,
         var: &mut Variable,
     ) -> Self::Out {
         if var.index >= self.depth {
-            var.index += self.by;
+            match self.direction {
+                Direction::Deepen => var.index += self.by,
+                Direction::Shallow => var.index -= self.by,
+            }
         }
     }
 
     fn map_call(
         &mut self,
         _name: &mut Option<Name>,
-        _span: Option<Span>,
+        _span: Span,
         call: &mut Call,
     ) -> Self::Out {
         call.on.map(self);
@@ -90,24 +101,56 @@ impl Mapper for Deepen {
     fn map_lambda(
         &mut self,
         _name: &mut Option<Name>,
-        _span: Option<Span>,
+        _span: Span,
         lambda: &mut Lambda,
     ) -> Self::Out {
         self.depth += lambda.args.len();
         lambda.inner.map(self);
         self.depth -= lambda.args.len();
     }
+
+    fn map_let(
+        &mut self,
+        _name: &mut Option<Name>,
+        _span: Span,
+        stmt: &mut Let,
+    ) -> Self::Out {
+        stmt.bound.map(self);
+        self.depth += 1;
+        stmt.body.map(self);
+        self.depth -= 1;
+    }
 }
 
+#[derive(Debug)]
 pub struct Substitute {
     pub index: usize,
     pub expr: NamedExpression,
 }
 
+impl Substitute {
+    fn with_args<V: Visitable>(&mut self, args: usize, visitable: V) -> <Self as Folder>::Out {
+        self.index += args;
+        self.expr.map(&mut RenameVars {
+            depth: 0,
+            by: args,
+            direction: Direction::Deepen,
+        });
+        let out = visitable.fold(self);
+        self.expr.map(&mut RenameVars {
+            depth: 0,
+            by: args,
+            direction: Direction::Shallow,
+        });
+        self.index -= args;
+        out
+    }
+}
+
 impl Folder for Substitute {
     type Out = NamedExpression;
 
-    fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out {
+    fn fold_epsilon(&mut self, name: Option<Name>, span: Span, eps: Epsilon) -> Self::Out {
         NamedExpression {
             name,
             expr: eps.into(),
@@ -115,7 +158,7 @@ impl Folder for Substitute {
         }
     }
 
-    fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out {
+    fn fold_literal(&mut self, name: Option<Name>, span: Span, lit: Literal) -> Self::Out {
         NamedExpression {
             name,
             expr: lit.into(),
@@ -123,7 +166,7 @@ impl Folder for Substitute {
         }
     }
 
-    fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, mut cat: Cat) -> Self::Out {
+    fn fold_cat(&mut self, name: Option<Name>, span: Span, mut cat: Cat) -> Self::Out {
         cat.first = Box::new(cat.first.fold(self));
         cat.rest = cat
             .rest
@@ -137,7 +180,7 @@ impl Folder for Substitute {
         }
     }
 
-    fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, mut alt: Alt) -> Self::Out {
+    fn fold_alt(&mut self, name: Option<Name>, span: Span, mut alt: Alt) -> Self::Out {
         alt.first = Box::new(alt.first.fold(self));
         alt.rest = alt
             .rest
@@ -151,7 +194,7 @@ impl Folder for Substitute {
         }
     }
 
-    fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, mut fix: Fix) -> Self::Out {
+    fn fold_fix(&mut self, name: Option<Name>, span: Span, mut fix: Fix) -> Self::Out {
         fix.inner = Box::new(fix.inner.fold(self));
         NamedExpression {
             name,
@@ -163,11 +206,13 @@ impl Folder for Substitute {
     fn fold_variable(
         &mut self,
         name: Option<Name>,
-        span: Option<Span>,
+        span: Span,
         var: Variable,
     ) -> Self::Out {
         if var.index == self.index {
-            self.expr.clone()
+            let mut out = self.expr.clone();
+            out.name = Name::merge(out.name, name);
+            out
         } else {
             NamedExpression {
                 name,
@@ -184,7 +229,7 @@ impl Folder for Substitute {
         }
     }
 
-    fn fold_call(&mut self, name: Option<Name>, span: Option<Span>, mut call: Call) -> Self::Out {
+    fn fold_call(&mut self, name: Option<Name>, span: 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 {
@@ -197,40 +242,36 @@ impl Folder for Substitute {
     fn fold_lambda(
         &mut self,
         name: Option<Name>,
-        span: Option<Span>,
+        span: Span,
         mut lambda: Lambda,
     ) -> Self::Out {
-        self.index += lambda.args.len();
-        lambda.inner = Box::new(lambda.inner.fold(self));
-        self.index -= lambda.args.len();
+        let depth = lambda.args.len();
+        lambda.inner = Box::new(self.with_args(depth, lambda.inner));
         NamedExpression {
             name,
             expr: lambda.into(),
             span,
         }
     }
-}
 
-pub struct Translate {
-    changed: bool,
-}
-
-impl Translate {
-    pub fn new() -> Self {
-        Self { changed: false }
+    fn fold_let(&mut self, name: Option<Name>, span: Span, mut stmt: Let) -> Self::Out {
+        stmt.bound = Box::new(stmt.bound.fold(self));
+        stmt.body = Box::new(self.with_args(1, stmt.body));
+        NamedExpression {
+            name,
+            expr: stmt.into(),
+            span,
+        }
     }
 }
 
-impl Default for Translate {
-    fn default() -> Self {
-        Self::new()
-    }
-}
+#[derive(Copy, Clone, Debug)]
+pub struct Reduce;
 
-impl Folder for Translate {
-    type Out = Result<NamedExpression, TranslateError>;
+impl Folder for Reduce {
+    type Out = Result<NamedExpression, ReductionError>;
 
-    fn fold_epsilon(&mut self, name: Option<Name>, span: Option<Span>, eps: Epsilon) -> Self::Out {
+    fn fold_epsilon(&mut self, name: Option<Name>, span: Span, eps: Epsilon) -> Self::Out {
         Ok(NamedExpression {
             name,
             expr: eps.into(),
@@ -238,7 +279,7 @@ impl Folder for Translate {
         })
     }
 
-    fn fold_literal(&mut self, name: Option<Name>, span: Option<Span>, lit: Literal) -> Self::Out {
+    fn fold_literal(&mut self, name: Option<Name>, span: Span, lit: Literal) -> Self::Out {
         Ok(NamedExpression {
             name,
             expr: lit.into(),
@@ -246,7 +287,13 @@ impl Folder for Translate {
         })
     }
 
-    fn fold_cat(&mut self, name: Option<Name>, span: Option<Span>, cat: Cat) -> Self::Out {
+    fn fold_cat(&mut self, name: Option<Name>, span: Span, mut cat: Cat) -> Self::Out {
+        cat.first = Box::new(cat.first.fold(self)?);
+        cat.rest = cat
+            .rest
+            .into_iter()
+            .map(|(p, e)| Ok((p, e.fold(self)?)))
+            .collect::<Result<_, _>>()?;
         Ok(NamedExpression {
             name,
             expr: cat.into(),
@@ -254,7 +301,13 @@ impl Folder for Translate {
         })
     }
 
-    fn fold_alt(&mut self, name: Option<Name>, span: Option<Span>, alt: Alt) -> Self::Out {
+    fn fold_alt(&mut self, name: Option<Name>, span: Span, mut alt: Alt) -> Self::Out {
+        alt.first = Box::new(alt.first.fold(self)?);
+        alt.rest = alt
+            .rest
+            .into_iter()
+            .map(|(p, e)| Ok((p, e.fold(self)?)))
+            .collect::<Result<_, _>>()?;
         Ok(NamedExpression {
             name,
             expr: alt.into(),
@@ -262,7 +315,13 @@ impl Folder for Translate {
         })
     }
 
-    fn fold_fix(&mut self, name: Option<Name>, span: Option<Span>, fix: Fix) -> Self::Out {
+    fn fold_fix(&mut self, name: Option<Name>, span: Span, mut fix: Fix) -> Self::Out {
+        let mut inner = fix.inner.fold(self)?;
+        if let Expression::Lambda(mut l) = inner.expr {
+            l.inner = Box::new(l.inner.fold(self)?);
+            inner.expr = Expression::Lambda(l);
+        }
+        fix.inner = Box::new(inner);
         Ok(NamedExpression {
             name,
             expr: fix.into(),
@@ -273,7 +332,7 @@ impl Folder for Translate {
     fn fold_variable(
         &mut self,
         name: Option<Name>,
-        span: Option<Span>,
+        span: Span,
         var: Variable,
     ) -> Self::Out {
         Ok(NamedExpression {
@@ -283,21 +342,16 @@ impl Folder for Translate {
         })
     }
 
-    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)?;
-        }
+    fn fold_call(&mut self, name: Option<Name>, span: Span, call: Call) -> Self::Out {
+        let on = call.on.fold(self)?;
 
         let lambda = on
             .expr
             .try_into_lambda()
-            .map_err(|on| TranslateError::CallNotAFunction { on, span })?;
+            .map_err(|on| ReductionError::CallNotAFunction { on, span })?;
 
         if lambda.args.len() != call.args.len() {
-            return Err(TranslateError::WrongArgCount {
+            return Err(ReductionError::WrongArgCount {
                 lambda,
                 args: call.args,
                 span,
@@ -307,33 +361,44 @@ impl Folder for Translate {
         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 });
+            arg.name = Name::merge(arg.name, Some(name));
+            arg.map(&mut RenameVars {
+                depth: 0,
+                by: i,
+                direction: Direction::Deepen,
+            });
             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);
+        out = out.fold(self)?;
+        out.name = Name::merge_all(array::IntoIter::new([name, on.name, out.name]));
+        out.span = span;
         Ok(out)
     }
 
-    fn fold_lambda(&mut self, name: Option<Name>, span: Option<Span>, lambda: Lambda) -> Self::Out {
+    fn fold_lambda(&mut self, name: Option<Name>, span: Span, lambda: Lambda) -> Self::Out {
         Ok(NamedExpression {
             name,
             expr: lambda.into(),
             span,
         })
     }
+
+    fn fold_let(&mut self, name: Option<Name>, span: Span, stmt: Let) -> Self::Out {
+        let mut out = stmt
+            .body
+            .fold(&mut Substitute {
+                index: 0,
+                expr: *stmt.bound,
+            })
+            .fold(self)?;
+        out.name = Name::merge(out.name, name);
+        out.span = span;
+        Ok(out)
+    }
 }
 
 #[cfg(test)]
@@ -345,23 +410,23 @@ mod tests {
         let var = NamedExpression {
             name: None,
             expr: Variable { index: 0 }.into(),
-            span: None,
+            span: Span::call_site(),
         };
 
         let lambda = NamedExpression {
             name: None,
             expr: Lambda {
-                args: vec!["x".to_owned().into()],
+                args: vec![Name::new_variable("x".to_owned())],
                 inner: Box::new(var),
             }
             .into(),
-            span: None,
+            span: Span::call_site(),
         };
 
         let var = NamedExpression {
             name: None,
             expr: Variable { index }.into(),
-            span: None,
+            span: Span::call_site(),
         };
 
         NamedExpression {
@@ -371,14 +436,18 @@ mod tests {
                 args: vec![var],
             }
             .into(),
-            span: None,
+            span: Span::call_site(),
         }
     }
 
     #[test]
     fn deepen_lambda() {
         let mut expr = make_expr(0);
-        expr.map(&mut Deepen { depth: 0, by: 1 });
+        expr.map(&mut RenameVars {
+            depth: 0,
+            by: 1,
+            direction: Direction::Deepen,
+        });
         assert_eq!(expr, make_expr(1))
     }
 
@@ -390,22 +459,22 @@ mod tests {
             expr: NamedExpression {
                 name: None,
                 expr: Epsilon.into(),
-                span: None,
+                span: Span::call_site(),
             },
         });
         assert_eq!(expr, make_expr(0))
     }
 
     #[test]
-    fn translate_lambda() {
+    fn reduce_lambda() {
         let expr = make_expr(1);
-        let expr = expr.fold(&mut Translate::new()).unwrap();
+        let expr = expr.fold(&mut Reduce).unwrap();
         assert_eq!(
             expr,
             NamedExpression {
-                name: Some("x".to_owned().into()),
+                name: Some(Name::new_variable("x".to_owned())),
                 expr: Variable { index: 1 }.into(),
-                span: None
+                span: Span::call_site(),
             }
         )
     }