Changes between Version 2 and Version 3 of Ticket #92

Show
Ignore:
Timestamp:
02/13/06 12:11:31 (7 years ago)
Author:
ijones
Comment:

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #92

    • Property summary changed from First Class Labels to add First Class Labels

  • Ticket #92 – description

    v2 v3  
    2424 
    2525----- 
    26  
    27  
    28 = First Class Labels = 
    29  
    30 == The Opportunity == 
    31  
    32 Haskell's type class and instance language enables a form of logic 
    33 meta-programming at the level of types. Since record system proposal can often 
    34 be phrased as an instance of Qualified Types, this means that '''many (not all!) 
    35 features of polymorphic extensible record systems can be implemented as a 
    36 Haskell library'''. To work around the limitation of Haskell 98, ''this tends to 
    37 require several language extensions'', as implemented in GHC and Hugs. 
    38  
    39 Examples include 
    40  
    41   * [http://homepages.cwi.nl/~ralf/HList/ Strongly typed heterogeneous collections] 
    42   * attachment:ticket:92:Data.Record.hs, which demonstrates an 
    43     implementation of something similar to Daan Leijen's extensible records 
    44     with scoped labels (though with type predicates instead of simple type 
    45     system extension; as a bonus, we have record concatenation as well) 
    46  
    47 == The Problem == 
    48  
    49 Independent of the specific record library, there needs to be a representation 
    50 of record field labels, and as record field selection in theses libraries is 
    51 usually based on types, field labels need to be distinguishable by their 
    52 types. In principle, this can easily be achieved by declaring for each label a 
    53 single-constructor data type: 
    54   {{{ 
    55   data LabelX = LabelX deriving (Read,Show) 
    56   }}} 
    57  
    58 However, this approach quickly runs into pragmatic issues in multi-module 
    59 programming: 
    60   1. There needs to be a common origin for importing record field label declarations used accross several modules. 
    61   2. The labels occupy the same namespace as types and data constructors, and using qualified names as record field labels is awkward at best. 
    62  
    63 Of these, 1 is the most severe. To wit, imagine that we have two modules, A 
    64 and B (think ...OpenGL and some GUI library), that both want to use records 
    65 with fields named 'PointX'. They'd both have to declare the field label, but 
    66 if we ever want to import A and B into the same module C (think OpenGL windows 
    67 in a GUI), we are in trouble, because we have two "conflicting" declarations 
    68 for PointX. Note that the following doesn't work! 
    69   {{{ 
    70   module A where  
    71   data PointX = PointX deriving Show 
    72   main = print PointX 
    73  
    74   module B where  
    75   data PointX = PointX deriving Show 
    76   main = print PointX 
    77  
    78   module C where 
    79   import A 
    80   import B 
    81   main = print [PointX,A.PointX,B.PointX] -- conflict here! ambiguous occurrence.. 
    82   }}} 
    83  
    84 Not only is the unqualified reference to PointX in C ambiguous, but qualifying 
    85 the labels doesn't help either: in spite of our intentions, A.PointX and 
    86 B.PointX are different types! 
    87  
    88 With current Haskell, the only way around this is to modify the imports: 
    89 introduce a new common ancestor module, say PointX, that declares the label 
    90 PointX, and have both A and B import that. However, this is impractical: it 
    91 breaks module composition, and there is no least upper bound in the import 
    92 hierarchy where we can safely place our label declarations once and for all. 
    93  
    94 == The Proposal == 
    95  
    96 '''I propose to introduce implicitly declared typed labels as first-class values 
    97 into Haskell' (ticket:92)'''. 
    98  
    99 === Options === 
    100  
    101 '''Option 1:''' 
    102  
    103 make label declarations unneccessary, by reserving a separate namespace for 
    104 labels and their types (to be concrete, prefix identifiers with '#', so that 
    105 we'd have `#pointX :: #PointX`). 
    106  
    107 This would affect language and implementations in the same way as numeric, 
    108 character, and string literals do. In particular, every occurrence of 
    109 `'#'<identifier>` would be interpreted as a value of type `'#'<Identifier>` 
    110 (the label type name is the capitalized label name). Apart from having their 
    111 own namespace, identified by the prefix '#', labels and their types would 
    112 just be ordinary constants and types, respectively. 
    113  
    114 With this option, the problematic example would look like this: 
    115 {{{ 
    116 module A where  
    117 main = print #pointX 
    118  
    119 module B where  
    120 main = print #pointX 
    121  
    122 module C where 
    123 import A 
    124 import B 
    125 main = print [#pointX,A.#pointX,B.#pointX] -- no conflicts here!  
    126 }}} 
    127  
    128 '''pro:''' simple in use, labels have their own namespace, no conflicting imports, known to work 
    129  
    130 '''con:''' need to give up some identifiable space in the language for labels and their types 
    131              
    132  
    133 '''Option 2:''' 
    134  
    135 make type sharing expressible (something like the sharing constraints in 
    136 Standard ML's module language, to allow you to say when two declarations from 
    137 different imports refer to the same type). 
    138  
    139 This would have a major impact on language and implementations.  Assuming a 
    140 sharing declaration of the form  
    141 {{{ 
    142   sharing <type1> <type2> 
    143 }}} 
    144 the implementation would have to: 
    145  1. find the declarations of `type1` and `type2` and check them for structural equivalence 
    146  2. unify `type1` and `type2`, ie., interpret either of them as a synonym for the same underlying type 
    147  
    148 In full generality, a feature like this would help to address 
    149 similar problems with other conflicting imports, and could be 
    150 extended to cover classes and instances as well (though instances 
    151 couldn't be named). For the current proposal, however, only a 
    152 trivial part of that generality would be needed. 
    153  
    154 With this option, the problematic example would look like this: 
    155 {{{ 
    156 module A where  
    157 data PointX = PointX deriving Show 
    158 main = print PointX 
    159  
    160 module B where  
    161 data PointX = PointX deriving Show 
    162 main = print PointX 
    163  
    164 module C where 
    165 import A 
    166 import B 
    167 sharing A.PointX B.PointX 
    168 main = print [PointX,A.PointX,B.PointX] -- no conflicts here! 
    169 }}} 
    170  
    171 '''pro:''' seems like a useful feature anyway 
    172  
    173 '''con:''' more complex than needed for this proposal, and would be rather verbose in use 
    174  
    175  
    176 '''Option 3:'''  
    177  
    178 introduce a common least upper bound for shared label imports.  (to be 
    179 concrete: there would be a module `Data.Label`, implicitly providing shared 
    180 declarations of any labels). 
    181  
    182 This would have a similarly small effect on the type system as Option 1, only 
    183 that instead of syntax, we'd use imports from the reserved module `Data.Label` 
    184 to identify what is a label and what is not. 
    185  
    186 Whenever encountering an `import Data.Label(<identifier>)`, we interpret 
    187 `Data.Label.<identifier>` as a constant of type `Data.Label.<Identifier>` and 
    188 `<identifier>` as a constant of type `<Identifier>`. the difference to normal 
    189 imports is that the compiler/type system needs to know about `Data.Label`. 
    190  
    191 In other words, `Data.Label` does not exist in source or object code, but as a 
    192 hint for the compiler/type system. Any identifier imported from there is a 
    193 label of its own type, nothing else can be imported from there. 
    194  
    195 With this option, the problematic example would look like this: 
    196 {{{ 
    197 module A where  
    198 import Data.Label(pointX) 
    199 main = print pointX 
    200  
    201 module B where  
    202 import Data.Label(pointX) 
    203 main = print pointX 
    204  
    205 module C where 
    206 import A 
    207 import B 
    208 main = print [pointX,A.pointX,B.pointX] -- no conflicts here! 
    209 }}} 
    210  
    211 '''pro:''' no syntax extension or separate label namespace, no problems with common imports 
    212  
    213 '''con:''' no separate label namespace, labels still need to be declared, by means of import 
    214  
    215 == Related Tickets and Links == 
    216  
    217 - ticket:27 tweak the existing records system (adopt: none) 
    218  
    219 - ticket:54 add overlapping or incoherent instances (adopt: probably no) 
    220  
    221 - ticket:71 Allow Undecidable Instances (adopt: probably no) 
    222  
    223 - ticket:36 add FunctionalDependencies (adopt: probably no) 
    224  
    225 - ticket:49 add multi parameter type classes (adopt: probably yes) 
    226  
    227 - [http://www.cs.uu.nl/~daan/pubs.html Extensible records with scoped labels] 
    228    
    229 - [http://homepages.cwi.nl/~ralf/HList/ Strongly typed heterogeneous collections] 
    230  
    231 - [http://www.haskell.org//pipermail/haskell-prime/2006-February/000463.html original Haskell' mailing list message]