- Haskell-prime - Haskell.org

deeqSeq proposal
by Andy Gill 05 Apr '06

05 Apr '06

For the reasons talked about in previous posts, I'd like to propose a deepSeq for Haskell'. - It provides a mechanism to allow an effective, systematic tracking down of a class of space leaks. - It provides a mechanism to simply stomp on a class of space leaks. - It avoids the user having to explicitly declare instances for a homebrew deepSeq for every type in your program. - It has a declarative feel; this expression is hyper strict. - Is a specification of strictness. - It will open up various optimization opportunities, avoiding building thunks. (I dont talk about this more, but I'm happy to elaborate) - It can have an efficient implementation, or a simple (slow) implementation. (The fast implementation one can be used to stomp space leaks, the slow one can help find the same leaks.) What I would like to propose for Haskell' are four things: (Essential) Add a deepSeq function into Haskell' deepSeq :: a -> b -> b - Don't really care if its in a class or not; would prefer not for the reasons John Hughes talked about. - This would deepSeq all its children for regular constructors. - deepSeq would not indirect into IO or MVar. - functions would be evaluated to (W?)HNF. - IO, ST are functions under the hood. (Easy) Add a $!! function, and a strict function f $!! a = a `deepSeq` f a strict a = a `deepSeq` a (Nice) Add a !! notation, where we have ! in datatypes. data StrictList a = Cons (!!a) (!!StrictList a) | Nil (Perhaps) Add a way of making *all* the fields strict/hyperstrict. data !!StrictList a = .., We could also do this for ! -------------- Implementation: deepSeq (RAW_CONS <is_deep_seq'd_bit> ... fields ) = if <is_deep_seq'd_bit> == True then return /* hey, we've already deepSeq'd this */ else set <is_deep_seq'd_bit> to True. deepSeq (field_1) ... deepSeq (field_n) deepSEQ (REF/MVAR...) = return So we only deepSeq any specific constructor once! Sorta like lazy evaluation :-) We'd need to catch exceptions, unset the is_deep_seq'd_bit, so that any subsequent call of deepSeq would also have the option of raising the exception. So, - How easy is this to add to the compilers? It looks pretty simple to me, and would provide huge bang-for-buck for Galois. - Any alternatives to the key concern; stomping on space leaks. (This proposal is orthogonal to the seq/Class discussion) Andy Gill Galois

3 2

asynchronous exceptions (was: RE: Concurrency)
by Simon Marlow 05 Apr '06

05 Apr '06

I'm not sure whether asynchronous exceptions should be in Haskell'. I don't feel entirely comfortable about the "interruptible operations" facet of the design, and I'm hoping that STM can clean things up: after all, STM already gives you a much nicer way to program in an exception-safe way, as long as you aren't doing any real I/O. The fact that throwTo can interrupt a takeMVar, but can't interrupt a foreign call, even a concurrent one, is a bit strange. We have this odd situation in GHC right now where throwTo can interrupt threadDelay on Unix, but not on Windows because threadDelay maps directly to a foreign call to Sleep() on Windows. To fix this I have to implement the I/O manager thread on Windows (I should do this anyway, though). On 03 April 2006 07:38, John Meacham wrote: > however, in a preemptive one, it is less clear whether they may be > delivered right away or not and what the implementation costs are, as > threads arn't necessarily blocked at a point where they can happily > deal with an exception. Perhaps the yhc guys have thought about the > problem? In fact, GHC's SMP mode still doesn't implement throwTo, mainly because it's rather difficult and I need to put some serious thought into how to do it. > there are also a few questions we would want answered for the spec > > * do we require the thrower to 'block' until the signal is recieved? > (only relevant to pre-emptive implementations) GHC's throwTo does block until the exception is delivered. The main argument for doing it this way is that you only need an extra forkIO to get the other version. Another argument is that it gives you more guarantees: if two threads throwTo each other, only one will succeed. > * what happens if mutilple thrown exceptions "pile up" before the > catcher gets to them? They get delivered in some order (fairness probably applies in the same way to threads blocked on MVars). > * what happns to exceptions that fall off the end of threads, or the > main thread? (should be answered anyway) throwTo a thread that has completed is a no-op. > * promtness? how much work is the target allowed to do before it > "sees" the exception? pthreads allows an implementation to delay > processing an exception to a "cancellation point" do we want the > same thing in haskell? if not, how will this affect OS threaded > implementations? The only guarantee you can give is "the exception isn't delayed indefinitely, unless the target thread remains inside a block". Just like the fairness property for MVars. Cheers, Simon

4 3

RE: deeqSeq proposal
by Simon Peyton-Jones 05 Apr '06

05 Apr '06

| >> let xs' () = 1 : 2 : xs' () | >> let xs2 = xs' | >> | >> let xs = 1 : 2 : xs | >> | >> So deepSeq xs2 ==> _|_, but deepSeq xs ==> xs No, no. deepSeq of either should be _|_. That's easy to achieve, even with the "marking" idea. Simply do a depth-first walk, but mark the node *after* traversing all its children, not before. That way, if there's a cycle you'll diverge, as you should! But you still get the effect that deepSeq (deepSeq x) = deepSeq x (dynamically). Simon

1 0

RE: asynchronous exceptions (was: RE: Concurrency)
by Simon Marlow 05 Apr '06

05 Apr '06

On 05 April 2006 12:47, David Roundy wrote: > On Tue, Apr 04, 2006 at 01:33:39PM +0100, Simon Marlow wrote: >> The fact that throwTo can interrupt a takeMVar, but can't interrupt a >> foreign call, even a concurrent one, is a bit strange. We have this >> odd situation in GHC right now where throwTo can interrupt >> threadDelay on Unix, but not on Windows because threadDelay maps >> directly to a foreign call to Sleep() on Windows. To fix this I >> have to implement the I/O manager thread on Windows (I should do >> this anyway, though). [...] >> The only guarantee you can give is "the exception isn't delayed >> indefinitely, unless the target thread remains inside a block". Just >> like the fairness property for MVars. > > I think this is fine. There's no need for strong guarantees that > asynchronous exceptions are delivered soon or interrrupt any > particular external function calls, or even interrupt particular > standard library functions. At least to me, that's what makes them > asynchronous. In other words, I wouldn't mind cooperative > asynchronous function calls. Which is to say, that I don't see any > reason the standard IO library shouldn't be allowed (by the standard) > to use block in all its calls. Yes, maybe it's ok. The nice thing about the way block works right now is that it doesn't quite block all asynchronous exceptions, it actually turns them into synchronous exceptions which are much more tractable. For example, in GHC's IO library I couldn't face the prospect of scrutinising every line of code for exception-safety, so I just put a block around everything that modifies Handle state. This isn't nearly as bad as it sounds, because any operation that blocks inside an I/O operation is still interruptible, but because we know which operations those are, we can be prepared to handle the exceptions. In fact, since the operations that block are mostly the I/O operations themselves, we're already well prepared for handling exceptions there anyway. So it all works out nicely. Concurrency abstractions built from MVars suffer a bit from async-exception-safety. The right way is to build these abstractions using the exception-safe withMVar & modifyMVar family, but they impose an overhead. Fortunately STM is exactly the right solution here. Cheers, Simon

1 0

RE: important news: refocusing discussion
by Simon Marlow 05 Apr '06

05 Apr '06

On 24 March 2006 12:28, Ross Paterson wrote: > On Fri, Mar 24, 2006 at 11:30:57AM -0000, Simon Marlow wrote: >> So I believe the issue is mainly one of perspective. Until I wrote >> this email I hadn't thought of (4) and my preference was for (2), >> but now I quite like the idea of (4). We would include concurrency >> in Haskell', but provide a separate addendum that specifies how >> imlementations that don't provide concurrency should behave. One >> advantage of (4) over (3) is that we can unambiguously claim that >> Haskell' has concurrencey. > > And we can unambiguously state that there is only one Haskell' > implementation (though a second is on the way). > > Sure, concurrency is essential to many applications, and should be > precisely specified. But it is also irrelevant to a lot of uses of > Haskell (except for ensuring that one's libraries are also usable on > concurrent implementations, as JohnM said). A specification of the > language without concurrency would be at least as valuable (having > more implementations). Perspective, as you say -- most people agree > we need both -- but I think you're a bit too negative about the > smaller variant. This is just a difference of opinion, and probably won't be easily resolved. It comes down to whether you think Haskell' should be a language that is wide enough to include such applications as a web server, or whether it has to stop short of including concurrency because it's too hard to implement (and it's not always hard - the YHC guys managed it in a matter of days, but I do realise it would be hard in Hugs). I think it would be a mistake to relegate concurrency to an addendum; it is a central feature of the language, and in fact is one area where Haskell (strictly speaking GHC) is really beginning to demonstrate significant advantages over other languages. We should make the most of it. Cheers, Simon

7 7

RE: Concurrency
by Simon Marlow 05 Apr '06

05 Apr '06

On 04 April 2006 20:07, John Meacham wrote: > Here are a couple of uses. We need waiting routines for every > interesting event, they are darn useful, and they admit a very > optimized implementation. > > A C library which reads a file descriptor, calling threadWaitRead > beforehand and then the call is much more efficient than calling the > library directly. As long as you can guarantee not to be preempted between threadWaitRead and the foreign call, yes. > A consumer-producer set up, you don't want to read into core memory > the producers data until you are sure you have somewhere to write it > to, so you have a 'threadWaitWrite-read-write' loop. > > UI design, a common issue is displaying continuously updating > information on the screen. You communicate with the X11 server via a > pipe, so it is possible to just completely fill the X11 buffer with > drawing requests and get a backlog killing your apps responsibility. > also, by the time these backloged events actually get to the screeen > they may be out of date and your app quickly crashes and burns if your > incoming data rate exceeds the speed at which you can draw to the > screen. > > Concurrency admits a nice solution, you have your thread that > generates the interesting info, (say, reading data from a DSP), > continually updating a shared location. your drawing routine is in a > 'threadWaitWrite-readlocation-drawit' loop. notice that > threadWaitWrite is needed because otherwise you would be forced to > send outdated data to the screen if you couldn't separate what you > write from when you write it. > > A C call that uses a file, but expects some precondition to be set > before it can be run. One that I ran into is a curses library that > waited for user input, but wanted the screen to be cleared before it > could be run. clearing the screen right away would have left the user > sitting staring at a blank screen with no instructions until they > pressed a key, the right thing to do was to do a threadWaitRead, clear > the screen, then call the routine. Sure, there's no problem with having operations that just wait for events. We already have System.IO.hWaitForInput, suppose we added System.IO.hWaitForOutput. That satisfies your requirements for threadWaitRead/threadWaitWrite, right? The point is, I believe there's nothing special about these event-waiting functions. If you want to wait for several events, then you fork a thread for each one and send the results down a shared channel. The implementation might well do something clever to avoid needing one OS thread per waiting event, or it might not. I can believe there are situations where the programmer might want more direct access to an event model for efficiency reasons, but I don't believe that this is essential functionality that needs to be in Haskell'. Cheers, Simon PS. I don't think hWaitForInput should have the timeout argument.

1 0

Re: Edison RC3
by Bulat Ziganshin 05 Apr '06

05 Apr '06

Hello Robert, Wednesday, April 5, 2006, 3:50:41 AM, you wrote: > And one final meta-API question; what are your thoughts about portability in > general? I would like to support as many implementations as possible, but > I'm already relying on MPTC, fundeps and undecidable instances (which may or > may not be in H'), and I'm considering the following: > -- instances of Typeable/Data (listed as non-portable) > -- assertions (for checking preconditions) > -- newtype deriving > Anyway, I'm interested in your thoughts about how important portability is. according to my experience - one can't write real programs in H98. one of the reasons why H' was started is to define standard for writing such programs. on the current moment GHC and Hugs are close enough to that we should see in this standard. They supports MPTC, FD, Typeable, more flexible instances declarations, and i think that you can work with assertions via preprocessor. so i recommend you to use GHC+Hugs compatibility as the first goal but avoid using of features that they both support but there is no exact definition (such as undecidable instances), as i itself do. This allows you and your users to use two the best Haskell implementations - one for debugging, other for production code, and almost ensure that your code will be H' compatible or require minimal changes. about Typeable - i attached file from ghc sources that allows to define instances both for Hugs and GHC. you can see examples of it's use in base libraries. it works for me for ghc641 and hugs2005 about undecidable instances - hugs and ghc 6.5 contains more liberate rule for checking decidability and i hope that it will be included in the H', see details on the http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/FlexibleInsta… and last but not least ;) language extensions that we absolutely need to use will probably go into the standard. may be the library/apps authors that use some extensions should write about this on the appropriate H' proposals pages to let committee know? ps: may be, we can/should create page with the list of extensions that probably will go into the standard? or just adjust the corresponding fields in the existing table? such info would be very helpful for developers, imho. not anyone has enough time and willing to follow all of the H' discussions -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

1 0

'deriving Tree (Eq,Ord)'
by Bulat Ziganshin 05 Apr '06

05 Apr '06

Hello how about this old proposal? http://www.cse.unsw.edu.au/~dons/haskell-1990-2000/msg00727.html -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

6 9

Re: Concurrency
by oleg＠pobox.com 05 Apr '06

05 Apr '06

It would be really great if the concurrency portion of Haskell' did not outlaw light-weight threads implemented via delimited continuations (similar to those in the ZFS system). Such threads are cooperative: a thread runs until it requests service from a `supervisor' (yield() being one of such requests). The advantage of these threads is that they are lightweight, that the scheduler becomes expressible in the Haskell itself (and so each application can have its own scheduler, with or without priorities, with or without sophisticated resource-aware scheduling), and such threads have a natural transactional semantics. In the ZFS project threads can only do IO that is explicitly provided for them, and nothing else. Or, to be more precise, threads are statically prevented from any IO; they must request IO from the supervisor, which then decides if to satisfy the request, and when. Due to the natural 'copy-on-write' semantics, transactional memory becomes trivial; exceptions require no roll-back because no global state is modified unless the explicit commit is requested. Incidentally, the cooperative nature of lightweight threads does not preclude preemption: because all processing occurs in a monad, we can just as well make a monad that issues yield() after a certain number of 'binds'. Still, it will be nice if yield() per se were available, so users could chose the strategy for themselves. Interacting with foreign calls is indeed a problem: it is imperative that foreign calls be non-blocking. ZFS had to implement select(2) binding to get the non-blocking network IO. Fortunately, asynchronous behavior is possible for *any* operating system call, under generous assumptions (which hold for Linix and BSD systems, among others): Lazy Asynchronous I/O for Event-Driven Servers http://www.usenix.org/events/usenix04/tech/general/elmeleegy.html >From the abstract: ``We compare the performance of web servers implemented using LAIO to the performance obtained with previous interfaces. For workloads with an appreciable amount of disk I/O, LAIO performs substantially better than the alternatives, because it avoids blocking entirely. In one such case, the peak throughput with LAIO is 24% higher than the next best alternative. For in-memory workloads it performs comparably.'' It does seem to be a general consensus that events are faster than threads, but more difficult to program [just because first-class delimited continuations are not available for all languages, IMHO]. Here's a summary of HotOS X presentation that touches on the topic: ** Making Events Less Slippery with eel Ryan Cunningham and Eddie Kohler, University of California, Los Angeles HotOS X: Tenth Workshop on Hot Topics in operating systems. Santa Fe, New Mexico, June 12-15, 2005. Cited from the summaries in USENIX ;login: v.30, N5, p.67, 2005. http://www.usenix.org/publications/login/2005-10/openpdfs/hotos05.pdf ''This talk continued the old debate concerning threads and events. Events are fast but difficult to program. The speaker described eel, a programming tool designed to simplify programming with events. [Basically, a GUI for losers. Should use better languages!] eel uses program analysis techniques to improve programmability while preserving the event model, and provides the libeel event library, visualization, and debugging tools. Programming events is hard because it is difficult to understand the flow of the program and difficult to debug. eel's visualization tools make it easy to visualize the control flow, and the debugger allows you to step through each program flow separately; you follow the callbacks related to the same connection, so each flow of related events appears sequential. The speaker concluded that events don't need to be hard to program. You can use simple tools to extract program control flow and to help with visualization, verification, and debugging. Margo Seltzer pointed out that while eel helps clarify the event- based program after it's written, it does not appear to help with the actual writing of the program. The speaker responded that by allowing the programmer to visualize newly written code, eel does make writing easier. Margo was not convinced that using events is worth all this trouble. The speaker said that using events is preferable because they are much faster. Pei Cao responded that based on her experience of designing large software projects people use both threads and events. Events are a pain, so people use them only when performance is absolutely critical, which does not happen very often.''

1 0

Re: FD improvement, variable quantification & generalised propagation
by oleg＠pobox.com 05 Apr '06

05 Apr '06

Claus Reinke wrote: > I hadn't given that much thought before, because FDs are meant > to determine their range types, and there isn't much difference > between universal and existential quantification if there is only > one possible variable value, eg: > > (forall a in {Char}. T a) vs (exists a in {Char}. T a) That is quite an interesting issue, and the one on which different Haskell implementations differ. Let us consider the following code > {-# OPTIONS -fglasgow-exts #-} > {-# OPTIONS -fallow-undecidable-instances #-} > > module Foo where > > class C a b | a -> b, b -> a where > foo :: b -> Bool > > data E a = forall b. C a b => E b > data U a = U (forall b. C a b => b) We see that given the constraint "C a b", the type |a| unambiguously determines the type |b|, and vice versa. One may ask if the type |E a| provides any type abstraction over |b|, and if the type |U a| provides any generalization over |b|. Hugs (March 2005) and GHC 6.4.1 differ in their answers. > instance C a a where foo _ = True > > t1 () = E undefined > t1' = case t1 () of E x -> foo x > > t2 () = U undefined > t2' = case t2 () of U x -> foo x Hugs -98 accepts this code; both t1' and t2' evaluate to True. GHC accepts t1 but flags t1'. GHC does not accept even t2. If we have more specific instances, then Hugs too reject the program (alas, for a different reason: unresolved overloading). If we have more specific instances > instance C () () where foo _ = True > instance C [a] [a] where foo _ = False then t2 becomes acceptable to GHC. t1' and t2' still present the problem; the latter is due to the unresolved overloading, which we can fix > t2 () = U undefined > t2' = case t2 () of U x -> foo (tail x) and now this code works in GHC, and Hugs. In Hugs, even the following is accepted: > t1 () = E () > t1' () = case t1 () of E x -> foo x however the inferred type for t1' is Foo> :t t1' t1' :: C a ([b] -> Bool) => () -> Bool which I can't explain at all... The slight change in the class: > class C a b | a -> b, b -> a where > foo :: b -> a -> Bool (please note: only the signature of foo is changed; the constraints and FD remain the same) the more specific instances now work in Hugs > instance C () () where foo _ _ = True > instance C [a] [a] where foo _ _ = False > > t1 () = E () > t1' = case t1 () of E x -> foo x () > > t2 () = U undefined > t2' = case t2 () of U x -> foo x [] As before, GHC accepts both t2 and t2' (but not t1'). It would be really great if the writers of typeclass-based programs could expect consistent results... > he suggested that the whole problem may be an instance of > generalised propagation: > > Generalised Constraint Propagation Over the CLP Scheme, > by Thierry Le Provost and Mark Wallace. Journal of Logic > Programming 16, July 1993. Also [ECRC-92-1] > http://eclipse.crosscoreop.com:8080/eclipse/reports/ecrc_genprop.ps.gz Francois Pottier's ICFP'05 invited talk had essentially the same gist: constraint propagation. He considered different domain: GADT and related implication and disequality constraints (I think he mentioned that the results applied to FDs as well) http://para.inria.fr/~fpottier/slides/fpottier-2005-09-icfp.pdf

1 0