On this page:
5.1 Overview of the implementation of structures
5.2 A polyvalent identifier:   type, match, constructor and instance
«tagged»
5.3 The tagged call expander (builder and instance)
«call [fieldᵢ] …+»
«no-values-error»
«call [fieldᵢ : τᵢ] …+»
«values-error»
«call [fieldᵢ valueᵢ] …+»
(no-values-error)
«call [fieldᵢ valueᵢ : τᵢ] …+»
(values-error)
5.3.1 Call to tagged with no fields: instance or constructor?
5.3.2 Signature for the tagged call expander
«name-id-mixin»
«∀-mixin»
«tagged-call-instance-or-builder-mixin»
«tagged-call-fields-mixin»
«empty-err»
«name-after-field-error»
«tagged-call-args-mixin»
5.3.3 Implementation
«call-expander»
«call-expander-cases»1
«call-expander-cases»2
5.4 Type expander
«tagged-type-fields-mixin»
«[fieldᵢ τᵢ] …+»
«[fieldᵢ] …+»
(name-after-field-error)
«tagged-type-args-mixin»
«type-expander»
«type-expander-cases»
5.4.1 The Tagged  Top type
«TaggedTop»1
«TaggedTop»2
5.5 Match expander
«tagged-match-no-implicit-bind-mixin»
«tagged-match-fields-mixin»
«[fieldᵢ patᵢⱼ …] …+»
(name-after-field-error)
«tagged-match-args-mixin»
«match-expander»
«match-expander-body»
5.6 Predicates for tagged structures
«tagged?»
5.6.1 The Tagged  Top? predicate
«provide TaggedTop?»
5.7 Defining shorthands with define-tagged
«tag-kw-mixin»
«default-tag-name»
«predicate?-mixin»
«default-name?»
«define-tagged-args-mixin»
«define-tagged»
«type-expander/define»
«match-expander/define»
«else-expander/define»
«predicate/define»
5.8 Implementation of uniform-get
5.9 Putting it all together
«*»
7.1

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

5.1 Overview of the implementation of structures

Tagged structures are represented using regular Racket structs, see Somewhat outdated overview of the implementation choices for structures, graphs and passes for a somewhat outdated discussion of alternative possibilities.

The ADT type system implemented by this library needs to know about all declared structures across the program, so that fields can be accessed anonymously, e.g. (get instance f) instead of the traditional (s-f instance) (where s is the struct’s identifier, and f is the field name). This allows the accessor get to work on all structures which contain a field with the given name (and therefore plays well with unions of structures which share some fields). It also avoids the need to specify the struct which declared a field in order to accessing it. A separate library adds a coat of syntactic sugar to enable the notation instance.f1.f2.f3, following the well-known convention often used by object-oriented languages.

The section Low-level implementation of tagged structures describes the low-level implementation of tagged structures, including how all declared structures are remembered across compilations, and the implementation of the basic operations on them: constructor, predicate, accessor, type, match expander, and row polymorphism (also known as static duck typing). The implementation of row polymorphism works by querying the list of all known tagged structures and returns those containing a given set of fields.

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

The tagged identifier can be used to describe a tagged structure type, a match pattern, a tagged structure builder function, or to directly create an instance. The last two cases are handled by the <call-expander>.

(define-multi-id tagged
  #:type-expander  tagged-type-expander
  #:match-expander tagged-match-expander
  #:call           tagged-call-expander)

5.3 The tagged call expander (builder and instance)

When called like a macro, tagged accepts several syntaxes:

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

A call to (tagged) with no field is ambiguous: it could return a constructor function for the structure with no fields, or an instance of that structure.

(tagged)

We tried to make a hybrid object using define-struct/exec which would be an instance of the structure with no fields, but could also be called as a function (which would return itself). Unfortunately, this use case is not yet fully supported by Typed/Racket: the instance cannot be annotated as a function type, or passed as an argument to a higher-order function (Typed/Racket issue #430). This can be circumvented by using unsafe operations to give the instance its proper type (Rec R ( ( R) struct-type)), but Typed/Racket does not consider this type applicable, and an annotation is required each time the instance is used as a builder function (Typed/Racket issue #431.

We therefore added two optional keywords, #:instance and #:builder, which can be used to disambiguate. They can also be used when fields respectively with or without values are specified, so that macros don’t need to handle the empty structure as a special case.

5.3.2 Signature for the tagged call expander

When called as a macro, tagged expects:

The four elements can appear in any order, with one constraint: the name must appear before the first field descriptor. Not only does it make more sense semantically, but it also avoids ambiguities when the list of field names is just a list of plain identifiers (without any type or value).

"the name must appear before any field"

We can now combine all four mixins.

(define-eh-alternative-mixin tagged-call-args-mixin
  #:define-splicing-syntax-class tagged-call-args-syntax-class
  (pattern {~mixin name-id-mixin})
  (pattern {~mixin tagged-call-instance-or-builder-mixin})
  (pattern {~mixin tagged-call-fields-mixin})
  (pattern {~mixin ∀-mixin}))

5.3.3 Implementation

The call expander uses the low-level functions tagged-builder!, tagged-∀-builder! and tagged-infer-builder! implemented in Creating instances of a tagged structure. The first returns the syntax for a builder function for the given tagged structure. The second returns the syntax for a polymorphic builder function for the given tagged structure, using the given type variables which are bound inside the field type declarations. The last returns the syntax for a polymorphic builder function for the given tagged structure, with one type parameter per field, which allows the type of each field to be inferred.

(define/syntax-parse+simple
    (tagged-call-expander :tagged-call-args-syntax-class)
  «call-expander-cases»)

If type variables are present, then tagged-∀-builder! is used. Otherwise, if types are specified, then tagged-builder! is used, otherwise tagged-infer-builder! is used.

(define/with-syntax f
  (if (attribute tvars?)
      (tagged-∀-builder! #'((tvarᵢ ) name [fieldᵢ : τᵢ] ))
      (if (attribute types?)
          (tagged-builder! #'(name [fieldᵢ τᵢ] ))
          (tagged-infer-builder! #'(name fieldᵢ )))))

If the #:instance keyword was specified, or if values are specified for each field, the builder function is immediately called with those values, in order to produce an instance of the tagged structure. Otherwise, the builder function itself is produced.

(if (attribute instance?)
    #'(f valueᵢ )
    #'f)

5.4 Type expander

When used as a type expander, tagged expects:

The three elements can appear in any order, with the same constraint as for the call expander: the name must appear before the first field descriptor.

"the name must appear before any field"

(define-eh-alternative-mixin tagged-type-args-mixin
  #:define-splicing-syntax-class tagged-type-args-syntax-class
  (pattern {~mixin name-id-mixin})
  (pattern {~mixin tagged-type-fields-mixin})
  (pattern {~mixin ∀-mixin}))

The type expander uses the low-level functions tagged-type!, tagged-∀-type! and tagged-infer-type! implemented in Type of a tagged structure. The first returns the syntax for the type for the given tagged structure. The second returns the syntax for a polymorphic type for the given tagged structure, using the given type variables which are bound inside the field type declarations. The last returns the syntax for a polymorphic type for the given tagged structure, with one type parameter per field, which allows the type of each field to be inferred or filled in later.

(define/syntax-parse+simple
    (tagged-type-expander :tagged-type-args-syntax-class)
  «type-expander-cases»)

If type variables are present, then tagged-∀-type! is used. Otherwise, if types are specified, then tagged-type! is used, otherwise tagged-infer-type! is used.

(if (attribute tvars?)
    (tagged-∀-type! #'((tvarᵢ ) name [fieldᵢ : τᵢ] ))
    (if (attribute types?)
        (tagged-type! #'(name [fieldᵢ τᵢ] ))
        (tagged-infer-type! #'(name fieldᵢ ))))

5.4.1 The TaggedTop type

The TaggedTop type is extracted from the low-level TaggedTop-struct identifier (which is a struct identifier). The TaggedTop type includes not only tagged structures, but also nodes.

Additionally, the TaggedTop? predicate is simply aliased from the low-level TaggedTop-struct?.

5.5 Match expander

When used as a match expander, tagged expects:

The three elements can appear in any order, with the same constraint as for the call expander: the name must appear before the first field descriptor.

"the name must appear before any field"

(define-eh-alternative-mixin tagged-match-args-mixin
  #:define-syntax-class tagged-match-args-syntax-class
  (pattern {~mixin name-id-mixin})
  (pattern {~mixin tagged-match-no-implicit-bind-mixin})
  (pattern {~mixin tagged-match-fields-mixin}))

The match expander uses the low-level function tagged-match! implemented in Type of a tagged structure. It returns the syntax for a match pattern for the given tagged structure. The resulting match pattern checks that the value is an instance of a tagged structure with the given name and fields, and matches the value of each field against the corresponding pattern.

(define/syntax-parse+simple
    (tagged-match-expander . :tagged-match-args-syntax-class)
  «match-expander-body»)

Unless #:no-implicit-bind is specified, we include the field name as part of the pattern, so that field names are bound to the field’s contents.

(if (attribute no-implicit)
    (tagged-match! #'(name [fieldᵢ (and patᵢⱼ )] ))
    (tagged-match! #'(name [fieldᵢ (and fieldᵢ patᵢⱼ )] )))

5.6 Predicates for tagged structures

(define-syntax tagged?
  (syntax-parser
    [(_ name fieldᵢ:id )
     (tagged-any-predicate! #'(name fieldᵢ ))]
    [(_ name [fieldᵢ:id :colon τᵢ:type] )
     (tagged-predicate! #'(name [fieldᵢ τᵢ] ))]
    [(_ name [fieldᵢ:id predᵢ:type] )
     (tagged-pred-predicate! #'(name [fieldᵢ predᵢ] ))]))

5.6.1 The TaggedTop? predicate

The TaggedTop? predicate is simply re-provided. It is initially defined in Common ancestor to all tagged structures: TaggedTop-struct.

5.7 Defining shorthands with define-tagged

The define-tagged macro can be used to bind to an identifier the type expander, match expander, predicate and constructor function for a given tagged structure.

The define-tagged macro expects:

The five elements can appear in any order, with the same constraint as for the call expander: the name must appear before the first field descriptor.

(define-eh-alternative-mixin define-tagged-args-mixin
  #:define-splicing-syntax-class define-tagged-args-syntax-class
  (pattern (~or {~mixin name-id-mixin}
                {~mixin tag-kw-mixin}
                {~mixin tagged-type-fields-mixin}
                {~mixin predicate?-mixin}
                {~mixin ∀-mixin})))

The define-tagged macro is then implemented using define-multi-id:

(define-syntax/parse+simple
    (define-tagged :define-tagged-args-syntax-class)
  (define-temp-ids "~a/pat" (fieldᵢ ))
  (quasisyntax/top-loc stx
    (begin
      (define-multi-id name
        #:type-expander    (make-id+call-transformer
                            #'«type-expander/define»)
        #:match-expander   «match-expander/define»
        #:else             «else-expander/define»)
      (define name?        «predicate/define»))))

The type expander handles the same three cases as for tagged: with type variables, with a type for each field, or inferred.

#,(if (attribute tvars?)
      (tagged-∀-type! #'((tvarᵢ ) tag-name [fieldᵢ τᵢ] ))
      (if (attribute types?)
          (tagged-type! #'(tag-name [fieldᵢ τᵢ] ))
          (tagged-infer-type! #'(tag-name fieldᵢ ))))

The match expander is a short form of the one implemented for tagged, as it takes only one positional pattern per field.

(λ (stx2)
  (syntax-case stx2 ()
    [(_ fieldᵢ/pat )
     (tagged-match! #'(tag-name [fieldᵢ fieldᵢ/pat] ))]
    ;Todo: implement a "rest" pattern))

Otherwise, when name is called as a function, or used as an identifier on its own, we produce a builder function. When name is called as a function, the builder function is applied immediately to the arguments, otherwise the builder function itself is used. The same three cases as for tagged are handled: with type variables, with a type for each field, or inferred.

#'#,(if (attribute tvars?)
        (tagged-∀-builder!
         #'((tvarᵢ ) tag-name [fieldᵢ τᵢ] ))
        (if (attribute types?)
            (tagged-builder! #'(tag-name [fieldᵢ τᵢ] ))
            (tagged-infer-builder! #'(tag-name fieldᵢ ))))

Finally, we define the predicate name?. Contrarily to tagged?, it does not take into account the field types, as we have no guarantee that Typed/Racket’s make-predicate works for those. Instead, name? recognises any instance of a tagged structure with the given tag name and fields. If a more accurate predicate is desired, it can easily be implemented using tagged?.

#,(tagged-any-predicate! #'(tag-name fieldᵢ ))

5.8 Implementation of uniform-get

uniform-get operates on tagged structures. It retrieves the desired field from the structure, and forces it to obtain the actual value.

It is implemented as tagged-get-field in Accessing fields of tagged structures, and is simply re-provided here.

5.9 Putting it all together

«*» ::=
(require (for-syntax racket/base
                     racket/syntax
                     syntax/parse
                     phc-toolkit/untyped
                     syntax/strip-context
                     racket/function
                     extensible-parser-specifications
                     racket/format
                     type-expander/expander)
         phc-toolkit
         multi-id
         type-expander
         racket/promise
         "tagged-structure-low-level.hl.rkt"
         racket/format)
 
 
 
 
(define-syntax uniform-get
  (make-rename-transformer #'tagged-get-field))
(define-syntax λuniform-get
  (make-rename-transformer #'λ-tagged-get-field))
(provide uniform-get
         λuniform-get
         tagged
         tagged?
         define-tagged
         TaggedTop
         TaggedTop?
 
         (for-syntax tagged-call-args-syntax-class
                     tagged-call-expander-forward-attributes
                     tagged-call-expander
 
                     tagged-type-args-syntax-class
                     tagged-type-expander-forward-attributes
                     tagged-type-expander
 
                     tagged-match-args-syntax-class
                     tagged-match-expander-forward-attributes
                     tagged-match-expander
 
                     define-tagged-args-syntax-class
                     define-tagged-forward-attributes))
 
(begin-for-syntax
  «∀-mixin»
  «name-id-mixin»
  «tagged-call-instance-or-builder-mixin»
  «tagged-call-fields-mixin»
  «tagged-call-args-mixin»
  «tagged-type-fields-mixin»
  «tagged-type-args-mixin»
  «tagged-match-fields-mixin»
  «tagged-match-no-implicit-bind-mixin»
  «tagged-match-args-mixin»
 
  «predicate?-mixin»
  «tag-kw-mixin»
  «define-tagged-args-mixin»)
 
(begin-for-syntax
  «call-expander»
  «type-expander»
  «match-expander»)
«tagged»
«tagged?»
«TaggedTop»
«define-tagged»