೔ຊιϑτ΢ΣΞՊֶձୈ 33 ճେձ (2016 ೥౓) ߨԋ࿦จूA bidirectional language for parsing andreflective printing
Zirun Zhu ɹ Yongzhe Zhang ɹ Hsiang-Shang Ko ɹ
Pedro Martins ɹ João Saraiva ɹ Zhenjiang Hu
Language designers usually need to implement parsers and printers. Despite being two intimately related
programs, in practice they are often designed separately, and then need to be revised and kept consistent
as the language evolves. It will be more convenient if the parser and printer can be unified and developedin one single program, with their consistency guaranteed automatically.
Furthermore, in certain scenarios (like showing compiler optimisation results to the programmer), it isdesirable to have a more powerful reflective printer that, when an abstract syntax tree corresponding to apiece of program text is modified, can reflect the modification to the program text while preserving layouts,
comments, and syntactic sugar.
To address these needs, a domain-specific language BiYacc is proposed, with which users can specify
both a parser and a reflective printer for an unambiguous grammar in a single program. BiYacc is basedon the theory of bidirectional transformations, which helps to guarantee by construction that the pairs ofparsers and reflective printers generated by BiYacc are consistent. BiYacc is capable of facilitating manytasks such as Pombrio and Krishnamurthi’s “resugaring”, language evolution, and refactoring.

structured and simplified representation and is eas-

1 Introduction

ier for the back-end to manipulate. On the other

Whenever we come up with a new programming

hand, a printer converts an AST back to a piece of

language, as the front-end part of the system weprogram text, which can be understood by the userneed to design and implement a parser and a printerof the system; this is useful for debugging the sys-

to convert between program text and an internaltem, reporting internal information to the user, or

representation. A piece of program text, while con-observing the optimisations performed on the AST

forming to a concrete syntax specification, is a flatby the back-end of the compiler [25].

string that can be easily edited by the program-

Parsers and printers do conversions in opposite

mer. A parser extracts the tree structure from suchdirections and are intimately related — for in-a string to a concrete syntax tree (CST), and con-stance, the program text printed from an AST

verts it to an abstract syntax tree (AST), which is ashould be parsed to the same tree. It is certainly far∗ This is an unrefereed paper.

Copyrights belong to
the authors.
Zirun Zhu ɹ Yongzhe Zhang, ૯ ߹ ‫ ڀ ݚ‬େ ֶ Ӄ େ ֶ,
SOKENDAI.
Hsiang-Shang Ko ɹ Zhenjiang Hu, ࠃཱ৘ใֶ‫ॴڀݚ‬,National Institute of Informatics.
Pedro Martins, ΧϦϑΥϧχΞେֶΞʔόΠϯߍ, University of California, Irvine.
Joo Saraiva, ϛʔχϣେֶ, University of Minho.

from being economical to write parsers and printers separately: The parser and printer need to berevised from time to time as the language evolves,and each time we must revise both of the two components and keep them consistent with each other,which is a time-consuming and error-prone task.
In response to this problem, many domain-specificOriginal program text:// the expression evaluates...
-a /* a is the variable denoting. . . */ *(1 + 1 + (a))

Abstract syntax tree:
Mul (Sub (Num 0) (Var "a"))(Add (Add (Num 1) (Num 1)) (Var "a"))tion that is hard for humans to read and is usually
not exposed to the user. So a natural idea is toreflect the change on the AST back to the program
text to make it easier for the user to check where
the changes are. With a conventional printer, immediately a problem occurs, as the printed result

Optimised abstract syntax tree:

will likely mislead the programmer into thinking

Mul (Sub (Num 0) (Var "a"))(Add (Num 2) (Var "a"))that the negation is replaced by a subtraction by

Printed result from a conventional printer:(0 - a) * (2 + a)

Printed result from an ideal printer:// the expression evaluates...
-a /* a is the variable denoting. . . */ *(2 + (a))ਤ1Conventional printer and reflective printerlanguages [3] [28] [26] [9] [21] have been proposed, inwhich the user can describe both a parser and aprinter in a single program. By unifying these twopieces of software and deriving them from single
and centralised code, we are creating a unified en-

the compiler; in addition, since the comments are
not preserved, it will be harder for the programmer to compare the updated and original versionsof the text. The problem illustrated here also occurs in many other practical situations where theparser and printer are used as a bridge between thesystem and the user, for example,• in program debugging where part of the orig-

inal program in an error message is displayedmuch diﬀerently from its original form [7] [19],and• in program refactoring where the comments
and layouts in the original program are com-vironment, which is easier to maintain and update,pletely lost after the AST is transformed by thetherefore respecting the “Don’t Repeat Yourself”

system [6].

principle of software development [16].

To make the printed result better, many at-

Despite their advantages, these domain-specifictempts have been made to enrich ASTs with morelanguages cannot deal with synchronisation be-

information. To see a particular instance, Pombrio

tween program text and ASTs, in the sense thatand Krishnamurthi [25] propose the notion resug-a printer will always produce a new piece of pro-aring, which devotes to representing evaluation se-gram text from scratch. Let us look at a concrete

quences in a core language in terms of its surface

example in Figure 1: The original program text is

syntax. Despite the fact that by applying thesean arithmetic expression, containing negation, (re-methods, the syntactic sugar (-a) in this example

dundant) parentheses, and some comments. It is

can be preserved during the printing, these meth-first parsed to an AST (supposing that addition

ods contaminate ASTs by injecting more than nec-

is left-associative) where the negation is desugared

essary information. As a results, the compiler is

to a subtraction, parentheses are implicitly repre-

hard to perform optimisation, and other tools de-sented by the tree structure, and the comments are

signed for the language must also carefully handle

thrown away. Then the AST is optimised by replac-

the additional information in AST.

ing Add (Num 1) (Num 1) with a constant Num 2. The

We aim to address these problems:

user may want to observe the optimisation made by• unifying the design of parsers and printers,

the compiler, but the AST is an internal representa-• reflecting changes properly into the original

program text when printing, and//www.prg.nii.ac.jp/project/biyacc.html, which con-• keeping the AST clean and neat.

tains two input examples with various test casesby proposing a domain-specific language BiYacc,

used in this paper.

which lets the user describe both a parser and a

The rest of the paper is organised as follows:reflective printer for an unambiguous grammar in• We first give an overview of BiYacc in Section 2,

a single program. Diﬀerent from a conventional

explaining how to describe in a single program

printer, a reflective printer will take a piece of pro-both a parser and a reflective printer for syn-gram text and an AST, which is usually slightly

chronising program text and its abstract syntax

modified from the AST corresponding to the pro-

representation.

gram text, and reflects the modification to the program text. Meanwhile the comments (and layouts)• After reviewing some background on bidirec-

tional transformations in Section 3, in partic-in the unmodified parts of the program text canular the bidirectional programming language

all be preserved. A taste of the reflective printing

BiGUL [18], we give the semantics of BiYacc

can be seen clearly from the above arithmetic ex-by compiling it to BiGUL in Section 4, guaran-pression example as shown in Figure 1. It is worth

teeing the properties (1) and (2) by construction.

noting that reflective printing is a generalisation of• We present a case study in Section 5, showing

the conventional notion of printing, because a re-that even though BiYacc is currently restricted

flective printer is able to accept an AST and an

to dealing with unambiguous grammars, it isempty piece of program text, in which case it willcapable of describing Tiger [1], which sharesbehave as a conventional printer producing a new

many similarities with full grown, widely used

piece of program text depending on the AST only.

languages. We demonstrate that BiYacc canFrom a BiYacc program we can generate ahandle syntactic sugar, partially subsume Pom-parser and a reflective printer; in addition, we wantbrio and Krishnamurthi’s “resugaring” [25], andto guarantee that the two generated programs are
consistent with each other. Specifically, we want toensure two inverse-like properties: Firstly, a pieceof program text s printed from an abstract syntax
tree t should be parsed to the same tree t, i.e.,parse (print s t) = t

facilitate language evolution.
• Related work including detailed comparison

with other systems is presented in Section 6 andin Section 7 we conclude the paper and present
some future work.

(1)

2 Language design of BiYacc

Secondly, updating a piece of program text s

This section presents the language design of Bi-

with an abstract syntax tree parsed from s should

Yacc by a running example handling arithmetic ex-leave s unmodified (including formatting details

pressions previously shown in Figure 1. We briefly

like parentheses and spaces), i.e.,summarise the definition of the syntax of BiYacc

print s (parse s) = s(2)These two properties are inspired by the theory ofbidirectional transformations [5] [15], and are guaranteed by construction for all BiYacc programs.
An online tool that implements the approachdescribed in this paper can be accessed at http:programs in Section 2. 1. In Section 2. 2, we present
the structure, the syntax, and the semantics of BiYacc programs from a high-level aspect by writing
the program for the arithmetic expression problem.

2. 1 Definition of BiYacc’s syntax
The syntax of BiYacc programs is shown in Figure 2, where the definition is rather straightforward
and can be treated as production rules. Anything
wrapped in single quotes is string literal, which
is basically keywords and built-in symbols of BiYacc. Terminal s are usually keywords and symbols in a user-defined language (such as ‘+’, ‘-’,‘let’, etc) and should be put within single quotes
in a BiYacc program, A Nonterminal is a symbolthat could be expanded to a list of Symbol s in theusual sense. HsDeclarations are Haskell declara-

Program ::= ‘Abstract’ HsDeclarations‘Concrete’ ProductionGroup +‘Actions’ ActionGroup +ProductionGroup ::= Nonterminal ‘->’ProductionBody + {‘|’} ‘;’
ProductionBody ::= Symbol+
Symbol ::= Primitive | Terminal | Nonterminal
ActionGroup ::= HsType ‘+>’ Nonterminal
Action +Action ::= HsPattern ‘+>’ Update + ‘;’
Update ::= Symbol| ‘(’ HsVariable ‘+>’UpdateCondition ‘)’| ‘(’ Nonterminal ‘->’ Update + ‘)’
UpdateCondition ::= Symbol| ‘(’ Nonterminal ‘->’UpdateCondition + ‘)’tions, and HsPattern and HsType denotes respectively a Haskell pattern and a Haskell datatype that

notation can be found in ProductionBody + {‘|’}

ਤ 2 Syntax of BiYacc programs
Nonterminals with prefix Hs denote Haskell entities andfollow the Haskell syntax; the notation nt + {sep} denotes a nonempty sequence of the same nonterminal nt
separated by sep; Name represents an identifier startingwith a character and followed by characters and numbers.

currence of ProductionBody is divided by the ver-it takes. Hence the constructors Add, Sub, Mul, andtical bar (‘|’). Spaces (including newline) merely

Div take two subexpressions (of type Arith) as ar-means string concatenation.

guments, while the constructors Var and Num respec-should conform to the datatype definitions in the
HsDeclarations part. Their definitions follow thesyntax of Haskell and are thus omitted here. A rare
where the bracket part means that one or more oc-

tively takes an String and Int as their arguments.
2. 2 Programs in BiYacc
A BiYacc program consists of three parts: abstract syntax definition, concrete syntax definition,
and actions describing how to update a concrete
syntax tree (CST) with an AST.
2. 2. 1 Defining the abstract and concrete
syntax

For instance, the expression “1 + 2 ∗ 3 − 4” can be
represented as this AST of type Arith:
Sub (Add (Num 1)(Mul (Num 2)(Num 3)))(Num 4)On the other hand, the concrete syntax — which
is defined in the second part beginning with the

The abstract syntax part — which starts with the

keyword Concrete — is defined by a context-free

keyword Abstract — is just one or more definitions

grammar, i.e., a set of production rules specifyingof Haskell datatypes. In our example, the abstract

how nonterminal symbols can be expanded to se-

syntax is defined in lines 1–9 by a single datatypequences of terminal and nonterminal symbols. For

Arith whose elements are constructed from inte-

our expression example, in lines 16–27 we use ager constants, variables, and the arithmetic oper-

standard grammatical structure to encode opera-

ators. Diﬀerent constructors — namely Add, Sub,tor precedence and order of association, which in-

Mul, Div, and Num — are used to construct diﬀer-

volves three nonterminal symbols Expr, Term, andent kinds of expressions, and in the definition each

Factor: An Expr can produce a left-leaning tree of

constructor is followed by the types of arguments

Terms, each of which can in turn produce a left-

leaning tree of Factors. To produce right-leaning

to update a CST — i.e., a piece of program text

trees or operators of lower precedence under those— with an AST. For our expression example, thewith higher precedence, the only way is to reachactions are defined in lines 29–45 in Figure 4. Be-

for the last production rule Factor -> '(' Expr ')',

fore explaining the actions, we should emphasise

resulting in parentheses in the produced programthat we are identifying program text with CSTs:

text. (There is also a nonterminal Name, which

Conceptually, whenever we write a piece of pro-produces identifiers.)

gram text, we are actually describing a CST rather

Syntax for comments.

than just a sequence of characters. Technically, it

Syntax for comments can be declared at the be-is almost eﬀortless to convert a piece of program

ginning of this part before any production rules.

text to a CST with existing parser technologies (weFor example, line 13 shows that the syntax for afollow the normal convention for parser-generating

single line comments is “//”, while line 14 statessystems that grammars must be unambiguous); thethat “/*” and “*/” are respectively the beginning

reverse direction is even easier, requiring only amark and ending mark for a block comment.

traversal of the CST. By integrating with existingparser technologies, BiYacc actions can focus on

1

Abstract

describing conversions between CSTs and ASTs —

2
3
4
5
6
7
8
9

data Arith = Num Int| Var String| Add Arith Arith| Sub Arith Arith| Mul Arith Arith| Div Arith Arith
deriving (Show, Eq, Read)

10
11

14

-> Expr '+' Term
| Expr '-' Term
| Term ;

19

22

25
26
27

ਤ3

Arith +> Expr
Add x y +> (x +> Expr) '+' (y +> Term);
Sub x y +> (x +> Expr) '-' (y +> Term);arith+> (arith +> Term);

34
35

Arith +> Term
Mul x y +> (x +> Term) '*' (y +> Factor);
Div x y +> (x +> Term) '/' (y +> Factor);arith+> (arith +> Factor);

37
38
39
40

Term

-> Term '*' Factor| Term '/' Factor| Factor ;

23
24

30

36

Expr

18

21

Actions

29

33%commentLine '//';
%commentBlock '/*' '*/' ;17

20

program text with CSTs in Section 4. 3.

32

15
16

printing. We will expound on this identification of

31

Concrete1213

the more interesting part in the tasks of parsing andArith +> Factor
Sub (Num 0) y +> '-' (y +> Factor);
Num i+> (i +> Int);
Var n+> (n +> Name);arith+> '(' (arith +> Expr) ')';

41
42
43
44

Factor -> '-' Factor| Int| Name| '(' Expr ')' ;45

ਤ4Synchronisation strategy part of a BiYacc
programSyntax definition parts of a BiYacc
program

The Actions part consists of groups of actions,and each group begins with a “type declaration”

2. 2. 2 Defining actionsof the form hsType ‘+>’ nonterminal stating that

The last and main part of a BiYacc program

the actions in this group specify updates on CSTs

starts with the keyword Actions, and describes how

generated from nonterminal using ASTs of type

hsType.

Informally, given an AST and a CST,

matching for an action succeeds, the updating oper-

the semantics of an action is to perform patternations specified by the action is executed; otherwise

matching simultaneously on both trees, and then

the next action is tried. Execution of the program

use components of the AST to update correspond-ends when the matched action specifies either noing parts of the CST, possibly recursively. (Theupdating operations or only updates to primitive

syntax ‘+>’ suggests that information from the left-

datatypes such as Int. BiYacc’s most interesting

hand side is embedded into the right-hand side.)behaviour shows up when all actions in the chosen

Usually the nonterminals in a right-hand side pat-group fail to match — in this case a suitable CST

tern are overlaid with update instructions, which

will be created. The specific approach adopted by

are also denoted by ‘+>’.

BiYacc is to perform pattern matching on the AST

Let us look at a specific action — the first one

only and choose the first matched action. A suit-for the expression example, at line 32 of Figure 4:

able CST conforming to the CST pattern is thenAdd x y +> (x +> Expr) '+' (y +> Term);

created, and after that the whole group of actions is

For the view pattern Add x y, an AST (of type

tried again. This time the pattern matching should

Arith) is said to match the pattern when it starts

succeed at the action used to create the CST, andwith the constructor Add (because the variable pat-the program will be able to make further progress.

tern, for example x and y, matches anything); if

Complex patterns.

the match succeeds, the two arguments of the con-

It is interesting to note that, by using more com-

structor (i.e., the two subexpressions of the ad-plex patterns, we can write actions that establish

dition expression) are then respectively bound to

nontrivial relationships between CSTs and ASTs.

the variables x and y. As for the CST pattern,

For example, the action at line 42 of Figure 4 as-

the main intention is to refer to the productionsociates abstract subtraction expressions whose left

rule Expr -> Expr '+' Term and use it to match those

operand is zero with concrete negated expressions;

CSTs produced by this rule. Since the action be-

this action is the key to preserving negated expres-longs to the group Arith +> Expr, the part ‘Expr ->’sions in the CST. For an example of a more com-of the production rule can be inferred, and thus isplex CST pattern: Suppose that we want to write a

not included in the CST pattern. Finally we over-pattern that matches those CSTs produced by thelay ‘x +>’ and ‘y +>’ on the nonterminal symbols

rule Factor -> '-' Factor, where the inner nonter-

Expr and Term to indicate that, after the simultane-

minal Factor produces a further '-' Factor using theous pattern matching succeeds, the subtrees x and ysame rule. This pattern is written by overlaying theof the AST are respectively used to update the left

production rule on the first nonterminal Factor (anand right subtrees of the CST.

additional pair of parentheses is required for the ex-

Semantics of the program.

panded nonterminal): '-' (Factor -> '-' Factor).

Having explained what an action means, we canMore examples involving this kind of deep patterns

now explain the semantics of the entire program.

will be presented in Section 5.

Given an AST and a CST as input, first a group

Layouts and comments preservation.

of actions is chosen according to the types of the

The reflective printer generated by BiYacc istrees. Then the actions in the group are tried incapable of preserving layouts and comments, but,order, from top to bottom, by performing simulta-

perhaps mysteriously, in Figure 3 and Figure 4

neous pattern matching on both trees. If pattern

there is no clue as to how layouts and commentsare preserved. This is because we decide to hidewhich respects that relation. We will explain how

layout preservation from the programmer, so that

this is achieved in the next section.

the more important logic of abstract and concrete

3 Foundation for BiYacc:

putback-

syntax synchronisation is not cluttered with layout

based bidirectional transformations

preserving instructions. Our current approach is

The behaviour of BiYacc is totally nontrivial:

fairly simplistic: We store layout information fol-Not only do we need to generate two diﬀerent

lowing each terminal in an additional field in the

programs from one, but we also need to guaran-

CST implicitly, and treat comments in the same
way as layouts†1 . During the printing stage, if thetee that the two generated programs are consis-

pattern matching on an action succeeds, the lay-

(1) and (2) stated in Section 1. It is possible toouts and comments after the terminals shown inseparately implement the print and parse seman-

the right-hand side of that action are preserved; ontics in an ad hoc way, but verifying the two con-the other hand, layouts and comments are dropped

sistency properties takes extra eﬀort. The imple-

when a CST is created in the situation where pat-mentation we present, however, is systematic andtern matching fails for all actions in a group. The

guarantees consistency by construction, thanks tolayouts and comments before the first terminal are

the well-developed theory of bidirectional transfor-

always kept during the printing. More details aboutmations (BXs for short). (See [5] and [15] for athis treatment and some exceptions can be foundcomprehensive introduction.)tent with each other, i.e., satisfy the properties

in Section 4.
Parsing semantics.
So far we have been describing the reflective

3. 1 Parsing and printing as bidirectionaltransformations

printing semantics of the BiYacc program, but we

The parse and print semantics of BiYacc pro-

may also work out its parsing semantics intuitively

grams are potentially partial — for example, if the

by interpreting the actions from right to left, con-actions in a BiYacc program do not cover all pos-verting the production rules to the corresponding

sible forms of program text and abstract syntax

constructors.

(This might remind the reader oftrees, parse and print will fail for those uncovered

the usual Yacc actions.) In fact, this paper will

inputs. Thus we should take partiality into accountnot define the parsing semantics formally, because

when choosing a BX framework in which to model

the parsing semantics is completely determined byparse and print. The framework we use in this pa-

the reflective printing semantics: If the actions are

per is an explicitly partial version of asymmetricwritten with the intention of establishing some re-lenses [11]: A (well-behaved) lens between a source

lation between the CSTs and ASTs, then BiYacc

type S and a view type V is a pair of functions get

will be able to derive the only well-behaved parser,

and put, where†1 One might argue, though, that layouts and comments should in fact be handled diﬀerently, sincecomments are usually attached to some entities
which they describe. For example, when a function declaration is moved to somewhere else (e.g.,
by a refactoring tool), we will want the comment
describing that function to be moved there as well.
We leave the proper treatment of comments as future work.

• the function get :: S → Maybe V extracts apart of a source of interest to the user as aview, and• the function put :: S → V → Maybe S

takes a source and a view and produces an
updated source incorporating information fromthe view.

Partiality is explicitly represented by wrapping theTheorem. Given a put function, there is at mostresult types in the Maybe monad. The pair of func-

one get function that forms a (well-behaved) BX

tions should satisfy the well-behavedness laws:with this put function.

′′

get s = Just v (PutGet)

That is, once we describe a put function in BiGUL,put s v = Just s (GetPut)

not only can we immediately obtain a get func-

Informally, the PutGet law enforces that put musttion satisfying PutGet and GetPut with the put

embed all information of the view into the up-

function, but also guarantee that the get function

dated source, so the view can be recovered from theis unique, i.e., completely determined by the put

source by get, while the GetPut law prohibits put

function. Due to this theorem, in this paper wefrom performing unnecessary updates by requiring

can focus solely on the printing (put) behaviour,that putting back a view directly extracted from aleaving the parsing (get) behaviour only implicitly

source by get must produce the same, unmodified(but unambiguously) specified.

put s v = Just s ⇒get s = Just v ⇒source. The parse and print semantics of a Bi-

BiGUL [18] is a putback-based bidirectional pro-Yacc program will be the pair of functions get andgramming language. It has been formally verified

put in a BX, satisfying the PutGet and GetPutin Agda [22] that BiGUL programs always de-laws by definition. The well-behavedness laws arenote well-behaved BXs. BiGUL is putback-based,

then exactly the consistency properties (1) and (2)meaning that a BiGUL program describes a put

reformulated for a partial setting.

function, but — since BiGUL is bidirectional —can also be executed as the corresponding get func-

3. 2 Putback-based bidirectional programmingtion. The specific BiGUL that we used for the BiYacc implementation, is an embedded DSL library

Having rephrased parsing and printing in termsof the Haskell port version. Here we introduceof BXs, we can now easily construct consistent pairs

three constructs in BiGUL to which a BiYacc pro-of parsers and printers using bidirectional program-

gram is compiled to.

ming techniques, in which the programmer writes

A BiGUL program has type BiGUL s v, where sa single program to denote the two directions ofand v are respectively the source and view types;

a well-behaved BX. Specifically, BiYacc programs

its put interpreter can then be given the typeare compiled to the putback-based bidirectional programming language BiGUL [18]. It has been formally verified in Agda [22] that BiGUL programs
always denote well-behaved BXs, and BiGUL has
been ported to Haskell as an embedded DSL library, which will be introduced in more detail in
Section 3. 2. BiGUL is putback-based, meaningthat a BiGUL program describes a put function,
but — since BiGUL is bidirectional — can also be
executed as the corresponding get function. The
advantage of putback-based bidirectional programming lies in the following theorem [12]:put :: BiGUL s v -> s -> v -> Maybe s

Replace.
The simplest BiGUL operation we use is
Replace :: BiGUL s s

which discards the original source and returns theview — which has the same type as the source —as the updated source. That is,
put Replace _ v = v

Update.
The next operation update is more complex, andis implemented with the help of Template Haskell[27]. The general form of the operation is$(update [p| spat |] [p| vpat |] [d| bs |]):: BiGUL s v(s -> v -> s) -> Branch s v

This operation decomposes the source and view by

Their put semantics are as follows: A branch ispattern matching with the patterns spat and vpat

applicable when the source and view respectively

respectively, pairs the source and view components

match spat and vpat in its main condition. Exe-as specified by the patterns (see below), and per-cution of a Case chooses the first applicable branchforms further BiGUL operations listed in bs on thefrom the list of branches, and continues with thatsource–view pairs. The way to determine whichbranch. When the chosen branch is normal, the as-source and view components are paired and whichsociated BiGUL operation is performed, and theoperation is performed on a pair is by looking forthe same names in the three arguments — for ex-

updated source should satisfy the exit condition
spat ′ (otherwise it is a runtime error)†3 ; when theample, this update operation

chosen branch is adaptive, the associated function$(update [p| (x, _) |] [p| x |] [d| x = Replace |])is applied to the source and view to compute anpairs first component of the source with the view,

adapted source, and the whole Case is rerun on thesince both are matched with x; the Replace oper-

adapted source and the view, and should go into

ation is then performed on this pair, since it isa normal branch this time. Think of an adaptive

the operation associated with x in the (singleton)
list of operations†2 . In general, any (type-correct)

branch as bringing a source that is too mismatched

BiGUL program can be used in the list of fur-

mal branch — which deals with sources and views

ther updates, not just the primitive Replace. In

in some sort of correspondence — can take over.

the source pattern, the part marked by underscore

This adaptation mechanism is used by BiYacc to(_) simply means that it will be skipped during theprint an AST when the source program text is too

update.

diﬀerent from the AST or even nonexistent at all.

Case.
The most complex operation we use is Case fordoing case analysis on the source and view:
Case :: [Branch s v] -> BiGUL s v

with the view to a suitable shape so that a nor-

4 Implementation of BiYacc
This section provides a prototype implementation of BiYacc in detail. The architecture of BiYacc is shown in Figure 5: On the surface, theCase takes a list of branches, of which there are two

programmer supplies a three-part BiYacc programkinds: normal branches and adaptive branches. For

as described in Section 2. 2, which is compiled into

a normal branch, we should specify a main condi-

an executable for performing synchronisation be-tion using a source pattern spat and a view pattern

tween program text and ASTs.

vpat, and an exit condition using a source patternficult to synchronise non-structured program text

spat ′ :and structured ASTs directly, we make use of ex-$(normalSV [p| spat |] [p| vpat |] [p| spat ′ |]) ::BiGUL s v -> Branch s v

An adaptive branch, on the other hand, only needsa main condition:$(adaptiveSV [p| spat |] [p| vpat |]) ::†2 This representation of lists of named BiGUL operations is admittedly an abuse of syntax, but
simplifies prototyping this system with Template
Haskell.

Since it is dif-isting technologies and separate the synchronisa†3 The exit condition is an over-approximation of
the range of this branch, so it is possible tocheck that the ranges of the branches in the same
Case statement are disjoint, as is standard forbidirectional or reversible programs. In general,
BiGUL’s semantics incorporates several kinds ofruntime checks for guaranteeing bidirectionality,
and it is the programmer’s responsibility to ensure that these checks can succeed.

tion into two phases. The synchronisation now becomes the composition of two bidirectional trans-

Concrete
Syntax

Abstract
Syntaxformations, one between program text and CSTs

BiYacc Program

and the other between CSTs and ASTs. The sec-

Compiler

ond BX is constructed as a BiGUL program andExecutable

is well-behaved by construction; we will explain in
Lexer

Section 3. 2 the basics of BiGUL and in Section
4. 1 how this BiGUL program is derived. The first
BX, on the other hand, is in fact an isomorphism,

Program
Text

ParserTokensBiGULProgram
CST

AST

Printerwhich we construct in a more ad hoc manner. Morespecifically, we derive a lexer and a parser (using

Printing
Actionsਤ5

Architecture of BiYacc

the parser generator Happy) for converting program text to CSTs, and a printer for flattening

to the semantic bracket are typeset in superscript.

CSTs to program text; this isomorphism, which

Top-level structure.

we call concrete parsing and printing, will be ex-

A BiYacc Program has the form

plained in Section 4. 2 and Section 4. 3. As is well

‘Abstract’ decls ‘Concrete’ pgs ‘Action’ ags

known, isomorphisms are special cases of BXs, andand is compiled to a three-part Haskell program by

the composition of two BXs is again a BX, so the

copying decls (which is already valid Haskell code),

composite transformations are still well-behaved.

converting each group of production rules in pgs

The grammar accepted by BiYacc is restricted

to a datatype, and each action group in ags to a

to pure LALR (1) without disambiguation rules

small BiGUL program. The
angle bracket nota1"!
#"
tion f e e ∈ es denotes the generation of ain the current implementation.

And the well-

behavedness of a BiYacc program is guaranteed bylist of entities of the form f e for each element e

the compiled BiGUL program, which means thatin the list es, in the order of their appearance insometimes BiGUL will raise a runtime error for thees. Comment syntax declarations (%commentLine andbad transformations not satisfying the properties%commentBlock) are only relevant to concrete parsing(1) and (2). In the future, we plan to extend Bi-

and printing, and are ignored in Figure 6.

Yacc by making more static checks, and support-

CST datatypes.

ing disambiguation declarations or employing other

The production rules in a context-free grammarparser generators so that it can handle a wider classdictate how to generate strings from nonterminals,

of grammars.

and a CST can be regarded as encoding one particular way of generating a string using the production

4. 1 Generating the BiGUL program

rules. In Haskell, we represent CSTs starting fromThe semantics of BiYacc, shown in Figure 6, isa nonterminal nt as a datatype named nt, whose

defined by source-to-source compilation to BiGUL.

constructors represent the production rules for nt.

Compilation rules are defined with the semantic

For each constructor we generate a unique name,bracket ([[·]]), and refer to some auxiliary functions,which is denoted by con(nt, syms). The fields of awhose names are in small caps. A nonterminal

constructor are generated from the right-hand sidein subscript gives the “type” of the argument orof the corresponding production rule in the way

metavariable before it, and additional arguments

described by the auxiliary function field: Nonter-[[‘Abstract’! decls ‘Concrete’" pgs ‘Action’# ! ags]]Program ="#decls [[pg]]ProductionGroup " pg ∈ pgs [[ag]]ActionGroup " ag ∈ ags[[nt ‘->’ bodies]]!ProductionGroup =!
""##‘data’ nt ‘=’ con(nt, syms) field(s) " s ∈ syms ‘|’ " syms ∈ bodies nullCon(nt)[[vt ‘+>’ st acts]]ActionGroup =prog(vt, st) ‘::’ ‘BiGUL’ st vt"! N,vt,st# ! A, st "#prog(vt, st) ‘=’ ‘Case’‘[’ [[a]]Action ‘,’ " a ∈ acts[[a]]Action " a ∈ acts {‘,’} ‘]’[[vpat ‘+>’ updates]]N,vt,stAction =‘$(normalSV’‘[p|’ srcCond(eraseVars(‘(’ st ‘->’ updates ‘)’)Update ) ‘|]’‘[p|’ vpat ‘|]’‘[p|’ srcCond(eraseVars(‘(’ st ‘->’ updates ‘)’)Update ) ‘|])’‘$(update’ ‘[p|’ removeAs(vpat)‘|]’ ‘[p|’"!
# srcPat(‘(’ st ‘->’ updates ‘)’)Update ‘|]’" u ∈ updates ‘|])’‘[d|’ [[u]]vt,vpat
Update[[‘(’ var ‘+>’ uc Primitive ‘)’]]vt,vpat
Update = var ‘= Replace;’[[‘(’ var ‘+>’ uc Nonterminal ‘)’]]vt,vpat
Update = var ‘=’ prog(varType(vt, vpat, var ), uc) ‘;’
vt,vpat[[‘(’ var ‘+>’ ‘(’ nt ‘->’ . . . ‘)’ ‘)’]]!vt,vpat
Update = [[‘(’ var" ‘+>’ nt ‘)’]]#Update
vt,vpatvt,vpat[[‘(’ . . . ‘->’ updates ‘)’]]Update = [[u]]Update ‘;’ " u ∈ updates[[symbol]]vt,vpat
Update = ‘’st[[vpat ‘+>’ updates]]A,
Action =‘$(adaptiveSV’ ‘[p| _ |]’ ‘[p|’ vpat ‘|])’‘(\_ _ ->’ defaultExpr(eraseVars(‘(’ st ‘->’ updates ‘)’)) ‘)’

field(nt)Nonterminal = nt
field(t)Terminal= ‘String’
field(p)Primitive= ‘(’ p ‘, String)’
eraseVars(‘(’ var ‘+>’ uc ‘)’)Update = uc
eraseVars(‘(’ nt ‘->’ updates" ‘)’)Update =#!
‘(’ nt ‘->’ eraseVars(u) " u ∈ updates ‘)’ eraseVars(symbol )Update = symbol
srcCond(‘(’ nt ‘->’ uconds ‘)’)" UpdateCondition# =!
"!
#‘(’ con(nt, condHead(uc) " uc ∈ uconds ) srcCond(uc) " uc ∈ uconds ‘)’
srcCond(symbol )UpdateCondition = ‘_’condHead(‘(’ nt ‘->’ . . . ‘)’)UpdateCondition = nt
condHead(symbol )UpdateCondition = symbol

srcPat(‘(’ var ‘+>’ uc Primitive ‘)’)Update = ‘(’ var ‘, _)’srcPat(‘(’ var ‘+>’ uc Nonterminal ‘)’)Update = var
srcPat(‘(’ nt ‘->’ updates ‘)’)"Update =
"
!
# !
#
‘(’ con(nt, condHead(uc) " uc ∈ eraseVars(updates) ) srcPat(u) " u ∈ updates ‘)’
srcPat(symbol )Symbol = ‘_’defaultExpr(symbol )Primitive = ‘(undefined, " ")’defaultExpr(symbol )Nonterminal = nullCon(symbol )defaultExpr(symbol )Terminal = ‘" "’defaultExpr(‘(’ nt ‘->’ uconds‘)’)UpdateCondition
=
"
"
!
# !
#
con(nt, condHead(uc) " uc ∈ uconds ) defaultExpr(uc) " uc ∈ uconds
ਤ6

Semantics of BiYacc programs (as BiGUL programs)

minals are left unchanged (using their names forprimitives for storing layout information (whites-

datatypes), terminal symbols are dropped, and anpaces and comments) appearing after them in the

additional String field is added for terminals andprogram text. The last step is to insert an ad-ditional empty constructor, the unique name generated for which is denoted by nullCon(nt); thisempty constructor is used as a default value to a
BiYacc printer whenever we want to create a newis compiled to$(normalSV [p| (Factor0 _ _) |] [p| Sub (Num 0) y |][p| (Factor0 _ _) |])$(update [p| Sub (Num 0) y |] [p| (Factor0 _ y) |][d| y = bigulArithFactor; |])piece of program text depending on the view only.

When the CST is a Factor0 and the AST matches

For instance, the third group of the concrete syn-Sub (Num 0) y, we enter this branch, decompose thetax defined in Figure 3 is translated to the following

source and view by pattern matching, and use

Haskell declarations:the view’s right subtree y to update the second

data Factor = Factor0 String Factor| Factor1 (Int, String)| Factor2 (Name, String)| Factor3 String Expr String| FactorNull2
deriving (Show, Eq, Read)

Note that the first String field of Factor0 stores thewhitespaces appearing after a negation sign in thefield of the source while skipping the first field(which stores whitespaces); the name of the BiGUL
program for performing the update is determinedby the type of the smaller source y (deduced by
varType) and that of the smaller view.

Adaptive branches.
When all actions in a group fail to match, we

program text.

should adapt the source into a proper shape to cor-

Action groups.
Each group of actions is translated into a small
BiGUL program, whose name is determined by theview type vt and source type st and denoted byprog(vt, st). The BiGUL program has one single
Case statement, and each action is translated into

respond to the view. This is done by generating
adaptive branches from the actions during compilation. For example, the first action in the Arith–
Factor group is compiled to$(adaptiveSV [p| _ |] [p| Sub (Num 0) _ |])(\ _ _ -> Factor0 " " FactorNull2)

two branches in this Case statement, one normal and

The body of the adaptation function is generated

the other adaptive. All the adaptive branches areby the auxiliary function defaultExpr, which cre-gathered in the second half of the Case statement,

ates a skeletal value that matches the source pat-so that normal branches will be tried first. For ex-

tern.

ample, the third group of type Arith +> Factor is

Entry point.

compiled tobigulArithFactor :: BiGUL Factor Arith
bigulArithFactor = Case [ . . . ]We said in Section 2 that the semantics of an action is to perform pattern matching on both thesource and view, and then update parts of thesource with parts of the view. This semantics is
implemented with a normal branch: The source
and view patterns are compiled to the entry condition, and, together with the updates overlaid on
the source pattern, also to an update operation. For
example, the first action in the Arith–Factor group+>

the BiGUL program compiled from the first groupof actions.

Normal branches.

Sub (Num 0) y

The entry point of the program is chosen to be'-' (y +> Factor)

This corresponds to our assumptionthat the initial input concrete and abstract syntax
trees are of the types specified for the first actiongroup. It is rather simple so the rules are not shownin the figure. For the expression example, we generate a definition
entrance = bigulArithExpr

which is invoked in the main program.
4. 2 Inverse properties between programtext and CSTs

is indeed the case because
parse (print cst) = Just cst ′Having explained the bidirectional transformation between CSTs and ASTs, the remaining task is⇒to establish an isomorphism between program text
and CSTs. Assuming that the grammar is unam-⇒

biguous and the parser generator is “correct”, we{ (3) }

print cst ′ = print cst{ print is injective }cst ′ = cst

will show that there exists an isomorphism between
program text and CSTs:
parse text = Just cst

4. 3 Generating concrete parser and printer⇒print cst = text (3)In current BiYacc, the implementation of the(4)parse function is further separated into two phases:

One direction is a partial (Maybe-valued) function

tokenising and parsing. In both phases, the layoutparse that converts program text into CSTs accord-

information (whitespaces and comments) is auto-

ing to the grammar, and the other is a total func-

matically preserved, which makes the CSTs isomor-

tion print from CSTs to program text.

phic to the program text. In the following, we willparse (print cst) = Just cst

To see the meaning of (3), we should first clarify

show how the lexer and parser are constructed andwhat print does: Our CSTs, as described in Section

later the printer.

4. 1, encode precisely the derivation trees, with the

Generating Lexer.

CST constructors representing the production rules

Apart from handling the terminal symbols ap-

used; what print does is simply traversing the CSTs

pearing in a grammar, the lexer automatically de-

and applying the encoded production rules to pro-rived by BiYacc can also recognise several kinds

duce the derived program text. Now consider whatof literals, including integers, strings, and iden-parse is supposed to do: It should take a piece oftifiers, respectively produced by the nonterminals

program text and find a derivation tree for it, i.e.,

Int, String, and Name. For now, the forms of thesea CST which prints to that piece of program text.

literals are pre-defined, but we take this as a stepThis statement is exactly (3). In other words, (3)towards a lexerless grammar, in which strings pro-is the functional specification of parsing, which isduced by nonterminals can be specified in terms

satisfied if the parser generator we use behaves cor-of regular expressions. Furthermore, whitespaces

rectly.

and comments are carefully handled in the derived

For (4), since the grammar is unambiguous, forlexer, so they can be completely stored in CSTs andany piece of program text there is at most one CST

correctly recovered to the program text in printing.

that prints to it, which is equivalent to saying that

This feature of BiYacc, which we explain below,

print is injective. In addition, it is reasonable tomakes layout preservation transparent to the pro-expect that a generated parser will be able to suc-grammer.

cessfully parse any valid program text; that is, for
any cst we haveAn assumption of BiYacc is that whitespaces
are only considered as separators between other to-parse (print cst) = Just cst ′kens. (Although there exist some languages such as

for some cst ′ . This is already close to (4); what re-

Haskell and Python where indentation does aﬀect

mains to be shown is that cst ′ is exactly cst, which

the meaning of a program, there are workarounds,
e.g., writing a preprocessing program to insert ex-

Usually, token separators arewrapped in the ‘-’ token; these whitespaces arethrown away in the lexing phase, but since we wantbound to $1, which is placed into the first field of

to keep layout information in CSTs, which are built

Factor0 by the associated Haskell action.

by the parser, the lexer should leave the separators

Generating printer.

plicit separators.)

intact and pass them to the parser. The specific

As mentioned in Section 4. 2, a printer generated

approach taken by BiYacc is wrapping a lexemeby BiYacc is supposed to traverse the CST andand the whitespaces following it into a single token

apply the encoded production rules to retrieve thatso that the CST still contains these whitespaces

piece of program text, which is rather simple andand a trivial printer can be constructed to natu-

straightforward. For example, the CST for Factor

rally transform the CST back to original programis flattened in the following way by defining the in-text. Beginning whitespaces are treated separately

stance of Show class in Haskell:from lexing and parsing, and are always preserved.
And in this prototype implementation, comments
are also considered as whitespaces.
Generating parser.

instance Show Factor whereshow (Factor0 s0 s1) = "-" ++ s0 ++ show s1show (Factor1 s0) = fst s0 ++ snd s0
show (Factor2 s0) = fst s0 ++ snd s0
show (Factor3 s0 s1 s2) = s0 ++ show s1 ++ s2
show (FactorNull2) = ""The concrete parser is used to generate a CSTfrom a list of tokens according to the production
rules in the grammar. Our parser is built using theparser generator Happy, which takes a BNF specification of a grammar and produces a Haskell
module containing a parser function. The grammar we feed into Happy is still essentially the one
specified in a BiYacc program, but in addition toparsing and constructing CSTs, the Happy actions
also transfer the whitespaces wrapped in tokens tocorresponding places in the CSTs. For example,
the production rules for Factor in the expression
example, as shown on the left below, are translated
to the Happy specification on the right:
Factor-> '-' Factor| Int| Name| '(' Expr ')';!

Factor
: token0 Factor{ Factor0 $1 $2 }| tokenInt{ Factor1 $1 }| tokenName{ Factor2 $1 }| token1 Expr token2{ Factor3 $1 $2 $3 }5 Case studies
The design of BiYacc may look simplistic andmake the reader wonder how much it can describe.
However, in this section we demonstrate with alarger case study that, without any extension, BiYacc can already handle real-world language features. Section 5. 1 gives a brief introduction to the
Tiger language, where we also make comparison
with the C programming language to show the complexity of Tiger. In the following sections, some
representative cases are presented to demonstrate
what BiYacc and reflective printing can achieve,
including preservation of syntactic sugar, constantpropagation, Pombrio and Krishnamurthi’s resugaring [25], and language evolution.
5. 1 The Tiger language
For this case study, we choose the Tiger language, which is a statically typed imperative lan-

We use the first expansion (token0 Factor) to ex-

guage first introduced in Appel’s textbook on com-plain how whitespaces are transferred: The gener-

piler construction [1]. Since Tiger’s purpose of

ated Happy token token0 matches a ‘-’ token pro-

design is pedagogical, it is not too complex and yet

duced by the lexer, and extracts the whitespaces

covers many important language features including

conditionals, loops, variable declarations and as-

Abstract

signments, and function definitions and calls. Someof these features can be seen in this Tiger program:function foo() =(for i := 0 to 10
do (print(if i < 5 then "smaller"else "bigger");
print("\n")))data TExp = TVarExp TVar | TString String| TInt Int | TSeqExp [TExp]| TLetExp [TDec] TExp | TNilExp| TIfExp TExp TExp (Maybe TExp)| TOpExp TExp TOper TExp
| ...
deriving (Show, Eq, Read)To give a sense of Tiger’s complexity, it takes an
LALR grammar with 81 production rules to specify Tiger’s syntax, while for C89 and C99 it takes
183 and 237 rules respectively (based on [17] andthe draft version of 1999 ISO C standard, excluding the preprocessing part). The diﬀerence is basically due to the fact that C has more primitive
types and various kinds of assignment statements.
Tiger is therefore a good case study with which we
can test the potential of our BX-based approach toconstructing parsers and reflective printers.
Excerpts of the abstract and concrete syntax ofTiger are respectively shown in Figure 7 and Figure 8 , where the usage of constructors can beguessed from its name easily. The abstract syntax is substantially the same as the original one
defined in Appel’s textbook (page 98); as for thedata TVar = TSimpleVar TSymbol| TFieldVar (TVar,TSymbol)| TSubscriptVar (TVar,TExp)
deriving (Eq,Show,Read)data TOper = TPlusOp | TMinusOp | . . .
| TEqOp | TNeqOp | . . .
deriving (Eq,Show,Read)data TDec = TVarDec TSymbol (Maybe TSymbol) TExp
| TTypeDec TTyDec| TFunctionDec TFundec
deriving (Eq,Show,Read)data TFundec =TFundec TSymbol [TFieldDec] (Maybe TSymbol) TExp
deriving (Eq,Show,Read)
type TSymbol = String...
ਤ7

An excerpt of Tiger’s abstract syntax

concrete syntax, Appel does not specify the wholecurrent syntax; finally, to circumvent the “dangling

grammar in detail, so we use a version slightly

else” problem, a terminal “end” is added to markadapted from Hirzel and Rose’s lecture notes [13].

the end of an if-then expression. One remark is

Some changes are made to handle features that arethat the language shown in Figure 3 is a subset

not supported by current BiYacc: For example, toof Tiger and is reused for building this example

make the grammar become unambiguous without

except for some changes on names of constructors

disambiguation rules, the operators are divided intoand production rules, which means that BiYacc

several groups, with the highest-precedence terms

programs can be developed in an incremental way.

(like literals) placed in the last group, just like what

We have tested our BiYacc program for Tiger

we did in the arithmetic expression example (Figure3); the AST constructors TFunctionDec or TTypeDecon all the sample programs provided on the homepage of Appel’s book†4 , including a merge sort im-

take a single function or type declaration instead

plementation and an eight-queen solver, and there

of a list of adjacent declarations (for representing

is no problem parsing and printing them.

mutual recursion) as in Appel’s book, since we can-complete BiYacc program for Tiger can be foundThe

not handle the synchronisation between a list oflists (in ASTs) and a list (in CSTs) with BiYacc’s†4 https://www.cs.princeton.edu/∼appel/modern/testcases/

BiYacc are:Concrete
Exp -> 'break' | LetExp | ArrExp | Assignment| ForExp | RecExp | IfThen | PrimitiveOpt| IfThenElse | WhileExp ;VarDec -> 'var' Name':=' Exp| 'var' Name ':' Name ':=' Exp ;LValue-> Name | OtherLValue ;OtherLValue -> Name '[' Exp ']'| OtherLValue '[' Exp ']' | LValue '.' Name;

TExp +> PrimitiveOpt
TIf e1 (TInt 1) (Just e2) +>(e1 +> PrimOpt) '|' (e2 +> PrimOpt1) ;t+> (t +> PrimOpt1) ;TExp +> PrimitiveOpt1
TIf e1 e2 (Just (TInt 0)) +>(e1 +> PrimOpt1) '&' (e2 +> PrimOpt2) ;t+> (t +> PrimOpt2) ;The parse function for these syntactic sugar is notinjective, since the alternative syntax and the fea-

SeqExp -> '(' ')' | '(' ExpSeq ')' ;ExpSeq -> Exp| Exp ';' ExpSeq ;tures being desugared into are both mapped toPrimitiveOpt

only the AST as input — cannot reliably determine-> PrimitiveOpt '|' PrimitiveOpt1| PrimitiveOpt1 ;...
PrimitiveOpt3 -> PrimitiveOpt3 '+' PrimitiveOpt4| . . . | PrimitiveOpt4 ;PrimitiveOpt5 -> 'nil' | Int| String| LValue | SeqExp | CallExp| '-' PrimitiveOpt5 ;IfThen-> 'if' Exp 'then' Exp 'end' ;IfThenElse -> 'if' Exp 'then' Exp 'else' Exp ;...
ਤ8

An excerpt of Tiger’s concrete syntax

at http://www.prg.nii.ac.jp/project/biyacc.html. In
the following sections, we will highlight some nontrivial printing strategies used in that program todemonstrate what BiYacc, in particular reflective
printing, can achieve.
5. 2 Syntactic sugar
Syntactic sugar, which lets the programmer use
some features in an alternative (perhaps conceptually higher-level) syntax, is pervasive in programming languages. For instance, Tiger representsboolean values false and true respectively as zeroand nonzero integers, and the logical operators& (“and”) and | (“or”) are converted to if ex-pressions in the abstract syntax: e1 & e2 is desugared and parsed to TIf e1 e2 (TInt 0) and e1 | e2 to
TIf e1 (TInt 1) e2. The printing actions for them inthe latter. A conventional printer — which takes
whether an abstract expression should be ensugared or not, whereas a reflective printer can makethe decision by inspecting the CST.
5. 3 Constant propagation
Constant propagation is an important compiler
optimisation that substitutes the values of known
constants in expressions at compile time rather
than at runtime. We use the example below ofsolving the eight-queen problem to show that BiYacc enables the observation of constant propagation performed on AST from program text.
Suppose the code snippet is:
let var N := 8type intArray = array of int
var row:= intArray [ N ] of 0...
function try(c:int)= (...)
in try(0)endwhere the variable N denotes the size of the problem. Since the length of the arrays only depends onthe variable N, it can be evaluated and optimised atcompile time. The right hand side of the variabledeclaration at line 3 is parsed to:TArrayExp "intArray" (TVarExp (TSimpleVar "N"))(TInt 0)After constant propagation, it is optimised to:TArrayExp "intArray" (TInt 8) (TInt 0)

Now we reflect the change back to program text
using BiYacc by simply performing printing. The
result is:
let var N := 8type intArray = array of int
var row:= intArray [ 8 ] of 0...
function try(c:int)= (...)
in try(0)endevaluation sequence on the source:
˜1 | ˜0→0 | ˜0

→

˜0

→

1

Due to the PutGet property, parsing these concrete terms will yield the corresponding abstract
terms in the first evaluation sequence, and this isexactly Pombrio and Krishnamurthi’ “emulation”
property, which they have to prove for their system; for BiYacc, however, the emulation property

Since the change is precisely located in the rightholds by construction, since BiYacc’s semantics ishand side of the variable declaration at line 3, otherdefined in terms of BiGUL, whose programs areparts of the program including layouts remain in-always well-behaved. Also diﬀerent from their ap-

tact.

proach is that we do not need to insert any additional information into the ASTs for remembering

5. 4 Resugaring

the form of the original sources. The advantage of

The idea of resugaring [25] is to print evaluation

our approach is that we can keep the abstract syn-sequences in a core language in terms of a surface

tax pure, so that other tools — the evaluator insyntax. Here we show that, without any exten-

particular — can process the abstract syntax with-sion, BiYacc is already capable of reflecting to theout being modified, whereas in their approach, theconcrete syntax some of the AST changes resulting

evaluator has to be adapted to work on the enrichedfrom evaluation, subsuming a part of Pombrio andabstract syntax.

Krishnamurthi’s work [25].

Also note that the above resugaring for Tiger

We borrow Pombrio and Krishnamurthi’s exam-is achieved for free — the programmer does notple of resugaring evaluation sequences for the logi-

need to write additional, special actions to achieve

cal operators “or” and “not”, but recast the exam-that. In general, BiYacc can easily and reliably

ple in Tiger. The “or” operator has been definedreflect AST changes that involve only “simplifica-

as syntactic sugar in Section 5. 2. For the “not” op-tion”, i.e., replacing part of an AST with a sim-

erator, which Tiger lacks, we introduce ‘˜’, repre-

pler tree, so it should not be surprising that Bi-

sented by TNot in the abstract syntax. Now consider

Yacc can also reflect simplification-like optimisa-

the source expression

tions such as constant propagation (we have men-

˜1 | ˜0which is parsed to
TIf (TNot (TInt 1)) (TInt 1) (Just (TNot (TInt 0)))tioned) and dead code elimination, and some refactoring transformations such as variable renaming.
All these can be achieved by one “general-purpose”

A typical call-by-value evaluator will produce the

BiYacc program, which does not need to be tai-following evaluation sequence given the above AST:

lored for each application.

TIf (TNot (TInt 1)) (TInt 1) (Just (TNot (TInt 0)))
→ TIf (TInt 0) (TInt 1) (Just (TNot (TInt 0)))5. 5 Language evolution→ TNot (TInt 0)
We conclude this section by looking at a prac→ TInt 1

If we perform reflective printing after every evalu-

tical scenario in language evolution, incorporating

ation step using BiYacc, we will get the following

all the applications we introduced in this section.
When a language evolves, some new features ofthe language (e.g., foreach loops in Java 5) can befact fairly straightforward:

implemented by desugaring to some existing fea-

type Tiger +> Guard handles the enclosing guard–tures (e.g., ordinary for loops), so that the com-

end pairs, distinguishes between single- and multi-

piler does not need to be extended to handle thebranch cases, and delegates the latter case to the

new features. As a consequence, all the engineer-

second group, which prints a list of branches recur-

ing work about refactoring or optimising transfor-

sively.

mations that has been developed for the abstract
syntax remains valid.

The first group ofThis is all we have to do — the corresponding
parser is automatically derived and guaranteed toConsider a kind of “generalised-if” expression al-

be consistent. Now guard expressions are desugared

lowing more than two cases, resembling the alterna-

to nested if expressions in parsing and preserved

tive construct in Dijkstra’s guarded command lan-in printing, and we can also resugar evaluation se-

guage [8]. We extend Tiger’s concrete syntax with

quences on the ASTs to program text. For instance,

the following production rules:

the following guard expression

Exp-> . . . | Guard | . . . ;Guard -> 'guard' CaseBs 'end' ;CaseBs -> CaseB CaseBs | CaseB ;CaseB -> LValue '=' Int '->' Exp ;For simplicity, we restrict the predicate produced
by CaseB to the form LValue '=' Int, but in general this can be any expression computing an integer. The reflective printing actions for this new
construct can still be written within BiYacc, but
require much deeper pattern matching:guard choice = 1 -> 4choice = 2 -> 8
choice = 3 -> 16

end

is parsed to
TIf (TEq (TName "choice") (TInt 1)) (TInt 4)(TIf (TEq (TName "choice") (TInt 2)) (TInt 8)(TIf (TEq (TName "choice") (TInt 3)) (TInt 16)
TSeqNil))

Suppose that the value of the variable choice is 2.
The evaluation sequence on the the AST will thenbe:TExp +> Guard
TIf (TOp (TVar (TSV "choice"))
TIf (TOp (TVar lv) TEqOp (TInt i)) e1 Nothing
TEqOp (TInt 1)) (TInt 4)+> 'guard' (CaseBs -> (CaseB ->(Just (TIf (TOp (TVar (TSV "choice"))(lv +> LValue) '=' (i +> Int) '->' (e1 +> Exp))
TEqOp (TInt 2)) (TInt 8)) 'end';(Just (TIf (TOp (TVar (TSV "choice"))
TIf (TOp (TVar lv) TEqOp (TInt i)) e1
TEqOp (TInt 3)) (TInt 16)(Just if2@(TIf _ _ _))Nothing))))+> 'guard' (CaseBs -> (CaseB ->→ TIf (TInt 0) (TInt 4)(lv +> LValue) '=' (i +> Int) '->' (e1 +> Exp))(Just (TIf (TOp (TVar (TSV "choice"))(if2 +> CaseBs)
TEqOp (TInt 2)) (TInt 8)) 'end';(Just (TIf (TOp (TVar (TSV "choice"))
TEqOp (TInt 3)) (TInt 16)
TExp +> CaseBs
Nothing))))TIf (TOp (TVar lv) TEqOp (TInt i)) e1 Nothing→ TIf (TOp (TVar (TSV "choice"))+> (CaseB ->TEqOp (TInt 2)) (TInt 8)(lv +> LValue) '='(Just (TIf (TOp (TVar (TSV "choice"))(i +> Int) '->' (e1 +> Exp));
TEqOp (TInt 3)) (TInt 16)
TIf (TOp (TVar lv) TEqOp (TInt i)) e1
Nothing))(Just if2@(TIf _ _ _))→ TIf (TInt 1) (TInt 8)+> (CaseB ->(Just (TIf (TOp (TVar (TSV "choice"))(lv +> LValue) '='TEqOp (TInt 3)) (TInt 16)(i +> Int) '->' (e1 +> Exp))
Nothing))(if2 +> CaseBs);→ TInt 8

Though complex, these printing actions are in

And the reflected evaluation sequence on the con-• concrete parsers and printers between program

crete expression will be:
guard

̸→
→ guardchoice = 1 -> 4choice = 2 -> 8
choice = 3 -> 16

text and CSTs are automatically derived (Sec-endtion 4. 3), so BiYacc synchronises program text
and ASTs, not just CSTs and ASTs as with the

choice = 2 -> 8
choice = 3 -> 16 end̸→→ 8Reflective printing fails for the first and third steps,
but this behaviour in fact conforms to Pombrio andKrishnamurthi’s “abstraction” property [25], which

previous version;• we present many nontrivial applications such as
resugaring and language evolution (Section 5);• our current system tries to preserve layouts andcomments in a transparent manner.

Unifying parsing and printing.

demands that core evaluation steps that make sense

Much research has been devoted to describing

only in the core language must not be reflected toparsers and printers in a single program. For exam-

the surface. In our example, the first and thirdple, both Rendel and Ostermann [26] and Matsuda

steps in the TIf-sequence evaluate the condition toand Wang [21] adopt a combinator-based approach,a constant, but conditions in guard expressions arewhere small components describing both parsing

restricted to a specific form and cannot be a con-and printing are glued together to yield more so-stant; evaluation of guard expressions thus has tophisticated behaviour, and can guarantee inverse

proceed in bigger steps, throwing away or goingproperties similar to (3) and (4) by construction

into a branch in each step, which corresponds to(with CST replaced by AST in the equations). By

two steps for TIf.

specialising one of the syntax to be XML syntax,

The reader may have noticed that, after the guard

Brabrand et al. [4] present a tool XSugar that han-expression is reduced to two branches, the layout

dles bijection between the XML syntax and anyof the second branch is disrupted; this is because

other syntax for a grammar, guaranteeing that thethe second branch is in fact printed from scratch.

transformation is reversible. However, the essen-This problem is discussed in Section 7. 2.

tial factor that distinguishes our system from others is that BiYacc is designed to perform synchro-

6 Related work
Comparison with our earlier prototype.

nisation while others are all targeted at handlingtransformations.

This paper is primarily based on and significantly

Just like BiYacc, all of the systems described

extends our previous tool demonstration paper [29],above handle pure unambiguous grammars with-which conducts an early experiment with the idea

out disambiguation declarations only. When theof casting parsing and reflective printing in theuser-defined grammar (or the derived grammar) isframework of bidirectional transformations. Com-

ambiguous, the behaviour of these systems is as

pared to our previous prototype, the current systemfollows: Neither of Rendel and Ostermann’s sys-

has the following improvements:tem (called “invertible syntax descriptions”, which• The well-behavedness of the underlying bidirec-

we shorten to ISDs henceforth) and Matsuda andtional language BiGUL (Section 3) we use in thisWang’s system (called FliPpr) will notify the user

version is formally verified [18], so we can guar-that the (derived) grammar is ambiguous.

antee the well-behavedness of BiYacc programs

ISDs, property (4) will fail, while for FliPpr bothmuch more confidently;

properties (3) and (4) will fail. (Since the discus-Forsion on ambiguous grammars has not been pre-priority integer i, corresponding to the hierarchi-

sented in their papers, we try the examples pro-

cal grammar structure. In other words, there is no

vided by their libraries and find these problems.)

need to specify the concrete grammar, which is al-

In contrast, Brabrand et al.

[4] give a detailed

ready implicitly embedded in the printer program.

discussion about ambiguity detection, and XSugar

This makes FliPpr programs neat and concise. Fol-can statically check that the transformations arelowing this approach, BiYacc programs can also bereversible. If any ambiguity in the program is de-made more concise: In a BiYacc program, the user

tected, XSugar will notify the user of the precise

is allowed to omit the production rules in the con-location where ambiguity arises. In BiYacc, thecrete syntax part, and they will be automaticallyambiguity analysis is performed by the parser gen-generated by extracting the terminals and nonter-erator employed in the system, and the result is re-minals in the right-hand sides of all actions. How-ported at compile time. If no warning is reported,

ever, if these production rules are supplied, BiYacc

the well-behavedness is always guaranteed, as ex-

will perform some sanity checks: It will make sureplained in Section 4. 2.

that, in an action group, the user has covered all of

Even though all these systems handle unambigu-

the production rules of the nonterminal appearingous grammar only, there are design diﬀerences be-in the “type declaration”, and never uses undefined

tween them. An ISD is more like a parser, while

production rules.

FliPpr lets the user describe a printer: To handle

Bidirectional transformations (BXs).

operator priorities, for example, the user of ISDs

Our work is theoretically based on bidirectional

will assign priorities to diﬀerent operators, consumetransformations [11] [5] [15], particularly taking in-parentheses, and use combinators such as chainl tospiration from the recent progress on putback-handle left recursion in parsing, while the user ofbased bidirectional programming [23] [24] [14] [10]FliPpr will produce necessary parentheses accord-[18]. As explained in Section 3, the purpose of bidi-

ing to the operator priorities. In BiYacc, the user

rectional programming is to relieve the burden of

defines the concrete syntax that has a hierarchicalthinking bidirectionally — the programmer writes

structure (Expr, Term, and Factor) to express oper-

a program in only one direction, and a program inator priority, and write printing strategies to pro-the other direction is derived automatically. We

duce (preserve) necessary parentheses. The user ofcall a language get-based when programs written in

XSugar will also likely need to use such a hierar-

the language denote get functions, and call a lan-chical structure.

guage putback-based when its programs denote put

It is interesting to note that, the part producing

functions. In the context of parsing and reflect-parentheses in FliPpr essentially corresponds to theing printing, the get-based approach lets the pro-hierarchical structure of grammars. For example,

grammer describe a parser, whereas the putback-to handle arithmetic expressions in FliPpr, we canbased approach lets the programmer describe awrite:

printer. Below we discuss in more depth how the

ppr' i (Minus x y) =parensIf (i >= 6) $ group $ppr 5 x <> nest 2(line' <> text "-" <> space' <> ppr 6 y);

FliPpr will automatically expand the definition andderive a group of ppr_i functions indexed by theputback-based methodology aﬀects BiYacc’s design by comparing BiYacc with a closely related,
get-based system.

Get-based vs putback-based.
Martins et al. [20] introduces an attribute

scratch as a & b or if a then b else 0 by suitablyordering the actions.

grammar–based BX system for defining transfor-

This diﬀerence is somewhat subtle, and one

mations between two representations of languages

might argue that Martins et al.’s design simply(two grammars). The utilisation is similar to Bi-

went one step too far — if their system had been

Yacc: The programmer defines both grammars

designed to respect the rule ordering as specified by

and a set of rules specifying a forward transfor-the user, as opposed to always choosing the mostmation (i.e., get), with a backward transformation

specialised rule, the system would have given its(i.e., put) being automatically generated. For ex-

user the same flexibility as BiYacc. Interestingly,

ample, the BiYacc actions in lines 32–34 of Figure

whether to let user-specified rule/action ordering

3 can be expressed in Martins et al.’s system asaﬀect the system’s behaviour is, in this case, ex-

get AE (add (l, ‘+’, r)) → plus

(get AE (l), get AT (r))

actly the line between get-based and putback-based

get AE (sub (l, ‘-’, r)) → minus(get AE (l), get AT (r))

design. The user of Martins et al.’s system writes→ get AT (t)rules to specify a forward transformation, whose

which describes how to convert certain forms of

semantics is the same regardless of how the rules

CSTs to corresponding ASTs. The similarity is ev-

are ordered, and thus it would be unpleasantly sur-

ident, and raises the question as to how get-based

prising if the rule ordering turned out to aﬀect theand putback-based approaches diﬀer in the context

system’s behaviour. We can view this from anotherof parsing and reflective printing.

angle: If the user is required to specify a forward

get AE (et(t))

The diﬀerence lies in the fact that, with a get-transformation while customising the backward be-

based system, certain decisions on the backward

haviour by carefully ordering the rules, then thetransformation are, by design, permanently en-

purpose of a bidirectionalisation system — whichcoded in the bidirectionalisation system and can-is to reduce the problem of writing bidirectional

not be controlled by the user, whereas a putback-transformations to unidirectional programming —based system can give the user fuller control. For

is largely defeated. By contrast, the user of Bi-

example, when no source is given and more thanYacc only needs to think in one direction about

one rules can be applied, Martins et al.’s sys-

the printing behaviour, for which it is natural totem chooses, by design, the one that creates theconsider how the actions should be ordered whenmost specialised version.

This might or might

an AST has many corresponding CSTs; the parsing

not be ideal for the user of the system. For ex-

behaviour will then be automatically and uniquely

ample: Suppose that we port to Martins et al.’s

determined. In short, relevance of action order-

system the BiYacc action that relates Tiger’s

ing is incompatible with get-based design, but isconcrete ‘&’ operator with a specialised abstracta natural consequence of putback-based thinking.

if expression in 5. 2, coexisting with a more gen-

Of course, it would be rather disappointing if alleral rule that maps a concrete if expression to

we can gain from adopting the putback-based ap-

an abstract if expression. Then printing the AST

proach was just the ability to customise the be-

TIf (TName "a") (TName "b") 0 from scratch will andhaviour of printing from scratch. We will make an-

can only produce a & b, as dictated by the system’sother case for putback-based thinking by sketchinghard-wired printing logic. By contrast, the user of

one potential extension to BiYacc in Section 7. 2.

BiYacc can easily choose to print the AST fromorder of association is respectively left-associative,

7 Conslusion and future work

right-associative, or non-associative. And the or-

In this paper, we have presented the design andder of these declarations specify the precedence

implementation of BiYacc, with which the pro-of these operators, with later declarations having

grammer can describe both a parser and a reflec-

higher precedence. It is therefore desirable to ex-tive printer for an unambiguous context-free gram-tend BiYacc to incorporate such use.

mar in a single program. Our solution is enriched

However, to use ambiguous grammars, we haveby it’s background of a putback-based bidirectional

to rethink about how to guarantee the inverse prop-transformation framework which allows the guaran-erties since the analysis in Section 4. 2 is no longer

tee of partial version of the consistency properties

applicable. Let us revisit the arithmetic expression(1) and (2) by construction. This system can sup-example in Figure 3, and define the concrete syntax

port various tasks of language engineering, fromwith additional disambiguation rules:

traditional constructions of basic machinery such%left '+' '-';
%left '*' '/';
Expr -> Expr '+' Expr | Expr '-' Expr
| Expr '*' Expr | Expr '/' Expr
| Name | Int | '(' Expr ')'| '-' Expr;

as printers and parsers to more complex tasks suchas Pombrio and Krishnamurthi’s “resugaring”, language evolution and refactorings.
We end this paper by presenting some inspiring
future work. In Section 7. 1, we analyse the toughproblem caused by incorporating disambiguation
declarations such as precedences and order of association commonly found in parser generators suchas Yacc and Happy.

In Section 7. 2 we show

the problem of naively matching-by-position strategy, and propose a new global matching strategy
that can be achieved by carefully design adaptation branches, which require a new surface syntax
to support however.
7. 1 Handling ambiguous grammars
As explained in Section 4. 2, we assume the grammars given to BiYacc are unambiguous in order toguarantee the inverse properties for concrete parsing and printing. In many scenarios, however, it
is more convenient for the user to use an initiallyambiguous grammar with additional disambiguation rules such as declarations of precedence andorder of association. For instance, the declarations
starting from %left, %right, and %nonassoc can becommonly found in parser generators such as Yacc
and Happy, meaning that the following terminals’

For the concrete parser, a natural choice is to
use the one generated by Happy from this grammar; this concrete parser will always construct valid
CSTs, i.e., those CSTs that respect the precedence
and order-of-association declarations. But then, forthe printing direction, we can no longer use theprimitive printer that strictly follows the production rules, since the inverse property (4) will be
invalidated: If we print an invalid CST to a pieceof program text and then parse the text, the resulting CST is necessarily valid and cannot be the one
we started with.
One way out might be to restrict the domainof the primitive printer to accept only valid CSTs
(and revise (4) to take additional partiality into
account), but this can make it hard to arrive atcorrectly behaving actions. For example, supposethat we have the program text x*2/5, and optimise
the “x*2” part in the corresponding AST to “x+x”,
as shown on the left side below:

Div
Mul
Var x

Div

Var x

Expr

Num 2

Add

TExpSeq

ExpSeq0

Num 5

Num 5

k := 2(dead code)

Expr ’/’ Expr
Expr ’+’ Expr

Int

Name

Name

"5"

"x"

"x"

Var x

ExpSeq0inc(x)ExpSeq0

k := x + 5

TExpSeqinc(x)

k := x + 5

ExpSeq0

IfThen0Concrete Syntax Tree (Simplified)

TExpSeq
TExpSeq

TIf
...

...

...

Updated Abstract Syntax Tree

If the actions are written naively, merely relating

What we want is removing the first concrete sub-corresponding AST and CST structures, then thetree, synchronising the second concrete subtree

updated AST will be printed by the BiGUL partwith the first abstract subtree, and so on, in orderto the invalid CST on the right above, which is

to keep as many original whitespaces as possible

rejected by the partial concrete printer, resulting(eg, the comment /* increment on x */). However,in an unexpected printing failure. We thus con-the BiYacc program synchronises the concrete andclude that for now there are complicated issues toabstract subtrees in order, and the subtrees are all

be tackled if ambiguous grammars are to be sup-mismatched, causing the concrete subtrees to beported and leave the work to the future.

printed from scratch and the original whitespaces
to be discarded. This scenario motivates us to ex-

7. 2 Global matching strategies

tend BiYacc with a mechanism
in which the user
1

In current BiYacc, the printing from an AST to

can write strategies that match subtrees of the samea CST is accomplished by recursively performing

structure in a more global manner.

pattern matching on both tree structures. This approach naturally comes with1the disadvantage that

more eﬀectively with the putback-based approach,the matching is mainly decided by the position ofsince matching strategies inherently belong to thenodes in the AST and CST. Consequently, a minor

putback direction.

structural change on the AST may completely dis-strategies such as based on the longest common

rupt the matching between the AST and the CST,

subsequence of two expression sequences, or based

and this may not be desirable.

on tree edit distance [2] can be hand-coded inThis matching problem is one that can be solved

Indeed, the global matching

A typical scenario where the matching of a CSTBiGUL, however, it is still a challenge to design

and an AST can be easily disrupted is the synchro-proper surface syntax in BiYacc for the user tonisation of two expression sequences. Consider thewrite their own global matching strategies.

following example in Tiger:( k := 2; /* dead code */inc(x); /* increment on x */k := x + 5;
if k then . . . ;...
)Acknoledgement This work was partially supported by the Japan Society for the Promotionof Science (JSPS) Grant-in-Aid for Scientific Research (A) No. 25240009.ɽ
ࢀ ߟ จ ‫ݙ‬Suppose that the AST is optimised by removing thedead expression k := 2. Then the CST and updated
AST become:[ 1 ] Appel, A. W.: Modern Compiler Implementation in ML, Cambridge University Press, 1998.
[ 2 ] Bille, P.: A survey on tree edit distance andrelated problems, Theoretical Computer Science,Vol. 337, No. 1(2005), pp. 217–239.
[ 3 ] Boulton, R.: Syn: A single language for specifying abstract syntax trees, lexical analysis, parsing and pretty-printing, Technical Report Number 390, Computer Laboratory, University of Cambridge, 1966.
[ 4 ] Brabrand, C., Møller, A., and Schwartzbach,M. I.: Dual syntax for XML languages, Information Systems, Vol. 33, No. 4(2008), pp. 385–406.
[ 5 ] Czarnecki, K., Foster, J. N., Hu, Z., Lämmel,
R., Schürr, A., and Terwilliger, J.: Bidirectional
Transformations: A Cross-Discipline Perspective,
International Conference on Model Transformation, Lecture Notes in Computer Science, Vol. 5563,
Springer, 2009, pp. 260–283.
[ 6 ] de Jonge, M. and Visser, E.: An Algorithm
for Layout Preservation in Refactoring Transformations, International Conference on Software Language Engineering, Lecture Notes in Computer Science, Vol. 6940, Springer, 2012, pp. 40–59.
[ 7 ] De Jonge, M.: Pretty-printing for software
reengineering, International Conference on Software Maintenance, IEEE, 2002, pp. 550–559.
[ 8 ] Dijkstra, E. W.: Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, Vol. 18, No. 8(1975), pp. 453–
457.
[ 9 ] Duregård, J. and Jansson, P.: Embedded
Parser Generators, Haskell Symposium, ACM, 2011,
pp. 107–117.
[10] Fischer, S., Hu, Z., and Pacheco, H.: The essenceof bidirectional programming, Science China Information Sciences, Vol. 58, No. 5(2015), pp. 1–21.
[11] Foster, J. N., Greenwald, M. B., Moore, J. T.,
Pierce, B. C., and Schmitt, A.: Combinators forbidirectional tree transformations: A linguistic approach to the view-update problem, ACM Transactions on Programming Languages and Systems,
Vol. 29, No. 3(2007), pp. 17.
[12] Foster, J. N.: Bidirectional programming languages, PhD Thesis, University of Pennsylvania,
2009.
[13] Hirzel, M. and Rose, K. H.: Tiger Language
Specification, https://cs.nyu.edu/courses/fall13/
CSCI-GA.2130-001/tiger-spec.pdf, 2013.
[14] Hu, Z., Pacheco, H., and Fischer, S.: Validity checking of putback transformations in bidirectional programming, International Symposium on
Formal Methods, Lecture Notes in Computer Science, Vol. 8442, Springer, 2014, pp. 1–15.
[15] Hu, Z., Schurr, A., Stevens, P., and Terwilliger,
J. F.: Dagstuhl seminar on bidirectional transformations (BX), ACM SIGMOD Record, Vol. 40,
No. 1(2011), pp. 35–39.

[16] Hunt, A. and Thomas, D.: The Pragmatic Programmer: From Journeyman to Master, AddisonWesley, 1999.
[17] Kernighan, B. W., Ritchie, D. M., and Ejeklint,
P.: The C programming language, Vol. 2, prenticeHall Englewood Cliﬀs, 1988.
[18] Ko, H.-S., Zan, T., and Hu, Z.: BiGUL: A
formally verified core language for putback-based
bidirectional programming, Partial Evaluation and
Program Manipulation, ACM, 2016, pp. 61–72.
[19] Kort, J. and Lämmel, R.: Parse-tree annotations
meet re-engineering concerns, International Workshop on Source Code Analysis and Manipulation,
IEEE, 2003, pp. 161–170.
[20] Martins, P., Saraiva, J., Fernandes, J. P., and
Van Wyk, E.: Generating attribute grammarbased bidirectional transformations from rewrite
rules, Partial Evaluation and Program Manipulation, ACM, 2014, pp. 63–70.
[21] Matsuda, K. and Wang, M.: FliPpr: A Prettier Invertible Printing System, European Symposium on Programming, Lecture Notes in Computer
Science, Vol. 7792, Springer, 2013, pp. 101–120.
[22] Norell, U.: Towards a practical programming
language based on dependent type theory, PhD Thesis, Chalmers University of Technology, 2007.
[23] Pacheco, H., Hu, Z., and Fischer, S.: Monadic
combinators for Putback style bidirectional programming, Partial Evaluation and Program Manipulation, ACM, 2014, pp. 39–50.
[24] Pacheco, H., Zan, T., and Hu, Z.: BiFluX:A Bidirectional Functional Update Language for
XML, Principles and Practice of Declarative Programming, ACM, 2014, pp. 147–158.
[25] Pombrio, J. and Krishnamurthi, S.: Resugaring: Lifting evaluation sequences through syntactic
sugar, Programming Language Design and Implementation, Vol. 49(2014), pp. 361–371.
[26] Rendel, T. and Ostermann, K.: Invertible syntax descriptions: Unifying parsing and pretty printing, Haskell Symposium, ACM, 2010, pp. 1–12.
[27] Sheard, T. and Jones, S. P.: Template metaprogramming for Haskell, Haskell Workshop, ACM,
2002, pp. 1–16.
[28] Visser, E.: Syntax Definition for Language Prototyping, PhD Thesis, University of Amsterdam,
1997.
[29] Zhu, Z., Ko, H.-S., Martins, P., Saraiva, J., andHu, Z.: BiYacc: Roll your parser and reflective
printer into one, Proceedings of the 4th International Workshop on Bidirectional Transformations
co-located with Software Technologies: Applications
and Foundations, STAF, CEUR-WS, 2015, pp. 43–50.