Transcript X - Piazza

Chapter 15
Functional Programming Languages
Chapter 15 Topics










Introduction
Mathematical Functions
Fundamentals of Functional Programming Languages
The First Functional Programming Language: LISP
Introduction to Scheme
COMMON LISP
ML
Haskell
Applications of Functional Languages
Comparison of Functional and Imperative Languages
2
Introduction
 The design of the imperative languages is
based directly on the von Neumann
architecture

Efficiency is the primary concern, rather than the
suitability of the language for software
development
3
Introduction
 The design of the functional languages is
based on mathematical functions

Based on theoretical basis mostly, but relatively
unconcerned with the architecture of the
machines on which programs will run
4
Lambda Expression
 Lambda calculus is developed by Church 1941
 Square function
is equivalent to lambda expressions (x) x * x
 Application , (( (x) x * x)2) evaluates to 4.
5
Lambda Expression
 According to Church, Lambda calculus (recursive
definition):



Any identifier is lambda expression Function application
If M and N are lambda expression, Application of M to
N, written MN is also lambda expression
Function abstraction M with parameter x
An abstraction ,  x. M, where M is lambda expression,
x is an identifier, is also lambda expression.
6
Lambda Expression
 BNF Grammar rules for lambda calculus:
 Example of lambda expression:
Parameter, body
Function application (MN)
7
Lambda Expression
In lambda expression x.M : x identifier is said
to be bound in M . Any identifier NOT bound in
M is said to be free.
 Bound variable is a place holder. They can be
renamed consistently with ANY FREE variable.
 Definition of free variable is

8
Lambda Expression

Replace x with N
substitution of an expression N for a variable x in
M, written as M[N/x] is defined as:
1.
2.
If free variables of N have NO bound occurrences in M,
then M[N/x] is formed by replacing all free occurrences
of x in M by N.
Otherwise, assume that y is free in N and bound in M.

Consistently, replace the binding and corresponding bound
occurrences of y in M by a new variable u. Repeat this
renaming of bound variables in M until the condition in 1 is
satisfied. Then proceed in Step 1.
เปลี่ยนชื่อ y in M เป็ นตัวแปรใหม่ u ก่อน
9
Lambda Expression
 Examples
เปลี่ยน x เป็ น y
เปลี่ยน y เป็ น x
-rename x ที่มีอยู่ (x เป็ น bound ให้ เปลี่ยนเป็ น u ก่อน)
-จากนั ้นเป็ น y ที่มีเป็ น x ซึง่ ไม่พบ y
10
Lambda Expression

Meaning of lambda expression:
Apply N to M
-แทนค่า x ด้ วย N
(ส่ง N เป็ น parameter แทน x)
 Evaluation of lambda expression is a derivation
sequence
 Example of evaluation
Or we can evaluate from inner most
((y.((x.xyz)a))b)  ((y.ayz )b)  (abz )
Referential transparency
11
Mathematical Functions
 Def: A mathematical function is a mapping
of members of one set, called the domain set,
to another set, called the range set
12
Mathematical Functions
 Lambda expressions describe nameless functions
 Lambda expressions are applied to parameter(s) by
placing the parameter(s) after the expression
e.g. ((x) x * x * x)(3)
which evaluates to 27
Just like the application of function….
13
Mathematical Functions
 Functional Forms

Def: A higher-order function, or functional form,
is one that either takes functions as parameters or
yields a function as its result, or both
14
Functional Forms
1. Function Composition

A functional form that takes two functions as
parameters and yields a function whose value is
the first actual parameter function applied to the
application of the second
Form: h  f ° g
which means h (x)  f ( g ( x))
For f (x)  x * x * x and g (x)  x + 3,
h  f ° g yields (x + 3)* (x + 3)* (x + 3)
15
Functional Forms
2. Construction

A functional form that takes a list of functions as
parameters and yields a list of the results of
applying each of its parameter functions to a
given parameter
Apply each parameter to each function
Form: [f, g]
For f (x)  x * x * x and g (x)  x + 3,
[f, g] (4) yields (64, 7)
f(4)
g(4)
16
Functional Forms
3. Apply-to-all

A functional form that takes a single function as
a parameter and yields a list of values obtained
by applying the given function to each element
of a list of parameters
Form: 
For h (x)  x * x * x
( h, (3, 2, 4)) yields (27, 8, 64)
h(3) h(2) h(4)
17
Fundamentals of Functional
Programming Languages
 The objective of the design of a FPL is to mimic
mathematical functions to the greatest extent
possible
 The basic process of computation is fundamentally
different from that of an imperative language


In an imperative language, operations are done and the
results are stored in variables for later use
Management of variables is a constant concern and
source of complexity for imperative programming
 In an FPL, variables are not necessary, as is the
case in mathematics
18
Fundamentals of Functional
Programming Languages
 In an FPL, the evaluation of a function
always produces the same result given the
same parameters


This is called referential transparency
Right-to-left/Left to Right DOESN’T matter
since no concept of variable
19
LISP
 Data object types: originally only atoms and
lists
 List form: parenthesized collections of
sublists and/or atoms
e.g., (A B (C D) E)
 Originally, LISP was a typeless language
 LISP lists are stored internally as singlelinked lists
20
LISP
 Lambda notation is used to specify functions and function
definitions. Function applications and data have the same
form.
e.g., the list --- (A B C) can mean


list containing of three atoms, A, B, and C
function application, meaning applying two parameters B,C to
function A
 The first LISP interpreter appeared only as a demonstration
of the universality of the computational capabilities of the
notation
21
Introduction to Scheme
 A mid-1970s dialect of LISP, designed to be
a cleaner, more modern, and simpler version
than the contemporary dialects of LISP
 Uses only static scoping
 Functions are first-class entities


They can be the values of expressions and
elements of lists
They can be assigned to variables and passed as
parameters
22
Introduction to Scheme
 Primitive Functions
1. Arithmetic: +, -, *, /, ABS,
SQRT, REMAINDER, MIN, MAX
e.g., (+ 5 2) yields 7
23
Introduction to Scheme
2. QUOTE -takes one parameter; returns the
parameter without evaluation


Normally, scheme interpreter, EVAL,
evaluates parameters. QUOTE is used to
avoid parameter evaluation when it is not
appropriate
QUOTE can be abbreviated with the apostrophe
prefix operator
e.g., '(A B) is equivalent to (QUOTE (A B))
24
Introduction to Scheme
3. CAR takes a list parameter; returns the first
element of that list
e.g., (CAR '(A B C)) yields A
(CAR '((A B) C D)) yields (A B)
4. CDR takes a list parameter; returns the list
after removing its first element
e.g., (CDR '(A B C)) yields (B C)
(CDR '((A B) C D)) yields (C D)
25
Introduction to Scheme
5. CONS takes two parameters, the first of
which can be either an atom or a list and the
second of which is a list; returns a new list
that includes the first parameter as its first
element and the second parameter as the
remainder of its result
e.g., (CONS 'A '(B C)) returns (A B C)
26
Introduction to Scheme
6. LIST - takes any number of parameters;
returns a list with the parameters as elements
27
Introduction to Scheme
 Lambda Expressions

Form is based on  notation
e.g., (LAMBDA (L) (CAR (CAR L)))
L is called a bound variable
 Lambda expressions can be applied
e.g.,
((LAMBDA (L) (CAR (CAR L))) '((A B)
C D))
28
Introduction to Scheme
 A Function for Constructing Functions
DEFINE - Two forms:
1. To bind a symbol to an expression
e.g.,
(DEFINE pi 3.141593)
(DEFINE two_pi (* 2 pi))
29
Introduction to Scheme
2. To bind names to lambda expressions
e.g.,
(DEFINE (cube x) (* x x x))
Example use:
(cube 4)
30
Introduction to Scheme
 Steps of evaluation process (for normal
functions):
1. Parameters are evaluated, in no particular order**
2. The values of the parameters are substituted into
the function body
3. The function body is evaluated
4. The value of the last expression in the body is the
value of the function
31
Introduction to Scheme
 Examples:
(DEFINE (square x) (* x x))
(DEFINE (hypotenuse side1
side1)
(SQRT (+ (square side1)
(square side2)))
)
32
Introduction to Scheme
 Predicate Functions: (#T is true and ()is false)
1. EQ? takes two symbolic parameters; it returns #T if
both parameters are atoms and the two are the same
e.g., (EQ? 'A 'A) yields #T
(EQ? 'A '(A B)) yields ()


Note that if EQ? is called with list parameters, the
result is not reliable
Also, EQ? does not work for numeric atoms
Find out: How many equal functions does it have?
33
Introduction to Scheme
 Predicate Functions:
2. LIST? takes one parameter; it returns #T if
the parameter is a list; otherwise()
3. NULL? takes one parameter; it returns #T if
the parameter is the empty list; otherwise()
Note that NULL? returns #T if the parameter is()
4. Numeric Predicate Functions
=, <>, >, <, >=, <=, EVEN?,
ODD?, ZERO?, NEGATIVE?
34
Introduction to Scheme
 Output Utility Functions:
(DISPLAY expression)
(NEWLINE)
35
Introduction to Scheme
 Control Flow
1. Selection- the special form, IF
(IF predicate then_exp else_exp)
e.g.,
(IF (<> count 0)
(/ sum count)
0
)
36
Introduction to Scheme
 Control Flow
2. Multiple Selection - the special form, COND
General form:
(COND
(predicate_1 expr {expr})
(predicate_1 expr {expr})
...
(predicate_1 expr {expr})
(ELSE expr {expr})
)
Returns the value of the last expr in the first
pair whose predicate evaluates to true
37
Example of COND
(DEFINE (compare x y)
(COND
((> x y) (DISPLAY “x is greater than y”))
((< x y) (DISPLAY “y is greater than x”))
(ELSE (DISPLAY “x and y are equal”))
)
)
38
Example Scheme Functions
1. member - takes an atom and a simple list; returns
#T if the atom is in the list; () otherwise
(DEFINE (member atm lis)
(COND
((NULL? lis) '())
((EQ? atm (CAR lis)) #T)
((ELSE (member atm (CDR lis)))
))
39
Example Scheme Functions
2. equalsimp - takes two simple lists as parameters; returns #T if
the two simple lists are equal; () otherwise
(DEFINE (equalsimp lis1 lis2)
(COND
((NULL? lis1) (NULL? lis2))
((NULL? lis2) '())
((EQ? (CAR lis1) (CAR lis2))
(equalsimp(CDR lis1)(CDR lis2)))
(ELSE '())
))
40
Example Scheme Functions
3. equal - takes two general lists as parameters; returns #T if the
two lists are equal; ()otherwise
(DEFINE (equal lis1 lis2)
(COND
((NOT (LIST? lis1))(EQ? lis1 lis2))
((NOT (LIST? lis2)) '())
((NULL? lis1) (NULL? lis2))
((NULL? lis2) '())
((equal (CAR lis1) (CAR lis2))
(equal (CDR lis1) (CDR lis2)))
(ELSE '())
))
41
Example Scheme Functions
4. append - takes two lists as parameters; returns the first
parameter list with the elements of the second parameter list
appended at the end
(DEFINE (append lis1 lis2)
(COND
((NULL? lis1) lis2)
(ELSE (CONS (CAR lis1)
(append (CDR lis1) lis2)))
))
42
Introduction to Scheme
 The LET function

General form:
(LET (
(name_1 expression_1)
(name_2 expression_2)
...
(name_n expression_n))
body
)

Semantics: Evaluate all expressions, then bind the values to the names; evaluate
the body
43
Introduction to Scheme
(DEFINE (quadratic_roots a b c)
(LET (
(root_part_over_2a
(/ (SQRT (- (* b b) (* 4 a c)))
(* 2 a)))
(minus_b_over_2a (/ (- 0 b) (* 2 a)))
(DISPLAY (+ minus_b_over_2a
root_part_over_2a))
(NEWLINE)
(DISPLAY (- minus_b_over_2a
root_part_over_2a))
))
44
Introduction to Scheme
 Functional Forms
1. Composition
- The previous examples have used it
2. Apply to All - one form in Scheme is mapcar
- Applies the given function to all elements of the given list;
result is a list of the results
(DEFINE (mapcar fun lis)
(COND
((NULL? lis) '())
(ELSE (CONS (fun (CAR lis))
(mapcar fun (CDR lis))))
))
45
Introduction to Scheme
 It is possible in Scheme to define a function that builds
Scheme code and requests its interpretation
 This is possible because the interpreter is a user-available
function, EVAL
 e.g., suppose we have a list of numbers that must be added
together
(DEFINE (adder lis)
(COND
((NULL? lis) 0)
(ELSE (+ (CAR lis)
(adder(CDR lis ))))
))
46
Adding a List of Numbers
((DEFINE (adder lis)
(COND
((NULL? lis) 0)
(ELSE (EVAL (CONS '+ lis)))
))
 The parameter is a list of numbers to be added; adder
inserts a + operator and interprets the resulting list
47
Introduction to Scheme
 Scheme includes some imperative features:
1. SET! binds or rebinds a value to a name
2. SET-CAR! replaces the car of a list
3. SET-CDR! replaces the cdr part of a list
48
COMMON LISP
 A combination of many of the features of the
popular dialects of LISP around in the early
1980s
 A large and complex language--the opposite of
Scheme
49
COMMON LISP
 Includes:








records
arrays
complex numbers
character strings
powerful I/O capabilities
packages with access control
imperative features like those of Scheme
iterative control statements
50
COMMON LISP
 Example (iterative set membership, member)
(DEFUN iterative_member (atm lst)
(PROG ()
loop_1
(COND
((NULL lst) (RETURN NIL))
((EQUAL atm (CAR lst))(RETURN T))
)
(SETQ lst (CDR lst))
(GO loop_1)
))
51
ML
 A static-scoped functional language with syntax
that is closer to Pascal than to LISP
 Uses type declarations, but also does type
inferencing to determine the types of undeclared
variables (will see in Chapter 5)
 It is strongly typed (whereas Scheme is essentially
typeless) and has no type coercions
 Includes exception handling and a module facility
for implementing abstract data types
52
ML
 Includes lists and list operations
 The val statement binds a name to a value
(similar to DEFINE in Scheme)
 Function declaration form:
fun function_name (formal_parameters) =
function_body_expression;
e.g.,
fun cube (x : int) = x * x * x; 53
Haskell
 Similar to ML (syntax, static scoped, strongly
typed, type inferencing)
 Different from ML (and most other functional
languages) in that it is purely functional (e.g., no
variables, no assignment statements, and no side
effects of any kind)
54
Haskell
 Most Important Features


Uses lazy evaluation (evaluate no subexpression
until the value is needed)
Has list comprehensions, which allow it to deal
with infinite lists
55
Haskell Examples
1. Fibonacci numbers (illustrates function
definitions with different parameter forms)
fib 0 = 1
fib 1 = 1
fib (n + 2) = fib (n + 1)
+ fib n
56
Haskell Examples
2. Factorial (illustrates guards)
fact n
| n == 0 = 1
| n > 0 = n * fact (n - 1)
The special word otherwise can appear as
a guard
57
Haskell Examples
3. List operations
List notation: Put elements in brackets
e.g., directions = [“north”,
“south”, “east”, “west”]

Size of list
Length: #
e.g., #directions is 4

Arithmetic series with the .. operator
e.g., [2, 4..10] is [2, 4, 6, 8, 10]

58
Haskell Examples
3. List operations (cont)
Catenation is with ++
e.g., [1, 3] ++ [5, 7] results in
[1, 3, 5, 7]

CONS, CAR, CDR via the colon operator (as in
Prolog) CONS
e.g., 1:[3, 5, 7] results in
[1, 3, 5, 7]

59
Haskell Examples
product of empty list = 1
product [] = 1
product (a:x) = a * product x
Tail part of list
x is a list
product(a..x) = a * product(x)
fact n = product [1..n]
product of a*..*x
fact(n) = product (1..n)
60
Haskell Examples
4. List comprehensions: set notation
e.g., [n * n | n ← [1..20]]
computes the square of 1, the square of 2,…the
square of 20
factors n = [i | i ← [1..n div 2],
n mod i == 0] for i=1 to n/2
compute (return n mod i
This function computes all of the factors of its given
parameter
61
Haskell Examples
 Quicksort:
Sort of empty list = empty
sort [] = []
sort (a:x) = sort [b | b ← x; b
<= a]
Sort of list [a..x] is
sort for all element b’s that is <= a
++ [a] ++
a is pivot
sort [b | b ← x; b > a]
sort for all element b’s that is > a
62
Haskell Examples
5. Lazy evaluation
e.g.,
Positive number starts from 0
positives = [0..] Squares is list of [02 12 22…]
squares = [n * n | n ← [0..]]
(only compute those that are necessary)
e.g., member squares 16
would return True
16 is a member of squares or not
63
Haskell Examples
 The member function could be written as:
is not a member of empty list
member [] b = False breturn
false
member(a:x) b=(a == b)||member x b
B is member of (a..x) or not
-return
if a==b or
member x b --make recursive all
squares = [n * n | n ← [0..]]
(only compute those that are necessary)
e.g., member squares 16
would return True
64
Haskell Examples
squares = [n * n | n ← [0..]]
(only compute those that are necessary)
e.g., member squares 16
 However, this would only work if the parameter to
squares was a perfect square; if not, it will keep
generating them forever (due to lazy evaluation).
The following version will always work:
member2 (m:x) n
If m < n
| m < n= member2 x n
| m == n
= True
If m equals to n, will return true.
| otherwise = False If m < n, will make a recursive ca
Otherwise will return false.
65
Applications of Functional
Languages
 APL is used for throw-away programs
 LISP is used for artificial intelligence




Knowledge representation
Machine learning
Natural language processing
Modeling of speech and vision
 Scheme is used to teach introductory
programming at a significant number of
universities
66
Comparing Functional and
Imperative Languages
 Imperative Languages:




Efficient execution
Complex semantics
Complex syntax
Concurrency is programmer designed
 Functional Languages:




Simple semantics
Simple syntax
Inefficient execution
Programs can automatically be made concurrent
67
Chapter 16
Logic Programming Languages
Chapter 16 Topics








Introduction
A Brief Introduction to Predicate Calculus
Predicate Calculus and Proving Theorems
An Overview of Logic Programming
The Origins of Prolog
The Basic Elements of Prolog
Deficiencies of Prolog
Applications of Logic Programming
Introduction
 Logic programming language or declarative
programming language
 Express programs in a form of symbolic logic
 Use a logical inferencing process to produce results
 Declarative rather that procedural:

only specification of results are stated (not detailed
procedures for producing them)
Introduction to Predicate
Calculus
 Proposition: a logical statement that may or
may not be true

Consists of objects and relationships of objects
to each other
Introduction to Predicate
Calculus
 Symbolic logic can be used for the basic
needs of formal logic:



express propositions
express relationships between propositions
describe how new propositions can be
inferred from other propositions
 Predicate calculus is a particular form of
symbolic logic used for logic
programming.
Propositions
 Objects in propositions are represented by
simple terms: either constants or variables
 Constant: a symbol that represents an object
 Variable: a symbol that can represent different
objects at different times

different from variables in imperative languages
Propositions
 Atomic propositions consist of compound
terms
 Compound term: one element of a
mathematical relation, written like a
mathematical function


Mathematical function is a mapping
Can be written as a table
Propositions
 Compound term composed of two parts


Functor: function symbol that names the relationship
Ordered list of parameters (tuple)
 Examples:
Functor(order list of parameters)
student(jon)
like(seth, OSX)
like(nick, windows)
like(jim, linux)
Propositions
 Propositions can be stated in two forms:


Fact: proposition is assumed to be true
Query: truth of proposition is to be determined
 Compound proposition:


Have two or more atomic propositions
Propositions are connected by operators
Logical Operators
Name
Symbol
Example
Meaning
negation

a
not a
conjunction

ab
a and b
disjunction

ab
a or b
equivalence

ab
implication


ab
ab
a is equivalent to
b
a implies b
b implies a
Quantifiers
Name
Example
Meaning
universal
∀X.P
For all X, P is true
existential
∃X.P
There exists a value of X
such that P is true
Clausal Form
Too many ways to state the same thing
Use a standard form for propositions
Clausal form:
Anticedent
Consequence
B1  B2  …  Bn  A1  A2  …  Am
means if all the As are true, then at least one B
is true
Antecedent: right side
Consequent: left side
Predicate Calculus and Proving
Theorems
 A use of propositions is to discover new theorems
that can be inferred from known axioms and
theorems
 Resolution: an inference principle that allows
inferred propositions to be computed from given
propositions
Resolution
หาคำตอบให้ ตวั แปรใน proposition
 Unification: finding values for variables in
propositions that allows matching process to
succeed
กาหนดค่าให้ ตวั แปรใน proposition เพื่อทดสอบว่าใช่คาตอบหรื อไม่
 Instantiation: assigning temporary values to
variables to allow unification to succeed
 After instantiating a variable with a value, if
matching fails, may need to backtrack and
instantiate with a different value
Theorem Proving
 Use proof by contradiction
 Hypotheses: a set of pertinent propositions
 Goal: negation of theorem stated as a
proposition
 Theorem is proved by finding an
inconsistency
Theorem Proving
 Basis for logic programming
 When propositions used for resolution, only
restricted form can be used
 Horn clause - can have only two forms Prolog
:single consequence


Headed: single atomic proposition on left side
Headless: empty left side (used to state facts)
 Most propositions can be stated as Horn clauses
Overview of Logic
Programming
 Declarative semantics


There is a simple way to determine the meaning of
each statement
Simpler than the semantics of imperative languages
 Programming is nonprocedural

Programs do not state now a result is to be
computed, but rather the form of the result
Example: Sorting a List
 Describe the characteristics of a sorted list,
not the process of rearranging a list
consequence
Antecedents
sort(old_list, new_list)  permute (old_list, new_list) 
sorted (new_list)
sorted (list)  ∀j such that 1 j < n, list(j)  list (j+1)
The Origins of Prolog
 University of Aix-Marseille

Natural language processing
 University of Edinburgh

Automated theorem proving
The Basic Elements of Prolog





Edinburgh Syntax
Term: a constant, variable, or structure
Constant: an atom or an integer
Atom: symbolic value of Prolog
Atom consists of either:


a string of letters, digits, and underscores beginning with a
lowercase letter
a string of printable ASCII characters delimited by
apostrophes
The Basic Elements of Prolog
 Variable: any string of letters, digits, and
underscores beginning with an uppercase letter
 Instantiation: binding of a variable to a value

Lasts only as long as it takes to satisfy one complete
goal
 Structure: represents atomic proposition
functor(parameter list)
Fact Statements
 Used for the hypotheses
 Headless Horn clauses
student(jonathan).
sophomore(ben).
brother(tyler, cj).
มีแต่ consequence
Rule Statements
 Used for the hypotheses
 Headed Horn clause
 Right side: antecedent (if part)

May be single term or conjunction
 Left side: consequent (then part)

Must be single term
 Conjunction: multiple terms separated by
logical AND operations (implied)
16-90
Rule Statements
parent(kim,kathy):- mother(kim,kathy).
 Can use variables (universal objects) to
generalize meaning:
parent(X,Y):- mother(X,Y).
sibling(X,Y):- mother(M,X),
mother(M,Y),
father(F,X),
father(F,Y).
Goal Statements
 For theorem proving, theorem is in form of
proposition that we want system to prove or
disprove – goal statement
 Same format as headless Horn
student(james)
 Conjunctive propositions and propositions with
variables also legal goals
father(X,joe)
สาหรับ query
Inferencing Process of Prolog
 Queries are called goals
 If a goal is a compound proposition, each of the facts is a
subgoal
 To prove a goal is true, must find a chain of inference rules
and/or facts. For goal Q:
B :- A
C :- B
…
Q :- P
Eg. Forward chaining
 Process of proving a subgoal called matching, satisfying, or
resolution
Inferencing Process
 Bottom-up resolution, forward chaining


Begin with facts and rules of database and attempt to find sequence that
leads to goal
works well with a large set of possibly correct answers
 Top-down resolution, backward chaining


begin with goal and attempt to find sequence that leads to set of facts in
database
works well with a small set of possibly correct answers
 Prolog implementations use backward chaining
Inferencing Process
 When goal has more than one subgoal, can use
either


Depth-first search: find a complete proof for the first
subgoal before working on others
Breadth-first search: work on all subgoals in parallel
 Prolog uses depth-first search

Can be done with fewer computer resources
Inferencing Process
 With a goal with multiple subgoals, if fail to
show truth of one of subgoals, reconsider
previous subgoal to find an alternative solution:
backtracking
 Begin search where previous search left off
 Can take lots of time and space because may
find all possible proofs to every subgoal
Simple Arithmetic
 Prolog supports integer variables and integer
arithmetic
 is operator: takes an arithmetic expression as
right operand and variable as left operand
 A is B / 10 + C
 Not the same as an assignment statement!
Example
speed(ford,100).
speed(chevy,105).
speed(dodge,95).
speed(volvo,80).
time(ford,20).
time(chevy,21).
time(dodge,24).
time(volvo,24).
distance(X,Y) :- speed(X,Speed),
time(X,Time),
Y is Speed * Time.
Trace
 Built-in structure that displays instantiations at
each step
 Tracing model of execution - four events:




Call (beginning of attempt to satisfy goal)
Exit (when a goal has been satisfied)
Redo (when backtrack occurs)
Fail (when goal fails)
Example
likes(jake,chocolate).
likes(jake,apricots).
likes(darcie,licorice).
likes(darcie,apricots).
trace.
likes(jake,X),
likes(darcie,X).
List Structures
 Other basic data structure (besides atomic
propositions we have already seen): list
 List is a sequence of any number of elements
 Elements can be atoms, atomic propositions, or
other terms (including other lists)
[apple, prune, grape, kumquat]
[]
(empty list)
[X | Y]
(head X and tail Y)
Example
 Definition of append function:
append([], List, List).
append([Head | List_1], List_2, [Head |
List_3]) :append (List_1, List_2, List_3).
Example
 Definition of reverse function:
reverse([], []).
reverse([Head | Tail], List) :reverse (Tail, Result),
append (Result, [Head], List).
Deficiencies of Prolog
 Resolution order control
 The closed-world assumption
 The negation problem
 Intrinsic limitations
Applications of Logic
Programming
 Relational database management systems
 Expert systems
 Natural language processing
 Education
Conclusions
 Advantages:



Prolog programs based on logic, so likely to be more
logically organized and written
Processing is naturally parallel, so Prolog interpreters
can take advantage of multi-processor machines
Programs are concise, so development time is
decreased – good for prototyping
Readings and Testing about Prolog
• http://www.doc.gold.ac.uk/~mas02g
w/prolog_tutorial/prologpages/
• http://www.gprolog.org/manual/gpr
olog.html
Intro to Logic Programming by Prolog
Prepared by
Manuel E. Bermúdez, Ph.D.
Associate Professor
University of Florida
Logic Programming
Fundamentals
 Horn clauses:

General form:
H  B1, B2, ... Bn

Meaning: if B1, B2, ... Bn are true,
then H is true.
 Deductive reasoning:
C  A,B
DC
D  A,B
Resolution
 Process of deriving new statements, combining
old ones, cancelling like terms, etc.
 Variables may acquire values through
unification. More later.
 Example:
fun(X)  sunny(X)
sunny(Florida)
fun(Florida)
Prolog Fundamentals
 All Prolog programs built from terms:


Programs
The data manipulated by programs
 Three types of terms:



Constants: integers, real numbers, atoms.
Variables.
Compound terms.
Prolog Fundamentals (cont’d)
 Constants: Integers, e.g. 123;
Reals, e.g.: 1.23
 Atoms:



Lexically, a lowercase letter followed by any
number of additional letters, digits or
underscores, e.g. foobar, 'Hello'.
Atoms do look like variables in other languages,
but foobar is not a variable; it has no binding,
it is a unique value.
An atom can also be sequence of punctuation
characters: *, ., =, @#$
Prolog Fundamentals (cont’d)
 Variables: begin with an upper-case letter,
e.g. X, My_var.
 Can be instantiated (take on a value) at run
time.
 Variables can start with an underscore, and
get special treatment.
Prolog Fundamentals (cont’d)
 A compound term, or structure, consists of an
atom called a functor, and a list of arguments,
e.g. sunny(florida), weird(prolog),
related(jim, john).
No space allowed
 A compound term may look like a function call,
but it isn’t. It is structured data, or logical facts.
Syntax for Terms
<term> ::= <constant>|<variable>|<compound-term>
<constant> ::= <integer> | <real number> | <atom>
<compound-term> ::= <atom> ( <termlist> )
<termlist> ::= <term> | <term> , <termlist>
 Even an arithmetic expression, usually
written as 1+2, is just an abbreviation
for +(1,2).
The Prolog Database
 A Prolog system maintains a collection of facts and
rules of inference, a database.
 A Prolog program is just a “store” of facts for this
database.
 The simplest item in the database is a fact: a term
followed by a period:
sunny(florida).
sunny(california).
father(jim, ann).
Simple Queries
?- sunny(florida).
Yes.
?- father(jim, ann).
Yes.
?- father(jim, tom).
No.
?- sunny(X).
Attempt to match X.
X = florida;
Type a semi-colon, and
X = california; the system tries again.
No.
This time it fails.
Lists




Similar to Lisp.
[a, b, c] is syntactic sugar.
Separate head from tail using ‘|’.
‘.’ similar to ‘cons’ in Lisp.
List notation
[]
[1]
[1,2,3]
[1,parent(X,Y)]
Term denoted
[]
.(1,[])
.(1,.(2,.(3,[])))
.(1,.(parent(X,Y),[]))
[1|X]
[1,2|X]
[1,2|[3,4]]
.(1,X)
.(1,.(2,X)))
[1,2,3,4]
Pattern Matching: Unification.
Examples:
[george, X] unifies with [george, tom]
[X, fred, [1, X]] unifies with
[jane, fred, [1, Y]] by Y = X = jane
[X, fred, [1, X]] does not unify with
[jane, fred, [1, ralph]], because X
cannot match both jane and ralph.
Unification
1. A constant unifies only with itself.
2. Two structures unify iff they have
•
•
•
The same functor.
The same number of arguments.
The arguments unify recursively.
3. A variable X unifies with anything. The
other thing could:
•
•
have a value. So, instantiate X.
be an uninstantiated variable. Link the two
variables, so that:

If either is instantiated later, they both share the value.
Example of Unification
Unify ([p, q, [c, X]], [Y, q, [X, c]]) =
Unify(p,Y) and Unify([q, [c, X]], [q, [X, c]]) =
(Y=p) and Unify(q,q)
and Unify( [[c, X]], [[X, c]]) =
(Y=p) and Unify( [c, X], [X, c])
and Unify(nil,nil) =
(Y=p) and Unify(c,X)
and Unify([X],[c]) =
(Y=p) and (X=c)
and Unify(X,c) and Unify(nil,nil) =
Example of Unification
(cont’d)
(Y=p)
and (X=c)
and Unify(valueof(X),c) =
(Y=p) and (X=c) and Unify(c,c) =
(Y=p) and (X=c).
Some Useful Predicates
 The predicate append(X,Y,Z) is true iff
appending Y onto the end of X yields Z.
Z=[X Y]
Examples:
?- append([1,2],[3,4],X).
X = [1, 2, 3, 4]
Yes.
?- append(X,[3,4],[1,2,3,4]).
X = [1, 2]
Yes.
Some Useful Predicates
(cont’d)
 append can be used with any pattern of
instantiation (that is, with variables in any
position). Example:
?- append(X,[3,4],[1,2,3,4]).
X = [1, 2]
Yes
Some Useful Predicates
(cont’d)
Example:
?- append(X,Y,[1,2,3]).
X = []
Y = [1, 2, 3] ;
X = [1]
Y = [2, 3] ;
X = [1, 2]
Y = [3] ;
X = [1, 2, 3]
Y = [] ;
No.
Other Predefined List
Predicates
Predicate
Description
member(X,Y)
Provable if list Y contains element X.
select(X,Y,Z)
Provable if list Y contains element X, and
removing X from Y yields Z.
Provable if Z is the Xth element of list Y,
counting from 0.
Provable if X is a list of length Y.
nth0(X,Y,Z)
length(X,Y)
 Queries using these predicates can contain
variables anywhere.
Sample Use of select
Z= list [1 2 3] that is removed 2.
?- select(2,[1,2,3],Z).
=[1 3]
Z = [1, 3] ;
No.
?- select(2,Y,[1,3]).
Y = [2, 1, 3] ;
Y = [1, 2, 3] ;
Y = [1, 3, 2] ;
No.
Prolog Rules (or maybe not :-)
 Rules are of the form
predicate :- conditions.
 The predicate is true iff all conditions are
true.
 Conditions appear as a list of terms,
separated by commas.
Prolog Rules (cont’d)
 The simplest rules are facts:
FatherOf(john,ted). MotherOf(connie,ted).
FatherOf(fred,carol).
MotherOf(connie,carol).
FatherOf(ted,ken).
MotherOf(jane,ken).
FatherOf(ted,lloyd). MotherOf(alice,lloyd)
FatherOf(lloyd,jim). MotherOf(carol,jim).
FatherOf(lloyd,joan). MotherOf(carol,joan).

Note: male/female names are meaningless.
Prolog Rules (cont’d)
 More complex rules:
ParentOf(X,Y) :- FatherOf(X,Y).
ParentOf(X,Y) :- MotherOf(X,Y).
Alternatives are attempted in the order
specified:
?- ParentOf(connie,ted).
First, match FatherOf(connie,ted). Fails.
Then, match MotherOf(connie,ted). Succeed.
Prolog Rules (cont’d)
 Using variables, we can get answers:
?- ParentOf(ted,C)
C = ken;
C = lloyd;
No.
?- ParentOf(P,carol)
P = fred;
P = connie;
No.
Prolog Rules (cont’d)
 Using more than one condition:
GrandParent(X,Y) :- ParentOf(X,Z),
ParentOf(Z,Y).
?- GranParent(G, jim)
Prolog performs a backtracking, depth-first,
left-to-right search for values to satisfy the
predicate(s) sought.
Search for GrandParent(G,jim)
?- GranParent(G, jim)
GP(G=X,Y=jim)
AND
PO(G=X,Z)
PO(Z,Y=jim)
OR
FO
(G=X=
Z=
MO
, (G=X=
)
Z=
OR
FO
, (Z=
) Y=jim)
G = fred, ted, connie, alice
,
MO
fff
(Z=
Y=jim)
,
Another example
 Facts:
AuthorOf("Life on a Donkey","Swartz").
AuthorOf("Big and Little","Jones").
AuthorOf("Where are We","White").
AuthorOf("In a Pig’s Eye","Brown").
AuthorOf("High Flight","Smith").
SubjectOf("Life on a Donkey",travel).
SubjectOf("Big and Little",life).
SubjectOf("Where are We",life).
SubjectOf("In a Pig’s Eye",travel).
SubjectOf("High Flight",bio).
Another example (cont’d)
 More facts:
AudienceOf("Life on a
Donkey",adult).
AudienceOf("Big and Little",child).
AudienceOf("Where are We",teen).
AudienceOf("In a Pig’s Eye",adult).
AudienceOf("High Flight",adult).
Selecting Reviewers
 Would like an author who:

has written books on the same subject.
Reviewer(Book,Person) :SubjectOf(Book,Sub),
SubjectOf(AnotherBook,Sub),
AuthorOf(AnotherBook,Person),
not AuthorOf(Book,Person).
Selecting Reviewers (cont’d)

If someone who has written in the same subject is
not available, then find someone who has written
for the same audience.
Reviewer(Book,Person) :AudienceOf(Book,Aud),
AudienceOf(AnotherBook,Aud),
AuthorOf(AnotherBook,Person),
not AuthorOf(Book,Person).
Exercise: Find reviewers for “Life on a Donkey”.
Hint: There are 3. A reviewer can qualify twice.