March 2010 - Haskell-Cafe

Re: Fast Haskell Parser
by Ben Lippmeier 10 Mar '10

10 Mar '10

Hi John, Doing a Google search for "haskell parser" returns the following link as its first result. That's the parser that GHC uses. http://www.haskell.org/happy/ You could also check out the following: http://www.haskell.org/haskellwiki/Parsec http://hackage.haskell.org/package/attoparsec This would also be a perfect question to ask on the haskell-cafe mailing list... Cheers, Ben. On 11/03/2010, at 10:39 AM, John D. Earle wrote: > I was thinking of ways to create an efficient Haskell parser. My initial thinking was to write a top down parser in Haskell, but if you want speed a table driven approach may make greater sense. > > Due to the existence of build bots there is a certain degree of compliancy concerning build times. I feel that convenience is an important factor. It should be convenient to build the source. Build bots make an assumption, namely the existence of a formal infrastructure. I believe that it should be possible to build something from source casually. > > This is a less demanding goal than high performance incremental builds. It would be nice to out perform make files because if you fail to do this, can it really be said that you are making progress? Correctness appears to be a low priority among computer programmers. That said, it may be worth investing some time in advance to figuring out how to best achieve both objectives, namely correctness and performance. Who knows skills acquired in one project may be useful in another and performance is usually welcome. > > So my question is, What sort of tools and methodologies exist in Haskell to create high performance parsers? My impression is the speed at which the parser performs its task is not the bottle-neck, but the parser might as well be designed to be efficient so as not to be intellectually lazy. It may even turn out that the parser may need to be efficient merely to compensate for the spawn of correctness, namely slow builds. > _______________________________________________ > Cvs-ghc mailing list > Cvs-ghc(a)haskell.org > http://www.haskell.org/mailman/listinfo/cvs-ghc

1 0

vector stream fusion, inlining and compilation time
by stefan kersten 10 Mar '10

10 Mar '10

hi, two questions in one post: i've been hunting down some performance problems in DSP code using vector and the single most important transformation seems to be throwing in INLINE pragmas for any function that uses vector combinators and is to be called from higher-level code. failing to do so seems to prevent vector operations from being fused and results in big performance hits (the good news is that the optimized code is quite competitive). does anybody have some more info about the do's and don'ts when programming with vector? the downside after adding the INLINE pragmas is that now some of my modules take _really_ long to compile (up to a couple of minutes); any ideas where i can start looking to bring the compilation times down again? i'm compiling with -O2 -funbox-strict-fields instead of -Odph (with ghc 6.10.4 on OSX 10.4), because it's faster for some of my code, but -O2 vs. -Odph doesn't make a noticable difference in compilation time. many thanks, <sk>

8 12

ANNOUNCE: yesod 0.0.0 (web framework)
by Michael Snoyman 10 Mar '10

10 Mar '10

Hello all, I'm happy to announce the first release of the Yesod Web Framework[1]. This framework has been in development for over a year and is in production use on a number of websites. The project homepage[2] provides a fairly thorough rundown of features; for here, I will suffice to say that this framework aims at the following goals: * RESTful applications * Deployable anywhere (based on WAI) * Safety While this framework is still in active development and can be expected to mature over time, this release is ready for use. To get started quickly, simply install the yesod package from Hackage and type "yesod init". Michael [1] http://hackage.haskell.org/package/yesod [2] http://www.yesodweb.com/code.html

2 6

Re: [Haskell-cafe] more thoughts on "Finally tagless"
by Tom Schrijvers 10 Mar '10

10 Mar '10

On Tue, Mar 9, 2010 at 2:45 PM, Tillmann Rendel <rendel(a)mathematik.uni-marburg.de> wrote: > Tom Schrijvers wrote: >>> >>> Yeah, subject "Finally Tagless" again, sorry, I'm just not done with it >>> yet. >>> >>> In Olegs haskell implementation he is using classes mainly to model the >>> syntax and instances to use for evaluators / compilers to allow multiple >>> interpretations. >>> >>> I wonder if it'd be possible to do the same without classes using data >>> types >>> instead? >>> >>> Something similar to what Luke Palmer has done here: >>> >>> >>> http://lukepalmer.wordpress.com/2010/01/24/haskell-antipattern-existential-… >> >> You can just use the dictionary translation of type classes to replace >> them with data types: >> >> E.g. >> >> class Eval sem where >> val :: Int -> sem Int >> add :: sem Int -> sem Int -> sem Int >> >>> --> >> >> data EvalDict sem = EvalDict { val :: Int -> sem Int, add :: sem Int >> -> sem Int -> sem Int } > > This is the way to program in the final tagless style without using type > classes, but there is an important difference to what Luke Palmer did in the > blog post cited above. While both approaches allow to encode type classes > using data types, they are technically different, and applicable for > different programs. > > In the dictionary approach, the dictionary contains fields of the same types > as the members of the class. For example, val has the type Int -> sem Int in > both the type class and the data type. > > This is not the case in the pattern described by Luke. There, the w type is > dropped from the types of the methods when converting to a data type. For > example, the type of growHorizontal is w -> Bool in the type class, but > simply Bool in the data type. > > The reason for this difference is that Luke uses the fact that w is going to > be always existentially bound, so it will not be externally usable anyway. > The information contained in the w values can just as well be stored in each > of the fields of the data type. > > The dictionary approach encodes abstract data types: The data type is the > interface, each value of the data type is an implementation, and a function > which takes the dictionary and is parametric in the type parameters of the > dictionary is a program which uses the data type abstractly. > > For example, a program using the Eval abstract data type from above could > look like this: > > -- using the type class > add_two :: Eval sem => sem -> sem > add_two x = add x (val 2) > > -- using the dictionary > add_two :: EvalDict sem -> sem -> sem > add_two dict x = add dict x (val dict 2) > > On the other hand, Luke describes an encoding of objects: The data type > describes the interface of an object, and each value of that data type is an > object, with possibly different implementations of each function in the > interface. A program using these objects can invent arbitrary new objects, > as long as all fields in the interface are defined. > > Since abstract data types and objects are fundamentally different, so are > these two programming patterns. Tillmann, Thanks for your insight of objects vs. abstract data types. William Cook's Onward! essay is relevant here. He characterizes the difference between objects and abstract data types nicely: the latter allow binary methods that pattern match (to exploit the combined knowledge of the internals of two different values) whereas objects only know their own implementation. Dictionaries by themselves are objects in Cook's sense: they are just a record of functions that cannot be inspected. We can have an infinite number of them (while we can only have one type class instance per sem type). However, the (sem a) values are not objects, and varying the dictionaries while keeping the sem type the same does not seem very useful for implementing different semantics. For a type class function like add :: sem Int -> sem Int -> sem Int, binary pattern matching seems essential for meaningful implementations, and hence objects don't make much sense. Would you agree? Cheers, Tom

2 1

Anyone up for Google SoC 2010?
by Malcolm Wallace 10 Mar '10

10 Mar '10

Google has announced that the Summer of Code programme will be running again this year. If haskell.org people would like to take part again this year, then we need volunteers: First, * suggestions for suitable projects (in the past this was organised using a reddit) * an administrator to co-ordinate the application to Google (I have done it for the last three years but am very willing to hand on to someone else) Google will accept applications from organisations in the period 8th - 12th March 2010, approx 1900UTC. If haskell.org is accepted again, students can apply between 29th March - 9th April. More volunteers will be required: * to review student applications and choose which to accept * to supervise the accepted students Both of these roles are called "mentor" in the Google system. Putting together a good team of mentors before applying as an organisation is helpful towards us being accepted into the programme. Regards, Malcolm

17 32

Detecting extensions of the host processor
by Henning Thielemann 10 Mar '10

10 Mar '10

I like to detect at runtime whether the processor my program runs on has certain extensions (SSE2, SSE3 or so) in order to execute optimized code. On Linux I can process the contents of /proc/cpuinfo but this will not work on Windows. Is there a portable way in Haskell?

2 1

Re: If the local variable can be changed ...
by John Lato 10 Mar '10

10 Mar '10

> From: zaxis <z_axis(a)163.com> > > So if the local variable can be changed, then we can use loop, etc. same as > imperative languages. For example, for (i=0; i<100; i++) where `i` is a > local variable in function. > In addition to John Millikin's suggestion, you can also do: map f [0..99] where f :: Int -> a; f = ... or mapM f [0..99] where f :: Int -> m a; f = ... for monadic actions. Here "f" is the body of the loop. The loop bodies must be completely independent, but this is a very useful technique. Cheers, John

1 0

Num instance for Lazy ByteStrings (was: NumLazyByteString Package License)
by Thomas DuBuisson 10 Mar '10

10 Mar '10

Tristan and other interested parties on the Cafe, Answering your question first, Tristan: I was going to use BSD3 (if it isn't already) for the NumLazyByteString. For the cafe too: A while ago I made a Num instance for LPS; it is currently on my code.haskell.org account. Notice this isn't on Hackage yet and the semantics will be different soon. Most notably I want to ensure divide and anything else implemented through 'asInteger' and 'asInteger2' results in a bytestring of length equal to the largest of the operands. If that isn't clear then let me be very explicit. NumLazyByteString intentionally allows overflow! If you want operations (mod 2^40) then you need only work with bytestrings of length 5 bytes and the operations will result in 5 byte ByteString. This is already true for basic operations (bit operations, +, -, *) but is not yet done for quot, rem, quotRem, divMod, mod, /, and other you can see leverage Integer instead of using custom code. Any desire for non-overflowing operations (basically, re-expressing Integer as LazyByteString) would have to be done as an newtype with a Num instance that grows the bytestring to the necessary level, preventing overflow prior to calling NumLazyByteString. Finally, I intend for numerous operations to be lazy. If you add two infinite bytestrings you should be able to get the result of that operation (modulo some finite value) using NumLazyByteString. This is obviously not true for those operations leveraging Integer. Any comments or requests on the future of this Library are welcome - I'll probably get around to finishing it and putting it on Hackage in a couple weeks. Cheers, Thomas On Sun, Mar 7, 2010 at 9:24 PM, Tristan Ravitch <travitch(a)cs.wisc.edu> wrote: > I found myself adding Bits and Num instances for ByteStrings when I > found your implementation (which is much better than mine was shaping > up to be). Do you have any particular license in mind for it? > > I used it in an implementation of the Delta Debugging algorithm > (http://www.st.cs.uni-saarland.de/dd/) which I was thinking I would > like to release, and wanted to make sure the licensing could work out > properly. > > Thanks, > -- > Tristan Ravitch > travitch(a)cs.wisc.edu > http://pages.cs.wisc.edu/~travitch > > -----BEGIN PGP SIGNATURE----- > Version: GnuPG v1.4.10 (GNU/Linux) > > iEYEARECAAYFAkuUiiUACgkQJklRJNuIcWSxmACfVblD+gR/Fv57teNTArSfXhHg > NtsAnRqBvinNesMk3mxMxDERw5MBn9jZ > =Jm4O > -----END PGP SIGNATURE----- > >

5 5

Re: First time haskell - parse error!
by John Lato 10 Mar '10

10 Mar '10

> From: Ketil Malde <ketil(a)malde.org> > > "S. Doaitse Swierstra" <doaitse(a)cs.uu.nl> writes: > >>> then (s1 ++ s2 ++ s3 ++ s4) where >>> s1 = "Golds " >>> s2 = show (gold s g) >>> s3 = ", Silvers " >>> s4 = show (silver s g) > >> If you want to keep the definitions local to the expression you should write > > ..but I think it is better style to avoid this kind of one-off named > values. I much prefer: > > then "Golds "++show (gold s g)++... > > For some reason, this is a style isse that doesn't get much attention, > at least not in the non-functional language tradition, where temporary > variables are scattered all over. So instead of doing: > > let ns y = not (isSpace y) > f x = takeWhile ns x > in map f > > We can use anonymous functions in place of the uninformatively named > ones: > > map (\x -> takeWhile (\y -> not (isSpace y)) x) > > and use partial application toward point-free-ness: > > map (takeWhile (not . isSpace)) I agree, and also tend to this style. Although I sometimes use one-off named values to avoid line wraps. For the particular task of combining strings like this, how about using Text.Printf.printf? then printf "Golds %s, Silvers %s" (show (gold s g)) (show (silver s g)) It can be a little hard to understand the type at first, but IMHO it works as expected. Cheers, John

1 0

more thoughts on "Finally tagless"
by Günther Schmidt 10 Mar '10

10 Mar '10

Hi all, and Oleg et al in particular. Yeah, subject "Finally Tagless" again, sorry, I'm just not done with it yet. In Olegs haskell implementation he is using classes mainly to model the syntax and instances to use for evaluators / compilers to allow multiple interpretations. I wonder if it'd be possible to do the same without classes using data types instead? Something similar to what Luke Palmer has done here: http://lukepalmer.wordpress.com/2010/01/24/haskell-antipattern-existential-… Günther

6 8