- Haskell - Haskell.org

Re: Functional dependencies and Constructor Classes
by Yoann Padioleau 19 Nov '02

19 Nov '02

Martin Sulzmann <sulzmann(a)comp.nus.edu.sg> writes: > Yoann Padioleau writes: > > nevertheless i found constructor class more elegant for many problems. > > Your solution is less elegant that the one using constructor classes. > > > > Yes, the current presentation of constructor classes might be easier > to comprehend. > > > I found too that type error messages of class using functionnal depedencies > > are not easy to read. There is often ambiguity in code that are not easy to solver. > > this problem does not appear with constructor classes. > > > > Well, that's the point of my encoding of functors using FD's. No > ambiguities will arise! > > The issue I want to raise is whether constructor classes are redundant > in the presence of FDs (yes, yes, we still might want to stick to the > constructor class representation, but that's a different issue). Oh, sorry, i misinterpret what you wanted to say. > > Martin > > > -- Yoann Padioleau, INSA de Rennes, France, Opinions expressed here are only mine. Je n'écris qu'à titre personnel. **____ Get Free. Be Smart. Simply use Linux and Free Software. ____**

1 0

Functional dependencies and improvement
by Martin Sulzmann 19 Nov '02

19 Nov '02

Hi, yet again FD's! In my previous example I employed FD's to improve constraints. However, there are cases where FD's seem to be overly restrictive. Take a look at the Haskell code below. Have others made similar experiences? Martin -- FDs are sometimes overly restrictive module Insert where class Insert a b | b -> a where insert :: a->b->b class Leq a where leq :: a->a->Bool instance Leq a => Insert a [a] -- we're not so interested in the values for the purpose of this example -- hugs or ghc will complain about the following instance instance Insert Int [Float] -- though this makes sense! Elements of value Int should allowed to be stored as Floats {- Reason: Improvement in case of FDs seems overly restrictive Consider Mark Jones paper "Type Classes with Functional Dependencies", page 12, Section 6.2. In case of the above type class we require that for each constraint Insert t1 t2 and declaration instance C => Insert t1' t2' where if phi(t2) = t2' then phi(t1) = t1' for some substitution phi. However, we have that phi([a]) = [Float] and phi(a) \not= Int where phi=[a |-> Float]. The problem is that the improvement strategy does not take into account the context in the instance declaration. Solution: We should only improve 'Insert a [b]' to 'Insert b [b]' where phi=[a |-> b] in case we additionally find 'Leq b'. Though, this cannot be specified with FD's. -}

2 1

Functional dependencies and Constructor Classes
by Martin Sulzmann 18 Nov '02

18 Nov '02

Hi, I was wondering whether other people made similiar observations. Functional dependencies seem to be expressiveness enough to encode some of the kinding rules required for Constructor Classes. Take a look at the Haskell code below (runs under hugs -98 or ghci -fglasgow-exts-fallow-undecidable-instances) Martin -- An alternative to constructor classes module Fmap where {- Instead of class Functor f where fmap :: (a->b)->(f a->f b) use -} class Fmap a b fa fb | a fb -> b fa, b fa -> a fb, fa fb -> a b where fmap2 :: (a->b)->(fa -> fb) {- We require: (1) fmap2 transforms a function into another function, i.e. fmap2's type should always be of shape (a->b)->(fa->fb) (2) b, fa uniquely determine a and fb (3) a, fb " b and fa (4) fa, fb " a and b Note that (1) is enforced by the class definition. (2)-(4) are enforced by FDs. My guess/conjecture is that the above axiomatization of functors is equivalent to the one found in Haskell98. -} -- some Examples {- The following is a variation of an example taken from Mark Jones original paper "A System of Constructor Classes: Overloading and Implicit Higher-Order Polymorphism". He used this example to motivate the introduction of constructor classes. The example is type correct using the alternative formulation of functors. -} cmap :: (Fmap a b fb1 fb, Fmap a1 b1 fa fb1) => (a1 -> b1) -> (a -> b) -> fa -> fb cmap f g = (fmap2 g) . (fmap2 f) -- identity functor instance Fmap a a a a where fmap2 h = h -- functor composition -- Instance is not allowed, cause leads to undecidable type inference {- instance (Fmap a b c d, Fmap e f a b) => Fmap e f c d where fmap2 h = fmap2 (fmap2 h) -} comp :: (Fmap fa1 fb1 fa fb, Fmap a b fa1 fb1) => (a -> b) -> fa -> fb comp h = fmap2 (fmap2 h)

1 0

CFP for LDTA 2003: ACM SIGPLAN Workshop
by Pierre-Etienne.Moreau＠loria.fr 18 Nov '02

18 Nov '02

Please apologize if you receive multiple copies of this message. ********************************************************** *** LDTA 2003: ACM SIGPLAN Workshop *** *** APRIL, 6, 2003 *** *** WARSAW, POLAND *** *** *** *** http://www-sop.inria.fr/LDTA2003 *** ********************************************************** Scope: ------ The aim of this one day workshop is to bring together researchers from academia and industry interested in the field of formal language definitions and language technologies, with a special emphasis on tools developed for or with these language definitions. Benefits of such active research fields are, among others: - Program analysis, transformation, generation - Formal analysis of language properties - Automatic generation of language processing tools Although these benefits are well-known, they are in current practices hardly exploited. For example, language definitions can be augmented in a manner that not only compilers/interpreters can be automatically generated but also other tools such as syntax-directed editors, debuggers, partial evaluators, test case generators, documentation generators, etc. Domains of applications that are of interest for this workshop are among others: - Language components, modeling languages - Re-engineering, re-factoring - Aspect-oriented programming, adaptive programming - Domain-specific languages - XML processing - Visualization and graph transformation Invited Talk: ------------- Hassan Ait Kaci, Distinguished Scientist, Research an Development, ILOG, France. Tool demonstrations: -------------------- The one day LDTA 2003 workshop program will also include a session on tool demonstrations. Submission procedure and publication: ------------------------------------- Submission process will be open in autumn 2002. Papers (of at most 15 pages) should be submitted electronically as (optionally compressed/gzipped) PostScript or PDF files to one of the program committee chairs: Barrett Bryant (bryant(a)cis.uab.edu) or Joao Saraiva (jas(a)di.uminho.pt) The message should also contain a text-only abstract and author information. Final copies of accepted papers, after revision, must not be longer than 20 pages and have to respect the proceedings style. Accepted papers will be published and available during the workshop. After revision, final copies of the accepted papers will be published in Electronic Notes in Theoretical Computer Science (ENTCS), Elsevier Science. Author's instructions are given here. The authors of the best papers will be invited to write a journal version of their paper which will be separately reviewed and after acceptance be published in a special issue devoted to LDTA 2003 of the journal Science of Computer Programming (Elsevier Science). Organizing Committee: --------------------- Isabelle Attali, INRIA Sophia Antipolis Mark van den Brand, CWI Amsterdam Pierre-Etienne Moreau, LORIA-INRIA Nancy Program committee co-chairs: ---------------------------- Barrett R. Bryant, University of Alabama at Birmingham, USA Joao Saraiva, University of Minho, Portugal Program Committee members: -------------------------- Don Batory, University Texas / Austin (USA) Uwe Glaesser, Simon Fraser University (Canada) Katsuhiko Gondow, JAIST (Japan) Uwe Kastens, University Paderborn (Germany) Paul Klint, CWI (The Netherlands) Jan Madey, University of Warsaw (Poland) Marjan Mernik, University of Maribor (Slovenia) Thomas Noll, University Aachen (Germany) Oege de Moor, Oxford University Computing Laboratory, (England) Peter D. Mosses, BRICS, University Aarhus (Denmark) Eelco Visser, Utrecht (The Netherlands) ----------------------------------------------------------------------- IMPORTANT DATES ----------------------------------------------------------------------- December 1st 2002 Submission of full paper January 20th 2003 Notification February 15th 2003 Final version due April 6th 2003 LDTA 2003

1 0

first stab at -ffunction-sections
by William Lee Irwin III 17 Nov '02

17 Nov '02

This could be an artifact of the -j64 (BTW, has anyone else noticed the makefiles can only keep 5 or 6 cpus busy at a time much of the time, and often less?). gcc -O -ffunction-sections -c Text/Regex/Posix_hsc.c -o Text/Regex/Posix_hsc.o Text/ParserCombinators/Parsec/Pos.hs:15: failed to load interface for `Prelude': Bad interface file: /mnt/h/tmp/ghc5-5.04/build-stage1/libraries/base/Prelude.hi does not exist Action: openFileEx Reason: No such file or directory File: /mnt/h/tmp/ghc5-5.04/build-stage1/libraries/base/Prelude.hi make[4]: *** [Text/ParserCombinators/Parsec/Pos.o] Error 1 make[4]: *** Waiting for unfinished jobs.... GHC/PrimopWrappers.hs:2: failed to load interface for `GHC.Base': Bad interface file: /mnt/h/tmp/ghc5-5.04/build-stage1/libraries/base/GHC/Base.hi does not exist Action: openFileEx Reason: No such file or directory File: /mnt/h/tmp/ghc5-5.04/build-stage1/libraries/base/GHC/Base.hi GHC/PrimopWrappers.hs:2: Failed to find interface decl for `GHC.Base.eqString' from module `GHC.Base' GHC/PrimopWrappers.hs:2: Failed to find interface decl for `GHC.Base.unpackCStringUtf8#' from module `GHC.Base' GHC/PrimopWrappers.hs:2: Failed to find interface decl for `GHC.Base.unpackFoldrCString#' from module `GHC.Base' GHC/PrimopWrappers.hs:2: Failed to find interface decl for `GHC.Base.unpackCString#' from module `GHC.Base' make[4]: *** [GHC/PrimopWrappers.o] Error 1 make[3]: *** [all] Error 1 make[3]: Leaving directory `/mnt/h/tmp/ghc5-5.04/build-stage1/libraries' make[2]: *** [all] Error 1 make[2]: Leaving directory `/mnt/h/tmp/ghc5-5.04/build-stage1' make[1]: *** [build-stage1] Error 2 make[1]: Leaving directory `/mnt/h/tmp/ghc5-5.04' make: *** [stamps/build-stamp] Error 2 debuild: fatal error at line 456: dpkg-buildpackage failed!

1 0

RFC822 date strings vs. current practice
by William Lee Irwin III 17 Nov '02

17 Nov '02

These don't appear to actually show up as mailers commonly format them: e.g.: Cc: linux-kernel(a)vger.kernel.org, trivial(a)rustcorp.com.au From: Olaf Dietsche <olaf.dietsche%23list.linux-kernel(a)t-online.de> To: Chris Wedgwood <cw(a)f00f.org> Subject: Re: [PATCH] 2.5.47: strdup() Date: Sun, 17 Nov 2002 02:37:27 +0100 The implementation in Time.lhs appears to follow the RFC to the letter, which doesn't match current practice. The following appears to match current practice somewhat more closely: genDate = do t <- getClockTime c <- toCalendarTime t let gmtOff = ctTZ c `div` 36 let gmtSgn = gmtOff >= 0 let gmtAbs = abs gmtOff let hrStr = (if gmtOff < 0 then "-" else "+") ++ (if gmtAbs < 10 00 then "0" else "") ++ show gmtAbs return $ (formatCalendarTime defaultTimeLocale "%a, %_d %b %Y %H :%M:%S " c) ++ hrStr

1 0

Running out of memory in a simple program
by Magnus Lindberg 15 Nov '02

15 Nov '02

{- Hi! I have a problem with monads. When a monadic function calls itself many times (see below) Hugs and GHCi runs out of memory/stack, and I can't see why. This is my program (well, I've kind of sipmlified it a lot :): -} newtype M a = M (Int -> (a,Int)) instance Monad M where return x = M $ \i -> (x,i) M f >>= k = M $ \i -> let (x,i2) = f i M f2 = k x in f2 i2 inc 0 = return () inc n = do inc'; inc (n-1) where inc' = M $ \i -> ((), i+1) runM :: M () -> IO () runM (M m) = print (m 0) -- in print i run n = runM (inc n) -- crashes for large n !! {- Shouldn't `run n' work for any n? But if I use n over 20 000 (or something) Hugs says "error: couldn't retreive enough memory when garabae-collecting" (or something), and other times Windows 2000 says "unknown software exception 0xc000000fd at 0x00040ec01". I tested to add "continuation passing style" (I don't really know what I should do) but that didn't work either. Does anyone have an idea of what the error is and what I should do / not do? Best regards, Magnus Lindberg -}

3 3

Euro-Par 2003, Topic 10 (CfP)
by Ch. A. Herrmann 15 Nov '02

15 Nov '02

Dear Haskellers, many of you are using Haskell as a tool for developing parallel programs, are working on parallelizing Haskell compilers, language extensions, or interfaces. If you are involved in parallel programming, I'd strongly encourage you to submit a paper to Topic 10 of Euro-Par 2003. It'll be a good forum to present your work. Apologies if you receive multiple copies of this message. ----------------------------------------------------------------------- ****************************************************** *** *** *** CALL FOR PAPERS *** *** Submission Deadline: February 9, 2003 *** *** *** *** EURO-PAR 2003 Topic 10 *** *** Parallel Programming: Models, Methods and *** *** Programming Languages *** *** *** *** Klagenfurt, Austria *** *** August 26-29, 2003 *** *** *** *** http://europar-itec.uni-klu.ac.at/ *** *** *** ****************************************************** Description This topic provides a forum for the presentation of the latest research results and practical experience in the development of parallel programs. Advances in algorithmic and programming models, design methods, languages, and interfaces are needed to produce correct, portable parallel software with predictable performance on different parallel and distributed architectures. The topic emphasises results that improve the process of developing high-performance programs, including high-integrity programs that are scalable with both problem size and complexity. Of particular interest are novel techniques by which parallel software can be assembled from reusable parallel components without compromising efficiency. Related to this is the need for parallel software to adapt, both to available resources and to the problem being solved. Where appropriate, contributions should demonstrate quantitative performance results in support of their claims, and address applications not adequately handled by well-established approaches. Focus * Languages, libraries and interfaces for different parallel programming models (e.g. data-parallelism, task-parallelism, functional, object-oriented, logic, component-based etc.). * Implementation and optimisation techniques for innovative parallel languages and programming models (e.g. threads, dataflow, tiling, skeletons, declarative languages, and generalised data-parallel approaches, etc.). * Performance models and their integration into the design of efficient parallel algorithms and programs (e.g. BSP, LogP, CGM, N-half and their alternatives, cost calculi and static performance prediction, profile-driven approaches). * Parallel programming paradigms and tools, their comparison and integration (e.g. data-parallel vs. task-parallel, coordination programming, performance analysis and debugging). * Methodological aspects of developing, optimizing and validating parallel programs (formalisms, semantics, specification, design, transformations, verification, etc.). * Software engineering for parallel and distributed systems (design patterns, portability, robustness, standardization, etc.). * Systematic approaches and programming models to support effective program development in grid environments. * Domain-specific parallel libraries and languages (e.g. for simulation, irregular and unstructured meshes, computational geometry, etc.). ----------------------------------------------------------------------- KEY DATES November 8, 2002 First call for papers February 9, 2003 Final date for submissions May 1, 2003 Notification of acceptance July 15, 2003 Early registration deadline ----------------------------------------------------------------------- PC COMMITTEE Global Chair Prof. José C. Cunha New University of Lisbon, Portugal Email: jcc(a)di.fct.unl.pt Vice Chairs Dr. Marco Danelutto University of Pisa, Italy Email: marcod(a)di.unipi.it Prof. Peter H. Welch University of Kent, United Kingdom Email: P.H.Welch(a)ukc.ac.uk Local Chair Dr. Christoph Herrmann Universität Passau, Germany Email: herrmann(a)fmi.uni-passau.de ----------------------------------------------------------------------- SUBMISSION DETAILS Authors are requested to submit their papers by using our submission site http://europar-itec.uni-klu.ac.at/submission.html (please indicate TOPIC 10). The site will open not later than at the beginning of January 2003. All accepted papers will be available at the conference in the proceedings published by Springer-Verlag in the LNCS series. ----------------------------------------------------------------------- MISSION STATEMENT EURO-PAR Euro-Par is the annual series of international conferences dedicated to the promotion and advancement of all aspects of parallel and distributed computing. Euro-Par 2003 will represent 19 topics in the categories of hardware, software, algorithms and applications. The conference normally attracts more than 300 participants coming from universities, research centres and industry. ---------------------------------------------------------------------- We are looking forward to receiving your paper submissions. Best regards -- Dr. Christoph Herrmann Teaching and Research Assistant University of Passau, Germany http://www.fmi.uni-passau.de/~herrmann

1 0

Re: Time library underspecified
by George Russell 15 Nov '02

15 Nov '02

The TimeExts library probably does most of what you want. I really ought to Haddockify the comments some time . . .

1 0

Implementing forward refs in monadic assembler and interpreter
by Mike Gunter 15 Nov '02

15 Nov '02

I need to implement an assembler and interpreter for a simple instruction set. For example, this code \begin{code} compute112 = do { zero r1 ; zero r2 ; addi r2 3 -- loop three times ;topLoop <- label ; addi r1 4 ; addi r2 (-1) -- decrement loop counter ; brPositive r2 topLoop ; add r1 100 } \end{code} would result in register r1 having a value 112. Without forward branches, the implementation is reasonably straightforward. The assembler can use a Monad with state and writer capabilities. The interpreter can use a continuation monad to implement branches and a state monad for the machine state. However, forward branches make things harder. I'd like to be able to write something along the lines of: \begin{code} compute12 = mdo { zero r1 ; zero r2 ; addi r2 3 -- loop three times ;topLoop <- label ; addi r1 4 ; addi r2 (-1) -- decrement loop counter ; brPositive r2 topLoop ; mov r3 r1 ; addi r3 (-10) -- !!! Forward branch: ; brPositive r3 out -- if r1 > 10 don't add 100 ; add r1 100 ;out <- label } \end{code} but it's not clear to me how to implement it. I'd be willing to accept a somewhat less clean version (for instance, with more cumbersome forward references.) Any help would be greatly appreciated. thanks, mike

5 4