bidirectionalization-combined: Prototype Implementation of Combining Syntactic and Semantic Bidirectionalization (ICFP'10)

[ language, program, public-domain ] [ Propose Tags ]

This is a prototype implementation of the idea presented in Combining Syntactic and Semantic Bidirectionalization by Janis Voigtlaender, Zhenjiang Hu, Kazutaka Matsuda and Meng Wang.

This package builds two executables to experiment with the system, a command line program "b18-combined" and a CGI based web interface "b18n-combined-cgi". The latter is also available online at

[Skip to Readme]
Versions [RSS] [faq] 0.1,
Dependencies base (==4.*), bytestring, cgi, containers, directory, hint (>=0.3.2), mtl, parsec, pretty, template-haskell, unix, utf8-string, xhtml [details]
License LicenseRef-PublicDomain
Author Kazutaka Matsuda, Joachim Breitner
Category Language
Home page
Source repo head: darcs get
Uploaded by JoachimBreitner at 2010-09-27T10:24:31Z
Distributions NixOS:
Executables b18n-combined-cgi, b18n-combined
Downloads 1785 total (4 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs not available [build log]
Last success reported on 2015-05-18 [all 10 reports]


Maintainer's Corner

For package maintainers and hackage trustees


Readme for bidirectionalization-combined-

[back to package description]
 `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ä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]:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ {.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


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



Current implementation can handle lists only.

<div class="footer">

<address>Kazutaka Matsuda: <>.</address>

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