May 2001 - Haskell - Haskell.org

Re: Implict parameters and monomorphism
by John Hughes 03 May '01

03 May '01

(B) Monomorphism restriction "wins" Bindings that fall under the monomorphism restriction can't be generalised Always generalise over implicit parameters *except* for bindings that fall under the monomorphism restriction Consequences * Inlining isn't valid in general * No unexpected loss of sharing * Simple bindings like z = ?y + 1 accepted (get value of ?y from binding site) (C) Always generalise over implicit parameters Bindings that fall under the monomorphism restriction can't be generalised, EXCEPT for implicit parameters Consequences * Inlining remains valid * Unexpected loss of sharing (from the extra generalisation) * Simple bindings like z = ?y + 1 accepted (get value of ?y from occurrence sites) Discussion ~~~~~~~~~~ None of these choices seems very satisfactory. But at least we should decide which we want to do. It's really not clear what is the Right Thing To Do. If you see z = (x::Int) + ?y would you expect the value of ?y to be got from the *occurrence sites* of 'z', or from the valuue of ?y at the *definition* of 'z'? In the case of function definitions, the answer is clearly the former, but less so in the case of non-fucntion definitions. On the other hand, if we say that we get the value of ?y from the definition site of 'z', then inlining 'z' might change the semantics of the program. Choice (C) really says "the monomorphism restriction doesn't apply to implicit parameters". Which is fine, but remember that every innocent binding 'x = ...' that mentions an implicit parameter in the RHS becomes a *function* of that parameter, called at each use of 'x'. Now, the chances are that there are no intervening 'with' clauses that bind ?y, so a decent compiler should common up all those function calls. So I think I strongly favour (C). Indeed, one could make a similar argument for abolishing the monomorphism restriction altogether. I disagree. I think it's important to have a simple model of how many times expressions are evaluated. Function bodies are clearly evaluated many times, once for each call, but non-function bindings should be evaluated at most once to respect call-by-need semantics. Breaking the monomorphism restriction in ANY case makes both space and time cost of evaluation unpredictable, and brittle when program changes elsewhere introduce or remove an implicit parameter. It isn't good enough to say `the chances are' that a program has, for example, linear time and constant space complexity: the programmer should be able to convince himself of such properties. As far as what one would `expect', it's in the very nature of dynamic binding that it makes the meaning of an expression depend on its context. I for one would certainly not expect that inlining a definition bound to such an expression should preserve its meaning! Inlining changes the context, so `of course' can change the meaning. So I strongly prefer (B)! John Hughes

6 6

Re: Implict parameters and monomorphism
by John Hughes 03 May '01

03 May '01

Maybe I misinterpret the Haskell Report but I thought it does not even demand call-by-need evaluation (it only speaks of non-strict semantics). So why have a special rule in the language definition to support something cbn-ish for this particular case? As long as the Report does not specify any execution model the MR looks rather arbitrary to me. Well, the Haskell Report may not require call-by-need semantics, but it permits it at least. Without the MR that would not be the case: some programs would *require* call-by-name. Actually I would prefer the report to be much more explicit about both sharing and evaluation order, to enable compiler-independent reasoning about time and space behaviour. As it stands, compilers do in fact implement call-by-need, and so one can in practice reason fairly safely about time behaviour, but they vary in the choice of evaluation order, which makes space leaks come and go on different compilers. In any case, I don't buy the argument that because reasoning about costs is already problematic in Haskell, it doesn't matter if we make it even harder...! > Breaking the monomorphism restriction in ANY case makes both > space and time cost of evaluation unpredictable, and brittle > when program changes elsewhere introduce or remove an implicit > parameter. It isn't good enough to say `the chances are' that > a program has, for example, linear time and constant space > complexity: the programmer should be able to convince himself > of such properties. Why isn't it good enough if the compilers give warnings then? The Report could even require it. To me it seems overly restrictive to rule out perfectly correct programs for the sole reason of potentially surprising space/time behaviour. After all it is not forbidden to write Haskell programs with obscure space leaks. I have no faith in compiler warnings. For one thing, they're irritating. For another, you don't see them when it matters -- when you *read* the code. I'd far rather explicitly distinguish call-by-name and call-by-value in the source code (and made a suggestion along these lines some time ago), so that the semantics is visible to all. Of course, we can't forbid the programmer to write inefficient programs. But we can make gross inefficiencies easier or harder to find. Haskell just can't be used in practice unless one tracks down and fixes space leaks. I don't want to be debugging "time leaks" caused by unexpected call-by-name as well! -- Andreas Rossberg, rossberg(a)ps.uni-sb.de John Hughes

2 1

Re: Existential Type Declarations in Hugs
by Critterrathman＠aol.com 03 May '01

03 May '01

In a message dated 5/3/2001 4:00:18 AM Central Daylight Time, qrczak(a)knm.org.pl writes: > Should be: > setx (MakeExistentialShape a) newx = MakeExistentialShape (setx a > newx) > The result of setx must have the same type as its first argument. > Thanks. That solves my problem. BTW, what is this "Skolem constant" that's referred to in the error message that I received? Chris Rathman

2 1

Re: Implict parameters and monomorphism
by Lennart Augustsson 03 May '01

03 May '01

OK, so since noone liked my original example here's another one. It involves no defaulting and no classes in the funny function definition. -- Here's the type signature that makes a difference. --fun :: a -> Char fun x = const (fun x) (fun True) fix f = let x = f x in x class C a where m :: a -> String instance C Char where m _ = "has signature" instance C Bool where m _ = "no signature" main = putStrLn (m (fix fun)) It is not at all surprising that you can write this. Originally type signatures only allowed you to put a signature that was more specific. Polymorhic recursion on the other hand allows you to make the type more general by putting a type signature on a definition. Combining these you can make the signature be incomparable to the deduced type. Using the class system you can then dispatch on the type and get different behaviour. -- Lennart

1 0

Re: Implict parameters and monomorphism
by C.Reinke 03 May '01

03 May '01

> But most importantly, this was a bad example. There was a much better > one posted on this mailing list a while ago. Does anyone remember it? > > -- Lennart Perhaps I should mention a useful application of this game, somewhat unhelpfully named "Representative thingies" in my Haskell corner: http://www.cs.ukc.ac.uk/people/staff/cr3/toolbox/haskell/ Load the file R.hs in your favourite Hugs (Hugs mode), and you'll see things like this (see comments in R.hs for more examples): Main> foldl (+) 0 [1..4] :: Int 10 Main> foldr (+) 0 [1..4] :: Int 10 Main> foldl (+) 0 [1..4] ((((0 + 1) + 2) + 3) + 4) Main> foldr (+) 0 [1..4] (1 + (2 + (3 + (4 + 0)))) Well, I found it useful (and fun; just a pity that you can't overload (implicit) application in Haskell;-).. Claus

1 0

RE: Implict parameters and monomorphism
by Simon Peyton-Jones 03 May '01

03 May '01

| a) That adding a type signature can change the dynamic semantics | of the program. This would be the first and only | occurrence of | such behaviour. | | At present, adding a type signature changes both the static | semantics and the cost of running a program That's true: but adopting (B) means that adding a type signature may cause the program to print a different answer! That seems qualitiatively different to giving the same answer only slower or faster; or rejecting the program altogether. Type signatures should specialise a type -- which means that efficiency may increase, or that the program may no longer be typable, but surely it shouldn't change the answer! | Are you sure this second one really holds? I claim the | effects analysis is just type inference! Indeed it is. I just don't want programmers to have to do type inference in their heads to figure out the meaning of the program. Simon

4 5

Re: Implict parameters and monomorphism
by C.Reinke 03 May '01

03 May '01

> > > Try this program: > > > -- Try commenting out this type signature. > > > fun:: (Num a) => a -> Int > > Defaulting applies only when all classes involved are Haskell 98. > > First, I cannot parse that sentence, but I assume you mean when all > classes are Prelude classes. > Second, I'm pretty sure we all agreed that this was a silly rule and > should not be in the Haskell definition. I was certain that that it had > been removed from the Haskell report, but I guess not. (hbc used > to make this check, but I removed it when everyone seemed to > agree that rule was a bad idea). http://research.microsoft.com/~simonpj/haskell98-revised/haskell98-bugs.html (Could it be made more prominent on www.haskell.org that this Haskell98 bugs list is indeed part of Simon's ongoing, soon to be completed revision of the two reports? Just so that people like me notice that the revised reports take priority over whatever the current ones say..) Page 49, Section 4.3.4, Ambiguous Types... In the third paragraph from the end of Section 4.3.4, replace "...an ambiguous type variable is defaultable if at least one of its classes is a numeric class..." by "...an ambiguous type variable, v, is defaultable if v appears only in constraints of the form (C v), where C is a class, and if at least one of its classes is a numeric class...". The new phrase is "if v appears only in constraints of the form (C v) where C is a class". Without this condition the rest of the sentence does not make sense. Claus

1 0

Re: Implict parameters and monomorphism
by C.Reinke 03 May '01

03 May '01

> > Try this program: > > -- Try commenting out this type signature. > > fun:: (Num a) => a -> Int > Defaulting applies only when all classes involved are Haskell 98. > hbc, nhc98 and Hugs are not conforming. Seems you're right (all classes for the ambiguous type variable need to be from prelude or standard libraries). Okay, so let's try the good old boring show: -- ii :: Double ii = 1 main = case length (show ii) of { 1 -> putStrLn "type signature excluded" ; _ -> putStrLn "type signature included" } Still, I liked Lennart's "magic" version;-) Claus

1 0

WFLP 2001 - Final Call for Papers
by Frank Steiner 03 May '01

03 May '01

====================================================================== FINAL CALL FOR PAPERS WFLP 2001 International Workshop on Functional and (Constraint) Logic Programming comprising the 10th International Workshop on Functional and Logic Programming and 16th Workshop on Logic Programming Kiel, Germany September 13-15, 2001 ====================================================================== NEW: * Submission guidelines for electronic submissions * Special issue of ENTCS (Electronic Notes in Theoretical Computer Science) for selected papers ---------------------------------------------------------------------- GENERAL WFLP 2001 is the combination of two workshops of a successful series of annual workshops on declarative programming. The international workshops on functional and logic programming aimed at bringing together researchers interested in functional programming, logic programming, as well as their integration. Previous workshops have been held in Benicassim (Spain), Grenoble (France), Bad Honnef (Germany). The workshops on (constraint) logic programming are the annual meeting of the Society of Logic Programming (GLP e.V.) and bring together researchers interested in logic programming, constraint programming, and related areas like databases and artificial intelligence. Previous workshops have been held in Germany, Austria and Switzerland. In this year both workshops will be jointly organized in order to promote the cross-fertilizing exchange of ideas and experiences among researches and students from the different communities interested in the foundations, applications, and combinations of high-level, declarative programming languages and related areas. The technical program of the workshop will include invited talks, presentations of refereed papers and demo presentations. The WWW page of the workshop is: http://www.informatik.uni-kiel.de/~wflp2001 ---------------------------------------------------------------------- TOPICS The topics of interest include (but are not limited to): * Functional programming * Logic programming * Constraint programming * Deductive databases * Extensions of declarative languages, objects * Multi-paradigm declarative programming * Foundations, semantics, nonmonotonic reasoning, dynamics * Parallelism, concurrency * Program analysis, abstract interpretation * Program transformation, partial evaluation, meta-programming * Specification, verification, declarative debugging * Knowledge representation, machine learning * Implementation of declarative languages * Advanced programming environments and tools * Applications The primary focus is on new and original research results but submissions describing innovative products, prototypes under development or interesting experiments (e.g., benchmarks) are also encouraged. ---------------------------------------------------------------------- IMPORTANT DATES Submission of papers: May 15, 2001 Notification of acceptance: June 20, 2001 Camera-ready papers: July 20, 2001 Workshop: September 13 - 15, 2001 ---------------------------------------------------------------------- SUBMISSION Authors are invited to submit an extended abstract (no longer than 10 pages including figures and references) or a system description (no longer than 3 pages) in postscript format (11pt) before May 15, 2001. Submissions should include the title, authors' names, affiliations, addresses, and e-mail. *NEW* The details about the procedure to submit papers electronically are described on the workshop website. If you have any problems with submitting papers, please send an email to wflp2001(a)informatik.uni-kiel.de. ---------------------------------------------------------------------- BEST NEWCOMER AWARD An award will be given to the best paper exclusively written by one or several young researchers who have not yet obtained their PhD degrees. Papers written in this category should be clearly marked "Student papers" in the submission. ---------------------------------------------------------------------- PROCEEDINGS The proceedings with the full versions of all accepted contributions (no longer than 15 pages for regular contributions and 3 pages for system descriptions) will be published as a Technical Report of the University of Kiel. *NEW* A special issue of ENTCS (Electronic Notes in Theoretical Computer Science) containing revised versions of high-quality contributions will be organized after the workshop. ---------------------------------------------------------------------- PROGRAM The workshop will be a 3-day event including presentations of the accepted papers, system demos, and INVITED TALKS by Peter Van Roy (Catholic University of Louvain) Thomas Arts (Ericsson) ---------------------------------------------------------------------- LOCATION WFLP 2001 will take place at the Christian-Albrechts-University of Kiel. More details about the accomodation, traveling information, etc., will be available at the WFLP 2001 WWW page at http://www.informatik.uni-kiel.de/~wflp2001/ ---------------------------------------------------------------------- CONTACT WFLP 2001 Prof. Michael Hanus Institut fuer Informatik und Praktische Mathematik Christian-Albrechts-Universitaet Kiel Olshausenstr. 40 D-24098 Kiel, Germany Phone: ++49-(0)431-880-7271 or -7270 (Secr.) Fax : ++49-(0)431-880-7613 Email: wflp2001(a)informatik.uni-kiel.de WWW: http://www.informatik.uni-kiel.de/~wflp2001/ ---------------------------------------------------------------------- PROGRAM COMMITTEE Slim Abdennadher (LMU Muenchen) Maria Alpuente (UP Valencia) Sergio Antoy (Portland State University) Christoph Beierle (FernUniv. Hagen) Alexander Bockmayr (Univ. Henri Poincare, Nancy) Harold Boley (DFKI Kaiserslautern) François Bry (LMU Muenchen) Juergen Dix (Univ. Koblenz) Rachid Echahed (IMAG, Grenoble) Uwe Egly (TU Wien) Moreno Falaschi (Univ. Udine) Burkhard Freitag (Univ. Passau) Thom Fruehwirth (LMU Muenchen) Norbert E. Fuchs (Univ. Zuerich) Ulrich Geske (GMD-FIRST Berlin) Michael Hanus (CAU Kiel) Herbert Kuchen (Univ. Muenster) Juan Jose Moreno Navarro (UP Madrid) Mario Rodriguez-Artalejo (UC Madrid) Dietmar Seipel (Univ. Wuerzburg) ---------------------------------------------------------------------- LOCAL ORGANIZING COMMITTEE Wolfgang Goerigk Michael Hanus Klaus Hoeppner Ulrike Pollakowski-Geuther Friedemann Simon Frank Steiner ----------------------------------------------------------------------

1 0

RE: Implict parameters and monomorphism
by Simon Peyton-Jones 03 May '01

03 May '01

| As far as what one would `expect', it's in the very nature of | dynamic binding that it makes the meaning of an expression | depend on its context. I for one would certainly not expect | that inlining a definition bound to such an | expression should preserve its meaning! Inlining changes the | context, so `of course' can change the meaning. So I strongly | prefer (B)! John: just to check, you do realise that (B) means a) That adding a type signature can change the dynamic semantics of the program. This would be the first and only occurrence of such behaviour. (For ordinary type classes, the monomorphism restriction will reject some programs that would otherwise be well typed; for implicit parameters, (B) will accept the program but with --- potentially ---- a different meaning.) b) That whether or not a definition is unconditionally inlinable at the source-language level cannot be determined by looking at the expression. You have to do something rather like effects analysis: look to see if it calls any function (transitively) that uses an implicit parameter. These seem like pretty dire properties. Are you sure it's worth it? Simon

3 2