Prolog’s Lists, Negation and Imperative Control Flow (Section 11.3)ListsLists ExamplesTic-Tac-Toe ExampleSlide 5Slide 6Slide 7Imperative Control Flow The cutImperative Control FlowProlog Database ManipulationLogic PuzzlesA Manual Solution (courtesy of Axel Schreiner)Manual SolutionSlide 14Prolog Solution (courtesy of Axel Schreiner)Prolog SolutionSlide 17Prolog Interpreter11Prolog’s Lists, Negation and Prolog’s Lists, Negation and Imperative Control FlowImperative Control Flow(Section 11.3)(Section 11.3)CSCI 431 Programming LanguagesCSCI 431 Programming LanguagesFall 2003Fall 2003A modification of slides developed by Felix A modification of slides developed by Felix Hernandez-Campos at UNC Chapel HillHernandez-Campos at UNC Chapel Hill22ListsLists•ConstructorsConstructors–[][] Empty list constantEmpty list constant–..Constructor functorConstructor functor•ExampleExample–.(a, .(b, .(c, []))).(a, .(b, .(c, [])))–[a, b, c][a, b, c] (syntactic sugar) (syntactic sugar)•Tail notation:Tail notation:–[a | [b, c]][a | [b, c]]–[a, b | [c]][a, b | [c]]HeadHeadTailTail33ListsListsExamplesExamplesNo notion of No notion of input or output input or output parametersparameters44Tic-Tac-Toe ExampleTic-Tac-Toe Example•3x3 grid3x3 grid•Two Players:Two Players:–X (computer)X (computer)–O (human)O (human)•Fact Fact x(n)x(n)indicates a indicates a movement by Xmovement by X–E.g.E.g. x(5), x(9)x(5), x(9)•Fact Fact o(n)o(n) indicates a indicates a movement by Omovement by O–E.g.E.g. o(1), o(6)o(1), o(6)55Tic-Tac-Toe ExampleTic-Tac-Toe Example•Winning conditionWinning condition66Tic-Tac-Toe ExampleTic-Tac-Toe ExampleStrategy: Strategy: goodgood moves movesOrdered List Ordered List of Choicesof Choices77Tic-Tac-Toe ExampleTic-Tac-Toe ExampleWinning SplitWinning SplitXX88Imperative Control FlowImperative Control FlowThe cutThe cut•Prolog has a number of explicit control flow featuresProlog has a number of explicit control flow features•!! Known as the Known as the cutcut–This is a zero-argument predicate that always succeedsThis is a zero-argument predicate that always succeeds–It commits the interpreter to the unification made between It commits the interpreter to the unification made between the parent goal and the left-hand side of the current rulesthe parent goal and the left-hand side of the current rules•ExampleExamplemember(X, [X|T]).member(X, [X|T]).member(X, [H|T]) :- member(X, T).member(X, [H|T]) :- member(X, T).member(X, [X|T]) :- !.member(X, [X|T]) :- !.member(X, [H|T]) :- member(X, T).member(X, [H|T]) :- member(X, T).member may member may succeed succeed nn times timesmember may succeed member may succeed at most oneat most one time timeIf this rule succeeded, do If this rule succeeded, do notnot try to use the following ones try to use the following ones99Imperative Control FlowImperative Control Flow•AlternativeAlternativemember(X, [X|T]).member(X, [X|T]).member(X, [H|T]) :- not(X=H), member(X, T).member(X, [H|T]) :- not(X=H), member(X, T).•How does How does notnot work? work?not(P) :- call(P), !, fail.not(P) :- call(P), !, fail.not(P).not(P).–callcall attempts to satisfy the goal P. attempts to satisfy the goal P.–failfail always fails. always fails.1010Prolog Database ManipulationProlog Database Manipulation•Two built-in predicates can be used to modify the Two built-in predicates can be used to modify the database of known factsdatabase of known facts•assert(P)assert(P) adds a new fact. adds a new fact.–E.g.E.g. assert(parent(kevin, john))assert(parent(kevin, john))•retract(P)retract(P) removes a known fact. removes a known fact.–E.g.E.g. retract(parent(kevin, john))retract(parent(kevin, john))1111Logic PuzzlesLogic PuzzlesAn Example (courtesy of Axel Schreiner):An Example (courtesy of Axel Schreiner):1. There are 3 boys and 3 girls.1. There are 3 boys and 3 girls.2. One girl is dressed in red, one in green, one in blue.2. One girl is dressed in red, one in green, one in blue.3. One boy is dressed in red, one in green, one in blue.3. One boy is dressed in red, one in green, one in blue.4. The boy in red danced with the girl in green.4. The boy in red danced with the girl in green.5. No boy danced with a girl who was dressed in the same color.5. No boy danced with a girl who was dressed in the same color.6. Which boy danced with the girl dressed in red?6. Which boy danced with the girl dressed in red?1212A Manual SolutionA Manual Solution(courtesy of Axel Schreiner)(courtesy of Axel Schreiner) A A constraintconstraint applies to applies to property values and is entered property values and is entered into the appropriate matrix. into the appropriate matrix. An assertion such as (4) is An assertion such as (4) is entered as a dot relating two entered as a dot relating two values for two properties:values for two properties:1313Manual SolutionManual Solution Each row and column can only Each row and column can only contain a single dot because contain a single dot because the relationship between the relationship between values is one-to-one. This can values is one-to-one. This can lead to further exclusions:lead to further exclusions:Exclusions such as (5) are Exclusions such as (5) are entered as crosses into the entered as crosses into the matrix. A cell may only matrix. A cell may only contain a dot or a cross, not contain a dot or a cross, not both:both:1414Manual SolutionManual Solution The process becomes more complicated once there The process becomes more complicated once there are more properties and therefore more matrices; are more properties and therefore more matrices; each property must be related to every other in a each property must be related to every other in a separate matrix.separate matrix. Eventually the solution can be read from the Eventually the solution can be read from the matrices: The boy in blue danced with the girl in matrices: The boy in blue danced with the girl in red.red.It can also lead to further dots It can also lead to further dots if only a single cell remains if only a single cell remains unfilled in a row or column:unfilled in a row or column:1515Prolog SolutionProlog Solution(courtesy of Axel Schreiner)(courtesy of Axel Schreiner)/* properties and values *//* properties and values */ boy(red).boy(red). boy(green).boy(green). boy(blue).boy(blue). girl(red).girl(red). girl(green).girl(green).