- Haskell - Haskell.org

Quantified class constraints (& back-chaining)
by Conal Elliott 02 Aug '07

02 Aug '07

I'm developing a type constructor class and want the constraint forall a. Monoid (m a) (where m :: * -> *), which is neither legal Haskell, nor supported by GHC. As a work-around, I used the first encoding suggested in "Simulating Quantified Class Constraints" (Valery Trifonov, Haskell Workshop '03). Add a type class class Monoid_f m where mempty_f :: forall a. m a mappend_f :: forall a. m a -> m a -> m a and an instance *schema* -- instance Monoid_f f where { mempty_f = mempty ; mappend_f = mappend } to instantiate manually wherever necessary. For instance, instance Monoid_f [] where { mempty_f = mempty ; mappend_f = mappend } The paper's second approach is to replace the schema and multiple instantiations with a single instance. instance Monoid_f f => Monoid (f a) where { mempty = mempty_f ; mappend = mappend_f } As the paper points out, Unfortunately, due to the type variable f in the head of the instance type, > this declaration is not in Haskell 98; however, at least two implementations > support extensions allowing such declarations. > Sadly, this solution runs into the problem of instance selection based only on head-matching, not back-chaining into constraints. For instance, I'd like also to use the following "conflicting" declaration. instance (Applicative f, Monoid a) => Monoid (f a) where mempty = pure mempty mappend = liftA2 mappend What's the state of thinking & doing with regard to universally quantified class constraints? Note that hereditary Harrop formulas do include universally quantified goals. Less ambitiously, I think GHC's type-checker already deals with universally-quantified variables, so perhaps quantified constraints are not a great reach (just guessing). Cheers, - Conal

4 4

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

3-yr post for language person
by Simon Peyton-Jones 31 Jul '07

31 Jul '07

Tim Griffin is advertising a 3-year research associate position at the Cambridge Computer Lab, working on a project that seeks to design and implement a meta-language for the specification and implementation of correct Internet routing protocols. He says "A PL person would be perfect". Details here: http://www.admin.cam.ac.uk/offices/personnel/jobs/vacancies.cgi?job=2114 Simon

1 0

APLAS 2007 call for poster presentations (Singapore, Nov 29 - Dec 1)
by Eijiro Sumii 31 Jul '07

31 Jul '07

CALL FOR POSTER PRESENTATIONS The Fifth ASIAN Symposium on Programming Languages and Systems (APLAS 2007) November 29 - December 1, 2007 Singapore http://flint.cs.yale.edu/aplas2007/ APLAS 2007 will include a poster session during the conference. The session aims to give students and researchers an opportunity to present their research to the community, and to get responses from other researchers. SCOPE: Poster presentations are sought in all areas of programming languages and systems, including (but not limited to): - semantics, logics, foundational theory - type systems, language design - program analysis, optimization, transformation - software security, safety, verification - compiler systems, interpreters, abstract machines - domain-specific languages and systems - programming tools and environments FORMAT: A space of A1 paper size (594 mm wide and 841 mm high) will be provided for each presentation. If you need more space, contact the poster chair (sumii AT ecei DOT tohoku DOT ac DOT jp). To prepare a good poster, search the Web for "poster presentation" and you will find many useful resources. REGISTRATION: Each presenter should e-mail a 1-2 page abstract in PDF or PostScript (including the title, authors, affiliations, and a summary of the work) to the poster chair (sumii AT ecei DOT tohoku DOT ac DOT jp) by September 14th, 2007. The program of the poster session will be announced by September 21st, 2007. We hope to accommodate every poster, but may restrict presentations (based on relevance and interest to the community) due to space constraints. IMPORTANT DATES: 1-2 page abstract September 14, 2007 notification September 21, 2007 conference November 29 - December 1, 2007 CONTACT: For questions or requests, please contact the APLAS 2007 poster chair, Eijiro Sumii (sumii AT ecei DOT tohoku DOT ac DOT jp).

1 0

Latest AngloHaskell news and a request
by Philippa Cowderoy 30 Jul '07

30 Jul '07

Two pieces of news regarding AngloHaskell: 1) We've been offered WiFi access at Microsoft Research for any attendees who want it. We'll need a name, email address and company/institution affiliation where appropriate - see wiki for details. 2) We're being given lunch on Friday! Finally, a request: We're a little short on crashspace, and I suspect this is affecting who's able to show up. Could people who can only make it with crashspace (or who can only make one day without) add their names on the wiki? Is there anyone in the area able to offer people at least some space on a floor? Last year we had offers early, and I think this helped get plans moving. For those who could use the reminder, the wiki page is at http://www.haskell.org/haskellwiki/AngloHaskell Many thanks, and I hope to see you there! -- flippa(a)flippac.org Society does not owe people jobs. Society owes it to itself to find people jobs.

1 0

Haskell->Erlang compiler, sort of
by Bulat Ziganshin 30 Jul '07

30 Jul '07

Hello haskell, http://blog.tornkvist.org/?id=1185571582964040 -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

1 0

Call for Submissions - First Workshop on Languages and Tools for Parallel and Distributed Programming (LTPD 2007)
by heron_carvalho 30 Jul '07

30 Jul '07

------------------------------------------------------------ First Workshop on Languages and Tools for Parallel and Distributed Programming (LTPD 2007) http://computacao.ucpel.tche.br/ltpd/ Gramado, RS - Brazil Co-located with SBAC-PAD 2007 (24-27 October 2007) *** Submissão de artigos: 24 de Agosto *** ------------------------------------------------------------ The objective of this workshop is to bring together researchers working on the design and implementation of programming languages, tools and techniques for distributed, parallel and mobile programming. Submitted papers should present original research that is unpublished and not submitted elsewhere. We encourage the submission of work in progress, especially by MSc and PhD students. We plan to provide a friendly environment where researchers can discuss current and future trends in programming languages for parallel and distributed programming. Papers can be written in English, Portuguese and Spanish. Papers should have 4 pages, following the IEEE Computer Society Proceedings Manuscript Formatting Guidelines. All accepted papers will be published in the On-Line conference proceedings, and as a technical report. The SBAC-PAD organization will also publish the electronic proceedings in CD. We plan to publish selected high quality papers from the proceedings in a local brazilian journal. At least one author of an accepted paper must attend the workshop and all workshop attendees must be registered to SBAC-PAD. Topics of Interest ------ -- -------- Topics of interest include, but are not limited to: * Programming Multi-Core Machines * Coordination Languages * Concurrent and Parallel Garbage Collection * Type systems and semantics for parallel, distributed and mobile languages * Declarative parallel, distributed and mobile languages * Languages for mobile and ubiquitous computing * Calculi for Mobility and Concurrency * Design Patterns * Distributed Objects * Distributed Component Models * Mobile Agents Languages * Software issues for multicore or multithreaded processors Important Dates --------- ----- * Deadline for paper submission: August 24, 2007 * Accepted Papers Notification: September 10, 2007 * Camera-Ready Submission: September 17, 2007 Organizing Committee ---------- --------- André Rauber Du Bois (Chair) - UCPel Francisco Heron de Carvalho Junior (Chair)- UFC Program Committe ------- -------- Adenauer Correa Yammin - UCPel Alcides Calsavara - PUCPR Álvaro Freitas Moreira - UFRGS André Rauber Du Bois - UCPel André Santos - UFPE Claudio Fernando Resin Geyer - UFRGS Cristiano Vasconcellos - UFPel Francisco Heron De Carvalho Jr - UFC Hans-Wolfgang Loidl - LMU, Germany Iara Augustin - UFSM Jorge Luis Victoria Barbosa - Unisinos Marco Túlio de Oliveira Valente - PUC-MG Phil Trinder - Heriot-Watt University, UK Rafael Dueire Lins - UFPE Ricardo Corrêa - UFC

1 0