June 2004 - Haskell - Haskell.org

final cfp: soft2004
by Stefano Bistarelli 21 Jun '04

21 Jun '04

============================================================================ ======= 6th International Workshop on Soft Constraints and Preferences September 27th, 2004 Toronto, Canada Held in conjunction with 10th International Conference on Principles and Practice of Constraint Programming, CP2004 http://www.sci.unich.it/~bista/organizing/soft-2004/ ============================================================================ ======== Call for Paper ============================================================================ ======== Preferences are ubiquitous in real life: most problems are over-constrained and would not be solvable if we insist that all their requirements are strictly met. Moreover, many problems are more naturally described via preference rather than hard statements. Soft constraints are the way the constraint community has extended his classical framework to deal with the conceept of preferences. However, other frameworks for expressing preferences have been proposed in the last few years in AI or related disciplines, with different features and leading to different results. For example, both qualitative and quantitative preference frameworks are being studied and used to model and solve real-life probleems. This workshop would like to bring together researchers interested in all aspects of preferences and soft constraints, such as: - theoretical frameworks - problem modeling - solving algorithms - languages - preference aggregation - preference elicitation - multi-objective or qualitative optimization - combining/integrating different frameworks and algorithms - comparative studies - real-life applications Submissions This workshop is intended to build on the experience and success of the workshops on soft constraints that have been held at CP99, CP2000, CP2001, CP2002 and CP2003, and on the AAAI 2002 workshop on preferences in AI and CP. Its aim is to provide a forum where researchers currently working in the area of preferences or soft constraints can discuss their most recent ideas and developments and think together about the most promising new directions. Therefore we encourage the presentation of work in progress or on specialized aspects of soft constraints. Papers that bridge the gap between theory and practice are especially welcome. Prospective attendees can submit a paper, which can be up to 15 pages in length. We encourage authors to submit papers electronically in postscript or pdf format. Papers should be formatted using the Lecture Notes in Computer Science (LNCS) style. Please send your submissions by email to stefano.bistarelli(a)iit.cnr.it using the subject line Soft-2004 Workshop Submission. Although no agreement is yet in place, we will consider the publication of a selection of papers presented at this workshop in a special issue of a journal or in a volume of a serie. Important Dates The proposed schedule of important dates for the workshop is as follows: Paper Submission deadline June 26th Notification of acceptance July 24th Camera-ready version deadline August 14th Workshop Date September 27th Workshop Organizers: Stefano Bistarelli (Primary Contact) Dipartimento di Scienze Università degli studi "G. D'Annunzio" di Chieti-Pescara, Italy Email: bista(a)sci.unich.it Web: http://www.sci.unich.it/~bista/ and Istituto di Informatica e Telematica C.N.R. Pisa, Italy Email: stefano.bistarelli(a)iit.cnr.it and Francesca Rossi Dipartimento di Matematica Pura ed Applicata Universita' degli Studi di Padova, Italy Email: frossi(a)math.unipd.it Web: http://www.math.unipd.it/~frossi/ Program Committee: Stefano Bistarelli (University of Pescara, Italy --- C.N.R., Pisa, Italy) Simon De Givry (Institut National de La Recherche Agronomique, Castanet Tolosan Cedex, France) Boi Faltings (EPFL, Switzerland) Carmen Gervet (IC-Parc, Imperial College, UK) Ulrich Junker (ILOG, France) Javier Larrosa (Universitat Politècnica de Catalunya, UPC, Barcelona, Spain) Jimmy H. M. Lee (The Chinese University of Hong Kong, Hong Kong) Pedro Meseguer (IIIA-CSIC, Bellaterra, Spain) Barry O'Sullivan (University College Cork, Ireland) Francesca Rossi (University of Padova, Italy) Thomas Schiex (Institut National de La Recherche Agronomique, Castanet Tolosan Cedex, France) Toby Walsh (Cork Constraints Computation Centre, Ireland)

1 0

ANNOUNCE: Chasing Bottoms
by Nils Anders Danielsson 19 Jun '04

19 Jun '04

Excerpt from the documentation at http://www.cs.chalmers.se/~nad/software/ChasingBottoms/docs/: Chasing Bottoms =============== Do you ever feel the need to test code involving bottoms (e.g. calls to the error function), or code involving infinite values? Then this library could be useful for you. It is usually easy to get a grip on bottoms by showing a value and waiting to see how much gets printed before the first exception is encountered. However, that quickly gets tiresome and is hard to automate using e.g. QuickCheck (http://www.cs.chalmers.se/~rjmh/QuickCheck/) With this library you can do the tests as simply as the following examples show. Testing explicitly for bottoms: > isBottom (head []) True > isBottom bottom True > isBottom (\_ -> bottom) False > isBottom (bottom, bottom) False Comparing finite, partial values: > ((bottom, 3) :: (Bool, Int)) ==! (bottom, 2+5-4) True > ((bottom, bottom) :: (Bool, Int)) <! (bottom, 8) True Showing partial and infinite values (\/! is join and /\! is meet): > approxShow 4 $ (True, bottom) \/! (bottom, b) "Just (True, b)" > approxShow 4 $ (True, bottom) /\! (bottom, b) "(_|_, _|_)" > approxShow 4 $ ([1..] :: [Int]) "[1, 2, 3, _" > approxShow 4 $ (cycle [bottom] :: [Bool]) "[_|_, _|_, _|_, _" Approximately comparing infinite, partial values: > approx 100 [2,4..] ==! approx 100 (filter even [1..] :: [Int]) True > approx 100 [2,4..] /=! approx 100 (filter even [bottom..] :: [Int]) True The code above relies on the fact that bottom, just as error "...", undefined and pattern match failures, yield exceptions. Sometimes we are dealing with properly non-terminating computations, such as the following example, and then it can be nice to be able to apply a timeout. > let primes = unfoldr (\(x:xs) -> Just (x, filter ((/= 0) . (`mod` x)) xs)) [2..] > timeOutMicro 100 (print $ filter ((== 1) . (`mod` 32)) primes) >>= print [97,193,257Nothing > timeOutMicro 100 (print $ take 5 $ filter ((== 1) . (`mod` 32)) primes) >>= print [97,193,257,353Nothing > timeOutMicro 100 (print $ take 5 $ filter ((== 1) . (`mod` 32)) primes) >>= print [97,193,257,353,449] Just () All the type annotations above are required. For the underlying theory and a larger example involving use of QuickCheck, see the article "Chasing Bottoms, A Case Study in Program Verification in the Presence of Partial and Infinite Values" (http://www.cs.chalmers.se/~nad/publications/danielsson-jansson-mpc2004.html) Source code: http://www.cs.chalmers.se/~nad/software/ChasingBottoms/chasing-bottoms.tar.…. /NAD

1 0

Re: [Haskell] comment on language shootout
by JP Bernardy 18 Jun '04

18 Jun '04

--- Gour <gour(a)mail.inet.hr> wrote: > Any comment from some experienced Haskell programmer > about the latest > language shootout published on: > > http://shootout.alioth.debian.org/index.php > regarding Haskell (ghc-6.2.1) score? I would have liked to re-implement some of the benchmarks, some of them should not be looked at by non-haskell programmers, that would give them an awfulidea of what the language looks like/how it should be used. I haven't found where to submit though. BTW, regex matching might be regarded as a bit biased toward ghc :) Cheers, JP. > > > __________________________________ > Do you Yahoo!? > Take Yahoo! Mail with you! Get it on your mobile > phone. > http://mobile.yahoo.com/maildemo > __________________________________ Do you Yahoo!? Yahoo! Mail is new and improved - Check it out! http://promotions.yahoo.com/new_mail

1 0

closure of coercions with classes
by Matthew Fluet 18 Jun '04

18 Jun '04

[Apologies for the slightly long setup. The guts of the question is: can one use the class system to code up the reflexive, transitive closure of a set of dynamic (but contextually implied) coercions? I'm coming to the conclusion that the answer is no, but I'm interested in a good explaination of why things don't work out.] Imagine an extension of the ST monad that gives nested scope [1]; that is, I add the following: blockST :: (forall s2. ST (s1, s2) a) -> ST s1 a liftST :: ST s1 a -> ST (s1, s2) a The first encapsulates the nested scope much as runST encapsulates the entire computation; the second imports computations from the outer scope to the inner scope. Now suppose I want to write a function that pairs the contents of two references into a new reference; furthermore, the function should be polymorphic in the scope of each of the input references, the output reference, and the final computation. That is, I'd like the type to be: pair :: STRef s1 a -> STRef s2 b -> ST s4 (STRef s3 (a, b)) The simplest definition clearly doesn't have enough polymorphism. If I write: pair v w = do a <- readSTRef v b <- readSTRef w newSTRef (v, w) then the function has the type: pair :: STRef s a -> STRef s b -> ST s (STRef s (a, b)) Now, there is no way to write pair with liftST terms that will result in sufficient polymorphism over scopes. For example, if I write: pair v w = do a <- readSTRef v b <- liftST (readSTRef w) liftST (liftST (newSTRef (v, w))) then the function has the type: pair :: STRef ((s1, s2), s3) a -> STRef (s1, s2) b -> ST (((s1, s2), s3), s4) (STRefr1 (a, b)) which isn't as general as I would like, as it imposes a particular order on the nested scopes. The only requirement is that scopes of the input refs and the output refs are nested inside the scope of the resulting computation. I can abstract the liftST applications and pass evidence that witnesses the correct scope nesting: pair :: (ST s1 a -> ST s4 a) -> (ST s2 a -> ST s4 b) -> (ST s3 (STRef s3 (a, b)) -> ST s4 (STRef s3 (a, b))) -> STRef s1 a -> STRef s2 b -> ST s4 (STRef s3 (a, b) pair lift1 lift2 lift3 v w = do a <- lift1 (readSTRef v) b <- lift2 (readSTRef w) lift3 (newSTRef (v, w)) Since evidence is really assembled from liftST terms, it is parametric in the return type. So, it make sense to give pair the more general type: pair :: (forall c. ST s1 c -> ST s4 c) -> (forall c. ST s2 c -> ST s4 c) -> (forall c. ST s3 c -> ST s3 c) -> STRef s1 a -> STRef s2 b -> ST s4 (STRef s3 (a, b)) Now, for the most part, it is obvious how to construct this evidence. My driving question is whether or not there is a way of moving it to the class system. That is, can some variation of the following be made to work: class AutoLiftST s1 s2 where autoLiftST :: ST s1 a -> ST s2 b instance AutoLiftST s1 (s1, s2) where autoLiftST = liftST pair :: (AutoLiftST s1 s4) -> (AutoLiftST s2 s4) -> (AutoLiftST s3 s4) -> STRef s1 a -> STRef s2 b -> ST s4 (STRef s3 (a, b)) pair v w = do a <- autoLiftST (readSTRef v) b <- autoLiftST (readSTRef w) autoLiftST (newSTRef (v, w)) where I could then write: test :: ST s0 (STRef s0 (Integer, Integer)) test = blockST (do v <- newSTRef 1 blockST (do w <- newSTRef 2 blockST (gpair v w))) and have the appropriate instances be derived/inferred. Note that this is basically boils down to choosing the appropriate elements from the reflexive, transitive closure of the liftST's implied by each blockST. Clearly, blindly throwing in reflexive and transitive instances of AutoLiftST leads to overlapping and undecidable instances. (OTOH, if one anticipates that blockST and liftST are operationally identity functions, then all of the instances of autoLiftST correspond to identity functions, and it doesn't matter which instance is chosen.) I've experimented with a few different attempts, but in the best case succeeded only in exhausting stack space while searching for satisfying instances. My gut feeling is that the search space is just too unconstrained; I'd be just as happy to hear a good explaination of exactly _what_ aspect of the problem makes it difficult, if not impossible. Finally, note that the type of liftST and the tuple type are just one way of connecting the inner and outer scopes. I'd actually prefer to dispense with liftST and make the evidence part of blockST. In explicit evidence style: blockST :: (forall s2. (forall b. ST s1 b -> ST s2 b) -> ST s2 a) -> ST s1 a while in the implicit evidence style: blockST :: (forall s2. AutoLiftST s1 s2 => ST s2 a) -> ST s1 a Now the atomic coercions are all implicitly introduced in the body of a blockST by the AutoLiftST s1 s2 class constraint. This leads to the interesting situation where _all_ AutoLiftST instances are of variables. On the other hand, it seem clear that within a nesting of blockST, we accumulate the constraints (AutoLiftST s1 s2, AutoLiftST s2 s3, ..., AutoLiftST sn-1 sn) and it is "obvious" how to compose AutoLiftST si sj for i <= j. [1] John Launchbury and Amr Sabry. Monadic State: Axiomatization and Type Safety. ICFP'97.

2 1

comment on language shootout
by Gour 18 Jun '04

18 Jun '04

Any comment from some experienced Haskell programmer about the latest language shootout published on: http://shootout.alioth.debian.org/index.php regarding Haskell (ghc-6.2.1) score? Sincerely, Gour -- Gour | gour(a)mail.inet.hr Registered Linux User | #278493 GPG Public Key | 8C44EDCD

4 3

Convert Expressions to....
by Scott West 18 Jun '04

18 Jun '04

Hello all, I was just wondering if anyone had any ideas on how I could create an expression type to produce strings of some sort. So say I have something like (Exp a) `oper` (Exp b), is there a way I could perform some operation on each left/right expression, and then on the whole expression? What I'm ultimately seeking is a way to turn expressions into mathML, or some similar sort of formatting. Thanks for any help you can provide! Regards, Scott

1 0

RE: [Haskell] comment on language shootout
by Simon Marlow 18 Jun '04

18 Jun '04

On 18 June 2004 13:50, Gour wrote: > Any comment from some experienced Haskell programmer about the latest > language shootout published on: > > http://shootout.alioth.debian.org/index.php > > regarding Haskell (ghc-6.2.1) score? I submitted improved versions for some of the benchmarks. My feeling is that the #1 reason for ghc being slower is usually Strings. To really do better we need a good PackedString library combined with PackedString I/O. I believe the current PackedString library is underperforming quite a bit - it's on my queue of things to look into. Cheers, Simon

1 0

Space behaviour & hyperseq
by Arjan van IJzendoorn 18 Jun '04

18 Jun '04

Hello Haskellers, I supervise a student who uses Haskell for simulating neural nets. A lot of computation goes on there and the program cannot handle as many iterations as we would like. We have improved performance by a factor of more than ten by putting strictness annotations in all data types. But the problem is that there are lists within these data structures and they are not strict. By using a trick I have now found that making the whole program state strict the program gets a much better looking heap profile. The trick I use is by writing a function hyperseq and then applying it before the next iterations begins: hyperseq x y = if x==x then y else error "this is very unlikely" This is very expensive and I chose to apply the function only once every 100 iterations. This gives reasonable performance. Two questions remain: 1) Is there a more efficient definition of hyperseq that does not traverse the data structure twice? The "show" function traverses the structure once but I found it to be much slower. 2) In this application the uses of lazy evaluation are rare and easily eliminated (zip xs [1..] and so on); is there some hidden GHC option that evaluates everything strictly? I realise that this would invalidate optimisations relying on certain laws but I just wonder how difficult this would be. Somebody must have given this a thought at one point. Cheers, Arjan

5 6

MathUI workshop: deadline extension
by Paul Libbrecht 18 Jun '04

18 Jun '04

:please distribute: :call for papers: workshop on Mathematical User Interfaces ---------------------------- Sept 18th 2004, Bialowezia, Poland at the Third Mathematical Knowledge Management Conference http://www.activemath.org/~paul/MathUI/ SCOPE The impact of mathematical knowledge management on user interfaces is only begininning to show. In interactive proof construction, some systems are able to suggest suitable theorems to apply to subgoals by harvesting online libraries; in computer algebra, folding/unfolding and automatic completion of terms helps the user with the input of complex expressions. Paradigms on how to use third-party software from within a preferred GUI are emerging and promise to innovate the notion of mathematical workspace. This workshop wants to focus on novel aspects of UI brought forward by the developments in MKM. It would like to bring together researchers and practioneers working with contemporary mathematical user-interfaces, including, but not limited to: - mathematical knowledge presentation - interactivity with mathematical objects - interactive simulations - mathematical objects input and manipulations. - access to mathematical knowledge INVITED TALK The workshop has invited Joris van der Hoeven for a talk about TeXMacs, an open-source WYSYWYG editor for mathematical publications. SUBMISSIONS AND DATES - Presentation proposals should be accompanied with an article or other presentation (for example a video or a mock-up GUI). Proceedings shall be online. - Either: - Submit your presentation proposal until June 30th - Or submit an abstract of your presentation (10 lines to half-a-page) until June 30th and a revised version until July 31st - Expect an answer on August 20th - Enjoy the workshop on Sept 18th PROGRAMME COMMITTEE Paul Cairns UCL Interaction Center, University College London, Great Britain Olga Caprotti Research Institute for Symbolic Computation, Linz, Austria Hanane Naciri Projet Lemme, INRIA Sophia Antipolis, France Norbert Kajler Ecole Nationale Supérieure des Mines de Paris, France Paul Libbrecht (organizer) Competence Center for E-Learning, DFKI GmbH, Saarbrücken, Germany Robert Miner Design Science Inc., Long Beach, California, USA MORE INFORMATION Host Conference: Mathematical Knowledge Management 2004 http://www.mizar.org/MKM2004/ More information can be read from the workshop's web-page http://www.activemath.org/~paul/MathUI/

1 0

Annoying naming clashes
by Ben.Yu＠combined.com 18 Jun '04

18 Jun '04

Hi, when writing haskell code. It is so annoying that name clashes keep happening. I have to be careful about the data constructor names, about the class names, about the class member names. I understand that we can use class to achieve some overloading effect. However, it does not help with data constructors. And, what's more important, it looks like Haskell does not allow two classes sharing methods of the same name. And that is something I deemed the most annoying. No matter how powerful type class is compared to Java interfaces, the naming problem just makes it so inconvinient. I'm a programmer who can be so easily affected by ethetics of the program. And when I have to keep worrying about "should I use this name? it may have been used in a similar class", the precious peace in mind is gone. As a novice haskell programmer, I might be missing something here though. If somebody can kindly give me some instruction of how to work with names, appreicate it a lot! Ben. This message is intended only for the addressee and may contain information that is confidential or privileged. Unauthorized use is strictly prohibited and may be unlawful. If you are not the intended recipient, or the person responsible for delivering to the intended recipient, you should not read, copy, disclose or otherwise use this message, except for the purpose of delivery to the addressee. If you have received this email in error, please delete and advise us immediately.

12 22