February 2004 - Haskell

Regular Expressions - take 2
by John Meacham 26 Feb '04

26 Feb '04

I went ahead and implemented Perl Compatable Regular Expression support as well as a module which uses template haskell to check regular expressions at runtime. The full set of modules is RRegex - PCRE if available, else Posix, (compatable with Text.Regex) RRegex.PCRE - Perl compatable regular expressions RRegex.Posix - posix regular extensions (compatable with Text.Regex.Posix) RRegex.TH - template haskell compile-time checked regular expressions RRegex.Syntax - perl like overloaded matching syntax Along the way, I extende the Posix interface, as the one in Text.Regex.Posix was lacking in several key ways. among the more interesting changes are ability to use (?options) syntax with posix expressions all of PCRE goodness. which is a lot. much better error messages (compile-time when using TH) example: > Fail: user error (PCRE Regular Expression Error: > [a-z_A-Z]+\(.*); > ^ unmatched parentheses) notice it points out the exact spot of the error. ability to pull out offset,length integer pairs, rather than extracting the substrings all the =~ stuff mentioned in my previous email. see the sort-of homepage here: http://haskell.org/hawiki/RegexSyntax and haddock documentation here: http://repetae.net/john/computer/haskell/hsregex/hsregex/docs/index.html John -- --------------------------------------------------------------------------- John Meacham - California Institute of Technology, Alum. - john(a)foo.net ---------------------------------------------------------------------------

1 0

RE: [Haskell] performance tuning Data.FiniteMap
by Simon Peyton-Jones 26 Feb '04

26 Feb '04

| But in managing this tradeoff, what is faster: | * constructing/destructing e.g. 16 trees (for a 65000 item table) | * 2 memcpy of 256 item arrays (perhaps after you primop?) | | If the later is not dramatically slower than I | will bias towards more arrayness. I doubt the latter is dramatically slower, but you'd have to experiment to find out. And GHC is not doing as well as it should on arrays just now. (One of the things on our to-do list.) Might vary between implementations too. Simon

2 1

Haskell job (OH, USA)
by Mark.Carroll＠Aetion.com 26 Feb '04

26 Feb '04

Aetion Technologies LLC seeks another high-quality programmer. Development is mostly in Haskell, with some Java, mostly under Linux. An ideal candidate is excellent at acquiring, applying, and writing about new knowledge. Additional background in disciplines like mathematics, science, engineering, etc. is also attractive. Aetion's main customers are in defense and finance, so we prefer to hire people who can likely get a security clearance, and who do not object to developing military applications. Telecommuting isn't really an option, but Columbus, Ohio is a nice enough city, and the work tends to be varied and interesting - more challenging than mundane. Although we work to build useful software, a lot of our activities are at the leading edge of research, keeping us far ahead of competitors. The vacancy has not yet been advertised more formally through the usual HR channels. Aetion is most definitely an equal-opportunity employer. It would be fine to direct questions and resumes directly to me; I can pass them on to the right people where necessary. -- Mark

1 0

RE: [Haskell] regular expression syntax - perl ain't got nothin on haskell
by Simon Marlow 26 Feb '04

26 Feb '04

> At 18:07 23/02/04 -0800, John Meacham wrote: > >It provides regular and monadic versions, a very overloaded > and useful > >interface, as well as extensibility. although currently the only > >instance is based on Text.Regex, it generalizes to matching lists of > >arbitrary type, not just strings, and also leaves the door open for > >compile-time checked and optimized regular expressions via template > >Haskell. > > I have a concern here that I hope you won't see as a negative > response to > your ideas... > > I recently ran into some problems porting some Haskell code > to Windows > because it used the Text.Regex library, which is dependent on > a Unix-only system. Text.Regex works fine on Windows, at least on GHC. It seems that Hugs doesn't make it available, perhaps because it requires an auxiliary C regex engine, which we provide as part of GHC. It may be that this code isn't as portable as the rest of Hugs, which is why they don't provide it, but I'll let the Huge folks comment on that. Cheers, Simon

2 1

RE: [Haskell] performance tuning Data.FiniteMap
by Simon Peyton-Jones 26 Feb '04

26 Feb '04

| > (//) is very slow | Is that inherent in Haskell (or laziness) or is it | just an artifact of the current GHC | implementation? Would the problem be solved by | making my arrays strict or by using Unboxed | arrays? Is there a faster array implementation | around? It's slow because it costs O(n) for what someone might expect to be an O(1) operation. Since the compiler does not know whether the 'old' array is going to be re-used for something else, it's forced to make a copy of the array, modifying the specified slot(s). Yes, the implementation could use memcpy, but it's still ridiculously expensive to copy a 10,000 word array to only modify one word. (GHC does not use memcpy -- it generates an explicit loop instead -- but it could if we added a new primop to encapsulate memcpy.) Advanced compiler optimisations might help, by detecting when the old copy isn't needed, but they are much much harder in a lazy language, and fragile to small program changes to boot. GHC makes no such attempt. An alternative is to put single-threaded-ness into the type system, as Clean does. Haskell's current story is to use O(log n) structures such as trees -- or to use a state monad. | PS I'm sorry if these are obvious beginner | questions. I would really realy like to use | Haskell for a production web application and am | trying to work through the various issues. It is | hard to find information on these sorts of things | and the absense of field testing means you just | have to ask these questions in advance. You should feel no need to apologise. Our community *needs* people like you, who are using Haskell for real applications. That's how we'll learn "where the shoe pinches". Ask away. Simon

2 1

RE: [Haskell] regular expression syntax - perl ain't got nothin on haskell
by Graham Klyne 25 Feb '04

25 Feb '04

At 17:24 24/02/04 +0000, Simon Marlow wrote: > > > At 18:07 23/02/04 -0800, John Meacham wrote: > > >It provides regular and monadic versions, a very overloaded > > and useful > > >interface, as well as extensibility. although currently the only > > >instance is based on Text.Regex, it generalizes to matching lists of > > >arbitrary type, not just strings, and also leaves the door open for > > >compile-time checked and optimized regular expressions via template > > >Haskell. > > > > I have a concern here that I hope you won't see as a negative > > response to > > your ideas... > > > > I recently ran into some problems porting some Haskell code > > to Windows > > because it used the Text.Regex library, which is dependent on > > a Unix-only system. > >Text.Regex works fine on Windows, at least on GHC. It seems that Hugs >doesn't make it available, perhaps because it requires an auxiliary C >regex engine, which we provide as part of GHC. It may be that this code >isn't as portable as the rest of Hugs, which is why they don't provide >it, but I'll let the Huge folks comment on that. Ah, yes, maybe so. The last communication I have on this is: http://www.haskell.org//pipermail/hugs-bugs/2004-January/001465.html #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

array IO
by Ketil Malde 25 Feb '04

25 Feb '04

Hi, Since I discovered that my program spent most of its time reading and writing files, I had a go at transforming it from using readFile to using array IO. Since my file consists of lines of length 18, I tried writing a similar function to readFile, to return a lazy list of lines as arrays, included below. This works, but wasn't more efficient. I haven't toyed to much with this kind of thing before, so please let me know if I'm doing anything obviously stupid. Perhaps the whole strategy is wrong? Should I wrap more of my program in IO, and do things incrementally there? (The files can be large, typically 100M-2G range, so reading them strictly is not an option) Or would it be more efficient to read larger chunks at a time? If so, what is a good chunk size? 1K? 4K? 1M? ----------8<-------------------- -- read the external file as a lazy list of arrays readXFile :: FilePath -> IO [UArray Int Word8] readXFile f = do h <- openFile f ReadMode getArrays h where getArrays h = do end <- hIsEOF h case end of True -> return [] False -> do (a :: IOUArray Int Word8) <- newArray (0,17) 0 hGetArray h a 18 a' <- unsafeFreeze a as <- unsafeInterleaveIO (getArrays h) return (a':as) ----------8<-------------------- -kzm -- If I haven't seen further, it is by standing in the footprints of giants

1 0

performance tuning Data.FiniteMap
by S. Alexander Jacobson 24 Feb '04

24 Feb '04

I believe FiniteMap works by representing the data in binary trees. It is therefore O(log2(n)) to read and update. However, if my application reads many more times than it writes, then perhaps I can get a substantial performance boost by increasing the branch factor on the tree. For example, if each node was an array of 256 elements, reads would be O(log256(n)), a 128x improvement! Note: I don't know what sort of penalty writes would have. In theory they would be 128x as expensive as well because each update would require copying 256 branches. However, in practice, I would bet that memcpy of 1k blocks can be optimized at the CPU so much that the difference might not be meaningful. Questions: Am I interpreting the performance issues correctly? Does FiniteMap used Arrays, Lists, or Algebraic Types? If arrays, is there an easy way to change the branching in FiniteMap? Do Haskell arrays do fast memcpy for small arrays? -Alex- _________________________________________________________________ S. Alexander Jacobson mailto:me@alexjacobson.com tel:917-770-6565 http://alexjacobson.com

4 3

More on POpen for Windows
by Graham Klyne 24 Feb '04

24 Feb '04

Further to problems reported in [1]. I've made a small step forward on this. I'm nearly out of time for now, so this is a partial report. I've created a pair of simple C programs: + EchoShiftLetters.c Reads from standard input and writes to standard output, converting all letters to upper case + SpawnEchoShiftLetters.c Uses spawnProc (the function at the heart of POpen) to run EchoShiftLetters, write some data to its standard output and read back from the standard output and standard error streams. It displays the data read back. This program works fine. What this demonstrates is that the basic Win32 API calls are working as expected, and that the problems encountered previously are probably to do with the Haskell-to-C interface, or the Hugs library routines that create I/O streams from file descriptors. My next step, when I get more time, is to try a simple Haskell program spawning the EchoShiftLetters program -- I'm expecting that to fail. There's one other datum: I attempted to build these test programs using the MinGW gcc tools, but got an undefined symbol error (I think it was WinMain) when building the SpawnEchoShiftLetters program. So I reverted to using the old MS Developer Studio tools. I think it was probably just a library missing from the build, but can't be sure of that. The code for all this can be found at [2]. #g -- [1] http://www.haskell.org//pipermail/libraries/2004-February/001700.html [2] http://www.ninebynine.org/Software/HaskellUtils/Win32/ ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

AC-unification libraries?
by Frank Atanassow 24 Feb '04

24 Feb '04

In the near future I expect to have need of an implementation of some basic term rewriting system algorithms, most notably: - term matching and unification - same, modulo associativity - same, modulo associativity and commutativity The first, of course, is easy to do myself; the second, I imagine, is not too difficult but, as I hear the last is very difficult to implement halfway efficiently, I would be grateful if someone could point me to an existing Haskell implementation. (No, I could not find a pointer at the Haskell website, or by scouring the web.) BTW, bonus points if such a framework supports extra things like checks for TRS confluence, termination, enumeration of critical pairs, Knuth-Bendix completion, etc. Thanks in advance. Regards, Frank

2 1