- Haskell - Haskell.org

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

RE: [Haskell] GHC Core & backend
by Simon Peyton-Jones 23 Feb '04

23 Feb '04

I don't see why it should be hard to use GHC's back end in this way. GHC's core language is pretty stable. I don't find the external representation of Core very appealing, but it's really meant for computers not people. An important constraint is that Core is *typed*, so you'd need a front end that kept type information around. Best thing would be to try a small experiment, to climb the learning curve a bit. Compile some little programs with GHC and see what Core they produce. Try generating a little Core. And so on. Kirsten Chevalier has quite a bit of experience of producing External Core using GHC, transforming it externally, and stuffing it back into GHC. Simon | -----Original Message----- | From: haskell-bounces(a)haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Arjan van | IJzendoorn | Sent: 13 February 2004 12:43 | To: haskell(a)haskell.org | Subject: [Haskell] GHC Core & backend | | Hello all, | | Is anybody using GHC's backend as a backend for their own compiler? | | In the paper "An external representation for the GHC Core Language" the | introduction states that "there are many (undocumented) idiosyncracies in | the way GHC produces Core from source Haskell". And that "it will be hard to | produced Core that can be integrated with GHC-produced core, and we don't | aim to support this". Has this changed since the time of writing this paper? | | It would be cool if, let's say, Helium (http://www.cs.uu.nl/helium) could | use all of GHC's libraries... | | Regards, Arjan van IJzendoorn | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell

1 0

Re: [Haskell] Compiling HXmlToolbox-3.01 on Mac OS X
by Sachin Desai 23 Feb '04

23 Feb '04

I've found that if I modify the Makefile and include -i<path-to-md5-directory> everything compiles and links fine. I did however have to make a small change to MD5.lhs removing the then clause. I don't believe this was correct but nevertheless it does compile and programs run. #ifdef __GLASGOW_HASKELL__ #define rotL rotateL #include "Zord64_EASY.hs" #else Could someone more knowledgeable explain what compiler flag, if any, is needed for the compilation to succeed with the above statement. I presume the problem was that MD5 was compiled "differently" than expected. The package as it came would not compile, make returned with nothing needs to be made, so I had to manually compile the file with the commands in the Makefile. -- Sachin On Feb 23, 2004, at 4:10 AM, Uwe Schmidt wrote: > Sachin Desai schrieb: > >> Has anyone successfully compiled this Toolbox on Mac OS X (10.3.2)? >> I've installed ghc made through darwinports, compiled and installed >> MD5 >> and am getting errors when building the toolbox. > > >> Skipping HTTP ( ./http/HTTP.hs, ./http/HTTP.o ) >> Compiling Browser ( ./http/Browser.hs, ./http/Browser.o ) > > it's not really a problem of the toolbox, but of the sources > we use for http access. the http modules are copied from Warrick Gray, > please look into the sources. we plan to rework the http input, to > modularize > it and to configure it for direct http support or via external > programs, or to > use only file access. Graham Klyne had similar problems when compiling > under > windows. perhaps a newer version of the http module may solve the > problem. > > uwe schmidt > > -- > > University of Applied Sciences, Wedel, Germany > http://www.fh-wedel.de/~si/index.html >

1 0

RE: [Haskell] "exists" keyword and "existential" types
by Simon Peyton-Jones 23 Feb '04

23 Feb '04

| I find myself confused by the lack of an "exists" quantifier to complement | "forall". It imposes seemingly arbitrary restrictions on the ways in which | types can be expressed, and makes some seemingly harmless (and useful) | types entirely inexpressible. | | For example, it seems as though runST could just as well be given the type | | runST :: forall a. exists s. ST s a -> a | | This isn't necessarily better than the usual type, but why can't it be | expressed? And it might actually be better: introducing exists would make | it possible to hoist quantifiers from both sides of the function arrow, | rather than just the RHS as GHC does now. | | And it would be nice to be able to pass around values of type | (exists t. Interface t => t), which behave just like OOP interface | pointers. I don't see how | | openInputStream :: FilePath -> IO (exists t. InputStream t => t) It's easier to suggest extensions to an already complicated type system than it is to give a watertight specification of the extension, still less to implement them. Mark Shields and I (mainly Mark) did go through the exercise of specifying a type system for Haskell with first-class existentials. It was extremely complicated, so much so that I cannot even explain *why* it was extremely complicated, though Mark may be able to. In my mind, it stands as an un-met challenge: can one add first-class existentials to Haskell (along with first-class universal quantification, of course). I know the Utrecht guys are thinking about doing this in (some version of) Helium. Once you have a good specification, there remains the challenges of (a) giving a reasonably simple type inference algorithm, and (b) implementing it. If anyone feels like running with this one, I'd like to suggest as a baseline the paper that Mark and I wrote about first-class universals "Practical type inference for higher-rank polymorphism". It's on my home page. http://research.microsoft.com/%7Esimonpj/papers/putting/index.htm The reason it makes a good starting point is that it gives a complete, executable type-inference engine for first-class universal polymorphism, well suited for extension with first-class existentials. And, of course, it comes with a very detailed tutorial (the paper). | > True, but why is this? Is there a deep reason why we can use nested | > foralls as the arguments to (->), but not as the arguments to any other | > type constructor? | | Apparently it makes type-checking Very Very Hard. Simon PJ may have | explained it to me ("impredicative", he called it), but I don't remember | offhand. This question, too, is discussed at some length in the paper. It is possible to do type inference in an impredicative system, but it's much harder. Le Botlan and Remy have an excellent paper, about a language called MLF, that describes such a system, but it's not for the faint hearted. Simon

1 0

"exists" keyword and "existential" types
by Ben Rudiak-Gould 23 Feb '04

23 Feb '04

I find myself confused by the lack of an "exists" quantifier to complement "forall". It imposes seemingly arbitrary restrictions on the ways in which types can be expressed, and makes some seemingly harmless (and useful) types entirely inexpressible. For example, it seems as though runST could just as well be given the type runST :: forall a. exists s. ST s a -> a This isn't necessarily better than the usual type, but why can't it be expressed? And it might actually be better: introducing exists would make it possible to hoist quantifiers from both sides of the function arrow, rather than just the RHS as GHC does now. And it would be nice to be able to pass around values of type (exists t. Interface t => t), which behave just like OOP interface pointers. I don't see how openInputStream :: FilePath -> IO (exists t. InputStream t => t) would cause any more problems than data Foo = forall t. InputStream t => Foo t openInputStream :: FilePath -> IO Foo What am I missing? While looking through old posts for insight, I came across a thread from last April started by Simon P-J, who wrote: > > Many of you have grown to love existential data types, which we current > write like this: > > data T = forall a. Foo a (a -> Int) > > Mark and I chose 'forall' rather than 'exists' to save grabbing another > keyword from the programmer. And indeed, the type of the constructor > Foo is > Foo :: forall a. a -> (a->Int) -> T > > But every single time I explain this to someone, I find I have to make > excuses for using the term 'forall'. I say "it really means 'exists', > but we didn't want to lose another keyword". > > I have gradually concluded that our decision was a mistake. (In > fairness to Mark, I think I was the primary advocate for it.) I reckon > that we should > > Allow 'exists' > Deprecate 'forall' (for defining existentials, that is) > Eventually allow only 'exists' > But I think the use of "forall" in this context is correct, and "exists" incorrect. I find it easy to explain: you're creating many different "Foo" constructors, one for every possible type a, so when you extract a value from a Foo you're getting some type a, but you don't know which. Using "exists" here would express something different, namely that there's only one Foo, but you don't know (and it mustn't matter) what type it expects to be bound to a, and therefore you can't apply Foo to a value unless that value is general enough to encompass all possible types for a. This gives the constructor function a rank-2 type, or equivalently an existentially-quantified variable at the top level. When you match against the value you're getting something which has to be able to stand in for any type. I think the source of confusion is not the use of forall, but the term "existential types". There is nothing existential about them! The type variables involved can be either existentially or universally quantified, depending on the context. They use exists in exactly the contexts where "ordinary" type variables use forall, and vice versa. Instead of changing the forall, I think we should change the name "existential types" to something which approximately reflects what they actually are, like "inaccessible types" or "hidden types". "Abstract types" would also be a possibility, but I think it would be confused with the separate concept of using module scope to hide value constructors. My other suggestions might also cause that kind of confusion, but I still think they're better than "existential types", which seems to have no more to do with the concept being expressed than "left-handed types" or "male types" would have. -- Ben

5 7