Constraint Functional-Logic Programming I am currently developing a Haskell library for constraint functional-logic programming. It is in an early alpha stage (does not support higher-order functions and implements no constraint solvers) but can already be used to mimic simple lazy functional-logic programs in Haskell. Monadic and Queue-Based Tree Search Insipred by Monadic Conctraint Programming by Tom Schrijvers et. al., I wrapped up some thoughts on the difference between monadic and queue-based tree search. Haskell idioms I did not understand before hacking them on my own When coding my first library for Hackage, I learned about two programming problems and their solutions in Haskell. I boiled them down to the essence and wrote two posts to share them. One on polyvariadic functions, the other on heterogeneous collections. To get an executable Haskell file simply strip off the .html suffix. Simple SAT Solver
Tom Schrijvers, Louis-Julien Guillemette, Stefan Monnier Abstract Haskell's multi-parameter type classes, together with functional dependencies, allow the specification of complex type-level operations, and the recent introduction of open type families in GHC makes such type-level programming even more accessible and flexible. But type-level code is special in that its correctness is crucial to the safety of the program; so except in those cases simple enough for the type checker to see trivially that the code is correct (or harmless), type-level programs need to come with their specification and correctness proof. In this article, we propose an extension to Haskell that allows the specification of invariants for type classes and open type families, together with accompanying evidence that those invariants hold. To accommodate the open nature of type classes and type families, the evidence itself needs to be open
Suppose someone stole all the monads but one, which monad would you want it to be? If you're a Haskell programmer you wouldn't be too bothered, you could just roll your own monads using nothing more than functions. But suppose someone stole do-notation leaving you with a version that only supported one type of monad. Which one would you choose? Rolling your own Haskell syntax is hard so you really want to choose wisely. Is there a universal monad that encompasses the functionality of all other monads? About a year ago I must have skimmed this post because the line "the continuation monad is in some sense the mother of all monads" became stuck in my head. So maybe Cont is the monad we should choose. This post is my investigation of why exactly it's the best choice. Along the way I'll also try to give some insight into how you can make practical use the continuation monad.
Here’s a visualization concept I came up with a while back to look at the way search engines and word-of-mouth affects hit frequency on the iBiblio web-traffic log. iBiblio consists of around 420 sites. Each one of the circles you see represents one of the websites. The size of each pie slice inside grows with respect to the number of hits by individual search engines (see the legend for which ones). The size of the circle grows with respect to the overall number of hits by people other than search engines. Hits are counted by number of unique incoming IP addresses per day. Links get drawn between cliques of websites where more than 1/4th of the unique IP addresses are the same on that day, meaning, more or less, that those sites often share traffic. The total amount of data was around 10TB and the visualization took about a day to process into a static animation. The original is meant to run on a wall-sized (16′x9′) or on our specialized visualization dome.
Datatype-Generic Programming Roland Backhouse at the University of Nottingham and Jeremy Gibbons at the University of Oxford have a joint EPSRC-supported project entitled Datatype-Generic Programming, running for three years and starting on 1st October 2003. Aim The project is to develop a novel mechanism for parametrizing programs, namely parametrization by a datatype or type constructor. The mechanism is related to parametric polymorphism, but of higher order. We aim to develop a calculus for constructing datatype-generic programs, with the ultimate goal of improving the state of the art in generic object-oriented programming, as occurs for example in the C++ Standard Template Library. further details of the project can be obtained from the contacts listed below.
Dependent type systems, in which types can depend on values, admit detailed specifications of function behavior and data invariants. Programming languages based on System F do not have dependent types, and are therefore more limited in what structure or function invariants can be encoded in the type system. In this paper, we show how guarded algebraic datatypes can simulate dependent types. We formalize additions to a guarded-datatypes-enhanced System F that allow types to depend on values and discuss the programming style that results, which is similar to theorem proving. Our technique can be applied to multiple existing programming languages, including Haskell and C#. We also introduce an idiom for eliminating any execution cost from programming with simulated dependent types. We have developed a tool to automatically produce the boilerplate necessary for the simulation, and we have used it to enforce data structure invariants and to allow elision of run-time bounds checks.
The Haskell project was begun in order to unify "more than a dozen non-strict, purely functional programming languages". (mirror) We are rapidly approaching that many viable choices for programming with dependent types. 1. Epigram 2. ATS (successor to Dependent ML) 3. Agda (successor to Cayenne) 4. Ωmega 5. NuPrl 6. Twelf 7. Isabelle 8. Coq etc caveats * Some of the items on this list are theorem provers first and dependently-typed programming languages second. Adam Chlipala argues that this is not such a problem for Coq. * Some of these choices may not be real options for programing with dependent types. Twelf is designed for programming about programming languages, and, if I remember correctly, doesn't have parametric polymorphism because of something having to do with higher-order abstract syntax. Is it time yet to do anything about the cornucopia of options? see comments
LambdaVM is a JVM backend for GHC. It is available at http://darcs.brianweb.net/ghc. October, 2008 Update See http://www.cs.rit.edu/~bja8464/lambdavm/ Documentation * Building Guide * FFI * Exceptions * Concurrency Misc Notes * Implementation * Todo * NestedVM Integration
An ingenious set of combinators for expressing pattern matching in a type-safe way. No ADTs required. Opens up the possibility of programming languages where we can declare new binding forms just as we declare new functions. abstract: Macros still have not made their way into typed higher-order programming languages such as Haskell and Standard ML. Therefore, to extend the expressiveness of Haskell or Standard ML gradually, one must express new linguistic features in terms of functions that fit within the static type systems of these languages. This is particularly challenging when introducing features that span across multiple types and that bind variables. We address this challenge by developing, in a step-by-step manner, mechanisms for encoding patterns and pattern matching in Haskell in a type-safe way.
Formerly Dr Haskell HLint can only be compiled by GHC 6.10.1 or above (it makes use of view patterns), but does not require any copy of GHC to run. HLint should be able to give hints for any Haskell code, including most GHC extensions
Timber program reacts to events sent to it from its execution environment. This process is potentially infinite, and the order of external events is not known in advance.To capture this intuition, Timber defines its primary run-time structure to be a set of interconnected reactive objects, that each encapsulate a piece of the global program state. A reactive object is a passive entity defined by a set of methods. Between invocations, a Timber object just maintains its state, ready to react . Timber objects evolve in parallel, although the methods belonging to a particular object are always run under mutually exclusion. Concurrency as well as state protection is thus implicit. Methods are either asynchronous or synchronous, as denoted by the keywords action and request, respectively. The most radical property of Timber is that it is free from any indefinitely blocking constructs; because of this, a Timber object is always fully responsive when not actively executing code.
for 6.10 We show how to build a quasiquoter for a simple mathematical expression language. Although the example is small, it demonstrates all aspects of building a quasiquoter. We do not mean to suggest that one gains much from a quasiquoter for such a small language relative to using abstract syntax directly except from a pedagogical point of view---this is just a tutorial!
Herein part six in my hobby project to rewrite my personal publishing software in Haskell. In part five (and its addendum), I roughed-out a persistence and concurrency model for the back-end. The next two pieces are rendering content (which will be done programmatically using the Text.XHtml.Strict module; that's a separate post) and integrating with a web server via FastCGI. This post covers FastCGI integration for Lighttpd and Apache2 in the form of smoke-testing a simple FastCGI handler.
Extensible and Modular Generics for the Masses (EMGM) applies concepts of datatype-generic programming to define generic functions for supported datatypes using type classes.