March 2002 - Haskell - Haskell.org

Your Email / Website Address
by Online Notice 12 Mar '02

12 Mar '02

1 0

RE: first-class polymorphism beats rank-2 polymorphism
by Ralf.Laemmel＠cwi.nl 11 Mar '02

11 Mar '02

Simon Peyton-Jones wrote: > Indeed the foralls are at the top, but I claim that wherever > you could use the composition function you were expecting, > you can also use the one GHC gives you. The two types > are isomorphic. > ... > Let me know if you find a situation where this isn't true. > ... > No I believe it is not a bug. I would be interested to see why you > needed to change your code. It is all not that simple. Let me try to explain. For some deeper background I refer to my draft. One more week to finish. http://www.cwi.nl/~ralf/rank2/ Maybe, we should do that offline. But maybe it is interesting for people how like rank-2 stuff. Let's consult the following code with the ghc 5.03 snapshot. It is basically the same kind of example as in my last posting but I point out a few things more clearly, and the example is simpler. --------------------------------------------------------------------- type Generic i o = forall x. i x -> o x type Id x = x comb :: (Generic Id Id) -> (Generic Id Id) -> (Generic Id Id) comb = undefined comb' :: forall x1 x11 x. (Id x1 -> Id x1) -> (Id x11 -> Id x11) -> Id x -> Id x comb' = undefined yacomb :: (forall x. x -> x) -> (forall x. x -> x) -> (forall x. x -> x) yacomb = (.) yacomb' :: forall x y z. (x -> x) -> (y -> y) -> (z -> z) yacomb' = undefined --------------------------------------------------------------------- I explain the code per def./decl.: 1. The type synonym Generic captures a parameterized function type where we can still plug in type constructors of kind *->* to derive domain and codomain from the explicitly quantified x. The type Generic suggests that we deal parametric polymorphism but in my real code I have class constraints on x. This immediately resolves Simon's concern about the usefulness of defining sequential composition in some new way. I had chosen seq. comp. as an example to play with types. If we go beyond parametric polymorphism, several binary combinators using Generic for arguments and result make sense (see my draft; feedback appreciated). 2. The type constructor Id of kind * -> * is the identity type constructor. That is, given a type, it returns the very same type. There are plenty of useful type constructors like Id but let's restrict our discussion to Id for simplicity. As an aside, I like it very much that ghc allows me to compose type synoyms like I do with Generic and Id. hugs doesn't allow me that, and this implies that I have to use datatypes instead for things like Id, and this in turn implies that I have quite some wrapping / unwrapping going on in my hugs expression code. 3. Let's suppose we want to define SOME binary function combinator comb. It takes two polymorphic functions of a certain type as for i and o and returns another polymorphic function with potentially some other i and o for the domain and codomain. In fact, I have chosen Id for all i and o parameters for the above comb for simplicity. Let's us ignore parametricity for a moment and pretend we know how to define many combinators like this. In the example above, I left comb undefined since I only want to play with the ghc type system. As I said, in my true code I define interesting combinators with such type schemes but with extra class constraints. This is the reason that I can do more things than parametricity allows me. So let us really not think of ordinary (say, parametric polymorphic) sequential composition as my last email maybe suggested. 4. So now let's ask for the type of comb in ghc. It turns out to be the rank-1 (!!!) type I captured as explicit type annotation for comb'. I would have expected a rank-2 type because the forall is scoped by the type synonym Generic. So why should I like to see the forall going to the top? I still would say that THIS IS A BUG. Here is why the types are different: The rank-1 type allows me to combine functions on say integers (by using Int for x x1 and x11). The rank-2 type that I am asking for rules out monomorphic functions to be composed. So the type with the foralls at the top, and the foralls scoped in a rank-2 discipline are NOT isomorphic. Also, keep the possibility of class constraints in mind. Simon, is it maybe possible that you confused the type of (.), that is, forall b c a. (b -> c) -> (a -> b) -> a -> c with the type forall z y x. (x -> x) -> (y -> y) -> z -> z. The b c a in (.) types deal with the possibly different result types. The z y x in my rank-1 comb (messed up by ghc) deal were originally meant to display insistance on polymorphic function arguments. So the the foralls should not be at the top. 5. The type that I wrote down for yacomb is precisely the rank-2 type I would have favoured to see for comb instead of the actual type suggested by ghci. It is a rank-2 type. A minor issue: I expanded the occurrences of Id for readability (ghc keeps them at all costs because it seems to assume that I like to get reminded of them which is not the case BTW). So everything (the two arguments and the result) are of type forall x. x -> x (which should be equal to Generic Id Id). As an example, I define yacomb to be equal to (.). But note yacomb is a very much restricted (.), not just that it composes type-preserving functions but it insists on polymorphic functions. 6. Now let us see what happens if we take all the foralls to the top. This function would be of the type as shown for yacomb', that is, forall x y z., ... This is precisely the type ghci suggests instead of the rank-2 type except that I applied away Id. Now let's try to define yacomb' in terms of yacomb, that is: yacomb' = yacomb This works. Let us not wonder why. Now let's try to define yacomb' in terms of (.) instead, that is: yacomb' = (.) You get a nice type error in ghci 5.03: test.hs:17: Inferred type is less polymorphic than expected Quantified type variable `x' is unified with another quantified type variabl e `z' Quantified type variable `y' is unified with another quantified type variabl e `z' Signature type: forall z y x. (x -> x) -> (y -> y) -> z -> z Type to generalise: (x -> x) -> (x -> x) -> x -> x When checking the type signature for `yacomb'' When generalising the type(s) for `yacomb'' module `Prelude' is not interpreted Whatever this means, it at least shows that the two types are not isomorphic in the sense that ghci very well separates them even in the case of parametric polymorphism. Or is this (another) bug? Simon Peyton-Jones also wrote: > No, GHC does not support partially applied type synonyms, > except in the RHS of other type synonyms. It is a VERY BIG thing to > allow this, because it amounts to allowing lambdas at the type level > and that messes up inference cruelly. > > Why do you think GHC does? Ok, that's what I meant: in RHSs of other type synonyms. BTW, it also works when passing parameters to parameterized datatypes. Here is a variation on defining Generic as a datatypes as opposed to the earlier type synonym. Id is still the same type synonym as before. data Generic' i o = G (forall x. i x -> o x) type TP = Generic Id Id Yes, I was surprised to see that it works to this extent. In fact, it is already quite expressive in this form because it allows us to have type constructors as type synonyms but of course not arbitrary lambdas as Girard's system would ask for. So I revise my question: Does the current support for partially applied type synonyms pose any challenges or is it basically just like macro expansion? That is, is the type system maybe not even affected by it? If it is easy, why is not in Haskell 98 and in hugs? It is terribly useful. Ralf

1 0

RE: H98 Report: expression syntax glitch
by Simon Peyton-Jones 11 Mar '02

11 Mar '02

Ross points out that this is really hard to parse: | case x of y | ($ True) $ \ z -> z :: Bool -> Bool -> y because the parser doesn't know when to stop eating the type and treat the arrow as the case-alternative arrow. Carl reminds us that this is hard to parse too: | do a == b == c because the layout processor is meant to insert a close curly where there would be a syntax error, and that depends on the non-associativity of (==). In both cases, the specification is unambiguous, but asks too much of the parser. But in neither case can I see a cure that is better than the disease. Remember, large-scale fixes are out of court. So in both cases I propose to say something like: here is an example that is hard to implement; wise programers will avoid code like this That is, point out the trap, and acknowledge that few impls will respect the letter of the law. This seems honest, and better than inventing some elaborate cure. Simon

1 0

College Student
by mary lee 11 Mar '02

11 Mar '02

To : Mr. Frank A. Chrishtoph<christo(a)nextsolution.co.jp> I am recently doing my assignment on Haskell at my college. I am just new on Haskell programming. I would like to request if you can teach me for just few programming rules on Haskell. It is my most appreciation to learn from you. My assignment title is INTERNATIONAL AIRLINES SYSTEM. May i know how to open file, put record entry and just read it from its database. How to do a simple input and output for acquire user options using functional programming. It is very important for me to learn Haskell in a proper way. It will lead me to write a good documentation. A good understanding on programming is good. I am good in Visual Basic, Pascal, Cobol, C++ and also JAVA. But facing functional programming is a real problem for me. Now i have doing a simple Haskell programming on the way. I just know how to import file, declare types and display output. Your help and guidelines is most appreciated. From, Lee Ling Ling __________________________________________________ Do You Yahoo!? Try FREE Yahoo! Mail - the world's greatest free email! http://mail.yahoo.com/

2 1

Icsm 2002 Call for Papers: deadline is approaching
by icsm2002.info＠unisannio.it 11 Mar '02

11 Mar '02

Dear Colleague I would like to remind you that the ICSM full paper submission deadline is approaching. ICSM (IEEE International Conference on Software Maintenance), 2002, and associated workshops: SCAM, WSE, WESS and the 1st Workshop on Database Maintenance and Reengineering (DBMR'2002) will be held next October 2002 in Montreal, Canada. Outstanding Keynotes such as Jon Pincus, Microsoft, Industrial and experience papers, research papers, tutorials, tool expositions, dissertation forum, workshops, panels, and other exciting activities have been planned. Papers are due by 18 March 2002 You can sumbit papers following the electronic sumbission process at: http://serg.ing.unisannio.it/~icsmpapers Alternatively, you can also submit the papers via email to: icsm2002.full(a)unisannio.it If you wish to submit papers via email, you are kindly encouraged to fill the Submission Form: http://web.ing.unisannio.it/icsm2002/SubForm.txt we hope that this "Call For Papers" will be useful for your work. Please forward the following to anybody who you think may be interested. Our apologies if you received multiple copy of this. If you would like to be removed from our list please send an email to icsm2002.info(a)unisannio.it with REMOVE in the subject. ICSM2002 Giuliano Antoniol, Program CoChair Ira D. Baxter, Program CoChair ============================================================================ IEEE International Conference on Software Maintenance 2002 Sponsored by IEEE ICSM-2002, Montreal, Canada, 3-6 October 2002 http://www.icsm2002.org icsm2002.info(a)unisannio.it Call for Papers Theme: Maintaining distributed heterogeneous systems ICSM is the major international conference in the field of software and systems maintenance, evolution, and management. This year's theme elaborates on last year's theme of "systems and software evolution in the era of the internet". Standalone legacy applications of yesterday and novel applications using today's technologies are rapidly becoming integrated as part of enterprise-wide and industry-wide systems. The need for rapid integration has led to many distributed heterogeneous systems that are very challenging to maintain and evolve. ICSM 2002 will address these new scenarios and the major challenges of maintenance and evolution. The focus of the conference will be on the new challenges that heterogeneous systems pose for software maintenance, and the new opportunities for researchers and practitioners. A main goal of ICSM is to promote interaction between researchers and practitioners. ICSM 2002 will bring together researchers, practitioners, developers and users of tools, technology transfer experts, and project managers. Jon Pincus (Microsoft) will describe how Microsoft handles software enhancements. Other outstanding Keynote speakers are being arranged. Past conferences have had Parnas, Rombach, McCabe, and Jacobson. ICSM-2002 will offer technical presentations and demonstrations from academia and industry. We are particularly interested in exchanging concepts, prototypes, research ideas, and other results that could contribute to the academic arena and also benefit business and the industrial community. ICSM 2002 will be participatory, with working collaborative sessions and presentations of industry projects. The Conference will be held in conjunction with: WESS -- Workshop on Empirical Studies of Software Maintenance. SCAM -- Source Code Analysis and Manipulation WSE -- Workshop on WEBsite Evolution Topics of interest include but are not restricted to the following aspects of maintenance and evolution: - Methods and theories - Maintenance and/or productivity metrics - Organizational frameworks - Preventive maintenance - Design for maintenance - Tools and environments - Life cycle and process control - Models/methods for error prediction - User interface evolution - Commercial off-the-shelf (COTS) - Third party maintenance - Freeware and open source applications - Program comprehension - Software and system visualisation - Knowledge based systems - Measurement of software - Formal methods - Legal aspects and standards - Software reusability - Internet and distributed systems - Empirical studies - Testing and regression testing - Remote, tele-work - Version and configuration management - Processes and strategies - Management and organisation - Co-operative applications - Source code analysis and manipulation - Processes and strategies - Impact of new software practices - Programming languages - Reengineering and reverse engineering - Multimedia systems RESEARCH PAPERS: Research papers should describe original and significant work in the research and practice of software maintenance and evolution. Case studies, empirical research, and experiments are particularly welcome. We also welcome papers that present leading edge and novel ideas in maintenance. Papers must not exceed 5000 words (10 pages IEEE style) in length, in English. To encourage strong submissions a prize will be awarded for the "Best Paper as Submitted". This Prize is offered by John Wiley & Sons, the publishers of the Journal of Software Maintenance and Evolution. The Program Committee will select the winner and a formal presentation of the Prize will be made in Montreal at ICSM 2002. FAST TRACK PAPERS: Fast Track papers should describe on-going research activities, or summarize the experience in software maintenance and evolution. Papers must not exceed 4 pages, IEEE style, in length, in English. Accepted fast-track papers will be included in a dedicated section of the conference proceedings. DISSERTATION FORUM: We welcome submissions of young researchers that have delivered their dissertation (Masters or Ph.D.) in the last three years. An award will be issued for the best submission. Four page summaries of accepted dissertations will be included in the conference proceedings and a special forum section will be organised at the conference. INDUSTRIAL APPLICATIONS: Proposals for presentations of Industrial Applications are welcome. These can be state-of-the-art descriptions, experience reports and survey reports from real projects, industrial practices and models, or tool demonstrations. A dedicated sub-committee of the program committee will review Industrial Application proposals and a 1-page summary of accepted proposals will be included in the conference proceedings. TUTORIALS: Tutorials should present software maintenance and evolution topics of interest to practitioners. Tutorials may be full day or half-day in length. SUBMISSION STYLE: PDF and/or Postscript electronic submission only. Papers longer than 15 pages or 6000 words will be returned to the authors. Acceptance notification will occur July 1, 2002. IMPORTANT DATES You can sumbit papers following the electronic sumbission process at: http://serg.ing.unisannio.it/~icsmpapers Alternatively, you can also submit the papers via email to: icsm2002.full(a)unisannio.it If you wish to submit papers via email, you are kindly encouraged to fill the Submission Form: http://web.ing.unisannio.it/icsm2002/SubForm.txt Research Papers deadline: 18 March 2002 mailto:icsm2002.full@unisannio.it Fast Track Papers deadline: 1 May 2002 mailto:icsm2002.short@unisannio.it Dissertation Forum deadline: 1 May 2002 mailto:icsm2002.thesis@unisannio.it Industrial Applications deadline: 1 May 2002 mailto:icsm2002.industry@unisannio.it Tutorials deadline: 18 March 2002 mailto:icsm2002.tutorial@unisannio.it

1 0

RE: Isn't this tail recursive?
by Simon Marlow 11 Mar '02

11 Mar '02

> On 10 Mar 2002, Jyrinx wrote: > > > In the case expression at the end of countAll, each of the > values looks > > to me like a recursive tail call - I should think (hope?) > that it would > > be optimized by GHC into a goto statement (a la Scheme). Instead, my > > program eats up memory (I've got 256 MB) until the RTS > whines about a > > stack overflow. > > It is tail recusive. unfortunately, that's not the problem. > apparently ghc is not smart enough to realize that countAll' should > really be strict in basically all arguments. (hell, I'm not > quite sure I > can claim to be smart enough to say that!) The function as written is only strict in its list argument, and its usage site only demands the 'l' argument strictly. So unless the compiler were to make use of the "can't fail" property of '+' on Int (which might not even hold if overflow checking is used), the compiler can't possibly evaluate the accumulating parameters of countAll' strictly. It would be possible to do strict evaluation in the case that the suspended computation is known to take a small bounded amount of time and space and can't fail - GHC doesn't do this, but we've wondered about it from time to time. I do wonder how often similar patterns crop up in practice - I've certainly encountered this pattern in my own code several times, and solved it using seq or strict constructor fields. > Never fear, > -fall-strict is here! I had no idea this flag still worked. As I recall, it was an experiment that turned out to be a bad idea - you're probably just better off using seq. Cheers, Simon

3 2

PPDP 2002 - Last call for papers --> March 21
by Claude Kirchner 11 Mar '02

11 Mar '02

PPDP 2002 - Call for papers March 21, 2002 submission deadline http://ppdp2002.cs.brown.edu Fourth International Conference on Principles and Practice of Declarative Programming 6-8 October, Pittsburgh, USA as part of PLI 2002 (http://pli2002.cs.brown.edu) *** The electronic submission system is open at *** http://ppdp-2002.loria.fr/ Invited speakers: Neil Jones (University of Copenhagen) Catuscia Palamidessi (The Pennsylvania State University) Janos Sztipanovits (Vanderbilt University ) Important dates March 21, 2002 submission FIRM deadline May 30, 2002 acceptance decisions June 30, 2002 Camera-ready copies October 6-8, 2002 Conference Submission web site: http://ppdp-2002.loria.fr Conference Chair: Frank Pfenning, CMU, USA Program Chair: Claude Kirchner, LORIA and INRIA 615, rue du Jardin Botanique, BP 101 54602 Villers-lès-Nancy, France Claude.Kirchner(a)loria.fr Program Committee: Hassan Ait Kaci: ILOG, France Olivier Danvy: BRICS, University of Aarhus, Denmark Mariangiola Dezani: Universita di Torino, Italy Francois Fages: INRIA, France Fergus Henderson: The University of Melbourne, Australia Manuel Hermenegildo: University of Madrid, Spain Andrew Gordon: Microsoft Research, UK Amy Felty: University of Ottawa, Canada Claude Kirchner: LORIA & INRIA, France Paul Klint: CWI, The Netherlands Michael Maher: Griffith University, Australia and Loyola University Chicago, USA Dale Miller: The Pennsylvania State University, USA Roberto Nieuwenhuis: University of Barcelona, Spain Frank Pfenning: CMU, USA Francesca Rossi: University of Padova, Italy Scope of the Conference PPDP 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 logic, functional, constraint, probabilistic, rule 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 related to new and interesting ideas relating broadly to declarative programming are encouraged. The technical program of the conference will combine presentations of the accepted papers and system descriptions with invited talks and advanced tutorials. Previous PPDP meetings were held in Paris (1999), Montreal (2000), Firenze (2001). Topics of Interest Logic and Constraint Programming; Rule Programming; Object-Oriented Programming; Concurrent Programming; Mobile Computing; Specification Languages and Methods; Type and Module Systems; Program Logics and Verification; Program Analysis and Transformation; Abstract Machines and Compilation Methods; Parallel and Distributed Implementations; Programming Environments; Applications of Declarative Programming; Implementation Techniques; Logical and Semantical Aspects of Declarative Programming; Declarative and probabilistic programming. Paper Submissions Submissions must be received on or before March 21, 2002 (this is a HARD deadline) and must describe original, previously unpublished work that has not been simultaneously submitted for publication elsewhere. They must be written in English and, in case the work is accepted for presentation and publication, one of the author must attend the conference to present it. Submissions must contain a clearly delineated part intended for the proceedings not exceeding 12 pages and 9 pt (for a full description see the ACM conference format at http://www.acm.org/sigplan/conferences/author-info) and must have a cover page with an abstract of up to 200 words, keywords, postal and electronic mailing addresses, and phone and fax numbers of the corresponding author. Additional material for possible consideration by reviewers may be included in the form of appendices. Submitted papers can be either: Regular papers that will be judged in particular on originality, correctness and significance, or System descriptions that will be judged in particular on usefulness and design, originality of system design, implementation or application. They must contain a link to a working system. All submissions are to be electronic unless specifically approved by the Program Chair. Submissions in PostScript or PDF formats should be submitted via the conference management system as described on the web site. Authors will be notified of acceptance decisions by May 30, 2002 Camera-ready copies of the accepted papers must be received by June 30, 2002. Proceedings will be published by ACM Press. Authors of accepted papers will be required to sign the ACM copyright form, which will be made accessible from this site. Conference Venue and Related Events PPDP 2002 is part of a federation of colloquia known as Principles, Logics and Implementations of high-level programming languages (PLI 2002) which includes the ACM SIGPLAN International Conference on Functional Programming (ICFP 2002) and the first ACM SIGPLAN Conference on Generators and Components (GCSE/SAIG'02) . The colloquia and affiliated workshops will run from October 4 to October 8, 2002 and will be held in Pittsburgh, USA. Details about the affiliated conferences and workshops will appear at the URL http://pli2002.cs.brown.edu/. Sponsorship PPDP 2002 is sponsored by ACM SIGPLAN. ----------------------------------------------------------------

1 0

RE: first-class polymorphism beats rank-2 polymorphism
by Simon Peyton-Jones 11 Mar '02

11 Mar '02

| Looking at the type of sequ, | the foralls for t end up at the top. | Hence, I have no chance to define sequential | composition. Indeed the foralls are at the top, but I claim that wherever you could use the composition function you were expecting, you can also use the one GHC gives you. The two types are isomorphic. Let me know if you find a situation where this isn't true. | Please let me know if this is a bug. No I believe it is not a bug. I would be interested to see why you needed to change your code. | I just realized that type synonyms in GHC seem to be valid | arguments even when not completely instantiated? This is | wonderful. It is not supported in hugs. How difficult is it | to cope with this? Does it make a real difference for the type system? No, GHC does not support partially applied type synonyms, except in the RHS of other type synonyms. It is a VERY BIG thing to allow this, because it amounts to allowing lambdas at the type level and that messes up inference cruelly. Why do you think GHC does? Simon

1 0

Layout indentation marking
by Ian Lynagh 10 Mar '02

10 Mar '02

Given this module module Main where main :: IO() main = putStrLn $ show $ foo foo :: Int foo = x + y where x = 6 s = "foo\ \bar" y = 7 nhc98 and hugs correctly (as per the revised report) print 13. ghc gives q.lhs:11: parse error on input `=' I think ghc is in the right here and the report should be updated to read + Where the start of a lexeme does not follow the end of a lexeme on the same line, this lexeme is preceded by <n> where n is the indentation of the lexeme, provided that it is not, as a consequence of the first two rules, preceded by {n}. (A string literal may span multiple lines -- Section 2.6.) (it currently reads + Where the start of a lexeme does not follow a complete lexeme on the same line, this lexeme is preceded by <n> where n is the indentation of the lexeme, provided that it is not, as a consequence of the first two rules, preceded by {n}. (A string literal may span multiple lines -- Section 2.6.) where I have altered only the first line). Thanks Ian

1 0

Protect your vacation home against winter freeze for less than 30 cents a day!
by Doak Serrels 10 Mar '02

10 Mar '02

1 0