- Haskell-prime - Haskell.org

Re: The dreaded M-R
by John Hughes 30 Jan '06

30 Jan '06

it would also be possible to require the compiler 'memoize' all top level bindings on their type parameter. then the problem goes away, but at the cost of hiding some machinery under the hood. however the type analysis pass mentioned above would often be able to discard of this 'under the hood' memoization and. We discussed this idea when Haskell was first designed. The trouble is, there's an awful interaction with space leaks. Imagine you have a binding let x = ...e1... in ...e2... where e1 contains pointers to some large structure, and then somewhere in e2 you need to drop those pointers. You write x `seq` ... at the place where you want to drop the pointers, right? (Assuming the pointers are no longer referred to from x's value). Wrong! If x is overloaded, then you've only forced the evaluation of *one instance* of x, and e1, together with the structures it points to, have to be retained in case you ever evaluate a *different* instance of x in the future! Memooising x on its type makes no difference to this: you have to retain e1 until every possible instance of x has been evaluated. If there's a fixed finite number of possibilities then this might be possible, if awkward ((x::Integer)`seq` (x::Float)`seq`...), but if there are infinitely many possible instances then you're screwed. So if it is to be *possible* to fix space leaks, then memoisation is not a good alternative to shared bindings. John

1 0

Removal candidates in patterns
by Olaf Chitil 29 Jan '06

29 Jan '06

I am very please to see on the Wiki also a list of removal candidates and that these include n+k patterns and ~ patterns. I'd like to add one pattern to this list of removal candiates: k patterns, that is, numeric literals. Why do I want to get rid of these three patterns? Because all three caused me no end of trouble when implementing the program transformation of the Haskell tracer Hat. Hat actually still doesn't handle nested ~ patterns. Why are these patterns so hard to implement for Hat? Surely the Haskell report gives a translation into simple core Haskell. Well, Hat does not use this translation because it does not want to be an inefficient pattern matcher (leave that job to the compiler) but produce a trace of the Haskell program as it is written. However, both n+k and k patterns cause calls of functions ( (-), (==) etc) that Hat has to record in its trace. Also ~ patterns do not fit the simple rewriting semantics of the Hat trace and hence have to be recorded specially. While in simple cases that occur in practice it is pretty straightforward to remove n+k, k and ~ patterns from a larger pattern while keeping the rest of the larger pattern intact, in the general case this is incredibly hard. Iff n+k patterns are removed, there is little good use for k patterns either. Since the introduction of monadic IO the ~ pattern is hardly used in practice either. In all the simple cases that these three are currently used in practice, it is easy for the programmer to define their function in an alternative way. So get rid of these three and pattern matching becomes so much more simple. Ciao, Olaf

6 5

module system/namespaces: separate with/use, allow local "use"
by Johannes Waldmann 29 Jan '06

29 Jan '06

With the module system, we should make a distinction between declaring (1) that we want to use a module (2) how to bring the module's names into scope E. g. in Ada, there is "with" and "use", and "use" can be local, see also http://www.dcs.gla.ac.uk/mail-www/haskell/msg00991.html (Similar thing is "using namespace" in C++) (in Java, "import" does really mean "use", since everything is "withed", but that "use" then has to be global - presumably for the same reason that Ada-with must be at the start of the module: for maintenance, dependence on other modules should be clearly visible). I think the current Haskell definition (import .. qualified .. hiding) is kludgy. Especially "hiding": that sounds similar in spirit to a subroutine call of the kind "call function f but don't execute its fourth statement". (PS: now it's enough kidneys from me) -- -- Johannes Waldmann -- Tel/Fax (0341) 3076 6479/80 -- ---- http://www.imn.htwk-leipzig.de/~waldmann/ -------

2 1

Re: more flexible partial application
by John Hughes 29 Jan '06

29 Jan '06

>On 1/23/06, Sebastian Sylvan <sebastian.sylvan(a)gmail.com> wrote: > > >>Are there any subtle reasons for why something like the following >>couldn't be allowed? >> >> >> >> >>>foo x y z w = ... >>>bar x w = foo x _ _ w >>> >>> >>I.e. a more flexible version of partial application. This would be >>translated too >> >> >> >>>bar x w = \y z -> foo x y z w >>> >>> >>I.e a function which takes the "_" parameters in the same order they >>were encountered in the function application. >> >> >> I'd be against this--its semantics isn't clear enough to me. For example, I usually assume id e = e, for any e, but id (f _ x) y = id (\y->f y x) y = f y x /= f _ x y = \z -> f z x y Or would (f _ x) y and f _ x y maybe be different? That would fix the problem above, while introducing another. Please, no! John

6 8

RE: ~ patterns
by Simon Peyton-Jones 27 Jan '06

27 Jan '06

| Actually, I think it's a much bigger wart that pattern matching in let | and where is lazy, and everywhere else is strict, than that we have an | operator ~ on patterns with a clean compositional semantics. Way back in But ! patterns would restore what you want let !(x,y) = e in ... Arguably, it's non-uniform, but at least the strict version would be much more convenient than switching to case. Simon

3 2

RE: The dreaded M-R
by Simon Marlow 27 Jan '06

27 Jan '06

On 27 January 2006 10:54, Simon Peyton-Jones wrote: >>> How about an even simpler solution: >>> >>> *All* pattern and variable bindings are monomorphic unless a type >>> signature is given. >>> > > >> Now that IS an interesting idea. The more I think about it, the more >> I like it. > > I like it too. But be aware that a top-level definition > > reverse = foldr (\x ys -> ys ++ [x]) [] > > would get the inferred type > > [()] -> [()] > > because it'd be monomorphic, and completely un constrained type > variables are defaulted to (), in GHC at least. This only becomes an issue if the binder is exported, because defaulting doesn't happen until the complete module has been typechecked. So in that case, probably the least surprising behaviour is for it to be an static error to export a binding with unresolved type variables, after defaulting has been applied. [ oops, hit send by mistake.. ] I was just going to point out that something similar happens in GHCi: Prelude> f <- return reverse Prelude> :t f f :: [()] -> [()] Cheers, Simon

1 0

RE: The dreaded M-R
by Simon Marlow 27 Jan '06

27 Jan '06

On 27 January 2006 10:54, Simon Peyton-Jones wrote: >>> How about an even simpler solution: >>> >>> *All* pattern and variable bindings are monomorphic unless a type >>> signature is given. >>> > > >> Now that IS an interesting idea. The more I think about it, the more >> I like it. > > I like it too. But be aware that a top-level definition > > reverse = foldr (\x ys -> ys ++ [x]) [] > > would get the inferred type > > [()] -> [()] > > because it'd be monomorphic, and completely un constrained type > variables are defaulted to (), in GHC at least. This only becomes an issue if the binder is exported, because defaulting doesn't happen until the complete module has been typechecked. So in that case, probably the least surprising behaviour is for it to be an static error to export a binding with unresolved type variables, after defaulting has been applied. incedentally, that's the type you get in GHCi

1 0

RE: The dreaded M-R
by Simon Peyton-Jones 27 Jan '06

27 Jan '06

| >How about an even simpler solution: | > | > *All* pattern and variable bindings are monomorphic unless a type | > signature is given. | > | Now that IS an interesting idea. The more I think about it, the more I like it. I like it too. But be aware that a top-level definition reverse = foldr (\x ys -> ys ++ [x]) [] would get the inferred type [()] -> [()] because it'd be monomorphic, and completely un constrained type variables are defaulted to (), in GHC at least. Simon

1 0

RE: The dreaded M-R
by Simon Marlow 26 Jan '06

26 Jan '06

On 26 January 2006 09:59, John Hughes wrote: > The solution I favour is simply to use *different syntax* for the two > forms of binding, so that a definition is monomorphic, and computed > at most once, if it uses the monomorphic binding operator, and > polymorphic/overloaded, computed at each use, if it uses the other. > Whether it's a function definition or not is irrelevant, as is whether > or not it carries a type signature. > > The trick is finding good syntax. I suggest = for bind-by-name, and > := for bind-by-need. The reasoning for the proposal makes complete sense to me, but I don't feel the proposed solution strikes the right balance. The MR is a subtle point that we don't want to have to burden newcomers to the language with, but having two forms of binding is a fundamental part of the language design that would surely crop up early on the Haskell learning curve. John - how do you envisage teaching this? I wonder if there's an alternative solution along these lines: - We use ParialTypeSignatures to make bindings monomorphic: http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/PartialTyp eSigs eg. x :: _ x = (+1) (incedentally until recently it was possible to do this in GHC using scoped type variables, but the change in the semantics of scoped type variables has removed that possibility). - we make it a static error for a variable bound by a simple pattern binding ("x = e") to be overloaded, unless a type signature is given. The error message would explain the problem, and how to fix it. Alternatively, we make it a strong warning. It seems to me that the partial type signatures extension provides a lot of bang for the buck - it gives us a way out of the MR in addition to partial type signatures. I'm not sure what to do about non-simple pattern bindings, though. Cheers, Simon

4 3

Re: Haskell-prime Digest, Vol 1, Issue 4
by John Hughes 26 Jan '06

26 Jan '06

Ross Paterson wrote: > I suggest = for bind-by-name, and > := for bind-by-need. > ... You're proposing that the =/:= distinction both decides whether constrained type variables are monomorphic and whether the binding should be implemented using sharing. If it only did the former (and the expectation was that all pattern bindings with unconstrained types used sharing), then existing legal programs would still be legal, and the examples that currently trip over the MR would be legal but inefficient. (Also, what does the shared/unshared distinction mean for functions?) Not just constrained type variables. All type variables. Because changes in the program elsewhere can easily change the status of a type variable from unconstrained to constrained, thus triggering monomorphism unexpectedly--that was the point of my comment about introducing an equality test in a function called from the definition. Changing the status of a type variable should not change the way it is treated by any replacement for the M-R. I don't quite follow what you're suggesting above. The main point of a =/:= distinction is to distinguish between sharing and non-sharing, isn't it? And sharing means you have to be monomorphic, at least for constrained type variables, and (by the argument above) thus for unconstrained ones too. How can sharing/unsharing and monomorphic/overloaded be separated? I'd really like to avoid ANOTHER rule that "guesses" what method to use, based on the form of the definition (your reference to pattern bindings above). That leads to surprises for the programmer, at least the less-than-expert one, when a definition is replaced by something that LOOKS equivalent, but type-checking or sharing suddenly behaves differently. Much preferable is a simple and obvious rule: = means unshared and polymorphic, := means shared and monomorphic. Shared/unshared doesn't matter for function definitions, but monomorphic/polymorphic can still be important. There is an interaction with implicit parameters here--which I suppose might make it into Haskell'. A := definition says: resolve all overloading here. Thus, if there is an implicit parameter in the RHS of such a definition, then it refers to the instance of that parameter in scope at the point of definition. With a = definition, it refers to the instance in scope at the point of use. This is an important distinction whether you're defining a function or anything else. This is discussed in my paper on Global Variables in Haskell, which suggested using implicit parameters to refer to global variables, rather than an unsafe unsafePerformIO applied to a newIORef. What if one has mutually recursive bindings, some using = and some := ? Does monomorphism kick in if some of the variables in a binding group use :=, or would we just require that all bindings in the same group use the same binder? (At first I couldn't see why one would ever use := with function bindings, but perhaps that's the reason.) I don't think there's really a problem in allowing a mixture of = and := in the same mutually recursive group, even if it could be quite confusing to do so! = just means that type variables and dictionaries should be abstracted, and that the binding should be by-name... let's assume that we're translating to System F, and we always insert at least a \()-> on such bindings in the translation. := means, on the other hand, that type variables and dictionaries are not abstracted, and so must be inherited from an enclosing scope. So in a group of the form f = ...g... g := ...f... then any type variables in the definition of g must refer to the enclosing scope, which means that they cannot be generalised in the definition of f either (since they are "free in the context"). But if there are type variables in the definition of f which do NOT occur in the type of g, then they can be generalised as usual. Meanwhile f can be bound by name, and g by need--there's no difficulty with that. This would be an odd thing to do, but I think it makes perfect sense. (I wonder what happens today, if you write mutually recursive definitions where the M-R applies to some, but not others?) Of course, polymorphic recursion would REQUIRE an = binding, but that shouldn't surprise anybody. John

2 1