April 2006 - Haskell-prime

Re: deeqSeq proposal
by Fergus Henderson 06 Apr '06

06 Apr '06

On 05-Apr-2006, Ben Rudiak-Gould <Benjamin.Rudiak-Gould(a)cl.cam.ac.uk> wrote: > Andy Gill wrote: > >- [various reasons for deepSeq] > You left out the one that most interests me: ensuring that there are no > exceptions hiding inside a data structure. Yes, that's important for fault isolation... see below. On 03-Apr-2006, Andy Gill <andy(a)galois.com> wrote: > > - Fergus Henderson used deeqSeq in our Cryptol to FPGA compiler, between > each pass, to make sure that we could assess which pass was taking > what time. Actually that wasn't the only reason why we needed deepSeq. The other reason, at least as important, was fault isolation. Like most compilers, the Cryptol to FPGA compiler consists of a number of of separate compilation phases. When a problem in our compiler such as an exception, heap or stack exhaustion, or an infinite loop occurs, it is very helpful to be able to know in which phase that error occurred. With lazy evaluation, this is tricky, since the execution of all the different phases will be interleaved. Any debugging messages produced by "trace" from the different stages also get interleaved. The Cryptol to FPGA compiler will (in verbose mode) print out a message when it starts each compilation stage. We use deepSeq to ensure that each stage has been fully evaluated before proceeding on to the next stage. This allows us to isolate faults to a particular compilation stage. I also used hyperSeq in previous Haskell programs before I joined Galois. I've found the need for this to be quite common... -- Fergus J. Henderson | "I have always known that the pursuit Galois Connections, Inc. | of excellence is a lethal habit" Phone: +1 503 626 6616 | -- the last words of T. S. Garp.

1 0

RE: deeqSeq proposal
by Simon Marlow 06 Apr '06

06 Apr '06

On 05 April 2006 21:02, Ben Rudiak-Gould wrote: > Andy Gill wrote: >> - [various reasons for deepSeq] > > You left out the one that most interests me: ensuring that there are > no exceptions hiding inside a data structure. > >> deepSeq :: a -> b -> b > > This ties demand for the (fully evaluated) normal form of an > expression to demand for the WHNF of a different expression, which is > a bit weird. I think it's cleaner for the primitive to be your > "strict", which ties demand for the normal form of an expression to > demand for the WHNF of the same expression. In fact I'd argue that > "deepSeq" should not be provided at all (though of course it can be > defined by the user). The analogy with seq is a bit > misleading---deepSeq is a lot less symmetric than seq. The > expressions (x `deepSeq` y `deepSeq` z) and (strict x `seq` strict y > `seq` z) are equivalent, but only the latter makes it clear that z > doesn't get fully evaluated. Agreed - that pinpoints something that seemed a little strange to me too. strict should be the primitive; or maybe strict renamed to deepSeq. Cheers, Simon

1 0

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