December 2002 - Haskell

RE: Running out of memory in a simple monad
by Simon Marlow 18 Dec '02

18 Dec '02

> Simon Marlow <simonmar(a)microsoft.com> writes: > > Also, GHCi retains CAFs in the same way as Hugs, the difference is > > that GHCi can be configured to throw away the results after > > evaluation (:set +r). > > If I set this flag, does GHCi discard CAFs during evaluation or at the > end of evaluation? Or, to put it another way, do classic > examples like > > module Main(main,primes) where > > main = print primes > primes = ... > > leak space? Actually CAF reverting only applies to CAFs in compiled code at the moment, and it happens after evaluation, not during it. The primes example will leak in GHCi (not in plain GHC, though). I guess the right thing to do is to revert them as soon as they're found to be unreferenced, but that's hard - the compiler's symbol table refers to all the top-level bindings, so it would probably have to use weak pointers. The CAF reverting feature was added mainly so that you can recover from doing hGetContents on stdout. Cheers, Simon

1 0

RE: Running out of memory in a simple monad
by Simon Marlow 18 Dec '02

18 Dec '02

Alastair Reid writes: > The workaround is simple enough: add a dummy argument to the CAF (so > that it is not a CAF any more): > > main _ = loop 50000 > > and then specify the extra argument when invoking it: > > main () > > (This is a pretty standard optimisation technique: we're trading time > to recompute a result for the space taken to store the result. Coming > from other languages where actions (i.e., monadic computations) are > not first class values, this is a bit surprising but, from a Haskell > perspective, it is completely uniform.) Careful: this isn't guaranteed to turn a CAF into a function. In particular, GHC will "optimise away" this trick when optimisation is turned on (and perhaps even when it isn't). The point is that adding dummy arguments isn't really a technique that should be relied upon. You might well argue that there ought to be a way to control the operational behaviour of the program w.r.t. CAFs (and in fact sharing in general), and I'd be inclined to agree. Also, GHCi retains CAFs in the same way as Hugs, the difference is that GHCi can be configured to throw away the results after evaluation (:set +r). Cheers, Simon

2 1

CfP: Workshop on Security Issues in Coordination Models, Languages and Systems
by Gianluigi Zavattaro 18 Dec '02

18 Dec '02

====================================================================== 1st International Workshop on Security Issues in Coordination Models, Languages and Systems (SecCo 2003) June 28-29, 2003, Eindhoven, the Netherlands Workshop affiliated to ICALP 2003, June 30 - July 4, 2003 http://cs.unibo.it/secco03 ====================================================================== SCOPE AND TOPICS New networking technologies are calling for the definition of models and languages adequate for the design and management of new classes of applications. Innovations are moving towards two directions: on the one hand, the Internet which supports wide area applications, on the other hand, smaller networks of mobile and portable devices which support applications based on a dynamically reconfigurable communication structure. In both the cases, the challenge is to develop applications while there is at design time no knowledge of involved entities. Coordination models and languages, which advocate a distinct separation between the internal behaviour of the entities and their interaction, represent a promising approach. However, due to the openness of these systems, new critical aspects come into play, such as the need to deal with malicious components or with a hostile environment. Current research on network security issues (e.g. secrecy, authentication, etc.) usually focuses on opening cryptographic tunnels between fully trusted entities. For this to work the structure of the system must be known beforehand. Therefore, the proposed solutions in this area are not always exploitable in this new scenario. The aim of the workshop is to cover the gap between the security and the coordination communities. More precisely, we intend to promote the exchange of ideas, focus on common interests, gain in understanding/deepening of central research questions, etc. Topics of interest include, but are not limited to: o Theoretical foundations, specification, analysis, case-studies, applications for authentication coordination models integrity open-distributed systems privacy mobile ad-hoc networks confidentiality agent-based infrastructures access control -in- peer-to-peer systems denial of service global computing service availability context-aware computing safety aspects component-based systems fault tolerance ubiquitous computing SUBMISSION GUIDELINES Submissions may be of two forms: o Short abstracts: up to 5 pages 11 pt, o Full papers: up to 12 pages 12 pt. They should be sent as PS or PDF to: secco03(a)cs.unibo.it The workshop proceedings will be published in the ENTCS series (Electronic Notes in Theoretical Computer Science) and full versions of selected papers will be likely invited for publication in a special issue of Science of Computer Programming (Elsevier). IMPORTANT DATES April 27, 2003: Submission deadline June 2, 2003: Notification of acceptance June 13, 2003: Pre-Final version June 28-29, 2003: Meeting date July 31, 2003: Final version WORKSHOP ORGANIZERS o Riccardo Focardi Dipartimento di Informatica Universita` Ca' Foscari di Venezia Via Torino, 155 I-30172 Mestre (Ve), Italy E-mail: focardi(a)dsi.unive.it Web: http://www.dsi.unive.it/~focardi o Gianluigi Zavattaro Dipartimento di Scienze dell'Informazione Universita` degli Studi di Bologna Mura A. Zamboni, 7 I-40127 Bologna (BO), Italy E-mail: zavattar(a)cs.unibo.it Web: http://cs.unibo.it/~zavattar PROGRAM COMMITTEE Frank de Boer (Utrecht University, The Netherlands) Giuseppe Castagna (Ecole normale superieure - ENS, France) Riccardo Focardi (University of Venezia, Italy) - Co-Chair Cedric Fournet (Microsoft Research Cambridge, UK) Heiko Mantel (DFKI, Germany) Antony Rowstron (Microsoft Research Cambridge, UK) David Sands (Chalmers University, Sweden) Steve Schneider (Royal Holloway, University of London, UK) Jan Vitek (Purdue University, USA) Gianluigi Zavattaro (University of Bologna, Italy) - Co-Chair

1 0

PADL 2003: call for participation
by Enrico Special Account 18 Dec '02

18 Dec '02

PADL'03: Second Call for Participation o PADL Registration Deadline is fast approaching (Dec 20th). Please register electronically asap. o Please also note that the special conference rate for the hotel is available only until Dec. 23rd. o Highlights of the conference: 25 contributed papers and invited talks by Gerard Huet, David Page, and Shriram Krishnamurthi o Special rates for ACM and ALP members. -------------------------------------------------------------------------------------------- PADL 2003 Program. Monday 13 January 2003 9.00-10.00 (I) invited talk David Page, The Role of Declarative Languages in Mining Biological Databases. 10.00-10.30 break 10.30-12.00 (II) session (3 papers) Data mining the yeast genome in a lazy functional language, Amanda Clare and Ross D. King Non-monotonic Reasoning on Beowulf Platforms, E. Pontelli, M. Balduccini, F. Bermudez Datalog with Constraints: A Foundation for Trust Management Languages, Ninghui Li, John C. Mitchell 12.00-1.30 lunch 1.30-2.30 (III) invited talk Shriram Krishnamurthi, The Continue Server (or, How I Administered PADL 2002 and 2003) 2.30-3.00 break 3.00-4.00 (IV) session (2 papers) Web Programming with SMLserver, Martin Elsman and Niels Hallenberg An Integrated Information System powered by Prolog, Antonio Porto 4.00-4.30 break 4.30-6.00 (V) session (3 papers) JMatch: Iterable Abstract Pattern Matching for Java, Jed Liu, Andrew C. Myers Sequence Quantification, Peter Schachte Roll: A language for specifying die-rolls, Torben Mogensen Tuesday 14 January 2003 9.00-10.00 (VI) invited talk Gerard Huet, Zen and the Art of Symbolic Computing: Light and Fast Applicative Algorithms for Computational Linguistics. 10.00-10.30 break 10.30-12.00 (VII) parallel session (3 papers and 3 papers) Parallel session (a) Reconstructing the Evolutionary History of Indo-European Languages using Answer Set Programming., Esra Erdem, Vladimir Lifschitz, Luay Nakhleh, and Donald Ringe Multi-Agent Reactive Systems, Prahladavaradan Sampath ACTILOG: An Agent Activation Language, Jacinto A. Davila Parallel session (b) Logic Programs for Querying Inconsistent Databases, Pablo Barcelo and Leopoldo Bertossi A CLP-Based Tool for Computer Aided Generation and Solving of Maths Exercises, Ana Paula Tomas, Jose Paulo Leal A Logical Framework for Modelling eMAS, Pierangelo Dell'Acqua and Luis Moniz Pereira 12.00-1.30 lunch 1.30-2.30 (VIII) session (2 papers) SXSLT: Manipulation Language for XML, Oleg Kiselyov, Shriram Krishnamurthi Type-based XML Processing in Logic Programming, Jorge Coelho and Mario Florido 2.30-3.00 break 3.00-4.00 (IX) parallel session (2 papers and 2 papers) Parallel session (a) WAM Local Analysis, Michel Ferreira, Luis Damas Garbage Collection Algorithms for Java--Based Prolog Engines, Qinan Zhou, Paul Tarau Parallel session (b) Solving Combinatorial Problems with a Constraint Functional Logic Language, Antonio J. Fernandez, Teresa Hortala-Gonzalez and Fernando Saenz-Perez Logic Programs as Compact Denotations, Patricia M. Hill and Fausto Spoto 4.00-4.30 break 4.30-6.00 (X) session (3 papers) A Strafunski Application Letter, Ralf Laemmel and Joost Visser Functional Hybrid Modelling, Henrik Nilsson, John Peterson, Paul Hudak Lambda Goes to Hollywood, Victor M. Gulias, Juan J. Sanchez, Carlos Abalde

1 0

Re: ANNOUNCE: GHC version 5.04.2 released
by Jorge Adriano 17 Dec '02

17 Dec '02

Hi, Are there going to be SuSE rpms available anytime soon? Anyone working on them? Thanks, J.A.

1 0

fundeps question
by nalexand＠gianther.hypbus.com 17 Dec '02

17 Dec '02

I want to use functional dependencies in a way I've not yet seen: to enforce commutativity. I define class Mul a b c | a b -> c, b a -> c where mul :: a -> b -> c I want instance (Mul a b c) => Mul b a c where mul x y = mul y x do what I expect: if I can multiply a and b, then I can multiply b and a _and always have the same type_. In a sense, this makes multiplication commute (in the land of types). For a whole variety of reasons, the many (4 or 5 now) ways I've tried to make this work have failed, both using Hugs and GHC. I mentioned I wanted typed multiplication to commute. Let me explain more thoroughly: suppose I had data Unit u v = Unit u v I want (Unit u1 value1) `mul` (Unit u2 value2) to have the same type as (Unit u2 value2) `mul` (Unit u1 value1). So say u1 :: Int, u2 :: Float, then (Unit u1 value1) `mul` (Unit u2 value2) :: (Unit Int (Unit Float blah)) and (Unit u2 value2) `mul` (Unit u1 value1) :: (Unit Int (Unit Float blah)) I don't care if the result type is Unit Int ... or Unit Float ..., as long as it is a) consistent and b) inferred and c) enforced. So far, no luck. A few other questions: What happenned to +m in Hugs? In general, if I wanted a fundep to specify that a pair (a, b) determined c _regardless of the order of a and b_, how could it be done? Why doesn't a b -> c, b a -> c do this? What I mean is that if I have one of a, b and Int (say) and c a Float, then I could infer the other of a, b once I have a single instance. And a 'bug' report: in the overlapping instance one-liner above, the Mul a b c => Mul b a c, I can have this in place and write contradictory instances that violate the fundeps that are not caught in GHC. (Hugs does not allow the overlapping instances to begin with, even worse.) Well, that became a clearinghouse for the frustrations of the last several days. Sorry. Thanks, Nick

4 3

diff in Haskell: clarification
by George Russell 16 Dec '02

16 Dec '02

Since various people seem to have misunderstood the problem, I shall try to state it more precisely. What is required is a function diff :: Ord a -> [a] -> [a] -> [DiffElement a] for the type data DiffElement a = InBoth a | InFirst a | InSecond a such that given the functions f1 (InBoth a) = Just a f1 (InFirst a) = Just a f1 (InSecond a) = Nothing and f2 (InBoth a) = Just a f2 (InFirst a) = Nothing f2 (InSecond a) = Just a the following identities hold: mapPartial f1 (diff l1 l2) == l1 and mapPartial f2 (diff l1 l2) == l2 This is a well-known problem. The most helpful Web page I could find about it is here: http://apinkin.net/space/DifferenceEngine There is an algorithm known as Myer's algorithm, but obviously I want it in Haskell rather than C, and it would be nice if someone else had written it so I don't have to.

4 4

Foundations of Object-Oriented Languages (FOOL10): Call for Participation
by ghelli 16 Dec '02

16 Dec '02

Call for Participation ====================== 10th International Workshop on Foundations of Object-Oriented Languages (FOOL10) January 18, 2003 - New Orleans, Louisiana Following POPL 2003 URL: http://www.cis.upenn.edu/~bcpierce/FOOL/FOOL10.html E-mail: fool10(a)di.unipi.it The search for sound principles for object-oriented languages has given rise to much work on the theory of programming languages during the past 15 years, leading to a better understanding of the key concepts of object-oriented languages and to important developments in type theory, semantics, and program verification. The FOOL workshops (http://www.cis.upenn.edu/~bcpierce/FOOL/index.html) bring together researchers to share new ideas and results in these areas. Program: 8:55 Start 9:00-10:00 Invited Talk: Andrew Kennedy - Microsoft Reasearch Cambridge UK: "Parametric Polymorphism for Popular Programming Languages", 10:00-10:30 Break 10:30-12:00 Session 1 1) "External Uniqueness" Dave Clarke, Tobias Wrigstad 2) "Enforcing Resource Usage Protocols via Scoped Methods" Gang Tan, Xinming Ou, David Walker 3) "Subtyping Mobile Classes and Mixins" Lorenzo Bettini, Viviana Bono, Betti Venneri 12:00-14:00 Lunch 14:00-15:00 Session 2 1) "Static Analysis for JML's assignable Clauses" Fausto Spoto, Erik Poll 2) "A Model of Garbage Collection for OO Languages" Rob Hunter, Shriram Krishnamurthi 15:00-15:30 Break 15:30-17:00 Session 3 1) "Abstract Data Types in Modular and Object-Oriented Programming: Algebraic and Flat Modeling " Philippe Narbel 2) "A Nominal Theory of Objects with Dependent Types" Martin Odersky, Vincent Cremet, Christine Rockl, Matthias Zenger 3) "Regular Object Types" Vladimir Gapeyev, Benjamin C. Pierce Details about registration and hotel reservation can be found at the FOOL10 web site http://www.cis.upenn.edu/~bcpierce/FOOL/FOOL10.html, while more information on POPL 2003 can be found at http://www.csd.auth.gr/~setn02/en/index.htm. We are looking forward to meeting you in New Orleans in January. ------------------------------------------------------------------------ ---- Prof. Giorgio Ghelli, PhD Universita' di Pisa, Dipartimento di Informatica, Via Buonarroti 2, I-56125, Pisa, ITALY mailto:ghelli@di.unipi.it http://www.di.unipi.it/~ghelli ------------------------------------------------------------------------ ----

1 0

RE: Running out of memory in a simple monad
by Richard Uhtenwoldt 16 Dec '02

16 Dec '02

David Bergman writes: >It is easy to get the feeling that the recursive call in > > recurse = do > f x > recurse > >is the last one, but this is just an illusion of the iterative layout of >"do". Sometimes the monads lure us into old iterative thought >patterns... > >Taking away the syntactic sugar, we end up with > > recurse = f x >> recurse > >This reveals the fact that there can be no last call optimization, >because the last call is ">>". What do you mean by this? Do you mean that that an implementation cannot execute arbitrarily many iterations/recursions of that last loop/definition in constant space? If that's what you mean, you are wrong. GHC does that. The IO monad would be pretty damned useless for actual work if implementations did not do that! Even if we replace the (>>) with a (:) as the "main operator"/"last call" of the loop, the result can execute in constant space because of optimizations. E.g., the program loop n=n:loop (n+1) main = print (loop 0) executes in constant space when compile by GHC 5.02. Details: Specifically, I let it run till it printed 2,500,000 at which time top reported the "RSS" to be 1,500 with no increase having occurred in a long time. top's manpage says that "RSS" is "the total amount of physical memory used by the task, in kilobytes". The statement about (>>) is true when the (>>) is in the IO monad. I did not check to see what happens in a "user-defined" monad.

3 7

Re: fundeps question
by Ashley Yakeley 16 Dec '02

16 Dec '02

At 2002-12-14 15:27, nalexand(a)gianther.hypbus.com wrote: >I define > >class Mul a b c | a b -> c, b a -> c where mul :: a -> b -> c The two constraints are identical. Each one says "given a and b, you have c". What you want is essentially this: class (Mul b a c) => Mul a b c where mul :: a -> b -> c mul a b = mul b a ...but that's not allowed as superclass contexts cannot be circular. >I want > >instance (Mul a b c) => Mul b a c where mul x y = mul y x This will overlap with any other "Mul" instance. Instance declarations cannot be made overridable the way functions in OOP languages can be: each instance declaration must have an entirely separate domain. -- Ashley Yakeley, Seattle WA

1 0