On this page:
Algebraic Data Types for compilers:   Implementation

Algebraic Data Types for compilers: Implementation

Georges Dupéron <georges.duperon@gmail.com>

This library is implemented using literate programming. The implementation details are presented in the following sections. The user documentation is in the Algebraic Data Types for compilers document.

    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

    2 Low-level implementation of tagged structures

      2.1 Overview

      2.2 Implementation using Racket structs

        2.2.1 Nodes as subtypes of their corresponding tagged struct type

      2.3 Common ancestor to all tagged structures: TaggedTop-struct

      2.4 Printing and comparing structures and nodes

        2.4.1 Printing tagged structures

      2.5 Comparing tagged structures

      2.6 Pre-declaring structs

        2.6.1 Why pre-declare the structs?

        2.6.2 Remembering tagged structures across compilations

        2.6.3 Sorting the set of fields

        2.6.4 Not-yet-remembered structs should cause an error

      2.7 Creating instances of a tagged structure

      2.8 Predicate for a tagged structure

        2.8.1 A predicate over the contents of the fields

      2.9 Matching against tagged structures

      2.10 Type of a tagged structure

      2.11 Accessing fields of tagged structures

      2.12 Row polymorphism

        2.12.1 Type for any tagged structure containing a given set of fields

        2.12.2 Changing the tag of a tagged structure

        2.12.3 Splitting a tagged structure

        2.12.4 Merging two tagged structures

        2.12.5 Updating a tagged structure

      2.13 Putting it all together

    3 Implementation of nodes: printing and equality

      3.1 Printing nodes

      3.2 Comparing and hashing nodes

        3.2.1 Hashing nodes

        3.2.2 Caching node equality

        3.2.3 Comparing nodes for equality


    4 Implementation of ADTs: syntax scopes

      4.1 Putting it all together

    5 User API for tagged structures

      5.1 Overview of the implementation of structures

      5.2 A polyvalent identifier: type, match, constructor and instance

      5.3 The tagged call expander (builder and instance)

        5.3.1 Call to tagged with no fields: instance or constructor?

        5.3.2 Signature for the tagged call expander

        5.3.3 Implementation

      5.4 Type expander

        5.4.1 The TaggedTop type

      5.5 Match expander

      5.6 Predicates for tagged structures

        5.6.1 The TaggedTop? predicate

      5.7 Defining shorthands with define-tagged

      5.8 Implementation of uniform-get

      5.9 Putting it all together

    6 Supertypes of tagged structures

      6.1 type-expander

      6.2 Match

      6.3 Nested supertype

      6.4 Conclusion

    7 User API for untagged structures

      7.1 Introduction

      7.2 Defining untagged structures with define-structure

      7.3 Implementation of StructureTop and StructureTop?

      7.4 Supertypes for structures

      7.5 Putting it all together

    8 User API for constructors

      8.1 Introduction

      8.2 The polyvalent identifier constructor: type, match, builder and instance

      8.3 Type-expander

      8.4 Match-expander

      8.5 Predicate

      8.6 Instance creation

      8.7 Defining shorthands for constructors with define-constructor

      8.8 Miscellanea

      8.9 Putting it all together

    9 User API for variants

      9.1 Introduction

      9.2 Implementation of variant

      9.3 Predicate

      9.4 define-variant

      9.5 Conclusion

    10 Somewhat outdated overview of the implementation choices for structures, graphs and passes

      10.1 Structures

      10.2 Passes, subtyping and tests

      10.3 Graphs

      10.4 Conclusion