Unit-5

Functional programming languages

1. immutable Data:
2. Functional programming languages emphasize immutable data, meaning once a
value is assigned, it cannot be changed.
3. This avoids issues related to side effects and makes programs more predictable.
4. First-Class Functions:
5. Functions are treated as first-class citizens, meaning they can be assigned to
variables, passed as arguments to other functions, and returned as values from other
functions.
6. Higher-Order Functions:
7. Functional programming languages often support higher-order functions, which are
functions that can take other functions as arguments or return them as results.
8. This enables a higher level of abstraction and code reuse.
9. Pure Functions:
Pure functions are functions that have no side effects and always return the same
output given the same input.
This property makes it easier to reason about the behavior of the code and facilitates
testing and debugging.
Recursion:
Recursion is a common technique in functional programming languages for
performing repetitive tasks.
Instead of using loops, functional programmers often use recursion to iterate over
data structures.
Lazy Evaluation:
Some functional programming languages support lazy evaluation, where expressions
are not evaluated until their results are actually needed.
This can improve performance and enable more efficient use of resources.

Examples of Functional Programming Languages:

1. Haskell:
2. Haskell is a purely functional programming language known for its strong static
typing system and lazy evaluation.
3. It has a rich type system and powerful features for writing concise and expressive
code.
4. Scala:
5. Scala is a hybrid functional programming language that runs on the Java Virtual
Machine (JVM).
6. It combines functional programming features with object-oriented programming,
making it suitable for both paradigms.
7. Clojure: Clojure is a functional programming language that runs on the Java Virtual
Machine and is designed for concurrency and interoperability with Java.
8. It emphasizes immutable data structures and provides powerful features for
managing state in concurrent programs.
9. Erlang:
Erlang is a functional programming language designed for building fault-tolerant
and highly available distributed systems.
It supports lightweight concurrency through its actor-based model and has built-in
support for message passing between concurrent processes.

Benefits of Functional Programming Languages:

1. Conciseness(short):
2. Functional programming languages often allow developers to express complex ideas
in fewer lines of code compared to imperative languages.
3. Safety:
4. Immutable data and pure functions make it easier to reason about the behavior of
programs and reduce the likelihood of bugs related to side effects and mutable
state.
5. Concurrency:
6. Functional programming languages often provide built-in support for concurrency
and parallelism, making it easier to write scalable and high-performance applications.
7. Expressiveness:
8. Functional programming languages provide powerful abstractions for working with
data and expressing algorithms, making it easier to write expressive and declarative
code.

Mathematical Functions:

In mathematics, a function is a relation between a set of inputs (domain) and a set of

possible outputs (range), where each input is related to exactly one output. Functions
in mathematics have the following characteristics:

1. Determinism:
2. A function always produces the same output for a given input.
3. Referential Transparency:
4. The output of a function depends only on its input, and it does not have any side
effects.
5. Immutability:
6. The function does not modify the input or any external state.
7. Pureness:
8. A pure function is free from side effects and has referential transparency.

Fundamentals of Functional Programming Languages:

Functional programming languages are based on the principles of mathematical

functions.

They emphasize the following fundamentals:

1. First-Class Functions:
2. Functions are treated as first-class citizens, meaning they can be passed as
arguments to other functions, returned as values from other functions, and assigned
to variables.
3. Higher-Order Functions:
4. Higher-order functions take other functions as arguments or return them as results.
They enable powerful abstractions and allow for the composition of functions.
5. Immutable Data:
6. Functional programming languages encourage immutability, where once a value is
assigned, it cannot be changed. Immutable data structures are preferred, which helps
in writing pure functions and avoiding side effects.
7. Pure Functions:
8. Pure functions are the cornerstone of functional programming. They always produce
the same output for a given input and have no side effects. Pure functions are
deterministic and referentially transparent.
9. Recursion:
Recursion is often favored over iteration in functional programming languages. It
allows for concise and elegant solutions to many problems, especially those related
to traversing and manipulating data structures.
Lazy Evaluation:
Some functional programming languages support lazy evaluation, where expressions
are not evaluated until their results are needed. Lazy evaluation can improve
performance and enable more efficient use of resources.
 Benefits of Mathematical Functions in Functional Programming
Languages:

 Clarity and Predictability: Programs written in functional programming languages

tend to be more concise and easier to reason about due to the emphasis on pure
functions and immutability.

 Concurrency and Parallelism:

 Functional programming languages provide abstractions for managing concurrency
and parallelism, making it easier to write scalable and efficient concurrent programs.
 Safety and Robustness:
 The emphasis on immutability and pure functions reduces the likelihood of bugs and
makes it easier to test and debug code.
 Expressiveness:
 Functional programming languages provide powerful abstractions for expressing
complex ideas in a concise and elegant manner, leading to more expressive and
maintainable codebases.

 Support for Functional Programming in Primarily

Imperative Languages
 Imperative programming languages have always provided only limited support for functional
programming.
 That limited support has resulted in little use of those languages for functional programming.
The most important restriction, related to functional programming, of imperative languages of
the past was the lack of support for higher-order functions.
 One indication of the increasing interest and use of functional programming is the partial
support for it that has begun to appear over the last decade in programming languages that
are primarily imperative. For example, anonymous functions, which are like lambda
expressions, are now part of JavaScript, Python, Ruby, and C#.
 In JavaScript, named functions are defined with the following syntax:

 function name (formal-parameters) { body

 }

 An anonymous function is defined in JavaScript with the same syntax, except that the name
of the function is omitted.
 C# supports lambda expressions that have a different syntax than that of C# functions.
For example, we could have the following:

 i => (i % 2) == 0

 This lambda expression returns a Boolean value depending on whether the given parameter (i) is even
(true) or odd (false). C#’s lambda expressions can have more than one parameter and more than
one statement.
 Python’s lambda expressions define simple one-statement anonymous functions that can
have more than one parameter. The syntax of a lambda expression in Python is exemplified
by the following:
 lambda a, b : 2 * a – b

 Note that the formal parameters are separated from function body by a colon. Python includes the
higher-order functions filter and map. Both often use lambda expressions as their first parameter.
The second parameter of these
 is a sequence type, and both return the same sequence type as their second parameter. In Python,
strings, lists, and tuples are considered sequences. Consider the following example of using the map
function in Python:

 map(lambda x: x ** 3, [2, 4, 6, 8])

 This call returns [8, 64, 216, 512].

 Python also supports partial function applications. Consider the following example:

 from operator import add

 add5 = partial (add, 5)

 The from declaration here imports the functional version of the addition operator, which is
named add, from the operator module.
 After defining add5, it can be used with one parameter, as in the following:

 add5(15)

 This call returns 20.

 Python includes lists and list comprehensions. Ruby’s blocks are effectively subprograms
that are sent to methods, which makes the method a higher-order subprogram. A Ruby block
can be converted to a subprogram object with lambda. For example, consider the
 following:
 times = lambda {|a, b| a * b}

 Following is an example of using times:

 x = times.(3, 4)

 This sets x to 12. The times object can be curried with the following:

 times5 = times.curry.(5)

 This function can be used as in the following:

 x5 = times5.(3)

 This sets x5 to 15.

 C# includes the FindAll method of the list class. FindAll is similar in purpose to
the filter function of ML. C# also supports a generic list data type.


A Comparison of Functional and Imperative Languages

 This section discusses some of the differences between imperative and functional languages.

 Functional languages can have a very simple syntactic structure. The list structure of LISP,
which is used for both code and data, clearly illustrates this.

 The syntax of the imperative languages is much more complex.

 This makes them more difficult to learn and to use.


 The semantics of functional languages is also simpler than that of the imperative languages.

 For example, in the de notational semantics description of an imperative loop construct given
in the loop is converted from an iterative construct to a recursive construct. This conversion is
unnecessary in a pure functional language, in which there is no iteration. Furthermore, we
assumed there were no expression side effects in all of the denotational semantic
descriptions of imperative constructs
 This restriction is unrealistic, because all of the C-based languages include expression side
effects. This restriction is not needed for the denotational descriptions of pure functional
languages.
 Some in the functional programming community have claimed that the use of functional programming
results in an order-of-magnitude increase in productivity, largely due to functional programs being
claimed to be only 10 percent as large as their imperative counterparts. While such numbers have been
actually shown for certain problem areas, for other problem areas, functional programs are more like 25
percent as large as imperative solutions to the same problems (Wadler, 1998). These factors allow
proponents of functional programming to claim productivity advantages over imperative programming of
4 to 10 times. However, program size alone is not necessarily a good measure of productivity. Certainly
not all lines of source code have equal complexity,
 programming Paradigm:
 Imperative Languages: Imperative languages focus on describing the
steps that a program should take to reach a certain goal.
 They rely heavily on statements that change the program's state
through assignment and control flow structures like loops and
conditionals.
 Functional Languages: Functional languages, on the other hand, treat
computation as the evaluation of mathematical functions and
emphasize immutable data and expression evaluation rather than
changing state. They discourage or eliminate side effects and mutable
state.
 State Management:
 Imperative Languages: In imperative languages, managing state is a
core concept. Variables are mutable, and the program's behavior often
depends on the current state.
 Functional Languages: Functional languages emphasize immutability,
meaning once a value is assigned, it cannot be changed. Instead of
mutating data, functional programming prefers creating new data
structures through transformations.
 Control Flow:
 Imperative Languages: Control flow structures like loops and
conditionals are fundamental to imperative languages. Programs are
typically structured around changing state based on certain conditions.
 Functional Languages: Functional programming often uses higher-
order functions like map, reduce, and filter for control flow. Recursion is
also common for iteration.
 Side Effects:
 Imperative Languages: Imperative languages commonly allow side
effects, which are changes to state or behavior that occur outside the
primary function or method being executed.
 Functional Languages: Functional languages aim to minimize or
eliminate side effects, promoting pure functions that only depend on
their input and produce consistent output without modifying external
state.
 Concurrency and Parallelism:
 Imperative Languages: Concurrency and parallelism in imperative
languages can be complex due to mutable state and shared memory.
Synchronization mechanisms like locks and semaphores are often used.
 Functional Languages: Functional languages inherently support
concurrency and parallelism due to their emphasis on immutability and
pure functions. This makes concurrent programming safer and more
manageable.
 Expressiveness and Readability:
 Imperative Languages: Imperative languages are often more verbose,
as they explicitly describe the steps needed to achieve a particular
outcome.
 Functional Languages: Functional languages tend to be more concise
and expressive, as they focus on what needs to be done rather than
how to do it.
 Typing Systems:
 Imperative Languages: Imperative languages may use static or
dynamic typing systems,
 where variables are explicitly declared or inferred at runtime,
respectively.
 Functional Languages: Functional languages often use static typing
systems, which can help catch errors at compile time and provide
better tooling support for refactoring and maintaining code.

 Logic programming is a programming, database and knowledge

representation paradigm based on formal logic.
 A logic program is a set of sentences in logical form, representing knowledge about
some problem domain.
 Computation is performed by applying logical reasoning to that knowledge, to solve
problems in the domain.
 Major logic programming language families include Prolog, Answer Set
Programming (ASP) and Datalog.
 In all of these languages, rules are written in the form of clauses:
 A :- B1, ..., Bn.

and are read as declarative sentences in logical form:

A if B1 and ... and Bn.

A is called the head of the rule, B1 , ..., Bn is called the body, and the Bi are
called literals or conditions. When n = 0, the rule is called a fact and is written in the
simplified form:
 A.

 Queries (or goals) have the same syntax as the bodies of rules and are commonly written
in the form:
 ?- B1, ..., Bn.

 In the simplest case of Horn clauses (or "definite" clauses), all of the A, B1, ...,
Bn are atomic formulae of the form p(t1 ,..., tm), where p is a predicate symbol naming a
relation, like "motherhood", and the ti are terms naming objects (or individuals). Terms
include both constant symbols, like "charles", and variables, such as X, which start with
an upper case letter.
 Consider, for example, the following Horn clause program:

 mother_child(elizabeth, charles).
 father_child(charles, william).
 father_child(charles, harry).
 parent_child(X, Y) :-
 mother_child(X, Y).
 parent_child(X, Y) :-
 father_child(X, Y).
 grandparent_child(X, Y) :-
 parent_child(X, Z),
 parent_child(Z, Y).

 Given a query, the program produces answers. For instance for a query ?-
parent_child(X, william) , the single answer is

 X = charles

 Various queries can be asked. For instance the program can be queried both to generate
grandparents and to generate grandchildren. It can even be used to generate all pairs of
grandchildren and grandparents, or simply to check if a given pair is such a pair:

 grandparent_child(X, william).
 X = elizabeth

 ?- grandparent_child(elizabeth, Y).
 Y = william;
 Y = harry.

  ?- grandparent_child(X, Y).
 X = elizabeth
 Y = william;
 X = elizabeth
 Y = harry.

 ?- grandparent_child(william, harry).
 no
 ?- grandparent_child(elizabeth, harry).
 yes

 Although Horn clause logic programs are Turing complete,[1][2] for most practical
applications, Horn clause programs need to be extended to "normal" logic programs with
negative conditions. For example, the definition of sibling uses a negative condition,
where the predicate = is defined by the clause X = X:

 sibling(X, Y) :-
 parent_child(Z, X),
 parent_child(Z, Y),
 not(X = Y).

 Logic programming languages that include negative conditions have the knowledge
representation capabilities of a non-monotonic logic.
 In ASP and Datalog, logic programs have only a declarative reading, and their execution
is performed by means of a proof procedure or model generator whose behaviour is not
meant to be controlled by the programmer. However, in the Prolog family of languages,
logic programs also have a procedural interpretation as goal-reduction procedures. From
this point of view, clause A :- B1,...,Bn is understood as:
 to solve A , solve B1 , and ... and solve Bn .

 Negative conditions in the bodies of clauses also have a procedural interpretation, known
as negation as failure: A negative literal not B is deemed to hold if and only if the
positive literal B fails to hold.
 Much of the research in the field of logic programming has been concerned with trying to
develop a logical semantics for negation as failure and with developing other semantics
and other implementations for negation. These developments have been important, in
turn, for supporting the development of formal methods for logic-based program
verification and program transformation.

Basic Elements of Prolog

A Prolog term is a constant, a variable, or a structure.

 A constant is either an atom or an integer. Atoms are the symbolic values of Prolog
and are similar to their counterparts in LISP. In particular, an atom is either a string
of letters, digits, and underscores that begins with a lowercase letter or a string of

Any printable ASCII characters delimited by apostrophes

A variable is any string of letters, digits, and underscores that begins with an
uppercase letter or an underscore (_).

Variables are not bound to types by declarations.

The binding of a value, and thus a type, to a variable is called an instantiation.

Instantiation occurs only in the resolution process. A variable that has not been
assigned a value is called uninstantiated.

Instantiations last only as long as it takes to satisfy one complete goal, which
involves the proof or disproof of one proposition.

Prolog variables are only distant relatives, in terms of both semantics and use, to the
variables in the imperative languages. The last kind of term is called a structure.
Structures represent the atomic propositions of predicate calculus, and their general
form is the same:

The functor is any atom and is used to identify the structure. The parameter list can
be any list of atoms, variables, or other structures. As discussed at length in the
following subsection, structures are the means of specifying facts in Prolog. They
can also be thought of as objects, in which case they allow facts to be stated in
terms of several related atoms. In this sense, structures are relations, for they state
relationships among terms. A structure is also a predicate when its context specifies
it to be a query.

Fact Statements

Prolog has two basic statement forms; these correspond to the headless and headed
Horn clauses of predicate calculus.
The simplest form of headless Horn clause in Prolog is a single structure, which is
interpreted as an unconditional assertion, or fact. Logically, facts are simply
propositions that are assumed to be true.

The following examples illustrate the kinds of facts one can have in a Prolog
program. Notice that every Prolog statement is terminated by a period.

These simple structures state certain facts about jake, shelley, bill, and mary.

For example, the first states that shelley is a female.

The last four connect their two parameters with a relationship that is named in the
functor atom; for example, the fifth proposition might be interpreted to mean that bill
is the father of jake.

Note that these Prolog propositions, like those of predicate calculus, have no intrinsic
semantics.

They mean whatever the programmer wants them to mean. For example, the
proposition

could mean bill and jake have the same father or that jake is the father of bill.

The most common and straightforward meaning, however, might be that bill is the
father of jake.
Rule Statements

The other basic form of Prolog statement for constructing the database corresponds
to a headed Horn clause.

This form can be related to a known theorem in mathematics from which a

conclusion can be drawn if the set of given conditions is satisfied.

The right side is the antecedent, or if part, and the left side is the
consequent, or then part. If the antecedent of a Prolog statement is true, then the
consequent of the statement must also be true. Because they are Horn clauses, the
consequent of a Prolog statement is a single term, while the antecedent can be

Either a single term or a conjunction.

Conjunctions contain multiple terms that are separated by logical AND operations. In
Prolog, the AND operation is implied. The structures that specify atomic propositions
in a conjunction are separated by commas, so one could consider the commas to be
AND operators. As an example of a conjunction, consider the following:

The general form of the Prolog headed Horn clause statement is

consequence: - antecedent_expression.

It is read as follows: “consequence can be concluded if the antecedent expression is

true or can be made to be true by some instantiation of its variables.” For example,

states that if mary is the mother of shelley, then mary is an ancestor of shelley.
Headed Horn clauses are called rules, because they state rules of implication

between propositions.

The basic elements of Prolog include:

1. Facts:
In Prolog, facts are statements about the world that are assumed to be
true. Facts consist of predicates and arguments. Predicates represent
relationships or properties, and arguments provide the specific details.

Facts are declared using the syntax:

predicate(argument1, argument2, ...).

For example:

parent(sanjay, maya).

2. Rules:
Rules in Prolog define relationships or conditions based on other facts or
rules.

They are used to derive new information or make logical inferences. Rules
consist of a head (the conclusion) and a body (the condition). The head
specifies the result or conclusion, while the body contains the conditions or
requirements for the rule to be true.

Rules are declared using the syntax:

head :- condition1, condition2, ...

For example:

Ancestor(X, Y) :- parent(X, Y).

3. Queries:
In Prolog, you can ask queries to the system to retrieve information or test
relationships. Queries are entered in the form of goals, which are logical
statements that you want to prove or find solutions for. You can ask queries
using the syntax:

?- goal.

For example:

?- ancestor(sanjay, maya).
4. Variables:
Variables are used in Prolog to represent unknown values or placeholders.
They start with an uppercase letter or an underscore (_) and can be used
to instantiate values during the execution of a query or rule. Variables allow
Prolog to find solutions and perform unification, which is the process of
matching values. For example:

?- parent(X, maya).

Here, X is a variable, and Prolog will attempt to find a value for X that
satisfies the query.

5. Logical Operators:
Prolog provides logical operators to combine conditions and goals.

The main logical operators in Prolog are:

 Conjunction (,): Represents logical AND. It requires both conditions to

be true.
 Disjunction (;): Represents logical OR. It satisfies the goal if either
condition is true.
 Negation (not or +): Represents logical NOT. It negates a condition,
making it false.

Here are some notable applications of logic programming:

1. Artificial Intelligence (AI):

Logic programming plays a significant role in AI applications, particularly in
areas such as expert systems, natural language processing, knowledge
representation, automated reasoning, and planning. The logical and
declarative nature of Prolog allows for elegant representation of complex
problems and efficient rule-based inference.

2. Computational Linguistics:
Logic programming is widely used in natural language processing (NLP)
tasks. It provides a formal and logical framework for representing grammar
rules, parsing sentences, semantic analysis, machine translation,
information extraction, and question answering systems.

3. Expert Systems:
Logic programming has been used in the development of expert systems,
which are computer-based systems that mimic human expertise in a
specific domain. Prolog’s ability to represent knowledge in rules and facts
makes it suitable for implementing expert systems that can perform
complex reasoning and decision-making tasks.

4. Database Querying:
Logic programming languages, including Prolog, can be used for querying
databases. The logical querying capabilities allow for expressing complex
queries involving multiple relationships and conditions. Prolog’s ability to
perform pattern matching and unification makes it useful for retrieving
information from relational databases.

5. Constraint Solving:
Logic programming is effective in solving constraint satisfaction problems
(CSPs). CSPs involve finding solutions that satisfy a set of constraints or
conditions. Prolog’s ability to handle logical constraints and perform
backtracking search makes it well-suited for solving puzzles, scheduling
problems, and optimization tasks.

6. Software Verification and Testing:

Logic programming can be used for software verification and testing. By
representing program specifications, constraints, and properties in logical
rules, Prolog can verify the correctness of a program or identify possible
errors and inconsistencies. It can also generate test cases based on
specified conditions or requirements.

7. Education and Teaching:

Logic programming, particularly Prolog, is often used as a teaching tool for
introducing fundamental concepts of logic, reasoning, and problem-solving.
Its simple syntax, declarative nature, and ability to visualize solutions make
it an effective educational tool for understanding computational logic and
problem-solving techniques.

8. Semantic Web:
Logic programming languages are utilized in the Semantic Web domain to
represent and reason with knowledge on the web. They provide a formal
framework for representing ontologies, semantic rules,

and logical inferences, enabling enhanced data integration, knowledge

sharing, and intelligent web applications.

1. An Introduction to Prolog Sept. 2008

2. Prolog statements • Like other programming languages, Prolog consists of collection of
statements. • Prolog has two basic statement forms: • Headless Horn clause – called facts
• Headed Horn clause – called rules
3. Facts • Represent statements that are always true. • The parameters are usually (but not
always) constants • Examples: • female(mary). • male(bill) • male(jake) • father( bill, jake). •
mother( mary , jake). • These simple structure state certain facts about jake, bill and mary.
• Note that these Prolog facts have no intrinsic semantics. They mean whatever the
programmer wants them to mean. • For example father( bill, jake). Could mean: • Bill and
jake have the same father • Jake is the father of bill • The most common meaning is that
bill is the fatehr of jake.
4. fortran algol60 simula67 cpl bcpl smalltalk80 cplusplus c Facts (contd.) Example Facts:
link(fortran,algol60). link(c,cplusplus). link(algol60,cpl). link(algol60,simula67).
link(cpl,bcpl). link(simula67,cplusplus). link(bcpl,c). link(simula67,smalltalk8).
5. Rules • This is the other basic form of Prolog statement. • Used to construct the database
corresponds of facts. • It is a headed Horn clause • Use :- instead of  and a comma
instead of a  • Right side: antecedent (if part) • May be single term or conjunction • Left
side: consequent (then part) • Must be single term
Rules (contd.) 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).
7. fortran algol60 simula67 cpl bcpl smalltalk80 cplusplus c Rules (contd.) Example Rules:
path(X,Y) :- link(X,Z) , link(Z,Y). Example Facts: link(fortran,algol60). link(c,cplusplus).
link(algol60,cpl). link(algol60,simula67). link(cpl,bcpl). link(simula67,cplusplus). link(bcpl,c).
link(simula67,smalltalk8).
8. Goals • In Prolog, these propositions are called goals. •
A series of one or more propositions, separated by commas •
 Should be thought of as a query • If the parameters of the goal are all constants, then the
answer to the query should be “Yes” or “No” • If the parameters of the goal contain
variable(s), then the answer to the query should be all the values for those variables which
satisfy the query, or “No” if no value satisfies it.
9. Goals (contd.) • Example: • link(algo60,L) , link(L,M). /* “Are there some values for L and
M such that algo60 is linked to L and L is linked to M?” */
============================================= • male(ahmad). /* Answer
should be Yes/No */ • father(X,ali). /* Answer should be X = “ ??” or No */ •
father(ali,naser). /* Answer should be Yes/No */ • father(bill,X), mother(mary,X). /* Answer
should be X = “??? or NO*/
10. Prolog Programs • Are a series of facts and/or rules. • Can be placed in any order, due to
the nonprocedural nature of logic-based languages • Are “executed” in a Prolog
environment using goal statements.
11. Inferencing Process of Prolog • If a goal is a compound proposition, each of the facts is
a subgoal. • To prove a goal is true, the inferencing process must find a chain of inference
rules and/or facts in the database that connect the goal to one or more facts in the
database. • For example, if Q is a goal, then either Q must be found as a fact in the
database or the inferencing process must find a fact P1 and a sequence of propositions
P2, P3, …Pn such that P2 :- P1. P3 :- P2. … Q :- Pn. • Process of proving a subgoal is
called matching, satisfying, or resolution
12. Example • Consider this goal man(bob) • This goal is compared with the facts and rules in
the database. If the database includes the fact man(bob) • The proof is trivial—Yes. • If ,
however, the database contains the following fact and rule. father(bob) man(X) :- father(X)
• Prolog should find these two statements and use them to infere truth of the goal.
13. Trace Example
14. Inferencing Process of Prolog (Contd.) • 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
15. Inferencing Process of Prolog (Contd.) • When goal has more than one sub goal, can
use either • Depth-first search: find a complete proof for the first sub goal before working
on others • Breadth-first search: work on all sub goals in parallel • Prolog uses depth-first
search • Can be done with fewer computer resources
16. Inferencing Process of Prolog (Contd.) • With a goal with multiple sub goals, if fail to
show truth of one of sub goals, reconsider previous sub goal 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 sub goal.
17. 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! • Should not be done with parameters •
Either both sides must have all variables instantiated (in which case is acts as a relational
=) or just the lefthand side is not instantiated (which means the lhs receives a value) •
Therefore, the following is never appropriate: • Sum is Sum + Number.
18. Arithmetic Example
19. Arithmetic Example (Contd.)
20. Recursion • Is the only way to do iteration in Prolog • Is usually accomplished with at least
one fact and one rule • Example: Consider the following mathematical definition of
factorial: • 0! = 1 • n! = (n-1)! * n  n > 0 • Here is the equivalent Prolog statements: •
fact(0,1). • fact(N,NFact) :- N > 0, N1 is N-1, fact(N1,N1Fact), NFact is N1Fact * N.
21. List Structures • The value of a list consists of zero or more elements, separated by
commas and enclosed in square brackets. • Example: [apple, prune, grape, kumquat] •
 Each element can be an atom or a list • A variable such a L can be used to represent an
entire list in a statement. • The expression [E] in a statement denotes a one-element list. •
The expression [ ] in a statement denotes an empty list.
22. List Structures (Contd.) • The expression [X | Y] in a statement denotes a list with one or
more elements where the first element is the head X and the rest of the list (which may be
empty) is the tail Y. • This is how recursion can be used to traverse each element of a list.
• X is called the “car” and Y is called the “cdr”.(These terms are from Lisp.) • For example,
in [apple, prune, grape, kumquat], apple is the car, and [prune, grape, kumquat] is the cdr.
23. List Structures (Contd.) • A list can be created with simple proposition. new_list ([apple,
prune, grape]) • This does the kind of thing that the proposition male(ahmad) does. • We
could have a second proposition like new_list ([ apricot, peach, pear]) • In goal mode, the
list can be dismantled into head and tail. new_list ([ Head, Tail]) • Then Head is
instantiated to apricot, and Tail to [peach, pear] • The | can specify a list construction or a
list dismanteling. Note that the following are equivalent: new_list ([ apricot, peach, pear |
[ ]]) new_list ([ apricot, peach | [pear]]) new_list ([ apricot | [peach, pear]])
24. Example 1 • Appending two lists together • append([ ],List,List). • append([Head|
List_1],List_2,[Head|List_3]) :- append(List_1,List_2, List_3). • The first one specifies that
when the empty list is appended to any other list, that list is the result. • The second one
specifies several characteristics of the new list. • The left-side states that the fist element
of the new list is the same as the first element of the first given list, because they are both
named Head. • The right-side specifies that the tail of the first given list (List_1) has the
second given list (List_2) appended to it to form the tail (List_3).
25. Example 1 (Contd.)
26. Example 2 • Reversing a list • reverse([ ], [ ]). • reverse([Head|Tail], List) :-
reverse(Tail,Result), append(Result, [Head],List).
27. Example 2 (Cont.)
28. Example 3 • Seeing if a list has a particular member • member(Element,[Element| _ ]). •
member(Element,[ _|List] :-member(Element,List). • The _ is an “anonymous” variable; i.e.,
we don’t care what the value is, although a value does need to be there.
29. Example 3 (Contd.)
30. Example 4 Definition of sum function: sum([],0). sum([H|T],N):-sum(T,M), N is H+M.
31. Example 6 Definition of findOccurrences function: findOccurrences(X,[],0).
findOccurrences(X,[X|T],N):- findOccurrences(X,T,Z), N is Z+1. findOccurrences(X,[_|
T],N):- findOccurrences(X,T,Z), N is Z.
32. Useful Exercises • Write a Prolog functor that interleaves two lists. For example given the
query: ?- interleave([1,2,3,4,5],[6,7,8,9,10],X). It should return X = [1,6,2,7,3,8,4,9,5,10] •
Write a Prolog functor that succeeds if its list input consists of palindrome values. For
example given the query: ?- palindrome([1,2,3,4,5,4,3,2,1]). It should return Yes. • Write
functors to compute: • the Fibonacci function • xy for integers x and y.
33. Example 5 Definition of diffList function: diffList([], List, []). diffList([H|L1], L2, L3) :-
not(member(H,L2)), diffList (L1, L2, L4), append([H],L4,L3). diffList([_|L1], L2, L3) :- diffList
(L1, L2, L3).
34. Deficiencies of Prolog • Resolution order control • The closed-world assumption • The
negation problem • Intrinsic limitations
35. Deficiencies of Prolog (Contd.) Resolution Order Control • Depth-first search method
can cause infinite recursion • Example: • ancestor(X,X). • ancestor(X,Y) :- ancestor(Z,Y),
parent(X,Z). • Keeps trying to satisfy the second rule • Can be solved by reversing the two
propositions on the right, but that is against the basic nonprocedural philosophy of Prolog
36. Deficiencies of Prolog (Contd.) Resolution Order Control (Cont.) • The cut operator ! •
Can eliminate backtracking • Is useful when a proposition can only be satisfied once •
Form isa,b,!,c,d • If c is not satisfied, the statement cannot go back and find another
possible value for b • Example: • member(Element, [Element | _ ]) :- ! • member(Element, [
_ | List]) :- member(Element,List). • The change in the first statement assumes that the list
 consists of unique members. • The cut operator also is contrary to the Prolog philosophy of
nonprocedural programming
37. Deficiencies of Prolog (Contd.) Close World Assumption • If Prolog has insufficient data
to answer a question, the answer is “no”, just as it would be if it had sufficient data to
answer “no”.
38. Deficiencies of Prolog (Contd.) The Negation Problem • Consider the following
statement: • sibling(X,Y) :- parent(M,X), parent(M,Y). • Nothing keeps a person from being
their own sibling! • Can be solved with a not proposition: • sibling(X,Y) :- parent(M,X),
parent(M,Y),not(X = Y). • However, the not proposition is not a not operator (double
negation is not allowed), which causes some limitations
39. Deficiencies of Prolog (Contd.) Intrinsic Limitations • Prolog is often not efficient •
Example: sorted([ ]). sorted([x]. sorted([x, y | list]) :- x <= y, sorted([y | list]). • All
permutations of list must be tried until the right one is found.
40. Applications of Logic Programming • Relational database management systems •
Expert systems • Natural language processing • Education

41. 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
