Artifact
5feeeb3a6e444bf8ef7ae0e342e5bf2e6ce4865e:
0000: 3b 09 09 58 4d 4c 2f 48 54 4d 4c 20 70 72 6f 63 ;..XML/HTML proc
0010: 65 73 73 69 6e 67 20 69 6e 20 53 63 68 65 6d 65 essing in Scheme
0020: 0a 3b 09 09 53 58 4d 4c 20 65 78 70 72 65 73 73 .;..SXML express
0030: 69 6f 6e 20 74 72 65 65 20 74 72 61 6e 73 66 6f ion tree transfo
0040: 72 6d 65 72 73 0a 3b 0a 3b 20 49 4d 50 4f 52 54 rmers.;.; IMPORT
0050: 0a 3b 20 41 20 70 72 65 6c 75 64 65 20 61 70 70 .; A prelude app
0060: 72 6f 70 72 69 61 74 65 20 66 6f 72 20 79 6f 75 ropriate for you
0070: 72 20 53 63 68 65 6d 65 20 73 79 73 74 65 6d 0a r Scheme system.
0080: 3b 09 28 6d 79 65 6e 76 2d 62 69 67 6c 6f 6f 2e ;.(myenv-bigloo.
0090: 73 63 6d 2c 20 6d 79 65 6e 76 2d 6d 69 74 2e 73 scm, myenv-mit.s
00a0: 63 6d 2c 20 65 74 63 2e 29 0a 3b 0a 3b 20 45 58 cm, etc.).;.; EX
00b0: 50 4f 52 54 0a 3b 20 28 70 72 6f 76 69 64 65 20 PORT.; (provide
00c0: 53 52 56 3a 73 65 6e 64 2d 72 65 70 6c 79 0a 3b SRV:send-reply.;
00d0: 09 20 20 20 70 6f 73 74 2d 6f 72 64 65 72 20 70 . post-order p
00e0: 72 65 2d 70 6f 73 74 2d 6f 72 64 65 72 20 72 65 re-post-order re
00f0: 70 6c 61 63 65 2d 72 61 6e 67 65 29 0a 3b 0a 3b place-range).;.;
0100: 20 53 65 65 20 76 53 58 4d 4c 2d 74 72 65 65 2d See vSXML-tree-
0110: 74 72 61 6e 73 2e 73 63 6d 20 66 6f 72 20 74 68 trans.scm for th
0120: 65 20 76 61 6c 69 64 61 74 69 6f 6e 20 63 6f 64 e validation cod
0130: 65 2c 20 77 68 69 63 68 20 61 6c 73 6f 0a 3b 20 e, which also.;
0140: 73 65 72 76 65 73 20 61 73 20 75 73 61 67 65 20 serves as usage
0150: 65 78 61 6d 70 6c 65 73 2e 0a 3b 0a 3b 20 24 49 examples..;.; $I
0160: 64 3a 20 53 58 4d 4c 2d 74 72 65 65 2d 74 72 61 d: SXML-tree-tra
0170: 6e 73 2e 73 63 6d 2c 76 20 31 2e 36 20 32 30 30 ns.scm,v 1.6 200
0180: 33 2f 30 34 2f 32 35 20 31 39 3a 31 36 3a 31 35 3/04/25 19:16:15
0190: 20 6f 6c 65 67 20 45 78 70 20 24 0a 0a 0a 3b 20 oleg Exp $...;
01a0: 4f 75 74 70 75 74 20 74 68 65 20 27 66 72 61 67 Output the 'frag
01b0: 6d 65 6e 74 73 27 0a 3b 20 54 68 65 20 66 72 61 ments'.; The fra
01c0: 67 6d 65 6e 74 73 20 61 72 65 20 61 20 6c 69 73 gments are a lis
01d0: 74 20 6f 66 20 73 74 72 69 6e 67 73 2c 20 63 68 t of strings, ch
01e0: 61 72 61 63 74 65 72 73 2c 0a 3b 20 6e 75 6d 62 aracters,.; numb
01f0: 65 72 73 2c 20 74 68 75 6e 6b 73 2c 20 23 66 2c ers, thunks, #f,
0200: 20 23 74 20 2d 2d 20 61 6e 64 20 6f 74 68 65 72 #t -- and other
0210: 20 66 72 61 67 6d 65 6e 74 73 2e 0a 3b 20 54 68 fragments..; Th
0220: 65 20 66 75 6e 63 74 69 6f 6e 20 74 72 61 76 65 e function trave
0230: 72 73 65 73 20 74 68 65 20 74 72 65 65 20 64 65 rses the tree de
0240: 70 74 68 2d 66 69 72 73 74 2c 20 77 72 69 74 65 pth-first, write
0250: 73 20 6f 75 74 0a 3b 20 73 74 72 69 6e 67 73 20 s out.; strings
0260: 61 6e 64 20 63 68 61 72 61 63 74 65 72 73 2c 20 and characters,
0270: 65 78 65 63 75 74 65 73 20 74 68 75 6e 6b 73 2c executes thunks,
0280: 20 61 6e 64 20 69 67 6e 6f 72 65 73 0a 3b 20 23 and ignores.; #
0290: 66 20 61 6e 64 20 27 28 29 2e 0a 3b 20 54 68 65 f and '()..; The
02a0: 20 66 75 6e 63 74 69 6f 6e 20 72 65 74 75 72 6e function return
02b0: 73 20 23 74 20 69 66 20 61 6e 79 74 68 69 6e 67 s #t if anything
02c0: 20 77 61 73 20 77 72 69 74 74 65 6e 20 61 74 20 was written at
02d0: 61 6c 6c 3b 0a 3b 20 6f 74 68 65 72 77 69 73 65 all;.; otherwise
02e0: 20 74 68 65 20 72 65 73 75 6c 74 20 69 73 20 23 the result is #
02f0: 66 0a 3b 20 49 66 20 23 74 20 6f 63 63 75 72 73 f.; If #t occurs
0300: 20 61 6d 6f 6e 67 20 74 68 65 20 66 72 61 67 6d among the fragm
0310: 65 6e 74 73 2c 20 69 74 20 69 73 20 6e 6f 74 20 ents, it is not
0320: 77 72 69 74 74 65 6e 20 6f 75 74 0a 3b 20 62 75 written out.; bu
0330: 74 20 63 61 75 73 65 73 20 74 68 65 20 72 65 73 t causes the res
0340: 75 6c 74 20 6f 66 20 53 52 56 3a 73 65 6e 64 2d ult of SRV:send-
0350: 72 65 70 6c 79 20 74 6f 20 62 65 20 23 74 0a 0a reply to be #t..
0360: 28 64 65 66 69 6e 65 20 28 53 52 56 3a 73 65 6e (define (SRV:sen
0370: 64 2d 72 65 70 6c 79 20 2e 20 66 72 61 67 6d 65 d-reply . fragme
0380: 6e 74 73 29 0a 20 20 28 6c 65 74 20 6c 6f 6f 70 nts). (let loop
0390: 20 28 28 66 72 61 67 6d 65 6e 74 73 20 66 72 61 ((fragments fra
03a0: 67 6d 65 6e 74 73 29 20 28 72 65 73 75 6c 74 20 gments) (result
03b0: 23 66 29 29 0a 20 20 20 20 28 63 6f 6e 64 0a 20 #f)). (cond.
03c0: 20 20 20 20 20 28 28 6e 75 6c 6c 3f 20 66 72 61 ((null? fra
03d0: 67 6d 65 6e 74 73 29 20 72 65 73 75 6c 74 29 0a gments) result).
03e0: 20 20 20 20 20 20 28 28 6e 6f 74 20 28 63 61 72 ((not (car
03f0: 20 66 72 61 67 6d 65 6e 74 73 29 29 20 28 6c 6f fragments)) (lo
0400: 6f 70 20 28 63 64 72 20 66 72 61 67 6d 65 6e 74 op (cdr fragment
0410: 73 29 20 72 65 73 75 6c 74 29 29 0a 20 20 20 20 s) result)).
0420: 20 20 28 28 6e 75 6c 6c 3f 20 28 63 61 72 20 66 ((null? (car f
0430: 72 61 67 6d 65 6e 74 73 29 29 20 28 6c 6f 6f 70 ragments)) (loop
0440: 20 28 63 64 72 20 66 72 61 67 6d 65 6e 74 73 29 (cdr fragments)
0450: 20 72 65 73 75 6c 74 29 29 0a 20 20 20 20 20 20 result)).
0460: 28 28 65 71 3f 20 23 74 20 28 63 61 72 20 66 72 ((eq? #t (car fr
0470: 61 67 6d 65 6e 74 73 29 29 20 28 6c 6f 6f 70 20 agments)) (loop
0480: 28 63 64 72 20 66 72 61 67 6d 65 6e 74 73 29 20 (cdr fragments)
0490: 23 74 29 29 0a 20 20 20 20 20 20 28 28 70 61 69 #t)). ((pai
04a0: 72 3f 20 28 63 61 72 20 66 72 61 67 6d 65 6e 74 r? (car fragment
04b0: 73 29 29 0a 20 20 20 20 20 20 20 20 28 6c 6f 6f s)). (loo
04c0: 70 20 28 63 64 72 20 66 72 61 67 6d 65 6e 74 73 p (cdr fragments
04d0: 29 20 28 6c 6f 6f 70 20 28 63 61 72 20 66 72 61 ) (loop (car fra
04e0: 67 6d 65 6e 74 73 29 20 72 65 73 75 6c 74 29 29 gments) result))
04f0: 29 0a 20 20 20 20 20 20 28 28 70 72 6f 63 65 64 ). ((proced
0500: 75 72 65 3f 20 28 63 61 72 20 66 72 61 67 6d 65 ure? (car fragme
0510: 6e 74 73 29 29 0a 20 20 20 20 20 20 20 20 28 28 nts)). ((
0520: 63 61 72 20 66 72 61 67 6d 65 6e 74 73 29 29 0a car fragments)).
0530: 20 20 20 20 20 20 20 20 28 6c 6f 6f 70 20 28 63 (loop (c
0540: 64 72 20 66 72 61 67 6d 65 6e 74 73 29 20 23 74 dr fragments) #t
0550: 29 29 0a 20 20 20 20 20 20 28 65 6c 73 65 0a 20 )). (else.
0560: 20 20 20 20 20 20 20 28 64 69 73 70 6c 61 79 20 (display
0570: 28 63 61 72 20 66 72 61 67 6d 65 6e 74 73 29 29 (car fragments))
0580: 0a 20 20 20 20 20 20 20 20 28 6c 6f 6f 70 20 28 . (loop (
0590: 63 64 72 20 66 72 61 67 6d 65 6e 74 73 29 20 23 cdr fragments) #
05a0: 74 29 29 29 29 29 0a 0a 0a 0a 3b 2d 2d 2d 2d 2d t)))))....;-----
05b0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
05c0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
05d0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
05e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
05f0: 2d 2d 2d 0a 3b 09 20 20 20 20 20 20 20 20 20 20 ---.;.
0600: 54 72 61 76 65 72 73 61 6c 20 6f 66 20 61 6e 20 Traversal of an
0610: 53 58 4d 4c 20 74 72 65 65 20 6f 72 20 61 20 67 SXML tree or a g
0620: 72 6f 76 65 3a 0a 3b 09 09 09 61 20 3c 4e 6f 64 rove:.;...a <Nod
0630: 65 3e 20 6f 72 20 61 20 3c 4e 6f 64 65 6c 69 73 e> or a <Nodelis
0640: 74 3e 0a 3b 0a 3b 20 41 20 3c 4e 6f 64 65 3e 20 t>.;.; A <Node>
0650: 61 6e 64 20 61 20 3c 4e 6f 64 65 6c 69 73 74 3e and a <Nodelist>
0660: 20 61 72 65 20 6d 75 74 75 61 6c 6c 79 2d 72 65 are mutually-re
0670: 63 75 72 73 69 76 65 20 64 61 74 61 74 79 70 65 cursive datatype
0680: 73 20 74 68 61 74 0a 3b 20 75 6e 64 65 72 6c 69 s that.; underli
0690: 65 20 74 68 65 20 53 58 4d 4c 20 74 72 65 65 3a e the SXML tree:
06a0: 0a 3b 09 3c 4e 6f 64 65 3e 20 3a 3a 3d 20 28 6e .;.<Node> ::= (n
06b0: 61 6d 65 20 2e 20 3c 4e 6f 64 65 6c 69 73 74 3e ame . <Nodelist>
06c0: 29 20 7c 20 22 74 65 78 74 20 73 74 72 69 6e 67 ) | "text string
06d0: 22 0a 3b 20 41 6e 20 28 6f 72 64 65 72 65 64 29 ".; An (ordered)
06e0: 20 73 65 74 20 6f 66 20 6e 6f 64 65 73 20 69 73 set of nodes is
06f0: 20 6a 75 73 74 20 61 20 6c 69 73 74 20 6f 66 20 just a list of
0700: 74 68 65 20 63 6f 6e 73 74 69 74 75 65 6e 74 20 the constituent
0710: 6e 6f 64 65 73 3a 0a 3b 20 09 3c 4e 6f 64 65 6c nodes:.; .<Nodel
0720: 69 73 74 3e 20 3a 3a 3d 20 28 3c 4e 6f 64 65 3e ist> ::= (<Node>
0730: 20 2e 2e 2e 29 0a 3b 20 4e 6f 64 65 6c 69 73 74 ...).; Nodelist
0740: 73 2c 20 61 6e 64 20 4e 6f 64 65 73 20 6f 74 68 s, and Nodes oth
0750: 65 72 20 74 68 61 6e 20 74 65 78 74 20 73 74 72 er than text str
0760: 69 6e 67 73 20 61 72 65 20 62 6f 74 68 20 6c 69 ings are both li
0770: 73 74 73 2e 20 41 0a 3b 20 3c 4e 6f 64 65 6c 69 sts. A.; <Nodeli
0780: 73 74 3e 20 68 6f 77 65 76 65 72 20 69 73 20 65 st> however is e
0790: 69 74 68 65 72 20 61 6e 20 65 6d 70 74 79 20 6c ither an empty l
07a0: 69 73 74 2c 20 6f 72 20 61 20 6c 69 73 74 20 77 ist, or a list w
07b0: 68 6f 73 65 20 68 65 61 64 20 69 73 0a 3b 20 6e hose head is.; n
07c0: 6f 74 20 61 20 73 79 6d 62 6f 6c 20 28 61 6e 20 ot a symbol (an
07d0: 61 74 6f 6d 20 69 6e 20 67 65 6e 65 72 61 6c 29 atom in general)
07e0: 2e 20 41 20 73 79 6d 62 6f 6c 20 61 74 20 74 68 . A symbol at th
07f0: 65 20 68 65 61 64 20 6f 66 20 61 20 6e 6f 64 65 e head of a node
0800: 20 69 73 0a 3b 20 65 69 74 68 65 72 20 61 6e 20 is.; either an
0810: 58 4d 4c 20 6e 61 6d 65 20 28 69 6e 20 77 68 69 XML name (in whi
0820: 63 68 20 63 61 73 65 20 69 74 27 73 20 61 20 74 ch case it's a t
0830: 61 67 20 6f 66 20 61 6e 20 58 4d 4c 20 65 6c 65 ag of an XML ele
0840: 6d 65 6e 74 29 2c 20 6f 72 0a 3b 20 61 6e 20 61 ment), or.; an a
0850: 64 6d 69 6e 69 73 74 72 61 74 69 76 65 20 6e 61 dministrative na
0860: 6d 65 20 73 75 63 68 20 61 73 20 27 40 27 2e 0a me such as '@'..
0870: 3b 20 53 65 65 20 53 58 50 61 74 68 2e 73 63 6d ; See SXPath.scm
0880: 20 61 6e 64 20 53 53 41 58 2e 73 63 6d 20 66 6f and SSAX.scm fo
0890: 72 20 6d 6f 72 65 20 69 6e 66 6f 72 6d 61 74 69 r more informati
08a0: 6f 6e 20 6f 6e 20 53 58 4d 4c 2e 0a 0a 0a 3b 20 on on SXML....;
08b0: 50 72 65 2d 50 6f 73 74 2d 6f 72 64 65 72 20 74 Pre-Post-order t
08c0: 72 61 76 65 72 73 61 6c 20 6f 66 20 61 20 74 72 raversal of a tr
08d0: 65 65 20 61 6e 64 20 63 72 65 61 74 69 6f 6e 20 ee and creation
08e0: 6f 66 20 61 20 6e 65 77 20 74 72 65 65 3a 0a 3b of a new tree:.;
08f0: 09 70 72 65 2d 70 6f 73 74 2d 6f 72 64 65 72 3a .pre-post-order:
0900: 3a 20 3c 74 72 65 65 3e 20 78 20 3c 62 69 6e 64 : <tree> x <bind
0910: 69 6e 67 73 3e 20 2d 3e 20 3c 6e 65 77 2d 74 72 ings> -> <new-tr
0920: 65 65 3e 0a 3b 20 77 68 65 72 65 0a 3b 20 3c 62 ee>.; where.; <b
0930: 69 6e 64 69 6e 67 73 3e 20 3a 3a 3d 20 28 3c 62 indings> ::= (<b
0940: 69 6e 64 69 6e 67 3e 20 2e 2e 2e 29 0a 3b 20 3c inding> ...).; <
0950: 62 69 6e 64 69 6e 67 3e 20 3a 3a 3d 20 28 3c 74 binding> ::= (<t
0960: 72 69 67 67 65 72 2d 73 79 6d 62 6f 6c 3e 20 2a rigger-symbol> *
0970: 70 72 65 6f 72 64 65 72 2a 20 2e 20 3c 68 61 6e preorder* . <han
0980: 64 6c 65 72 3e 29 20 7c 0a 3b 20 20 20 20 20 20 dler>) |.;
0990: 20 20 20 20 20 20 20 20 20 28 3c 74 72 69 67 67 (<trigg
09a0: 65 72 2d 73 79 6d 62 6f 6c 3e 20 2a 6d 61 63 72 er-symbol> *macr
09b0: 6f 2a 20 2e 20 3c 68 61 6e 64 6c 65 72 3e 29 20 o* . <handler>)
09c0: 7c 0a 3b 09 09 28 3c 74 72 69 67 67 65 72 2d 73 |.;..(<trigger-s
09d0: 79 6d 62 6f 6c 3e 20 3c 6e 65 77 2d 62 69 6e 64 ymbol> <new-bind
09e0: 69 6e 67 73 3e 20 2e 20 3c 68 61 6e 64 6c 65 72 ings> . <handler
09f0: 3e 29 20 7c 0a 3b 09 09 28 3c 74 72 69 67 67 65 >) |.;..(<trigge
0a00: 72 2d 73 79 6d 62 6f 6c 3e 20 2e 20 3c 68 61 6e r-symbol> . <han
0a10: 64 6c 65 72 3e 29 0a 3b 20 3c 74 72 69 67 67 65 dler>).; <trigge
0a20: 72 2d 73 79 6d 62 6f 6c 3e 20 3a 3a 3d 20 58 4d r-symbol> ::= XM
0a30: 4c 6e 61 6d 65 20 7c 20 2a 74 65 78 74 2a 20 7c Lname | *text* |
0a40: 20 2a 64 65 66 61 75 6c 74 2a 0a 3b 20 3c 68 61 *default*.; <ha
0a50: 6e 64 6c 65 72 3e 20 3a 3a 20 3c 74 72 69 67 67 ndler> :: <trigg
0a60: 65 72 2d 73 79 6d 62 6f 6c 3e 20 78 20 5b 3c 74 er-symbol> x [<t
0a70: 72 65 65 3e 5d 20 2d 3e 20 3c 6e 65 77 2d 74 72 ree>] -> <new-tr
0a80: 65 65 3e 0a 3b 0a 3b 20 54 68 65 20 70 72 65 2d ee>.;.; The pre-
0a90: 70 6f 73 74 2d 6f 72 64 65 72 20 66 75 6e 63 74 post-order funct
0aa0: 69 6f 6e 20 76 69 73 69 74 73 20 74 68 65 20 6e ion visits the n
0ab0: 6f 64 65 73 20 61 6e 64 20 6e 6f 64 65 6c 69 73 odes and nodelis
0ac0: 74 73 0a 3b 20 70 72 65 2d 70 6f 73 74 2d 6f 72 ts.; pre-post-or
0ad0: 64 65 72 20 28 64 65 70 74 68 2d 66 69 72 73 74 der (depth-first
0ae0: 29 2e 20 20 46 6f 72 20 65 61 63 68 20 3c 4e 6f ). For each <No
0af0: 64 65 3e 20 6f 66 20 74 68 65 20 66 6f 72 6d 20 de> of the form
0b00: 28 6e 61 6d 65 0a 3b 20 3c 4e 6f 64 65 3e 20 2e (name.; <Node> .
0b10: 2e 2e 29 20 69 74 20 6c 6f 6f 6b 73 20 75 70 20 ..) it looks up
0b20: 61 6e 20 61 73 73 6f 63 69 61 74 69 6f 6e 20 77 an association w
0b30: 69 74 68 20 74 68 65 20 67 69 76 65 6e 20 27 6e ith the given 'n
0b40: 61 6d 65 27 20 61 6d 6f 6e 67 0a 3b 20 69 74 73 ame' among.; its
0b50: 20 3c 62 69 6e 64 69 6e 67 73 3e 2e 20 49 66 20 <bindings>. If
0b60: 66 61 69 6c 65 64 2c 20 70 72 65 2d 70 6f 73 74 failed, pre-post
0b70: 2d 6f 72 64 65 72 20 74 72 69 65 73 20 74 6f 20 -order tries to
0b80: 6c 6f 63 61 74 65 20 61 0a 3b 20 2a 64 65 66 61 locate a.; *defa
0b90: 75 6c 74 2a 20 62 69 6e 64 69 6e 67 2e 20 49 74 ult* binding. It
0ba0: 27 73 20 61 6e 20 65 72 72 6f 72 20 69 66 20 74 's an error if t
0bb0: 68 65 20 6c 61 74 74 65 72 20 61 74 74 65 6d 70 he latter attemp
0bc0: 74 20 66 61 69 6c 73 20 61 73 0a 3b 20 77 65 6c t fails as.; wel
0bd0: 6c 2e 20 20 48 61 76 69 6e 67 20 66 6f 75 6e 64 l. Having found
0be0: 20 61 20 62 69 6e 64 69 6e 67 2c 20 74 68 65 20 a binding, the
0bf0: 70 72 65 2d 70 6f 73 74 2d 6f 72 64 65 72 20 66 pre-post-order f
0c00: 75 6e 63 74 69 6f 6e 20 66 69 72 73 74 0a 3b 20 unction first.;
0c10: 63 68 65 63 6b 73 20 74 6f 20 73 65 65 20 69 66 checks to see if
0c20: 20 74 68 65 20 62 69 6e 64 69 6e 67 20 69 73 20 the binding is
0c30: 6f 66 20 74 68 65 20 66 6f 72 6d 0a 3b 09 28 3c of the form.;.(<
0c40: 74 72 69 67 67 65 72 2d 73 79 6d 62 6f 6c 3e 20 trigger-symbol>
0c50: 2a 70 72 65 6f 72 64 65 72 2a 20 2e 20 3c 68 61 *preorder* . <ha
0c60: 6e 64 6c 65 72 3e 29 0a 3b 20 49 66 20 69 74 20 ndler>).; If it
0c70: 69 73 2c 20 74 68 65 20 68 61 6e 64 6c 65 72 20 is, the handler
0c80: 69 73 20 27 61 70 70 6c 69 65 64 27 20 74 6f 20 is 'applied' to
0c90: 74 68 65 20 63 75 72 72 65 6e 74 20 6e 6f 64 65 the current node
0ca0: 2e 20 4f 74 68 65 72 77 69 73 65 2c 0a 3b 20 74 . Otherwise,.; t
0cb0: 68 65 20 70 72 65 2d 70 6f 73 74 2d 6f 72 64 65 he pre-post-orde
0cc0: 72 20 66 75 6e 63 74 69 6f 6e 20 66 69 72 73 74 r function first
0cd0: 20 63 61 6c 6c 73 20 69 74 73 65 6c 66 20 72 65 calls itself re
0ce0: 63 75 72 73 69 76 65 6c 79 20 66 6f 72 20 65 61 cursively for ea
0cf0: 63 68 0a 3b 20 63 68 69 6c 64 20 6f 66 20 74 68 ch.; child of th
0d00: 65 20 63 75 72 72 65 6e 74 20 6e 6f 64 65 2c 20 e current node,
0d10: 77 69 74 68 20 3c 6e 65 77 2d 62 69 6e 64 69 6e with <new-bindin
0d20: 67 73 3e 20 70 72 65 70 65 6e 64 65 64 20 74 6f gs> prepended to
0d30: 20 74 68 65 0a 3b 20 3c 62 69 6e 64 69 6e 67 73 the.; <bindings
0d40: 3e 20 69 6e 20 65 66 66 65 63 74 2e 20 54 68 65 > in effect. The
0d50: 20 72 65 73 75 6c 74 20 6f 66 20 74 68 65 73 65 result of these
0d60: 20 63 61 6c 6c 73 20 69 73 20 70 61 73 73 65 64 calls is passed
0d70: 20 74 6f 20 74 68 65 0a 3b 20 3c 68 61 6e 64 6c to the.; <handl
0d80: 65 72 3e 20 28 61 6c 6f 6e 67 20 77 69 74 68 20 er> (along with
0d90: 74 68 65 20 68 65 61 64 20 6f 66 20 74 68 65 20 the head of the
0da0: 63 75 72 72 65 6e 74 20 3c 4e 6f 64 65 3e 29 2e current <Node>).
0db0: 20 54 6f 20 62 65 20 6d 6f 72 65 0a 3b 20 70 72 To be more.; pr
0dc0: 65 63 69 73 65 2c 20 74 68 65 20 68 61 6e 64 6c ecise, the handl
0dd0: 65 72 20 69 73 20 5f 61 70 70 6c 69 65 64 5f 20 er is _applied_
0de0: 74 6f 20 74 68 65 20 68 65 61 64 20 6f 66 20 74 to the head of t
0df0: 68 65 20 63 75 72 72 65 6e 74 20 6e 6f 64 65 0a he current node.
0e00: 3b 20 61 6e 64 20 69 74 73 20 70 72 6f 63 65 73 ; and its proces
0e10: 73 65 64 20 63 68 69 6c 64 72 65 6e 2e 20 54 68 sed children. Th
0e20: 65 20 72 65 73 75 6c 74 20 6f 66 20 74 68 65 20 e result of the
0e30: 68 61 6e 64 6c 65 72 2c 20 77 68 69 63 68 20 73 handler, which s
0e40: 68 6f 75 6c 64 0a 3b 20 61 6c 73 6f 20 62 65 20 hould.; also be
0e50: 61 20 3c 74 72 65 65 3e 2c 20 72 65 70 6c 61 63 a <tree>, replac
0e60: 65 73 20 74 68 65 20 63 75 72 72 65 6e 74 20 3c es the current <
0e70: 4e 6f 64 65 3e 2e 20 49 66 20 74 68 65 20 63 75 Node>. If the cu
0e80: 72 72 65 6e 74 20 3c 4e 6f 64 65 3e 0a 3b 20 69 rrent <Node>.; i
0e90: 73 20 61 20 74 65 78 74 20 73 74 72 69 6e 67 20 s a text string
0ea0: 6f 72 20 6f 74 68 65 72 20 61 74 6f 6d 2c 20 61 or other atom, a
0eb0: 20 73 70 65 63 69 61 6c 20 62 69 6e 64 69 6e 67 special binding
0ec0: 20 77 69 74 68 20 61 20 73 79 6d 62 6f 6c 0a 3b with a symbol.;
0ed0: 20 2a 74 65 78 74 2a 20 69 73 20 6c 6f 6f 6b 65 *text* is looke
0ee0: 64 20 75 70 2e 0a 3b 0a 3b 20 41 20 62 69 6e 64 d up..;.; A bind
0ef0: 69 6e 67 20 63 61 6e 20 61 6c 73 6f 20 62 65 20 ing can also be
0f00: 6f 66 20 61 20 66 6f 72 6d 0a 3b 09 28 3c 74 72 of a form.;.(<tr
0f10: 69 67 67 65 72 2d 73 79 6d 62 6f 6c 3e 20 2a 6d igger-symbol> *m
0f20: 61 63 72 6f 2a 20 2e 20 3c 68 61 6e 64 6c 65 72 acro* . <handler
0f30: 3e 29 0a 3b 20 54 68 69 73 20 69 73 20 65 71 75 >).; This is equ
0f40: 69 76 61 6c 65 6e 74 20 74 6f 20 2a 70 72 65 6f ivalent to *preo
0f50: 72 64 65 72 2a 20 64 65 73 63 72 69 62 65 64 20 rder* described
0f60: 61 62 6f 76 65 2e 20 48 6f 77 65 76 65 72 2c 20 above. However,
0f70: 74 68 65 20 72 65 73 75 6c 74 0a 3b 20 69 73 20 the result.; is
0f80: 72 65 2d 70 72 6f 63 65 73 73 65 64 20 61 67 61 re-processed aga
0f90: 69 6e 2c 20 77 69 74 68 20 74 68 65 20 63 75 72 in, with the cur
0fa0: 72 65 6e 74 20 73 74 79 6c 65 73 68 65 65 74 2e rent stylesheet.
0fb0: 0a 0a 28 64 65 66 69 6e 65 20 28 70 72 65 2d 70 ..(define (pre-p
0fc0: 6f 73 74 2d 6f 72 64 65 72 20 74 72 65 65 20 62 ost-order tree b
0fd0: 69 6e 64 69 6e 67 73 29 0a 20 20 28 6c 65 74 2a indings). (let*
0fe0: 20 28 28 64 65 66 61 75 6c 74 2d 62 69 6e 64 69 ((default-bindi
0ff0: 6e 67 20 28 61 73 73 71 20 27 2a 64 65 66 61 75 ng (assq '*defau
1000: 6c 74 2a 20 62 69 6e 64 69 6e 67 73 29 29 0a 09 lt* bindings))..
1010: 20 28 74 65 78 74 2d 62 69 6e 64 69 6e 67 20 28 (text-binding (
1020: 6f 72 20 28 61 73 73 71 20 27 2a 74 65 78 74 2a or (assq '*text*
1030: 20 62 69 6e 64 69 6e 67 73 29 20 64 65 66 61 75 bindings) defau
1040: 6c 74 2d 62 69 6e 64 69 6e 67 29 29 0a 09 20 28 lt-binding)).. (
1050: 74 65 78 74 2d 68 61 6e 64 6c 65 72 09 09 09 3b text-handler...;
1060: 20 43 61 63 68 65 20 64 65 66 61 75 6c 74 20 61 Cache default a
1070: 6e 64 20 74 65 78 74 20 62 69 6e 64 69 6e 67 73 nd text bindings
1080: 0a 09 20 20 20 28 61 6e 64 20 74 65 78 74 2d 62 .. (and text-b
1090: 69 6e 64 69 6e 67 0a 09 20 20 20 20 20 28 69 66 inding.. (if
10a0: 20 28 70 72 6f 63 65 64 75 72 65 3f 20 28 63 64 (procedure? (cd
10b0: 72 20 74 65 78 74 2d 62 69 6e 64 69 6e 67 29 29 r text-binding))
10c0: 0a 09 20 20 20 20 20 20 20 20 20 28 63 64 72 20 .. (cdr
10d0: 74 65 78 74 2d 62 69 6e 64 69 6e 67 29 20 28 63 text-binding) (c
10e0: 64 64 72 20 74 65 78 74 2d 62 69 6e 64 69 6e 67 ddr text-binding
10f0: 29 29 29 29 29 0a 20 20 20 20 28 6c 65 74 20 6c ))))). (let l
1100: 6f 6f 70 20 28 28 74 72 65 65 20 74 72 65 65 29 oop ((tree tree)
1110: 29 0a 20 20 20 20 20 20 28 63 6f 6e 64 0a 09 28 ). (cond..(
1120: 28 6e 75 6c 6c 3f 20 74 72 65 65 29 20 27 28 29 (null? tree) '()
1130: 29 0a 09 28 28 6e 6f 74 20 28 70 61 69 72 3f 20 )..((not (pair?
1140: 74 72 65 65 29 29 0a 09 20 20 28 6c 65 74 20 28 tree)).. (let (
1150: 28 74 72 69 67 67 65 72 20 27 2a 74 65 78 74 2a (trigger '*text*
1160: 29 29 0a 09 20 20 20 20 28 69 66 20 74 65 78 74 )).. (if text
1170: 2d 68 61 6e 64 6c 65 72 20 28 74 65 78 74 2d 68 -handler (text-h
1180: 61 6e 64 6c 65 72 20 74 72 69 67 67 65 72 20 74 andler trigger t
1190: 72 65 65 29 0a 09 20 20 20 20 20 20 28 65 72 72 ree).. (err
11a0: 6f 72 20 22 55 6e 6b 6e 6f 77 6e 20 62 69 6e 64 or "Unknown bind
11b0: 69 6e 67 20 66 6f 72 20 22 20 74 72 69 67 67 65 ing for " trigge
11c0: 72 20 22 20 61 6e 64 20 6e 6f 20 64 65 66 61 75 r " and no defau
11d0: 6c 74 22 29 29 29 29 0a 09 28 28 6e 6f 74 20 28 lt"))))..((not (
11e0: 73 79 6d 62 6f 6c 3f 20 28 63 61 72 20 74 72 65 symbol? (car tre
11f0: 65 29 29 29 20 28 6d 61 70 20 6c 6f 6f 70 20 74 e))) (map loop t
1200: 72 65 65 29 29 20 3b 20 74 72 65 65 20 69 73 20 ree)) ; tree is
1210: 61 20 6e 6f 64 65 6c 69 73 74 0a 09 28 65 6c 73 a nodelist..(els
1220: 65 09 09 09 09 3b 20 74 72 65 65 20 69 73 20 61 e....; tree is a
1230: 6e 20 53 58 4d 4c 20 6e 6f 64 65 0a 09 20 20 28 n SXML node.. (
1240: 6c 65 74 2a 20 28 28 74 72 69 67 67 65 72 20 28 let* ((trigger (
1250: 63 61 72 20 74 72 65 65 29 29 0a 09 09 20 28 62 car tree))... (b
1260: 69 6e 64 69 6e 67 20 28 6f 72 20 28 61 73 73 71 inding (or (assq
1270: 20 74 72 69 67 67 65 72 20 62 69 6e 64 69 6e 67 trigger binding
1280: 73 29 20 64 65 66 61 75 6c 74 2d 62 69 6e 64 69 s) default-bindi
1290: 6e 67 29 29 29 0a 09 20 20 20 20 28 63 6f 6e 64 ng))).. (cond
12a0: 0a 09 20 20 20 20 20 20 28 28 6e 6f 74 20 62 69 .. ((not bi
12b0: 6e 64 69 6e 67 29 20 0a 09 09 28 65 72 72 6f 72 nding) ...(error
12c0: 20 22 55 6e 6b 6e 6f 77 6e 20 62 69 6e 64 69 6e "Unknown bindin
12d0: 67 20 66 6f 72 20 22 20 74 72 69 67 67 65 72 20 g for " trigger
12e0: 22 20 61 6e 64 20 6e 6f 20 64 65 66 61 75 6c 74 " and no default
12f0: 22 29 29 0a 09 20 20 20 20 20 20 28 28 6e 6f 74 ")).. ((not
1300: 20 28 70 61 69 72 3f 20 28 63 64 72 20 62 69 6e (pair? (cdr bin
1310: 64 69 6e 67 29 29 29 20 20 3b 20 6d 75 73 74 20 ding))) ; must
1320: 62 65 20 61 20 70 72 6f 63 65 64 75 72 65 3a 20 be a procedure:
1330: 68 61 6e 64 6c 65 72 0a 09 09 28 61 70 70 6c 79 handler...(apply
1340: 20 28 63 64 72 20 62 69 6e 64 69 6e 67 29 20 74 (cdr binding) t
1350: 72 69 67 67 65 72 20 28 6d 61 70 20 6c 6f 6f 70 rigger (map loop
1360: 20 28 63 64 72 20 74 72 65 65 29 29 29 29 0a 09 (cdr tree))))..
1370: 20 20 20 20 20 20 28 28 65 71 3f 20 27 2a 70 72 ((eq? '*pr
1380: 65 6f 72 64 65 72 2a 20 28 63 61 64 72 20 62 69 eorder* (cadr bi
1390: 6e 64 69 6e 67 29 29 0a 09 09 28 61 70 70 6c 79 nding))...(apply
13a0: 20 28 63 64 64 72 20 62 69 6e 64 69 6e 67 29 20 (cddr binding)
13b0: 74 72 65 65 29 29 0a 09 20 20 20 20 20 20 28 28 tree)).. ((
13c0: 65 71 3f 20 27 2a 6d 61 63 72 6f 2a 20 28 63 61 eq? '*macro* (ca
13d0: 64 72 20 62 69 6e 64 69 6e 67 29 29 0a 09 09 28 dr binding))...(
13e0: 6c 6f 6f 70 20 28 61 70 70 6c 79 20 28 63 64 64 loop (apply (cdd
13f0: 72 20 62 69 6e 64 69 6e 67 29 20 74 72 65 65 29 r binding) tree)
1400: 29 29 0a 09 20 20 20 20 20 20 28 65 6c 73 65 09 )).. (else.
1410: 09 09 20 20 20 20 3b 20 28 63 61 64 72 20 62 69 .. ; (cadr bi
1420: 6e 64 69 6e 67 29 20 69 73 20 61 20 6c 6f 63 61 nding) is a loca
1430: 6c 20 62 69 6e 64 69 6e 67 0a 09 09 28 61 70 70 l binding...(app
1440: 6c 79 20 28 63 64 64 72 20 62 69 6e 64 69 6e 67 ly (cddr binding
1450: 29 20 74 72 69 67 67 65 72 20 0a 09 09 20 20 28 ) trigger ... (
1460: 70 72 65 2d 70 6f 73 74 2d 6f 72 64 65 72 20 28 pre-post-order (
1470: 63 64 72 20 74 72 65 65 29 20 28 61 70 70 65 6e cdr tree) (appen
1480: 64 20 28 63 61 64 72 20 62 69 6e 64 69 6e 67 29 d (cadr binding)
1490: 20 62 69 6e 64 69 6e 67 73 29 29 29 0a 09 09 29 bindings)))...)
14a0: 29 29 29 29 29 29 29 0a 0a 3b 20 70 6f 73 74 2d )))))))..; post-
14b0: 6f 72 64 65 72 20 69 73 20 61 20 73 74 72 69 63 order is a stric
14c0: 74 20 73 75 62 73 65 74 20 6f 66 20 70 72 65 2d t subset of pre-
14d0: 70 6f 73 74 2d 6f 72 64 65 72 20 77 69 74 68 6f post-order witho
14e0: 75 74 20 2a 70 72 65 6f 72 64 65 72 2a 0a 3b 20 ut *preorder*.;
14f0: 28 6c 65 74 20 61 6c 6f 6e 65 20 2a 6d 61 63 72 (let alone *macr
1500: 6f 2a 29 20 74 72 61 76 65 72 73 61 6c 73 2e 20 o*) traversals.
1510: 0a 3b 20 4e 6f 77 20 70 72 65 2d 70 6f 73 74 2d .; Now pre-post-
1520: 6f 72 64 65 72 20 69 73 20 61 63 74 75 61 6c 6c order is actuall
1530: 79 20 66 61 73 74 65 72 20 74 68 61 6e 20 74 68 y faster than th
1540: 65 20 6f 6c 64 20 70 6f 73 74 2d 6f 72 64 65 72 e old post-order
1550: 2e 0a 3b 20 54 68 65 20 66 75 6e 63 74 69 6f 6e ..; The function
1560: 20 70 6f 73 74 2d 6f 72 64 65 72 20 69 73 20 64 post-order is d
1570: 65 70 72 65 63 61 74 65 64 20 61 6e 64 20 69 73 eprecated and is
1580: 20 61 6c 69 61 73 65 64 20 62 65 6c 6f 77 20 66 aliased below f
1590: 6f 72 0a 3b 20 62 61 63 6b 77 61 72 64 20 63 6f or.; backward co
15a0: 6d 70 61 74 69 62 69 6c 69 74 79 2e 0a 28 64 65 mpatibility..(de
15b0: 66 69 6e 65 20 70 6f 73 74 2d 6f 72 64 65 72 20 fine post-order
15c0: 70 72 65 2d 70 6f 73 74 2d 6f 72 64 65 72 29 0a pre-post-order).
15d0: 0a 3b 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d .;--------------
15e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
15f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1600: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1610: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a 3b 09 09 09 45 ----------.;...E
1620: 78 74 65 6e 64 65 64 20 74 72 65 65 20 66 6f 6c xtended tree fol
1630: 64 0a 3b 20 74 72 65 65 20 3d 20 61 74 6f 6d 20 d.; tree = atom
1640: 7c 20 28 6e 6f 64 65 2d 6e 61 6d 65 20 74 72 65 | (node-name tre
1650: 65 20 2e 2e 2e 29 0a 3b 0a 3b 20 66 6f 6c 64 74 e ...).;.; foldt
1660: 73 20 66 64 6f 77 6e 20 66 75 70 20 66 68 65 72 s fdown fup fher
1670: 65 20 73 65 65 64 20 28 4c 65 61 66 20 73 74 72 e seed (Leaf str
1680: 29 20 3d 20 66 68 65 72 65 20 73 65 65 64 20 73 ) = fhere seed s
1690: 74 72 0a 3b 20 66 6f 6c 64 74 73 20 66 64 6f 77 tr.; foldts fdow
16a0: 6e 20 66 75 70 20 66 68 65 72 65 20 73 65 65 64 n fup fhere seed
16b0: 20 28 4e 64 20 6b 69 64 73 29 20 3d 0a 3b 20 20 (Nd kids) =.;
16c0: 20 20 20 20 20 20 20 66 75 70 20 73 65 65 64 20 fup seed
16d0: 24 20 66 6f 6c 64 6c 20 28 66 6f 6c 64 74 73 20 $ foldl (foldts
16e0: 66 64 6f 77 6e 20 66 75 70 20 66 68 65 72 65 29 fdown fup fhere)
16f0: 20 28 66 64 6f 77 6e 20 73 65 65 64 29 20 6b 69 (fdown seed) ki
1700: 64 73 0a 0a 3b 20 70 72 6f 63 65 64 75 72 65 20 ds..; procedure
1710: 66 68 65 72 65 3a 20 73 65 65 64 20 2d 3e 20 61 fhere: seed -> a
1720: 74 6f 6d 20 2d 3e 20 73 65 65 64 0a 3b 20 70 72 tom -> seed.; pr
1730: 6f 63 65 64 75 72 65 20 66 64 6f 77 6e 3a 20 73 ocedure fdown: s
1740: 65 65 64 20 2d 3e 20 6e 6f 64 65 20 2d 3e 20 73 eed -> node -> s
1750: 65 65 64 0a 3b 20 70 72 6f 63 65 64 75 72 65 20 eed.; procedure
1760: 66 75 70 3a 20 70 61 72 65 6e 74 2d 73 65 65 64 fup: parent-seed
1770: 20 2d 3e 20 6c 61 73 74 2d 6b 69 64 2d 73 65 65 -> last-kid-see
1780: 64 20 2d 3e 20 6e 6f 64 65 20 2d 3e 20 73 65 65 d -> node -> see
1790: 64 0a 3b 20 66 6f 6c 64 74 73 20 72 65 74 75 72 d.; foldts retur
17a0: 6e 73 20 74 68 65 20 66 69 6e 61 6c 20 73 65 65 ns the final see
17b0: 64 0a 0a 28 64 65 66 69 6e 65 20 28 66 6f 6c 64 d..(define (fold
17c0: 74 73 20 66 64 6f 77 6e 20 66 75 70 20 66 68 65 ts fdown fup fhe
17d0: 72 65 20 73 65 65 64 20 74 72 65 65 29 0a 20 20 re seed tree).
17e0: 28 63 6f 6e 64 0a 20 20 20 28 28 6e 75 6c 6c 3f (cond. ((null?
17f0: 20 74 72 65 65 29 20 73 65 65 64 29 0a 20 20 20 tree) seed).
1800: 28 28 6e 6f 74 20 28 70 61 69 72 3f 20 74 72 65 ((not (pair? tre
1810: 65 29 29 09 09 3b 20 41 6e 20 61 74 6f 6d 0a 20 e))..; An atom.
1820: 20 20 20 28 66 68 65 72 65 20 73 65 65 64 20 74 (fhere seed t
1830: 72 65 65 29 29 0a 20 20 20 28 65 6c 73 65 0a 20 ree)). (else.
1840: 20 20 20 28 6c 65 74 20 6c 6f 6f 70 20 28 28 6b (let loop ((k
1850: 69 64 2d 73 65 65 64 20 28 66 64 6f 77 6e 20 73 id-seed (fdown s
1860: 65 65 64 20 74 72 65 65 29 29 20 28 6b 69 64 73 eed tree)) (kids
1870: 20 28 63 64 72 20 74 72 65 65 29 29 29 0a 20 20 (cdr tree))).
1880: 20 20 20 20 28 69 66 20 28 6e 75 6c 6c 3f 20 6b (if (null? k
1890: 69 64 73 29 0a 09 20 20 28 66 75 70 20 73 65 65 ids).. (fup see
18a0: 64 20 6b 69 64 2d 73 65 65 64 20 74 72 65 65 29 d kid-seed tree)
18b0: 0a 09 20 20 28 6c 6f 6f 70 20 28 66 6f 6c 64 74 .. (loop (foldt
18c0: 73 20 66 64 6f 77 6e 20 66 75 70 20 66 68 65 72 s fdown fup fher
18d0: 65 20 6b 69 64 2d 73 65 65 64 20 28 63 61 72 20 e kid-seed (car
18e0: 6b 69 64 73 29 29 0a 09 09 28 63 64 72 20 6b 69 kids))...(cdr ki
18f0: 64 73 29 29 29 29 29 29 29 0a 0a 3b 2d 2d 2d 2d ds)))))))..;----
1900: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1910: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1920: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1930: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
1940: 2d 2d 2d 2d 0a 3b 20 54 72 61 76 65 72 73 65 20 ----.; Traverse
1950: 61 20 66 6f 72 65 73 74 20 64 65 70 74 68 2d 66 a forest depth-f
1960: 69 72 73 74 20 61 6e 64 20 63 75 74 2f 72 65 70 irst and cut/rep
1970: 6c 61 63 65 20 72 61 6e 67 65 73 20 6f 66 20 6e lace ranges of n
1980: 6f 64 65 73 2e 0a 3b 0a 3b 20 54 68 65 20 6e 6f odes..;.; The no
1990: 64 65 73 20 74 68 61 74 20 64 65 66 69 6e 65 20 des that define
19a0: 61 20 72 61 6e 67 65 20 64 6f 6e 27 74 20 68 61 a range don't ha
19b0: 76 65 20 74 6f 20 68 61 76 65 20 74 68 65 20 73 ve to have the s
19c0: 61 6d 65 20 69 6d 6d 65 64 69 61 74 65 0a 3b 20 ame immediate.;
19d0: 70 61 72 65 6e 74 2c 20 64 6f 6e 27 74 20 68 61 parent, don't ha
19e0: 76 65 20 74 6f 20 62 65 20 6f 6e 20 74 68 65 20 ve to be on the
19f0: 73 61 6d 65 20 6c 65 76 65 6c 2c 20 61 6e 64 20 same level, and
1a00: 74 68 65 20 65 6e 64 20 6e 6f 64 65 20 6f 66 20 the end node of
1a10: 61 0a 3b 20 72 61 6e 67 65 20 64 6f 65 73 6e 27 a.; range doesn'
1a20: 74 20 65 76 65 6e 20 68 61 76 65 20 74 6f 20 65 t even have to e
1a30: 78 69 73 74 2e 20 41 20 72 65 70 6c 61 63 65 2d xist. A replace-
1a40: 72 61 6e 67 65 20 70 72 6f 63 65 64 75 72 65 20 range procedure
1a50: 72 65 6d 6f 76 65 73 0a 3b 20 6e 6f 64 65 73 20 removes.; nodes
1a60: 66 72 6f 6d 20 74 68 65 20 62 65 67 69 6e 6e 69 from the beginni
1a70: 6e 67 20 6e 6f 64 65 20 6f 66 20 74 68 65 20 72 ng node of the r
1a80: 61 6e 67 65 20 75 70 20 74 6f 20 28 62 75 74 20 ange up to (but
1a90: 6e 6f 74 20 69 6e 63 6c 75 64 69 6e 67 29 0a 3b not including).;
1aa0: 20 74 68 65 20 65 6e 64 20 6e 6f 64 65 20 6f 66 the end node of
1ab0: 20 74 68 65 20 72 61 6e 67 65 2e 20 20 49 6e 20 the range. In
1ac0: 61 64 64 69 74 69 6f 6e 2c 20 74 68 65 20 62 65 addition, the be
1ad0: 67 69 6e 6e 69 6e 67 20 6e 6f 64 65 20 6f 66 20 ginning node of
1ae0: 74 68 65 0a 3b 20 72 61 6e 67 65 20 63 61 6e 20 the.; range can
1af0: 62 65 20 72 65 70 6c 61 63 65 64 20 62 79 20 61 be replaced by a
1b00: 20 6e 6f 64 65 20 6f 72 20 61 20 6c 69 73 74 20 node or a list
1b10: 6f 66 20 6e 6f 64 65 73 2e 20 54 68 65 20 72 61 of nodes. The ra
1b20: 6e 67 65 20 6f 66 0a 3b 20 6e 6f 64 65 73 20 69 nge of.; nodes i
1b30: 73 20 63 75 74 20 77 68 69 6c 65 20 64 65 70 74 s cut while dept
1b40: 68 2d 66 69 72 73 74 20 74 72 61 76 65 72 73 69 h-first traversi
1b50: 6e 67 20 74 68 65 20 66 6f 72 65 73 74 2e 20 49 ng the forest. I
1b60: 66 20 61 6c 6c 0a 3b 20 62 72 61 6e 63 68 65 73 f all.; branches
1b70: 20 6f 66 20 74 68 65 20 6e 6f 64 65 20 61 72 65 of the node are
1b80: 20 63 75 74 20 61 20 6e 6f 64 65 20 69 73 20 63 cut a node is c
1b90: 75 74 20 61 73 20 77 65 6c 6c 2e 20 20 54 68 65 ut as well. The
1ba0: 20 70 72 6f 63 65 64 75 72 65 0a 3b 20 63 61 6e procedure.; can
1bb0: 20 63 75 74 20 73 65 76 65 72 61 6c 20 6e 6f 6e cut several non
1bc0: 2d 6f 76 65 72 6c 61 70 70 69 6e 67 20 72 61 6e -overlapping ran
1bd0: 67 65 73 20 66 72 6f 6d 20 61 20 66 6f 72 65 73 ges from a fores
1be0: 74 2e 0a 0a 3b 09 72 65 70 6c 61 63 65 2d 72 61 t...;.replace-ra
1bf0: 6e 67 65 3a 3a 20 42 45 47 2d 50 52 45 44 20 78 nge:: BEG-PRED x
1c00: 20 45 4e 44 2d 50 52 45 44 20 78 20 46 4f 52 45 END-PRED x FORE
1c10: 53 54 20 2d 3e 20 46 4f 52 45 53 54 0a 3b 20 77 ST -> FOREST.; w
1c20: 68 65 72 65 0a 3b 09 74 79 70 65 20 46 4f 52 45 here.;.type FORE
1c30: 53 54 20 3d 20 28 4e 4f 44 45 20 2e 2e 2e 29 0a ST = (NODE ...).
1c40: 3b 09 74 79 70 65 20 4e 4f 44 45 20 3d 20 41 74 ;.type NODE = At
1c50: 6f 6d 20 7c 20 28 4e 61 6d 65 20 2e 20 46 4f 52 om | (Name . FOR
1c60: 45 53 54 29 20 7c 20 46 4f 52 45 53 54 0a 3b 0a EST) | FOREST.;.
1c70: 3b 20 54 68 65 20 72 61 6e 67 65 20 6f 66 20 6e ; The range of n
1c80: 6f 64 65 73 20 69 73 20 73 70 65 63 69 66 69 65 odes is specifie
1c90: 64 20 62 79 20 74 77 6f 20 70 72 65 64 69 63 61 d by two predica
1ca0: 74 65 73 2c 20 62 65 67 2d 70 72 65 64 20 61 6e tes, beg-pred an
1cb0: 64 20 65 6e 64 2d 70 72 65 64 2e 0a 3b 09 62 65 d end-pred..;.be
1cc0: 67 2d 70 72 65 64 3a 3a 20 4e 4f 44 45 20 2d 3e g-pred:: NODE ->
1cd0: 20 23 66 20 7c 20 46 4f 52 45 53 54 0a 3b 09 65 #f | FOREST.;.e
1ce0: 6e 64 2d 70 72 65 64 3a 3a 20 4e 4f 44 45 20 2d nd-pred:: NODE -
1cf0: 3e 20 23 66 20 7c 20 46 4f 52 45 53 54 0a 3b 20 > #f | FOREST.;
1d00: 54 68 65 20 62 65 67 2d 70 72 65 64 20 70 72 65 The beg-pred pre
1d10: 64 69 63 61 74 65 20 64 65 63 69 64 65 73 20 6f dicate decides o
1d20: 6e 20 74 68 65 20 62 65 67 69 6e 6e 69 6e 67 20 n the beginning
1d30: 6f 66 20 74 68 65 20 72 61 6e 67 65 2e 20 54 68 of the range. Th
1d40: 65 20 6e 6f 64 65 0a 3b 20 66 6f 72 20 77 68 69 e node.; for whi
1d50: 63 68 20 74 68 65 20 70 72 65 64 69 63 61 74 65 ch the predicate
1d60: 20 79 69 65 6c 64 73 20 6e 6f 6e 2d 23 66 20 6d yields non-#f m
1d70: 61 72 6b 73 20 74 68 65 20 62 65 67 69 6e 6e 69 arks the beginni
1d80: 6e 67 20 6f 66 20 74 68 65 20 72 61 6e 67 65 0a ng of the range.
1d90: 3b 20 54 68 65 20 6e 6f 6e 2d 23 66 20 76 61 6c ; The non-#f val
1da0: 75 65 20 6f 66 20 74 68 65 20 70 72 65 64 69 63 ue of the predic
1db0: 61 74 65 20 72 65 70 6c 61 63 65 73 20 74 68 65 ate replaces the
1dc0: 20 6e 6f 64 65 2e 20 54 68 65 20 76 61 6c 75 65 node. The value
1dd0: 20 63 61 6e 20 62 65 20 61 0a 3b 20 6c 69 73 74 can be a.; list
1de0: 20 6f 66 20 6e 6f 64 65 73 2e 20 54 68 65 20 72 of nodes. The r
1df0: 65 70 6c 61 63 65 2d 72 61 6e 67 65 20 70 72 6f eplace-range pro
1e00: 63 65 64 75 72 65 20 74 68 65 6e 20 74 72 61 76 cedure then trav
1e10: 65 72 73 65 73 20 74 68 65 20 74 72 65 65 20 61 erses the tree a
1e20: 6e 64 20 73 6b 69 70 73 0a 3b 20 61 6c 6c 20 74 nd skips.; all t
1e30: 68 65 20 6e 6f 64 65 73 2c 20 75 6e 74 69 6c 20 he nodes, until
1e40: 74 68 65 20 65 6e 64 2d 70 72 65 64 20 79 69 65 the end-pred yie
1e50: 6c 64 73 20 6e 6f 6e 2d 23 66 2e 20 54 68 65 20 lds non-#f. The
1e60: 76 61 6c 75 65 20 6f 66 20 74 68 65 20 65 6e 64 value of the end
1e70: 2d 70 72 65 64 0a 3b 20 72 65 70 6c 61 63 65 73 -pred.; replaces
1e80: 20 74 68 65 20 65 6e 64 2d 72 61 6e 67 65 20 6e the end-range n
1e90: 6f 64 65 2e 20 54 68 65 20 6e 65 77 20 65 6e 64 ode. The new end
1ea0: 20 6e 6f 64 65 20 61 6e 64 20 69 74 73 20 62 72 node and its br
1eb0: 6f 74 68 65 72 73 20 77 69 6c 6c 20 62 65 0a 3b others will be.;
1ec0: 20 72 65 2d 73 63 61 6e 6e 65 64 2e 0a 3b 20 54 re-scanned..; T
1ed0: 68 65 20 70 72 65 64 69 63 61 74 65 73 20 61 72 he predicates ar
1ee0: 65 20 65 76 61 6c 75 61 74 65 64 20 70 72 65 2d e evaluated pre-
1ef0: 6f 72 64 65 72 2e 20 57 65 20 64 6f 20 6e 6f 74 order. We do not
1f00: 20 64 65 73 63 65 6e 64 20 69 6e 74 6f 20 61 20 descend into a
1f10: 6e 6f 64 65 20 74 68 61 74 0a 3b 20 69 73 20 6d node that.; is m
1f20: 61 72 6b 65 64 20 61 73 20 74 68 65 20 62 65 67 arked as the beg
1f30: 69 6e 6e 69 6e 67 20 6f 66 20 74 68 65 20 72 61 inning of the ra
1f40: 6e 67 65 2e 0a 0a 28 64 65 66 69 6e 65 20 28 72 nge...(define (r
1f50: 65 70 6c 61 63 65 2d 72 61 6e 67 65 20 62 65 67 eplace-range beg
1f60: 2d 70 72 65 64 20 65 6e 64 2d 70 72 65 64 20 66 -pred end-pred f
1f70: 6f 72 65 73 74 29 0a 0a 20 20 3b 20 6c 6f 6f 70 orest).. ; loop
1f80: 20 66 6f 72 65 73 74 20 6b 65 65 70 3f 20 6e 65 forest keep? ne
1f90: 77 2d 66 6f 72 65 73 74 0a 20 20 3b 20 66 6f 72 w-forest. ; for
1fa0: 65 73 74 20 69 73 20 74 68 65 20 66 6f 72 65 73 est is the fores
1fb0: 74 20 74 6f 20 74 72 61 76 65 72 73 65 0a 20 20 t to traverse.
1fc0: 3b 20 6e 65 77 2d 66 6f 72 65 73 74 20 61 63 63 ; new-forest acc
1fd0: 75 6d 75 6c 61 74 65 73 20 74 68 65 20 6e 6f 64 umulates the nod
1fe0: 65 73 20 77 65 20 77 69 6c 6c 20 6b 65 65 70 2c es we will keep,
1ff0: 20 69 6e 20 74 68 65 20 72 65 76 65 72 73 65 0a in the reverse.
2000: 20 20 3b 20 6f 72 64 65 72 0a 20 20 3b 20 49 66 ; order. ; If
2010: 20 6b 65 65 70 3f 20 69 73 20 23 74 2c 20 6b 65 keep? is #t, ke
2020: 65 70 20 74 68 65 20 63 75 72 72 20 6e 6f 64 65 ep the curr node
2030: 20 69 66 20 61 74 6f 6d 69 63 2e 20 49 66 20 74 if atomic. If t
2040: 68 65 20 6e 6f 64 65 20 69 73 20 6e 6f 74 20 61 he node is not a
2050: 74 6f 6d 69 63 2c 0a 20 20 3b 20 74 72 61 76 65 tomic,. ; trave
2060: 72 73 65 20 69 74 73 20 63 68 69 6c 64 72 65 6e rse its children
2070: 20 61 6e 64 20 6b 65 65 70 20 74 68 6f 73 65 20 and keep those
2080: 74 68 61 74 20 61 72 65 20 6e 6f 74 20 69 6e 20 that are not in
2090: 74 68 65 20 73 6b 69 70 20 72 61 6e 67 65 2e 0a the skip range..
20a0: 20 20 3b 20 49 66 20 6b 65 65 70 3f 20 69 73 20 ; If keep? is
20b0: 23 66 2c 20 73 6b 69 70 20 74 68 65 20 63 75 72 #f, skip the cur
20c0: 72 65 6e 74 20 6e 6f 64 65 20 69 66 20 61 74 6f rent node if ato
20d0: 6d 69 63 2e 20 4f 74 68 65 72 77 69 73 65 2c 0a mic. Otherwise,.
20e0: 20 20 3b 20 74 72 61 76 65 72 73 65 20 69 74 73 ; traverse its
20f0: 20 63 68 69 6c 64 72 65 6e 2e 20 49 66 20 61 6c children. If al
2100: 6c 20 63 68 69 6c 64 72 65 6e 20 61 72 65 20 73 l children are s
2110: 6b 69 70 70 65 64 2c 20 73 6b 69 70 20 74 68 65 kipped, skip the
2120: 20 6e 6f 64 65 0a 20 20 3b 20 61 73 20 77 65 6c node. ; as wel
2130: 6c 2e 0a 0a 20 20 28 64 65 66 69 6e 65 20 28 6c l... (define (l
2140: 6f 6f 70 20 66 6f 72 65 73 74 20 6b 65 65 70 3f oop forest keep?
2150: 20 6e 65 77 2d 66 6f 72 65 73 74 29 0a 20 20 20 new-forest).
2160: 20 28 69 66 20 28 6e 75 6c 6c 3f 20 66 6f 72 65 (if (null? fore
2170: 73 74 29 20 28 76 61 6c 75 65 73 20 28 72 65 76 st) (values (rev
2180: 65 72 73 65 20 6e 65 77 2d 66 6f 72 65 73 74 29 erse new-forest)
2190: 20 6b 65 65 70 3f 29 0a 09 28 6c 65 74 20 28 28 keep?)..(let ((
21a0: 6e 6f 64 65 20 28 63 61 72 20 66 6f 72 65 73 74 node (car forest
21b0: 29 29 29 0a 09 20 20 28 69 66 20 6b 65 65 70 3f ))).. (if keep?
21c0: 0a 09 20 20 20 20 20 20 28 63 6f 6e 64 09 09 09 .. (cond...
21d0: 3b 20 61 63 63 75 6d 75 6c 61 74 65 20 6d 6f 64 ; accumulate mod
21e0: 65 0a 09 20 20 20 20 20 20 20 28 28 62 65 67 2d e.. ((beg-
21f0: 70 72 65 64 20 6e 6f 64 65 29 20 3d 3e 09 3b 20 pred node) =>.;
2200: 73 65 65 20 69 66 20 74 68 65 20 6e 6f 64 65 20 see if the node
2210: 73 74 61 72 74 73 20 74 68 65 20 73 6b 69 70 20 starts the skip
2220: 72 61 6e 67 65 0a 09 09 28 6c 61 6d 62 64 61 20 range...(lambda
2230: 28 72 65 70 6c 2d 62 72 61 6e 63 68 65 73 29 09 (repl-branches).
2240: 3b 20 69 66 20 73 6f 2c 20 73 6b 69 70 2f 72 65 ; if so, skip/re
2250: 70 6c 61 63 65 20 74 68 65 20 6e 6f 64 65 0a 09 place the node..
2260: 09 20 20 28 6c 6f 6f 70 20 28 63 64 72 20 66 6f . (loop (cdr fo
2270: 72 65 73 74 29 20 23 66 20 0a 09 09 09 28 61 70 rest) #f ....(ap
2280: 70 65 6e 64 20 28 72 65 76 65 72 73 65 20 72 65 pend (reverse re
2290: 70 6c 2d 62 72 61 6e 63 68 65 73 29 20 6e 65 77 pl-branches) new
22a0: 2d 66 6f 72 65 73 74 29 29 29 29 0a 09 20 20 20 -forest))))..
22b0: 20 20 20 20 28 28 6e 6f 74 20 28 70 61 69 72 3f ((not (pair?
22c0: 20 6e 6f 64 65 29 29 09 3b 20 69 74 27 73 20 61 node)).; it's a
22d0: 6e 20 61 74 6f 6d 2c 20 6b 65 65 70 20 69 74 0a n atom, keep it.
22e0: 09 09 28 6c 6f 6f 70 20 28 63 64 72 20 66 6f 72 ..(loop (cdr for
22f0: 65 73 74 29 20 6b 65 65 70 3f 20 28 63 6f 6e 73 est) keep? (cons
2300: 20 6e 6f 64 65 20 6e 65 77 2d 66 6f 72 65 73 74 node new-forest
2310: 29 29 29 0a 09 20 20 20 20 20 20 20 28 65 6c 73 ))).. (els
2320: 65 0a 09 09 28 6c 65 74 2a 2d 76 61 6c 75 65 73 e...(let*-values
2330: 0a 09 09 20 28 28 28 6e 6f 64 65 3f 29 20 28 73 ... (((node?) (s
2340: 79 6d 62 6f 6c 3f 20 28 63 61 72 20 6e 6f 64 65 ymbol? (car node
2350: 29 29 29 20 3b 20 6f 72 20 69 73 20 69 74 20 61 ))) ; or is it a
2360: 20 6e 6f 64 65 6c 69 73 74 3f 0a 09 09 20 20 28 nodelist?... (
2370: 28 6e 65 77 2d 6b 69 64 73 20 6b 65 65 70 3f 29 (new-kids keep?)
2380: 09 09 20 3b 20 74 72 61 76 65 72 73 65 20 69 74 .. ; traverse it
2390: 73 20 63 68 69 6c 64 72 65 6e 0a 09 09 20 20 20 s children...
23a0: 28 6c 6f 6f 70 20 28 69 66 20 6e 6f 64 65 3f 20 (loop (if node?
23b0: 28 63 64 72 20 6e 6f 64 65 29 20 6e 6f 64 65 29 (cdr node) node)
23c0: 20 23 74 20 27 28 29 29 29 29 0a 09 09 20 28 6c #t '())))... (l
23d0: 6f 6f 70 20 28 63 64 72 20 66 6f 72 65 73 74 29 oop (cdr forest)
23e0: 20 6b 65 65 70 3f 0a 09 09 20 20 20 20 20 20 20 keep?...
23f0: 28 63 6f 6e 73 20 0a 09 09 09 28 69 66 20 6e 6f (cons ....(if no
2400: 64 65 3f 20 28 63 6f 6e 73 20 28 63 61 72 20 6e de? (cons (car n
2410: 6f 64 65 29 20 6e 65 77 2d 6b 69 64 73 29 20 6e ode) new-kids) n
2420: 65 77 2d 6b 69 64 73 29 0a 09 09 09 6e 65 77 2d ew-kids)....new-
2430: 66 6f 72 65 73 74 29 29 29 29 29 0a 09 20 20 20 forest)))))..
2440: 20 20 20 3b 20 73 6b 69 70 20 6d 6f 64 65 0a 09 ; skip mode..
2450: 20 20 20 20 20 20 28 63 6f 6e 64 0a 09 20 20 20 (cond..
2460: 20 20 20 20 28 28 65 6e 64 2d 70 72 65 64 20 6e ((end-pred n
2470: 6f 64 65 29 20 3d 3e 09 3b 20 65 6e 64 20 74 68 ode) =>.; end th
2480: 65 20 73 6b 69 70 20 72 61 6e 67 65 0a 09 09 28 e skip range...(
2490: 6c 61 6d 62 64 61 20 28 72 65 70 6c 2d 62 72 61 lambda (repl-bra
24a0: 6e 63 68 65 73 29 09 3b 20 72 65 70 6c 2d 62 72 nches).; repl-br
24b0: 61 6e 63 68 65 73 20 77 69 6c 6c 20 62 65 20 72 anches will be r
24c0: 65 2d 73 63 61 6e 6e 65 64 0a 09 09 20 20 28 6c e-scanned... (l
24d0: 6f 6f 70 20 28 61 70 70 65 6e 64 20 72 65 70 6c oop (append repl
24e0: 2d 62 72 61 6e 63 68 65 73 20 28 63 64 72 20 66 -branches (cdr f
24f0: 6f 72 65 73 74 29 29 20 23 74 0a 09 09 09 6e 65 orest)) #t....ne
2500: 77 2d 66 6f 72 65 73 74 29 29 29 0a 09 20 20 20 w-forest)))..
2510: 20 20 20 20 28 28 6e 6f 74 20 28 70 61 69 72 3f ((not (pair?
2520: 20 6e 6f 64 65 29 29 09 3b 20 69 74 27 73 20 61 node)).; it's a
2530: 6e 20 61 74 6f 6d 2c 20 73 6b 69 70 20 69 74 0a n atom, skip it.
2540: 09 09 28 6c 6f 6f 70 20 28 63 64 72 20 66 6f 72 ..(loop (cdr for
2550: 65 73 74 29 20 6b 65 65 70 3f 20 6e 65 77 2d 66 est) keep? new-f
2560: 6f 72 65 73 74 29 29 0a 09 20 20 20 20 20 20 20 orest))..
2570: 28 65 6c 73 65 0a 09 09 28 6c 65 74 2a 2d 76 61 (else...(let*-va
2580: 6c 75 65 73 0a 09 09 20 28 28 28 6e 6f 64 65 3f lues... (((node?
2590: 29 20 28 73 79 6d 62 6f 6c 3f 20 28 63 61 72 20 ) (symbol? (car
25a0: 6e 6f 64 65 29 29 29 20 20 3b 20 6f 72 20 69 73 node))) ; or is
25b0: 20 69 74 20 61 20 6e 6f 64 65 6c 69 73 74 3f 0a it a nodelist?.
25c0: 09 09 20 20 28 28 6e 65 77 2d 6b 69 64 73 20 6b .. ((new-kids k
25d0: 65 65 70 3f 29 09 09 20 20 3b 20 74 72 61 76 65 eep?).. ; trave
25e0: 72 73 65 20 69 74 73 20 63 68 69 6c 64 72 65 6e rse its children
25f0: 0a 09 09 20 20 20 28 6c 6f 6f 70 20 28 69 66 20 ... (loop (if
2600: 6e 6f 64 65 3f 20 28 63 64 72 20 6e 6f 64 65 29 node? (cdr node)
2610: 20 6e 6f 64 65 29 20 23 66 20 27 28 29 29 29 29 node) #f '())))
2620: 0a 09 09 20 28 6c 6f 6f 70 20 28 63 64 72 20 66 ... (loop (cdr f
2630: 6f 72 65 73 74 29 20 6b 65 65 70 3f 0a 09 09 20 orest) keep?...
2640: 20 20 20 20 20 20 28 69 66 20 28 6f 72 20 6b 65 (if (or ke
2650: 65 70 3f 20 28 70 61 69 72 3f 20 6e 65 77 2d 6b ep? (pair? new-k
2660: 69 64 73 29 29 0a 09 09 09 20 20 20 28 63 6f 6e ids)).... (con
2670: 73 0a 09 09 09 20 20 20 20 28 69 66 20 6e 6f 64 s.... (if nod
2680: 65 3f 20 28 63 6f 6e 73 20 28 63 61 72 20 6e 6f e? (cons (car no
2690: 64 65 29 20 6e 65 77 2d 6b 69 64 73 29 20 6e 65 de) new-kids) ne
26a0: 77 2d 6b 69 64 73 29 0a 09 09 09 20 20 20 20 6e w-kids).... n
26b0: 65 77 2d 66 6f 72 65 73 74 29 0a 09 09 09 20 20 ew-forest)....
26c0: 20 6e 65 77 2d 66 6f 72 65 73 74 29 09 09 3b 20 new-forest)..;
26d0: 69 66 20 61 6c 6c 20 6b 69 64 73 20 61 72 65 20 if all kids are
26e0: 73 6b 69 70 70 65 64 0a 09 09 20 20 20 20 20 20 skipped...
26f0: 20 29 29 29 29 29 29 29 29 09 09 09 3b 20 73 6b ))))))))...; sk
2700: 69 70 20 74 68 65 20 6e 6f 64 65 20 74 6f 6f 0a ip the node too.
2710: 20 20 0a 20 20 28 6c 65 74 2a 2d 76 61 6c 75 65 . (let*-value
2720: 73 20 28 28 28 6e 65 77 2d 66 6f 72 65 73 74 20 s (((new-forest
2730: 6b 65 65 70 3f 29 20 28 6c 6f 6f 70 20 66 6f 72 keep?) (loop for
2740: 65 73 74 20 23 74 20 27 28 29 29 29 29 0a 20 20 est #t '()))).
2750: 20 20 20 6e 65 77 2d 66 6f 72 65 73 74 29 29 0a new-forest)).
2760: 0a .