Implementing Logic Programming Languages By Graph

ImplementingLogicProgrammingLanguagesByGraphRewritingPeterMc.BrienMarch1992TheImperialCollegeofScience,TechnologyandMedicineDepartmentofComputing180Queen'sGateLondonSW72BZ©1992,PeterMc.BrienSubmittedtotheUniversityofLondoninpartialfulfilmentoftherequirementsforthedegreeofDoctorofPhilosophyPage2AbstractTheuseofgraphrewritingasacomputationalmodelforcomputerprogramminglanguageshasreceivedconsiderableattentioninthescientificliteratureoverthepastdecade.Whilsttheimplementationoffunctionalprogramminglanguagesbygraphrewritingissimpleandintuitive,theimplementationoflogicprogramminglanguagesislessdirectandconsequentlyhasbeenmorelimitedinpractice.Afterdescribingsomeoftheproblemsassociatedwitha‘direct’approachtoimplement-inglogicprogrammingbygraphrewriting,andcomparingthesituationtothatfoundwhenusingtermrewriting,thisthesissetsouttoaddresstheproblemsbyproposingtwoinnovations.Thefirstisamodifiedformofgraphrewriting,whichsupportssomefeaturesoftermrewriting,anddirectlysupportsthenotionofthelogicalvariableandbacktrackingonvariables.Thesecondisacompilertargetlanguageandcorrespondingabstractmachine,whichefficientlyimplementssuchmodifiedgraphrewritingonconventionalVonNeumanncomputerarchitectures.Aproofthattheabstractmachinecorrectlyimplementsthecompilertargetlanguageisgiven.TheapproachisillustratedbydemonstratinghowitmaybeusedtoimplementbothPrologandamorenovellogicprogramminglanguagecalledthePLL.Thegraphrewritinglanguageanditsassociatedabstractmachinehavebeenthesubjectofanimplementationinthe‘C’language,andthustheresultsdescribedwithinthisthesishavebeenrealizedinpractice.Issuesrelatingtotheuseofthetechniquesdescribedonaparallelcomputerarchitecturearealsobrieflydealtwith,butnopracticalworkhasbeenconductedinthisdirection.Page3Page4TableofContentsIntroduction9ExecutingLogicUsingGraphRewriteRules................10OutlineofChapters....................................13HistoryandPublicationoftheMaterialinthisThesis..........151:Background171.1TermRewriteSystems....................................................................171.1.1TermsandTermRewrites..........................171.1.2NormalForms&Confluency........................211.1.3ReductionStrategies................................231.2GraphRewriteSystems...................................................................231.2.1Graphs..........................................231.2.2GraphRewriting..................................271.2.3TreesRepresentingTerms..........................311.2.4TheRelationshipBetweenTRSandGRS..............321.2.5AdvantagesofUsingaGraphicalRepresentation........331.3CompilerTargetLanguages............................................................341.3.1Dactl............................................351.3.2Lean............................................391.4AbstractMachines...........................................................................401.4.1G-Machine......................................411.4.2WAM..........................................49Summary&Conclusions......................................................................582:GraphRewriting&LogicProgrammingLanguages612.1TheLogicalVariable......................................................................642.1.1IdentityFunctionsandNodes........................652.2UnificationofGraphs......................................................................692.3LogicalDisjunctions.......................................................................722.3.1PhantomVariableBindings..........................722.3.2PhantomRewrites................................742.3.3TermRewritesonGraphs..........................782.3.4UsingTermandGraphRewrites......................79Summary&Conclusions......................................................................83Page53:TAM-RewriteRules853.1TheRewriteAlgorithm...................................................................893.2TAMRewriteRules........................................................................903.2.1TAMSyntax....................................903.2.2GraphicalRepresentationofTAMExpressions..........913.2.3HeadofRewriteRules..............................933.2.4ConditionalExpressions............................943.2.5BodyofRewriteRules..............................983.3AnImplementationofProlog.........................................................993.3.1SLDResolution..................................993.3.2PrologPredicates................................1013.3.3PosingaQueryandReturningtheResult..............1023.3.4Backtracking....................................1033.3.5Cut............................................1063.3.6NegationByFailure..............................1073.4AnImplementationofthePLL.....................................................1083.4.1Conjunctions....................................1093.4.2Equality&Arithmetic............................1113.4.3ConditionalOperators............................1123.4.4PosingaQueryandReturningtheResult..............1123.4.5Disjunctions.............................