@c run with texi-to-pdf-presetation foo.texi foo.pdf
\input texinfo   @c -*-texinfo-*-
@settitle Fold and XML Transformation
@c +background: background.svg

@titlepage 
@title Fold and XML Transformation
@subtitle SFP 2007
@author Andy Wingo
@end titlepage

@section origins

Pain avoidance, indignation

@iftex
Preparing for a presentation in February, I was struck with the
realization: if I'm doing this in my free time, for fun, why force
myself to endure the abomination known as OpenOffice?
@end iftex

@section svg instead of openoffice

Each layer can be a slide

@ifnottex
@image{inkscape-layers.png,831,486}
@end ifnottex

@iftex
(picture of inkscape with xml editor open)
@end iftex

@section bullets in svg is a drag

"This could be better"

SVG is XML, and I have a hammer!

@ifnottex
@image{i-have-a-hammer.png,300,300}
@end ifnottex

@iftex
(Here I knew that I had a problem to work on.)
@end iftex

@section simple slides language

@example
<slides>
 <slide>
  <title>Hi.</title>
  <para>Hello<br/>world</para>
 </slide>
</slides>
@end example

@section example in sxml

@example
(slides
 (slide
  (title "Hi.")
  (para "Hello" (br) "world")))
@end example

@section try rewrite with pre-post-order

Table-driven rewrite of S-expressions

Great stuff

@iftex
Kicks XSLT in the pants

Try pre-post-order to transform
some simple slides vocab to SVG
@end iftex

@section pre-post-order: slides->html

@example
`((slides . ,(lambda (tag . kids)
               `(html (body ,@@kids))))
  (slide  . ,(lambda (tag . kids)
               `(div (@@ (class "slide"))
                     ,@@kids)))
  (title  . ,(lambda (tag . kids)
               `(h1 ,@@kids)))
  (*text* . ,(lambda (tag text)
               text))
  ...)
@end example

@section slides as html

@example
(html
 (body
  (div (@@ (class "slide"))
       (h1 "Hi.")
       (p "Hello" (br) "world"))))
@end example

@section slides as svg

@example
(svg (@@ (width "1024") (height "768"))
     (g (text
         (@@ (x "96") (y "216")
            (font-size "64px"))
         (tspan (@@ (x "96") (y "216"))
                "Hello")
         (tspan (@@ (x "96") (y "280"))
                "world"))))
@end example

@section pre-post-order: slides->svg
@example
(tspan (@@ (x "96") (y "216")) "Hello")
(tspan (@@ (x "96") (y "280")) "world")
@end example

?

@iftex
(Here I knew I had an interesting problem.)
@end iftex

@section the problem

Rendering a declarative document
into SVG is a context-sensitive
transformation

Post-order transformation is
context-insensitive

@section multithreadedness

post-order can be expressed in
terms of the multithreaded foldt

@example
(define (foldt fup fhere tree)
  (if (atom? tree)
      (fhere tree)
      (fup (map (lambda (kid)
                  (foldt fup fhere kid))
                tree))))
@end example

@section layout is a single-threaded

Need new combinator in terms of foldts: monadic layout seed

@example
(define (foldts fdown fup fhere seed tree)
  (if (atom? tree)
      (fhere seed tree)
      (fup seed
           (fold (lambda (kid kseed)
                  (foldts fdown fup fhere
                          kseed kid))
                 (fdown seed tree)
                 tree)
           tree)))
@end example

@section macro expansion for xml

pre-post-order can also do pre-order rewrites of the tree

Need ability to modify tree being traversed

@section solution: foldts*

@example
(define (foldts* fdown fup fhere seed tree)
  ...
      (call-with-values
          (lambda () (fdown seed tree))
        (lambda (kseed tree)
          (fup seed
               ...))))
@end example

@section multi-valued seeds painful

Writing foldts* handlers painful

Need automatic destructuring of seed

Solution: multi-valued fold
@itemize
@item Idea taken from scsh
@end itemize

@section foldts*-values

Analogous to fold-values:

@example
(define (fold-values proc list . seeds)
  (if (null? list)
      (apply values seeds)
      (call-with-values
          (lambda ()
            (apply proc (car list) seeds))
        (lambda seeds
          (apply fold-values
                 proc (cdr list) seeds)))))
@end example

@section foldts*-values

A general traversal combinator

Handlers convenient to write, easy destructuring of multi-valued seed

Efficient

@section pre-post-order for svg layout?

The svg problem: deriving domain-specific combinators on top of
foldts*-values

foldts not terribly nice to program directly

"fold-layout"

@section building on foldts*-values

@itemize
@item Decide the format for the seeds
@item Implement fdown, fup, fhere
@end itemize

@section fold-layout seed format

@itemize
@item return value
@item some representation of "layout"
@item hierarchical params
@item current bindings table
@item "post-handler"
@end itemize

@section fold-layout bindings example

@example
`((slide
   (pre-layout . ,slide-pre-layout)
   (post . ,slide-post))
  (header
   (post . ,header-post))
  (cartouche
   (pre-layout . ,cartouche-pre-layout)
   (post . ,cartouche-post))
  (p
   (post . ,p-post))
  (*text* . ,text-handler))
@end example

@section fold-layout: implementing fdown

Handlers to call in fdown: pre-layout, pre/macro

@example
(define (cartouche-pre-layout
         tree params layout)
  (let-layout layout (x y)
    (let-params params (margin-left
                        margin-top)
      (make-layout (+ x margin-left)
                   (+ y margin-top))))) 
@end example

@section fold-layout: implementing fup

Handlers to call in fup: post

@example
(define (p-post tag params old-layout layout
                kids)
  (values
   layout
   `(text
     (@@ (x ,(make-text-x params old-layout))
        (y ,(make-text-y params old-layout)))
     ,@@kids)))
@end example

@section fold-layout: implementing fhere

Handlers to call in fhere: *text*

@example
(define (text-handler text params layout) 
  (values
   (layout-advance-text-line params layout)
   `(tspan
     (@@ (x ,(make-text-x params layout))
        (y ,(make-text-y params layout)))
     ,text)))
@end example

@section conclusions (1/2)

@itemize
@item foldts underlies (all?) XML transformations
@item foldts* is like foldts, but allows macro transformation
@itemize
@item foldts*-values is a convenient foldts*
@end itemize
@end itemize

@section conclusions (2/2)

@itemize
@item When you need foldts, you generally want a domain-specific
combinator built on foldts.
@itemize
@item It is possible to "derive" such combinators methodically
@end itemize
@item fold-layout is such a combinator
@itemize
@item Graphics layout with functional programming
@end itemize
@end itemize

@section questions?

Thanks for listening!

Andy Wingo

wingo@@pobox.com

wingolog.org/software/guile-present/

@bye