SRM Institute of Science and
Technology
Advanced Programming Practice-
18CSC207J
Unit 4 - Logic Programming
Paradigm
Topics
• Definition
• First-class function, Higher-order function, Pure functions, Recursion
• Packages: Kanren, SymPy
• PySWIP, PyDatalog
• Other languages: Prolog, ROOP, Janus
• Demo: Logic Programming in Python
Introduction
It can be an abstract model of computation.
Solve logical problems like puzzles, series
Have knowledge base which we know before and along with the question
Specify knowledge and how that knowledge is to be applied through a series of
rules
In logic programming, the common approach is to apply the methods of resolution
and unification
Knowledge is given to machine to produce result. Exp : AI and ML code
Introduction
The Logical Paradigm takes a declarative approach to problem-solving.
Various logical assertions about a situation are made, establishing all known facts.
Then queries are made.
The role of the computer becomes maintaining data and logical deduction.
Execution of a logic program is a theorem proving process; that is, computation is done
by logic inferences
Prolog ( PROgramming in LOGic) is a ) is a representative logic language
Exp : Prolog, ROOP, Janus
What is a logic ?
• A logic is a language.
• It has syntax and semantics.
• More than a language, it has inference rules.
• Syntax:
• The rules about how to form formulas;
• This is usually the easy part of a logic.
• Semantics:
• about the meaning carried by the formulas,
• mainly in terms of logical consequences.
• Proof Theory
• Proof Theory describe correct ways to derive
Features of Logical paradigms
• Computing takes place over the domain of all terms defined over a “universal” alphabet.
• Values are assigned to variables by means of automatically generated substitutions, called
most general unifiers.
• These values may contain variables, called logical variables.
• The control is provided by a single mechanism: automatic backtracking.
• Strength - simplicity and Conciseness
• Weakness –
• has to do with the restrictions to one control mechanism
• use of a single data type.
General Overview
• Programs written in logic languages consist of declarations that are actually
statements, or propositions, in symbolic logic.
• One of the essential characteristics of logic programming languages is their
semantic
• The basic concept of this semantics is that there is a simple way to determine the
meaning of each statement, and it does not depend on how the statement might
be used to solve a problem.
Concepts of logic paradigm and theoretical background
• Includes both theoretical and fully implemented languages
• They all share the idea of interpreting computation as logical deduction.
• Notation Algorithm = Logic + Control
• Logic Programming uses facts and rules for solving the problem.
• That is why they are called the building blocks of Logic Programming.
• Facts
• Actually, every logic program needs facts to work with so that it can achieve the given
goal.
• Facts basically are true statements about the program and data.
• Exp : Delhi is the capital of India.
• Rules
• Constraints which allow us to make conclusions about the problem domain.
• Basically written as logical clauses to express various facts.
• Exp if we are building any game then all the rules must be defined.
Parts of Logical programming
1. A series of definitions/declarations that define the problem domain
2. Statements of relevant facts
3. Statement of goals in the form of a query
Advantages
• The system solves the problem, so the programming steps themselves are kept to a
minimum;
• Proving the validity of a given program is simple.
Perspectives on logic programming
• Computations as Deduction
• Theorem Proving
• Non-procedural Programming
• Algorithms minus Control
• A Very High Level Programming Language
• A Procedural Interpretation of Declarative Specifications
Computation as Deduction
• Logic programming offers a slightly different paradigm for computation:
computation is logical deduction
• It is raining -> Road is wet
• Current logic programming languages use first order logic (FOL) which is
often referred to as first order predicate calculus (FOPC).
• The first order refers to the constraint that we can quantify (i.e. generalize) over
objects, but not over functions or relations.
Theorem Proving
• Logic Programming uses the notion of an automatic theorem prover as an
interpreter.
• The theorem prover derives a desired solution from an initial set of axioms.
• The proof must be a "constructive" one so that more than a true/false answer
can be obtained
• E.G. The answer to
• exists x such that x = sqrt(16)
• should be x = 4 or x = -4
Non-procedural Programming
• Logic Programming languages are non-procedural programming
languages
• That is, one specifies:
• the set of objects involved in the computation
• the relationships which hold between them
• the constraints which must hold for the problem to be solved
• and leaves it up the language interpreter or compiler to decide how
to satisfy the constraints
A Declarative Example
• Here’s a simple way to specify what has to be true if X is the
smallest number in a list of numbers L
1. X has to be a member of the list L
2. There can’t be list member X2 such that X2<X
Use logic to do reasoning
• Example: Given information about fatherhood and motherhood, determine grand
parent relationship
• E.g. Given the information called facts
• John is father of Lily
• Kathy is mother of Lily
• Lily is mother of Bill
• Ken is father of Karen
• Who are grand parents of Bill?
Use logic to do reasoning
• Example: Given information about fatherhood and motherhood, determine grand
parent relationship
• E.g. Given the information called facts
• John is father of Lily
John
• Kathy is mother of Lily
Bill Lily
• Lily is mother of Bill Kathy
Karen Ken
• Ken is father of Karen
• Who are grand parents of Bill?
Example
Domains
being = symbol
Predicates
L(x,y): % X lives in Y
L(Mary, Austin) % Mary lives in , Austin
Clauses
P % Present
¬p %Not Present
Logic Operators
Truth Tables
Truth Tables
Example Statements
Consider the following knowledge:
Bob is Fred’s father father(Bob, Fred)
Sue is Fred’s mother mother(Sue, Fred)
Barbara is Fred’s sister sister(Barbara, Fred)
Jerry is Bob’s father father(Jerry, Bob)
And the following rules:
A person’s father’s father is the person’s grandfather
A person’s father or mother is that person’s parent
A person’s sister or bother is that person’s sibling
If a person has a parent and a sibling, then the sibling has the same parent
Example Statements
These might be captured in first-order predicate calculus as:
x, y, z : if father(x, y) and father(y, z) then grandfather(x, z)
x, y : if father(x, y) or mother(x, y) then parent(x, y)
x, y : if sister(x, y) or brother(x, y) then sibling(x, y) and sibling(y, x)
x, y, z : if parent(x, y) and sibling(y, z) then parent(x, z)
We would rewrite these as
grandfather(x, z) father(x, y) and father(y, z)
parent(x, y) father(x, y)
parent(x, y) mother(x, y)
Packages: Kanren
• Provides a way to simplify the code for business logic.
• Express the logic in terms of rules and facts.
• The following command will help you install kanren −
• pip install kanren
Matching mathematical expressions
Sympy Package
Boolean True function
Boolean False function
And and Or Function
And function Or function
• A logical AND function evaluates its two • A logical OR function evaluates two Boolean
arguments and returns False if either of them arguments and returns True if either of them is
is False True
NOT and XOR Function
Not Function XOR function
• A Logical Not function results in negation of the Boolean • The Logical XOR (exclusive OR) function returns True
argument. It returns True if its argument is False and if an odd number of the arguments are True and the
returns False if True. The ~ operator performs the rest are False and returns False if an even number of
operation similar to Not function the arguments are True and the rest are False
NAND and NOR Function
Nand Function Nor Function
• This function performs Logical NAND operation. It • This function performs Logical NOR operation. It
evaluates its arguments and returns True if any of them are evaluates its arguments and returns False if any of
False, and False if they are all True them are True, and True if they are all False.
Datalog Concepts
• pyDatalog is a powerful language with very few syntactic elements, mostly
coming from Python :
• Variables and expressions
• Loops
• Facts
• Logic Functions and dictionaries
• Aggregate functions
• Literals and sets
• Tree, graphs and recursive algorithms
• 8-queen problem
Reference
• [Link]
1 2
5 3 7
4
6
Encode the following facts and rules in pyDatalog:
Bear is big
Elephant is big
Cat is small
Bear is brown
Cat is black
Elephant is gray
An animal is dark if it is black
An animal is dark if it is brown
Write a query to find which animal is dark and big.
from pyDatalog import pyDatalog
pyDatalog.create_terms('Bear,Elephant,Cat,Black,G
ray,light,Brown,Big,small,size,color,X,Y,dark')
+size("Bear","Big")
+size("Elephant","Big")
+size("Cat","small")
+color("Bear","Brown")
+color("Cat","Black")
+color("Elephant","Gray")
dark(X) <= (color(X,"Black"))
dark(X) <= (color(X,"Brown"))
light(X) <= (color(X,"Gray"))
print(light(X) &(size(X,'Big')))
PySwip Introduction
• PySwip is a Python - SWI-Prolog bridge enabling to query SWI-Prolog in your
Python programs.
• It features an (incomplete) SWI-Prolog foreign language interface, a utility class
that makes it easy querying with Prolog and also a Pythonic interface.
• Since PySwip uses SWI-Prolog as a shared library and ctypes to access it,
• it doesn't require compilation to be installed.
• Reference :
• [Link]
Example
