Proposal 001: Schemas

• Requires: strings are no longer accepted in value position. String values use double quotes or fenced strings. Bare names are symbols that resolve to values, without the former . reference prefix. Map keys are still literal strings.
• Proposed: int and float become built-in type values. Rename the existing conversion functions to coerce/int and coerce/float, with their current conversion behavior. string, bool, top, and bottom are also built-in values. Built-in symbols ⊤, ⊥, &, |, ?, *, tuple, list, ..., and => supply constraint operator identity.
• Proposed: Add the constraint interpretation rules, operators, list markers, and functions defined below. Extend fn to accept an optional contract after each parameter list.
• TODO: Update the value, symbol, function, and JSON/RON representation sections of the main Dust specification. Define the encoded representation of built-in type values and other constraint values without adding new required source tags.

Dust does not define a separate runtime category for schemas. Types, constraints, functions, collections, and concrete data are all Dust values. A schema is a value interpreted as a description of possible values by a schema-aware operation. The same value can be manipulated as ordinary data without applying constraint semantics.

A type is a value and a constraint is a value used in a particular role. A bound and a validator are particular ways to express constraints. Adding a constraint can make a description more specific.

Ordinary Dust evaluation constructs maps and lists without applying schema operators. A schema-aware operation interprets its schema arguments as constraints. It does not change the meaning of ordinary equality, lookup, or collection updates.

(local Named {name string})
(local ada {name "Ada" age 37})

(get Named "name")                    ; => string
(get ada "name")                      ; => "Ada"
(= {name "Ada"} ada)                  ; => false
(valid? {name "Ada"} ada)             ; => true, because the shape is open
(valid? Named ada)                    ; => true
(valid? Named {age 37})               ; => false, required name is missing

(local pending [& int 3])
pending                               ; => [& int 3], ordinary list data
(= pending 3)                         ; => false
(meet pending top)                    ; => 3, interpreted as a constraint

For schema interpretation, a scalar such as 3 means exactly 3. A map such as {name "Ada"} means any map with name equal to "Ada". Dust does not provide a closed-map or exact-map constraint form in this proposal.

top permits every possible value. bottom permits no possible value. The Unicode aliases ⊤ and ⊥ denote the same two values.

Meet combines constraints by intersection of possible values. Join combines constraints by union of possible values. The long forms are meet and join. Their short forms are & and |.

[meet int 3]           ; Exactly 3
[& int 3]              ; Exactly 3, short form
[join int string]      ; Any integer or string
[| int string]         ; Any integer or string, short form

[& top int]            ; int: top adds no restriction
[| top int]            ; top: top already admits every value
[& bottom int]         ; bottom: no value can satisfy bottom
[| bottom int]         ; int: bottom adds no alternatives
[& ⊤ ⊥]                ; bottom
[| ⊤ ⊥]                ; top

[& int 3 [> 2]]        ; 3 satisfies both constraints
[& int 3 [> 4]]        ; bottom: 3 does not satisfy >4
[& int string]         ; bottom: no value is both an integer and a string
[| int string int]     ; Equivalent to [| int string]

(meet)                 ; => top
(join)                 ; => bottom
(meet int 3 [> 2])     ; => 3
(join int string)      ; => [| int string], or an equivalent normalized value

Both meet and join are associative, commutative, and idempotent. Their meanings do not depend on operand order or repetition. Meet distributes over join. These laws concern admitted values, not ordinary equality of the source lists. Default preferences add separate rules, and nested preference groups may be significant.

The list [& int 3] does not compute a meet during ordinary evaluation. The function call (meet int 3) computes it. A computed result can be a concrete value, a constraint, or bottom. A schema-aware operation may normalize descriptions before using them.

Each map member describes a field with the same key. Fields are required unless marked optional. The long form [optional S] and short form [? S] are field descriptors. They are valid only as map-member descriptions, not as standalone constraints. The member's value must satisfy S when the field is present.

(local Person {
  name string
  nickname [optional string]
  age [? int]
  address {
    line1 string
    city string
    country [| [* "USA"] string]
  }
})

{name top}             ; Requires name, with no restriction on its value
{name [? top]}         ; Name may be absent, or contain any value
{name string}          ; Requires a string name
{name [? string]}      ; String name is optional

(meet {name [? string]} {name "Ada"})
; => {name "Ada"}: one description requires the field

(meet {name [? "Ada"]} {name [? "Grace"]})
; => {name [? bottom]}: absence of name is still allowed

(meet {name [? "Ada"]} {name "Grace"})
; => bottom: name is required but the values conflict

Meet of maps combines their fields by key and meets the constraints of matching fields. Nonmatching fields are included without changes to their constraints. Dust map literals continue to reject duplicate keys. Meet provides repeated contributions without duplicate map members.

(local municipality {
  name string
  pop int
  capital bool
})

(local largeCapital [&
  municipality
  {pop [& int [> 5000000]] capital true}
])

(local kinshasa [&
  largeCapital
  {name "Kinshasa" pop 16320000 capital true}
])

(meet kinshasa top)
; => {name "Kinshasa" pop 16320000 capital true}
; The result is still an open shape when interpreted as a schema.

A bound is a comparison against a constant. A bound denotes every value that satisfies its comparison. Mathematically, ⟦[> 18]⟧ = {x | x >= 18}=. Thus a bound is a predicate-defined set, not a separate class of runtime object. The recognized bound operators are >, >=, <, <=, ==, and !=. String patterns may also use =~ and !~ with Dust regular-expression values. A bound can be evaluated or simplified without a supplied concrete candidate when its meaning is decidable.

An ordinary boolean-returning function can act as a validator. A list headed by that function omits the first argument. The value being checked supplies the missing first argument. The remaining list members are passed as ordinary arguments. A validator returns the original candidate on success during constraint interpretation, not the function's boolean result.

Bounds and validators use the same declarative list syntax. The constraint engine has symbolic knowledge of recognized bounds. It does not need symbolic knowledge of other validator functions. Ordinary validators are checked when their candidate is concrete. Validator functions must be pure for order-independent constraint semantics.

[> 2]                          ; Values greater than 2
[& int [>= 0] [<= 10]]         ; Integers 0 through 10
[& int [> 0] [< 10]]           ; Integers 1 through 9
[& [>= 0] [<= 7] [>= 3]]      ; Equivalent to [& [>= 3] [<= 7]]

(local allowed [& int [|
  [& [>= 0] [<= 10]]
  [& [>= 100] [<= 200]]
]])
(valid? allowed 7)             ; => true
(valid? allowed 150)           ; => true
(valid? allowed 50)            ; => false

(> 5 2)                        ; => true, ordinary function call
(valid? [> 2] 5)               ; => true, predicate used as a constraint

(valid? [strings/starts-with? "Super"] "Superman")  ; => true
(valid? [strings/ends-with? "e"] "Superman")        ; => false
(valid? [=~ #re "^[A-Z].*[a-z]$"] "Superbe")       ; => true
(valid? [!~ #re "v"] "Superbe")                   ; => true

(local min-length?
  (fn [text count-min] (>= (count text) count-min)))
(valid? [& string [min-length? 3]] "Ada")            ; => true
(valid? [& string [min-length? 3]] "Al")             ; => false

(meet [> 10] [< 5])          ; => bottom, contradiction is decidable
(meet string [strings/starts-with? "Super"])
; => [& string [strings/starts-with? "Super"]], or an equivalent constraint

The schema engine must not invoke an arbitrary validator to test a still-incomplete constraint. It may invoke a validator when meet has produced a concrete candidate. When a validator is opaque to symbolic reasoning, meet preserves its requirement for later checking.

TODO: Specify errors returned by validators, numeric cross-kind bounds, and whether =~ and !~ use complete-match or search semantics. Dust's numeric types and comparison functions do not implicitly convert integers and floats.

Dust lists are ordinary data during evaluation. A recognized list operator or => form has constraint-specific meaning when interpreted as a schema. Positional list constraints use an explicit tuple constructor. The list constructor permits a positional prefix and an open tail. The ... marker permits zero or more additional elements. An omitted tail constraint means top. A list without an operator is a literal-list constraint, which admits only that exact list. It does not constrain each element by interpreting the elements as schemas. Use [tuple int string] to admit pairs containing an integer and a string.

[tuple int string]           ; Exactly two elements, integer then string
[tuple int string bool]      ; Exactly three elements of the given types
[tuple {name string} int]    ; A map followed by an integer
[tuple 1 2 3]               ; Exactly [1 2 3], with explicit positional constraints
[tuple]                     ; Exactly the empty list
[1 2 3]                     ; Exact literal list [1 2 3], not an implicit tuple schema
[]                          ; Exact empty literal list

[list string int ... bool]   ; String, integer, then zero or more booleans
[list string int ...]        ; String, integer, then any additional values
[... int]                   ; Zero or more integers
[... [| int string]]        ; Each element independently integer or string
[...]                       ; Any list, including an empty list
[| [... int] [... string]]  ; All integers or all strings, not a mixture
[... {name string}]         ; Zero or more maps with a string name

(local Household {
  head {name string}
  people [... {name string age int}]
  location [tuple float float]
  visits [... {
    date string
    attendees [... {name string}]
  }]
})

(local length-between?
  (fn [xs low high] (<= low (count xs) high)))

(local Group [&
  [... {name string}]
  [length-between? 2 5]
])
(valid? Group [{name "Ada"} {name "Grace"}]) ; => true
(valid? Group [{name "Ada"}])                ; => false
(valid? [tuple 1 2 3] [1 2 3])              ; => true
(valid? [1 2 3] [1 2 3])                    ; => true, exact literal-list match
(valid? [1 2 3] [1 2 4])                    ; => false

A list headed by an operator or validator has the defined operator meaning. Other lists describe exact list values, not elementwise tuple schemas. The compiler does not infer positional constraints from unmarked lists. TODO: Specify a way to express a literal list whose first element is also a recognized schema operator.

TODO: Specify canonical normalization of list constraints and representation of literal function values within tuples. Deferred: Constraints applying to arbitrary map keys.

A default is a preferred alternative within a join. The long form [default S] and short form [* S] mark a preferred alternative. A default does not exclude other allowed values. It does not make a required field optional. An optional field is not created solely because it contains a default.

[| [default "Ada"] string]          ; Any string, with preferred value "Ada"
[| [* "Ada"] string]                ; Equivalent short form
[| [* 8080] int]                    ; Any integer, with preferred value 8080

(local PersonWithDefault {
  name [| [* "Ada"] string]
  nickname [? [| [* "Ace"] string]]
})

(valid? PersonWithDefault {})                    ; => false, name is required
(materialize PersonWithDefault)                   ; => {name "Ada"}
(materialize (meet PersonWithDefault {name "Grace"}))
; => {name "Grace"}, explicit value satisfies the schema

(materialize {name string})                       ; => #err, no concrete name is determined
(materialize {name [? [| [* "Ada"] string]]})     ; => {}, optional field is absent

Materialization selects permitted concrete values from a description, including usable defaults. It does not convert a supplied value to another type. Coercion is an explicit conversion, such as (coerce/int "37") producing 37. Meet of int and "37" is bottom, not 37. Materialization returns new data and does not change its input.

Default preferences must not use first-wins or last-wins selection. Nested preferred joins may have different meanings from flattened preferred joins. TODO: Specify the full interaction of marked joins, nested joins, conflicting preferences, and incomplete values using executable reference cases.

A function constraint describes permitted argument sequences and required results. The marker => separates input constraints from the result constraint. The ordinary value [int => string] is a first-class description of callable behavior. A function body is not executed when a function constraint is constructed.

A Dust function may place a contract list directly after its parameter list. Input checks run before its body. The result check runs after its body returns. Failed checks return a structured error. A function without a contract uses the existing invocation rules.

(local greet
  (fn [person]
    [{name string} => string]
    (str "Hello, " (get person "name"))))

(greet {name "Ada" age 37})  ; => "Hello, Ada"
(greet {age 37})             ; => contract error, missing name

(local describe
  (fn
    ([x]
      [int => string]
      (str x))
    ([x prefix]
      [int string => string]
      (str prefix x))))

(local sum
  (fn [x & more]
    [int ... int => int]
    (reduce + x more)))

[&
  [int => string]
  [int string => string]
]
; Describes one callable that supports both arities.

Each function arity has an independent contract. Variadic input contracts use the same ... tail notation as list constraints. The tail describes actual extra arguments, not Dust's internal null rest binding when no extras were supplied. Meet of function constraints requires every applicable call promise to hold. It must not independently meet argument and result types in a way that loses their correspondence.

TODO: Specify full callable subtyping and checking of externally supplied function values. Deferred: Higher-order callback wrappers, function identity effects, and complete behavioral enforcement for function-valued arguments. TODO: Decide whether a separate defn form will be added as a shorthand for top-level local plus fn.

The names below describe new ordinary Dust functions. The symbolic & and | functions are aliases of meet and join. All functions accept evaluated values.

bottom is a constraint value distinct from #err. A schema-aware operation must not mistake a stored #err value for the bottom constraint. An impossible meet produces bottom. A failed valid? returns false. A failed explain returns a structured #err value. An invalid schema expression or failed computation produces #err, not bottom.

Diagnostic errors use Dust's existing #err tagged representation. The top-level value is the complete input. Each member of errors has a value for the offending subvalue. The path member is a native JSON pointer into the schema representation. The in member is a native JSON pointer into the input value. A root pointer is written (jsonptr ""), not /. An error may include a source location and structured cause data.

(local People [... {name string}])
(explain People [{name "Ada"} {name 42}])
; =>
#err {
  <schema mismatch>
  schema [... {name string}]
  value [{name "Ada"} {name 42}]
  errors [{
    path /1/name
    in /1/name
    schema string
    value 42
    message "Expected a string"
  }]
}

(local allowed [& int [|
  [& [> 1] [<= 10]]
  [& [>= 100] [<= 200]]
]])
(meet allowed 300)        ; => bottom
(valid? allowed 300)      ; => false
(explain allowed 300)
; => Illustrative report, exact field names and messages are TODO.
#err {
  <schema mismatch>
  schema [& int [| [& [> 1] [<= 10]] [& [>= 100] [<= 200]]]]
  value 300
  errors [
    {
      path /2/1/2
      in (jsonptr "")
      schema [<= 10]
      value 300
      message "300 exceeds upper bound 10"
    }
    {
      path /2/2/2
      in (jsonptr "")
      schema [<= 200]
      value 300
      message "300 exceeds upper bound 200"
    }
  ]
}

The constraint form [fail "message"] denotes bottom with a custom diagnostic. A failed branch of a join contributes no final error if another branch succeeds. If all branches fail, explain reports their relevant diagnostics. The fail form is declarative data, not a call performed during list construction.

(valid? [| int [fail "Not an integer"]] 3)     ; => true
(explain [| int [fail "Not an integer"]] "x")
; => #err containing the failed integer constraint and the custom message

(meet int string)          ; => bottom
(explain int "x")          ; => structured #err <schema mismatch>
(valid? [? int] 3)         ; => #err <schema invalid>, not false

TODO: Determine exact tags, message fields, nested causes, and source-location representation. TODO: Run equivalent CUE examples and compare the content and order of diagnostics. TODO: Specify how source information is preserved when a normalized meet produces bottom. TODO: Specify whether explanation data is recorded by meet or recomputed by explain from the original descriptions.

Implementations must test the following properties for pure constraints and concrete inputs.

• Meet and join are associative, commutative, and idempotent in their accepted-value semantics.
• Meet with top and join with bottom do not change a constraint's meaning.
• Meet with bottom yields bottom, and join with top yields top.
• Meet of open shapes combines fields recursively without allowing duplicate literal keys.
• A conflicting optional field does not make a shape impossible unless another constraint requires that field.
• The admitted values do not depend on the order of meet and join operands.
• Default selection must not depend on the order of alternatives within the same join.
• valid?, explain, meet, and join do not mutate their inputs.
• explain returns null only for successful validation.
• materialize does not coerce values and does not create absent optional fields solely from their defaults.
• String comparisons, bounds, and arbitrary validators use consistent candidate-argument rules.
• Function contracts check input arguments before executing the body and check the returned value afterward.

• Pattern constraints for arbitrary map keys.
• multi dispatch constraints.
• Recursive descriptions, reference cycles, and structural cycles.
• Complete default-preference rewrite rules and normalized representation.
• Canonical constraint serialization, hashing, equality, and semantic equivalence.
• Exact representation of literal function values in positional list constraints and reserved-head literal lists.
• Full higher-order function contracts and automatic callback instrumentation.
• Detailed structured diagnostics based on executable CUE comparison cases.
• Resource limits for symbolic solving and validator execution.

The interpreter may compile a surface schema into an explicit map-based abstract syntax tree (AST). Each AST node is a map with a kind field and named operands or children. The AST distinguishes type constraints, literal constraints, shapes, meet, join, bounds, validators, optional fields, defaults, lists, and function constraints. Compilation does not change the meaning of the source value. The AST is an internal representation, not a new source syntax and not an open shape merely because its nodes are maps.

For example, {name [? [& string [> "A"]]]}= may compile to a structure of this form:

{
  kind "shape"
  fields {
    name {
      presence "optional"
      schema {
        kind "meet"
        operands [
          {kind "type" name "string"}
          {kind "bound" operator ">=" value "A"}
        ]
      }
    }
  }
  source {file "example.dust" line 1 column 1}
}

AST child constraints use explicit node maps even when the surface syntax used lists or scalars. Field presence is recorded separately from the field's value constraint. The source member is optional and carries source positions needed for diagnostics. An implementation may attach source information to each node and keep references to its original constraint terms after normalization.

• Basic type values: int, float, string, bool.
• Derived type value (proposed): number, equivalent to [| int float].
• Literal constraint values: Numbers, quoted strings, booleans, null, and maps or lists interpreted as described above.
• Lattice values: top / ⊤, bottom / ⊥.
• Meet: meet / &, including (meet constraints*) and [& constraints*].
• Join: join / |, including (join constraints*) and [| constraints*].
• Field presence: optional / ?, written [? schema] only for map fields.
• Preferred alternative: default / *, written [* schema] within a join.
• Bounds: <, <=, >, >=, ==, !=, =~, !~ in one-operand constraint form.
• Opaque validators: [predicate extra-arguments*], with the candidate supplied as the first argument.
• Tuple: [tuple schemas*], an exact-length positional list.
• Open list: [list schemas* ... tail-schema], [... schema], and [...].
• Function contract: [input-schemas* => output-schema], with a per-arity signature in fn.
• Custom failure: [fail "message"].
• Schema operations: (valid? schema value), (explain schema value), (meet constraints*), (join constraints*), (materialize schema).
• Value conversion: (coerce/int value), (coerce/float value).
• Existing predicates: int?, float?, number?, string?, boolean?, list?, map?, fn?, error?.
• Existing data operations used by validators: count, get, strings/starts-with?, strings/ends-with?, regex/matches.
• Proposed comparison operators not present as such in current Dust: ==, !=, =~, !~.
• Existing comparison operations: <, <=, >, >=, =, comparison/not=.
• AST: map-based internal schema nodes with kind, operands or children, and optional source positions.