Changes between Version 2 and Version 3 of Ticket #92


Ignore:
Timestamp:
Feb 13, 2006 8:11:31 PM (9 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]