社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE

Ripple Down Rule を用いたソースコード変更の分類
エディパーキンソン† 川口 真司† 井上 克郎††大阪大学大学院情報科学研究科 〒560-8531 大阪府豊中市待兼山町１番３号
E-mail: †{eddy, s-kawagt, inoue} @ist.osaka-u.ac.jp
あらまし

開発者は時折大量のコード変更をせまられる．このようなソースコード変更はなるべく少ないほうが望ましい．

Ripple Down Rule (RDR) は実績のある知識獲得手法である．RDR は経験から得られる知識をシンプルに管理するための手法であり，一度判定に失敗した事例を再利用することでより適切な判定を下すことを可能にする．本研究では，推薦されたコードの書き方と，実際に書きなおされたコードを確かめることで，RDR を用いて変更履歴を分類できるかどうかを検証した．まだより多くの作業が必要だが，得られた結果は RDR による分類が有用であることを示唆している．

キーワード Ripple Down Rules, Personal Software Process, Software Defects

Ripple Down Rules, a practical method of learning from code rewrites
Eddy PARKINSON†

Shinji KAWAGUCHI†

Katsuro INOUE††Department of Computer Science, Osaka University 1-3, Machikaneyama-cho, Osaka, 560-8531 Japan
E-mail:Abstract†{eddy, s-kawagt, inoue} @ist.osaka-u.ac.jp

Software developers sometimes rewrite large sections of program code. Reducing the number of rewrites would savevaluable development time. Ripple Down Rules (RDR) has a proven knowledge acquisition track record. RDR looks to offer a simple tomaintain method capturing knowledge gained through experience. RDR allows recommendations identified when a failure occurs, to be
captured and reused. The approach is evaluated by examining recommended ways of writing code and examining rewritten code to see ifmodifications can be categorised using RDR. The results suggest the idea is feasible, although more work is needed.

Keyword Ripple Down Rules, Personal Software Process, Software Defects
learn from the choices of experts in a systematic way, see

1. Introduction
Software development suffers from budget overruns[Preston93] for a case study.

and project failures. A report by [StandishGroup01] states
20% of software development projects are cancelled and
50% of projects have an average cost of 189% of theoriginal estimate. Personal software process (PSP), see[Humphrey95],

has

improvements

insuccessfully

achieved

dramatic

2. Understanding MCRDR
MCRDR works on the principle there are exceptions toeveryrule.

Whenafailureoccurs

andsomeandrecommendation is made to help prevent such failures, theimproving the quality of the software delivered torecommended action is added to the rule base. Thecustomers, see [Ferguson99] for a case study. PSP is arecommended action exists to prevent a particular failure

gradual learning process that focuses on developers

and only applies in certain situations. MCRDR is an

keeping notes to help them learn from previous mistakes.

extended version of RDR.

controlling

budgetoverrun

The idea described here is to combine PSP with Multiple
Classification Ripple Down Rules. MCRDR helps novices
Key: Attribute – ConclusionzFigures 1 is a simple example used here to describe
Case:

Normal day - Wear shorts and t-shirt

Case1: Hot and sunny¾Raining - Wear coat

Case2: Cold and raining

Case4: Hot and raining¾

Hot - T-shirt, shorts and take umbrella

Windy - Take kite

Case3: Windy and sunny
Figure 1

RDR and MCRDR. On the first day, the first line “normaland so when “Hot - T-shirt, shorts and take umbrella” isday” is created because on the first day it was hot andtrue, “Raining - Wear coat” is evaluated as false. RDRsunny so we decided to wear shorts and a t-shirt. When it

only allowed one conclusion in the tree to be true and sois cold and raining, wearing shorts and t-shirt is not ait

good solution. The indentation indicates an exception toconclusions into one, MCRDR solves this problems andthe rule, so the second day “cold and raining” is an

has replaced RDR

exception,needing

adifferentconclusion.

wassometimes

necessarytocombine

severalBecausewearing shorts and a t-shirt was not a good solution, theFigure 2 shows that the order of the cases does not

exception, “raining - wear coat” is added. To add thehave a significant impact on knowledge acquisition. With

exception a difference between the first “Normal day” andthe two rules, “Raining - T-shirt, shorts and takethe second day is needed. Either raining or cold can beumbrella” and “Cold - Wear coat”, in figure 2, it is stillused as an attribute to distinguish between the two cases.

necessary to distinguish between hot and cold days andWhen picking attributes an expert tends to perform better

when it is raining and not raining. The same conclusions

than a novice. Experts tend to be better at picking

are reached and the same distinctions between cases also

attributes to distinguish between cases and as a result end

occur, just in a different order.

Key: Attribute – Conclusion
z

Case:

Normal day - Wear shorts and t-shirt

Case1: hot and sunny¾

Raining - T-shirt, shorts and take umbrella

Case2: Hot and raining

Case4: Cold and raining¾

Cold - Wear coatCase3: Windy and sunny

Windy - Take kite

Figure 2
up with a more compact set of rules, see [Kang95].
Experts are able to define complex attributes that
distinguish between cases. Also by examining attributes

The simplicity comes from only having to identify apicked by novices it has been possible to identify

difference between two cases, rather than trying to create

incorrect assumptions made by the novice.

some complex problem solving method. When attempting
to create problem solving methods [Compton98] notes

On the third day it is windy, hot and sunny, so the firstconclusion is possible, but instead a new exception isadded, “Windy - Take kite”. By adding this exception thethat:“we invariably attempted to develop something thatwas far more complex than is actually required.”next time it is windy the conclusion take kite will be used,
this is because there are no exceptions to the “Windy Take kite” rule in the rule base.

The quote highlights the problem of developing simple
rules that take into account exceptions. The rules infigures 1 & 2 show how MCRDR allows exceptions to be

Next a hot and raining day is encountered, because theadded to existing simple rules without restructuring.

rule “Raining - Wear coat” evaluates to true for a hot andraining day, an exception to this conclusion is added,“Hot - T-shirt, shorts and take umbrella”. The structure

3. Conclusion Classification with MCRDR

is such than any rule can have an exception and theMedical experts have successfully used MCRDR toexception is itself a rule. Each rule is made up of ancapture knowledge [Khan03], [Preston93]. When MCRDR

attribute condition and a conclusion, as can be seen inwas evaluated for use as a method for creating diets to fit

Figure 1.

patient preferences [Khan03], a senior dietician said themethod offered “considerable potential to improve theThe MCRDR approach allows several conclusions to bedaily routine”. The work suggests problems that are suitedtrue. For example on a raining and windy day bothto Case Based Reasoning (CBR) approaches are better“Raining - Wear coat” and “Windy - Take kite” aretackled using MCRDR.

evaluated as being true. When an exception is true itmeans the parent conclusions are accepted as being false,While the identification of conclusions can in manycases be automated, in some a partially manual search iswith overall project management, see [Seshagiri03] for acase study.

needed. With a 1600 rule knowledge base such as[Preston93], a manual search of the rule base would be

PSP involves developers keeping track of defects theytime consuming. It looks as if the time needed to find

find and when they are removed, with the aim of trying toconclusions limits the scope of MCRDR. To help dealfind ways of removing defects sooner in the developmentwith this problem the MCRDR help desk system which

process. Methods such as requirements reviews and code

[Kang97] describes contains a search mechanism to help

reviews are employed to try and spot defects early andsearch the large case base rather than relying on a manual

remove them long before unit testing and integration

search of the MCRDR tree. Another approach to thetesting. PSP involves making developers aware of theproblem of searching through a large MCRDR case basetypes of defects that exist and the costs of removing them.

was introduced by [Vazey04]. The method used is asequence of requests for specific information, graduallyrefining the search for a conclusion.

PSP & TSP also uses estimated LOC to help predict thenumber of defects that will exist. Such estimation
techniques are continually refined by comparing actual
LOC and actual defects to those estimated. The difference
between the predicted and actual schedule and budget in

4. Maintenance of MCRDR
One of the advantages of MCRDR over Expert Systems[Ferguson99] had a standard deviation of about 25% foris that it does not require knowledge engineers tobudget and 12% for the schedule spread over 14 projects.

maintain the rule base, see [Khan03], [Preston93]. For an
introduction to Expert Systems see [Jackson99]. The
problem of maintaining an Expert System is that new

6. Usefulness of combining MCRDR & PSP

knowledge is difficult to add because it tends to conflictTraining is cited as a key part of PSP [Ferguson97].

with the existing rules in the system, this is highlighted inThe training includes the writing of 10 small programs[Preston93]. In contrast to Expert Systems, MCRDR

and this case data is then used to train developers. The

allows new knowledge without impacting on existing ruleknowledge in MCRDR is also captured using case data.

base. This advantage is highlighted by the quote:

The advantage of using MCRDR is that it provides“Rule addition of the order of 20 per hour could

novices with the information they need to make expert

be achieved with very low error rates. It was realised thatlike decisions right from the very beginning, rather thanerror rates could be eliminated by validating the rules asthem having to relearn it from scratch.

they were added.” [Preston93]
While MCRDR does not claim to be a perfect methodof passing on knowledge, it does appear to offer a better

5. Personal

SoftwareProcessandTeam

method of passing on expert knowledge than other

Software Process (PSP & TSP)

approaches,

PSP was developed by [Humphrey95], it has achievedknowledge from an expert to a novice is difficult to do.

impressive improvements in predicting schedules andThis problem is highlighted by the following statement:

reducing

defects.

The

companytechnicalsee[Preston93],[Khan03].

Passingreport[Ferguson99] reported:"[After] long term experience of maintaining an expert“Our average project schedule overrun has beensystem. What became clear ... when an expert is asked

reduced from 112% to 5%, and our average budget

how they reached a conclusion they do not and cannot

overrun from 87% to -4%.”

explainhow

theyreachedtheirconclusion."see[Preston93].
This was achieved over several years and involved
training all programmers in PSP. Several books were used

To help deal with this problem RDR was developed, itin the training process and the training process looks touses actual case data to capture expert knowledge. PSPbe central to PSP [Ferguson97]. Team Software Processhighlights the value of using past cases to guide the(TSP) was developed by [Humphrey 99] after PSP to help

creation of schedules and aid the removal of defects.

Combining these two ideas lead to:

not remove the issue of the time spent searching forconclusions. This suggests the conclusions added to theHypothesis

1:

NovicesusingMCRDRtopredict

rule base would gain from having some measure of theirbudgets and schedules are able to achieve the sametime and quality value attached. Equally it means thatstandard as experts in 95% of cases.

having low value conclusions in the rule base could

Hypothesis 2: Novices using MCRDR are able to be as

potentially have a negative impact on the value of the ruleeffective at removing defects as experts in 95% of cases.

base. It may be possible to use some form of formal
notation to help resolve the problem of searching the rule

The 95% comes from the MCRDR literature, seebase, but this requires further investigation.

[Preston93], and is an estimate of the percentage accuracy
that MCRDR achieved in a domain. While the reality ofBecause the conclusions are labels without a value, it

what can actually be achieved is far from clear, the above

makes it hard to decide if a conclusion is right or wrong.

hypothesises give a rough benchmark that can used toUntil the categories reach the stage where the conclusions

assess progress.

are useful in some way the choice of which categories areworth creating is arbitrary. This suggests that using
MCRDR to categorise modifications provides little morethan a rough list and the real advantage of using MCRDR

7. Evaluating code re-writes

willThe code modifications described in Figure 3 comes

comewhenrecommendations

arecreatedthat

improve things.

from sourceforge.net and appear to be typical of suchprojects. Even though only 18 cases are listed, many ofthe modifications are similar, which suggests MCRDR is

8. Conclusion

able to separate modifications into simple categories. The

To test the idea of using MCRDR to pass software

process of using MCRDR to categorise modifications has
highlighted two weaknesses:

development knowledge from experts to novices there is a1.

As the rule base gets larger it becomes harder to add

need to examine not only actual modifications made to

new rules, because much searching is needed to checkcode but also to identify cases where experts have been

if a similar case has been seen before.

able to reduce the impact of project modifications.

The conclusions are labels that have little value; they

Identifying cases where an expert disagrees with a choicedescribe modifications, but do not say what should bemade by a novice should allow expert recommendations

done to improve the situation.

to be identified. Following this up by asking the expert to2.

identify an attribute in the case that lead them to conclude
an alternative action was needed should allow an MCRDR

The difficulty of searching the rule base means thatrule tree to be created.

there is a need for high reward conclusions to balance thetime spent searching the rule base with the reward gainedThe

from implementing the conclusion. While several methods

Key: Attribute–studyofmodified

codeshowsthatwhen

classifying conclusions using MCRDR, the classification

exist that speed up the searching of the rule base, these doConclusion

Case:

1.

Complete line(s) of code moved

statements that existed in more than one place are centralisation & enhanced 1, 8

2.

Changed constant3.

Removed complete line(s) of code feature had negative impact

4.

Apply function to many constants/variables process to produce a particular value type is centralised5.

Modified a single section of code Added simple feature/removed defect9, 15(ア ) Inserted if + else statement around code

14, 16

6.

Removed method call(ア ) Replaced variable/ constant with method

process used to produce a particular value type is centralised

simplistic name/text/visual enhancement or fix

Added simple feature/removed bug

Centralisation removed the need for the method call2
3, 5, 174, 14

6, 7, 10,11

12, 137.

Inserted new lines of code

Added simple feature/removed bug

148.

New methods inserted containing new code

Added feature

15, 16

Figure 3 – MCRDR classification of code modification

has little value, when the conclusion is not useful.

Priya 2003
[StandishGroup01] CHAOS Chronicles II, The Standish

The examination of the MCRDR and PSP literature andGroup, www.standishgroup.com, 2001

code re-writes shows that using MCRDR to pass on expert[Vazey04] Achieving Rapid Knowledge Acquisition in aPSP knowledge to novices is a promising idea. What

High-Volume Call Centre, in Proceedings of the Pacificremains unclear is the detail of actual recommendations

Knowledge Acquisition Workshop, 2004

discovered

whileusingPSP.

AddingactualPSP

recommendations to a MCRDR rule base should reveal
more about the value and feasibility of the hypothesises
described above.

9. References[Compton98] A Trade Off Between Domain Knowledge
andProblem

SolvingMethod

Power 、 Eleventh

Workshop on Knowledge Acquisition, P. Compton, Z.
Ramadan,P.

Preston,T.

Le-Gia,V.Chellen,M.

Mulholland, D.B. Hibbert, P.R. Haddad, B. Kang 1998.
[Ferguson97] Results of Applying the Personal Software
Process, IEEE Computer, Vol. 30, No. 5, P. Ferguson,
W. Humphrey, S. Khajenoori, S. Macke, and A. Matvya
1997[Ferguson99] Software Process Improvement Works, SEI
Technical Report, CMU/SEI-TR-99-27 Ferguson P.,
Leman G., Perini P., Renner S. & Seshagiri G. 1999
[Humphrey95] A Discipline for Software Engineering,Addison-Wesley, Watts Humphrey 1995.
[Humphrey99] Introduction to the Team Software Process,Addison-Wesley, Watts Humphrey 1999
[Jackson99] Introduction to Expert Systems, 3rd ed.,Addison-Wesley, Harlow, England, Peter Jackson 1999.
[Kang95] Multiple Classification Ripple Down Rules
Evaluation and Possibilities, in Proceedings 9th Banff
Workshop on Knowledge Acquisition, B.H. Kang, P.
Compton, and P. Preston 1995
[Kang97] Help Desk System with Intelligent Interface, inApplied Artificial Intelligence, 11: 611-631, Kang, B.
H., Yoshida, K., Motoda, H. and Compton, P. 1997
[Khan03] Building a case based diet recommendation
system without a knowledge engineer, in Artificial
Intelligence in Medicine 27(2): 155-179, Abdus Salam
Khan, Achim G. Hoffmann 2003
[Preston93]

A

1600

RuleExpert

SystemWithout

Knowledge Engineers, in J. Leibowitz, editor, Second
World Congress on Expert Systems, P. Preston, G.
Edwards, and P. Compton 1993
[Seshagiri03] Walking the Talk Building Quality into theSoftware Quality Management Tool, Third International
Conference On Quality Software, Girish V. Seshagiri, S.