February 2006 - Haskell

Datatype-generic programming 2006, registration now open
by Fermin Reig 15 Feb '06

15 Feb '06

[Apologies for multiple copies] ====================================================================== Registration for DGP 2006 is now open. Please visit the web site for instructions. Spring School on Datatype-Generic Programming http://www.cs.nott.ac.uk/ssdgp2006/ University of Nottingham, UK 24-27 April 2006 ************ Background and objectives ************ Generic programming is a thriving research area aimed at making programming more effective by making it more general. This school aims to give participants insights into the applications of datatype-generic programming and the current research challenges in the area. This school is a successor to the Summer School and Workshop on Generic Programming, held in Oxford in August 2002 (lecture notes appeared as volume 2793 of LNCS). ************ Technical programme ************ The lectures will be tutorial-style (as opposed to conference-style) and will be accessible to beginning computing science postgraduates. The scientific programme consists of six courses given by renowned specialists, and a student session. The list of courses is the following: * Thorsten Altenkirch (University of Nottingham): (in collaboration with Conor McBride and Peter Morris) Generic programming with dependent types * Jeremy Gibbons (University of Oxford): Design Patterns as Higher-Order Datatype-Generic Programs * Ralf Hinze (Universitat of Bonn): Generic Programming, Now! (in collaboration with Andres Loeh) * Johan Jeuring (Universiteit Utrecht): Comparing Approaches to Generic Programming (in collaboration with Ralf Hinze and Andres Loeh) * Ralf Laemmel (Microsoft) The next 700 traversal approaches * Tim Sheard (Portland State University): Putting the Curry-Howard Isomorphism to work. Copies of the draft lecture notes will be provided to all participants. The purpose of the student session is to give students an opportunity to present their work and get feedback. Registrants are invited to propose short talks (15-20 min). The selection will be based on abstracts of 150-400 words. ************ Social programme ************ A conference dinner will be organised (attendance at which will be charged separately). ************ Co-location ************ The Symposium on Trends in Functional Programming (TFP 2006), and the Conference of the Types Project (TYPES 2006) will be held in Nottingham the week before this spring school. ************ Accommodation ************ Information about accommodation is available at the School's web site. ************ APPSEM ************ This is an APPSEM-affiliated event. APPSEM funds can be used to support participants from APPSEM-affiliated sites. This message has been checked for viruses but the contents of an attachment may still contain software viruses, which could damage your computer system: you are advised to perform your own checks. Email communications with the University of Nottingham may be monitored as permitted by UK legislation.

1 0

Haskell Weekly News: February 13, 2006
by dons＠cse.unsw.edu.au 14 Feb '06

14 Feb '06

Haskell Weekly News: February 13, 2006 Greetings, and thanks for reading issue 24 of HWN, a weekly newsletter covering developments in the Haskell community. Each Monday, new editions are posted to [1]the Haskell mailing list and to [2]The Haskell Sequence. [3]RSS is also available. 1. http://www.haskell.org/mailman/listinfo/haskell 2. http://sequence.complete.org/ 3. http://sequence.complete.org/node/feed Announcements * FFI Imports Packaging Utility. Dimitry Golubovsky [4]announced the pre-release of the FFI Imports Packaging Utility (ffipkg), a new member of the HSFFIG package. The `ffipkg' utility prepares a Haskell package containing FFI imports for building by accepting locations of C header and foreign library files as command line arguments and producing Haskell source files with FFI declarations, a Makefile, a Cabal package descriptor file, and a Setup.hs file suitable for running the Cabal package setup program. The utility acts as a "driver" running the C preprocessor, the equivalent of the hsffig program, and the source splitter. darcs get --partial http://hsffig.sourceforge.net/repos/hsffig-1.1 4. http://article.gmane.org/gmane.comp.lang.haskell.general/13262 * Haskell in Higher Education. John Hughes [5]announced that the result of his survey into the use of Haskell in higher education are out. The survey covers 89 universities, accounting for 5-10,000 students being taught Haskell this academic year. The results are [6]available on the web. 5. http://article.gmane.org/gmane.comp.lang.haskell.general/13234 6. http://www.cs.chalmers.se/~rjmh/Wash/Survey/teaching.htm Haskell' This section covers activity on [7]Haskell' this week. * [8]The type and class namespace * [9]The monomorphism restriction and performance * [10]Haskell' priorities * [11]Specifying language extensions * [12]FilePath as a data type * [13]Objective data on the use of extensions * [14]Parallel list comprehensions * [15]Tuple representations * Restricted data types [16]parts 1, [17]2, and [18]3. * Bang patterns [19]parts 1, and [20]2 * [21]First-class labels * [22]Scoped type variables 7. http://hackage.haskell.org/trac/haskell-prime 8. http://thread.gmane.org/gmane.comp.lang.haskell.prime/181 9. http://thread.gmane.org/gmane.comp.lang.haskell.prime/257 10. http://thread.gmane.org/gmane.comp.lang.haskell.prime/259 11. http://thread.gmane.org/gmane.comp.lang.haskell.prime/312 12. http://thread.gmane.org/gmane.comp.lang.haskell.prime/338 13. http://thread.gmane.org/gmane.comp.lang.haskell.prime/361 14. http://thread.gmane.org/gmane.comp.lang.haskell.prime/373 15. http://thread.gmane.org/gmane.comp.lang.haskell.prime/395 16. http://thread.gmane.org/gmane.comp.lang.haskell.prime/405 17. http://thread.gmane.org/gmane.comp.lang.haskell.prime/445 18. http://thread.gmane.org/gmane.comp.lang.haskell.prime/471 19. http://thread.gmane.org/gmane.comp.lang.haskell.prime/411 20. http://thread.gmane.org/gmane.comp.lang.haskell.prime/439 21. http://thread.gmane.org/gmane.comp.lang.haskell.prime/447 22. http://thread.gmane.org/gmane.comp.lang.haskell.prime/461 Discussion * Generic catch in a MonadIO. Oleg Kiselyov [23]forked an interesting discussion, with code, on formulating a generic catch function. 23. http://thread.gmane.org/gmane.comp.lang.haskell.general/13247 * RFC: Streams. Bulat Ziganshin [24]posted a request for feedback on the interface of a new Streams library CharEncoding transformers. 24. http://article.gmane.org/gmane.comp.lang.haskell.general/13249 * RFC: Time Library 0.3. Ashley Yakely [25]announced the third draft of a replacement for the standard time library. 25. http://thread.gmane.org/gmane.comp.lang.haskell.libraries/4249 * Eliminating Multiple-Array Bound Checking through Non-dependent . Oleg [26]also writes on writing code with non-trivial static guarantees in the present-day Haskell (i.e., Haskell98 + rank-2 types). He describes how to eliminate array bounds checking when processing several arrays at a time. The number of arrays to process is not statically known. Furthermore, the arrays may have different sizes and bounds -- potentially, empty and non-overlapping too. Excellent stuff. 26. http://article.gmane.org/gmane.comp.lang.haskell.general/13259 * Haskell #1 in Great Language Shootout. As of Friday Haskell is ranked [27]overall 1st on the [28]Great Language Shootout, and 2nd fastest. Thanks to the following people (in alphabetical order) who've contributed code and ideas (and apologies if I've missed any one!): Aaron, Alson, Bertram, Bjorn, Branimir, Brian, Bryn, Cale, Chris, David, Don, Einar, Greg, Iavor, Jan-Willem, Jean-Philippe, Jeff, Joel, Johannes, Josh, Ketil, Kimberly, Lemmih, Matthias, Mirko, Sebastian, Simon and Udo. 27. http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=all 28. http://shootout.alioth.debian.org/ Code Watch Command line completion. Mon Feb 6 04:26:54 PST 2006 Simon Marlow * Basic completion in GHCi This patch adds completion support to GHCi when readline is being used. Completion of identifiers (in scope only, but including qualified identifiers) in expressions is provided. Also, completion of commands (:cmd), and special completion for certain commands (eg. module names for the :module command) are also provided. Contributing to HWN You can help us create new editions of this newsletter. Please see the [29]contributing information, send stories to dons -at- cse.unsw.edu.au. The darcs repository is available at darcs get http://www.cse.unsw.edu.au/~dons/code/hwn 29. http://sequence.complete.org/hwn-contrib

1 0

CFP: PLC 2006 and WORLDCOMP 2006
by Marco Morazan 13 Feb '06

13 Feb '06

Call For Papers WORLDCOMP'06 The 2006 World Congress in Computer Science, Computer Engineering, and Applied Computing (composed of 28 Joint Conferences) June 26-29, 2006, Las Vegas, USA http://www.world-academy-of-science.org/worldcomp06/ws This is anticipated to be the largest annual gathering of researchers in computer science, computer engineering and applied computing. Featured events include: keynote by Prof. Barry Vercoe (founding member of MIT Media Lab); tutorial by Prof. H. J. Siegel (Director, Colorado State University, ISTeC Center); discussion session with Jim Gettys (primary developer of X Window System, xhost, ...) and others. You are invited to submit a paper for consideration (refer to the submission information below.) All accepted papers will be published in the respective conference proceedings (proceedings will be sent to DBLP, Ei, Thomson Scientific, IEE INSPEC, DoPP, and others, for indexing procedures.) The 2006 World Congress in Computer Science, Computer Engineering, and Applied Computing (WORLDCOMP'06) is composed of the following 28 conferences (all will be held simultaneously, same location and dates: June 26-29, 2006, USA). o The 2006 International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'06) o The 2006 International Conference on Scientific Computing (CSC'06) o The 2006 International Conference on Grid Computing and Applications (GCA'06) o The 2006 International Conference on Security and Management (SAM'06) o The 2006 International Conference on Artificial Intelligence (ICAI'06) o The 2006 International Conference on Machine Learning; Models, Technologies and Applications (MLMTA'06) o The 2006 International Conference on Software Engineering Research and Practice (SERP'06) o The 2006 International Conference on Programming Languages and Compilers (PLC'06) o The 2006 International Conference on Internet Computing (ICOMP'06) o The 2006 International Conference on Semantic Web and Web Services (SWWS'06) o The 2006 International Conference on Computer Design (CDES'06) o The 2006 International Conference on Real-Time Computing Systems and Applications (RTCOMP'06) o The 2006 International Conference on Embedded Systems and Applications (ESA'06) o The 2006 International Conference on Wireless Networks (ICWN'06) o The 2006 International Conference on Pervasive Systems and Computing (PSC'06) o The 2006 International Conference on Image Processing, Computer Vision, and Pattern Recognition (IPCV'06) o The 2006 International Conference on Computer Graphics and Virtual Reality (CGVR'06) o The 2006 International Conference on Modeling, Simulation and Visualization Methods (MSV'06) o The 2006 International Conference on Computer Games Development (CGD'06) o The 2006 International Conference on Frontiers in Education: Computer Science and Computer Engineering (FECS'06) o The 2006 International Conference on Foundations of Computer Science (FCS'06) o The 2006 International Conference on e-Learning, e-Business, Enterprise Information Systems, e-Government, and Outsourcing (EEE'06) o The 2006 International Conference on Data Mining (DMIN'06) o The 2006 International Conference on Information and Knowledge Engineering (IKE'06) o The 2006 International Conference on Bioinformatics and Computational Biology (BIOCOMP'06) o The 2006 International Conference on Computing in Nanotechnology (CNAN'06) o The 2006 International Conference on Engineering of Reconfigurable Systems and Algorithms (ERSA'06) o The 2006 International Conference on Communications in Computing (CIC'6) (a link to each conference's URL can be found at http://www.world-academy-of-science.org/worldcomp06/ws currently under construction.) General Chair/Coordinator: H. R. Arabnia, PhD The University of Georgia Department of Computer Science 415 Graduate Studies Research Center Athens, Georgia 30602-7404, USA Tel: (706) 542-3480 Fax: (706) 542-2966 E-mail: hra(a)cs.uga.edu Purpose / History: This set of joint conferences is the largest annual gathering of researchers in computer science, computer engineering and applied computing. Many of the 28 joint conferences in WORLDCOMP are the premier conferences for presentation of advances in their respective fields. The motivation is to assemble a spectrum of affiliated research conferences into a coordinated research meeting held in a common place at a common time. The main goal is to provide a forum for exchange of ideas in a number of research areas that interact. The model used to form these annual conferences facilitates communication among researchers in different fields of computer science, computer engineering and applied computing. Both inward research (core areas of computer science and engineering) and outward research (multi-disciplinary, inter-disciplinary, and applications) will be covered during the conferences. Submission of Papers: Prospective authors are invited to submit their draft paper (about 5 to 8 pages - single space, font size of 10 to 12) to H. R. Arabnia by Feb. 20, 2006. email submissions in MS document or PDF formats are preferable (Fax or postal submissions are also fine.) All reasonable typesetting formats are acceptable (later, the authors of accepted papers will be asked to follow a particular typesetting format to prepare their papers for publication.) The length of the Camera-Ready papers (if accepted) will be limited to 7 (IEEE style) pages. Papers must not have been previously published or currently submitted for publication elsewhere. The first page of the draft paper should include: title of the paper, name, affiliation, postal address, email address, telephone number, and Fax number for each author. The first page should also include the name of the author who will be presenting the paper (if accepted) and a maximum of 5 keywords. Also, the name of the conference that the paper is being submitted to must be mentioned on the first page. Papers will be evaluated for originality, significance, clarity, and soundness. Each paper will be refereed by two researchers in field. The Camera-Ready papers will be reviewed by one person. Members of Program and Organizing Committees: The Program Committee includes members of chapters of World Academy of Science (chapters: supercomputing; scientific computing; artificial intelligence; imaging science; databases; simulation; software engineering; embedded systems; internet and web technologies; communications; computer security; and bioinformatics.) Those interested in joining the Program Committee should email H. R. Arabnia (hra(a)cs.uga.edu) the following information: Name, affiliation and position, complete mailing address, email address, tel/fax numbers, a short biography together with research interests and the name of the conference offering to help with. Location of Conferences: The conferences will be held in the Monte Carlo Resort hotel, Las Vegas, Nevada, USA (with any overflows at other near-by hotels). The Monte Carlo Resort is a mega hotel with excellent conference facilities and over 3,000 rooms. The hotel is minutes from the airport with 24-hour shuttle service to and from the airport. This hotel has many recreational attractions, including: waterfalls, spa, pools and kiddie pools, sunning decks, Easy River water ride, wave pool with cascades, lighted tennis courts, health spa (with workout equipment, whirlpool, sauna, ...), arcade virtual reality game rooms, nightly shows, snack bars, a number of restaurants, shopping area, bars, ... Many of these attractions are open 24 hours a day and most are suitable for families and children. The negotiated room rate for conference attendees is very reasonable. The hotel is within walking distance from most other attractions (major shopping areas, recreational destinations, fine dining, street shows, ...) Important Dates: Feb. 20, 2006: Submission of papers (about 5 to 8 pages) March 20, 2006: Notification of acceptance April 20, 2006: Camera-Ready papers and Prereg. due June 26-29, 2006: The 2006 World Congress in Computer Science, Computer Engineering, and Applied Computing (WORLDCOMP'06 - 28 joint conferences) Topical Scope For Each Conference: To receive the complete list of topics for each of the 28 conferences, send an email to hra(a)cs.uga.edu. Future Announcements: If you do not wish to receive future announcements about this event, please send an email to hra(a)cs.uga.edu.

1 0

ANN: FFI Imports Packaging Utility (pre-release)
by Dimitry Golubovsky 13 Feb '06

13 Feb '06

I am pleased to announce the pre-release of the FFI Imports Packaging Utility (ffipkg), a new member of the HSFFIG package. The `ffipkg' utility prepares a Haskell package containing FFI imports for building by accepting locations of C header and foreign library files as command line arguments and producing Haskell source files with FFI declarations, a Makefile, a Cabal package descriptor file, and a Setup.hs file suitable for running the Cabal package setup program. The utility acts as a "driver" running the C preprocessor, the equivalent of the hsffig program, and the source splitter. Everybody working on a project involving imports from foreign libraries: feel free to try it out. Any feedback will be appreciated. Suggested reading: http://www.haskell.org/haskellwiki/FFI_Imports_Packaging_Utility How to get it: This pre-release is available from the darcs repo only: no new downloads have been added yet to the project page at sourceforge.net. darcs get --partial http://hsffig.sourceforge.net/repos/hsffig-1.1 Run `make' first Then run Setup.hs as usual to configure/build/install the package. Don't forget to specify path to Alex if it is not on the default PATH. The package installs as HSFFIG-1.1 Requirements: GHC >=6.4 (I use 6.4.1) Cabal >= 1.1.3 (older version may not work because of excutables install bug and missing parts of API). For Cabal from darcs, read about the "new userHooks" option of ffipkg. Alex is needed Packages parsec and FilePath are needed. The package also contains an unfinished "xmldump" utility which depends on the hxt (XML Toolbox) package. Please let me know if this is a great inconvenience: I may remove it from the release. Hope that this utility will be useful for the developers. -- Dimitry Golubovsky Anywhere on the Web

1 0

any implementation of "How to write a financial contract" ?
by Assini, Pasqualino 11 Feb '06

11 Feb '06

Hello, I would like to know if there is any publicly available implementation of the combinatorial library described in the excellent "How to write a financial contract" paper by Simon Jones and Jean-Marc Eber. [1] Best regards, titto ------------------------- Pasqualino "Titto" Assini Head of Software Development Nesstar Ltd John Tabor House Wivenhoe Park Colchester,CO4 3SQ UK Tel: +44 1206 874333 Mobile: +44 7910 726 084 Fax: +44 1206 873516 E-mail: titto(a)nesstar.com Website: www.nesstar.com [1] See http://research.microsoft.com/Users/simonpj/Papers/financial-contracts/c ontracts-icfp.htm

1 0

Eliminating Multiple-Array Bound Checking through Non-dependent types
by oleg＠pobox.com 11 Feb '06

11 Feb '06

An earlier message showed an example of writing code with non-trivial static guarantees in the present-day Haskell (i.e., Haskell98 + rank-2 types). http://pobox.com/~oleg/ftp/Haskell/types.html#branding Although this approach obviously falls short of the genuine dependent typing, we can use it in the existing, well-maintained functional language systems. Thus we may begin to acquire taste for dependent typing -- which, McBride at al. point out, matter. The present message shows a more advanced example -- eliminating array bound checking when processing several arrays at a time. The number of arrays to process is not statically known. Furthermore, the arrays may have different sizes and bounds -- potentially, empty and non-overlapping bounds. The example involves native Haskell arrays, index computations, and general recursion. All array indexing operations are statically guaranteed to be safe -- and so we can safely use an efficient unsafeAt provided by GHC seemingly for that purpose. The code is efficient; the static assurances in the main loop over arrays cost us no run-time overhead. The example uses only Haskell98 + higher-ranked types. No new type classes are introduced. The safety is based on: Haskell type system, quantified type variables, and a compact general-purpose trusted kernel. I thank Daniel Yokomizo for the challenge. Our example is folding over multiple, variously-sized arrays. This is like a fold over an array -- generalized to an arbitrary number of arrays, whose index ranges do not have to be the same (and do not have to overlap). Typing this example in a genuinely dependent type system is probably going to be quite challenging. Our goal is to implement a function marray_fold :: (Ix i, Integral i) => (seed -> [e] -> seed) -> seed -> [Array i e] -> seed Its third argument is a list of arrays; the arrays have all the same element and index types; the actual sizes (that is, the lower and upper bounds) may differ. Some arrays in the list may even be empty (with the lower bound higher than the upper one). The function marray_fold, like left fold, applies its left argument to the values extracted from the corresponding arrays. Because arrays may have different sizes and bounds, marray_fold operates over the range of indices that is the intersection of the ranges of the argument arrays. For example: dot a1 a2 = marray_fold (\seed l -> product l + seed) 0 [a1,a2] computes the dot products of two arrays. Granted our example is a bit contrived: in practice one would probably use ``fixed arity'' multiple array fold (similar to zipWith, zipWith3, etc -- which are more efficient and simpler to implement). Also simple is the processing of arrays of the same bounds (and invoking an error continuations if the bounds turn out different). OTH, our present example is more challenging and thus more interesting. Here's the complete implementation (assuming the short trusted branding library explained below). > {-# OPTIONS -fglasgow-exts #-} > module MDep where > import Data.Array > > marray_fold :: (Ix i, Integral i) => > (seed -> [e] -> seed) -> seed -> [Array i e] -> seed > marray_fold _ seed [] = seed -- No arrays, no fold > marray_fold f seed arrs = brands arrs (marray_fold' f seed) seed > > marray_fold' f seed (barrs, bl, bh) = loop (bl2i bl) seed > where loop bi seed = bsucc bh bi (\bi' -> loop bi' seed') seed' > where seed' = f seed (map (!. bi) barrs) > > brands :: (Ix i, Integral i) => [Array i e] > -> (forall s. ([BArray s i e], BLow s i, BHi s i) -> w) > -> w -> w > brands [arr] consumer onempty = > brand arr (\ (barr,bl,bh) -> consumer ([barr],bl,bh)) onempty > brands (a:arrs) consumer onempty = > brands arrs (\bbars -> brand_merge bbars a consumer onempty) onempty The function |brands| computes the intersection index range for the given arrays, and brands each array and the intersection range. The range is given as a pair (BLow s i, BHi s i). The quantified (and thus unforgeable) type variable |s| represents the brand. The function |brands| has a higher-ranked type and must have a signature. Incidentally, functions like that are relatively rare; processors of the list of arrays of the same brand do not require any signature (cf. marray_fold'). The folding loop has as few index comparison operations as algorithmically needed, i.e., only one per iteration. Operator (!.) is a statically safe array indexing operator. The type system and the trust properties of the kernel below guarantee that in the expression "arr !. m" the index `m' is positively in range of the array `arr' bounds. Here are a few test cases, of the dot product over several arrays > dots ars = marray_fold (\seed l -> product l + seed) 0 ars > test1 = dots [listArray (1,5) [1..]] > test2 = dots [listArray (1,5) [1..],listArray (1,5) [1,1..]] > test3 = dots [listArray (1,5) [1..],listArray (5,1) [1,1..]] > test4 = dots [listArray (1,5) [1..],listArray (2,7) [1,1..]] > test5 = dots [listArray (1,5) [1..],listArray (7,7) [1,1..]] > test6 = dots [listArray (1,5) [1..],listArray (5,5) [1,1..], > listArray (3,7) [3..]] The case test3 demonstrates the inclusion of an empty array; test5 shows non-overlapping arrays. The code relies on the compact general-purpose trusted kernel explained below. That code should be put into a separate module. First we introduce tags for Branded arrays, Branded indices, and Branded low and high bounds. > -- the data constructors of those four must *not* be exported! > newtype BArray s i a = BArray (Array i a) > newtype BIndex s i = BIndex i > newtype BLow s i = BLow i > newtype BHi s i = BHi i > unbi (BIndex i) = i These are `newtype's and so impose no run-time overhead. Of interest is a phantom type variable 's', which marks a _brand_ of an array and of an array index. An index or a bound are branded if they are positively within the range of the array of their brand. The type variable 's' is similar to that in the ST monad. The latter relies on 's' to enforce serialization. We, OTH, do not impose any linearity constraints on 's' -- it may be freely duplicated and discarded (see `unbi'). It is created however under controlled conditions. The safety depends on the trusted way of creating branded types: the data constructors BIndex, BLow, BHi, and BArray must be used in the trusted kernel only, and should not be available anywhere else. The uniqueness of 's' afforded by the explicit universal quantification prevents mixing up of different brands. We must re-iterate that safety depends on assurances of the code that constructs branded values. Because of the high assurance, we must formulate the safety properties as propositions, and prove them. Fortunately, the code below is compact and straightforward, as well as general purpose. We start with an introduction rule for BArray: > brand:: (Ix i, Integral i) > => Array i e > -> (forall s. (BArray s i e, BLow s i, BHi s i) -> w) > -> w -> w > brand (a::Array i e) k kempty = > let (l,h) = bounds a > in if l <= h then k ((BArray a)::BArray () i e, BLow l, BHi h) > else kempty The function takes an array and two continuations. If the array is empty, kempty is returned. Otherwise, the continuation k is invoked, which receives the branded array along with two branded indices, for the lower and the upper bounds of the array. Proposition: For the argument (a,l,h) of the continuation k, the branded integral indices l and h are within the bounds of the non-empty branded array a. Proof: from the semantics of the functions `bounds' and `inRange', properties of integral numbers and ranges over integral numbers (specifically, contiguity), and the code itself. The function brand has a higher-rank type. It is the existential quantification of 's' as well as the absence of BArray constructor elsewhere guarantee that the same brand entails the same bounds. For this example, we need another introduction rule for BArray: > brand_merge :: (Ix i, Integral i) => > ([BArray s i e], BLow s i, BHi s i) > -> Array i e > -> (forall s'. ([BArray s' i e], BLow s' i, BHi s' i) -> w) > -> w -> w > brand_merge (bas,(BLow bl),(BHi bh)) (a :: Array i e) k kempty = > let (l,h) = bounds a > l' = max l bl > h' = min h bh > in if l' <= h' then > k (((BArray a)::BArray () i e) : > (map (\ (BArray a) -> BArray a) bas), > BLow l', BHi h') > else kempty The function |brand_merge| takes a list of branded arrays and their greatest common bound (specified as a pair of branded indices). The function also takes an unbranded array. We prepend the new array to the existing ones, and adjust the greatest common bound. The result will have a new brand, which signifies that the new |bl| and |bh| indices are within the range of all of the arrays. The mapped function (\ (BArray a) -> BArray a) is operationally identity. Hopefully the compiler recognizes this fact. Proposition: Given (bas, l, h) where [l,h] is an integral range, forall arr in bas. [l,h] in bounds(arr) if the continuation k is ever invoked, its argument (bas',l',h') has the property: bas' is a non-empty list, [l',h'] is a non-empty linear (integral) range, forall arr in bas'. [l',h'] in bounds(arr) Proof: from the semantics of the functions `bounds' and `inRange', properties of integral numbers and ranges over integral numbers (specifically, contiguity), and the code itself. > bl2i:: BLow s i -> BIndex s i > bl2i (BLow i) = BIndex i Proposition: if bl is within the bounds of an array branded with s, then the result is BIndex within the bounds of that array. Proof: trivial. > bsucc:: (Integral i, Ix i) > => BHi s i -> BIndex s i -> (BIndex s i -> r) -> r -> r > bsucc (BHi upb) (BIndex i) on_within on_out > = let i' = succ i > in if i' <= upb then (on_within (BIndex i')) else on_out The function `bsucc' takes two branded indices that correspond to the same bounds (see the variable 's'). The function also takes two continuations, on_within and on_out. The first index is considered to be an upper limit. The function increments the second index. If the result does not exceed the upper limit, we invoke on_within and pass it the result. Otherwise, we invoke `on_out'. Safety Proposition: l <= upb <= h, l <= i <= h, (i+1) <= upb |- l <= (i+1) <= h Proof: from i < (i+1) and properties of inequalities. The safety proposition justifies our use of the data constructor BIndex. > bpred:: (Ix i, Integral i) > => BLow s i -> BIndex s i -> (BIndex s i -> r) -> r -> r > bpred (BLow lwb) (BIndex i) on_within on_out > = let i' = pred i > in if i' >= lwb then (on_within (BIndex i')) else on_out The dual of `bsucc'. Safety Proposition: l <= lwb <= h, l <= i <= h, (i-1) >= lwb |- l <= (i-1) <= h Because a branded index is assuredly within the bounds of the array of the same brand, we can write > infixl 5 !. > (!.):: (Ix i) => BArray s i e -> (BIndex s i) -> e > (BArray a) !. (BIndex i) = a ! i actually, we may _safely_ replace a ! i with `unsafeAt a i' A reader may have noticed a seemingly artificial |Integral i| constraint on indices. Why can't the mere |Ix i| constraint suffice? That would let us potentially deal with multi-dimensional arrays. Alas, the sole |Ix i| constraint does not suffice because the Ix laws guaranteed in Haskell are lame. For example: inRange (l,h) l ? Does not always hold: inRange (2,1) 2 ---> False if rangeSize (l,h) >0, inRange (l,h) l ? does not seem to follow from the provided laws l <= h, inRange(l,h) l ? False: let l = (1,2); h = (2,1) in (l<=h, inRange (l,h) l) gives (True,False) let (bl,bh) = ((1,2),(1,2)) -- non-empty range (l,h) = ((1,1),(2,1)) -- non-empty range l' = max l bl -- (1,2) h' = min h bh -- (1,2) rangeSize (l',h') is positive but inRange (l,h) l' is False Although Ord is a super-class of Ix, the comparison operation of Ord is not required to have any relationship with ranges. And in fact, it doesn't: the comparison operation on tuples is lexicographic, which isn't the best choice for tuples representing multi-dimensional ranges. Perhaps this message might provide the incentive for more precise specification of the laws for various basic classes in future Haskell standards.

1 0

Re[2]: [Haskell] Streams: the extensible I/O library
by Bulat Ziganshin 10 Feb '06

10 Feb '06

Hello Andrew, Wednesday, February 08, 2006, 8:24:59 PM, you wrote: >> AP> Bulat, it wouldn't hurt to include a motivation section at the top. As >> AP> I understand, it's ultimately all about speed, right? Otherwise, we >> AP> would all be happy with lists (and unsafeInterleave*). So maybe a >> AP> comparison between Stream and [] should be given. >> >> you guessed wrong :) this library is ultimately about replacing >> System.IO library (i.e. Handles) AP> Let me rephrase my question: Why not just reimplement the Handles API AP> (with some extensions like binary IO)? Is there really a need to use a AP> handle-like API for more than real IO? If so, what is the need, AP> expressivity or performance (or both)? Maybe a use case showing what AP> you can do with your library, and how you would have to do it otherwise? now i understood you. actually, my presentation was meant only for a few people who are already know about limitations of current library, who are already requested additional features but don't got it. here i need to give some history: when a System.IO interface was developed, it implements much less features than now, and its implementation was enough simple and straightforward. as time goes, the more and more features was added to this library: complex buffering scheme, several async i/o implementations, locking, networking. And at current moment, GHC's System.IO implementation consists of about 3000 lines with a rather monolithic structure. you can't easily add new feature or make using of some "heavyweight" feature optional because it needs to make changes through the entire library. As the result, GHC users can't get improvements in this library, required for his work. Some of them even develop his own libraries what implements just that they need. for example, Einar Karttunen developed networking library with advanced async i/o and support for i/o of fast packed strings. But such solutions is not universal - his library can't be used for file i/o, fo example, although the code is essentially the same. what i done? the main merit of Streams library is not implementation of any particular feature, but birth of framework for the I/O sub-libraries. and my library essentially is just a collection of such sublibs. first, for example, implements file i/o, second implements buffering, third - utf-8 encoding, and so on. the most important property of all these sublibs is that no one of them is greater than 300 lines. that means that it is far easier to understand, modify or even replace any of them. and that will have no impact to other part of library because all these sublibs binded together not via data fields, but with well defined interfaces now, implementing any new I/O feature or new I/O source means only implementing Stream class-comforming interface - all other features, including locking, buffering, encoding, compression, serialization, binary and text i/o, async i/o, will become available automatically. the same for transformers - once implemented gzip compression or UTF-16 encoding support will become automatically available for all the I/O sources, present and future. is not that great? :) moreover, user apllication or third party lib can easily implement new stream types or transformers without bothering the original library. so, this lib in some aspect is meta-meta-instrument, whose capital will be automatically increasing as new sublibs will appear. just at this moment its advantages over System.IO is in the following areas: faster i/o support for optional utf-8 encoding binary i/o and serialization user-controlled locking if you will look inside the archive, you will find directory Examples, which demonstrates usage of all these features. as i said in docs, i also plan to implement other user requests to the System.IO library another consequence of emerging this library is that all these features will become available on Hugs and other Haskell compilers, that never had enough man resources to develop such great library as GHC's System.IO. and about using streams in monads other than IO. i really don't know, whether it will be used or not. at least, for seriazliation it looks promising. for example, there is functions "encode" and "decode" that is like show/read pair, but implements binary encoding according to the instances of Binary class. and of course, it is implemented through the StringBuffer instance of Stream class, working in the ST monad. comparing to the Handles, library provides essentially the same interface. again, you can find information about swithcing from Handles to Streams in doc. i plan to provide in future "legacy layer" which will emulate 100% of System.IO interface, but use the streams internally. It will be essential for old apps, especially if Streams will become official and sole GHC i/o library about internal organization - Streams is somewhat like that if Simon himself splitted up Handles library to the small independent parts and then replaced part of them with simpler/faster implementations. nothing more, except for common Stream class interface, developed by John Goerzen. my work was mainly to bring the best ideas together :) -- Best regards, Bulat mailto:bulatz@HotPOP.com

1 0

context rules for "default"
by Doug McIlroy 09 Feb '06

09 Feb '06

What is the rationale for the requirement that, in order for the ambiguous type of a numeric constant to be resolved by the default declaration, all classes in the context must be in the Standard Prelude or Standard Library (Revised Report 4.3.4)? This makes it hard to introduce new polymorphic functions whose domain includes the integers. Doug McIlroy

1 0

TFP2006: Last CFP
by Henrik Nilsson 09 Feb '06

09 Feb '06

Dear Colleague, Please find enclosed the third call for papers for Trends in Functional Programming (TFP) 2006. Just one week to go tp the abstract submission deadline of 17 February! Please note that registration for TFP 2006 is now open! My apologies for duplicate copies. Best regards, /Henrik -- Henrik Nilsson School of Computer Science and Information Technology The University of Nottingham nhn(a)cs.nott.ac.uk This message has been checked for viruses but the contents of an attachment may still contain software viruses, which could damage your computer system: you are advised to perform your own checks. Email communications with the University of Nottingham may be monitored as permitted by UK legislation. TFP 2006 Seventh Symposium on Trends in Functional Programming Nottingham, UK, 19 - 21 April, 2006 http://www.cs.nott.ac.uk/~nhn/TFP2006 Co-located with Types 2006 and Spring School on Datatype-Generic Programming CALL FOR PAPERS The Symposium on Trends in Functional Programming (TFP) is an international forum for researchers with interests in all aspects of functional programming languages, focusing on providing a broad view of current and future trends in Functional Programming. It aspires to be a lively environment for presenting the latest research results through acceptance by extended abstracts. A formal post-symposium refereeing process then selects the best papers presented at the symposium for publication in a high-profile volume. TFP 2006 is going to be held in Nottingham, UK, 19 - 21 April. Note that this is significantly earlier in the year than past TFPs that generally were held in August - September. TFP 2006 is co-located with Types 2006 (18 - 21 April). The TFP symposium is the successor to the successful series of Scottish Functional Programming Workshops. Previous TFP symposia were held in Edinburgh, Scotland in 2003, in Munich, Germany in 2004, and in Tallinn, Estonia in 2005 (co-located with ICFP and GPCE). For further general information about TFP, see http://www.tifp.org/. SCOPE OF THE SYMPOSIUM The Symposium recognises that new trends may arise through various routes. As part of the Symposium's focus on trends we therefore identify the following five categories of paper. High-quality papers are solicited in any of these categories: Research Papers: leading-edge, previously unpublished research work Position Papers: on what new trends should or should not be Project Papers: descriptions of recently started new projects Evaluation Papers: what lessons can be drawn from a finished project Overview Papers: summarising work with respect to a trendy subject Papers must be original, and not submitted for simultaneous publication in any other forum. They may consider any aspect of functional programming: theoretical, implementation-oriented, or more experience-oriented. Also applications of functional programming techniques to other languages may be considered. Papers on the following subject areas are particularly welcome: o dependently typed functional programming o validation and verification of functional programs o debugging for functional languages o functional programming and security o functional programming and mobility o functional programming and formally motivated computing o functional languages for telecommunications applications o functional languages for embedded systems o functional programming applied to global computing o functional GRIDs o functional languages for reasoning about imperative/object- oriented programs o interoperability with imperative programming languages o any new emerging trend in the functional programming area If you are in doubt on whether your paper is within the scope of TFP, please contact the TFP 2006 programme chair, Henrik Nilsson, nhn(a)cs.nott.ac.uk. BEST STUDENT PAPER AWARD TFP traditionally pays special attention to research students, acknowledging that students are almost by definition part of new subject trends. To acknowledge this, a prize for the best student paper is awarded each year. CO-LOCATION WITH TYPES 2006 AND DATATYPE-GENERIC PROGRAMMING 2006 TFP 2006 is co-located with Types 2006 (to be held 18 - 21 April). To take advantage of the synergies offered by these two complementary events, we will invite a number of joint keynote speakers, hold joint sessions on topics of mutual interest, such as dependently typed functional programming, and run common social events. The schedule will be arranged so that participants may freely move between parallel sessions of the two events. See http://www.cs.nott.ac.uk/types06/ for further details. TFP 2006 and Types 2006 are immediately followed by the Spring School on Datatype-Generic Programming 2006 (24 - 27 April), which should be of direct interest to many of the TFP and Types Participants. See http://www.cs.nott.ac.uk/ssdgp2006/ for further details. SUBMISSION AND LOCAL PROCEEDINGS Acceptance to the symposium is by extended abstracts of between 6 and 10 pages. Accepted abstracts are to be completed to full papers before the symposium for publication in the local symposium proceedings and on-line. Important dates: Deadline for abstract submission: 17 February, 2006 Notification of acceptance: 27 February, 2006 Registration deadline: 17 March, 2006 Camera-ready copy of full paper: 24 March, 2006 The submission must clearly indicate to which category it belongs: research, position, project, evaluation or overview paper. It should also indicate whether the main author or authors are research students. Abstracts and full papers must be written in English. Papers for the symposium proceedings must adhere to the formatting instructions provided on the TFP 2006 site. Papers must not exceed 16 pages; papers in some categories may comprise considerably fewer pages. The papers of the local proceedings will also be made available on-line under the following conditions, with which all authors are asked to agree: The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder. See the TFP 2006 website for further instructions to authors and details on how to submit. POST SYMPOSIUM REFEREEING AND PUBLICATION In addition to the local symposium proceedings, we intend to continue the TFP tradition of publishing a high-quality subset of contributions in the Intellect series on Trends in Functional Programming (see http://www.intellectbooks.co.uk/series.php?series=1) All TFP authors will be invited to submit revised papers after the symposium. These will will be refereed to normal conference standards, and a subset of the best papers over all categories will be selected for publication. Papers will be judged on their contribution to the research area, with appropriate criteria applied to each category of paper. Papers submitted for publication by Intellect must follow formatting and any other instructions provided by the Programme Chair. For TFP 2005, in order to enhance the quality of student submissions, a process where student papers were given extra feedback was tried out. A similar process might be put in place for this TFP, contingent on the outcome of that trial. ORGANISATION Symposium Chair: Marko van Eekelen, Radboud University Nijmegen, NL Programme Chair: Henrik Nilsson, University of Nottingham, UK Treasurer: Greg Michaelson, Heriot-Watt University, UK Local Arrangements: Joel Wright, University of Nottingham, UK PROGRAMME COMMITTEE: o Kenichi Asai, Ochanomizu University o Gilles Barthes, INRIA, Sophia Antipolis o Olaf Chitil, University of Kent o Catherine Dubois, IIE, Evry o Marko van Eekelen, Radboud Universiteit Nijmegen o Jeremy Gibbons, Oxford University o Kevin Hammond, University of St Andrews o Zoltán Horváth, Eötvös Loránd University o Frank Huch, Christian-Albrechts-University of Kiel o Johan Jeuring, Universiteit Utrecht o Greg Michaelson, Heriot-Watt University o Henrik Nilsson, University of Nottingham o Ricardo Peña, Universidad Complutense de Madrid o Morten Rhiger, Roskilde University o Colin Runciman, University of York o Carsten Schürmann, IT University of Copenhagen o Zhong Shao, Yale University o Phil Trinder, Heriot-Watt University SPONSORS We are actively looking for additional TFP sponsors, who may help to subsidise attendance by research students, for example. If you or your organisation might be willing to sponsor TFP, or if you know someone who might be willing to do so, please do not hesitate to contact the Symposium chair: Marko van Eekelen. Your students will be grateful!

1 0

generic catch in a MonadIO
by oleg＠pobox.com 08 Feb '06

08 Feb '06

The ability to use functions 'catch', 'bracket', 'catchDyn', etc. in MonadIO other than IO itself has been a fairly frequently requested feature: http://www.haskell.org/pipermail/glasgow-haskell-users/2003-September/00566… http://haskell.org/pipermail/libraries/2003-February/000774.html The reason it is not implemented is because these functions cannot be defined for a general MonadIO. However, these functions can be easily defined for a large and interesting subset of MonadIO. The following code demonstrates that. It uses no extensions (other than those needed for the Monad Transformer Library itself), patches no compilers, and proposes no extensions. The generic catch has been useful in a database library (Takusen), where many operations work in a monad (ReaderT Session IO): IO with the environment containing the database session data. Many other foreign libraries have a pattern of passing around various handles, which are better hidden in a monad. Still, we should be able to handle IO errors and user exceptions that arise in these computations. > {-# OPTIONS -fglasgow-exts #-} > > module CaughtMonadIO where > > import Data.Typeable > import Data.Dynamic > import Control.Monad.Trans > import Control.Exception hiding (catch, catchDyn) > import qualified Control.Exception (catch) > import Control.Monad.Reader > import Control.Monad.Writer > import Control.Monad.State > import Control.Monad.RWS > import Control.Monad.Error > > --------------------- Tests > > data MyException = MyException String deriving (Show, Typeable) > > testfn True = throwDyn (MyException "thrown") > testfn False = return True > > testc m = catchDyn (m >>= return . show) (\ (MyException s) -> return s) > > test1 = do tf True >>= print; tf False >>= print > where > tf x = runReaderT (runWriterT (testc (do > tell "begin" > r <- ask > testfn r))) x > > test2 = do tf True >>= print; tf False >>= print; > where > tf x = runReaderT (runErrorT (do > r <- ask > testfn r `catchDyn` > (\ (MyException s) -> throwError s))) x The implementation is quite trivial. > class MonadIO m => CaughtMonadIO m where > gcatch :: m a -> (Exception -> m a) -> m a > > instance CaughtMonadIO IO where > gcatch = Control.Exception.catch > instance (CaughtMonadIO m, Error e) => CaughtMonadIO (ErrorT e m) where > gcatch m f = mapErrorT (\m -> gcatch m (\e -> runErrorT $ f e)) m The following is almost verbatim from `Control.Monad.Error' Section "MonadError instances for other monad transformers" > instance CaughtMonadIO m => CaughtMonadIO (ReaderT r m) where > gcatch m f = ReaderT $ > \r -> gcatch (runReaderT m r) (\e -> runReaderT (f e) r) The following instances presume that an exception that occurs in 'm' discard the state accumulated since the beginning of 'm's execution. If that is not desired -- don't use StateT. Rather, allocate IORef and carry that _immutable_ value in a ReaderT. The accumulated state will thus persist. One can always use IORefs within any MonadIO. > instance (Monoid w, CaughtMonadIO m) => CaughtMonadIO (WriterT w m) where > m `gcatch` h = WriterT $ runWriterT m > `gcatch` \e -> runWriterT (h e) > instance CaughtMonadIO m => CaughtMonadIO (StateT s m) where > m `gcatch` h = StateT $ \s -> runStateT m s > `gcatch` \e -> runStateT (h e) s > instance (Monoid w, CaughtMonadIO m) => CaughtMonadIO (RWST r w s m) where > m `gcatch` h = RWST $ \r s -> runRWST m r s > `gcatch` \e -> runRWST (h e) r s > catchDyn :: (Typeable e, CaughtMonadIO m) => m a -> (e -> m a) -> m a > catchDyn m f = gcatch m (\e -> maybe (throw e) f ((dynExceptions e) > >>= fromDynamic))

5 5