- Haskell - Haskell.org

RE: Typesafe MRef with a regular monad
by Simon Peyton-Jones 24 Jun '03

24 Jun '03

You can't overwrite an entry with a value of a different type, because the keys are typed! Any more than you can overwrite an IORef with a value of a different type. S | -----Original Message----- | From: Ralf Hinze [mailto:ralf@informatik.uni-bonn.de] | Sent: 06 June 2003 15:01 | To: Simon Peyton-Jones; Tim Sweeney; haskell(a)haskell.org; Ashley Yakeley | Subject: Re: Typesafe MRef with a regular monad | | Am Freitag, 6. Juni 2003 15:47 schrieb Simon Peyton-Jones: | > Yes, one *could* use dynamic types. But the check would always succeed! | | Why is that? If I overwrite an entry with a value of a different type, | then the check fails. I am certainly missing something ... | | Cheers, Ralf |

4 3

ANNOUNCE: Cryptographic Library for Haskell
by Dominic Steinitz 23 Jun '03

23 Jun '03

I would like to annouce the first release of the Haskell Cryptographic Library (0.2.0). See http://www.haskell.org/crypto/ReadMe.html for more details. This library collects together existing Haskell cryptographic functions and augments them so that they: · Have common type signatures. · Can be used with the standard mode and padding algorithms (in the case of block mode ciphers). This very initial release contains: · DES · Blowfish · Cipher Block Chaining (CBC) mode · PKCS#5 and nulls padding Dominic Steinitz

2 1

RE: main modules in GHC
by Simon Peyton-Jones 23 Jun '03

23 Jun '03

| >I've implemented a -main-is flag for GHC, so you can nominate either the | >module containing the main function, or the main function name, or both. | | I take it that's not yet a released compiler version? (I'm currently using | 5.4.03, and expect to upgrade at some time after the generics support is | felt to be reasonably stable and also supported by Hugs.) Correct. It'll be in 6.2. Till then, you can use a development snapshot (once a nightly build on the HEAD goes through) S

1 0

RE: main modules in GHC
by Graham Klyne 23 Jun '03

23 Jun '03

At 11:37 23/06/03 +0100, Simon Peyton-Jones wrote: >The question of conveniently naming a function to use as the 'main' >function has come before. >I've implemented a -main-is flag for GHC, so you can nominate either the >module containing the main function, or the main function name, or both. That sounds most helpful, thank you. (For me, nominating the module is enough.) >The change is in the repository, and it's documented in the manual. I >hope this'll help the test-suite folk. I take it that's not yet a released compiler version? (I'm currently using 5.4.03, and expect to upgrade at some time after the generics support is felt to be reasonably stable and also supported by Hugs.) #g ------------------- Graham Klyne <GK(a)NineByNine.org> PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E

1 0

RE: main modules in GHC
by Simon Peyton-Jones 23 Jun '03

23 Jun '03

The question of conveniently naming a function to use as the 'main' function has come before. I've implemented a -main-is flag for GHC, so you can nominate either the module containing the main function, or the main function name, or both. The change is in the repository, and it's documented in the manual. I hope this'll help the test-suite folk. Simon | -----Original Message----- | From: haskell-admin(a)haskell.org [mailto:haskell-admin@haskell.org] On Behalf Of Hal Daume III | Sent: 13 June 2003 21:07 | To: Matthew Donadio | Cc: Graham Klyne; Haskell Mailing List | Subject: Re: main modules in GHC, deriving differences between GHC and Hugs | | Yes, but there's a problem with this solution. Namely, if Foo.hs takes a | long time to compile, then you can't leverage having already created Foo.o | and Foo.hi when making the Main. | | The solution I use is a script that you call like: | | ghcmake File | | which creates MainXXX.hs (where XXX is a random number) and this contains: | | module Main where { import qualified File (main) ; main = File.main } | | It then runs ghc --make on that and deletes the MainXXX.hs file. | | This works okay, but isn't very satisfactory. | | Personally, I think this is stupid and that you should be able to compile | any module with a 'main :: IO a' function as an executable without having | to call it Main. You can probably find a message from me to this extent | in the archives, as well as some response. | | - Hal | | -- | Hal Daume III | hdaume(a)isi.edu | "Arrest this man, he talks in maths." | www.isi.edu/~hdaume | | On Fri, 13 Jun 2003, Matthew Donadio wrote: | | > Graham Klyne wrote: | > > GHC seems to require a 'main' module in a file in order to generate an exe | > > file. This makes it awkward to create unit test programs, because I | > > generally create one (to run stand-alone) for each major module. Now I | > > want to create a "master test" module that runs all the individual module | > > tests. But if the module tests are all "main" modules it seems I cannot | > > bring them all together into a larger program. Have I overlooked any way | > > to create an executable program from any module containing a main function | > > of the appropriate type? | > | > The easiest way to handle this is to run all the source through the C | > preprocessor, and put #ifdef's around main and the module name. | > Something like | > | > #ifdef UNIT_TEST | > module Main where | > #else | > module Foo where | > #endif | > | > foo x y = x + y | > | > tests = [ foo 2 3 == 5, | > foo 3 4 /= 6 | > ] | > | > #ifdef UNIT_TEST | > main = print $ and tests | > #else | > foo_test = and tests | > #endif | > | > I haven't done this with Haskell, but I have done it with a lot of my C | > libraries. | > | > -- | > Matthew Donadio (m.p.donadio(a)ieee.org) | > _______________________________________________ | > Haskell mailing list | > Haskell(a)haskell.org | > http://www.haskell.org/mailman/listinfo/haskell | > | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell

1 0

Language-Independent Arithmetic
by Ashley Yakeley 23 Jun '03

23 Jun '03

>From the Haskell 98 Report, sec. 6.4: "The default floating point operations defined by the Haskell Prelude do not conform to current language independent arithmetic (LIA) standards. These standards require considerably more complexity in the numeric structure and have thus been relegated to a library." Is this true? Which library? -- Ashley Yakeley, Seattle WA

3 2

Re: Overlapping instances in existentials
by oleg＠pobox.com 21 Jun '03

21 Jun '03

Ed Komp replied to Simon Peyton-Jones: > Within the GHC compiler > > can't be instantiated to Double --- but that's tricky to pin down. > this may be tricky to pin down. > But, there is specific information in my example to exclude Double: > I had carefully constructed the type definitions to avoid > ambiguity. Indeed, the open world assumption makes it rather difficult to define a constraint that two type variables must denote different types. I wish it were possible to easily write forall a b. (NotEq a b) => ... Functional dependencies can be used to achieve a similar effect -- but sometimes that are not applicable. I wish there were a way to assert to the compiler that there will be no more instances of a specific class. The compiler can record this assumption in the object file. When the compiler builds the final executable and finds an unexpected instance, the compiler can tell the user that he lied. > | class SubType a b where > | inj :: a -> b > | prj :: b -> Maybe a > | > | instance SubType a (Either a x) where > | inj =3D Left > | prj =3D either Just (const Nothing) > | > | instance (SubType a b) =3D> SubType a (Either x b) where > | inj =3D Right . inj > | prj =3D either (const Nothing) prj > | > | type BaseType = Either Integer ( Either Bool () ) > | > | type Value = (Either Double BaseType) > | > | data Foo = forall x. (SubType x BaseType) => MkFoo x > | > | test :: Foo -> Value > | test (MkFoo x) = inj x I'm quite dubious that test can be typed at all (see below). Even if the problem with overlapping instances could be solved. I seem to remember being on this road before. I'd be great to get GHC to run the typechecker at run time, to choose the right instance. Alas. In the example above, the constraint on Foo only guarantees (SubType x BaseType). When we create MkFoo True, for example, the compiler knows the type the value being encapsulated, chooses the right instance (that is, the dictionary), and places the dictionary and the value into the MkFoo envelope. The function test executes "inj x" whose return type is different from the BaseType. that is, 'inj' implicitly has the constraint (SubType x Value). However, MkFoo x only guarantees (SubType x BaseType). This is not a technicality. Let us disambiguate the instances and remove all overlapping: > class SubType a b where > inj :: a -> b > prj :: b -> Maybe a > instance SubType Bool (Either Bool x) where > inj = Left > prj = either Just (const Nothing) > instance SubType Integer (Either Integer x) where > inj = Left > prj = either Just (const Nothing) > instance (SubType Bool b) => SubType Bool (Either Integer b) where > inj = Right . inj > prj = either (const Nothing) prj > instance (SubType Bool b) => SubType Bool (Either Double b) where > inj = Right . inj > prj = either (const Nothing) prj > instance (SubType Integer b) => SubType Integer (Either Double b) where > inj = Right . inj > prj = either (const Nothing) prj > type BaseType = Either Integer ( Either Bool () ) > type Value = (Either Double BaseType) > data Foo = forall x. (SubType x BaseType) => MkFoo x > -- test :: Foo -> Value > -- test (MkFoo x) = inj x > test1 :: Foo -> BaseType > test1 (MkFoo x) = inj x This code types and even runs: *> test1 $ MkFoo True *> Right (Left True) Indeed, when the compiler sees MkFoo True, it chooses the right instance of the class (SubType x BaseType), and packs the corresponding dictionary into MkFoo. When we run test1 $ MkFoo True, the compiler extracts the dictionary from MkFoo, extracts the field inj from that dictionary, and runs the corresponding procedure. At this time (at run time), the compiler does not and cannot choose instances. If we uncomment the procedure test above, we predictably get the error: /tmp/k2.hs:32: Could not deduce (SubType x Value) from the context (SubType x BaseType) Probable fix: Add (SubType x Value) to the existential context of a data constructor Or add an instance declaration for (SubType x Value) arising from use of `inj' at /tmp/k2.hs:32 In the definition of `test': inj x As we saw above, we cannot widen the constraint at the run time. The function test wants to use a different function inj -- not the one associated with (SubType Bool BaseType) -- the chosen instance -- but a different one, associated with an instance (SubType Bool Value). However, we cannot chose the instance at that time because the compiler does not know the exact type of the value in the existential envelope. To do as you wish, the compiler would have had to compile the typechhecer into the target executable code. Not that it would be a bad idea.

1 0

Overlapping instances in existentials
by Simon Peyton-Jones 20 Jun '03

20 Jun '03

[I'm widening this to the Haskell list, because overlapping instances are of general interest.] | To determine (SubType y Value) which is just: | (SubType y (Either Double BaseType)) | | it seems to me that GHC should (has to?) use | instance (SubType a b) => SubType a (Either x b) | | I do not see how the other alternative is applicable: | instance SubType a (Either a x) Well, the "target" (Subtype y (Either Double BaseType)) can match against *both* of these instances. It can match instance (SubType a b) => SubType a (Either x b) by taking a=y, x=Double, b=BaseType *If y were instantiated to Double* it could match the second instance declaration too. Now, you say, y is an existential type variable, so it can't be instantiated to Double --- but that's tricky to pin down. Consider: class Show a where show :: a -> String instance Show a => Show [a] where... instance Show [Char] where... f :: Show a => [a] -> String f xs = show xs main = print (f "hello") When doing type inference for 'f' we don't know what 'a' will be instantiated to. Picking the first is arguably wrong if f is called at type String (as it is here). So GHC and Hugs both bleat. Now your situation is an *existential* type variable, not a universal one. But still, if y *was* Double in a particular situation, then the other instance decl "should" apply, perhaps. Or maybe not. GHC simply does not have a satisfactory solution to the overlapping-instance question. Nor, I think, does Hugs. A good start would be for someone to write a "guide to the problems/design-space of overlapping instances". (There is a ton of back email on the Haskell list about this as raw material.) People regularly ask for extensions and/or changes to the way GHC deals with overlap, which I mostly resist, not purely out of laziness -- it's just that I don't want to meddle until we can move to something that is plainly better. I enclose a long comment from GHC's source code that Jeff Lewis wrote on this topic too. Sorry not to be more helpful. It's a bit of a swamp. Simon > | >> test.hs:26: > | >> Could not unambiguously deduce (SubType x Value) > | >> from the context (SubType x BaseType) > | >> The choice of (overlapping) instance declaration > | >> depends on the instantiation of `x' > | >> Probable fix: > | >> Add (SubType x Value) > | >> to the existential context of a data constructor > | >> Or add an instance declaration for (SubType x Value) > | >> arising from use of `inj' at test.hs:26 > | >> In the definition of `test': inj x > | >> Failed, modules loaded: none. > | >> Prelude> > | > | > | -- ----------------------------------------------------------- > | -- test.hs > | -- ----------------------------------------------------------- > | module Test where > | > | import Control.Monad.Error > | > | class SubType a b where > | inj :: a -> b > | prj :: b -> Maybe a > | > | instance SubType a (Either a x) where > | inj = Left > | prj = either Just (const Nothing) > | > | instance (SubType a b) => SubType a (Either x b) where > | inj = Right . inj > | prj = either (const Nothing) prj > | > | -- ----------------------------------------------------------- > | > | type BaseType = Either Integer ( Either Bool () ) > | > | type Value = (Either Double BaseType) > | > | data Foo = forall x. (SubType x BaseType) => MkFoo x > | > | test :: Foo -> Value > | test (MkFoo x) = inj x \subsection{Avoiding a problem with overlapping} Consider this little program: \begin{pseudocode} class C a where c :: a class C a => D a where d :: a instance C Int where c = 17 instance D Int where d = 13 instance C a => C [a] where c = [c] instance ({- C [a], -} D a) => D [a] where d = c instance C [Int] where c = [37] main = print (d :: [Int]) \end{pseudocode} What do you think `main' prints (assuming we have overlapping instances, and all that turned on)? Well, the instance for `D' at type `[a]' is defined to be `c' at the same type, and we've got an instance of `C' at `[Int]', so the answer is `[37]', right? (the generic `C [a]' instance shouldn't apply because the `C [Int]' instance is more specific). Ghc-4.04 gives `[37]', while ghc-4.06 gives `[17]', so 4.06 is wrong. That was easy ;-) Let's just consult hugs for good measure. Wait - if I use old hugs (pre-September99), I get `[17]', and stranger yet, if I use hugs98, it doesn't even compile! What's going on!? What hugs complains about is the `D [a]' instance decl. \begin{pseudocode} ERROR "mj.hs" (line 10): Cannot build superclass instance *** Instance : D [a] *** Context supplied : D a *** Required superclass : C [a] \end{pseudocode} You might wonder what hugs is complaining about. It's saying that you need to add `C [a]' to the context of the `D [a]' instance (as appears in comments). But there's that `C [a]' instance decl one line above that says that I can reduce the need for a `C [a]' instance to the need for a `C a' instance, and in this case, I already have the necessary `C a' instance (since we have `D a' explicitly in the context, and `C' is a superclass of `D'). Unfortunately, the above reasoning indicates a premature commitment to the generic `C [a]' instance. I.e., it prematurely rules out the more specific instance `C [Int]'. This is the mistake that ghc-4.06 makes. The fix is to add the context that hugs suggests (uncomment the `C [a]'), effectively deferring the decision about which instance to use. So, what's the fix? I think hugs has it right. Here's why. Let's try something else out with ghc-4.04. Let's add the following line: d' :: D a => [a] d' = c Everyone raise their hand who thinks that `d :: [Int]' should give a different answer from `d' :: [Int]'. Well, in ghc-4.04, it does. The `optimization' only applies to instance decls, not to regular bindings, giving inconsistent behavior. Old hugs had this same bug. Here's how we fixed it: like GHC, the list of instances for a given class is ordered, so that more specific instances come before more generic ones. For example, the instance list for C might contain: ..., C Int, ..., C a, ... When we go to look for a `C Int' instance we'll get that one first. But what if we go looking for a `C b' (`b' is unconstrained)? We'll pass the `C Int' instance, and keep going. But if `b' is unconstrained, then we don't know yet if the more specific instance will eventually apply. GHC keeps going, and matches on the generic `C a'. The fix is to, at each step, check to see if there's a reverse match, and if so, abort the search. This prevents hugs from prematurely chosing a generic instance when a more specific one exists. --Jeff BUT NOTE [Nov 2001]: we must actually *unify* not reverse-match in this test. Suppose the instance envt had ..., forall a b. C a a b, ..., forall a b c. C a b c, ... (still most specific first) Now suppose we are looking for (C x y Int), where x and y are unconstrained. C x y Int doesn't match the template {a,b} C a a b but neither does C a a b match the template {x,y} C x y Int But still x and y might subsequently be unified so they *do* match. Simple story: unify, don't match.

4 3

RE: stack space overflow
by Hal Daume 20 Jun '03

20 Jun '03

Seems to work for me. I changed it a bit (I believe you meant 'len ar' on the first line, with the following defintion of 'len': len = (1+) . uncurry (flip (-)) . bounds , but other than that, I left your code as it is). Can you provide input on which it fails? It works for me on large input like: *Main> ind 1 "foo" $ listArray (1,10000) (concat $ repeat "abcfoodefgfooa") even in ghci. -- Hal Daume III | hdaume(a)isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume > -----Original Message----- > From: haskell-admin(a)haskell.org > [mailto:haskell-admin@haskell.org] On Behalf Of Ketil Z. Malde > Sent: Friday, June 20, 2003 7:05 AM > To: haskell(a)haskell.org > Subject: stack space overflow > > > > Hi, > > I have a small function to find all indices in an array where a given > subword can be found, looking like this: > > > ind i ws ar > > | i+length ws-1 > len e = [] > > | and [ar!(i+j) == ws!!j | j<-[0..length ws-1]] = i : ind > (i+1) ws ar > > | otherwise = ind (i+1) ws ar > > (i::Int is the position, ws::[a] is the word to look for, while > ar::Array Int a is the array wherein to look) > > This occasionally blows up with a stack overflow, perhaps I'm being > dense, but I'm not sure why. Any suggestions? > > BTW, is there a general way to track down stack overflows? I use the > -xc option, are there any other tricks I should know about? And does > heap profiling (GHC) imply more stack usage -- I seem to get overflows > much more easily when profiling. > > -kzm > -- > If I haven't seen further, it is by standing in the > footprints of giants > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell >

1 0

WRLA 2004 - Call for papers
by alberto＠sip.ucm.es 20 Jun '03

20 Jun '03

[[ -- Apologies for multiple copies of this message -- ]] + + + + + WRLA'04 + + + + + CALL FOR PAPERS + + + + + WRLA'04 + + + + + +----------------------------------------------------------+ | | | 5th International Workshop on | | Rewriting Logic and its Applications | | | | W R L A 2004 | | | | Barcelona, Spain, March 27-28, 2004 | | | | http://www.fdi.ucm.es/wrla2004 | +----------------------------------------------------------+ The workshop will be held in conjunction with ETAPS 2004 7th European Joint Conferences on Theory and Practice of Software March 27 - April 4, 2004 http://www.lsi.upc.es/etaps04 IMPORTANT DATES November 24, 2003 Deadline for submission January 15, 2004 Notification of acceptance February 18, 2004 Final version in electronic form March 27-28, 2004 Workshop in Barcelona AIMS AND SCOPE Rewriting logic (RL) is a natural model of computation and an expressive semantic framework for concurrency, parallelism, communication and interaction. It can be used for specifying a wide range of systems and languages in various application fields. It also has good properties as a metalogical framework for representing logics. In recent years, several languages based on RL (ASF+SDF, CafeOBJ, ELAN, Maude) have been designed and implemented. The aim of the workshop is to bring together researchers with a common interest in RL and its applications, and to give them the opportunity to present their recent works, discuss future research directions, and exchange ideas. The topics of the workshop comprise, but are not limited to, * foundations and models of RL; * languages based on RL, including implementation issues; * RL as a logical framework; * RL as a semantic framework, including applications of RL to - object-oriented systems, - concurrent and/or parallel systems, - interactive, distributed, open ended and mobile systems, - specification of languages and systems; * extensions of RL, including - real-time and probabilistic extensions, - tile logic, - rewriting approaches to behavioral specifications; * verification techniques for RL specifications, including - equational and coherence methods, and - verification of properties expressed in modal and temporal logics; * comparisons of RL with existing formalisms having analogous aims, including - rho-calculus, - structural operational semantics, - concurrency calculi, - dynamic algebras. PAST EVENTS Previous WRLA workshops have been organized in - Asilomar, California, September 3-6, 1996, - Pont-a-Mousson, France, September 1-4, 1998, - Kanazawa, Japan, September 18-20, 2000, - Pisa, Italy, September 19-21, 2002. The proceedings of the WRLA workshops have been published as volumes 4, 15, 36, and 71 in the Elsevier ENTCS series, available at http://www.elsevier.nl/locate/entcs Selected papers from WRLA'96 have been published in a special issue of Theoretical Computer Science, Volume 285(2), 2002. LOCATION WRLA 2004 will be held in Barcelona, Spain in March 27-28, 2004. It is a satellite workshop of ETAPS 2004, the European Joint Conferences on Theory and Practice of Software. For venue, registration and suggested accommodation see the ETAPS 2004 web page http://www.lsi.upc.es/etaps04 For information about Barcelona, see among others the city web page http://www.bcn.es/english/ihome.htm PROGRAM COMMITTEE David Basin ETH Zurich Manuel Clavel Universidad Complutense de Madrid Steven Eker SRI International, Menlo Park Kokichi Futatsugi JAIST, Tatsunokuchi Fabio Gadducci Universita di Pisa Alexander Knapp LMU, Muenchen Claude Kirchner INRIA Lorraine & LORIA, Nancy Salvador Lucas Universidad Politecnica de Valencia Narciso Marti-Oliet Universidad Complutense de Madrid (Chair) Jose Meseguer University of Illinois at Urbana-Champaign Ugo Montanari Universita di Pisa Pierre-Etienne Moreau INRIA Lorraine & LORIA, Nancy Grigore Rosu University of Illinois at Urbana-Champaign Carolyn Talcott SRI International, Menlo Park SUBMISSIONS Submissions will be evaluated by the Program Committee for inclusion in the proceedings, which will be available at the time of the workshop and are expected to be published in the Elsevier ENTCS series. Papers must contain original contributions, be clearly written, and include appropriate reference to and comparison with related work. They must be unpublished and not submitted simultaneously for publication elsewhere. Papers (of at most 15 pages) should be submitted electronically, preferably as PDF files, to the workshop email address wrla2004(a)sip.ucm.es providing also a text-only abstract, and detailed contact information of the corresponding author. The final program of the workshop will also include system demonstrations and two invited presentations by Gilles Dowek Ecole Polytechnique & INRIA, Palaiseau Mario Rodriguez-Artalejo Universidad Complutense de Madrid Based on the quality and interest of the accepted papers, the program committee will study the possibility of preparing a special issue of a scientific journal in the field. ORGANIZING COMMITTEE Narciso Marti-Oliet, Manuel Clavel, and Alberto Verdejo Departamento de Sistemas Informaticos y Programacion Universidad Complutense de Madrid, Spain CONTACT INFORMATION For more information, please contact the organizers wrla2004(a)sip.ucm.es or visit the workshop web page http://www.fdi.ucm.es/wrla2004 IMPORTANT DATES November 24, 2003 Deadline for submission January 15, 2004 Notification of acceptance February 18, 2004 Final version in electronic form March 27-28, 2004 Workshop in Barcelona + + + + + WRLA'04 + + + + + CALL FOR PAPERS + + + + + WRLA'04 + + + + +

1 0