Changes between Initial Version and Version 1 of FirstClassLabels

Feb 13, 2006 8:11:10 PM (12 years ago)

add first class labels, from Claus Reinke


  • FirstClassLabels

    v1 v1  
     1= First Class Labels =
     3== The Opportunity ==
     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.
     12Examples include
     14  * [ 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)
     20== The Problem ==
     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  }}}
     31However, this approach quickly runs into pragmatic issues in multi-module
     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.
     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
     47  module B where
     48  data PointX = PointX deriving Show
     49  main = print PointX
     51  module C where
     52  import A
     53  import B
     54  main = print [PointX,A.PointX,B.PointX] -- conflict here! ambiguous occurrence..
     55  }}}
     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!
     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.
     67== The Proposal ==
     69'''I propose to introduce implicitly declared typed labels as first-class values
     70into Haskell' (ticket:92)'''.
     72=== Options ===
     74'''Option 1:'''
     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`).
     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.
     87With this option, the problematic example would look like this:
     89module A where
     90main = print #pointX
     92module B where
     93main = print #pointX
     95module C where
     96import A
     97import B
     98main = print [#pointX,A.#pointX,B.#pointX] -- no conflicts here!
     101'''pro:''' simple in use, labels have their own namespace, no conflicting imports, known to work
     103'''con:''' need to give up some identifiable space in the language for labels and their types
     106'''Option 2:'''
     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).
     112This would have a major impact on language and implementations.  Assuming a
     113sharing declaration of the form
     115  sharing <type1> <type2>
     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
     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.
     127With this option, the problematic example would look like this:
     129module A where
     130data PointX = PointX deriving Show
     131main = print PointX
     133module B where
     134data PointX = PointX deriving Show
     135main = print PointX
     137module C where
     138import A
     139import B
     140sharing A.PointX B.PointX
     141main = print [PointX,A.PointX,B.PointX] -- no conflicts here!
     144'''pro:''' seems like a useful feature anyway
     146'''con:''' more complex than needed for this proposal, and would be rather verbose in use
     149'''Option 3:'''
     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).
     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.
     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`.
     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.
     168With this option, the problematic example would look like this:
     170module A where
     171import Data.Label(pointX)
     172main = print pointX
     174module B where
     175import Data.Label(pointX)
     176main = print pointX
     178module C where
     179import A
     180import B
     181main = print [pointX,A.pointX,B.pointX] -- no conflicts here!
     184'''pro:''' no syntax extension or separate label namespace, no problems with common imports
     186'''con:''' no separate label namespace, labels still need to be declared, by means of import
     188== Related Tickets and Links ==
     190- ticket:92 add first class labels
     192- ticket:27 tweak the existing records system (adopt: none)
     194- ticket:54 add overlapping or incoherent instances (adopt: probably no)
     196- ticket:71 Allow Undecidable Instances (adopt: probably no)
     198- ticket:36 add FunctionalDependencies (adopt: probably no)
     200- ticket:49 add multi parameter type classes (adopt: probably yes)
     202- [ Extensible records with scoped labels]
     204- [ Strongly typed heterogeneous collections]
     206- [ original Haskell' mailing list message]