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]


Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


  • No Candidates
Versions [RSS] 0.1,
Dependencies base (>=4 && <5), 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
Revised Revision 1 made by JoachimBreitner at 2022-02-07T11:03:01Z
Category Language
Home page
Source repo head: git clone
Uploaded by JoachimBreitner at 2010-09-27T10:24:31Z
Reverse Dependencies 1 direct, 0 indirect [details]
Executables b18n-combined-cgi, b18n-combined
Downloads 1887 total (4 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs not available [build log]
Last success reported on 2015-05-18 [all 10 reports]

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&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]:

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