August 2004 - Haskell

XML Serialization and type constraints
by Simon D. Foster 25 Aug '04

25 Aug '04

I'm trying to implement an extensible XML De/Serializer in Haskell for use with SOAP and XML Schema (using the Haskell XML Toolbox). The idea is you have a type-class, which is instantiated for each type you want to encode/de-encode. This class (atm) takes the form; class XMLSerializer a where encodeElements :: NamespaceTable -> Flags -> a -> [XmlFilter] encodeAttributes :: NamespaceTable -> Flags -> a -> [XmlFilter] encodeTree :: NamespaceTable -> String -> Flags -> a -> XmlFilter encodeTrees :: NamespaceTable -> String -> Flags -> a -> [XmlFilter] decodeAttribute :: String -> XmlTree -> Maybe a decodeElement :: XmlTree -> Maybe a decodeTree :: XmlTree -> Maybe a decodeTrees :: XmlTrees -> Maybe a (and a few default instances) This type-class can then be used recursively to build XML representations of Haskell data. I now want to expand this system to make is more extensible. For starters, to make it useful with SOAP, I need to add optional explicit typing of data. To this end I have another class; XSDType, which stores the XSD equivalent name and name-space for a particular Haskell type. This is what is used to add explicit type data to the XML documents. Adding this data involves adding an extra attribute to each node in the tree. More generally however each "Hook", which adds extra data at each node has type NamespaceTable -> Flags -> a -> ([XmlFilter], [XmlFilter]), where a is the type of the value. However, this is where the problem comes. How do I go about expressing that a has a constraint XSDType a? I don't want to add this constraint to the Serializer class itself since an XML tree may not be typed by XSD. Somehow I need a way of adding extra constraints to a dynamically. My first idea was to create another class Encoder; class Encoder e a where encode :: NamespaceTable -> Flags -> e -> a -> ([XmlFilter], [XmlFilter]) Encoder is parameterized over two types; the first being a type to represent the hook itself and the second is the type of the value being serialized. Thus if I introduced this new class into the Serializer class non parametrically; eg for encodeElements; encodeElements :: Encoder e a => NamespaceTable -> Flags -> e -> a -> [XmlFilter] I can create a dummy type SOAPEnc and an instance of Encoder for it with the appropriate constraint; data SOAPEnc = SOAPEnc instance XSDType a => Encoder SOAPEnc a where encode ... = ... and passing SOAPEnc to encodeElements as the e parameter would force the constraint XSDType onto a. This system works fine in theory, but the problem comes when I actually try to call encodeElements on any value parameterised across a. For example lets say we wanted to Serialize a list of Serializeables; instance Serializable a => Serializable [a] where encodeTrees nst n f e x = map (encodeTree nst n f e) x This does not work because Encoder is parameterized over e and [a] and I get; Could not deduce (Encoder e a, XMLSerializer a) from the context (XMLSerializer [a], Encoder e [a]) The obvious way to fix this would be with an extra constraint on the instance; instance (Encoder e a, Serializable a) => Serializable [a]. But since e is not parameterized in Serializable this doesn't help. I could add an extra parameter to Serializable but this would mean that for every different hook, I'd need to duplicate all the serializer functions and the decode functions would all require to be passed an encoding parameter even though they don't need one. This frankly defeats the whole objective of a hook system. My question is this; Is there any way of "inserting" extra constraints on 'a' by passing some form of extra parameter to the appropriate function or by another method and is there anyway of making the above method work? -Si. (Please CC me replies as I'm not subscribed). -- Simon D. Foster <u1sf(a)dcs.shef.ac.uk> Sheffield University

2 7

Call for participation: GPCE'04 -- Generative Programming and Component Engineering
by Eelco Visser 25 Aug '04

25 Aug '04

CALL FOR PARTICIPATION ---------------------------------------------------------------------- Third International Conference on Generative Programming and Component Engineering (GPCE'04) Vancouver, October 24-28, 2004 co-located with OOPSLA 2004 and ISMM 2004 http://gpce04.gpce.org ---------------------------------------------------------------------- Online Registration http://www.regmaster.com/oopsla2004.html early registration with reduced rates closes September 16 ---------------------------------------------------------------------- Generative and component approaches have the potential to revolutionize software development in a similar way as automation and components revolutionized manufacturing. Generative Programming (developing programs that synthesize other programs), Component Engineering (raising the level of modularization and analysis in application design), and Domain-Specific Languages (elevating program specifications to compact domain-specific notations that are easier to write and maintain) are key technologies for automating program development. GPCE arose as a joint conference, merging the prior conference on Generative and Component-Based Software Engineering (GCSE) and the Workshop on Semantics, Applications, and Implementation of Program Generation (SAIG). The goal of GPCE is to provide a meeting place for researchers and practitioners interested in cutting edge approaches to software development. We aim to foster further cross-fertilization between the software engineering research community on the one hand, and the programming languages community on the other, in addition to supporting the original research goals of both the GCSE and the SAIG communities. We seek papers both in software engineering and in programming languages, and especially those that bridge the gap and are accessible to both communities at the same time. * Invited speakers * Keynote: Jack Greenfield on Software Factories * Peter Mosses on Modular Language Descriptions * Technical program * 25 papers * Aspect-orientation * Staged programming * Meta-programming * Model-driven approaches * Product lines * Domain-specific languages * Tutorials * Adaptive Object-Model Architecture: Dynamically Adapting to Changing Requirements * Multi-stage Programming in Meta-OCaml * Generative Software Development * Program Transformation Systems: Theory and Practice for Software Generation, Maintenance and Reengineering * Workshops * Software Transformation Systems Workshop * First MetaOCaml Workshop * Young Researchers Workshop * Workshop on Best Practices Model-Driven Software Development * Workshop on Managing Variabilities Consistently in Design and Code * Demonstrations * Implementation of DSLs using staged interpreters in MetaOCaml * MetaEdit+: Domain-Specific Modeling for Full Code Generation Demonstrated * Towards Domain-Driven Development: the SmartTools Software Factory * Xirc: Cross-Artifact Information Retrieval * C-SAW and GenAWeave: A Two-Level Aspect Weaving Toolsuite * The Concern Manipulation Environment * Program Transformations for Re-Engineering C++ Components

1 0

ICFP'04 early registration deadline
by Amr A Sabry 24 Aug '04

24 Aug '04

****************************************************** *** Early registration rates expire 25 August 2004 *** ****************************************************** The 2004 International Conference on Functional Programming (ICFP) Snowbird, Utah September 19-22, 2004 Call for Participation Registration, hotel information, conference program (accepted papers, poster session, and affiliated workshops on Erlang, Haskell, and Scheme) at the following web site: http://www.cs.indiana.edu/icfp04/

1 0

Full Professor (C4) for Intelligent Systems
by Int. Center for Computational Logic 24 Aug '04

24 Aug '04

Open Position The Faculty of Computer Science of the Technische Universitaet Dresden, Germany, will appoint a new Full Professor (C4) for Intelligent Systems on the 1st October 2005. The successful applicant will be the representative for the area of intelligent systems. In particular, the applicant should be prepared to represent and develop an area, where sensor information is applied to guide intelligent systems in the natural world. The applicant should have an international reputation in at least one of the following subject areas, or related specialisations: Perception, Communication, Autonomy, Machine Learning and Uncertainty. The teaching responsibilities include teaching in German and English on the subjects covered by the faculty. Furthermore, the applicant is expected to participate in the undergraduate education and in general events with other faculties, and also participate in the self-administration of the faculty and the Technische Universitaet Dresden. Assuming that internationally recognised theoretical/systematic research achievements from at least one of the above topics is satisfied, value will be placed on experience with large projects in international cooperations, experience in the application of scientific results, notable teaching ability and either a habilitation or comparable academic achievements. The applicant should also meet the employment requirements described in €40 of the Saechsiches Hochschulgesetz (Saxony education law) from 11th July 1999. Women are especially encouraged to apply. Applications from the severely handicapped are considered preferentially compared to applicants of similar ability. Applications should be made with a photograph, and be supported with a chronological curriculum vitae, description of scientific and professional development, list of scientific works, a choice of three essential publications and authenticated copies of the certificate of the highest academic degree obtained, and submitted by 30th September 2004 to: TU Dresden, Dekan der Fakultaet Informatik, Herrn Prof. Dr. Dr. h. c. A. Schill, 01062 Dresden, Germany. For more information please contact Prof. Dr. Steffen Hoelldobler International Center for Computational Logic Technische Universitaet Dresden <mailto:sh@iccl.tu-dresden.de> +49 351 463 38340

1 0

Re: overzealous defaulting?
by John Meacham 24 Aug '04

24 Aug '04

This reminds me of something I have not quite figured out what should happen from the report module A where import B a = 32 + b default (Integer) module B where import A b = 32 + a default (Int) so, what types do 'a' and 'b' get? ghc sort of sidesteps the issues with the hi-boot files, so they will get whatever is declared in those, but what is the correct thing that should happen in a fully recursive module supporting haskell compiler? John -- John Meacham - ⑆repetae.net⑆john⑈

2 1

Workshop: CUFP
by Koen Claessen 19 Aug '04

19 Aug '04

CALL FOR PARTICIPATION Commercial Users of Functional Programming (CUFP) Sept 18, 2004 Co-located with ICFP http://www.galois.com/cufp/ Functional languages have been under academic development for over 25 years, and are still proving to be very fertile ground for programming language research. Consequently, most of the development focus of these languages is driven by academic and theoretical questions. More recently, however, functional languages have been very successfully used in commercial, industrial, and government settings, where their advantages have been able to be leveraged dramatically. The goal of CUFP is to act as a voice for commercial users of functional programming languages and technology. It aims to help functional programming become increasingly viable as a technology for use in the commercial, industrial, and government space, by providing a forum for FP professionals to share their experiences and ideas, whether business, management or engineering. It also aims to enable the formation and cementing of relationships and alliances that further the commercial use of functional languages. Providing user feedback to language designers and implementers is not a primary goal of the meeting, though it will be welcome if it occurs. The meeting will last a full day, with a mix of invited and submitted presentations, plus discussion sessions. There will be no published proceedings. The meeting is intended to be more of a discussion forum than a technical interchange. Committee Koen Claessen Byron Cook David Fox John Lalonde John Launchbury (Chair)

1 0

GHC writes to stderr
by Georg Martius 19 Aug '04

19 Aug '04

Hi folks, I am just wondering why ghc writes its output to stderr instead of stdout. In case of an error it might be reasonably but all the ordinary information about chaising and stuff should go to a buffered stream I think. Why do I care? I start ghc from emacs in a compile window. The output gets displayed and in the case of an unbuffered output the display gets updated for every single character. I don't have to tell you how slow that is. Cheers, Georg

1 0

newbie question: variable not in scope: "isSpace"
by A.J. Bonnema 15 Aug '04

15 Aug '04

If I use isSpace from the hugs interpretor, it works. If I use isSpace from a test.hs file I get the error message: Undefined variable "isSpace" From ghc I get the error message: Variable not in scope: "isSpace" What is wrong? Guus. -- A.J. Bonnema, Leiden The Netherlands, user #328198 (Linux Counter http://counter.li.org)

2 1

Eliminating Array Bound Checking through Non-dependent types
by oleg＠pobox.com 14 Aug '04

14 Aug '04

There is a view that in order to gain static assurances such as an array index being always in range or tail being applied to a non-empty list, we must give up on something significant: on data structures such as arrays (to be replaced with nested tuples), on general recursion, on annotation-free programming, on clarity of code, on well-supported programming languages. That does not have to be the case. This message shows a non-trivial example involving native Haskell arrays, index computations, and general recursion. All arrays 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 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. Our example is `bsearch', taken from the famous paper "Eliminating Array Bound Checking Through Dependent Types" by Hongwei Xi and Frank Pfenning (PLDI'98). Hongwei Xi's code was written in SML extended with a restricted form of dependent types. Here is the original code of the example (taken from Figure 3 of that paper, see also http://www-2.cs.cmu.edu/~hwxi/DML/examples/) ] datatype 'a answer = NONE | SOME of int * 'a ] ] assert sub <| {n:nat, i:nat | i < n } 'a array(n) * int(i) -> 'a ] assert length <| {n:nat} 'a array(n) -> int(n) ] ] fun('a){size:nat} ] bsearch cmp (key, arr) = ] let ] fun look(lo, hi) = ] if hi >= lo then ] let ] val m = (hi + lo) div 2 ] val x = sub(arr, m) ] in ] case cmp(key, x) of ] LESS => look(lo, m-1) ] | EQUAL => (SOME(m, x)) ] | GREATER => look(m+1, hi) ] end ] else NONE ] where look <| ] {l:nat, h:int | 0 <= l <= size /\ 0 <= h+1 <= size } int(l) * int(h) ] -> 'a answer ] in ] look (0, length arr - 1) ] end ] where bsearch <| ('a * 'a -> order) -> 'a * 'a array(size) -> 'a answer The text after `<|' are dependent type annotations. They _must_ be specified by the programmer -- even for internal functions such as `look'. Here's our code, deliberately written to be as close to Hongwei Xi's code as possible (This message is the complete code): > {-# OPTIONS -fglasgow-exts #-} > module Dep where > import Data.Array > > bsearch cmp (key, arr) = brand arr (\arr' -> bsearch' cmp (key, arr')) > > bsearch' cmp (key,arr) = look lo hi > where > (lo,hi) = bbounds arr > look lo hi = let m = bmiddle lo hi > x = arr !. m > in case cmp (key,x) of > LT -> bpred lo m (look lo) Nothing > EQ -> Just (unbi m, x) > GT -> bsucc hi m (\m' -> look m' hi) Nothing This code is just as algorithmically efficient as the Dependent SML code: one middle index computation, one element comparison, one index comparison, one index increment or decrement per iteration. There are no type annotations as none are needed. 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. > barr1 = listArray (5,5 + (length s)-1) s where s = "abcdefgh" > btest1 = bsearch (uncurry compare) ('c',barr1) > btest2 = bsearch (uncurry compare) ('x',barr1) The code relies on a compact general-purpose trusted kernel explained below. That code should be preferably put into a separate module. First we introduce tags for Branded arrays and Branded indices: > -- those two must *not* be exported! > newtype BArray s i a = BArray (Array i a) > newtype BIndex s i = BIndex 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 is branded if it is certainly within the range of the array of its 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 (see bbounds below) and discarded (see `unbi'). It is created however under controlled conditions. The safety depends on the trusted way of creating branded types: the constructors BIndex and BArray should 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 BIndex 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. > bbounds:: (Ix i) => BArray s i a -> (BIndex s i, BIndex s i) > bbounds (BArray a) = let (l,h) = bounds a in (BIndex l, BIndex h) Proposition: the two indices returned by bbounds are within the range of the array 'a'. Proof: from the semantics of the function `bounds', taken here as an axiom. > bmiddle:: (Integral i) => BIndex s i -> BIndex s i -> BIndex s i > bmiddle (BIndex i1) (BIndex i2) = BIndex ((i1 + i2) `div` 2) Proposition: l <= i1 <= h, l <= i2 <= h |- l <= (i1 + i2) `div` 2 <= h Proof: plain arithmetics. We should stress that the type of bmiddle assures that all indices involved have the same brand -- that is, the same lower and upper boundaries. A brand 's' is a (type-level) representation of index bounds. At compile time, we don't know what they are, but the unforgeability of 's' (see below) statically guarantees that the same 's' represents the same bounds. > bsucc:: (Ord i,Num i) > => BIndex s i -> BIndex s i -> (BIndex s i -> r) -> r -> r > bsucc (BIndex upb) (BIndex i) on_within on_out > = let i' = i + 1 > 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:: (Ord i,Num i) > => BIndex s i -> BIndex s i -> (BIndex s i -> r) -> r -> r > bpred (BIndex lwb) (BIndex i) on_within on_out > = let i' = i - 1 > 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' Finally, we need an introduction rule for BArray: > brand:: (Ix i) => Array i e -> (forall s. BArray s i e -> w) -> w > brand (a::Array i e) k = k ((BArray a)::BArray () i e) The function has a higher-rank type. It is the existential quantification of 's' as well as the absence of BArray constructor elsewhere guarantees that the same brand entails the same bounds.

5 10

Re: DData AscList
by JP Bernardy 14 Aug '04

14 Aug '04

--- John Meacham <john(a)repetae.net> wrote: > So, pursuient to discussion on the various other > haskell lists and some talk about DData recently, > I was wondering whether adding an ordered > list type might be useful. Often, when one knows a > list is ordered, many algorithms (like building a > tree-based set, or a map) become more > efficient, however it is up to the programmer to > ensure an ordered list is used where one is > expected or obscure bugs might occur. > > I was thinking... (off the top of my head) > > module > Data.OrdList(OrdList,toList,fromList,unsafeFromAscList) > where > > newtype Ord a => OrdList a = OrdList { toList :: [a] > } > > fromList = OrdList . sort > unsafeFromAscList xs = OrdList xs > > with some appropriate instances which make an > OrdList behave pretty much > exactly like a list, except maintaining the ordered > invarient... > > > then we can safely convert between the various > container types in O(n) > time without the posibility of messing up... > > comments? Fine, but OrdList should be a subtype of List... and so it has to be done in an "adhoc" fashion. Encoding every other property in a class hierarchy might lead to a big mess. (The ordered property is applicable to any sequence; crossing all independant properties leads to an explosion of the number of types.) To go a bit further, I find it unfortunate to define an extra type for essentially the same structure with more information on it. I'm interested on what Oleg has to say about this, in relation of his recent findings. Also, I wonder how the problem is approached in a dependent-types language. (understand epigram) For this purpose I move to the mother list. > where is the current proposed DData library anyway? Simon Marlow expressed the wish to include part of it (excluding sequences) in the standard distribution. In the meantime, find it on my homepage: users.skynet.be/jyp/DData/ddata.tar.gz Cheers, JP. __________________________________ Do you Yahoo!? New and Improved Yahoo! Mail - 100MB free storage! http://promotions.yahoo.com/new_mail

1 0