- Haskell-prime - Haskell.org

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

RE: Priorities
by Simon Marlow 06 Feb '06

06 Feb '06

On 05 February 2006 00:21, Benjamin Franksen wrote: > On Friday 03 February 2006 08:52, Tomasz Zielonka wrote: >> On Thu, Feb 02, 2006 at 01:05:57PM +0000, Ross Paterson wrote: >>> Personally, I'm not sure about caseless underscore, concurrency, >>> natural numbers and parallel list comprehensions. >> >> There is one more reason to leave concurrency out of the standard. >> >> Some experts (like Hans Boehm) argue, that concurrency can't be >> added to the language as a library. >> http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf >> >> This is true for many imperative programming languages. Haskell >> seems to be an exception: >> >> http://www.haskell.org//pipermail/glasgow-haskell-users/2005-December >> /009417.html >> >> We don't have any problems with ensuring good cooperation between >> mutable variables and concurrency synchronisation primitives, because >> the language doesn't have mutable variables, they are delivered in >> the concurrency library - the variables _are_ the synchronisation >> primitives. > > What about IORefs? The interaction between concurrency and IORefs was recently discussed on the ghc-users list: http://www.haskell.org//pipermail/glasgow-haskell-users/2005-December/00 9389.html Cheers, Simon

1 0

Re[2]: [Haskell-cafe] Why is $ right associative instead of left associative?
by Bulat Ziganshin 06 Feb '06

06 Feb '06

Hello Henning, Monday, February 06, 2006, 4:12:44 PM, you wrote: >> In my opinion all the special syntactic sugar for lists should go >> away. I don't think lists are special enough to motivate it. HT> Fine, someone shares my attitude towards the list sugar. Nevertheless, do HT> you mean with 'no sugar for lists' also no infix operator for list HT> construction? I would still like an operator of low precedence for list HT> construction for writing e.g. (1,'a"):(2,'b'):[]. i prefer to have ":" and "[]" as general collection constructors: class Collection c a where [] :: c a -- creates empty collection (:) :: a -> c a -> c a -- adds value to the head of collection and having "default rules" that instatiates this collection type to list if there is no type signatures and other information what allows to find proper type of collection constructed this way - just like the "default Int" language construct defaults all untyped numeric constants to Int -- Best regards, Bulat mailto:bulatz@HotPOP.com

1 0