8 - Logic Programming and Prolog

ucla | CS 131 | 2023-12-06 12:09

---

Table of Contents

• Logic Programming
• Prolog
  • Facts
  • Rules
    • Negation
  • Queries
  • Resolution
  • Unification
    • Matching facts/rules to goals
  • Lists
    • Recursive rules in list pattern matching
    • List pattern matching is syntactic sugar

Logic Programming

• structure
  • 
• declarative queries on facts and rules
  • 
• Prolog is the most popular logic lang, offshoots are very similar

Prolog

• when given a query, prolog finds a chain of connections bw query, facts and rules
  • 

  • Facts

• declarative statement about the world
• the relationship/fact is a functor (red), the operands are the objects the functor operates on and are called atoms (purple)
  • we can specify order of facts/rules
• functors and atoms must be all lower case and are static assertions not function calls
• facts can be nested deeply
  • 

Rules

• lets us define a new fact in terms of other existing facts or rules
• rules have a head (green) and body (red)
  • 
• a comma separating a rule’s body represents a logical AND (union)
• we can define more complex rules using known facts with logical ands and variables (blue, capitalized) which are used as placeholders for atoms
  • 
• recursive rules using pattern matching
  • 
  • beware infinite looping
• closed world assumption (CWA) - prolog evaluates true queries iff they are true, else false (not unknown)

  Negation

• CWA -

  Queries

• either T/F queries or fill in the blanks queries, the query atom is represented by a variable (capital)
  • 
• resolution is the process of evaluating a query

  Resolution

• occurs top down with each fact and rule
  • 
• when prolog finds a matching it makes an association of the variable in the query to the matched fact/rule and continues until no more true matchings and backtracks
  • 
  • 
• E.g., true/false query
  • 
• E.g., true query for multiple values
  • 

    Unification

• the step of resolution that matches a single goal and a single fact/rule
  • 
• thus resolution performs many unifications

  Matching facts/rules to goals

• matching a rule/fact to a goal works using a tree
  • 
• the rules of matching are the following:
  • the numebr of children is called the functor’s arity

Lists

• prolog lists can contain numbers, atoms, or other lists
• processing using both pattern matching and unification to process lists -> done with facts and rules
• sps a rule of vars: is_same(X,X)
  • querying is_same(lit,lit) -> true
  • querying is_same(ucla,usc) -> false
• list pattern matching [X|XS] is same as haskell’s (x:xs)
  • e.g., is_head(X,[X|XS]) true if X matches X as the first item in the list
  • so is_head(lit,[lit,dank,snack]) -> true
• list pattern [X,Y|XS] is equiv to (x:y:xs)
  • e.g. is_sec(Y,[X,Y|XS]) true if Y is second item

    Recursive rules in list pattern matching

• checking elem of list
• modifying lists, e.g. deleting from a list can be used in many ways
  • 
  • how it works:
    • 
• built in facts/rules on lists
  • 

    List pattern matching is syntactic sugar

•