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.