- Haskell-Cafe - Haskell.org

RE: [Haskell-cafe] readEitherChan
by Simon Marlow 26 Jun '04

26 Jun '04

On 24 June 2004 21:24, S. Alexander Jacobson wrote: > Cool! Why does it have an efficiency problem? Because it does busy-waiting. > And I would also observe that this solution > doesn't work for readEitherChan because there is > no tryReadChan. The naive tryReadChan > > tryReadChan chan = if isEmptyChan chan then return Nothing else > return $ readChan chan > > leaves you vulnerable to race conditions. > > It looks like we have now have two very similar > functions that, because they need the concrete > representation, need to be added in the library: > tryReadChan and tryReadSampleVar. > > Is there a systemic reason why these two very > similar functions are absent? There is no point > in my trying to add them if there is some *in > principle* difficulty. There's no fundamental difficulty that I'm aware of. The lack of these functions is probably down to historical reasons: tryTakeMVar and tryPutMVar are recent additions to the old MVar interface. > The concurrent paper seems > to indicate that there is something fundamentally > suspect about a choice operator as a primitive. > Is that issue related? The argument is based on the difficulty of implementing choice in a multithreaded or distributed setting, and the fact that simplifications to make the implementation easier tend to interfere with abstraction. It seems to me that with MVars you can implement pretty much any abstraction you need, including choice, and it's not clear that there would be any advantage to providing any more primitives. That's based on my experience so far, anyway - I know there are people out there that have made rather more heavy use of MVars than I have (eg. George Russell). > Also, you wouldn't need these functions if > Haskell's concurency model was defined to be > non-preemptive. How come forkIO was not > specifically defined to be non-preemptive (with > forkOS dependent on the local OS native threading > model)? So threads forked by forkIO would be non-preemptive with respect to what? Other threads forked by forkIO, or forkOS? forkOS is a very recent addition, BTW. Its primary purpose is to make a "bound" thread, to give the programmer a handle on which OS thread is used to make foreign calls. See this paper we submitted to the Haskell Workshop this year: http://www.haskell.org/~simonmar/papers/conc-ffi.ps.gz Hope that sheds some light. Cheers, Simon

2 1

RE: [Haskell-cafe] Haskell and concurrency
by Simon Marlow 26 Jun '04

26 Jun '04

On 25 June 2004 11:52, Graham Klyne wrote: > Anyway, I was wondering if any of the work on concurrent Haskell or > concurrent functional programming addresses similar systems or ideas, > in which implementation/hardware concurrency is decoupled from > application concurrency requirements, and particularly with a view to > applications requiring very low-overhead fine-grained concurrency? Concurrent Haskell is designed to provide exactly the kind of lightweight concurrency you're after. It won't be as quick as a custom application-specific threading model in the way you describe, but it's a *lot* faster than using one OS-thread for each thread in your system. And if you find it to be still too slow for your application, we know of several ways to speed it up... Cheers, Simon

2 1

RE: [Haskell-cafe] how to get started: a text application
by Bayley, Alistair 25 Jun '04

25 Jun '04

> From: Max Ischenko [mailto:max@ucmg.com.ua] > > Well, yes. In Markdown, like in most other "rich-text" > formats symbols are overloaded a lot. After all, it has to > constrain itself to "plain text". > > I'm going to try a "two-stage tokenization" (not sure how to > name this correctly). Basically, first I'd split the raw text > into "symbols" (like space, char, digit, left-bracket) and > then turn these symbols into tokens (like paragraph, > reference, start bold text, end bold text, etc.) Markdown looks a lot like Wiki source to me i.e. it looks like the text source for a Wiki page. It seems to serve the same purpose i.e. well-formatted plain text intended for conversion to HTML. Many (most?) Wiki engines use straightforward regex substitution to convert the text source into HTML, rather than implement a lexer/parser/pretty-printer combination. Obviously this makes for a fairly simple implementation. Mind you, some of the regex's are quite complex... See, for example: Source for Moin-moin, which runs the Haskell wiki: http://cvs.sf.net/viewcvs.py/moin/MoinMoin/parser/wiki.py?view=markup Original c2.com wiki (actual source a bit hard to find): http://www.c2.com/cgi/wiki?TextFormattingRegularExpressions ... which leads to: http://www.c2.com/cgi/wiki?TextFormattingRegularExpressionsDiscussion http://www.c2.com/cgi/wiki?AlternativesToRegularExpressions ----------------------------------------- ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************

3 3

Haskell and concurrency
by Graham Klyne 25 Jun '04

25 Jun '04

[Reminiscing mode] Recent discussions about Haskell concurrency remind me of a design I attempted some years ago for a real-time web content analyzer proxy (the sort of thing that companies would deploy to prevent their employees from downloading viruses from the web, etc.). The design was based on my (imperfect) understanding of lazy functional languages and their implementation (with some help from, SPJ's book), in particular using a graph-reduction model to evaluate a function like isSafe :: [octet] -> Bool The intent was that there could be an arbitrary and potentially very large number of concurrent web accesses passing through the proxy, so a thread-per-access could be unacceptably expensive, especially when each thread would most of the time be waiting for data. The advantage that I saw in the graph-reduction approach was that the current state of each evaluation would be entirely in the current expression graph, and there would be no per-transaction overhead other than the essential state information. The graph-reduction engine itself would have a number of worker threads, each of which would perform any graph reductions for which available incoming data was available -- a kind of demand-and-availability driven evaluation model. (The design was too ambitious to be implemented in the actual product, though it did spawn a company joke about Schonfinkel's device, and I understand that a number of ideas did eventually find their way into the implementation over time, but that's another story.) Anyway, I was wondering if any of the work on concurrent Haskell or concurrent functional programming addresses similar systems or ideas, in which implementation/hardware concurrency is decoupled from application concurrency requirements, and particularly with a view to applications requiring very low-overhead fine-grained concurrency? #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

how to get started: a text application
by Max Ischenko 25 Jun '04

25 Jun '04

Hi all, I'm going to try to implement a version of Markdown tool[1] in Haskell. The application is rather simple: take a text file with some (simple) mark-up embedded in it and turn it into another text file, this time with XHTML markup. I need some guidelines on how to get started. I'll have to struggle with both the language itself (as I am a newcomer) plus with libraries that I may need. If I to do this in some convenient language, like Python, I'd use a lexer to parse the input, a state machine to build some internal representation and some serializer to write this into XHTML. Which approaches could you suggest for that kind of application in Haskell? I'd especially glad to hear about some "idiomatic" or "native" ways to solve the problem. I've made a quick search and found tools like Parsec, HaXML, Happy and WASH/HTML. Not sure which ones I'll need. [1] - http://daringfireball.net/projects/markdown/ TIA, max.

2 3

RE: [Haskell-cafe] readEitherChan
by Simon Marlow 25 Jun '04

25 Jun '04

On 19 June 2004 03:06, Thomas Hallgren wrote: > Tomasz Zielonka wrote: > >> On Tue, Jun 15, 2004 at 06:29:59PM -0400, S. Alexander Jacobson >> wrote: >> >> >>> readEitherChan::Chan a -> Chan b -> Either a b >>> >>> eitherChan a b left right = readEitherChan a b >>= either left >>> right >>> >>> >> ... I think it would be safer to create once new Chan (Either a b), >> and then read from it. >> >> createEitherChan :: Chan a -> Chan b -> IO (Chan (Either a b)) >> >> > Although createEitherChan might be the best solution for some > application, it would be interesting to know what the recommended way > to implement the function eitherChan above is, if that is what you > really need? > > The eitherChan function corresponds to guarded nondeterministic > choice, usually written (a?P)+(b?Q) process calculi, i.e., a rather > fundamental concurrency operator. > > Section 5 of [1] enumerates some reasons why guarded nondeterministic > choice is not available as a primitive in Concurrent Haskell. Section > 5.2 describes a function select for nondeterministic choice, but I > don't see how to use that to implement readEitherChan (or > takeEitherMVar)... It's a hard problem. Trying to code up takeEitherMVar by hand always seems to lead to solutions with race conditions - I can't see a way to do it. Perhaps takeEitherMVar should be provided as a primitive, but I'm concerned that the same problems will crop up if we tried to implement takeEitherMVar in a multi-threaded runtime (GHC doesn't currently have a true multi-threaded runtime, but we'd like to do it someday). So I think in order to do this you have to build another abstraction around MVars. I've attached some code I just hacked up to do just that; it's untested (but compiles), and has a couple of known deficiencies, but it might be along the right lines. Cheers, Simon

3 2

Re: [Haskell-cafe] Polymorphic algebraic type constructors
by MR K P SCHUPKE 24 Jun '04

24 Jun '04

What you are suggesting - whilst it seems reasonable requires a fundamental change to the type system. At the moment [] signifies an empty list of type 'a' ... what you are suggesting requires [] to have a different type from [a]... This means a simple case statement : case a of (a:as) -> [] -> would now not type because everything on the LHS of the cases must be the same type. Infact I don't see how it could be any other way... 'a' has a type call it [a]... how could [] be any other type? Keean.

4 5

RE: atomic MVar overwrite (was RE: [Haskell-cafe] How to use QSem?)
by Simon Marlow 24 Jun '04

24 Jun '04

On 23 June 2004 17:46, S. Alexander Jacobson wrote: > Basically, what I want is a tryReadSampleVar > function. > > Or, if we stick with MVars, I don't want another > thread to operate between the tryTakeMVar and the > putMVar. In particular, I don't want another > thread to believe (mistakenly) that the mvar is > empty when it is simply being updated. > > I suppose I could define a new abstraction where I > have a second mvar that acts as an exclusive lock > on the the first MVar. e.g. > > data XMVar a = XMVar (MVar ()) MVar a > > overWriteXMVar (XMVar lock mvar) val = > withMVar lock (\_->tryTakeMVar mvar >> putMVar mvar val) > tryTakeXMVar (XMVar lock mvar) val = > withMVar lock (\_->tryTakeMVar mvar) > > But, I think it would be more sane simply to > have a tryReadSampleVar somewhere. If you send me code for tryReadSampleVar, I'll incorporate it. Unfortunately SampleVar is abstract, so you'll need to take the source for that library (libraries/base/Control/Concurrent/SampleVar.hs in a GHC distribution) and modify it to create your own version. Cheers, Simon

1 0

Polymorphic algebraic type constructors
by Graham Klyne 24 Jun '04

24 Jun '04

If I have a polymorphic algebraic type (T a) with several type constructors, only one of which actually references the type parameter, is there any way to express type conversion for the type-parameter-independent constructors without actually mentioning all the constructors? Here's a simple example based on Either: [[ data A = A String deriving (Show, Eq) data B = B String deriving (Show, Eq) f :: (a->b) -> Either String a -> Either String b f g (Right a) = (Right $ g a) f g (Left s) = (Left s) -- f g (s) = (s) -- doesn't work a2b (A s) = (B s) t1 = f a2b (Left "x") t2 = f a2b (Right (A "y")) ]] The second case for 'f' throws a type error when the constructor 'Left' is omitted, because the type of 's' is fixed to be Either String A when the required result (in this case, because of a2b) is Either String B. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

4 6

Re: [Haskell-cafe] Polymorphic algebraic type constructors
by MR K P SCHUPKE 24 Jun '04

24 Jun '04

Adrian Hey wrote: I think all occurences of [] have type forall a. [a] The case expression.. case a of (a':as) -> <expr1> [] -> <expr2> Should be typed as if written.. case a of (a':as) -> let a=(a':as) in <expr1> [] -> let a=[] in <expr2> ---------------------------------------------------- Well, we will have to agree to disagree, I find the current system makes perfect sense, and is easy to reason with. If I want a let binding I can write one. The difference is really this: case a of (a:as) -> <expr1> e -> e In this case e represent 'the same []' as on the left hand side. in the let binding this is a new and fresh '[]'... When I pattern match a variable in a case extression I really expect it to get the type of the case... There are circunstances when I go on to use e, and if it is not grounded by the case expression I will get hit by the monomorphoism restriction, and have to add non haskell98 type annotation to ground 'e'... for example If I pass e to a polymorphic function, it won't know what type e has... case a of (a':as) -> let a=(a':as) in <expr1> [] -> let a=[] in (polyfn a) where polyfn a has a type like polyfna :: Ord a -> [a] -> String Now the above won't work and you will have to do: [] -> let a=[] in (polyfn (a :: [SomeListType])) and of course if you are using generics then how can polyfn get the original type of 'a' in the case expression... for example: polyfn :: Typable a -> [a] -> ShowS polyfn a = shows (typeOf a) then: case a of (a:as) -> <expr1> e -> polyfn e is correct, but: case a of (a':as) -> let a=(a':as) in <expr1> [] -> let a=[] in (polyfn a) does what? Keean.

2 1