Repository: tweag/nickel
Pull request #1195 (2023-03-23 11:48:19)

Stdlib array extension
Following #935, add a batch of missing functions to the array stdlib. This PR adds a `slice` primitive operation as well, required to implement the corresponding function of the stdlib. This PR adds a new `enum` stdlib module as well, moving a few functions/contracts from the `string` module.

Doing so, we also expanded the documentation of folds, by adding a more informal description as well as a paragraph on `fold_right` vs `fold_left`. This is useful as a reference for the documentation of `reduce_right` and `reduce_left` too.

## Follow-up

We can now get rid of the `%tail%` primop, which is subsumed by `%slice% 1 (%length% <.>)`. In the same spirit, we should probably get rid of `%head%` in favor of `%elem_at% 0`. This is planned in a follow-up PR.


Patch:
diff --git a/src/eval/operation.rs b/src/eval/operation.rs
index ded355cb..ec4ba7cd 100644
--- a/src/eval/operation.rs
+++ b/src/eval/operation.rs
@@ -2305,7 +2305,6 @@ impl<R: ImportResolver, C: Cache> VirtualMachine<R, C> {
                 MergeMode::Standard,
                 &mut self.call_stack,
             ),
-
             BinaryOp::Hash() => {
                 let mk_err_fst = |t1| {
                     Err(EvalError::TypeError(
@@ -3280,6 +3279,118 @@ impl<R: ImportResolver, C: Cache> VirtualMachine<R, C> {
                     pos2.into_inherited(),
                 )))
             }
+            NAryOp::ArraySlice() => {
+                let mut args = args.into_iter();
+
+                let (
+                    Closure {
+                        body:
+                            RichTerm {
+                                term: t1,
+                                pos: pos1,
+                            },
+                        ..
+                    },
+                    fst_pos,
+                ) = args.next().unwrap();
+
+                let (
+                    Closure {
+                        body:
+                            RichTerm {
+                                term: t2,
+                                pos: pos2,
+                            },
+                        ..
+                    },
+                    snd_pos,
+                ) = args.next().unwrap();
+
+                let (
+                    Closure {
+                        body:
+                            RichTerm {
+                                term: t3,
+                                pos: pos3,
+                            },
+                        env: env3,
+                    },
+                    third_pos,
+                ) = args.next().unwrap();
+                debug_assert!(args.next().is_none());
+
+                let Term::Num(ref start) = &*t1 else {
+                    return Err(EvalError::TypeError(
+                        String::from("Number"),
+                        String::from("%array_slice%, 1st argument"),
+                        fst_pos,
+                        RichTerm {
+                            term: t1,
+                            pos: pos1,
+                        },
+                    ));
+                };
+
+                let Term::Num(ref end) = &*t2 else {
+                    return Err(EvalError::TypeError(
+                        String::from("Number"),
+                        String::from("%array_slice%, 2nd argument"),
+                        snd_pos,
+                        RichTerm {
+                            term: t2,
+                            pos: pos2,
+                        },
+                    ));
+                };
+
+                let t3_owned = t3.into_owned();
+
+                let Term::Array(mut array, attrs) = t3_owned else {
+                    return Err(EvalError::TypeError(
+                        String::from("Array"),
+                        String::from("%array_slice%, 3rd argument"),
+                        third_pos,
+                        RichTerm::new(t3_owned, pos3),
+                    ));
+                };
+
+                let Ok(start_as_usize) = usize::try_from(start) else {
+                    return Err(EvalError::Other(
+                        format!(
+                            "%array_slice%: expected the 1st argument (start) to be a positive integer smaller than {}, got {start}",
+                            usize::MAX
+                        ),
+                        pos_op
+                    ));
+                };
+
+                let Ok(end_as_usize) = usize::try_from(end) else {
+                    return Err(EvalError::Other(
+                        format!(
+                            "%array_slice%: expected the 2nd argument (end) to be a positive integer smaller than {}, got {end}",
+                            usize::MAX
+                        ),
+                        pos_op
+                    ));
+                };
+
+                let result = array.slice(start_as_usize, end_as_usize);
+
+                if let Err(crate::term::array::OutOfBoundError) = result {
+                    return Err(EvalError::Other(
+                        format!(
+                            "%array_slice%: index out of bounds. Expected `start <= end <= {}`, but got `start={start}` and `end={end}`.",
+                            array.len()
+                        ),
+                        pos_op
+                    ));
+                };
+
+                Ok(Closure {
+                    body: RichTerm::new(Term::Array(array, attrs), pos_op_inh),
+                    env: env3,
+                })
+            }
         }
     }
 }
diff --git a/src/parser/grammar.lalrpop b/src/parser/grammar.lalrpop
index 6c9af2cb..1d2588bd 100644
--- a/src/parser/grammar.lalrpop
+++ b/src/parser/grammar.lalrpop
@@ -880,6 +880,8 @@ NOpPre<ArgRule>: UniTerm = {
         UniTerm::from(mk_opn!(NAryOp::RecordUnsealTail(), t1, t2, t3)),
     "insert_type_variable" <key: ArgRule> <pol: ArgRule> <label: ArgRule> =>
         UniTerm::from(mk_opn!(NAryOp::InsertTypeVar(), key, pol, label)),
+    "array_slice" <t1: ArgRule> <t2: ArgRule> <t3: ArgRule> =>
+        UniTerm::from(mk_opn!(NAryOp::ArraySlice(), t1, t2, t3)),
 }
 
 TypeBuiltin: Types = {
@@ -1072,6 +1074,7 @@ extern {
         "label_with_notes" => Token::Normal(NormalToken::LabelWithNotes),
         "label_append_note" => Token::Normal(NormalToken::LabelAppendNote),
         "label_push_diag" => Token::Normal(NormalToken::LabelPushDiag),
+        "array_slice" => Token::Normal(NormalToken::ArraySlice),
 
         "{" => Token::Normal(NormalToken::LBrace),
         "}" => Token::Normal(NormalToken::RBrace),
diff --git a/src/parser/lexer.rs b/src/parser/lexer.rs
index 2324c084..19eea13c 100644
--- a/src/parser/lexer.rs
+++ b/src/parser/lexer.rs
@@ -324,6 +324,8 @@ pub enum NormalToken<'input> {
     LabelAppendNote,
     #[token("%label_push_diag%")]
     LabelPushDiag,
+    #[token("%array_slice%")]
+    ArraySlice,
 
     #[token("{")]
     LBrace,
diff --git a/src/stdlib.rs b/src/stdlib.rs
index da43042f..72881c13 100644
--- a/src/stdlib.rs
+++ b/src/stdlib.rs
@@ -5,7 +5,7 @@ use crate::term::make as mk_term;
 use crate::term::RichTerm;
 
 /// This is an array containing all the Nickel standard library modules.
-pub fn modules() -> [StdlibModule; 8] {
+pub fn modules() -> [StdlibModule; 9] {
     [
         StdlibModule::Builtin,
         StdlibModule::Contract,
@@ -14,6 +14,7 @@ pub fn modules() -> [StdlibModule; 8] {
         StdlibModule::String,
         StdlibModule::Number,
         StdlibModule::Function,
+        StdlibModule::Enum,
         StdlibModule::Internals,
     ]
 }
@@ -28,6 +29,7 @@ pub enum StdlibModule {
     String,
     Number,
     Function,
+    Enum,
     Internals,
 }
 
@@ -41,6 +43,7 @@ impl StdlibModule {
             StdlibModule::String => "<stdlib/string.ncl>",
             StdlibModule::Number => "<stdlib/number.ncl>",
             StdlibModule::Function => "<stdlib/function.ncl>",
+            StdlibModule::Enum => "<stdlib/enum.ncl>",
             StdlibModule::Internals => "<stdlib/internals.ncl>",
         }
     }
@@ -54,6 +57,7 @@ impl StdlibModule {
             StdlibModule::String => include_str!("../stdlib/string.ncl"),
             StdlibModule::Number => include_str!("../stdlib/number.ncl"),
             StdlibModule::Function => include_str!("../stdlib/function.ncl"),
+            StdlibModule::Enum => include_str!("../stdlib/enum.ncl"),
             StdlibModule::Internals => include_str!("../stdlib/internals.ncl"),
         }
     }
@@ -73,6 +77,7 @@ impl TryFrom<Ident> for StdlibModule {
             "string" => StdlibModule::String,
             "number" => StdlibModule::Number,
             "function" => StdlibModule::Function,
+            "enum" => StdlibModule::Enum,
             "internals" => StdlibModule::Internals,
             _ => return Err(UnknownStdlibModule),
         };
@@ -90,6 +95,7 @@ impl From<StdlibModule> for Ident {
             StdlibModule::String => "string",
             StdlibModule::Number => "number",
             StdlibModule::Function => "function",
+            StdlibModule::Enum => "enum",
             StdlibModule::Internals => "internals",
         };
         Ident::from(name)
diff --git a/src/term/array.rs b/src/term/array.rs
index 13f24fb6..d3a318ea 100644
--- a/src/term/array.rs
+++ b/src/term/array.rs
@@ -53,6 +53,10 @@ impl ArrayAttrs {
     }
 }
 
+/// A Nickel array, represented as a view (slice) into a shared backing array. The view is
+/// delimited by `start` (included) and `end` (excluded). This allows to take the tail of an array,
+/// or an arbitrary slice, in constant time, providing actual linear time iteration when
+/// imlementing recursive functions, such as folds, for example.
 #[derive(Debug, Clone, PartialEq)]
 pub struct Array {
     inner: Rc<[RichTerm]>,
@@ -60,6 +64,8 @@ pub struct Array {
     end: usize,
 }
 
+pub struct OutOfBoundError;
+
 impl Array {
     /// Creates a Nickel array from reference-counted slice.
     pub fn new(inner: Rc<[RichTerm]>) -> Self {
@@ -69,6 +75,23 @@ impl Array {
         Self { inner, start, end }
     }
 
+    /// Resize the view to be a a sub-view of the current one, by considering a slice `start`
+    /// (included) to `end` (excluded).
+    ///
+    /// The parameters must satisfy `0 <= start <= end <= self.end - self.start`. Otherwise,
+    /// `Err(..)` is returned.
+    pub fn slice(&mut self, start: usize, end: usize) -> Result<(), OutOfBoundError> {
+        if start > end || end > self.len() {
+            return Err(OutOfBoundError);
+        }
+
+        let prev_start = self.start;
+        self.start = prev_start + start;
+        self.end = prev_start + end;
+
+        Ok(())
+    }
+
     /// Returns the effective length of the array.
     pub fn len(&self) -> usize {
         self.end - self.start
diff --git a/src/term/mod.rs b/src/term/mod.rs
index 9f50d399..ad0435e0 100644
--- a/src/term/mod.rs
+++ b/src/term/mod.rs
@@ -1375,6 +1375,10 @@ pub enum NAryOp {
     ///   - the [kind](types::VarKind) of the type variable
     ///   - a [label](Term::Label) on which to operate
     InsertTypeVar(),
+    /// Return a sub-array corresponding to a range. Given that Nickel uses array slices under the
+    /// hood, as long as the array isn't modified later, this operation is constant in time and
+    /// memory.
+    ArraySlice(),
 }
 
 impl NAryOp {
@@ -1385,7 +1389,8 @@ impl NAryOp {
             | NAryOp::StrSubstr()
             | NAryOp::MergeContract()
             | NAryOp::RecordUnsealTail()
-            | NAryOp::InsertTypeVar() => 3,
+            | NAryOp::InsertTypeVar()
+            | NAryOp::ArraySlice() => 3,
             NAryOp::RecordSealTail() => 4,
         }
     }
@@ -1394,13 +1399,14 @@ impl NAryOp {
 impl fmt::Display for NAryOp {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         match self {
-            NAryOp::StrReplace() => write!(f, "strReplace"),
-            NAryOp::StrReplaceRegex() => write!(f, "strReplaceRegex"),
+            NAryOp::StrReplace() => write!(f, "str_replace"),
+            NAryOp::StrReplaceRegex() => write!(f, "str_replace_regex"),
             NAryOp::StrSubstr() => write!(f, "substring"),
-            NAryOp::MergeContract() => write!(f, "mergeContract"),
-            NAryOp::RecordSealTail() => write!(f, "%record_seal_tail%"),
-            NAryOp::RecordUnsealTail() => write!(f, "%record_unseal_tail%"),
-            NAryOp::InsertTypeVar() => write!(f, "%insert_type_variable%"),
+            NAryOp::MergeContract() => write!(f, "merge_contract"),
+            NAryOp::RecordSealTail() => write!(f, "record_seal_tail"),
+            NAryOp::RecordUnsealTail() => write!(f, "record_unseal_tail"),
+            NAryOp::InsertTypeVar() => write!(f, "insert_type_variable"),
+            NAryOp::ArraySlice() => write!(f, "array_slice"),
         }
     }
 }
diff --git a/src/typecheck/operation.rs b/src/typecheck/operation.rs
index cd5f44c8..b0fccbcf 100644
--- a/src/typecheck/operation.rs
+++ b/src/typecheck/operation.rs
@@ -437,7 +437,7 @@ pub fn get_bop_type(
 }
 
 pub fn get_nop_type(
-    _state: &mut State,
+    state: &mut State,
     op: &NAryOp,
 ) -> Result<(Vec<UnifType>, UnifType), TypecheckError> {
     Ok(match op {
@@ -470,6 +470,19 @@ pub fn get_nop_type(
             ],
             mk_uniftype::dynamic(),
         ),
+        // Num -> Num -> Array a -> Array a
+        NAryOp::ArraySlice() => {
+            let element_type = state.table.fresh_type_uvar();
+
+            (
+                vec![
+                    mk_uniftype::num(),
+                    mk_uniftype::num(),
+                    mk_uniftype::array(element_type.clone()),
+                ],
+                mk_uniftype::array(element_type),
+            )
+        }
         // This should not happen, as MergeContract() is only produced during evaluation.
         NAryOp::MergeContract() => panic!("cannot typecheck MergeContract()"),
         // Morally: Sym -> Polarity -> Lbl -> Lbl
diff --git a/stdlib/array.ncl b/stdlib/array.ncl
index f3c4f097..c23bcbda 100644
--- a/stdlib/array.ncl
+++ b/stdlib/array.ncl
@@ -47,7 +47,7 @@
             [ 2, 3 ]
         ```
         "%
-      = fun l => %tail% l,
+      = fun array => %array_slice% 1 (%length% array) array,
 
     drop_last : forall a. Array a -> Array a
       | doc m%"
@@ -59,11 +59,7 @@
             [ 1, 2 ]
         ```
         "%
-      # TODO: we need a slice primop
-      = fun l => l
-        |> reverse
-        |> drop_first
-        |> reverse,
+      = fun array => %array_slice% 0 (%length% array - 1) array,
 
     length : forall a. Array a -> Number
       | doc m%"
@@ -116,12 +112,62 @@
 
     fold_left : forall a b. (a -> b -> a) -> a -> Array b -> a
       | doc m%"
-        Fold a function over an array.
+        Fold a function over an array. Folds serve a similar purpose to loops or
+        iterators in a functional language like Nickel. `fold_left` iterates over
+        an array, by repeatedly applying a function over each element, threading
+        an additional arbitrary state (the accumulator, of type `a` in the
+        signature).
+
         `fold_left f init [x1, x2, ..., xn]` results in `f (... (f (f init x1) x2) ...) xn`.
 
         This function is strict in the intermediate accumulator.
 
-        For example:
+        # Left vs right
+
+        Folds come in two variants, left and right. How to decide which one to
+        use?
+
+        - If the folded function isn't associative (such as subtraction), then
+          each variant will give a different result. The choice is dictacted by
+          which one you need. For example:
+
+          ```nickel
+          array.fold_right (-) 0 [1, 2, 3, 4]
+           => -2
+          array.fold_left (-) 0 [1, 2, 3, 4]
+           => -10
+          ```
+        - If the folded function is associative, both `fold_right` and
+          `fold_left` return the same result. In that case, **`fold_left` is
+          generally preferred**, because it forces the evaluation of the
+          intermediate results resulting in less memory consumption and overall
+          better performance (outside of pathological cases).
+          `fold_left` also iterates from the start of the array, which
+          correponds to the usual behavior of loops and iterators in most
+          programming languages. There is one case where `fold_right` might be
+          preferred, see the next point.
+        - If the folded function is associative but _(left) short-circuiting_,
+          meaning that it can sometimes determine the result without using the
+          right argument, then `fold_right` provides early return. An example is
+          the boolean AND operator `&&`: when evaluating `left && right`, if
+          `left` is `false`, the whole expression will evaluate to `false`
+          without even evaluating `right`. Consider the following expression:
+
+          ```nickel
+          array.replicate 1000 true
+          # gives [false, .. true 1000 times]
+          |> array.prepend false
+          |> array.fold_right (&&) [false]
+          ```
+
+          Here, `fold_right` will stop at the first element, and the operation
+          runs in constant time, given the definition of `fold_right` and the
+          lazy evaluation of Nickel. If we had used `fold_left` instead, which
+          is closer to a standard iterator, we would have iterated over all of
+          the 1000 elements of the array.
+
+        # Examples
+
         ```nickel
           fold_left (fun acc e => acc + e) 0 [ 1, 2, 3 ] =>
             (((0 + 1) + 2) 3) =>
@@ -142,10 +188,21 @@
 
     fold_right : forall a b. (a -> b -> b) -> b -> Array a -> b
       | doc m%"
-        Fold a function over a array.
+        Fold a function over an array. Folds serve a similar purpose to loops or
+        iterators in a functional language like Nickel. `fold_right` iterates
+        over an array, by repeatedly applying a function to each element and
+        threading an additional arbitrary state (the accumulator of type `a` in
+        the signature).
+
         `fold_right f init [x1, x2, ..., xn]` results in `f x1 (f x2 (... (f xn init) ...))`.
 
-        For example:
+        # Left vs right
+
+        Folds come in two variants, left and right. How to decide which one to
+        use? Please refer to the documentation of `fold_left`.
+
+        # Examples
+
         ```nickel
           fold_right (fun e acc => acc @ [e]) [] [ 1, 2, 3 ] =>
             ((([] @ [3]) @ [2]) @ [1]) =>
@@ -346,5 +403,193 @@
         if %length% arr <= 1
         then arr
         else [ %head% arr ] @ (%tail% arr |> flat_map (fun a => [v, a])),
+
+    slice
+      : forall a. Number -> Number -> Array a -> Array a
+      | doc m%"
+          `slice start end array` returns the slice of `array` between `start` (included) and
+          `end` (excluded).
+
+          # Preconditions
+
+          In `slice start end value`, `start` and `end` must be positive
+          integers such that `0 <= start <= end <= array.length value`.
+
+          # Examples
+
+          ```nickel
+          slice 1 3 [ 0, 1, 2, 3, 4, 5]
+            => [ 1, 2 ]
+          slice 0 3 [ "Hello", "world", "!" ]
+            => [ "Hello", "world", "!" ]
+          slice 2 3 [ "Hello", "world", "!" ]
+            => [ "!" ]
+           ```
+        "%
+      = fun start end value => %array_slice% start end value,
+
+    split_at
+      : forall a. Number -> Array a -> {left: Array a, right: Array a}
+      | doc m%"
+          Splits an array in two at a given index, and puts all the elements
+          to the left of the element at the given index (excluded) in the
+          `left` field, and the rest of the array in the `right` field.
+
+          # Preconditions
+
+          In `split_at inded value`, `index` must be a positive integer such
+          that `0 <= index <= array.length value`.
+
+          # Examples
+
+          ```nickel
+          split_at 2 [ 0, 1, 2, 3, 4, 5]
+            => { left = [ 2, 3, 4, 5 ], right = [ 0, 1 ] }
+          split_at 0 [ "Hello", "world", "!" ]
+            => { left = [  ], right = [ "Hello", "world", "!" ] }
+          split_at 3 [ "Hello", "world", "!" ]
+            => { left = [ "Hello", "world", "!" ], right = [  ] }
+          ```
+        "%
+      = fun index value => {
+        left = %array_slice% 0 index value,
+        right = %array_slice% index (%length% value) value
+      },
+
+    replicate
+      : forall a. Number -> a -> Array a
+      | doc m%"
+          `replicate n x` creates an array containing `x` exactly `n` times.
+
+          # Preconditions
+
+          `n` must be an integer greater or equal to `0`.
+
+          # Examples
+
+          ```nickel
+          replicate 0 false
+            => [ ]
+          replicate 5 "x"
+            => [ "x", "x", "x", "x", "x" ]
+          ```
+        "%
+      = fun n x => %generate% n (fun _i => x),
+
+    range_step
+      : Number -> Number -> Number -> Array Number
+      | doc m%"
+          `range_step start end step` generates the array of numbers
+          `[start, start + step, start + 2*step, ..]` up to the first element
+          (excluded) larger than or equal to `end`
+
+          # Preconditions
+
+          In `range_step start end step`, `start` and `end` must satisfy `start
+          <= end`. `step` must be strictly greater than `0`.
+
+          # Examples
+
+          ```nickel
+          range_step (-1.5) 2 0.5
+           => [ -1.5, -1, -0.5, 0, 0.5, 1, 1.5 ]
+          ```
+        "%
+      = fun start end step => %generate%
+          ((end - start) / step |> number.floor)
+          (fun i => start + i*step),
+
+    range
+      : Number -> Number -> Array Number
+      | doc m%"
+          `range start end` generates the array of numbers
+          `[start, start + 1, start + 2, ..]` up to the first element
+          (excluded) larger than or equal to `end`.
+
+          `range start end` is equivalent to `range_step start end 1`.
+
+          # Preconditions
+
+          In `range_step start end`, `start` and `end` must satisfy
+          `start <= end`.
+
+          # Examples
+
+          ```nickel
+          range 0 5
+           => [ 0, 1, 2, 3, 4 ]
+          ```
+        "%
+      = fun start end => range_step start end 1,
+
+    reduce_left
+      : forall a. (a -> a -> a) -> Array a -> a
+      | doc m%"
+        Reduces the elements to a single one, by repeatedly applying a reducing
+        operation. If the array is empty, returns an empty array.
+
+        `reduce_left` associates to the left, that is
+        `reduce_left op [x1, x2, ..., xn]` results in `op (... (op (op x1 x2) x3) ...) xn`.
+
+        `reduce_left` is the same as `fold_left`, but uses the first element as
+        the initial accumulator.
+
+        # Left vs right
+
+        The rationale to decide between `fold_left` and `fold_right` applies to
+        `reduce_left` and `reduce_right` as well. See the documentation of
+        `fold_left`.
+
+        # Examples
+
+        ```nickel
+          reduce_left (@) [ [1, 2], [3], [4,5] ]
+            => (([1, 2] @ [3]) @ [4,5])
+            => [ 1, 2, 4, 5 ]
+          reduce_left (-) [ 1, 2, 3, 4]
+            => ((1 - 2) - 3) - 4
+            => -8
+        ```
+        "%
+      = fun f array =>
+        let first = %elem_at% array 0 in
+        let rest = %array_slice% 1 (%length% array) array in
+        fold_left f first rest,
+
+    reduce_right
+      : forall a. (a -> a -> a) -> Array a -> a
+      | doc m%"
+        Reduces the elements to a single one, by repeatedly applying a reducing
+        operation. If the array is empty, returns an empty array.
+
+        `reduce_right` associates to the right, that is
+        `reduce_right op [x1, x2, ..., xn]` results in
+        `op x1 (op x2 (... (op xn-1 xn) ...))`.
+
+        `reduce_right` is the same as `fold_right`, but uses the last element as
+        the initial element.
+
+        # Left vs right
+
+        The rationale to decide between `fold_left` and `fold_right` applies to
+        `reduce_left` and `reduce_right` as well. See the documentation of
+        `fold_left`.
+
+        # Examples
+
+        ```nickel
+          reduce_right (@) [ [1, 2], [3], [4,5] ]
+            => [1, 2] @ ([3] @ [4,5])
+            => [ 1, 2, 4, 5 ]
+          reduce_right (-) [ 1, 2, 3, 4]
+            => 1 - (2 - (3 - 4))
+            => -2
+        ```
+        "%
+      = fun f array =>
+         let last_index = %length% array - 1 in
+         let last =  %elem_at% array last_index in
+         let rest = %array_slice% 0 last_index array in
+         fold_right f last rest,
   }
 }
diff --git a/stdlib/enum.ncl b/stdlib/enum.ncl
new file mode 100644
index 00000000..e4b04482
--- /dev/null
+++ b/stdlib/enum.ncl
@@ -0,0 +1,62 @@
+{
+    enum = {
+      Tag
+        | doc m%"
+          Contract to enforce the value is an enum tag.
+
+          # Examples
+
+          ```nickel
+            (`foo | Tag) =>
+              `foo
+            (`FooBar | Tag) =>
+              `FooBar
+            ("tag" | Tag) =>
+              error
+          ```
+          "%
+        = contract.from_predicate builtin.is_enum,
+
+      TagOrString
+        | doc m%%"
+            Accepts both enum tags and strings. Strings are automatically
+            converted to an enum tag.
+
+            `TagOrString` is typically used in conjunction with an enum type, to
+            accept tags represented as strings (e.g. coming from a JSON
+            serialization) as well.
+
+            # Examples
+
+            ``` nickel
+            let Schema = {
+              protocol
+                | enum.TagOrString
+                | [| `http, `ftp |],
+              port
+                | Number,
+              method
+                | enum.TagOrString
+                | [| `GET, `POST |]
+            } in
+            let serialized =
+              m%"
+                {"protocol": "http", "port": 80, "method": "GET"}
+              "%
+              |> builtin.deserialize `Json
+            in
+
+            serialized | Schema
+            ```
+          "%%
+        = fun label value =>
+          %typeof% value
+          |> match {
+            `String => %enum_from_str% value,
+            `Enum => value,
+             _ => contract.blame_with_message
+               "expected either a string or an enum tag"
+               label,
+            },
+    }
+}
diff --git a/stdlib/record.ncl b/stdlib/record.ncl
index a2425b10..f698ca85 100644
--- a/stdlib/record.ncl
+++ b/stdlib/record.ncl
@@ -107,7 +107,7 @@
         else
           r in
         %record_insert% field r content,
-    
+
     map_values : forall a b. (a -> b) -> {_: a} -> {_: b}
     | doc m%"
       Maps a function over every field value of a record.
@@ -159,7 +159,7 @@
     is_empty : forall a. {_: a} -> Bool
     | doc m%"
       Check whether a record is empty.
-      
+
       ```nickel
       is_empty {} => true
       is_empty { foo = 1 } => false
diff --git a/stdlib/string.ncl b/stdlib/string.ncl
index 1e673fca..268ee877 100644
--- a/stdlib/string.ncl
+++ b/stdlib/string.ncl
@@ -76,22 +76,6 @@
       else
         %blame% (%label_with_message% "not a string" l),
 
-    EnumTag
-    | doc m%"
-      Contract to enforce the value is an enum tag.
-
-      For example:
-      ```nickel
-        (`foo | EnumTag) =>
-          `foo
-        (`FooBar | EnumTag) =>
-          `FooBar
-        ("tag" | EnumTag) =>
-          error
-      ```
-      "%
-    = contract.from_predicate builtin.is_enum,
-
     Stringable
     | doc m%"
       Contract to enforce the value is convertible to a string via
@@ -434,7 +418,7 @@
     = from,
 
     # from_enum | < | Dyn> -> String = fun tag => %to_str% tag,
-    from_enum | EnumTag -> String
+    from_enum | enum.Tag -> String
     | doc m%"
       Converts an enum variant to its string representation.
 
@@ -487,7 +471,7 @@
     = fun s => s == "true",
 
     # to_enum | String -> < | Dyn> = fun s => %enum_from_str% s,
-    to_enum | String -> EnumTag
+    to_enum | String -> enum.Tag
     | doc m%"
       Converts any string that represents an enum variant to that enum variant.
 


Test patch:
diff --git a/tests/integration/pass/stdlib_string.ncl b/tests/integration/pass/stdlib_string.ncl
index d7b7cb52..c994178c 100644
--- a/tests/integration/pass/stdlib_string.ncl
+++ b/tests/integration/pass/stdlib_string.ncl
@@ -13,8 +13,8 @@ let {check, ..} = import "lib/assert.ncl" in
   ("9001" | string.NumLiteral) == "9001",
   # string.CharLiteral
   ("e" | string.Character) == "e",
-  # string.EnumTag
-  (`Foo | string.EnumTag) == `Foo,
+  # enum.Tag
+  (`Foo | enum.Tag) == `Foo,
   # string.Stringable
   (`Foo | string.Stringable) == `Foo,
   (true | string.Stringable) == true,