- Haskell - Haskell.org

Re: class assosiated types, via GADTs or FDs
by oleg＠pobox.com 17 Feb '05

17 Feb '05

Manuel M T Chakravarty wrote: > The functional dependency encoding prevents you from ever making the > representation of your tries/maps (in the MapKey class example) > abstract. It does not only prevent you from declaring it as an abstract > data type, but it actually forces users of a library built in this way > to understand the representation types and manually encode them in their > application code. It seems that problem can be easily solved in Haskell with the existing tools. First of all, one has to mention partial signatures, which are possible in Haskell to some extent (sufficient in our case) http://pobox.com/~oleg/ftp/Haskell/types.html#partial-sigs But mainly, if we wish to hide some details of the representation, why not to use tools that are built for that, such as applicative functors? They are _easily_ implementable in Haskell, arguably idiomatic, and free from the above drawbacks. The type system itself takes care to properly hide the representation. The following messages describe the realization of (generative and applicative and recursive) functors in great detail: http://www.haskell.org/pipermail/haskell/2004-August/014463.html http://www.haskell.org/pipermail/haskell/2004-September/014515.html Here's a simple example tailored to Manuel M T Chakravarty's sample code. First, the illustration of the problem: > {-# OPTIONS -fglasgow-exts #-} > {-# OPTIONS -fallow-undecidable-instances #-} > module MK where > > class MapKey k fm | k -> fm where > lookp :: k -> fm v -> Maybe v > empty :: k -> fm v > -- NB: The original signature of empty doesn't mention k, which > -- is already problematic, but you can fix this by > -- adding it as a dummy argument to fm. > > data BoolMap v = Integer > instance MapKey Bool BoolMap > > newtype AnyMap k v = AM [(k,v)] > instance MapKey Char (AnyMap Char) where > lookp k (AM m) = lookup k m > empty _ = AM [] > test1 = lookp True undefined Indeed, the type of lookp is *MK> :t lookp lookp :: forall k fm v. (MapKey k fm) => k -> fm v -> Maybe v If we want to specialize it for Bool keys, we indeed can't write lookpBool :: forall fm v. (MapKey Bool fm) => Bool -> fm v -> Maybe v but we perfectly well can write > lookpBool k m = lookp (k::Bool) m One can object that although we don't have to know how the Map of Bool keys is realized, we can actually see that, from the type of lookpBool. We have to hide that. But the type system already lets us do that. Let us look again at the type lookp :: forall k fm v. (MapKey k fm) => k -> fm v -> Maybe v The problem is the presence of `fm'. A few algebraic transformations on that expression give us forall k v. k -> (exists fm. (MapKey k fm) => fm v) -> Maybe v which is easily realizable in Haskell. > data Map' k v = forall fm. MapKey k fm => Map' (fm v) > > class MapKey' k where > lookp' :: k -> Map' k v -> Maybe v > lookp' k (Map' m) = lookp k m > empty' :: Map' k v One and only instance of MapKey' we will ever need: > instance MapKey k fm => MapKey' k where > empty' = Map' (empty (undefined::k)) First we note that the signature of empty' _does_ mention the type of keys in essential manner -- but does not leak the representation of the map. We also note that type of lookp': *MK> :t lookp' lookp' :: forall k v. (MapKey' k) => k -> Map' k v -> Maybe v Now, the representation of the map is perfectly hidden. We can now write: > test2 = let m = empty' in lookp' 'a' m > test3 = let m = empty' in lookp' True m No unneeded signatures -- and the ``library'' automatically adjusts the representation of maps based on the type of the key -- which seems to have been the main motivation for the associated types.

1 0

Announcement: APPSEM-II Summer School, Sep 8-12
by Hans-Wolfgang Loidl 17 Feb '05

17 Feb '05

APPSEM II Summer School Frauenchiemsee, September 8-12, 2005 1st CALL FOR PARTICIPATION The IST-FET Summer School on Applied Semantics (APPSEM-II) will take place September 8-12, 2005 in Frauenchiemsee near Munich. We are proud to announce the following confirmed speakers: Andrew Pitts, Cambridge: Nominal Syntax and Semantics Philippa Gardner, London: Local Reasoning about Data Update Francois Pottier, Paris: A modern eye on ML type inference: old techniques and recent developments Gilles Barthe, Nice: Dependent Types in Programming Chris Hankin, London: Principles of Program Analysis The school is open to all interested graduated and (senior) undergraduate students as well as researchers. A limited number of student grants covering all fees, accommdation, and travel, are available. Neither participation nor grants are restricted to APPSEM sites. For details including deadlines please see the WWW page at http://www.appsem.org/summer_school.html

1 0

MTCoord'05: Second call for papers
by Isabelle Linden 17 Feb '05

17 Feb '05

[ Our apologies for multiple copies. ] ====================================================================== Second Call for Papers 1st International Workshop on Methods and Tools for Coordinating Concurrent, Distributed and Mobile Systems (MTCoord 2005) April 23, 2005, Namur, Belgium Workshop affiliated to Coordination'2005, April 20 - 23 2005 ====================================================================== IMPORTANT DATES: o March 1, 2005: Abstract submission deadline. o March 8, 2005: Paper Submission deadline. o April 1, 2005: Notification of acceptance. o April 10, 2005: Final version. o April 23, 2005: Meeting Date. SCOPE Various classes of computational models, languages, and formalisms have emerged in the aim of providing high-level descriptions of concurrent, distributed, and mobile systems. Typical examples include so-called coordination languages and models (e.g. Gamma, Linda, Manifold, Reo, Klaim, Lime, ...), concurrent constraint languages (e.g. cc languages, Mozart, ...) and process algebras (e.g. CSP, CCS, pi-calculus, ...). These models are based on generative communication via a shared data space or on data communication through channels. In both cases, software components are typically conceived in isolation assuming that the required data will eventually be available. However, making a whole system out of these components and, in particular, ensuring that interactions occur properly is far from being obvious. The aim of the workshop is precisely to bring together researchers, working in different communities (coordination, constraints, process algebras), on methods and tools for the construction of concurrent, distributed and mobile systems. TOPICS OF INTEREST Topics of interest include but are not limited to o Model checking techniques, in particular parallel, distributed and probabilistic ones o Design of high-level specifications, eg based on first-order, modal and temporal logics o Techniques for requirements capture and analysis o Theorem proving based methodologies o Compositional and refinement-based methodologies o Debugging techniques o Abstract interpretation o Program analysis and transformation o Simulation and testing o Formal methods for security o Tools environments and architectures o Applications and case studies, in particular in web services and biology SUBMISSION GUIDELINES Papers describing original work are solicited as contributions to MTCoord 2005. Submitted papers should be limited to 6 000 words, preferrably formatted according to the Electronical Notes in Theoretical Computer Science. They should be submitted through the conference management system that will be available from the workshop web site http://www.info.fundp.ac.be/MTCoord/MTCoord05 PUBLICATION Selected work will be published in a volume of the Electronical Notes in Theoretical Computer Science. LOCATION The workshop will be held in Namur in April 23 2005. It is a satellite workshop of Coordination 2005. For venue and registration, see the Coordination'2005 web page at http://www.coordination2005.org WORKSHOP ORGANIZERS o Lubos Brim, Masaryk University Brno, Czech Republic o Isabelle Linden, University of Namur, Belgium PROGRAMME COMITTEE (provisional) o Ivana Cerna, Masaryk University Brno, Czech Republic o Rance Cleaveland, State University of New York at Stony Brook, USA o Giorgio Delzanno, University of Genova, Italy o Wan Fokkink, CWI, The Netherlands o Jean-Marie Jacquet, University of Namur, Belgium o Marta Kwiatkowska, University of Birmingham, United Kingdom o Angelika Mader, University of Twente, The Netherlands o Andreas Podelski, Max Planck Institute, Germany o Kaisa Sere, Abo Akademi University, Finland o Peter Van Roy, University of Louvain-la-Neuve, Belgium o Mirko Viroli, Alma Mater Studiorum Università di Bologna a Cesena, Italy

1 0

Installation with yum.
by Manoj Kummini 16 Feb '05

16 Feb '05

Hi. I am trying to install haskell on FC3 following the instructions from http://www.haskell.org/fedora/ I copied the lines: root@blandings ~# cat /etc/yum.repos.d/haskell.repo [haskell-stable] name=Haskell Packages (stable) baseurl=http://haskell.org/fedora/haskell/$releasever/$basearch/RPMS.stable gpgcheck=1 installdir=/opt root@blandings ~# When I try to install it, nothing happens, and I get the following message: root@blandings ~# yum install haskell-stable Setting up Install Process Setting up Repo: base repomd.xml 100% |=========================| 1.1 kB 00:00 Setting up Repo: haskell-stable repomd.xml 100% |=========================| 951 B 00:00 Setting up Repo: updates-released repomd.xml 100% |=========================| 951 B 00:00 Reading repository metadata in from local files base : ################################################## 2622/2622 haskell-st: ################################################## 53/53 primary.xml.gz 100% |=========================| 292 kB 03:02 MD Read : ################################################## 684/684 updates-re: ################################################## 684/684 No Match for argument haskell-stable Nothing to do root@blandings ~# I am new to yum, and could not find much help on the web for using this. Could someone tell me what I am missing or point to a URL? Thanks Manoj. -- Manoj Kummini Graduate Student, Dept. of Mathematics, The Univ. of Kansas, Lawrence KS 66045 USA. 38 deg 55 min N, 95 deg 14 min W. http://www.math.ku.edu/~kummini/index.html

2 1

Writer monad
by Emil Axelsson 16 Feb '05

16 Feb '05

Hello, I have a huge space leak in a program due to laziness in the writer monad. Now when I'm trying to examine the behaviour of writer I get a bit puzzled by the following program: foo :: MonadWriter [Int] m => Int -> m () foo n = do tell [n] foo $ n+1 test = (snd $ runWriter $ foo 0) !! 3 testT = (snd $ runIdentity $ runWriterT $ foo 0) !! 3 I would expect both test and testT to terminate with the value 3, due to the laziness that caused me problems. But here is the actual run results: Ok, modules loaded: Main. *Main> test 3 *Main> testT *** Exception: stack overflow *Main> Could someone please explain this to me? / Emil

2 1

[Newbie] Data structure for Dijkstra's algorithm
by RCP-Software 14 Feb '05

14 Feb '05

Hi! I am new to functional Programming and need some advice. I want to implement Dijkstra's algorithm for the shortest path problem. The algorithm calculates the shortest path from a single vertex in a directed graph to any other connected vertex ( http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm ). For input and output I need an appropriate graph representation. It should be as simple to implement as possible - speed and memory consumption does not matter. The graph consists of vertices (including the source vertex) and weighted edges. I first thought of an adjacency matrix implemented with nested lists. Something like [[0,1,6,2] , [1,0,2,infinity] , [6,2,0,3] , [2,infinity,3,0]] where every sublist represents a vertex, and every entry represents the edge weight to another vertex (infinity means there is no direct connection, and 0 means it points to itself). My main problem is that this adjacency list is not so easy to process. For my output I need a tree like structure and I always need to keep track of the previous vertex and its distance etc. Other approaches e.g. structure-like tuples didn't really work - my C experience is worthless. Bottom line - I don't what to do. Any help is appreciated. TIA, Robert Potthast

6 5

Re: help with some basic code that doesn't work
by Shin-Cheng Mu 14 Feb '05

14 Feb '05

Malcolm Wallace <Malcolm.Wallace(a)cs.york.ac.uk> wrote: > Just a comment, since a couple of people have made similar statements. > Haskell will derive Eq for arbitrarily complex types - there is no > restriction to "simple" types, whatever they might be. Now that this topic is brought up... Occasionally I would need to define recursive datatypes using an explicit fixed-point operator, such as: > data Fix f = In (f (Fix f)) deriving (Show, Eq) > data L a x = Nil | Cons a x deriving (Show, Eq) However, Haskell was not able to derive from Fix f any instances. The following is what happens in GHCi: *Main> In Nil == In Nil Context reduction stack overflow; size = 21 Use -fcontext-stack20 to increase stack size to (e.g.) 20 `Eq (L e (Fix (L e)))' arising from use of `==' at <interactive>:1 `Eq (Fix (L e))' arising from use of `==' at <interactive>:1 <<deleted>> *Main> In Nil Context reduction stack overflow; size = 21 Use -fcontext-stack20 to increase stack size to (e.g.) 20 `Show (L e (Fix (L e)))' arising from use of `print' at <interactive>:1 <<deleted>> Probably Malcolm meant that Haskell will derive standard instances for arbitrarily complex type **if they are definable manually**. If so Malcolm's statement is true -- indeed I cannot even declare the instances by hand. The following declaration is acceptable by GHC after using the option -fallow-undecidable-instances, but even though, I got the same error message as I try to print In Nil. > Instance Show (f (Fix f)) => Show (Fix f) where > showsPrec _ (In x) = ("In ("++) . showsPrec 1 x . (')':) This is rather unsatisfactory, because I would not be able to inspect values of type Fix f in the interpreter. Is there a way to get around this? sincerely, Shin

4 3

Using hs-plugins with ghci
by Javier García-Vivó Albors 12 Feb '05

12 Feb '05

Hello everybody. I'm trying to use hs-plugins library with ghci and this is the result: >>> ghci -package plugins ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.2.1, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base ... linking ... done. Loading package altdata ... linking ... done. Loading package haskell98 ... linking ... done. Loading package hi ... linking ... done. Loading package unix ... linking ... done. Loading package lang ... linking ... done. Loading package posix ... linking ... done. Loading package haskell-src ... linking ... done. Loading package plugins ... linking ... /usr/local/lib/hs-plugins/HSplugins.o: unknown symbol `addDLL' ghc-6.2.1: panic! (the `impossible' happened, GHC version 6.2.1): can't load package `plugins' Please report it as a compiler bug to glasgow-haskell-bugs(a)haskell.org, or http://sourceforge.net/projects/ghc/. Does anybody know how to fix it?? I'm getting crazy with this problem!! Thanks a lot. ---------------------------------------------------------------- This message was sent using IMP, the Internet Messaging Program.

3 2

2nd CFP Coordination and Organisation (CoOrg05)
by L.W.N.van.der.Torre＠cwi.nl 11 Feb '05

11 Feb '05

Second Call for Papers Submission site is now open (strict deadline March 1): http://coorg05.di.unito.it/ 1st International Workshop on Coordination and Organisation (CoOrg 2005) CoOrg 2005 is a one day workshop affiliated with the Seventh International Conference on Coordination Models and Languages (COORDINATION 2005), Namur, Belgium, April 20-23, 2005. (http://www.coordination2005.org) Workshop goals Organizations embody a powerful way to coordinate complex behavior in human society. Different models of organisations exist, from bureaucratic systems based on norms to competitive systems based on markets. Moreover, organizational concepts allow to structure the behavior of complex entities in a hierarchy of encapsulated entities: departments structured in roles, organisations structured in departments, and interorganizational coordination structured in organizations. Organizations specify the interaction and communication possibilities of each of these entities, abstracting from the implementation of their behavior. Since these entities are autonomous, they can only be coordinated exogeneously. Organisational models have been popular in the last years in agent theory for modelling coordination in open systems, where departments and organisations are modelled as autonomous entities. This is also due to the need to ensure social order within MAS applications like Web Services, Grid Computing, and Ubiquitous Computing. In these settings, openness, heterogeneity, and scalability pose new challenges on traditional MAS organizational models. It becomes necessary to integrate organizational and individual perspectives and to promote the dynamic adaptation of models to organizational and environmental changes. Nowadays, practical applications of agents to organizational modeling are being widely developed. Moreover, organisational concepts are used frequently for coordination purposes in different areas of Computer Science. For example, roles are used in access control, conceptual modelling, programming languages and patterns. Contracts are used in design by contract, and services are used in web services and service level agreements. Message based communication is used in networking. Finally, coordination techniques are used in formal models of organisations to analyse or simulate them. In contrast, most coordination languages refer mostly to different kinds of metaphors, like blackboards, shared dataspaces, component composition and channels. Although coordination is usually said to be of a multidisciplinary nature, the links between organisations and coordination have never received proper attention at the coordination conferences. CoOrg 2005, as part of COORDINATION2005, will provide an excellent opportunity to meet researchers studying coordination and organisations in cognitive science, social sciences, agent theory, computer science, philosophy, etc., to discuss the current state of the art and identify potential future directions and research issues. Topics of interest The topics of this symposium include, but are not restricted to, the following: * organisational concepts and methods for coordination: o role based coordination o contract based coordination o coordination in normative multiagent systems o service oriented coordination * coordination techniques for organisations: o normative systems o markets o authority and power o trust * interorganisational coordination o control of autonomy in coordination o integration of organizations * applications of coordination and organisation: o multiagent social simulation models o organization based software engineering o organization oriented programming o organizational patterns Invited speaker Andrea Omicini, University of Bologna Proceedings The papers accepted for the symposium will be available at the workshop. Moreover, selected work will be published in a volume of ENTCS. Important Dates * March 1, 2005: Submissions deadline * March 15, 2005: Notification of authors * April 1, 2005: camera ready copies deadline * April 20-23, 2005: COORDINATION 2005 conference Submissions The length of each paper including figures and references must be between 10 and 15 ENTCS style pages. All papers must be submitted in PDF or postscript format. Papers are to be submitted through the following web address: http://coorg05.di.unito.it/. Submissions should explicitly state their contribution and their relevance to the theme of the workshop. Other criteria for selection will be originality, significance, correctness, and clarity. Simultaneous or similar submissions to other conferences or journals are allowed, when this is indicated on the first page of the submitted paper. Chairs Leon van der Torre, CWI Amsterdam, The Netherlands Guido Boella, Department of Computer Science, Universita' di Torino, Italy Program committee * Farhad Arbab - CWI Amsterdam and University Leiden * Frank de Boer - CWI Amsterdam and University Leiden * Guido Boella - Dipartimento di Informatica, Universita' di Torino (co-chair) * Olivier Boissier - Systemes Multi-Agents G2I, ENSM.SE Saint-Etienne * Cristiano Castelfranchi - Institute of Cognitive Sciences and Technologies (ISTC), Italy * Kevin Crowston - Syracuse University * Mehdi Dastani - University of Utrecht * Joris Hulstijn - Vrije Universiteit Amsterdam * Andrea Omicini - University of Bologna * Pierre-Yves Schobbens - Institut d'Informatique University of Namur * Carles Sierra - IIIA of the Spanish Research Council, Barcelona * Leon van der Torre - CWI Amsterdam (co-chair) On the web SYMPOSIUM WEBSITE: http://boid.info/CoOrg05 COORDINATION 2005 WEBSITE: http://www.coordination2005.org/

1 0

Cfp: ICTCS'05 conference
by g. michele pinna 11 Feb '05

11 Feb '05

Ninth Italian Conference on Theoretical Computer Science (ICTCS'05) Certosa di Pontignano (Siena), Italy October 12 - 14, 2005 http://ictcs05.dsmi.unisi.it Call for Papers The Ninth Italian Conference on Theoretical Computer Science will take place at the Certosa di Pontignano (Siena), Italy. Papers presenting original contributions in any area of theoretical computer science are being sought. Topics include (but are not limited to): analysis and design of algorithms, computability, computational complexity, cryptography, formal languages and automata, foundations of programming languages and program analysis, foundations of artificial intelligence and knowledge representation, foundations of web programming natural computing paradigms (quantum computing, bioinformatics), parallel and distributed computation, program specification and verification, term rewriting, theory of concurrency, theory of data bases, theory of logical design and layout, type theory, security, symbolic and algebraic computation, Program Committee: Michele Bugliesi (Venezia), Mario Coppo (Torino, Co-Chair), Pierluigi Crescenzi (Firenze), Giulia Galbiati (Pavia) Luisa Gargano (Salerno), Giorgio Ghelli (Pisa), Roberto Grossi (Pisa), Benedetto Intrigila (L'Aquila), Nicola Leone (Cosenza), Elena Lodi (Siena, Co-Chair), Flaminia Luccio (Trieste), Andrea Masini (Verona), Giancarlo Mauri (Milano), Corrado Priami (Trento), Geppino Pucci (Padova), Davide Sangiorgi (Bologna). Organizing Committee: S. Brunetti (Siena), G. Michele Pinna (Cagliari - Siena, Chair), E.B.P. Tiezzi (Siena). Invited Speakers: Luca Cardelli (Microsoft Research, Cambridge, United Kingdom) Giuseppe Castagna (LIENS - École Normale Supérieure, Paris, France) Nicola Santoro (School of Computer Science, Carleton University, Ottawa, Canada) Dates and Deadlines: Submission Deadline: 15 April 2005 Acceptance Notification: 7 June 2005 Camera-ready deadline: 2 July 2005 Early registration deadline: 16 September 2005 Conference: 12-14 October 2005 Submissions: Authors are invited to submit electronically one copy of their draft paper, not exceeding fifteen pages. The paper should clearly indicate the results achieved, their significance, and their relation to other work in the area. Extended proofs can be placed in a clearly marked appendix. It is planned to publish the proceedings in the Springer Lecture Notes in Computer Science series. To uniform the submissions the authors are encouraged to use Latex and the Springer LNCS style (www.springer.de/comp/lncs) The web-based submission form is available at the page ictcs05.dsmi.unisi.it/submission.html. In case electronic submission is not possible, the authors should contact: Mario Coppo Dipartimento di Informatica, Universita' di Torino Corso Svizzera 185 I-10149 Torino, Italy email: coppo(a)di.unito.it Conference Page: This Call For Papers is available online at the conference web page ictcs05.dsmi.unisi.it Registration Details: The registration form will be reachable from the conference web page. A limited number of grants for students and young researchers covering the registration fees are available. Details for the applications are in the conference web page.

1 0