Turbo Prolog Owners Handbook

April 6, 2018 | Author: Anonymous | Category: Documents
Share
Report this link


Description

to your IBM- PC. Turbo Prolog introduces you to the brave new rtllldlia YoueWilYlhit11lyouneed to know aboutthis fascinating new ManlMachine. TurboProlog Owner'sHandbook Copyright1986by BorlandInternational,Inc. 4585ScottsValleyDrive ScottsValley.CA95066 USA Table ofContents Introduction HowtoUseThisBook TheDistributionDisks MinimumSystemRequirements Acknowledgments..... ChapterIAboutProlog What CanTurboPrologbeUsedFor? HowDoesTurboPrologDifferFromOther Languages? Chapter2A ShortIntroductiontotheTurboPrologSystem TheMainMenu........... EnteringYourFirstTurboPrologProgram EditorSurvivalKit. BasicOperation. BlockOperations SearchandReplace Tracing..... Altering theDefaultWindow Setup Temporary Changesto Windows Savinga WindowLayout Chapter3TutorialI:FiveSimplePrograms TheStructure of A TurboPrologProgram Variables..... ObjectsandRelations DomainsandPredicates CompoundGoals AnonymousVariables FindingSolutionsinCompoundGoals-Backtracking TurboProlog theMatchmaker:UsingNot Comments.......... . A MoreSubstantialProgramExample Summary.......... . I I 2 2 2 3 .4 .4 .7 .7 .8 II II II 12 14 15 15 15 17 17 19 20 20 22 22 23 24 27 27 28 Chapter 4TutorialII:A CloserLookatDomains,ObjectsandLists33 FreeandBoundVariables.........33 TurboProlog'sStandard DomainTypes34 CompoundObjectsCanSimplifyYourClauses!38 DomainDeclarationof CompoundObjects38 GoingDowna Level40 Recursion.............42 RecursiveObjects.........44 TheFascinating Worlds of ListsandRecursion45 UsingLists.......46 ListMembership......47 WritingElementsof a List...48 AppendingOneListto Another: DeclarativeandProceduralProgramming48 OnePredicateCanHaveSeveralApplications49 Chapter 5TutorialIII:TurboProlog'sRelentlessSearchfor Solutions51 MatchingThingsUp:TheUnificationof Terms51 Controlling theSearchforSolutions....54 Useof Fail.............57 PreventingBacktracking:TheCutElement58 Using theCut toPreventBacktracking to a PreviousSubgoalina Rule.....58 Using theCut toPreventBacktracking to theNextClause59 DeterminismandtheCut..........60 Chapter 6TutorialIV: Arithmetic,SimpleInputandOutput, andDebugging63 Prolog cando ArithmeticToo!.........63 TheOrder of Evaluationof ArithmeticExpressions64 Comparisons........64 SpecialConditions forEquality66 ArithmeticFunctionsandPredicates68 SimpleInputandOutput69 Writing.....69 Reading.... ..72 Debugging andTracing74 SomePredicates areSpecial75 AnExerciseinTracing75 Chapter 7TutorialV:SeeingThroughTurboProlog'sWindows77 Setting the ScreenDisplayAttributes77 WindowsinYourPrograms...78 ReadandWrite WithWindows80 Screen-BasedInputandOutput82 A SimpleArcadeGame.....83 A WordGuessing GameUsingWindows86 A Window ToDOS87 DateandTi me.........88 iiTurboPrologOwner's Handbook Chapter 8TutorialVI:GraphicsandSound TurboProlog'sGraphics TurtleGraphicsCommands Let'sHear TurboProlog Chapter 9TutorialVII:FilesandStrings TheTurboPrologFileSystem StringProcessing........ . TypeConversion StandardPredicates FindallandRandom....... . Chapter10TutorialVIII:SpreadingYourWings BuildingA SmallExpertSystem.... Prototyping:A SimpleRoutingProblem Adventuresina DangerousCave HardwareSimulation..... Towers of Hanoi..... . Divisionof WordsIntoSyllables TheN QueensProblem UsingTheKeyboard..... ChapterI IProgrammer'sGuide AnOverview of theTurboProlog System BasicLanguageElements Names..... ReservedNames RestrictedNames ProgramSections DomainDeclarations ShorteningDomainsDeclarations PredicateDeclarations Clauses..... SimpleConstants Variables CompoundTermsor Structures TurboPrologMemoryManagement CompilerDirectives check_cmpio check_determ code diagnostics include nobreak nowarnings project traceandshorttrace trail....... Tableof Contents 91 91 93 96 99 99 104 106 107 109 09 12 14 16 17 18 21 24 27 27 28 28 29 29 29 30 31 32 32 32 33 33 34 35 35 36 36 36 37 38 38 38 38 39 iii DynamicDatabasesinTurboProlog Declarationof theDatabase Handling Facts...... . Extending theDatabaseonto Files Control of Input andOutput Parameters:FlowPatterns Programmi ngStyle............... StackConsiderations andEliminatingTailRecursion Useof theFailPredicate.......... . Determinism,Non-determinism andHow to Setthe Cut DomainsContaining References.... Generating ExecutableStand-Alone Programs Modular Programming...... . Projects............ GlobalDomainsandGlobalPredicates Compiling andLinking theModules AnExample......... . Interfacing Procedures Written inOther Languages Declaring ExternalPredicates Calling Conventions andParameters... . Naming Conventions......... . AnAssemblerRoutineCalledfromTurbo Prolog Calling C.PascalandFORTRANProcedures from TurboProlog Low-LevelSupport.............. . Accessing theEditor From Within a TurboProlog Program edit.. display......... . editmsg......... . Directory andFormatting Facilities dir....... . writef......... Chapter12ReferenceGuide FilesontheDistributionDisk FilesNeededWhenUsing Turbo Prolog Installation..... TheMainMenu iv TheRunCommand TheCompile Command TheOptions Menu TheEdit Command TheFilesMenu Load Save Directory FileName ZapFileinEditor Print..... TurboProlog Owner's Handbook 140 140 141 142 144 145 145 148 149 149 151 152 152 153 154 154 155 156 56 56 57 59 59 61 61 61 61 62 62 62 63 63 64 64 164 164 165 166 166 166 166 167 167 167 168 168 Erase..... Rename Operating System SetupMenu DefiningDirectories Librarian.... WindowDefinition Color Setting.. Miscellaneous.. LoadConfiguration SaveConfiguration Quit Command.. TheTurboPrologEditor CursorMovementCommands Insert andDeleteCommands BlockCommands..... MiscellaneousCommands.. TheCalculationof ScreenAttributes MonochromeDisplayAdapter Color/Graphics Adapter ArithmeticFunctionsandPredicates ClassifiedIndexof StandardPredicates AlphabeticalDirectory of StandardPredicates asserta assertz attribute back beep bios bound char _int clearwindow closefile consult cursor. cursorform date deletefile dir disk. display dot. edit. editmsg eof.. existfile exit.. Tableof Contents 68 68 68 68 68 69 69 70 71 71 72 72 72 73 74 75 76 77 78 78 79 79 81 82 82 82 82 82 82 83 83 83 83 83 83 83 84 84 84 84 84 84 84 85 85 85 85 v fail field_attr field_str filepos file_str findall flush forward free.. frontchar frontstr fronttoken graphics is name left line.. makewindow membyte memword nl not... openappend openmodify openread openwrite pencolor pendown penup. portbyte ptr_dword readchar. read device readint readln. readreal readterm removewindow renamefile retract right save scr _attr scr _char shiftwindow sound. storage str_char viTurboPrologOwner's Handbook 85 85 85 86 86 86 87 87 87 87 87 87 88 88 88 88 88 89 89 89 89 89 89 90 90 90 90 90 90 90 91 91 91 91 91 91 91 91 92 92 92 92 92 92 92 93 93 str_int str_len str_real system text. time trace upper_lower window_attr window_str write writedevice writef.. BNFSyntaxforTurboProlog Names ProgramSection Directives DomainsSection PredicateandDatabase Section ClauseSection GoalSection Terms.. Comparisons CompilerDirectives SystemLimits... AppendixAASCIICharacter Codes AppendixBError Messages AppendixCPLINK Useof theFilePLlNK.BAT Contents of theFilePLlNK.BAT AppendixDPROLOG.SYS AppendixEUsingTurboPrologwithTurboPascal AppendixFGlossary............ Listof Figures 2-1TheLogonDisplay.......... . 2-2TheMainMenuandtheFour SystemWindows 2-3UsingtheEditor 2-4Executinga Program 3-1Backtracking... 4-1Evaluationof Factorial( 4,Answer) 10-1PrototypeMap..... 10-2FundamentalXORCircuit 10-3TheTowersof Hanoi 10-4TheN QueensChessboard I I-IMemoryPartitioninginTurboProlog Tableof Contents 193 193 193 194 194 194 194 194 194 195 195 195 195 196 196 197 197 197 198 198 199 199 199 196 ·200 .201 ·205 ·209 ·210 ·211 ·213 ·215 ·7 ·8 ·9 10 25 44 113 116 117 121 134 vii I 1-2SampleDiagnosticDisplay.... I 1-3ExampleUseof theIncludeDirective I I -4Useof trace I 1-5ActivationRecord I 1-6ActivationRecord 12-1OptionsMenu 12-2FilesMenu... 12-3SetupMenu 12-4WindowDefinitionMenu 12-5Color SettingsMenu 12-6MiscellaneousMenu Listof Tables 2-1 4-1 4-2 4-3 4-4 6-1 6-2 6-3 6-4 6-5 7-1 7-2 8-1 8-2 8-3 8-4 9-1 I I-I 11-2 12-1 12-2 12-3 12-4 12-5 12-6 viii Summaryof EditorKeystrokes StandardDomainTypes SimpleObjects... ListProcessing... ListMatching.... ArithmeticOperations Operator Priority.. RelationalOperators ArithmeticPredicates andFunctions StandardReadingPredicates MonochromeDisplayAdapter AttributeValues Color/Graphics Adapter Attribute Values GraphicsResolutionChoices PaletteChoicesinMediumResolution BackgroundColors TheComputer asPiano ModeandFileposition. KeywordContents T raceWindowMessages EditingCommandOverview MonochromeDisplayAdapter AttributeValues Color/Graphics Adapter Attribute Values ArithmeticPredicates andFunctions GraphicsScreenFormats CompilerDirectives....... TurboPrologOwner's Handbook 137 137 139 157 159 166 167 169 170 170 171 13 35 35 46 46 63 64 65 68 73 78 78 92 92 92 97 102 130 138 172 178 178 179 188 196 Introduction TurboPrologisa fifth-generationcomputerlanguagethat takesprogrammingintoa new dimension.Becauseof itsnatural,logicalapproach,both people new to program- ming andprofessionalprogrammerscanbuildpowerfulapplications-suchasexpert systems,customizedknowledgebases,naturallanguageinterfaces,andsmart informa- tionmanagement systems. TurboPrologisa declarativelanguage.Thismeansthat.giventhenecessaryfactsand rules,itcanusedeductivereasoningtosolveprogrammingproblems.Bycontrast, Pascal,BASIC andother traditionalcomputer languagesareprocedural: theprogram- mermust providestep-by-stepprocedures telling thecomputer how to solveprob- lems. The Prolog programmer need only supply a description of the problem (the goal) andthegroundrulesforsolvingit,andthePrologsystemwilldeterminehow to go about a solution. HOW TO USE THIS BOOK Thismanualisdesignedto servetwo different typesof reader:thosenew toProlog, andthosefamiliarwith theProlog language. If you're a new user of Prolog,youshouldfirst readChaptersIand2.ChapterItells youalittleabout theadvantagesof TurboProlog,andChapter2describeshow to enter programs into the system,how to have them compiled andexecuted and,finally, howtouseTurboProlog'suniquedebuggingfacilities.Youwillthenknowenough about Turbo Prolog to get going with the tutorials, which are presented inChapters 3- 10.Each tutorialchapter includes a variety of exercises to help youcheck your under- standing. If you're already familiar with Prolog,you canbegin with Chapter 2,which covers basic systemoperations,andthenmoveontoChapterII,whichdescribeshowTurbo Prolog differs from other Prolog implementations. All readers will want to refer to Chapter12,which provides detailed information about allaspects of Turbo Prolog. 1 Thetutorialscoverallaspectsof TurboPrologprogramming,exceptmodularpro- gramming andinterfacing with other languagessuchasC,Pascal,or assemblylanguage. Thesefeaturesare describedinChapterII,whichalsocontainshintsandtipsonpro- gramming styleanda wealthof other information about advancedsystemfeatures. For details about the filessuppliedonthedistribution disk,installation,andTurbo Pro- logmenucommands,seeChapter12.. THE DISTRIBUTION DISKS Your distribution disk contains themainTurboProlog program andseveralother files. Information about eachof thesefilescanbefoundinChapterII. TurboPrologisnotcopy-protected.PleasenotethatBorland'sno-nonsenselicense statement licensesyou to useyour copy of TurboProlog asif it were a book.It isnot licensed to a single person, nor isit tied to one particular computer. The only restriction on using Turbo Prolog is that it must not be used by two differentpeople at the same time, just asa book cannot bereadby two peopleat the sametime.And,of course,giving awaycopiesof TurboProlog to others wouldbea violationof Borland'scopyright. MINIMUM SYSTEMREQUIREMENTS TouseTurboProlog,youshouldhavethe following: •IBMPCor compatiblecomputer •384K RAMinternalmemory •PC-DOS or MS-DOS operating system,version2.0or later ACKNOWLEDGMENTS Inthismanual,referencesaremade to severalproducts: •TurboProlog andGeoBaseare trademarksandTurboPascalisa registeredtrade- mark of BorlandInternational,Inc. •WordStar isa registeredtrademark of MicroPro InternationalCorp. •MultiMateisa trademark of MultiMateInternationalCorp. •IBMPC,AT,XT,PCjr,andPortable Computer are registered trademarks of Interna- tionalBusinessMachinesCorp. 2Turbo Prolog Owner's Handbook 1About Prolog Over thelastdecade,thepriceof hardwarehashalvedapproximatelyeveryfourth year,while the cost of writing software hasincreased annually,andnow takes by far the largestportionof a totalsystembudget.Softwareaccountedfor about10%of total systemcostsin1970,50% in1975,andmore than80% in1985.Thisrapidlyescalating costhasinfluencedthedevelopmentof newprogrammingtoolstomakeiteasier, quicker andtherefore cheaper to develop programs.Inparticular,research has focused onwaysof handingover a largerpart of the work to themachineitself. Prologistheresultof manyyearsof suchresearchwork.Thefirstofficialversionof Prolog wasdevelopedat theUniversityof Marseilles,FrancebyAlainColmerauerin theearly1970sasaconvenienttoolforPROgramminginLOGic.Itismuchmore powerfulandefficient thanmost other well-knownprogramming languageslikePascal andBASIC.Forexample,aprogramfora givenapplicationwilltypicallyrequireten timesfewer programlineswithProlog thanwithPascal. Today,Prolog isa very important tool inartificialintelligence applicationsprogramming andinthedevelopment of expert systems.Severalwell-knownexpert systemshells are written inProlog,including APES,ESP/Advisor andXi. The demand for more "user friendly" andintelligent programsisanotherreasonfor Prolog'sgrowing popularity. Unlike,for example,Pascal,a Prolog program gives the computer a descriptionof the problem using a number of factsandrules,and then asksit to findallpossible solutions to the problem. InPascal,one must tell the computer exactly how to perform its tasks. But oncethePrologprogrammerhasdescribedwhatmustbecomputed,theProlog systemitself organizes how that computationiscarriedout.Becauseof thisdeclarative (ratherthanprocedural)approach,well-knownsourcesoferrorsinPascaland BASIC-such asloops that carryout one toomanyor one too few operations-are eliminatedright from the start.Moreover,Prolog teachestheprogrammer to makea well-structured description of a problem, so that, with practice, Prolog canalsobe used asa specificationtool. AlthoughPrologmakesprogramming fareasier,it canalsomakeseveredemandson thecomputer.TurboPrologisthefirstimplementationof Prolog for theIBMPCand compatiblepersonalcomputers that isbothpowerfulandconservativeinitsmemory requirements.It provides more features than many mainframe implementations. Turbo 3 Prologisa full-fledgedcompilerwithapull-downmenuinterfaceandfullarithmetic, graphicsandsystem-levelfacilities.TurboPrologproducescompiledprogramsthat execute very quickly but do not gobble memory like other,lesscomprehensivemicro- computer implementations of Prolog. In1983, Japanpublishedplans for anambitious nationalproject involving the design and productionof fifthgenerationcomputers,for whichPrologwaschosenasthefunda- mentalsystemlanguage(correspondingtotheuseof assemblylanguageincurrent architectures). Turbo Prolog runs on a computer costing about $2000 yet in a compari- sonmadein1984usinganearlierversionof thesystem,it producedprogramsthat executed faster than those producedby the prototype of the Japanese fifth generation computer. WHAT CAN TURBO PROLOG BE USED FOR? Thereareanumberof practicalapplicationsfor TurboProlog.Here'sasamplerof what youcando: •Produceprototypesforvirtuallyanyapplicationprogram.Aninitialideacanbe implementedquickly,andthemodelupon whichit isbasedtested"live." •Controlandmonitoringof industrialprocesses.TurboPrologprovidescomplete accessto, the computer'sI/O ports. •Implement dynamicrelationaldatabases. •Translatelanguages,eithernaturalhumanlanguagesor fromoneprogramminglan- guageto another.ATurboPrologprogramwaswrittento translatefromHewlett PackardBASICtoCunderUNIX onanHP-9000computerfora totalsoftware development cost of lessthan$7500. •Constructnaturallanguageinterfacestoexistingsoftware,sothatexistingsystems become more widely accessible.With TurboProlog it isparticularly easyto include windowsinsuchaninterface. •Construct expert systemsandexpert-systemshells. •Construct symbolicmanipulationpackagesfor solvingequations,differentiationand integration,etc. •Theoremproving andartificialintelligencepackagesinwhich TurboProlog'sdeduc- tivereasoningcapabilitiesareusedfor testing different theories. HOW DOES TURBO PROLOG DIFFER FROM OTHER LANGUAGES? Let'stakeacloserlookathowTurboPrologdiffersfromtraditionalprogramming languages. 4Turbo Prolog Owner's Handbook TurboPrologisdescriptive.Insteadof a seriesof steps specifying how the computer must work tosolveaproblem,aTurboPrologprogramconsistsof adescriptionof the problem.Thisdescriptionismadeupof threecomponents,with the first andsecond partscorresponding to thedeclarationsectionsof a Pascalprogram: I.Namesandstructuresof objectsinvolvedintheproblem 2.Namesof relationswhichareknown to exist between theobjects 3.Factsandrulesdescribing theserelations ThedescriptioninaTurboPrologprogramisusedtospecifythedesiredrelation between the giveninput data andtheoutput whichwillbegeneratedfrom that input. TurboPrologusesfactsandrules.Apart fromsomeinitialdeclarations,a TurboProlog program essentially consists of a list of logical statements, either in the form of factssuch as: it israining today. or intheformof rulessuchas: youwillget wet if it israining andyou, forget your umbrella. TurboPrologcanmakedeductions.Given the facts johnlikesmary. tom likessam. andtherule jeanettelikesXif tom likesX. TurboProlog candeduce that jeanettelikessam. Youcangivethe TurboProlog programa goal,for example findevery personwho likessam andTurboProlog willuseitsdeductive ability to findallsolutions to theproblem. Executionof TurboPrologprogramsiscontrolledautomatically.WhenaTurboProlog programisexecuted,thesystemtries to findallpossiblesetsof valuesthat satisfy the given goal.During execution, resultsmay be displayed or the user may be prompted to type insome data.TurboProlog usesa backtracking mechanismwhich,once one solu- tion hasbeen found,causes Turbo Prolog to reevaluate any assumptionsmade to seeif somenew variablevalueswillprovide new solutions. TurboProlog has a very short and simple syntax.It istherefore mucheasier to learn than the syntaxof more complicatedtraditionalprogramming languages. TurboProlog ispowerful. Turbo Prolog isa higher levellanguage than, for instance,Pascal. Aspointedout earlier,TurboProlog typically uses10timesfewerprogramlineswhen solvingaproblemthanPascal.Amongotherthings,thisisduetothefactthat About Prolog5 TurboProloghasa built-inpattern-recognitionfacility,aswellasa simpleandefficient way of handlingrecursivestructures. TurboPrologiscompiled,yet allowsinteractiveprogramdevelopment.Aprogrammer can testindividualsectionsof a programat anypointandalter thegoalof theprogram, without having to appendnew code.Thiswouldcorrespondto being ableto tryout anyarbitraryprocedureina Pascalprogram,evenafter theprogramhasbeencom- piled. Thishasbeena brief overview of theuniquefeaturesof TurboProlog.Asyoudelve more deeplyinto thismanualandbeginwritingprograms,you'lldiscovermore of its powerfulabilities.Now let's turn to Chapter 2 andget startedwith the TurboProlog system. 6Turbo Prolog Owner's Handbook 2A Short Introduction to the Turbo Prolog System Thischapter describes thebasicoperationof the TurboPrologsystem,includinghow tomakeasystembackup,usethemenusystem,runa TurboPrologprogram,and create a programfileusing the TurboProlog editor. Chapter12,the technicalreference,givesa completelistof thefilessuppliedonthe distributiondiskandthefilesneededwhenusingtheTurboPrologsystem.Turbo Prologcomespre-installedandreadytorunonanIBMPCor fullycompatiblecom- puter.If youaren't satisfiedwith some of the defaults (suchasour choiceof colorsfor thedisplay) theyareeasyto changeusingpull-downmenus.Seepage168.Fornow, untilyou're familiarwith the system,youcantryout TurboProlog asis. THE MAINMENU Once you have a copy of the system on your working disk and you are in the appropri- atedirectory, typePROLOG.YoushouldseethelogonmessageshowninFigure2-1. Figure 2-1TheLogonDisplay 7 Inaddition to the version of Turbo Prolog you are using,the logon message shows you theconfigurationfor TurboProlog onyour computer. Now press the spacebar andthe TurboProlog mainmenuandfour systemwindows willappear asshowninFigure2-2. Figure 2-2TheMainMenu and theFour SystemWindows TheMainMenushowsyou the commandsandpull-downmenusavailable.Youselect anitemonamenubypressingtheassociatedhighlightedcapitalletterorbyfirst moving thehighlightedbarusingthearrow keys,andthenpressing lB. Theuseof eachwindow isdescribed throughout thischapter. Thebottomlineof thescreencontainsastatusmessagedescribingtheuseof the functionor cursorkeys.Themeaningof thesekeyschangesdependingonwhat you aredoing with thesystemat a giventime: tracing,editing,or running a program,etc. ENTERING YOURFIRST TURBO PROLOG PROGRAM Consider thefollowingintroductory TurboPrologprogram.We'llbeusingit toillus- trate how to create,run,andedit TurboProlog programs. predicates hello goal hello. clauses hello:- makewindow(1,7,7,"Myfirstprogram",L;,Sb,lO,22), nl,write("Pleasetypeyourname"), cursor(L;,S), readln(Name),nl, write("Welcome",Name). Select the Edit optioneither by moving thecursor with the arrow keysuntilit isover the word Edit and then pressing IB, or by simply pressing CD.The screen should now look likeFigure2-3. 8Turbo Prolog Owner's Handbook In"COOIpileIDIlOptionsrilesSetupIlult Figure 2-3UsingtheEditor Note that theeditor windowishighlightedandthestatustext at thebottomreflects thenew meaningof the functionkeys. Toseehow to correct amistake,typeinthe firstlineof the aboveprogram as predivates Tocorrect the mistake,position the cursor over the erroneous letter v andthenpress @ill.Watchcarefullywhat happens to thedisplay.Nowpress!]) andlook again.The mistakeshouldbe corrected.Now typeinthe firstsevenlinesof the aboveprogram text,pressing ~at theendof eachline. Whenyoutype the endof the linethat begins makewindow ........ . therest of the text willscroll to the leftinside the editor's window. Just to make sure it hasn't reallydisappeared,press ~after typing inthisline,thenpress the El key and holditdownuntilthecursorstopsmoving.Afteryouseewhathappens,movethe cursor back to where youleftoff andfinishtypingintheprogram. Once youare satisfied that the program text hasbeen entered correctly,press 1E to leave the editor, then select the Runoption from the menu.If you entered the program correctly,theprogramwillbecompiledandthenexecutedandyoushouldseethe displayshowninFigure2-4. Now type your firstname andpress ~ "The program youhave entered willrespond WelcomeAlfredo (or whatever yournameis)andwait foryoutopressthespacebar.Thescreenwill thenclear,leavingthemainmenuandtheprogramtext visible.Tryrunningthepro- gramagainanduseanaliasthistime! AShort Introduction to the Turbo Prolog System9 limCOIIpileEditOption.rilessPerson2. (InEnglish:FindPerson Iaged9andPerson2aged9sothat Person IandPerson2are different). TurboPrologwilltry to finda solutionto thefirstsubgoalandcontinueto thenext subgoalonlyafter thefirstsubgoalisreached.Thefirstsubgoalissatisfiedby taking Person Ito be peter.Now Turbo Prolog cansatisfy pupil(Person2,Q) by also taking Person2to be peter.Now we come to the third andfinalsubgoal Personl(>Person2 Tutorial I: Five Simple Programs23 SincePerson IandPerson2areboth peter,thissubgoalfails,soTurbo Prolog backtracks to theprevious subgoal.It thensearchesfor another solution to the secondsubgoal pupil(Person2,9) whichisfulfilledby taking Person2to bechris.Now, the thirdsubgoal Person1Person2 issatisfied,sincepeterandchrisaredifferent,andhencetheentiregoalissatisfied. However,sinceTurboPrologmust findallpossiblesolutionstoa goal,onceagainit backtracks to thepreviousgoalhoping to succeedagain.Since pupil(Person2,9) canalsobe satisfiedby taking Person2 to be susan,Turbo Prolog tries the third subgoal onceagain.It succeedssincepeter andsusanaredifferent.soanothersolutionto the entire goalhasbeenfound. Searching formore solutions,TurboProlog onceagainbacktracksto thesecondsub- goal.Butallpossibilitieshavebeenexhaustedforthissubgoalnow,sobacktracking continues to the first subgoal.Thiscanbe satisfiedafreshby taking Person Ito bechris. The secondsubgoalnow succeedsby taking Person2to be peter,so the third subgoalis satisfied,fulfilling the entire goal. The finalsolution iswith Person IandPerson2as susan.Since this causes the finalsubgoal tofail,TurboPrologmustbacktracktothesecondsubgoal,buttherearenonew possibilities. Hence, Turbo Prolog backtracks to the first subgoal.But the possibilities for Person Ihavealsobeenexhaustedandexecution terminates. TypeintheabovecompoundgoalforProgram3andverifythatTurboProlog respondswith Person1=peter,Person2=chris Person1=peter,Person2=susan Person1=chris,Person2=peter Person1=chris,Person2=susan Person1=susan,Person2=peter Person1=susan,Person2=chris 6Solutions Goal: Figure3-1illustrateshow Turbo Prolog backtracks to satisfya goal. ExerciseDecide what TurboProlog'sreply to the goal pupil(Person1,9)andpupil(Person2,10). willbe,thencheck your answer by typing intheexercise. TurboProlog theMatchmaker:UsingNot Supposewe want to write a small-scalecomputer datingprogramcontainingalistof registeredmales,a listof whosmokes,andtherulethat sophieislooking for aman who iseither a non-smoker or a vegetarian.The occurrence of or insophie's selection ruleindicates that we canusemore thanone TurboProlog rule to expressit: 24Turbo Prolog Owner's Handbook sophiecoulddate(X)ifmale(X)andnot(smoker(X)). sophiecoulddate(X)ifmale(X)andvegetarian(X). TheserulesareusedinProgram4,whichyoushouldnow typeinto your computer. pupil(Person1,9)andpupil(Person(2,9)andPerson1()Person2 II II peter pupil(paul,10) pupil(chris,9) pupil(susan,9) peter pupil(paul,10) pupil(chris,9) pupil(susan,9) peterpeterFAILS No(more)possiblechoiceshereso BACKTRACK pupil(Person1,9)andpupil(Person2,9)andPerson1()Person2 II II peter pupil(paul,10) pupil(chris,9) pupil(susan,9) chris pupil(peter,9) peterchrisSUCCEEDS No(more)possiblechoiceshereso BACKTRACK pupil(Person1,9)andpupil(Person2,9)andPerson1()Person2 II II peter pupil (paul, 10) pupil(chris,9) pupil(susan,9) susan pupil(peter,9) pupil(paul,10) pupil(chris,9) petersusanSUCCEEDS No(more)possiblechoiceshereso BACKTRACK No(more)possiblechoiceshereso BACKTRACK pupil(Person1,9)andpupil(Person2,9)andPerson1()Person2 II II chris pupil(peter,9) pupil(paul,10) pupil(susan,9) peter pupil(paul,10) pupil(chris,9) pupil(susan,9) chrispeterSUCCEEDS No(more)possiblechoiceshereso BACKTRACK Figure 3-1Backtracking Tutorial I:Five Simple Programs25 1*ProgramL;*1 domains personsymbol predicates goal male(person) smoker(person) vegetarian(person) sophie_could_date(person) sophie_could_date(X)and write("apossibledateforsophieis",X)andnl. clauses male(joshua) . male(bill) . male(tom) . smoker(guiseppe). smoker(tom). vegetarian(joshua). vegetarian(tom). sophie_could_date(X)ifmale(X)andnot(smoker(X)). sophie_could_date(X)ifmale(X)andvegetarlan(X). Apart fromtheuseof tworules(TurboPrologletsyouuseasmanyasyouplease), there areseveralother novel features in thise ~ a m p l e .First,notice the useof not asin not(smoker(X)) TurboProlog willevaluate thisastrue if it isunable to prove smoker(X) istrue.Using notinthiswayisstraightforward,butitmustberememberedthatTurboProlog cannot,for example,assumeautomatically that someone iseither a smoker or a non- smoker. This sort of information must be explicitly built into our facts andrules. Thus, in Program 4,the first clausefor sophie_could_dateassumesthat anymalenot known to bea smoker isa non-smoker. , Second,notice the incorporation of a goal within the program.Every time we execute our minicomputer-dating program,it willbe with the samegoalinmind-to find a list of possibledates for sophie-so TurboProlog allowsusto include this goalwithin the program.However, we must theninclude the standardpredicate write( •••••••••• ) so that the settings (if any) of the variable Xwhich satisfy the goalaredisplayedon the screen.We must alsoinclude thestandardpredicate nl whichsimply causesa new line to beprinted. Standardpredicates are predicates that arebuilt into the Turbo Prolog system.Gener- ally,theymakefunctionsavailablethat cannotbeachievedwithnormalTurboProlog clauses,andareoftenusedjust for theirside-effects(likereadingkeyboardinput or screendisplays)rather thanfor their truth value. ExecuteProgram4 andverify that TurboProlog displays apossibledateforsophieisjoshua 26Turbo Prolog Owner's Handbook Surprisingly.eventhoughtom(beingmaleandavegetarian),wouldbeeligiblefora date,if weincludea goalintheprogram,onlythefirstsolutionisfound.Tofindall solutions,trydeletingthegoalfromtheprogram,thengivethegoalinresponseto Turbo Prolog's prompt during execution (aswe did earlier). This time allpossible dates willbe displayed.Evenif the goalisinternal (i.e., written into the program), it ispossible for allsolutionsto bedisplayed; seeChapter 5. Comments It isgood programming style to include comments that explaindifferent aspectsof the program. This makes your program easy to understand for both you andothers.If you choosegoodnamesfor variables,predicates,anddomains,you'llbeableto get away with fewer comments,sinceyour programwillbemore self-explanatory. Comments inTurboProlog must beginwith thecharacters 1*(slash,asterisk) andend with the characters */.Whatever iswritten inbetweenisignoredby the TurboProlog compiler.If you forget to close with */,a section of your program will be unintentionally considered asa comment. Turbo Prolog will give you anerror messageif you forget to closea comment. 1*Thisisanexampleofacomment*1 1***********************************1 1*andsoarethesethreelines*1 1***********************************1 A MoreSubstantial ProgramExample Program5isa familyrelationshipsdatabase that hasbeenheavily commented. 1*Program5*1 domains personsymbol predicates male(person) female(person) father(person,person) mother(person,person) parent(person,person) sister(person,person) brother(person,person) uncle(person,person) grandfather(person,person) clauses male(alan). male(charles). male(bob) . male(ivan). female(beverly). female(fay) . female(marilyn). female(sally) . Tutorial I: Five Simple Programs27 mother(marilyn,beverly). mother(alan,sally). father(alan,bob) father(beverly,charles). father(fay,bob). father(marilyn,alan). parent(X,Y)ifmother(X,Y). parent(X,Y)iffather(X,Y). brother(X,Y)if male(Y)and parent(X,P)and parent(Y,P)and X()Y. sister(X,Y)if female(Y)and parent(X,P)and parent(Y,P)and X()Y. uncle(X,U)if mother(X,P)and brother(P,U). uncle(X,U)if father(X,P)and brother(P,U). grandfather(X,G)if father(P,G)and mother(X,P). grandfather(X,G)if father(X,P)and father(p,G) . I*ThebrotherofX isY if*1 I*Yisamaleand*1 I*theparentofX isPand*1 I*theparentofY isPand*1 1*X andYarenotthesame*1 I*ThesisterofX isY if*1 I*Yisfemaleand*1 I*theparentofX isPand*1 I*theparentofY isPand*1 I*XandYarenotthesame*1 I*TheuncleofX isU if*1 I*themotherofX isPand*1 I*thebrotherofPisU.*1 I*TheuncleofX isU if*1 I*thefatherofX isPand*1 I*thebrotherofPisU*1 I*ThegrandfatherofX isG *1 I*ifthefatherofPisG*1 I*andthemotherofX isP.*1 I*ThegrandfatherofX isG *1 I*ifthefatherofX isP*1 I*thefatherofPisG*1 Typeandexecute thisprogram and,by formulating appropriate goals,useTurbo Pro- log to answer the followingquestions: I.Isalanivan'sbrother? 2.Who ismarilyn's grandfather? 3.Who isfay'ssister? 4.What istherelationship(if any)betweenmarilyn andbeverly? The relations uncle and grandfather are both described by two clauses, though only one isnecessary.Try to rewrite uncleandgrandfatherusing oneclausefor each. 28Turbo Prolog Owner's Handbook Summary A TurboProlog programhasthefollowingbasicstructure: dOlllains 1* ...domainstatements*1 predicates 1* ...predicatestatements*1 goal clauses 1* ...clauses(rulesandfacts)...*1 If youdon't includea goalintheprogram,TurboPrologwillaskfor a goalwhenthe programisexecuted. Factshave the generalform: relation(object,object, ... ,object) Ruleshavethe generalform relation(object,object, ... ,object)if relation(object, ... ,object)and relation(object, ... ,object). Tobeconsistent withother versionsof Prolog,if canbereplacedby the symbol:- anda comma (,) canbe usedinsteadof and. Thus is_older(Person1,Person2)if age(Person1,Age1)and age(Person2,Age2)and Age1)Age2. and is_older(Person1,Person2) age(Person1,Age1), age(Person2,Age2), Age1)Age2. areexactly equivalent. .Apredicate consistsof one or more clauses.Clauses that belong to the samepredicate must followoneanother. ExerciseUse Turbo Prolog to construct a smallthesaurus.Youshould store factslike similar_meaning(big,gigantic). similar_meaning(big,enormous). similar_meaning(big,tall). similar_meaning(big,huge). similar_meaning(happy,cheerful). similar_meaning(happy,gay). similar_meaning(happy,contented). Tutorial I:Five Simple Programs29 sothat a goalof the form similar_meaning(big,X) would causeTurboProlog to display a list of alternative words for big. ExerciseGiventhefollowingfactsandrulesabout amurdermystery,canyouuse TurboProlog to findwho dunnit? 30 person(allan,25,m,football_player). person(allan,25,m,butcher). person(barbara,22,f,hairdresser). person(bert,55,m,carpenter). person (john,25,m,pickpocket) . had_affair(barbara,john). had_affair(barbara,bert). had_affair(susan,john). killed_with(susan,club). motive(money). motive(jealousy). smeared_in(catherine,blood). smeared_in(allan,mud). owns(bert,wooden_leg). owns(john,pistol). 1*Background-knowledge*1 operates_identically(wooden_leg,club). operates_identically (bar,club). operates_identically(pair_of_scissors,knife). operatesidentically(football_boot,club). owns_probably(X,football_boot)if person(X,_,_,football_player). owns_probably(X,pair_of_scissors)if person(X,_,_,_,_). owns_probably(X,Object)if owns(X,Object). 1*Suspectallthosewhoownaweaponwithwhichsusancould possiblyhavebeenkilled*1 suspect(X)if killed_with(susan,Weapon)and operates_identically(Object,Weapon)and owns_probably(X,Object). 1*Suspectmenthathavehadanaffairwithsusan*1 suspect(X)if motive(jealousy)and person(X,_,m,_)and had_affair(susan,X). Turbo Prolog Owner's Handbook 1*Suspectfemaleswhohavehadanaffairwithamansusanknew*1 suspect(X)if motive(jealousy)and person(X,_,k,_)and had_affair(X,Man)and had_affair(susan,Man). 1*Suspectpickpocketswhosemotivecouldbemoney*1 suspect(X)if motive(money)andperson(X,_,_,pickpocket). Tutorial I: Five Simple Programs31 32Turbo Prolog Owner's Handbook 4Tutorial II: A Closer Look at Domains, Objects and Lists This chapter willfamiliarizeyou with many of the Turbo Prolog features you'llbe using themost.Weintroducetheconceptsof freeandboundvariables,standarddomain types,andcompoundobjects.You'lllearnhow to userecursioninyour programs, and seehow to takeadvantageof TurboProlog'sextensivelist-handling facilities. If a TurboProlog variablehasa knownvalue,we sayit isbound to that valueandthat otherwise it isfree.Thischapter beginsby considering thebindingsof variablesduring the evaluationof a.goal. Bound variables have values from a domain which iseither itself of standard type or isa user-defineddomainbuilt upfromoneor more suchdomains.Inthesecondpart of thischapter,westudydomainsinsomedetailandlearnhowtobuildcompound domainsincluding thosewhichallow listsof objects to beregardedasa singleentity. Just aslistsareoneof Turbo Prolog'smost important data structures, themost impor- tantPrologprogrammingtechniqueisrecursion;inparticular,recursionallowsusto processtheelementsof a list.Thischapterconcludeswithseveralexamplesshowing theuseof recursion. FREE AND BOUND VARIABLES TurboProlog distinguishesbetween two typesof variables: •Freevariable-Turbo Prolog doesnot know itsvalue •Bound variable-a knownvalue Look at Program 6,andconsider how Turbo Prolog will solve the following compound goal: likes(X,reading)andlikes(X,swimming). 33 1*Programb*1 domains person,hobby= symbol predicates likes(person,hobby) clauses likes(ellen,reading). likes(john,computers). likes(john,badminton). likes(leonard,badminton). likes(eric,swimming). likes(eric,reading). TurboProlog searchesfromleft to right.Inthe first subgoal likes(X,reading) the variable Xisfree (itsvalueisunknown before TurboProlog attempts to satisfy the subgoal) but, on the other hand, the second argument, reading,isknown. Turbo Prolog willnow searchfor a fact that canfulfillthedemandsinthesubgoal. The first fact isa match,so the free variable Xwill be bound to the relevant valuein the fi rst fact,ellen. likes(ellen,reading). At thesametime,TurboPrologplacesapointerinthedatabaseindicatinghowfar down the searchprocedurehasreached. Next, the second subgoalmust be fulfilled.Since Xisnow bound to ellen,Turbo Prolog hasto searchfor the "fact" likes(ellen,swimming). Turbo Prolog searches from the beginning of the database,but in vain.Thus, the second subgoalisfalsewhen Xisellen. Turbo Prolog now attempts another solution of the first subgoal with Xfree once again. Thesearchfor a secondfact that canfulfillthefirstsubgoalstartsfrom theplacelast marked (provided there aremore untestedpossibilities). TURBO PROLOG'SSTANDARD DOMAIN TYPES TurboProlog candealwith sixstandarddomain types,asshowninTable4-1. 34Turbo Prolog Owner's Handbook char integer real string symbol Table4-1StandardDomain Types character enclosedbetween two singlequotationmarks (e.g.'a'). integersfrom- 32,768to 32,767. numbers with anoptionalsignfollowedbysomedigits;then(optionally) a decimalpoint (.)followedby somedigitsfor thefractionalpart;andfinallyan optionalexponentialpart-for example,ane followedby anoptionalsignand anexponent. Following areexamplesof realnumbers: 42705 -9999 86.72 -9111.929437 -521 e238 64e-94 -79.83e+21 Thepermittednumber rangeis± I e- 307 to± I e+ 308.Integersareautomati- callyconvertedto realnumberswhennecessary. Any sequenceof characterswrittenbetween a pairof doublequotationmarks, e.g."jonathan mark's book" Twoformats arepermittedfor symbols: (I) a sequenceof letters,numbersand underscores,provided the first characterislowercase;or (2) a character sequencesurroundedby a pair of doublequotationmarks(thisisusedinthe caseof symbolscontaining spaces,or if a symboldoesnot start witha lowercase letter).Following areexamplesof strings: "railway_ticket" "Dorid_lnc" Symbolsandstringscanbeusedinterchangeably,but they arehandleddiffer- entlyinternally.Symbolsarekept ina lookup table,whichresultsina very quick matchingprocedureduring a search.Thedisadvantageisthat thesymboltable takesuproom andtheinsertion takestime.Youmust determinewhichdomain willoffer thebestperformanceina givenprogram. fileThefiledomaintypeisdescribedinChapter 9. Let'slook at some more examples of objects that belong to domains of standard type. Table4-2SimpleObjects swift,abc,kenneth,"animallover" -1,3,5,0 3.45,0.01,-30.5,123.4e+5 'a','b','c', '/','&' "One two", "name number 5","&&" (symbol) (integer) (real) (char) (string) Tutorial II: ACloser Look at Domains, Objects and Lists35 Objects belonging to character and string domains, and that contain a \ (backslash) have a specialmeaning: \Number \n a character with the ASCIIvalueNumber Newline character \tTabulatecharacter Thus,the three objectsbelow write('\13') write( '\n') nl willcausea newline to bedisplayed. We willnow work out somepredicatedeclarationsusingthesestandarddomains.If standarddomainsaretheonlydomainsinthepredicatedeclarations,theprogram need not have a domainssection.For example, suppose we wish to define a predicate sothat a goalsimilar to alphabet_position(A_character,N) willbetrueif A-characteristheNthletter inthe alphabet.Clausesfor thispredicate wouldlook like alphabet_position('a',1). alphabet_position('b',2). alphabet_position('c',3). alphabet_position(,0).1*othercharactersgive° II Thepredicatecanbe declaredasfollows: predicates alphabet_position(char,integer) andthereisno needfor a domainssection. Asanotherexample,supposewewishtodeclareapredicatethatcanbeusedin connectionwith addition.Thus,we needa predicate suchthat inthe following goal add(X,y,Z). the arguments are the two numbers to be added andthe number that represents the total,corresponding to theequation X+Y= Z Consequently, the predicates declaration must stipulate that add needs three numeric arguments,andit must describe the typesof domain to which they belong: add(integer,integer,integer) or add(real,real,real) If both predicate declarations are used, the predicate add canbe used for both integers andrealnumbers.Thisisdue to the fact that TurboProlog permits multiplepredicate declarations.Inmultipledeclarationsof thesamepredicate,thedeclarationsmustbe givenoneafter theother andthey must allhave thesamenumber of arguments. 36Turbo Prolog Owner's Handbook Program7isacompleteTurboPrologprogramthatfunctionsasaminitelephone directory that usesthestandardpredicatesreadlnandwrite.Thedomainssectionhas beenomitted, sinceonly standarddomains areused.Theprogram asksfor a name to be typed in.When the name isentered, the corresponding telephone number isfound from the databaseanddisplayedon thescreen. 1*Program7*1 predicates reference(symbol,symbol) goal clauses write(IIPleasetypeaname:11), readln(The_Name), reference(The_Name,Phone_No), write (liThephonenumberisII, Phone_No) , nl. reference(IIAlbert ll ,1101-1231;56 11 ). reference(IIBettyll,1101-569767 11 ). reference(IICarol ll ,1101-2671;00 11 ). reference(IIDorothyll,1I01-191051 11 ). Finally,to illustrate the char domain type,Program8 definesis/etter which, when given the goals isletter( '%'). isletter( 'Q'). willreturnfalseandtruerespectively. 1*Program8*1 predicates isletter(char) clauses isletter(Ch)ifCh(='z'and'a'(=Ch. isletter(Ch)ifCh(='Z'and'A'(=Ch. ExerciseTypeinProgram7andtry eachof thesegoalsinturn. (1)reference (IiCarol ll , y). (2)reference(X,1I01-191951 11 ). (3)reference(IIMavisll,y). (1;)reference(X,y). Kimsharesa flat with Dorothy andsohasthe samephone number.Add thisinforma- tion to the clausesfor thepredicatereferenceandtry the goal reference(X,1I01-191051 11 ). to check your addition. TypeProgram8 andtry eachof thesegoalsinturn. (1)isletter('x'). (2)isletter('2'). (3)isletter(lIhello ll ). (1;)isletter(a). (5)isletter(X). Tutorial II: A Closer Look at Domains, Objects and Lists37 COMPOUND OBJECTS CANSIMPliFY YOUR CLAUSES! TurboProlog allowsyouto makeobjects that containother objects.Thesearecalled compound objects.Compoundobjectscanberegardedandtreatedasa singleobject, whichgreatly simplifiesprogramming. Consider,for example,the fact owns(john,book("FromHeretoEternltyl,"JamesJones")). inwhich we state that john owns the book FromHere to Eternity,which was written by James Jones.Likewise,we couldwrite owns(john,horse(blacky)). which canbeinterpreted as: john owns a horse by the name of blacky.The compound objectsinthese two examplesare book("FromHeretoEternityl,"JamesJones") and horse(blacky) If we hadinsteadwritten two facts owns(john,"FromHeretoEternity"). owns(john,blacky). we would not have. been able to decide whether blocky was the title of a book or the nameof a horse.On the other hand,the first component of a compoundobject, the functor,isusedtodistinguishbetweendifferentobjects.Intheexampleabove,we madeuseof the functors bookandhorse to indicate the difference. Compoundobjects consist of a functor andthe sub-objectsbelonging to it: functor(object1,object2,...objectN) Afunctor without objectsiswritten as functor( ) or just functor Domain Declaration of Compound Objects We will now look at how compound objects are defined when domain declarations are used.Inthe subgoal thevariable Xcanbeboundto different typesof objects,either a book,a horse,or perhapsother typesof objects.Becauseof this,wecannolongeremploytheold definition of the ownspredicate owns(symbol,symbol) 38Turbo Prowg Owner's Handbook where thesecondargument hasto refer to objectsbelonging to a domain of symbol type.Instead,we usea new formulationof the predicatedeclaration: owns(name,articles) The articlescanthenbedescribed with thedomaindeclarations domains articles= book(title,author);horse(name) title,author,name= symbol The semicolon canbereadasor.In this case,two alternatives are possible: a book can be identified by its title and author, and a horse canbe identified by a name. The domains title,author,andnameareallof symbol type. Morealternativescaneasilybeaddedto thedomaindeclaration:articlescouldalso includea boat or a bankbook,for example. For boat we canmakedo withanobject with a functor whichhasnoobjects.On the other hand, we wish to give the bank balance asa figure within bankbook. The domains declarationof articlesistherefore extended to articles=book(title,author);horse(name);boat;bankbook(integer) Here aresomeexamplesof how compoundobjectsfrom thedomain articlescanbe usedinsome factswhichdefine thepredicate owns: owns(john,book("Afriendofthefamilyl,"IrwinShaw")). owns(john,horse(blacky)). owns(john,boat). owns(john,bankbook(1000)). With the goal owns(john,Thing). we willnow receive theanswers: Thing Thing Thing Thing book("Afriendofthefamily","IrwinShaw") horse(blacky) boat bankbook(1000) How domain declarationsarewritten-a summary. domain= alternativel(D,D, ... );alternative2(D,D, ... ) Here,alternative I andalternative2arearbitrary (but different) functors.Thenotation (0,0,,,.)representsa list of domainnamesthat areeitherdeclaredelsewhere,or are oneof the standarddomainssymbol,integer,realor char. Notice: I.The alternatives are separatedby semicolons. 2.Every alternative consists of a functor, andpossibly a list of domains for the corre- sponding objects. Tutorial II: ACloser Look at Domains, Objects and Lists39 Program 9 uses functors to move the cursor around the screen asa "side-effect" of the evaluationof goals.For example moves the cursor up two linesfrom itsstartingpositionof row 4 andcolumn9 of the screen.It usesthebuilt-inpredicate cursor(row,column) to position thecursor at thespecifiedrow andcolumn. /1Program91/ domains row,column,step= integer movement=up(step);down(step); left(step);right(step) predicates move_cursor(row,column,movement) clauses move_cursor(R,C,up(Step)):- Rl=R-Step,cursor(Rl,C). move_cursor(R,C,down(Step)):- Rl=R+Step,cursor(Rl,C). move_cursor(R,C,left(_)):- Cl=C-l,cursor(R,Cl). move_cursor(R,C,right(_)):- Cl=C+l,cursor(R,Cl). Ifweaddedthealternativeno,amovementcouldalsoinclude"nostep"asin (R,c'no).Note that thefunctornoissufficient torepresent"nomove- ment."No sub-objectsarerequired. Going Down a Level TurboProlog allowsyouto construct compoundobjectsonseverallevels.For exam- ple,in book("TheUglyDuckling","Andersen") insteadof using the author's surname,we couldusea new structure that describes the author inmore detail,includingboth theauthor'sfirstnameandsurname.Calling the functor for theresultingnew compoundobject author,thedescriptionof thebook is changedto book("TheUglyDucklingl,author("HansChristianl,IAndersen")) Intheolddomaindeclaration book(title,author) we seethat the secondargument inthe book functor isauthor.But the olddeclaration author= symbol 40Turbo Prolog Owner's Handbook canonlyincludea singlenamewhichisthereforenolongersufficient.Wemustnow specify that anauthor isalso a compound object comprising the author's first name and surname.Thisisachievedwith thedomainstatement: author=author(firstname,surname) whichleadsusto the following declarations: domains articles= book(title,author); author=author(firstname,surname) title,firstname,surname= symbol Whenweusecompoundobjectsondifferentlevelsinthisway,it isoftenhelpfulto draw a "tree": book I\ titleauthor I\ firstnamesurname Adomainstatement describes only onelevelof the tree at a time andnot thewhole tree.For instance,a book cannotbedefinedwith the following domain statement: book=book(title,author(name,surname» Asanotherexample,considerhowtorepresentthegrammaticalstructureof the sentence "ellenowns thebook" using a compoundobject. The most simplesentencestructure consistsof a nounanda verbphrose: sentence= sentence(noun,verbphrase) Anounisjust a simpleword: noun=noun(word) Averbphroseconsistsof either a verbanda nounphroseor singleverb. verbphrase= verbphrase(verb,noun);verb(word) verb=verb(word) Using thesedomaindeclarations (sentence,noun,article,verbphroseandverb),the sen- tence"ellenowns thebook" becomes: sentence(noun(ellen),verbphrase(verb(owns),noun(book») The corresponding tree is: sentence /\ nlun ellenownsthebook Tutorial II: A Closer Look at Domains, Objects and Lists41 ExerciseWrite a suitabledomainsdeclaration using compound objects that couldbe usedin a Turbo Prolog catalog of musical shows.A typical entry in the catalog might be: Show:West SideStory Lyrics:StephenSondheim Music:LeonardBernstein ExerciseUsing compound objects wherever possible,write a Turbo Prolog program to keep a database ofthe current Top Tenhit records. Entries should include the name of the song,the name of the singer or group,itspositioninthe Top Tenchart,andthe number of weeksinthe charts. Recursion Program10illustratesanimportantTurboPrologprogrammingtechniquecalled recursion.Recursionisusuallyusedintwo situations: •whenrelationsaredescribed with the helpof the relations themselves •when compound objects are a part of other compound objects (i.e.,they arerecur- siveobjects) The first situation occurs inProgram10.It gives a fact and a rule for the singlepredicate factorialwhich,whenusedina goallike factorial(N,F) willreturn true if F isequalto N! i.e.,if F= N*(N-1)*(N-2)* ... *3*2*1 Before we discusshow factorialworks, type theprograminandtry out the following goals: 42 factorial(l,Answer)./*goal1*/ factorial(2,Answer)./*goal2*1 factorial(3,Answer).1*goal3*1 1*goal*1 factorial(S,Answer).1*goal5*1 factorial(b,720).1*goalb*1 factorial(10,2000).1*goal7*1 1*Program10*/ domains n,f= integer predicates factorial(n,f) clauses factorial(l,l). factorial(N,Res)if N )0and N1= N-1and factorial(Nl,FacNl)and Res= N*FacNl. Turbo Prolog Owner's Handbook Inthe program, N I =N- Ishouldberegardedasa more readable form of the clause: =(N1,-(N,1)) where- isa functor.Thus N I =N-I evaluatesto trueprovidedN Iisbound to the valueof N-I. Let'sinvestigatehow factorialworks whensatisfying the goal factorial(2,Answer) Using therule,we have factorial(2,Res)if 2>1,N1=2-1,factorial(N1,FacN1),Res=2*FacN1. Sowe must evaluate the goal factorial(1,FacN1). Using the fact factorial(1,1). the goalissatisfiedbybinding FacN I toI.Inturn,we now need to evaluate Res=2*FacN1 whichissolvedwith Resbound to 2 * I,so theinitialgoalissatisfiedwith Answer bound to 2. For a more complicatedevaluationlike we have theevaluationsequence if factorial(3,FacN1)if 3>1,N11=3-1,factorial(3-1,FacN11),Res=3*FacN11 factorial(2,FacN11)if 2>1,N11=2-1,factorial(2-1,FacN111),Res=3*FacN111 factorial(2-1,FacN111)succeedswithFacN111boundto1 factorial(3-1,FacN11)succeedswithFacN11boundto2 succeedswithFacN1boundto6 succeedswithResboundto Hence,factorial( 4,Answer)succeedswith Answer bound to 24. Tutorial II: A Closer Look at Domains, Objects and Lists43 goal: calls: calls: calls: calls: calls:factorial(1,1) Figure 4-1Evaluation of Factorial(4,Answer) ExerciseAdddomainsandpredicates declarations to the following factsandrules: factorial(X,Y)ifnewfactorial(D,1,X,Y). newfactorial(X,y,X,y). newfactorial(U,V,X,y)if U1=U+1, U1V=U1*V, newfactorial(U1,U1V,X,Y). andtryout theresultingprogramwith the following goals: 1.factorial(3,Answer). 2. 3.factorial(S,Answer). Usingpencilandpaper,trace theexecutionof the first goal. RecursiveObjects Recursioncanalsobeusedto describeobjectswhere thenumber of elementsisnot knowninadvance.Consider thisproblem: Which object candescribe the namesof all pupilsina schoolclass,without usknowing thenumber of pupilsinadvance? Tosolvethisproblem,let'sformulateacorrespondingdomainsdeclarationforthe domainc/oss/ist,stepby step.We start by describing anempty classwithno students: classlist=empty Next, we formulate therecursivedefinition classlist=class(name,classlist) Thus,a typicalobject wouldbe class(peter,X) whichsymbolizesaC/oss/istwithpeterasthefirstmember.Xsymbolizesasmaller c/oss/ist (without peter).Hence, a classconsisting of two students couldbe describedby class(peter,class(james,empty)) anda classconsistingof three studentsby class(andrew,class(peter,class(james,empty))) 44Turbo Prolog Owner's Handbook Note that class(name,classlist) isacompoundobject where the functorisclass,nameisone student inthe class,and classlist contains the other students. The final,complete domainsdeclarationconsists of the two alternativedefinitions classlist=class(name,classlist);empty Likewiseaseriesof numbers could,forinstance,be definedby integerlist=list(integer,integerlist);empty ExerciseWrite the compound TurboProlog terms that describe the followinglistof numbers: 1,3,6,0,3 anddraw the corresponding tree. ExerciseFor the purposes of our TurboProlog programs, we wish to treat arithme- ticexpressions,suchasI + 2 - 3,asobjects.Muchofthisisaccomplishedbythe domainsdeclaration: expr=plus(expr,expr);number(integer) whichgivessuchobjectpossibilitiesas corresponding to the arithmeticexpression4+ 5.The expressionI + 2 + 3 couldsimi- larlybe writtenas: plus(number(1),plus(number(2),number(3))) or plus(plus(number(1),number(2)),number(3)) Appendnewalternativestotheabovedomainsdeclarationsothatobjectsthat describe2-4 or 2+ 3-log(5) are alsopermitted. THE FASCINATING WORLDS OF LISTS AND RECURSION Listsare thebasicdata structureinTurboPrologprograms,correspondingroughly to Pascal'suseof arrays.Becauselistsare socommon,TurboPrologprovidesaneasier way to represent them than as compound objects. A list that consists of the numbersI, 2,and3 canbe writtenas [1,2,3,1. Theelementsof alistareseparatedbycommasandenclosedby[and].Hereare some examples: [dog,cat,canaryl [livalerieann","jonathan","michael"l Tutorial II: A Closer Look at Domains, Objects and Lists45 Todeclarea domain for listsof integers,we usea declarationsuchas domains integerlist= integer* where the asterisk indicates that there are0or more elementsina list. The objectsina list canbe anything,including other lists.However, allelementsina list mustbelongtothesamedomainandtheremustbeadomainsdeclarationforthe objects that follows thisform: domains objectlist= objects* objects TurboPrologprocessesa listbydividingit into two parts:theheadandthe tail.The headof thelist [1,2,3]istheelementI.The tailof [1,2,3]isthelist youget whenyou remove thehead,namely [2,3]. Table 4-3List Processing List ['a','b','c'] [I ] [ ] [[ 1,2.3],[2,3,4].[]] HeadTail 'a'['b','c'] undefined [1,2,3] [] (anemptylist) undefined [[2,3,4],[]] Turbo Prolog usesa verticalbar (I) to separate the headandtailof a list.Hence,a list withheadXandtailY iswritten [XIY] If TurboProlog tries to satisfy the goal scores([XIY]) andfindsthe fact scores([0,1,0,2,6,0,0,1,2,3]) the variable Xwillbebound to theheadof the list,i.e.,to theinteger 0,andY willbe bound to the tailof thelist,i.e.,the list [1,0,2,6,0,0,1,2,3,]. Table 4-4 gives severalexamples of list matching.Free variables are boundinthe same way asXandY inthepreviousexample. ListI [X,y,z] [7] [1,2,3,4] [1,2] 46 Table 4-4List Matching List2 [egbert,eats,icecream] [XI Y] [X, YIZ] [3I X] VariableBinding X = egbert,Y = eats,Z = icecream X=7, Y=[] X= I,Y=2, Z=[3,4] Thecomparisonfails,since theheadsof the two listsdiffer. TurboPrologOwner's Handbook Using Lists Inthisandthefollowingtwosections,we'llexaminesometypicalTurboProloglist- processing predicates. ListMembership Supposewehavea list with thenames [john,leonard,eric,frankJ -andwouldlike to useTurboProlog to investigateif a givennameisinthe list.Inother words, we must express the relation member between two objects-a name anda list of names--corresponding to thepredicate statement member(name,namelist). InProgramII, the first clauseinvestigates the headof the list.If the headisequal to the Namewe aresearching for,we canconclude that Nameisa member of thelist.Since the tailof thelistisof nointerest.it isindicatedby "_".Thanksto thisfirstclause,the goal member(john,[john,leonard,eric,frankJ) issatisfied. 1*Program11*1 domains namelist=name* name= symbol predicates member(name,namelist). clauses member(Name,[Namel_J). member(Name,[_ITailJ)ifmember(Name,Tail). If the head of the list isdifferent from Name, we need to investigate whether Name can be foundinthe tailof thelist.InEnglish: "Name isa member of thelist if Name ismember of the tail" andinTurboProlog: member(Name,[_ITailJ)ifmember(Name,Tail). ExerciseTypeinthe above program andtry the following goal: member(susan,[ian,susan,johnJ) Add domain andpredicate statements so that the member predicate canalsobeused to investigateif a numberisa member of a listof numbers.Try severalgoalsto test your resultingnew program,including Tutorial II: ACloser Look at Domains,Objects and Lists47 ExerciseDoestheorderof thetwoclausesforthememberpredicatehaveany significance?Test thebehavior of theprogramwhenthe two rulesareswapped.The difference appearsif the goal istestedinboth situations. Writing Elements of a List Now we'll define a predicate that writes out elements of a list on separatelines.Again, we needto think recursively. write_a_list([)). write_a_list([HeadITail))if write(Head),nl,write_a_list(Tail). Thefirstclausesays:Stopwhentherearenofurtherelementsinthelist(thelistis empty); the second says:Write the headof the list, write a newline, and then dealwith the tail. ExerciseComplete thewrite_a-1istprogramabove andtest thefollowing goal: Appending One List to Another: Declarative andProcedural Programming As given, the member predicate of ProgramIIworks in two ways.Consider its clauses onceagain: member(Name,[Namel_)). member(Name,[_ITail))ifmember(Name,Tail). Wecanthinkof theseclausesfromtwodifferentpointsof view.Froma declarative viewpoint they say that,given a list,Nameisa member of that list if itsheadisName;if not,Nameisamemberof thelistifitisamemberof itstail.Fromaprocedural viewpoint the two clauses couldbe interpreted: to find a member of a list, findits head, otherwise finda member of itstail. These two points of view correspond to thegoals and since,ineffect, the first goal asks Turbo Prolog to check that something istrue, whereas thesecondasksTurboProlog to findallmembers of thelist [1,2,3,4]. The beauty of Turbo Prolog liesinthe fact that,often,if we construct the clausesfor a predicatefromonepoint of view,they'llwork for theother.Asanexampleof this, we'llnowconstructapredicatetoappendonelisttoanother.Forexample,let's appendthelists[1,2,3]and[4,5] to form thelist [1,2,3,4,5].We'lldefinethepredicate append with three arguments: append(Listl,List2,List3) 48TurboPrologOwner's Handbook Thiscombines List IandList2to form List3.Once againwe are usingrecursion(from a proceduralpoint of view). If List Iisempty,theresultof appendingList IandList2willbethesameasList2.In TurboProlog: append([),List2,List2). Otherwise,wecancombineList IandList2to formList3bymaking theheadof List I the head of LisG.(Below, the variable Xisused as the headof both List I andList3).The restof List3(itstail)isobtainedbyputting together therest of List Iandthewholeof List2.(The tailof List3isU, whichiscomposedof the rest of List I (namely, L I) and the wholeof List2.InTurboProlog: append([XIL1),List2,[XIL3))if append(L1,List2,L3). The append predicate thusoperatesasfollows:While List Iisnot empty, therecursive ruletransfersoneelementatatimetoList3.WhenList Iisempty,thefirstclause ensuresthat List2hooksonto thebackof List3. ExerciseThetwopredicatesappendandwritelistareintheTurboProlog programbelow.Typeintheprogram andrunit with thefollowing goal: append([1,2,3),[S,6),L)andwritelist(L). Now try thisgoal: append([1,2),[3),L),append(L,L,LL),writelist(LL). 1*Program12*1 domains integerlist=integer* predicates append(integerlist,integerlist,integerlist) writelist(integerlist) clauses append([),List,List). append([XIL1),List2,[XIL3))if append(L1,List2,L3). writelist([),([)). writelist([HeadITail))if write(Head),nl,writelist(Tail). One Predicate Can HaveSeveral Applications Lookingatappendfromadeclarativepointofview,wehavedefinedarelation betweenthreelists.Thisrelationalsoholdsif List IandList3areknownbut List2isn't and if only List3isknown.Forexample,to findwhichtwo listscouldbeappendedto form a knownlist,we couldusea goalof the form for whichTurbo Prolog willfindthe solutions Tutorial II: A Closer Look at Domains,Objects and Lists49 L1[ ],L2=[1,2, L;] L1[1],L2= [2,L;] L1[1,2],L2=[L;] L1[1,2,L;],L2=[] L; solutions We canalsouseappend to findwhichlist couldbeappendedto [3,4] to form thelist [1,2,3,4]by giving the goal append(L1,[3,L;],[1,2,3,L;]). Turbo Prolog finds the solutionL I=[1,2]. append hasdefined a relationbetween aninput set andanoutput set insucha manner that the relationappliesboth ways.We canthereforeask "Which output corresponds to thisgiveninput?" or "Whichinput corresponds to thisgivenoutput?" ExerciseBy amending the clausesgivenfor member inProgramII, construct clauses for a predicateevenmemberwhichwouldbesolvedgivena goal evenmember(2,[1,2,3,L;,5,6]). andwhich,given the goal evennumber(X,[1,2,3,L;,5,6]). woulddisplay X=2 X=L; X=6 3solutions 50TurboPrologOwner' s Handbook 5Tutorial III:Turbo Prolog's Relentless Search for Solutions Thischapterfallsintotwomainparts.Inthefirst,weexamineindetailtheprocess TurboProloguseswhentryingtomatcha goalwithaclause.Thisprocessiscalled unificationandcorresponds to parameter passinginother programming languages. Inthesecondpart,you'lllearnhow to controlTurboProlog'ssearchfor solutionsof goals. This will include techniques that make it possible for a program to carry out a task whichwouldotherwisebeimpossible,either becausethe searchwould take too long or (lesslikely with TurboProlog) becausethe systemwouldrunout of freememory. MATCHING THINGSUP: THE UNIFICATION OF TERMS Consider Program13interms of the (external) goal written_by(X,y). 1*Program13*1 domains title, authorsymbol pagesinteger publicationbook(title,page) predicates written_by(author,publication) long_novel(Title) clauses written_by(fleming,book("DRNO",210)). written_by(melville,book("MOBYDICK",bOO)) long_novel(Title):-written_by(_,book(Title,Length)), Length>300. WhenTurboPrologtriestofulfillthegoal,itmusttryeachof theclausesforthe predicate written-.by in turn, trying to get a match between the parameters X andYand theparametersineachclauseforwritten_by.Thistermmatchingoperationiscalled unification. 51 SinceXandYare free variablesin thisgoal,anda free variablecanbe unified with any other term, the very first clauseunifieswith the goalclause written_by (XY written_by(fleming,book("MOBYDICK",boo)) ThusXbecomesbound to fiemingandY becomesbound to book(" MOBY DfCK",600) soTurboProlog displays X =fleming,Y =book("MOBYDICK",boo) 1Solution If,on theother hand,we giveProgram13the goal written_by(X,book("MOBYDICK",Y)). thenagainunificationisattemptedwith the first clausefor written_by(X,book("MOBYDICK",Y)). I I written_by(fleming,book("DRNOli,210)). SinceXisfree,it becomesbound to fieminganda matchisattemptedbetween book("DRNOli,200) and book("MOBYDICK",Y) Acompound term canunify with another compound term provided they both involve the samefunctor andthe samenumber of arguments,andallthe subterms unify pair- wise.Inthiscase,thefunctoristhesame(book)andthenumber of subtermsistwo ineachcase.However,theconstant MOBYDICKcanunifyonlywithitself or witha free variable.Thus,no matchispossiblebetween MOBY DICK andDRNO andunifica- tionfails. TurboProlog now attemptsa matchbetween written_by (X, book( "MOBYDICK",Y)) and written_by(melville,book("MOBYDICK",boo)) The free variable Xunifies (andbecomesbound with) the constant melville.The com- poundterms book("MOBYDICK",Y) and book("MOBYDICK",boo) unify,sincetheybothinvolvethesamefunctorbook;theyhavethesamenumber of arguments;theconstantMOBYDICKunifieswithitself;andtheconstant 600canbe unifiedwith the freevariableY.Thus the goalsucceedsandTurboProlog responds 52 X = melville,Y =bOO 1Solution Turbo Prolog Owner's Handbook Finally,considerexecutionof thegoal long_novel(X). When TurboProlog triesto fulfilla goal,it investigateswhether or not thereexistsa matching fact or left sideof a rule.Inthiscase,thematchiswith theleft sideof a rule long_novel(X ) long_novel(Title):- written_by(_,book(Title,Length)),Length>300. sincethe free variable Xcanbe unified with anyother term and,inparticular,another free variable.Next, Turbo Prolog makes the first clauseon the right side of thisrule the current sub-goal,andunificationisachievedwith the first fact for written-1Jyasfollows: written_by(Name,book(Title,Length)) written_by(fleming,book("DRNOli,210)) inwhichLengthhasbecomebound to 210. Now thesecondclauseontherightsideof thelongJJovelrulebecomesthecurrent sub-goal Length>300 Before unificationisattempted, the bound variableLengthisreplacedwith the value to whichit isbound,210.Since 210>300 isa legalcomparisonof two integer values,thecomparisonismade-and, of course, returns false.TurboProlog now attempts a different unificationof written_by(Name,book(Title,Length)) (seethenext section) andbindsTitleto "MOBYDICK"andLengthto 600.Now Length>300 unifieswithLengthreplacedby600(thevalueto whichit isbound)andindeedsuc- ceeds,sothatlongJJovelalsosucceedswithTitleboundto"MOBYDICK".Turbo Prolog displays X ="MOBYDICK" 1Solution Summaryof TurboProlog'sUnificationAlgorithm •Afree variable canbe unified with any term. The variableis then bound to the other term. •Aconstant (aninteger,for example) canunify withitself or with a freevariable. •Acompoundtermcanunifywithanothercompoundterm,providedtheyboth involve thesamefunctor andhavethe samenumber of arguments.Further,allthe subterms must unify pairwise. (Lists are treated asa specialkindof compound term). Tutorial III: Turbo Prolog's Relentless Search for Solutions53 Boundvariablesarereplacedwiththevaluetowhichtheywereboundprior to unification. Thus,unification takescareof: •Assigning values to variables (i.e.,parameter passing). •Accessingdata structures viaa generalpattern-matching mechanism. •Certainkindsof testsfor equality. CONTROLLING THE SEARCH FOR SOLUTIONS Inthissectionwe'lllookatsometechniqueswecanusetocontrolTurboProlog's searchfor solutions of our goals. Let's start by looking at Program14inlight of this goal, which cOl'1sistsof two subgoals: likes(X,wine)andlikes(X,books) 1*Program *1 domains name,thing=symbol predicates likes(name,thing) reads(name) is_inquisitive(name) clauses likes(john,wine). likes(lance,skiing). likes(Z,books)if reads(Z)and is_inquisitive(Z). likes(lance,books). likes(lance,films). reads (john) . is_inquisitive(john). When evaluating the goal,TurboProlog notes whichsubgoalshavebeensatisfiedand whichhavenot.This searchcanberepresentedby a goaltree: Before goalevaluation begins, the goal tree consists of two unsatisfiedsubgoals.Inwhat follows below, subgoals already satisfiedin a goal tree are underlined with a dotted line, andthe corresponding satisfying clauseheadisshown underneath. Inourexample,thegoaltreeshowsthat two subgoalsmustbesatisfied.Todoso, Turbo Prolog follows thefirstbasicprinciple: Subgoalsmust besatisfied fromlefttoright. 54Turbo Prolog Owner's Handbook The clause Turbo Prolog chooses to satisfy the first subgoalisdetermined by the second basicprinciple: Predicateclausesmust betested intheorderthey appearintheprogram. When executing Program14,TurboProlog findsa suitableclauseinthe firstfact.Let's look at the goaltree again: /\ likes(X,wine)likes(X,booksj likes(john,wine) The subgoal likes(X,wine) matches thefact: likes(john,wine). bybinding X to the value john.TurboProlog next tries to satisfy the next subgoal to the right. The satisfactionof the secondsubgoalstarts a completelynew searchprocedure, with X=john.The firstclause likes(john,wine) . doesnotmatchthe subgoal likes(X,books) sincewineisnot thesameasbooks.TurboPrologmust therefore trythenext clause, but lancedoesnot matchthe valueof X (john),so thesearchcontinues withthe third clause likes(Z,books)ifreads(Z)andis_inquisitive(Z). TheparameterZisavariableandsomatcheswithX,andthesecondparameters agree.When Xmatches Z,TurboPrologdemands that Zalsobeboundto the value john. Weknownow that the subgoalmatchestheleftsideof a rule.Continued searchingis determinedbythethirdbasicprinciple: Whena subgoalmatchestheleft sideof a rule,therightsideof thatrulemustbe satisfied next.Therightsideconstitutesthenew set of subgoals. Fromthiswe get the followinggoaltree: A likes(X,wine)likes(X,books) likes(john,wine)likes(Z,books) d /.\... reas(Z)lS_lnqulsltlve(Z) Tutorial Ill: Turbo Prolog's Relentless Search for Solutions55 The goaltree now includes the subgoals reads(Z)andis_inquisitive(Z) whereZhasthevalue john.TurboProlog willnow searchfor factsthatmatchboth subgoals.Theresulting finalgoaltree isshownbelow: A likes(X,wine)likes(X,books) likes(john,wine)likes(Z,books) /\ reads(Z)is_inquisitive(Z) reads(john)is_inquisitive(john) According to thefourthbasicprinciple: A goalhasbeen satisfied whena matchingfactisfoundforalltheextremities (leaves) of thegoaltree, sowe know now that our initialgoalissatisfied. Turbo Prolog uses the resultof thesearchprocedure indifferent ways,depending on how it was initiated. If the goalisa subgoalin a rule, Turbo Prolog keeps trying to satisfy the next subgoalin the rule.If the goalisa question from the user, Turbo Prolog replies directly: X =john 1solution Goal: Aswe sawinChapter 3,having oncesatisfieda goal,TurboProlog backtracks to find alternative solutions. It willalsobacktrack if a subgoal fails,hoping to resatisfy a previous subgoalinsucha way that the failedsubgoalissatisfiedwithnew variablevalues. To fulfill a subgoal, Turbo Prolog begins a search with the first clausein a predicate. Two thingscanhappen: I.Amatching clauseheadisfound.The following thenhappens: a.If thereisanother clausethat canpossiblyresatisfy thesubgoal,the first such clauseismarkedwith a pointer to indicate a backtrackingpoint. b.Allfreevariablesinthesubgoalthatmatchvaluesintheclauseheadare assignedthesevalues(thevariablesbecomebound). c.If the matching clauseis the left side of a rule, that rule must be satisfied. This is doneby treating theright sideof theruleasa new goal. 2.Amatchingclauseheadcannotbefoundandthegoalfails.TurboPrologback- tracksasit attempts toresatisfyaprevioussubgoal.Allvariablesthat werefree before the subgoalwaspreviously satisfiedaremade freeagain. 56 TurboPrologfirstsearchestheclauseindicatedbythepointer.If thesearchis unsuccessful,it backtracks again.If backtracking exhausts allclauses for allsubgoals, the goalfails. Turbo Prolog Owner's Handbook Use of Fail Turbo Prolog contains a standardpredicate that forces backtracking-fail. The effect of failcorresponds to the effect of 2=3. We'lluseProgram15to illustrate theuseof this predicate. 1*Program15*1 domains name= symbol predicates father(name,name) everybody clauses father(leonard,katherine). father(carl,jason). father(carl,marilyn). everybodyif father(X,y)and write(X,1IisII,Y,II'sfather\n ll )and fail. The goalfather(X, Y)couldbeusedintwo different situations: •Asaninquiry to the TurboProlog system(anexternal goaO •On theright sideof a rule (aninternal goaO,asin: grandfather(X,B)iffather(X,y)andfather(Y,B). With father(X, Y)asanexternal goal,Turbo Prolog will write out allpossible solutions in theusualway: X=....,Y=... . X=....,Y=... . ....solutions Withfather(X, Y)asaninternalgoal,TurboProlog willcontinuewith thenext subgoal onceit hasbeensatisfiedandwilldisplayonlyonesolution.However,thepredicate everybodyinProgram15usesthefailpredicate to disturb theusualmechanism. Theobject of thepredicateeverybodyisto produceneaterresponsesfromprogram runs.Compare the answers to the two goals Goal:father_to(X,y) X=leonard,Y =katherine X=carl,Y=jason X=carl,Y=marilyn 3solutions Goal:everybody leonardiskatherine'sfather carlisjason'sfather carlismarilyn'sfather Nosolution Thepredicateeverybodymakesuseof backtrackingtogeneratemoresolutionsfor father(X, Y)by trying to satisfy theright sideof everybody: father(X,Y)andwrite(X,1IislI,y,llIsfather\n ll )andfail. Tutorial III: Turbo Prolog's Relentless Search for Solutions57 Thesesubgoalsmust besatisfiedfrom left to right.The first father(X,y) canbe satisfiedwith X= leonard andY = katherine,sothat TurboProlog continues to thenext subgoal,the standardpredicate write.It fulfillsits task by writing some values, andthencontinues to thelast subgoal,thestandardpredicatefail. Failcanneverbesatisfied,soTurboPrologisforcedtobacktrack.writecannotbe resatisfied(offernewsolutions),soTurboPrologmustbacktrackagaintothefirst subgoal. Anewsolution,namelyX= carlandY = sam,isfound.TurboPrologcannow continue to the next subgoal,where the valuesare written out,andfinallyreaches the last subgoal-fail-which once againinitiatesbacktracking,andsoon. ExerciseTypeinProgram14andevaluate the following goals: father(X,y). and everybody. Why are the solutions to everybody terminatedby False?For a clue,append: everybody asa secondclauseto the definitionof predicateeverybody andreevaluatethe goal. PREVENTING BACKTRACKING: THE CUT ELEMENT TurboPrologcontainsanelement thatpreventsbacktrackingundercertaincircum- stances.Theelementiscalledthecutandiswrittenasanexclamationmark ( !).Its effect issimple: Itisimpossibletobacktrackpast a cut There are two mainusesof the cut: •When you know in advance that certain possibilities will never give rise to meaningful solutions, soit isa waste of time andstorage space to backtrack over them.By using a cut inthissituation,theresultingprogramwillrunquicker anduselessmemory. •When thelogicof a programdemands thecut. Inthefollowing examples,we willuseseveralschematicTurboPrologrulesrl,r2,r3 whichalldescribe thesamepredicate r,plusseveralsubgoalsa,b,c,etc. Using theCut toPrevent Backtracking toa PreviousSubgoal in aRule r1ifaandband!andc. Thisisawayof tellingTurboPrologthatwearesatisfiedwiththefirstsolutionof subgoalsa andb.As a concrete example,consider Program16.It isbasedon the idea that two peoplemight likeone another if they haveat least oneinterest incommon. 58Turbo Prolog Owner's Handbook 1*Program1b*1 domains name,sex,interest=symbol interests=interest* predicates findpairs person(name,sex,interests) member(interest,interests) common_interest(interests, interests, interest) clauses findpairsifperson(Man,m,ILIST1)and person(Woman,f,ILIST2)and common_interest(ILIST1,ILIST2,_)and write(Man,IImightlikeII,Woman)andnland fail. findpairs:- write(II-----------endofthe1ist--- II ). common_interest(IL1,IL2,X )if member(X,IL1)andmember(X,IL2)and!. person(tom,m, [travel,books,baseball1). member(X,[XI_1). member(X,[_IL1)ifmember(X,L). Theuseof thecutinthepredicate isthereasonthepredicatefinds onlyonecommoninterest.If the cut werenot employed,thesamenameswouldbe writtenmany timesif the personshadmany interestsincommon. Using theCut toPrevent Backtracking totheNext Clause This isa way to tell Turbo Prolog that it has chosen the correct clause for thispredicate. For example,given r1if!andaandbandc. r2if!andd. r3ifc. thetwocutsensurethatonlyoneof thefollowingclausesrl,r2or r3willbeused. (Remember,rl,r2,r3areclausesfor the samepredicate r). Our example inthiscaseisbasedonProgram9 (Chapter 4),which defined the facto- rialpredicate without the useof the cut: factorial(1,1). factorial(N,Res)if N>1and N1=N-1and factorial(N1,Temp)and Res=N*Temp. The condition N> I was necessary, since the second clausecould be satisfied with N = I. Without thisconditionthefirstargumentinfactorialcouldbecomenegativeandthe program wouldloop forever (or untilmemory wasexhausted). Tutorial Ill: Turbo Prolog's Relentless Search for Solutions59 With theuseof the cut,however,we canadopt thenew clauses factorial(1,1)if!. factorial(N,Res)if N1=N-1andfactorial(N1,Between)andRes=N*Between. where the cutindicates that,for N= I.the secondclauseshouldnot betested. Determinism and theCut The member predicate (definedinChapter 4) isanexample of a predicate having non- deterministicclauses,i.e.,clausescapableof generating multiple solutions through back-. tracking.Inmanyimplementationsof TurboProlog,specialcaremustbetakenwith non-deterministicclausesbecauseoftheattendantdemandsmadeonmemory resourcesatruntime.InTurboProlog,however,internalchecksaremadefornon- deterministic clauses and these are dealt with in a specialway, thusreducing the burden upon theprogrammer. However,for debugging (andother) purposes,it canstillsometimesbenecessaryfor the programmer to intercede and the checLdeterm compiler directive isprovided for this reason.If check determisinserted at the very beginning of a program, a warning will be displayed if any non-deterministic clauses are encountered during the evaluation of a goal.Pressing[!1[)causesthewarningtobeignored,whilepressinganyotherkey abortsevaluationof thegoal. Non-deterministicclausescanbemadedeterministicbyinsertingcuts.Thus, verifyJTlember withclauses verify_member(X,[XI_l)):-! verify_member(X,[_IY1):-verify_member(X,y). isa deterministic version of member, the only difference between the two being the cut to stopbacktrackinginthefirst clause. verifyJTlembercanbeusedto check that anelement isa member of a givenlist,but cannotbeusedina goallike verify_member to successivelybindXto themembersof [1.2,3.4,5],sincethegoalsucceedswithX bound toIandnobacktracking takesplace. 60Turbo Prolog Owner's Handbook ExerciseSupposeanaveragetaxpayerintheUSA isa UScitizen,a marriedperson with two children,andearnsno less than$500 a month andno more than$2,000 per month.Define a TurboProlog predicate speciaLtaxpayer which,with thisgoal special_taxpayer(fred). will succeedonly if fredfailsone of the conditions for anaverage taxpayer. Use the cut to ensure that thereisnounnecessarybacktracking. ExercisePlayersina certainsquashclubaredividedinto threeleagues,andplayers may only challengemembers intheir own leagueor the leaguebelow (if thereisone). WriteaTurboPrologprogramthatwilldisplayallpossiblematchesbetweenclub playersinthe form: tomversusbill marjoryversusannette Use the cut to ensure,for example, that tomversusbill and billversustom arenot bothdisplayed. Tutorial III: Turbo Prolog's Relentless Search for Solutions61 62Turbo Prolog Owner's Handbook 6Tutorial IV: Arithmetic, Simple Input and Output, and Debugging TurboProlog'sarithmeticcapabilitiesaresimilartothoseprovidedinprogramming languages such asBASIC, C andPascal.It includes a fullrange of arithmetic functions and standardpredicates asdiverse asthe arctangent function, anda family of predicates for bitwiselogicaloperations.Thesearedescribedinthefirstpart of thischapter,along with standardpredicates for basic input and output of numeric and non-numeric values. The finalpart of thischapterresumesthediscussionof debuggingat thepoint where Chapter 2 left off.As programs become larger andmore complex, you'll require more control over the amount of information produced by the various trace facilities, and this section tellshow to gainthat control. PROLOG CAN DO ARITHMETIC TOO! We have already seensome simpleexamples of Turbo Prolog's arithmetic capabilities. TurboPrologcanperformallfourbasicarithmeticoperations(addition,subtraction, multiplication anddivision) between integer andreal values, the type of the result being determined according to Table6-1. Table6-1Arithmetic Operations OeerandIOeeratorOeerand2Result integer+,-, *integerinteger real+,-, *integerreal integer+,-, *realreal real+,-, *realreal integer or realinteger or realreal 63 The Order of Evaluation of Arithmetic Expressions Arithmetic expressions,suchasthe oneon theright sideof the=predicatein A = 1+6/(11+3)*z may includeoperands(numbersandvariables),operators+,-, *,I,andparentheses "("and")".Hexadecimalnumbers areidentifiedby a preceding dollar sign.The valueof anexpressioncanonly becalculatedif allvariablesarebound at the time of evaluation. This calculationmust then be made ina certain order, determined by the priority of the arithmetic operators; operators with the highest priority are evaluated first. Thus,eval- uationof arithmetic expressionsproceedsasfollows: •If theexpressioncontainssubexpressionsinparentheses,thesubexpressionsare evaluatedfirst. •If theexpressioncontains* (multiplication) or I (division),theseoperationsarecar- riedout next,working fromleft to right through the expression. •Finally+ (addition)and- (subtraction) arecarriedout,againworking fromleft to right. Returning to our example expression, since variables must be bound before evaluation, assumethat Zhas thevalue4.Thevalueof (II + 3)isthefirstsubexpressiontobe evaluated, andit evaluates to14.Now 6/14canbe evaluated to give 0.428571and then 0.428571 *4 gives1.714285.Finally,evaluating1+ 1.714285 gives the value of the expres- sion as2.714285.If A belongs to a domain of real type, A will be bound to 2.714285,but if A belongs to a domain of integer type, A willbebound to 2. Comparisons Inthe following statement: X+L;< 9- y Table6-2Operator Priority Operator +- * / moddiv - + (unary) Priority I 2 3 4 (which is the Turbo Prolog equivalent of: The total of Xand 4 isless than 9 minus Y),the relationaloperator< (lessthan)indicatestherelationbetween the twoexpressions, X+4and9-Y. If Value I andValue2represent thevaluesof the two expressions,we couldwrite thisrelationina "normal" TurboProlog statement format as less_than(Value1,Value2) We couldalsowrite the TurboProlog sentences plus(X,L;,Value1) minus(9,L;,Value) 64Turbo Prolog Owner's Handbook Table 6-3Relational Operators = or >< lessthanor equalto equal greater than greater thanor equalto different from to describehow X+4and9-Yare evaluatedto Va!ue!andVa!ue2,respectively.The entire comparisonX +4 V,down([V,Y1). Definition3 shortens singlepeak further by observingruleI.Thus,usingdefinition3 singlepeak(Y,up) succeedsif Y isbound to a singlepeakedlist appended to anascendinglist and singlepeak(Y,down) succeedsif Y isbound to a descendinglist. Programmer's Guide147 Definition3 singlepeak([l,_). singlepeak([_l,_). singlepeak([U,VIW1,up):- UV,singlepeak([VIW1,down). Rule4.LetTurboProlog'sunificationmechanismdoasmuch of thework aspossible.At first thought, youmight think to define a predicate equal to test two lists for equality as equal ( [ 1, [ 1) . equal([UIX1,[UIY1):- equal(X,y). but thisisunnecessary.Using the definition equal(X,X). TurboProlog'sunificationmechanismdoes allthe work! Rule5.Usebacktrackinginsteadofrecursiontoeffectrepetition.Backtracking decreases stack requirements. The idea is to use the repeat . .. failcombination instead of recursion.Thisissoimportant that the next sectionisdedicated to the technique. Useof the Fail Predicate Tohavea particular sequence of subgoalsevaluatedrepeatedly,it isoften necessary to define a predicatelikerunwith a clauseof the form run:- readln(X), process(X,y), write(Y) , run. thusincurring unnecessary tailrecursionoverheads that cannot be automatically elimi- natedby the systembecauseprocess(X, Y)involvesbacktracking. Inthiscase,therepeat. .. failcombinationavoids the needfor the finalrecursivecall. Given repeat. repeat:-repeat. we canredefinerunwithout tailrecursionasfollows: run:- repeat, readln(X), process(X,y), write(Y) , fail. failcausesTurbo Prolog to backtrack to process,and eventually to repeat,which always succeeds. 148Turbo Prolog Owner's Handbook Determinism,Non-determinism andHow toSet theCut The compiler directive checLdeterm isuseful when you need to decide where to place thecut,sinceit marks thoseclauseswhichgiveriseto non-deterministic predicates.If youwant tomakethesepredicatesdeterministic,thecut willhavetobeinsertedto stopthebacktracking(whichcausesthenon-determinism).Asa generalruleinsuch cases,the cut should alwaysbe inserted asfar to the left aspossible without destroying theunderlying logicof theprogram. DomainsContaining References Consider thepredicate lookupinProgram62 during the evaluationof thegoal lookup(tom,27,Tree), lookup(dick,28,Tree), lookup(harry,26,Tree). IIProgram62II domains treereferencet(id,val,tree,tree) id= symbol val= integer predicates lookup(id,val,tree) clauses lookup(ID,VAL,t(ID,VAL,_,_)):-l. lookup(ID,VAL,t(ID1,_,TREE,_)):- ID> Text buffer full


Comments

Copyright © 2025 UPDOCS Inc.