September 2006 - Haskell

PLAN-X 2007: Call for Papers and Demos (Deadline Extended)
by Torsten Grust 20 Sep '06

20 Sep '06

Third Call for Papers and Software Demonstrations P L A N - X 2 0 0 7 Programming Language Techniques for XML An ACM SIGPLAN Workshop colocated with POPL 2007 Nice, France -- January 20, 2007 http://www.plan-x-2007.org/ || The submission deadline for PLAN-X 2007 has been || || postponed by a few days. New submission deadline: || || Tuesday, October 10, 2006, 5 PM (PDT) || -- PLAN-X 2007 Aim and Scope The XML data model and its associated languages add interesting twists to programming language practice as well as theory. Just like its four predecessors, the PLAN-X 2007 workshop turns the spotlight on how programming languages can embrace, for example, tree-shaped XML data structures, regular expression types extracted from schema descriptions, very small or large XML instances, queries against XML data, and XML transformations. XML reaches deep into all aspects of language design, type systems, compilers, as well as runtimes and PLAN-X 2007 is THE forum to present and discuss novel research work in this area. We invite contributions -- papers as well as software demonstrations -- from members of the programming language, database, theory, and document processing communities and look forward to a workshop in which this diversity of contributions and attendees leads to lively discussion and a fun event. If you are architecting a software system that fuses programming language and XML technology in interesting and innovative ways, please submit a software demonstration proposal to PLAN-X 2007. The workshop program will feature a special demo session. A two-page description of the accepted software demonstrations will be included in the proceedings. PLAN-X 2007 will be held in cooperation with and just after POPL 2007, the 34th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages in the Plaza Hotel in Nice, France, on Januar 20, 2007. -- PLAN-X 2007 Topics of Interest Topics of interest include the following (though interesting and/or innovative papers on all aspects of programming languages for XML are welcome): - Design of programming and query languages for XML - Programming in the XML data model itself (e.g., extending XQuery into a full-fledged programming language) - Formal accounts of XML and its processors (based on logic, automata, variants of lambda calculus, etc.) - Compilers and interpreters for XML-aware languages and optimization techniques - Type systems, schema languages, and other constraints (e.g., keys) for tree-shaped data - Tree automata and transducers - Languages and systems that can cope with XML fragments (messages) or very large XML instances (beyond main-memory size) - Programming language glue between browsers, web services, and databases - Pioneering applications of XML-aware language technology -- Proceedings Accepted submissions will be collected to form the informal PLAN-X 2007 proceedings, to be indexed on Michael Ley's DBLP site and distributed at the workshop. The material may thus be published elsewhere at a later date. -- Paper Format and Submission The web-based paper submission site for PLAN-X 2007 is open! Submit at URL http://www.easychair.org/PLANX2007/ (Please register as a New User to obtain a login and password for the submission site.) PLAN-X 2007 calls for contributions relevant to the open list of topics sketched above. We explicitly welcome reports on innovative, off-beat, and ''early stage'' approaches as long as the submission reports on original work not published or submitted elsewhere. - Please format your papers according to the ACM guidelines and SIG proceedings templates available at http://www.acm.org/sigs/pubs/proceed/template.html The mandatory submission file format is PDF. - Regular papers should not exceed 10 pages in length including references and appendices, but shorter abstracts (of, e.g., 2000 words) often suffice and are acceptable as well. - Software demonstration proposals are limited to 2 pages and should include a sketch of the methods you employ as well as a description of what exactly will be demoed. Please submit your demonstration proposal via the regular paper submission site and add "(Demo)" to your submission's title. -- Important Dates - Paper submission (extended): Tue, Oct 10, 2006, 5 PM (PDT) - Notification of acceptance: Sat, Nov 25, 2006 - Camera-ready copy due: Sun, Dec 17, 2006 - Workshop: Sat, Jan 20, 2007 -- PLAN-X 2007 Program Committee - Michael Benedikt (Lucent, USA) - Daniela Florescu (Oracle, USA) - Alain Frisch (INRIA Roquencourt, France) - Giorgio Ghelli, Chair (U Pisa, Italy) - Haruo Hosoya (U Tokyo, Japan) - Anders Møller (U Aarhus, Denmark) - Mukund Raghavachari (IBM T.J. Watson Research Center, USA) - Alan Schmitt (INRIA Rhône-Alpes, France) - Sophie Tison (U Lille, France) - Philip Wadler (U Edinburgh, UK) -- PLAN-X 2007 Workshop Chairs - General Chair - Program Chair Torsten Grust Giorgio Ghelli TU München U Pisa Munich, Germany Pisa, Italy grust(a)in.tum.de ghelli(a)di.unipi.it

1 0

Re: [Haskell] How to define Y combinator in Haskell
by David House 15 Sep '06

15 Sep '06

On 15/09/06, Haihua Lin <HaihuaLin(a)163.com> wrote: > Is there a way to define it in Haskell? Note that the function 'fix' (find the fixpoint of a function) already exists in Haskell, and is equivalent to the Y combinator. It's interesting that most (all?) fixed-point combinators don't typecheck. The Y combinator, and by extension recursion in general, has to be added as a constant to the language. -- -David House, dmhouse(a)gmail.com

3 3

Is there an example how to pass a string to VBA?
by Andreas Marth 15 Sep '06

15 Sep '06

Hallo everybody! I'm trying to pass a String to VBA and am totally stuck. Does anyody have a working example how to do this? I am interested in either a plain low level DLL or a COM DLL or anything else if there is something else. I hope someone did this already and can give me a helping hand. A nice weekend for everybody, Andreas

2 2

How to define Y combinator in Haskell
by Haihua Lin 15 Sep '06

15 Sep '06

Hi, Writing yc = \f -> (\x -> f(x x)) (\x -> f(x x)) causes type error. Is there a way to define it in Haskell? Thanks, Haihua

2 1

ETAPS 2007 - Call for Submissions
by João Saraiva 15 Sep '06

15 Sep '06

***************************************************************** *** *** *** ETAPS 2007 *** *** March 24 - April 1, 2007 *** *** Braga, Portugal *** *** *** *** http://www.di.uminho.pt/etaps07/ *** *** *** *** CALL FOR SUBMISSIONS *** *** *** *** Abstract submission deadline: 6th October, 2006 *** *** Full submission deadline: 13th October, 2006 *** *** *** ***************************************************************** The European Joint Conferences on Theory and Practice of Software (ETAPS) is the primary European forum for academic and industrial researchers working on topics related to Software Science. It is a confederation of five main conferences, several satellite workshops and other events. * Main Conferences - Call for Submissions: CC 2007 International Conference on Compiler Construction ESOP 2007 European Symposium on Programming FASE 2007 Fundamental Approaches to Software Engineering FOSSACS 2007 Foundations of Software Science and Computation Structures TACAS 2007 Tools and Algorithms for the Construction and Analysis of Systems See: http://www.di.uminho.pt/etaps07/conf.html * Workshops - Call for Submissions: For the complete list of workshops and their deadlines See: http://www.di.uminho.pt/etaps07/workshops.html * Tutorials - Call for Submissions: See: http://www.di.uminho.pt/etaps07/tutorials.html

1 0

On computable types. II. Flipping the arrow
by oleg＠pobox.com 15 Sep '06

15 Sep '06

Part I of the series introduced the type-level functional language with the notation that resembles lambda-calculus with case distinction, fixpoint recursion, etc. Modulo a bit of syntactic tart, the language of the type functions even looks almost like the pure Haskell. In this message, we show the applications of computable types, to ascribe signatures to terms and to drive the selection of overloaded functions. We can compute the type of a tree of the depth fib(N) or a complex XML type, and instantiate the read function to read the trees of only that shape. A telling example of the power of the approach is the ability to use not only (a->) but also (->a) as an unary type function. The former is just (->) a. The latter is considered impossible. In our approach, (->a) is written almost literally as (flip (->) a) This series of messages has been inspired by Luca Cardelli's 1988 manuscript ``Phase Distinctions in Type Theory'' http://lucacardelli.name/Papers/PhaseDistinctions.pdf and by Simon Peyton Jones and Erik Meijer's ``Henk: A Typed Intermediate Language'' http://www.research.microsoft.com/~simonpj/Papers/henk.ps.gz which expounds many of the same notions in an excellent tutorial style and in modern terminology. I'm very grateful to Chung-chieh Shan for pointing out these papers to me and for thought-provoking discussions. > {-# OPTIONS -fglasgow-exts #-} > {-# OPTIONS -fallow-undecidable-instances #-} > > module TypeFN where > import TypeLC -- Load part I of this series (prev message) Our first example comes from Cardelli's paper: defining the type Prop(n), of n-ary propositions. That is, Prop(2) should be the type Bool -> Bool -> Bool Prop(3) is the type of functions Bool -> Bool -> Bool -> Bool etc. Cardelli's paper (p. 10) writes this type as let Prop:: AllKK(N:: NatK) Type = recK(F:: AllKK(N:: NatK) Type) funKK(N:: NatK) caseK N of 0K => Bool; succK(M) => Bool -> F(M); let and2: Prop(2K) = fun(a: Bool) fun(b: Bool) a & b; Here 0K and 2K are type-level numerals of the kind NatK; recK is the type-level fix-point combinator. The computed type Prop(2) then gives the type to the term and2. In our system, this example looks as follows: > data Prop' > instance A (F Prop') f (F (Prop',f)) > instance A (F (Prop',f)) Zero Bool > instance E (f :< m) r => A (F (Prop',f)) (Su m) (Bool -> r) > type Prop = Rec (F Prop') > type Prop2 = E (F Prop :< N2) r => r > and2 = (\x y -> x && y) `asTypeOf` (undefined:: Prop2) We can compute types by applying type functions, just as we can compute values by applying regular functions. Indeed, let us define a StrangeProp of the kind NAT -> Type. StrangeProp(n) is the type of propositions of arity m, where m is fib(n). We compose together the already defined type function Prop2 and the type function Fib in the previous message. > data StrangeProp > instance E (F Prop :< (F Fib :< n)) r => A (F StrangeProp) n r > oddand4t :: E (F StrangeProp :< (F FSum :< N2 :< N2)) r => r > oddand4t = undefined > oddand5 = (\x1 x2 x3 x4 -> ((x1 && x2 && x3) &&) . and2 x4) > `asTypeOf` oddand4t *DepType> :t oddand4t oddand4t :: Bool -> Bool -> Bool -> Bool -> Bool -> Bool We can do better, with the help of higher-order type functions. First we declare a few standard Haskell type constants as constants in our calculus, with trivial evaluation rules > instance E Bool Bool > instance E Int Int > instance E String String > instance E (a->b) (a->b) -- We could just as well evaluate under > instance E (a,b) (a,b) -- these We introduce the combinator Ntimes: |NTimes f x n| applies f to x n times. This is a sort of fold over numerals. > data Ntimes > instance A (F Ntimes) f (F (Ntimes,f)) > instance A (F (Ntimes,f)) x (F (Ntimes,f,x)) > instance A (F (Ntimes,f,x)) Zero x > instance E (F Ntimes :< f :< (f :< x) :< n) r => A (F (Ntimes,f,x)) (Su n) r > data ATC1 c > instance A (F (ATC1 c)) x (c x) We can then write the type of n-ary propositions Prop(N) in a different way, as an N-times application of the type constructor (Bool->) to Bool. > type PropN' n = E(F Ntimes :< (F (ATC1 ((->) Bool))) :< Bool :< n) r => r > and2' = (\x y -> x && y) `asTypeOf` (undefined:: PropN' N2) To generalize, > data ATC2 (c :: * -> * -> *) > instance A (F (ATC2 c)) x (F (ATC1 (c x))) -- currying of type constructors > type SPropN' n = E(F Ntimes :< (F (ATC2 (->)) :< Bool) :< Bool > :< (F Fib :< n)) r => r > test_spn4 = undefined::SPropN' (Su N3) *TypeFN> :t test_spn4 test_spn4 :: Bool -> Bool -> Bool -> Bool -> Bool -> Bool The comparison of ATC1 with ATC2 shows two different ways of defining abstractions: as (F x) terms (`lambda-terms' in our calculus) and as polymorphic types (Haskell type abstractions). The two ways are profoundly related. The more verbose type application notation, via (:<), has its benefits. After we introduce another higher-order function > data Flip > instance A (F Flip) f (F (Flip,f)) > instance A (F (Flip,f)) x (F (Flip,f,x)) > instance E (f :< y :< x) r => A (F (Flip,f,x)) y r we make a very little change > type SSPropN' n = E(F Ntimes :< (F Flip :< (F (ATC2 (->))) :< Bool) :< Bool > :< (F Fib :< n)) r => r > test_sspn4 = undefined::SSPropN' (Su N3) and obtain quite a different result: *TypeFN> :t test_sspn4 test_sspn4 :: ((((Bool -> Bool) -> Bool) -> Bool) -> Bool) -> Bool In effect, we were able to use not only (a->) but also (->a) as an unary type function. Moreover, we achieved the latter by almost literally applying the flip function to the arrow type constructor (->). Using the type inspection tools (typecast), we can replace the family of functions ATC1, ATC2 with one, kind-polymorphic, polyvariadic function ATC. This approach will be explained in further messages. We can use the computed types to drive overloaded functions such as read and show. The specifically instantiated read functions, in particular, will check that a (remotely) received serialized value matches our expectation. Let's consider the type of trees of the depth of at most N. > data Node v els = Node v [els] deriving (Read, Show) > type TreeDN v l n = E(F Ntimes :< (F (ATC1 (Node v))) :< l :< n) r => r > instance E (Node v els) (Node v els) > read_tree3 s = (read s) `asTypeOf` (undefined:: TreeDN Int String N3) *TypeFN> :t read_tree3 read_tree3 :: String -> Node Int (Node Int (Node Int String)) > ttree3_1 = read_tree3 "Node 1 [Node 2 []]" > ttree3_2 = read_tree3 "Node 1 [Node 2 [Node 3 [\"ok\"]]]" > ttree3_3 = read_tree3 "Node 0 [Node 1 [Node 2 [Node 3 [\"ok\"]]]]" *TypeFN> ttree3_2 Node 1 [Node 2 [Node 3 ["ok"]]] *TypeFN> ttree3_3 *** Exception: Prelude.read: no parse The ability of computed types to drive the selection of overloaded functions has wider implications. We can remove the need for functional dependencies, or simulate functional dependencies when they cannot apply. For example, one may define a multi-parameter typeclass but cannot assert functional dependencies, because not all instances satisfy them. Therefore, using the methods of the class may require complex and annoying type annotations. Computed types remove the need to manually write these annotations; the typechecker can compute them itself. This subject is to be explored further. The last example showed computations of polymorphic types, which, unsurprisingly, have the form of type abstractions. Our calculus is built around the deep connection between type abstraction/instantiation and functional abstraction/application.

1 0

On computable types. I. Typed lambda and type closures
by oleg＠pobox.com 15 Sep '06

15 Sep '06

This is the first message in a series on arbitrary type/kind-level computations in the present-day Haskell, and on using of so computed types to give signatures to terms and to drive the selection of overloaded functions. We can define the type TD N to be the type of a tree fib(N)-level deep, and instantiate the read function for the tree of that type. The type computations are largely expressed in a functional language not too unlike Haskell itself. In this message we present call-by-value lambda-calculus with booleans, naturals and case-discrimination. The distinct feature of our implementation, besides its simplicity, is the primary role of type application rather than that of abstraction. Yet we trivially represent closures and higher-order functions. We use proper names for function arguments (rather than deBruijn indices), and yet we avoid the need for fresh name generation, name comparison, and alpha-conversion. We have no explicit environment and no need to propagate and search it, and yet we can partially apply functions. Our implementation fundamentally relies on the connection between polymorphism and abstraction, and takes the full advantage of the type-lambda implicitly present in Haskell. The reason for the triviality of our code is the typechecker's already doing most of the work need for an implementation of lambda-calculus. Our code is indeed quite simple: its general part has only three lines: instance E (F x) (F x) instance (E y y', A (F x) y' r) => E ((F x) :< y) r instance (E (x :< y) r', E (r' :< z) r) => E ((x :< y) :< z) r The first line says that abstractions evaluate to themselves, the second line executes the redex, and the third recurses to find it. Still, we may (and did) write partial applications, the fixpoint combinator, Fibonacci function, and S and K combinators. Incidentally, the realization of the S combinator again takes three lines, two of which build the closures (partial applications) and the third line executes the familiar S-rule. instance A (F CombS) f (F (CombS,f)) instance A (F (CombS,f)) g (F (CombS,f,g)) instance E (f :< x :< (g :< x)) r => A (F (CombS,f,g)) x r Incidentally, the present code constitutes what seems to be the shortest proof that the type system of Haskell with the undecidable instances extension is indeed Turing-complete. That extension is needed for the fixpoint combinator -- which is present in the system described in Luca Cardelli's 1988 manuscript: http://lucacardelli.name/Papers/PhaseDistinctions.pdf As he wrote, ``Here we have generalized the language of constant expressions to include typed lambda abstraction, application and recursion (because of the latter we do not require compile-time computations to terminate).'' [p9] This message is all the code, which runs in GHC 6.4.1 (it could well run in Hugs; alas, Hugs does not like infix type constructors like :<). > {-# OPTIONS -fglasgow-exts #-} > {-# OPTIONS -fallow-undecidable-instances #-} > > module TypeLC where First we define some constants > data HTrue = HTrue > data HFalse = HFalse > data Zero = Zero > data Su a = Su a Indicator for functions, or applicable things: > data F x and the applicator > class A l a b | l a -> b The meaning of |A l a b| is that the application to |a| of an applicable thing denoted by |l| yields |b|. Surprisingly, this already works. Let us define the boolean Not function > data FNot by case analysis: > instance A (F FNot) HTrue HFalse > instance A (F FNot) HFalse HTrue The next function is the boolean And. It takes two arguments, so we have to handle currying now. > data FAnd Applying And to an argument makes a closure, waiting for the second argument. > instance A (F FAnd) x (F (FAnd,x)) When we receive the second argument, we are in the position to produce the result. Again, we use the case analysis. > instance A (F (FAnd,HTrue)) a a > instance A (F (FAnd,HFalse)) a HFalse Commonly, abstraction is held to be `more fundamental', which is reflected in the popular phrase `Lambda-the-Ultimate'. In our system, application is fundamental. An abstraction is a not-yet-applied application -- which is in itself a first-class value. The class A defines the meaning of a function, and an instance of A becomes the definition of a function (clause). We have dealt with simple expressions and applicative things. We now build sequences of applications, and define the corresponding big step semantics. We introduce the syntax for applications: > data f :< x > infixl 1 :< and the big-step evaluation function: > class E a b | a -> b Constants evaluate to themselves > instance E HTrue HTrue > instance E HFalse HFalse > instance E Zero Zero Abstractions are values and so evaluate to themselves > instance E (F x) (F x) Familiar rules for applications > instance (E y y', A (F x) y' r) => E ((F x) :< y) r > instance (E (x :< y) r', E (r' :< z) r) => E ((x :< y) :< z) r Other particular rules > instance E x x' => E (Su x) (Su x') That is all. The rest of the message are the tests. The first one is the type-level equivalent of the following function: testb x = and (not x) (not (not x)) At the type level, it looks not much differently: > type Testb x = > E (F FAnd :< (F FNot :< x) :< (F FNot :< (F FNot :< x))) r => r > testb1_t = undefined :: Testb HTrue > testb1_f = undefined :: Testb HFalse We introduce the applicative fixpoint combinator > data Rec l > instance E (l :< (F (Rec l)) :< x) r => A (F (Rec l)) x r and define the sum of two numerals > fix f = f (fix f) > vsum = fix (\self n m -> case n of 0 -> m > (n+1) -> 1 + (self n m)) At the type level, this looks as follows > data FSum' -- first define the non-recursive function > instance A (F FSum') self (F (FSum',self)) > instance A (F (FSum',self)) n (F (FSum',self,n)) -- build closures > instance A (F (FSum',self,Zero)) m m > instance E (self :< n :< m) r => A (F (FSum',self,(Su n))) m (Su r) > type FSum = Rec (F FSum') -- now we tie up the knot After we define a few sample numerals, we can add them > type N0 = Zero; type N1 = Su N0; type N2 = Su N1; type N3 = Su N2 > (n0 :: N0, n1::N1, n2::N2, n3::N3) = undefined > test_sum :: E (F FSum :< x :< y) r => x -> y -> r > test_sum = undefined > > test_sum_2_3 = test_sum n2 n3 *TypeLC> :t test_sum_2_3 test_sum_2_3 :: Su (Su (Su (Su (Su Zero)))) Finally, the standard test -- Fibonacci > vfib = fix(\self n -> case n of 0 -> 1 > 1 -> 1 > (n+2) -> (self n) + (self (n+1))) > data Fib' > instance A (F Fib') self (F (Fib',self)) -- build closure > instance A (F (Fib',self)) Zero (Su Zero) > instance A (F (Fib',self)) (Su Zero) (Su Zero) > instance E (F FSum :< (self :< n) :< (self :< (Su n))) r > => A (F (Fib',self)) (Su (Su n)) r > type Fib = Rec (F Fib') > test_fib :: E (F Fib :< n) r => n -> r > test_fib = undefined > > test_fib_5 = test_fib (test_sum n3 n2) Finally, we demonstrate that our calculus is combinatorially complete, by writing the S and K combinators > data CombK > instance A (F CombK) a (F (CombK,a)) > instance A (F (CombK,a)) b a > > data CombS > instance A (F CombS) f (F (CombS,f)) > instance A (F (CombS,f)) g (F (CombS,f,g)) > instance E (f :< x :< (g :< x)) r => A (F (CombS,f,g)) x r A few examples: SKK as the identity > type Test_skk x = E (F CombS :< F CombK :< F CombK :< x) r => r > test_skk1 = undefined:: Test_skk HTrue and the representation of numerals in the SK calculus. The expression (F FSum :< Su Zero) is a partial application of the function sum to 1. > type CombZ = F CombS :< F CombK > type CombSu = F CombS :< (F CombS :< (F CombK :< F CombS) :< F CombK) > type CombTwo = CombSu :< (CombSu :< CombZ) > test_ctwo :: E (CombTwo :< (F FSum :< Su Zero) :< Zero) r => r > test_ctwo = undefined We define the instances of Show to be able to show things. We define the instances in a way that the value is not required. > instance Show HTrue where show _ = "HTrue" > instance Show HFalse where show _ = "HFalse" > instance Show Zero where show _ = "N0" > instance Show x => Show (Su x) where > show _ = "N" ++ (show (x+1)) > where ('N':xs) = show (undefined::x) > x = (read xs)

1 0

ANN: SmallCheck 0.1
by Colin Runciman 14 Sep '06

14 Sep '06

SmallCheck: another lightweight testing library in Haskell. Folk-law: if there is any case in which a program fails, there is almost always a simple one. SmallCheck is similar to QuickCheck (Claessen and Hughes 2000-) but instead of a sample of randomly generated values, SmallCheck tests properties for all the finitely many values up to some depth, progressively increasing the depth used. For data values, depth means depth of construction. For functional values, it is a measure combining the depth to which arguments may be evaluated and the depth of possible results. Other possible sales pitches: * write test generators for your own types more easily * be sure any counter-examples found are minimal * write properties using existentials as well as universals * establish complete coverage of a defined test-space * display counter-examples of functional type A new version of SmallCheck can be obtained from: http://www.cs.york.ac.uk/fp/smallcheck0.1.tar The differences from 0.0 are two fixes (space-fault, output buffering), an 'unsafe' but sometimes useful Testable (IO a) instance and additional examples. Comments and suggestions welcome. Colin R

2 2

Re: [Haskell] Re: ANN: Haskell98 termination analyzer (AProVE)
by Stephan Swiderski 12 Sep '06

12 Sep '06

Jim Apple wrote: > On 9/11/06, Neil Mitchell <ndmitchell(a)gmail.com> wrote: > > Can you give any examples of terminating Haskell programs that a human > > can analyse (perhaps with a bit of thought), but that your system > > can't? (I couldn't find any in your paper) > > Euclid's algorithm is mentioned on the web page, if I remember correctly. Unfortunately, we are unable to show the termination of the gcd function as definied in the Hugs Prelude. But we could show the termination of this slightly modified version: igcd :: Int -> Int -> Int igcd x y = igcd' (abs x) (abs y) igcd' :: Int -> Int -> Int igcd' 0 x = x igcd' y 0 = y igcd' (x+1) (y+1) | x > y = igcd' (x-y) (y+1) | otherwise = igcd' (y-x) (x+1) So not only the algorithm itself is important; also the way it is written is sometimes essential for proving termination. Best regards, Stephan

1 0

ambiguous (partially defined) type problem / active objects
by Maarten 12 Sep '06

12 Sep '06

Dear all, I'm trying to create active nodes that have a common base part and a user definable custom part, run in their own thread and can communicate/send message to each other. For some reason the compiler complains about an ambiguous type, while I feel, though the type may be partially ambiguous, I'm not using that particular part in related function calls. So in some ways I think there is nothing to complain. Is there a way to resolve this? Are there better/easier solutions to this problem? My solution so far is as follows (see code is below): The active nodes have different types that have a common base state and a changing top state. The base state will be responsible for connection nodes to each other, the top state is user defined. 1. I 'piggy-bag' two State transformers (and IO) onto each other, one with the base state and one with the custom state 2. In their own thread, the top state transformer processes the contents of a list (in which each element is an action) that comes from a channel. 3. The channel is basically the active object and can receive message. 4. Since 'active objects' need to be stored in a list in the base state they are wrapped in a general node data structure (GN) that hides the type of the active object. In this way, actions can be fed to the channel and are executed in the thread and context of the state monad. One can define a changing topstate and add basic functionality to it. This works reasonably well, except that when I store a node into another node (using the base functionality) and later on retrieve it and then want to apply some other suitably typed functions functions using only the base functionality, the compiler complains that the type is ambiguous. However I feel it shouldn't complain, since the functions doesn't use the ambiguous part. Of course the problem is resolved as soon as a function establishes the type. However, in many cases I don't know (and don't want to know the type). Can this be resolved? The code below is unfortunately rather long. Of course it doesn't compile, unless the last comment is removed. If removed it works fine. Any comments and pointers appreciated. Thanks. (I'm quite new to haskell, so I may be missing some obvious things.) Maarten P.S. (Sorry for the long code sample below, but I don't know how to condens is into something smaller, while retaining the relevant properties). {-# OPTIONS -fglasgow-exts -cpp -fallow-undecidable-instances #-} module Main where import Data.Generics import Control.Monad.State import Data.Unique import Control.Concurrent (forkIO, forkOS) import Control.Concurrent.Chan import Control.Concurrent.MVar instance Show Unique where show a = show (hashUnique a) -- default node state; same for all states; nodes are active objects (see below) data DefNodeState = DefNodeState { id::Unique, nodes::ActiveObjects } deriving Show -- make this default state a base state transformer type BaseStateT m = StateT DefNodeState m type BaseStateTIO = BaseStateT IO -- TopStateT with parameterizable state type TopStateT ts a = StateT ts BaseStateTIO a instance Show (TopStateT b ()) where show a = "TopStateT Monad" tsTc = mkTyCon "TopStateT" instance forall ts. (Show ts, Typeable ts) => Typeable1 (StateT ts BaseStateTIO) where typeOf1 _ = mkTyConApp tsTc [] -- hide top state type so we can put them in a list; typeable so it can be cast back data GN = forall o. (Show o,Typeable o) => GN o instance Show (GN) where show (GN o) = "GN " ++ show o gnTc = mkTyCon "GN" instance Typeable GN where typeOf _ = mkTyConApp gnTc [] -- convenience type type ActiveObjects = [GN] -- active objects -- make topstate an active object by putting it in a chan data ActiveObject a = ActiveObject (Chan (TopStateT a ())) -- make active object instance of show instance Show (ActiveObject o) where show o = "ActiveObject Chan StateT" -- make active object typeable activeObjectTc = mkTyCon "ActiveObject" instance Typeable1 ActiveObject where typeOf1 _ = mkTyConApp activeObjectTc [] -- make new active object over some state newActiveObject action state t = do chan <- newChan contents <- getChanContents chan forkIO (start (action contents) state) return (ActiveObject chan) -- send an action if we are not interested in the result send :: forall a . (Typeable a, Show a) => ActiveObject a -> TopStateT a () -> IO () send (ActiveObject chan) act = do writeChan chan act -- sync an action if we are interested in the result sync :: forall a b. (Typeable a, Show a) => ActiveObject a -> TopStateT a b -> IO b sync ao f = do mv <- newEmptyMVar send ao (f' mv) a <- takeMVar mv return a where f' mv = do a <- f lift $ lift $ putMVar mv a class SendSync t where sendM :: forall a. (Typeable a, Show a) => t a -> TopStateT a () -> IO () syncM :: forall a b. (Typeable a, Show a) => t a -> TopStateT a b -> IO b instance SendSync (ActiveObject) where sendM ao m = send ao m syncM ao m = sync ao m {- unforunately doesn't work instance SendSync (GN) where sendM (GN ao) m = sendM ao m syncM (GN ao) m = syncM ao m -} castGN :: forall a. (Show a,Typeable a) => GN -> ActiveObject a castGN (GN o) = mcast o where mcast o = case (cast o) of Nothing -> error "No cast possible" Just a -> a -- some test states for toplevel data TestState = TestState { val::Int } deriving (Show,Typeable) data TestState2 = TestState2 { val2::Int } deriving (Show,Typeable) uid :: forall b. TopStateT b Unique uid = lift $ gets Main.id changeUid :: forall b. Unique -> TopStateT b () changeUid n = do lift $ modify (\s -> s { Main.id = n }) newUid :: forall b. TopStateT b () newUid = do n <- lift $ lift $ newUnique lift $ modify (\s -> s { Main.id = n }) -- add a node to list in basestate addNode :: forall o a. (Typeable a, Show o,Typeable o) => ActiveObject o -> TopStateT a () addNode n = do ns <- lift $ gets nodes lift $ modify (\s -> s { nodes = (GN n):ns }) -- get a node from list in basestate getNode :: forall a o. (Show o,Typeable o) => Integer -> (TopStateT a (ActiveObject o)) getNode i = do ns <- lift $ gets nodes let ao = ns !! (fromInteger i) return (castGN ao) -- action that executes messages send to it action [] = return () action (e:es) = do -- just for testing i <- uid s <- get ns <- lift get lift $ lift $ putStrLn $ "event (" ++ show i ++ "):" ++ " state:" ++ show s ++ " nstate:" ++ show ns -- e action es -- create a new node state with a unique id newNodeState = do u <- newUnique return (DefNodeState u []) -- start evaluation start action state = do ns <- newNodeState execStateT (execStateT action state) ns return () main = do ao <- newActiveObject action (TestState 5) TestState ao2 <- newActiveObject action (TestState2 5) TestState2 -- simple test u1 <- syncM ao (gets val) putStrLn $ "u1:" ++ show u1 -- show complete state r <- syncM ao (get) putStrLn $ show r -- connect ao to ao2 sendM ao (addNode ao2) -- get node back ao2' <- syncM ao (getNode 0) -- get unique id u <- syncM ao2' (uid) putStrLn $ "u:" ++ show (hashUnique u) -- set a new id sendM ao2' (newUid) -- show it u' <- syncM ao2' (uid) putStrLn $ "u':" ++ show (hashUnique u') -- u2 <- syncM ao2' (gets val2) getChar return ()

1 0