August 2007 - Haskell

Call for Book Chapters: Process Algebra/Algebraic Languages/Specification-based AD
by Michael Alexander 02 Aug '07

02 Aug '07

Apologies if you received multiple copies of this message CALL FOR BOOK CHAPTERS BOOK TITLE: Process Algebra for Parallel and Distributed Processing: Algebraic Languages in Specification-Based Software Development EDITORS: Michael Alexander, WU Wien Bill Gardner, University of Guelph The book will be published in the Computational Science Series by Chapman and Hall/CRC Press in 2008 INTRODUCTION: Programming today's multi-core processor architectures, clusters, and grids is hard. Compiler research -- despite years of effort -- has still not produced implicit instruction parallelism detection that goes much beyond that of basic loop-parallelism. In addition, parallel programming in the past two decades has seen only measured improvements in parallel algorithms, languages with parallel expressivity, frameworks, and distributed validation support. As compilers have failed to deliver on their original promises, the objective of easing fine-grained parallel application programmability remains. As a consequence, new and additional paradigms are being looked at to solve what amounts to an emerging "parallel software development crisis". The approach that looks most promising is that of specification-based software development. It has its origins 3 decades ago, and it has been in a holding state for many years, only to re-emerge to a wider audience with the advent of the Object Management Group's Model Driven Architecture (MDA). Yet, specification-based software development can only deliver correct, parallel and distributed programs if the specification is precise, sufficiently expressive, and complete. Here, algebraic languages and process algebras are the paradigm that could catalyze solutions to many problems hampering efficient multi-core processor, cluster, and grid programmability problems. They are moving into a wide realm, as evidenced by the recent release of an interpreter for the algebraic Sun Fortress Language. The book is targeted to bring together the state-of-the-art in research on the application of algebraic languages and process algebras to parallel and distributed processing. It will be written to the problem statement of programming today's multi-core processor architectures, clusters, and grids. RECOMMENDED TOPICS INCLUDE BUT ARE NOT LIMITED TO THE FOLLOWING: The book aims to extensively treat algebraic languages/process algebras in parallel processing, embodying the state-of-the-art in many of the following non-inclusive list of subtopics, emphasizing an algebraic approach in each. Parallelism-oriented algebraic languages Process calculi as catalysts to solving the concurrent programming challenge Challenges in parallel programming Formal models in distributed and parallel processing Model checking, verification techniques Program transformation Axiomatizations Concurrent languages Formal semantics Formal object-oriented languages Algebras in the theory of parallel processing and distributed computing (Object oriented) distributed systems algebras Algebras and library-based approaches Frameworks supporting algebraic implementations MPI and process algebras Algebraic treatments of parallel and distributed databases (relational algebras/calculi) Concurrent composition Program generation Specification methods, notations and languages (Z, VDM-SL, B, etc.) Model and algebra transformation Operational semantics of distributed/parallel algebraic languages Parallel and distributed system specification Process algebra compilers Timed algebras Actor models CCS/CSP/ACP/Pi-Calculus/etc. in parallel-and distributed processing Equational Reasoning Software reliability/safety-critical systems Proofs Compositional/noncompositional methods Formal software development Integrated development environments for formal software Tools Case studies The editors invite the submission of abstracts (300-600 words) for proposed chapters, not under consideration elsewhere. Format and preparation instructions for full chapter submissions will be supplied to authors of accepted abstracts. Submitted chapters will undergo peer review. IMPORTANT DATES: Abstracts deadline, August 6, 2007 Notify accepted abstracts, August 13, 2007 Chapters deadline, Sep. 3, 2007 Notify accepted chapters, Dec. 17, 2007 Final manuscripts with index word lists, Feb. 18, 2008 HOW TO SUBMIT: Please post an abstract of your planned submission via EDAS at http://edas DOT info/newPaper.php?c=5487 There, create an EDAS account and paste the abstract text into the paper registration form. The book's website can be found at: http://carmel.cis.uoguelph.ca/paBook Editor Contacts Dr. Michael Alexander Wirtschaftsuniversitaet Wien Department of Information Systems and Process Management Augasse 2-6 A-1090 Vienna, Austria Email: malexand(a)wu-wien.ac.at Telephone: +43.1.31336.4467 Dr. William Gardner University of Guelph Department of Computing and Information Science 50 Stone Rd E Guelph, ON, N1G 2W1, Canada Email: wgardner(a)cis.uoguelph.ca Telephone: +1.519.824.4120 x52696

1 0

type class instance selection & search
by Conal Elliott 01 Aug '07

01 Aug '07

I keep running into situations in which I want more powerful search in selecting type class instances. One example I raised in June, in which all of the following instances are useful. > instance (Functor g, Functor f) => Functor (O g f) where > fmap h (O gf) = O (fmap (fmap h) gf) > instance (Cofunctor g, Cofunctor f) => Functor (O g f) where > fmap h (O gf) = O (cofmap (cofmap h) gf) > instance (Functor g, Cofunctor f) => Cofunctor (O g f) where > cofmap h (O gf) = O (fmap (cofmap h) gf) > instance (Cofunctor g, Functor f) => Cofunctor (O g f) where > cofmap h (O gf) = O (cofmap (fmap h) gf) My understanding is that this sort of instance collection doesn't work together because instance selection is based only on the matching the head of an instance declaration (part after the "=>"). I'm wondering why not use the preconditions as well, via a Prolog-like, backward-chaining search for much more flexible instance selection? Going further, has anyone investigated using Prolog as a model for instance selection? Better yet, how about LambdaProlog ( http://www.lix.polytechnique.fr/Labo/Dale.Miller/lProlog) which generalizes from Horn clauses to (higher-order) hereditary Harrop formulas, including (restricted but powerful) universals, implication, and existentials? Once search is in there, ambiguity can arise, but perhaps the compiler could signal an error in that case (i.e., if the ambiguity is not eliminated by further search pruning). My motivation: I've been playing with a programming style in which my type formulation leads to automatic construction of much of the code, thanks to use of Functor, Applicative, Monoid, and type composition. An example is http://haskell.org/haskellwiki/Applicative_data-driven_programming, and I'm trying now to do the same to create a much simpler implementation of Eros ( http://conal.net/papers/Eros) I think this programming style is what Conor was alluding to recently as "types don't just contain data, types explain data" (http://article.gmane.org/gmane.comp.lang.haskell.cafe/26520) (Conor: I hope you chime in.) My hunch is that this programming style tends to run up against the head-only instance matching mechanism and would work much better with a more powerful means of selecting instances. - Conal

7 11

Type Lambdas in Gofer
by Jim Apple 01 Aug '07

01 Aug '07

The code in "Bananas in Space: Extending Fold and Unfold to Exponential Types" http://citeseer.ist.psu.edu/293490.html mirror: http://www.cs.nott.ac.uk/~gmh/bananas.pdf uses Gofer, and has examples such as data Rec f = In (f (Rec f)) type P f a = f (Rec f, a) mapP :: Functor f => (a -> b) -> P f a -> P f b mapP g = fmap (\(x,a) -> (x, g a)) instance Functor f => Functor (P f) where fmap = mapP Why did Gofer have this power while Haskell does not? Jim

4 3

type class instance selection & search
by Andrzej Jaworski 01 Aug '07

01 Aug '07

Simon Peyton-Jones <simonpj(a)microsoft.com> wrote: > It certainly makes sense to do backward chaining, but I don't know any Haskell implementation > that's tried it. It'd be more complicated in the presence of functional dependencies, since we > must "undo" any unifications done as a result of discarded searches, much like the "trail" in a > Prolog implementation. Perhaps linear logic search could make this easier. LolliMon http://www.cs.cmu.edu/~fp/lollimon shows how it can be done; additional ideas like memory management and concurrency might avail form this too. I believe that it is high time to revisit logic and Haskell is an excellent ground for this (e.g. multicore is essentially signal processing that can be elegantly solved probably only by multivalued logic). > To be honest I can't see myself trying this anytime soon. Because of the unification part, it'd > be a significant structural change. And one would > need to dig into the theory to make sure that > the algorithm was both sound and complete (finds all solutions). Not much of help but a refreshing read: http://www.cs.cmu.edu/~fp/papers/tocl07.pdf Regards, -Andrzej

1 0