Changes between Initial Version and Version 1 of FirstClassLabels

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