January 2005 - Haskell-Cafe

Initial (term) algebra for a state monad
by oleg＠pobox.com 06 Jan '05

06 Jan '05

Andrew Bromage wrote: << -- WARNING: This code is untested under GHC HEAD data State s a = Bind :: State s a -> (a -> State s b) -> State s b | Return :: a -> State s a | Get :: State s s | Put :: s -> State s () instance Monad (State s) where (>>=) = Bind return = Return instance MonadState s (State s) where get = Get put = Put runState :: State s a -> s -> (s,a) runState (Return a) s = (s,a) runState Get s = (s,s) runState (Put s) _ = (s,()) runState (Bind (Return a) k) s = runState (k a) s runState (Bind Get k) s = runState (k s) s runState (Bind (Puts) k) _ = runState (k ()) s runState (Bind (Bind m k1) k2) s = runState m (\x -> Bind (k1 x) k2) s >> The following is the code that does run, on GHC 6.2.1. Typeclasses are just as good at pattern-matching as (G)ADT, and GHC is quite good at suggesting the constraints that I have missed. The latter comes quite handy when one programs half-asleep. {-# OPTIONS -fglasgow-exts #-} {-# OPTIONS -fallow-undecidable-instances #-} module B where import Control.Monad import Control.Monad.State hiding (runState) -- data State s a -- = Bind :: State s a -> (a -> State s b) -> State s b -- | Return :: a -> State s a -- | Get :: State s s -- | Put :: s -> State s () class RunBind t s a => RunState t s a | t s -> a where runst :: t -> s -> (s,a) data Bind t1 t2 = Bind t1 t2 data Return t = Return t data Get = Get data Put t = Put t instance RunState (Return a) s a where runst (Return a) s = (s,a) instance RunState Get s s where runst _ s = (s,s) instance RunState (Put s) s () where runst (Put s) _ = (s,()) instance (RunState m s a, RunState t s b) => RunState (Bind m (a->t)) s b where runst (Bind m k) s = runbind m k s class RunBind m s a where runbind :: RunState t s b => m -> (a->t) -> s -> (s,b) instance RunBind (Return a) s a where runbind (Return a) k s = runst (k a) s instance RunBind (Get) s s where runbind Get k s = runst (k s) s instance RunBind (Put s) s () where runbind (Put s) k _ = runst (k ()) s instance (RunBind m s x, RunState y s w) => RunBind (Bind m (x->y)) s w where runbind (Bind m f) k s = runbind m (\x -> Bind (f x) k) s data Statte s a = forall t. RunState t s a => Statte t instance RunState (Statte s a) s a where runst (Statte t) s = runst t s instance RunBind (Statte s a) s a where runbind (Statte m) k s = runbind m k s instance Monad (Statte s) where (Statte m) >>= f = Statte (Bind m (\x -> f x)) return = Statte . Return instance MonadState s (Statte s) where get = Statte Get put = Statte . Put test1 (a::a) = runst (do x <- (return a :: Statte Char a) y <- get put 'b' return (y,x)) 'a' test1' = test1 "ok" test2 = runst (return True :: Statte Char Bool) 'a'

4 3

Tutorial for server programming in concurrent Haskell
by Ahn Ki-yung 05 Jan '05

05 Jan '05

I've recently started a small tutorial for server programming in concurrent Haskell. http://kyagrd.dyndns.org/wiki/HaskellServerProgramming For newbies in Haskell and/or server programming, there should be an interoductory tutorial with concrete and simple examples before Simon Marlow's papers about web server implementation in Haskell. This tutorial consists of two famous examples, Echo and Chat, with the source code and makefile to be downloaded, compliled and tested right away. I hope this could be some helpt to those who want to start server programming in Haskell. Server programming in modern fucntional language with concurrency support is a real pleasure! You should also try Erlang if you havnt' tried yet.

2 1

Re: [Haskell-cafe] ReadS with Maybe
by Jon Cast 05 Jan '05

05 Jan '05

Henning Thielemann <lemming(a)henning-thielemann.de> wrote: > What is the reason for the definition > ReadS a = [(a, String)] > not being > ReadS a = Maybe (a, String) > ? The latter one reflects that either one or no value is read, whereas > the first definition allows an arbitrary number of read values which > is confusing and unsafe in my opinion. List is a backtracking monad, while Maybe is merely an error monad. You have to have backtracking to bet better than LL(1) or LR(1) parsing, and LL(1) is not an acceptable restriction for a fundamental function like read. Jonathan Cast

1 0

ReadS with Maybe
by Henning Thielemann 05 Jan '05

05 Jan '05

What is the reason for the definition ReadS a = [(a, String)] not being ReadS a = Maybe (a, String) ? The latter one reflects that either one or no value is read, whereas the first definition allows an arbitrary number of read values which is confusing and unsafe in my opinion.

4 3

RE: [Haskell-cafe] GHC for .NET?
by Simon Peyton-Jones 05 Jan '05

05 Jan '05

| Understandably, however, there is real resistance in language communities like Haskell's to changing | or even extending a language for the sake of interoperability and API access: instead people work | incredibly hard to encode interoperability via existing mechanisms. In the end, whoever picks up the | burden of doing Haskell.NET will face the same unenviable choice that every other .NET language | design group has faced: | | (a) do you modify and/or extend the language to make "the nicest possible Haskell-like language in | the context of .NET" | | or (b) do you implement Haskell faithfully without language extensions, but where using the .NET | libraries is in practice somewhat arcane and unpleasant, probably sufficiently so that you'll be unable | to attract .NET-savvy programmers to your language. | | Personally I think language designs in space (a) are more interesting, since perfectly good native | implementations of Haskell are already available on most platforms. I also think you learn a lot more | by trying to create something new, and you give yourself the maximum possible long-term chance of | rivalling other .NET languages (which I think should be an important goal for a Haskell.NET) I agree with all of that, including leaning towards (a) -- and it also helps to explain why we have moved so slowly on the GHC.net front. GHC is a big system already, and specifically tries to be multi-platform. Making substantial, but platform-specific, language changes is arguably the Right Thing (as Don says), but not so attractive for GHC. Simon

1 0

RE: [Haskell-cafe] Problem with fundeps.
by Simon Peyton-Jones 05 Jan '05

05 Jan '05

I can see why you think it "ought" to work. The instance decls instance (Vspace a v) => Vspace a (c->v) instance Num a => Vspace a a certainly overlap, but GHC does something sensible with the overlap, and that's presumably what you want. BUT the functional-dependency mechanism doesn't have the same resolution mechanism for overlap, and so it thinks both might match, and hence rejects the program. So yet another GHC enhancement might be to combine instance selection with the improvement coming from functional dependencies. Operationally, given a constraint, match it against possible instance decls using only the types *before* the arrow in the fundep (the 'v' in the case of Vspace) once an instance is chosen, the usual overlap-resolution stuff, use the fundep to force the other type(s) to match Hmmm. Has anyone else come across this? Meanwhile, why couldn't you have this: instance (Vspace a v) => Vspace a (c->v) instance Vspace Int Int instance Vspace Float Float etc That is, one instance for each base type? You only have a finite number of base types, so this might not be too bad. Simon | -----Original Message----- | From: haskell-cafe-bounces(a)haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of | Jerzy Karczmarczuk | Sent: 03 January 2005 13:02 | To: haskell-cafe(a)haskell.org | Subject: Re: [Haskell-cafe] Problem with fundeps. | | Henning Thielemann cites myself | | >>I am afraid that something is wrong with my understanding of multi- | >>param classes with dependencies. I tried to generalize one of my old | >>packages for quantum *abstract* computations, where state vectors are | >>defined as functional objects,... | >> | >>class Vspace a v | v -> a | >>where | >> (<+>) :: v -> v -> v | >> (*>) :: a -> v -> v | >> -- etc. | >> | >>instance Vspace a a where | >> (<+>) = (+) | >> (*>) = (*) | >> -- etc. No problem. | >> | >>instance (Vspace a v) => Vspace a (c->v) where | >> f <+> g = \x -> f x <+> g x | >> (a *> f) x = a *> (f x) | >> -- ... | >> | >> | > | >I had the same problem with the same class | > http://www.haskell.org//pipermail/haskell-cafe/2004-March/005979.html | > and thus Dylan Thurston advised me to drop functional dependencies. | > | > | I can't... Otherwise I am killed by ambiguities, later. | | >Here are two implementations using multi-type classes without functional | >dependencies. (They wait for unification, yet, sorry.) | > http://cvs.haskell.org/darcs/numericprelude/VectorSpace.lhs | > http://cvs.haskell.org/darcs/numericprelude/physunit/VectorSpace.hs | > | > | I followed this discussion, and I know your and DT DARC project. | Unfortunately my ambitions are Gargantuan, I want to have | vector spaces which encompass functions over ADT (the config. | specification for a quantum system), functions over functions | (duals and operators), and also functional tensors, which makes | it possible to construct binary functions as a 'product' of two | unary functions; extensible. | | And all this over all kind of scalars. Principally complex, but | also some differential scalars (elements of a differential algebra, | permitting to do the 'automatic differentiation' of Dirac brackets | and also kets, which would permit to use constructively the | differential recurrential definitions of states (Hermite functions, | etc.) For the moment I am obliged to FIX the field of scalars, this | *partly* solves my mathematical troubles. | | I believe in almost all what Ashley Yakeley (and Marcin QK) say, | but in | | >>> instance (Num a)=>Vspace a (c->a) where | >>> instance (Vspace a v) => Vspace a (c->v) where | >> | >> | > | >These are also incompatible. ... | > | the word 'incompatible' should be understood as 'incompatible with | current Haskell', *not* with common sense. Pity. It is obvious that | both: a function any -> scalar, and (any->scalar)->any->scalar | with good arithmetic scalars permit to establish the vector structure. | | Actually, the instances as quoted above produces bizarrily an error | which says that something is less polymorphic than expected; the | overlapping is accepted (apparently). | | Sigh. | | Jerzy Karczmarczuk | | | | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1

RE: [Haskell-cafe] Re: GHC for .NET?
by Don Syme 05 Jan '05

05 Jan '05

> I've heard complaints about the unsuitability of the Java VM for lazy > functional languages. I wonder if the CLR also has issues for this? The CLR has some technical features that make it more attractive than the JVM, e.g. pointer-based unsafe code (useful for some closure representations), tailcalls, generics, light-weight code generation (the latter can be used for mixed interpretation/compilation with code reclamation). But in the end it will depends on what your goals are - you will probably take a performance hit, but you will get a lot of benefits, e.g. loads of great libraries and tools. I think a variant of Haskell could find a niche in the context of either Java or .NET. Cheers Don -----Original Message----- From: haskell-cafe-bounces(a)haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of Ashley Yakeley Sent: 04 January 2005 01:14 To: haskell-cafe(a)haskell.org Subject: [Haskell-cafe] Re: GHC for .NET? In article <5DCA48FADB33FF4D8C32A164DF24F2B0023C12C0(a)EUR-MSG-03.europe.corp.microso ft.com>, "Don Syme" <dsyme(a)microsoft.com> wrote: > We still frequently talk about doing either Haskell.NET or a strict > language much closer to Haskell (perhaps as a stepping stone to doing > Haskell). But neither are currently active projects. I've heard complaints about the unsuitability of the Java VM for lazy functional languages. I wonder if the CLR also has issues for this? -- Ashley Yakeley, Seattle WA _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

RE: [Haskell-cafe] GHC for .NET?
by Don Syme 05 Jan '05

05 Jan '05

> There is some good groundwork already done... I'd add that during my first effort to do GHC.NET I modified GHC to optionally preserve full type information through to the backend, including type applications. This is necessary if you're going to produce verifiable code. > The trouble here is that Haskell's type system is more expressive > than the CLR's in some ways, notably the use of higher-kinded > type variables. The problem with higher-kinded type variables is quite significant, and were one of the reasons I stopped work on ghc.net. It is an open question as to whether you can compile type parameters to .NET generics and higher-kinded parameters by some other means (i.e. to casts etc.) - I believe it is possible by passing term parameters in place of higher-kinded type variables, where the term parameters are called whenever the type function is applied. However when I tried to implement this scheme it got too complex, especially given how few uses of higher-kinded polymorphism there are in practice. It would probably be better to initially simply inline all higher-kinded code at the callsites. Cheers Don -----Original Message----- From: Simon Peyton-Jones Sent: 04 January 2005 12:18 To: Don Syme; John Goerzen; haskell-cafe(a)haskell.org Cc: GHC users Subject: RE: [Haskell-cafe] GHC for .NET? | "The GHC compiler for .NET is currently under development at | Microsoft Research, Cambridge". | | Hmm. That location sounds familiar :-) Does anyone know if this is | actually going to happen? Or if there's any code anywhere, however | experimental, to try? It'd make a lot of sense to give GHC a .NET back end, and it's a question that comes up regularly. The reason that we haven't done it here, at GHC HQ, is because it's a more substantial undertaking than might at first appear (see below). Furthermore, it'd permanently add a complete new back-end platform for us to maintain. Given our rather limited development effort (= Simon and me), we have so far not bitten the bullet, and we have no immediate plans to do so. It'd be a good, well-defined project for someone else to tackle, and there is some good groundwork already done: * Sigbjorn Finne did a simple interop implementation that allows a Haskell program to be compiled to native code (as now) but to call .NET programs via a variant of the FFI. I don't think this work is in active use, and I'd be surprised if it worked out of the box, but it could probably be revived with modest effort * Andre Santos and his colleagues at UFPE in Brazil are working on a .NET back end, that generates CLR IL, though I don't know where they are up to. * GHC.Net would be extra attractive if there was a Visual Studio integration for GHC. Substantial progress on this has been made in 2004 by Simon Marlow, Krasimir Angelov, and Andre Santos and colleagues. There may be others that I don't know of. If anyone wants to join in this effort, do contact the above folk. And please keep us informed! Simon Here's a summary of why it's a non-trivial thing to do: - The first thing is to generate native CLR Intermediate Language (IL). That's not really hard. Requires thinking about representations for thunks and functions, and it may not be particularly efficient, but it can surely be done. An open question is about whether to generate verifiable IL or not. The trouble here is that Haskell's type system is more expressive than the CLR's in some ways, notably the use of higher-kinded type variables. So, to generate verifiable IL one is bound to need some run-time casts, and it's not clear how to minimise these. At first blush this is *all* you need do. But it isn't! - Next, you need to think about how to inter-operate with .NET libraries. You don't really want to write "foreign import..." for each and every import. You'd like GHC to read the CLR meta-data directly. But there are lots of tricky issues here; see the paper that Mark Shields and I wrote about "Object-oriented style overloading for Haskell". - Now you need to figure out how to implement GHC's primitive operations: the I/O monad arbitrary precision arithmetic concurrency exceptions finalisers stable pointers software transactional memory Not all of these are necessary, of course, but many are used in the libraries. The CLR supports many of them (e.g. concurrency) but with a very different cost model. - Last, you have to figure out what to do for the libraries. GHC has a pretty large library, and you either have to implement the primops on which the library is based (see previous point), or re-implement it. For example, GHC's implementation of I/O uses mutable state, concurrency, and more besides. For each module, you need to decide either to re-implement it using .NET primitives, or to implement the stuff the module is based on. These challenges are mostly broad rather than deep. But to get a production quality implementation that runs a substantial majority of Haskell programs "out of the box" requires a decent stab at all of them.

1 0

RE: [Haskell-cafe] GHC for .NET?
by Don Syme 05 Jan '05

05 Jan '05

> Next, you need to think about how to inter-operate with .NET > libraries. You don't really want to write "foreign import..." > for each and every import. You'd like GHC to read the CLR > meta-data directly. But there are lots of tricky issues here; > see the paper that Mark Shields and I wrote about "Object-oriented > style overloading for Haskell". >From what I've seen, .NET interoperability (i.e. API access) is too important to simply encode into a language using existing language mechanisms. Let's be honest: there isn't a single language that has succeeded in giving decent inter-operability without modifying and/or substantially extending the language (there are several faithful language implementations, e.g. OCamlIL, but these efforts have not covered interoperability). I really don't see why Haskell will be any different. Of course no design group _wants_ to change or extend their existing language, and on the whole they do not end up doing it because of limitations in the CLR. Instead they eventually come around to the fact that there are big benefits to providing .NET API access that "feels right" to the programmer, rather than forcing the programmer to use arcane encodings into existing language constructs, even if that means changing and/or extending the language. Some see this as a weakness of the .NET approach to interoperability (because it forces too much on each language, e.g. generics, classes, interfaces, properties, namespaces). Some also see it as its strength (because it gives the API designer a better set of tools, all of which will be understood by each language - at least better when compared to COM or C). Many in the first camp are language designers and/or implementers, while many in the second are working programming teams who are very happy to be able to use high-level, extensible APIs from a number of programming languages. You can argue over whether .NET has made good choices for the primitives used to express APIs (some hate classes, some hate generics), but the fundamental principle won't change: if you want rich common constructs for expressing APIs, then the language designers and implementers pay the price (by having to support a common set of non-trivial constructs), while the programmers reap the benefits. Understandably, however, there is real resistance in language communities like Haskell's to changing or even extending a language for the sake of interoperability and API access: instead people work incredibly hard to encode interoperability via existing mechanisms. In the end, whoever picks up the burden of doing Haskell.NET will face the same unenviable choice that every other .NET language design group has faced: (a) do you modify and/or extend the language to make "the nicest possible Haskell-like language in the context of .NET" or (b) do you implement Haskell faithfully without language extensions, but where using the .NET libraries is in practice somewhat arcane and unpleasant, probably sufficiently so that you'll be unable to attract .NET-savvy programmers to your language. Personally I think language designs in space (a) are more interesting, since perfectly good native implementations of Haskell are already available on most platforms. I also think you learn a lot more by trying to create something new, and you give yourself the maximum possible long-term chance of rivalling other .NET languages (which I think should be an important goal for a Haskell.NET) But people devoted to the Haskell standard will no doubt prefer (b), as may people whose main interest is in presenting .NET functionality in a Haskell-esque way (e.g. via Fran-like libraries). Finally, all this just deals with "import" interoperability. Nearly as important in practice is "export" interoperability, i.e. how is your Haskell code going to look to other .NET languages, and is it going to be usable by those languages. Just my 2c worth for the New Year :-) Cheers Don -----Original Message----- From: Simon Peyton-Jones Sent: 04 January 2005 12:18 To: Don Syme; John Goerzen; haskell-cafe(a)haskell.org Cc: GHC users Subject: RE: [Haskell-cafe] GHC for .NET? | "The GHC compiler for .NET is currently under development at | Microsoft Research, Cambridge". | | Hmm. That location sounds familiar :-) Does anyone know if this is | actually going to happen? Or if there's any code anywhere, however | experimental, to try? It'd make a lot of sense to give GHC a .NET back end, and it's a question that comes up regularly. The reason that we haven't done it here, at GHC HQ, is because it's a more substantial undertaking than might at first appear (see below). Furthermore, it'd permanently add a complete new back-end platform for us to maintain. Given our rather limited development effort (= Simon and me), we have so far not bitten the bullet, and we have no immediate plans to do so. It'd be a good, well-defined project for someone else to tackle, and there is some good groundwork already done: * Sigbjorn Finne did a simple interop implementation that allows a Haskell program to be compiled to native code (as now) but to call .NET programs via a variant of the FFI. I don't think this work is in active use, and I'd be surprised if it worked out of the box, but it could probably be revived with modest effort * Andre Santos and his colleagues at UFPE in Brazil are working on a .NET back end, that generates CLR IL, though I don't know where they are up to. * GHC.Net would be extra attractive if there was a Visual Studio integration for GHC. Substantial progress on this has been made in 2004 by Simon Marlow, Krasimir Angelov, and Andre Santos and colleagues. There may be others that I don't know of. If anyone wants to join in this effort, do contact the above folk. And please keep us informed! Simon Here's a summary of why it's a non-trivial thing to do: - The first thing is to generate native CLR Intermediate Language (IL). That's not really hard. Requires thinking about representations for thunks and functions, and it may not be particularly efficient, but it can surely be done. An open question is about whether to generate verifiable IL or not. The trouble here is that Haskell's type system is more expressive than the CLR's in some ways, notably the use of higher-kinded type variables. So, to generate verifiable IL one is bound to need some run-time casts, and it's not clear how to minimise these. At first blush this is *all* you need do. But it isn't! - Next, you need to think about how to inter-operate with .NET libraries. You don't really want to write "foreign import..." for each and every import. You'd like GHC to read the CLR meta-data directly. But there are lots of tricky issues here; see the paper that Mark Shields and I wrote about "Object-oriented style overloading for Haskell". - Now you need to figure out how to implement GHC's primitive operations: the I/O monad arbitrary precision arithmetic concurrency exceptions finalisers stable pointers software transactional memory Not all of these are necessary, of course, but many are used in the libraries. The CLR supports many of them (e.g. concurrency) but with a very different cost model. - Last, you have to figure out what to do for the libraries. GHC has a pretty large library, and you either have to implement the primops on which the library is based (see previous point), or re-implement it. For example, GHC's implementation of I/O uses mutable state, concurrency, and more besides. For each module, you need to decide either to re-implement it using .NET primitives, or to implement the stuff the module is based on. These challenges are mostly broad rather than deep. But to get a production quality implementation that runs a substantial majority of Haskell programs "out of the box" requires a decent stab at all of them.

1 0

RE: [Haskell-cafe] GHC for .NET?
by Don Syme 03 Jan '05

03 Jan '05

That's out of date - I abandoned my first effort to do ghc.net in favour of doing a strict functional language first - F# is the result (http://research.microsoft.com/projects/fsharp) We still frequently talk about doing either Haskell.NET or a strict language much closer to Haskell (perhaps as a stepping stone to doing Haskell). But neither are currently active projects. Thanks Don -----Original Message----- From: haskell-cafe-bounces(a)haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of John Goerzen Sent: 29 December 2004 00:51 To: haskell-cafe(a)haskell.org Subject: [Haskell-cafe] GHC for .NET? Over at http://www.gotdotnet.com/community/resources/Default.aspx?ResourceTypeDr opDownList=Language+vendors&SortDirection=Desc&SortColumnName=CreationDa te, I read: "The GHC compiler for .NET is currently under development at Microsoft Research, Cambridge". Hmm. That location sounds familiar :-) Does anyone know if this is actually going to happen? Or if there's any code anywhere, however experimental, to try? As a side note, the dotgnu project includes a C-to-CLR compiler, though it has trouble passing the autoconf stuff in ghc (and I may not have the expertise to fix it; it is crashing on the alignment tests). I figure that if I can get portable enough C code out of ghc, and a runtime compiled to CLR, it should be possible to compile Haskell to .NET that way. Anyway, it's just me off on a tangent again. Thanks, John _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1