DOC PREVIEW
Berkeley COMPSCI 164 - Implementing Prolog

This preview shows page 1-2-3-4-28-29-30-31-58-59-60-61 out of 61 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 61 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 61 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 61 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 61 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 61 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 61 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 61 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 61 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 61 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 61 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 61 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 61 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 61 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1Where are we heading today?TodayProlog refresherStructure of ProgramsUnificationTwo exercisesUnification algorithmToday, you will design a series of algorithmsWe will start with subsets of PrologSome algorithms will use “magic”Algorithm (1, no choice)Prolog execution is finding a proof of query truthProof treeLet’s trace the process of the computationNow develop an outline of the interpreterAlgorithm (1,no choice) w/out handling of mgusConcepts: Reduction of a goal. Unifier.An algorithmic question: when to merge mgusDesign question: How do MGUs propagate?MGUs propagate the answerMGUs propagate the answerBoth up and down propagation is neededAlgorithm (1,no choice) with unification, style 1Algorithm (1,no choice) with unification, style 2Summary of Algorithm for (1, no choice)DiscussionUnify and subst used in PA3Example executed on PA3 PrologAlgorithm (n, no choice)ResolventAlgorithmStudent algorithmWhat to change in (n, no choice)?Your exerciseSummaryExample executed on PA3 PrologAlgorithm (1, oracular choice)Search treeExample search tree (for Append)AlgorithmAlgorithm for (1,oracle choice)SummaryAlgorithm (n, oracular choice)Analysis of this problemWhat to change in (n, no choice)?Algorithm (1, backtracking)Implementing the oracleAlgorithm for (1,backtracking)ExampleThe implementation structureExample executed on PA3 PrologAlgorithm (n, backtracking)Algorithm (n,backtracking) is the key task in PA3ExampleAlgorithm (2, backtracking)Algorithm (2,backtracking), cont.The complete view of control transferExample executed on PA3 PrologAlgorithm (n, backtracking)Reading1Lecture 7Implementing Prologunification, backtracking with coroutinesRas Bodik Shaon BarmanThibaud HottelierHack Your Language!CS164: Introduction to Programming Languages and Compilers, Spring 2012UC BerkeleyWhere are we heading today?Today, we’ll go deeper into the territory of programming under abstraction −developing abstractions that others can conveniently use.Previously in cs164, we built constructs with yielditerators (L4), lazy list concatenation (HW2),regexes based on backtracking (HW2)Today, we will build Prolog, an entirely new languagePA3 is assigned today: Prolog on top of your PA2 coroutines2TodayFind a partner. Get a paper and pencil. You will solve a series of exercises leading to a Prolog interpreter.3Prolog refresher4Program:eat(thibaud, vegetables).eat(thibaud, fruits).eat(lion, thibaud).Queries:eat(thibaud, lion)?eat(thibaud, X)?Structure of Programsworks(ras). Fact (Axiom)works(thibaud) :- works(ras). Ruleworks(X)? QueryIn a rule:a(X, Y) :- b(X,Z), c(Z,Y) VariableConstantHead BodyFree VariableClauseUnificationUnification is what happens during matching.What does it means to be compatible?a(1,Y) | a(X,2)a(X) | b(X)a(1,Y) | a(2,X)a(1, Y) | a(1, X)A call to unify(term1, term2) yields most general unifier(mgu)6Two exercisesFind mgu for these two unifications:a(X,Y) | a(b(Y),c(Z))a([1|X]) | a(X)7Unification algorithmSee the simple description in The Art of PrologChapter 4.1, pages 88-91.8Choice of clausebacktrackingby oraclenot needed1 nnumber of clauses on the rhs of rulesToday, you will design a series of algorithms9Choice of clausebacktrackinga(X) :- b(X).b(Y) :- c(Y).c(1).c(2).a(X) :- b(X), c(X).b(2).c(1).c(2).by oraclenot neededa(X) :- b(X).b(Y) :- c(Y).c(1).a(X) :- b(X), c(X).b(1).c(1).1 nnumber of clauses on the rhs of rulesWe will start with subsets of Prolog10Choice of clausebacktrackingdeterministic algorithm (all steps determined by the algorithm)by oraclenon-deterministic algorithm(crucial choices made by oracle)not neededdeterministic algorithm (all steps determined by the algorithm)1 nnumber of clauses on the rhs of rulesSome algorithms will use “magic”11Choice of clausebacktrackingby oraclenot neededa(X) :- b(X).b(Y) :- c(Y).c(1).1 nnumber of clauses on the rhs of rulesAlgorithm (1, no choice)12Prolog execution is finding a proof of query truthProgram:a(X) :- b(X).b(Y) :- c(Y).c(1).Goal (query):?- a(Z).Answer: trueZ = 113Proof that the query holds:c(1) base fact, implies that …c(Y) holds, which implies that …b(Y) holds, which implies that …b(X) holds, which implies that …a(X) holds, which implies that …a(Z) holds. The last one is the queryso the answer is true!Recall “c(Y) holds” means exists value for Y such that C(Y) holds.Proof treeProgram:a(X) :- b(X).b(Y) :- c(Y).c(1).Goal (query):?- a(Z).Answer: trueZ = 114These steps form a proof treea(Z)a(X) b(X) b(Y) c(Y) c(1) trueN.B. this would be a proof tree, rather than a chain, if rhs’s had multiple goals.Let’s trace the process of the computationProgram:a(X) :- b(X).b(Y) :- c(Y).c(1).Goal (query):?- a(Z).Answer: trueZ = 115Two operations do all the work:a(Z) the query is out initial goala(X) match head of a(X):-b(X) b(X) reduce goal a(X) to goal b(X) b(Y) match head of b(Y):-c(Y) c(Y) reduce b(Y) to c(Y) c(1) match head of c(1). true we matched a factThe operations:1) match goal to a head of clause C2) reduce goal to rhs of CNow develop an outline of the interpreterStudent answer:16Algorithm (1,no choice) w/out handling of mgusdef solve(goal): match goal against the head C.H of a clause C // how many matches are there? Can assume 0/1 if no matching head found: return FAILURE // done if C has no rhs: return SUCCESS // done, found a fact else // reduce the goal to the rhs of C return solve_goal(C.rhs)Note: we ignore the handling of mgus here, to focus on how the control flows in the algorithm. We’ll do mgus next …17Concepts: Reduction of a goal. Unifier.We reduce a goal to a subgoalIf the current goal matches the head of a clause C,then we reduce the goal to the rhs of C.Result of solving a subgoal is a unifier (mgu)or false, in the case when the goal is not trueBut what do we do with the unifiers?are these mgus merged? If yes, when?18An algorithmic question: when to merge mgusProgram:a(X) :- b(X).b(Y) :- c(Y).c(1).Goal (query):?- a(Z).Answer: trueZ = 119Unifications created in matchinga(Z)a(X) Z=X b(X) b(Y) X=Y c(Y) c(1) Y=1 trueResult is conjunction of these mgus:Z=X, X=Y, Y=1So, the answer is Z=1 internal variables X,Y are suppressedDesign question: How do MGUs propagate?20Down the recursion? or …a(Z)a(X) Z=X b(X) b(Y) Z=X, X=Y c(Y) c(1) Z=X, X=Y, Y=1 trueMGUs propagate the answer21… up the recursion or …a(Z)a(X) Z=X Z=X,X=Y,Y=1 b(X) b(Y) X=Y X=Y,Y=1 c(Y)


View Full Document

Berkeley COMPSCI 164 - Implementing Prolog

Documents in this Course
Lecture 8

Lecture 8

40 pages

Load more
Download Implementing Prolog
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Implementing Prolog and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Implementing Prolog 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?