- Haskell - Haskell.org

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

Constant space infinite itteration ... solution?
by b.i.mills＠massey.ac.nz 13 Dec '02

13 Dec '02

Hi all, Ok, I've got the Farari out of the garage, in to gear, and even driven it slowly around the block, but every time I put my foot down it just stalls. I'm trying to write a non trivial gui in Haskell. At the moment I'm using Hugs, and rapidly coming to the conclusion that I should be using something else such as GHC. As I see it the problem is basically that of tail recursion removal or as David Bergman calls it "last call optimisation". Specifically: David Bergman wrote > 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 ">>". In response Richard Uhtenwoldt echoed my own thoughts ... > 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? And also said ... > 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! So, my problem is that I find that my program crashes with "garbage collector can't collect enough memory" after about 64 Million output operations. What's really annoying is that I can write the whole thing *recursively* in C in a very "functional" manner, and it works just fine. As I see it the problem is that >> and >>= are functions and David is right about the "not the last call" problem. But, Richard is right that related optimisations should be possible in Haskell, and if not then you can kiss the whole load good by and go back to system programming in C. In particular I would claim that the definition: recurse = f x >>= recurse is essentially using >>= as a proxy temporal execution handler. So in the above definition the call to recurse *is* a "last-call", at least according to >>=. I'm probably saying that in a rather unorthodox manner, but I hope my basic intention is clear. In fact we can see >> in Haskell as rather kin to ; in C (Or perhaps it should be >>=, since ; does transfer the state to the subsequent computation). So, I've loaded GHC and I'm looking to use it instead (I expected to eventually anyway), but does this solve my problem? Or have I misunderstood something here? Also ... I've been using the graphics libs with HUGS, but I can't find the equivalent in GHC ... what is the recomended library for writing GUIs in GHC Haskell? And where do I get it? Thanks in advance ... Bruce (IIMS, Massey at Albany). ps: I've also been looking at Fudgets, but the code seems a bit cranky.

5 4

FM2003: Call for TUTORIALS
by mailinglist-admin＠fmeurope.org 13 Dec '02

13 Dec '02

FM2003: Call for TUTORIALS The FME symposia on Formal Methods is a forum for the dissemination of basic as well as applied up-to-date culture on the use of formal methods for software development. Maintaining the tradition, a tutorial program that gives attendees the opportunity to gain new insights, knowledge and skills on evolving and emerging research topics in the area of formal methods will be an essential part of the symposium. The Tutorials are scheduled for September 8-9, 2003 at the beginning of the symposium. Survey papers and/or tutorial notes will be made available to the tutorial attendees at the symposium. Tutorials are intended to provide independent instruction on a relevant theme, therefore no commercial or sales-oriented presentations will be accepted. Proposals of Tutorials which encompass any topic dealing with precise mathematical methods for software development, and in particular their application to new application areas that are critical in the new aspects of the information society are solicited. A non-exhaustive suggested list of topics and areas in the scope of FM2003 is listed in the FM2003 Call for Papers (http://fme03.isti.cnr.it/) Instructors are invited to submit proposals for half-day and full-day tutorials and, upon selection, are required to provide tutorial notes or a survey paper on the topic of presentation before June 8, 2003 in postscript, pdf or on paper (no colour print). Proper tutorial notes are preferred, but well-printed transparencies will be accepted as well. Proposals should be send to the Tutorials Chair Mieke Massink by March 7, 2003. Proposals should be in Postscript or PDF format. Please include the following information in the proposal that should not exceed 5 pages: * name and affiliation of proposer/organizer (including address, phone number, fax number, e-mail address) * name and affiliation of additional presenters * instructor's experience in the area, such as other tutorials, courses etc. * title * objective * abstract * outline * duration * audio-visual and technical requirements * target audience * assumed background of attendees * brief biography of each instructor (for inclusion in publicity) * indication whether a survey paper will be provided (max. 30 pages) Evaluation of proposals will be based on the relevance of the subject matter and on the expertise and experience of the instructors. Important Dates Submission of Tutorial proposals: March 7, 2003 Notification of acceptance: March 20, 2003 Camera ready papers/notes: June 8, 2003 Conference: September 8-14, 2003 Web page of FM03: http://fme03.isti.cnr.it/ Tutorial proposals should be submitted to the FM2003 Tutorial Chair: Mieke Massink C.N.R.-Ist. ISTI "A. Faedo" Area della Ricerca di Pisa Via Moruzzi 1, I56124 Pisa, Italy Tel: +39-050-3152981 Fax: +39-050-3138091 email: Mieke.Massink(a)cnuce.cnr.it -- ---------------------------------------------------------------- Dr. Mieke Massink Ph.D. - Researcher FM&&T group (http://matrix.iei.pi.cnr.it/FMT) C.N.R. - Area della Ricerca di Pisa - Ist. ISTI Via G. Moruzzi, 1 - I56124 Pisa, Italy Tel: +39 050 3152981 http://www.cnuce.pi.cnr.it/people/M.Massink/ Fax: +39 050 3138091 E-mail: Mieke.Massink(a)cnuce.cnr.it ---------------------------------------------------------------- _______________________________________________ Mailinglist mailing list Mailinglist(a)fmeurope.org http://www.fmeurope.org/mailman/listinfo/mailinglist

1 0

lazy stream I/O
by Wolfgang Jeltsch 13 Dec '02

13 Dec '02

Hello, what are the arguments against lazy stream I/O? Wolfgang

2 1

RE: Constant space infinite itteration ... solution?
by David Bergman 12 Dec '02

12 Dec '02

Hi, Bruce. Just want to clarify the "last call optimisation"/"tail recursion" terminology. One does not "remove" a tail recursive call, one just make it O(1) w.r.t. stack (or any other "where have we been" call frame structure...) with the help of "tail recursion optimisation". "Last call optimisation" is a generalization of the latter optimisation, applicable to any call, recursive or not. In effect, implementers seldom care whether the last call is recursive or not, they just skip the "return address" pushing, making "last call optimisation" operationally equivalent to "tail recursion optimisation". Richard was (and still is) completely correct in that last call optimisation is not a crucial element in lazy evaluation, although that is not necessarily true when strictness analysis or explicit strictness annotations (!) allow the implementation to skip the general thunk creation/inspection/destruction loop and instead use the much more time-efficient eager evaluation (i.e., mapping to the C code you referred to...), which can be memory-inefficient, similar to your Hugs experience. Good luck with that Ferrari (that is the only Ferrari we Haskellers will ever see...) /David Bruce wrote: > > > Hi all, > > > Ok, I've got the Farari out of the garage, in to gear, and even driven > it slowly around the block, but every time I put my foot down it just > stalls. > > I'm trying to write a non trivial gui in Haskell. At the moment I'm > using Hugs, and rapidly coming to the conclusion that I should be > using something else such as GHC. > > As I see it the problem is basically that of tail recursion removal or > as David Bergman calls it "last call optimisation". > > Specifically: > > David Bergman wrote > > > 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 ">>". > > In response Richard Uhtenwoldt echoed my own thoughts ... > > > 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? > > And also said ... > > > 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! > > So, my problem is that I find that my program crashes with "garbage > collector can't collect enough memory" after about 64 Million output > operations. > > What's really annoying is that I can write the whole thing > *recursively* in C in a very "functional" manner, and it works just > fine. > > As I see it the problem is that >> and >>= are functions > and David is right about the "not the last call" problem. But, Richard > is right that related optimisations should be possible in Haskell, and > if not then you can kiss the whole load good by and go back to system > programming in C. > > In particular I would claim that the definition: > > recurse = f x >>= recurse > > is essentially using >>= as a proxy temporal execution handler. So in > the above definition the call to recurse > *is* a "last-call", at least according to >>=. I'm > probably saying that in a rather unorthodox manner, > but I hope my basic intention is clear. > > In fact we can see >> in Haskell as rather kin to ; in C > (Or perhaps it should be >>=, since ; does transfer the > state to the subsequent computation). > > So, I've loaded GHC and I'm looking to use it instead > (I expected to eventually anyway), but does this solve > my problem? Or have I misunderstood something here? > > Also ... I've been using the graphics libs with HUGS, > but I can't find the equivalent in GHC ... what is > the recomended library for writing GUIs in GHC Haskell? > And where do I get it? > > Thanks in advance ... > > Bruce (IIMS, Massey at Albany). > > ps: I've also been looking at Fudgets, but the code seems > a bit cranky. > > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell >

1 0

RE: Constant space infinite itteration ... solution?
by David Bergman 12 Dec '02

12 Dec '02

Hi, Bruce. Just want to clarify the "last call optimisation"/"tail recursion" terminology. One does not "remove" a tail recursive call, one just make it O(1) w.r.t. stack (or any other "where have we been" call frame structure...) with the help of "tail recursion optimisation". "Last call optimisation" is a generalization of the latter optimisation, applicable to any call, recursive or not. In effect, implementers seldom care whether the last call is recursive or not, they just skip the "return address" pushing, making "last call optimisation" operationally equivalent to "tail recursion optimisation". Richard was (and still is) completely correct in that last call optimisation is not a crucial element in lazy evaluation, although that is not necessarily true when strictness analysis or explicit strictness annotations (!) allow the implementation to skip the general thunk creation/inspection/destruction loop and instead use the much more time-efficient eager evaluation (i.e., mapping to the C code you referred to...), which can be memory-inefficient, similar to your Hugs experience. Good luck with that Ferrari (that is the only Ferrari we Haskellers will ever see...) /David Bruce wrote: > > > Hi all, > > > Ok, I've got the Farari out of the garage, in to gear, and even driven > it slowly around the block, but every time I put my foot down it just > stalls. > > I'm trying to write a non trivial gui in Haskell. At the > moment I'm using Hugs, and rapidly coming to the conclusion > that I should be using something else such as GHC. > > As I see it the problem is basically that of tail recursion > removal or as David Bergman calls it "last call optimisation". > > Specifically: > > David Bergman wrote > > > 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 ">>". > > In response Richard Uhtenwoldt echoed my own thoughts ... > > > 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? > > And also said ... > > > 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! > > So, my problem is that I find that my program crashes with > "garbage collector can't collect enough memory" after about > 64 Million output operations. > > What's really annoying is that I can write the whole thing > *recursively* in C in a very "functional" manner, and it works just > fine. > > As I see it the problem is that >> and >>= are functions > and David is right about the "not the last call" problem. > But, Richard is right that related optimisations should > be possible in Haskell, and if not then you can kiss the > whole load good by and go back to system programming in C. > > In particular I would claim that the definition: > > recurse = f x >>= recurse > > is essentially using >>= as a proxy temporal execution handler. So in > the above definition the call to recurse > *is* a "last-call", at least according to >>=. I'm > probably saying that in a rather unorthodox manner, > but I hope my basic intention is clear. > > In fact we can see >> in Haskell as rather kin to ; in C > (Or perhaps it should be >>=, since ; does transfer the > state to the subsequent computation). > > So, I've loaded GHC and I'm looking to use it instead > (I expected to eventually anyway), but does this solve > my problem? Or have I misunderstood something here? > > Also ... I've been using the graphics libs with HUGS, > but I can't find the equivalent in GHC ... what is > the recomended library for writing GUIs in GHC Haskell? > And where do I get it? > > Thanks in advance ... > > Bruce (IIMS, Massey at Albany). > > ps: I've also been looking at Fudgets, but the code seems > a bit cranky. > > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell >

1 0