February 2002 - Haskell-Cafe

Re: Monadic Call/CC?
by Ashley Yakeley 22 Feb '02

22 Feb '02

>Given this: > > class (Monad m) => PeirceMonad m where > { > peirceM :: ((a -> m b) -> m a) -> m a; > }; > >...which Monads can be made PeirceMonads? Here's one: data ContMonad p a = MkContMonad ((a -> p) -> p); unContMonad (MkContMonad app) = app; instance Monad (ContMonad p) where { return a = MkContMonad (\cont -> cont a); (MkContMonad ma) >>= bf = MkContMonad (\cont -> ma (\a -> unContMonad (bf a) cont)); }; instance PeirceMonad m where { peirceM foo = MkContMonad (\cont -> unContMonad (foo (\a -> MkContMonad (\_ -> (cont a)))) cont); }; doContMonad :: ContMonad p p -> p; doContMonad cm = unContMonad cm id; test1 = doContMonad (peirceM (\continuation -> do { continuation 1; continuation 2; continuation 3; })); -- returns 1 Now here's the interesting thing. The usual way to represent "real-world" functions (i.e. with side-effects, or changing the world) from a to b is to define a special _type constructor_, 'IO', and define the function as 'a -> IO b'. But an alternative, would have been to define a special _type_, Action, and define the function as 'a -> (b -> Action) -> Action'. And then your 'main' function has type 'Action'. Nor do we have to declare special >>= and return functions as we do for IO. Here's how it's equivalent: type Action = IO (); type ActionMonad = ContMonad Action; doActionMonad :: ActionMonad () -> Action; doActionMonad cm = unContMonad cm return; liftIO :: IO a -> ActionMonad a; liftIO ioa = MkContMonad (\cont -> ioa >>= cont); ...and note that we get Peirce continuations for free: peirce foo cont = foo (\a _ -> (cont a)) cont; -- constructors removed -- Ashley Yakeley, Seattle WA

2 1

Re: Monadic Call/CC?
by Ashley Yakeley 22 Feb '02

22 Feb '02

At 2002-02-21 19:36, I wrote: > And then your 'main' function has type 'Action'. Sorry, And then your 'main' function has type 'Action -> Action'. -- Ashley Yakeley, Seattle WA

1 0

Re: Monadic Call/CC?
by Ashley Yakeley 21 Feb '02

21 Feb '02

At 2002-02-20 22:15, I wrote (on the Haskell list): >Haskell? Given this: > > class (Monad m) => PeirceMonad m where > { > peirceM :: ((a -> m b) -> m a) -> m a; > }; > >...which Monads can be made PeirceMonads? This is untested, but... instance PeirceMonad IO where { peirceM foo = do { ref <- newIORef Nothing; catch (foo (\a -> do { writeIORef ref (Just a); ioError (userError "break"); })) (\ex -> do { ma <- readIORef ref; case ma of { Just a -> return a; _ -> ioError ex; }; }) } }; So you can do it if you have refs and throw/catch for your monad. I think. -- Ashley Yakeley, Seattle WA

2 1

RE: Survival of generic-classes in ghc
by Jan-Willem Maessen 21 Feb '02

21 Feb '02

* Language philosophers who are skimming this discussion will want to take a look at #### below. Simon PJ writes: > One thing that is slowing me down is a design uncertainty: how to > deal cleanly with constructors. To write read, show, etc, one needs > access to the constructor name, fixity etc. We dance around that a > little in the paper. I'm thinking of this design: ... > -- Con is part of the Generics library, like 1, :*:, :+: > newtype Con c a = Con a > > class ConCls c where > name :: c -> String > arity :: c -> Arity > ..etc.. > > data NilT -- Phantom types > data ConsT -- one per constructor > > instance ConCls NilT where > name _ = "Nil" > ...etc... > > instance ConCls ConsT wher > name _ = "Cons" > ...etc... But you're going to have to keep those ConCls dictionaries somewhere, which means either: 1) The type Con should existentially quantify over c: < data Con a = forall c. (ConCls c) => Con a [I haven't checked that this is even legal anywhere, but you get the idea] 2) Any function which needs the type "c" must carry around a dictionary for *each* constructor in the type. I'm not quite sure how to work the typing of the code generic functions in this regime, though I'm sure it could somehow be managed. As long as we're reifying everything in sight, why not simplify the design problem and reify the constructor dictionaries? >From my own strawman experiments (this is old code): > data Constructor t = Constructor CI !t > > data CI = CI Bool String Int [String] [Bool] deriving (Eq) > -- Op-ness, constructor, fixity, field names, strictnesses of fields We could do something similar for fields, of course. There need only be one copy of this info for each data constructor (and field); it's easy for the compiler to share these. The type CI is effectively a representation of the dictionary for ConCls. The "Constructor" type the works just like the existentially quantified example (1). The drawback? We need to store the constructor info CI in every reified constructor. My suspicion is this will not matter much in practice. Compiling generics should be done with one of two sets of assumptions: * Generics are a mechanism of convenience. If you want your code to go fast, you should write the code longhand (possibly using an overlapping instance for an otherwise generic function/class). In this case, the extra overhead of the constructor info is likely to be a drop in the bucket. * Generics should be specialized at the types at which they are used. This might be accomplished by careful inlining of reification functions into the bodies of generic methods (or vice versa). In this case "Constructor" should vanish. ####################### On a broader philosophical note: I'm disturbed by the idea of adding explicit type application and the like to Haskell. Haskell language extensions are rapidly becoming a riotous array of confusing syntax and twisty semantic corners. From an experimenter's standpoint, this isn't so bad. However, many of these extensions are incredibly useful, and there's a lot of code relying upon them. This creates pressure (from both users and implementors) to immortalize the existing, grubby implementations. The result? An incomprehensible, byzantine language. For example, we now have multiparameter type classes (useful) with functional dependencies (addressing a vital problem with multiparameter constraint solving). Now Simon is wants explicit type application, kind annotations, and the like. There are some things Haskell does very well---algebraic types and pattern matching are cleaner and more pleasant to use then in ML, and the class system has proven to be Haskell's most brilliant distinguishing feature. I'd like to see solutions to some of the current problems that build on these strengths. I'm not sure if it's possible to get a type language based on functions and pattern matching in the face of type inference. Cayenne makes it clear that one can write type-level code very naturally when the type language and the value language work the same way. Similarly, I observe that: * Views = coercion methods + implicitly-inserted coercions + deforestation * Generics = reification methods + functions become methods + implicitly-inserted reification + deforestation The two lists are pretty similar, and it might be worth trying to unify the efforts in some fashion---possibly by breaking down the functionality into simple pieces. Here are some possibilities: * Come up with a coherent story on implicitly-inserted coercions. Ideally fromInteger and fromRational would just be specific cases of this coherent story. (The current story is nice and coherent: if it's a numeric constant, there's a coercion, otherwise there isn't.) * Allow patterns to match at multiple types, if those types match particular constraints (such as coercability). These two together might well be enough to give you views. * Give the deriving mechanism a language-level reading. Allow "deriving"-like clauses outside the context of type declarations. * Give some way to declare "closure" of a class. This should be done with an eye on abstraction barriers. Perhaps "closed" classes may still be derived (by newtypes, or using the mechanism for generics). * Make generic functions look like closed classes; possibly this means allowing the programmer to write instances as part of the class declaration. * Perhaps Haskell needs a universal class. This class would provide the reification methods for all [boxed?] data types, and might be a place for the implementation to hide (e.g.) type-based GC methods or specialized versions of seq. I'm hoping something along these lines is enough for single-parameter generics at least. Much of this work already exists in fragmentary form. However, in many cases it's part of attempts at larger mechanisms. For example, "views" proposals have suggested using distinguished "view types", and adding coercions when patterns mention the constructor of a view type. "Closed" classes were mentioned in the paper on instance resolution at PoPL last month. And of course there's lots of good work on generics, the big problem being that the efforts have become scattershot and still doesn't seem to fit the rest of the language nicely. It's time to reduce the useful mechanisms to their essentials. -Jan-Willem Maessen Eager Haskell project

1 0

RE: Survival of generic-classes in ghc
by Simon Peyton-Jones 21 Feb '02

21 Feb '02

| and I know from testing earlier versions that the | generic-classes support was pretty buggy. Is there any hope | of a revival? Does it already work in CVS? I suspect it will | rot away if nobody works on it. | | Any comments from the implementors - does the idea "fit well" | with ghc? Is it a lot of work to make it more stable? No, it should not be a lot of work to revive, and I will do it. Keep bugging me until I do. One thing that is slowing me down is a design uncertainty: how to deal cleanly with constructors. To write read, show, etc, one needs access to the constructor name, fixity etc. We dance around that a little in the paper. I'm thinking of this design: -- An example data type data List a = Nil | Cons a (List a) -- The "ring" type derived from it -- Note the Con wrapped around the constructors data ListO a = Con NilT 1 :+: Con ConsT (a :*: List a) -- Con is part of the Generics library, like 1, :*:, :+: newtype Con c a = Con a class ConCls c where name :: c -> String arity :: c -> Arity ..etc.. data NilT -- Phantom types data ConsT -- one per constructor instance ConCls NilT where name _ = "Nil" ...etc... instance ConCls ConsT wher name _ = "Cons" ...etc... Now you can write class Show a where show :: a -> String show {| Con c t |} (Con x) = (name (undefined::c)) ++ show x ...etc.. Note the "undefined::c"; it is really just a type argument to "name", so that we get the string for the right constructor. It's a bit clunky, though. Another possiblity would be to make the ConCls class look like this class ConCls c where name :: String arity :: Int ...etc... Now we'd have to give an explicit type argument at the call site: show {| Constr c t |} (Con x) = (name {| c |}) ++ show x I quite like the thought of being able to supply explicit type arguments.... but I don't konw how to speak about the order of type parameters. What order does map takes its two type parameters in? Another question is whether we need an indication that we have reached a field of the constructor. Should we have: data ListO a = Con NilT (Field 1) :+: Con ConsT (Field a :*: (Field List a)) newtype Field a = Field a Without this, it's hard to write a generic function to count the number of fields of the data type. But in general, one might want to know when making the transition from "this" type to the argument types of the constructors. I think that the main reason I'm not making much progress is that I don't know what design choices to make. I'd be glad to discuss it with interested parties. Simon

2 1

Re: a universal printer for Haskell?
by Bernard James POPE 20 Feb '02

20 Feb '02

Hi all, This thread started with the consideration of a means (hack?) to implement a generic printer in Haskell. It has moved to the bigger issue of Meta programming, in particular reflection. I think this is a topic worthy of consideration, and something we don't seem to talk much about in these groups. > Ashley Yakeley writes: > What I would hate to see is widespread use of reflection in general > programs. It rather seems to miss the point of Haskell's type system. I think the point of Haskell's type system varies depending on who you ask. The rules may be fixed to a certain degree in Haskell 98, but future versions of the language are free to change them. Meta programming is made more difficult when you have a strong static type system, no doubt. But is that a problem of meta programming or of the type system? This is a matter of opinion. Systems such as Meta ML [1], show that the two can be made compatible. I must admit that I haven't used Meta ML, so I'm not in a position to evaluate it, although it does make for some interesting research. My point is that there are some things that can't easily be expressed in current Haskell (like generic printing) that are useful and might be aided by meta-programming technology. The interesting question is can it be done in a way that preserves whatever we want from the type system: safety, security, efficiency, error detection ... > And I don't want other people peeking inside my types at run-time. There are numerous ways to provide security for your data types. You can specifically request that they not be made visible to the meta facility, or you can use a module system to grant access to the implementation of data only in certain modules. It does not have to be program wide. The scheme I suggested for generic printing was not as safe as you might like, but it was intended to be simple and easy to implement, and there is some merit in that I think. Cheers, Bernie.

3 2

Re: a universal printer for Haskell?
by C.Reinke 20 Feb '02

20 Feb '02

> You don't need meta-programming technology (reflection) to do things like > generic prinitng. A generic programming extension of Haskell (like > Generic Haskell, or derivable classes) can do the job for you. Isn't generic programming usually based on a kind of compile-time reflection (if the argument is of this type, do this, else..)? And don't you write generic functions with the intention that the implementation will figure out the approriate type-specific variants, i.e., you write your code at a level of abstraction that is not easily reached with the standard language tools -- a meta level, where functions at different types are the first-class objects of discourse? I find it helpful to think of generic programming support as one way of integrating well-behaved subsets of reflection and other meta-programming techniques into Haskell. It is partly a trade-off: you get some of the features and avoid some of the problems of a fully reflective architecture. It is also a specialisation: by avoiding the full generality, the specific subset of features can be designed in a structured fashion, with the application domain in mind, making them easier to use for that domain. Claus (another fan of reflection and meta-programming, who would like to get their advantages without their disadvantages -- the latter are more clearly visible in a pure functional language than in Lisp)

2 1

Re: a universal printer for Haskell?
by Ashley Yakeley 20 Feb '02

20 Feb '02

At 2002-02-19 22:46, Bernard James POPE wrote: >The scheme I suggested for generic printing >was not as safe as you might like, but it was intended to be simple >and easy to implement, and there is some merit in that I think. I strongly recommend you check out generic classes: <http://www.haskell.org/ghc/docs/latest/set/generic-classes.html> I suspect you can use them to do what you want... -- Ashley Yakeley, Seattle WA

2 1

Re: syntax...(strings/interpolation/here docs)
by C.Reinke 20 Feb '02

20 Feb '02

{- > Unlike my rough proposal, one should aim for a combination of > (mostly) in-Haskell implementation and (some) pre-processing. As > Thomas Nordin has pointed out to me in private email, Hugs (Dec > 2001) already supports this (module lib/hugs/Quote.hs and flag +H). > > The real trick is to have the same support in all implementations.. -} module HereDocuments where {- :set +H -} import Quote text = `` When I mentioned pre-processing, I didn't mean doing something to generate a Haskell program, I meant simple language extension (as in: syntactic sugar). It is nice that the Hugs variant of here documents is easily implemented with pre-processing, but that should be done behind the scenes. Usually, I wouldn't make such a fuss, but here documents are really not some new and experimental feature. They're an old hat, and a very useful hat. The only question is how to integrate them into the rest of Haskell. The Lewis/Nordin suggestion implemented in Hugs looks like a good compromise, but it won't do harm to bind the sugar to an option/flag for a test period. In the end, a stable form of here documents should be part of the language (not part of what you can do to it with whatever tools in whatever contexts), directly supported by all implementations. '' main = putStrLn $ trim text -- Claus

5 4

Re: a universal printer for Haskell?
by Ashley Yakeley 20 Feb '02

20 Feb '02

At 2002-02-19 20:50, Eray Ozkural wrote: >> It's ugly, and isn't part of the spirit of the language. > >The above statement cannot be a basis for any argument against Bernard's >proposal. It's an aesthetic argument that hopes for an aesthetic consensus among Haskell users (which may or may not exist). ... >Since you are defining the spirit of the language, Oh no, spirit cannot be defined, only suggested. ... >A general concept such as reflection cannot be deemed as worthless in >itself. It might reasonably be considered inappropriate to Haskell. Reflection may be useful for debugging, so I would not call it worthless. I consider reflection such as Generics to be in more or less the same aesthetic category as unsafe IO functions -- something to be generally avoided but perhaps useful in certain limited contexts such as debugging. I don't use Generics or unsafe-anything in my Haskell software. I _do_ occasionally use the 'deriving' construct, which is strictly speaking reflection though I think a relatively harmless form. What I would hate to see is widespread use of reflection in general programs. It rather seems to miss the point of Haskell's type system. >Any system that has a tiny bit of introspective powers can be said to be >reflective to some extent, for instance a Haskell interpreter. That's fine, but I don't include a Haskell interpreter in my compiled Haskell programs. And I don't want other people peeking inside my types at run-time. -- Ashley Yakeley, Seattle WA

1 0