On this page:
1.1 A note on polysemy
1.2 Introduction
1.3 Remembered data types and pre-declarations
1.4 The initialisation process
1.5 Tagged structures, untagged structures, constructors, and variants

1 Algebraic Data Types

    1.1 A note on polysemy

    1.2 Introduction

    1.3 Remembered data types and pre-declarations

    1.4 The initialisation process

    1.5 Tagged structures, untagged structures, constructors, and variants

1.1 A note on polysemy

The name “constructor” usually designates two things:
  • A tagged value, like the ones created or accessed using the constructor macro defined in User API for constructors

  • A constructor function or macro for some kind of data structure, which is the function or macro used to create instances of that data structure.

Since this could lead to ambiguities, we clarify by saying “constructor” in the former case, and “builder” or “builder function” in the latter case.

1.2 Introduction

We define variants (tagged unions), with the following constraints:

The datatype package by Andrew Kent also implements Algebraic Data Types. The main differences are that unlike our library, data structures have to be declared before they are used (they are not "anonymous"), and a given constructor name cannot be shared by multiple unions, as can be seen in the example below where the second define-datatype throws an error:

> (require datatype)
> (define-datatype Expr
    [Var (Symbol)]
    [Lambda (Symbol Expr)]
    [App (Expr Expr)])
> (define-datatype Simple-Expr
    [Var (Symbol)]
    [Lambda (Symbol Expr)])

eval:3:0: define-datatype: variant type #<syntax:3:0 Var>

already bound

  in: Simple-Expr

1.3 Remembered data types and pre-declarations

This library works by remembering all the constructors and all the tagged structures across compilations. More precisely, each constructor’s tag name is written to a file named "adt-pre-declarations.rkt" in the same directory as the user code. The tag name and list of fields of each tagged structure is also written in the same file.

The generated "adt-pre-declarations.rkt" file declares a struct for each tagged structure and constructor, so that all user files which require the same "adt-pre-declarations.rkt" will share the same struct definitions.

User files which make use of the phc-adt should include a call to adt-init before using anything else. The adt-init macro requires the "adt-pre-declarations.rkt" file, and records the lexical context of that require, so that the other macros implemented by this library can fetch the pre-declared struct types from the correct lexical scope. The "ctx.hl.rkt" file takes care of recording that lexical scope, while "adt-init.rkt" performs the initialisation sequence (creating the "adt-pre-declarations.rkt" file if it does not exist, loading the pre-declared struct types from "adt-pre-declarations.rkt", and using a utility from "ctx.hl.rkt" to record the lexical context).

(require "ctx.hl.rkt")

1.4 The initialisation process

The initialisation process can be somewhat complex: the directives (remember-output-file "adt-pre-declarations.rkt"), (set-adt-context) and (require "adt-pre-declarations.rkt") have to be inserted in the right order, and the file "adt-pre-declarations.rkt" has to be initialised with the appropriate contents when it does not exist. The adt-init macro defined in ""adt-init.rkt"" takes care of these steps.

(require "adt-init.rkt")

The generated "adt-pre-declarations.rkt" file will call the pre-declare-all-tagged-structure-structs macro defined in "tagged-structure-low-level.hl.rkt".

1.5 Tagged structures, untagged structures, constructors, and variants

We first define a low-level interface for tagged structures in the "tagged-structure-low-level.hl.rkt" file. This low-level interface includes for-syntax functions for expressing the type of tagged structures, creating builder functions for them, as well as match patterns. It also includes means to access the value of a given field on any tagged structure which contains that field. The "tagged.hl.rkt" file provides syntactic sugar for this low-level interface, and defines the tagged identifier, which acts as a type expander, match expander and macro. The macro can be used to create builder functions which return instances of tagged structures, or to directly create such instances.

(require "tagged.hl.rkt")

The ""tagged-supertype.hl.rkt"" file defines a few operations implementing some form of "static duck typing": As a type expander, (tagged-supertype fieldᵢ ) expands to the union type of all tagged structures containing a superset of the given set of fields. As a match expander, (tagged-supertype [fieldᵢ patᵢⱼ ] ) expands to a match pattern which accepts any tagged structure with a superset of the given set of fields, as long as the value of each fieldᵢ matches against all of the corresponding patᵢⱼ .

(require "tagged-supertype.hl.rkt")

We then define untagged structures, which are tagged structures with the untagged tag name. Untagged structures can be used conveniently when the tag name is not important and the goal is simply to map a set of field names to values. The "structure.hl.rkt" file defines the structure type expander, match expander and macro. The structure identifier acts as a simple wrapper around tagged which supplies untagged as the tag name.

(require "structure.hl.rkt")

Constructors are defined as tagged structures containing a single field, called values. The constructor macro, defined in ""constructor.hl.rkt"" accepts a rich syntax for creating constructor instances containing multiple values, associated with the tag name. The values are aggregated in a list, which is stored within the values field of the tagged structure used to implement the constructor. The constructor identifier is therefore nothing more than syntactic sugar for tagged. It relies on the xlist library, which provides a rich syntax for expressing the complex list types, as well as the corresponding match pattern.

(require "constructor.hl.rkt")

For convenience, we write a variant form, which is a thin wrapper against the union type of several constructors and tagged structures, (U constructor-or-tagged ).

(require "variant.hl.rkt")

Finally, we directly include the row polymorphism features from "tagged-structure-low-level.hl.rkt":

(require "tagged-structure-low-level.hl.rkt")

«*» ::=
(begin «require-modules»)
(provide adt-init