February 2006 - Haskell-prime

Bang patterns, ~ patterns, and lazy let
by John Hughes 07 Feb '06

07 Feb '06

I just looked at the bang pattern proposal in more detail. To summarise: * Pattern-matching is presently strict against constructors, lazy against variables. * ~p matches p lazily; matching always succeeds, binding the variables in p to _|_ if matching p fails. * !p matches p strictly; matching always loops if the value matched is _|_, even if p is a variable or ~ pattern. Note that !~p is not the same as p (matching it can never fail, p itself is not matched strictly), but ~!p is the same as ~p. So far, so good--everything has a clean semantics and is easy to understand. Now for the warts: * Patterns on the left hand side of a let or where are implicitly preceded by ~, making matching in these contexts lazy by default. * ! on the left hand side of a let or where *has a different meaning to ! in a pattern* -- it means that the ~ that would have been implicitly inserted by the previous rule, is not inserted after all! This is not the same as banging the pattern with the implicit ~, because as I remarked above, !~p is not the same as p. This really, really smacks of committee design, doesn't it? Come on, it's a dog's breakfast! I've made clear before that I consider the FIRST rule above (that matching in let and where has an implicit ~) to be a wart already, but giving ! a second meaning to control whether or not the first wart is really applied is growing warts on warts! The one good thing to be said for this design is that it doesn't break existing code. But really--the design is unreasonably complex, and would just store up trouble for the future. Imagine trying to make a further extension to pattern matching next time Haskell is revised, without breaking code that relies on the warts on warts above! I would urge that either we stick with the present design, or, if bang patterns are added (which a lot speaks for), that the language be simplified at the same time so that patterns are matched in the same way everywhere, and BOTH warts above are excised. Some existing code would break, but in return the language would become simpler and more expressive. John

3 2

RE: MPTCs and functional dependencies
by Simon Peyton-Jones 07 Feb '06

07 Feb '06

I'm confident that it is premature to standardise functional dependencies at this stage, very useful though they are. If you doubt me, read the JFP journal submission that Martin Sulzmann and Peter Stuckey and I have been working on. http://research.microsoft.com/%7Esimonpj/papers/fd-chr Fundeps are very, very tricky. My own view is that associated types are a more promising way forward at the programming language level. They are a little less expressive than fundeps, I think, but a whole lot less tricky. But we don't have an implementation of them yet, so we can hardly standardise them! Multi-parameter type classes, yes. Functional dependencies, no. Simon | -----Original Message----- | From: haskell-prime-bounces(a)haskell.org [mailto:haskell-prime-bounces@haskell.org] On Behalf Of | Ross Paterson | Sent: 02 February 2006 11:25 | To: haskell-prime(a)haskell.org | Subject: MPTCs and functional dependencies | | On Thu, Feb 02, 2006 at 11:38:07AM +0100, John Hughes wrote: | > The problem with Haskell 98 is that it *lacks* features which | > have become absolutely essential to Haskell programmers today. Those | > features are what really *need* discussion and energy spent on them. | > | > [...] | > | > Multi-parameter classes with functional dependencies | > - used everywhere... for example in monad transformers... so | > *must* be included this time | > - omitted from Haskell 98 because "the right design" wasn't clear | > - it's still unclear! Functional dependencies *in some form* | > are essential, but associated types and datatypes look nicer | > in many ways! | > - is it too late, in practice, to replace fundeps by something | > else? How will we know? If we are to standardize on associated | > types instead, we need a major effort to *make sure* all | > important applications of fundeps can be represented. How will | > we organize that? | | I agree that MPTCs are much less useful (though not completely useless) | without something like FDs or associated types. But the specification | of FDs is far from clear: the system described in Mark's paper is quite | a bit weaker than what is implemented by GHC and (more shakily) by Hugs. | It seems that associated types aren't ready yet, but I don't think FDs | are either, accustomed as people are to them. | | I have another worry about MPTCs. They require require relaxations on | the form of instances (FlexibleInstances on the wiki), which in turn | require relaxations on contexts and thus deferred context reduction (see | FlexibleContexts). The result is that missing instances get reported | later than they do now. MPTCs are very useful and probably necessary, | but there is a cost. | | _______________________________________________ | Haskell-prime mailing list | Haskell-prime(a)haskell.org | http://haskell.org/mailman/listinfo/haskell-prime

9 10

Re: Restricted Data Types
by John Hughes 07 Feb '06

07 Feb '06

From: John Meacham <john(a)repetae.net> Subject: Re: Restricted Data Types however, what prevents the following from being _infered_ return Foo :: Moand m => m Foo so, we think we can specialize it to return Foo :: Set Foo however, we no longer have the constraint that Foo must be in Eq! Maybe I wasn't up-front enough about this in the paper: RDTs add a new form of constraint in contexts, wft t, meaning that type t is well-formed. While base types and type variables can be assumed to be well-formed, other types may only be used at all in the context of a suitable well-formedness constraint. That means that the Monad class is not allowed to declare return :: a -> m a because there's no guarantee that the type m a would be well-formed. The type declared for return has to become return :: wft (m a) => a -> m a i.e. when return is called, it has to be passed a dictionary proving that m a is well-formed. In the case of Set, that's an Eq a dictionary. In your example, the most general type of return Foo is (Monad m, wft (m Foo)) => m Foo, and when you instantiate m to Set, you're left with the contraint wft (Set Foo), which reduces to Eq Foo. The changes to the type system are that all typing rules have to add wft t constraints to the context, for every type t that appears in them. Fortunately most can be immediately discarded, since base types are always well-formed, and data type definitions imply constraint reduction rules that eliminate wft constraints unless the datatype is restricted. For example, wft [a] reduces to wft a, because lists place no restriction on their element type. Wft constraints on type *variables* can be discarded where the variables are generalised, *provided* the instantiation rule only permits variables to be instantiated at well-formed types. There's no need to write the type of reverse as wft a => [a] -> [a], if polymorphic type variables can only every be instantiated to well formed types. The only wft constraints that cannot be discarded are thus those where the type that must be well-formed is an application of a type constructor variable, such as wft (m a) in the type of return. That suggests that wft constraints ought not to be too common in real code, but they do crop up in monadic library code-- class Monad m where return :: wft (m a) => a -> m a (>>=) :: (wft (m a), wft (m b)) => m a -> (a -> m b) -> m b That's why, without some clever optimisation, RDTs will lead to massive extra dictionary passing (in implementations that use dictionaries). "It'll be just fine as long as you don't use monads" isn't really a good enough argument, is it?! John

2 1

Re: Bang patterns, ~ patterns, and lazy let
by John Hughes 07 Feb '06

07 Feb '06

From: Ross Paterson <ross(a)soi.city.ac.uk> John Hughes wrote: >> I would urge that either we stick with the present design, or, if bang >> patterns are added (which a lot speaks for), that the language be >> simplified at the same time so that patterns are matched in the same way >> everywhere, and BOTH warts above are excised. Some existing code would >> break, but in return the language would become simpler and more expressive. > > Would top-level bindings of constructor patterns and !x be evaluated when the module was loaded (or at compile time)? Yes. Nothing else makes sense, does it? If that's problematic (although I can't see why it would be), just forbid strict patterns at the top level of modules. Load time rather than compile-time, I think--otherwise the compiled code for a module could depend on the *code* of modules it imports, not just on their interfaces, which would be harmful for separate compilation. John

1 0

Re: Restricted data types
by John Hughes 07 Feb '06

07 Feb '06

On 2/5/06, Jim Apple <jbapple+haskell-prime(a)gmail.com> wrote: >> Have we considered Restricted Data Types? >> >> http://www.cs.chalmers.se/~rjmh/Papers/restricted-datatypes.ps > > Nice to see my old paper hasn't sunk without trace! As Taral pointed out, though, Restricted Data Types have not been implemented, and they can't be seriously considered for Haskell' until they have been. They are a fairly major extension, requiring changes to the way context reduction works, and introducing many new constraints to contexts. That said, the problem they address comes up again and again and again, so I think it would be worth making a serious attempt to solve it--but not necessarily for Haskell'. A few points. Perhaps the biggest disadvantage of Restricted Data Types from an implementation point of view is the need to pass a potentially large number of dictionaries to overloaded monadic functions, which in most cases will never be used. For jhc, this would not be a problem, of course--so perhaps jhc is the best setting to try RDT's out in. For dictionary passing implementations, I suggested compiling two versions of each affected function, one fast version without the RDT dictionaries for the common case, and the other with them for the general case. It's not clear how many functions would be affected, or how much code size would grow as a result. >From a language point of view, introducing well-formed-type constraints into contexts can make definitions overloaded that were formerly polymorphic, thus triggering the M-R and potentially causing type errors. But if the M-R were reformed, for example as Simon M suggested, so as not to distinguish between polymorphic and overloaded definitions, then this problem would go away. (Or rather, it would strike regardless of RDTs, so someone else would carry the blame!). Finally, I wrote my paper before fundeps came on the scene. Some of the contortions I went through in my simulation of RDTs could be avoided with the help of fundeps. The alternative solution I discuss at the end--parameterising classes and functions over contexts--would also benefit frlom fundeps. A Collection class could be defined something like this: class Collection c cxt | c -> cxt where empty :: cxt a => c a member :: cxt a => a -> c a -> Bool ... I still think it's nicer to associate cxt with c at the type definition of c, rather than in instance definitions of potentially many classes, but this alternative should be considered. How it would relate to associated types I can't imagine--associated contexts? Summary: it would be great to add RDTs to Haskell, but there's a lot of work to be done before they can be considered for the standard. John

1 0

Existential types: want better syntactic support (autoboxing?)
by Johannes Waldmann 07 Feb '06

07 Feb '06

It is standard practice to hide implementation details, in particular, not publishing the type of an object, but just the interfaces that its type implements. We can do this with existential types but the notation feels clumsy. See my message http://www.haskell.org//pipermail/haskell-cafe/2005-June/010516.html -- -- Johannes Waldmann -- Tel/Fax (0341) 3076 6479/80 -- ---- http://www.imn.htwk-leipzig.de/~waldmann/ -------

11 20

Representing Tuple types as products
by Thomas Davie 07 Feb '06

07 Feb '06

Here's a random idea that popped into my head. There have been a few discussions about unicode support in Haskell'. One of the particular places this is useful would appear to be type signatures, I was considering that it would be particularly neat to be able to represent tuples as cross products if the user so desired. As such: fst :: α × β → α would be equivalent to: fst :: (α, β) → α Just random thought for the day, what do people think? Bob

5 5

extending bang proposal Re: strict Haskell dialect
by Bulat Ziganshin 06 Feb '06

06 Feb '06

Hello Ketil, Monday, February 06, 2006, 4:06:35 PM, you wrote: >> foo :: !Int -> !Int KM> (Is the second ! actually meaningful?) yes! it means that the function is strict in its result - i.e. can't return undefined value when strict arguments are given. this sort of knowledge should help a compiler to "propagate" strictness and figure out the parts of program that can be compiled as strict code. really, i think ghc is able to figure functions with strict result just like it is able to figure strict function arguments KM> Personally, I think is much nicer than sprinkling seq's around, and KM> generally sufficient. However, there could perhaps be disambiguities? btw, it's just implemented in the GHC HEAD KM> Last time this came up, I think examples resembling these were brought KM> up: KM> foo :: [!a] -> ![a] -> a yes, i remember this SPJ's question :) "[!a]" means that list elements are strict, it's the same as defining new list type with strict elements and using it here. "![a]" means "strict list", it is the same as defining list with "next" field strict: data List1 a = Nil1 | List1 !a (List1 a) data List2 a = Nil2 | List2 a !(List2 a) data List3 a = Nil3 | List3 !a !(List3 a) the type List3 is a simple strict list, like in any strict programming language. foo :: [!a] -> ![a] -> ![!a] -> a translates to foo :: List1 a -> List2 a -> List3 a -> a KM> foo' :: Map !Int String -> Int -> String that means that keys in this map saved as strict values. for example, the following definition type Map a b = [(a,b)] will be instantiated to Map !Int String ==> [(!Int, String)] KM> Anyway, if a reasonable semantics can be formulated, I think KM> strictness type annotations would be a great, useful, and KM> relatively non-intrusive (AFAICT, entirely backwards compatible) KM> addtion to Haskell'. such proposal already exists and supported by implementing this in GHC HEAD -- Best regards, Bulat mailto:bulatz@HotPOP.com

2 2

Bang patterns
by Simon Peyton-Jones 06 Feb '06

06 Feb '06

Earlier on the Haskell' list, I proposed bang patterns as a way to make it more convenient for Haskell programmers to make their programs stricter. E.g. f (!x, y) = .... I've documented the proposal here http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/BangPatter ns I've implemented it in GHC, so you can try it out. Use -fbang-patterns to enable bang patterns. If you use -fglasgow-exts you get -fbang-patterns as well. If you don't want that, use -fglasgow-exts -fno-bang-patterns. I'd be interested to hear your experiences. (Committee members: do add notes to the Wiki page giving pros and cons.) Simon

2 2

RE: Priorities
by Simon Marlow 06 Feb '06

06 Feb '06

On 03 February 2006 16:03, John Goerzen wrote: > I know, of course, that Java green threads and Haskell forkIO threads > are called "threads", but I personally believe its misleading to call > it concurrency -- they're not doing more than one thing at a time. We use the terms "concurrency" and "parallelism" to mean two completely distinct concepts, as others have pointed out. Concurrency means structuring your program as multiple independent threads of control, which are independent of each other and can interact in non-deterministic ways. Parallelism means running computations simultaneously on multiple processors - you can run a concurrent program in parallel, but you can also use parallelism to speed up single-threaded programs. > Well, I must admit to being confused at the present state of things. > > Right now, we have forkIO, which seems, to me, like a fancy wrapper > around select or poll. It's very nice, really. > > I'm not clear, though, on how to integrate other C libraries that have > their own async I/O systems into all of this. (For instance, LDAP or > SQL libraries) We do have a nice story for all this, probably nicer than in any other language implementation you'll come across. GHC gives you both the performance from lightweight threads, combined with the ability to use OS-level concurrency for invoking FFI calls that might block, such as the SQL or LDAP libraries you refer to . In these cases you don't have to incorporate the library's file descriptors into one Giant Select, you just make a blocking call to the library. The runtime makes sure it happens in a different OS thread, so it doesn't block any of your Haskell threads. Lightweight threads by default, OS threads when needed. > The exact interaction between FFI, forkIO, forkOS, etc. is, to me, > extremely vague right now. It also seems much more complex than in > other languages, and perhaps varies from one Haskell implementation to > the next. There is only one Haskell implementation that really does concurrency. Hugs has cooperative concurrency, but that's pretty limited (I don't think it does I/O, for example). The story is more complex than in other languages, but I think it's largely a matter of documentation, the design has been very carefully thought out: http://www.haskell.org/~simonmar/papers/conc-ffi.pdf I'm glad you pointed out that you find the situation confusing, I'll definitely try to improve the documentation. Cheers, Simon

1 0