March 2012 - Haskell-Cafe

Google Summer of Code idea of project & application
by Damien Desfontaines 20 Mar '12

20 Mar '12

Dear members of Haskell Cafe, My name is Damien Desfontaines, and I'm currently following a Theoretical Computer Science Major at the École Normale Supérieure in Paris, which is one of the most selective universities in France. To complete my curriculum, I am to find a three-month internship related to something I have learnt, including lambda-calculus, compilers, graph theory, languages theory, and complexity & calculability theories. I wish to make it useful for the open-source community, for example by working for the Haskell group through the Google Summer of Code Program. The project I suggest is mainly inspired by Ticket #1555 [1] : I think that would be a great idea to make it possible to call some Haskell code into OCamL. In particular, this would contribute to the spreading of Haskell in countries where OCamL is proeminent, mainly France and Italy. The idea would be the following : building a translator which would turn Haskell code into (purely functional) OCamL code, in order to enable the use of Haskell functions and libraries within OCamL programs, in a "human-readable" way (the OCamL source code generated would ideally be understandable enough to be manually modified). I am well aware that one of the main issues lies in dealing with the conversion between the two types systems, especially because of Haskell's lazy evaluation and typeclasses. However, such a challenge really motivates me to spend hours looking for the most efficient and usable solution, I would really enjoy spending three months on such problems. However, I sincerely think I have the skills needed to go through such a project. Indeed, I have a long experience with OCamL. I used this language to automatically write the undecidable Gödel proposition in Peano arithmetics, using Tarski's original proof [2]. I have written a mini-Java compiler with it [3], a MISP microprocessor simulator along with three friends [4], and many other things for studies and personal entertainment. My experience of Haskell is shorter, I learnt it with two books, "Learn You a Haskell for Great Good !" and "Real World Haskell" (you are the co-author of this last book, aren't you ? Well, congratulations, it's really well-written and precise !). I use it mainly for mathematical-oriented works, and for coding competitions such as Google Jam or Prologin. I also have a little experience with open-source software : I have been using Debian Linux for 4 years, so I know the basics of UNIX administration. I know how to write a bug report, a man-page, a README, etc. I spend a lot of time helping others on french IRC channels, Linux- or programmation-oriented. I contribute to the Weboob project [5] by writing documentation and new modules. This, in my opinion, makes me quite autonomous, and able to solve issues by myself, by reading documentation, manuals or language specifications. Apart from that, I have never been engaged in development of "large" projects such as Haskell - but I am ready and excited to start ! I am confident I can interact efficiently with the Haskell community: if you would like me to create a blog syndicated to Planet Haskell, in which I would explain my work every one or two weeks, I can do that. I know how to read a man-page, a language specification or a system documentation, so I consider myself as quite autonomous to answer questions I could ask myself during a project. Furthermore, please let me know if you think my skills could be useful to another Haskell project. I look forward to the opportunity to discuss this idea with one or several developers, Damien Desfontaines [1] http://hackage.haskell.org/trac/summer-of-code/ticket/1555 [2] http://www.eleves.ens.fr/home/desfonta/godel/godel.ml [3] http://www.eleves.ens.fr/home/desfonta/ProjetCompil/ [4] https://github.com/kyoDralliam/CircuitSimulator [5] http://weboob.org/

6 8

Google Summer of Code 2012
by Edward Kmett 19 Mar '12

19 Mar '12

It is that time of year again; the Google Summer of Code is upon us! If you are a student and want to sign up to make $5,000 for hacking on the code you love over the summer or are willing to help out as a mentor, now is the time to act. Please sign up by adding your name to the list at: http://hackage.haskell.org/trac/summer-of-code/wiki/People2012 Our main wiki entry for the Summer of Code 2012 is now online: http://hackage.haskell.org/trac/summer-of-code/wiki/Soc2012 If you are interested in applying as a student, here are some guidelines: http://hackage.haskell.org/trac/summer-of-code/wiki/StudApply2012 Student signups with Google start next week, but it is a good idea to start discussing things with potential mentors as soon as possible. The official * deadline* for student applications with Google is April 6th, but if you are interested please add your name to the People2012 page above, as soon as possible! *Interested in helping out, but not sure how?* There are a number of ideas that we've been collecting for projects available through the trac http://hackage.haskell.org/trac/summer-of-code/report/1 and which have been collecting over time in a reddit we used to use in years past: http://www.reddit.com/r/haskell_proposals/top/ While that reddit and the larger http://reddit.com/r/haskell reddit is a great place to discuss proposals, we had to choose one mechanism to supply Google with our ideas officially, so please submit proposals to the trac if you can think of something you like to work on, or which would be an appropriately beneficial project for a summer worth of work. *Helping Out Darcs* Haskell.org is planning to continue to act as an umbrella organization covering darcs for the Summer of Code once more. If you are interested in helping them out, they also have a page full of project ideas as well: http://wiki.darcs.net/GoogleSummerOfCode Again, please submit proposals as tickets to the trac if you can think of something you'd like to work on or have a neat idea for something someone else might want to work on (especially if you'd be willing to mentor it!) Of course, you can always feel free to email me or inquire on irc.freenode.net on #haskell or #haskell-soc or with the darcs folks over on #darcs for more information. If you don't have an IRC client, you can get there from: http://webchat.freenode.net Thank you all very much and we look forward to another successful Summer of Code! -Edward Kmett

1 0

ANN: unification-fd 0.7.0
by wren ng thornton 19 Mar '12

19 Mar '12

-------------------------------------------- -- unification-fd 0.7.0 -------------------------------------------- The unification-fd package offers generic functions for single-sorted first-order structural unification (think of programming in Prolog, or of the metavariables in type inference)[1][2]. The library *is* sufficient for implementing higher-rank type systems a la [Peyton Jones, Vytiniotis, Weirich, Shields], but bear in mind that unification variables are the metavariables of type inference--- not the type-variables. An effort has been made to make the package as portable as possible. However, because it uses the ST monad and the mtl-2 package it can't be H98 nor H2010. However, it only uses the following common extensions which should be well supported[3]: Rank2Types MultiParamTypeClasses FunctionalDependencies -- Alas, necessary for type inference FlexibleContexts -- Necessary for practical use of MPTCs FlexibleInstances -- Necessary for practical use of MPTCs UndecidableInstances -- For Show instances due to two-level types -------------------------------------------- -- Changes (since 0.6.0) -------------------------------------------- This release is another major API breaking release. Apologies, but things are a lot cleaner now and hopefully the API won't break again for a while. The biggest change is that the definition of terms has changed from the previous: data MutTerm v t = MutVar !v | MutTerm !(t (MutTerm v t)) To the much nicer: data UTerm t v = UVar !v | UTerm !(t (UTerm t v)) The old mnemonic of "mutable terms" was inherited from the code's previous life implementing a logic programming language; but when I was playing around with implementing a type checker I realized that the names don't really make sense outside of that original context. So the new mnemonic is "unification terms". In addition to being a bit shorter, it should help clarify the separation of concerns (e.g., between unification variables vs lambda-term variables, type variables, etc.). The swapping of the type parameters is so that UTerm can have instances for Functor, Monad, etc. This change should've been made along with the re-kinding of variable types back in version 0.6.0, since the UTerm type is the free monad generated by t. I've provided all the category theoretic instances I could imagine some plausible reason for wanting. Since it's free, there are a bunch more I haven't implemented since they don't really make sense for structural terms (e.g., MonadTrans, MonadWriter, MonadReader, MonadState, MonadError, MonadCont). If you can come up with some compelling reason to want those instances, I can add them in the future. Since the order of type parameters to BindingMonad, UnificationFailure, Rank, and RankedBindingMonad was based on analogy to the order for terms, I've also swapped the order in all of them for consistency. I've removed the eqVar method of the Variable class, and instead added an Eq superclass constraint. Again, this should've happened with the re-kinding of variables back in version 0.6.0. A major benefit of this change is that now you can use all those library functions which require Eq (e.g., many of the set-theoretic operations on lists, like (\\) and elem). I've added new functions: getFreeVarsAll, applyBindingsAll, freshenAll; which are like the versions without "All", except they're lifted to operate over Foldable/Traversable collections of terms. This is crucial for freshenAll because it allows you to retain sharing of variables among the collection of terms. Whereas it's merely an optimization for the others (saves time for getFreeVarsAll, saves space for applyBindingsAll). The type of the seenAs function has also changed, to ensure that variables can only be seen as structure rather than as any UTerm. Thanks to Roman Cheplyaka for suggesting many of these changes. -------------------------------------------- -- Description -------------------------------------------- The unification API is generic in the type of the structures being unified and in the implementation of unification variables, following the two-level types pearl of Sheard (2001). This style mixes well with Swierstra (2008), though an implementation of the latter is not included in this package. That is, all you have to do is define the functor whose fixed-point is the recursive type you're interested in: -- The non-recursive structure of terms data S a = ... -- The recursive term type type PureTerm = Fix S And then provide an instance for Unifiable, where zipMatch performs one level of equality testing for terms and returns the one-level spine filled with pairs of subterms to be recursively checked (or Nothing if this level doesn't match). class (Traversable t) => Unifiable t where zipMatch :: t a -> t b -> Maybe (t (a,b)) The choice of which variable implementation to use is defined by similarly simple classes Variable and BindingMonad. We store the variable bindings in a monad, for obvious reasons. In case it's not obvious, see Dijkstra et al. (2008) for benchmarks demonstrating the cost of naively applying bindings eagerly. There are currently two implementations of variables provided: one based on STRefs, and another based on a state monad carrying an IntMap. The former has the benefit of O(1) access time, but the latter is plenty fast and has the benefit of supporting backtracking. Backtracking itself is provided by the logict package and is described in Kiselyov et al. (2005). In addition to this modularity, unification-fd implements a number of optimizations over the algorithm presented in Sheard (2001)--- which is also the algorithm presented in Cardelli (1987). * Their implementation uses path compression, which we retain. Though we modify the compression algorithm in order to make sharing observable. * In addition, we perform aggressive opportunistic observable sharing, a potentially novel method of introducing even more sharing than is provided by the monadic bindings. Basically, we make it so that we can use the observable sharing provided by the modified path compression as much as possible (without introducing any new variables). * And we remove the notoriously expensive occurs-check, replacing it with visited-sets (which detect cyclic terms more lazily and without the asymptotic overhead of the occurs-check). A variant of unification which retains the occurs-check is also provided, in case you really need to fail fast. * Finally, a highly experimental branch of the API performs *weighted* path compression, which is asymptotically optimal. Unfortunately, the current implementation is quite a bit uglier than the unweighted version, and I haven't had a chance to perform benchmarks to see how the constant factors compare. Hence moving it to an experimental branch. These optimizations pass a test suite for detecting obvious errors. If you find any bugs, do be sure to let me know. Also, if you happen to have a test suite or benchmark suite for unification on hand, I'd love to get a copy. -------------------------------------------- -- Notes and limitations -------------------------------------------- [1] At present the library does not appear amenable for implementing higher-rank unification itself; i.e., for higher-ranked metavariables, or higher-ranked logic programming. To be fully general we'd have to abstract over which structural positions are co/contravariant, whether the unification variables should be predicative or impredicative, as well as the isomorphisms of moving quantifiers around. It's on my todo list, but it's certainly non-trivial. If you have any suggestions, feel free to contact me. [2] At present it is only suitable for single-sorted (aka untyped) unification, a la Prolog. In the future I aim to support multi-sorted (aka typed) unification, however doing so is complicated by the fact that it can lead to the loss of MGUs; so it will likely be offered as an alternative to the single-sorted variant, similar to how the weighted path-compression is currently offered as an alternative. [3] With the exception of fundeps which are notoriously difficult to implement. However, they are supported by Hugs and GHC 6.6, so I don't feel bad about requiring them. Once the API stabilizes a bit more I plan to release a unification-tf package which uses type families instead, for those who feel type families are easier to implement or use. There have been a couple requests for unification-tf, so I've bumped it up on my todo list. -------------------------------------------- -- References -------------------------------------------- Luca Cardelli (1987) /Basic polymorphic typechecking/. Science of Computer Programming, 8(2):147--172. Atze Dijkstra, Arie Middelkoop, S. Doaitse Swierstra (2008) /Efficient Functional Unification and Substitution/, Technical Report UU-CS-2008-027, Utrecht University. <http://www.cs.uu.nl/research/techreps/repo/CS-2008/2008-027.pdf> Simon Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, Mark Shields /Practical type inference for arbitrary-rank types/, to appear in the Journal of Functional Programming. (Draft of 31 July 2007.) Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, and Amr Sabry (2005) /Backtracking, Interleaving, and/ /Terminating Monad Transformers/, ICFP. <http://www.cs.rutgers.edu/~ccshan/logicprog/LogicT-icfp2005.pdf> Tim Sheard (2001) /Generic Unification via Two-Level Types/ /and Paramterized Modules/, Functional Pearl, ICFP. <http://web.cecs.pdx.edu/~sheard/papers/generic.ps> Tim Sheard & Emir Pasalic (2004) /Two-Level Types and/ /Parameterized Modules/. JFP 14(5): 547--587. This is an expanded version of Sheard (2001) with new examples. <http://web.cecs.pdx.edu/~sheard/papers/JfpPearl.ps> Wouter Swierstra (2008) /Data types a la carte/, Functional Pearl. JFP 18: 423--436. <http://www.cs.ru.nl/~wouters/Publications/DataTypesALaCarte.pdf> -------------------------------------------- -- Links -------------------------------------------- Homepage: http://code.haskell.org/~wren/ Hackage: http://hackage.haskell.org/package/unification-fd Darcs: http://community.haskell.org/~wren/unification-fd Haddock (Darcs version): http://community.haskell.org/~wren/unification-fd/dist/doc/html/unification… -- Live well, ~wren

1 0

Re: [Haskell-cafe] Best way to use the google visualization (javascript) API rather than static image charts (hs-gchart)?
by Ryan Newton 18 Mar '12

18 Mar '12

Thanks David, As an update, HJScript is a bit of a nightmare to figure out (missing documentation, examples). And the model of JS values: http://hackage.haskell.org/packages/archive/language-javascript/0.4.10/doc/… Seems less human comprehensible than, for example, WebBits': http://hackage.haskell.org/packages/archive/WebBits/2.0/doc/html/BrownPLT-J… However, jmacro is a breeze for spitting out JS code. The little script below will make a simple line plot with google charts. I'll give flot a try latter. Zooming / panning sounds nice. Cheers, -Ryan Aforementioned script: ------------------------------------------------------------------------------- {-# LANGUAGE QuasiQuotes #-} import Language.Javascript.JMacro hdr :: String hdr = "<html> <head> <script type=\"text/javascript\" src=\" https://www.google.com/jsapi\"></script> <script type=\"text/javascript\">" ftr :: String ftr = " </script> </head> <body> <div id=\"chart_div\" style=\"width: 900px; height: 500px;\"></div> </body> </html>" testdata :: [(String, Int, Int)] testdata = [ ("2004", 100, 400), ("2005", 1170, 460), ("2006", 860, 580), ("2007", 1030, 540) ] -- | This provides a set of basic functional programming primitives, a few utility functions -- and, more importantly, a decent sample of idiomatic jmacro code. View the source for details. -- body :: JStat body :: (ToJExpr a3, ToJExpr a2, ToJExpr a1, ToJExpr a) => (a, a1, a2) -> a3 -> JStat body (title,line1,line2) testdata = [$jmacro| google.load("visualization", "1", {packages:["corechart"]}); fun drawChart { var dat = new google.visualization.DataTable(); dat.addColumn('string', `(title)` ); dat.addColumn('number', `(line1)` ); dat.addColumn('number', `(line2)` ); // -- Here's our data... this can get BIG: dat.addRows( `(testdata)` ); var options = { title: `(title)` }; var chart = new google.visualization.LineChart(document.getElementById('chart_div')); chart.draw(dat, options); } google.setOnLoadCallback(drawChart); |] main = do putStrLn hdr print$ renderJs$ body ("blah","line1","line2") testdata putStrLn ftr

1 0

Stack overflow while programming imperatively
by Clark Gaebel 18 Mar '12

18 Mar '12

Hey list. I was recently fixing a space leak by dropping down to imperative programming in a section of my code, when it started developing space leaks of its own. I found the problem though - it was my "for loop": http://hpaste.org/65514 Can anyone provide suggestions on why that stack overflows? It seems ridiculously tail recursive. I tried to do it more haskell-like with http://hpaste.org/65517, but it was still spending 75% of its time in GC. Is there any way to write such a loop with ~100% productivity? I don't think there should be _any_ garbage generated, as all values may be stack allocated. Is this a performance regression in GHC? Thanks, - clark

2 2

Summer of Code idea: Haskell Web Toolkit
by Alejandro Serrano Mena 18 Mar '12

18 Mar '12

Hi, I'm really looking forward to helping in the Summer of Code, if Haskell goes into it this year (something I take for granted :). I would like to propose an idea for a project, and I'm looking for suggestions about whether it's good, should be improved or it's just unfeasible. My idea is to make a client-side Haskell Web Toolkit, in the spirit of Google Web Toolkit, which would allow to program in Haskell the client part of a web application, and would complement the web frameworks already existing for Haskell (such as Yesod and Snap). The point is coming about with a Haskell-ish way to program applications, to reuse all the existing knowledge for our beloved language. I've added more details in a pre-proposal in Google Docs, available in https://docs.google.com/document/d/1FnTNO9uTobDHRTDXWurKns7vGTjeauw0nRhbtt6… Tell me if you prefer to see it in other format, but I didn't want to generate a bigger e-mail. Thanks in advance.

10 16

We *have* been accepted into the Google Summer of Code
by Edward Kmett 18 Mar '12

18 Mar '12

Just to clarify, since I've been getting a ton of emails on the topic, we *have* been accepted to the Google Summer of Code this year. The list on their site is still updating, and we should appear there shortly. -Edward

3 3

cabal-install problem with alex dependency in bytestring-lexing
by Erik de Castro Lopo 17 Mar '12

17 Mar '12

Hi all, With a base system with just ghc and cabal-install, if I try to install bytestring-lexing I get: $ cabal install bytestring-lexing Resolving dependencies... Configuring bytestring-lexing-0.4.0... cabal: The program alex version >=2.3 is required but it could not be found. cabal: Error: some packages failed to install: bytestring-lexing-0.4.0 failed during the configure step. The exception was: ExitFailure 1 The cabal file for bytestring-lexing contains Build-Tools: alex >= 2.3 Is there any way to make the cabal install of bytestring-lexing force the install of alex first? Cheers, Erik -- ---------------------------------------------------------------------- Erik de Castro Lopo http://www.mega-nerd.com/

6 8

In an imperative language, commands & fulling memory cells is easy, but gives the false impression that S/W engineering is easy.
by KC 17 Mar '12

17 Mar '12

-- -- Regards, KC

3 2

In Haskell, because of the fine layers of abstraction that are possible, it pays to hone one's critical thinking skills.
by KC 17 Mar '12

17 Mar '12

-- -- Regards, KC

4 4