Changes between Version 1 and Version 2 of Ticket #92

Feb 13, 2006 7:37:04 PM (10 years ago)


  • Ticket #92 – Description

    v1 v2  
    1313  * [ Strongly typed heterogeneous collections]
    14   * the attached attachment:Data.Record.hs
     14  * attachment:Data.Record.hs
    1616''Any such libary will need to represent record field labels, and if record
    2222use of such record libraries (such typed constants have other uses in
    2323type-level programming as well).
     28= First Class Labels =
     30== The Opportunity ==
     32Haskell's type class and instance language enables a form of logic
     33meta-programming at the level of types. Since record system proposal can often
     34be phrased as an instance of Qualified Types, this means that '''many (not all!)
     35features of polymorphic extensible record systems can be implemented as a
     36Haskell library'''. To work around the limitation of Haskell 98, ''this tends to
     37require several language extensions'', as implemented in GHC and Hugs.
     39Examples include
     41  * [ 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)
     47== The Problem ==
     49Independent of the specific record library, there needs to be a representation
     50of record field labels, and as record field selection in theses libraries is
     51usually based on types, field labels need to be distinguishable by their
     52types. In principle, this can easily be achieved by declaring for each label a
     53single-constructor data type:
     54  {{{
     55  data LabelX = LabelX deriving (Read,Show)
     56  }}}
     58However, this approach quickly runs into pragmatic issues in multi-module
     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.
     63Of these, 1 is the most severe. To wit, imagine that we have two modules, A
     64and B (think ...OpenGL and some GUI library), that both want to use records
     65with fields named 'PointX'. They'd both have to declare the field label, but
     66if we ever want to import A and B into the same module C (think OpenGL windows
     67in a GUI), we are in trouble, because we have two "conflicting" declarations
     68for PointX. Note that the following doesn't work!
     69  {{{
     70  module A where
     71  data PointX = PointX deriving Show
     72  main = print PointX
     74  module B where
     75  data PointX = PointX deriving Show
     76  main = print PointX
     78  module C where
     79  import A
     80  import B
     81  main = print [PointX,A.PointX,B.PointX] -- conflict here! ambiguous occurrence..
     82  }}}
     84Not only is the unqualified reference to PointX in C ambiguous, but qualifying
     85the labels doesn't help either: in spite of our intentions, A.PointX and
     86B.PointX are different types!
     88With current Haskell, the only way around this is to modify the imports:
     89introduce a new common ancestor module, say PointX, that declares the label
     90PointX, and have both A and B import that. However, this is impractical: it
     91breaks module composition, and there is no least upper bound in the import
     92hierarchy where we can safely place our label declarations once and for all.
     94== The Proposal ==
     96'''I propose to introduce implicitly declared typed labels as first-class values
     97into Haskell' (ticket:92)'''.
     99=== Options ===
     101'''Option 1:'''
     103make label declarations unneccessary, by reserving a separate namespace for
     104labels and their types (to be concrete, prefix identifiers with '#', so that
     105we'd have `#pointX :: #PointX`).
     107This would affect language and implementations in the same way as numeric,
     108character, 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
     111own namespace, identified by the prefix '#', labels and their types would
     112just be ordinary constants and types, respectively.
     114With this option, the problematic example would look like this:
     116module A where
     117main = print #pointX
     119module B where
     120main = print #pointX
     122module C where
     123import A
     124import B
     125main = print [#pointX,A.#pointX,B.#pointX] -- no conflicts here!
     128'''pro:''' simple in use, labels have their own namespace, no conflicting imports, known to work
     130'''con:''' need to give up some identifiable space in the language for labels and their types
     133'''Option 2:'''
     135make type sharing expressible (something like the sharing constraints in
     136Standard ML's module language, to allow you to say when two declarations from
     137different imports refer to the same type).
     139This would have a major impact on language and implementations.  Assuming a
     140sharing declaration of the form
     142  sharing <type1> <type2>
     144the 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
     148In full generality, a feature like this would help to address
     149similar problems with other conflicting imports, and could be
     150extended to cover classes and instances as well (though instances
     151couldn't be named). For the current proposal, however, only a
     152trivial part of that generality would be needed.
     154With this option, the problematic example would look like this:
     156module A where
     157data PointX = PointX deriving Show
     158main = print PointX
     160module B where
     161data PointX = PointX deriving Show
     162main = print PointX
     164module C where
     165import A
     166import B
     167sharing A.PointX B.PointX
     168main = print [PointX,A.PointX,B.PointX] -- no conflicts here!
     171'''pro:''' seems like a useful feature anyway
     173'''con:''' more complex than needed for this proposal, and would be rather verbose in use
     176'''Option 3:'''
     178introduce a common least upper bound for shared label imports.  (to be
     179concrete: there would be a module `Data.Label`, implicitly providing shared
     180declarations of any labels).
     182This would have a similarly small effect on the type system as Option 1, only
     183that instead of syntax, we'd use imports from the reserved module `Data.Label`
     184to identify what is a label and what is not.
     186Whenever 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
     189imports is that the compiler/type system needs to know about `Data.Label`.
     191In other words, `Data.Label` does not exist in source or object code, but as a
     192hint for the compiler/type system. Any identifier imported from there is a
     193label of its own type, nothing else can be imported from there.
     195With this option, the problematic example would look like this:
     197module A where
     198import Data.Label(pointX)
     199main = print pointX
     201module B where
     202import Data.Label(pointX)
     203main = print pointX
     205module C where
     206import A
     207import B
     208main = print [pointX,A.pointX,B.pointX] -- no conflicts here!
     211'''pro:''' no syntax extension or separate label namespace, no problems with common imports
     213'''con:''' no separate label namespace, labels still need to be declared, by means of import
     215== Related Tickets and Links ==
     217- ticket:27 tweak the existing records system (adopt: none)
     219- ticket:54 add overlapping or incoherent instances (adopt: probably no)
     221- ticket:71 Allow Undecidable Instances (adopt: probably no)
     223- ticket:36 add FunctionalDependencies (adopt: probably no)
     225- ticket:49 add multi parameter type classes (adopt: probably yes)
     227- [ Extensible records with scoped labels]
     229- [ Strongly typed heterogeneous collections]
     231- [ original Haskell' mailing list message]