- Haskell - Haskell.org

call for papers ICFP 2001
by Xavier Leroy 18 Dec '00

18 Dec '00

ICFP 2001: Call for Papers ICFP 2001: International Conference on Functional Programming Firenze (Florence), Italy; 3-5 September 2001 associated with PLI 2001: Colloquium on Principles, Logics, and Implementations of High-Level Programming Languages Important dates: Submission deadline 15 March 2001, 18:00 UTC Notification of acceptance or rejection 11 May 2001 Final paper due 29 June 2001 Conference 3-5 September 2001 Scope: ICFP 2001 seeks original papers on the full spectrum of the art, science, and practice of functional programming. The conference invites submissions on all topics ranging from principles to practice, from foundations to features, and from abstraction to application. The scope covers all languages that encourage programming with functions, including both purely applicative and imperative languages, as well as languages that support objects and concurrency. Papers setting new directions in functional programming, or describing novel or exemplary applications of functional programming, are particularly encouraged. Topics of interest include, but are not limited to, the following: * Foundations: formal semantics, lambda calculus, type theory, monads, continuations, control, state, effects. * Design: modules and type systems, concurrency and distribution, components and composition, relations to object-oriented and logic programming, multiparadigm programming. * Implementation: abstract machines, compile-time and run-time optimization, just-in-time compilers, memory management, foreign-function and component interfaces. * Transformation and Analysis: abstract interpretation, partial evaluation, program transformation, theorem proving, specification and verification. * Applications: scientific and numerical computing, symbolic computing and artificial intelligence, systems programming, databases, graphic user interfaces, multimedia programming, web programming. * Experience: FP in education and industry, ramifications on other paradigms and computing disciplines. * Functional pearls: elegant, instructive examples of functional programming. Submission guidelines: Please refer to the submission Web site http://cristal.inria.fr/ICFP2001/ Program committee: General chair Program committee Benjamin Pierce Karl Crary, Carnegie Mellon University University of Pennsylvania Marc Feeley, University of Montréal Giorgio Ghelli, University of Pisa Program chair Simon Peyton Jones, Microsoft Research John Hughes, Chalmers University Xavier Leroy Naoki Kobayashi, University of Tokyo INRIA Rocquencourt Julia Lawall, DIKU, U. Copenhagen Domaine de Voluceau, B.P. 105 Sheng Liang, Stratum8 78153 Le Chesnay, France John Reppy, Bell Labs, Lucent Technologies E-mail: Xavier.Leroy(a)inria.fr Scott Smith, John Hopkins University Fax: + 33 - 1 - 39 63 56 84 Carolyn Talcott, Stanford University Phone: + 33 - 1 - 39 63 55 61 Kwangkeun Yi, KAIST

1 0

Finding primes using a primes map with Haskell and Hugs98
by Shlomi Fish 18 Dec '00

18 Dec '00

Hi! As some of you may know, a Haskell program that prints all the primes can be as short as the following: primes = sieve [2.. ] where sieve (p:x) = p : sieve [ n | n <- x, n `mod` p > 0 ] Now, this program roughly corresponds to the following perl program: ###### SNIP SNIP ##### #!/usr/bin/perl use strict; my (@primes, $a, $p); @primes = (2); MAIN_LOOP: for($a = 3; $a < 1000; $a++) { foreach $p (@primes) { if ($a % $p == 0) { next MAIN_LOOP; } } push @primes, $a; } print join(", ", @primes); ####### SNIP SNIP ##### The program can be more optimized for both speed and code size, but I wanted to make it as verbose as possible. The algorithm keeps a list of the primes, and for each new number checks if it is divisable by any of them and if not it adds it to the list. There is a different algorithm which keeps a boolean map which tells whether the number at that position is prime or not. At start it is initialized to all trues. The algorithm iterates over all the numbers from 2 to the square root of the desired bound, and if it encounters a prime number it marks all the numbers p*p, p*p+p, p*p+2*p, p*p+3*p, etc. as not prime. It is generally considered a better algorithm than the previous one, because it uses less costier operations (multiplications and additions instead of modulos.) The perl program that implements that algorithm is this: #### SNIP SNIP ##### #!/usr/bin/perl use strict; sub primes { my $how_much = shift; my (@array, $bound, $a, $b, @primes); @array = (1) x $how_much; $bound = int(sqrt($how_much))+1; for($a=2;$a<=$bound;$a++) { if ($array[$a]) { for($b=$a*$a;$b<$how_much;$b+=$a) { $array[$b] = 0; } push @primes, $a; } } for(;$a<$how_much;$a++) { if ($array[$a]) { push @primes, $a; } } return @primes; } print join(", ", primes(1000)); ##### SNIP SNIP ###### Now, I tried writing an equivalent Haskell program and the best I could do was the following: ---- SNIP SNIP ----- module Primes where import Prelude import Array how_much :: Int how_much = 1000 initial_primes_map :: Array Int Bool initial_primes_map = array (1, how_much) [ (i,True) | i <- [1 .. how_much] ] mybound :: Int mybound = ceiling(sqrt(fromInteger(toInteger(how_much)))) next_primes_map :: Int -> Array Int Bool -> Array Int Bool next_primes_map a primes_map = if (a == mybound) then primes_map else next_primes_map (a+1) ( if primes_map!a then primes_map // [ (i*a, False) | i <- [a .. (prime_bound a)] ] else primes_map ) prime_bound :: Int -> Int prime_bound a = (floor(fromInteger(toInteger(how_much))/fromInteger(toInteger(a)))) get_primes_map :: Array Int Bool get_primes_map = (next_primes_map 2 initial_primes_map) list_primes :: Array Int Bool -> Int -> [Int] list_primes primes_map n = if (n > how_much) then [] else ( if primes_map!n then n:(list_primes primes_map (n+1)) else list_primes primes_map (n+1) ) show_primes = show (list_primes get_primes_map 2) ---- SNIP SNIP ----- The problem is that when running it on hugs98 on a Windows98 computer with 64MB of RAM, I cannot seem to scale beyond 30,000 or so, as my boundary. When entering how_much as 50,000 I get the following message: ERROR: Garbage collection fails to reclaim sufficient space In perl I can scale beyond 100,000, and if I modify the code to use a bit vector (using vec) to much more. So my question is what am I or hugs are doing wrong and how I can write better code that implements this specific algorithm. >From what I saw I used tail recursion, (and hugs98 has proper tail recursion, right?), and there's only one primes_map present at each iteration (and thus, at all), so it shouldn't be too problematic. Does it have to do with the way hugs98 implements and Int to Bool array? Regards, Shlomi Fish ---------------------------------------------------------------------- Shlomi Fish shlomif(a)vipe.technion.ac.il Home Page: http://t2.technion.ac.il/~shlomif/ Home E-mail: shlomif(a)techie.com The prefix "God Said" has the extraordinary logical property of converting any statement that follows it into a true one.

4 4

Problem with functional dependencies
by qrczak＠knm.org.pl 17 Dec '00

17 Dec '00

The following module is rejected by both ghc -fglasgow-exts -fallow-undecidable-instances and hugs -98 ------------------------------------------------------------------------ class HasFoo a foo | a -> foo where foo :: a -> foo data A = A Int data B = B A instance HasFoo A Int where foo (A x) = x instance HasFoo A foo => HasFoo B foo where foo (B a) = foo a ------------------------------------------------------------------------ The error messsage says that the type inferred for foo in B's instance is not general enough: the rhs has type "HasFoo B Int => B -> Int", but "HasFoo B foo => B -> foo" was expected. Should it really be wrong? I don't know the details of type inference with fundeps, but intuitively it should work, yielding an instance HasFoo B Int. Could it be made legal please? With the fundep removed, it works. I need it for a preprocessor which generates instances like that for B without knowing the type to put as the second class argument. Fundeps aren't essential, but... -- __("< Marcin Kowalczyk * qrczak(a)knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK

1 0

PLI 2001: call for workshop proposals
by b.venneri 13 Dec '00

13 Dec '00

CALL FOR WORKSHOP PROPOSALS Principles, Logics and Implementations of high-level programming languages (PLI 2001) Firenze, Italy September 3 - 7, 2001 http://music.dsi.unifi.it/pli01 PLI 2001, a federation of colloquia which includes ICFP 2001 (ACM-SIGPLAN International Conference on Functional Programming) and PPDP 2001 (ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming), will be held in Firenze, Italy, September 3-7 2001. Workshops affiliated to PLI 2001 will be held before, after or in parallel with the main conferences. Researchers and practitioners are invited to submit workshop proposals, that should be sent to the PLI 2001 Workshop Chair Betti Venneri mailto:venneri@dsi.unifi.it with "PLI01 Workshop Submission" in the subject header. Proposals should include * a short scientific justification of the proposed topic (somehow related to the colloquia), * names and contact information of the organizers, * expected number of participants and duration (the preference is for one day-long workshops), * estimated dates for paper submissions, notification of acceptance and final versions and any other relevant information (e.g., invited speakers, publication policy, etc.). THE DEADLINE FOR RECEIPT OF PROPOSALS IS JANUARY 8, 2001. Proposals will be evaluated by the PLI 2001 Workshop Chair, the ICFP and PPDP Program Chairs and Conference Chairs. Notification of acceptance will be made by February 2, 2001. The titles and brief information related to accepted workshop proposals will be included in the conference program and advertised in the call for participation. Workshop organizers will be responsible for producing a Call for papers and a Web site, for reviewing and making acceptance decisions on submitted papers, and for scheduling workshop activities in consultation with the local organizers. Workshop selection committee: Xavier Leroy (INRIA, France), ICFP 2001 Program Chair Benjamin C. Pierce (Univ. of Pennsylvania), ICFP 2001 Conference Chair Harald Sondergaard (Univ. of Melbourne), PPDP 2001 Program Chair Rocco De Nicola (Univ. of Firenze), PPDP 2001 Conference Chair Betti Venneri (Univ. of Firenze), PLI 2001 Workshop Chair. we

1 0

PPDP 2001: Call for Papers
by Harald Sondergaard 11 Dec '00

11 Dec '00

Third International Conference on PRINCIPLES AND PRACTICE OF DECLARATIVE PROGRAMMING Firenze, Italy, 5-7 September 2001 CALL FOR PAPERS PPDP 2001 aims to stimulate research on the use of declarative methods in programming and on the design, implementation and application of programming languages that support such methods. Topics of interest include any aspect related to understanding, integrating and extending programming paradigms such as those for functional, logic, constraint and object-oriented programming; concurrent extensions and mobile computing; type theory; support for modularity; use of logical methods in the design of program development tools; program analysis and verification; abstract interpretation; development of implementation methods; application of the relevant paradigms and associated methods in industry and education. This list is not exhaustive: submissions describing new and interesting ideas relating broadly to declarative programming are encouraged. The technical program of the conference will combine presentations of the accepted papers with invited talks and advanced tutorials. PPDP 2001 is part of a federation of colloquia known as Principles, Logics and Implementations of high-level programming languages (PLI 2001) which includes the ACM SIGPLAN International Conference on Functional Programming (ICFP 2001). The colloquia will run from 2 to 8 September, 2001. The venue for the conference is Firenze (Florence), one of Europe's most attractive cities, famous for its churches, galleries and museums. For more details, see the conference web site. Important Dates: Submission 15 March 2001 Notification 7 May 2001 Final Version 11 June 2001 Affiliated Workshops: Proposals are being solicited for PLI 2001 affiliated workshops. Details about the submission of proposals are available at http://music.dsi.unifi.it/pli01/wkshops. Web Sites and Email Contact: PPDP 2001: http://music.dsi.unifi.it/pli01/ppdp PLI 2001: http://music.dsi.unifi.it/pli01 mailto:ppdp01@cs.mu.oz.au Conference Chair: Rocco De Nicola, Universita di Firenze http://www.dsi.unifi.it/~denicola/ mailto:denicola@dsi.unifi.it Program Chair: Harald Sondergaard, The University of Melbourne http://www.cs.mu.oz.au/~harald/ mailto:harald@cs.mu.oz.au Program Committee: Maria Alpuente, Univ. Politecnica de Valencia, ES Yves Caseau, Bouygues, FR Michael Codish, Ben-Gurion Univ. of the Negev, IL Saumya Debray, Univ. of Arizona, US Conal Elliott, Microsoft Research, US Sandro Etalle, Univ. Maastricht, NL Roberto Giacobazzi, Univ. di Verona, IT Michael Leuschel, Univ. of Southampton, GB John Lloyd, Australian National Univ., AU Torben Mogensen, Kobenhavns Univ., DK Alan Mycroft, Cambridge Univ., GB Gopalan Nadathur, Univ. of Minnesota, US Martin Odersky, Ecole Polyt. Fed. Lausanne, CH Catuscia Palamidessi, Penn State Univ., US Andreas Podelski, Max-Planck-Inst. Informatik, DE Kostis Sagonas, Uppsala Univ., SE Christian Schulte, Univ. des Saarlandes, DE Michael Schwartzbach, Aarhus Univ., DK Harald Sondergaard, Univ. of Melbourne, AU Peter J. Stuckey, Univ. of Melbourne, AU

1 0

Meet us on Wine Alley
by francois.xavier.bodin＠winealley.com 06 Dec '00

06 Dec '00

Hello! I found your address on a site about wine, food and good living. I thought that you will be interested by the services that our site offers. www.wine-alley.com is a virtual Club for all those interested in wine in both a professional and personal capacity. We now have more than 3900 members, both amateur and in the trade who use our site to discuss wine, buy and sell it and tell us about the best sources. Club members use the Newsgroup of www.wine-alley.com to exchange information and experiences. Only the other day someone asked how much a certain rare wine was worth, I asked for more information about the grape variety, which doesn't grow in France. Currently there have been more than 717 questions and replies. There is also the small ads. column. Among the 7 adverts placed this week there have been some really good deals including a magnum of 1945 Pichon Lalande and a 1947 Cheval blanc! Let me make it clear - www.wine-alley.com itself does not sell or buy wine: we simply offer our members the facilites for making their own arrangements. www.wine-alley.com is also a site supplying information in real time, particularly the latest news from winegrowers and makers via the French Press Agency (AFP). We also have a database of more than 21,000 wines with information supplied directly to the site by winegrowers co-operatives and specialist magazines. I should be delighted if you would come and join us. At www.wine-alley.com you will find similarly-minded people who just want to share their love of wine. Kind regards François Xavier Bodin, Manager of the Online Club fx.bodin(a)winealley.com PS. Registering with the www.wine-alley.com club is absolutely free and commits you to nothing. If you are not interested in my offer, please excuse this letter; I am sorry to have bothered you. To prevent further unwanted intrusions please click on the following link, your email will be automatically removed from our list. http://www.wine-alley.com/wines/desmail.asp?id=307392&l=uk

1 0

RE: Rank-2 polymorphism & type inference
by Simon Peyton-Jones 05 Dec '00

05 Dec '00

Musing on Zhanyong's problem some more, a solution occurs to me. Curiously, it's exactly the solution required for another useful extension to type classes. Here is is, so people can shoot holes in it. | In more detail, here's what happens. First we typecheck the RHS of | f, deducing the types | | x :: a where a is fresh | y :: k a where k is fresh | y >> return x :: k a | op (y >> return x) :: Bool with constraint C (k a) | \x -> op (y >> return x) :: a -> Bool with constraint C (k a) | | Now we try to generalise over a. We need to discharge the contraint | C (k a). Later we will find that y::[Int], so k=[], but we | don't know that yet. So we can't solve the constraint. One bad solution I thought of was to give f the type f :: forall a. C (k a) => a -> Bool This is bad because it's not the type signature the programmer specified. (It's also bad operationally because we'll pass a dictionary at runtime, which isn't necessary.) The good solution is to say this: \x -> op (y >> return x) :: a -> Bool with constraint C (k a) (just as before) /\a \x -> op (y>>return x) :: forall a. a -> Bool with constraint (forall a. C (k a)) This requires us to permit constraints with for-alls in them. As luck would have it, Ralf Hinze and I propose just such a thing in our paper "Derivable Type Classes" (Section 7) http://research.microsoft.com/~simonpj/#derive The motivation there is this: how can you write an equality instance for data T k a = MkT (k (T k a)) We can try: instance ... => Eq (T k a) where (MkT a) == (MkT b) = a == b But what is the "..."? We need that "k" is an equality type constructor. The right context is instance (forall a. Eq a => Eq (k a)) => Eq (T k a) where ...as before... Aha! A constraint with a for-all. There are some more details in the paper. So perhaps there's a reason for adding this extension in the implementation (to solve Zhanyong's problem) even for a Haskell 98 compiler. Simon

1 0

Call for papers: Haskell Workshop 2001
by Johan Jeuring 05 Dec '00

05 Dec '00

============================================================================ CALL FOR PAPERS 2001 Haskell Workshop Firenze, Italy The Haskell Workshop forms part of the PLI 2001 colloquium on Principles, Logics, and Implementations of high-level programming languages, which comprises the ICFP/PPDP conferences and associated workshops. Previous Haskell Workshops have been held in La Jolla (1995), Amsterdam (1997), Paris (1999), and Montreal (2000). http://www.cs.uu.nl/people/ralf/hw2001.{html,pdf,ps,txt} ============================================================================ Scope ----- The purpose of the Haskell Workshop is to discuss experience with Haskell, and possible future developments for the language. The scope of the workshop includes all aspects of the design, semantics, theory, application, implementation, and teaching of Haskell. Submissions that discuss limitations of Haskell at present and/or propose new ideas for future versions of Haskell are particularly encouraged. Adopting an idea from ICFP 2000, the workshop also solicits two special classes of submissions, application letters and functional pearls, described below. Application Letters ------------------- An application letter describes experience using Haskell to solve real-world problems. Such a paper might typically be about six pages, and may be judged by interest of the application and novel use of Haskell. Functional Pearls ----------------- A functional pearl presents - using Haskell as a vehicle - an idea that is small, rounded, and glows with its own light. Such a paper might typically be about six pages, and may be judged by elegance of development and clarity of expression. Submission details ------------------ Deadline for submission: 1st June 2001 Notification of acceptance: 1st July 2001 Final submission due: 1st August 2001 Haskell Workshop: to be announced Authors should submit papers of at most 12 pages, in postscript format, formatted for A4 paper, to Ralf Hinze (ralf(a)cs.uu.nl) by 1st June 2001. The use of the ENTCS style files is strongly recommended. Application letters and functional pearls should be labeled as such on the first page. They may be any length up to twelve pages, though shorter submissions are welcome. The accepted papers will be published as a University of Utrecht technical report. Programme committee ------------------- Manuel Chakravarty University of New South Wales Jeremy Gibbons University of Oxford Ralf Hinze (chair) University of Utrecht Patrik Jansson Chalmers University Mark Jones Oregon Graduate Institute Ross Paterson City University, London Simon Peyton Jones Microsoft Research Stephanie Weirich Cornell University ============================================================================

1 0

RE: Rank-2 polymorphism & type inference
by Simon Peyton-Jones 05 Dec '00

05 Dec '00

| > My question is: how does the type inference algorithm work in the | > presence of rank-2 types? Does anyone know of any documentation on | > this? Thanks! I had a look at this. Actually it turns out to be only loosely related to rank-2 polymorphism. I've been able to reproduce your problem using only Haskell 98. It looks like a problem with incomplete type inference Consider this: module MP where class C t where op :: t -> Bool instance C [t] where op x = True test :: [Int] -> Bool -- REQUIRED! test y = let f :: c -> Bool f x = op (y >> return x) in f (y::[Int]) Both GHC and Hugs reject this module if the type signature for test is omitted. NHC (v1.00, 2000-09-15) falls over completely, with Fail: Prelude.chr: bad argument All three succeed if the signature is in, or if the signature for f is omitted. This was unexpected, to me at least. You may need to add a type signature if polymorphic recursion is being used, but here it isn't! The problem is this: the compiler learns that y::[Int] "too late" to make use of it when solving the constraints arising from the RHS of f. In more detail, here's what happens. First we typecheck the RHS of f, deducing the types x :: a where a is fresh y :: k a where k is fresh y >> return x :: k a op (y >> return x) :: Bool with constraint C (k a) \x -> op (y >> return x) :: a -> Bool with constraint C (k a) Now we try to generalise over a. We need to discharge the contraint C (k a). Later we will find that y::[Int], so k=[], but we don't know that yet. So we can't solve the constraint. Adding the type signature to 'f' lets both GHC and Hugs figure out that y::[Int] in advance, so we need to solve the constraint C ([] a), which is fine. So I think you have uncovered a genuine problem, and one I don't know how to solve. It can always be "solved" by adding more type information, such as the type sig for 'test'. In you case you said: | After sending out my question, I noticed that hugs and ghc understood my | code differently: from the error messages, we can see that hugs view (\a | -> super a) as having type Sub b _1 -> Super b _2, while ghc thinks it | is Sub c a -> Super c Int. To verify it, I changed my code s.t. y is | defined as | | y = f (\(a :: Sub c Int) -> super a) x This is exactly right, and GHC is happy now. I can't account for Hugs' behaviour. The "right" solution is presumably to defer all constraint checking until we know what 'k' is. But that's a bit tricky because the constraint checking generates bindings that must appear in f's RHS. A full solution looks a bit over-kill-ish. But it's unsettling that the inference algorithm is incomplete. Simon

1 0

Rank-2 polymorphism & type inference
by Zhanyong Wan 04 Dec '00

04 Dec '00

Hello, I'm playing with Haskell's rank-2 polymorphism extension and am puzzled by the following example: ----------------------------------------------------------- module R2Test where class SubType a b where super :: a -> b data Sub c a = Sub data Super c a = Super instance SubType (Sub c a) (Super c a) f :: (forall c. Sub c a -> Super c b) -> Sub c a -> Super c b f g x = undefined x :: Sub c Int x = undefined y :: Super c Int y = f (\a -> super a) x ---------------------------------------------------------- I though the definition of y should type-check because (roughly): 1. We know x :: Sub c Int, y :: Super c Int 2. Hence in f :: (forall c. Sub c a -> Super c b) -> Sub c a -> Super c b, we know a is Int and b is Int. 3. Hence (\a -> super a) :: (forall c. Sub c Int -> Super c Int), and we are all set. However, Hugs 98 Feb 2000 (with the -98 switch) gives me: ERROR "R2Test.hs" (line 19): Cannot justify constraints in application *** Expression : \a -> super a *** Type : Sub b _1 -> Super b _2 *** Given context : () *** Constraints : SubType (Sub b _1) (Super b _2) and GHC 4.08.1 (with the -fglasgow-exts switch) gives: R2Test.hs:19: Could not deduce `SubType (Sub c a) (Super c Int)' from the context: () Probable cause: missing `SubType (Sub c a) (Super c Int)' in the type signature of an expression or missing instance declaration for `SubType (Sub c a) (Super c Int)' arising from use of `super' at R2Test.hs:16 In the right-hand side of a lambda abstraction: super a If I remove the "forall c." from the type signature for f, then both compilers accept my code. My question is: how does the type inference algorithm work in the presence of rank-2 types? Does anyone know of any documentation on this? Thanks! -- Zhanyong # Zhanyong Wan http://pantheon.yale.edu/~zw23/ ____ # Yale University, Dept of Computer Science /\___\ # P.O.Box 208285, New Haven, CT 06520-8285 ||___|

1 1