September 2006 - Haskell

Haskell' Status Report
by Isaac Jones 28 Sep '06

28 Sep '06

Ravi Nanavati has very helpfully put together a status report for the Haskell Prime process. Please see this link, or read the pasted text below: http://hackage.haskell.org/trac/haskell-prime/wiki/Status' peace, isaac Summary: Since the Haskell Workshop last year, the Haskell community has documented (on this wiki) over 70 proposals for changes to Haskell 98. In March of this year, two subcommittees were established to focus on concurrency and the class system - two difficult areas that are important to the success of Haskell'. The committee has also used StrawPolls to filter and discuss the universe of proposals that has been gathered. Based on the most recent straw poll, 12 proposals (listed in the table at the bottom of the page) have been identified that are expected to get into Haskell' (over 2/3 of the committee in favor). An additional 19 proposals seem likely to get into Haskell' (based on slightly weaker criteria). Members of the committee conflict on 9 of the remaining proposals, and their status will be determined during the writing process. The remaining proposals are not expected to be part of Haskell'. Concurrency: The concurrency support in Haskell' will be based on the Control.Concurrent library, with minor modifications. There will be a thread-safe interface for mutable state, suitable for use in library code that does not otherwise use concurrency (though what it will be based on is an open issue). There will also be independent FFI annotations for specifying whether foreign calls are concurrent (with other Haskell threads) and reentrant. Bound threads will not be required by the concurrency standard, but they will be an allowed extension with a specified meaning. Open issues include whether standard will require preemptive concurrency, the syntax of the new FFI annotations and the memory-model semantics of IORefs. Class system: The work on the class system has focused on resolving the MultiParamTypeClassesDilemma. The core of the dilemma is that multi-parameter typeclasses are a popular extension that is strongly desired for Haskell'. However, many important uses of MPTCs (like the monad transformer library) require additional extensions to resolve ambiguities in their typechecking. Historically, FunctionalDependencies have been used for this purpose, but they are very tricky to implement and are also difficult to specify in a way that guarantees the termination of typechecking. AssociatedTypes are a possible replacement, but our current implementation experience with them is very limited. The subcommittee has explored several ways to resolve this dilemma (including restricted FDs, fast-tracked ATs and FDs as a "blessed" extension), but, so far, no consensus has emerged. Our current plan is to focus on writing other parts of the Haskell' standard, in the hopes that additional implementation experience with ATs will clarify the situation. Libraries: Thus far, libraries have been an underemphasized portion of the Haskell' effort (only 7 of the 70+ proposals have significant library content). However, there is a consensus that a revised standard library is an important part of the Haskell' effort. The current plan is to focus on starting to write the language portions of the standard first, since we have a substantial amount of work to do there which requires focused attention. After that effort is well underway, a companion library effort will begin. Several members of the committee have volunteered for this effort and additional volunteers will be needed. "definitely-in" Proposal Status: Description (Those volunteering to write this section): add some kind of Concurrency (IJ, SM) add ForeignFunctionInterface (MC, SM) add multi-parameter type classes (MS) add RankNTypes or Rank2Types (AL) add PolymorphicComponents (AL) add ExistentialQuantification (existential components) (AL, MS, SJT) add HierarchicalModules (IJ, BH, MW) add EmptyDataDeclarations (BH, HN) DoAndIfThenElse (SM, HN) fix comment syntax grammar (SM) add PatternGuards (RN, DS) add InfixTypeConstructors (BH, AL)

2 1

Types in Language Design and Implementation 2007 - Call for Papers
by Simon Marlow 28 Sep '06

28 Sep '06

[ posting on behalf of George Necula <necula(a)eecs.berkeley.edu> ] =============== Read the html version of this CFP at http://www.cs.berkeley.edu/~necula/tldi07/cfp.html The ACM SIGPLAN Workshop on Types in Language Design and Implementation Affiliated with ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), 2007. Scope The role of types and proofs in all aspects of language design, compiler construction, and software development has expanded greatly in recent years. Type systems, type analyses, and formal deduction have led to new concepts in compilation techniques for modern programming languages, verification of safety and security properties of programs, program transformation and optimization, and many other areas. In light of this expanding role of types, the ACM SIGPLAN Workshop on Types in Language Design and Implementation (TLDI'07) follows five previous International Workshops on types in compilation and language design(TIC'97, TIC'98, TIC'00, and TLDI'03 and TLDI'05), with the hope of bringing together researchers to share new ideas and results in this area. Submissions for this event are invited on all interactions of types with language design, implementation, and programming methodology. This includes both practical applications and theoretical aspects. TLDI'07 specifically encourages papers from a broad field of programming language and compiler researchers, including those working in object-oriented, dynamically-typed, late-binding, systems programming, and mobile-code paradigms, as well as traditional fully-static type systems. Topics of interest include: Typed intermediate languages and type-directed compilation Type-based language support for safety and security Types for interoperability Type systems for system programming languages Type-based program analysis, transformation, and optimization Dependent types and type-based proof assistants Types for security protocols, concurrency, and distributed computing Type inference and type reconstruction Type based specifications of data structures and program invariants Type-based memory management Proof-carrying code and certifying compilation This is not meant to be an exhaustive list; papers on novel utilizations of type information are welcome. Authors concerned about the suitability of a topic are encouraged to inquire via electronic mail to the program chair prior to submission. We solicit submissions on original research not published or submitted for publication elsewhere. Technical summaries, in English and not to exceed 10 pages ACM format, should be submitted via the Web submission form by Sunday, October 1, 2006 5PM Pacific Daylight Savings Time. See what this means in your time zone. Web submission form: https://www.softconf.com/starts/tldi07/ Adobe Portable Document Format (PDF) is strongly preferred for all submissions. Authors should be sure to use full font inclusion to ensure portability. All papers must be formatted for US Letter (8.5"x11") paper. Postscript (PS) format submissions will also be accepted, provided that they preview and print properly using Ghostscript with standard fonts. Important Dates Please note: Due to the short time from submission to publication of the proceedings, the submission deadlines given below are firm. Sunday, October 1, 2006, 5PM PDT Deadline for submission of papers Friday, Nov 10, 2006 Notification of acceptance Friday, Nov 23, 2006 Camera-ready copy due Tuesday, Jan 16, 2007 TLDI'07 in Nice, France Jan 17-19, 2007 POPL'07 in Nice, France Program Chair George Necula University of California 783 Soda Hall Berkeley, CA 94720 Email: necula @ cs.berkeley.edu Tel.: +1-510-643-1481 Fax: +1-510-642-3962 Program Committee Damien Doligez, INRIA Peter Lee, Carnegie Mellon University Andrew Kennedy, Microsoft Research, Cambridge Naoki Kobayashi, Tohoku University George Necula (chair)ty of California, Berkeley Randy Pollack, Edinburgh University Norman Ramsey, Harvard University David Tarditi, Microsoft Research, Redmond Stephanie Weirich, University of Pennsylvania Hongwei Xi, Boston University General Chair Francois Pottier, NRIA Rocquencourt

1 0

Haskell' Status Report
by Doug McIlroy 27 Sep '06

27 Sep '06

One thing jumped out at me from the status report: everything was "add", which reminded me of many old languages designed by accretion. Are the new facilities so perfectly orthogonal as not to subsume anything that was already there? Are none of them simply relaxations of previous limitatations? Parsimony is part of the allure of Haskell. What do the new facilities enable one to discard from the Haskell 98 report? Doug McIlroy

1 0

Haskell Standard: Please email me if you want to join the committee.
by Isaac Jones 27 Sep '06

27 Sep '06

Greetings, As announced at the Haskell Workshop, the Haskell Prime process is running another committee selection round. We are specifically looking for people to write sections of the Haskell Report for the "definitely in" and "probably in" proposals, as described in: http://hackage.haskell.org/trac/haskell-prime/wiki/Status' Please email me if you think you would like to write sections of the report and be on the committee. Please tell me which of the "definitely in" or "probably in" sections you would like to help with writing. Also, anyone interested in the future of the language should sign up for the Haskell Prime mailing list if you aren't already: http://haskell.org/mailman/listinfo/haskell-prime peace, isaac

1 0

compiler-independent core libraries infrastructure
by Bulat Ziganshin 27 Sep '06

27 Sep '06

(i crosspost my letter into main haskell list because i hope that proposed solution is of great interest for (discussion with) many developers) Hello Ian, Friday, September 8, 2006, 5:52:57 AM, you wrote: >> and last question - i don't like inclusion of unix and win32 in a list >> of core libs. why they are here? may be it's possible to include small >> modules with functionality required for compiler itself in GHC.* >> hierarchy and then move the rest into extra libraries? > This doesn't work well for any parts shared with the other compilers. > "core libs" is possibly the wrong name for it - "bootstrapping libs" > might be more appropriate. > Note also that unix and win32 haven't been included in anything they > weren't already, it's just that other libraries (those that are now > called "extra libs") have been taken out. We can always take more out > for 6.8 if we want. thank you - you have cleaned up the situation for me. thanks to Cabal, now ghc is much more modular than 6.4. but it is not yet the ultimate solution and i propose to discuss what we can do in future, possibly even in 6.6.1. i will become devil advocate for a little :) i am, John de MacLee programmer, never planned to build ghc itself and i don't need any bootstrapping libs in my download. please sell it as separate ghc-for-ghc package :) the core-ghc package should then contain only libraries that are dependent on GHC compiler internals (GHC.* part of base, stm and th - and nothing more!) moreover, i want to be able to upgrade even these libraries without upgrading compiler proper. or, to be exact, i may need to install newer versions of these libraries which contains new features and therefore not 100% compatible with libraries shipped at the moment when GHC 6.6.1 was released why this may be impossible? first, because existing libs and programs may rely on older interfaces. i think that Cabal should eventually solve this problem so that multiple version of any lib can be installed on computer (to be exact, on concrete GHC installation) and proper version of library selected for any project. but that's another discussion.. what is a 'base' library now? it is the library that implements common set of operations for latest versions of ghc, hugs and nhc. it contains low-level implementation for ghc, but relies on separate hugsbase package for hugs (the same for nhc, afaiu). so, first step is obvious - separate ghc-base library from the rest. hugsbase, ghc-base and nhc-base packages should provide common set of low-level operations, hiding from other libraries implementation details, differences between compilers, and differences between compiler versions. they should provide _incremental_ interfaces so that old code will continue to work with newer compilers. eventually compiler-specific code for stm and th should also go into these libraries but that is not the immediate goal then, a base library may be written against "virtual Haskell compiler", which provides uniform set of low-level features while 'base' decorates these features with user-friendly interfaces even more interesting variant is to allow ghc-base and other compiler-specific base packages to export non-incremental interfaces and use 'base' solely to "equalize" all compilers to some common interface, providing emulation of all missing features (i think that such emulation will be compiler-independent that means that it's better to put it into compiler-independent package). then, _all_ other libs should rely on version of base package version instead of version of compiler they are use. so: ghc 6.2 ghc 6.2.2 ghc 6.4.3 hugs 2003 .... all supported in base 1.0 package which expose stable interface independent on compiler used. all other libraries relies on this interface and therefore works with any compiler whose support included in base 1.0. as ghc 6.6 rolls out, we add its support to 'base' library, rolling out base-1.0.1. and all libraries written against base 1.0, now will work with ghc 6.6, although they can ignore some features what was not included in base 1.0 API. at the same time, base-2.0 rolled out which includes new APIs (but don't omit old ones!), supporting new features of ghc 6.6. but base 2.0 continues to support existing compilers, providing emulation of new features for old compilers. those developers that need these new features upgrade their cabal files to require base 2.0. those users of old compilers that go to compile these apps download (automatically) and install base-2.0 lib so, i propose: - ghc-base/hugsbase/.. libs to implement _subset_ of common low-level API - base lib to "equalize" several compilers and compiler versions, providing _full_ common low-level API. when we need to include new API, we roll out new major version of base and work hard to support old compilers by providing some emulation of new feature. base lib versions should be independent on compiler versions and as much backward-compatible as possible - all other libs to just specify version of base lib they utilize and be happy and of course we should split base lib into ~10 independent libraries to simplify development and deployment of new features. if i need, say, new ByteString features, i would be very unhappy if i need at the same time to upgrade interface to arrays last line: i have some experience of writing compiler-independent code with Haskell and C++ and believe that this plan is realistic -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

2 3

Haskell Weekly News: September 27, 2006
by dons＠cse.unsw.edu.au 27 Sep '06

27 Sep '06

--------------------------------------------------------------------------- Haskell Weekly News http://haskell.org/haskellwiki/HWN Issue 42 - September 27, 2006 --------------------------------------------------------------------------- Welcome to issue 42 of HWN, a weekly newsletter covering developments in the Haskell community. Each week, new editions are posted to [1]the Haskell mailing list as well as to [2]the Haskell Sequence and [3]Planet Haskell. [4]RSS is also available, and headlines appear on [5]haskell.org. This week we see a new Hugs release, and the results of the ICFP contest are out! We feature a special report on the Commercial Users of Functional Programming workshop, courtesy of John Hughes 1. http://www.haskell.org/mailman/listinfo/haskell 2. http://sequence.complete.org/ 3. http://planet.haskell.org/ 4. http://sequence.complete.org/node/feed 5. http://haskell.org/ Announcements * ICFP Contest Results. CMU's Principles of Programming Group [6]announced the results of this year's [7]ICFP programming contest. Congratulations to the winning team from Google, 'Team Smartass', (Christopher Hendrie, Derek Kisman, Ambrose Feinstein and Daniel Wright), who used Haskell along with C++, Bash and Python. Haskell has now been used by the winning team three years running! An honourable mention to team Lazy Bottoms, another Haskell team, who managed to crack several of the puzzles first. Five teams from the [8]#haskell IRC channel were [9]placed in the top 50. A video stream of the results announcement is [10]available, shot and cut by Malcolm Wallace. Many thanks to the [11]CMU team for organising such a great contest! 6. http://icfpcontest.org/ 7. http://icfp06.cs.uchicago.edu/ 8. http://haskell.org/haskellwiki/IRC_channel 9. http://icfpcontest.org/scoreboard.shtml 10. http://video.google.com/videoplay?docid=6419094369756184531 11. http://www.cs.cmu.edu/afs/cs/Web/Groups/pop/pop.html * New release of Hugs. Ross Paterson [12]announced a new minor release of Hugs, fixing a few bugs with the May 2006 release, and with libraries roughly matching the forthcoming GHC 6.6 release. It is available from [13]the Hugs page. 12. http://article.gmane.org/gmane.comp.lang.haskell.hugs.user/493/ 13. http://www.haskell.org/hugs/ * HAppS version 0.8.2. Einar Karttunen [14]announced the release of the Haskell Application Server version 0.8.2. HAppS is a Haskell web application server for building industrial strength internet applications safely, quickly, and easily. With HAppS you focus entirely on application functionality implemented in your favourite language and you don't have to worry about making sure all sorts of server subsystems are functioning properly. [15]More info. 14. http://article.gmane.org/gmane.comp.lang.haskell.general/14292/ 15. http://happs.org/ * Codec.Compression.GZip and .BZip. Duncan Coutts [16]released two new packages: zlib and bzlib, which provide functions for compression and decompression in the gzip and bzip2 formats, directly on [17]ByteStrings. Both provide pure functions on streams of data represented by lazy ByteStrings. This makes it easy to use either in memory or with disk or network IO. There is API documentation is available [18]here and [19]here. 16. http://article.gmane.org/gmane.comp.lang.haskell.general/14265/ 17. http://www.cse.unsw.edu.au/~dons/fps.html 18. http://haskell.org/~duncan/zlib/docs 19. http://haskell.org/~duncan/bzlib/docs * System Fc branch merged into GHC. Manuel Chakravarty [20]merged the [21]System Fc branch of GHC into GHC head. This is a significant development, adding extensions to GHC to support an [22]FC-based intermediate language, a new implementation of GADTs, along with indexed data types and indexed newtypes (generalised [23]associated data types). [24]More details about the implementation. 20. http://article.gmane.org/gmane.comp.lang.haskell.cvs.all/28297/ 21. http://www.cse.unsw.edu.au/~chak/papers/SCP06.html 22. http://hackage.haskell.org/trac/ghc/wiki/IntermediateTypes 23. http://www.cse.unsw.edu.au/~chak/papers/CKPM05.html 24. http://hackage.haskell.org/trac/ghc/wiki/TypeFunctions * Job writing security software in Haskell. Andrew Pimlott [25]announced that Planning Systems, Inc. has a job opportunity for Haskell programmers, writing a high-assurance authorization system. [26]Job description. 25. http://article.gmane.org/gmane.comp.lang.haskell.cafe/15439/ 26. http://www.plansys.com/careers/job_details.cfm?JobID=28 * Dr Haskell 0.1. Neil Mitchell [27]released Dr Haskell, a tool to help suggest improvements to your Haskell code. Dr Haskell will analyse your code, and suggest shorter alternatives for rewriting. [28]More details. 27. http://article.gmane.org/gmane.comp.lang.haskell.general/14285/ 28. http://www-users.cs.york.ac.uk/~ndm/projects/drhaskell.php * BitSyntax for Haskell. Adam Langley [29]released a [30]bit syntax library for Haskell, based on Erlang's [31]bit syntax (great for building and breaking up binary structures). Nice! 29. http://article.gmane.org/gmane.comp.lang.haskell.general/14287/ 30. http://www.imperialviolet.org/binary/bitsyntax/ 31. http://www.erlang.org/doc/doc-5.4.12/doc/programming_examples/bit_syntax.ht… * File fuzzing. Tim Newsham [32]made available FileH, a Haskell tool for generating test data via random file mutation. [33]More details. 32. http://article.gmane.org/gmane.comp.lang.haskell.cafe/15386/ 33. http://www.isecpartners.com/file_fuzzers.html * A DSL for state machines. Stephane Bortzmeyer [34]announced a Haskell implementation of a proposal to the IETF to standardize [35]a language used for finite state machines (which are common in IETF standards). The reference implementation is [36]available. 34. http://article.gmane.org/gmane.comp.lang.haskell.cafe/15116/ 35. http://www.cosmogol.fr/ 36. http://www.cosmogol.fr/shadok.html * A language tag parser. Stephane Bortzmeyer announced [37]GaBuZoMeu, a set of programs to parse and check [38]language tags (see RFC 4646 produced by the IETF Working Group LTRU - Language Tag Registry Update). 37. http://www.bortzmeyer.org/gabuzomeu-parsing-language-tags.html 38. http://www.iana.org/assignments/language-subtag-registry Haskell' This section covers the [39]Haskell' standardisation process. * [40]'Here' documents 39. http://hackage.haskell.org/trac/haskell-prime 40. http://thread.gmane.org/gmane.comp.lang.haskell.prime/1658/focus=1658 Conference roundup The [41]Commercial Users of Functional Programming workshop (CUFP), held in association with [42]ICFP, attracted a record turn-out this year. 57 attendees came to listen to 9 speakers talk about commercial uses of Scheme, Erlang, Reflect, OCaml, and Haskell. Four of the speakers talked about applications of Haskell. 41. http://www.galois.com/cufp/ 42. http://www.cs.luc.edu/icfp/ * Linspire in Haskell. Clifford Beshers talked about the adoption of Haskell at [43]Linspire. Linspire switched recently from OCaml to Haskell, citing readability, classes, the IO monad, and more complete libraries as reasons. So far CGI scripts and a package autobuilder have been implemented in Haskell. Static typing, and the use of purely functional data structures on disk, have helped make for reliable code. Performance has been generally good, although Parsec parsers proved to be slow on larger files--a problem that was solved using Data.ByteString. Space leaks have not been a problem, perhaps because frequent IO keeps programs strict. Belying the myth that functional programmers are hard to recruit, Linspire's announcement that they were adopting Haskell generated several resumes, despite explicitly stating that they were not recruiting. 43. http://www.linspire.com/ * Haskell programming at Credit Suisse. Howard Mansell talked about Haskell programming at [44]Credit Suisse in New York. This group's business is derivative trading for clients. Valuing complex derivatives is computationally costly, requiring nightly runs on thousands of CPUs. There is a real competitive advantage in being able to build models quickly, since some exotic derivatives may only be traded 10-100 times in total. Previously models were built using Excel, with heavy computations delegated to C++ plugins. Most of the Excel code has now been replaced by Haskell, with Excel just providing the user interface (which in turn is generated by DSELs). The work has been done by [45]Lennart Augustsson and [46]Gabriele Keller, but Credit Suisse needs more Haskell programmers -- they're hiring. 44. http://www.credit-suisse.com/ 45. http://www.cs.chalmers.se/~augustss/ 46. http://www.cse.unsw.edu.au/~keller * Hardware design at Bluespec Inc.. Rishiyur Nikhil talked about [47]Bluespec Inc, which offers System Verilog tools implemented in about 90K loc of Haskell. Bluespec's tools are based on MIT research in the 90s into generating hardware from term rewriting systems; using Bluespec's 'rules' complex hardware can be described at a high level, improving productivity and reducing errors. Selling the tools based on Haskell requires short, punchy examples to convince old hands that there is a better way than writing RTL by hand. Bluespec have started sales, and many more trials are under way. 47. http://www.bluespec.com/ * Aetion, AI and Haskell. Garret Morris talked about Haskell applications at [48]Aetion, which is a defence contractor offering AI applications based on Bayesian nets. Rapidly changing priorities make it important to minimize the code impact of changes, which suits Haskell well. Aetion have developed three main projects in Haskell, all successful. Haskell's concise code was perhaps most important for rewriting: it made it practicable to throw away old code occasionally. DSELs allowed the AI to be specified very declaratively. Less successful was the decision to link Haskell to a GUI in Java: the need to serialize data made it impossible to use functions as representations, which was unfortunate. Other issues included getting libraries to work together, patchy Windows support, and a need for more debugging tools. 48. http://www.aetion.com/ Discussion * Curious Functor class. Ashley Yakeley [49]described the curious class of functors for which foralls can move across. 49. http://article.gmane.org/gmane.comp.lang.haskell.cafe/15447/ * Variadic functions and typeCast. Michael Shulman [50]submitted a general version of the trick to implement variadic functions in Haskell [51]outlined by Oleg 50. http://article.gmane.org/gmane.comp.lang.haskell.cafe/15401/ 51. http://okmij.org/ftp/Haskell/vararg-fn.lhs * Serialising existential types. Misha Aizatulin [52]pondered the interesting problem of serialisation of datatypes with existential constructors. Several options were suggested. 52. http://thread.gmane.org/gmane.comp.lang.haskell.general/14260/focus=14260 * Replacing GMP. Peter Tanski [53]updated the [54]page relating to portably replacing GMP in GHC (and other Haskell systems) 53. http://article.gmane.org/gmane.comp.lang.haskell.glasgow.user/10746 54. http://hackage.haskell.org/trac/ghc/wiki/ReplacingGMPNotes Blog noise Haskell news from the blogosphere. * [55]Lambda abstractions to be added to C++ * [56]Haskell in Ruby: a Ruby Prelude * [57]Google Research announcement of their ICFP teams' results * [58]Some analysis of previous ICFP contest results * [59]Simple unix tools in Haskell * [60]Bazaar vs Darcs * [61]CVS vs Darcs * [62]Adventures in Open Source Erlang * [63]Is functional programming going mainstream? 55. http://www.regdeveloper.co.uk/2006/09/22/cplusplus-lambda-future/ 56. http://cwilliams.textdriven.com/articles/2006/08/29/haskell-in-ruby 57. http://googleresearch.blogspot.com/2006/09/and-awards-go-to.html 58. http://blog.interlinked.org/programming/icfp.html 59. http://haskell.org/haskellwiki/Simple_unix_tools 60. http://www.kdedevelopers.org/node/2024 61. http://mark.stosberg.com/Tech/darcs/cvs_switch/easier.html 62. http://yarivsblog.com/articles/2006/09/01/oo-fp-erlang-and-me 63. http://ifacethoughts.net/2006/09/25/is-functional-programming-going-mainstr… Quotes of the Week * Clifford Beshers : "When we code in Haskell, we go home on time" * Bulat : "There is new Time library, which is supposed to replace old System.Time. We hope that it will happen before 2038" * edwardk : "I should probably just type up the problem specification in Haskell and click compile. Funny how that seems to yield the answer" * vincenz : "OCaml used to be pretty, Haskell made it ugly" * glguy : "I remember what class I was in when I was reading Hudak's book and discovered `fix'. Life altering..." * glguy : "> take 10 $ map length $ fix (([()]:).scanl (++) [()])" * lambdabot : "[1,1,2,3,5,8,13,21,34,55]" * agentzh : "Haskell is really a powerful weapon" * gaal : "You know you've been reading lots of Haskell papers when... someone says '(bbiab, $job)' and you try mentally to run :t on that" * audreyt : "Pugs seems to be just my excuse to apply each and every technique from the GHC changelogs..." * Pseudonym : "[OlegFacts] Oleg solves N P-hard problems in N log N time... in the type system" * dons : "[On improving Cabal dependency handling] fps 0.8 is an exemplary instance of part number fps 0.8. Interestingly, this one is lavender. Also, it is broken: it is (a fps 0.8 missing a base 1.0)." * Mark Bessey : "When really massively-parallel systems start to become more common, the programming model will have to change. What languages you'll likely use to program these beasts is an interesting question - most likely, it'll be a functional language, something like Haskell, or Erlang." * Philippa : "[vincenz] Forget theory, it's about pragmatics [Philippa] we're talking FP, they tend to be the same thing" Contributing to HWN To help create new editions of this newsletter, please see the [64]contributing information. Send stories to dons at cse.unsw.edu.au. The darcs repository is available at darcs get http://www.cse.unsw.edu.au/~dons/code/hwn 64. http://haskell.org/haskellwiki/HWN

1 0

Performance, Optimization and Code Generation
by George Beshers 26 Sep '06

26 Sep '06

This starts out with my being interested in darcs <-> git related issues. Since git uses sha1 I wanted to have the ability to calculate sha1 in an application where I was intending to use darcs as a back-end. The performance gap is > * 30 between Haskell and sha1sum. That seemed rather steep and so I started looking... Using ghc 6.4.2 The following code is from SHA1: -- {-# INLINE step #-} step :: ABCDE -> BS.ByteString -> ABCDE step abcde0@(ABCDE a b c d e) words = abcde5 where s16 = get_word_32s words s80 = s16 ++ (zipWith4 f0) (drop 13 s80) (drop 8 s80) (drop 2 s80) s80 f0 a b c d = rotL (a `xor` b `xor` c `xor` d) 1 (s20_0, s60) = splitAt 20 s80 (s20_1, s40) = splitAt 20 s60 (s20_2, s20) = splitAt 20 s40 (s20_3, _) = splitAt 20 s20 abcde1 = foldl (doit f1 0x5a827999) abcde0 s20_0 abcde2 = foldl (doit f2 0x6ed9eba1) abcde1 s20_1 abcde3 = foldl (doit f3 0x8f1bbcdc) abcde2 s20_2 ABCDE a' b' c' d' e' = foldl (doit f2 0xca62c1d6) abcde3 s20_3 f1 (XYZ x y z) = (x .&. y) .|. ((complement x) .&. z) f2 (XYZ x y z) = x `xor` y `xor` z f3 (XYZ x y z) = (x .&. y) .|. (x .&. z) .|. (y .&. z) abcde5 = ABCDE (a + a') (b + b') (c + c') (d + d') (e + e') -- {-# INLINE get_word_32s #-} get_word_32s :: BS.ByteString -> [Word32] get_word_32s s = map f [0..15] where f i = foldl (+) 0 $ map (\n -> toEnum (fromEnum (BS.index s (i*4+n))) `shiftL` (8 * (3-n))) [0..3] -- {-# INLINE doit #-} doit :: (XYZ -> Word32) -> Word32 -> ABCDE -> Word32 -> ABCDE doit f k (ABCDE a b c d e) w = ABCDE a' a (rotL b 30) c d where a' = rotL a 5 + f (XYZ b c d) + e + w + k -- {-# INLINE rotL #-} rotL :: Word32 -> Rotation -> Word32 rotL a s = shiftL a s .|. shiftL a (s-32) -- rotL a s = a `seq` rotate a s I want to focus on the *rotL* function --- get_word_32s might be faster with a rewrite. Using -prof -auto-all and -P at runtime produced the following summary... COST CENTRE MODULE %time %alloc ticks bytes get_word_32s MySHA1 39.3 35.0 10597 6952614960 rotL MySHA1 22.6 18.5 6089 3682275072 step MySHA1 21.2 24.1 5701 4783669848 doit MySHA1 16.2 21.8 4362 4332088320 As part of a larger program, but the sha1 portion was where 98% of the time went. So * I tried using the built-in "rotate", * I tried inlining, * I tried using -fasm directly * I tried generating C with -O2, * I tried using 'seq' in a number of places. None of this made much difference. Comment, the C code for just rotL would be unsigned int rotate(unsigned int a, int b) { return (a << b) | (a >> (b - 32)); } and the assembler at gcc -O2 is concise and straightforward: .file "rotate.c" .text .p2align 4,,15 .globl rotate .type rotate, @function rotate: pushl %ebp movl %esp, %ebp movl 8(%ebp), %edx movl 12(%ebp), %ecx popl %ebp movl %edx, %eax sall %cl, %eax subl $32, %ecx shrl %cl, %edx orl %edx, %eax ret .size rotate, .-rotate .section .note.GNU-stack,"",@progbits .ident "GCC: (GNU) 3.3.5 (Debian 1:3.3.5-3)" GHC's code on this part is nothing like competitive because of the need for closures --- I think. 1) What approaches to getting the compiler to optimize have I overlooked? Or, how would you change the code to get the compiler to generate better code for rotL? 2) Am I missing an easy way to get strictness on the rotL function? 3) Is there something I am missing that keeps ghc's code from becoming about as concise as gcc -O2? 4) Is the code generator simply not able to handle this? Thanks in advance, George

4 3

Repeated evaluation of a constant value.
by Paul Johnson 26 Sep '06

26 Sep '06

I recently wanted to pass a lookup table around a program. Rather than having something explicitly typed as Map.Map I wrote a function that assembled a Map and then used Map.lookup to return a function, like this: > module Main where > > import qualified Data.Map as Map > import Debug.Trace > > alist :: [(String, Integer)] > alist = map (\i -> (show i, i)) [1..100] > > table :: [(String, Integer)] -> String -> Maybe Integer > table ls str = Map.lookup str fm > where fm = trace "Trace: making the map" $ Map.fromList ls "table" can be seen as a function from an association list to a look-up function. > demo :: [(String, Integer)] -> IO () > demo ls = do > showLookup "5" > showLookup "70" > showLookup "164" > showLookup "wibble" > where > func = table ls > showLookup str = > putStrLn $ "Look up " ++ show str ++ " gives " ++ > show (func str) ++ "." > > main :: IO () > main = demo alist I reasoned that closure returned by "table ls" would contain a thunk for "fm", which in turn would be evaluted the first time it was called. But it isn't: instead "fm" gets evaluated for every call to "table", as shown by the repeated trace messages. Store this message as "Thunk.lhs". Compile with ghc -O2 and run "main". What you get is: Trace: making the map Look up "5" gives Just 5. Trace: making the map Look up "70" gives Just 70. Trace: making the map Look up "164" gives Nothing. Trace: making the map Look up "wibble" gives Nothing. So my question is: how do I write "table" to return a function which does not build the lookup table for every call? Or is this a bug in GHC? (I should add that my real "table" function is rather more complicated, and only invokes Map.lookup on a subset of its arguments.) Paul.

3 3

Integrated Formal Methods 2007: First call for technical papers
by Jeremy.Gibbons＠comlab.ox.ac.uk 26 Sep '06

26 Sep '06

IFM 2007 Sixth International Conference on Integrated Formal Methods 2nd - 6th July 2007, Oxford, UK http://www.ifm2007.org First Call for Technical Papers The design and analysis of computing systems presents a significant challenge: systems need to be understood at many different levels of abstraction, and examined from many different perspectives. Formal methods---languages, tools, and techniques with a sound, mathematical basis---can be used to develop a thorough understanding, and to support rigorous examination. However, further research into effective integration is required if these methods are to have a significant impact outside academia. The IFM series of conferences seeks to promote that research, to bring together the researchers carrying it out, and to disseminate the results of that research among the wider academic and industrial community. Original, technical contributions are invited in all aspects of formal methods integration, including: * the application of one or more formal methods as an integral part of a process of analysis or design * the development or extension of one method, based upon the inclusion of ideas or concepts from others * the addition of formality to informal or semi-formal modelling languages, tools, or techniques * the combination of different formal methods, in terms of semantic integration or practical application The programme of accepted contributions will be supported by a series of workshops and tutorials, including a doctoral symposium. Important dates: The deadline for full paper submission is January 29th, 2007. Authors will be notified on or before March 19th, 2007. Details of the electronic submission process will be made available at the conference website. Conference location: IFM 2007 will be held at St Anne's College, Oxford: one of the larger colleges of the University, with excellent facilities for conferences and workshops. Additional facilities will be available in the new Computing Laboratory building, less than 5 minutes' walk from the College grounds. Oxford is easily reached from most UK cities, and is 70 minutes from the country's largest airport. Programme committee: Didier Bert, Institute IMAG, Grenoble, France Eerke Boiten, University of Kent, UK Jonathan Bowen, Museophile Ltd, UK Michael Butler, University of Southampton, UK Paul Curzon, Queen Mary, University of London, UK Jim Davies, University of Oxford, UK John Derrick, University of Sheffield, UK Steve Dunne, University of Teesside, UK Andy Galloway, University of York, UK Chris George, United Nations University, Macau Jeremy Gibbons, University of Oxford, UK Wolfgang Grieskamp, Microsoft Research, Redmond, US Henri Habrias, University of Nantes, France Maritta Heisel, University of Magdeburg, Germany Soon-Kyeong Kim, University of Queensland, Australia Michel Lemoine, ONERA, Toulouse, France Shaoying Liu, Hosei University, Tokyo, Japan Dominique Mery, LORIA, France Stephan Merz, LORIA, France Richard Paige, University of York, UK Luigia Petre, Turku Centre for Computer Science, Finland Jaco van de Pol, Centre for Mathematics and Computer Science, The Netherlands Judi Romijn, Eindhoven University of Technology, The Netherlands Thomas Santen, Technical University of Berlin, Germany Steve Schneider, University of Surrey, UK Wolfram Schulte, Microsoft Research, Redmond, US Kaisa Sere, Abo Akademi University, Turku, Finland Jane Sinclair, University of Warwick, UK Graeme Smith, University of Queensland, Australia Jin Song Dong, National University of Singapore Bill Stoddart, University of Teesside, UK Kenji Taguchi, National Institute of Informatics, Japan Helen Treharne, University of Surrey, UK Heike Wehrheim, University of Paderborn, Germany Kirsten Winter, University of Queensland, Australia Jim Woodcock, University of York, UK

1 0

ANN: HAppS version 0.8.2
by Einar Karttunen 25 Sep '06

25 Sep '06

We are pleased to announce HAppS -- Haskell Application Server version 0.8.2. HAppS is a Haskell web application server for building industrial strength Internet applications safely, quickly, and easily. With HAppS you focus entirely on application functionality implemented in your favorite language and you don't have to worry about making sure all sorts of server subsystems are functioning properly. This release has the following highlights: * Switch to BSD3 license. * Support for new ByteString. * Support GHC 6.6 (using the HAppS.cabal.ghc66) * Good support for cookies. * Revise HAppS.DNS and make it easier to access from the outside. * Much faster URI parsing. * Many internal changes to HTTP and Saver implementations. * Add new examples: cookie, dns, http. HAppS can be obtained from http://happs.org/ or directly from: * http://happs.org/auto/HAppS-0.8.2.tar.gz * darcs get --partial --tag=HAppS-0.8.2 http://happs.org/HAppS Einar Karttunen, Alex Jacobson, David Himmelstrup

1 0