To: seminaire@pauillac.inria.fr From: Didier.Remy@inria.fr Subject: SEM - INRIA : Cristal - 11/05/01 - Paris - FR Vous pouvez maintenant vous abonner à nos annonces de séminaires http://pauillac.inria.fr/seminaires/subscribe.html S E M I N A I R E . ___ / _ _ / _ / / / \ / \ / / __| / |___ |_/ |_/ / |__ |_/ |_ ___ . / / ___ __ /_ _ / _/ /| /| _ __ __ _ _ / / / /_ / __| / / |/ | / \ /_ / / \ | / __| |___ / / __/ |_ |_/ |_ / | |_/__/ |_ |_/ |/ |_/ I N R I A - Rocquencourt Salle de conference du Bat 11 Vendredi 11 mai, 10h30 -------------- Andrew Tolmach -------------- Portland State University ============================== Modular Lazy Search Algorithms ============================== Constraint satisfaction problems (CSPs) over finite domains are both practically significant and computationally hard. Although many sophisticated imperative algorithms have been developed over the past few decades, they have usually been implemented and presented monolithically, which makes them hard to understand, reuse, or combine. On the other hand, lazy-functional programmers have long understood how to write modular search code by putting generation and testing into separate functions, communicating via an explicit, lazy intermediate data structure. But only fairly simple search algorithms have been treated this way in the past. In this talk, I will describe a parameterised Haskell framework for solving CSPs, and show that many advanced imperative search algorithms can be obtained by suitable choice of parameters. More importantly, arbitrary combinations of algorithms and domain-specific heuristics can be obtained by simple composition. Modularity exacts a considerable performance penalty, however. I will discuss recent work aimed at improving performance by using deforestation rewrite rules in the Glasgow Haskell Compiler, as well as some results for Objective Caml. (Joint work with Thomas Nordin.)