Changes between Initial Version and Version 1 of FirstClassLabels


Ignore:
Timestamp:
Feb 13, 2006 8:11:10 PM (10 years ago)
Author:
ijones
Comment:

add first class labels, from Claus Reinke

Legend:

Unmodified
Added
Removed
Modified
  • FirstClassLabels

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