August 2006 - Haskell

ANNOUNCE: The experimental GHCi debugger
by pepe 22 Aug '06

22 Aug '06

Dear all It is that time of the year again. Google SoC has come to an end and a flurry of students announce their results to the corresponding community. Yesterday Jun Mukai reported on the status of HaskellNet and now it is the turn of the GHCi debugger project. The contributions of this project are mainly two: - Intermediate value viewer: The new ':print' and ':sprint' in GHCi allow to explore semievaluated values without forcing them, accessing the internals and recovering the types. - Dynamic breakpoints: The new ':breakpoint' command integrates seamlessly in GHCi and allows to set breakpoints in your code Which add to previously existing work polished as part of this project too: - The breakpoint and breakpointCond functions in GHC.Base allow to manually install (conditional) breakpoints in your code, which will be activated when you run your program in GHCi DETAILS Though it needs an update, you can check the wiki dump page at: http://haskell.org/haskellwiki/GHC/GHCiDebugger In it you will find a lot of outdated stuff, but also some interesting things: * some examples of the closure viewer * how to get the patches and build it * A link to the Users Guide documentation page for GHCi that now includes a section for the debugger (I know it does not render well in all the browsers out there, but this is just a snapshot) * A video! Watch me debug a Haskell Universal Machine (I know I know, it's not so impressing, and sorry for the poor audio. Macbooks don't seem to like cheap mics so I had to use a phone bluetooth hands-free) FUTURE WORK Overall, this version is a basic, "the simplest thing that could possibly work" implementation. Call stack traces have unhappily not made it into this version, but there are some proposals already and the GHC people seem very interested in getting themselves a feature complete debugger, so you should not lose hope. Future work should include exploring more advanced realizations of dynamic breakpoints. ACKNOWLEDGEMENTS Big thanks to Google for making this project possible. Big thanks to my mentors too, David Himmelstrup and Simon Marlow, for accepting this role. I know how busy they are and I hope I have not been too big of a burden during these months. As a colofon to the project, odds are that the GHC people will include my patches in the 6.6 Release Candidate at the end of the week. Needless to say, I will be most interested in hearing from any issues you may find, especially if you try it before the Release Candidate date. Please let me know of any additional feature requests you have too, or better add them to the wiki where other people will see them too. So please, if you feel like doing it, give it a go before the Release Candidate and let me know if you found any issue! pepe

1 0

status report of HaskellNet
by Jun Mukai 22 Aug '06

22 Aug '06

Dear all, HaskellNet is develped under GSoC program, and I'd like to report the current status of HaskellNet. HaskellNet will be a collection library for networking. Now, it contains, - SMTP - POP3 - IMAP - HTTP - (FTP) - URI - Mime parser and, I wrote a Stream like type class of ByteString. I also wrote the example code to connect these libraries with hsgnutls. Because FTP client is came from missingh, it is licensed under LGPL (Thanks to John Goerzen). Others includeing HTTP (came from Bjorn Bringert's code) are licensed under BSD3. You can obtain the codes from http://darcs.haskell.org/SoC/haskellnet (add .lgpl to get with FTP client). The period of SoC will end soon, but HaskellNet is now under development. Although the current codes have (maybe) no problems, they can not be tested fully. In addition to it, I want to add other protocols and other ideas. Actually, There are discussions between me and Alexander Jacobson about importing Protocol.DNS from HAppS. But, I did not have the time to do it (Although it can be done shortly). I mean, I'd like to keep the development of HaskellNet. Any comments are welcome. Best Regards, Jun Mukai mukai(a)jmuk.org

2 1

ANN: SmallCheck 0.0 another lightweight testing tool
by Colin Runciman 22 Aug '06

22 Aug '06

I have written a prototype tool that is similar in spirit, and in some of its workings, to QuickCheck, but based on exhaustive testing in a bounded space of test values. Sales pitch: wouldn't you like to ... * write test generators for your own types more easily? * be sure that any counter-examples found are minimal? (##) * write properties using existentials as well as universals? * establish complete coverage of a defined test-space? * display counter-examples of functional type? (##) * guarantee repeatable test results? (##) For more details and a Haskell 98 module SmallCheck download the small tar file at: http://www.cs.york.ac.uk/fp/smallcheck0.0.tar If you try it, do let me know how you get on. Comments & suggestions welcome. Colin R -------- (##) There have been versions of QuickCheck with extras that address these issues in other ways.

1 0

[ANNOUNCE] Frisby: composable, linear time parser for arbitrary PEG grammers
by John Meacham 22 Aug '06

22 Aug '06

Frisby is an implementation of the 'packrat' parsing algorithm, which parse PEG grammars and have a number of very useful qualities, they are a generalization of regexes in a sense that can parse everything in LL(k), LR(k), and more, including things that require unlimited lookahead, all in guarenteed linear time. There is no need for a separate lexing pass when using a packrat parser due to the subsumpion of regular expressions, and the unlimited lookahead obviating the need to tokenize the input. The work is still alpha, but has had some very promising test results, parsing (subsuming lexing) megabytes of test input in seconds that traditional backtracking parsers completely fail at. Although the basic mechanism works, the API is still in flux, at the moment, parsers are specified almost exactly in their native grammar form. here is an example of a simple parser and evaluator for numeric expressions. additive = mdo additive <- mkRule $ multitive <> char '+' ->> additive ## uncurry (+) // multitive multitive <- mkRule $ primary <> char '*' ->> multitive ## uncurry (*) // primary primary <- mkRule $ char '(' ->> additive <<- char ')' // decimal decimal <- mkRule $ many1 (oneOf ['0' .. '9']) ## read return additive // is choice, it attempts its left argument, and if it fails, it trys its right one. <> is concatination <<- and ->> are concatination that discard the results of one side or the other and ## is jus a fancy way of writing 'fmap' to process the results. notice the use of 'mdo' to implement monadic recursion. the home page and more information is here: http://repetae.net/computer/frisby/ I would greatly welcome feedback on the API. I have included routines that take standard regular expression syntax and translate them into an equivalent frisby parser. John -- John Meacham - ⑆repetae.net⑆john⑈

1 0

ANNOUNCE: GHC's new support engineer: Ian Lynagh
by Simon Marlow 21 Aug '06

21 Aug '06

We are delighted to announce that GHC now has a full-time support engineer. He is Ian Lynagh (aka Igloo on IRC), and is well known to many of you on the Haskell and GHC mailing lists. He'll be helping with all aspects of GHC, especially release management, bug diagnosis and tracking, documentation, packaging, and supporting other GHC hackers. Welcome Ian! We were absolutely delighted by both the number and quality of the people who applied for the post, and we want to thank them all very much for doing so. We love you all! Andrew Herbert, the lab director of Microsoft Research Cambridge lab director, also deserves a big thank-you, for supporting this post (no strings attached!). It'll make a huge difference. Looking forward to seeing many of you soon, at the GHC Hackathon [1] (25 people registered), and/or at ICFP in Portland. Simon Peyton Jones and Simon Marlow [1] http://hackage.haskell.org/trac/ghc/wiki/Hackathon

1 0

The GHC typechecker is Turing-complete
by Robert Dockins 18 Aug '06

18 Aug '06

This message is literate Haskell so you can all follow along at home. The program developed in this message was tested on GHC 6.4.2. My purpose today is to show that the GHC typechecker with multi-parameter typeclasses, functional dependencies, and undecidable instances is Turing- complete. Some time ago on this mailing list, there was a brief discussion about a lambda calculus and a direct Turing-machine implementation; either would be sufficient to demonstrate the Turing-completeness of the typechecker. However, neither implementation was preserved on-list, and the links are now dead. My strategy will be to embed the SK combinator calculus. The SK combinator calculus is capable of embedding the lambda calculus, which is well-known to be Turing-complete. Furthermore, the SK calculus is simpler to implement than the lambda calculus. For a complete proof of Turing-completeness, one should have a correctness proof for the embedding. I do not undertake such a proof here, but I will demonstrate what I hope to be convincing evidence for the correctness of this embedding. I begin by throwing the switches that give me the needed extensions. > {-# OPTIONS -fglasgow-exts -fallow-undecidable-instances #-} > module SK where Next I define the terms of the SK combinator basis. This includes symbols for the combinators themselves, a symbol for application, and a way to introduce arbitrary uninterpreted types into computations. > data K0 > data S0 > data App x y > data Other a Now I proceed to create the evaluator by first defining a single-step reduction relation. This relation is carefully designed to be reflexive on normal forms, and always reduces the leftmost-outermost redex. I then form the final evaluation relation by taking the transitive closure of single-step reduction. The semantics of typeclass constraint satisfaction are basicly strict. That is, the typechecker will make sure to fully evaluate all class constraints and fully instantiate all types whether or not those types turn out to be needed. Because of this, I need to be careful to form the transitive closure in a way that doesn't cause the typechecker to diverge on evaluation when it should not (of course, the typecheker will diverge on divergent terms). In order to do this, I define the single-step reduction relation so that it returns an additional result in addition to the reduced term. This result indicates 'More' whenever a redex was found and reduced and 'Done' otherwise. A few reduction rules perform reduction in parallel. These rules will return 'More' if reduction was performed on any subterm. > data Done > data More > class CombineDone d1 d2 d | d1 d2 -> d > instance CombineDone Done Done Done > instance CombineDone Done More More > instance CombineDone More Done More > instance CombineDone More More More The 'Eval1' relation performs a single step of reduction. The presentation of this relation is somewhat tedious because we are forced to enumerate each possible spine shape up to 4 'App's deep. I could possibly do this more concisely if I enabled overlapping instances. > class Eval1 x y d | x -> y d I start by providing axioms stating that atomic terms evaluate to themselves with no reduction. > instance Eval1 S0 S0 Done > instance Eval1 K0 K0 Done > instance Eval1 (Other a) (Other a) Done There are a number of cases which just propagate evaluation contexts underneath the right-hand side of of 'App' when the spine shape cannot be reduced any further. These fairly uninteresting cases are collected together here. > instance Eval1 x x' d => Eval1 (App K0 x) (App K0 x') d > instance Eval1 x x' d => Eval1 (App S0 x) (App S0 x') d > instance ( Eval1 x x' d1 > , Eval1 y y' d2 > , CombineDone d1 d2 d > ) => Eval1 (App (App S0 x) y) (App (App S0 x') y') d > > instance Eval1 x x' d => Eval1 (App (Other a) x) (App (Other a) x') d > > instance ( Eval1 x x' d1 > , Eval1 y y' d2 > , CombineDone d1 d2 d > ) => Eval1 (App (App (Other a) x ) y ) > (App (App (Other a) x') y') d > > instance ( Eval1 x x' d1 > , Eval1 y y' d2 > , Eval1 z z' d3 > , CombineDone d1 d2 d4 > , CombineDone d3 d4 d > ) => Eval1 (App (App (App (Other a) x ) y ) z ) > (App (App (App (Other a) x') y') z') d Now we get to the real meat. Here are the rules for reducing the 'K' combinator. There are rules for reducing under both 2 and 3 'App's. > instance Eval1 (App (App K0 x) y) x More > instance Eval1 (App (App (App K0 x) y) z) (App x z) More And here, the rule for reducing the 'S' combinator. > instance Eval1 > (App (App (App S0 f) g) x) > (App (App f x) (App g x)) > More Finally, a rule to decompose an arbitrary 'App' context. I propagate the evaluation context down the left side of an 'App' only when that 'App' is not involved in any redexes. This implements the leftmost- outermost strategy. In any leftmost spine consisting of 4 'App's, the leftmost 'App' can never be involved in any redex. The cases for other levels of 'App's are folded into the above rules. > instance ( Eval1 (App (App (App p q) x) y) a d > ) => Eval1 (App (App (App (App p q) x) y) z) (App a z) d Now I need to take the transitive closure of the 'Eval1' relation. I do this with the auxiliary 'EvalAux' class. The first instance represents the base case, where 'Eval1' performed no reductions. The second instance implements the transitivity and does bookkeeping with the termination markers. > class EvalAux x y q1 | x q1 -> y > instance EvalAux x x Done > instance ( Eval1 x y q > , EvalAux y z q > ) => EvalAux x z More Now at last I can define the evaluation relation. It is defined in terms of 'EvalAux' and hides the termination bookkeeping. > class Eval x y | x -> y > instance EvalAux x y More => Eval x y I define convenient functions to allow me to invoke the type evaluators and a synonym for 'undefined' to cut down on typing. > eval1 :: Eval1 x y q => x -> y > eval1 = undefined > eval :: Eval x y => x -> y > eval = undefined > bot :: a > bot = undefined Before showing off the evaluator, I'm going to need several dummy types to work with. > data P0 > data Q0 > data R0 > type P = Other P0 > type Q = Other Q0 > type R = Other R0 Now, some examples of the SK evaluator in action. First I show that the S and K combinators have their expected axiomatic behavior. (Note, the following demonstrations rely on definitions found in the appendix at the end). > testK = eval (bot :: K P Q) :: P > testS = eval (bot :: S P Q R) :: App (App P R) (App Q R) Now I demonstrate several different ways of writing the identity combinator. > test1 = eval (bot :: I P) :: P > test2 = eval (bot :: C K0 I0 P) :: P > test3 = eval (bot :: App (Y KI0) P) :: P Axiomatic demonstrations of several other important combinators. > test4 = eval (bot :: M P) :: App P P > test5 = eval (bot :: W P Q) :: App (App P Q) Q > test6 = eval (bot :: C P Q R) :: App (App P R) Q > test7 = eval (bot :: B P Q R) :: App P (App Q R) Uncomment the following line to cause GHC to diverge. > -- testOmega = eval (bot :: OMEGA) Finally, a presentation of the church numerals in combinatory form. > type FoldN n = App (App n P) Q > type Z = SK0 > type Succ0 = App S0 (App (App S0 KS0) K0) > type Plus0 = App (App S0 KS0) (App (App S0 (App K0 (App S0 (App K0 S0)))) > (App S0 KK0)) > type Mult0 = App (App S0 KS0) K0 > type Succ a = App Succ0 a > type Mult n m = App (App Mult0 n) m > type Plus n m = App (App Plus0 n) m > type One = Succ Z > type Two = Succ One > type Three = Succ Two > type Four = Succ Three > type Five = Succ Four > test_n1 = eval (bot :: FoldN Z) :: Q > test_n2 = eval (bot :: FoldN One) :: App P Q > test_n3 = eval (bot :: FoldN (Plus Two Three)) > test_n3 :: App P (App P (App P (App P (App P Q)))) > test_n4 = eval (bot :: FoldN (Mult Two Four)) > test_n4 :: App P (App P (App P (App P (App P (App P (App P (App P Q))))))) ================================================= Appendix: definitions of additional combinators > type K x y = App (App K0 x) y > type S f g x = App (App (App S0 f) g) x > type I x = App SKK0 x > type B x y z = App (App (App B0 x) y) z > type C x y z = App (App (App C0 x) y) z > type M x = App M0 x > type W f x = App (App W0 f) x > type Y f = App Y0 f > type I0 = SKK0 > type B0 = App (App S0 KS0) K0 > type C0 = App (App S0 (App (App B0 B0) S0)) KK0 > type W0 = App C0 (App (App B0 M0) (App (App B0 B0) (App C0 I0))) > type L0 = App (App C0 B0) M0 > type Y0 = App (App S0 L0) L0 > type KI0 = App K0 I0 > type M0 = App (App S0 I0) I0 > type OMEGA = App M0 M0 > type KK0 = App K0 K0 > type KS0 = App K0 S0 > type KK x = App KK0 x > type KS x = App KS0 x > type SK0 = App S0 K0 > type SS0 = App S0 S0 > type SKK0 = App (App S0 K0) K0 > type SKS0 = App (App S0 K0) S0 > type SSK0 = App (App S0 S0) K0 > type SSS0 = App (App S0 S0) S0 > type SK f x = App (App SK0 f) x > type SS f x = App (App SS0 f) x > type SKK x = App SKK0 x > type SKS x = App SKS0 x > type SSK x = App SSK0 x > type SSS x = App SSS0 x

4 4

How to read one char from stdin and return immediately?
by Haihua Lin 18 Aug '06

18 Aug '06

Hi all, How to read one char from stdin and return immediately? I mean there is no need to wait the user input a return. For example: Print "y/n: " Users input y, return immediately, no return need. I have tried code as below, but it didn't work for me. import IO main = do hSetBuffering stdout NoBuffering putStr "Y/N: " c <- getChar putStr ("Your input is " ++ show c++".\n") Thanks very much. Best regards, Haihua Lin

2 1

Re: Re: [Haskell] How to read one char from stdin and return immediately?
by Haihua Lin 18 Aug '06

18 Aug '06

I just tried. It works. Sorry for my mistake. Thanks. > >Hi > >> hSetBuffering stdout NoBuffering > >Try hSetBuffering stdin NoBuffering, since its stdin you are reading from. > >Thanks > >Neil >

1 0

Re: [Haskell] How to read one char from stdin and return immediately?
by Neil Mitchell 18 Aug '06

18 Aug '06

Hi > hSetBuffering stdout NoBuffering Try hSetBuffering stdin NoBuffering, since its stdin you are reading from. Thanks Neil

1 0

Reminder: ICFP'06 registration deadline
by John Reppy 17 Aug '06

17 Aug '06

[update: hotel help info and deadline reminder] ------------------------------------------------------------------------ CALL FOR PARTICIPATION The 11th ACM SIGPLAN International Conference on Functional Programming (ICFP 2006) Portland, Oregon September 18-20, 2005 ------------------------------------------------------------------------ For more details, see http://icfp06.cs.uchicago.edu Preliminary Program: http://icfp06.cs.uchicago.edu/schedule.html Registration information: http://regmaster2.com/conf/icfp2006.html Hotel information: http://icfp06.cs.uchicago.edu/hotel.html ------------------------------------------------------------------------ Reminder: the deadline for early registration is Friday, August 18th. Note: if you are having difficulty with your hotel reservation, please contact Larry Skaja (larry at cteusa dot com) for help. ------------------------------------------------------------------------

1 0