Changes between Version 1 and Version 2 of Ticket #92


Ignore:
Timestamp:
Feb 13, 2006 7:37:04 PM (9 years ago)
Author:
claus
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #92 – Description

    v1 v2  
    1212 
    1313  * [http://homepages.cwi.nl/~ralf/HList/ Strongly typed heterogeneous collections] 
    14   * the attached attachment:Data.Record.hs 
     14  * attachment:Data.Record.hs 
    1515 
    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). 
     24 
     25----- 
     26 
     27 
     28= First Class Labels = 
     29 
     30== The Opportunity == 
     31 
     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. 
     38 
     39Examples 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 
     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  }}} 
     57 
     58However, this approach quickly runs into pragmatic issues in multi-module 
     59programming: 
     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 
     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 
     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 
     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! 
     87 
     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. 
     93 
     94== The Proposal == 
     95 
     96'''I propose to introduce implicitly declared typed labels as first-class values 
     97into Haskell' (ticket:92)'''. 
     98 
     99=== Options === 
     100 
     101'''Option 1:''' 
     102 
     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`). 
     106 
     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. 
     113 
     114With this option, the problematic example would look like this: 
     115{{{ 
     116module A where  
     117main = print #pointX 
     118 
     119module B where  
     120main = print #pointX 
     121 
     122module C where 
     123import A 
     124import B 
     125main = 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 
     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). 
     138 
     139This would have a major impact on language and implementations.  Assuming a 
     140sharing declaration of the form  
     141{{{ 
     142  sharing <type1> <type2> 
     143}}} 
     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 
     147 
     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. 
     153 
     154With this option, the problematic example would look like this: 
     155{{{ 
     156module A where  
     157data PointX = PointX deriving Show 
     158main = print PointX 
     159 
     160module B where  
     161data PointX = PointX deriving Show 
     162main = print PointX 
     163 
     164module C where 
     165import A 
     166import B 
     167sharing A.PointX B.PointX 
     168main = 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 
     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). 
     181 
     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. 
     185 
     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`. 
     190 
     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. 
     194 
     195With this option, the problematic example would look like this: 
     196{{{ 
     197module A where  
     198import Data.Label(pointX) 
     199main = print pointX 
     200 
     201module B where  
     202import Data.Label(pointX) 
     203main = print pointX 
     204 
     205module C where 
     206import A 
     207import B 
     208main = 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]