phc-adt-tagged.scrbl (14508B)
1 #lang scribble/manual 2 3 @(require racket/require 4 (for-label (subtract-in typed/racket/base type-expander) 5 type-expander 6 phc-adt 7 racket/shared 8 (lib "phc-adt/tagged.hl.rkt") 9 (lib "phc-adt/structure.hl.rkt") 10 (lib "phc-adt/constructor.hl.rkt") 11 (lib "phc-adt/variant.hl.rkt") 12 (lib "phc-adt/tagged-supertype.hl.rkt")) 13 scribble-enhanced/doc 14 scribble-math 15 (subtract-in scribble/struct scribble-enhanced/doc) 16 scribble/decode) 17 @doc-lib-setup 18 19 @title{Tagged structures} 20 21 @deftech{Tagged structures} behave like Racket's plain @racket[struct]s, but 22 do not need to be declared before they are used. They are similar to 23 @tech[#:doc '(lib "scribblings/guide/guide.scrbl")]{prefab} structs in that 24 aspect, but prefab structs lack field names, i.e. they behave more like 25 vectors tagged with the prefab struct's name. 26 27 A tagged structure is identified by its tag name, and its set of field names. 28 The type of a tagged structure can be expressed without having declared the 29 tagged structure in advance. It is also possible to create instances of tagged 30 structures without declaring them beforehand, and this applies to match 31 patterns for tagged structures too. Fields can be accessed without knowing the 32 structure's tag name, using @racket[(uniform-get instance field-name)]. 33 34 These features make tagged structures particularly suited for writing 35 compilers and other programs which transform large and complex data structures 36 in small steps. This library is designed to work hand in hand with the 37 @elem[#:style 'tt "phc-graph"] library (not available yet, but will be soon), 38 which adds to tagged structures some support for safe cyclic data structures, 39 and easy manipulation of those via higher-order operations. The regular tagged 40 structures should normally not be used to form cyclic data structures@note{It 41 is possible in theory to build cyclic data structures using @racket[shared], 42 for example, but this use case is not supported by this library, and is 43 unlikely to play well with Typed/Racket in any case.}. Thus, the graph library 44 uses @deftech{nodes} instead, which can contain cycles, as long as the cycles 45 are safely created via the graph library. Nodes also have a tag name and a set 46 of fields, and each node type is a subtype of the corresponding tagged 47 structure with the same name and fields. 48 49 @defform[#:kind "type expander" 50 #:literals (:) 51 (tagged tag-name fields-maybe-types) 52 #:grammar 53 [(tag-name Identifier) 54 (fields-maybe-types (code:line just-fieldᵢ ...) 55 (code:line maybe-∀ field+type-descriptorᵢ ...)) 56 (maybe-∀ (code:line) 57 (code:line #:∀ (tvarⱼ ...))) 58 (just-fieldᵢ fieldᵢ 59 [fieldᵢ]) 60 (field+type-descriptor [fieldᵢ typeᵢ] 61 [fieldᵢ : typeᵢ]) 62 (fieldᵢ Identifier) 63 (typeᵢ Type) 64 (tvarⱼ Identifier)]]{ 65 66 Expands to the type for a tagged structure with the given tag name and 67 fields. If the types for the fields are not given, then the tagged structure 68 is polymorphic, with one type variable per field. 69 70 If @racket[#:∀ (tvarⱼ ...)] is specified, a polymorphic tagged structure is 71 polymorphic, with the given type variables. 72 73 The elements may appear in any order, as long as the tag name appears before 74 any field descriptor, and as long as the field descriptors form a contiguous 75 sequence.} 76 77 @defform*[#:kind "syntax" 78 #:link-target? #f 79 #:literals (:) 80 ((tagged maybe-instance maybe-∀ tag-name fields-maybe-types) 81 (tagged maybe-builder maybe-∀ tag-name fields+values-maybe-types)) 82 #:grammar 83 [(maybe-instance (code:line) 84 #:instance) 85 (maybe-builder (code:line) 86 #:builder) 87 (tag-name Identifier) 88 (maybe-∀ (code:line) 89 (code:line #:∀ (tvarⱼ ...))) 90 (fields-maybe-types (code:line just-fieldᵢ ...) 91 (code:line [fieldᵢ : typeᵢ] ...)) 92 (just-fieldᵢ fieldᵢ 93 [fieldᵢ]) 94 (field+value-maybe-type (code:line [fieldᵢ valueᵢ] ...) 95 (code:line field+value+typeᵢ ...)) 96 (field+value+typeᵢ [fieldᵢ : typeᵢ valueᵢ] 97 [fieldᵢ valueᵢ : typeᵢ]) 98 (fieldᵢ Identifier) 99 (typeᵢ Type) 100 (valueᵢ Expression)]]{ 101 When using the @racket[fields-maybe-types] syntax, this form expands to a 102 lambda function which can be used to build an instance of the tagged 103 structure, by passing as many values as there are fields. 104 105 When using the @racket[fields+values-maybe-types] syntax, this form directly 106 returns an instance of the tagged structure, with the given values. 107 108 It is mandatory to disambiguate with either @racket[#:instance] or 109 @racket[#:builder] when using @racket[tagged] with an empty list of fields 110 (i.e. a structure with no fields) as it cannot be guessed from the syntax 111 otherwise, so it is best to always include one or the other when writing a 112 macro which expands to uses of @racket[tagged]. 113 114 When types are specified, they are used to annotate the values when producing 115 an instance, otherwise they are used as the argument types for the builder 116 function. 117 118 When @racket[#:∀ (tvarⱼ ...)] is specified for a builder, a polymorphic 119 builder is produced, with the given @racket[tvarⱼ ...] type variables. 120 121 When @racket[#:∀ (tvarⱼ ...)] is specified for an instance, the type of 122 values annotated with @racket[tvarⱼ] is inferred, and an instance of a 123 polymorphic tagged structure is produced. A @racket[tvarⱼ] can be used within 124 a more complex type, in which case only that part of the type is inferred. 125 126 The elements may appear in any order, as long as the tag name appears before 127 any field descriptor, and as long as the field descriptors form a contiguous 128 sequence.} 129 130 @defform[#:kind "match expander" 131 #:link-target? #f 132 #:literals (:) 133 (tagged tag-name maybe-no-implicit field-maybe-patsᵢ ...) 134 #:grammar 135 [(tag-name Identifier) 136 (maybe-no-implicit (code:line) 137 (code:line #:no-implicit-bind)) 138 (field-maybe-patsᵢ fieldᵢ 139 [fieldᵢ patᵢⱼ ...]) 140 (fieldᵢ Identifier) 141 (patᵢⱼ #,"match pattern")]]{ 142 Expands to a match pattern for a tagged structure with the given name and 143 fields. The value of each @racket[fieldᵢ] is matched against all of the 144 corresponding @racket[patᵢⱼ ...]. When there are not @racket[patᵢⱼ] for a 145 @racket[fieldᵢ], the brackets around the field name may be omitted. 146 147 Unless @racket[#:no-implicit-bind] is specified, every @racket[fieldᵢ] is 148 bound by the match pattern to the field's value. 149 150 The elements may appear in any order, as long as the tag name appears before 151 any @racket[field-maybe-patsᵢ], and as long as the @racket[field-maybe-patsᵢ] 152 form a contiguous sequence.} 153 154 @defform*[#:kind "syntax" 155 #:literals (:) 156 [(tagged? tag-name fieldᵢ ...) 157 (tagged? tag-name [fieldᵢ : typeᵢ] ...) 158 (tagged? tag-name [fieldᵢ predᵢ] ...)] 159 #:contracts ([tag-name Identifier] 160 [fieldᵢ Identifier] 161 [typeᵢ Type/Make-Predicate] 162 [predᵢ (ExpressionOf (→ Any Any : typeᵢ))])]{ 163 Expands to a predicate for tagged structures with the given @racket[tag] and 164 @racket[field]s. If types are specified, each @racket[typeᵢ] is passed to 165 @racket[make-predicate], and the resulting predicate is checked against the 166 value of the corresponding @racket[fieldᵢ]. 167 168 Each @racket[typeᵢ] must therefore be a valid type for which 169 @racket[make-predicate] can generate a predicate (@racket[make-predicate] 170 cannot create a predicate for some types, like function types, or any type 171 which translates to a 172 @tech[#:doc '(lib "scribblings/reference/reference.scrbl")]{chaperone} 173 contract. 174 175 The last form allows the use of arbitrary predicates @racket[predᵢ] which are 176 checked against the value of the corresponding @racket[fieldᵢ]. When the type 177 of a given @racket[predᵢ] includes a filter asserting that it returns true if 178 and only if the value is of type @racket[typeᵢ], then the predicate produced by 179 @racket[tagged-predicate!] will also have that filter on the corresponding 180 field. By default, any function of type @racket[(→ Any Any)] will 181 implicitly have the @racket[Any] filter, which does not bring any extra 182 information. 183 184 The elements may appear in any order, as long as the tag name appears before 185 any field descriptor, and as long as the field descriptors form a contiguous 186 sequence.} 187 188 @defform[#:kind "syntax" 189 #:literals (:) 190 (define-tagged name maybe-tag-name maybe-predicate? fields-maybe-types) 191 #:grammar 192 [(name Identifier) 193 (maybe-tag-name (code:line) 194 (code:line #:tag tag-name)) 195 (tag-name Identifier) 196 (maybe-predicate? (code:line) 197 (code:line #:? predicate-name?)) 198 (predicate-name? Identifier) 199 (fields-maybe-types (code:line just-fieldᵢ ...) 200 (code:line maybe-∀ field+type-descriptorᵢ ...)) 201 (maybe-∀ (code:line) 202 (code:line #:∀ (tvarⱼ ...))) 203 (just-fieldᵢ fieldᵢ 204 [fieldᵢ]) 205 (field+type-descriptor [fieldᵢ typeᵢ] 206 [fieldᵢ : typeᵢ]) 207 (fieldᵢ Identifier) 208 (typeᵢ Type) 209 (tvarⱼ Identifier)]]{ 210 211 Defines @racket[name] as a shorthand for the type expander, match expander, 212 builder function and predicate for a tagged structure with the given 213 @racket[tag-name] and fields. 214 215 When @racket[#:tag tag-name] is omitted, it defaults to @racket[name]. 216 217 The predicate is bound to @racket[predicate-name?]; When 218 @racket[#:? predicate-name?] is omitted, it defaults to @racket[_name?], which 219 is an identifier with the same lexical context as @racket[name], with a 220 @racket["?"] appended at the end. 221 222 The @racket[_name] and @racket[_predicate?] identifiers behave as follows: 223 224 @(make-blockquote 225 "leftindent" 226 (flow-paragraphs 227 (decode-flow 228 (splice-run 229 @defidform[#:kind "type expander" 230 #:link-target? #f 231 _name]{ 232 Expands to the same type as @racket[(tagged tag-name fields-maybe-types)] 233 would.})))) 234 235 @(make-blockquote 236 "leftindent" 237 (flow-paragraphs 238 (decode-flow 239 (splice-run 240 @defidform[#:link-target? #f _name]{ 241 Expands to the same builder function as 242 @racket[(tagged #:builder tag-name fields-maybe-types)] would.})))) 243 244 @(make-blockquote 245 "leftindent" 246 (flow-paragraphs 247 (decode-flow 248 (splice-run 249 @defform[#:kind "match expander" 250 #:link-target? #f 251 (_name patᵢ ...)]{ 252 Expands to the same match pattern as 253 @racket[(tagged tag-name [fieldᵢ patᵢ] ...)] would.})))) 254 255 @(make-blockquote 256 "leftindent" 257 (flow-paragraphs 258 (decode-flow 259 (splice-run 260 @defidform[#:link-target? #f _predicate?]{ 261 Expands to the same predicate as @racket[(tagged? just-fieldᵢ)] would. Note 262 that it does not attempt to check the field values, as doing so would mean 263 that all of the @racket[typeᵢ], if specified, would have to be suitable 264 arguments for @racket[make-predicate].})))) 265 266 The elements of the grammar for @racket[define-tagged] may appear in any 267 order, as long as the tag name appears before any field descriptor, and as 268 long as the field descriptors form a contiguous sequence.} 269 270 @defform[#:kind "type expander" 271 #:literals (:) 272 (tagged-supertype tag-name field+typeᵢ ...) 273 #:grammar 274 [(tag-name Identifier) 275 (field+type [fieldᵢ typeᵢ] 276 [fieldᵢ : typeᵢ])]]{ 277 Expands to the union type of all tagged structures with the given name and a 278 superset of the given fields, where each given @racket[fieldᵢ] must have the 279 corresponding type @racket[typeᵢ], and the other fields have the type 280 @racket[Any].} 281 282 @defform[#:kind "match expander" 283 #:link-target? #f 284 #:literals (:) 285 (tagged-supertype tag-name maybe-no-implicit field-maybe-patsᵢ ...) 286 #:grammar 287 [(tag-name Identifier) 288 (maybe-no-implicit (code:line) 289 (code:line #:no-implicit-bind)) 290 (field-maybe-patsᵢ fieldᵢ 291 [fieldᵢ patᵢⱼ ...]) 292 (fieldᵢ Identifier) 293 (patᵢⱼ #,"match pattern")]]{ 294 Expands to a match pattern accepting any tagged structures with the given 295 name and a superset of the given fields, where each given @racket[fieldᵢ] must 296 match all the corresponding @racket[patᵢⱼ], and the other fields are matched 297 against @racket[_] (i.e. they can contain any value). 298 299 Unless @racket[#:no-implicit-bind] is specified, every @racket[fieldᵢ] is 300 bound by the match pattern to the field's value, but the other extra fields 301 are not bound to any variable. 302 303 The elements may appear in any order, as long as the tag name appears before 304 any field descriptor, and as long as the field descriptors form a contiguous 305 sequence.} 306 307 @defform[(tagged-supertype* …)]{ 308 Currently not implemented. Will be equivalent to nesting 309 @racket[tagged-supertype].} 310 311 @defidform[#:kind "type" 312 TaggedTop]{ 313 314 The supertype of all @tech{tagged structures}, including @tech{untagged 315 structures}, @tech{nodes} and @tech{constructors}.} 316 317 @defproc[(TaggedTop? [v Any]) Boolean]{ 318 A predicate for @racket[TaggedTop]. It accepts all @tech{tagged structures}, 319 including @tech{untagged structures}, @tech{nodes} and @tech{constructors}, 320 and rejects any other value.} 321 322 @defform[(uniform-get v f) 323 #:grammar 324 ([v Expression] 325 [f Identifier])]{ 326 Returns the value contained within the @racket[f] field of the tagged structure 327 instance @racket[v].}