Welcome to the eleventh edition of the Haskell Communities and Activities Report – a collection of entries about everything that is going on and related to Haskell in some way that appears twice a year.
This time, there was a rather long delay between the submission deadline and the actual publication. I apologize for any entries that are already outdated now due to this delay and promise that I will try to keep this time shorter for the next edition.
I have looked at the total number of entries in all the reports and discovered that the report has been continuously growing until the 11/2005 edition, which had 149 entries. After that, there was a decline: the 06/2005 edition had 144 entries, and the current 11/2006 edition has only 134 entries.
How and why do entries get removed? Generally, entries have to be updated every time for inclusion in the report. If I do not hear back from the author of an entry or there are no updates, but the entry seems still up-to-date, I keep it around for the next edition. But every entry should be updated in a more or less significant way at least once per year, otherwise it is removed. The idea of this Report is to document the current state of the communities, after all, and of course an old entry can be revived if there is activity again.
I hope that the recent decline in entries is a temporary phenomenon and not the beginning of a long-term trend. All the more, I want to thank all the authors who have found the time to update their entries or provide new reports! As always, I have enjoyed putting everything together and reading about all the exciting new developments.
There are certainly some projects that are missing from this Report. When I am aware of a certain project or a recent development, I often try to encourage the authors to submit in time, but I also rely on you, the readers, to ask missing projects to provide information for the next edition, or to write about your own project. Do not worry about whether your project is adequate: If it has anything to do with Haskell at all, there is a place for it in the Report.
Please mark the final weeks of April in your calendar, because that is when the entries for the May edition will be collected.
As always, feedback is very welcome <hcar at haskell.org>. Enjoy the Report!
Andres Löh, University of Bonn, Germany
HaskellWiki is a MediaWiki installation now running on haskell.org, including the haskell.org “front page”. Anyone can create an account and edit and create pages. Examples of content include:
We encourage people to create pages to describe and advertise their own Haskell projects, as well as add to and improve the existing content. All content is submitted and available under a “simple permissive” license (except for a few legacy pages).
In addition to HaskellWiki, the haskell.org website hosts some ordinary HTTP directories. The machine also hosts mailing lists. There is plenty of space and processing power for just about anything that people would want to do there: if you have an idea for which HaskellWiki is insufficient, contact the maintainers, John Peterson and Olaf Chitil, to get access to this machine.
The #haskell IRC channel is a real-time text chat where anyone can join to discuss Haskell. The channel has grown substantially in users over the last 6 months, and now #haskell averages over 240 concurrent users. Point your IRC client to irc.freenode.net and join the #haskell conversation!
For non-English conversations about Haskell there is now:
Related Haskell channels are now emerging, including:
More details at the #haskell home page: http://haskell.org/haskellwiki/IRC_channel
Planet Haskell is an aggregator of Haskell people’s blogs and other Haskell-related news sites. As of mid-October content from 29 blogs and other sites is being republished in a common format.
A common misunderstanding about Planet Haskell is that it republishes only Haskell content. That is not its mission. A Planet shows what is happening in the community, what people are thinking about or doing. Thus Planets tend to contain a fair bit of “off-topic” material. Think of it as a feature, not a bug.
A blog is eligible to Planet if it is being written by somebody who is active in the Haskell community, or by a Haskell celebrity; also eligible are blogs that discuss Haskell-related matters frequently, and blogs that are dedicated to a Haskell topic (such as a software project written in Haskell). Note that at least one of these conditions must apply, and virtually no blog satisfies them all. However, blogs will not be added to Planet without the blog author’s consent.
To get a blog added, email Antti-Juhani Kaijanaho <antti-juhani at kaijanaho.fi> and provide evidence that the blog author consents to this (easiest is to get the author send the email, but any credible method suffices).
Planet is hosted by Galois Connections, Inc. (→7.1.2) as a service to the community. The Planet maintainer is not affiliated with them.
The Haskell Weekly News (HWN) is a weekly newsletter covering developments in Haskell. Content includes announcements of new projects, discussions from the various Haskell communities, notable project commit messages, Haskell in the blogspace, and more.
It is published in html form on The Haskell Sequence, via mail on the Haskell mailing list, on Planet Haskell (→1.3), and via RSS. Headlines are published on haskell.org (→1.1). The Haskell Weekly News is also available in Spanish translation.
http://www.haskell.org/haskellwiki/Haskell_Weekly_News
“Hitchhickers Guide to Haskell” is a tutorial aimed to provide a “quick start into Haskell” for programmers with solid experience of other languages under their belt. Instead of “side by side” comparison between Haskell and another language of choice (like C or Java), the tutorial is built around case studies, which show how typical tasks are performed in Haskell.
This is work in progress, only 5 chapters have been written so far.
The tutorial is available on the Haskell wiki (URL below) or from the darcs repository at http://adept.linux.kiev.ua/repos/hhgtth.
Right now I am collecting ideas for subsequent chapters, so any feedback from readers is appreciated more than ever.
http://www.haskell.org/haskellwiki/Hitchhikers_guide_to_Haskell
Haskell is one of the leading languages for teaching functional programming, enabling students to write simpler and cleaner code, and to learn how to structure and reason about programs. This introduction is ideal for beginners: it requires no previous programming experience and all concepts are explained from first principles via carefully chosen examples. Each chapter includes exercises that range from the straightforward to extended projects, plus suggestions for further reading on more advanced topics. The presentation is clear and simple, and benefits from having been refined and class-tested over several years.
Features:
Publication details:
Further information:
The Haskell wikibook is an attempt to build a community textbook that is at once free (in cost and remixability), comprehensive and cohesive.
Since the last report, we have overhauled the front page and first few three chapters, and added chapters on advanced topics such as laziness and existential types. We have also been importing a very large amount of content from outside sources, selected pieces of Haskell wiki for starters, as well as the entirety of the excellent tutorials Write Yourself a Scheme in 48 Hours by Johnathan Tang and Yet Another Haskell Tutorial by Hal DauméIII. Thanks to all authors, outsiders and wikibook natives alike. As a result of your generous donations, we now have enough content to meet the basic needs for our readers.
Our main focus will thus be on cleaning up what we have and merging it all into a single textbook.
| Report by: | Diego Navarro (syntaxfree on #haskell) |
| Status: | published online, open to suggestions, translation to english pending |
“Two weights, two measures” is a Haskell tutorial focusing on the construction of a very simple DSEL for a fictional prison system exploiting the structure of the Either type (with a few proposed extensions). Its target audience is beginning programmers. The tutorial aims to explore the first steps of how closures/combinators/higher-order functions can be used to define domain specific languages for simple algebraic structures. It’s currently available only in portuguese, but it should be translated at some point.
The full text can be found at the URL below.
“An introduction to Haskell with autophagic snakes” is a Haskell tutorial focusing on the exploration of co-recursive sequences using infinite lists in Haskell. Its target audience is beginning programmers. The tutorial aims to exempllify lazy evaluation and simple combinators to abstract repetitive structures in the corecursive definitions of sequences. It’s currently available only in portuguese, but it should be translated at some point.
The full text can be found at the URL below.
The survey "Realization of Natural-Language Interfaces Using Lazy Functional Programming" is scheduled to be published in ACM Computing Surveys in December 2006. If I have missed any relevant publications, please contact me at rfrost@cogeco.ca. It may be possible to add references before the survey goes to print. If not, I shall put new references on a web page which I am creating to keep the survey up-to-date with future work.
A draft of the survey is available at: http://cs.uwindsor.ca/~richard/PUBLICATIONS/NLI_LFP_SURVEY_DRAFT.pdf
GHC is in good shape. We have no good way to measure how many GHC users there are but if the traffic on the GHC mailing lists is anything to go by, the numbers are increasing quite rapidly. Indeed, GHC was rapidly becoming a success-disaster, so that we (Simon & Simon) were becoming swamped in GHC-related mail. Happily, Microsoft Research has agreed to fund a full-time support engineer, in the form of Ian Lynagh (Igloo), who has already made a huge difference.
A highlight of the last six months was the GHC Hackathon, which we ran a immediately before ICFP in Portland, with wonderful support from Galois and Portland State University. Forty-plus people showed up to have GHC’s innards inflicted on them, and appeared unharmed by the experience.
A significant outcome is that we have written a great deal of Wiki material about GHC’s implementation (the “commentary”) and about how to build and modify GHC (the “building guide”). Documents with these titles were available before but had become rather out of date. These new, up-to-date documents live on the GHC developer’s Wiki. We urge you to read and improve them: http://hackage.haskell.org/trac/ghc/wiki (near the bottom).
We (finally) released GHC 6.6 in October 2006. To get GHC 6.6, go to the Download page (http://www.haskell.org/ghc/download_ghc_66.html). There was an extended period of release-candidate testing, so we fondly hope that this will be a relatively stable release. There are many improvements, all listed in the Release notes http://haskell.org/ghc/docs/6.6/html/users_guide/release-6-6.html. The most important new features include:
Life still goes on and there is current development version (HEAD), that will ultimately become GHC 6.8. You can find binary snapshots at the download page http://www.haskell.org/ghc/dist/current/dist/ or build from sources available via the darcs repository (http://darcs.haskell.org/ghc/). This version already includes significant new features:
If you want to know today’s state-of-the-art, you should check the GHC 6.8 status page at http://haskell.org/haskellwiki/GHC/6.8. At this moment we are working on the following features which are planned to be included in GHC 6.8 in next few months:
The September 2006 release of Hugs fixes a few bugs found in the previous release, and updates the libraries to approximately match those of GHC 6.6, which was about to release at the time. The Windows build is now largely automated, thanks to Neil Mitchell, so it is easier to produce more frequent releases.
As with the previous release, the source distribution is available in two forms: a huge omnibus bundle containing the Hugs programs and lots of useful libraries, or a minimal bundle, with most of the libraries hived off as separate Cabal packages. We hope that more library packages will be released independently, so that Hugs will become less reliant on development snapshots.
Obsolete non-hierarchical libraries will be removed in the next major release.
As ever, volunteers are welcome.
nhc98 is a small, easy to install, compiler for Haskell’98. Despite rumours to the contrary, nhc98 is still very much alive and working, although it does not see any new development these days. The current public release is version 1.18, with a new release expected soon for compatibility with ghc-6.6 and the re-arranged hierarchical libraries. We recently moved over to a darcs repo for maintenance.
The Yhc (→2.4) fork of nhc98 is also making good progress.
The York Haskell Compiler (yhc) is a fork of the nhc98 (→2.3) compiler, with goals such as increased portability, platform independent bytecode, integrated Hat support and generally being a cleaner code base to work with. Yhc now compiles and runs almost all Haskell 98 programs, has basic FFI support – the main thing missing is haskell.org base libraries, which is being worked on.
Since that last HCAR a lot of work has been put in place on the infrastructure of the project – we now have a new build system, nightly builds, automated testing, snapshot releases, wiki documentation, a haskell.org darcs repository. There has also been a focus on creating libraries to allow programmers to reuse some of the work done by Yhc – in particular Yhc.ByteCode and Yhc.Core.
Going forward our focus is to support the haskell.org base libraries, get full Cabal support, enhance our Yhc.* libraries, refactor everything and to support Haskell’ fully.
http://www.haskell.org/haskellwiki/Yhc
| Report by: | Anthony Sloane |
| Participants: | Michael Olney |
| Status: | unreleased |
The project at Macquarie University (→7.3.5) to run Haskell on handheld devices based on Palm OS is close to producing a working implementation for experimentation. Our port of the yhc (→2.4) runtime is now running small examples on simulators and real devices. We are currently testing with larger GUI-based programs. We expect to make a public alpha release sometime in the (southern) summer.
| Report by: | Keith Hanna |
| Status: | active (first release: November 2005) |
Pivotal 0.025 is a very early prototype of a Vital-like environment for Haskell. Unlike Vital, however, Pivotal is implemented entirely in Haskell. The implementation is based on the use of the hs-plugins library (→4.4.1) to allow dynamic compilation and evaluation of Haskell expressions together with the gtk2hs library (→4.8.2) for implementing the GUI.
At present, the implementation is only in a skeletal state but, nevertheless, it provides some useful functionality. The Pivotal web site provides an overview of its principles of operation, a selection of screen shots (including a section illustrating image transforms in the complex plane), and a (very preliminary!) release of the Haskell code for the system.
A more extensive implementation (based on the use of the GHC API (→2.1) for reflection, in place of the hs-plugins (→4.4.1) mechanism) is planned as soon as the required hooks are available in GHC 6.6.
The Camila project explores how concepts from the VDM++ specification language and the functional programming language Haskell can be combined. On one hand, it includes experiments of expressing VDM’s data types (e.g. maps, sets, sequences), data type invariants, pre- and post-conditions, and such within the Haskell language. On the other hand, it includes the translation of VDM specifications into Haskell programs. Moreover, the use of the OOHaskell library (→4.6.6) allows the definition of classes and objects and enables important features such as inheritance. In the near future, support for parallelism and automatic translation of VDM++ specifications into Haskell will be added to the libraries.
Camila goes beyond VDM++ and has support for modelling software components. The work done until now in this field is concerned with rendering and prototyping (coalgebraic models of) software components in Camila. To encourage the use of this technology we have developed a tool to generate components from Camila specifications. The advantage of component based development is that it makes possible to construct complex software from simple pre-existing building blocks. So we have also animated an algebra of components to compose them in several ways. Finally a way to animate components was also implemented.
Two implementation strategies were devised: one in terms of a direct encoding in “plain” Haskell, another resorting to type-level programming techniques, the latter offered interesting particularities.
The web site of Camila (http://wiki.di.uminho.pt/wiki/bin/view/PURe/Camila) provides documentation. Both library and tool are distributed as part of the UMinho Haskell Libraries and Tools.
HASP is a fork of Niklas Broberg’s Haskell Server Pages. Changes includes:
Some of the features implemented in HASP will be ported back into the main HSP tree. However, experimental features like byte code generation via the GHC api will most likely stay in HASP.
http://darcs.haskell.org/~lemmih/hasp/
| Report by: | Phil Trinder |
| Participants: | Phil Trinder, Abyd Al Zain, Greg Michaelson, Kevin Hammond, Yang Yang, Jost Berthold, Murray Gross |
A complete, GHC-based implementation of the parallel Haskell extension GpH and of evaluation strategies is available. Extensions of the runtime-system and language to improve performance and support new platforms are under development.
Al Zain A. Implementing High-Level Parallelism on Computational Grids, PhD Thesis, Heriot-Watt University, 2006.
Al Zain A. Trinder P.W. Loidl H.W. Michaelson G.J. Managing Heterogeneity in a Grid Parallel Haskell, Journal of Scalable Computing: Practice and Experience 7(3), (September 2006).
The GUM implementation of GpH is available in three development branches.
Our main hardware platform are Intel-based Beowulf clusters. Work on ports to other architectures is also moving on (and available on request):
http://www.macs.hw.ac.uk/~dsg/gph/
ftp://ftp.macs.hw.ac.uk/pub/gph/gum-4.06-snap-i386-unknown-linux.tar
<gph at macs.hw.ac.uk>, <mgross at dorsai.org>
| Report by: | Phil Trinder |
| Participants: | Phil Trinder, Hans-Wolfgang Loidl, Jan Henry Nyström, Robert Pointon |
GdH supports distributed stateful interactions on multiple locations. It is a conservative extension of both Concurrent Haskell and GpH (→3.2.1), enabling the distribution of the stateful IO threads of the former on the multiple locations of the latter. The programming model includes forking stateful threads on remote locations, explicit communication over channels, and distributed exception handling.
An alpha-release of the GdH implementation is available on request <gph at macs.hw.ac.uk>. It shares substantial components of the GUM implementation of GpH (Glasgow parallel Haskell) (→3.2.1).
Nystrom J.H. Trinder P.W. King D.J. Are High-level Languages suitable for Robust Telecoms Software? Proc. 24th Int. Conference on Computer Safety, Reliability and Security (SAFECOMP’05), Fredrikstad, Norway (September 2005).
http://www.macs.hw.ac.uk/~dsg/telecoms/publications/SafeComp2005.pdf Nystrom, J.H., Trinder, P.W., King,D.J. A Comparative Evaluation of Three High-level Distributed Languages for Telecoms Software. In preparation.
Eden has been jointly developed by two groups at Philipps Universität Marburg, Germany and Universidad Complutense de Madrid, Spain. The project has been ongoing since 1996. Currently, the team consists of the following people:
Eden extends Haskell with a small set of syntactic constructs for explicit process specification and creation. While providing enough control to implement parallel algorithms efficiently, it frees the programmer from the tedious task of managing low-level details by introducing automatic communication (via head-strict lazy lists), synchronisation, and process handling.
Eden’s main constructs are process abstractions and process instantiations. The function process :: (a -> b) -> Process a b embeds a function of type (a -> b) into a process abstraction of type Process a b which, when instantiated, will be executed in parallel. Process instantiation is expressed by the predefined infix operator ( # ) :: Process a b -> a -> b. Higher-level coordination is achieved by defining skeletons, ranging from a simple parallel map to sophisticated replicated-worker schemes. They have been used to parallelise a set of non-trivial benchmark programs.
Rita Loogen, Yolanda Ortega-Mallén and Ricardo Peña: Parallel Functional Programming in Eden, Journal of Functional Programming 15(3), 2005, pages 431–475.
A major revision of the parallel Eden runtime environment for GHC 6.5 is available. Support for Glasgow parallel Haskell (GpH) is currently being added to this version of the runtime environment. It is planned for the future to maintain a common parallel runtime environment for Eden, GpH and other parallel Haskells.
Epigram is a prototype dependently typed functional programming language, equipped with an interactive editing and typechecking environment. High-level Epigram source code elaborates into a dependent type theory based on Zhaohui Luo’s UTT. The definition of Epigram, together with its elaboration rules, may be found in ‘The view from the left’ by Conor McBride and James McKinna (JFP 14 (1)).
Simply typed languages have the property that any subexpression of a well typed program may be replaced by another of the same type. Such type systems may guarantee that your program won’t crash your computer, but the simple fact that True and False are always interchangeable inhibits the expression of stronger guarantees. Epigram is an experiment in freedom from this compulsory ignorance.
Specifically, Epigram is designed to support programming with inductive datatype families indexed by data. Examples include matrices indexed by their dimensions, expressions indexed by their types, search trees indexed by their bounds. In many ways, these datatype families are the progenitors of Haskell’s GADTs, but indexing by data provides both a conceptual simplification – the dimensions of a matrix are numbers – and a new way to allow data to stand as evidence for the properties of other data. It is no good representing sorted lists if comparison does not produce evidence of ordering. It is no good writing a type-safe interpreter if one’s typechecking algorithm cannot produce well-typed terms.
Programming with evidence lies at the heart of Epigram’s design. Epigram generalises constructor pattern matching by allowing types resembling induction principles to express as how the inspection of data may affect both the flow of control at run time and the text and type of the program in the editor. Epigram extracts patterns from induction principles and induction principles from inductive datatype families.
Whilst at Durham, Conor McBride developed the Epigram prototype in Haskell, interfacing with the xemacs editor. Nowadays, a team of willing workers at the University of Nottingham are developing a new version of Epigram, incorporating both significant improvements over the previous version and experimental features subject to active research.
The Epigram system is also being used successfully by Thorsten Altenkirch, and more recently Conor McBride, in an undergraduate course on Computer Aided Formal Reasoning for two years http://www.e-pig.org/darcs/g5bcfr/. Several final year students have successfully completed projects that involved both new applications of and useful contributions to Epigram.
Peter Morris is working on how to build the datatype system of Epigram from a universe of containers. This technology would enable datatype generic programming from the ground up. Central to these ideas is the concept of indexed container that has been developed recently. There are ongoing efforts to elaborate the ideas in Edwin Brady’s PhD thesis about efficiently compiling dependently typed programming languages.
We have started writing a stand-alone editor for Epigram using Gtk2Hs (→4.8.2). Thanks to a most helpful visit from Duncan Coutts and Axel Simon, two leading Gtk2Hs developers, we now have the beginnings of a structure editor for Epigram 2. For the moment, we are also looking into a cheap terminal front-end.
There has also been steady progress on Epigram 2 itself. Most of the recent progress has been on the type theoretic basis underpinning Epigram. A new representation of the core syntax has been designed to facilitate bidirectional type checking. The semantics of individual terms are glued to their syntactical representation. We have started implementing observational equality, combining the benefits of both intensional and extensional notions of equality. The lion’s share of the core theory has already been implemented, but there is still plenty of work to do.
Whilst Epigram seeks to open new possibilities for the future of strongly typed functional programming, its implementation benefits considerably from the present state of the art. Our implementation makes considerable use of applicative functors, higher-kind polymorphism and type classes. Moreover, its denotational approach translates Epigram’s lambda-calculus directly into Haskell’s. On a more practical note, we have recently shifted to the darcs version control system and cabal framework.
Epigram source code and related research papers can be found on the web at http://www.e-pig.org and its community of experimental users communicate via the mailing list <epigram at durham.ac.uk>. The current implementation is naive in design and slow in practice, but it is adequate to exhibit small examples of Epigram’s possibilities. The new implementation will be much less rudimentary. At the moment, there is direct low-level interface to the state of the proof state called Ecce. Its documentation, together with other Epigram 2 design documents, can be found at http://www.e-pig.org/epilogue/.
Chameleon is a Haskell style language which integrates sophisticated reasoning capabilities into a programming language via its CHR programmable type system. Thus, we can program novel type system applications in terms of CHRs which previously required special-purpose systems.
A new version of Chameleon including examples and documentation is available via http://taichi.ddns.comp.nus.edu.sg/taichiwiki/ChameleonHomePage
XHaskell is an extension of Haskell with XDuce style regular expression types and regular expression pattern matching. We have much improved the implementation which can found under the XHaskell home-page.
A new version of XHaskell including examples and documentation is available via http://taichi.ddns.comp.nus.edu.sg/taichiwiki/XhaskellHomePage
| Report by: | Martin Sulzmann |
| Participants: | Edmund S. L. Lam and Martin Sulzmann |
ADOM is an agent-oriented extension of Haskell with a unique approach to the implementation of cognitive Belief-Desire-Intention (BDI) agents. In ADOM, agent reasoning operations are viewed as monadic computations. Agent reasoning operations can be stratified: Low-level reasoning operations involve the agents beliefs and actions whereas high-level reasoning operations involve the agents goals and plans. Monads allow us to compose various levels of reasoning together, while maintaining clear and distinct separation between the different levels. ADOM can be used directly as an agent-oriented domain specific language, or used to build more higher level BDI agent abstractions on top of it (eg. AgentSpeak, 3APL). ADOM also introduces the use of Constraint Handling Rules (CHR), embedded with Haskell, to directly model the agent’s belief of its dynamically changing domain (world) and it’s actions which invoke change to it’s domain. The key advantage of our approach are:
More information on ADOM can be found here http://taichi.ddns.comp.nus.edu.sg/taichiwiki/ADOMHomePage
| Report by: | Atze Dijkstra |
| Participants: | Atze Dijkstra, Jeroen Fokker, Arie Middelkoop, Doaitse Swierstra |
| Status: | active development |
The purpose of the EHC project is to provide a description of a Haskell compiler which is as understandable as possible so it can be used for education as well as research.
For its description an Attribute Grammar system (AG) (→4.3.1) is used as well as other formalisms allowing compact notation like parser combinators. For the description of type rules, and the generation of an AG implementation for those type rules, we use the Ruler system (→5.5.2) (included in the EHC project).
The EHC project also tackles other issues:
Currently EHC already incorporates more advanced features like higher-ranked polymorphism, partial type signatures, class system, explicit passing of implicit parameters (i.e. class instances), extensible records, kind polymorphism.
Part of the description of the series of EH compilers is available as a PhD thesis, which incorporates previously published material on the EHC project.
The compiler is used for small student projects as well as larger experiments such as the incorporation of an Attribute Grammar system.
We are currently working on the following:
http://www.cs.uu.nl/groups/ST/Ehc/WebHome
http://www.cs.uu.nl/wiki/HUT/AttributeGrammarSystem
http://www.cs.uu.nl/wiki/HUT/ParserCombinators
Urban Boquist, Code Optimisation Techniques for Lazy Functional Languages, PhD Thesis, Chalmers University of Technology 1999
| Report by: | Arie Middelkoop |
| Participants: | Arie Middelkoop, Jurriaan Hage |
| Status: | Prototype finished |
Uniqueness typing is a type system feature of the functional programming language Clean to identify unique values. The space these values occupy can be recycled directly after their only use, thus enabling a form of static garbage collection that greatly improves the efficiency of functional programs. Our goal is to take this idea, and use it to produce more efficient Haskell code.
This project consists of two parts: an analysis to determine which values are unique (front-end), and a code specializer that uses the analysis results to optimize memory management (back-end). We did focus on the front-end part and implemented a prototype using the Essential Haskell (→3.3.5) project as a research vehicle. Code generation is ongoing work of the Essential Haskell project, and we intent to integrate the results of the uniqueness analysis in a later phase.
Our uniqueness analyzer works as follows. Each type constructor of a well-typed program is annotated with a fresh identifier called the uniqueness annotation. From the structure of the AST, we generate a bunch of constraints between these annotations. Solving the constraints gives a local reference count (taking the current slice of the program into account) and global reference count (taking the whole program into account) of each annotation. The global reference count is constructed from the local reference counts and serves as an approximation of an upper bound to the actual usage of a value. (Sub)values that end up with an upper bound are considered unique, others are shared.
http://abaris.zoo.cs.uu.nl:8080/wiki/pub/Top/Publications/uniqueness.pdf
https://svn.cs.uu.nl:12443/repos/EHC/branches/uniqueness/EHC/
A set of type and other extensions to a Haskell-derived language to support the general notion of Object-Oriented programming. An interpreter is under construction to provide a programming environment. No public release is currently available as the system is not yet usable.
| Report by: | Andrew Butterfield |
| Participants: | Andrew Butterfield, Glenn Strong, Malcolm Dowse |
| Status: | ongoing |
We are particularly interested in formal models of the external effects of I/O in pure lazy functional languages. The emphasis is on reasoning about how programs affect their environment, rather than the issue of which programs have identical I/O behaviour.
Software development often consists of designing a (set of mutually recursive) datatype(s), to which functionality is added. Some functionality is datatype specific, other functionality is defined on almost all datatypes, and only depends on the type structure of the datatype.
Examples of generic (or polytypic) functionality defined on almost all datatypes are the functions that can be derived in Haskell using the deriving construct, storing a value in a database, editing a value, comparing two values for equality, pretty-printing a value, etc. Another kind of generic function is a function that traverses its argument, and only performs an action at a small part of its argument. A function that works on many datatypes is called a generic function.
There are at least two approaches to generic programming: use a preprocessor to generate instances of generic functions on some given datatypes, or extend a programming language with the possibility to define generic functions. The techniques behind some of these ideas are given in a separate subsection. In Comparing approaches to generic programming in Haskell (in the lecture notes of the Spring School on Datatype-Generic Programming 2006, held in Nottingham, April 2006, to appear in LNCS), Ralf Hinze, Johan Jeuring and Andres Löh compare 8 different approaches to generic programming in Haskell, both lightweight approaches and language extensions. Most of the approaches discussed in this and previous versions of the Communities report are addressed. In the same set of lecture notes, Jeremy Gibbons discusses the various interpretations of the word ‘generic’.
DrIFT is a preprocessor which generates instances of generic functions. It is used in Strafunski to generate a framework for generic programming on terms. New releases appear regularly, the latest is 2.2.0 from April 2006.
Light-weight generic programming There are a number of approaches to light-weight generic programming.
Generic functions for data type traversals can (almost) be written in Haskell itself (using many of the extensions of Haskell provided by GHC), as shown by Ralf Lämmel and Simon Peyton Jones in the ‘Scrap your boilerplate’ (SYB) approach (http://www.cs.vu.nl/boilerplate/). The SYB approach to generic programming in Haskell has been further elaborated in the recently published (in FLOPS ’06) paper “Scrap Your Boilerplate” Reloaded and “Scrap Your Boilerplate” Revolutions (to appear in MPC’06). In these papers Ralf Hinze, Andres Löh, and Bruno Oliveira show, amongst others, how by viewing the SYB approach in a particular way, the choice of basic operators becomes obvious.
In Open data types and open functions (to appear at PPDP’06), Andres Löh and Ralf Hinze propose to add extensible data types to Haskell, and they show how to use these extensible data types to implement generic functions in a light-weight approach to generic programming.
In Generics as a Library, Bruno Oliveira, Ralf Hinze and Andres Löh show how to extend Ralf Hinze’s “Generic for the Masses” approach to be able to extend generic functions with ad-hoc behaviour for new data types.
Finally, in Generic programming, NOW! (in the lecture notes of the Spring School on Datatype-Generic Programming 2006, held in Nottingham, April 2006, to appear in LNCS), Ralf Hinze and Andres Löh show how GADTs can be used to implement many of the lightweight approaches to generic programming directly in Haskell.
Generic Haskell In Generic views on data types (to appear in MPC’06) Stefan Holdermans, Johan Jeuring, Andres Löh, and Alexey Rodriguez show how to add views on data types to Generic Haskell. Using these views, typical fixed-point functions such as determining the recursive children of a constructor of a recursive data type can be combined with the usual Generic Haskell programs in a single program. The Generic Haskell compiler has been extended with views (available via svn).
Other In Generic Programming with Sized Types (to appear in MPC’06), Andreas Abel defines a generic programming language in which you can only define terminating generic programs, by adding sizes to types.
In iData for the World Wide Web: programming interconnected web forms (in FLOPS’06), Rinus Plasmeijer and Peter Achten show how to use the generic programming extension of Clean for implementing web forms.
Jeremy Gibbons’ tutorial Design Patterns as Higher-Order Datatype-Generic Programs from ECOOP and OOPSLA 2005 has been written up as a paper, http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/#hodgp. He and Bruno Oliveira have also written about The Essence of the Iterator Pattern as a higher-order datatype-generic program (http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/#iterator), in terms of McBride and Paterson’s idioms or applicative functors.
The Spring School on Datatype-Generic Programming has taken place in Nottingham, UK, April 23 - 26, see http://www.cs.nott.ac.uk/ssdgp2006/. There were lectures about comparing approaches to generic programming in Haskell, generic programming in Haskell using GADTs, the implementation of patterns as generic programs, generic programming in Omega (a Haskell-like functional programming language with a limited form of dependent types), and in Epigram (→3.3.1) (a dependently typed programming language).
Thanks to Cabal, we can now easily upgrade any installed library to a new version. There is only one exception: the Base library is closely tied to compiler internals, so you cannot use the Base library shipped with GHC 6.4 in GHC 6.6 and vice versa.
The Core library is a project of dividing the Base library into two parts – a small compiler-specific one (the Core library proper) and the rest – a new, compiler-independent Base library that uses only services provided by the Core lib.
Then, any version of the Base library can be used with any version of the Core library, i.e. with any compiler. Moreover, it means that the Base library will become available for the new compilers, like yhc (→2.4) and jhc – this will require adding to the Core lib only a small amount of code implementing low-level compiler-specific functionality.
The Core library consists of directories GhcCore, HugsCore … implementing compiler-specific functionality and Core directory providing common interface to this functionality, so that external libs should import only Core.* modules in order to be compiler-independent.
In practice, the implementation of the Core lib became a refactoring of the GHC.* modules by splitting them into GHC-specific and compiler-independent parts. Adding implementations of compiler-specific parts for other compilers will allow us to compile the refactored Base library with any compiler, including old versions of GHC. At this moment, the following modules were succesfully refactored: GHC.Arr, GHC.Base, GHC.Enum, GHC.Float, GHC.List, GHC.Num, GHC.Real, GHC.Show, GHC.ST, GHC.STRef; the next step is to refactor IO functionality.
http://haskell.org/haskellwiki/Library/Core
<Bulat.Ziganshin at gmail.com>
| Report by: | Martin Erwig |
| Status: | mostly stable, not maintained |
The PFP library is a collection of modules for Haskell that facilitates probabilistic functional programming, that is, programming with stochastic values. The probabilistic functional programming approach is based on a data type for representing distributions. A distribution represent the outcome of a probabilistic event as a collection of all possible values, tagged with their likelihood.
A nice aspect of this system is that simulations can be specified independently from their method of execution. That is, we can either fully simulate or randomize any simulation without altering the code which defines it.
The library was developed as part of a simulation project with biologists and genome researchers. We originally had planned to apply the library to more examples in this area, however, the student working in this area has left, so this project is currently in limbo.
No changes since the last report.
| Report by: | Marnix Klooster |
| Status: | Hmm 0.2 released, slow-paced development |
Hmm is a small Haskell library to parse and verify Metamath databases.
Metamath (http://metamath.org) was conceived and almost completely implemented by Norman Megill. It a project for formalizing mathematics, a file format for specifying machine-checkable proofs, and a program for generating and verifying this file format. Already more than 7500 proofs have been verified from the axioms of set theory.
Version 0.2 of Hmm has been released on October 28th, 2005.
The development version can be found at http://www.solcon.nl/mklooster/repos/hmm/. This is a darcs repository (→6.4).
Hmm can’t currently do more than just read and verify a Metamath file. However, the longer-term goal is to generate calculational proofs from Metamath proofs. As an example, the Metamath proof that cross-product distributes over union (see http://us.metamath.org/mpegif/xpundi.html) could be visualized something like this:
I am working towards this goal, slowly and step by step.
GSLHaskell is a high level functional interface to linear algebra and other numerical computations internally implemented using GSL and LAPACK. The goal is to achieve the functionality and performance of GNU-Octave or similar system s. The library is still very incomplete, but it has already been useful in a few elementary pattern recognition and computer vision applications.
Recent developments include a simplification of the interface and improved linear algebra based on LAPACK.
| Report by: | Frederik Eaton |
| Status: | unstable; actively maintained |
The index aware linear algebra library is a Haskell interface to a set of common vector and matrix operations. The interface exposes index types and ranges to the type system so that operand conformability can be statically guaranteed. For instance, an attempt to add or multiply two incompatibly sized matrices is a static error. A prepose-style (i.e. following Kiselyov and Chan’s “Implicit Configurations” paper) approach is used for generating type-level integers for use in index types. Vectors can be embedded in a program using a set of template Haskell routines.
Currently the library is in a “proof-of-concept” state. The interface has an example implementation using Arrays, but ultimately it should be primarily used with a fast external linear algebra package such as ATLAS. I would like to see it become part of Alberto Ruiz’s GSL library (→4.2.3), which can be used with ATLAS, and he has expressed an interest in adopting it. That is why I haven’t given it a real name yet.
The original announcement is here:
http://article.gmane.org/gmane.comp.lang.haskell.general/13561
http://ofb.net/~frederik/futility/src/Vector/Base.hs
http://ofb.net/~frederik/futility/src/Vector/Array.hs
http://ofb.net/~frederik/futility/src/Vector/Template.hs
http://ofb.net/~frederik/futility/src/Domain.hs
http://ofb.net/~frederik/futility/src/Prepose.hs
http://ofb.net/~frederik/futility/src/Vector/read-example.hs
Ivor is a tactic-based theorem proving engine with a Haskell API. Unlike other systems such as Coq and Agda, the tactic engine is primarily intended to be used by programs, rather than a human operator. To this end, the API provides a collection of primitive tactics and combinators for building new tactics. This allows easy construction of domain specific tactics, while keeping the core type theory small and independently checkable.
The primary aim of the library is to support research into generative programming and resource bounded computation in Hume (http://www.hume-lang.org/). In this setting, we have developed a dependently typed framework for representing program execution cost, and used the Ivor library to implement domain specific tactics for constructing programs within this framework. However the library is more widely applicable, some potential uses being:
Ivor features a dependent type theory similar to Luo’s ECC with definitions, with additional (experimental) multi-stage programming support. Optionally, it can be extended with heterogenous equality, primitive types and operations, new parser rules and user defined tactics. By default, all programs in the type theory terminate, but in the spirit of flexibility, the library can be configured to allow general recursion.
The library is in active development, although at an early stage. Future plans include development of more basic tactics (for basic properties such as injectivity and disjointness of constructors, and elimination with a motive), a compiler (with optimisations) and a larger collection of standard definitions.
| Report by: | Martin Erwig |
| Status: | mostly stable, not maintained |
Haskell Rules is a domain-specific embedded language that allows semantic rules to be expressed as Haskell functions. This DSEL provides logical variables, unification, substitution, non-determinism, and backtracking. It also allows Haskell functions to be lifted to operate on logical variables. These functions are automatically delayed so that the substitutions can be applied. The rule DSEL allows various kinds of logical embedding, for example, including logical variables within a data structure or wrapping a data structure with a logical wrapper.
| Report by: | Doaitse Swierstra |
| Status: | Released as cabal packages |
The Utrecht attribute grammar system has been extended:
Some small changes were made to the cabal files in order to make installation under GHC 6.6 run.
| Report by: | Richard A. Frost |
| Participants: | Rahmatullah Hafiz, Paul Callaghan |
| Status: | Pre-release |
Existing parser combinators cannot accommodate left-recursive grammars. In some applications, this shortcoming requires grammars to be rewritten to non-left-recursive form which may hinder definition of the associated semantic functions. In applications that involve ambiguous pattern-matching, such as NLP, the rewriting to non-left-recursive form may result in loss of parses.
In our project, we have developed combinators which accommodate ambiguity and left-recursion (both direct and indirect) in polynomial time, and which generate polynomial-sized representations of the exponential number of parse trees corresponding to highly-ambiguous input. The compact representations are similar to those generated by Tomita’s algorithm.
Polynomial complexity for ambiguous grammars is achieved through memoization of fully-backtracking combinators. Systematic memoization is implemented using monads. Direct left-recursion is accommodated by storing additional data in the memotable which is used to curtail recursive descent when no parse is possible. Indirect left recursion is accommodated by use of the context in which results are created and the context in which they are subsequently considered for re-use.
We have implemented our approach in Haskell, and are in the process of optimizing the code and preparing it for release in December of 2006.
A technical report with definitions, proofs of termination and complexity, and reference to publications, is available at: http://cs.uwindsor.ca/~richard/GPC/TECH_REPORT_06_022.pdf
| Report by: | Martin Erwig |
| Status: | mostly stable, not maintained |
The Recursion Library for Haskell provides a rich set of generic traversal strategies to facilitate the flexible specification of generic term traversals. The underlying mechanism is the Scrap Your Boilerplate (SYB) approach. Most of the strategies that are used to implement recursion operators are taken from Stratego.
The library is divided into two layers. The high-level layer defines a universal traverse function that can be parameterized by five aspects of a traversal.
The low-level layer provides a set of primitives that can be used for defining more traversal strategies not covered in the library. Two fixpoint strategies inntermost and outermost are defined to demonstrate the usage of the primitives. The design and implementation of the library is explained in a paper listed on the project web page.
hs-plugins is a library for dynamic loading and runtime compilation of Haskell modules, for Haskell and foreign language applications. It can be used to implement application plugins, hot swapping of modules in running applications, runtime evaluation of Haskell, and enables the use of Haskell as an application extension language. Version 1.0rc1 has been released.
Work to port hs-plugins to GHC 6.6 is underway.
http://www.cse.unsw.edu.au/~dons/hs-plugins/
darcs get
The “time” package replaces the old System.Time module for handling time. It is included in the current GHC distribution.
The “main” modules feature representation of UTC and UT1, as well as the proleptic Gregorian calendar, time-zones, and functions for strftime-style formatting. Additional “second-level” modules handle TAI, leap-seconds, Julian, ISO 8601 week, and “year and day” calendars, calculation of Easter, and POSIX time. Modules are organised under Data.Time.
The source is in the darcs (→6.4) repository “time” in the current standard libraries, and is built by the GHC library build process. The documentation could benefit from the addition of use examples.
In case anyone is interested, I’ve put a darcsized copy of the code here:
Ther have been no changes since April 2006.
All contributions are welcome.
Streams is the new I/O library developed to extend existing Haskell’s Handle-based I/O features. It includes:
The main idea of the library is its clear class-based design that allows to split all functionality into a set of small maintainable modules, each of which supports one type of streams (file, memory buffer …) or one feature (locking, buffering, Char encoding …). The interface of each such module is fully defined by some type class (Stream, MemoryStream, TextStream), so the library can be easily extended by third party modules that implement additional stream types (network sockets, array buffers …) and features (overlapped I/O …).
The new version 0.2 adds support for memory-mapped files, files >4GB on Windows, ByteString I/O, full backward compatibility with the NewBinary library (both byte-aligned and bit-aligned modes), more orthogonal serialization API, serialization from/to memory buffer, and even better speed. Sorry, it was never documented
The upcoming version 0.3 will provide automatic buffer deallocation using ForeignPtrs, serialization from/to ByteStrings, full backward compatibility with Handle-base I/O and, hopefully, full documentation for all its features.
http://haskell.org/haskellwiki/Library/Streams
http://www.haskell.org/library/Streams.tar.gz http://www.haskell.org/library/StreamsBeta.tar.gz
<Bulat.Ziganshin at gmail.com>
System.FilePath is a library for manipulating FilePath’s in Haskell programs. This library is Posix (Linux) and Windows capable – just import System.FilePath and it will pick the right one. It is written in Haskell 98 + Hierarchical Modules. There are features to manipulate the extension, filename, directory structure etc. of a FilePath.
This module has received significant discussion on the Haskell mailing lists, and going forward I hope that it can be incorporated into the Haskell base libraries.
http://www-users.cs.york.ac.uk/~ndm/projects/libraries.php#filepath
hinotify is a simple Haskell wrapper for the Linux kernel’s inotify mechanism. inotify allows applications to watch file changes since Linux kernel 2.6.13. You can for example use it to do a proper locking procedure on a set of files, or keep your application up do date on a directory of files in a fast and clean way.
hinotify is still a very young library and might still be a bit rough around the edges. Next updates will include non-threading support and perhaps a little reworked API.
darcs get
The CoddFish library provides a strongly typed model of relational databases and operations on them, which allows for static checking of errors and integrity at compile time. Apart from the standard relational database operations, it allows the definition of functional dependencies and, therefore, provides normal form verification and database transformation operations.
The library makes essential use of the HList library (→4.6.6), which provides arbitrary-length tuples (or heterogeneous lists), and makes extensive use of type-level programming with multi-parameter type classes.
CoddFish lends itself as a sandbox for the design of typed languages for modeling, programming, and transforming relational databases.
Currently, a reimplementation of CoddFish based on GADTs is underway.
http://wiki.di.uminho.pt/wiki/bin/view/PURe/CoddFish
Takusen is a library for accessing DBMS’s. Like HSQL, we support arbitrary SQL statements (currently strings, extensible to anything that can be converted to a string). Takusen’s ‘unique-selling-point’ is a design for processing query results using a left-fold enumerator. For queries the user creates an iteratee function, which is fed rows one-at-a-time from the result-set. We also support processing query results using a cursor interface, if you require finer-grained control. We also support invoking database stored procedures with In/Out parameters, and processing of SQL statements that return multiple result sets. Currently we fully support Oracle, Sqlite, and PostgreSQL.
Since the last report we have:
http://darcs.haskell.org/takusen/
http://darcs.haskell.org/takusen/doc/html
(see Database.Enumerator for Usage instructions and examples)
Haskell implementations come with modules to handle Maps, Sets, and other common data structures. We call these modules the Standard Collection Libraries. The goal of this project is to improve on those.
Beside incremental improvement of the current code (stress testing, ironing bugs out, small improvements of API, …), a package has been created to gather collection-related code that would not fit in the base package yet. This includes changes that are either potentially de-stabilizing, controversial or otherwise experimental.
This new package features notably:
The collection package is ready for experimental use by the Haskell community. An important difference with other collection frameworks is that this one is intended as an evolution rather that a revolution. It should be easy to migrate code from using Data.Map/Set to the new framework.
Future plans include:
http://hackage.haskell.org/trac/ghc/wiki/CollectionLibraries
Monads are very common in Haskell programs and yet every time one needs a monad, it has to be defined from scratch. This is boring, error prone and unnecessary. Many people have their own libraries of monads, and it would be nice to have a common one that can be shared by everyone. Some time ago, Andy Gill wrote the monad transformer library that has been distributed with most Haskell implementations, but he has moved on to other jobs, so the library was left on its own. I wrote a similar library (before I knew of the existence of Andy’s library) and so i thought i should combine the two. The “new” monadic library is not really new, it is mostly reorganization and cleaning up of the old library. It has been separated from the “base” library so that it can be updated on its own.
Since the last report, there has been a new major release of the monad library (version 2.0), and a minor update (version 2.0.1).
Users interested in using the library can download it (with documentation) from the library’s website.
Data.ByteString provides packed strings (byte arrays held by a ForeignPtr), along with a list interface to these strings. It lets you do extremely fast IO in Haskell; in some cases, even faster than typical C implementations, and much faster than [Char]. It uses a flexible “foreign pointer” representation, allowing the transparent use of Haskell or C code to manipulate the strings.
Data.ByteString is written in Haskell98 plus the foreign function interface and cpp. It has been tested succesfully with GHC 6.4 and 6.5, and hugs March 2005.
It has been a period of great activity for Data.ByteString, which is now part of the fptools base libraries, and installed by default with GHC 6.6 and Hugs 2006. The array fusion system has been completely rewritten to use streams, with dramatic speed improvements. This work appears in our recent “Rewriting Haskell Strings” paper.
http://www.cse.unsw.edu.au/~dons/fps.html
darcs get
Edison, a library of efficient data structures for Haskell, now has a new maintainer! A major update of the library – version 1.2 – has just been released.
Major changes from Edison version 1.1 (released in 1999), include:
http://www.eecs.tufts.edu/~rdocki01/edison.html
| Report by: | Henning Thielemann |
| Participants: | Dylan Thurston, Henning Thielemann |
| Status: | experimental, active development |
The hierarchy of numerical type classes is revised and oriented at algebraic structures. Axiomatics for fundamental operations are given as QuickCheck properties, superfluous super-classes like Show are removed, semantic and representation-specific operations are separated, the hierarchy of type classes is more fine grained, and identifiers are adapted to mathematical terms.
There are both certain new type classes representing algebraic structures and new types of mathematical objects.
Currently supported algebraic structures are
There is also a collection of mathematical object types, which is useful both for applications and testing the class hierarchy. The types are
Using the revised system requires hiding some of the standard functions provided by Prelude, which is fortunately supported by GHC (→2.1). The library has basic Cabal support and a growing test-suite of QuickCheck tests for the implemented mathematical objects.
Collect more Haskell code related to mathematics, e.g. for linear algebra. Study of alternative numeric type class proposals and common computer algebra systems. Ideally each data type resides in a separate module. However this leads to mutual recursive dependencies, which cannot be resolved if type classes are mutually recursive. We start to resolve this by fixing the types of some parameters of type class methods. E.g. power exponents become simply Integer instead of Integral, which has also the advantage of reduced type defaulting.
A still unsolved problem arises for residue classes, matrix computations, infinite precision numbers, fixed point numbers and others. It should be possible to assert statically that the arguments of a function are residue classes with respect to the same divisor, or that they are vectors of the same size. Possible ways out are encoding values in types or local type class instances. The latter one is still neither proposed nor implemented in any Haskell compiler. The modules are implemented in a way to keep all options open. That is, for each number type there is one module implementing the necessary operations which expect the context as a parameter. Then there are several modules which provide different interfaces through type class instances to these operations.
| Report by: | Oleg Kiselyov |
| Developers: | Oleg Kiselyov, Ralf Lämmel, Keean Schupke |
HList is a comprehensive, general purpose Haskell library for typed heterogeneous collections including extensible records and variants. HList is analogous of the standard list library, providing a host of various construction, look-up, filtering, and iteration primitives. In contrast to the regular lists, elements of heterogeneous lists do not have to have the same type. HList lets the user formulate statically checkable constraints: for example, no two elements of a collection may have the same type (so the elements can be unambiguously indexed by their type).
An immediate application of HLists is the implementation of open, extensible records with first-class, reusable, and compiled-time only labels. We and now others (Alexandra Silva, Joost Visser: PURe.CoddFish project (→4.5.1)) have also used HList for type-safe database access in Haskell. HList-based Records form the basis of OOHaskell http://darcs.haskell.org/OOHaskell. The HList library relies on common extensions of Haskell 98.
We have changed the representation of (extensible and polymorphic) Records. Now, the field label information is purely phantom, that is, compile-time only. At run-time, a record is just a heterogeneous list of field values. We realize records as sequences of field values, where the type of each field is annotated with its (phantom) label. We also present an alternative; it too, represents records as sequences of field values; only now the type of the entire sequence is annotated with the phantom type sequence of the corresponding labels. The latter representation can easily realize ‘tables’.
We have added the implementation of extensible polymorphic variants (open unions), as duals of records. We can re-use as much of old code as possible, when adding new alternatives to the variant and extending the functions to the extended variant. We obtain the variant subtyping for free.
The HList repository is now moved to Darcs (→6.4): http://darcs.haskell.org/HList
We are working on Cabalizing HList, expanding on the work by Einar Karttunen.