- Haskell-Cafe - Haskell.org

Resolution of time for threadDelay / registerDelay
by Neil Davies 22 Jan '07

22 Jan '07

The GHC concurrency run time currently forces all delays to be resolved to 1/50th of second - independent of any of the run time settings (e.g. -V flag) - with rounding to the next 1/50th of second. This means that, in practice, the "jitter" in the time that a thread wakes as compared with can be rather large - 20ms to 30ms; 20ms from the GHC base library rounding along with a "jiffy" from the operating system. As far as I can see there is no reason why there should be any quantization of delay times - the implementation creates an ordered list of times which could be at any resolution (say microseconds) - this would reduce the "jitter" to that of an operating system jiffy. Thoughts? Neil

1 0

ANN: regex-* updates and regex-tdfa 0.20 first release
by Chris Kuklewicz 22 Jan '07

22 Jan '07

Greetings. I have several bits of news about regex-* packages. First: I have fixed a small bug in one instance of RegexContext, defined in Text.Regex.Contex in the regex-base class (included in GHC). The new version of regex-base is 0.80 and is available at http://darcs.haskell.org/packages/regex-unstable/regex-base/. The instance fixed was > instance (RegexLike a b) => RegexContext a b (MatchResult b) where and I doubt this affects anyone at the moment. Second: There is also a new version of regex-tre at http://darcs.haskell.org/packages/regex-unstable/regex-tre/ (version 0.81) that exposes the 'compRightAssoc' option when making a Regex (see Text.Regex.TRE.Wrap for all the options). Third: I wish to note that that the libtre backend (up to the current version 0.7.5) that regex-tre uses is buggy and that regex-tre / libtre should only be used where testing shows that no bugs are being trigged. (Why go to that much trouble? Because the libtre backend is very very fast). Fourth: The fabulous new all Haskell POSIX compatible backend! This is a first announcement of regex-tdfa, my "tagged" DFA regular expression backend. It is an implementation of regular expressions in Haskell; it does not hand off the data to a library written in c. The ultimate goal of regex-tdfa is to replace regex-posix as the default engine that come with GHC. Why go to the trouble of replacing regex-posix? Because regex-posix is very very slow (and not quite POSIX, as seen at the end of this message). The new regex-tdfa does not use the slow backtracking method like my pure Haskell backend regex-posix. It uses a deterministic finite automata, similar in spirit to one I derived from CTKlight for use in the pure Haskell regex-dfa backend (which is LGPL -- the rest are BSD-3 license). But regex-dfa is fast at a cost of not returning any parenthesized subexpression captures (i.e only \0 and not \1 \2 \3 ...). The regex-tre backend (BSD3) that uses the libtre c library (LGPL) employs a special "tagged" dfa technique to get subexpression captures while still using an efficient DFA. The regex-posix engine that comes with GHC is impossibly slow but regex-tre is very very fast and (claims to also be) a POSIX engine. I was thus inspired to create regex-tdfa which aims to create a pure Haskell variant of this tagged-DFA algorithm under a simple BSD3 license. The 0.20 version of regex-tdfa that I am announcing is available at http://darcs.haskell.org/packages/regex-unstable/regex-tdfa/ and requires the updated regex-base (version 0.80 or greater) and is setup to compile for GHC 6.6. These could be back-ported to GHC 6.4 by adding the fps package to GHC 6.4 to get Data.ByteString and removing references to Data.Sequence in the new regex-base and regex-tdfa packages. As of now, my first untuned version of the regex-tdfa backend performs about 2-3 times slower than regex-tre and the libtre c library. This also means regex-tdfa performs 3+ times faster than the regex-parsec engine. So the goal of a fast replacement for regex-posix is close to hand. The bad news: libtre has two problems, the first is that it is buggy. I have found patterns that the libtre engine does not handle correctly: the wrong match for the whole expression and/or subexpressions is returned (or it will fail to match when it should have succeeded). The second problem is that it does not always follow the POSIX standard policy in determining which possible parenthesized subexpession captures to return when there are several possibilities. My regex-tdfa engine does not have the bugs that I have found in libtre. But since it uses the same design concepts as libtre it had the same problem with not following the POSIX standard policy for capturing subexpressions. To fix this I have exteneded the tagging technique to keep enough information to follow the POSIX spec. So of all the regex-* backends, the regex-tdfa is the only one that passes all the tests that I have for POSIX compatibility. End note: The regex-posix engine, despite its name, does not follow the POSIX standard policy for capturing subexpressions. Example 1 of 2: "ab" =~ "((a?)((ab)?))(b?)" This should capture the sub ranges (0,2)(0,2)(0,0)(0,2)(0,2)(2,2) But it does capture the sub ranges (0,2)(0,1)(0,1)(1,1)(-1,-1)(1,2) The first group is (0,2) means the whole match was \0=="ab" The second group (0,2) or (0,1) means the first group "((a?)((ab)?))" should match \1=="ab" but it returns \1=="a". This first group should have been chosen for maximum length and the failure to do so is a policy violation. Example 2 of 2: "x" =~ "(.?)*" This should capture: (0,1)(0,1) But it does capture: (0,1)(1,1) The first group of (0,1) means the regex did match the whole \0=="x". But the regex-posix engine matched an extra iteration of the "(.?)" under the "*" operator against the empty string after the "x" and returned the empty capture of (1,1). This highly non-useful behavior violates POSIX policy. My regex-parsec engine follows a non-POSIX policy, in which it maximizes the length of just the captured subexpressions instead of all the subpatterns of the regular expression. This is useful and was easy to write and is easy to explain and agrees with the policy of other libraries such as Boost.Regex for C++ ( as in the third FAQ at http://www.boost.org/libs/regex/doc/faq.html ) But to replace regex-posix I need a fast POSIX policy engine, which is what regex-tnfa has now achieved. I will submit regex-tdfa to replace regex-posix once I have a stable version that has been further cleaned up and tuned. Anyone who wishes a useful performance time/spacce tuning challenge is free to help. If you have any evil or stressful examples of regular expressions, then I welcome adding them to my tests. -- Chris Kuklewicz

1 0

Haskell -> Tk
by Peter Padawitz 22 Jan '07

22 Jan '07

Does anybody know O'Haskell or Timber and its interface Tk.hs to Tcl/Tk (see here <http://fldit-www.cs.uni-dortmund.de/%7Epeter/tk.html>)? I have the following problem: Tk.hs <http://fldit-www.cs.uni-dortmund.de/%7Epeter/Tk.hs> contains a record (structure) /Canvas/ with selectors line :: [(Int,Int)] -> [LineOpt] -> Request Line polygon :: [(Int,Int)] -> [PolygonOpt] -> Request Polygon that are compiled into synonymous Tk widgets for lines and polygons, respectively. Unfortunately, Tk.hs crashes if the point list parameter of line or polygon contains more than 100 points. Why??? Of course, one may split a point list into smaller ones that are compiled correctly. But this may not produce the same picture, for instance, if the entire list represents a polygon to be filled or a line to be smoothened. Peter

1 0

Problems using Storable.poke* from separate OS thread.
by Corey O'Connor 22 Jan '07

22 Jan '07

The short version: If a haskell routine exported to C is called from a CoreAudio IO Proc, which is on a separate thread than the main thread, the Haskell routine seams to exit early without notice. If the same routine is called from the main thread the routine produces correct output. Any ideas on why Storeable.poke* would cause problems in this situation? The long version: I'm attempting to generate audio using Haskell and CoreAudio.* For a start I tried converting Noel Cragg's HAL sinewave demo to process the audio frames in Haskell. The original is here: http://www.red-bean.com/~noel/audio/hal-demo.c How CoreAudio HAL output works is like this: - A audio callback is registered with the audio device - Audio playback is started - A separate thread, dedicated to audio processing, will then call the audio callback with pre-allocated buffers to be filled out with audio samples. The test program has "main" in C and the audio callback in C. The C callback forwards to a Haskell routine exported by the FFI system. This routine should behave identically to the C implementation that already exists. However, the routine does not work correctly if called from the audio thread. The test program also calls the routine from the main thread in a manner that should be identical to how it's called from the thread. This is used to verify the Haskell callback does actually produce the same audio as the original C callback. So I know the code should work, but just fails for some inexplicable reason on the threaded callback. Other notes: - The program is compiled with -threaded and linked against the threaded RTS. - If I structure the routine like this: ... print "Before the audio is written to the buffer." process_frames print "After the audio is written to the buffer." The first print succeeds but the second print never occurs. No IO error is reported to try_. - If I take that same structure and remove "pokeElemAt" from process_frames. The second print occurs. I've uploaded the test program here: http://www.tothepowerofdisco.com/downloads/TestAudioOutput.zip Some notes on if you actually try to build it: - You have to build 3 times; There is a bug in XCode's custom build rule handling or the projects custom build rule. - The executable is wrapped in a app bundle but is actually a command line app. - It's a hack and I'm a beginner so comments are scarce and some code may be strange. ;-) - Assumes ghc 6.6 is installed to /usr/local Any ideas? -- -Corey O'Connor

2 2

Re: [Haskell-cafe] Fractional sqrt
by Henning Thielemann 22 Jan '07

22 Jan '07

On Mon, 22 Jan 2007, Yitzchak Gale wrote: > Henning Thielemann wrote: > > > > there is already an implementation of continued > > > > fractions for approximation of roots and transcendent functions by Jan > > > > Skibinski: > > > > http://darcs.haskell.org/numeric-quest/Fraction.hs > > I wrote: > > > Wow, nice. Now - how was I supposed to have found that? > > Simon Peyton-Jones wrote: > > Perhaps one of you can add this to the libraries-and-tools page? > http://www.haskell.org/haskellwiki/Libraries_and_tools/ > > I added a new page for the Numeric Quest library, > and added it to the Mathematics category. > (Should it be in any other category?) > I also updated the references to Numeric Quest > on the Mathematics and Physics page. Great work! However I would not throw away the links to the Internet archive because the pages stored there link to the original HTML pages which are lost. It's cumbersome to navigate through the archived pages. The Darcs repository at cvs.haskell.org is no official update by Jan Skibinski - I set up that repository to simplify further development. I added the keyword "continued fractions" to the Wiki page so the module can be discovered by other people.

2 1

Partial Application
by Philippe de Rochambeau 22 Jan '07

22 Jan '07

Hello, my original query concerning partial application was triggered by the following statement from Thomson's "The Craft of Functional Programming", p. 185: " multiplyUC :: (Int, Int) -> Int multiplyUC (x,y) = x * y multiply :: Int -> Int -> Int multiply x y = x * y .... In the case of multiplications we can write expression like multiply 2". When I read this, I thought that you could partially apply "multiply" by typing "multiply 2" at the ghci prompt. However, this generated an error: <interactive>:1:0: No instance for (Show (Int -> Int)) arising from use of `print' at <interactive>:1:0-9 Possible fix: add an instance declaration for (Show (Int -> Int)) In the expression: print it In a 'do' expression: print it After reading http://www.haskell.org/hawiki/PartialApplication, I figured out that you can only partially apply declared functions, in source files, not at the prompt: multiplyBy2 = multiply 2 Now "multiplyBy2 50" yields "100" On page 22 of "Programming in Haskell", Howard says that you can do the following partial application of the curried function add': add' 1 :: Int -> Int, where add and add' are declared as add :: (Int,Int) -> Int add (x,y) = x + y add' :: Int -> (Int -> Int) add' x y = x + y However, typing "add' 1" at the prompt generates an error. If I add the following to my source file addOne = add' 1 typing addOne 5" at the prompt yields "6", which is the right answer. Cheers, phiroc

11 15

mtl tweaks
by Nicolas Frisby 21 Jan '07

21 Jan '07

There have been some discussions of augmentations of the monad transformer library. I at least know there was a discussion regarding strictness of state/value components in the state monad transformer (I must admit I didn't track the conclusion of that one). I have another small mtl complaint: ReaderT, for example, requires the base type to be a Monad in order to make it a Functor. So it's Monad m => Functor (ReaderT r m) instead of Functor f => Functor (ReaderT r f), which is what's actually necessary for the instance. Remember, I did say _small_ complaint. I realize this has a bit to do with the class heirarchy and that's a sensitive issue. Regarding backwards compatibility and interface changes, note that the Monad m => Monad (ReaderT r m) instance would be unaffected by this... it's only the Functor => Functor instance. If someone wants to treat a transformed monad as a functor, then they're probably savvy enough to specify the base monad as a functor (especially with the @fmap f = (>>= return . f)@ recipe). They won't even see a difference unless they are rolling their own monad, since all mtl monads are also functors. 1) Is there a collection of these suggestions specifically for mtl? On the wiki? On the bug tracker? 2) Any chance we could make this change to the library? Thanks, Nick

2 1

Re: [Haskell-cafe] Article review: Category Theory
by Yitzchak Gale 20 Jan '07

20 Jan '07

I wrote: >> Will (id :: A -> A $!) do the trick? Ulf Norell wrote: > The problem is not with id, it's with composition. For any f and g we > have > > f . g = \x -> f (g x) > > So _|_ . g = \x -> _|_ for any g. OK, so then how about f .! g = ((.) $! f) $! g -Yitz

4 7

Article review: Category Theory
by David House 20 Jan '07

20 Jan '07

Hey all, I've written a chapter for the Wikibook that attempts to teach some basic Category Theory in a Haskell hacker-friendly fashion. http://en.wikibooks.org/wiki/Haskell/Category_theory >From the article's introduction: "This article attempts to give an overview of category theory, insofar as it applies to Haskell. To this end, Haskell code will be given alongside the mathematical definitions. Absolute rigour is not followed; in its place, we seek to give the reader an intuitive feel for what the concepts of category theory are and how they relate to Haskell." I'd love comments from newcomers and experts alike regarding my approach, the content, improvements and so on. Of course, it's on the wikibook, so if you have anything to add (that's not _too_ substantial otherwise I'd recommend discussion first) then go ahead. Thanks in advance. -- -David House, dmhouse(a)gmail.com

15 36

File locked unnecessarily (the file)
by Arie Peterson 20 Jan '07

20 Jan '07

Except that the example was not attached. Sorry. Greetings, Arie

1 0