On Wed, Mar 01, 2006 at 11:00:41AM +0000, Malcolm Wallace wrote:

Thus, although I agree that none is ready for inclusion in Haskell-prime, I think we do need some mechanism for experimental records to be tried out in real Haskell implementations before the Haskell-double-prime committee starts its work.

Perhaps, taking the extensions-layering idea, we could say that the current named-fields are encapsulated as an "extension that is part of the standard". Implementations could then introduce a flag to switch off this particular extension (current records) in conjunction with flags to switch on experimental replacements. This would give a certain flexibility for users to play with different systems, and the breaking of compatibility would be explicitly notated, either by the build options, or using a proposal like ticket #94.

My suggestion is that we separate out everything from the Report to do with named-field records into something like a self-contained addendum. Whilst still an official part of the language standard, it might also be marked as a possibility for future removal. This would make it clear what parts of the language could be changed (or re-used without conflict) in an alternative records system.

Sounds like a good idea to me, if it can be done. We might want to do the same thing with FDs (assuming we come up with a form good enough for Haskell'). There will be a question of how contagious these extensions are, e.g. am I using extension X if I import a module that uses it?

On Saturday 04 March 2006 19:35, Claus Reinke wrote:

a more promising approach would be to specify the user-level features of the current system, then to show at least two translations: one for the current desugaring, and a second one to demonstrate at least one implementation of those features in an alternative record system.

the point of that exercise would be to figure out which features of the current user-level view of labelled fields would make a later transition difficult, and to mark them as deprecated or to remove them now. in other words, the "reference" translation should not be to the most powerful record system imagined so far, but to a fairly simple one, which all "better" record systems ought to be able to mimic.

my current favourite for such a simple alternative record system would be Daan Leijen's "Extensible records with scoped labels" (TFP2005): http://www.cs.uu.nl/~daan/pubs.html

Yes. Daan Leijen's record system is the best of all the ones I have read about, not least because of its simplicity.

ps. the Curry folks are looking into adding labelled fields, and seem to have decided to go for a trial implementation of Daan's system before making any decisions: http://www.informatik.uni-kiel.de/~curry/listarchive/0406.html

I would very much like to have this. I wouldn't mind if it were qualified as an experimental extension, etc.. If not in Haskell' then maybe at least in some future ghc version? Ben

Can it be implemented efficiently? Cale Gibbard wrote:

On 04/03/06, Benjamin Franksen wrote:

...

On Saturday 04 March 2006 19:35, Claus Reinke wrote:

...

my current favourite for such a simple alternative record system would be Daan Leijen's "Extensible records with scoped labels" (TFP2005): http://www.cs.uu.nl/~daan/pubs.html Yes. Daan Leijen's record system is the best of all the ones I have read about, not least because of its simplicity.

I just looked at this, and it made me wonder why we all haven't jumped on it. It looks pretty much ideal -- are there any known problems with it? It has pretty much all the operations that you'd want in an extensible record system, there are no lacks predicates to worry about, type inference is complete and sound (and there are constructive proofs available of this), and it doesn't look like it should be all that difficult to implement (the paper even gives suggestions as to possible efficient implementations). What are we searching for?

- Cale _______________________________________________ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime

Yes, I've read the article too. And I really like the record system. But an off-hand remark like that doesn't convince me. Daan, what's your opinion? -- Lennart Jim Apple wrote:

On 3/6/06, Lennart Augustsson wrote:

...

Can it be implemented efficiently?

Section 8, p. 8: "This leads to a simple compilation scheme that gives constant access to labels, but avoids the many runtime parameters for extension. The extension operation is done dynamically but since it is O(n) anyway, we expect that the runtime penalty is negligible."

Jim _______________________________________________ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime

interesting. it always seems that I get more responses if I argue against my own interests?-) anyway: - if you want explicitly declared, non-extensible records, you can use data type variants to tag anonymous records with fixed sets of labels (so anonymous records accomodate both user groups) - if you want type class interfaces that hide representation, will they be any easier to implement on top of labelled fields? it was investigation of this issue that led me away from TREX (the type of extension there forces you to name labels in the type, and type classes force you to make types more explicit than needed), and to approaches based on first-class labels - these questions, and more like them (eg., how to tag polymorphic components?), should be addressed when preparing labelled fields for replacement, as per Malcolm's suggestion; if you define a user-level view of records that can be implemented by either labelled fields or extensible records, then you have to account for typical usage patterns as well - if the committee follows Malcolm's suggestion, with my comments, implementations could, at some point, provide an implementation of records using Daan's system as an alternative to the current implementation.; it is possible that, in the process of defining the alternative translation into Daan's system, the committee finds that there is no point in keeping the old system around - in case you hadn't noticed: the Data.Record.hs attached to the first-class labels ticket does implement scoped labels in current Haskell+ (only ghc at the moment, I'm afraid, which is one reason why I'm after more coherence between implementations). it does not have Daan's simple types, because Haskell doesn't give me a commutative-associative type constructor, and I have to implement what would otherwise be a type-system extension via type classes (hence predicates in types). but for some of you, that's what you ask for anyway, and you do get record concatenation as a bonus;-) - once upon a time, there was paper after paper on optimizing pattern matching. but, in these days of heavy type-class programming, I could only name a single paper on optimizing type-classes. I remember one of the first talks on HLists, where the speaker said something like "advanced Haskell compilers will eliminate this type-class overhead statically" and the Haskell compiler implementers in the audience replied "what Haskell compilers? ours won't!". what about using the static properties of HLists, Data.Record, nested tuples, and so on, for generating constant time access, etc? any takers?-) cheers, claus

Hello Claus, Monday, March 6, 2006, 2:35:04 PM, you wrote:

...

also, while i like dynamic records for some types of tasks, i think that the "spirit" of Haskell in whole is to give explicit definitions of all types used and in this respect this type extension in not on "main way".

CR> record extension is the basis for record concatenation, which is CR> the basis for composing programs that use records. for instance, CR> if you have two attribute grammars that compute two sets of CR> attributes and you want to compose them into a single grammar, CR> you run into troubles. (dual arguments for extensible variants, CR> be it for exception types, or for extensible grammars that cover CR> haskell+extensions without having to specify and maintain two CR> separate grammars). and the concept of partial type specifications CR> is not uncommon in Haskell (polymorphism, type classes). (sorry for late answer) this again should be maintained in "Haskell way", i.e. with static type declarations: data Pizza = ... data Cola = ... type PizzaWithCola = Pizza+Cola weight :: PizzaWithCola -> Double weight pc = pizzaWeight pc + colaWeight pc pizzaWeight :: Pizza -> Double colaWeight :: Cola -> Double it is one more remainder of what we need OOP-like features such as data fields inheritance. O'Haskell has something in this area, although afair it doesn't support the multiple inheritance -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

...

my own opinion is that this scheme is like classes - they can be resolved at compile time in most real cases but noone do it because code will be too large. if some function can accept any records which has field 'a' then to use this function on records of different types we need either to do specialization or use scheme with non-constant access time

for those who haven't seen it, the following paper explored the former possibility with good success (at a time when type classes where still somewhat simpler:): Dictionary-free Overloading by Partial Evaluation Mark P. Jones, ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, Orlando, Florida, June 1994. http://www.cse.ogi.edu/~mpj/pubs/pepm94.html cheers, claus

Efficient implementations are discussed in the paper. It looks simple enough complexity-wise at compile time. I'm not 100% sure, but at a glance, I don't see anything here which looks like it should be very complex. As for the actual runtime semantics, apart from using association lists (linear selection, constant extension) or labelled vectors (log selection, linear extension), records may be implemented as plain unlabelled vectors (constant selection, linear extension), provided that an additional extension predicate is used in the type system, which can always be inferred and so may be hidden from the user completely. Given that one would expect record selection to be very common, this last option looks quite attractive. Another nice aspect is that we'd get automatic labelled variant types almost for free from the same machinery. - Cale On 06/03/06, Lennart Augustsson wrote:

Can it be implemented efficiently?

Cale Gibbard wrote:

...

On 04/03/06, Benjamin Franksen wrote:

...

On Saturday 04 March 2006 19:35, Claus Reinke wrote:

...

my current favourite for such a simple alternative record system would be Daan Leijen's "Extensible records with scoped labels" (TFP2005): http://www.cs.uu.nl/~daan/pubs.html Yes. Daan Leijen's record system is the best of all the ones I have read about, not least because of its simplicity.

I just looked at this, and it made me wonder why we all haven't jumped on it. It looks pretty much ideal -- are there any known problems with it? It has pretty much all the operations that you'd want in an extensible record system, there are no lacks predicates to worry about, type inference is complete and sound (and there are constructive proofs available of this), and it doesn't look like it should be all that difficult to implement (the paper even gives suggestions as to possible efficient implementations). What are we searching for?

- Cale _______________________________________________ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime

I have similar concerns. All of the record proposals I have seen don't really seem to subsume the current haskell record system, the task is different, anonymous records feel like they fill a similar niche to anonymous tuples, and just like we don't declare everything as newtype Foo = Foo (Int,Char,Either Bar Baz) it would seem odd that the only way to get named fields is to do the same thing but with records. not to say that the record proposals won't be useful in their own right, but I wouldn't want too see them necessarily replace labeled fields. it would also be unfortunate if the choice to use the (often cleaner) labeled fields implied a run-time and change in representation, one shouldn't have to make decisions like that. It feels to me that anonymous records should look more like the other anonymous(ish) type haskell provides, tuples. so the following syntax feels more natural (x = 3,y = 4) (x=3 | r) where (perhaps) (x,y,z) is shorthand for (t1 = x,t2 = y,t3 = z) this would also have the nice advantage that it is syntaxwise more backwards compatable, since labeled fields require a constructor argument to appear before the {}'s but tuples already don't. (and presumably a new record system wouldn't) I think an issue is that we call the current system records, so we expect them to work like other languages records, when in actuality, they are just labeled fields on standard haskell datatypes, but since that is true, we get all the power of standard haskell datatypes such as strict fields, summation types, the ability to declare instances and lots of typesafety. Haskell currenty just doesn't have a record system, adding one shouldn't get rid of the unrelated and very useful labeled fields feature :) John -- John Meacham - ⑆repetae.net⑆john⑈

On 06/03/06, Johannes Waldmann wrote:

With respect to the discussion on records, let me throw in my usual warning: all of this seems overly obsessed with concrete representations of data types.

We already have mechanisms for abstraction. There's a gap in our ability to form certain concrete representations we might want. This paper simply describes how to add those representations to the language in a nice way.

The representation should not be exposed in the first place: you don't want to access it (=> make all fields private) you don't want to extend it (=> implementation inheritance is bad, interface inheritance is good.) (read e. g. Introduction to Design Patterns by Gamma et al.)

You think it is a win to be able to write a function that takes "everything that has a foo :: Foo component"? I think it is not, since it is not robust design. It will only take records, and components have to be components. What if you later change the type's representation from a record to something else? If you change the component to a function? If you want a reliable notion of "everything that has a foo :: Foo", then you need to declare an interface (erm, one parameter type class).

Well, changing data representations is always inflexible. This isn't a new problem, and as you mentioned, you can still fix it with the use of typeclasses.

My point is that the OO community has learned all this stuff the hard way (from software problems arising from naive use of objects and inheritance), and it has taken them years, if not decades, and now it looks as if we are going to joyfully repeat this whole process.

Large product types normally indicate an awkward design, yes, but they're still implicit in many real-world interfaces, and it can be quite difficult to deal with them. This gives nice ways to break them up and work with them where they naturally occur.

An important selling point of the records proposal seems to be that you don't have to declare a type name for a record type. While I don't buy this whole idea (we have a declarative programming language but we want to avoid (type) declarations?) I see a concrete problem: what if you want to make such a nameless type an instance of some type class? Then we get all sorts of overlappings.

Well, I don't know about that. You don't have to declare a type name simply because all the types here already exist. You can still newtype them. However, not all record types are polymorphic. Declaring instances for completely specified rows would not be an issue. It's not clear to me that having instances for polymorphic records would be too much of an issue either. Yes, it would be easy to get overlaps, but not much more so than with existing polymorphic types. If there's more than one polymorphic instance, then of course you get overlap, because you can construct a record type with the union of the labels from the two instances. However are multiple row-polymorphic instances even needed? Due to the problem that records could very well satisfy both predicates in any situation like that, if you needed multiple instances, it would be better to newtype as usual.

So with respect to the original post (see the subject of this email) I tend to agree: leave records as they are. Of course they are problematic, but the main reason is not missing extensibility.

Well, the issue is just that Haskell does not actually have a record system. It has algebraic types, and while those can emulate certain aspects of records, they are not the same thing. The current "record syntax" is just syntax sugar for labelling the fields of a product in an algebraic type. It's nice syntax sugar, and I wouldn't want to get rid of it. (Though it could perhaps do with a renaming :)

As I see it, the problem is that the named component notation was added late and still allows to access the earlier positional notation, and the component names are in the (module-global) namespace.

The problem is that people see "record syntax" and think that somehow what they're declaring is any different from an ordinary product. The syntax gives you a little more capacity for dealing with more fields, and a little bit of future proofing, but not much more, and really it's the same thing, as the ability to use the positional notation indicates. Even with syntax sugar, using large product types in current Haskell is poor design. I'll illustrate one of the main reasons for this, and how extensible records can help fix that problem: Suppose that A, B, and C are types and that we have: data T = T {x :: A, y :: B, z :: C} which we're trying to use to simulate a record type. Then any function f :: T -> T has the ability to read and depend on all the components of the T which it is working with. There are many cases where this is completely inappropriate, but restricting access to one or more of the components is difficult. We'd need to define a new typeclass with get/set functions, and use that instead. Doing this sort of thing for every one of the fields of every product one uses is obviously not a good solution. On the other hand, a function: f :: {x :: A, y :: B | r} -> {x :: A, y :: B | r} obviously can only depend and act on the x and y components, and is not allowed to touch z at all. Sure, you might perhaps say that there's too much polymorphism there, but this usually isn't an issue, and there are still newtypes to tag things and ensure that they don't get into the wrong parts of the program. Record types would also be permitted as members of algebraic data types. More flexible systems than just using products as records are possible using typeclasses with label types like HList, but these generally involve quite a lot of typeclass hackery which, while it's nice to see that it can be done, at some point begins to feel like an abuse of the system, when one could do a better treatment at the compiler level. Such systems still wouldn't have properties as nice as the record system in the paper. (There is no provision for associative or commutative data/type constructors.) A related issue is that these tend to be closer in performance to association lists, which means that while extension is fast, record selection is linear time.

This would be more tolerable if we had ad-hoc overloading. Since we haven't, I'm now basically putting each data declaration in a separate module and import these qualified. (This simulates the "per-type" namespace for components.)

I think that ad-hoc overloading would be much more intolerable. In some cases the design you describe (separating a data type into a module) is appropriate, but I wouldn't hold myself to it. Usually I'd only use that if I planned to hide the constructors. A lot of the time, field labels can be renamed such that they don't overlap. Inventing new names is not hard work. (You can just put part or all of the type name in the labels, and you get basically the same effect as the module system gives you.) - Cale