Repository: tweag/nickel
Pull request #248 (2020-12-14 12:01:02)

Eliminate the inner terms of primitive operators 1: Switch
Depend on #247. Since we're at it, let us continue what we started for equality in #247: do not store additional state and/or parameters internally inside primitive operators themselves, but rather use the stack.

The goal is to eventually get rid of the dependency of `UnaryOp<CapturedTerm>/BinaryOp<CapturedTerm>` to `CapturedTerm`, which causes special casing and code duplication. For example, the typechecking of such operators, environment management (which is done both for standard application, primitive application, and for these subterms inside primitive operators), and so on. 

This PR focuses on the `switch` construct, which goes from a `Switch(cases: HashMap<Ident, CapturedTerm>, default: CapturedTerm)` operator applied to the expression to test, to a unary operator `Switch(has_default: bool)` which retrieves the cases and a potential default case from the stack, eliminating any dependency to `RichTerm`.

Although the parser could directly generate an appropriate application of this operator, this would make the tyepchecking of switch quite hacky: thus, we rather add a dedicated `Switch(exp, cases, default)` node to the AST for typechecking purpose, which evaluates to an application of the corresponding primitive operator.

Also include small syntax fixes (the last comma is now optional, and the default case needs not to be in last position).


Patch:
diff --git a/src/eval.rs b/src/eval.rs
index 6011ed4c..3ba2a2f4 100644
--- a/src/eval.rs
+++ b/src/eval.rs
@@ -264,6 +264,32 @@ where
                 env.insert(x, (Rc::clone(&thunk), IdentKind::Let()));
                 Closure { body: t, env }
             }
+            Term::Switch(exp, cases, default) => {
+                let has_default = default.is_some();
+
+                if let Some(t) = default {
+                    stack.push_arg(
+                        Closure {
+                            body: t,
+                            env: env.clone(),
+                        },
+                        pos.clone(),
+                    );
+                }
+
+                stack.push_arg(
+                    Closure {
+                        body: RichTerm::new(Term::Record(cases), pos.clone()),
+                        env: env.clone(),
+                    },
+                    pos.clone(),
+                );
+
+                Closure {
+                    body: RichTerm::new(Term::Op1(UnaryOp::Switch(has_default), exp), pos),
+                    env,
+                }
+            }
             Term::Op1(op, t) => {
                 let op = op.map(|t| Closure {
                     body: t,
@@ -571,6 +597,22 @@ fn subst(rt: RichTerm, global_env: &Environment, env: &Environment) -> RichTerm
 
                 RichTerm::new(Term::App(t1, t2), pos)
             }
+            Term::Switch(t, cases, default) => {
+                let default =
+                    default.map(|d| subst_(d, global_env, env, Cow::Borrowed(bound.as_ref())));
+                let cases = cases
+                    .into_iter()
+                    .map(|(id, t)| {
+                        (
+                            id,
+                            subst_(t, global_env, env, Cow::Borrowed(bound.as_ref())),
+                        )
+                    })
+                    .collect();
+                let t = subst_(t, global_env, env, bound);
+
+                RichTerm::new(Term::Switch(t, cases, default), pos)
+            }
             Term::Op1(op, t) => {
                 let op = op.map(|t| subst_(t, global_env, env, Cow::Borrowed(bound.as_ref())));
                 let t = subst_(t, global_env, env, bound);
diff --git a/src/grammar.lalrpop b/src/grammar.lalrpop
index f1fa23d0..2c5574cb 100644
--- a/src/grammar.lalrpop
+++ b/src/grammar.lalrpop
@@ -3,7 +3,7 @@ use crate::term::{BinaryOp, RichTerm, Term, UnaryOp, StrChunk};
 use crate::term::make as mk_term;
 use crate::mk_app;
 use crate::types::{Types, AbsType};
-use super::utils::{StringKind, mk_span, mk_label, strip_indent};
+use super::utils::{StringKind, mk_span, mk_label, strip_indent, SwitchCase};
 use super::lexer::{Token, NormalToken, StringToken, MultiStringToken, LexicalError};
 use std::collections::HashMap;
 use either::*;
@@ -60,6 +60,27 @@ RichTerm: RichTerm = {
 
         mk_term::let_in(id, t1, t2)
     },
+    "switch" "{" <cases: (switch_case ",")*> <last: switch_case?> "}" <exp: SpTerm<RichTerm>> => {
+        let mut acc = HashMap::with_capacity(cases.len());
+        let mut default = None;
+
+        for case in cases.into_iter().map(|x| x.0).chain(last.into_iter()) {
+            match case {
+                SwitchCase::Normal(id, t) => acc.insert(id, t),
+                // If there are multiple default cases, the last one silently
+                // erases the others. We should have a dedicated error for that
+                SwitchCase::Default(t) => default.replace(t),
+            };
+        }
+
+        RichTerm::from(
+            Term::Switch(
+                exp,
+                acc,
+                default,
+            )
+        )
+    },
     "if" <b:Term> "then" <t:Term> "else" <e:SpTerm<RichTerm>> =>
         mk_app!(Term::Op1(UnaryOp::Ite(), b), t, e),
     "import" <s: Str> => RichTerm::from(Term::Import(s)),
@@ -248,11 +269,6 @@ UOp: UnaryOp<RichTerm> = {
     "tag" <s: Str> => UnaryOp::Tag(s),
     "wrap" => UnaryOp::Wrap(),
     "embed" <Ident> => UnaryOp::Embed(<>),
-    "switch" "{" <ds: (switch_case ",")*> <default: switch_default?> "}" =>
-        UnaryOp::Switch(
-            ds.into_iter().map(|x| x.0).collect(),
-            default,
-        ),
     "map" <Atom> => UnaryOp::ListMap(<>),
     "recordMap" <Atom> => UnaryOp::RecordMap(<>),
     "seq" => UnaryOp::Seq(),
@@ -263,12 +279,9 @@ UOp: UnaryOp<RichTerm> = {
     "fieldsOf" => UnaryOp::FieldsOf(),
 };
 
-switch_case: (Ident, RichTerm) = {
-    <id: Ident> "=>" <t: SpTerm<Atom> > => (id, t),
-}
-
-switch_default: RichTerm = {
-    "_" "=>" <SpTerm<Atom>> "," => <>,
+switch_case: SwitchCase = {
+    <id: Ident> "=>" <t: Term> => SwitchCase::Normal(id, t),
+    "_" "=>" <t: Term> => SwitchCase::Default(<>),
 }
 
 // TODO: convenience for messing with precedence levels during development. Once
diff --git a/src/operation.rs b/src/operation.rs
index 698ca7fa..18305520 100644
--- a/src/operation.rs
+++ b/src/operation.rs
@@ -260,13 +260,43 @@ fn process_unary_operation(
                 ))
             }
         }
-        UnaryOp::Switch(mut m, d) => {
+        UnaryOp::Switch(has_default) => {
+            let (cases_closure, _) = stack.pop_arg().expect("missing arg for switch");
+            let default = if has_default {
+                Some(
+                    stack
+                        .pop_arg()
+                        .map(|(clos, _)| clos)
+                        .expect("missing default case for switch"),
+                )
+            } else {
+                None
+            };
+
             if let Term::Enum(en) = *t {
-                match m.remove(&en) {
-                    Some(clos) => Ok(clos),
-                    None => match d {
-                        Some(clos) => Ok(clos),
-                        None => Err(EvalError::TypeError(
+                let Closure {
+                    body:
+                        RichTerm {
+                            term: cases_term, ..
+                        },
+                    env: cases_env,
+                } = cases_closure;
+
+                let mut cases = match *cases_term {
+                    Term::Record(map) => map,
+                    _ => panic!("invalid argument for switch"),
+                };
+
+                cases
+                    .remove(&en)
+                    .map(|body| Closure {
+                        body,
+                        env: cases_env,
+                    })
+                    .or(default)
+                    .ok_or_else(||
+                        // ? We should have a dedicated error for unmatched pattern
+                        EvalError::TypeError(
                             String::from("Enum"),
                             String::from("switch"),
                             arg_pos,
@@ -274,19 +304,16 @@ fn process_unary_operation(
                                 term: Box::new(Term::Enum(en)),
                                 pos,
                             },
-                        )),
-                    },
-                }
+                        ))
+            } else if let Some(clos) = default {
+                Ok(clos)
             } else {
-                match d {
-                    Some(clos) => Ok(clos),
-                    None => Err(EvalError::TypeError(
-                        String::from("Enum"),
-                        String::from("switch"),
-                        arg_pos,
-                        RichTerm { term: t, pos },
-                    )),
-                }
+                Err(EvalError::TypeError(
+                    String::from("Enum"),
+                    String::from("switch"),
+                    arg_pos,
+                    RichTerm { term: t, pos },
+                ))
             }
         }
         UnaryOp::ChangePolarity() => {
diff --git a/src/parser/utils.rs b/src/parser/utils.rs
index a73b5812..2dc23ead 100644
--- a/src/parser/utils.rs
+++ b/src/parser/utils.rs
@@ -1,3 +1,4 @@
+use crate::identifier::Ident;
 /// A few helpers to generate position spans and labels easily during parsing
 use crate::label::Label;
 use crate::position::RawSpan;
@@ -13,6 +14,13 @@ pub enum StringKind {
     Multiline,
 }
 
+/// Distinguish between a normal case `id => exp` and a default case `_ => exp`.
+#[derive(Clone, Debug)]
+pub enum SwitchCase {
+    Normal(Ident, RichTerm),
+    Default(RichTerm),
+}
+
 /// Make a span from parser byte offsets.
 pub fn mk_span(src_id: FileId, l: usize, r: usize) -> RawSpan {
     RawSpan {
diff --git a/src/term.rs b/src/term.rs
index 119f32b2..7d7dc3da 100644
--- a/src/term.rs
+++ b/src/term.rs
@@ -74,6 +74,13 @@ pub enum Term {
     /// A recursive record, where the fields can reference each others.
     #[serde(skip)]
     RecRecord(HashMap<Ident, RichTerm>),
+    /// A switch construct. The evaluation is done by the corresponding unary operator, but we
+    /// still need this one for typechecking.
+    Switch(
+        RichTerm,                 /* tested expression */
+        HashMap<Ident, RichTerm>, /* cases */
+        Option<RichTerm>,         /* default */
+    ),
 
     /// A list.
     List(Vec<RichTerm>),
@@ -196,9 +203,9 @@ impl Term {
     {
         use self::Term::*;
         match self {
-            Op1(UnaryOp::Switch(ref mut map, ref mut def), ref mut t) => {
-                map.iter_mut().for_each(|e| {
-                    let (_, t) = e;
+            Switch(ref mut t, ref mut cases, ref mut def) => {
+                cases.iter_mut().for_each(|c| {
+                    let (_, t) = c;
                     func(t);
                 });
                 func(t);
@@ -279,6 +286,7 @@ impl Term {
             Term::Let(_, _, _)
             | Term::App(_, _)
             | Term::Var(_)
+            | Term::Switch(..)
             | Term::Op1(_, _)
             | Term::Op2(_, _, _)
             | Term::Promise(_, _, _)
@@ -327,6 +335,7 @@ impl Term {
             Term::Var(Ident(id)) => id.clone(),
             Term::Let(_, _, _)
             | Term::App(_, _)
+            | Term::Switch(..)
             | Term::Op1(_, _)
             | Term::Op2(_, _, _)
             | Term::Promise(_, _, _)
@@ -351,6 +360,7 @@ impl Term {
             Term::Let(_, _, _)
             | Term::App(_, _)
             | Term::Var(_)
+            | Term::Switch(..)
             | Term::Op1(_, _)
             | Term::Op2(_, _, _)
             | Term::Promise(_, _, _)
@@ -388,6 +398,7 @@ impl Term {
             | Term::Wrapped(_, _)
             | Term::Let(_, _, _)
             | Term::App(_, _)
+            | Term::Switch(..)
             | Term::Var(_)
             | Term::Op1(_, _)
             | Term::Op2(_, _, _)
@@ -415,6 +426,7 @@ impl Term {
             | Term::List(_)
             | Term::Fun(_, _)
             | Term::App(_, _)
+            | Term::Switch(..)
             | Term::Var(_)
             | Term::Op1(_, _)
             | Term::Op2(_, _, _)
@@ -477,12 +489,8 @@ pub enum UnaryOp<CapturedTerm> {
     /// `embed c x` will have enum type `a | b | c`. It only affects typechecking as at runtime
     /// `embed someId` act like the identity.
     Embed(Ident),
-    // This is a hacky way to deal with this for now.
-    //
-    // Ideally it should change to eliminate the dependency with RichTerm
-    // in the future.
     /// A switch block. Used to match on a enumeration.
-    Switch(HashMap<Ident, CapturedTerm>, Option<CapturedTerm>),
+    Switch(bool /* presence of a default case */), //HashMap<Ident, CapturedTerm>, Option<CapturedTerm>),
 
     /// Static access to a record field.
     ///
@@ -565,15 +573,7 @@ impl<Ty> UnaryOp<Ty> {
         use UnaryOp::*;
 
         match self {
-            Switch(m, op) => Switch(
-                m.into_iter()
-                    .map(|e| {
-                        let (id, t) = e;
-                        (id, f(t))
-                    })
-                    .collect(),
-                op.map(f),
-            ),
+            Switch(has_default) => Switch(has_default),
             ListMap(t) => ListMap(f(t)),
             RecordMap(t) => RecordMap(f(t)),
 
@@ -799,7 +799,7 @@ impl RichTerm {
                     state,
                 )
             }
-            Term::Op1(UnaryOp::Switch(cases, default), t) => {
+            Term::Switch(t, cases, default) => {
                 // The annotation on `map_res` use Result's corresponding trait to convert from
                 // Iterator<Result> to a Result<Iterator>
                 let cases_res: Result<HashMap<Ident, RichTerm>, E> = cases
@@ -817,10 +817,7 @@ impl RichTerm {
                 let t = t.traverse(f, state)?;
 
                 f(
-                    RichTerm {
-                        term: Box::new(Term::Op1(UnaryOp::Switch(cases_res?, default), t)),
-                        pos,
-                    },
+                    RichTerm::new(Term::Switch(t, cases_res?, default), pos),
                     state,
                 )
             }
@@ -1054,6 +1051,31 @@ pub mod make {
         };
     }
 
+    /// Multi field record for types implementing `Into<Ident>` (for the identifiers), and
+    /// `Into<RichTerm>` for the fields. Identifiers and corresponding content are specified as a
+    /// tuple: `mk_record!(("field1", t1), ("field2", t2))` corresponds to the record `{ field1 =
+    /// t1; field2 = t2 }`.
+    #[macro_export]
+    #[cfg(test)]
+    macro_rules! mk_switch {
+        ( $exp:expr, $( ($id:expr, $body:expr) ),* ; $default:expr ) => {
+            {
+                let mut map = std::collections::HashMap::new();
+                $(
+                    map.insert($id.into(), $body.into());
+                )*
+                $crate::term::RichTerm::from($crate::term::Term::Switch($crate::term::RichTerm::from($exp), map, Some($crate::term::RichTerm::from($default))))
+            }
+        };
+        ( $exp:expr, $( ($id:expr, $body:expr) ),*) => {
+                let mut map = std::collections::HashMap::new();
+                $(
+                    map.insert($id.into(), $body.into());
+                )*
+                $crate::term::RichTerm::from($crate::term::Term::Switch($crate::term::RichTerm::from($exp), map, None))
+        };
+    }
+
     pub fn var<I>(v: I) -> RichTerm
     where
         I: Into<Ident>,
diff --git a/src/typecheck.rs b/src/typecheck.rs
index b1a052a0..4e0a7627 100644
--- a/src/typecheck.rs
+++ b/src/typecheck.rs
@@ -535,6 +535,31 @@ fn type_check_(
             type_check_(state, envs.clone(), strict, e, arr)?;
             type_check_(state, envs, strict, t, src)
         }
+        Term::Switch(exp, cases, default) => {
+            // Currently, if it has a default value, we typecheck the whole thing as
+            // taking ANY enum, since it's more permissive and there's no loss of information
+            let res = TypeWrapper::Ptr(new_var(state.table));
+
+            for case in cases.values() {
+                type_check_(state, envs.clone(), strict, case, res.clone())?;
+            }
+
+            let row = match default {
+                Some(t) => {
+                    type_check_(state, envs.clone(), strict, t, res.clone())?;
+                    TypeWrapper::Ptr(new_var(state.table))
+                }
+                None => cases.iter().try_fold(
+                    mk_typewrapper::row_empty(),
+                    |acc, x| -> Result<TypeWrapper, TypecheckError> {
+                        Ok(mk_tyw_enum_row!(x.0.clone(), acc))
+                    },
+                )?,
+            };
+
+            unify(state, strict, ty, res).map_err(|err| err.to_typecheck_err(state, &rt.pos))?;
+            type_check_(state, envs, strict, exp, mk_tyw_enum!(row))
+        }
         Term::Var(x) => {
             let x_ty = envs
                 .get(&x)
@@ -1063,10 +1088,10 @@ pub fn unify_rows(
         (AbsType::RowEmpty(), AbsType::Dyn()) => Err(RowUnifError::ExtraDynTail()),
         (AbsType::Dyn(), AbsType::RowEmpty()) => Err(RowUnifError::MissingDynTail()),
         (AbsType::RowEmpty(), AbsType::RowExtend(ident, _, _))
-        | (AbsType::Dyn(), AbsType::RowExtend(ident, _, _)) => Err(RowUnifError::ExtraRow(ident)),
-        (AbsType::RowExtend(ident, _, _), AbsType::Dyn())
+        | (AbsType::Dyn(), AbsType::RowExtend(ident, _, _))
+        | (AbsType::RowExtend(ident, _, _), AbsType::Dyn())
         | (AbsType::RowExtend(ident, _, _), AbsType::RowEmpty()) => {
-            Err(RowUnifError::MissingRow(ident))
+            Err(RowUnifError::ExtraRow(ident))
         }
         (AbsType::RowExtend(id, ty, t), r2 @ AbsType::RowExtend(_, _, _)) => {
             let (ty2, t2_tail) =
@@ -1358,35 +1383,8 @@ pub fn get_uop_type(
             constraint(state, row.clone(), id.clone()).unwrap();
             mk_tyw_arrow!(mk_tyw_enum!(row.clone()), mk_tyw_enum!(id.clone(), row))
         }
-        // 1. rows -> a
-        // 2. forall b. b -> a
-        // Rows is ( `label1, .., `labeln ) for label in l.keys().
-        // Unify each branch in l.values() with a.
-        // If the switch has a default case, the more general type 2. is used.
-        UnaryOp::Switch(l, d) => {
-            // Currently, if it has a default value, we typecheck the whole thing as
-            // taking ANY enum, since it's more permissive and there's not a loss of information
-            let res = TypeWrapper::Ptr(new_var(state.table));
-
-            for exp in l.values() {
-                type_check_(state, envs.clone(), strict, exp, res.clone())?;
-            }
-
-            let row = match d {
-                Some(e) => {
-                    type_check_(state, envs.clone(), strict, e, res.clone())?;
-                    TypeWrapper::Ptr(new_var(state.table))
-                }
-                None => l.iter().try_fold(
-                    mk_typewrapper::row_empty(),
-                    |acc, x| -> Result<TypeWrapper, TypecheckError> {
-                        Ok(mk_tyw_enum_row!(x.0.clone(), acc))
-                    },
-                )?,
-            };
-
-            mk_tyw_arrow!(mk_tyw_enum!(row), res)
-        }
+        // This should not happen, as Switch() is only produced during evaluation.
+        UnaryOp::Switch(_) => panic!("cannot typecheck Switch()"),
         // Dyn -> Dyn
         UnaryOp::ChangePolarity() | UnaryOp::GoDom() | UnaryOp::GoCodom() | UnaryOp::Tag(_) => {
             mk_tyw_arrow!(AbsType::Dyn(), AbsType::Dyn())
diff --git a/src/types.rs b/src/types.rs
index 6a8e4e3e..bc01e107 100644
--- a/src/types.rs
+++ b/src/types.rs
@@ -220,9 +220,10 @@ impl Types {
                                 rest_contract,
                                 mk_fun!(
                                     "x",
-                                    mk_term::op1(
-                                        UnaryOp::Switch(map, Some(Term::Bool(false).into())),
-                                        mk_term::var("x"),
+                                    mk_app!(
+                                        mk_term::op1(UnaryOp::Switch(true), mk_term::var("x")),
+                                        Term::Record(map),
+                                        Term::Bool(false)
                                     )
                                 )
                             )


Test patch:
diff --git a/src/parser/tests.rs b/src/parser/tests.rs
index fab08fa1..90b11188 100644
--- a/src/parser/tests.rs
+++ b/src/parser/tests.rs
@@ -1,9 +1,9 @@
 use super::lexer::{Lexer, LexicalError, NormalToken, StringToken, Token};
 use crate::identifier::Ident;
-use crate::mk_app;
 use crate::term::make as mk_term;
 use crate::term::Term::*;
 use crate::term::{BinaryOp, RichTerm, StrChunk, UnaryOp};
+use crate::{mk_app, mk_switch};
 use codespan::Files;
 
 fn parse(s: &str) -> Option<RichTerm> {
@@ -155,18 +155,7 @@ fn enum_terms() {
 
     assert_eq!(
         parse_without_pos("switch { foo => true, bar => false, _ => 456, } 123"),
-        mk_term::op1(
-            UnaryOp::Switch(
-                vec![
-                    (Ident::from("foo"), Bool(true).into()),
-                    (Ident::from("bar"), Bool(false).into())
-                ]
-                .into_iter()
-                .collect(),
-                Some(Num(456.).into())
-            ),
-            Num(123.),
-        )
+        mk_switch!(Num(123.), ("foo", Bool(true)), ("bar", Bool(false)) ; Num(456.))
     )
 }