1
ImprovingPrologPrograms:Refactoringfor
Prolog
ALEXANDERSEREBRENIK
LaboratoryofQualityofSoftware(LaQuSo),T.U.Eindhoven
HG5.91,DenDolech2,P.O.Box513,5600MBEindhoven,TheNetherlands
(e-mail:A.Serebrenik@tue.nl)
TOMSCHRIJVERS∗
DepartmentofComputerScience,K.U.LeuvenCelestijnenlaan200A,B-3001,Heverlee,Belgium(e-mail:Tom.Schrijvers@cs.kuleuven.ac.be)
BARTDEMOEN
DepartmentofComputerScience,K.U.LeuvenCelestijnenlaan200A,B-3001,Heverlee,Belgium(e-mail:Bart.Demoen@cs.kuleuven.ac.be)
submitted1January2003;revised1January2003;accepted1January2003
Abstract
Refactoringisanestablishedtechniquefromtheobject-oriented(OO)programmingcommunitytorestructurecode:itaimsatimprovingsoftwarereadability,maintainabilityandextensibility.Al-thoughrefactoringisnottiedtotheOO-paradigminparticular,itsideashavenotbeenappliedtoLogicProgramminguntilnow.
ThispaperappliestheideasofrefactoringtoPrologprograms.Acatalogueispresentedlistingrefactoringsclassifiedaccordingtoscope.SomeoftherefactoringshavebeenadaptedfromtheOO-paradigm,whileothershavebeenspecificallydesignedforProlog.ThediscrepancybetweenintendedandoperationalsemanticsinPrologisalsoaddressedbysomeoftherefactorings.
Inaddition,ViPReSS,asemi-automaticrefactoringbrowser,isdiscussedandtheexperiencewithapplyingViPReSStoalargeProloglegacysystemisreported.ThemainconclusionisthatrefactoringisbothaviabletechniqueinPrologandaratherdesirableone.
1Introduction
Maintainingandadaptingsoftwaretakesupasubstantialpartoftheentireprogrammingeffort,bothintimeandmoney.Erlikh(2000)andMoad(1990)bothreportonthepropor-tionofmaintenancecostsexceeding90%ofthebudget.About75%ofthesecostsarespentonprovidingenhancements(intheformofadaptiveorperfectivemaintenance)(NosekandPalvia1990;vanVliet2000).
Beforeprovidingenhancements,itisrecommendedtoimprovethedesignofthesoft-wareinapreliminarystep.Thismethodology,calledrefactoring,emergedfromanumberofpioneerresultsintheOO-community(Fowleretal.1999;Opdyke1992;Robertsetal.
∗ResearchAssistantoftheFundforScientificResearch-Flanders(Belgium)(F.W.O.-Vlaanderen)
2AlexanderSerebrenik,TomSchrijversandBartDemoen
1997)andrecentlycametoprominenceforfunctional(Lietal.2003)andprocedural(Gar-ridoandJohnson2003)languages.
Refactoringisadisciplinedtechniqueforrestructuringanexistingbodyofcode,alter-ingitsinternalstructurewithoutchangingitsexternalbehavior.Itsheartisaseriesofsmallsource-to-sourceprogramtransformations,calledrefactorings,thatchangeprogramstruc-tureandorganization,butnotprogramfunctionality.Themajoraimofrefactoringistoimprovereadability,maintainabilityandextensibilityoftheexistingsoftware.
Whileperformanceimprovementisnotconsideredasacrucialissueforrefactoring,itcanbenotedthatwell-structuredsoftwareismoreamenabletoperformancetuning.Wealsoobservethatcertaintechniquesthatweredevelopedinthecontextofprogramoptimization,suchasdead-codeeliminationandredundantargumentfiltering,canimproveprogramorganizationand,hence,canbeusedasrefactoringtechniques.
InthispaperwestudyrefactoringtechniquesforProlog.Ourgoalsarethreefold.Firstly,wewanttoshowthatrefactoringisaviabletechniqueforPrologandmanyoftheexistingtechniquesdevelopedforrefactoringingeneralareapplicable.Secondly,Prolog-specificrefactoringsarepossibleandtheapplicationofsomegeneraltechniquesmaybehighlyspecializedtowardsProlog.Finally,itshouldbeclearthatrefactoringisnotonlyviableforPrologbutalsoveryusefulforthemaintenanceofPrologprograms.
InordertoachieveourgoalswepresentacatalogueofrefactoringtechniquesforPro-log.ThelistedrefactoringsareamixofgeneralandProlog-specificones.MostoftherefactoringsproposedhavebeenimplementedinaprototyperefactoringbrowserViPReSS.ViPReSShasbeensuccessfullyappliedforrefactoringa50,000lines-longlegacysystem.Ascompletenessofthecatalogueisclearlynotpossible,weaimedtoshowawiderangeofpossibilitiesforfutureworkoncombiningtheformaltechniquesofprogramanalysisandtransformationwithsoftwareengineering.Theformalelaborationofaparticulartopicmaybeasubstantialstudyonitsown,asshowstheworkondetectingduplicatecodebyVanhoof(2004)thatwasinspiredbyapreliminaryversionofourwork.
OutlineofthePaperFirst,Section2providesabriefoverviewoftherefactoringprocess.Next,theuseofseveralrefactoringtechniquesisillustratedonasmallexampleinSection3.ThenacatalogueofPrologrefactoringsisgiveninSection4.InSection5weintroduceViPReSS,anddiscussitsapplicationinacasestudy.Finally,inSection6weconclude.
2TheRefactoringProcess
Therefactoringprocessconsistsofapplyinganumberofrefactorings,withbothlocalizedandglobalimpact,toasoftwaresystem.Theindividualsignificanceofarefactoringmaybeapparent,butoftenarefactoringseemstrivialonitsownandonlyinconjunctionwithotherrefactoringsorintendedchangesdoestheusefulnessbecomeclear.Thatisthereasonwhyitisnotfeasibletofullyautomaterefactorings.Theymustbecarefullyconsideredinviewoftheprogrammer’sintentions.
Forthisreasontheprocessofapplyingasinglerefactoringistobesplitintoanumberofdistinctactivities(MensandTourw´e2004).Theseactivitiesinvolvedecisionstobemadebytheprogrammer.
Thefirstdecisioniswherethesoftwareshouldberefactored.Makingthisdecisionauto-
ImprovingPrologPrograms:RefactoringforProlog3
maticallycanbeadifficulttaskonitsown.Severalwaystoresolvethismaybeconsidered.Forinstance,onecanaimatidentifyingsocalledbadsmells,i.e.,“structuresofthecodethatsuggest(sometimesscreamfor)thepossibilityofrefactoring”(Fowleretal.1999).Tothisendprogramanalysiscanbeused.Forexample,itiscommonpracticewhileorderingpredicateargumentstostartwiththeinputargumentsandendwiththeoutputarguments.Modeinformationcanbeusedtodetectwhenthisruleisviolated.
Next,oneshoulddeterminewhichrefactoringsshouldbeapplied.Sometimes,thecor-respondencebetweenbadsmellsandrefactoringsisclear.Forinstance,ifthepredicateargumentsarenotorderedaccordingtothe“inputfirstoutputlast”rule,onecansuggesttotheusertoreorderthearguments.ThisrefactoringisfurtherdiscussedinSection4.3.Inmorecomplexsituationstherelationbecomeslessobvious:anumberofdifferentrefac-toringsareapplicableandtheuserhastochoosebetweenthem.Forexample,letmoduleAcontainapredicatethatismutuallyrecursivewithpredicatepfrommoduleB,andmod-uleCcontainapredicatethatismutuallyrecursivewithpredicateqfrommoduleB.Thissituationcanbeidentifiedasproblematicsincenoclearhierarchycanbedefinedbetweenthesemodules.Onepossiblesolutionwouldbetomergethethreemodules(Section4.2).Alternatively,onemaytrytofirstsplitBintoB1,containingp,andB2containingqsuchthattherearenocirculardependenciesbetweenB1andB2(Section4.2).Ifthissplitispossible,AcouldbemergedwithB1,andCwithB2(Section4.2).Automaticrefactoringtools,socalledrefactoringbrowsers,canbeexpectedtomakesuggestionsonwhererefac-toringtransformationsshouldbeapplied.Thesesuggestionscanthenbeeitherconfirmedorrejectedbytheprogrammer.
Bydefinition,refactoringsshouldpreservethesoftware’sfunctionality.Hence,thenextstepconsistsofensuringthatthebehaviorisindeedpreserved.Thisstep,ofcourse,de-pendsonthedefinitionofbehavior.Inthecaseoflogicprogramming,behaviorcomprisescomputedanswerssemantics,termination,andsideeffectssuchasinput/output.Itshouldbeobservedthatparticularapplicationdomainsmightrequireextendingthenotionofbe-haviortoincludesuchconceptsasefficiencyormemoryuse.Moreover,inorderforsomerefactoringstobeapplicablecertainpreconditionsshouldhold,likeabsenceofuser-definedmeta-predicatesfordead-codeeliminationdiscussedinSection4.1.Sometimesverificationofthepreconditionscannotbedoneautomatically,butmustbedelegatedtotheuser.Subsequently,thechosentransformationisapplied.Thisstepmightalsorequireuserinput.Considerforexamplearefactoringthatrenamesapredicate:whileautomatictoolscanhardlybeexpectedtoguessthenewpredicatename,theyshouldbeabletodetectallprogrampointsaffectedbythechange.ThisrefactoringisfurtherstudiedinSection4.3.Finally,theconsistencybetweentherefactoredprogramcodeandotherrelatedartifactsshouldbemaintained.Byartifactsweunderstandamongotherssoftwaredocumentation,specificationsandtestdescriptions.Theabilitytoperformthistaskautomaticallystronglydependsontheformalismsusedtoexpressthecorrespondingartifacts.Forinstance,doc-umentationgeneratorssuchaslpdoc(Hermenegildo2000)makeitpossibletokeepthedocumentationconsistentautomatically,whereasadhocunstructuredcommentsaremuchhardertoupdateautomatically.Ensuringconsistencyisconsideredasfuturework.
4AlexanderSerebrenik,TomSchrijversandBartDemoen
3DetailedPrologRefactoringExample
Weillustratesomeofthetechniquesproposedbyadetailedrefactoringexample.Con-siderthefollowingcodefragmentfromO’Keefe’s“TheCraftofProlog”(1994),p.195.Itdescribesthreeoperationsonareaderdatastructureusedtosequentiallyreadtermsfromafile.Thethreeoperationsaremakereader/3,whichinitializesthedatastructure,readerdone/1,whichcheckswhethernomoretermscanberead,andreadernext/3,whichgetsthenexttermandadvancesthereader.
Listing3.1-O’Keefe’soriginalversion
make_reader(File,Stream,State):-open(File,read,Stream),read(Stream,Term),
reader_code(Term,Stream,State).reader_code(end_of_file,_,end_of_file):-!.
reader_code(Term,Stream,read(Term,Stream,Position)):-stream_position(Stream,Position).reader_done(end_of_file).
reader_next(Term,read(Term,Stream,Pos),State)):-stream_position(Stream,_,Pos),read(Stream,Next),
reader_code(Next,Stream,State).
Wewillnowapplyseveralrefactoringstotheaboveprograminordertoimproveitsreadability.
Firstly,weuseif-then-elseintroduction(Section4.4)togetridoftheredcut1inthereadercode/3predicate(modifiedcodeisunderlined):
Listing3.2-Replacecutbyif-then-else
reader_code(Term,Stream,State):-(Term=end_of_file,State=end_of_file->
true
;
State=read(Term,Stream,Position),stream_position(Stream,Position)
).
Theresultofthisautomatictransformationrevealstwomalpractices:thefirstisproduc-ingoutputbeforethecommit,somethingO’Keefehimselfdisapprovesofin(1994).Thismalpracticeandthewaystoresolveitarefurtherinvestigatedin4.4.Theproblemisfixedto:
Listing3.3-Outputaftercommit
reader_code(Term,Stream,State):-(Term=end_of_file->
State=end_of_file
;
State=read(Term,Stream,Position),
Asdefinedine.g.(O’Keefe1994):acutthataltersthemeaning.
1
ImprovingPrologPrograms:RefactoringforProlog
stream_position(Stream,Position)
).
5
Thesecondmalpracticeisaunificationintheconditionoftheif-then-elsewhereanequalitytestismeant.ConsiderthecasethattheTermargumentisavariable.ThenthebindingofTermtotheatomendoffileiscertainlyunwantedbehavior.Thetransfor-mationinquestionisdiscussedinSection4.4.Thefollowingcodedoesnotexhibittheproblematicbehavior:
Listing3.4-Equalitytest
reader_code(Term,Stream,State):-(Term==end_of_file->
State=end_of_file
;
State=read(Term,Stream,Position),stream_position(Stream,Position)
).
Next,wenoticethattheconjunctionread/2,readercode/3occurstwice.Byapply-ingpredicateextraction(Section4.4)ofthiscommonsequence,weget:
Listing3.5-Predicateextraction
make_reader(File,Stream,State):-open(File,read,Stream),
read_next_state(Stream,State).reader_next(Term,read(Term,Stream,Pos),State)):-stream_position(Stream,_,Pos),read_next_state(Stream,State).read_next_state(Stream,State):-read(Stream,Term),
reader_code(Term,Stream,State).
Nextweputtheinputargumentfirstandtheoutputargumentslast(Section4.3below),aprinciplealsoadvocatedin(O’Keefe1994):
Listing3.6-Argumentreordering
reader_next(read(Term,Stream,Pos),Term,State):-stream_position(Stream,_,Pos),read_next_code(Stream,State).
Finally,notethatthenamingofthetwobuiltinsstreamposition/[2,3]maybecon-fusingtotheuser.Itiseasiertodistinguishbetweentheirfunctionalitybasedonpredicatenamethanbasedonarity.Weintroducethelessconfusingnamesgetstreamposition/2andsetstreamposition/3respectively.Inaddition,weprovideamoreconsistentnam-ingformakereader,moreinlinewiththeothertwopredicatesintheinterface.Theim-portanceofconsistentnamingconventionsisalsostressedin(O’Keefe1994).
Notethatdirectrenamingofbuilt-inssuchasstreampositionisnotpossible,butasimilareffectcanbeachievedbyextractingthebuilt-inintoanewpredicatewiththede-siredname.ExtractingapredicateandrenamingpredicatesareconsideredinSections4.4and4.3,respectively.
6AlexanderSerebrenik,TomSchrijversandBartDemoen
Inordertoavoidconfusionbetweenabuilt-inpredicatereadandafunctorreadwerenamethelatterfunctortoreader.
Listing3.7-Renaming
reader_init(File,Stream,State):-open(File,read,Stream),
reader_next_state(Stream,State).
reader_next(reader(Term,Stream,Pos),Term,State)):-set_stream_position(Stream,Pos),reader_next_state(Stream,State).reader_done(end_of_file).
reader_next_state(Stream,State):-read(Stream,Term),
build_reader_state(Term,Stream,State).build_reader_state(Term,Stream,State):-(Term==end_of_file->
State=end_of_file
;
State=reader(Term,Stream,Position),get_stream_position(Stream,Position)
).set_stream_position(Stream,Position):-stream_position(Stream,_,Position).
get_stream_position(Stream,Position):-stream_position(Stream,Position).
Thisexampledemonstrateshowthecodereadabilitycanbeamelioratedbyperformingaseriesofrelativelysimpletransformationsteps.Wehaveseenthatsomeofthesestepsrequireduser’sinput.Clearlythechangescanbeperformedmanually.However,refac-toringbrowsersshouldbeabletoguaranteeconsistency,correctnessandfurthermorecanautomaticallysingleoutopportunitiesforrefactoring.
Techniquesappliedabovearewell-suitedforlocalcodeimprovement,i.e.,theobjectsmodifiedarepredicatesandclauses.Inthenextsectionwealsoconsidertechniquesforglobalcoderestructuringsuchasduplicatepredicatesremoval(Section4.1).
4ACatalogueofPrologrefactorings
InthissectionwepresenttherefactoringsthatwehavefoundtobeusefulforPrologprograms.TheconsideredPrologprogramsarenotlimitedtopurelogicprograms,butmaycontainvariousbuilt-inssuchasthosedefinedintheISOstandard(1995).Theonlyexceptionarehigher-orderconstructsthatarenotdealtwithautomatically,butmanually.Thisisdoneduetothefactthathigherorderconstructssuchascallmakeitimpossibletodecideatthecompile-timewhichpredicateisgoingtobecalledatthecorrespondingprogrampointduringexecution.Automatingthedetectionandhandlingofhigher-orderpredicatesisanimportantpartoffuturework.
ImprovingPrologPrograms:RefactoringforProlog7
Therefactoringsinthiscataloguearegroupedbytheirscope.Thescopeexpressestheuser-selectedtargetofaparticularrefactoring.Hence,refactoringstartsbychoosinganobjectinthespecifiedscope.Forinstance,splitmodule(Section4.2)startswithselectingamodule.Thentheobjectistransformed.Forus,thismeansthatthemoduleissplit.Finally,thechangespropagatetotheaffectedcodeoutsidetheselectedscope.Thelattermighthappenwhenthereisadependencyoutsidethescope.Thiscorrespondstoupdatingimportdeclarationsinothermodulesofthesystem.
ForPrologprogramswedistinguishthefollowingfourscopes,basedonthecodeunitsofProlog:systemscope(Section4.1),modulescope(Section4.2),predicatescope(Section4.3)andclausescope(Section4.4).
AsastartingpointforthiscatalogueweusedFowler’s(2003)forobject-orientedlan-guages.WeselectedthosewithclearPrologcounterparts,extendedthelistwithProlog-specifictransformationsandsomewell-knownprogramtransformations,suchasdeadcodeelimination.
Inthecurrenttechnicalnoteweonlyincludeashortsummaryoftherefactoringshereandrefertothecompaniontechnicalreport(Schrijversetal.2003).Thisreportcontainsthefullcataloguewithdetaileddescriptionoftherefactorings,examples,preconditionsandautomatizationtechniques.
4.1SystemScopeRefactorings
Thesystemscopeencompassestheentirecodebase.Theuserwantstoconsiderthesystemasawhole.
4.1.1Eliminateexplicitmodulequalification
InmanyPrologsystems,suchasQuintus(IntelligentSystemsLaboratory2003a),themodulesystemisnon-strict,i.e.thenormalvisibilityrulescanbeoverriddenbyaspecialconstruct,calledexplicitmodulequalificationandwrittenasm:q,wheremisamodulethatcontainsdefinitionofthepredicateq/0.Therefactoringproposedaddsimportandexportdeclarationstogetridofthesespecialsyntaxconstructions.Byforcingthecodetoconformtoastrictmodulesystemanumberofqualitycharacteristicsareimproved.Firstofall,astrictmodulesystembetterexpressestheideaofinformationhiding,whichisimportantforsoftwaremaintainabilityandreadability(Parnas1972).Moreover,sincenotallPrologsystemssupporttheaboveconstruct,codeportabilityisimproved.
4.1.2Extractcommoncodeintopredicates
Thisrefactoringlooksforcommonfunctionalityacrossthesystemandextractsitintonewpredicates.Thecommonfunctionalityconsistsofidenticalsubsequencesofgoalsthatarecalledindifferentpredicatebodies,andextractsthemintonewpredicates.Theoverallreadabilityoftheprogramimprovesastheaffectedpredicatebodiesgetshorter,andthecallstothenewpredicatescanbemoremeaningfulthanwhattheyreplace.Moreovertheincreasedsharingsimplifiesmaintenanceasnowonlyonecopyneedstobemodified.Theproblemofidentifyingidenticalsubsequencesofofgoalsisrelatedtodetermininglongestrepeatedsubsequences(CrowandSmith1992;PitkowandPirolli1999).4.1.3Hidepredicates
8AlexanderSerebrenik,TomSchrijversandBartDemoen
Thisrefactoringremovesexportdeclarationsforpredicatesthatarenotimportedinanyothermodule.Itsimplifiestheprogrambyreducingthenumberofentrypointsintomod-ulesandhencetheintermoduledependencies.
4.1.4Removedeadcode
Deadcodeiscodethatcanneverbeexecutedandthereforecanbesafelyeliminatedwithoutaffectingcorrectnessoftheexecution.Deadcodeeliminationissometimesper-formedincompilersforefficiencyreasons,butitisalsousefulfordevelopers:deadcodeclutterstheprogram.Weconsiderapredicatedefinitionastheunitofdeadcode.4.1.5Removeduplicatepredicates
Predicateduplicationorcloningisawell-knownproblem,prominentlycausedby“copy&paste”andunawarenessofavailablelibrariesandexportedpredicatesinothermodules.Themainproblemwithduplicationisitsbadmaintainability.Itisuptotheusertodecidewhethertothrowawaysomeoftheduplicatesandtouseoneoftheremainingdefinitionsinsteadortoreplacealltheduplicatepredicatesbyanewversioninanewmodule.4.1.6Renamefunctor
Thisrefactoringrenamesatermfunctoracrossthesystem.Ifthefunctorhasseveraldifferentmeaningsandonlyoneshouldberenamed,itisuptotheusertoidentifywhatoccurrencecorrespondswithwhatmeaning.
4.2ModuleScopeRefactorings
Themodulescopeconsidersaparticularmodule.Usuallyamoduleisimplementingawell-definedfunctionalityandistypicallycontainedinonefile.
4.2.1Mergemodules
Mergingseveralmodulesintoonecanbeadvantageousincaseofstronginterdepen-dencyofthemodulesinvolved.Moreover,mergingexistingmodulesandsplittingthere-sultingmodulecanleadtoanimprovedmodulestructure.
4.2.2Removedeadintra-modulecode
Similartodeadcoderemovalforanentiresystem(seeSection4.1),thisrefactoringworksatthelevelofasinglemodule.Itisusefulforincompletesystemsorlibrarymoduleswithanunknownnumberofuses.Recallthatdeterminingthelivenessofthecoderequiresknowledgeoftop-levelpredicates.Inthecaseofintra-moduledeadcodeelimination,thesetoftoplevelpredicatesisextendedwith,orreplacedby,theexportedpredicatesofthemodule.
4.2.3Renamemodule
Thisrefactoringapplieswhenthenameofthemodulenolongercorrespondstothefunctionalityitimplementse.g.duetootherrefactorings.4.2.4Splitmodule
ImprovingPrologPrograms:RefactoringforProlog9
Therefactoringisusefultosplitunrelatedpartsofamoduleormakealargemodulemoremanageable.
Moores(Moores1998)hasshownthatthenumberofuser-definedpredicatescorrelateswiththenumberoferrorsdetected.Basedonanempiricalstudyhesuggestedathresholdofaround35±5predicatesperprogram.WhilethisishardlyreasonableasarequirementforanentirePrologsystem,trespassingthethresholdshouldbeusedasaguidelinewhentheSplitModulerefactoringcanbeapplied.
4.3PredicateScopeRefactorings
Thepredicatescopetargetsasinglepredicate.Thecodethatdependsonthepredicatemayneedupdatingaswell.Butthisisconsideredanimplicationoftherefactoringofwhicheithertheuserisalertedorthenecessarytransformationsareperformedautomatically.4.3.1Addargument
Thisrefactoringshouldbeappliedwhenacalleeneedsmoreinformationfromits(directorindirect)caller,whichisverycommoninPrologprogramdevelopment.Givenavariableinthebodyofthecallerandthenameofthecallee,therefactoringbrowsershouldprop-agatethisvariablealongallpossiblecomputationpathsfromthecallertothecallee.Thisrefactoringisanimportantpreliminarystepprecedingadditionalfunctionalityintegrationorefficiencyimprovement.
4.3.2Movepredicate
Thisrefactoringmovesapredicatedefinitionfromonemoduletoanother.Itcanimprovetheoverallstructureoftheprogrambybringingtogetherinterdependentorrelatedpredi-cates,henceimprovingbothcohesionofeachoneofthemodulesinvolved,andcouplingofthepair.Movepredicateappearsoftenafterpredicateextraction,i.e.,extractcommoncodeorextractpredicatelocally,discussedinSections4.1and4.4,respectively.
4.3.3Renamepredicate
Thisrefactoringcanimprovereadabilityandshouldbeappliedwhenthenameofapredicatedoesnotrevealitspurpose.
4.3.4Reorderarguments
OurexperiencesuggeststhatwhilewritingpredicatedefinitionsPrologprogrammerstendtobeginwiththeinputargumentsandtoendwiththeoutputarguments.ThishabithasbeenidentifiedasagoodpracticeandevenfurtherrefinedbyO’Keefe(1994)tomoreelaboraterules.Unfortunately,thispracticeisdifficulttomaintainwhenadditionalargu-mentsareaddedlater.Weobservedthatfailuretoconfirmtothis“inputfirstoutputlast”expectationpatternisexperiencedasveryconfusing.
4.3.5Specializepredicate
Byspecializingapredicatewemeanproducinga(numberof)morespecificversion(s)ofagivenpredicateprovidedsomeknowledgeontheintendedusesofthepredicate.Spe-
10AlexanderSerebrenik,TomSchrijversandBartDemoen
cialisationcansimplifycodeaswellasmakeameaningfuldistinctionbetweendifferentusesofapredicate.
4.3.6Removeredundantarguments
Thebasicintuitionhereisthatparametersthatarenolongerusedbyapredicateshouldbedropped.Itimprovesreadability.
LeuschelandSørensen(1996)establishedthattheredundancypropertyisundecid-ableandsuggestedtwotechniquestofindsafeandeffectiveapproximations:top-downgoal-orientedRAF(RedundantArgumentFiltering)andbottom-upgoal-independentFAR(RAF“upside-down”).InthecontextofrefactoringFARisthemoreusefultechnique,sinceonlyFARdealscorrectlywithexportedpredicatesusedinunknowngoals.
4.4ClauseScopeRefactorings
Theclausescopeaffectsasingleclauseinapredicate.Usually,thisdoesnotaffectanycodeoutsidetheclausedirectly.
4.4.1Extractpredicatelocally
Thisrefactoringissimilartothesystem-scoperefactoringwiththesamename.However,itdoesnotaimtoautomaticallydiscoverusefulcandidatesforreplacement.Theuserisresponsibleforselectingthesubgoalthatshouldbeextracted,inordertoimprovethereadability.
4.4.2Invertif-then-else
Theorderof“then”and“else”branchescanbeimportantforcodereadability.Toen-hancereadabilityitmightbeworthwhileputtingtheshorterbranchas“then”andthelongeroneas“else”.Alternatively,thenegationoftheconditionmaybemorereadablebecause,forexample,adoublenegationcanbeeliminated.
4.4.3Replacecutbyif-then-else
Thistechniqueaimsatimprovingprogramreadabilitybyreplacingcuts(!)bythemoredeclarativeif-then-else(->;).Moredetaileddiscussiononreplacingcutbyif-then-elseisdeferredtoRelatedworkandextensions.
4.4.4Replaceunificationby(in)equalitytest
Oftenfullunificationsareusedinsteadofequalityorothertests.O’Keefein(1994)advocatestheimportanceofsteadfastcode.Recall,thatsteadfastcodeproducestherightanswersforallpossiblemodesandinputs.Amoremoderateapproachistowritecodethatworksfortheintendedmodeonly.Unificationsucceedsinseveralmodesandsodoesnotconveyaparticularintendedmode.Equality(==,=:=)andinequality(\\==,=\\=)checksusuallyonlysucceedforoneparticularmodeandfailorraiseanerrorforothermodes.Hencetheirpresencemakesiteasierinthecodeandatruntimetoseetheintendedmode.Moreover,ifonlyacomparisonwasintended,thenfullunificationmayleadtounwantedbehaviourinunforeseencases.4.4.5Produceoutputaftercommit
ImprovingPrologPrograms:RefactoringforProlog11
Thisrefactoringaddressesasimilarissueasthepreviousone.Producingoutputbeforethecommit(cut)doesnotproperlyconveytheintendedmodeofapredicate.Moreoveritmayleadtounexpectedresultswhenusedinthewrongmode.
5TheViPReSSrefactoringbrowser
TherefactoringtechniquespresentedinSection4havebeenimplementedintheprototyperefactoringbrowserViPReSS2.IthasbeenimplementedonthebasisofVIM,apopularcloneofthewell-knownVIeditor.ThetexteditingfacilitiesofVIMmakeiteasytoim-plementtechniqueslikemovepredicate(Section4.3).
MostoftherefactoringtaskshavebeenimplementedasSICStusProlog(IntelligentSystemsLaboratory2003b)programsinspectingsourcefilesand/orcallgraphs.UpdatestofileshavebeenimplementedeitherdirectlyinthescriptinglanguageofVIMor,whenmanyfilesneedupdatingatonce,throughedscripts.VIMfunctionswerewrittentoinitiatetherefactoringsandtogetuserinput.
ViPReSShasbeensuccessfullyappliedtoalarge(morethan53KLOC)legacysystemusedattheComputerSciencedepartmentoftheKatholiekeUniversiteitLeuventomanagetheeducationalactivities.Thesystem,calledBTW,hasbeendevelopedandextendedsincetheearlyeightiesbymorethantenprogrammers,manyofwhomarenolongeremployedbythedepartment.TheimplementationhasbeendoneinMasterProLog(ITMasters2000),whichisnolongersupported.Therefore,preparingthecodeformigrationtoamoremod-ernPrologdialectandgeneralstructureimprovementwereessentialforfurtherevolutionofthesystem.
Byusingtherefactoringtechniqueswesucceededinobtainingabetterunderstandingofthisreal-worldsystem,inimprovingitsstructureandmaintainability,andinpreparingitforintendedchanges:portingittoastate-of-the-artPrologsystemandadaptingittoneweducationaltasksthedepartmentisfacingasapartoftheunifiedBachelor-MastersysteminEurope.
Apreliminarystudyrevealedthatmanymoduleswereunused.Webroughtinanexperttohelpusidentifythebulkoftheseunusedmodules,includingout-of-fashionuserinter-facesandoutdatedversionsofprogramfiles.Thisreducedthesystemsizetoamere20,000lines.
Next,theactualrefactoringprocesswasstarted.Asthefirstphaseweappliedsystem-scoperefactorings.ViPReSSwasusedtocleanupafterthebulkdeadcoderemoval:299predicatesintheremainingmoduleswereidentifiedasdead.Thisreducedthesizebyanother1,500lines.MoreoverViPReSSdiscovered79pairwiseidenticalpredicates.Inmostofthecases,identicalpredicatesweremovedtonewmodulesusedbytheoriginalones.Thepreviousstepsallowedustoimprovetheoverallstructureoftheprogrambyreducingthenumberoffilesfrom294to116withatotalof18,000lines.Verylittletimewasspenttobringthesystemintothisstate.Theexpertsweresufficientlyfamiliarwiththesystemtoidentifyobsoleteparts.Thesystem-scoperefactoringstookonlyafewminutes
2
Vi(m)P(rolog)Re(factoring)(by)S(chrijvers)(and)S(erebrenik)
12AlexanderSerebrenik,TomSchrijversandBartDemoen
each.DuringthisphasemostoftheworkhasbeendonebyViPReSS,whiletheuser’sinvolvementwaslimitedtochoosingawaytodealwithduplicatepredicates.
Thesecondphaseofrefactoringconsistedofathoroughcodeinspectionaimedatlocalimprovement.Manymalpracticeswereidentified:excessiveuseofcut(Section4.4)com-binedwithoutputconstructionbeforecommit(Section4.4)beingthemostnotableone.Additional“badsmells”discoveredincludebadpredicatenamessuchasq,unusedargu-mentsandunificationsinsteadofidentitychecksornumericalequalities(Sections4.3,and4.4,respectively).SomeofthesewerelocatedbyViPReSS,otherswererecognisedbytheusers,whileViPReSSperformedthecorrespondingtransformations.Thisstepismorede-mandingoftheuser.Shehastoconsiderallpotentialcandidatesforrefactoringseparatelyanddecideonwhattransformationsapply.Hence,thelion’sshareoftherefactoringtimeisspentontheselocalchanges.
Insummary,fromthecasestudywelearnedthatautomaticsupportforrefactoringtech-niquesisessentialandthatViPReSSiswell-suitedforthistask.AstheresultofapplyingrefactoringtoBTWweobtainedbetter-structuredlumber-freecode.Nowitisnotonlymorereadableandunderstandablebutitalsosimplifiesimplementingtheintendedchanges.Fromourexperiencewithrefactoringthislargelegacysystemandtherelativetimein-vestmentsoftheglobalandthelocalrefactorings,werecommendstartingoutwiththeglobalonesandthenselectivelyapplylocalrefactoringsastheneedoccurs.ThecurrentversionofViPReSScanbedownloadedfromhttp://www.cs.kuleuven.ac.be/˜toms/vipress.
6Conclusions
InthispaperwehavestudiedrefactoringtechniquesforProlog.Firstly,wehaveshownthatrefactoringisaviabletechniqueforPrologandthatmanyoftheexistingtechniquesdevelopedforrefactoringingeneralareapplicable.Ourrefactoringcataloguecontainsmanysuchrefactorings.
Secondly,Prolog-specificrefactoringsarepossibleandtheapplicationofsomegeneraltechniquesmaybehighlyspecializedtowardsProlog.Inthiscontext,thecompaniontech-nicalreport(Schrijversetal.2003)showshowrefactoringfitsinwithexistingworkonprogramanalysisandtransformationinthecontextofPrologandhowmanyoftheseex-istingtechniquesmaybeadaptedforthepurposeofpartiallyautomatingtherefactoringprocess.Also,ViPReSS,ourrefactoringbrowserintegratesseveralautomatablepartsofthepresentedrefactoringsintheVIMeditor.
Finally,itshouldbeclearthatrefactoringPrologprogramsisnotjustviablebutveryusefulforthemaintenanceofPrologprograms.Refactoringhelpsbridgethegapbetweenprototypesandreal-worldapplications.Indeed,extendingaprototypetoprovideadditionalfunctionalityoftenleadstocumbersomecode.Refactoringallowssoftwaredevelopersbothtocleanupcodeafterchangesandtopreparecodeforfuturechanges.Theseareimportantbenefitsthatalsoapplytologicprogramming.
Ascompletenessofthecatalogueisclearlynotpossible,weaimedtoshowawiderangeofpossibilitiesforfutureworkoncombiningtheformaltechniquesofprogramanalysisandtransformationwithsoftwareengineering.Throughoutthecataloguemanyspecific
ImprovingPrologPrograms:RefactoringforProlog13
issuesforfutureworkhavebeenmentioned.Belowwelistrelatedworkandmoregeneralchallengesforthefuture.
6.1RelatedandFutureWork
Logicprogramminghasoftenbeenusedtoimplementrefactoringsforotherlanguages,e.g.ameta-logicverysimilartoPrologisusedtodetect,forinstance,obsoleteparametersin(Tourw´eandMens2003).
Seipeletal.(2003)includerefactoringamongtheanalysisandvisualizationtechniquesthatcanbeeasilyimplementedbymeansofFNQUERY,aProlog-inspiredquerylanguageforXML.However,thediscussionstaysatthelevelofanexample.TheM.Sc.thesisofSteinke(2003)wasdedicatedtorefactoringoflogicprograms.ACatalogueofrefactor-ingshasbeencomposedandaprototypesystemhasbeenimplemented.However,onlypredicate-scoperefactoringshavebeenconsideredandonlythetransformationstephasbeenimplemented.
Inthelogicprogrammingcommunityquestionsrelatedtorefactoringhavebeeninten-sivelystudiedinthecontextofprogramtransformationandspecialisation.Therearetwoimportantdifferenceswiththislineofwork.Firstly,refactoringimprovesreadability,main-tainabilityandextensibilityratherthanperformance.Secondly,forrefactoringuserinputisessentialwhileinthementionedliteraturestrictlyautomaticapproacheswereconsidered.However,someofthetransformationsdevelopedforprogramoptimization,e.g.deadcodeelimination,canbeconsideredasrefactoringsandhaveanimportantfunctioninrefactor-ingbrowsers.
Tofurtherincreasethelevelofautomationofparticularrefactoringsadditionalinforma-tionsuchastypesandmodescanbeused.
FuturerefactoringtoolscanalsobenefitfromintegrationwithPrologdevelopmenten-vironments.ModernPrologsystemsareoftenequippedwithfeaturesextendingtheISOStandardsuchasconstraintsolvingoverdifferentdomainsandConstraintHandlingRules,coroutining,interfacestoforeignlanguages,GUI-developmentsystemsanddatabases.Inmostofthecases,therefactoringtechniquesdescribedabovecanstillbeappliedtoim-provethecode.Certainrefactoringsmaybespeciallydesignedforparticularextensions.Forinstance,ourexperiencesuggeststhatsimplifyingprimitiveconstraintsmaybeusefulinthecaseofCLP.
References
1995.Informationtechnology—Programminglanguages—Prolog—Part1:Generalcore.ISO/IEC.ISO/IEC13211-1:1995.
CROW,D.ANDSMITH,B.1992.Dbhabits:comparingminimalknowledgeandknowledge-basedapproachestopatternrecognitioninthedomainofuser-computerinteractions.39–63.
ERLIKH,L.2000.Leveraginglegacysystemdollarsfore-business.ITProfessional2,3(May),17–23.
FOWLER,M.2003.Refactoringsinalphabeticalorder.Availableathttp://www.refactoring.com/catalog/.
FOWLER,M.,BECK,K.,BRANT,J.,OPDYKE,W.,ANDROBERTS,D.1999.Refactoring:improv-ingthedesignofexistingcode.ObjectTechnologySeries.Addison-Wesley.
14AlexanderSerebrenik,TomSchrijversandBartDemoen
GARRIDO,A.ANDJOHNSON,R.2003.RefactoringCwithconditionalcompilation.In18thIEEEInternationalConferenceonAutomatedSoftwareEngineering,H.KirchnerandC.Ringeissen,Eds.IEEE,323–326.
HERMENEGILDO,M.V.2000.Adocumentationgeneratorfor(c)lpsystems.InComputationalLogic-CL2000,FirstInternationalConference,London,UK,July2000,Proceedings,J.Lloyd,V.Dahl,U.Furbach,M.Kerber,K.-K.Lau,C.Palamidessi,L.MonizPereira,Y.Sagiv,andP.J.Stuckey,Eds.LectureNotesinArtificialIntelligence,vol.1861.SpringerVerlag,1255–1269.INTELLIGENTSYSTEMSLABORATORY.2003a.QuintusPrologUser’sManual.POBox1263,SE-16429Kista,Sweden.
INTELLIGENTSYSTEMSLABORATORY.2003b.SICStusPrologUser’sManual.POBox1263,SE-16429Kista,Sweden.
ITMASTERS.2000.MasterProLogProgrammingEnvironment.www.itmasters.com.
LEUSCHEL,M.ANDSØRENSEN,M.H.1996.Redundantargumentfilteringoflogicprograms.InProceedingsofthe6thInternationalWorkshoponLogicProgramSynthesisandTransformation,J.Gallagher,Ed.LNCS,vol.1207.SpringerVerlag,83–103.
LI,H.,REINKE,C.,ANDTHOMPSON,S.2003.Toolsupportforrefactoringfunctionalprograms.InHaskellWorkshop2003,J.Jeuring,Ed.AssociationforComputingMachinery.
´,T.2004.Asurveyofsoftwarerefactoring.IEEETransactionsonSoftwareMENS,T.ANDTOURWE
Engineering30,2(February),126–138.
MOAD,J.1990.Maintainingthecompetitiveedge.Datamation36,4(February),61–66.
MOORES,T.T.1998.Applyingcomplexitymeasurestorule-basedPrologprograms.TheJournalofSystemsandSoftware44,45–52.
NOSEK,J.T.ANDPALVIA,P.C.1990.Softwaremaintenancemanagement:changesinthelastdecade.JournalofSoftwareMaintenance:ResearchandPractice2,3(September),157–174.O’KEEFE,R.A.1994.TheCraftofProlog.MITPress,Cambridge,MA,USA.
OPDYKE,W.F.1992.Refactoringobject-orientedframeworks.Ph.D.thesis,UniversityofIllinoisatUrbana-Champaign.
PARNAS,D.L.1972.Onthecriteriatobeusedindecomposingsystemsintomodules.Communi-cationsoftheACM15,12(Dec.),1053–1058.
PITKOW,J.ANDPIROLLI,P.1999.Removingredundantargumentsoffunctions.In2ndUSENIXsymposiumonInternettechnologiesandsystems.1–12.
ROBERTS,D.,BRANT,J.,ANDJOHNSON,R.1997.ArefactoringtoolforSmalltalk.TheoryandPracticeofObjectSystems(TAPOS)3,4,253–263.
SCHRIJVERS,T.,SEREBRENIK,A.,ANDDEMOEN,B.2003.RefactoringPrologprograms.Tech.Rep.CW373,DepartmentofComputerScience,KatholiekeUniversiteitLeuven,Leuven,Bel-gium.
SEIPEL,D.,HOPFNER,M.,ANDHEUMESSER,B.2003.AnalysingandvisualizingPrologpro-gramsbasedonXMLrepresentations.InProceedingsofthe13thInternationalWorkshoponLogicProgrammingEnvironments,F.MesnardandA.Serebrenik,Eds.31–45.Publishedastech-nicalreportCW371ofKatholiekeUniversiteitLeuven.
STEINKE,D.2003.RefactoringvonlogischenProgram-men.M.S.thesis,Universit¨atRostock.Availableat
http://e-lib.informatik.uni-rostock.de/fulltext/2003/diploma/SteinkeDirk-2003.ps.gz.
´,T.ANDMENS,T.2003.Identifyingrefactoringopportunitiesusinglogicmetaprogram-TOURWE
ming.In7thEuropeanConferenceonSoftwareMaintenanceandReengineering,Proceedings.IEEEComputerSociety,91–100.
VAN
VLIET,H.2000.Softwareengineering:principlesandpractice.JohnWiley&sons.Secondedition.
ImprovingPrologPrograms:RefactoringforProlog15
VANHOOF,W.2004.Searchingsemanticallyequivalentcodefragmentsinlogicprograms.InLogic-basedProgramSynthesisandTransformation.14thinternationalworkshop,LOPSTR2004,Verona,Italy,August26-28,2004,Pre-Proceedings,S.Etalle,Ed.1–18.
因篇幅问题不能全部显示，请点此查看更多更全内容