Transcript ppt

Logic and Programs
• Most programs use Boolean expressions over data
• Logic statements can express program semantics
– I.e., axiomatic semantics
• Logic also can be the subject of computation
– E.g., automatic deduction systems, theorem-provers
• Can handle computation and proof interchangeably
– E.g., for restricted forms of logic (Horn Clauses  FOL)
• Programming languages then can help automate this
– E.g., logic programming in Prolog
• Mechanisms readily implemented in a functional style
– E.g., in Scheme or other functional programming languages
CSE 425: Logic Programming I
Logic Programs
• Logic programming languages (and programming
frameworks in other languages like Scheme or C++)
– Provide a means for encoding well formed statements
– Provide algorithms for implementing inference rules
• Sometimes called “deductive databases”
– Logic programming systems as logic + control where the
logic is specified and the control is automated
– To be feasible, however, some restrictions are needed
• Widely applicable beyond theorem proving
– E.g., programming robots to adapt to situational factors
CSE 425: Logic Programming I
Intro to Prolog
• The most widely used logic programming language
– Though lots of logic programming is done in other languages
• Syntax is similar to first-order-logic (FOL) syntax
– E.g., ancestor(x,y)^ancestor(y,z) → ancestor(x,z) in FOL
is ancestor(X,Z) :- ancestor(X,Y), ancestor(Y,Z) in Prolog
– Note: variables are capitalized (or begin with an underscore)
– Note: comma indicates conjunction (and)
– Also, Prolog uses =< instead of <= for less-than-or equal
• Lists are delimited by square brackets in Prolog
– E.g., [alice, bob, X]
• Can do head|tail matching (as in ML, Haskell)
– E.g., [H|T] = [alice, bob, X] gives [alice] and [bob, X]
CSE 425: Logic Programming I
Prolog Interpreter Environment
• Maintains a database of statements and variables
– E.g., loaded from a file, and/or entered by the user
• User can enter a predicate as a query
–
–
–
–
E.g., ancestor(bob,alice)
Interpreter matches query to statements in its database
If query is fully bound, will produce a yes or no answer
If query has a variable, will find a satisfactory binding
• User also can ask for the result of an expression
– E.g., X is 3 + 5, write(X)
• Unification in Prolog
– A constant only unifies with itself (exact match is required),
while a variable may unify via renaming and/or binding
– Predicates unify if same signature, and the arguments unify
CSE 425: Logic Programming I
Today’s Studio Exercises
• We’ll code up initial ideas from Scott Chapter 11
– Looking at basic parsing and evaluation mechanisms for
propositional and predicate logic, and proceeding from there
• Today’s exercises are again in C++
– Please take advantage of the text books and the on-line
pages that are linked on the course web site
– As always, please ask for help as needed
• When done, e-mail your answers to the
[email protected] course account, with subject
line “Logic Programming Studio I”
CSE 425: Logic Programming I