- Haskell-Cafe - Haskell.org

Re: [Haskell-cafe] Re: Lazy XML handling
by Niklas Broberg 22 May '04

22 May '04

MR K P Shupke wrote: >Can you give me an example where processing HAS to be in a different order? No, but I can give an example where a list based encoding is less sufficient. I'm coming from a completely different view here, namely that of using Haskell not to query or transform but to create XML. I'm currently in a project[1] trying to fix a working implementation of Haskell Server Pages[2], i.e. using Haskell as a server-side scripting language for dynamic webpages. Clearly the most used mode of operation in this setting is constructing an XML tree rather than querying or transforming an existing one. With this in mind, the list based encoding would be less efficient than a treelike datatype. Building the XML tree is likely to be done bottom-up, and adding a parent to a subtree would be O(n) with a list, but O(1) with a tree datatype. Building a whole tree from the bottom up is O(n^2) for a list, but O(n) for the tree datatype. MR K P Shupke wrote: >The nested lists does not allow any extra flexibility in traversal, at the >cost of >greater complexity. The one case it is simpler is if you want to look up a >single >node by its 'tree address' - This is more complex with the list-rep, as you >have to count nodes at a given level, skipping irrelevent nodes... The fact that the list based representation is indeed more complex is in my opinion a clear indication that it should not be the standard. Compare this to Haskell strings where the standard is the simple but ineffective [Char], but where there is another more efficient representation, PackedString, if you really need it. Simplicity and ease of understanding is not to be taken lightly. By using a tree datatype representation you also get pattern matching directly on the structure of the tree, a very useful feature to have. MR K P Shupke wrote: >The list rep is very good at data extraction, if you want to extract a >sub-tree >of a given type you just ignore all tags until you find one of the correct >type, then output all tags until the depth returns to the level of the >initial >tag. That might possibly be a programmatic advantage, though I don't see how it would be more difficult with a tree datatype. In any case it is no more efficient, both are O(n). As far as I can tell there is no single area where the list representation would outperform a tree datatype, other than the special case of lazy streaming. My suggestions are thus: The standard representation should be a tree datatype, both because it is more general and efficiently supports a wide range of operation modes (construction, querying, transformation, rendering), and also because that is what lies closest to the intuition of XML. However, the ability to stream large XML structures lazily is clearly useful and is difficult to achieve using a tree datatype. Why not add it as a specialisation? The standard representation would be a datatype XML living in Data.XML (or similar), and the specialized would be a type XMLStream living in Data.XML.Stream. There should of course also be functions to convert between the types. Comment away, /Niklas [1] http://www.dtek.chalmers.se/~d00nibro/hsp/ [2] http://www.research.microsoft.com/~emeijer/Papers/HSP.pdf _________________________________________________________________ Protect your PC - get McAfee.com VirusScan Online http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963

1 0

GHC and libc
by Per Larsson 21 May '04

21 May '04

When I compile my haskell program (on a linux machine) with GHC and send it to a colleague he can't run it because he has a somewhat older version of libc. Is there a GHC switch that I have missed that enables you to statically link the parts of libc that is used by the haskell program? Alternatively have someone other tips for solving this problem? (I'm reluctant to force all my colleagues to install GHC, because of the size and long installation time, and I can't let them use Hugs because I've used some GHC-only features in my program.) Per Larsson

5 6

c2hs and gtk+hs problem
by scott west 19 May '04

19 May '04

Hello all, I've recently attempted to get the gtk+hs bindings operational, with evidently no success. They both compile fine, but when trying to "make all" the examples in the gtk+hs tree, it gives up with: /usr/local/lib/c2hs-0.12.0/ghc6/libc2hs.a(C2HS.o)(.text+0x32): In function `__stginit_C2HS_': : undefined reference to `__stginit_CForeign_' /usr/local/lib/c2hs-0.12.0/ghc6/libc2hs.a(C2HSBase.o)(.text+0x28): In function `__stginit_C2HSBase_': : undefined reference to `__stginit_MarshalUtils_' /usr/local/lib/c2hs-0.12.0/ghc6/libc2hs.a(C2HSMarsh.o)(.text+0x32): In function `__stginit_C2HSMarsh_': : undefined reference to `__stginit_CString_' /usr/local/lib/c2hs-0.12.0/ghc6/libc2hs.a(C2HSMarsh.o)(.text+0x3c): In function `__stginit_C2HSMarsh_': : undefined reference to `__stginit_MarshalUtils_' /usr/local/lib/c2hs-0.12.0/ghc6/libc2hs.a(C2HSMarsh.o)(.text+0x50): In function `__stginit_C2HSMarsh_': : undefined reference to `__stginit_MarshalAlloc_' /usr/local/lib/c2hs-0.12.0/ghc6/libc2hs.a(C2HSMarsh.o)(.text+0x5a): In function `__stginit_C2HSMarsh_': : undefined reference to `__stginit_Ptr_' /usr/local/lib/c2hs-0.12.0/ghc6/libc2hs.a(NewStorable.o)(.text+0x28): In function `__stginit_NewStorable_': : undefined reference to `__stginit_Storable_' collect2: ld returned 1 exit status Does anyone have any possible ways to resolve this? Thanks for any help!! Regards, Scott

4 4

generic preprocessor for haskell
by Per Larsson 19 May '04

19 May '04

I have recently made a small detour into ocaml programming and I'm rather impressed with the generic preprocessor 'camlp4' for ocaml. Camlp4 allows the programmer to (i) interact with the ocaml parser and lexer to extend the concrete grammar with new syntax and (ii) to directly define the translation of such new syntax forms in terms of ocaml abstract syntax. Haskell programmers (at least in GHC) can also manipulate abstract syntax with the Template Haskell extension and the Language.Haskell.THSyntax library, but to my knowing there is no haskell compiler which supports the inclusion of new syntax forms. Wouldn't such a tool be cool? In the haskell community there are a number of handmade preprocesserors (DrIFT, Generic Haskell, HaRP, ...) which are both cumbersome to write, because the authors must write a (partial) haskell parser for every small extension, but also cumbersome to use because of increasing complexity to your makefiles and different standards for error reporting. Also, experimental extensions could quickly be written and evaluated by the haskell users, decreasing the dependency on the compiler maintainers. Per Larsson

5 5

Re: [Haskell-cafe] Re: Lazy XML handling
by MR K P SCHUPKE 18 May '04

18 May '04

>I'd say it's still less easy (through clearly possible) for an application >to adopt alternative traversal patterns. Yes, thats true, but thats the order in which the tokenizer outputs tags... This is the order tags must be processed if you wish to stream - otherwise you need a heap of tags to keep the ones you are not ready to process from the tokenizer. In effect we can transform an algorithm that requires a different traversal into one that uses this traversal, at a possible slight increase in complexity. The gain is sequential stream based processing. Can you give me an example where processing HAS to be in a different order? In effect HaXml's representation actually simplifies to the above anyway... if you think about... [ A [B,C,D [E,F], G] H [I,J] ] => [(0,A),(1,B),(1,C),(1,D),(2,E),(2,F),(1,G),(0,H),(1,I),(1,J)] The nested lists does not allow any extra flexibility in traversal, at the cost of greater complexity. The one case it is simpler is if you want to look up a single node by its 'tree address' - This is more complex with the list-rep, as you have to count nodes at a given level, skipping irrelevent nodes... The list rep is very good at data extraction, if you want to extract a sub-tree of a given type you just ignore all tags until you find one of the correct type, then output all tags until the depth returns to the level of the initial tag. Regards, Keean.

2 1

Re: [Haskell-cafe] Re: Lazy XML handling
by MR K P SCHUPKE 17 May '04

17 May '04

Please note... The list represents a tree because each node is: [(XmlTreeDepth,XmlElement)] This IS a tree, just a different representation. If what I am saying sounds strange check out the section in Knuth: Volume 1, on representing trees, you will find a whole load besides the C-type pointer based tree. I am not sure what the representation you just gave is??? [[ element ]] surely that simplifies to a list of elements... what am I missing? Regards, Keean.

2 1

Programming style and XML processing in Haskell
by Graham Klyne 15 May '04

15 May '04

After an extended period of procrastination and nipping at the edges of the problem, I feel a need to tackle head on the requirement for a "usable" XML handling library in Haskell. As far back as 1999, Malcolm Wallace and Colin Runciman observed that "Haskell is a very suitable language for XML processing" [1], yet there still does not seem to be a generically useful XML handling library, suitable (say) for inclusion as part of a standard Haskell compiler library. Why do I say this? I have looked at three separate XML libraries, and each has problems which I perceive make them unsuitable for the purposes I have in mind. It may be that part of my problem here is a mistaken view of Haskell programming style, possible exposure of which is one of my reasons for posting this. My immediate goal is to create an RDF/XML parser, the output from which is a data structure representing an RDF graph. This involves parsing the XML to an XML-infoset-like form, then traversing this to extract information for the RDF graph. I want to create a function like this: parseRDFXML :: String -> RDFGraph My XML processing requirements: (1) basic XML parsing (2) predefined and character entity handling (< & &#n; etc) (3) general entity handling (DTD entity definitions and substitutions, per internal DTD subset) (4) easy access to values extracted from XML data (i.e. for XML-to-non-XML processing) (5) XML namespace handling (6) library usable outside the IO monad (i.e. by functions that return non-IO values) Non-requirements, but maybe nice to have: (7) parameter entities (8) External entities (9) XML/DTD validation (1)-(4) correspond roughly to the level of support required of XML parsers for handling "standalone" documents. Almost all modern usage of XML that I'm aware of depends to lesser or greater degree on on (5). (8) and (9) are, I think, in conflict with having library functions that can be used outside the IO monad, since they require that the parser be able to access external data. (7) is really a helper for DTD-based validation, and my own view is that validity checking is better performed using XML schema. Some of the facilities provided by (8) are now being addressed by alternative activities that build upon a basic XML (XInclude, Binary attachments for SOAP, etc.). Requirement (6) arises for me because I have adopted a style of programming in Haskell that is mostly consisting of pure functions, without recourse to monads. I use parser monads locally as required, and I use IO and state monads at the upper levels of my programs to deal with and record the program's interaction with the outside world. It seems to me that this approach leads to functions that are easier to pick up and use. I've found that, when using third party libraries, stand-alone functions present an easier learning curve compared with libraries that are based around a (sometimes complex) monadic state. Maybe I'm missing something here? ... Turning to the XML libraries, I've looked at three: (A) Joe English's HXML parser [2] (B) HaXml [3] (C) Haskell Xml Toolbox [4] (A) HXML is very easy to understand and use, but it does very little more than basic XML parsing. No level of DTD handling is provided, as far as I've been able to determine. (B) HaXML does a little more of what I want, to the extent that it can parse DTDs, and even perform some basic validity checking. I can't find anywhere in the code that seems to address substitution of entities defined in the DTD, and I'm not sure if it can parse a DTD and XML from the same XML file. There are references in the code to external DTD subsets, but I can't see any attempt to implement this. I have found that the HaXML's error handling is rather severe, in that there are a wide of input data errors that cause the library to 'error' rather than return a diagnostic value. (C) Haskell Xml Toolbox is the most functional package (being the only package with XML namespace support) and also the most difficult to use. Unfortunately, it seems that much of the DTD functionality (needed for expanding general entities) is performed I/O monad, as it is part of the code than performs validation, which, as noted above, needs access to external resources. My biggest problem with this package is that it seems to be very difficult and unwieldy to use as part of another library: much of the code seems to be oriented toward creating complete programs for XML-to-XML transformations of various kinds. I've a view that XML namespace support should be quite easy to graft onto either of the other packages, given an extension to the data type used to describe nodes and elements. Over the past couple of months, I've been wavering between pushing ahead with (B) or (C). Both have problems, and either would require significant effort on my part. If I use (C), it involves the least amount of new code, but I think I would find myself ripping out chunks of code to create functions that I can use outside the IO monad, which would effectively fork the codebase. If I use (B), I need to address the error handling problem, though I think I know roughly how to do that (I already made a start; details below). A previous problem I had was that the HaXML code needs CPP preprocessing, which was problematic for me, but since then a simple CPP-equivalent in Haskell has been implemented so I think I can work around that problem. I think I'd need to write new code to deal with entity substitution and namespaces, but I think both of those could be implemented as filters that layer on top of the basic package. So the pendulum swings again, and I now think that HaXML is looking like the most promising base for further development. ... What do I think an XML library for Haskell should look like? The component's I'd like to see would look something like this: XML parser :: String ---> (internal representation) | \ | -----> IO function to perform full validation | and external DTD handling [optional] v XML filter combinators --+--> entity substitution logic | +--> namespace handling | +--> XSLT processing [optional, for now **] v DOM-like read-only interface for access to data at level comparable to XML infoset (used to avoid dependency between applications that use infoset data and details of the internal representation used.) Does this seem reasonable? [**] my thought is that an XSLT document could be "compiled" into an XML filter function. #g -- [1] http://www.cs.york.ac.uk/fp/HaXml/icfp99.html#furtherwork [2] http://www.flightlab.com/~joe/hxml/ [3] http://www.cs.york.ac.uk/fp/HaXml/ [4] http://www.fh-wedel.de/~si/HXmlToolbox/ .... Work I've already done on HaXML: I made a start on a unit test program, and some modifications to the HMW combinator library to allow parse errors to be handled by the calling program. The initial test data has been stolen from the Hxml Toolbox software kit. The 4 test cases all run without errors under Hugs. Feel free to grab anything you think may be useful. The revisions are here: http://www.ninebynine.org/Software/HaskellUtils/HaXml-1.11/ The test program and data files are here: http://www.ninebynine.org/Software/HaskellUtils/HaXml-1.11/test/ (The test program has a commented-out feature to generate formatted versions of the input files which can be renamed for use as comparison test data.) The modified source code includes: + http://www.ninebynine.org/Software/HaskellUtils/HaXml-1.11/src/Text/ParserC… modified to include an option to return a diagnostic message or parser result, via an (Either String a) value. The original interface is (mostly) preserved, and new functions added to support the extended return values (e.g. papplydiag). + http://www.ninebynine.org/Software/HaskellUtils/HaXml-1.11/src/Text/XML/HaX… modified to work with the regised parser structure. A new function, xmlParseDiag, added to return an (Either String a) value. Also added an eof parser and documentOnly functions to perform some of the function of sanitycheck. (I also commented out the #if stuff so I could test under Hugs.) (Malcolm pointed out to me that the lexer also throws some errors, but I think that could be addressed by returning an error token and leaving the parser to deal with the resulting syntax error.) ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

3 3

by MR K P SCHUPKE 15 May '04

15 May '04

>> correcting parser >I would think this is a rather specialized requirement. I certainly don't >want a "correcting" parser for my work. But I can see that some >applications might... Especially if you are aiming for a genarally applicable library. What's really needed is a 'Strictness' switch for the parser, so you can select validating, or non-validating. The parser I wrote uses heuristsics that specify how to fix mistakes (like missing close tags) - this enables the XML parser to parse HTML with the correct set of rules. >This seems reasonable, and I'd expect a reasonable implementation (of a >filter) to stream via lazy evaluation where that matches the final usage >pattern. The outline I sketched (copied below) was intended to be built >upon something like HaXML's filter idea, so that streaming processing would >(in principle) be possible. If you don't use a list based representation, the only other way to get 'lazy' behaviour is to use the 'event' model - which is a lot more complex, but possible using one thread to do the parsing, and a Channel to pass the events through. I think you misunderstand what the parser and renderer do, the parser takes String input and outputs a stream of elements based on the BNF specification for XML... It looks like: data XmlElement = XMLDecl [XmlAttribute] | DocType XmlTagName XmlSystemLiteral XmlPubidLiteral | EmptyTag XmlTagName [XmlAttribute] | STag XmlTagName [XmlAttribute] | ETag XmlTagName | Text [XmlElement] | CharData String | CharRef Int | EntityRef XmlTagName | PERef XmlTagName | CDSect String | PI XmlTagName String | Comment String | Flush | Undefined | Unparsed String deriving (Show,Eq) The renderer takes a stream of these elements and converts to a String. All the filtering/reading/writing is done on streams of these elements. For example a filter could select only <Person ...> records from an XML data source, the person specific reader would then convert to a specific representation of a Person... myReadey :: [(XmlTreeDepth,XmlElement)] -> [Person] a writer does the opposite. Regards, Keean.

2 1

Re: [Haskell-cafe] Programming style and XML processing in Haskell
by MR K P SCHUPKE 14 May '04

14 May '04

Just sticking in my two pence worth... I am not sure what application you intend this for, but I find most XML parsers completely useless. With my application programmers hat on, I do not want to validate against a DTD, I want to extract as much information as possible from bad XML... what I would like is a correcting parser - one which outputs XML in compliance, but will accept any old rubbish and make a best guess attempt to fix it up (based on a set of configurable heuristic rules)... Secondly I deal with very large documents, the tree form of which won't fit in memory, so I would see an XML parser doin the following... parser :: String -> [XmlElements] filter :: [XmlElements] -> [XmlElements] reader :: [XmlElements] -> ... output data types ... writer :: ... input data types ... -> [XmlElements] render :: [XmlElements] -> String In order to keep track of the tree structure the tree-depth of each element is encoded within the XmlElement type... thus allowing the data to be streamed through the filters/readers etc. This means the parser can output the first element as soon as it encounters the second element (lazy list == stream in Haskell) rather than having to wait until the last element as would happen with a DOM tree (it is a tree not a graph as XML elements can only contain sub-elements)... As I said the above is just my opinion, and as it happens I have written a parser that does the above... I guess that is why there are several parsers for XML available (different requirements) and there will probably be many more ... Regards, Keean.

3 2

push/enter vs eval/apply question
by 7253146＠informatica.alumnos.uma.es 14 May '04

14 May '04

Hi. I have read part of the paper "Making a fast curry. Push/enter vs eval/apply for higher-order languages" (Simon Marlow ans Simon Peyton Jones, http://research.microsoft.com/Users/simonpj/papers/eval-apply/eval-apply.ps) where the tradeoffs of both currying models are discused. The paper takes the STG machine as design model. Just as an exercise, I tried to find the curying models for the G and TIM machines as described in "Implementing Functional Languages: a tutorial" (Simon Peyton Jones and David R. Lester, http://research.microsoft.com/Users/simonpj/Papers/pj-lester- book/student.pdf.gz). It was easy to find out that the fourth proposed implementation of the TIM machine was push/enter-oriented ("UpdateMarkers" instruction checks inside a function how many arguments it has been taken). But I have not find anything about for the G machine. It seems to not care about the number of arguments of a supercombinator: when one is evaluated, always have sufficient arguments, and partial applications are simple subgraphs with a mini spine of applications. I guess that only makes sense to talk about the two currying models push/enter and eval/apply when the considered machine is spineless, because on "spineful" or "spine-based" machines the graph of the lambda-calculus expression to evaluate is explicitly represented in memory, so we can see currying as lambda- application over generic lambda-variables. I am very interested on this matter. Please confirm my guess or explain why I am wrong, whoever knows it. Thanks in advance. Regards, Jose David --------------------------------------------- Este mensaje lo ha enviado un Alumno de la Universidad de Malaga. http://www.alumnos.uma.es/

1 0