Changes between Version 2 and Version 3 of Records/SyntaxDirectedNameResolution


Ignore:
Timestamp:
Feb 27, 2012 9:58:42 PM (3 years ago)
Author:
elaforge
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Records/SyntaxDirectedNameResolution

    v2 v3  
    11= Syntax Directed Name Resolution = 
    22 
    3 The idea is a # prefix for identifiers.  `#f` is a "type directed function".  It 
    4 requires the type of its argument to be monomorphic, and is desugared to `M.f`, 
    5 where `M` is the module defining the type of `f`s argument. 
     3The idea is a # prefix for identifiers.  `#a` is a "type directed function". 
     4It requires the type of its argument to be monomorphic.  An application 
     5`#a :: forall x. M.X -> x` is desugared to `M.a :: M.X -> Y` where `Y` depends 
     6on the concrete type of `M.a`.  All it does is strip the module part off off 
     7the argument type, and look for the symbol `a` in that module.  The module 
     8must be imported qualified for the resolution to happen, so compiling a 
     9certain module only needs to look at its direct dependents. 
    610 
    711Everything else remains the same.  Records wishing the same name must live in 
    8 separate modules, but field access looks like: `(#a . #b) record` 
    9  
    10 This works to set fields of a record as well.  Let M.f be a function from 
     12separate modules, but field access looks like: `(#b . #a) record`.  People 
     13who like unqualified imports can still use them, since `import A.B.C` will 
     14bring `A.B.C.a` into scope as well as `a`.  If there are two `a`s from 
     15separate modules, an unqualified `a` will give an ambiguous error as always, 
     16but `#a` will use its argument type to automatically qualifiy it to the right 
     17module.  Since `#a` is desugared to `A.B.C.a` it's a separate symbol from `a` 
     18and they can both exist in the same module provided, of course, that you 
     19imported `A.B.C` qualified. 
     20 
     21This is enough for field access, but to support convenient modification, some 
     22notion of lenses has to be built in and the rule has to be modified, from 
     23`#a :: forall x. M.X -> x` ==> `M.a :: M.X -> Y` to look at the first argument 
     24of a `Lens` class: 
     25`#a :: forall x. Lens M.X x` ==> `M.a :: Lens M.X Y`.  Effectively this is 
     26just substituting `Lens` for `(->)`.  Maybe it could be extended to look at 
     27the first argument of any type constructor `forall m x. m M.X x`, that way 
     28the syntax can be used to resolve not just record fields, but any function, 
     29or any member of Category, or whatever. 
     30 
     31Here's an example using plain function "# resolution": 
     32 
     33{{{ 
     34import qualified Inner 
     35import qualified Outer 
     36-- data Outer.Outer = Outer { a :: Inner.Inner } 
     37-- data Inner.Inner = Inner { b :: Int } 
     38 
     39record :: Outer.Outer 
     40record = Outer.Outer (Inner.Inner 42) 
     41 
     42val :: Int 
     43val = (#b.#a) record 
     44 
     45-- Type of 'record' must already be known: 
     46(#b.#a) :: Outer.Outer -> Int 
     47-- Due to the definition of (.) and its return type being known: 
     48#a :: Outer.Outer -> b 
     49-- New "# Resolution" rule: The first argument is in module Outer, so 
     50-- resolve to Outer.a, and now we know the full type of Outer.a: 
     51Outer.a :: Outer.Outer -> Inner.Inner 
     52-- Due to the definition of (.) and its return type being known: 
     53#b :: Inner.Inner -> c 
     54-- # Resolution: 
     55Outer.b :: Inner.Inner -> Int 
     56-- So the Ints match, and val is (effectively) rewritten as: 
     57val = (Inner.b . Outer.a) record 
     58}}} 
     59 
     60This works to set fields of a record as well.  Let `M.a` be a function from 
    1161a record to a lens focused on a certain field of that record.  Now you can 
    1262write: 
    1363 
    1464{{{ 
    15 M.a :: M.Record -> Lens M.Record M.A 
    16 set :: Lens record field -> record -> record 
    17 val = set (#a 42) record 
    18 }}} 
    19  
    20 which becomes: `set (M.a record) 42` 
    21  
    22 Or composed `set ((#a.#b) record) 42` becomes `set ((M.a . N.b) record) 42` 
    23  
    24 Of course you can define operators for update if you like that kind of thing. 
    25  
    26 As long as the compiler can figure out a monomorphic type expected by the input 
    27 of #a then it shouldn't need type annotations. 
     65M.a :: M.Record -> Lens M.Record Int 
     66set :: record -> Lens record field -> field -> record 
     67 
     68record :: M.Record 
     69record = M.Record (6*9) 
     70 
     71val :: M.Record 
     72val = set (#a record) 42 
     73 
     74-- Due to the type of set: 
     75(#a record) :: record -> Lens record field -> record -> record 
     76-- Type of 'record' must already be known: 
     77#a :: M.Record -> b 
     78-- # Resolution: 
     79M.a :: M.Record -> Lens M.Record Int 
     80-- The Ints match, and val is: 
     81val = set (M.a record) 42 
     82}}} 
     83 
     84Unfortunately, it doesn't work with a lens get: 
     85 
     86{{{ 
     87get :: Lens record field -> record -> field 
     88val = get #a record 
     89#a :: Lens M.Record field 
     90-- Oops, can't apply # reduction, because its first argument type is 'Lens ...' 
     91-- not 'M.Record ...'. 
     92}}} 
     93 
     94The # resolution needs the #a to be a function with a known first argument 
     95type.  We could say that's fine because lenses are only really needed for 
     96setting since getting is already a plain composable function, and write gets 
     97like `#a_ record`.  But that's ugly and unsatisfying, and you can't pass 
     98around the getter and setter as one unit. 
     99 
     100Also, composed set will run into problems.  So lets build lenses into the 
     101language.  Two changes: as a convenience, `deriving (Lens)` will generate 
     102lenses for the fields instead of get functions.  And, the # reduction will 
     103treat an argument type of `Lens a b` specially, requiring that the type of `a` 
     104being known, and looking in its module: 
     105 
     106M.hs: 
     107{{{ 
     108data M.Record = Record { a :: Int } deriving (Lens) 
     109}}} 
     110 
     111{{{ 
     112import qualified M 
     113 
     114get :: Lens record field -> record -> field 
     115val = get #a record 
     116 
     117#a :: Lens M.Record field 
     118-- # resolution on Lens: 
     119M.a :: Lens M.Record Int 
     120-- val is 
     121val = get M.a record 
     122}}} 
     123 
     124 
     125Let's try with composed lenses. 
     126 
     127`set ((#b.#a) record) 42` should become `set ((Inner.b . Outer.a) record) 42` 
     128 
     129Outer.hs: 
     130{{{ 
     131data Outer = Outer { a :: Inner.Inner } deriving (Lens) 
     132}}} 
     133 
     134Inner.hs: 
     135{{{ 
     136data Inner = Inner { b :: Int } deriving (Lens) 
     137}}} 
     138 
     139Main.hs: 
     140{{{ 
     141-- A lens composition operator.  Most lens libraries overload (.) with this, 
     142-- so we'd either need to make a new operator or move Control.Category into 
     143-- the Prelude.  Let's go with a new operator: 
     144(!) :: Lens b c -> Lens a b -> Lens a c 
     145 
     146-- This is the more usual argument order for 'set'.  It makes it easier to 
     147-- partially apply as well: 
     148set :: Lens record field -> field -> record -> record 
     149 
     150record :: Outer.Outer 
     151record = Outer.Outer (Inner.Inner 42) 
     152 
     153val :: Outer.Outer -> Outer.Outer 
     154val = set (#b!#a) 42 
     155 
     156-- Due to the type of 'set' and the type of 'record' already being known: 
     157(#b!#a) :: Lens Outer.Outer field 
     158-- Due to the definition of (!) and its return type being known: 
     159#a :: Lens Outer.Outer b 
     160-- # resolution on Lens: 
     161Outer.a :: Lens Outer.Outer Inner.Inner 
     162-- Due to the second argument of (!) being known: 
     163#b :: Lens Inner.Inner c 
     164-- # resolution on Lens 
     165Inner.b :: Lens Inner.Inner Int 
     166-- result is 
     167val = set (Inner.b ! Outer.a) 42 record 
     168}}} 
     169 
     170Note that there must be a known monomorphic type for the #a so this may require 
     171some type declarations: 
     172 
     173{{{ 
     174-- no type declared 
     175set42 = set #a 42 
     176 
     177-- Due to type of 'set': 
     178#a :: Lens a b 
     179-- 'a' is not monomorphic, error! 
     180}}} 
     181 
     182However, they should be rare in practice, since if `set42` is passed to a 
     183function that gives it a monomorphic type or applied to a M.Record then the 
     184ambiguity is resolved. 
     185 
     186== discussion == 
     187 
     188If we can generalize #-resolution to work on an arbitrary binary type constructor 
     189argument like `(~>) Known x` then we don't need to build a Lens class in.  That's 
     190nice because people can keep experimenting with libraries, especially since 
     191different lens libraries have different features (e.g. StateT integration, 
     192partial lenses, etc.).  However, in practice records aren't very satisfying 
     193without a nice update syntax, so perhaps a lens library should be promoted to 
     194the platform at least.  Can the new "generalized deriving" feature replace 
     195ugly TH splices with a nice deriving clause or would that need to be built in?  At the least I think it would need an extension to suppress record declaration's automatic creation of get functions. 
    28196 
    29197== pros == 
     
    33201 3. Works on any function, so it doesn't tie you to the implementation of a record, you can remove a field and add a compatibility shim.  So no tension between directly exposing the record implementation vs. writing a bunch of set/modify boilerplate. 
    34202 4. Module export list controls access over record fields as always. 
    35  5. The problem of field access and update is not built in to the language but relegated to a library. 
    36  6. Orthogonal to records: any function can be addressed. 
     203 5. Orthogonal to records: any function can be addressed. 
    37204 
    38205== cons == 
    39206 
    40  1. Still can't have two records with the same field name in the same module since it relies on modules for namespacing.  Would need nested modules to put multiple  
    41  2. Lenses can't handle updates that change the type, e.g. from `Rec a` to `Rec b`.  If the `set` function is `Lens rec field -> field -> rec -> rec` then you can't change the type of `rec`.  Not sure if this is solvable without the set being builtin syntax, or a fancier lens implementation could admit `Lens rec1 rec2 field -> field -> rec1 -> rec2`. 
     207 1. Still can't have two records with the same field name in the same module since it relies on modules for namespacing. 
     208 2. Lenses can't handle updates that change the type, e.g. from `Rec a` to `Rec b`.  If the `set` function is `Lens rec field -> field -> rec -> rec` then you can't change the type of `rec`.  I'm sure if this is solvable without the set being builtin syntax, or a fancier lens implementation could admit `Lens rec1 rec2 field -> field -> rec1 -> rec2`. 
    42209 3. It's another way to resolve a name to a different function body that's not typeclasses.  One way should be enough.  But typeclasses are fundamentally global. 
    43210 4. The function to resolve must be monomorphic, so there is no "structural polymorphism" e.g. `getName :: (Has Name a) => a -> String` 
    44  5. Still have to use TH to derive the lenses. 
    45  
    46 From my point of view (elaforge), the pros are very compelling, especially how record fields aren't a built-in concept but are just normal haskell identifiers. 
     211 
     212From my point of view (elaforge), the pros are compelling, especially how 
     213record fields aren't a built-in concept but are just normal haskell 
     214identifiers. 
    47215 
    48216My spin on the cons: 
    49217 
    50  1. I don't mind.  To my mind, modules are there for namespace control and so two things shouldn't be able to have the same name in one module by definition.  Nested modules might be a more orthogonal way to approach namespacing flexibility than coming up with some non-module non-typeclass way to distinguish names. 
    51  2. It's not too satisfying, but you can fall back to `rec { field = ... }`.  In practice I'd define a type specific update function as I do now, to avoid being tied `field` always existing in the record. 
     218 1. I don't mind.  To my mind, modules are there for namespace control and so two things shouldn't be able to have the same name in one module by definition.  I have very few records that really want to have the same field name *and* live in the same module, but for those who have more of those, nested modules would be an orthogonal feature that would satisfy them. You could argue that this is a necessary development, because modules are *the* user-controlled namespace and access control mechanism (typeclasses are always global and hence not that controlled), then the solution must be modules.  Any other solution is either going to be unsatisfactory because you can't control the scope of the names, or unsatisfactory because it's a non-module way of namespacing. 
     219 
     220 2. It's not too satisfying, but you can fall back to `rec { field = ... }`.  In practice I'd define a type specific update function as I do now, to avoid being tied `field` always existing in the record.  Still, it's worth thinking about whether this proposal could later be extended to support type-changing updates if there were further language support. 
     221 
    52222 3. The global-ness of typeclass seems hard to reconcile with the idea of wanting to control export of record fields, so maybe this is unavoidable. 
    53  4. I'm not real kind of structural polymorphism anyway, I believe parametric and typeclass polymorphism are more principled. 
    54  5. Ya ok, but this can be spun as a pro: the fact that field update is in a library and not built-in means we can wait until the lens libraries settle down before hardcoding something into the language.  A record implementation that wants syntactic support for field updates will have to build in something anyway, so this is just flexibility to delay that building-in. 
     223 
     224 4. I'm not real fond of structural polymorphism anyway, I believe parametric and typeclass polymorphism are more principled.