- Haskell - Haskell.org

Monomorphism Restriction
by Ashley Yakeley 09 Jun '01

09 Jun '01

Is there a point to the "monomorphism restriction" in GHC and Hugs? In practice, all it seems to mean is "occasionally require unnecessary explicit type signatures". -- Ashley Yakeley, Seattle WA

1 0

Re: Why is there a space leak here?
by cwitty＠newtonlabs.com 09 Jun '01

09 Jun '01

"S. Alexander Jacobson" <alex(a)shop.com> writes: > For example w/ foldl: > > foldl + 0 [1..10000] > foldl (+) ((+) 0 1) [2..10000] > foldl (+) ((+) ((+) 0 1) 2) [3..10000] > > Can't the implementation notice that each iteration leads to a > larger closure and, if it is running out of space go ahead an just > evaluate (+) 0 1? It's complicated. You can't (in general) know whether application of a function will increase or decrease the space used. If you were running out of space, would you just search the whole unevaluated program graph for reductions which somehow seemed "likely" to reduce the space used? Would you add such reduction nodes to some global list at the time they were created? > I realize that there is a risk of evaluating _|_ unnecessarily, but if you > are otherwise going to run out of memory, you might as well give it a > shot. > > In practice, how often do you expect to see growing expressions that cover > a _|_ that are not actually an error in any case? It's certainly possible. One portable way to implement a memoizing function in Haskell (if the domain of the function is countable) is to lazily build a data structure that contains the results of the function on every possible argument. Then you evaluate the portions of the data structure that you need; the result on each argument is only evaluated once. This probably would count as a "growing expression", and it's certainly possible that the function on some arguments would be bottom. > Hunting down memory leaks is already so obscure, that you might as well > take a shot at solving the problem automatically... > > Alternatively, is there some magical way of warning about leaky > expressions at compile time? You don't have to ban them, but it would be > nice if the programmer were aware of which parts of the code are likely to > grow... In general, this problem is uncomputable. It might be possible to come up with some useful approximation, but I bet that's a very difficult research problem. Carl Witty

3 2

SAS'01: Early registration 15th June
by radhia＠lix.polytechnique.fr 09 Jun '01

09 Jun '01

___________________________________________________________________________ [We apologize for any inconvience caused by multiple copies] SAS'01 Eigth International Static Analysis Symposium La Sorbonne, Paris, 16-18 July, 2001 http://www.ens.fr/sas01/ Registration information is available on the SAS'01 website. Early registration ends soon (15th June). ___________________________________________________________________________

1 0

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 06 Jun '01

06 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