- Haskell - Haskell.org

RE: [Haskell] How to zip folds: A library of fold transformers
by Simon Peyton-Jones 29 Oct '05

29 Oct '05

Oleg: I'm sure you're aware of the close connection between your FR stuff (nice) and the foldr/build list-fusion work? (So-called "short-cut deforestation".) To make short-cut deforestation work, one has to write map, filter etc in precisely the style you give. I have not grokked your zip idea, though it looks cunning. I wonder if it could be formulated in such a way that we could do foldr/build fusion down both branches of a zip? John Launchbury et al had a paper about hyper-functions which tackled the zip problem too. http://citeseer.ist.psu.edu/krstic01hyperfunctions.html. Also Josef Svengingsson (ICFP'02). I don't know how these relate to your solution. Simon | -----Original Message----- | From: haskell-bounces(a)haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of | oleg(a)pobox.com | Sent: 12 October 2005 01:25 | To: haskell(a)haskell.org | Subject: [Haskell] How to zip folds: A library of fold transformers | | | We show how to merge two folds into another fold | `elementwise'. Furthermore, we present a library of (potentially | infinite) ``lists'' represented as folds (aka streams, aka | success-failure-continuation--based generators). Whereas the standard | Prelude functions such as |map| and |take| transform lists, we | transform folds. We implement the range of progressively more complex | transformers -- from |map|, |filter|, |takeWhile| to |take|, to |drop| | and |dropWhile|, and finally, |zip| and |zipWith|. | | Emphatically we never convert a stream to a list and so we never use | value recursion. All iterative processing is driven by the fold | itself. | | The implementation of zip also solves the problem of ``parallel | loops''. One can think of a fold as an accumulating loop. One can | easily represent a nested loop as a nested fold. Representing parallel | loop as a fold is a challenge, answered at the end of the message. We | need recursive types -- but again, never value recursion. | | This library is inspired by Greg Buchholz' message on the Haskell-Cafe list | and is meant to answer open questions posed at the end of that message | http://www.haskell.org/pipermail/haskell-cafe/2005-October/011575.html | | This message a complete literate Haskell code. | | > {-# OPTIONS -fglasgow-exts #-} | > module Folds where | | First we define the representation of a list as a fold: | | > newtype FR a = FR (forall ans. (a -> ans -> ans) -> ans -> ans) | > unFR (FR x) = x | | It has a rank-2 type. The defining equations are: if flst is a value | of a type |FR a|, then | unFR flst f z = z if flst represents an empty list | unFR flst f z = f e (unFR flst' f z) | if flst represents the list with the head 'e' | and flst' represents the rest of that list | | >From another point of view, |unFR flst| can be considered a _stream_ | that takes two arguments: the success continuation of the type | |a -> ans -> ans| and the failure continuation of the type |ans|. The LogicT | paper discusses such types in detail, and shows how to find that "rest | of the list" flst'. The slides of the ICFP05 presentation by | Chung-chieh Shan point out to more related work in that area. | | But we are here to drop, take, dropWhile, etc. Our functions will | take a stream and return another stream, of the |FR a| type, which | represents truncated, filtered, etc. source stream. | | Let us define two sample streams: a finite and an infinite one: | | > stream1 :: FR Char | > stream1 = FR (\f unit -> foldr f unit ['a'..'i']) | > stream2 :: FR Int | > stream2 = FR (\f unit -> foldr f unit [1..]) | | and the way to show the stream. This is the only time we convert |FR a| | to a list -- so we can more easily show it. | | > instance Show a => Show (FR a) where | > show l = show $ unFR l (:) [] | | | The map function is trivial: | | > smap :: (a->b) -> FR a -> FR b | | *> smap f l = FR(\g -> unFR l (g . f)) | | which can also be written as | | > smap f l = FR((unFR l) . (flip (.) f)) | | For example, | | > test1 = show $ smap succ stream1 | | | Next is the filter function: | | > sfilter :: (a -> Bool) -> FR a -> FR a | > sfilter p l = FR(\f -> unFR l (\e r -> if p e then f e r else r)) | | > test2 = sfilter (not . (`elem` "ch")) stream1 | | The function takeWhile is quite straightforward, too | | > stakeWhile :: (a -> Bool) -> FR a -> FR a | > stakeWhile p l = FR(\f z -> unFR l (\e r -> if p e then f e r else z) z) | | > test3 = stakeWhile (< 'z') stream1 | > test3' = stakeWhile (< 10) stream2 | | As we can see, stakeWhile well applies to an infinite stream. | | The functions take, drop, dropWhile ask for more complexity. | | > stake :: (Ord n, Num n) => n -> FR a -> FR a | > stake n l = FR(\f z -> | > unFR l (\e r n -> if n <= 0 then z else f e (r (n-1))) (const z) n) | | > test4 = stake 20 stream1 | > test4' = stake 5 stream1 | > test4'' = stake 11 stream2 | > test4''' = (stake 11 . smap (^2)) stream2 | | The function sdrop shows the major deficiency: we're stuck with the | (<=0) test for the rest of the stream. In this case, some delimited | continuation operators like `control' can help, in limited | circumstances. | | > sdrop :: (Ord n, Num n) => n -> FR a -> FR a | > sdrop n l = FR(\f z -> | > unFR l (\e r n -> if n <= 0 then f e (r n) else r (n-1)) (const z) n) | | > test5 = sdrop 20 stream1 | > test5' = sdrop 5 stream1 | > test5'' = stake 5 $ sdrop 11 stream2 | | The function dropWhile becomes straightforward | | > sdropWhile :: (a -> Bool) -> FR a -> FR a | > sdropWhile p l = FR(\f z -> | > unFR l (\e r done -> | > if done then f e (r done) | > else if p e then r done else f e (r True)) (const z) False) | | > test6 = sdropWhile (< 'z') stream1 | > test6' = sdropWhile (< 'd') stream1 | > test6'' = stake 5 $ sdropWhile (< 10) stream2 | | The zip function is the most complex. | | Here we need a recursive type: an iso-recursive type to emulate the | equi-recursive one. | | > newtype RecFR a ans = RecFR (a -> (RecFR a ans -> ans) -> ans) | > unRecFR (RecFR x) = x | | This is still a newtype: there is no extra consing. | | I will not pretend that the following is the most perspicuous piece of code: | | *> szip :: FR a1 -> FR a2 -> FR (a1,a2) | *> szip l1 l2 = FR(\f z -> | *> let l1' = unFR l1 (\e r x -> unRecFR x e r) (\r -> z) | *> l2' = unFR l2 (\e2 r2 e1 r1 -> f (e1,e2) (r1 (RecFR r2))) (\e r-> z) | *> in l1' (RecFR l2')) | | It can be simplified to the following: | | > szipWith :: (a->b->c) -> FR a -> FR b -> FR c | > szipWith t l1 l2 = FR(\f z -> | > unFR l1 (\e r x -> unRecFR x e r) (\x -> z) | > (RecFR $ | > unFR l2 (\e2 r2 e1 r1 -> f (t e1 e2) (r1 (RecFR r2))) (\e r -> z))) | > | > szip :: FR a -> FR b -> FR (a,b) | > szip = szipWith (,) | | | One can easily prove that this function does correspond to zip for all | finite streams. The proof for infinite streams requires more | elaboration. | | > test81 = szip stream1 stream1 | > test82 = szip stream1 stream2 | > test83 = szip stream2 stream1 | > test84 = stake 5 $ szip stream2 (sdrop 10 stream2) | | As one may expect (or not), these tests give the right results | | *Folds> test83 | [(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e'),(6,'f'),(7,'g'),(8,'h'),(9,'i') ] | *Folds> test84 | [(1,11),(2,12),(3,13),(4,14),(5,15)] | | _______________________________________________ | Haskell mailing list | Haskell(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell

2 1

Problem with superclass entailment in "A Static Semantics for Haskell"
by Stefan Wehr 29 Oct '05

29 Oct '05

Hi all, I believe there is a problem in the rule for instance declarations in "A Static Semantics For Haskell" [1] because the premise which ensures that instances for all superclasses are defined seems to hold trivially. [2] seems to have the same problem. I now describe the problem by showing how an incorrect program is accepted by the rules given in [1]. I omit many, many details that are irrelevant to this problem. Consider the following program: class C a class C a => D a instance D Int The instance environment IE for this program is built recursively by the rule for modules bodies (Fig. 15) and looks like this: IE = {forall a. D a => C a, D Int} We would expect that the rule for instance declarations (Fig. 26) rejects the program because there is no instance declaration for C Int. However, the rule uses the *whole* instance environment IE to check whether there is an instance declaration for C Int. But this holds trivially, because we have D Int in IE and the implication (forall a. D a => C a) lets us the conclude that C Int holds!! In other words: The rule uses the implication (forall a. D a => C a) to make sure that the very same implication is valid for a = Int. A possible solution might be to remove the constraint D Int before checking whether C Int holds. However, I am not sure whether the resulting rule is complete. An alternative solution would be to use a weaker entailment judgment. Any thoughts? Am I just missing some implicit condition on the instance environment? References: [1] @Article{Faxen02, title = "A static semantics for {Haskell}", author = "Karl-Filip Fax{\'e}n", journal = "Journal of Functional Programming", year = "2002", number = "4\&5", volume = "12", pages = "295--357", } [2] @Article{Hall1996, author = "Cordelia V. Hall and Kevin Hammond and Simon L. {Peyton Jones} and Philip L. Wadler", title = "Type classes in {Haskell}", journal = "ACM Transactions on Programming Languages and Systems", volume = "18", number = "2", pages = "109--138", year = "1996", } Cheers, Stefan Wehr -- Stefan Wehr Web: http://www.stefanwehr.de PGP: Key is available from pgp.mit.edu, ID 0B9F5CE4

1 0

FM'06 Announcement and Call for Submissions
by events-admin＠fmeurope.org 28 Oct '05

28 Oct '05

FM'06: 14TH INTERNATIONAL SYMPOSIUM ON FORMAL METHODS 21 - 27 August 2006 McMaster University, Hamilton, Ontario, Canada http://fm06.mcmaster.ca/ ANNOUNCEMENT AND CALL FOR SUBMISSIONS FM'06 is the fourteenth in a series of symposia organized by Formal Methods Europe, http://www.fmeurope.org, an independent association whose aim is to stimulate the use of, and research on, formal methods for software development. The symposia have been notably successful in bringing together innovators and practitioners in precise mathematical methods for software development, industrial users as well as researchers. Submissions are welcomed in the form of original papers on research and industrial experience, proposals for workshops and tutorials, entries for the exhibition of software tools and projects, and reports on ongoing doctoral work. FM'06 welcomes all aspects of formal methods research, both theoretical and practical. We are particularly interested in the experience of applying formal methods in practice. The broad topics of interest of this conference are: * Tools for formal methods: tool support and software engineering, environments for formal methods. * Theoretical foundations: specification and modelling, refining, static analysis, model-checking, verification, calculation, reusable domain theories. * Formal methods in practice: experience with introducing formal methods in industry, case studies. * Role of formal methods: formal methods in hardware and system design, method integration, development process. TECHNICAL PAPERS Full papers should be submitted via the web site. Papers will be evaluated by the Program Committee according to their originality, significance, soundness, quality of presentation and relevance with respect to the main issues of the symposium. Accepted papers will be published in the Symposium Proceedings, to appear in Springer's Lecture Notes in Computer Science series, http://www.springeronline.com/lncs . Submitted papers should have not been submitted elsewhere for publication, should be in Springer's format, (see Springer's web site), and should not exceed 16 pages including appendices. A prize for the best technical paper will be awarded at the symposium. INDUSTRIAL USAGE REPORTS One day will be dedicated to sharing the experience -- both positive and negative -- with using formal methods in industrial environments. The Industry Day is organized by ForTIA, the Formal Techniques Industry Association, http://www.fortia.org . This year's Industry Day investigates the use of formal methods in security and trust. Invited papers on organizational and technical issues will be presented. Inquiries should be directed to the Industry Day Chairs; see the web site for details. WORKSHOPS We welcome proposals for one-day or one-and-a-half-day workshops related to FM'06. In particular, but not exclusively, we encourage proposals for workshops on various application domains. Proposals should be directed to the Workshop Chair. TUTORIALS We are soliciting proposals for full-day or half-day tutorials. The tutorial contents can be selected from a wide range of topics that reflect the conference themes and provide clear utility to practitioners. Each proposal will be evaluated on importance, relevance, timeliness, audience appeal and past experience and qualification of the instructors. Proposals should be directed to the Tutorial Chair. POSTER AND TOOL EXHIBITION An exhibition of both research projects and commercial tools will accompany the technical symposium, with the opportunity of holding scheduled presentations of commercial tools. Proposals should be directed to the Poster and Tools Exhibition Chair. DOCTORAL SYMPOSIUM For the first time, FM'06 will feature a doctoral symposium. Students are invited to submit work in progress and to defend it in front of "friendly examiners". Participation for students who are accepted will be subsidized. Submissions should be directed to the Doctoral Symposium Chair. SUBMISSION DATES Technical Papers, Workshops, Tutorials: Friday, February 24, 2006 Posters and Tools, Doctoral Symposium: Friday, May 26, 2006 NOTIFICATION DATES Technical Papers: Friday, April 28, 2006 Workshops, Tutorials: Friday, March 10, 2006 Posters and Tools, Doctoral Symposium: Friday, June 9, 2006 ORGANIZATION General Chair: Emil Sekerinski (McMaster) Program Chairs: Jayadev Misra (U. Texas, Austin), Tobias Nipkow (TU Munich) Workshop Chair: Tom Maibaum (McMaster) Tutorial Chair: Jin Song Dong (NUS) Tools and Poster Exhibition Chair: Marsha Chechik (U. Toronto) Industry Day Chairs: Volkmar Lotz (SAP France), Asuman Suenbuel (SAP US) Doctoral Symposium Chair: Augusto Sampaio (U. Pernambuco) Sponsorship Chair: Juergen Dingel (Queens U.) PROGRAM COMMITTEE Jean-Raymond Abrial (ETH Zurich) Alex Aiken (Stanford U.) Keijiro Araki (Kyushu U.) Ralph Back (Abo Akademi) Gilles Barthe (INRIA) David Basin (ETH Zurich) Ed Brinksma (U. Twente) Michael Butler (U. Southampton) Rance Cleaveland (U. Stony Brook) Jorge Cuellar (Siemens) Werner Damm (U. Oldenburg) Frank de Boer (U. Utrecht) Javier Esparza (U. Stuttgart) Jose Fiadeiro (U. Leicester) Susanne Graf (VERIMAG) Ian Hayes (U. Queensland) Gerard Holzmann (JPL) Cliff Jones (U. Newcastle) Gary T. Leavens (Iowa State U.) Rustan Leino (Microsoft) Xavier Leroy (INRIA) Dominique Mery (LORIA) Carroll Morgan (UNSW) David Naumann (Stevens) E.-R. Olderog (U. Oldenburg) Paritosh Pandya (TIFR) Sriram Rajamani (Microsoft) John Rushby (SRI) Steve Schneider (U. Surrey) Vitaly Shmatikov (U. Texas, Austin) Bernhard Steffen (U. Dortmund) P.S. Thiagarajan (NUS) Axel van Lamsweerde (U. Louvain) Martin Wirsing (LMU Munich) Pierre Wolper (U. Liege) LOCAL ORGANIZATION Publicity: Wolfram Kahl, Alan Wassyng, Jeff Zucker Tools, Posters, Book Exhibition: Spencer Smith Social Events: Ridha Khedri Local Arrangements:: William Farmer, Mark Lawford Events Co-ordinator: Ryszard Janicki _______________________________________________ events mailing list events(a)fmeurope.org http://www.fmeurope.org/mailman/listinfo/events

1 0

RE: [Haskell] PROPOSAL: class aliases
by Simon Peyton-Jones 28 Oct '05

28 Oct '05

| This is a proposal for a language extension which will hopefully mitigate the | issues holding back evolution of the standard prelude as well as provide | useful class abstraction capabilities in general. A short summary would be "type synonyms for class constraints". You'd definitely want the syntax to look as much like a type synonym decl as possible. I've considered this before, but never done anything about it because superclasses are so close. Specifically, what is the difference between (i) class (C a, D a) => CD a and (ii) class alias CD a = (C a, D a) Note that (i) is Haskell 98. * In both cases one can write f :: (CD a) => ... instead of the more voluminous f :: (C a, D a) * However with (i), for each type T one must write instance C T where { ...meths for C... } instance D T where { ...meths for D... } instance CD T where {} whereas with (ii) one can write instance CD T where { ...meths for C... ...meths for D... } I believe that this latter is the sole difference. Am I right? [Implementation aspects aside.... with (i) GHC will pass one dictionary CD containing a pair of dictionaries, one for C and one for D.] If so, than rather than invent a whole new mechanism, why not simply extend the existing superclass mechanism to allow a single instance decl to declare instances for several classes? For example, one add to Haskell 98 the following: an instance declaration for a class CD with superclasses C and D may give the instances for its superclasses C and D [One could quibble about details. E.g Should the class decl for CD *say* whether the instance decl *must* contain decls for the superclass methods? Or can one vary it on a instance-by-instance basis, which might be more flexible?] Anyway, my main point it: would a smaller change not suffice? Simon

9 10

[Fwd: Bug in Data.IntSet?]
by Ketil Malde 28 Oct '05

28 Oct '05

Sigh. My system insists on rewriting outgoing mail headers, and ghc-users refuses non-subscribers to post there. I'm too tired to fight this at the moment, so I'll send it here in the hope that it will be picked up by the right adressee. -k -------- Original Message -------- Subject: Bug in Data.IntSet? Date: Thu, 27 Oct 2005 15:25:30 +0200 From: Ketil Malde <ketil(a)ii.uib.no> To: glasgow-haskell-users <glasgow-haskell-users(a)haskell.org> AFAICT, there is a bug in Data.IntSet.split Here's an excerpt from GHCi: *Main> let m=482 in Data.IntSet.split (16*m) $ Data.IntSet.fromList (List.map (m*) [17,18,19,30,40]) ({8194,8676,9158},{14460,19280}) *Main> let m=481 in Data.IntSet.split (16*m) $ Data.IntSet.fromList (List.map (m*) [17,18,19,30,40]) ({},{8177,8658,9139,14430,19240}) *Main> let m=481 in Data.Set.split (16*m) $ Data.Set.fromList (List.map (m*) [17,18,19,30,40]) ({},{8177,8658,9139,14430,19240}) *Main> let m=482 in Data.Set.split (16*m) $ Data.Set.fromList (List.map (m*) [17,18,19,30,40]) ({},{8194,8676,9158,14460,19280}) *Main> let m=482 in Data.Set.split (16*m) $ Data.Set.fromList (List.map (m*) [17,18,19,30,40]::[Int]) ({},{8194,8676,9158,14460,19280}) % ghci --version The Glorious Glasgow Haskell Compilation System, version 6.4.1 -k

3 2

Petri Nets 2006 CFP
by P S Thiagarajan 28 Oct '05

28 Oct '05

Apologies if you receive multiple copies. ------------------------------------------------------------------------ Call for Papers and Announcement Petri Nets 2006 27th INTERNATIONAL CONFERENCE ON APPLICATION AND THEORY OF PETRI NETS AND OTHER MODELS OF CONCURRENCY Turku, Finland, June 26-30, 2006 Additional information about the conference will be published via http://www.cs.abo.fi/atpn2006/ Contact e-mail: atpn2006(a)abo.fi In 2006 the Petri Nets conference is co-located with the ACSD'06. Important Dates: Submission of Papers & Tool Presentations: November 15, 2005 Notification: March 1, 2006 Final Version Due: April 1, 2006 Tutorials & Workshops: June 26-27, 2006 Conference: June 28-30, 2006 The deadline for submission of papers and tool presentations is STRICT. However, if you submit the title page before Nov. 15 it is sufficient to submit the full paper/tool presentation before Nov. 22. The title page must contain a short abstract, classification of the paper, and tell whether it is a theory paper, application paper, or tool presentation. The 27th annual international Petri Net conference and tutorials will be organised by ùÕ÷o Akademi University, Department of Computer Science. Papers presenting original contributions in any area of application and theory of Petri nets are sought. The language of the conference is English. Topics System design and verification using nets, Analysis and synthesis, structure and behaviour of nets, Relationships between net theory and other approaches, Causality/partial order theory of concurrency, Net-based semantical, logical and algebraic calculi, Symbolic net representation (graphical or textual), Computer tools for nets, Experience with using nets, case studies, Educational issues related to nets, Higher-level net models, Timed and stochastic nets, Standardisation of nets, Applications of nets to different kinds of systems and application fields, e.g.: flexible manufacturing systems, real-time systems, embedded systems, defence systems, biological systems, health and medical systems, environmental systems, hardware structures, telecommunications, railway networks, office automation, workflows, supervisory control, protocols and networks, Internet, e-commerce and trading, programming languages, performance evaluation, operations research. The conference takes place under the auspices of EATCS and GI SIG "Petri Nets and Related System Models". Paper Submissions Submissions for papers must: * Contain original contributions that have not been published or submitted to other conferences/journals in parallel with this conference. * Clearly state the problem being addressed, the goal of the work, the results achieved, and the relation to other work. * Be in the Springer LNCS-format: http://www.springer.de/comp/lncs/authors.html. * Have a length that does not exceed 20 pages. * Be in English and in a form that can be immediately included in the proceedings without major revision. * Be sent electronically (as a PostScript or PDF file) using the website http://sttt.cs.uni-dortmund.de/atpn06/servlet/Conference no later than November 15, 2005. The title page must: * Contain a short abstract and a classification of the topics covered, preferably using the list of topics above. * Clearly indicate whether the paper is submitted as a theory paper, an application paper, or both. A typical application paper is a paper that describes one or more projects in which Petri net models and tools have been used in practice. An application paper may also describe a tool, a methodology, or other developments that demonstrate the applicability of Petri nets to industrial systems. Submissions received too late and submissions sent by fax will be immediately rejected. The same will happen with papers which are not in English or exceed the page limit. Authors will be notified of acceptance/rejection by March 1, 2006. The proceedings will be published by Springer-Verlag in Lecture Notes in Computer Science. The final camera-ready version of accepted papers must be received by Susanna Donatelli no later than April 1, 2006. The page limit is 20 pages. Program Committee Co-Chair (Theory Papers) P. S. Thiagarajan School of computing, NUS 3 Science Drive 2 Singapore 117543 Phone: +65-6874 7998 Fax: +65-6779 4580 Program Committee Co-Chair (Application Papers) Susanna Donatelli Università degli Studi di Torino Dipartimento di Informatica Corso Svizzera 185 I-10149 Torino Italy Phone: +39 011 6706746 Fax: +39 011 751603 Organising Committee Chair Johan Lilius ùÕ÷o Akademi University Department of Computer Science Lemminkú¿ènengatan 14 A FIN-20540 Turku FINLAND Phone: +358 40 5440741 Fax: +358 2 215 4732 Tools Demonstration Chair Jerker Bjúä·kqvist ùÕ÷o Akademi University Department of Computer Science Lemminkú¿ènengatan 14 A FIN-20540 Turku FINLAND Phone: +358 2 215 3348 Fax: +358 2 215 4732 Tutorials and Workshops The conference takes place Wednesday to Friday. However, the surrounding days also offer a large variety of Petri net activities. The Introductory Tutorial is offered to participants who have little or no prior experience with Petri nets. The talks give an overview of the area, and they will help new-comers to understand the basic ideas in many of the conference contributions. The Advanced Tutorials and Workshops are offered to those who already have some knowledge of Petri nets. They are divided into several strands covering different subjects. A detailed description of the tutorials and workshops will be available via the conference Web pages. Finally, it will be possible to arrange meetings for different groups, e.g., participants in international Petri net projects. It will also be possible to arrange small educational courses, e.g., with respect to some of the Petri net tools. Submissions for such activities must contain a 2-5 page description. They must be received by one of the PC-chairs no later than January 15, 2006. Tools for Petri Nets As part of the conference, there will be an exhibition of computer tools for Petri nets together with a limited number of tool presentations, i.e., talks about tools. For tool presentations a rotation principle will be enforced. This means that the same tool cannot be presented year after year -- unless it has been significantly enhanced. Submissions for tool presentations must: * Focus on the description of a computer tool for Petri Nets (not an application of the tool or the theory behind the tool). * Be in the Springer LNCS-format: http://www.springer.de/comp/lncs/authors.html. * Have a length that does not exceed 10 pages. * Be in English and in a form that can be immediately included in the proceedings without major revision. * Be sent electronically (as a PostScript or PDF file) using the website http://sttt.cs.uni-dortmund.de/atpn06/servlet/Conference no later than November 15, 2005. Submissions for tool demonstrations must: * Be in English and contain a 3-10 pages description of the tool. * Be received by the tool demonstration chair Jerker Bjúä·kqvist no later than April 1, 2006. Participants wishing to demonstrate tools are encouraged to bring their own machines, as only a limited number of local machines will be available for this purpose, with limited support for installation. Program Committee J. Billington, Australia D. Buchs, Switzerland N. Busi, Italy G. Ciardo, USA J.M. Colom, Spain P. Darondeau, France S. Donatelli, Italy (co-chair, applications) G. Franceschinis, Italy B. Haverkort, The Netherlands X. He, USA K. van Hee, The Netherlands M. Heiner, Germany J. Hillston, UK K. Hiraishi, Japan P. Jancar, Czech Republic G. Juhas, Germany M. Koutny, UK L.M. Kristensen, Denmark J. Lilius, Finland M. Mukund, India W. Penczek, Poland L. Petrucci, France L. Pomello, Italy L. Recalde, Spain K. Schmidt, Germany P.S. Thiagarajan, Singapore (co-chair, theory) T. Ushio, Japan R. Valk, Germany F. Vernadat, France Steering Committee W. van der Aalst, The Netherlands J. Billington, Australia J. Desel, Germany S. Donatelli, Italy S. Haddad, France K. Jensen, Denmark (chair) H.C.M. Kleijn, The Netherlands M. Koutny, UK S. Kumagai, Japan T. Murata, USA C.A. Petri, Germany (honorary member) L. Pomello, Italy W. Reisig, Germany G. Rozenberg, The Netherlands M. Silva, Spain

1 0

Re: Instances That Ignore Type Constraints? (HList-related)
by oleg＠pobox.com 27 Oct '05

27 Oct '05

Just to add one more example to Ralf's reply: We get exactly the same kind of problem if we try *Main> null [fromEnum] <interactive>:1:6: Ambiguous type variable `a' in the constraint: `Enum a' arising from use of `fromEnum' at <interactive>:1:6-13 Probable fix: add a type signature that fixes these type variable(s) Indeed, fromEnum is a polymorphic function |fromEnum :: (Enum a) => a -> Int| The expression [fromEnum] has the type |(Enum a) => [a -> Int]| that carries the constraint Enum a. That constraint has to be eventually resolved somehow. For a top-level expression (not a function), the constraint must be resolved. Granted, the function 'null' could care less what the list is made of, and whether all constraints are resolved. But Haskell does. One may say that instead of inferring the type [fromEnum] :: forall a. (Enum a) => [a -> Int] Haskell should have inferred [fromEnum] :: [forall a. (Enum a) => a -> Int] and the problem would have been solved. There is no longer an (outermost, top-level) constraint to resolve. When GHC does implement MLF and start explicitly supporting impredicative types, the problem would be fixed indeed... Currently, the only way to achieve the same effect is to do this manually: newtype W = W (forall a. (Enum a) => a -> Int) *Main> null [W fromEnum] False Perhaps indeed we should move to Cafe...

1 0

RE: [Haskell] Instances That Ignore Type Constraints? (HList-related)
by Ralf Lammel 27 Oct '05

27 Oct '05

Hi, 'isBoxed (Carton func)' fails because there is no way whatsoever that any expression context will disambiguate the x y type variables of func's type. That is, the type of `isBoxed (Box func)` does not expose x (and y -- the latter being irrelevant because of the fundep); so there is no way that the type system could ever figure out which x (and y) was meant; hence overloading will never ever get resolved (check out the hugs type error, which tells you exactly that). One could argue in favor of incoherent choice of instances. (I don't!) Say, if you had: {-# OPTIONS -fallow-undecidable-instances #-} {-# OPTIONS -fallow-incoherent-instances #-} instance Func x x -- or some other generic instance It will work fine: ghci> isBoxed (Carton func) HFalse However, why would you want to wrap such a function anyhow, if you are not going to use it? :-) Perhaps, this is a case of superficial, say unintended polymorphism. If you *really* wanted to box (or to carton) a polymorphic type-class bounded function, then you may need to do something like this: data WFunc = WFunc (forall x y. Func x y => (x -> y)) hugs-or-ghci> isBoxed (Carton (WFunc func)) HFalse This works fine ... but this is probably *not* what you wanted in the first place. Also, this technique is extremely limiting because now you would need to fabricate wrappers like WFunc for each new polymorphic expression (when the constraints or the type differ). I am keen to hear more about your problem, and to help accordingly. (Haskell-café?) Regards, Ralf > -----Original Message----- > From: haskell-bounces(a)haskell.org [mailto:haskell-bounces@haskell.org] On > Behalf Of Jared Warren > Sent: Wednesday, October 26, 2005 7:01 PM > To: Haskell Mailing List > Subject: [Haskell] Instances That Ignore Type Constraints? (HList-related) > > > > data Box x = Box x > > data Carton x = Carton x > > class Func x y | x -> y where func :: x -> y > > > class IsBoxed f b | f -> b where isBoxed :: f -> b > > instance IsBoxed (Box x) HTrue where isBoxed _ = hTrue > > instance IsBoxed (Carton x) HFalse where isBoxed _ = hFalse > > `isBoxed (Box func)` fails in GHC with "Ambiguous type variables > `x', `y' in the constraint: `Func x y' arising from use of `func'...".

1 0

Instances That Ignore Type Constraints? (HList-related)
by Jared Warren 27 Oct '05

27 Oct '05

I'm working with data structures that contain class methods from the HList library (classes with functional dependencies). What I want to be able to do is operate on high-level parts of the structure while ignoring the type constraints of the lower-level components. For example, say I have two data types and a class method: > data Box x = Box x > data Carton x = Carton x > class Func x y | x -> y where func :: x -> y I want to define a function 'isBoxed' that identifies whether a function is in a Box or in a Carton that I can use like `isBoxed (Carton func)`. Naively: > class IsBoxed f b | f -> b where isBoxed :: f -> b > instance IsBoxed (Box x) HTrue where isBoxed _ = hTrue > instance IsBoxed (Carton x) HFalse where isBoxed _ = hFalse (Where hTrue is a constructorish thing for the empty datatype HTrue.) But `isBoxed (Box func)` fails in GHC with "Ambiguous type variables `x', `y' in the constraint: `Func x y' arising from use of `func'...". I realise that it's solvable if I have a finite number of instances for Func, but what I actually want to box is functions with recursive constraints like HList's hLookupByLabel.* I tried to borrow some ideas (like TypeCast and empty data types) from the examples that come along with HList (like keyword-arguments.hs) to no avail. Can anybody give me a hand? Thanks, Jared Warren <warren(a)cs.queensu.ca> * I could satisfy the type constraints with the infinite HList Record: {Label hZero -> undefined, Label (hSucc hZero) -> undefined, ...} ...but that obviously runs into an infinite type.

1 0

OCaml-intensive summer internships at trading firm
by Yaron Minsky 27 Oct '05

27 Oct '05

Jane Street Capital (http://janestcapital.com) is a proprietary trading company located in Manhattan. We're looking for students interested in internships for the summer of 2006. Jane Street is an open and informal environment (you can wear shorts and a t-shirt to the office), and the work is technically challenging, including systems programming, machine learning, statistical analysis, parallel processing, and anything that crosses our path that looks useful. One unusual attraction of the job is that the large majority of our programming is done in OCaml. Here's what we're looking for from candidates: - A commitment to the practical. Both development and research are tightly integrated with our trading operation, and we work very hard to keep our work relevant. One of the big attractions of the job is the opportunity to apply serious ideas to real-world problems. - Great communication skills. We need people who can explain things clearly and cogently, who can read dense academic papers and write clear documentation. - Strong programming skills. Most of our programming is in OCaml, so being a solid Caml hacker is a big plus. Extra points for deep knowledge of OCaml internals and experience wrapping thorny libraries. But we're also interested in great programmers who we are convinced will be able to pick up OCaml quickly, so anyone with high-level of proficiency with functional languages would be a good match. - Top-notch mathematical and analytic skills. We want people who can solve difficult technical problems, and think clearly and mathematically about all sorts of problems. - Strong Unix/Linux skills --- We're looking for someone who knows their way around the standard Unix tools, can write makefiles, shell scripts, etc. We're also very interested in people with serious systems administration and architecture experience. Summer interns are paid quite well, and we can help out with housing costs if you don't live nearby. If you're interested, please send a cover-letter and resume to: yminsky(a)janestcapital.com -- Yaron Minsky <yminsky(a)janestcapital.com>

1 0