Re: [Haskell-cafe] Records (was Re: [Haskell] Improvements to GHC)
Chris Kuklewicz writes:
Would the record system describe at http://lambda-the-ultimate.org/node/view/1119 also be convertable "into System Fw, GHC's existing, strongly-typeed intermediate language." ?
Probably. Daan's current implementation uses MLF, which I believe is
system F implemented for ML.
(We're talking about the system in Daan Leijen's paper, "Extensible
Records With Scoped Labels". Good stuff.)
--
David Menendez
You can change the project and update operators in the HList library to behave in exactly this way. At the moment they are constrained to not allow multiple identical labels in records. If this kind of access is considered useful, I can add it to the HList distribution. Keean. David Menendez wrote:
Chris Kuklewicz writes:
Would the record system describe at http://lambda-the-ultimate.org/node/view/1119 also be convertable "into System Fw, GHC's existing, strongly-typeed intermediate language." ?
Probably. Daan's current implementation uses MLF, which I believe is system F implemented for ML.
(We're talking about the system in Daan Leijen's paper, "Extensible Records With Scoped Labels". Good stuff.)
Keean Schupke writes:
David Menendez wrote:
Chris Kuklewicz writes:
Would the record system describe at http://lambda-the-ultimate.org/node/view/1119 also be convertable "into System Fw, GHC's existing, strongly-typeed intermediate language." ?
Probably. Daan's current implementation uses MLF, which I believe is system F implemented for ML.
(We're talking about the system in Daan Leijen's paper, "Extensible Records With Scoped Labels". Good stuff.)
You can change the project and update operators in the HList library to behave in exactly this way. At the moment they are constrained to not allow multiple identical labels in records. If this kind of access is considered useful, I can add it to the HList distribution.
This is true. I've implemented a small subset of HList that's able to
emulate Daan's three record operators using only fundeps and undecidable
instances.
*Main> let r = foo .=. "Bar" .*. emptyRecord
*Main> r
Record{foo="Bar"}
*Main> let r2 = foo .=. () .*. r
*Main> r2
Record{foo=(),foo="Bar"}
*Main> r2 .!. foo
()
*Main> (r2 .-. foo) .!. foo
"Bar"
(This is actually *more* powerful than the system described in Daan's
paper, because labels are first class.)
While this is a testament to the power of Haskell's extended type-class
system, I'm not sure that it can replace a dedicated record system. In
his paper, Daan describes how to implement the records such that field
lookups take O(log n) or even O(1) time. HList can't do better than
O(n).
Of course, in the absence of a powerful record system, HList is the way
to go. Rather than decide on a new record system sight unseen, let's
implement them using HList and see how they feel.
--
David Menendez
David Menendez wrote:
Keean Schupke writes:
David Menendez wrote:
Chris Kuklewicz writes:
Would the record system describe at http://lambda-the-ultimate.org/node/view/1119 also be convertable "into System Fw, GHC's existing, strongly-typeed intermediate language." ?
Probably. Daan's current implementation uses MLF, which I believe is system F implemented for ML.
(We're talking about the system in Daan Leijen's paper, "Extensible Records With Scoped Labels". Good stuff.)
You can change the project and update operators in the HList library to behave in exactly this way. At the moment they are constrained to not allow multiple identical labels in records. If this kind of access is considered useful, I can add it to the HList distribution.
This is true. I've implemented a small subset of HList that's able to emulate Daan's three record operators using only fundeps and undecidable instances.
*Main> let r = foo .=. "Bar" .*. emptyRecord *Main> r Record{foo="Bar"} *Main> let r2 = foo .=. () .*. r *Main> r2 Record{foo=(),foo="Bar"} *Main> r2 .!. foo () *Main> (r2 .-. foo) .!. foo "Bar"
(This is actually *more* powerful than the system described in Daan's paper, because labels are first class.)
While this is a testament to the power of Haskell's extended type-class system, I'm not sure that it can replace a dedicated record system. In his paper, Daan describes how to implement the records such that field lookups take O(log n) or even O(1) time. HList can't do better than O(n).
Of course, in the absence of a powerful record system, HList is the way to go. Rather than decide on a new record system sight unseen, let's implement them using HList and see how they feel.E
Exactly! I like the idea of being able to construct and modify the semantics of a record system (and with the stuff in the OOHaskell paper you can play with Object systems in the same way). The important point with HLists is not that record syntax should not be added to Haskell, but that we can translate it to the existing type system with no conflicts. (ie the type system does not need to be extended there just needs to be some syntax, with an optimised implementation) HList can do O(log n) by the way, if the labels have order, you can implement a binary search tree of labels (Of course all the accessor functions would need to be rewritten). I wonder if some syntactic support for label creation would make things nicer. Actually one really useful change I would like would be to define type class functions over all tuples, that way you could write O(1) accessor functions on tuples using peano number indexes. class TupleIdx u i t | u i -> t where idx :: u -> i -> t instance (a,b) HNil a where (a,_) _ = a instance (a,b) (HSucc HNil) b where (_,b) _ = b instance (a,b,c) HNil a where (a,_,_) = a instance (a,b,c) (HSucc HNil) b where (_,b,_) = b instance (a,b,c) (HSucc (HSucc HNil)) c where (_,_,c) = c etc... However I haven't thought very hard about how to represent the complete (infinite) set of instances, but using this you can write products of tuples, and create records with O(1) access times from a pair of tuples. Keean
Keean Schupke writes:
HList can do O(log n) by the way, if the labels have order, you can implement a binary search tree of labels (Of course all the accessor functions would need to be rewritten).
The idea of writing a type-level balanced binary search tree fills me
with an uncertain mixture of excitement and dread. Particularly if you
want to be able to compare records for equality.
--
David Menendez
David Menendez wrote:
Keean Schupke writes:
HList can do O(log n) by the way, if the labels have order, you can implement a binary search tree of labels (Of course all the accessor functions would need to be rewritten).
The idea of writing a type-level balanced binary search tree fills me with an uncertain mixture of excitement and dread. Particularly if you want to be able to compare records for equality.
Hmm... You have to write and define what you mean by equality for normal HList records anyway. As you need to ignore the order of elements the equality test is effectively: a == b if (a `subset` b) and (b `subset` a) The test for "a subset b" tests if each element in a exists in b. With an ordered tree, the labels must be in the same order, so the equality just has to compare elements is a consistant (say pre-order) way. In the end HList records were written as they are for clarity in the paper, and not really as a number-crunching implementation. I find them fast enough for database work, where the records represent the query (in terms of projections) and the result table in a type safe way... Infact my simple DB library goes quite a way beyond what HaskellDB can do, mainy due to the complex type-mechanics being hidden inside the HList/record library. Keean.
participants (2)
-
David Menendez -
Keean Schupke