June 2001 - Haskell - Haskell.org

CFP: ICLP ws SAVE 2001
by Giorgio Delzanno 07 Jun '01

07 Jun '01

=============================================================================== We apologize for multiple copies of this message =============================================================================== ICLP 2001 workshop SAVE 2001 Specification, Analysis and Validation for Emerging Technologies in Computational Logic http://www.disi.unige.it/person/DelzannoG/save.html Dec 1, 2001 , Coral Beach Hotel and Resort, Paphos, Cyprus Submission Deadline: August 25, 2001 The huge increase in interconnectivity we have witnessed in the last decade has boosted the development of systems which are often large-scale, distributed, time-critical, and possibly acting in an unreliable or malicious environment. Furthermore, software and hardware components are often mobile, and have to interact with a potentially arbitrary number of other entities. These systems require solid formal techniques for their verification and analysis. In this respect, computational logic plays an increasingly important role, both providing formal methods for proving system's correctness and tools - e.g. using techniques like constraint programming and theorem proving - for verifying their properties. In addition, computational logic is gaining importance as tool for the specification of (part) of these systems. For instance, one can think at the specification, in a form of temporal logic, of a communication protocol. Such specification offers the advantage that one can reason about it using formal methods, and at the same time it is often easily executable by rewriting it into a logic-based programming language. Extending and shifting slightly from the scope of the predecessors (on verification and logic languages) held in the context of past editions of ICLP, the aim of this workshop is to bring together researchers interested in the use of computational logicas a tool for the specification, analysis and validation of systems, with particular emphasis on (but not restricted to) emerging technologies like World Wide Web and E-Commerce, (protocols for) Smart Cards and Mobile Telephony, Wireless Technology, Hybrid Systems, Real-Time and Distributed systems etc. Topics The topics of interest include but are not limited to: Specification languages and rapid prototyping: Logic programming and its extensions First-order, constructive, modal and temporal logic Constraints Type theory Analysis: Abstract interpretation Static analysis Validation: Simulation and testing Deductive methods Model checking Theorem proving The preferred issues include, but are not limited to: Mobility: specification and verification of mobile code. Security: access rights, information flow, and security protocols. Interaction, coordination, negotiation, communication and exchange on the Web. Open and infinite-state systems. Real-time systems. Important Dates: Deadline for submissions: August 25, 2001. Notification of acceptance/rejection: September 15, 2001. Final papers due: October 5, 2001. Authors should submit papers of at most 15 pages, in postscript format, formatted for A4 paper, to Giorgio Delzanno (giorgio(a)disi.unige.it) by 31st July 2001. The proceedings will be published in electronic format. A printed version will be distributed to all participants of the workshop. On the basis of the number and quality of the submissions, we could also consider the possibility of inviting submissions for a special issue of an international journal dedicated to the workshop. Workshop Organizers/PC Chairs: Giorgio Delzanno Dipartimento di Informatica e Scienze dell'Informazione Universita' di Genova giorgio(a)disi.unige.it Sandro Etalle Department of Computer Science University of Twente and CWI etalle(a)cs.utwente.nl Maurizio Gabbrielli Dipartimento di Matematica ed Informatica Universita' di Udine gabbri(a)dimi.uniud.it Program Committee: Radhia Cousot, CNRS & École Polytechnique, France Giorgio Delzanno, University of Genova, Italy Sandro Etalle, University of Twente and CWI, The Netherlands Maurizio Gabbrielli, University of Udine, Italy Thierry Massart, University of Brussels, Belgium Frank Pfenning, Carnegie Mellon University, USA Andreas Podelski, Max Planck Institute, Germany Sriram Rajamani, Microsoft Research, USA Jean-Francois Raskin, University of Brussels, Belgium

1 0

Re: Why is there a space leak here? (fwd)
by Malcolm Wallace 07 Jun '01

07 Jun '01

Hi Claus, I've had a look at this example in GHood, and you are right, nhc98 does seem to create several copies of v-in. > import Observe > > foo1 m > = take m (observe "v-out" v) > where > v = 1 : concat (map triple (observe "v-in" v)) > triple x = [x,x,x] > > main = printO $ (foo1 100::[Int]) > Perhaps Malcolm can explain what nhc98 does with this example? At a guess, I think the answer lies in lambda-lifting. nhc98 -c Leak.hs +CTS -lift -CTS shows this code for `v' (reformatted a little to make it easier to read): Main.Prelude.173.v = \ v223 v224 -> Prelude.: (Prelude._apply1 (Prelude.fromInteger v223) 1L) (Prelude._apply1 (Prelude.concat) (Prelude.map (Main.Prelude.174.triple) (Observe.observe (Observe.Observable.Prelude.[] v224) (LAMBDA225) (Prelude._apply2 (Main.Prelude.173.v) v223 v224)))) v takes two arguments; v223 represents the numeric dictionary, and v224 the Observer dictionary. The recursive reference to v is not a cyclic pointer to a constant structure, but actually a function call. I believe the real culprit is that nhc98 does not implement the monomorphism restriction. IIRC, the DMR applies to every group of simple pattern bindings at the same let-bound scope, not just the top-level, so really we ought to default-away the dictionaries, which would solve this particular space oddity. Regards, Malcolm

1 0

Functional Dependency
by Saswat Anand 07 Jun '01

07 Jun '01

Hi, I am trying to define a commutative operator : (%+) :: a -> b -> c (%+) :: b -> a -> c instead of defining a class and instantiating twice every time, I am trying to do the following: class Commutative a b c where (%+) :: a -> b -> c class Operation a b c | a b -> c where (%+%) :: a -> b -> c instance (Operation a b c) => Commutative a b c where (%+) = (%+%) instance (Operation b a c) => Commutative a b c where (%+) = flip (%+%) -- instance Operation Int (Maybe Int) Int where i %+% (Just s) = i + s --- With hugs -98 +mo ((2::Int) %+ (Just (2::Int)))::Int gives 4 But (2::Int) %+ (Just (2::Int)) is of type Commutative Int (Maybe Int) a => a. So is (Just (2::Int)) %+ (2::Int) Is the dependency in Operation class not sufficient. Any work around? Which flags to be set for Ghc to accept this code. I tried -fallow-overlapping-instances and -fallow-undecidable-instances. Thanks, S

1 0

Why is there a space leak here?
by David Bakin 06 Jun '01

06 Jun '01

Why is there a space leak in foo1 but not in foo2? (I.e., in Hugs Nov '99) foo1 eats cells (and eventually runs out) where foo2 doesn't. That is, if I do (length (foo1 1000000)) I eventually run out of cells but (length (foo2 1000000)) runs fine (every GC returns basically the same amount of space). Something must be wrong in flatten but it follows the pattern of many functions in the prelude (which I'm trying to learn from). I have been puzzling over this for nearly a full day (getting this reduced version from my own code which wasn't working). In general, how can I either a) analyze code looking for a space leak or b) experiment (e.g., using Hugs) to find a space leak? Thanks! -- Dave -- This has a space leak, e.g., when reducing (length (foo1 1000000)) foo1 m = take m v where v = 1 : flatten (map triple v) triple x = [x,x,x] -- This has no space leak, e.g., when reducing (length (foo2 1000000)) foo2 m = take m v where v = 1 : flatten (map single v) single x = [x] -- flatten a list-of-lists flatten :: [[a]] -> [a] flatten [] = [] flatten ([]:xxs) = flatten xxs flatten ((x':xs'):xxs) = x' : flatten' xs' xxs flatten' [] xxs = flatten xxs flatten' (x':xs') xxs = x': flatten' xs' xxs

8 14

Re: Why is there a space leak here?
by Mark Tullsen 05 Jun '01

05 Jun '01

"Steinitz, Dominic J" wrote: > I'd love it if someone could write a tutorial paper on space > leaks. I agree that would be very useful. > Even with the explanations that have been provided, I find it > difficult to understand why expressions get evaluated in a > particular order and why garbage collections happen at a given > point. In my "traces" I did the garbage collections as soon as possible, basically removing unused let bindings. The ordering of evaluations is a bit more tricky ... I would recommend becoming familiar with the various call-by-need calculi. For me, it was more intuitive than trying to understand what's going on at some lower level (such as the STG Machine) and then relate that lower level to my program. With call-by-need calculi you can understand what's going on at the source level. Here's a starting point: The Call-by-Need Lambda Calculus, POPL 95, Ariola, Felleisen, Maraist, Odersky, & Wadler @article{maraist-odersky-wadler:need-JFP98, author = "John Maraist and Martin Odersky and Philip Wadler", title = "The Call-by-Need Lambda Calculus", journal = "Journal of Functional Programming", volume = 8, number = 3, month = may, year = 1998, publisher = "Cambridge University Press", } - Mark

1 0

Re: Why is there a space leak here?
by Steinitz, Dominic J 05 Jun '01

05 Jun '01

I'd love it if someone could write a tutorial paper on space leaks. Even with the explanations that have been provided, I find it difficult to understand why expressions get evaluated in a particular order and why garbage collections happen at a given point. Dominic. ------------------------------------------------------------------------------------------------- 21st century air travel http://www.britishairways.com

1 0

Advantages of Paper
by George Russell 05 Jun '01

05 Jun '01

I don't want to seem incredibly Luddite, but there are some things the World Wide Web is not good at, and one of them is permanence. Try for example finding out about Glasgow Haskell from http://www.dcs.gla.ac.uk, which was I think the standard URL a few years ago. In 2050 we may not even have a World Wide Web (remember Gopher?), or if we do URLs as we have them may be as outdated as those e-mail addresses I remember which included lots of percent signs telling the network to send your message to Birmingham via Beachy Head. I find it therefore of concern that many crucial Haskell documents, including the standard and, for example, the various Glasgow Haskell manuals, are only available online. I therefore suggest that they at least be printed out in the form of technical reports, and made available in this form to libraries, which are well-used to storing information long-term. Otherwise the curious in 2050 will be able to locate manuals for FORTRAN II and Simula (as I can do in 5 minutes in the local library), but getting Haskell documentation will be about as easy as reading 5-track paper tape. I don't think it matters if Haskell itself is obsolete in the year 2050, as it probably will be. But it will be a pity if most of the papers written using it are hard to figure out because the documentation itself is missing.

4 4

A pecular algebraic data structure
by Jan Skibinski 05 Jun '01

05 Jun '01

I've been working with one pecular algebraic data structure, named Register, which is described in currently upgraded http://www.numeric-quest.com/haskell/QuantumComputer.html. or in gzipped version of the same document http://www.numeric-quest.com/haskell/QuantumComputer.html.gz. Section 13 of that document outlines the background for the topic of this message. But the section is just way too long to quote it in here. But to summarize it: data Register is pecular because it is indexable but not observable in a standard way, and because two different representations can describe the same state. In theory there should be well defined transformation from one representation to another. This seems to me as a good subject for some research work. Granted that there are many experts on functional data structures out there (I do not want to pressure any of you gurus, so I am not naming anyone :-)), could you please look at the write-up and help me with the following questions? + Is the Register data structure strangely unique, or does it fit somewhere into a hierarchy of known functional data structures? I would be happy to learn that the latter is the case, since I could then start looking at it at a more formal, well known and tested way. + Is a non-uniqness of representation amenable to formal treatment, such as deforestation? Jan

1 0

proof in haskell ?
by luc 04 Jun '01

04 Jun '01

chapter 12 of birds book mention mike spivey' theorem prover. are there anything available in source code about proof in haskell ? (btw , haskell is a great language ! one of the rare that try to "improve lazyness " ! (chaperter 11) thanks Luc

2 1

GHC core representation
by Andrew Tolmach 04 Jun '01

04 Jun '01

Dear Haskellers, Many months after the topic was first raised, there is finally a draft document describing a formal external syntax for GHC's "Core" intermediate language. It is available from http://www.cs.pdx.edu/~apt/ext-core.ps Those who wish to experiment seriously with the format described can download the latest "HEAD" experimental version of GHC. Using the "-fext-core" option when compiling "foo.hs" will generate a file "foo.core" (in additition to any other outputs specified). The document currently gives only an informal semantics "Core;" a much more formal semantics -- which I view as a very important thing to have in practice -- is in progress but not quite ready for public scrutiny. As this is very much a draft (you'll see the holes!), feedback is welcome, but due to the GHC-internals nature of this topic, please direct your comments to glasgow-haskell-users(a)haskell.org or to me personally at apt(a)cs.pdx.edu. I'll be out of email contact for the next month, though, so don't expect replies until July! - Andrew Tolmach

1 0