Weblog of Kenny

Their key idea is based on "program by relation" paradigm. We recall their example converting Netscape book and XBel bookmark in the paper as follows,

relation top =

Html [ Head [String], Body [H1 [ t :: String ] , Dl [nc] ] ]

<->

Xbel [ Title [ t :: String ], xc ]

where contents (nc, xc)

relation contents =
( nb | nf )*
<->
( xb | xf )*
where bookmark(nb,xb), folder(nf, xf)

-- note that the pattern matching assumes indeterministic matching. nb and nf or xb or xf can be in any order.

relation bookmark =
( Dt [ A[Href [ url :: String], title ::String]] )
<->
(Bookmark [Href [url :: String],Title[ title ::String]] ] )

relation folder =
Dt [H3 [title :: String], Dl [ nc] ]
<->
Folder[Title [title ::String], xc ]
where contents (nc, xc)

In the above example, top describes nestscape and XBel bookmarks are in relation, if the H1 from Hthml is the same as the title of Xbel, and their contents are in relation. contents relation ties the nescape bookmark content with the xbel bookmark contents. Now that the nb and nf, xb and xf can be in any order. This assume the values matches with the pattern any order. nb and xb must be in bookmark relation. and xf and nf must be in folder relation. There is a recursion in the folder relation.

  The semantics is described as follows in our own sytax. We only consider the forward transformation, the backward transformation is dual to it.

for relation

relation r = P <-> Q  where W

we have two phases:

parsing phase:  W |- v in P => venv 

value v matches with pattern P under the extra relation W, producing value binding venv.

Note that venv contains all possible matching. For instamce

A in (x :: A?, y :: A?) => { x -> A, y -> () } or  { x -> (), y -> A }.

unparsing phase: W | - venv <= Q ni v'

that is under W, value binding venv unparses Q producing value v'.

Technical aspects:

They use parse automata which is close to the regular expression tree automata with variable from XDuce's simpler design paper.