9.4 Variant Records

A variant record is an aggregate data type that is a union of records (i.e., a union of structs); it can hold any one of a variety of records. Each constituent record type is called a variant of the union type. Variant records can also be inductive. Consider the idea that context-free grammars can be used to define data structures in addition to languages, which we explored in Chapter 5. A variant record is an effective building block for building a data structure defined with a context-free grammar because the variant record mirrors the EBNF definition of the data structure. We can use a linked list of integers in C to illustrate a variant record. Consider the following EBNF definition of a list:

The following example shows a variant record for this linked list in C:

While observably superfluous, wrapping int number; in a struct (lines 8–11) is required to make List a variant record because a variant record is a union of structs. More importantly, this implementation of a variant record of the list completely mirrors the EBNF definition of the list. Each variant of the union corresponds to an alternative of the non-terminal < L>. Specifically, the variant aatom (lines 8–11) corresponds to the production rule < L > ::= < A >, while the variant aatom_llist (lines 13–18) corresponds to the production rule < L > ::= < A >< L >. Key theme: There is a one-to-one mapping between production rules and constructors.

9.4.1 Variant Records in Haskell

The reserved word data in Haskell introduces a new type. Consider the following Haskell program illustrating both the power of the ML type system and the ease with which it can be used to rapidly construct complex data types, akin to building with LEGO® bricks. Run this program incrementally through the Haskell interpreter multiple times while exploring the types declared, the values of those types constructed, and the functions that manipulate the values of those data types (and the values they return):

Table 9.1 summarizes the support for C/C++-style structs and unions in ML, Haskell, Python, and Java.

Table 9.1 Support for C/C++ Style structs and unions in ML, Haskell, Python, and Java

9.4.2 Variant Records in Scheme: (define-datatype ...) and (cases ...)

Unlike ML and Haskell, Scheme does not have built-in support for defining and manipulating variant records, so we need a tool for these tasks in Scheme. The (define-datatype ...) and (cases ...) extensions to Racket Scheme created by Friedman, Wand, and Haynes (2001) provide support for constructing and deconstructing respectively, variant records in Scheme. The (define-datatype ...) form defines variant records.

Syntax:

A new function called a constructor is automatically created for each variant to construct data values belonging to that variant. The following code is a data type definition of a list of integers:

To interpret this definition, set the language to Essentials of Programming Languages by including #lang eopl as the first line of the program in DrRacket IDE. This definition automatically creates a linked list variant record and an implementation of the following interface:

• a unary function aatom, which creates an atom node

• a binary function aatom_llist, which creates an atom list node

• a binary predicate llist?

We build llists using the constructors:

The (cases ...) form, in the EOPL extension to Racket Scheme, provides support for decomposing and manipulating the constituent parts of a variant record created with the constructors automatically generated with the (define-datatype ...) form.

Syntax:

The following function accepts a value of type llist as an argument and manipulates its fields with the cases form to sum its nodes:

Notice that the (cases ...) form binds the values of the fields of the value of the data type to symbols (for subsequent manipulation). The define-datatype and cases forms are the analogs of the composition and decomposition operators, respectively. Data types defined with (define-datatype ...) can also be mutually recursive (recall the grammar for S-expressions). In SLLGEN, the sllgen:make-define-datatypes procedure is used to automatically generate the define-datatype declarations from the grammar (or we can manually define them). Table 9.2 summarizes the support for defining and manipulating variant records in the programming languages we have discussed here.

Table 9.2 Support for Composition (Definition) and Decomposition (Manipulation) of Variant Records in a Variety of Programming Languages

Programming Exercises for Section 9.4

Exercise 9.4.1 Explain why the following C++ code does not compile successfully. Explain why the Racket Scheme (define-datatype ...) construct does not suffer from this problem. (Java also does not suffer from this problem.) Modify the following code so that it will compile successfully.

Show your code and explain your observations in a comment in the program.

Exercise 9.4.2 Rewrite the Haskell program in Section 9.4.1 in ML. The two programs are nearly identical, with the differences resulting from the syntax in ML being slightly more verbose than that in Haskell. Table 9.7 (later in the chapter) compares the main concepts and features, including the syntactic differences, of ML and Haskell.

Exercise 9.4.3 Pascal implements a form of discriminated union using variant records. Write a Pascal program to determine whether the Free Pascal compiler² tests the discriminant of a variant record when a variant field is accessed. Report your observations.

Exercise 9.4.4 Consider the following definition of a list in EBNF:

Define a variant record list in C++ for this list data structure. The data type must be inductive and must completely conform to (i.e., naturally reflect) the grammar shown here. Do not use more than 25 lines of code in your definition of the data type, and do not use a class or any other object-oriented features of C++.

Exercise 9.4.5 (Ullman 1997, Exercise 6.2.8, pp. 209–210) Define a Haskell data type for boolean expressions. Boolean expressions are made up of boolean values, boolean variables, and operators. There are two boolean values: True or False. A boolean variable (e.g., “p”) can be bound to either of the two boolean values. Boolean expressions are constructed from boolean variables and values using the operators AND, OR, and NOT. An example of a boolean expression is (AND (OR p q) (NOT q)), where p and q are boolean variables. Another example is (AND p True).

(a) Define a Haskell data type Boolexp whose values represent legal boolean expressions. You may assume that boolean variables (but not the expressions themselves) are represented as strings.

(b) Define a function eval exp env :: Boolexp -> [[Char]] -> Bool in Haskell that accepts a boolean expression exp and a list of true boolean variables env, and determines the truth value of exp based on the assumption that the boolean variables in env are true and all other boolean variables are false. You may use the Haskell elem list member function in your definition of eval.

Bear in mind that exp is not a string, but rather a value constructed from the Boolexp data type.

Examples:

Solve this exercise with at most one data type definition and a five-line eval function.

Exercise 9.4.6 Consider the following definition of a binary tree in BNF:

(a) Define a variant record binarytree in Racket Scheme using (define-datatype ...) for this binary tree data structure. The data type must be inductive and must completely conform to (i.e., naturally reflect) the grammar shown here.

(b) Define a function sum_leaves in Racket Scheme using (cases ...) to sum the leaves of a binary tree created using the data type defined in (a).

2. https://www.freepascal.org