December 2001 - Haskell

Strict foldl
by Ch. A. Herrmann 07 Dec '01

07 Dec '01

Hi Haskellers, which compiler settings do I have to pass to ghc-5.02 in order to achieve that the strictness analyzer recognizes strictness of (+) in foldl and computes sum in constant space? Prelude> sum [1..10000000] had the following effect: PID USER PRI NI SIZE RSS SHARE STAT %CPU %MEM TIME COMMAND 23542 herrmann 20 0 250M 130M 97500 R 66.3 52.4 0:21 ghc-5.02 Of course, one could define a strict foldl oneself: > sfoldl f e [] = e > sfoldl f e (x:xs) = (sfoldl f $! (f e x)) xs ( > sfoldl (+) 0 [1..10000000] returns 50000005000000 in about a minute interpreted using 18MB of total space.) But with the own definition one has to redefine many of the prelude functions. Thanks in advance -- Christoph Herrmann

4 5

RE: Strict foldl
by Julian Seward (Intl Vendor) 07 Dec '01

07 Dec '01

| > Prelude> sum [1..10000000] | > | > had the following effect: | > | > PID USER PRI NI SIZE RSS SHARE STAT %CPU %MEM TIME COMMAND | > 23542 herrmann 20 0 250M 130M 97500 R 66.3 52.4 0:21 ghc-5.02 | | Is this what I think it is? Do you benchmark the | interpreter? Interpreted code isn't optimised. When I | compile | | main = print $ sum [1..10000000] | | with -O2, it takes 13s on a 600MHz P3 and runs in 1.5MB of | space. I should point out that the interpreter's (byte-)code generator is simplistic, and does not emit code to stub (make NULL) stack slots which are known to be dead. This is probably causing the space behaviour you are seeing. In contrast the compiled-code back ends do do stack stubbing. If anyone wants to rewrite the byte code generator to keep track of stack slot liveness and emit suitable stub insns, that would be a service to us all :) [constant folding] | The natice code generator probably also performs some of | those optimisations, but I am not sure exactly which. Yes, it tries quite hard to fold literal trees and usually succeeds well enough that the generated code is pretty much identical to that emitted by gcc. J

1 0

Haskell Persistence
by Vorin, Michael 07 Dec '01

07 Dec '01

I am interested in pursuing practical development of persistence in Haskell. To this end I have been looking for code/systems which have been developed previously to build upon - not wishing to reinvent the wheel. I have found some references in the literature but have been enable to track down any "artefacts". I was hopping someone could help me. I have found: (1) Efficient Persistent Haskell, Tony Davie, Kevin Hammond, and Juan Quintela Division of Computer Science, University of St Andrews, 1998 (2) Models for Persistence in Lazy Functional Programming Systems, McNally, University of St Andrews, 1993. (3) A Functional Database (1989) (Correct) Phil Trinder (4) Two Models For Integrating Persistence and Lazy Functional Languages (1991) David J. McNally, Antony J.T. Davie (5) Realizing State-Based Database Concepts in a Non-Strict, Statically Typed, Purely Functional Persistent Programming Language Yoshihiko Ichikawa Department of Information Sciences, Ochanomizu University

2 1

Re: class parameters to existential datatypes
by Ashley Yakeley 06 Dec '01

06 Dec '01

At 2001-12-06 13:11, Ashley Yakeley wrote: >At 2001-12-06 13:04, John Hughes wrote: > >> > data Foo c = forall a . c a => Foo a > >What are you trying to say? In 'data Foo c' you are saying that c is a >type (as a parameter). In 'c a =>' you are saying that c is a class. So >naturally Haskell complains. I'm sorry, I'm not paying attention today... -- Ashley Yakeley, Seattle WA

1 0

Re: class parameters to existential datatypes
by Ashley Yakeley 06 Dec '01

06 Dec '01

At 2001-12-06 13:04, John Hughes wrote: > > data Foo c = forall a . c a => Foo a What are you trying to say? In 'data Foo c' you are saying that c is a type (as a parameter). In 'c a =>' you are saying that c is a class. So naturally Haskell complains. -- Ashley Yakeley, Seattle WA

1 0

Re: class parameters to existential datatypes
by John Hughes 06 Dec '01

06 Dec '01

I would like to be able to write something like this: > data Foo c = forall a . c a => Foo a Unfortunately, this isn't allowed (apparently) because it's an illegal class assertion (or at least that's what ghc tells me). ... so I have two questions: 1) Is there any particular reason whey we can't do this (it would break some type safety things or whatever) 2) Any ways to get around it? Thanks! - Hal Hmm. Interesting. I wrote a paper a couple of years ago, on "Restricted Data Types", which discusses among other things how to simulate abstraction over a class by abstraction over the corresponding dictionary type. You might find the technique useful. It's at http://www.cs.chalmers.se/~rjmh/Papers/restricted-datatypes.ps John Hughes

1 0

Rewriting Implementations
by N Ghani 06 Dec '01

06 Dec '01

Is there any Haskell implementations of rewriting tools. This could be any of string, term, equational or whatever forms of rewriting. Also are there any Haskell packages including data structures for algebriac objects like monoids, groups, rings, modules, graphs, categories, enriched categories, K-algebras (ie monoids in K-modules), kan extensions .... Finally, are there any haskell packages for computing quotients of such structures (perhpas using rewriting) Neil

1 0

FOOL 9 Call for Participation
by Martin Odersky 06 Dec '01

06 Dec '01

CALL FOR PARTICIPATION The Ninth International Workshop on Foundations of Object-Oriented Languages FOOL 9 Sponsored by ACM SIGPLAN January 19, 2002 Portland, Oregon Following POPL '02 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 bring together researchers to share new ideas and results in these areas. The next workshop, FOOL 9, will be held in Portland, Oregon, on Saturday January 19, 2002, the day after POPL'02. To register for the workshop, use the standard registration form, available through: http://www.cse.ogi.edu/PacSoft/conf/popl -------------------------------------------------------------------------- Preliminary schedule Saturday, January 29, 2002 8:40 Start 8:45-9:45 Invited Talk Distributed Objects - The Next 10 Years Andrew Black 9:45-10:15 Break 10:15-12:15 Session 1 Modular Typechecking for Hierarchically Extensible Datatypes and Functions Todd Millstein, Craig Chambers Type-checking multi-methods in ML (A modular approach) Daniel Bonniot First-Class Modules for Haskell Mark Shields, Simon Peyton Jones Extensible Objects Without Labels Christopher Stone 12:15-14:00 Lunch 14:00-15:30 Session 2 Modern Concurrency Abstractions for C# Nick Benton, Luca Cardelli, Cedric Fournet OO languages late-binding signature Antoine Beugnard A Semantics for Advice and Dynamic Joint Points in Aspect-Oriented Programming Mitchell Wand, Gregor Kiczales, Christopher Dutchyn 15:30-16:00 Break 16:00-17:30 Session 3 Automatic Discovery of Read-Only Fields, Jens Palsberg, Tian Zhao, Trevor Jim. Generation of Verification Conditions for Abadi and Leino's Logic of Objects Francis Tang, Martin Hofmann Simple Type Inference for Structural Polymorphism Jacques Garrigue ------------------------------------------------------------------------- Steering Committee: Martin Abadi, University of California, Santa Cruz Kim Bruce, Williams College Luca Cardelli, Microsoft Research Kathleen Fisher, AT&T Labs Benjamin Pierce, University of Pennsylvania (chair) Didier Remy, INRIA Rocquencourt Program Committee: Viviana Bono, Universita di Torino Craig Chambers, University of Washington Erik Ernst, University of Aalborg Giorgio Ghelli, University of Pisa Atsushi Igarashi, University of Tokyo Shriram Krishnamurthi, Brown University Martin Odersky, EPFL (chair) <fool9(a)cs.williams.edu> Clemens Szyperski, Microsoft Research Jan Vitek, Purdue University

1 0

RE: Haskell 98 Revised
by Simon Peyton-Jones 05 Dec '01

05 Dec '01

Folks, Concerning the recent change about instance declarations, should this be valid? module M( C(op1) ) where -- NB: op2 not exported class C a where op1 :: a->a op2 :: a->a module N where import M instance C Int where op1 = ... op2 = ... -- Is this ok? The point here is that M does not export op2. Can we still bind it in the instance declaration in N? The old Report was silent on this point, and so is the new one. I'd like to say "no, this is illegal". Haskell uses hiding as its main abstraction mechanism, and if op2 is hidden then an importing module should not be able to see it in any way. I'll clarify this; but I thought I should point out the issue. Simon | -----Original Message----- | From: Simon Peyton-Jones [mailto:simonpj@microsoft.com] | Sent: 04 December 2001 12:03 | To: haskell(a)haskell.org | Cc: Simon Peyton-Jones | Subject: Haskell 98 Revised | | | Gentle Haskellers | | The December issue of the Haskell 98 Report is done. | | http://research.microsoft.com/~simonpj/haskell98-revised | | As usual, changes are highlighted in the overall bugs list | thus: [Dec 2001], so you can find them easily. | | There are the usual crop of presentational improvements | (thanks esp to Ian Lynagh, George Russel, Feliks Kluzniak for | much careful reading). There are two non-trivial changes that | I decided to adopt: | | 1. Add showIntAtBase, showOct and showHex to the Numeric library. | | 2. Remove the wart concerning qualified names in instance | declarations. | This a breaking change, in the sense that exotic Haskell programs | may have to change, but I judge it worth it, after some | consultation. | In particular: | * if you use H/Direct, you'll have to re-generate your | Haskell files with a different flag | * if you use the Edison library, you'll need a new copy of | the library (this isn't a problem in practice because it | comes bundled with your compiler) | | The other thing I'd ask you to look at particularly is the | layout algorithm. George and Ian have both pointed out bugs, | but it's very easy to get wrong so a few more eyeballs on it | would be a Good Thing. | | The only unresolved thing I have in my pile is some stuff | about the lexical syntax of comments, which I find it hard to | get excited about. We are definitely converging. My earnest | hope is to finally freeze the Report at Christmas. So this | is your last chance. I hope. | | Thanks | | Simon | | ========================== | The instance decl wart | | In Haskell 98 as she stands, when you give an instance | declaration, the method name is treated as an *occurrence* | and so has to be | qualified if it is ambiguous: | | module Foo where | | compare = <something> | | instance Ord T where | Prelude.compare = ... -- NB! | | You have to say "Prelude.compare" on the LHS, because both | Prelude.compare and Foo.compare are in scope. This is | reasonable on the RHS, of course, but it is plain silly on | the LHS, because it | *must* refer to the compare from the Ord class! After all, | its an instance declaration for Ord. | | Not only is it surprising (most people think that plain | "compare" should be fine) but it also adds a whole new big | production to the grammar (qfunlhs). | | So, after some consulation, I have decided to remove this | wierd thing. The analogy is with type signatures, where we | can already write | | module Foo where | | compare :: Int -> Int | compare = ... | | Note that we don't have to write "Foo.compare :: Int -> Int" | in the type signature. | | | The remaining question is how to explain this point in the | Report. My initial conclusion is that simply deleting the | offending text was enough. Explaining the problem (given that | it isn't really a problem) seems to complicate matters. | Nevertheless I'm entirely happy to add an explanation, if | people want it and say what they'd like to see. | | The relevant section is 4.3.2. page 46 of the Report. | | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell |

2 1

RE: hiding imports
by Simon Peyton-Jones 05 Dec '01

05 Dec '01

I think it's an ill-thought-out exception. The point is this: if a data constructor cannot appear on its own in a hiding list, then you can't hide the constructor without hiding the type. Currently you can say import Maybe hiding( Just ) It would be simpler and more uniform to only allow data constructors inside parens, just as for exports, but then I'd have to say import Maybe hiding( Maybe(Just) ) and now the type constructor Maybe is hidden too. I say "ill thought out" because the exception doesn't actually solve the problem, as you point out. You may accidentally hide things you didn't mean to. So perhaps the cure is as bad as the disease. Changing this would be technically easy (delete a sentence) but it might break some programs, so that suggests the status quo. Simon | -----Original Message----- | From: Iavor S. Diatchki [mailto:diatchki@cse.ogi.edu] | Sent: 04 December 2001 19:14 | To: haskell(a)haskell.org | Subject: hiding imports | | | hello, | | i was wondering if there was a reasong why "hiding imports" | have different semantics from "importing imports" and | "exports". what i mean is, if one | writes: | | module A(T) where | data T = T | only the type constructor T is exported. simillarly if i write: | | module A where | data T = T | | module B where | import A(T) | | only the type constructor is imported, but if i write | (module A as above) | | module B where | import A hiding (T) | | both the type constructor and the value constructor are hidden. | | this seems not only irregular, but may also be inconvinient | in practise as sometimes it happens that a type constructor | and a data constructor have the same name, but the data | constructor does not "belong" to the type constructor. for example: | | module A where | type T = TGen Int | data TGen a = T a | S | | module B where | import A hiding (T) -- intending to just hide the type T | genF = T -- error T not in scope! | | so if i wanted to ignore the type T, but still have the data | constructor i | have to explicitly import it, i.e. write: | module B where | import A hiding (T) | import A (TGen(T)) | which is kind of ugly. is this strange behaviour for | historical reasons, | or was there a practical reason why this decision was made? | | bye | iavor | | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell |

1 0