diff options
Diffstat (limited to 'doc/ref/sxml-match.texi')
-rw-r--r-- | doc/ref/sxml-match.texi | 377 |
1 files changed, 377 insertions, 0 deletions
diff --git a/doc/ref/sxml-match.texi b/doc/ref/sxml-match.texi new file mode 100644 index 000000000..3adf34751 --- /dev/null +++ b/doc/ref/sxml-match.texi @@ -0,0 +1,377 @@ +@c -*-texinfo-*- +@c This is part of the GNU Guile Reference Manual. +@c Copyright (C) 2010, 2013 Free Software Foundation, Inc. +@c See the file guile.texi for copying conditions. +@c +@c Based on the documentation at +@c <http://planet.plt-scheme.org/package-source/jim/sxml-match.plt/1/1/doc.txt>, +@c copyright 2005 Jim Bender, and released under the MIT/X11 license (like the +@c rest of `sxml-match'.) +@c +@c Converted to Texinfo and modified by Ludovic Courtès, 2010. + +@node sxml-match +@section @code{sxml-match}: Pattern Matching of SXML + +@cindex pattern matching (SXML) +@cindex SXML pattern matching + +The @code{(sxml match)} module provides syntactic forms for pattern +matching of SXML trees, in a ``by example'' style reminiscent of the +pattern matching of the @code{syntax-rules} and @code{syntax-case} macro +systems. @xref{SXML}, for more information on SXML. + +The following example@footnote{This example is taken from a paper by +Krishnamurthi et al. Their paper was the first to show the usefulness of the +@code{syntax-rules} style of pattern matching for transformation of XML, though +the language described, XT3D, is an XML language.} provides a brief +illustration, transforming a music album catalog language into HTML. + +@lisp +(define (album->html x) + (sxml-match x + [(album (@@ (title ,t)) (catalog (num ,n) (fmt ,f)) ...) + `(ul (li ,t) + (li (b ,n) (i ,f)) ...)])) +@end lisp + +Three macros are provided: @code{sxml-match}, @code{sxml-match-let}, and +@code{sxml-match-let*}. + +Compared to a standard s-expression pattern matcher (@pxref{Pattern +Matching}), @code{sxml-match} provides the following benefits: + +@itemize +@item +matching of SXML elements does not depend on any degree of normalization of the +SXML; +@item +matching of SXML attributes (within an element) is under-ordered; the order of +the attributes specified within the pattern need not match the ordering with the +element being matched; +@item +all attributes specified in the pattern must be present in the element being +matched; in the spirit that XML is 'extensible', the element being matched may +include additional attributes not specified in the pattern. +@end itemize + +The present module is a descendant of WebIt!, and was inspired by an +s-expression pattern matcher developed by Erik Hilsdale, Dan Friedman, and Kent +Dybvig at Indiana University. + +@unnumberedsubsec Syntax + +@code{sxml-match} provides @code{case}-like form for pattern matching of XML +nodes. + +@deffn {Scheme Syntax} sxml-match input-expression clause1 clause2 @dots{} +Match @var{input-expression}, an SXML tree, according to the given @var{clause}s +(one or more), each consisting of a pattern and one or more expressions to be +evaluated if the pattern match succeeds. Optionally, each @var{clause} within +@code{sxml-match} may include a @dfn{guard expression}. +@end deffn + +The pattern notation is based on that of Scheme's @code{syntax-rules} and +@code{syntax-case} macro systems. The grammar for the @code{sxml-match} syntax +is given below: + +@verbatim +match-form ::= (sxml-match input-expression + clause+) + +clause ::= [node-pattern action-expression+] + | [node-pattern (guard expression*) action-expression+] + +node-pattern ::= literal-pattern + | pat-var-or-cata + | element-pattern + | list-pattern + +literal-pattern ::= string + | character + | number + | #t + | #f + +attr-list-pattern ::= (@ attribute-pattern*) + | (@ attribute-pattern* . pat-var-or-cata) + +attribute-pattern ::= (tag-symbol attr-val-pattern) + +attr-val-pattern ::= literal-pattern + | pat-var-or-cata + | (pat-var-or-cata default-value-expr) + +element-pattern ::= (tag-symbol attr-list-pattern?) + | (tag-symbol attr-list-pattern? nodeset-pattern) + | (tag-symbol attr-list-pattern? + nodeset-pattern? . pat-var-or-cata) + +list-pattern ::= (list nodeset-pattern) + | (list nodeset-pattern? . pat-var-or-cata) + | (list) + +nodeset-pattern ::= node-pattern + | node-pattern ... + | node-pattern nodeset-pattern + | node-pattern ... nodeset-pattern + +pat-var-or-cata ::= (unquote var-symbol) + | (unquote [var-symbol*]) + | (unquote [cata-expression -> var-symbol*]) +@end verbatim + +Within a list or element body pattern, ellipses may appear only once, but may be +followed by zero or more node patterns. + +Guard expressions cannot refer to the return values of catamorphisms. + +Ellipses in the output expressions must appear only in an expression context; +ellipses are not allowed in a syntactic form. + +The sections below illustrate specific aspects of the @code{sxml-match} pattern +matcher. + +@unnumberedsubsec Matching XML Elements + +The example below illustrates the pattern matching of an XML element: + +@lisp +(sxml-match '(e (@@ (i 1)) 3 4 5) + [(e (@@ (i ,d)) ,a ,b ,c) (list d a b c)] + [,otherwise #f]) +@end lisp + +Each clause in @code{sxml-match} contains two parts: a pattern and one or more +expressions which are evaluated if the pattern is successfully match. The +example above matches an element @code{e} with an attribute @code{i} and three +children. + +Pattern variables must be ``unquoted'' in the pattern. The above expression +binds @var{d} to @code{1}, @var{a} to @code{3}, @var{b} to @code{4}, and @var{c} +to @code{5}. + +@unnumberedsubsec Ellipses in Patterns + +As in @code{syntax-rules}, ellipses may be used to specify a repeated pattern. +Note that the pattern @code{item ...} specifies zero-or-more matches of the +pattern @code{item}. + +The use of ellipses in a pattern is illustrated in the code fragment below, +where nested ellipses are used to match the children of repeated instances of an +@code{a} element, within an element @code{d}. + +@lisp +(define x '(d (a 1 2 3) (a 4 5) (a 6 7 8) (a 9 10))) + +(sxml-match x + [(d (a ,b ...) ...) + (list (list b ...) ...)]) +@end lisp + +The above expression returns a value of @code{((1 2 3) (4 5) (6 7 8) (9 10))}. + +@unnumberedsubsec Ellipses in Quasiquote'd Output + +Within the body of an @code{sxml-match} form, a slightly extended version of +quasiquote is provided, which allows the use of ellipses. This is illustrated +in the example below. + +@lisp +(sxml-match '(e 3 4 5 6 7) + [(e ,i ... 6 7) `("start" ,(list 'wrap i) ... "end")] + [,otherwise #f]) +@end lisp + +The general pattern is that @code{`(something ,i ...)} is rewritten as +@code{`(something ,@@i)}. + +@unnumberedsubsec Matching Nodesets + +A nodeset pattern is designated by a list in the pattern, beginning the +identifier list. The example below illustrates matching a nodeset. + +@lisp +(sxml-match '("i" "j" "k" "l" "m") + [(list ,a ,b ,c ,d ,e) + `((p ,a) (p ,b) (p ,c) (p ,d) (p ,e))]) +@end lisp + +This example wraps each nodeset item in an HTML paragraph element. This example +can be rewritten and simplified through using ellipsis: + +@lisp +(sxml-match '("i" "j" "k" "l" "m") + [(list ,i ...) + `((p ,i) ...)]) +@end lisp + +This version will match nodesets of any length, and wrap each item in the +nodeset in an HTML paragraph element. + +@unnumberedsubsec Matching the ``Rest'' of a Nodeset + +Matching the ``rest'' of a nodeset is achieved by using a @code{. rest)} pattern +at the end of an element or nodeset pattern. + +This is illustrated in the example below: + +@lisp +(sxml-match '(e 3 (f 4 5 6) 7) + [(e ,a (f . ,y) ,d) + (list a y d)]) +@end lisp + +The above expression returns @code{(3 (4 5 6) 7)}. + +@unnumberedsubsec Matching the Unmatched Attributes + +Sometimes it is useful to bind a list of attributes present in the element being +matched, but which do not appear in the pattern. This is achieved by using a +@code{. rest)} pattern at the end of the attribute list pattern. This is +illustrated in the example below: + +@lisp +(sxml-match '(a (@@ (z 1) (y 2) (x 3)) 4 5 6) + [(a (@@ (y ,www) . ,qqq) ,t ,u ,v) + (list www qqq t u v)]) +@end lisp + +The above expression matches the attribute @code{y} and binds a list of the +remaining attributes to the variable @var{qqq}. The result of the above +expression is @code{(2 ((z 1) (x 3)) 4 5 6)}. + +This type of pattern also allows the binding of all attributes: + +@lisp +(sxml-match '(a (@@ (z 1) (y 2) (x 3))) + [(a (@@ . ,qqq)) + qqq]) +@end lisp + +@unnumberedsubsec Default Values in Attribute Patterns + +It is possible to specify a default value for an attribute which is used if the +attribute is not present in the element being matched. This is illustrated in +the following example: + +@lisp +(sxml-match '(e 3 4 5) + [(e (@@ (z (,d 1))) ,a ,b ,c) (list d a b c)]) +@end lisp + +The value @code{1} is used when the attribute @code{z} is absent from the +element @code{e}. + +@unnumberedsubsec Guards in Patterns + +Guards may be added to a pattern clause via the @code{guard} keyword. A guard +expression may include zero or more expressions which are evaluated only if the +pattern is matched. The body of the clause is only evaluated if the guard +expressions evaluate to @code{#t}. + +The use of guard expressions is illustrated below: + +@lisp +(sxml-match '(a 2 3) + ((a ,n) (guard (number? n)) n) + ((a ,m ,n) (guard (number? m) (number? n)) (+ m n))) +@end lisp + +@unnumberedsubsec Catamorphisms + +The example below illustrates the use of explicit recursion within an +@code{sxml-match} form. This example implements a simple calculator for the +basic arithmetic operations, which are represented by the XML elements +@code{plus}, @code{minus}, @code{times}, and @code{div}. + +@lisp +(define simple-eval + (lambda (x) + (sxml-match x + [,i (guard (integer? i)) i] + [(plus ,x ,y) (+ (simple-eval x) (simple-eval y))] + [(times ,x ,y) (* (simple-eval x) (simple-eval y))] + [(minus ,x ,y) (- (simple-eval x) (simple-eval y))] + [(div ,x ,y) (/ (simple-eval x) (simple-eval y))] + [,otherwise (error "simple-eval: invalid expression" x)]))) +@end lisp + +Using the catamorphism feature of @code{sxml-match}, a more concise version of +@code{simple-eval} can be written. The pattern @code{,[x]} recursively invokes +the pattern matcher on the value bound in this position. + +@lisp +(define simple-eval + (lambda (x) + (sxml-match x + [,i (guard (integer? i)) i] + [(plus ,[x] ,[y]) (+ x y)] + [(times ,[x] ,[y]) (* x y)] + [(minus ,[x] ,[y]) (- x y)] + [(div ,[x] ,[y]) (/ x y)] + [,otherwise (error "simple-eval: invalid expression" x)]))) +@end lisp + +@unnumberedsubsec Named-Catamorphisms + +It is also possible to explicitly name the operator in the ``cata'' position. +Where @code{,[id*]} recurs to the top of the current @code{sxml-match}, +@code{,[cata -> id*]} recurs to @code{cata}. @code{cata} must evaluate to a +procedure which takes one argument, and returns as many values as there are +identifiers following @code{->}. + +Named catamorphism patterns allow processing to be split into multiple, mutually +recursive procedures. This is illustrated in the example below: a +transformation that formats a ``TV Guide'' into HTML. + +@lisp +(define (tv-guide->html g) + (define (cast-list cl) + (sxml-match cl + [(CastList (CastMember (Character (Name ,ch)) (Actor (Name ,a))) ...) + `(div (ul (li ,ch ": " ,a) ...))])) + (define (prog p) + (sxml-match p + [(Program (Start ,start-time) (Duration ,dur) (Series ,series-title) + (Description ,desc ...)) + `(div (p ,start-time + (br) ,series-title + (br) ,desc ...))] + [(Program (Start ,start-time) (Duration ,dur) (Series ,series-title) + (Description ,desc ...) + ,[cast-list -> cl]) + `(div (p ,start-time + (br) ,series-title + (br) ,desc ...) + ,cl)])) + (sxml-match g + [(TVGuide (@@ (start ,start-date) + (end ,end-date)) + (Channel (Name ,nm) ,[prog -> p] ...) ...) + `(html (head (title "TV Guide")) + (body (h1 "TV Guide") + (div (h2 ,nm) ,p ...) ...))])) +@end lisp + +@unnumberedsubsec @code{sxml-match-let} and @code{sxml-match-let*} + +@deffn {Scheme Syntax} sxml-match-let ((pat expr) ...) expression0 expression ... +@deffnx {Scheme Syntax} sxml-match-let* ((pat expr) ...) expression0 expression ... +These forms generalize the @code{let} and @code{let*} forms of Scheme to allow +an XML pattern in the binding position, rather than a simple variable. +@end deffn + +For example, the expression below: + +@lisp +(sxml-match-let ([(a ,i ,j) '(a 1 2)]) + (+ i j)) +@end lisp + +binds the variables @var{i} and @var{j} to @code{1} and @code{2} in the XML +value given. + +@c Local Variables: +@c coding: utf-8 +@c End: |