- Haskell-Cafe - Haskell.org

catch the stdout when execute a shell cmd
by Forest Liu 24 Jan '07

24 Jan '07

I use "system" in System.Cmd to execute a shell cmd, then how can I catch its stdout? -- Sincerely, Forest Liu(��S)

2 1

GADTs are expressive
by Jim Apple 24 Jan '07

24 Jan '07

To show how expressive GADTs are, the datatype Terminating can hold any term in the untyped lambda calculus that terminates, and none that don't. I don't think that an encoding of this is too surprising, but I thought it might be a good demonstration of the power that GADTs bring. {-# OPTIONS -fglasgow-exts #-} {- Using GADTs to encode normalizable and non-normalizable terms in the lambda calculus. For definitions of normalizable and de Bruin indices, I used: Christian Urban and Stefan Berghofer - A Head-to-Head Comparison of de Bruijn Indices and Names. In Proceedings of the International Workshop on Logical Frameworks and Meta-Languages: Theory and Practice (LFMTP 2006). Seattle, USA. ENTCS. Pages 46-59 http://www4.in.tum.de/~urbanc/Publications/lfmtp-06.ps @incollection{ pierce97foundational, author = "Benjamin Pierce", title = "Foundational Calculi for Programming Languages", booktitle = "The Computer Science and Engineering Handbook", publisher = "CRC Press", address = "Boca Raton, FL", editor = "Allen B. Tucker", year = "1997", url = "citeseer.ist.psu.edu/pierce95foundational.html" } -} module Terminating where -- Terms in the untyped lambda-calculus with the de Bruijn representation data Term t where Var :: Nat n -> Term (Var n) Lambda :: Term t -> Term (Lambda t) Apply :: Term t1 -> Term t2 -> Term (Apply t1 t2) -- Natural numbers data Nat n where Zero :: Nat Z Succ :: Nat n -> Nat (S n) data Z data S n data Var t data Lambda t data Apply t1 t2 data Less n m where LessZero :: Less Z (S n) LessSucc :: Less n m -> Less (S n) (S m) data Equal a b where Equal :: Equal a a data Plus a b c where PlusZero :: Plus Z b b PlusSucc :: Plus a b c -> Plus (S a) b (S c) {- We can reduce a term by function application, reduction under the lambda, or reduction of either side of an application. We don't need this full power, since we could get by with normal-order evaluation, but that required a more complicated datatype for Reduce. -} data Reduce t1 t2 where ReduceSimple :: Replace Z t1 t2 t3 -> Reduce (Apply (Lambda t1) t2) t3 ReduceLambda :: Reduce t1 t2 -> Reduce (Lambda t1) (Lambda t2) ReduceApplyLeft :: Reduce t1 t2 -> Reduce (Apply t1 t3) (Apply t2 t3) ReduceApplyRight :: Reduce t1 t2 -> Reduce (Apply t3 t1) (Apply t3 t2) {- Lift and Replace use the de Bruijn operations as expressed in the Urban and Berghofer paper. -} data Lift n k t1 t2 where LiftVarLess :: Less i k -> Lift n k (Var i) (Var i) LiftVarGTE :: Either (Equal i k) (Less k i) -> Plus i n r -> Lift n k (Var i) (Var r) LiftApply :: Lift n k t1 t1' -> Lift n k t2 t2' -> Lift n k (Apply t1 t2) (Apply t1' t2') LiftLambda :: Lift n (S k) t1 t2 -> Lift n k (Lambda t1) (Lambda t2) data Replace k t n r where ReplaceVarLess :: Less i k -> Replace k (Var i) n (Var i) ReplaceVarEq :: Equal i k -> Lift k Z n r -> Replace k (Var i) n r ReplaceVarMore :: Less k (S i) -> Replace k (Var (S i)) n (Var i) ReplaceApply :: Replace k t1 n r1 -> Replace k t2 n r2 -> Replace k (Apply t1 t2) n (Apply r1 r2) ReplaceLambda :: Replace (S k) t n r -> Replace k (Lambda t) n (Lambda r) {- Reflexive transitive closure of the reduction relation. -} data ReduceEventually t1 t2 where ReduceZero :: ReduceEventually t1 t1 ReduceSucc :: Reduce t1 t2 -> ReduceEventually t2 t3 -> ReduceEventually t1 t3 -- Definition of normal form: nothing with a lambda term applied to anything. data Normal t where NormalVar :: Normal (Var n) NormalLambda :: Normal t -> Normal (Lambda t) NormalApplyVar :: Normal t -> Normal (Apply (Var i) t) NormalApplyApply :: Normal (Apply t1 t2) -> Normal t3 -> Normal (Apply (Apply t1 t2) t3) -- Something is terminating when it reduces to something normal data Terminating where Terminating :: Term t -> ReduceEventually t t' -> Normal t' -> Terminating {- We can encode terms that are non-terminating, even though this set is only co-recursively enumerable, so we can't actually prove all of the non-normalizable terms of the lambda calculus are non-normalizable. -} data Reducible t1 where Reducible :: Reduce t1 t2 -> Reducible t1 -- A term is non-normalizable if, no matter how many reductions you have applied, -- you can still apply one more. type Infinite t1 = forall t2 . ReduceEventually t1 t2 -> Reducible t2 data NonTerminating where NonTerminating :: Term t -> Infinite t -> NonTerminating -- x test1 :: Terminating test1 = Terminating (Var Zero) ReduceZero NormalVar -- (\x . x)@y test2 :: Terminating test2 = Terminating (Apply (Lambda (Var Zero))(Var Zero)) (ReduceSucc (ReduceSimple (ReplaceVarEq Equal (LiftVarGTE (Left Equal) PlusZero))) ReduceZero) NormalVar -- omega = \x.x@x type Omega = Lambda (Apply (Var Z) (Var Z)) omega = Lambda (Apply (Var Zero) (Var Zero)) -- (\x . \y . y)@(\z.z@z) test3 :: Terminating test3 = Terminating (Apply (Lambda (Lambda (Var Zero))) omega) (ReduceSucc (ReduceSimple (ReplaceLambda (ReplaceVarLess LessZero))) ReduceZero) (NormalLambda NormalVar) -- (\x.x@x)(\x.x@x) test4 :: NonTerminating test4 = NonTerminating (Apply omega omega) help3 help1 :: Reducible (Apply Omega Omega) help1 = Reducible (ReduceSimple (ReplaceApply (ReplaceVarEq Equal (LiftLambda (LiftApply (LiftVarLess LessZero) (LiftVarLess LessZero)))) (ReplaceVarEq Equal (LiftLambda (LiftApply (LiftVarLess LessZero) (LiftVarLess LessZero)))))) help2 :: ReduceEventually (Apply Omega Omega) t -> Equal (Apply Omega Omega) t help2 ReduceZero = Equal help2 (ReduceSucc (ReduceSimple (ReplaceApply (ReplaceVarEq _ (LiftLambda (LiftApply (LiftVarLess _) (LiftVarLess _)))) (ReplaceVarEq _ (LiftLambda (LiftApply (LiftVarLess _) (LiftVarLess _)))))) y) = case help2 y of Equal -> Equal help3 :: Infinite (Apply Omega Omega) help3 x = case help2 x of Equal -> help1

6 9

Announce: Package rdtsc for reading IA-32 time stamp counters
by Martin Grabmueller 24 Jan '07

24 Jan '07

Hallo all, version 1.0 of package rdtsc has just been released. This small package contains one module called 'Rdtsc.Rdtsc'. This module provides the function 'rdtsc' for accessing the 'rdtsc' machine register on modern IA-32 processors. This is a 64-bit counter which counts the number of processor cycles since the machine has been powered up. Using this instruction, you can make very precise time measurements which are independent of the actual CPU frequency. But note that you can get strange results sometimes on a superscalar processor. A small program using this library looks like this: module Main where import Rdtsc.Rdtsc main = do t1 <- rdtsc t2 <- rdtsc putStrLn ("Cost of rdtsc (ffi call): " ++ show (t2 - t1)) Note that the Haskell foreign function interface imposes some additional overheads. On my machine, it takes about 950 cycles to call this function twice and to compute the difference, whereas in C the overhead is only about 84 cycles. The documentation for the package is available here: http://uebb.cs.tu-berlin.de/~magr/projects/rdtsc/ Download the source using darcs: darcs get http://uebb.cs.tu-berlin.de/~magr/darcs/rdtsc/ I would really like to get feedback on this little package, which already has been quite useful for me. Have fun and Happy Haskell Hacking in th New Year, Martin

6 7

Re: [Haskell-cafe] Strings in Haskell
by Alexy Khrabrov 24 Jan '07

24 Jan '07

I wonder if that's another reason OCaml is used in a(t least one) hedge fund -- why Jane St. preferred OCaml to Haskell, I wonder? Was it the state of affairs then that OCaml was more efficient (? -- WAGuess), and would they prefer Haskell now? I'm trying to make sense out of OCaml objects out of that already infamously annoying "Practical OCaml" book, and class object <blah>... doesn't look like much, not to say that "class object" sounds about as bad as most English in that book. (Written by an English major... What a decline in US education! :) I come from ML background, so Haskell laziness and OCaml objects are all new to me. But my Haskell book, Haskell School of Expression, is so much better written, that I'm reading it much faster. I'm CC'ing Yaron as his e-mail comes up in my Gmail context adwords on the word "Haskell." :) I'm interested in financial data mining and market modeling -- are there any good application of FP there, say in Lisp? Cheers, Alexy P.S. Somebody with an old-fashioned mail client please feel free to change the subject to "Financial Engineering with FP," gmail seems to etch its subjects in stone. :) On 1/23/07, Martin Jambon <martin_jambon(a)emailuser.net> wrote: > On Mon, 22 Jan 2007, Alexy Khrabrov wrote: > > > Greetings -- I'm looking at several FP languages for data mining, and > > was annoyed to learn that Erlang represents each character as 8 BYTES > > in a string which is just a list of characters. Now I'm reading a > > Haskell book which states the same. Is there a more efficient Haskell > > string-handling method? Which functional language is the most > > suitable for text processing? > > In OCaml, strings are compact sequences of bytes. And you can pass them > as-is to C functions: > > http://caml.inria.fr/pub/ml-archives/caml-list/2002/08/e109df224ff0150b3020… > > > Martin > > -- > Martin Jambon > http://martin.jambon.free.fr >

6 7

strange behavior in Text.Regex.Posix
by John MacFarlane 23 Jan '07

23 Jan '07

Can anyone help me understand this odd behavior in Text.Regex.Posix (GHC 6.6)? Prelude Text.Regex.Posix Text.Regex> subRegex (mkRegex "\\^") "he\350llo" "@" "he@llo" Why does /\^/ match \350 here? Generally Text.Regex.Posix seems to work fine with unicode characters. For example, \350 is treated as a single character here: Prelude Text.Regex.Posix Text.Regex> subRegex (mkRegex "e.l") "he\350llo" "@" "h@lo" The problem is specific to \350 and doesn't happen with, say, \351: Prelude Text.Regex> subRegex (mkRegex "\\^") "he\351llo" "@" "he\351llo" Is this a bug, or just something I'm not understanding? John

2 1

Re: [Haskell] Hyperlinking source code formatter?
by Simon Marlow 23 Jan '07

23 Jan '07

Conal Elliott wrote: > I'd like to turn source code (mine and others') into a fully hyperlinked > form, in which every name reference links to the name's definition. > Syntax-coloring would be great also. I see Programmatica. Is it in > use, supported, and reasonably easy to install and use? Are there other > options? Thanks, If anyone is thinking of writing such a tool, the GHC API would be a great place to start, incedentally. Cheers, Simon

1 0

Announce: hpaste
by Eric Mertens 23 Jan '07

23 Jan '07

Hello, I am pleased to announce "hpaste", the Haskell Paste-bin. Over the course of this week many of the active #haskell members and I have been developing this application to provide #haskell with a reliable paste bot whose features are tuned to the needs of the channel. Everyone is invited to see hpaste for themselves at http://hpaste.ath.cx:8000 hpaste.org has been registered, and in a few days time will be the permanent home of hpaste. An example of how hpaste was recently used to teach can be seen at http://hpaste.ath.cx:8000/43 A paste-bin is a place for IRC users to paste and annotate code snippets in a stable environment. This keep users from flooding the channel and saves users from having to scroll back constantly to review a paste. hpaste uses haskell syntax coloring (provided by hscolour) and is able to generate a color-coded diff of two pastes to give users an additional tool to share and teach. This project was a wonderful way for me to learn both the old and new HAppS APIs which have both proven to be quite powerful. In addition to providing a web-interface, hpaste is able to announce new pastes to the IRC channel via a bot based on Don Stewart's IRC bot tutorial. darcs has been instrumental in this colaborative effort, and the hpaste source is available with: darcs get --partial http://www.scannedinavian.com/~eric/hpaste Feedback is both encouraged and welcomed! -- Eric Mertens emertens(a)gmail.com

1 0

Strings in Haskell
by Alexy Khrabrov 23 Jan '07

23 Jan '07

Greetings -- I'm looking at several FP languages for data mining, and was annoyed to learn that Erlang represents each character as 8 BYTES in a string which is just a list of characters. Now I'm reading a Haskell book which states the same. Is there a more efficient Haskell string-handling method? Which functional language is the most suitable for text processing? Cheers, Alexy

4 3

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