Evaluator update

[cueckoo]

Originally opened by @myitcv in cuelang/cue#338

Overview

This is roadmap for a CUE evaluator rewrite. That language has changed enough since inception to make the original evaluator no longer suitable. We also have a better view on the requirements now.

The main objectives of the rewrite are:

• simplification
• fix many bugs
• improve performance, most notably making it more predictable
• enable planned critical features

We don't anticipate doing an evaluator rewrite often, btw.

Details

There are a few features that will hinge on the new evaluator design. We'll discuss them here. Many of the new features hinge on being able to order conjuncts of unification midstream. All these features would come for free or could be implemented with little effort given the foreseen new evaluator.

Association Arrays

A philosophy of CUE is that configuration should be specifiable in the native API, without the need for abstractions. This mostly works well, but breaks down in DSLs like CUE where an API is expressed in terms of lists where they mean maps. The Kubernetes APIs are littered with such cases. To add insult to injury, unification is a notoriously poor formalism for composing such lists. Association arrays solve this issue by allowing lists to be reinterpreted as maps. See #165 for more info.

Builtin validators and User-defined constraint types

An undocumented feature of CUE is the ability to use certain builtin types as validation types. Some builtins, however, are not commutative with respect to unification, which is not valid CUE. This can be fixed by including a reordering step in the evaluator. A rewrite is not strictly necessary for this, but it makes things easier.

The same would hold for a constraint builtin that allows converting boolean expressions to constraints.

Redesign of closed structs

Closed structs are a bit tedious to use in practice. This is partly because the evaluator has some bugs, and partly because the definition is too restrictive.

A good API design allows for extensibility. CUE's closed struct seem to fly in the face of this concept. The main purpose of closed structs, however, is to catch typos in field names. Experience with GCL and other languages indicate this is a common mistake and can give quite a headache.

How do we reconcile these two goals? A good analogy can be drawn to Protocol Buffers, which by design allows the addition of arbitrary fields, but once the respective definitions are converted to typed languages like Go, a misspelled field will cause a compile error. Closed structs should be seen in this context.

Closed structs do play another role: the presence of fields may disambiguate a disjunction. That is a disjunct that would cause a "compilation error" because of the presence of a field in a struct with which it is unified is eliminated from a disjunction.

A goal of the evaluator redesign is to relax the restrictions of closed structs to make them more convenient and find a definition that does not conflict with the concept of open APIs, while being formally rigorous enough to serve as a disambiguator of disjunctions.

Robustness of programmatic API

The programmatic API currently must maintain a parallel structure to the evaluated values that must be kept in sync. This is error prone. The memoization strategy and in the new design allow this to be kept in the evaluated strategies itself.

Links

• All issues specific to this roadmap issue
• Open issues specific to this roadmap issue