- Haskell - Haskell.org

graphs and trees again
by Wolfgang Jeltsch 13 Jan '04

13 Jan '04

Hello, for my studies I recently needed graph and tree handling code. Because nothing I found seemed to satisfy my needs, I finally started writing my own graph and tree module. I was especially disappointed with Data.Graph and Data.Tree. The reasons are: * The Implementation of the types is not hidden so that code using Data.Graph and Data.Tree can get very implementation-dependent. * Vertices are ints which is too low level in my opintion. I think it would be better to allow different types for vertices because this seems to closer reflect what applications demand. * I'd prefer to be able to use arbitrary sets of vertices instead of only continuous ranges. * There are only very few functions for trees and forests. Is there any interest for improving or even rewriting these two modules? Maybe, I could contribute here. For those interested in my graph and tree modules, I attached them to this mail. By the way, they don't use any non-standard features. Note that I wrote them as a part of a university project so that I'm probably not allowed to license them privately. Therefore they should be only looked at but not used in any other way. Wolfgang

1 0

C++ preprocessor, Was: Uniqueness types in FC++
by Jan Kybic 13 Jan '04

13 Jan '04

> as well. But if we're going to do this, we may as well define a new > "FC++ language" in its own right and write a compiler which converts > this into C++ code. Yes! I fully back this approach, please let me know if you start a project like this. I would propose to use a Haskell-like language as the "source", because it is nice, clean and FC++ is modeled after it anyway. This would simplify the tedious, repetitive and error-prone writing of FC++ signatures. I would only vote for making the language strict, not lazy by default, or perhaps controlling the strictness the way Clean does, since I found that (unwanted) laziness was slowing my programs tremendously at getting rid was difficult (for me) and made the programs ugly. The seamless interoperability with C++ would be a clear win for me, since there is so many libraries already available for C++ and besides, some parts of the program might be better suited for imperative programming. Yes, I had a look at the Felix programming language and I liked it, but I found it too Ocam-like - I find it's approach to genericity (C++ templates) using modules much heavier than in Haskell, where you get genericity without any extra effort, unless you ask for specialized version. Yours, Jan -- ------------------------------------------------------------------------- Jan Kybic <kybic(a)ieee.org> tel. +420 2 2435 7264 or <kybic(a)fel.cvut.cz>, http://cmp.felk.cvut.cz/~kybic

1 0

CFP: Workshop on Constraint Programming and Constraint for Verification (CP+CV'04)
by Giorgio Delzanno 13 Jan '04

13 Jan '04

================================================================================ CALL FOR PAPERS Workshop on Constraint Programming and Constraint for Verification (CP+CV'04) March 28, Barcelona, Spain at the European Joint Conferences on Theory and Practice of Software (ETAPS) Home page: http://www.mpi-sb.mpg.de/conferences/cpv04/ ================================================================================ OVERVIEW The use of constraints had its scientific and commercial breakthrough in the 1990s. Programming with constraints makes it possible to model and specify problems with uncertain, incomplete information and to solve combinatorial problems, as they are abundant in industry and commerce, such as scheduling, planning, transportation, resource allocation, layout, design, and analysis. Constraint-based programming languages enjoy elegant theoretical properties, conceptual simplicity, and practical success. The aim of the workshop is to provide opportunity for interactions with the other ETAPS'04 events and to be a major meeting point in the research area inbetween the Constraint Programming conferences, which are held each autumn. The workshop will consist of sessions with invited talks that summarize the main challenges and/or application potential for the community, and sessions with short presentations describing ongoing work. Taking inspiration from the CP 02 workshop CFV, we will have a special track dedicated to "formal verification". In recent years there has been an increasing interest for the application of constraint programming and constraint solving technology to the formal verification of hardware and software systems. Constraint solvers for Boolean (SAT) and arithmetic domains (Presburger, polyhedra, linear constraints) are widely used as subprocedures of symbolic model checkers (e.g. nuSMV) and of model checkers for hybrid and real time systems (e.g. HyTech, Uppaal). Constraint solving is also used for computing static analysis of programs with numerical data variables and concurrent systems (e.g. via the Structural Theory of Petri Nets). The aim of this special track is to bring together researchers working in constraints and verification and to investigate the theoretical foundations, new applications, and future developments in this area. SUBMISSION To submit, send an email to Giorgio Delzanno giorgio(a)disi.unige.it containing four consecutive ASCII lines with title, author(s), email(s) and WWW link directly to compressed postscript file (5-15 pages). Accepted papers will be available electronically at the workshop web-page and may be published in hard-copy proceedings (available at the workshop). ORGANISATION AND PROGRAM COMMITTEE Giorgio Delzanno, DISI - University of Genova Thom Fruehwirth, University of Ulm Francois Fages, INRIA Rocquencourt Joao Marques-Silva, Technical University of Lisbon, IST/INESC-ID/CEL Andreas Podelski, MPI - Saarbruecken Peter Stuckey, University of Melbourne IMPORTANT DATES January 28, 2004: Paper submissions February 25, 2004: Acceptance decisions March 12, 2004: Final version due March/April, 2004: Workshop at ETAPS 2004

1 0

RE: GHC, functional dependency, rank-2 type
by Simon Peyton-Jones 13 Jan '04

13 Jan '04

That is indeed bizarre. I'll look into it. Simon | -----Original Message----- | From: haskell-bounces(a)haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of | oleg(a)pobox.com | Sent: 13 January 2004 05:51 | To: haskell(a)haskell.org | Subject: GHC, functional dependency, rank-2 type | | | There appears to be a problem with GHC's handling of multi-parameter | constraints with functional dependencies in the context of rank-2 | types. The problem is not present in Hugs. | | Let us first consider a simple example: | | > module Test where | > class Foo a | > | > class Bar a | > | > data Obj = Obj | > | > instance Bar Obj | > | > instance (Bar a) => Foo a | > | > foo:: (Foo a) => a -> String | > foo _ = "works" | > | > runFoo:: (forall a. (Foo a) => a -> w) -> w | > runFoo f = f Obj | | Here, the type of foo indicates | | > Test> :t foo | > foo :: Foo a => a -> String | | that foo can be applied to the value of any type so long as it is in | class Foo. The type of runFoo says that runFoo takes a function that | can process the value of every type of class Foo. The function foo | seems to be such a function. Therefore, "runFoo foo" should be | well-typed. And it is, and it works, both in Hugs (version November | 2002) and in GHC 6.0.1 (which is the current version for FreeBSD). | | However, if we make the classes Foo and Bar seemingly multi-parameter, | the trouble begins: | | > class Foo a b | a->b | > | > class Bar a b | a->b | > | > data Obj = Obj | > | > instance Bar Obj Obj | > | > instance (Bar a b) => Foo a b | > | > foo:: (Foo a b) => a -> String | > foo _ = "works" | > | > runFoo:: (forall a b. (Foo a b) => a -> w) -> w | > runFoo f = f Obj | | In Hugs: | | > Test> :t foo | > foo :: Foo a b => a -> String | > Test> runFoo foo | > "works" | | As before, the function foo promises to handle the value of any type a | so long as "Foo a b" is satisfied (for any b -- although there can be | only one such b, due to the functional dependency). The function | runFoo takes any function that can handle the value of any type "a" | subject to the "Foo a b" constraint. So, "runFoo foo" should be | well-typed and should work. And it is, in Hugs. | | GHC 6.01 is a different matter, unfortunately. An attempt to load the | above code in GHC succeeds, with flags: | {-# OPTIONS -fglasgow-exts -fallow-undecidable-instances #-} | | Furthermore, the types of foo and runFoo seem to be in perfect match. | | > *Test> :t foo | > foo :: forall a b. (Foo a b) => a -> String | > *Test> :t runFoo | > runFoo :: forall w. (forall a b. (Foo a b) => a -> w) -> w | | And yet, | | *Test> runFoo foo | | <interactive>:1: | Could not deduce (Bar a b) from the context (Foo a b) | arising from use of `foo' at <interactive>:1 | Probable fix: | Add (Bar a b) to the expected type of an expression | In the first argument of `runFoo', namely `foo' | In the definition of `it': it = runFoo foo | | Why all of the sudden does GHC need the constraint Bar a b? The | function foo didn't ask for that... However, if we define foo and | runFoo as follows: | | > foo:: (Foo a b) => a -> b -> String | > foo _ _ = "works" | > | > runFoo:: (forall a b. (Foo a b) => a -> b -> w) -> w | > runFoo f = f Obj Obj | | then both GHC and Hugs are happy: "runFoo foo" says that it works in both. | | What's more bizarre, even the following works: | | > runFoo:: (forall a b. (Foo a b) => a -> b -> w) -> w | > runFoo f = f Obj undefined | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell

1 0

Preliminary CFP: DALT 2004 - 2nd Workshop on Declarative Agent Languages and Technologies
by João Leite 13 Jan '04

13 Jan '04

------------------------------------------------------------- P R E L I M I N A R Y C A L L F O R P A P E R S The Second International Workshop on Declarative Agent Languages and Technologies (DALT-2004) http://centria.di.fct.unl.pt/~jleite/dalt04/index.htm to be held at the The Third International Joint Conference on Autonomous Agents & Multi-Agent Systems (AAMAS 2004) New York, USA 19 or 20 July 2004 ------------------------------------------------------------- ---------- Overview: ---------- Building multi-agent systems still calls for models and technologies that ensure system predictability, enable feature discovery and verification, and accommodate flexibility. Declarative approaches offer to satisfy precisely these properties of large-scale multi-agent systems. Recent advances in the area of computational logics provide a strong foundation for declarative languages and technologies. Equipped with such strong foundation, declarative approaches can enable agents to reason about their interactions and their environment and hence not only establish the required tasks but also handle exceptions that arise in many systems. However, a great effort still has to be done to make formal methods and declarative technologies available to the broader agent community, and to apply theoretical results to enable practical implementation of agent systems. Accordingly, Declarative Agent Languages and Technologies (DALT) workshop aims at bringing together (1) researchers working on formal methods for agent and multi-agent systems design, (2) engineers interested in exploiting the potentials of declarative approaches for specification of agent-based systems, and (3) practitioners exploring the technology issues arising from a declarative representation of systems. Topics of interest include, but are not limited to: Declarative agent communication and coordination languages Declarative approaches to the engineering of agent systems Experimental studies of declarative technologies Industrial and commercial experiences with declarative agent technologies Formal methods for the specification and verification of agent systems Computational logics in multi-agent systems Argumentation and dialectical systems Declarative description of contracts and negotiation issues Lessons learned from the design and implementation of agent systems Declarative paradigms for the combination of heterogeneous agents Constraints and agent systems Declarative policies and security in MAS Knowledge-based and knowledge-intensive MAS Modeling of agent rationality ---------------- Important dates: ---------------- Submission: April 1st, 2004 Notification: May 1st, 2004 Final Version: May 21st, 2004 DALT 2004: July 19th or 20th, 2004 ------------ Submission: ------------ Papers should be written in English, formatted according to the Springer LNCS style, and not exceed 16 pages. Paper submission is electronic via the conference home page. ------------ Publication: ------------ A printed volume with the proceedings will be available at the workshop. DALT 2003 post-proceedings are being published by Springer-Verlag as a volume of the LNAI series. Some contacts have already been made towards collecting the papers presented at DALT 2004 in the form of a journal special issue or a book from an international publisher. --------------------- Organizing Committee: --------------------- João Leite (Universidade Nova de Lisboa) Andrea Omicini (Università di Bologna a Cesena) Paolo Torroni (Università di Bologna) PInar Yolum (Vrije Universiteit Amsterdam) ------------------ Program Committee: ------------------ Rafael Bordini, The University of Liverpool, UK Marco Colombetti, Politecnico di Milano, Italy Stefania Costantini, Università degli Studi di L'Aquila, Italy Mehdi Dastani, Universiteit Utrecht, The Netherlands Jürgen Dix, The University of Manchester, UK Michael Fisher, University of Liverpool, UK Mike Huhns, University of South Carolina, USA Catholijn Jonker, Vrije Universiteit Amsterdam, The Netherlands Alessio Lomuscio, King's College, London, UK Viviana Mascardi, DISI, Genova, Italy John Jules Ch. Meyer, Universiteit Utrecht, The Netherlands Charles L. Ortiz, SRI International, Menlo Park, CA, USA Sascha Ossowski, Universidad Rey Juan Carlos, Madrid, Spain Lin Padgham, RMIT University, Australia Luís Moniz Pereira, Universidade Nova de Lisboa, Portugal Jeremy Pitt, Imperial College, London, UK Juan Rodriguez-Aguilar, Spanish Research Council, Spain Fariba Sadri, Imperial College, UK Marek Sergot, Imperial College, UK Onn Shehory, IBM Research Lab in Haifa, Israel Munindar Singh, North Carolina State University, USA Wiebe van der Hoek, The University of Liverpool, UK Wamberto Vasconcelos, University of Aberdeen, UK Michael Winikoff, RMIT University, Australia

1 0

Call for papers: Fourth International Workshop on Reduction Strategies in Rewriting and Programming (WRS'04)
by Sergio Antoy 13 Jan '04

13 Jan '04

=============================================================== We apologize for multiple copies of this call for participation =============================================================== ******************************** * * * WRS'04 CALL FOR PAPERS * * * ******************************** http://www-i2.informatik.rwth-aachen.de/WRS04/ The Fourth International Workshop on Reduction Strategies in Rewriting and Programming (WRS'04) will be held on June, 2, 2003, in Aachen, Germany, as a part of the Federated Conference on Rewriting, Deduction, and Programming (RDP'04). IMPORTANT DATES: March 17, 2004 Deadline for electronic submission of papers April 14, 2004 Notification of acceptance of papers May 2, 2004 Deadline for final versions of accepted papers June 2, 2004 Workshop TOPICS include, but are not restricted to: * theoretical foundations for the definition and semantic description of reduction strategies * strategies in different frameworks (term rewriting, graph rewriting, infinitary rewriting, lambda calculi, higher order rewriting, conditional rewriting, rewriting with built-ins, narrowing, constraint solving, etc.) and their application in (equational, functional, functional-logic) programming (languages) * properties of reduction strategies / computations under strategies (e.g., completeness, computability, decidability, complexity, optimality, (hyper-)normalization, cofinality, fairness, perpetuality, context-freeness, neededness, laziness, eagerness, strictness) * interrelations, combinations and applications of reduction under different strategies (e.g., evaluation mechanisms in programming languages, equivalence conditions for fundamental properties like termination and confluence, applications in modularity analysis, connections between strategies of different frameworks, etc.) * program analysis and other semantics-based optimization techniques dealing with reduction strategies * rewrite systems / tools / implementations with flexible / programmable strategies as essential concept / ingredient * specification of reduction strategies in (real) languages * tutorials and systems related to evaluation strategies INVITED TALKS will be given by: * Olivier Danvy (University of Aarhus, Denmark), Normalization by Evaluation * Jan Willem Klop (Vrije Universiteit Amsterdam, The Netherlands), Reduction Cycles PROGRAM COMMITTEE: Sergio Antoy Portland (USA) (co-chair) Roberto Di Cosmo Paris VII (France) Juergen Giesl Aachen (Germany) Bernhard Gramlich Wien (Austria) Salvador Lucas Valencia (Spain) Aart Middeldorp Innsbruck (Austria) Jaco van de Pol Amsterdam (The Netherlands) Pierre Rety Orleans (France) Amr Sabry Bloomington (USA) Yoshihito Toyama Sendai (Japan) (co-chair) SUBMISSIONS: We solicit papers on all aspects of reduction strategies in rewriting and programming. Submissions should describe unpublished work, except for survey papers which are explicitly welcome, too. Submissions should not exceed 10 pages (however, survey papers may be longer) and be sent in PostScript or PDF format to the PC co-chairs at wrs04(a)redstar.cs.pdx.edu by March 17, 2004. The use of the style file available from the RDP workshop style page is encouraged. The call-for papers is also available in PDF format. Submissions should include the title, authors' names, affiliations, addresses, and e-mail. Selection of papers by the PC will be based on originality, significance, and correctness. Final versions will be due by May 2, 2004. PUBLICATION: Accepted papers will be included in the preliminary workshop proceedings that will be available at the workshop. The final workshop proceedings will be published in Elsevier's Electronic Notes in Theoretical Computer Science (ENTCS) series. For further questions please contact the program co-chairs: Sergio Antoy and Yoshihito Toyama at wrs04(a)redstar.cs.pdx.edu.

1 0

subset test
by Wolfgang Jeltsch 12 Jan '04

12 Jan '04

Hello, I just discovered that currently there is no subset test function in Data.Set. Could such a function be added? Wolfgang

1 0

mkSet on sorted lists
by Wolfgang Jeltsch 12 Jan '04

12 Jan '04

Hello, does Data.Set.mkSet run in linear time when applied to a sorted list? Wolfgang

2 3

MS-Windows build of Hugs with experimental Unicode support
by Graham Klyne 12 Jan '04

12 Jan '04

Further to my last message [1], if anyone else wants to play with the experimental Unicode support for Hugs under MS-Windows, I've placed a Windows executable file on my Web site, linked from [2]. #g -- [1] http://haskell.org/pipermail/haskell/2004-January/013377.html [2] http://www.ninebynine.org/Software/FatHugs.html ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

Building experimental Unicode version of Hugs on Windows
by Graham Klyne 12 Jan '04

12 Jan '04

In my previous note about building Hugs under Windows using MS Visual Studio, I omitted a couple of details, so I update my notes here... Starting with: http://cvs.haskell.org/Hugs/downloads/snapshots/hugs98-20040109.tar.gz Using Microsoft Visual Studio, version 6, and the supplied project file (hugs.dsw): (1) edit src/msc/options.h to include #define UNICODE_CHARS 1 (2) run config.bat to copy options.h and config.h to the source directory (3) Add the following files to the Visual Studio project: char.c edit.c errors.c evaluator.c goal.c machdep.c module.c observe.c opts.c script.c strutil.c (4) Change the Visual Studio project to specify ../../icons for the resource include path. (5) In version.c, changed the definition of VERSION_STRING to some value that this instantiation of Hugs will use as part of the registry key for saving its options (to avoid disturbing settings for the standard Hugs installstion). The build still throws up an obscure error: [[ Install hugs binary The system cannot find the file specified. Error executing c:\winnt\system32\cmd.exe. ]] but this doesn't affect the resulting executable, which ends up in a subdirectory of .../src/msc, depending on the option being built. Copied the resulting executable into the Hugs installation directory, using a different filename (preferably related to the VERSION_STRING value used above). Using a version of Hugs built as above, I've been able to run a complex test suite program. My next step is to see if the Unicode support is sufficient to run the HXML toolbox software. ... Attempting to load module HUnitExample.hs from the 3.01 HXML toolbox distribution (), I'm getting: [[ ERROR "..\hparser\Unicode.hs":116 - Hexadecimal character escape out of range ]] The corresponding source code is this: [[ -- | -- test for a legal multi byte XML char isMultiByteXmlChar :: Unicode -> Bool isMultiByteXmlChar i = ( i >= '\x00000080' && i <= '\x0000D7FF' ) || ( i >= '\x0000E000' && i <= '\x0000FFFD' ) || ( i >= '\x00010000' && i <= '\x0010FFFF' ) ]] (The final line is number 116) Digging deeper, I see that the Hugs support has MAX_UNI_CHAR is 0x10FFFD, but the Haskell toolbox uses 0x10FFFF. Which is correct? For now, I'll edit the Hugs source, file unitable.c (not forgetting to increase the size of the final Char_Block entry by 2). That seems to be accepted, but subsequently I'm having some problems with the HXML source code, which I'll report separately. #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0