Repository: tweag/nickel
Pull request #335 (2021-03-31 09:20:27)

Change precedence of let and annotations
Depend on #317.

## The problem

Given the ML-style lets, Nickel programs or subprograms often have the following shape:

```
let id1 = val1 in
let id2 = val2 in
...
result
```

The result usually being a configuration, a common thing to do is to add a contract:

```
let Contract = { ... } in
// or let Contract = (import "contracts.ncl").SomeContract
let id = val in
...
result | #Contract
```

The problem is that currently, annotations (type or contract) bind more loosely than anything else. Thus, the following example is parsed as `(let Contract = { ... } in ...) | #Contract`, which fails at run-time because `Contract` is not in scope of the annotation. Even if one can just add parentheses `let ... in (result | #Contract)`, in our limited tests already, it comes often and is annoying. Parsing the original example directly as `let Contract = { .. } in ... in (result | #Contract)` would have exactly the same operational semantics, while bringing more things in scope, which sounds like a better way.

## Implementation

This is not totally trivial as it may first seem, because it introduces a kind of dangling else issue: `let id = val in exp` may or may not have a trailing annotation, and thus `let id = val in let id2 = val2 in exp | #Contract` is ambiguous, as well as other constructs that can have a let on the right, such as `fun x => let id = val in ... | #Contract`. LALRPOP precedence annotations are not powerful enough to solve this, but hopefully only a few top-level rule may have let on the right (`if-then-else`, `let`, `switch` and `fun`), and thanks to LALRPOP's macros, there isn't much code duplication in this PR.

## Consistency

This change may introduce some quirks:
 1. Type and contracts annotations are treated the same in the grammar. For type annotations, this change is semantically significant, as `let id = val in exp : Type` would previously typecheck `val`, while it doesn't when parsed as `let id = val in (exp : Type)`. However, one could argue that the fact that `let id = val in exp : Type` includes `val` in the statically typed block isn't a totally obvious choice either.
 2. Let bindings eagerly "eat" annotations, while other constructs don't: `(fun x => x | forall a. a -> a)` still parses as before and as expected, but if we add a let, `(fun x => let _ign = null in x | forall a. a -> a)` is parsed as `(fun x => (let ign_ = null in x | forall a. a -> a))`. This is different and will most probably fail when applied. This different treatment may be confusing.

For 1., we could parse differently type and contract annotations, but this sounds like introducing a new inconsistency.

For 2., different stances would be:
 - Only apply the proposed change to chained lets, that is `let id1 = val1 in .. let id2 = val2 in .. exp | #Contract`, but not if there's a different construct on the left, like `fun x => let id = .. in .. exp | #Contract`. There again, I'm not sure this really less confusing.
 - Treat all of `if-then-else`, `let`, `switch` and `fun` the same way. But that means `fun x => x : forall a. a -> a` now fails, because now `x` is typechecked `x` against `forall a. a -> a` instead of the whole function.

aspiwack: I do believe that `let … in` should be the loosest grammar element. So I think this is going in the right direction.

Maybe before merging we may want a conversation about precedence in general. Haskell has the convention that nothing binds tighter than application (except in one case that we don't like to think about :slightly_smiling_face: ). But I don't think that it's quite right. I think that we want, in particular, from tighter to looser:

1. Record selection `u.f`
2. Application `u v`
3. Type and contract annotations `x | c`, `x : t`
4. Function binders `fun x => u`
5. Let binders `let x = u in v`

This does appear to solve the infelicities you mention. What do you think?
yannham: >     1. Record selection `u.f`
> 
>     2. Application `u v`
> 
>     3. Type and contract annotations `x | c`, `x : t`
> 
>     4. Function binders `fun x => u`
> 
>     5. Let binders `let x = u in v`
> 
> 
> This does appear to solve the infelicities you mention. What do you think?

Sounds good. There's also the `if-then-else`. It would be between annotations and function binders, I guess.
aspiwack: Agreed. @edolstra do you also agree?

----

How do we proceed? Is it better to merge the PR in its present state, or to modify all the precedences in one fell swoop?
yannham: This shouldn't be a huge patch (we may have to rewrite tests or the like, but I don't think many rely on the current semantics), and the changes looks a bit interdependent, so let me add them to this PR (or close and re-open a new one)?
dpulls[bot]: :tada: All dependencies have been resolved !
edolstra: Sounds good to me. Probably easiest to update this PR.

FWIW the [Nix precedence](https://github.com/NixOS/nix/blob/906adadacd2d1c98346a2f42c0b42a32d2806d94/src/libexpr/parser.y#L325-L395) is:

* Attribute selection
* Function application
* A bunch of operators
* if-then-else
* Lambdas
yannham: It's implemented in the last commit. I put if-then-else, lambdas, and let-binding at the same precedence level, because there is no ambiguity. I need to fix a merge conflict now, though.

Patch:
diff --git a/src/grammar.lalrpop b/src/grammar.lalrpop
index 86c38eb8..b000239d 100644
--- a/src/grammar.lalrpop
+++ b/src/grammar.lalrpop
@@ -15,7 +15,7 @@ use codespan::FileId;
 
 grammar<'input>(src_id: FileId);
 
-SpTerm<Rule>: RichTerm = <l: @L> <t: Rule> <r: @R> => t.with_pos(mk_pos(src_id, l, r));
+WithPos<Rule>: RichTerm = <l: @L> <t: Rule> <r: @R> => t.with_pos(mk_pos(src_id, l, r));
 
 TypeAnnot: MetaValue = ":" <l: @L> <ty: Types> <r: @R> => MetaValue {
     doc: None,
@@ -69,19 +69,7 @@ LeftOp<Op, Current, Previous>: RichTerm =
 LeftOpLazy<Op, Current, Previous>: RichTerm =
     <t1: Current> <op: Op> <t2: Previous> => mk_app!(Term::Op1(op, t1), t2);
 
-pub Term: RichTerm = {
-    <t: SpTerm<RichTerm>> <meta: Annot?> => {
-        let pos = t.pos;
-
-        if let Some(mut meta) = meta {
-            meta.value = Some(t);
-            RichTerm::new(Term::MetaValue(meta), pos)
-        }
-        else {
-            t
-        }
-    }
-};
+pub Term: RichTerm = WithPos<RootTerm>;
 
 pub ExtendedTerm: ExtendedTerm = {
     "let" <id:Ident> <meta: Annot?> "=" <t: Term> => {
@@ -100,17 +88,10 @@ pub ExtendedTerm: ExtendedTerm = {
     Term => ExtendedTerm::RichTerm(<>),
 }
 
-RichTerm: RichTerm = {
-    <l: @L> "fun" <ps:Pattern+> "=>" <t: SpTerm<RichTerm>> <r: @R> => {
-        let pos = mk_pos(src_id, l, r);
-        ps.into_iter().rev().fold(t, |t, p| RichTerm {
-            term: Box::new(Term::Fun(p, t)),
-            pos,
-        })
-    },
-    "let" <id:Ident> <meta: Annot?> "=" <t1: Term> "in" <t2:SpTerm<RichTerm>> => {
+RootTerm: RichTerm = {
+    "let" <id:Ident> <meta: Annot?> "=" <t1: Term> "in"
+        <t2: Term> => {
         let pos = t1.pos;
-
         let t1 = if let Some(mut meta) = meta {
             meta.value = Some(t1);
             RichTerm::new(Term::MetaValue(meta), pos)
@@ -121,7 +102,15 @@ RichTerm: RichTerm = {
 
         mk_term::let_in(id, t1, t2)
     },
-    "switch" "{" <cases: (switch_case ",")*> <last: switch_case?> "}" <exp: SpTerm<RichTerm>> => {
+    <l: @L> "fun" <ps:Pattern+> "=>" <t: Term> <r: @R> => {
+        let pos = mk_pos(src_id, l, r);
+        ps.into_iter().rev().fold(t, |t, p| RichTerm {
+            term: Box::new(Term::Fun(p, t)),
+            pos,
+        })
+    },
+    "switch" "{" <cases: (switch_case ",")*> <last: switch_case?> "}"
+        <exp: Term> => {
         let mut acc = HashMap::with_capacity(cases.len());
         let mut default = None;
 
@@ -142,29 +131,47 @@ RichTerm: RichTerm = {
             )
         )
     },
-    "if" <b:Term> "then" <t:Term> "else" <e:SpTerm<RichTerm>> =>
-        mk_app!(Term::Op1(UnaryOp::Ite(), b), t, e),
+    "if" <cond: Term> "then" <t1: Term> "else" <t2: Term> =>
+        mk_app!(Term::Op1(UnaryOp::Ite(), cond), t1, t2),
+    AnnotatedTerm,
+};
+
+AnnotatedTerm: RichTerm = {
+    <t: WithPos<Infix>> <meta: Annot?> => {
+        let pos = t.pos;
+
+        if let Some(mut meta) = meta {
+            meta.value = Some(t);
+            RichTerm::new(Term::MetaValue(meta), pos)
+        }
+        else {
+            t
+        }
+    },
+};
+
+Infix: RichTerm = {
     "import" <s: StaticString> => RichTerm::from(Term::Import(OsString::from(s))),
-    SpTerm<InfixExpr>,
+    InfixExpr,
 };
 
 Applicative: RichTerm = {
-    <t1:SpTerm<Applicative>> <t2: RecordOperand> => mk_app!(t1, t2),
-    <op: UOp> <t: SpTerm<RecordOperand>> => mk_term::op1(op, t),
-    <op: BOpPre> <t1: SpTerm<RecordOperand>> <t2: SpTerm<Atom>> => mk_term::op2(op, t1, t2),
-    <RecordOperand>,
+    <t1:WithPos<Applicative>> <t2: WithPos<RecordOperand>> => mk_app!(t1, t2),
+    <op: UOp> <t: WithPos<RecordOperand>> => mk_term::op1(op, t),
+    <op: BOpPre> <t1: WithPos<RecordOperand>> <t2: WithPos<Atom>> => mk_term::op2(op, t1, t2),
+    RecordOperand,
 };
 
 RecordOperand: RichTerm = {
-    SpTerm<Atom>,
-    SpTerm<RecordOperationChain>,
+    Atom,
+    RecordOperationChain,
 }
 
 RecordOperationChain: RichTerm = {
-    <t: SpTerm<RecordOperand>> "." <id: Ident> => mk_term::op1(UnaryOp::StaticAccess(id), t),
-    <t: SpTerm<RecordOperand>> "." <t_id: StrChunks> => mk_term::op2(BinaryOp::DynAccess(), t_id, t),
-    <t: SpTerm<RecordOperand>> "-$" <t_id: SpTerm<Atom>> => mk_term::op2(BinaryOp::DynRemove(), t_id, t),
-    <r: SpTerm<RecordOperand>> "$[" <id: Term> "=" <t: Term> "]" =>
+    <t: WithPos<RecordOperand>> "." <id: Ident> => mk_term::op1(UnaryOp::StaticAccess(id), t),
+    <t: WithPos<RecordOperand>> "." <t_id: StrChunks> => mk_term::op2(BinaryOp::DynAccess(), t_id, t),
+    <t: WithPos<RecordOperand>> "-$" <t_id: WithPos<Atom>> => mk_term::op2(BinaryOp::DynRemove(), t_id, t),
+    <r: WithPos<RecordOperand>> "$[" <id: Term> "=" <t: Term> "]" =>
         mk_app!(mk_term::op2(BinaryOp::DynExtend(), id, r), t),
 };
 
@@ -173,7 +180,7 @@ Atom: RichTerm = {
     "num literal" => RichTerm::from(Term::Num(<>)),
     "null" => RichTerm::from(Term::Null),
     Bool => RichTerm::from(Term::Bool(<>)),
-    <StrChunks>,
+    StrChunks,
     Ident => RichTerm::from(Term::Var(<>)),
     "`" <Ident> => RichTerm::from(Term::Enum(<>)),
     "{" <fields: (<RecordField> ",")*> <last: RecordField?> "}" => {
@@ -293,7 +300,7 @@ ChunkLiteral : String =
         })
     };
 
-ChunkExpr: StrChunk<RichTerm> = HashBrace <t: SpTerm<RichTerm>> "}" => StrChunk::Expr(t, 0);
+ChunkExpr: StrChunk<RichTerm> = HashBrace <t: WithPos<Term>> "}" => StrChunk::Expr(t, 0);
 
 HashBrace = { "#{", "multstr #{" };
 
@@ -487,7 +494,7 @@ subType : Types = {
         Types(AbsType::List(ty))
     },
     <Ident> => Types(AbsType::Var(<>)),
-    "#" <SpTerm<Atom>> => Types(AbsType::Flat(<>)),
+    "#" <WithPos<Atom>> => Types(AbsType::Flat(<>)),
     "(" <Types> ")" => <>,
     "<" <rows:(<Ident> ",")*> <last: (<Ident>)?> <tail: ("|" <Ident>)?> ">" => {
         let ty = rows.into_iter()


Test patch:
diff --git a/tests/pass.rs b/tests/pass.rs
index 8bc80bd1..4c7e4956 100644
--- a/tests/pass.rs
+++ b/tests/pass.rs
@@ -102,3 +102,8 @@ fn serialize() {
     check_file("serialize.ncl");
     check_file("serialize-package.ncl");
 }
+
+#[test]
+fn annot_parsing() {
+    check_file("annotations.ncl");
+}
diff --git a/tests/pass/annotations.ncl b/tests/pass/annotations.ncl
new file mode 100644
index 00000000..d2def197
--- /dev/null
+++ b/tests/pass/annotations.ncl
@@ -0,0 +1,26 @@
+let Assert = fun l x => x || %blame% l in
+
+// left_annot_precedence
+(let dummy = null in
+  let LocalAssert = Assert in
+  true | #LocalAssert) &&
+
+(if false then
+    null
+  else
+    let dummy = null in
+    let LocalAssert = Assert in
+    true | #LocalAssert) &&
+
+(let f = fun x =>
+    let dummy = null in
+    let LocalAssert = Assert in
+    x | #LocalAssert in
+  f true) &&
+
+// others_precedence
+((fun x => x | #Assert) true) &&
+(let AssertOk = fun l t => if t == `Ok then t else %blame% l in
+  switch {Ok => true, Err => false} `Ok | #AssertOk) &&
+
+true
diff --git a/tests/pass/contracts.ncl b/tests/pass/contracts.ncl
index 099c8386..472f709c 100644
--- a/tests/pass/contracts.ncl
+++ b/tests/pass/contracts.ncl
@@ -77,7 +77,7 @@ f `boo == 3) &&
 (({a = 1, b = "b", c = false} | {a: Num, b: Str | Dyn})
   == {a = 1, b = "b", c = false}
   | #Assert) &&
-((fun r => r.b | {a: Num | Dyn} -> Dyn) {a = 1, b = 2} == 2
+(((fun r => r.b) | {a: Num | Dyn} -> Dyn) {a = 1, b = 2} == 2
   | #Assert) &&
 
 
diff --git a/tests/pass/typechecking.ncl b/tests/pass/typechecking.ncl
index 4ec3c58c..af4412dc 100644
--- a/tests/pass/typechecking.ncl
+++ b/tests/pass/typechecking.ncl
@@ -103,16 +103,16 @@ let typecheck = [
   [1, "2", false],
   //TODO: the type system may accept the following test at some point.
   //([1, "2", false] : List),
-  (["a", "b", "c"] : List Str),
-  ([1, 2, 3] : List Num),
-  (fun x => [x] : forall a. a -> List a),
+  ["a", "b", "c"] : List Str,
+  [1, 2, 3] : List Num,
+  (fun x => [x]) : forall a. a -> List a,
 
   // lists_ops
-  fun l => %tail% l : forall a. List a -> List a,
-  fun l => %head% l : forall a. List a -> a,
-  fun f l => %map% l f : forall a b. (a -> b) -> List a -> List b,
-  fun l1 => fun l2 => l1 @ l2 : forall a. List a -> List a -> List a,
-  fun i l => %elemAt% l i : forall a. Num -> List a -> a,
+  (fun l => %tail% l) : forall a. List a -> List a,
+  (fun l => %head% l) : forall a. List a -> a,
+  (fun f l => %map% l f) : forall a b. (a -> b) -> List a -> List b,
+  (fun l1 => fun l2 => l1 @ l2) : forall a. List a -> List a -> List a,
+  (fun i l => %elemAt% l i) : forall a. Num -> List a -> a,
 
   // recursive_records
   {a : Num = 1, b = a + 1} : {a : Num, b : Num},
diff --git a/tests/typecheck_fail.rs b/tests/typecheck_fail.rs
index e0e9e306..7064c3bf 100644
--- a/tests/typecheck_fail.rs
+++ b/tests/typecheck_fail.rs
@@ -84,7 +84,9 @@ fn enum_simple() {
 
 #[test]
 fn enum_complex() {
-    assert_typecheck_fails!("fun x => switch {bla => 1, ble => 2, bli => 4} x : <bla, ble> -> Num");
+    assert_typecheck_fails!(
+        "(fun x => switch {bla => 1, ble => 2, bli => 4} x) : <bla, ble> -> Num"
+    );
     // TODO typecheck this, I'm not sure how to do it with row variables
     // LATER NOTE: this requires row subtyping, not easy
     assert_typecheck_fails!(