compiling XPath to Scheme source code

  Hello all,

  I'm working on translating XPath expressions to Scheme
source code which evaluates the XPath. As a proof of concept
I translated some expressions which test XPath issues. Here
are these expressions:

/usr/bin/xmllint   # trivial xpath + referencing root node
/AAA/CCC           # resulted nodeset contains several nodes
//DDD/BBB          # test of 'descendant' axis
/AAA/*/*/BBB       # test of '*'
//BBB/@name        # test of 'attribute' axis
/AAA/BBB[1]        # selecting a node by its position
/AAA/BBB[last()]   # using a function to filter nodeset
/AAA/BBB[CCC]      # XPath in the predicate
  # nested predicates, relational operator
//openssh[.//sshd[@date<20040923]]
  # function in function
//bin/*[contains(name(), 'vi')]

  I'd like to get suggestions what other XPath issues should
be tested before starting to make a real implementation.

--

  Why compile to Scheme _source_ code?

  Some of the reasons:

* one can see what is going to be executed,

* it is possible to rewrite parts of the source code to make
  some sorts of optimization,

* in some cases it is possible to translate Scheme source code
  into the other programming languages,

* smart Scheme compiler can optimize code while compiling it.

  Your ideas are welcome.

--

  An example of simple XPath.

[example 1]

; Define a tree and an xpath expression
(define tree1 '(*top*
  (AAA (BBB) (CCC) (BBB) (BBB) (DDD (BBB)) (CCC))))
(define xpath-str1 "AAA/CCC")

; Translate the xpath to a Scheme source code
(define xpath-proc-src1 (xpath->scheme xpath-str1))
; A value of the variable "xpath-proc-src1" is:
;
;   (node-join
;     (sxml:child (ntype?? 'AAA))
;     (sxml:child (ntype?? 'CCC)))

; Compile the XPath code and execute it
(define xpath-proc1
  (eval xpath-proc-src1 (scheme-report-environment 5)))
(define result1 (xpath-proc1 tree1))
; A value of the variable "result1" is:
;
;    ((CCC) (CCC))

[/example 1]

--

  Referring the root node.

  The root node is stored in the XPath variable "*root*".
An XPath expression like

/AAA/CCC

  is interpreted like

$*root*/AAA/CCC

  So we don't need to pass root node as parameter, and
txpath's core function definitions can be simplified. The

(lambda (nodeset root-node context var-binding) ...)

  becomes

(lambda (nodeset context var-binding) ...)

--

  Binding of variables (on example of "*root*").

[example 2]

; Define variables.
(define tree2 tree1)            ; see example 1
(define xpath-str2 "/AAA/CCC")  ; like "AAA/CCC"

; Translate the xpath to a Scheme source code
(define xpath-proc-src2 (xpath->scheme xpath-str2))

; A value of the variable "xpath-proc-src2" is:

; (node-join
;   *root*
;   (sxml:child (ntype?? 'AAA))
;   (sxml:child (ntype?? 'CCC)))
;
; "eval" will fail on this expression because the variable
; "*root*" is not bound. So the new step appears.

; Bind variables.
(define xpath-proc-src2b
  (sxlet ((*root* tree2)) xpath-proc-src2))

; A value of the variable "xpath-proc-src2" is:
;
; (let ((*root* (lambda (dummy) tree2)))
;      (node-join
;         *root*
;         (sxml:child (ntype?? 'AAA))
;         (sxml:child (ntype?? 'CCC))))
;
; This can be compiled and executed.

(define xpath-proc2
  (eval xpath-proc-src2b (scheme-report-environment 5)))
(define result2 (xpath-proc2 tree2))
;
;   ((CCC) (CCC))

  The variable "*root*" is indeed a lambda because the function
"node-join" expects only expressions of the type "converter"
(converter: (node|nodeset) -> nodeset).

  Now it is not required to pass bindings of XPath variables
because Scheme compiler can do it. And definitions of sxpath
library functions can be further simplified.

(lambda (nodeset root-node context var-binding) ...)

  becomes

(lambda (nodeset context) ...)

[/example 2]

--

  Filtering.

[example 3]

(define tree3 '(*top* (AAA "1") (AAA "2") (AAA "3")))
(define xpath-str3 "AAA[last()]")

(define xpath-proc-src3 (xpath->scheme xpath-str3))
;
; (node-join
;   (node-reduce
;     (sxml:child (ntype?? 'AAA))
;     (xpath-filter (scxml:core-last))))

(define xpath-proc3
  (eval xpath-proc-src3 (scheme-report-environment 5)))
(define result3 (xpath-proc3 tree3))
;
; ((AAA "3"))

[/example 3]

  The "xpath-filter" is indeed a macro. It does what it should
do (for each node, evaluates a predicate. If the result is
a number, then it filters by the position, else it filters by
the boolean value of result).

  The "side-effect" of "xpath-filter" (and reason why it is
a macro) is that it introduces Scheme variables:

- *contextNodeset*
- *contextNode*
- *contextTail*
- *contextPosition*

  The code of predicates can use these variables. For example,
"scxml:core-last" is macrodefined as:

(define-macro (scxml:core-last)
  `(lambda (unused-nodeset)
    (null? (cdr *contextTail*))))

Notes:

1) Essential part is "(null? (cdr *contextTail*))", the only
   use of lambda is to make type "converter").

2) Good Scheme compiler should remove unused variable
   *contextPosition* here.

  Now it is not required to pass context variables to the
predicates, and the definitions of sxpath library functions
can be simplified again.

(lambda (nodeset root-node context var-binding) ...)

  becomes

(lambda (nodeset) ...)


--

  The current code is available at

http://xmlhack.ru/protva/tmp/20041119_scpath.tar.gz

  The code is just a mess. It works only under Bigloo.
Don't look inside. I'm going to rewrite the code from scratch.
The only reason to show codes now is to prove the text above.

--

Regards, 

Oleg Paraschenko


-------------------------------------------------------
This SF.Net email is sponsored by: InterSystems CACHE
FREE OODBMS DOWNLOAD - A multidimensional database that combines
robust object and relational technologies, making it a perfect match
for Java, C++,COM, XML, ODBC and JDBC. www.intersystems.com/match8