Postdoc/PhD Positions on the Monadic Constraint Programming project

The Declarative Languages and Artificial Intelligence Group at the
Catholic University of Leuven is urgently looking for doctoral and
postdoctoral research candidates in the area of Constraint Programming.

Both positions concern the application and development of Constraint
Programming techniques, and the Monadic Constraint Programming framework in
particular, for solving problems of industrial scale. Close collaboration with
our industrial partners is expected, and involves aspects of mutual interest,
modeling, search heuristics and parallelization among others. More
information on the Monadic Constraint Programming can be found at
http://www.cs.kuleuven.be/~toms/MCP/.

For the postdoctoral position, applicants should have a Ph.D. in Computer
Science and for the doctoral position, a masters degree in Computer Science or
equivalent. A background and interest in Constraint Programming is essential.
Experience in functional programming (Haskell), Gecode, software engineering
and implementation are important assets.

Appointment to the postdoctoral position will be for the period of up to two
years. Appointment to the doctoral position will be for the period of one year
initially with possibility for extension to four years ending in a Ph.D. The
salary is compatible with the departmental rates for postdoctoral and doctoral
research fellows, and can take experience into consideration.

Please direct inquiries and applications, preferably by e-mail, to:

Professor Bart Demoen
Department of Computer Science
K.U.Leuven
Celestijnenlaan 200A
B-3001 Heverlee
Belgium

Email: bart.demoen@cs.kuleuven.be
Phone: +32 16 327547

Informal notice of interest should be received as soon as possible no later than
November 25, 2009. Review of applications begins as of now. Positions start as
soon as January 1, 2010.

Haskell Type Constraints Unleashed

Dominic Orchard and I have written a new paper on new type system features for supporting EDSLs.

Haskell Type Constraints Unleashed
D. Orchard, T. Schrijvers

The popular Glasgow Haskell Compiler extends the Haskell 98 type system with several powerful features, leading to an expressive language of type terms. In contrast, constraints over types have received much less attention, creating an imbalance in the expressivity of the type system.
In this paper, we rectify the imbalance, transferring familiar type-level constructs, synonyms and families, to the language of constraints, providing a symmetrical set of features at the type-level and constraint-level. We introduce constraint synonyms and constraint families, and illustrate their increased expressivity for improving the utility of polymorphic EDSLs in Haskell, amongst other examples. We provide a discussion of the semantics of the new features relative to existing type system features and similar proposals, including details of termination.

We greatly appreciate your feedback. Also example of other problems that could be solved by the new features are very welcome.

Release 0.6 of Monadic Constraint Programming

We've just released version 0.6 of the Monadic Constraint Programming framework on Hackage.

This release provides a whole lot of generic support for Finite Domain (FD) constraint solvers: a common modeling language and infrastructure for targeting different backends. Very useful if you happen to develop an FD solver and want to hook it up to our framework to benefit from its advanced search capabilities.

Users will of course be much more interested in the actual backends that we provide. Besides the basic Haskell FD solver we had before, there are now three different ways of interfacing Gecode, one of the best FD solvers out there and open source too. To get started, the examples directory shows how to model a number of well-known problems.

EffectiveAdvice: AOP, mixin inheritance, monads, parametricity, non-interference, ...

How to reason about effectful advice? Write your AOP programs in Haskell, the world's best imperative programming language. Use monads and monad transformers for effects and functional mixins for advice. In return you get powerful reasoning tools: equational reasoning and parametricity.

Read the technical report. The appendix has some pretty cool parametricity proofs on non-interference of advice, based on Janis' Voigtlaender's ICFP'09 paper "Free Theorems Involving Type Constructor Classes".

EffectiveAdvice: Overview, background and proofs
Bruno Oliveira, Tom Schrijvers and William Cook

Abstract

Advice is a mechanism, widely used in aspect-oriented languages, that allows one program component to augment or modify the behavior of other components. Advice is useful for modularizing concerns, including logging, error handling, and some optimizations, that would otherwise require code to be scattered throughout a system. When advice and other components are composed together they become tightly coupled, sharing both control and data flows. However this creates important problems: modular reasoning about a component becomes very difficult; and two tightly coupled components may interfere with the control and data flows of each other.

This paper presents EffectiveAdvice, a disciplined model of advice, inspired by Aldrich's Open Modules, that has full support for effects in both base components and advice. With EffectiveAdvice, equivalence of advice, as well as base components, can be checked by equational reasoning. The paper describes an implementation of EffectiveAdvice as a Haskell library and shows how to use it to solve well-known programming problems. Advice is modeled by mixin inheritance and effects are modeled by monads. Interference patterns previously identified in the literature are expressed as combinators. Parametricity, together with the combinators, is used to prove two harmless advice theorems. The result is an effective model of advice that supports effects in both advice and base components, and allows these effects to be separated with strong non-interference guarantees, or merged as needed.

Monadic Constraint Programming with Gecode

We have a new paper available, reporting on the next stage in the Monadic Constraint Programming project:

Monadic Constraint Programming with Gecode
Pieter Wuille and Tom Schrijvers

This paper presents FD-MCP, a finite domain modeling language on top of the
Monadic Constraint Programming framework for Haskell. FD-MCP leverages
Haskell's rich static type system and powerful abstraction mechanisms for
implementing syntactic sugar, model transformations and compilation to
solver backends. Two backends are provided: a basic Haskell solver and a
Gecode code generator.
Our benchmarks establish that FD-MCP models are much more concise than
hand-coded Gecode programs, more so when using disjunction, without sacrificing
performance.

The code is available from the project page.

NEW: The paper has been accepted at ModRef 2009, and a revised version is available.

16th Prolog Programming Contest Results

[Here are my photos of the contest.]

Most of you already know what the Prolog programming contest is about. To the
others I have to say, shame on you! The contest is of course about locking up
several teams of Prolog programmers in a room for two hours with 5 challenges.
Each team has at most 3 members and one laptop. The team that solves most
challenges in the least amount of time is the winner.

You should know that the first rule of the contest is:

The contest is for fun and there are no losers.

Of course, there are losers outside of the contest, with silly excuses for
not participating, like:
- I have to go sight-seeing in Hollywood tonight, or
- My talk for the Commercial Users workshop is not written yet.
The silliest of all is:
- I don't know Prolog.
How low can you go.

Fortunately, we had many eager and willing participants. Very few of them had
to be pressed into it. They readily agreed, even before their first coffee of
the morning! No less than 10 teams showed up.
So we had
- 2 all-American teams,
- 3 Leuven teams,
- 1 team from Italy and 1 from Spain,
- a bunch of Danish rookies, and
- 2 mixed teams
* an Austrian, Scottish, and commercial New-Zealander team
* a French-Dutch-Italian team with Marco Gavanelli.

In fact, Marco is the only of of last year's winners here to defend the
title. Shame on the other two.

Now, I must say it is at least as much fun running the contest as it is
participating. You get to watch all the teams in action, doing all kinds of
things to get ahead. Like swapping around the keyboard. The Italians were
really smart, reading the challenge pages on both sides simultaneously.

You learn a lot of things running the contest. For instance, reading the
problem statement is actually useful: minimizing the maximal distance is not
the same as computing the average. Another one: Did you know that Danes read
from left to right, but write from right to left. Finally, a revelation:
base cases do seem to be essential.

Before we move on to the ranking, there are a number of people I have to
thank. Firstly, there is Bart Demoen, the creator of this contest who has
helped me with the problem statements and given practical advice on running
the contest. He enjoys a well-deserved sabbatical from the contest this
year. Thank you, Bart!

Secondly, I would like to thank the local organizers, Hai-Feng Guo and Gopal
Gupta, who have provided us with an excellent venue and sponsoring the prizes.
Thanks to Brian DeVries, Stanley Jointer and their colleagues, who have helped
get everything ready and put the room back to order after the herd of Logic
Programmers. Thanks guys!

Also thanks to the program chairs, Pat and David, for making the Programming
Contest an integral part of the program. Thank you!

Last but not least, I would like to thank my wife, Annemie, who has
created the prizes. Thank you.

Now, on to the ranking. This year's challenges were too easy. All teams had
at least one solution, and most teams had more than one. We got 38
submissions, of which 25 were correct. Bart Demoen would be ashamed of
passing so many. With the challenges being so easy having 3 correct
solutions was not enough to make the top 3.

The team that came in third, with four submission and four correct answers, is
the team of Alessandro Dal Palu, Agostino Dovier and Enrico Pontelli!

Then, there are two teams left: the team of Leslie De Coninck and the team
of Jan Wielemaker. Both know they have four correct submissions, but Jan's
team has also submitted a solution for the 5th challenge. Sorry guys, but
Jan's team forgot a base case there, and the other team was more than 100
minutes ahead. So I'd like to call forward this year's winners:
Leslie De Koninck, Hanne Vlaeminck and Peter Van Weert!




I hope you enjoyed it.

Tom

Prolog Programming Contest

The 16th Prolog Programming is in full swing with 10 teams competing for the title of best Prolog programmers of the year.

You can still participate in the online contest.