Changes between Initial Version and Version 1 of FirstClassLabels


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