Repository: tweag/nickel (rust)

Issue:
Better handling of primitive functions and operators
Currently, primitive operators (either infix operators like `+` or builtin functions such as `length`) can only appear fully applied in the AST, inside the nodes `Op1(UnaryOp, Term)` and `Op2(BinaryOp, Term, Term)`. This has the following consequences:
 1. They must be parsed as specific keywords, that can't be used as identifiers elsewhere. As the list of operators will grow bigger in tandem with the standard lib, this will be polluting the global environment. Also, naming is not consistent: you write `lists.fold f l empty` because `fold` is written in pure Nickel in the lists standard library but write directly `map f l` or `length l` because they are primitive operators. It would be nice to have them in the corresponding libraries/namespaces only.
 2. It makes the process of adding an operator clumsier: first add the corresponding token in the lexer, then add some boilerplate to interface the lexer and the parser, then write the implementation in the abstract machine (although to be fair it's not that terrible either)
 3. They can't be partially applied, as in `let mapF = map f in ...`

## Proposals
To circumvent part of the above difficulties, one can either directly change the way operators are handled in the AST, or keep it as it is now but use a specific syntax for primitive operators.

### Without changing the AST
Use a special syntax, different from identifiers, for prefix primitive operators, like `%map%`. This wouldn't clash with identifiers anymore, and can be wrapped in libraries by defining e.g. `map = fun f l => %map% f l`. One could even allow this syntax only when parsing the standard library, such that in normal programs the only way to access `%map%` is to use the wrapper `lists.map`.

This solves 1. and 3., but 2. is harder: because operators must still be fully applied, the parser has to be aware of the arity of the operator, making it difficult to parse uniformly an application of `%op%`. Unless we have a different syntax for unary and binary operators. This also induces some overhead, namely calling the intermediate function.

### By changing the AST
Another direction is to make primitive operators first class terms, that can be applied to via the standard application. This raises the following questions:
 - Strictness: the usual function application is lazy, while primitive application is eager. Let's keep the `Op1` and `Op2` constructs. A fully applied operator (using standard application) then reduces to the corresponding eager operator application. Infix operators  could be parsed directly as operator application like before, to avoid the indirection.
 - Partial application: one needs to be able to represent the new WHNF corresponding to a partially applied binary operator (such as `map f`), either encoding it as a function `fun x => map f x`, or using a dedicated construct `PartialOp`.

## Conclusion
Both approaches amount roughly to the same thing: wrap primitive eager operators as lazy functions to make them compatible with standard application. The first approach makes prefix operators syntactically distinct, and wrap them in libraries as standard functions. It has the advantage of not touching the AST or the abstract machine, but makes 2. a bit clumsier to solve. The second approach avoids changing the syntax by supporting this wrapping directly in the AST. It gives a bit more flexibility, incurs a bit less execution overhead, and makes 2. simpler, because prefix operators are now just usual identifiers. The price to pay is modifying the AST and the abstract machine.

Pull request description:
Special syntax for fully-applied primitive operations
Close #228. Use a specific syntax for fully applied built-in operators, `%operator%`, and wrap this primitive version in vanilla functions of the standard library.

This has the unfortunate consequence described in #226, that is that wrapped operator does not behave as unwrapped operator with respect to typing, but this is a separate topic that needs to be addressed anyway.

This also led to #244. This PR currently assigns correct but less ergonomic types - the ones with `Dyn` - to primitive operators wrapped in the standard library, while the actual primitive ones stay polymorphic. We'll have to resolve this discrepancy together with #244.

Patch:
diff --git a/src/grammar.lalrpop b/src/grammar.lalrpop
index 244031be..132ccfa3 100644
--- a/src/grammar.lalrpop
+++ b/src/grammar.lalrpop
@@ -556,7 +556,6 @@ extern {
         "hasField" => Token::Normal(NormalToken::HasField),
         "map" => Token::Normal(NormalToken::Map),
         "elemAt" => Token::Normal(NormalToken::ElemAt),
-        "merge" => Token::Normal(NormalToken::Merge),
 
         "{" => Token::Normal(NormalToken::LBrace),
         "}" => Token::Normal(NormalToken::RBrace),
diff --git a/src/merge.rs b/src/merge.rs
index b77b14b7..f71830da 100644
--- a/src/merge.rs
+++ b/src/merge.rs
@@ -11,7 +11,7 @@
 //! - All the fields of `r1` that are not in `r2`
 //! - All the fields of `r2` that are not in `r1`
 //! - Fields that are both in `r1` and `r2` are recursively merged: for a field `f`, the result
-//! contains the binding `f = merge r1.f r2.f`
+//! contains the binding `f = r1.f & r2.f`
 //!
 //! As fields are recursively merged, merge needs to operate on any value, not only on records.
 //!
diff --git a/src/parser/lexer.rs b/src/parser/lexer.rs
index dfa0f2c4..4ff4278f 100644
--- a/src/parser/lexer.rs
+++ b/src/parser/lexer.rs
@@ -141,7 +141,7 @@ pub enum NormalToken<'input> {
     #[regex("m(#+)\"", |lex| lex.slice().len())]
     MultiStringStart(usize),
 
-    #[token("tag")]
+    #[token("%tag%")]
     Tag,
     #[token("Assume(")]
     Assume,
@@ -156,61 +156,59 @@ pub enum NormalToken<'input> {
     #[token("Docstring(")]
     Docstring,
 
-    #[token("isNum")]
+    #[token("%isNum%")]
     IsNum,
-    #[token("isBool")]
+    #[token("%isBool%")]
     IsBool,
-    #[token("isStr")]
+    #[token("%isStr%")]
     IsStr,
-    #[token("isFun")]
+    #[token("%isFun%")]
     IsFun,
-    #[token("isList")]
+    #[token("%isList%")]
     IsList,
-    #[token("isRecord")]
+    #[token("%isRecord%")]
     IsRecord,
 
-    #[token("blame")]
+    #[token("%blame%")]
     Blame,
-    #[token("chngPol")]
+    #[token("%chngPol%")]
     ChangePol,
-    #[token("polarity")]
+    #[token("%polarity%")]
     Polarity,
-    #[token("goDom")]
+    #[token("%goDom%")]
     GoDom,
-    #[token("goCodom")]
+    #[token("%goCodom%")]
     GoCodom,
-    #[token("goField")]
+    #[token("%goField%")]
     GoField,
 
-    #[token("wrap")]
+    #[token("%wrap%")]
     Wrap,
-    #[token("embed")]
+    #[token("%unwrap%")]
+    Unwrap,
+    #[token("%embed%")]
     Embed,
-    #[token("mapRec")]
+    #[token("%mapRec%")]
     MapRec,
-    #[token("seq")]
+    #[token("%seq%")]
     Seq,
-    #[token("deepSeq")]
+    #[token("%deepSeq%")]
     DeepSeq,
-    #[token("head")]
+    #[token("%head%")]
     Head,
-    #[token("tail")]
+    #[token("%tail%")]
     Tail,
-    #[token("length")]
+    #[token("%length%")]
     Length,
-    #[token("fieldsOf")]
+    #[token("%fieldsOf%")]
     FieldsOf,
 
-    #[token("unwrap")]
-    Unwrap,
-    #[token("hasField")]
+    #[token("%hasField%")]
     HasField,
-    #[token("map")]
+    #[token("%map%")]
     Map,
-    #[token("elemAt")]
+    #[token("%elemAt%")]
     ElemAt,
-    #[token("merge")]
-    Merge,
 
     #[token("{")]
     LBrace,
diff --git a/src/program.rs b/src/program.rs
index 097cc0e3..16b56552 100644
--- a/src/program.rs
+++ b/src/program.rs
@@ -181,12 +181,22 @@ impl Program {
     fn mk_global_env(&mut self) -> Result<eval::Environment, ImportError> {
         let mut global_env = HashMap::new();
 
+        self.load_stdlib(
+            "<stdlib/builtins.ncl>",
+            nickel_stdlib::BUILTINS,
+            &mut global_env,
+        )?;
         self.load_stdlib(
             "<stdlib/contracts.ncl>",
             nickel_stdlib::CONTRACTS,
             &mut global_env,
         )?;
         self.load_stdlib("<stdlib/lists.ncl>", nickel_stdlib::LISTS, &mut global_env)?;
+        self.load_stdlib(
+            "<stdlib/records.ncl>",
+            nickel_stdlib::RECORDS,
+            &mut global_env,
+        )?;
         Ok(global_env)
     }
 
@@ -580,7 +590,7 @@ mod tests {
 
     #[test]
     fn simple_type_check() {
-        let res = eval_string("let x = 5 in if isNum x then true else 1");
+        let res = eval_string("let x = 5 in if %isNum% x then true else 1");
 
         assert_eq!(Ok(Term::Bool(true)), res);
     }
@@ -647,13 +657,16 @@ Assume(#alwaysTrue, false)
     #[test]
     fn flat_higher_order_contract() {
         let res = eval_string(
-            "let alwaysTrue = fun l t => let boolT = Assume(Bool, t) in
-    if boolT then boolT else blame l in
-let alwaysFalse = fun l t => let boolT = Assume(Bool, t) in
-    if boolT then  blame l else boolT in
-let not = fun b => if b then false else true in
-Assume(#alwaysTrue -> #alwaysFalse, not ) true
-",
+            "let alwaysTrue = fun l t =>
+              let boolT = Assume(Bool, t) in
+              if boolT then boolT else %blame% l
+            in
+            let alwaysFalse = fun l t =>
+              let boolT = Assume(Bool, t) in
+              if boolT then %blame% l else boolT
+            in
+            let not = fun b => if b then false else true in
+            Assume(#alwaysTrue -> #alwaysFalse, not ) true",
         );
 
         assert_eq!(Ok(Term::Bool(false)), res);
@@ -788,22 +801,24 @@ Assume(#alwaysTrue -> #alwaysFalse, not ) true
     #[test]
     fn records_prims() {
         assert_eq!(
-            eval_string("hasField \"foo\" { foo = 1; bar = 2; }"),
+            eval_string("%hasField% \"foo\" { foo = 1; bar = 2; }"),
             Ok(Term::Bool(true))
         );
         assert_eq!(
-            eval_string("hasField \"fop\" { foo = 1; bar = 2; }"),
+            eval_string("%hasField% \"fop\" { foo = 1; bar = 2; }"),
             Ok(Term::Bool(false))
         );
 
         assert_eq!(
-            eval_string("(mapRec (fun y => fun x => x + 1) { foo = 1; bar = \"it's lazy\"; }).foo"),
+            eval_string(
+                "(%mapRec% (fun y => fun x => x + 1) { foo = 1; bar = \"it's lazy\"; }).foo"
+            ),
             Ok(Term::Num(2.)),
         );
         assert_eq!(
             eval_string(
-                "let r = mapRec
-                    (fun y x => if isNum x then x + 1 else 0)
+                "let r = %mapRec%
+                    (fun y x => if %isNum% x then x + 1 else 0)
                     { foo = 1; bar = \"it's lazy\"; }
                 in
                 (r.foo) + (r.bar)"
@@ -812,12 +827,12 @@ Assume(#alwaysTrue -> #alwaysFalse, not ) true
         );
 
         assert_eq!(
-            eval_string("hasField \"foo\" ( { foo = 2; bar = 3; }-$(\"foo\"))"),
+            eval_string("%hasField% \"foo\" ( { foo = 2; bar = 3; }-$(\"foo\"))"),
             Ok(Term::Bool(false))
         );
 
         assert_eq!(
-            eval_string("hasField \"foo\" ( { bar = 3; }$[\"foo\" = 1])"),
+            eval_string("%hasField% \"foo\" ( { bar = 3; }$[\"foo\" = 1])"),
             Ok(Term::Bool(true))
         );
         assert_eq!(
@@ -830,22 +845,22 @@ Assume(#alwaysTrue -> #alwaysFalse, not ) true
     /// just that the evaluation succeeds
     #[test]
     fn seq_expressions() {
-        assert_eq!(eval_string("seq 1 true"), Ok(Term::Bool(true)));
+        assert_eq!(eval_string("%seq% 1 true"), Ok(Term::Bool(true)));
         assert_eq!(
-            eval_string("let x = (1 + 1) in seq x x"),
+            eval_string("let x = (1 + 1) in %seq% x x"),
             Ok(Term::Num(2.0))
         );
 
         assert_eq!(
-            eval_string("let r = {a=(1 + 1);} in deepSeq r (r.a)"),
+            eval_string("let r = {a=(1 + 1);} in %deepSeq% r (r.a)"),
             Ok(Term::Num(2.0))
         );
         assert_eq!(
-            eval_string("let r = {a=(1 + 1);b=(\"a\" ++ \"b\");} in deepSeq r (r.b)"),
+            eval_string("let r = {a=(1 + 1);b=(\"a\" ++ \"b\");} in %deepSeq% r (r.b)"),
             Ok(Term::Str(String::from("ab")))
         );
         assert_eq!(
-            eval_string("let r = {a={b=(1 + 1);};} in deepSeq r ((r.a).b)"),
+            eval_string("let r = {a={b=(1 + 1);};} in %deepSeq% r ((r.a).b)"),
             Ok(Term::Num(2.0))
         );
 
@@ -853,7 +868,7 @@ Assume(#alwaysTrue -> #alwaysFalse, not ) true
             eval_string(
                 "let inj = fun x => {b=(x + 2);} in
                 let cat = fun x => fun y => x ++ y in
-                let r = {a=(inj 1);b=(cat \"a\" \"b\");} in deepSeq r ((r.a).b)"
+                let r = {a=(inj 1);b=(cat \"a\" \"b\");} in %deepSeq% r ((r.a).b)"
             ),
             Ok(Term::Num(3.0))
         )
@@ -861,49 +876,49 @@ Assume(#alwaysTrue -> #alwaysFalse, not ) true
 
     #[test]
     fn lists() {
-        assert_eq!(eval_string("elemAt [1,2,3] 1"), Ok(Term::Num(2.0)));
+        assert_eq!(eval_string("%elemAt% [1,2,3] 1"), Ok(Term::Num(2.0)));
         assert_eq!(
-            eval_string("elemAt (map (fun x => x + 1) [1,2,3]) 1"),
+            eval_string("%elemAt% (%map% (fun x => x + 1) [1,2,3]) 1"),
             Ok(Term::Num(3.0))
         );
 
-        eval_string("elemAt [1,2,3] (-1)").unwrap_err();
-        eval_string("elemAt [1,2,3] 4").unwrap_err();
+        eval_string("%elemAt% [1,2,3] (-1)").unwrap_err();
+        eval_string("%elemAt% [1,2,3] 4").unwrap_err();
 
-        assert_eq!(eval_string("length []"), Ok(Term::Num(0.0)));
-        assert_eq!(eval_string("length [1,2,3]"), Ok(Term::Num(3.0)));
+        assert_eq!(eval_string("%length% []"), Ok(Term::Num(0.0)));
+        assert_eq!(eval_string("%length% [1,2,3]"), Ok(Term::Num(3.0)));
 
         assert_eq!(
-            eval_string("length ([] @ [1,2] @ [3,4] @ [])"),
+            eval_string("%length% ([] @ [1,2] @ [3,4] @ [])"),
             Ok(Term::Num(4.0))
         );
         // Test case added after https://github.com/tweag/nickel/issues/154
         assert_eq!(
-            eval_string("let x = 1 in let l = [x] @ [2] in head l"),
+            eval_string("let x = 1 in let l = [x] @ [2] in %head% l"),
             Ok(Term::Num(1.0))
         );
 
         assert_eq!(
-            eval_string("head [\"a\",\"b\",\"c\"]"),
+            eval_string("%head% [\"a\",\"b\",\"c\"]"),
             Ok(Term::Str(String::from("a")))
         );
-        eval_string("head []").unwrap_err();
+        eval_string("%head% []").unwrap_err();
 
         assert_eq!(
-            eval_string("length (tail [true,false,1])"),
+            eval_string("%length% (%tail% [true,false,1])"),
             Ok(Term::Num(2.0))
         );
-        eval_string("tail []").unwrap_err();
+        eval_string("%tail% []").unwrap_err();
 
         assert_eq!(
             eval_string(
                 "let Y = fun f => (fun x => f (x x)) (fun x => f (x x)) in
                 let foldr_ =
                     fun self => fun f => fun acc => fun l =>
-                        if length l == 0 then acc
+                        if %length% l == 0 then acc
                         else
-                            let h = head l in
-                            let t = tail l in
+                            let h = %head% l in
+                            let t = %tail% l in
                             let next_acc = self f acc t in
                             f next_acc h
                 in
@@ -914,7 +929,7 @@ Assume(#alwaysTrue -> #alwaysFalse, not ) true
                             if y then true else false
                         else false
                 in
-                let all = fun pred => fun l => foldr and true (map pred l) in
+                let all = fun pred => fun l => foldr and true (%map% pred l) in
                 let isZ = fun x => x == 0 in
                 all isZ [0, 0, 0, 1]"
             ),
@@ -1001,7 +1016,7 @@ Assume(#alwaysTrue -> #alwaysFalse, not ) true
     #[test]
     fn enriched_terms_thunk_update() {
         assert_eq!(
-            eval_string("let x = {a=(fun x => Default(1)) 1} in seq (x.a) ((x & {a=2}).a)"),
+            eval_string("let x = {a=(fun x => Default(1)) 1} in %seq% (x.a) ((x & {a=2}).a)"),
             Ok(Term::Num(2.0))
         );
     }
@@ -1080,9 +1095,9 @@ Assume(#alwaysTrue -> #alwaysFalse, not ) true
                  )
              ) in
              let toCtr = fun f => fun l => fun x => (
-               if (isNum x) then (
-                 if (f x) then x else blame l)
-               else blame l
+               if (%isNum% x) then (
+                 if (f x) then x else %blame% l)
+               else %blame% l
              ) in
              let isEven = toCtr isEven_ in
              let isDivBy3 = toCtr isDivBy3_ in
@@ -1294,11 +1309,11 @@ Assume(#alwaysTrue -> #alwaysFalse, not ) true
 
     #[test]
     fn fields_of() {
-        assert_peq!("fieldsOf {}", "[]");
-        assert_peq!("fieldsOf {a = 1; b = 2; c = 3}", "[\"a\", \"b\", \"c\"]");
-        assert_peq!("fieldsOf {aAa = 1; Zzz = 2;}", "[\"Zzz\", \"aAa\"]");
+        assert_peq!("%fieldsOf% {}", "[]");
+        assert_peq!("%fieldsOf% {a = 1; b = 2; c = 3}", "[\"a\", \"b\", \"c\"]");
+        assert_peq!("%fieldsOf% {aAa = 1; Zzz = 2;}", "[\"Zzz\", \"aAa\"]");
         assert_peq!(
-            "fieldsOf {foo = {bar = 0}; baz = Default(true)}",
+            "%fieldsOf% {foo = {bar = 0}; baz = Default(true)}",
             "[\"baz\", \"foo\"]"
         );
     }
@@ -1346,16 +1361,22 @@ Assume(#alwaysTrue -> #alwaysFalse, not ) true
 
     #[test]
     fn boolean_op() {
-        assert_peq!("1+1>1 && isStr 0", "false");
-        assert_peq!("-1 < -2 && isFun (fun x => x)", "false");
-        assert_peq!("isNum 0 && isFun (fun x => x) || 1 == 0 && true", "true");
+        assert_peq!("1+1>1 && %isStr% 0", "false");
+        assert_peq!("-1 < -2 && %isFun% (fun x => x)", "false");
+        assert_peq!(
+            "%isNum% 0 && %isFun% (fun x => x) || 1 == 0 && true",
+            "true"
+        );
         assert_peq!(
-            "isNum 0 && isFun false || 1 == 0 && false || 1 > 2 && 2 < 1",
+            "%isNum% 0 && %isFun% false || 1 == 0 && false || 1 > 2 && 2 < 1",
             "false"
         );
-        assert_peq!("!(isNum true) && !(isFun 0) && !(isBool \"a\")", "true");
         assert_peq!(
-            "!(isNum (fun x => x) || isBool (fun x => x) || isFun (fun x => x))",
+            "!(%isNum% true) && !(%isFun% 0) && !(%isBool% \"a\")",
+            "true"
+        );
+        assert_peq!(
+            "!(%isNum% (fun x => x) || %isBool% (fun x => x) || %isFun% (fun x => x))",
             "false"
         );
 
@@ -1379,29 +1400,30 @@ Assume(#alwaysTrue -> #alwaysFalse, not ) true
         eval_string("Assume({}, {a=1})").unwrap_err();
 
         assert_peq!(
-            "let x = Assume({a: Num, s: Str}, {a = 1; s = \"a\"}) in deepSeq x x",
+            "let x = Assume({a: Num, s: Str}, {a = 1; s = \"a\"}) in %deepSeq% x x",
             "{a = 1; s = \"a\"}"
         );
-        eval_string("let x = Assume({a: Num, s: Str}, {a = 1; s = 2}) in deepSeq x x").unwrap_err();
-        eval_string("let x = Assume({a: Num, s: Str}, {a = \"a\"; s = \"b\"}) in deepSeq x x")
+        eval_string("let x = Assume({a: Num, s: Str}, {a = 1; s = 2}) in %deepSeq% x x")
+            .unwrap_err();
+        eval_string("let x = Assume({a: Num, s: Str}, {a = \"a\"; s = \"b\"}) in %deepSeq% x x")
             .unwrap_err();
-        eval_string("let x = Assume({a: Num, s: Str}, {a = 1}) in deepSeq x x").unwrap_err();
-        eval_string("let x = Assume({a: Num, s: Str}, {s = \"a\"}) in deepSeq x x").unwrap_err();
+        eval_string("let x = Assume({a: Num, s: Str}, {a = 1}) in %deepSeq% x x").unwrap_err();
+        eval_string("let x = Assume({a: Num, s: Str}, {s = \"a\"}) in %deepSeq% x x").unwrap_err();
         eval_string(
-            "let x = Assume({a: Num, s: Str}, {a = 1; s = \"a\"; extra = 1}) in deepSeq x x",
+            "let x = Assume({a: Num, s: Str}, {a = 1; s = \"a\"; extra = 1}) in %deepSeq% x x",
         )
         .unwrap_err();
 
         assert_peq!(
-            "let x = Assume({a: Num, s: {foo: Bool}}, {a = 1; s = { foo = true}}) in deepSeq x x",
+            "let x = Assume({a: Num, s: {foo: Bool}}, {a = 1; s = { foo = true}}) in %deepSeq% x x",
             "{a = 1; s = { foo = true}}"
         );
         eval_string(
-            "let x = Assume({a: Num, s: {foo: Bool} }, {a = 1; s = { foo = 2}}) in deepSeq x x",
+            "let x = Assume({a: Num, s: {foo: Bool} }, {a = 1; s = { foo = 2}}) in %deepSeq% x x",
         )
         .unwrap_err();
-        eval_string("let x = Assume({a: Num, s: {foo: Bool} }, {a = 1; s = { foo = true; extra = 1}}) in deepSeq x x").unwrap_err();
-        eval_string("let x = Assume({a: Num, s: {foo: Bool} }, {a = 1; s = { }}) in deepSeq x x")
+        eval_string("let x = Assume({a: Num, s: {foo: Bool} }, {a = 1; s = { foo = true; extra = 1}}) in %deepSeq% x x").unwrap_err();
+        eval_string("let x = Assume({a: Num, s: {foo: Bool} }, {a = 1; s = { }}) in %deepSeq% x x")
             .unwrap_err();
     }
 
diff --git a/src/stdlib.rs b/src/stdlib.rs
index 00ab6c71..5493f95e 100644
--- a/src/stdlib.rs
+++ b/src/stdlib.rs
@@ -4,8 +4,10 @@ use crate::identifier::Ident;
 use crate::term::make as mk_term;
 use crate::term::{RichTerm, UnaryOp};
 
+pub const BUILTINS: &str = include_str!("../stdlib/builtins.ncl");
 pub const CONTRACTS: &str = include_str!("../stdlib/contracts.ncl");
 pub const LISTS: &str = include_str!("../stdlib/lists.ncl");
+pub const RECORDS: &str = include_str!("../stdlib/records.ncl");
 
 /// Accessors to the lists standard library.
 pub mod lists {
diff --git a/src/typecheck.rs b/src/typecheck.rs
index 7c3d3364..f33f6e8a 100644
--- a/src/typecheck.rs
+++ b/src/typecheck.rs
@@ -1429,9 +1429,11 @@ pub fn get_uop_type(
         UnaryOp::ListLength() => mk_tyw_arrow!(AbsType::List(), AbsType::Num()),
         // This should not happen, as ChunksConcat() is only produced during evaluation.
         UnaryOp::ChunksConcat(_, _, _) => panic!("cannot type ChunksConcat()"),
-        // forall rows. { rows } -> List
+        // BEFORE: forall rows. { rows } -> List
+        // Dyn -> List
         UnaryOp::FieldsOf() => mk_tyw_arrow!(
-            mk_tyw_record!(; TypeWrapper::Ptr(new_var(state.table))),
+            AbsType::Dyn(),
+            //mk_tyw_record!(; TypeWrapper::Ptr(new_var(state.table))),
             AbsType::List()
         ),
     })
@@ -1851,7 +1853,7 @@ mod tests {
 
         // We can typecheck any contract
         parse_and_typecheck(
-            "let alwaysTrue = fun l t => if t then t else blame l in
+            "let alwaysTrue = fun l t => if t then t else %blame% l in
             (fun x => x) : #alwaysTrue -> #alwaysTrue",
         )
         .unwrap();
@@ -1946,7 +1948,7 @@ mod tests {
         )
         .unwrap_err();
         parse_and_typecheck(
-            "(fun x => switch {bla => 1, ble => 2, bli => 4,} (embed bli x)) : <bla, ble> -> Num",
+            "(fun x => switch {bla => 1, ble => 2, bli => 4,} (%embed% bli x)) : <bla, ble> -> Num",
         )
         .unwrap();
 
@@ -2054,9 +2056,9 @@ mod tests {
 
     #[test]
     fn seq() {
-        parse_and_typecheck("seq false 1 : Num").unwrap();
-        parse_and_typecheck("(fun x y => seq x y) : forall a. (forall b. a -> b -> b)").unwrap();
-        parse_and_typecheck("let xDyn = false in let yDyn = 1 in (seq xDyn yDyn : Dyn)").unwrap();
+        parse_and_typecheck("%seq% false 1 : Num").unwrap();
+        parse_and_typecheck("(fun x y => %seq% x y) : forall a. (forall b. a -> b -> b)").unwrap();
+        parse_and_typecheck("let xDyn = false in let yDyn = 1 in (%seq% xDyn yDyn : Dyn)").unwrap();
     }
 
     #[test]
@@ -2073,16 +2075,18 @@ mod tests {
 
     #[test]
     fn lists_operations() {
-        parse_and_typecheck("fun l => tail l : List -> List").unwrap();
-        parse_and_typecheck("fun l => head l : List -> Dyn").unwrap();
-        parse_and_typecheck("fun f l => map f l : forall a. (forall b. (a -> b) -> List -> List)")
-            .unwrap();
+        parse_and_typecheck("fun l => %tail% l : List -> List").unwrap();
+        parse_and_typecheck("fun l => %head% l : List -> Dyn").unwrap();
+        parse_and_typecheck(
+            "fun f l => %map% f l : forall a. (forall b. (a -> b) -> List -> List)",
+        )
+        .unwrap();
         parse_and_typecheck("(fun l1 => fun l2 => l1 @ l2) : List -> List -> List").unwrap();
-        parse_and_typecheck("(fun i l => elemAt l i) : Num -> List -> Dyn ").unwrap();
+        parse_and_typecheck("(fun i l => %elemAt% l i) : Num -> List -> Dyn ").unwrap();
 
-        parse_and_typecheck("(fun l => head l) : forall a. (List -> a)").unwrap_err();
+        parse_and_typecheck("(fun l => %head% l) : forall a. (List -> a)").unwrap_err();
         parse_and_typecheck(
-            "(fun f l => elemAt (map f l) 0) : forall a. (forall b. (a -> b) -> List -> b)",
+            "(fun f l => %elemAt% (%map% f l) 0) : forall a. (forall b. (a -> b) -> List -> b)",
         )
         .unwrap_err();
     }
diff --git a/stdlib/builtins.ncl b/stdlib/builtins.ncl
new file mode 100644
index 00000000..2a2d6a3c
--- /dev/null
+++ b/stdlib/builtins.ncl
@@ -0,0 +1,13 @@
+{
+  builtins = {
+    isNum : Dyn -> Bool = fun x => %isNum% x;
+    isBool : Dyn -> Bool = fun x => %isBool% x;
+    isStr : Dyn -> Bool = fun x => %isStr% x;
+    isFun : Dyn -> Bool = fun x => %isFun% x;
+    isList : Dyn -> Bool = fun x => %isList% x;
+    isRecord : Dyn -> Bool = fun x => %isRecord% x;
+
+    seq : forall a. Dyn -> a -> a = fun x y => %seq% x y;
+    deepSeq : forall a. Dyn -> a -> a = fun x y => %deepSeq% x y;
+  }
+}
diff --git a/stdlib/contracts.ncl b/stdlib/contracts.ncl
index 1df6bb68..2695f7ed 100644
--- a/stdlib/contracts.ncl
+++ b/stdlib/contracts.ncl
@@ -1,73 +1,73 @@
 {
-    dyn = fun l t => t;
+  dyn = fun l t => t;
 
-    num = fun l t => if isNum t then t else blame l;
+  num = fun l t => if %isNum% t then t else %blame% l;
 
-    bool = fun l t => if isBool t then t else blame l;
+  bool = fun l t => if %isBool% t then t else %blame% l;
 
-    string = fun l t => if isStr t then t else blame l;
+  string = fun l t => if %isStr% t then t else %blame% l;
 
-    list = fun l t => if isList t then t else blame l;
+  list = fun l t => if %isList% t then t else %blame% l;
 
-    func = fun s t l e =>
-        if isFun e then
-            (fun x => t (goCodom l) (e (s (chngPol (goDom l)) x)))
-        else
-            blame l;
+  func = fun s t l e =>
+      if %isFun% e then
+          (fun x => t (%goCodom% l) (e (s (%chngPol% (%goDom% l)) x)))
+      else
+          %blame% l;
 
-    forall_var = fun sy pol l t =>
-        let lPol = polarity l in
-        if pol == lPol then
-            unwrap sy t (blame l)
-        else
-            wrap sy t;
+  forall_var = fun sy pol l t =>
+      let lPol = %polarity% l in
+      if pol == lPol then
+          %unwrap% sy t (%blame% l)
+      else
+          %wrap% sy t;
 
-    fail = fun l t => blame (tag "Fail" l);
+  fail = fun l t => %blame% (%tag% "Fail" l);
 
-    row_extend = fun contr case l t =>
-        if (case t) then
-            t
-        else
-            contr (tag "NotRowExt" l) t;
+  row_extend = fun contr case l t =>
+      if (case t) then
+          t
+      else
+          contr (%tag% "NotRowExt" l) t;
 
-    record = fun cont l t =>
-        if isRecord t then
-            cont {} l t
-        else
-            blame (tag "not a record" l);
+  record = fun cont l t =>
+      if %isRecord% t then
+          cont {} l t
+      else
+          %blame% (%tag% "not a record" l);
 
-    dyn_record = fun contr l t =>
-        if isRecord t then
-            mapRec (fun _field => contr l) t
-        else
-            blame (tag "not a record" l);
+  dyn_record = fun contr l t =>
+      if %isRecord% t then
+          %mapRec% (fun _field => contr l) t
+      else
+          %blame% (%tag% "not a record" l);
 
-    record_extend = fun field contr cont acc l t =>
-        if hasField field t then
-            let acc = acc$[field = contr (goField field l) (t.$field)] in
-            let t = t -$ field in
-            cont acc l t
-        else
-            blame (tag "missing field" l);
+  record_extend = fun field contr cont acc l t =>
+      if %hasField% field t then
+          let acc = acc$[field = contr (%goField% field l) (t.$field)] in
+          let t = t -$ field in
+          cont acc l t
+      else
+          %blame% (%tag% "missing field" l);
 
-    forall_tail = fun sy pol acc l t =>
-        let magic_fld = "_%wrapped" in
-        if pol == (polarity l) then
-            if hasField magic_fld t then
-                if (t -$ magic_fld) == {} then
-                    let fail = blame (tag "polymorphic tail mismatch" l) in
-                    let inner = unwrap sy (t.$magic_fld) fail in
-                    acc & inner
-                else
-                    blame (tag "extra field" l)
-            else
-                blame (tag "missing polymorphic part" l)
-        else
-            acc$[magic_fld = wrap sy t];
+  forall_tail = fun sy pol acc l t =>
+      let magic_fld = "_%wrapped" in
+      if pol == (%polarity% l) then
+          if %hasField% magic_fld t then
+              if (t -$ magic_fld) == {} then
+                  let fail = %blame% (%tag% "polymorphic tail mismatch" l) in
+                  let inner = %unwrap% sy (t.$magic_fld) fail in
+                  acc & inner
+              else
+                  %blame% (%tag% "extra field" l)
+          else
+              %blame% (%tag% "missing polymorphic part" l)
+      else
+          acc$[magic_fld = %wrap% sy t];
 
     dyn_tail = fun acc l t => acc & t;
 
     empty_tail = fun acc l t =>
         if t == {} then acc
-        else blame (tag "extra field" l);
+        else %blame% (%tag% "extra field" l);
 }
diff --git a/stdlib/lists.ncl b/stdlib/lists.ncl
index 62aa8dde..091c41ad 100644
--- a/stdlib/lists.ncl
+++ b/stdlib/lists.ncl
@@ -1,21 +1,31 @@
 {
   lists = {
+    head : List -> Dyn = fun l => %head% l;
+
+    tail : List -> List = fun l => %tail% l;
+
+    length : List -> Num = fun l => %length% l;
+
+    map : (Dyn -> Dyn) -> List -> List = fun f l => %map% f l;
+
+    elemAt : List -> Num -> Dyn = fun l n => %elemAt% l n;
+
     concat : List -> List -> List = fun l1 l2 => l1 @ l2;
 
     foldl : forall a. (a -> Dyn -> a) -> a -> List -> a =
       fun f fst l =>
-        if length l == 0 then
+        if %length% l == 0 then
           fst
         else
-          let rest = foldl f fst (tail l) in
-          seq rest (f rest (head l));
+          let rest = foldl f fst (%tail% l) in
+          %seq% rest (f rest (%head% l));
 
     fold : forall a. (Dyn -> a -> a) -> List -> a -> a =
       fun f l fst =>
-        if length l == 0 then
+        if %length% l == 0 then
           fst
         else
-          f (head l) (fold f (tail l) fst);
+          f (%head% l) (fold f (%tail% l) fst);
 
     cons : Dyn -> List -> List = fun x l => [x] @ l;
 
diff --git a/stdlib/records.ncl b/stdlib/records.ncl
new file mode 100644
index 00000000..7b22bad9
--- /dev/null
+++ b/stdlib/records.ncl
@@ -0,0 +1,10 @@
+{
+  records = {
+    map : forall a b. (Str -> a -> b) -> {_: a} -> {_: b} = fun f r => %mapRec% f r;
+
+    // TODO: change Dyn to { | Dyn} once the PR introducing open contracts lands
+    fieldsOf : Dyn -> List = fun r => %fieldsOf% r;
+
+    hasField : Str -> Dyn -> Bool = fun r field => %hasField% r field;
+  }
+}


Test patch:
diff --git a/src/parser/tests.rs b/src/parser/tests.rs
index 95ae11b6..fab08fa1 100644
--- a/src/parser/tests.rs
+++ b/src/parser/tests.rs
@@ -137,11 +137,11 @@ fn lets() {
 #[test]
 fn unary_op() {
     assert_eq!(
-        parse_without_pos("isNum x"),
+        parse_without_pos("%isNum% x"),
         mk_term::op1(UnaryOp::IsNum(), mk_term::var("x"))
     );
     assert_eq!(
-        parse_without_pos("isNum x y"),
+        parse_without_pos("%isNum% x y"),
         mk_app!(
             mk_term::op1(UnaryOp::IsNum(), mk_term::var("x")),
             mk_term::var("y")