Designing Crux – Record Traits

I’ve intentionally tried not to break much new ground with Crux’s type system. I mostly want the language to be a pleasant, well-executed, modern language and type system for the web.

That said, when porting some web APIs to Crux, I ran into an bothersome issue with an interesting solution. I’ll motivate the problem a bit and then share the solution below.

Records and Row Polymorphism

Crux has row-polymorphic record types. Think of records as anonymous little structs that happen to be represented by JavaScript objects. Row polymorphism means that functions can be written to accept many different record types, as long as they have some subset of properties.

fun length(vec) {
    math.sqrt(vec.x * vec.x + vec.y * vec.y)
}

length({x: 10, y: 20})
length({x: 3, y: 4, name: "p1"})
length({x: 15})               // type error, missing property y
length({x: "one", y: "two"})  // type error, x and y must be numbers

I lived in a TypeScript codebase for nine months or so and the convenience of being able to quickly define anonymous record types is wonderful. Sometimes you simply want to return a value that contains three named fields, and defining a new type and giving it a name is busywork that contributes to the common belief that statically typed languages feel “heavy”.

Crux supports both nominal types (String, CustomerID, Array, …) and anonymous records, sometimes called structural types.

The problem here is how structural types interact with traits.

Imagine coming to Crux for the first time and trying to encode some values as JSON.

json.encode(10)              // returns "10"
json.encode("hello")         // returns "\"hello\""
json.encode(True)            // "true"
json.encode([15, 30, 12])    // "[15,30,12]"
json.encode(js.Null)         // "null"

json.encode({code: 200, text: "OK"})
// Type error: records don't implement traits

Wait, what? Why does everything work but records?

Records and Traits

json.encode‘s type is fun encode<V: ToJSON>(value: V) — that is, it accepts any value which implements the ToJSON trait. Why don’t records implement traits? Well, record types are anonymous, as described before. They don’t necessarily have unique definitions or names, so how would we define a ToJSON instance for this record?

Haskell, and other statically-typed languages, simply have the programmer manually construct a HashMap and JSON-encode that. In Crux, that approach might look something like:

let map = hashmap.new()
map["x"] = 10
map["y"] = 20
json.encode(map)

Not too bad, but not as nice as using record syntax here.

To solve this problem, which is “only” a human factors problem (but remember that Crux is intended to be delightful), I came up with something that I believe to be novel. I haven’t seen this technique before in the row polymorphism literature or any languages I’ve studied.

There are two parts to this problem. First we want to use record literals to construct key-value maps, and then we want to define trait instances that can use said maps.

Dictionaries

As I mentioned, Crux records are implemented as JavaScript objects. This is pretty convenient when interfacing with JavaScript APIs.

data jsffi ReadyState {
    UNSENT = 0,
    OPENED = 1,
    HEADERS_RECEIVED = 2,
    LOADING = 3,
    DONE = 4,
}

type XMLHttpRequest = {
    mutable onreadystatechange: () => (),
    readyState: ReadyState,
    responseText: JSOption<String>,
    // ...
}

Sometimes, however, JavaScript objects are used as key-value maps instead of records. Crux provides a Dict type for that case. Dict is like Map, except keys are restricted to strings to allow implementation on a plain JavaScript object.

let d = dict.new()
d["happy"] = True
d["sad"] = False
json.encode(d)  // "{\"happy\":true,\"sad\":false}"

There is a ToJSON instance for any Dict<V> where V: ToJSON. But can we provide better syntax for creating one? It would be nicer to write:

let d = dict.from({
    happy: True,
    sad: False,
})

To implement dict.from, we need a new type of record constraint: one that says, I accept any set of fields, as long as every value has a consistent type.

fun from<V>(record: {...: V}): Dict<V> {
    // some unsafe JS code to copy the record into a mutable JS object
}

Read ... as “arbitrary set of fields” and : V as “has type V”. Thus, {...: V} is the new type of record constraint, and it’s read as “record with arbitrary set of fields where each field’s value has type V”.

So now we can write:

json.encode(dict.from({
    happy: True,
    sad: False,
}))

Better, but we’re still not done. For one, dict.from requires the values to have the same type — not necessary for JSON encoding. Two, it’s annoying to have to call two functions to quickly create a JSON object.

Defining Record Instances

Here’s where record trait instances come in. First we need to convert all the record’s field values into a common type T. Then, once the record has been converted into a record of type {...: T}, it can be passed to dict.from and then json.encode. The resulting syntax is:

“`crux
// Read as: implement ToJSON for records where…
impl json.ToJSON {…} {
// …this code runs across each property of the record,
// producing a value of type {…: json.Value}…
for fieldValue {
json.toJSON(fieldValue)
}

// which is then encoded into a JSON object.
toJSON(record) {
    json.toJSON(dict.from(record))
}

}
“`

And there you have it, a ToJSON instance for any record, at least as long as the record’s field types implement ToJSON themselves.

json.encode({
    code: 200,
    status: "OK",
})

I’ve never seen a feature like this in the literature or languages I’ve studied, but if you have, please let me know!

Leave a Reply

Your email address will not be published. Required fields are marked *