README.md (6275B)
1 [](https://travis-ci.org/jsmaniac/phc-adt) 2 [](https://codecov.io/gh/jsmaniac/phc-adt) 3 [](http://jsmaniac.github.io/travis-stats/#jsmaniac/phc-adt) 4 [](http://docs.racket-lang.org/phc-adt/) 5 [](https://github.com/jsmaniac/phc-adt/issues) 6 [](https://creativecommons.org/publicdomain/zero/1.0/) 7 8 phc-adt 9 ======= 10 11 This library provides Algebraic Datatypes (structures and variants), with the 12 features described below. It is designed to work hand-in-hand with our graph 13 library (https://github.com/jsmaniac/phc), but can also be used on its own. 14 15 Structures 16 ---------- 17 18 We define structures as an extension of Racket's syntax. Structures are 19 anonymous products of values, where each value is annotated by a field 20 name. The syntax used for constructing an instance of a structure is: 21 22 (structure [field₁ : value₁] … [fieldₙ : valueₙ]) 23 24 The type of a structure is described using a similar syntax: 25 26 (structure [field₁ : type₁] … [fieldₙ : typeₙ]) 27 28 Accessing the field `f` of an instance `i` is done using the dot operator: 29 30 i.f 31 32 The main difference with Racket's built-in `struct` is that the type does not 33 need to be pre-declared to create instances of a structure, making them 34 effectively anonymous. Racket also requires knowing the name of the struct 35 type in order to access a field of an instance, using `(s-f i)` where `s` is 36 the struct's name, `f` is the field name and `i` is the instance. When very 37 similar structures are used, specifying the structure's name each time becomes 38 cumbersome. 39 40 Unions 41 ------ 42 43 Typed/Racket has built-in untagged union types, which can be constructed using 44 the following notation: 45 46 (U type₁ … typeₙ) 47 48 These cannot be used as-is inside node types for our graph library 49 (https://github.com/jsmaniac/phc), because there is no way at run-time to 50 distinguish between the various cases of the union in the general case. For 51 example, `(U (→ Integer) (→ String))` denotes the type of an union of thunks, 52 one returning an `Integer` and the other a `String`, and it is not 53 possible to know to which case an instance belongs without calling the thunks, 54 which could have undesired side-effects. 55 56 The graph library's implementation relies on being able to rewrite arbitrary 57 data structures, changing the type of some parts in the process. We therefore 58 allow only a limited form of unions, namely those where all cases but one are 59 pairs whose first element is a symbol. The first element of the pair can then 60 be used to distinguish between the cases. The remaining case is used as a 61 fall-back when the symbol comparison for all others have failed, and should 62 not overlap with the other cases. 63 64 Variants 65 -------- 66 67 We define variants (tagged unions) as an alternative to Racket's untagged 68 unions. In our implementation, variants are anonymous unions of 69 constructors. Each constructor is a tuple of values annotated with a 70 tag. Variants are usually not anonymous in other languages: the same 71 constructor cannot belong to two different variants. In our implementation, 72 this is not the case: two different variants can contain the same exact 73 constructor. The reason for this feature is that the input and output types of 74 graph transformations are very similar, and are likely to contain 75 nearly-identical variants. Name collisions would be frequent if a constructor 76 name was bound to a single variant. We use the following syntax to denote a 77 variant type: 78 79 (V constructor₁ … constructorₙ) 80 81 Constructors are the product of a tag name and a payload, which is itself a 82 product of zero or more types. Constructors types are declared as follows: 83 84 (constructor tag payload₁ … payloadₙ) 85 86 Instances of a constructor can be created using the following syntax: 87 88 (constructor tag v₁ … vₙ) 89 90 All constructors within a variant should have a distinct tag, but the same tag 91 name can be used in the several variants, with an identical or different 92 payload. 93 94 To improve encapsulation, we further define *private* constructors. These have 95 a unique tag which is uncomparable to all other tags, even those using the 96 same string of characters for the name. We also define *uninterned* 97 constructors, which are strict subtypes of the regular constructor with the 98 same name (i.e. using the same string of characters for the name). Another way 99 to see these is that a *private* constructor protects both its creation 100 mechanism and its matching mechanism, whereas the *uninterned* constructors 101 protect only the creation mechanism, but no special permission is needed to 102 match on an *uninterned* constructor. 103 104 When using Racket's `match` form, an instance of a variant only matches with 105 its tag (or an uninterned subtype) and the same number of fields. 106 107 --- 108 109 Nodes 110 ----- 111 112 Below follows a short description of graph nodes, which are provided by a 113 separate library (https://github.com/jsmaniac/phc-graph, code is currently 114 being refactored and migrated from https://github.com/jsmaniac/phc). 115 116 Graph nodes behave like tagged structures in most aspects. They are similar to 117 a constructor containing a structure as its single field. An *incomplete* node 118 can only be created within a *mapping* of the same graph, using a notation 119 similar to the one used for structures: 120 121 (node-name [field₁ : value₁] … [fieldₙ : valueₙ]) 122 123 The type of a node can be expressed similarly: 124 125 (node-name [field₁ : type₁] [fieldₙ : typeₙ]) 126 127 It is not possible to access an *incomplete* node's fields. However, once the 128 graph is fully constructed, the field `f` of the *promise* node `p` can be 129 accessed using the same dot operator: 130 131 p.f 132 133 On the other hand, it is not possible to directly create a promise node 134 without using a graph constructor. 135 136 **TODO:** nodes are actually rather similar to uninterned constructors 137 containing a single value, which is a structure.