Prolog

• Directed resolution with positive literals at front: backward reasoning
• Database is ordered: clauses are tried in the order in which they appear.
• Depth-first search with backtracking.
  • Each problem state is a set of goals left to satisfy, each with an associated point in the database which has been reached in an attempt to satisfy the goal.
  • When a goal is satisfied by an assertion (a clause with no variables), any new variable bindings are propagated to the goal that depends on it.
  • When a goal is satisfied by a rule, its antecedents, with new variable bindings, become new goals.
  • When it is impossible to satisfy a goal (the end of the database is reached), the system backtracks to the previous goal, and an attempt is made to resatisfy it by proceeding down the database from where it was last satisfied.
  • When it is impossible to backtrack further, the search fails.
• Negation as failure
  • Failure to prove a goal is treated as proving the negation of the goal.
  • This is based on the closed-world assumption, the assumption that for every predicate appearing in the database, all instances of that predicate are in the database.
• Syntax
  • Variables are capitalized or begin with an underscore, constants are lower-case (the opposite of standard logic notation!).
  • , = &
  • Rules appear as reverse implications, with :- as the reverse implication symbol.

    sister (X, Y) :-  female (Y), parent (X, M, F), parent (Y, M, F).
    

  • Lists:
    • [a,b,c,d]
    • [Head|Tail]
• Declarative and procedural interpretations of Prolog programs
• Some programs

  • person(eve).
    person(X) :- mother(X,Y),person(Y).
    mother(suzie,eve).
    mother(joan,suzie).
    

  • member(X, [X|_]).
    member(X,[_|Y]) :- member(X,Y).
    

  • isa(elephant,mammal).
    isa(clyde,elephant).
    hasprop(mammal,legnumber,4).
    hasprop(elephant,weight,1000).
    
    hasproperty(Entity,Property,Value) :-
        hasprop(Entity,Property,Value).
    
    hasproperty(Entity,Property,Value) :-
        hasproperty(Superentity,Property,Value), !,
        isa(Entity,Superentity).
    

  • append1([],X,X).
    append1([Xhead|Xtail],Y,[Xhead|Z]) :-
        append1(Xtail,Y,Z).