2015 30th IEEE/ACM International Conference on Automated Software Engineering

Learning to Generate Pseudo-code from Source
Code using Statistical Machine Translation
Yusuke Oda, Hiroyuki Fudaba, Graham Neubig, Hideaki Hata,
Sakriani Sakti, Tomoki Toda, and Satoshi Nakamura
Graduate School of Information Science, Nara Institute of Science and Technology
8916-5 Takayama, Ikoma, Nara 630-0192, Japan{oda.yusuke.on9, fudaba.hiroyuki.ev6, neubig, hata, ssakti, tomoki, s-nakamura}@is.naist.jp
Abstract—Pseudo-code written in natural language can aid
the comprehension of source code in unfamiliar programming
languages. However, the great majority of source code has nocorresponding pseudo-code, because pseudo-code is redundantand laborious to create. If pseudo-code could be generated
automatically and instantly from given source code, we could
allow for on-demand production of pseudo-code without humaneffort. In this paper, we propose a method to automaticallygenerate pseudo-code from source code, speciﬁcally adopting thestatistical machine translation (SMT) framework. SMT, which
was originally designed to translate between two natural languages, allows us to automatically learn the relationship between
source code/pseudo-code pairs, making it possible to create a
pseudo-code generator with less human effort. In experiments,
we generated English or Japanese pseudo-code from Python
statements using SMT, and ﬁnd that the generated pseudo-codeis largely accurate, and aids code understanding.

comprehension of beginners because it explicitly describes
what the program is doing, but is more readable than an
unfamiliar programming language.
Fig. 1 shows an example of Python source code, and English pseudo-code that describes each corresponding statementin the source code.1 If the reader is a beginner at Python(or a beginner at programming itself), the left side of Fig.
1 may be difﬁcult to understand. On the other hand, theright side of the ﬁgure can be easily understood by mostEnglish speakers, and we can also learn how to write speciﬁc
operations in Python (e.g. if we want to check if the type ofthe variable is not an integer, we can see that we write “if
not isinstance(something, int):”). In other words,
pseudo-code aids the “bottom-up comprehension” [3] of given
source code.

Keywords: Algorithms, Education, Statistical ApproachI.

However, in real programming environments, pseudo-code
corresponding to source code rarely exists, because pseudocode is not necessary once a programmer has a good graspof the programming language and project. In addition, indiscriminately inserting pseudo-code into existing source code
manually would impose a large burden on programmers. On
the other hand, if pseudo-code could be generated automatically, this burden could be reduced, and pseudo-code could
be created for actual programming projects. If we want topractically use automatically generated pseudo-code, we cansay that satisfying the following 4 points is required:

I NTRODUCTION

Understanding source code is an essential skill for all
programmers. This is true for programmers at all levels, as it isnecessary to read and understand code that others have written
to, for example, work efﬁciently in a group or to integrate andmodify open-source software. On a macro level, there are avariety of tools to aid engineers in comprehending the overall
structure of programming projects. For example, DeLine et al.
proposed a tool that allows programming experts to evaluate
large-scale cooperative software engineering projects [1]. Rahman et al. also proposed a system that recommends methods
for ﬁxing source code when it does not work as expected [2].

•pseudo-code is accurate enough to describe the behavior of the original source code,•

pseudo-code should be provided upon the readers’request,•pseudo-code should be automatically generated to
avoid the burden on programmers, and•the method to generate pseudo-code should be efﬁcient, to avoid making the readers wait.

On a more ﬁne-grained level, when we try to understand the
behavior of source code in detail, we usually need to read eachstatement in the source code carefully, and understand what
each statement does. Of course, thoroughly reading and understanding source code of existing software is possible (althoughtime consuming) for veteran programmers. In contrast, thisprocess is much more difﬁcult for beginner programmers or
programmers who are learning a new programming language.
Such inexperienced readers sometimes do not understand thegrammar and style of the source code at hand, so reading
source code written in such languages imposes a large burden.

In this study, we propose a method to automatically generate pseudo-code from source code. In particular, our proposed
method makes two major contributions:

On the other hand, in educational texts about programming
and algorithms, it is common to use “pseudo-code,” which
describes the behavior of statements in the program using
natural language (usually in English, or the programmers’
mother tongue) or mathematical expressions. Pseudo-code aids

1 While there are many varieties of pseudo-code, in this paper we assume
that pseudo-code is “line-to-line” translation between programming and natural
languages as shown by Fig. 1. This assumption clearly deﬁnes the relationshipbetween source code and pseudo-code and is a convenient ﬁrst step towards
applying machine translation to this task.

978-1-5090-0025-8/15 $31.00 © 2015 IEEE
DOI 10.1109/ASE.2015.36

574

Fig. 1.

Example of source code written in Python and corresponding pseudo-code written in English.

•

To our knowledge, this is the ﬁrst method for generating pseudo-code that completely describes thecorresponding source code. This should be contrasted
with previous work on comment generation, whichaims to help experienced engineers by reducing theamount of source code to be read, and is described in§II.

•

We propose a framework to perform pseudo-code
generation using statistical machine translation (SMT).
SMT is a technology that can automatically learn how
to translate between two languages, and was designed
for translating between natural languages, such as English and Japanese. Our proposed method of applying
this to pseudo-code generation has several beneﬁts,
the largest of which being that it is easy to extend thegenerator to other combinations of programming andnatural languages simply by preparing data similar tothat in Fig. 1.

and thus comments are expected to concisely summarize
what the code is doing, instead of covering each statement
in detail. From a technical point of view, however, pseudocode generation is similar to automatic comment generation
or automatic documentation as both generate natural language
descriptions from source code, so in this section we outline
the methods used in previous approaches and contrast them toour method.
There are two major paradigms for automatic comment generation: rule-based approaches, and data-based approaches. Regarding the former, for example, Sridhara et al.
perform summary comment generation for Java methods byanalyzing the actual method deﬁnition using manually deﬁned
heuristics [4], [5]. Buse et al. also proposed a method togenerate documents that include the speciﬁcation of exceptions
that could be thrown by a function and cases in which
exceptions occur [6]. Moreno et al. also developed a method togenerate summaries that aid understanding, especially focusing
on class deﬁnitions [7]. These rule-based approaches use
detailed information closely related to the structure of source
code, allowing for handling of complicated language-speciﬁc
structures, and are able to generate accurate comments when
their rules closely match the given data. However, if we need
new heuristics for a speciﬁc variety of source code or project,or to create a system for a new programming language or
natural language, the system creator must manually appendthese heuristics themselves. This causes a burden on the maintainers of comment generation systems, and is a fundamental
limitation of rule-based systems.

In this paper, we ﬁrst refer to related works on automaticcomment generation and clarify the differences and the meritsof our method (§II). Second, we describe the summary of two
SMT frameworks to be used in this study (§III). Next, we
explain how to apply the SMT framework to pseudo-code generation (§IV), how we gather source code/pseudo-code parallel
data to train our pseudo-code generation system (§V), and themethod to evaluate the generated pseudo-code using automaticand code understanding criteria (§VI). In experiments, weapply our pseudo-code generation system to the Python-toEnglish and Python-to-Japanese pseudo-code generation tasks,
and we ﬁnd that providing automatically generated pseudocode along with the original source code makes the codeeasier to understand for programming beginners (§VII). We
ﬁnally mention the conclusion and future directions, including
applications to other software engineering tasks (§VIII).2II.

On the other hand, in contrast to rule-based systems, databased approaches can be found in the comment generation orcode summarization ﬁelds. Wong et al. proposed a method
for automatic comment generation that extracts commentsfrom entries of programming question and answer sites using
information retrieval techniques [8]. There are also methods
to generate summaries for code based on automatic text
summarization [9] or topic modeling [10] techniques, possibly
in combination with the physical actions of expert engineers[11]. This sort of data-based approach has a major merit: if
we want to improve the accuracy of the system, we need
only increase the amount of “training data” used to construct
it. However, existing methods are largely based on retrieving
already existing comments, and thus also have signiﬁcantissues with “data sparseness;” if a comment describing theexisting code doesn’t already exist in the training data, there
is no way to generate accurate comments.

R ELATED W ORKS

There is a signiﬁcant amount of previous work on automatic comment and document generation. The importantdifference between our work and conventional studies is the
motivation. Previous works are normally based on the thoughtof “reducing” the amount of code to be read. This is a
plausible idea for veteran engineers, because their objective
is to understand a large amount of source code efﬁciently,
2 Datasets used to construct and evaluate our pseudo-code generators areavailable at http://ahclab.naist.jp/pseudogen/575

B. Phrase-based Machine Translation

SMT, which we describe in the next section, combines
the advantages of these approaches, allowing for detailed
generation of text, like the rule-based approaches, while being
learnable from data like the data-based approaches.
III.

One of the most popular SMT frameworks is phrasebased machine translation (PBMT) [15], which directly uses
the phrase-to-phrase relationships between source and target
language pairs. In software engineering studies, Karaivanov
et al. proposed a method applying the PBMT framework
to programming language conversion, which learns the relationships between parts of statements in two programming languages (e.g. “System.out.println” in Java to“Console.WriteLine” in C#) [16].

S TATISTICAL M ACHINE T RANSLATION

SMT is an application of natural language processing(NLP), which discovers the lexical or grammatical relationships between two natural languages (such as English andJapanese), and converts sentences described in a natural language into another natural language. SMT algorithms used inrecent years are mainly based on two ideas:•

extract the relationships (usually called “rules”) between small fragments of new input and output languages, and•use these relationships to synthesize the translation
results of a new input sentence using statistical models
to decide which translation is best [12], [13], [14].

To describe PBMT modeling, we introduce
a set of phrasepairs φ = [φ1 , φ2 , · · · φ|φ| ]. Each φn = s(n) → t(n) represents the n-th subsequence of the source sentence s(n) andthe target subsequence t(n) associated with the corresponding
source subsequence. For example, in Fig. 2, s is separated into
|φ| = 4 phrases:
⎤
⎡

“if”
→
“if”

“x”
→
“x”
 ⎥
⎢ 
.
(2)
φ=⎣

“% 5”
→
“by 5” ⎦ “== 0 :” → “is divisible” 

SMT frameworks have quickly developed in recent years,
mainly because of the large amount of data available and theincrease in calculation power of computers. In this section, we
describe the foundations of the SMT framework. Especially,
we explain the details of the phrase-based machine translation (PBMT) and tree-to-string machine translation (T2SMT),
which are major SMT frameworks, used in this work to convert
source code into pseudo-code.

φ is generated using a “phrase table”, which contains various phrase-to-phrase relationships with probabilities, and is
extracted from a parallel corpus as explained in §III-D.
Given φ, we can generate the target sentence t fromthe source sentence by concatenating each t(n) . But simply
concatenating t(n) according to their order cannot obtain an
accurate target sentence, because the grammatical characteristics (e.g. ordering of tokens) of the source and target languages
are usually different. For example, if we concatenate the target
side phrases of Equation (2), we obtain the target sentence “ifx by 5 is divisible,” which is not a ﬂuent English sentence.

A. Overview of Statistical Machine Translation
At ﬁrst, we introduce some notation for the formulation of
SMT-based pseudo-code generation. Let s = [s1 , s2 , · · · , s|s| ]describe the “source sentence,” an array of input tokens, andt = [t1 , t2 , · · · , t|t| ] describe the “target sentence,” an arrayof output tokens. The notation | · | represents the length ofa sequence. In this paper, we are considering source code
to pseudo-code translation, so s represents the tokens in the
input source code statements and t represents the words ofa pseudo-code sentence. For example, in the small Python to
English example in Fig. 2, s is described as the sequence of
Python tokens [“if”, “x”, “%”, “5”, “==”, “0”, “:”], and t
is described as [“if”, “x”, “is”, “divisible”, “by”, “5”], with|s| = 7 and |t| = 6.

To avoid this problem, we need to perform “reordering,”
which chooses the proper order of phrases in the target
sentence. To express reordering, we introduce the phrasealignment a = [a1 , a2 , · · · , a|φ| ], where each an is an integerthat represents the order of the n-th phrase pair in the source
sentence. In Fig. 2, we assume that a = [1, 2, 4, 3], whichmeans that ﬁrst and second phrase pairs keep their own
positions, and the third and fourth phrase pairs are swapped
before the target sentence is generated.
Formally, the conditional probability Pr(t|s) of the PBMT
model is usually estimated using a log-linear model, thatcombines several probabilities calculated over the source andtarget sentences [17]:The objective of SMT is to generate the most probabletarget sentence t̂ given a source sentence s. Speciﬁcally, we doso by deﬁning a model specifying the conditional probability
distribution of t given s, or Pr(t|s), and ﬁnd the t̂ thatmaximizes this probability:t̂ ≡arg max Pr(t|s).

t̂

(1)

t

The difference of each SMT framework is guided by themethod for calculating Pr(t|s). This probability is estimatedusing a set of source/target sentence pairs called a “parallel
corpus.” For example, Fig. 1 is one example of the type ofparallel corpus targeted in this study, in which have one-byone correspondences between each line in the source code andpseudo-code.

≡arg max Pr(t|s)

arg max Pr(t, φ, a|s)arg max

=

(3)

t

(4)

t,φ,a

exp(wT f (t, φ, a, s))exp(wT f (t , φ, a, s))

t,φ,a
t
T

arg max w f (t, φ, a, s),

(5)
(6)

t,φ,a

where f (t, φ, a, s) represents feature functions calculated during the translation process, and w represents the weight vectorof the corresponding features, which deﬁnes the importance ofeach feature. Intuitively, Equation (6) means that the PBMT

576

T2SMT was originally conceived for translating natural
languages such as English, and because natural languages
include ambiguities we obtain the parse tree Ts using aprobabilistic parser that deﬁnes the probability Ts given s, or
Pr(Ts |s) [19], [20]. Thus, the formulation of T2SMT can beobtained by introducing this parsing probability into Equation(1):t̂

= arg max Pr(t|s)


(7)

t

arg max Pr(t|Ts ) Pr(Ts |s).

(8)

t,Ts

Fortunately, the probability Pr(Ts |s) can be ignored in our
proposed method for pseudo-code generation, because all practical programming languages have a compiler or interpreterthat can parse the corresponding source code deterministically,
and thus there is only one possible parse tree. So the formulation is less complex:t̂  arg max Pr(t|Ts ),(9)tFig. 2.

Fig. 3 shows the process of T2SMT-based pseudo-code
generation. First, we obtain the parse tree Ts by transforming
the input statement into a token array using tokenization, andparsing the token array into a parse tree using parsing. The
important point of Fig. 3 is that Ts is deﬁned by the grammarof the programming language, and is not an “abstract” syntax
tree. This requirement comes from the characteristics of theinner workings of the T2SMT algorithm, and this topic is
described in detail in §IV.

Example of Python to English PBMT pseudo-code generation.

model ﬁnds the sentence which has the highest “score” calculated by the weighted sum of the features: wT f (t, φ, a, s).
Some typical examples of these features include:•

Language model Pr(t) measures the ﬂuency of thesentence t under the target language as described in§III-E.

•

Phrase translation model calculates the productof the probabilities Pr(t(n) |s(n) ) of the individualphrases in the sentence.

•

The probability Pr(t|Ts ) is deﬁned similarly to that of
PBMT (usually formulated as a log-linear model) with two
major differences:•

In the T2SMT, we use the “derivation” d =[d1 , d2 , · · · , d|d| ] instead of the phrase pairs φ in(n)

PBMT. Each dn = Ts → t(n) represents therelationship between between a source subtree (thegray boxes in Fig. 3) and target phrase with wildcards. All derivations are connected according to thestructure of original parse tree Ts , and the target
sentence is generated by replacing wildcards with theircorresponding phrases.

Reordering model Pr(a|φ) calculates the probabilityof the arranging each phrase in a particular order.

While PBMT’s mechanism of translating and reordering
short phrases is simple, it also lacks the expressive power
to intuitively model pseudo-code generation. For example,
we intuitively know that the English string including two
wildcards “X is divisible by Y ” corresponds to the source code
“X % Y == 0:,” but PBMT is not capable of using thesewildcards. Thus, φ in the example in Fig. 2 uses obviously“wrong” correspondences such as “==0:” → “is divisible”.
In addition, source code has an inherent hierarchical structure
which can not be used by explicitly when only performing
phrase-to-phrase translation and reordering.

•

The T2SMT translation process does not include explicit reordering models because the ordering of thewildcards in the target phrase naturally deﬁnes thetarget ordering.

D. Extracting SMT Rules
To train the PBMT and T2SMT models, we have to extract
the translation rules, which deﬁne the relationship between theparts of the source and target language sentences, from thegiven parallel corpus. To do this, we use a “word alignment”
between both sentences. Word alignments represent the wordto-word level relationships between both languages, shownin Fig. 4. In standard SMT training, word aligments areautomatically calculated from the statistics of a parallel corpus
by using a probabilistic model and unsupervised machinelearning techniques [21], [22].

C. Tree-to-string Machine Translation
As we mentioned in the previous section, PBMT-based
pseudo-code generation cannot take advantage of wildcards
or the hierarchical correspondences between two languages.
T2SMT uses the parse tree of source sentence Ts instead of
the source tokens s to avoid this problem [18], as shown in
Fig. 3.

577

Fig. 3.

Fig. 4.

After obtaining the word alignment of each sentence inthe parallel corpus, we assume that the phrases that satisfy
the below conditions can be extracted as a phrase pair for the
PBMT framework:•

no words outside of the phrases are aligned to a wordin either phrase.

Fig. 6.

Extracting T2SMT translation rules according to word alignment.

Extracted PBMT and T2SMT rules are evaluated using
some measures and stored into the rule table for each framework along with these evaluation scores. These scores are used
to calculate feature functions that are used in the calculation ofprobabilities Pr(t|s) or Pr(t|Ts ). For example, the frequencyof the rule in the parallel corpus, length of the phrase, and thecomplexity of the subtree are often used as features.

Word alignment between two token strings.

some words in both phrases are aligned, andExtracting PBMT translation rules according to word alignment.

Fig. 6 shows an extraction of a translation rule corresponding
to the phrase with wildcards “X is divisible by Y ” bycombining minimal rules in the bold rectangle, with two rules
corresponding to “x” and “5” being replaced by wildcards
respectively.

Example of Python to English T2SMT pseudo-code generation.

•

Fig. 5.

E. Language Model
Another important feature function of SMT is the “language model,” which evaluates the ﬂuency of the sentence inthe target language. Given the target sentence t, the language
model is deﬁned as the product of probabilities of each word
in t given the previous words:

For example, Fig. 5 shows one phrase pair extraction φ =“== 0 :” → “is divisible”.

|t|

Pr(t) ≡In the case of the T2SMT framework, we use a method
known as the GHKM algorithm [23] to extract tree-to-stringtranslation rules. The GHKM algorithm ﬁrst splits the parsetree of the source sentence into several subtrees according
to alignments, and extracts the pairs of the subtree and its
corresponding words in the target sentence as “minimal rules.”Next, the algorithm combines some minimal rules according
to the original parse tree to generate larger rules. For example,

i=1
|t|

≡

Pr(ti |t1 , t2 , · · · , ti−1 )(10)Pr(ti |ti−1
1 ),

(11)

i=1

where the notation xji = [xi , xi+1 , · · · , xj ] represents thesubsequence of x containing the i-th to j-th elements. In
addition, to save memory and prevent data sparseness, most578

practical language models use “n-gram models:”i−1
Pr(ti |ti−11 )  Pr(ti |ti−n+1 ),(12)

where an n-gram is deﬁned as n consecutive words. Thisapproximation means that the next word ti is conditioned on
only on the previous (n−1) words. The simplest n-gram model
can be calculated simply from target language text using thecount of appearances of each n-gram:Pr(ti |ti−1
i−n+1 ) ≡count(tii−n+1 )count(ti−1i−n+1 )

Fig. 7.

(13)

where count(x) is the number of appearances of sequencex in the given corpus. For example, if the word (1-gram)“is” appears 10 times and the 2-gram “is divisible” appears
3 times in the same corpus, then we can estimate Pr(ti =“divisible”|ti−1 = “is”) = 3/10. In addition, we also use a further approximation method known as Kneser-Ney smoothing[24], which smooths probabilities for all n-grams, preventing
problems due to data sparsity, allowing us to calculate theprobability of any sentence accurately.

method such as the Stanford Tokenizer3 . If we aretargeting a language with no spaces (e.g. Japanese), wemust explicitly insert delimiters between each word in
the sentence. Fortunately, tokenizing natural language
is a well-developed area of NLP studies, so we canﬁnd tokenizers for major languages easily.

It should also be noted that n-gram models are easily
applied to any type of sequence data and frequently used forsoftware engineering, typically to measure the naturalness ofthe source code [25], [26] or distinguish the characteristics ofsource code [27], [28].
IV.

A PPLYING SMT TO P SEUDO - CODE G ENERATIONIn the previous section, we described two SMT frameworks: PBMT and T2SMT. The important advantage of using
these frameworks is that we need not describe new translation
rules explicitly when we update the pseudo-code generator,
because the SMT framework is a statistical approach and translation rules from programming language to natural language
can be automatically obtained from training data. This fact
greatly reduces the burden on engineers to create or maintain
pseudo-code generators. If we want to cover a new case in
our generator, we simply search for or create pseudo-code
corresponding to the desired statements, instead of creating
specialized rules for each new case. For example, if we wantto create a rule “if X is an even number” for the source code
“if X % 2 == 0:” instead of “if X is divisible by 2,”
we only need to append a sentence including this example
to our corpus, for example, “if something is an even number”
and “if something % 2 == 0:.” This work is obviously
easier than describing rules explicitly, as this sort of data canbe created by programmers even if they are not familiar with
our particular pseudo-code generating system, and could also
potentially be harvested from existing data.

••

Tokenizer of the source programming language.
Usually, we can obtain a concrete deﬁnition of the programming language from its grammar, and a tokenizer
module is often provided as a part of the standard
library of the language itself. For example, Python
provides tokenizing methods and symbol deﬁnitionsin the tokenize module.

•

Parser of the source programming language. Similarly to the tokenizer, a parser for the programming
language, which converts source code into a parsetree describing the structure of the code, is explicitly
deﬁned in the language’s grammar. Python also provides a way of performing abstract parsing in the ast
module. However, the output of this module cannot be
used directly, as described in the next section.

A. Surface Modiﬁcation of Abstract Syntax TreeAs with the Python library ast, parsing methods provided
by standard libraries of programming languages are often“abstract” parsers, which are deﬁned more by the executiontime semantics of the language than its written form. As
we mentioned in the previous section, the GHKM heuristics, which extract tree-to-string translation rules, use wordalignments, which are deﬁned over the leaves of the syntax
tree. Abstract syntax trees often use keywords and operators
existing in the source code as internal nodes rather than leaves,
but these surface words could be strongly related to speciﬁcwords in the target language (e.g. the token “if” in Python
corresponds to the word “if” in English).
Of course, we could always develop a new parser fromgrammar deﬁnitions for speciﬁc programming languages, but
this is not always easy (e.g. C++ grammar is deﬁned using
hundreds of pages in the ofﬁcial speciﬁcation document). In
this paper, we apply a more reasonable way to generate aparse-like tree from an abstract syntax tree using two processes
described below.

If we want to construct the SMT-based pseudo-code generator described in this paper for any programming language/natural language pair, we must prepare the following
data and tools.
•

The head insertion process.

Source code/pseudo-code parallel corpus to train the
SMT-based pseudo-code generator.

1) Head Insertion: First, we append a new edge called“HEAD” into the abstract syntax tree, which include the labelof inner nodes as their leaves. Fig. 7 shows an example ofTokenizer of the target natural language. If we consider a language that puts spaces between words (e.g.
English), we can use a simpler rule-based tokenization

3 http://nlp.stanford.edu/software/tokenizer.shtml

579

can use open-source tools to assist in constructing the system.
We use following tools in this study: MeCab to tokenize
Japanese sentences [29], pialign to train word alignments [22],KenLM to train Kneser-Ney smoothed language model [30],Moses to train and generate target sentences using the PBMT
model [31], and Travatar to train and generate target sentencesusing T2SMT models [32].
V.
Fig. 8.

Pruning and simpliﬁcation process.

G ATHERING A S OURCE C ODE TO P SEUDO - CODEPARALLEL C ORPUS

As we described in §III, we need a source code/pseudocode parallel corpus to train SMT-based pseudo-code generators. In this study, we created Python-to-English and Pythonto-Japanese parallel corpora by hiring programmers to add
pseudo-code to existing code.

the head insertion process for a tree generated from the sourcecode “if x % 5 == 0:” using the ast module in Python.
Applying this process, words that have disappeared in theprocess of making the abstract syntax tree such as “if” canbe treated as candidates for word alignment. This process is
simple and easy to be applied to abstract syntax trees of any
programming language if we can generate their trees using
an abstract parser. On the other hand, there is one optionof the head insertion process: where to position the HEAD
nodes in the tree. In this paper, we put all HEAD nodes at theleftmost child of the parent for English and rightmost child forJapanese, corresponding to the order of the head word in thetarget language.

For the Python-to-English corpus, we contracted one engineer to create pseudo-code for Django (a Web application
framework), and obtained a corpus containing 18,805 pairsof Python statements and corresponding English pseudo-code.
For Python-to-Japanese, we ﬁrst hired one engineer to create
Python code for solutions to problems from Project Euler4 .
a site with arithmetic problems designed for programming
practice. We obtained 722 Python statements, which include
177 function deﬁnitions related to solving arithmetic problems.
These are used to perform human evaluation experiments
described in §VI-B and §VI-C. This code is shown to anotherJapanese engineer, who created Japanese pseudo-code corresponding to each statement. It should be noted that in bothcases, this pseudo-code was created by a separate engineer
not involved with this work, demonstrating that no special
knowledge of the proposed system is required to create training
data for it.

2) Pruning and Simpliﬁcation: In expanded trees the number of their leaves after head insertion becomes signiﬁcantly
larger than the number of words in the target sentence, and this
could cause noise in automatic word alignment. To ﬁx this, weapply some pruning and simpliﬁcation heuristics to reduce thecomplexity of trees. We developed 20 hand-written rules toprune and simplify the head-inserted tree by removing nodes
that don’t seem related to the surface form of the language.
Fig. 8 shows an example after this process was applied to theresult of Fig. 7.

Next, we divided this data into separate sets for our
experiments. We split the Python-to-English corpus into 3
parts that include 16,000, 1,000, and 1,805 statements. The
16,000 element set is the “training” data used to extract SMT
rules and train the language model. The next 1,000 is the“development” data used to optimize the weight vector w of
the log-linear model. The last 1,805 is the “test” data used
to evaluate the trained SMT models. The Python-to-Japanese
corpus is smaller than the Python-to-English corpus, so we
perform 10-fold cross-validation, in which we use 90% of thedata as training data, no development data (w is set as thedefault of each SMT framework), and 10% as test data.

In our method for pseudo-code generation, only thesetransformation methods require human engineering. However,developing these methods is easier than developing a rulebased system, because they are relatively simple and largely
independent of the language of the pseudo-code.
B. Training Process of Pseudo-code Generator
Up until this section, we described details of each part ofour pseudo-code generation system.
Fig. 9 shows the whole process of our pseudo-code generator, and Fig. 10 shows the training process of the PBMTand T2SMT frameworks. In this paper, we compare 4 typesof methods for pseudo-code generation. PBMT is a method
directly using the tokens of programming and natural languages in the PBMT framework. Raw-T2SMT is a T2SMTbased method trained by raw abstract syntax trees of the programming language without the modiﬁcations described in theprevious section. Head-T2SMT is also a T2SMT-based method
trained using modiﬁed trees with only the head insertion
process. Reduced-T2SMT is the last T2SMT-based method,using the head insertion, pruning, and simpliﬁcation processes.

VI.

E VALUATING P SEUDO - CODE G ENERATION

Once we have generated pseudo-code, we would like toevaluate its accuracy and usefulness. To do so, we use an
automatic measure of translation accuracy adopted from the
SMT literature, a manual evaluation of the accuracy of code
generation, and a measure of how much the pseudo-code
can contribute to code understanding. As described in thefollowing sections, we calculate automatic evaluation measuresfor English and Japanese pseudo-code and manual accuracy
and code understanding for Japanese pseudo-code.

The algorithms for training SMT systems from a parallel
corpus are too complex to develop ourselves. Fortunately, we

4 https://projecteuler.net/

580

Fig. 9.

Whole training process of each proposed method (a bold border indicates language-dependent processes).

Fig. 10.

Training process of PBMT and T2SMT frameworks.

TABLE I.

A. Automatic Evaluation – BLEU

Level
AA (5)
A (4)
B (3)
C (2)
E (1)

First, to automatically measure the accuracy of pseudocode generation, we use BLEU (Bilingual Evaluation Understudy) [33], an automatic evaluation measure of the generated
translations widely used in machine translation studies. BLEU
automatically calculates the similarity of generated translations
and human-created reference translations. BLEU is deﬁned as
the product of “n-gram precision” and a “brevity penalty.” ngram precision measures the ratio of length n word sequences
generated by the system that are also created in the humanreference, and the brevity penalty is a penalty that prevents thesystem from creating overly short hypotheses (that may havehigher n-gram precision). BLEU gives a speciﬁc real value
with range [0,1] and is usually expressed as a percentage. If
the translation results are completely equal to the references,the BLEU score becomes 1.

D EFINITION OF ACCEPTABILITY

Meaning
Grammatically correct, and ﬂuent
Grammatically correct, and not ﬂuent
Grammatically incorrect, and easy to understandGrammatically incorrect, and difﬁcult to understandNot understandable or some important words are lacking

not entirely guarantee that each translation result is semantically correct for the source sentence. To more accurately
measure the quality of the translations, we also perform an
evaluation using human annotators according to the acceptability criterion [34] shown in TABLE I. We employed 5Japanese expert Python programmers to evaluate statementwise acceptabilities of each generated Japanese pseudo-code.
C. Human Evaluation (2) – Code Understanding

In this study, we evaluated the quality of generated English
and Japanese pseudo-code using BLEU, using the humandescribed pseudo-code of each statement as a reference.

Especially for beginner programmers, pseudo-code may
aid comprehension of the corresponding source code. To
examine this effect, we perform a human evaluation of code
understanding using experienced and unexperienced Japanese
Python programmers through a Web interface.

B. Human Evaluation (1) – Acceptability
BLEU can automatically and quickly calculate the accuracyof generated translations based on references. However, it doesFirst, we show a sample of a function deﬁnition and581

TABLE II.
Level
5
4
3
2
1
0

D EFINITION OF UNDERSTANDABILITY

TABLE III.

Meaning
Very easy to understandEasy to understandNot either easy or difﬁcult to understandDifﬁcult to understand
Very difﬁcult to understandDo not understandPseudo-code
Generator
PBMT
Raw-T2SMT
Head-T2SMT
Reduced-T2SMT

corresponding pseudo-code as in Fig. 1 to unexperienced
programmers, who read the code. These programmers thenassign a 6-level score indicating their impression of how wellthey understood the code for each sample. This impression issimilar to Likert scale described in TABLE II. The evaluationinterface records these scores and elapsed time from proposing
a sample to the programmer submitting the score. This elapsed
time can be assumed to be the time required by the programmer
to understand the sample. Next, we have the programmers
describe the behavior of functions they read in their mothertongue. We obtained these results from 14 students, in which
6 students had less than 1 year of Python experience (including
no experience), perform this experiment task.

Code setting that shows only source code itself, withno pseudo-code.

•

Reference setting that shows human-created pseudocode (i.e. training data of the pseudo-code generator).

•

Automated setting that shows code automatically generated by our Reduced-T2SMT method.

VII.

BLEU%
(English)(Japanese)
25.71
51.67
49.74
55.66
47.69
59.41
54.08
62.88

Mean Acceptability(Japanese)
3.627
3.812
4.039
4.155

developing many engineers for a variety of objectives, and thus
there is larger variance. The results of PBMT and Head-T2SMT
for Python-to-English reﬂect these characteristics. As we mentioned in §III-B, PBMT-based pseudo-code generators cannot
adequately handle grammatically complicated sentences, likely
the reason for their reduced accuracy. Each T2SMT systemachieves signiﬁcantly higher BLEU than the PBMT system,
indicating that properly analyzing the program structure before
generating comments is essential to accurately generating
pseudo-code.
We can also note that the Head-T2SMT system has a lower
score than Raw-T2SMT for the Python-to-English dataset.
This result is likely caused by the variance of human-createdpseudo-code and word alignment. The head insertion processintroduces many new tokens into the syntax tree and some ofthese tokens have no information to express the relationshipbetween programming and natural language, causing problems
in automatic word alignment. However, this problem did not
rise to the surface for the Python-to-Japanese dataset, because
it has less variance in the data. The Reduced-T2SMT systemachieves the highest BLEU score for all settings in bothlanguages, indicating that this method can avoid this problem
by reducing redundant structures in head-inserted syntax trees.

We use 117 function deﬁnitions in the Python-to-Japanese
corpus that were split into 3 settings randomly (each split wasdifferent for each subject), which were respectively shown withdifferent varieties of pseudo-code:•

BLEU% AND MEAN ACCEPTABILITIES OF EACH
PSEUDO - CODE GENERATOR .

To evaluate statistical signiﬁcance, we performed a pairwise bootstrap test [36] for 10,000 sets of evaluation sentences
randomly extracted from these results. Based on this we
obtained a statistical signiﬁcance under p < 0.001 for all
T2SMT systems against the PBMT system, and p < 0.001
for the Reduced-T2SMT system against all other systems.

E XPERIMENTAL R ESULTS AND D ISCUSSIONFirst, TABLE III shows the BLEU scores for each of
the proposed methods for Python-to-English and Python-toJapanese datasets, and the mean acceptability score of eachmethod for the Python-to-Japanese dataset.

We can also see in TABLE III that the acceptability scoresof the pseudo-code for the Python-to-Japanese dataset is also
improved in correlation to the BLEU improvement. Especially,
Reduced-T2SMT achieves a mean acceptability over 4, whichmeans that a large amount of the pseudo-code generated by
the most advanced method Reduced-T2SMT was judged as
grammatically correct by evaluators.

From these results, we can see that the BLEU scores are
relatively high (except for PBMT on the Python-to-English
data set), suggesting that the proposed method is generating
relatively accurate results for both data sets. For reference, acurrent state-of-the-art SMT system achieves a BLEU scoreof about 48 in the relatively easy French-to-English pair [35],suggesting that translation from source code to pseudo-code iseasier than translating between natural languages. This result
can be expected, because SMT systems targeting natural language pairs always include the noise caused by ambiguities oftokenization or parsing for source natural language sentences,while our pseudo-code generator has no such input ambiguity.

Fig. 11 shows the acceptability distribution of each system.
We can see that all systems can generate grammatically correct
and ﬂuent pseudo-code for 50% of the statements. Further, we
can see that each T2SMT-based system generates less pseudocode with “intermediate acceptability.” This is an interesting
result, but it is intuitively understandable that T2SMT-based
systems can generate accurate pseudo-code if their rule tables
cover the input statements, because these systems explicitly
use the grammatical information through syntax trees of the
programming language.

In addition, we can see that BLEU scores for the Pythonto-Japanese dataset are higher than the Python-to-English
dataset. This can be attributed to the characteristics of eachdataset. The Python-to-Japanese dataset’s original source code
was generated by one engineer from arithmetic problems for
programming practice, so all the input code in the set shares asimilar programming style. In contrast, the source code of the
Python-to-English dataset is extracted from Django, which is

Finally, TABLE IV shows the results of the code understanding experiment. In this table, we show 3 results calculatedby different evaluator groups. The Experienced group includes
8 of 14 evaluators who have more than 1 year of experience582

Fig. 11.

Acceptability distribution of each system.

TABLE IV.

M EAN UNDERSTANDABILITY IMPRESSIONS AND MEAN
TIME TO UNDERSTAND .

Group
Experienced

Inexperienced

All

Setting
Code
Reference
Automated
Code
Reference
Automated
Code
Reference
Automated

Mean Impression
2.55
3.05
2.71
1.32
2.10
1.81
1.95
2.60
2.28

Mean Time
41.37
35.65
46.48
24.99
24.97
39.52
33.35
30.54
43.15

in programming Python, The Inexperienced group includes theremaining 6 evaluators (with less than 1 year of experienceof Python), and All includes all evaluators. From the results,
we can see that the result of the Reference setting achieves
the highest understandability and the fastest reading time ofall settings. This means that proposing correct pseudo-code
improves the ease and efﬁciency of code reading when readers
try to read the whole source code in detail. The result of theAutomated setting also achieves a better impression than thatof the Code setting. However, the reading time becomes longer
than other settings. We assume that this is the result of the few
strange lines of pseudo-code generated from our generator (e.g.
pseudo-code scored 1 in acceptability) that confuse the readersin their attempt to interpret source code. Reducing generation
errors in the Automated method can reduce this time-loss, inprinciple, similarly to the results of Reference.

Fig. 12.

syntax tree) pairs related to each other, and described several
algorithms to adjust the parallel corpus to be in a format
appropriate for SMT.
In the future work, we are planning to develop a pseudocode generator uses the proposed SMT framework to handle
multiple statements, close to the standard setting of automaticcomment generation. To do so, we must ﬁnd or create ahigh-quality parallel corpus of source code and comments
corresponding to multiple statements in the source code,
which is a less well-formed problem than creating line-toline comments, and is thus an interesting challenge for future
work. We also plan to investigate the use of automatic pseudocode generation by experienced programmers in large software
project environments. For example, automatically generated
pseudo-code could be used by programmers to conﬁrm thatthe code that they wrote is actually doing what they expect
it to be doing, or to help conﬁrm when existing (single-line)
comments in the source code have gone stale and need to be
updated.

Fig. 12 shows 3 sets of examples from the proposed methods. We can see that each T2SMT-based systems (especially
Reduced-T2SMT) generates more accurate sentences in English
than the PBMT system.
VIII.

Examples of generated pseudo-code from each system.

C ONCLUSION AND F UTURE W ORK

In this paper, we proposed a method for pseudo-code
generation that is, to our knowledge, the ﬁrst of its type. Our
method is based on statistical machine translation (SMT) techniques, especially phrase-based machine translation (PBMT)
and tree-to-string machine translation (T2SMT), which allow
us to automatically learn statement-wise pseudo-code generators and require less human effort to create and update ourgenerators. Experiments showed that our proposed methods
generate grammatically correct pseudo-code for the Pythonto-English and Python-to-Japanese programming/natural language pairs, and distinguished that proposing pseudo-code withsource code improves code comprehension of programmers forunfamiliar programming languages. To use SMT frameworks,
we prepared a parallel corpus, which includes sentence (orACKNOWLEDGMENT
Part of this work was supported by the Program for
Advancing Strategic International Networks to Accelerate theCirculation of Talented Researchers. We also thank Mr. Akinori Ihara, who also gave us useful advice regarding this work.
R EFERENCES[1]

R. DeLine, G. Venolia, and K. Rowan, “Software development withcode maps,” Commun. ACM, vol. 53, no. 8, pp. 48–54, 2010.
[2] M. M. Rahman and C. K. Roy, “Surfclipse: Context-aware meta searchin the ide,” in Proc. ICSME, 2014, pp. 617–620.

583

[3]

[4]

[5]

[6]
[7]

[8]

[9]

[10]

[11]

[12]
[13]
[14]

[15]
[16]

[17]

[18]

[19]
[20]

[21]

[22]

[23]
[24]
[25]
[26]

[27]
[28]

[29] T. Kudo, K. Yamamoto, and Y. Matsumoto, “Applying conditionalrandom ﬁelds to Japanese morphological analysis.” in Proc. EMNLP,
vol. 4, 2004, pp. 230–237.
[30] K. Heaﬁeld, I. Pouzyrevsky, J. H. Clark, and P. Koehn, “Scalable
modiﬁed Kneser-Ney language model estimation,” in Proc. ACL, Soﬁa,
Bulgaria, August 2013, pp. 690–696.
[31] P. Koehn, H. Hoang, A. Birch, C. Callison-Burch, M. Federico,
N. Bertoldi, B. Cowan, W. Shen, C. Moran, R. Zens, C. Dyer, O. Bojar,
A. Constantin, and E. Herbst, “Moses: Open source toolkit for statisticalmachine translation,” in Proc. ACL, 2007, pp. 177–180.
[32] G. Neubig, “Travatar: A forest-to-string machine translation engine
based on tree transducers,” in Proc. ACL, Soﬁa, Bulgaria, August 2013,
pp. 91–96.
[33] K. Papineni, S. Roukos, T. Ward, and W.-J. Zhu, “Bleu: A method forautomatic evaluation of machine translation,” in Proc. ACL, 2002, pp.
311–318.
[34] I. Goto, K. P. Chow, B. Lu, E. Sumita, and B. K. Tsou, “Overview of thepatent machine translation task at the ntcir-10 workshop,” in NTCIR-10,
2013.
[35] O. Bojar, C. Buck, C. Federmann, B. Haddow, P. Koehn, J. Leveling,
C. Monz, P. Pecina, M. Post, H. Saint-Amand, R. Soricut, L. Specia, and
A. Tamchyna, “Findings of the 2014 workshop on statistical machinetranslation,” in Proc. WMT, 2014, pp. 12–58.
[36] P. Koehn, “Statistical signiﬁcance tests for machine translation evaluation,” in Proc. EMNLP, 2004, pp. 388–395.

M.-A. Storey, “Theories, tools and research methods in program comprehension: Past, present and future,” Software Quality Journal, vol. 14,
no. 3, pp. 187–208, 2006.
G. Sridhara, E. Hill, D. Muppaneni, L. Pollock, and K. Vijay-Shanker,“Towards automatically generating summary comments for java methods,” in Proc. ASE, 2010, pp. 43–52.
G. Sridhara, L. Pollock, and K. Vijay-Shanker, “Automatically detecting
and describing high level actions within methods,” in Proc. ICSE, 2011,
pp. 101–110.
R. P. Buse and W. R. Weimer, “Automatic documentation inference for
exceptions,” in Proc. ISSTA, 2008, pp. 273–282.
L. Moreno, J. Aponte, G. Sridhara, A. Marcus, L. Pollock, and K. VijayShanker, “Automatic generation of natural language summaries for javaclasses,” in Proc. ICPC, 2013, pp. 23–32.
E. Wong, J. Yang, and L. Tan, “Autocomment: Mining question andanswer sites for automatic comment generation,” in Proc. ASE, 2013,
pp. 562–567.
S. Haiduc, J. Aponte, L. Moreno, and A. Marcus, “On the useof automated text summarization techniques for summarizing source
code,” in Proc. WCRE, 2010, pp. 35–44.
B. P. Eddy, J. A. Robinson, N. A. Kraft, and J. C. Carver, “Evaluating
source code summarization techniques: Replication and expansion,” inProc. ICPC, 2013, pp. 13–22.
P. Rodeghero, C. McMillan, P. W. McBurney, N. Bosch, and S. D’Mello,“Improving automated source code summarization via an eye-tracking
study of programmers,” in Proc. ICSE, 2014, pp. 390–401.
P. Koehn, Statistical Machine Translation. Cambridge University Press,
2010.
A. Lopez, “Statistical machine translation,” ACM Computing Surveys,
vol. 40, no. 3, pp. 8:1–8:49, 2008.
P. F. Brown, V. J. D. Pietra, S. A. D. Pietra, and R. L. Mercer, “Themathematics of statistical machine translation: Parameter estimation,”
Computational Linguistics, vol. 19, no. 2, pp. 263–311, 1993.
P. Koehn, F. J. Och, and D. Marcu, “Statistical phrase-based translation,”in Proc. NAACL-HLT, 2003, pp. 48–54.
S. Karaivanov, V. Raychev, and M. Vechev, “Phrase-based statisticaltranslation of programming languages,” in Proc. Onward!, 2014, pp.
173–184.
F. J. Och and H. Ney, “The alignment template approach to statisticalmachine translation,” Computational Linguistics, vol. 30, no. 4, pp. 417–
449, 2004.
L. Huang, K. Knight, and A. Joshi, “Statistical syntax-directed translation with extended domain of locality,” in Proc. AMTA, vol. 2006,
2006, pp. 223–226.
D. Klein and C. D. Manning, “Accurate unlexicalized parsing,” in Proc.
ACL, 2003, pp. 423–430.
S. Petrov, L. Barrett, R. Thibaux, and D. Klein, “Learning accurate,compact, and interpretable tree annotation,” in Proceedings of COLINGACL, 2006, pp. 433–440.
P. F. Brown, V. J. D. Pietra, S. A. D. Pietra, and R. L. Mercer, “Themathematics of statistical machine translation: Parameter estimation,”
Computational Linguistics, vol. 19, no. 2, pp. 263–311, Jun. 1993.
G. Neubig, T. Watanabe, E. Sumita, S. Mori, and T. Kawahara, “An
unsupervised model for joint phrase alignment and extraction,” in Proc.
ACL-HLT, Portland, Oregon, USA, 6 2011, pp. 632–641.
M. Galley, M. Hopkins, K. Knight, and D. Marcu, “What’s in atranslation rule?” in Proc. NAACL-HLT, 2004, pp. 273–280.
R. Kneser and H. Ney, “Improved backing-off for m-gram language
modeling,” in Proc. ICASSP, 1995, pp. 181–184.
A. Hindle, E. T. Barr, Z. Su, M. Gabel, and P. Devanbu, “On thenaturalness of software,” in Proc. ICSE, 2012, pp. 837–847.
T. T. Nguyen, A. T. Nguyen, H. A. Nguyen, and T. N. Nguyen, “A
statistical semantic language model for source code,” in Proc. FSE,
2013, pp. 532–542.
Z. Tu, Z. Su, and P. Devanbu, “On the localness of software,” in Proc.
FSE, 2014, pp. 269–280.
A. T. Nguyen and T. N. Nguyen, “Graph-based statistical language
model for code,” in Proc. ICSE, 2015.

584