Chapter 3
Tuples, Records, and Variants

In Chapter 2 we saw that, using a language with only functions and application, we could represent advanced programming constructs such as tuples and lists. However, we pointed out that these encodings have fundamental problems, such as a low degree of efficiency, and the fact that they necessarily expose their details to the programmer, making them difficult and dangerous to work with in practice. Recall how we could take our encoding of a pair from Chapter 2 and apply it like a function; clearly the wrong behavior. In this chapter we look at how we can build some of these advanced features into the language, namely tuples and records, and we conclude the chapter by examining variants.

3.1 Tuples

One of the most fundamental forms of data aggregation in programming is the notion of pairing. With pairs, or 2-tuples, almost any data structure can be represented. Tripling can be represented as (1,(2,3)), and in general n-tuples can be represented with pairs in a similar fashion. Records and C-style structs can be represented with sets (n-tuples) of (label, value)-pairs. Even objects can be built up from pairs, but this is stretching it (just as encoding pairs as functions was stretching it).

In Chapter 2, we showed an encoding of pairs based on functions. There were two problems with this representation of pairs. First of all, the representation was inefficient. More importantly, the behavior of pairs was slightly wrong, because we could apply them like functions. To really handle pairs correctly, we need to add them directly to the language. We can add pairs to D in a fairly straightforward manner. We show how to add pair functionality to the interpreter, and leave the operational semantics for pairs as an exercise for the reader.

First, we extend the expr type in our interpreter to include the following.

Next, we add the following clauses to our eval function.

Notice that our pairs are eager, that is, the left and right components of the pair are evaluated, and must be values for the pair itself to be considered a value. For example, (2, 3+4) ==> (2, 7). Caml tuples exhibit this same behavior. Also notice that our space of values is now bigger. It includes:

• numbers 0, 1, -1, 2, -2, ...
• booleans True, False
• functions Function x -> ...
• pairs (v₁,v₂)

Now that we have 2-tuples, encoding 3-tuples, 4-tuples, and n-tuples is easy. We simply do them as (1,(2,(3,(...,n)))). As we saw before, lists can be encoded as n-tuples.

3.2 Records

Records are a variation on tuples in which the fields have names. Records have several advantages over tuples. The main advantage is the named field. From a software engineering perspective, a named field “zipcode” is far superior to “the third element in the tuple.” The order of the fields of a record is arbitrary, unlike with tuples.

Records are also far closer to objects than tuples are. We can encode object polymorphism via record polymorphism. Record polymorphism is discussed in Section 3.2.1. The motivation for using records to encode objects is that a subclass is composed of a superset of the fields of its parent class, and yet instances of both classes may be used in the context of the superclass. Similarly, record polymorphism allows records to be used in the context of a subset of their fields, and so the mapping is quite natural. We will use records to model objects in Chapter 5.

Our D records will have the same syntax as Caml records. That is, records are written as {l₁=e₁; l₂=e₂; ...; l_n=e_n}, and selection is written as e.l_k, which selects the value labeled l_k from record e. We use l as a metavariable ranging over labels, just as we use e as a metavariable indicating an expression; an actual record is for instance {x=5; y=7; z=6}, so x here is an actual label.

If records are always statically known to be of fixed size, that is, if they are known to be of fixed size at the time we write our code, then we may simply map the labels to integers, and encode the record as a tuple. For instance,

Obviously, the makes for ugly, hard-to-read code, but for C-style structs, it works. But in the case where records can shrink and grow, this encoding is fundamentally too weak. C++ structs can be subtypes of one another, so fields that are not declared may, in fact, be present at runtime.

On the other hand, pairs can be encoded as records quite nicely. The pair (3, 4) can simply be encoded as the record {l=3; r=4}. More complex pairs, such as those used to represent lists, can also be encoded as records. For example, the pair (3, (4, (5, 6))), which represents the list [3; 4; 5; 6], can be encoded as the record {l=3; r={l=4; r={l=5; r=6}}}.

A variation of this list encoding is used in the mergesort example in Section 4.3.2. This variation encodes the above list as {l=3; r={l=4; r={l=5; r={l=6; r=emptylist}}}}. This encoding has the nice property that the values are always contained in the l fields, and the rest of the list is always contained in the r fields. This is much closer to the way real languages such as Caml, Scheme, and Lisp represent lists (recall how we write statements like let (first::rest) = mylist in Caml).

3.2.1 Record Polymorphism

Records do more that just add readability to programs. For instance, if you have {size=10; weight=100} and {weight=10; name="Mike"}, either of these two records can be passed to a function such as

Function x -> x.weight.

This is known (in a typed language) as subtype polymorphism. In the function above, x can be any record with a weight field. Subtype polymorphism on records is known as record polymorphism. Caml disallows record polymorphism, so the Caml version of the above code will not typecheck.

In object-oriented languages, subtype polymorphism is known as object polymorphism, or, more commonly, as simply polymorphism. The latter is, unfortunately, confusing with respect to the parametric polymorphism of Caml.

3.2.2 The DR Language

We will now define the DR language: D with records. Again, we will concentrate on the interpreter, and leave the operational semantics as an exercise to the reader.

The first thing we need to consider is how to represent record labels. Record labels are symbols, and so we could use our identifiers (Ident "x") as labels, but it is better to think of record labels as a different sort. For instance, labels are never bound or substituted for. So we will define a new type in our interpreter.

Next, we need a way to represent the record itself. Records may be of arbitrary length, so a list of (label,expression)-pairs is needed. In addition, we need a way to represent selection. The DR expr type now looks like the following.

Let’s look at some concrete to abstract syntax examples for our new language.

In addition, our definition of values must now be extended to include records. Specifically, {l₁=v₁; l₂=v₂; ...; l_n=v_n} is a value, provided that v₁,v₂,...,v_n are values.

Finally, we add the necessary rules to our interpreter. Because records can be of arbitrary length, we will have to do a little more work when evaluating them. The let-rec-and syntax in Caml is used to declare mutually recursive functions, and we use it below.

Notice that our interpreter correctly handles {}, the empty record, by having it compute to the itself since it is, by definition, a value.

3.3 Variants

We have been using variants in Caml, as the types for expressions expr. Now we study untyped variants more closely. Caml actually has two (incompatible) forms of variant, regular variants and polymorphic variants . In the untyped context we are working in, the Caml polymorphic variants are more appropriate and we will use that form.

We briefly contrast the two forms of variant in Caml for readers unfamiliar with polymorphic variants. Recall that in Caml, regular variants are first declared as types

3.3.1 Variant Polymorphism

Like records, variants are polymorphic. In records, many different forms of record could get through a particular selection (any record with the selected field). In variants, the polymorphism is dual in that many different forms of match statement can process a given variant.

3.3.2 The DV Language

Here we see how the definition of a record is modeled as a use of a variant, and a use of a record is the definition of a variant. This is possible because

We will now define the DV language, D with ...Variants.

The new syntax requires variant syntax and match syntax. Just as we restrict functions to have one argument only, we also restrict variant constructors to take one argument only; multiple- or zero-argument variants must be encoded. In concrete syntax, we construct variants by n(e) for n a named variant and e its parameter, for example `Positive(3). Variants are then used via match: Match e With n₁(x₁) -> e₁ | ...| n_m(x_m) -> e_m. We don’t define a general pattern match as found in Caml--our Match will matching a single variant field at a time, and won’t work on anything besides variants.

The abstract syntax for DV is as follows. First, each variant needs a name.

The DV abstract syntax expr type now looks like

Let’s look at some concrete to abstract syntax examples for our new language.

Note in this example we can’t just have a variant Zero since 0-ary variants are not allowed, and a dummy argument must be supplied. Multiple-argument variants may be encoded by a single argument variant over a pair or record (since we have neither pair or records in DV, the only recourse is the encoding of pairs used in D in Section 2.3.4).

In addition, our definition of DV values must also be extended from the D ones to include variants: n(v) is a value, provided v is. To define the meaning of DV execution, we extend the operational semantics of D with the following two rules:

The Variant rule constructs a new variant labeled n; its argument is eagerly evaluated to a value, just as in Caml: `Positive(3+2) ==> `Positive(5). The Match rule first computes the expression e being matched to a variant n_j(v_j), and then looks up that variant in the match, finding n_j(x_j) -> e_j, and then evaluating e_j with its variable x_j given the value of the variant argument.

Variants and Records are Duals Variants are the dual of records: a record is this field and that field and that field; a variant is this field or that field or that field. Since they are duals, defining a record looks something like using a variant, and defining a variant looks like using a record. Variants can directly encode records and vice-versa, in a programming analogy of how DeMorgan’s Laws allows logical and to be encoded in terms of or, and vice-versa: p Or q = Not(Not p And Not q); p And q = Not(Not p Or Not q).

Variants can be encoded using records as follows.

The tricky part of the encoding is that definitions must be turned in to uses and vice-versa. This is done with functions: an injection is modeled as a function which is given a record and will select the specified field.

Here is how records can be encoded using variants.

where x above is any fresh variable.

One other interesting aspect about the duality between records and variants is that both records and variants can encode objects. A variant is a message, and an object is a case on the message. In the variant encoding of objects, it is easy to pass around messages as first-class entities. Using variants to encode objects makes objects that are hard to typecheck, however, and that is why we think of objects as more record-like.