 `b18n-combined`: Combining Syntactic and Semantic Bidirectionalization
======================================================================

What's This?
------------

This program, `b18n-combined`, is a prototype implementation of
the paper "Combining Syntactic and Semantic Bidirectionalization" 
written by Janis Voigtl&auml;nder, Zhenjiang Hu, Kazutaka Matsuda,
and Meng Wang, which is accepted at ICFP'10.

The program takes input program describing a view function that constructs a view from a source, 
and generates a put-back function that reflects updates on the view to the source. 
Thanks to combination of syntactic and semantic bidirectionalization, 
the program can generates effective put-back functions in the sense that
the generated put-back functions can put back more updates than 
those obtained by either of syntactic/semantic bidirectionalization.

Online Version
--------------

A [CGI version] of the program is provided for your convenience.

[CGI version]: http://www.kb.ecei.tohoku.ac.jp/~kztk/b18n-combined/


Example
-------
 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ {.shell}
$ cat example/init.txt 
init []          = []
init [a]         = []
init (a:b:x)     = a:initWork b x
initWork a []    = []
initWork a (b:x) = a:initWork b x
$ ./dist/build/b18n-combined/b18n-combined example/sieve.txt -syn -hs
import Control.Monad
import BUtil
data Cmpl t0 t1
    = Csieve_Cmpl_1
    | Csieve_Cmpl_2 t0
    | Csieve_Cmpl_3 t1 (Cmpl t0 t1)
sieve ([]) = []
sieve (a : []) = []
sieve (a : (b : x)) = b : sieve (x)
sieve_B s v = head (sieve_T_I v (sieve_Cmpl s))
sieve_Cmpl ([]) = Csieve_Cmpl_1
sieve_Cmpl (a : []) = Csieve_Cmpl_2 a
sieve_Cmpl (a : (b : x)) = Csieve_Cmpl_3 a (sieve_Cmpl (x))
sieve_T_I x1 x2 = mplus (sieve_T_I_1 x1 x2) (mplus (sieve_T_I_2 x1 x2) (mplus (sieve_T_I_3 x1 x2) mzero))
sieve_T_I_1 [] (Csieve_Cmpl_1) = do return ([])
sieve_T_I_1 _ _ = mzero
sieve_T_I_2 [] (Csieve_Cmpl_2 a) = do return (a : [])
sieve_T_I_2 _ _ = mzero
sieve_T_I_3 (b : tv1) (Csieve_Cmpl_3 a
                                     tc1) = do (x) <- sieve_T_I tv1 tc1
                                               return (a : (b : x))
sieve_T_I_3 _ _ = mzero
$ ./b18n-combined example/sieve.txt -sem
import Data.Bff
import BUtil
sieve_B s v
    = bff Main.sieve s v
sieve ([]) = []
sieve (a : []) = []
sieve (a : (b : x)) = b : sieve (x)
$ ./b18n-combined example/sieve.txt -comb 
import Control.Monad
import BUtil
sieve_Bb bias s v
    = gen_put_bias bias Main.sieve(\x y -> castError $ (sieve_22_B $! x) $! y) s v
sieve_Bbd = withDefaultBias sieve_Bb
sieve_Bd = withDefault sieve_B
sieve_B s v = sieve_Bb rear s v
data Cmpl
    = Csieve_22_Cmpl_1
    | Csieve_22_Cmpl_2
sieve ([]) = []
sieve (a : []) = []
sieve (a : (b : x)) = b : sieve (x)
sieve_22_B s v = head (sieve_22_T_I v (sieve_22_Cmpl s))
sieve_22_Cmpl (Z) = Csieve_22_Cmpl_1
sieve_22_Cmpl (S (Z)) = Csieve_22_Cmpl_2
sieve_22_Cmpl (S (S x)) = sieve_22_Cmpl (x)
sieve_22_T_I x1 x2 = mplus (sieve_22_T_I_1 x1 x2) (mplus (sieve_22_T_I_2 x1 x2) (mplus (sieve_22_T_I_3 x1 x2) mzero))
sieve_22_T_I_1 (Z) (Csieve_22_Cmpl_1) = do return (Z)
sieve_22_T_I_1 _ _ = mzero
sieve_22_T_I_2 (Z) (Csieve_22_Cmpl_2) = do return (S Z)
sieve_22_T_I_2 _ _ = mzero
sieve_22_T_I_3 (S tv1) tc1 = do (x) <- sieve_22_T_I tv1 tc1
                                return (S (S x))
sieve_22_T_I_3 _ _ = mzero
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

How to Build Using cabal-install
--------------------------------

If you have [cabal-install] (part of the Haskell Platform) available on your system, you can install b18n-combined using the command

    cabal install bidirectionalization-combined

[cabal-install]: http://haskell.org/cabal/download.html

How to Build Manually
---------------------


  0. Install [GHC] and make sures that following Haskell packages 
     are installed.
     * mtl, template-haskell, containers, pretty, parsec (for web interface: directory, xhtml, cgi, utf8-string, bytestring, unix, hint >= 0.3.2)
  1. Get the source tarball from 
     [./bidirectionalization-combined-0.1.tar.gz](./bidirectionalization-combined-0.1.tar.gz) or from [hackage].
  2. Unfold the source tarball
     * `tar zxvf bidirectionalization-combined-0.1.tar.gz` 
  3. Build the executables by 
     1. `runhaskell Setup.hs configure`
     2. `runhaskell Setup.hs build`
    
Note that the source code is also available via darcs.

     darcs get http://www.kb.ecei.tohoku.ac.jp/~kztk/darcs/sem_syn/

[GHC]: http://www.haskell.org/ghc/
[hackage]: http://hackage.haskell.org/package/bidirectionalization-combined


Limitation
----------

Current implementation can handle lists only.

<div class="footer">

----------------------------------------------------
<address>Kazutaka Matsuda: <kztk@kb.ecei.tohoku.ac.jp>.</address>

<p>The first version of this page was published in Jul. 29th, 2010.</p>

</div>

