Recursive records and recursion

[yannham]

In Nix, the rec keyword allows a field of a record to cross-reference the other fields of the same record. Jsonnet also provides this possibility via self. This is commonly used for sharing and reusing data as in (Nix syntax):

/* Share a single source of truth */
rec {
    name="my-pkg";
    version="1.1.2";
    url="https://someurl/tarballs/my-pkg-${version}";
    /* ... */
}

/* Code reuse */
rec {
    /* Actual code from Nixpkg */
    concatMap = /* ... */

    flatten = x:
        if isList x
        then concatMap (y: flatten y) x
        else [x];
    }
}

We propose to add recursive records to Nickel.

General recursion

Recursive records are a source of general recursion (although not the only one), as fields may reference themselves, directly or indirectly. This is exemplified in the definition of flatten above. Nickel is a configuration language, and most of its use cases should not require the use of general recursion. Several languages competing in the same domain are not Turing-complete, such as Dhall, CUE or Starlark. But recursion is hard to rule out in an untyped language with higher-order functions:

• Untyped higher-order functions allow to write fix-point combinators
• Even without higher order functions, recursive bindings such as Nix rec or mutually recursive top-level procedures may introduce direct or indirect recursion

The aforementioned languages sidestep these points because:

• Dhall is statically typed
• CUE does not feature higher-order functions
• Starlark is not able to statically exclude recursive calls. Instead, the runtime detects recursion and immediately aborts the program

Moreover, even if rare, there are legitimate cases which require general recursion. Our intent is to offer great defaults, in particular for building and traversing data structures so that explicit recursion is almost never needed. But also to offer an escape hatch when there is no better solution. We propose to introduce recursion and recursive records, but in a way that makes accessing true recursion really explicit, or even a bit awkward.

Proposals

Recursive records

1. à la Nix

Add a rec keyword which, when put before the definition a record, brings all the fields in scope.

• This makes fields available to nested records
• However, in Nix, one cannot restrict which fields of the record are accessible: it is all or nothing
• There is also no mean to tell at the usage site if an identifier is a recursive field or has been introduced by a standard binding

2. Self/This

Introduce a special variable which refers to the current record, self, to access other fields.

• This makes cross-references explicit at usage site
• It does not make fields available to nested records. One has to provide a parent or super keyword for that, or to allow let bindings inside records to capture self in a local variable (both are done in Jsonet)

3. Recursive let-binding

as in OCaml, use an explicit let rec form for recursive bindings. A recursive record can be written as let rec r = {a=0; b=r.a+1} [1]

• Gives an explicit and customizable name to the record, which is also available to nested records
• Unless restricted to records, this immediately gives recursive lists and recursive functions

General recursion

A simple solution to discourage recursion is to only rely on recursive records, without explicit recursive functions. This makes it accessible but awkward enough so that the user knows he is doing something non standard. Even more:

• A full-fledged proposal 3. already gives access to recursive functions. If this is deemed too permissive, one can restrict let rec to records.
• In proposals 1. and 3., recursive calls are not syntactically distinct. One way to make it more explicit would be to require a rec also at the (recursive) call site (as in Bosque), as in the fictitious let rec loop n = if n > 0 then rec loop (n - 1) else "done".

If on the contrary, one wants to provide a direct syntax for recursive
functions:

• For proposals 1. and 2., we can add the recursive let binding form of 3. just for functions

Late binding

It may be desirable for inheritance-like mechanisms to late bind self (or recursive fields in case 1.). In particular, when merging, self would be bound to the resulting record:

let r1 = {a="a" + self.b; b="b";} /* {a="ab";b="b;} in */
let r2 = {b="c";} in merge r1 r2 /* {a="ac";b="c";} in */

People simulates this capacity in Nix using fixpoints for overriding packages, and Jsonnet's self is late bound. This may also prove essential for incremental evaluation.

---

1. This is actually not valid OCaml, as the form of the right hand side of a let rec is restricted in practice.

[edolstra]

As a slight aside, we should consider getting rid of nested records because they make things unnecessarily complicated. For example, with Nixpkgs overlays, it's easy to override a top-level package foo, but good luck figuring out how to override perlPackages.foo.

So the record { a = 1; b.c = 2; } shouldn't be a record containing fields a and b (where b is a record containing c), but a record containing fields a and b.c. This removes ambiguity about what self refers to, e.g. in { a = 1; b.a = 2; b.c = self.a; }, b.c would evaluate to 1, since self refers to the entire record.

Edit: this is more relevant to #84, since it means a.b.c = {e="bar"}; is something different than a.b.c.e = "bar";.

[edolstra]

I think my preference would be for something that behaves like the NixOS module system, but without any special syntax like rec or config.<attr> or self. So you could write { a = 1; b = a; }, and the value of b depends on whether this record is later extended with a definition that overrides a.

[mboes]

Is this closed by #135? Sounds like the decision was made there to not require an explicit rec keyword. The rest of this issue appears to be obsolete.

[yannham]

Closed by #135 for records, superseded by #525 for let-binding.