- Haskell - Haskell.org

RE: literate scripts.
by Simon Marlow 06 Aug '03

06 Aug '03

> Ghc should not accept this code, because, no matter how the > unliterating > is achieved, it is illegal for a literal string to contain a > literal newline character. Known bug in GHC. In the testsuite, but unfortunately not documented. Cheers, Simon

1 0

literate scripts.
by Immanuel Litzroth 06 Aug '03

06 Aug '03

I have a small question relating to literate haskell programs that use the \begin{code} \end{code} style. Am I correct to assume that \end{code} inside a string should be recognized as being inside a string. The report seems to say this, but the unlit that is distributed with ghc doesn't grok this. Has anyone written an Unlit module in Haskell? Immanuel *************************************************************************** It makes me uncomfortable to see An English spinster of the middle class Describe the amorous effects of `brass', Reveal so frankly and with such sobriety The economic basis of society. W.H. Auden -- Immanuel Litzroth Software Development Engineer Enfocus Software Kleindokkaai 3-5 B-9000 Gent Belgium Voice: +32 9 269 23 90 Fax : +32 9 269 16 91 Email: Immanuell(a)enfocus.be web : www.enfocus.be ***************************************************************************

2 3

RE: Solution to the monomorphism restriction/implicit parameter problem
by Simon Peyton-Jones 05 Aug '03

05 Aug '03

| I just figured out why the monomorphism restriction interacts so weirdly | with implicit parameters, and how to fix it. I'm afraid that I have not read all of the recent exciting flood of messages carefully, but I do remember that the interaction of the monomorphism restriction with implicit parameters was the subject of a long debate some time ago. Indeed, it leads to strange things, as you have found. Below I reproduce a long comment from TcSimplify.lhs (one of GHC's modules) that describes the problem and GHC's solution. It explicitly points out that the currently-adopted solution means that inlining (beta reduction) is not always valid. This is undoubtedly a bad thing. The comment would be better enshrined in GHC's documentation. You say that "All implementations should be changed so that they do the right thing". If only we knew what the Right Thing is! I believe that your suggestion is * adopt solution (C) in the list below (always generalise implicit parameters) * but reject any program for which that would cause the implicit function to be called more than once Maybe that's a good plan, but if so it'd be better to apply it to all overloaded bindings. That is: abandon the monomorphism restriction altogether; instead always generalise every binding (whether function or non-function binding) but warn or reject the program if it seems that the implicit function might be called more than once. Simon Comments from TcSimplify Question 3: monomorphism ~~~~~~~~~~~~~~~~~~~~~~~~ There's a nasty corner case when the monomorphism restriction bites: z = (x::Int) + ?y The argument above suggests that we *must* generalise over the ?y parameter, to get z :: (?y::Int) => Int, but the monomorphism restriction says that we *must not*, giving z :: Int. Why does the momomorphism restriction say this? Because if you have let z = x + ?y in z+z you might not expect the addition to be done twice --- but it will if we follow the argument of Question 2 and generalise over ?y. Possible choices ~~~~~~~~~~~~~~~~ (A) Always generalise over implicit parameters Bindings that fall under the monomorphism restriction can't be generalised Consequences: * Inlining remains valid * No unexpected loss of sharing * But simple bindings like z = ?y + 1 will be rejected, unless you add an explicit type signature (to avoid the monomorphism restriction) z :: (?y::Int) => Int z = ?y + 1 This seems unacceptable (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. BOTTOM LINE: we choose (B) at present. See tcSimplifyRestricted

2 2

Re: The madness of implicit parameters: cured?
by Ashley Yakeley 05 Aug '03

05 Aug '03

At 2003-08-04 22:33, Ben Rudiak-Gould wrote: >This illustrates what you pointed out earlier, that the >program's semantics can be changed by adding explicit type signatures >which include implicitly-parameterized parameters. But wasn't avoiding this a design goal of your proposal? >> If it is valid, then this must be a valid reduction: >> >> ((\a -> ((a,\@x -> @x) {@x = 2})) (\@x -> @x),\@x -> @x) {@x = 1} >> ((\@x -> @x,\@x -> @x) {@x = 2},\@x -> @x) {@x = 1} > >Not unless you give an explicit type signature, no. So effectively your proposal is the same as the existing implicit parameter mechanism, except that the compiler is a bit stricter in certain cases where the types are ambiguous? -- Ashley Yakeley, Seattle WA

2 1

RE: Text I/O library proposal, first draft
by Hal Daume 05 Aug '03

05 Aug '03

this is true; however, it is likely that it would be much faster for me to read in word8s and parse them to Ints myself than to read in Chars (using the old libraries) and parse those to ints (I've done some experiments and the overhead for reading haskell Chars is very non-negligible). i'd like to take advantage of this new infrastructure, if possible... -- Hal Daume III | hdaume(a)isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume > -----Original Message----- > From: libraries-admin(a)haskell.org > [mailto:libraries-admin@haskell.org] On Behalf Of John Meacham > Sent: Thursday, July 31, 2003 4:36 PM > To: libraries(a)haskell.org; haskell(a)haskell.org > Subject: Re: Text I/O library proposal, first draft > > > presumably if you are doing random access on the file, it is > in a known > nonarbitrary text encoding (like utf8). in which case you can > read/access the file with the binary routines and just use the > appropriate text conversions to get data out. > John > > On Thu, Jul 31, 2003 at 03:55:44PM -0700, Hal Daume wrote: > > Hi Ben, > > > > > Bad things: > > > > > > * There's no way to implement fgetpos/fsetpos type > functionality, > > > because coders don't expose their internal state. (In > fact, there > > > would need to be a way to explicitly copy the state, > since it may > > > well include IORefs, Ptrs, etc.) Is this a serious problem? > > > > Yes! This is an enormously serious problem. At least for me. > > > > It's not a problem for writing files, but I really really > really need > > this functionality when reading files. Reason: I'm often > tooling around > > in very large (1gb or greater) files which happen to be > sorted on some > > sort of index and I need to do binary search in them. To > load all the > > file into Haskell or to do linear search is impossible. > > > > Other than that, I rather like the design. > > > > - Hal > > -- > > Haskell mailing list > > Haskell(a)haskell.org > > http://www.haskell.org/mailman/listinfo/haskell > > > > -- > -------------------------------------------------------------- > ------------- > John Meacham - California Institute of Technology, Alum. - > john(a)foo.net > -------------------------------------------------------------- > ------------- > _______________________________________________ > Libraries mailing list > Libraries(a)haskell.org > http://www.haskell.org/mailman/listinfo/libraries >

1 0

The madness of implicit parameters: cured?
by Ben Rudiak-Gould 05 Aug '03

05 Aug '03

When I first learned about implicit parameters I thought they were a great idea. The honeymoon ended about the time I wrote some code of the form "let ?foo = 123 in expr2", where expr2 used ?foo implicitly, and debugging eventually unearthed the fact that ?foo's implicit value was not being set to 123 in expr2. That was enough to scare me off of using implicit parameters permanently. More recently, I've realized that I really don't understand implicit parameters at all. They seemed simple enough at first, but when I look at an expression like f x = let g y = ?foo in g I realize that I have no idea what f's type should be. Is it (?foo :: c) => a -> b -> c or is it a -> ((?foo :: c) => b -> c) ? As far as I can tell, these are not the same type: you can distinguish between them by partially applying f with various different values of ?foo in the implicit environment. GHC tells me that f has the former type, but I still have no idea why: is it because g has an implicit ?foo parameter and f implicitly applies its own ?foo to g before returning it? Why would it do that? Or is it because ?foo is here interpreted as referring to an implicit parameter bound in the call of f, instead of in g? That doesn't make sense either. The final straw was: Prelude> let ?x = 1 in let g = ?x in let ?x = 2 in g 1 Prelude> let ?x = 1 in let g () = ?x in let ?x = 2 in g () 2 This is insanity. I can't possibly use a language feature which behaves in such a non-orthogonal way. Now the interesting part: I think I've managed to fix these problems. I'm afraid that my solution will turn out to be just as unimplementable as my original file I/O proposal, and that's very likely in this case since I'm far from grokking Haskell's type system. So I'm going to present my idea and let the gurus on this list tell me where I went wrong. Here we go. First, discard the current implicit-parameter scheme entirely. (I'll eventually build up to something very similar.) Now introduce the idea of "explicit named parameters" to Haskell. This requires three extensions: a new kind of abstraction, a new kind of application, and a way of representing the resulting types. The abstraction could be done with a new lambda form, but instead I'll use a special prefix on identifiers which are to be considered named parameters, namely the character #. The new application form will be [F] { #x = [G] } where [F] and [G] are expressions. [F] must evaluate to a function with an explicit named parameter #x. The type notation for a named parameter will be (#name :: type). They can appear only on the left side of a ->. Named parameters can only be passed by name, so their order relative to positional parameters and each other doesn't matter; therefore we may as well "bubble them up" to the head of the list of arguments. In fact, we could put them in the context with the type classes, but I won't do so. Examples: cons :: (#elem :: a) -> (#list :: [a]) -> [a] cons #elem #list = #elem : #list cons { #elem = 'h', #list = "ello" } -- legal cons 'h' "ello" -- illegal: named params must be passed by name cons { #list = "ello" } -- legal, has type (#elem :: Char) -> String cons { #list = "ello", #elem = 'h' } -- legal cons { #list = "ello" } { #elem = 'h' } -- legal append :: (#right :: [a]) -> [a] -> [a] append left #right = ... -- named args gravitate left Now introduce the idea of "auto-lifted named parameters". I'll distinguish these from ordinary named parameters by using an @ prefix instead of #. These are exactly the same as ordinary named parameters except that if they appear in the type on the right hand side of an application node, they are implicitly lifted to the whole node. For example, if [F] has an auto-lifted parameter @p, and [G] has auto-lifted parameters @p and @q, then [F][G] is implicitly converted to something like \@p @q -> [F] { @p = @p } ( [G] { @p = @p, @q = @q } ). Finally, introduce the following syntax: * As an expression, ?x is short for \@x -> @x. * On the left hand side of the = sign in a named application, ?x is the same as @x. * For backward compatibility, "let ?x = [E] in [F]" should be treated as equivalent to "[F] { ?x = [E] }". Now we have something almost the same as the current implicit-parameter system, except that it behaves in a much safer and saner way. For example, looking at the confusing expressions from the beginning again: f x = let g y = ?foo in g This obviously has type (?foo :: c) -> a -> b -> c. It doesn't matter where the ?foo parameter appears in the type because it will always be referred to explicitly, by name, exactly once in each call of f. let ?x = 1 in let g = ?x in let ?x = 2 in g This reduces as follows: let ?x = 1 in let g = ?x in let ?x = 2 in g ( let g = \@x -> @x in g { @x = 2 } ) { @x = 1 } (\@x -> @x) { @x = 2 } { @x = 1 } 2 { @x = 1 } At this point we get a type error, as we should: a let binding of an implicit parameter that's never used is almost certainly a coding error. let ?x = 1 in let g () = ?x in let ?x = 2 in g () Reduces in exactly the same way as the previous case, with the same result. Again, this is as is should be. Why are the semantics so much clearer? I think the fundamental problem with the existing semantics is the presence of an implicit parameter environment, from which values are scooped and plugged into functions at hard-to-predict times. By substituting a notation which clearly means "I want this implicit parameter of this function bound to this value right now, and if you can't do it I want a static type error", we avoid this ambiguity. More thoughts, assuming this all pans out (knocking on wood): * Explicit named parameters seem like a useful idea too. Maybe they should be added to Haskell. * We should really, really drop the "let ?x" form and switch to the record-update notation. In "( let g = ?x in g { ?x = 2 } ) { ?x = 1 }" it's obvious what's going to happen and what the result will be, but in "let ?x = 1 in let g = ?x in let ?x = 2 in g" it's very unclear, even though, under the translation above, these two forms are equivalent. * I think it may be possible to extend this to provide default values for named parameters, which would be really really cool (no more separate foo and fooBy functions). -- Ben

4 14

Re: The madness of implicit parameters: cured?
by Ashley Yakeley 05 Aug '03

05 Aug '03

At 2003-08-04 20:00, Ben Rudiak-Gould wrote: >This is a different lambda calculus, with a different beta rule. You can >see the same effect in the type inference rules for implicit parameters: >If f has type Int -> String and ?x has type (?x :: Int) => Int, then f ?x >has type (?x :: Int) => String, i.e. the implicit ?x parameter is lifted >out of the RHS to become a parameter of the whole application node. This >rule is what makes implicit parameters implicit. Ah. Actually I think the beta rule is unchanged with Haskell's implicit parameters. Consider: x :: (?x :: Int) => Int f :: Int -> String f :: ((?x :: Int) => Int) -> ((?x :: Int) => String) -- specialisation f x :: (?x :: Int) => String -- apply beta rule >As you pointed out, this reduction behavior depends on f's type, so this >is necessarily a typed lambda calculus. But that's okay because Haskell is >statically typed. So is this valid or not? b :: (?x :: Int) => Int b = \@x -> @x f :: ((?x :: Int) => Int) -> (Int,Int) f = \a -> ((a,\@x -> @x) {@x = 2}) f b :: (Int,Int) f b = ((b,\@x -> @x) {@x = 2}) = ((\@x -> @x,\@x -> @x) {@x = 2}) If it is valid, then this must be a valid reduction: ((\a -> ((a,\@x -> @x) {@x = 2})) (\@x -> @x),\@x -> @x) {@x = 1} ((\@x -> @x,\@x -> @x) {@x = 2},\@x -> @x) {@x = 1} -- Ashley Yakeley, Seattle WA

2 1

Pure functional TypeRep [Was: Existentials...]
by oleg＠pobox.com 05 Aug '03

05 Aug '03

This message shows how to map _types_ to integers at compile time -- and then extend this facility to run-time so it can be used with existentially-quantified types. It is statically guaranteed that different types receive different integer labels. Unlike TyCons of Dynamics, our mapping does NOT rely on unsafePerformIO. We use the typechecker itself to compare types. It seems our typemap can also be used for _safe_ casts, in particular, for casting away the existential blemish. This message was inspired by Amr Sabry's problem on existentials. Unlike Hal Daume's solution posted here earlier, we do not use Dynamics nor GMap -- therefore, we completely avoid unsafePerformIO and unsafeCoerce. Our solution is purely functional and assuredly type-safe (to the extent the typechecker can be trusted). Extensions used: -fglasgow-exts -fallow-undecidable-instances -fallow-overlapping-instances First, the compile-time mapping from types to integers. Polytypic list: > data Nil t r = Nil > data Cons t r = Cons t r > > class PList ntype vtype cdrtype where > cdr:: ntype vtype cdrtype -> cdrtype > empty:: ntype vtype cdrtype -> Bool > value:: ntype vtype cdrtype -> vtype > > instance PList Nil vtype cdrtype where > empty = const True > > instance (PList n v r) => PList Cons v' (n v r) where > empty = const False > value (Cons v r) = v > cdr (Cons v r) = r and the finite map from types to integers > class TypeSeq t s where > type_index:: t -> s -> Int > > instance (PList Cons t r) => TypeSeq t (Cons t r) where > type_index _ _ = 0 > > instance (PList Cons t' r', TypeSeq t r') => TypeSeq t (Cons t' r') where > type_index v s = 1 + (type_index v $ cdr s) Let us build some finite map > init_typeseq = Cons (undefined::Char) $ > Cons (undefined::Int) $ > Cons (undefined::Bool) $ > Cons (undefined::String) $ > Cons (undefined::Maybe Char) $ > Nil A typeseq maps a type to an integer -- which is the type's position in the polytypic list. We are satisfied with the first occurrence of the type in the list. It is plain that a typeseq maps different types to different integers. Let us see how it works: -- *Main> type_index True init_typeseq -- 2 -- *Main> type_index 'a' init_typeseq -- 0 -- *Main> type_index "a" init_typeseq -- 3 -- *Main> type_index (1::Int) init_typeseq -- 1 -- *Main> type_index (Just 'a') init_typeseq -- 4 -- *Main> type_index (Just True) init_typeseq -- <interactive>:1: -- No instance for (TypeSeq (Maybe Bool) (Nil t r)) -- arising from use of `type_index' at <interactive>:1 -- In the definition of `it': type_index (Just True) init_typeseq We call this mapping compile-time because the translation from a type to the corresponding encoding (1+1+...1) is done at compile time, when the appropriate instance of the TypeSeq class is chosen. A sufficiently smart compiler can just as well fold the constant expression (1+1...+1) down to a single integer. Also, errors in the translation are reported at compile-time. However, to apply the mapping to existential types, we need to extend the former to run-time. > class TypeRep t where > tr_index:: t -> Int > > -- All of the following are almost the same. > -- The Template Haskell can really help us here > instance TypeRep Char where > tr_index x = type_index x init_typeseq > > instance TypeRep Int where > tr_index x = type_index x init_typeseq > > instance TypeRep Bool where > tr_index x = type_index x init_typeseq > > instance TypeRep String where > tr_index x = type_index x init_typeseq > > instance TypeRep (Maybe Char) where > tr_index x = type_index x init_typeseq Now, Amr Sabry's Problem > data F a b = > forall c. (TypeRep c) => PushF (a -> c) (F c b) > | Bottom (a -> b) > > f1 :: Char -> Bool > f1 'a' = True > f1 _ = False > > f2 :: Bool -> String > f2 True = "true" > f2 False = "false" > > f3 :: String -> Int > f3 = length > > fs = PushF f1 (PushF f2 (PushF f3 (Bottom id))) First, we make fs an instance of class Show. It is jolly convenient. > data HF = forall a b. (TypeRep a,TypeRep b) => HF (F a b) > show_fn_type (g::(a->b)) > = "(" ++ (show (tr_index (undefined::a))) ++ > "->"++(show (tr_index (undefined::b))) ++ ")" > > instance (TypeRep a, TypeRep b) => Show (F a b) where > show = show . hsf_to_lst . HF > where > hsf_to_lst (HF (Bottom g)) = [show_fn_type g] > hsf_to_lst (HF (PushF g next)) = (show_fn_type g):(hsf_to_lst$HF next) Now, Amr Sabry's question: ] Is it possible to write a function ] f :: F a b -> T c -> F c b ] where (T c) is some type for values of type 'c' or values representing ] the type 'c' or whatever is appropriate. Thus if given the ] representation of Bool, the function should return: ] PushF f2 (PushF f3 (Bottom id)) ] and if given the representation of String the function should return ] PushF f3 (Bottom id) ] and so on. First, we prepend to the given F a b structure the identity composition. We see the meaning of it below. > f fs v = f' (PushF id fs) v > f':: (TypeRep c) => (F a b) -> c -> F a b > f' here@(PushF g next) (v::tv) = > if tr_index v == tr_index (g undefined) > then here > else case next of > PushF g1 next' -> f' (PushF (g1.g) next') v > Bottom g1 -> f' (Bottom (g1.g)) v The function f' takes a data structure F a b and a value of type c and returns another data structure F a b, but of a different structure PushF g next here 'next' has the type F c b -- which is the answer to Amr Sambry's question. The function g::a->c is a composition of all previously occurring functions. This is a neat "side-effect" of the function f': we partially compose the given F a b structure up to the given type. Let us see how it works: *Main> fs ["(0->2)","(2->3)","(3->1)","(1->1)"] *Main> f fs 'a' ["(0->0)","(0->2)","(2->3)","(3->1)","(1->1)"] *Main> f fs True ["(0->2)","(2->3)","(3->1)","(1->1)"] *Main> f fs "a" ["(0->3)","(3->1)","(1->1)"] *Main> f fs (1::Int) ["(0->1)","(1->1)"] Because f is capable of producing any partial composition, it can do the full composition just as easily: > flatten:: (TypeRep a, TypeRep b) => F a b -> (a -> b) > flatten fs :: (a->b) > = case f fs (undefined::b) of > PushF g (Bottom g1) -> g1.g And it indeed works: *Main> flatten fs 'a' 4 -- the length of the word true *Main> flatten fs 'b' 5 -- the length of the word false Again, I can't seem to write any Haskell code that doesn't explicitly use undefined.

4 8

Re: The madness of implicit parameters: cured?
by Ashley Yakeley 05 Aug '03

05 Aug '03

At 2003-08-04 18:19, Ben Rudiak-Gould wrote: > \@x -> ((\a -> ((a,\@x -> @x) {@x = 2})) @x) > >If we next apply (\a -> ...) to @x, something interesting happens: we >have to rename to avoid variable capture. I don't see why, isn't this much the same as ordinary names? (\a -> ((\a -> a) 1,a)) 2 ((\a -> a) 1,2) (1,2) -- Ashley Yakeley, Seattle WA

1 0

Re: The madness of implicit parameters: cured?
by Ashley Yakeley 05 Aug '03

05 Aug '03

At 2003-08-04 18:19, Ben Rudiak-Gould wrote: >> ((\a -> ((a,\@x -> @x) {@x = 2})) (\@x -> @x),\@x -> @x) {@x = 1} > ^^^ >> ((\@x -> @x,\@x -> @x) {@x = 2},\@x -> @x) {@x = 1} > >This reduction is incorrect. It's a simple beta-reduction, it must be correct. b :: (?x :: Int) => Int b = \@x -> @x f :: ((?x :: Int) => Int) -> (Int,Int) f = \a -> ((a,\@x -> @x) {@x = 2}) f b :: (Int,Int) f b = ((b,\@x -> @x) {@x = 2}) -- Ashley Yakeley, Seattle WA

2 1