SXML
====

(sxml apply-templates)
----------------------

Overview
........

Pre-order traversal of a tree and creation of a new tree:

     	apply-templates:: tree x <templates> -> <new-tree>

where

      <templates> ::= (<template> ...)
      <template>  ::= (<node-test> <node-test> ... <node-test> . <handler>)
      <node-test> ::= an argument to node-typeof? above
      <handler>   ::= <tree> -> <new-tree>

This procedure does a normal, pre-order traversal of an SXML tree. It walks the tree, checking at each node against the list of matching templates.

If the match is found (which must be unique, i.e., unambiguous), the corresponding handler is invoked and given the current node as an argument. The result from the handler, which must be a <tree>, takes place of the current node in the resulting tree. The name of the function is not accidental: it resembles rather closely an apply-templates function of XSLT.

Usage
.....

apply-templates tree templates

(sxml fold)
-----------

Overview
........

(sxml fold) defines a number of variants of the fold algorithm for use in transforming SXML trees. Additionally it defines the layout operator, fold-layout, which might be described as a context-passing variant of SSAX's pre-post-order.

Usage
.....

foldt fup fhere tree The standard multithreaded tree fold.

FUP is of type [a] -> a. FHERE is of type object -> a.

foldts fdown fup fhere seed tree The single-threaded tree fold originally defined in SSAX. See (sxml ssax), for more information.

foldts* fdown fup fhere seed tree A variant of foldts that allows pre-order tree rewrites. Originally defined in Andy Wingo's 2007 paper, Applications of fold to XML transformation.

fold-values proc list . seeds A variant of fold that allows multi-valued seeds. Note that the order of the arguments differs from that of fold.

foldts*-values fdown fup fhere tree . seeds A variant of foldts* that allows multi-valued seeds. Originally defined in Andy Wingo's 2007 paper, Applications of fold to XML transformation.

fold-layout tree bindings params layout stylesheet A traversal combinator in the spirit of SSAX's pre-post-order.

fold-layout was originally presented in Andy Wingo's 2007 paper, Applications of fold to XML transformation.

     bindings := (<binding>...)
     binding  := (<tag> <bandler-pair>...)
               | (*default* . <post-handler>)
               | (*text* . <text-handler>)
     tag      := <symbol>
     handler-pair := (pre-layout . <pre-layout-handler>)
               | (post . <post-handler>)
               | (bindings . <bindings>)
               | (pre . <pre-handler>)
               | (macro . <macro-handler>)

pre-layout-handler
     A function of three arguments:

     kids
          the kids of the current node, before traversal

     params
          the params of the current node

     layout
          the layout coming into this node

     PRE-LAYOUT-HANDLER is expected to use this information to return a layout to pass to the kids. The default implementation returns the layout given in the arguments.

post-handler
     A function of five arguments:

     tag
          the current tag being processed

     params
          the params of the current node

     layout
          the layout coming into the current node, before any kids were processed

     klayout
          the layout after processing all of the children

     kids
          the already-processed child nodes

     POST-HANDLER should return two values, the layout to pass to the next node and the final tree.

text-handler
     TEXT-HANDLER is a function of three arguments:

     text
          the string

     params
          the current params

     layout
          the current layout

     TEXT-HANDLER should return two values, the layout to pass to the next node and the value to which the string should transform.

(sxml simple)
-------------

Overview
........

A simple interface to XML parsing and serialization.

Usage
.....

xml->sxml [port] Use SSAX to parse an XML document into SXML. Takes one optional argument, PORT, which defaults to the current input port.

sxml->xml tree [port] Serialize the sxml tree TREE as XML. The output will be written to the current output port, unless the optional argument PORT is present.

sxml->string sxml Detag an sxml tree SXML into a string. Does not perform any formatting.

(sxml ssax)
-----------

Overview
........

Functional XML parsing framework
--------------------------------

SAX/DOM and SXML parsers with support for XML Namespaces and validation
.......................................................................

This is a package of low-to-high level lexing and parsing procedures that can be combined to yield a SAX, a DOM, a validating parser, or a parser intended for a particular document type. The procedures in the package can be used separately to tokenize or parse various pieces of XML documents. The package supports XML Namespaces, internal and external parsed entities, user-controlled handling of whitespace, and validation. This module therefore is intended to be a framework, a set of "Lego blocks" you can use to build a parser following any discipline and performing validation to any degree. As an example of the parser construction, this file includes a semi-validating SXML parser.

The present XML framework has a "sequential" feel of SAX yet a "functional style" of DOM. Like a SAX parser, the framework scans the document only once and permits incremental processing. An application that handles document elements in order can run as efficiently as possible. Unlike a SAX parser, the framework does not require an application register stateful callbacks and surrender control to the parser. Rather, it is the application that can drive the framework -- calling its functions to get the current lexical or syntax element. These functions do not maintain or mutate any state save the input port. Therefore, the framework permits parsing of XML in a pure functional style, with the input port being a monad (or a linear, read-once parameter).

Besides the PORT, there is another monad -- SEED. Most of the middle- and high-level parsers are single-threaded through the SEED. The functions of this framework do not process or affect the SEED in any way: they simply pass it around as an instance of an opaque datatype. User functions, on the other hand, can use the seed to maintain user's state, to accumulate parsing results, etc. A user can freely mix his own functions with those of the framework. On the other hand, the user may wish to instantiate a high-level parser: SSAX:make-elem-parser or SSAX:make-parser. In the latter case, the user must provide functions of specific signatures, which are called at predictable moments during the parsing: to handle character data, element data, or processing instructions (PI). The functions are always given the SEED, among other parameters, and must return the new SEED.

From a functional point of view, XML parsing is a combined pre-post-order traversal of a "tree" that is the XML document itself. This down-and-up traversal tells the user about an element when its start tag is encountered. The user is notified about the element once more, after all element's children have been handled. The process of XML parsing therefore is a fold over the raw XML document. Unlike a fold over trees defined in [1], the parser is necessarily single-threaded -- obviously as elements in a text XML document are laid down sequentially. The parser therefore is a tree fold that has been transformed to accept an accumulating parameter [1,2].

Formally, the denotational semantics of the parser can be expressed as

      parser:: (Start-tag -> Seed -> Seed) ->
     	   (Start-tag -> Seed -> Seed -> Seed) ->
     	   (Char-Data -> Seed -> Seed) ->
     	   XML-text-fragment -> Seed -> Seed
      parser fdown fup fchar "<elem attrs> content </elem>" seed
       = fup "<elem attrs>" seed
     	(parser fdown fup fchar "content" (fdown "<elem attrs>" seed))

      parser fdown fup fchar "char-data content" seed
       = parser fdown fup fchar "content" (fchar "char-data" seed)

      parser fdown fup fchar "elem-content content" seed
       = parser fdown fup fchar "content" (
     	parser fdown fup fchar "elem-content" seed)

Compare the last two equations with the left fold

      fold-left kons elem:list seed = fold-left kons list (kons elem seed)

The real parser created by SSAX:make-parser is slightly more complicated, to account for processing instructions, entity references, namespaces, processing of document type declaration, etc.

The XML standard document referred to in this module ishttp://www.w3.org/TR/1998/REC-xml-19980210.html

The present file also defines a procedure that parses the text of an XML document or of a separate element into SXML, an S-expression-based model of an XML Information Set. SXML is also an Abstract Syntax Tree of an XML document. SXML is similar but not identical to DOM; SXML is particularly suitable for Scheme-based XML/HTML authoring, SXPath queries, and tree transformations. See SXML.html for more details. SXML is a term implementation of evaluation of the XML document [3]. The other implementation is context-passing.

The present frameworks fully supports the XML Namespaces Recommendation:http://www.w3.org/TR/REC-xml-names/ Other links:

[1]
     Jeremy Gibbons, Geraint Jones, "The Under-appreciated Unfold," Proc. ICFP'98, 1998, pp. 273-279.

[2]
     Richard S. Bird, The promotion and accumulation strategies in transformational programming, ACM Trans. Progr. Lang. Systems, 6(4):487-504, October 1984.

[3]
     Ralf Hinze, "Deriving Backtracking Monad Transformers," Functional Pearl. Proc ICFP'00, pp. 186-197.

Usage
.....

current-ssax-error-port

with-ssax-error-to-port port thunk

xml-token? _
 -- Scheme Procedure: pair? x
     Return `#t' if X is a pair; otherwise return `#f'.

xml-token-kind token

xml-token-head token

make-empty-attlist

attlist-add attlist name-value

attlist-null? _
 -- Scheme Procedure: null? x
     Return `#t' iff X is the empty list, else `#f'.

attlist-remove-top attlist

attlist->alist attlist

attlist-fold kons knil lis1

define-parsed-entity! entity str Define a new parsed entity. ENTITY should be a symbol.

Instances of &ENTITY; in XML text will be replaced with the string STR, which will then be parsed.

reset-parsed-entity-definitions! Restore the set of parsed entity definitions to its initial state.

ssax:uri-string->symbol uri-str

ssax:skip-internal-dtd port

ssax:read-pi-body-as-string port

ssax:reverse-collect-str-drop-ws fragments

ssax:read-markup-token port

ssax:read-cdata-body port str-handler seed

ssax:read-char-ref port

ssax:read-attributes port entities

ssax:complete-start-tag tag-head port elems entities namespaces

ssax:read-external-id port

ssax:read-char-data port expect-eof? str-handler seed

ssax:xml->sxml port namespace-prefix-assig

ssax:make-parser  . kw-val-pairs

ssax:make-pi-parser orig-handlers

ssax:make-elem-parser my-new-level-seed my-finish-element my-char-data-handler my-pi-handlers

(sxml ssax input-parse)
-----------------------

Overview
........

A simple lexer.

The procedures in this module surprisingly often suffice to parse an input stream. They either skip, or build and return tokens, according to inclusion or delimiting semantics. The list of characters to expect, include, or to break at may vary from one invocation of a function to another. This allows the functions to easily parse even context-sensitive languages.

EOF is generally frowned on, and thrown up upon if encountered. Exceptions are mentioned specifically. The list of expected characters (characters to skip until, or break-characters) may include an EOF "character", which is to be coded as the symbol, *eof*.

The input stream to parse is specified as a port, which is usually the last (and optional) argument. It defaults to the current input port if omitted.

If the parser encounters an error, it will throw an exception to the key parser-error. The arguments will be of the form (PORT MESSAGE SPECIALISING-MSG*).

The first argument is a port, which typically points to the offending character or its neighborhood. You can then use port-column and port-line to query the current position. MESSAGE is the description of the error. Other arguments supply more details about the problem.

Usage
.....

peek-next-char [port]

assert-curr-char expected-chars comment [port]

skip-until arg [port]

skip-while skip-chars [port]

next-token prefix-skipped-chars break-chars [comment] [port]

next-token-of incl-list/pred [port]

read-text-line [port]

read-string n [port]

find-string-from-port? _ _ . _ Looks for STR in <INPUT-PORT>, optionally within the first MAX-NO-CHAR characters.

(sxml transform)
----------------

Overview
........

SXML expression tree transformers
=================================

Pre-Post-order traversal of a tree and creation of a new tree
-------------------------------------------------------------

     pre-post-order:: <tree> x <bindings> -> <new-tree>

where

      <bindings> ::= (<binding> ...)
      <binding> ::= (<trigger-symbol> *preorder* . <handler>) |
                    (<trigger-symbol> *macro* . <handler>) |
     		(<trigger-symbol> <new-bindings> . <handler>) |
     		(<trigger-symbol> . <handler>)
      <trigger-symbol> ::= XMLname | *text* | *default*
      <handler> :: <trigger-symbol> x [<tree>] -> <new-tree>

The pre-post-order function visits the nodes and nodelists pre-post-order (depth-first). For each <Node> of the form (NAME <Node> ...), it looks up an association with the given NAME among its <BINDINGS>. If failed, pre-post-order tries to locate a *default* binding. It's an error if the latter attempt fails as well. Having found a binding, the pre-post-order function first checks to see if the binding is of the form

     	(<trigger-symbol> *preorder* . <handler>)

If it is, the handler is 'applied' to the current node. Otherwise, the pre-post-order function first calls itself recursively for each child of the current node, with <NEW-BINDINGS> prepended to the <BINDINGS> in effect. The result of these calls is passed to the <HANDLER> (along with the head of the current <NODE>). To be more precise, the handler is _applied_ to the head of the current node and its processed children. The result of the handler, which should also be a <tree>, replaces the current <NODE>. If the current <NODE> is a text string or other atom, a special binding with a symbol *text* is looked up.

A binding can also be of a form

     	(<trigger-symbol> *macro* . <handler>)

This is equivalent to *preorder* described above. However, the result is re-processed again, with the current stylesheet.

Usage
.....

SRV:send-reply . fragments Output the FRAGMENTS to the current output port.

The fragments are a list of strings, characters, numbers, thunks, #f, #t -- and other fragments. The function traverses the tree depth-first, writes out strings and characters, executes thunks, and ignores #f and '(). The function returns #t if anything was written at all; otherwise the result is #f If #t occurs among the fragments, it is not written out but causes the result of SRV:send-reply to be #t.

foldts fdown fup fhere seed tree

post-order tree bindings

pre-post-order tree bindings

replace-range beg-pred end-pred forest

(sxml xpath)
------------

Overview
........

SXPath: SXML Query Language
===========================

SXPath is a query language for SXML, an instance of XML Information set (Infoset) in the form of s-expressions. See (sxml ssax) for the definition of SXML and more details. SXPath is also a translation into Scheme of an XML Path Language, XPath (http://www.w3.org/TR/xpath). XPath and SXPath describe means of selecting a set of Infoset's items or their properties.

To facilitate queries, XPath maps the XML Infoset into an explicit tree, and introduces important notions of a location path and a current, context node. A location path denotes a selection of a set of nodes relative to a context node. Any XPath tree has a distinguished, root node -- which serves as the context node for absolute location paths. Location path is recursively defined as a location step joined with a location path. A location step is a simple query of the database relative to a context node. A step may include expressions that further filter the selected set. Each node in the resulting set is used as a context node for the adjoining location path. The result of the step is a union of the sets returned by the latter location paths.

The SXML representation of the XML Infoset (see SSAX.scm) is rather suitable for querying as it is. Bowing to the XPath specification, we will refer to SXML information items as 'Nodes':

      	<Node> ::= <Element> | <attributes-coll> | <attrib>
      		   | "text string" | <PI>

This production can also be described as

     	<Node> ::= (name . <Nodeset>) | "text string"

An (ordered) set of nodes is just a list of the constituent nodes:

      	<Nodeset> ::= (<Node> ...)

Nodesets, and Nodes other than text strings are both lists. A <Nodeset> however is either an empty list, or a list whose head is not a symbol. A symbol at the head of a node is either an XML name (in which case it's a tag of an XML element), or an administrative name such as '@'. This uniform list representation makes processing rather simple and elegant, while avoiding confusion. The multi-branch tree structure formed by the mutually-recursive datatypes <Node> and <Nodeset> lends itself well to processing by functional languages.

A location path is in fact a composite query over an XPath tree or its branch. A singe step is a combination of a projection, selection or a transitive closure. Multiple steps are combined via join and union operations. This insight allows us to elegantly implement XPath as a sequence of projection and filtering primitives -- converters -- joined by combinators. Each converter takes a node and returns a nodeset which is the result of the corresponding query relative to that node. A converter can also be called on a set of nodes. In that case it returns a union of the corresponding queries over each node in the set. The union is easily implemented as a list append operation as all nodes in a SXML tree are considered distinct, by XPath conventions. We also preserve the order of the members in the union. Query combinators are high-order functions: they take converter(s) (which is a Node|Nodeset -> Nodeset function) and compose or otherwise combine them. We will be concerned with only relative location paths [XPath]: an absolute location path is a relative path applied to the root node.

Similarly to XPath, SXPath defines full and abbreviated notations for location paths. In both cases, the abbreviated notation can be mechanically expanded into the full form by simple rewriting rules. In case of SXPath the corresponding rules are given as comments to a sxpath function, below. The regression test suite at the end of this file shows a representative sample of SXPaths in both notations, juxtaposed with the corresponding XPath expressions. Most of the samples are borrowed literally from the XPath specification, while the others are adjusted for our running example, tree1.

Usage
.....

nodeset? x

node-typeof? crit

node-eq? other

node-equal? other

node-pos n

filter pred?
 -- Scheme Procedure: filter pred list
     Return all the elements of 2nd arg LIST that satisfy predicate
     PRED.  The list is not disordered - elements that appear in the
     result list occur in the same order as they occur in the argument
     list. The returned list may share a common tail with the argument
     list. The dynamic order in which the various applications of pred
     are made is not specified.

          (filter even? '(0 7 8 8 43 -4)) => (0 8 8 -4)

take-until pred?

take-after pred?

map-union proc lst

node-reverse node-or-nodeset

node-trace title

select-kids test-pred?

node-self pred?
 -- Scheme Procedure: filter pred list
     Return all the elements of 2nd arg LIST that satisfy predicate
     PRED.  The list is not disordered - elements that appear in the
     result list occur in the same order as they occur in the argument
     list. The returned list may share a common tail with the argument
     list. The dynamic order in which the various applications of pred
     are made is not specified.

          (filter even? '(0 7 8 8 43 -4)) => (0 8 8 -4)

node-join . selectors

node-reduce . converters

node-or . converters

node-closure test-pred?

node-parent rootnode

sxpath path