Introduction

Lecture_Module 1
Introduction to Functional and
Logic Programming

Programming languages broadly fall

into two categories:

• procedural
• applicative languages.
 Procedural (imperative)
languages

• Explicitly detail out how to perform tasks

• Make use of assignment statements as a
basic construct
• Built around the control abstraction of
• sequencing,
• branching and
• looping etc.
• Variables directly refer to storage
locations.
• Programs are viewed as
• a sequence of commands (instructions)
that manipulate memory locations.
• Historically the most popular style of
programming.
• Basis for virtually all mainstream
languages such as
• C, C++, Smalltalk, BASIC, Pascal
• The users of such languages have to

• describe the problem (in terms of what is to be

computed),
• organize the computation steps in the form of
procedures and instructions
• organize the memory management during
computation.
• Proving correctness of the program in
imperative language becomes difficult
as

• it depends on the state of computation

• state is determined by the contents of each
memory location.
• it becomes worse if the program deals with
large amount of memory.
 Shift of procedural paradigm
• user concentrates on what to be computed
rather than how to be computed
• designs are not to be influenced by particular
machine details rather depend on clear
understanding of mathematical descriptions
• such programs produce more reliable results
• program proving becomes much simpler as
• it can be proved mathematically
• expressions in imperative languages are good
example of such computation
• user is relieved of naming memory locations required
for storing intermediate values.
Applicative ( Declarative)
Languages
• These are based on mathematical
principles.
• There are two computing paradigms in
applicative category.
• One is based on resolution principle, called
logic languages and
• Other is based on reduction called functional
languages.
 Logic Languages
• Focus on logical assertions describing
relationship between data values.

• Automatic derivations of answers to

questions from the assertions using
resolution.

• Logic languages have logic as base.

• Logic is a study of the methods and
principles used to
• distinguish correct from incorrect reasoning.
• However we shall consider logic as an
algebraic system for the language of
statements.
• Within the language of statements, we
need to distinguish
• proposition from predicate
• Proposition is a statement which is either
true or false but not both at same time. For
example,

• Sun is hot is true and can not be false.

• Moon is hot is false and can not be true.

• The operational structure of the languages

of propositions is called Boolean Algebra.
• Boolean Algebra becomes Boolean Logic
• if a deductive system of inference is
associated with it

• The most important deductive system of

inference is modus ponen rule i.e.,

• If P → Q and P are true then we can infer the

truth of Q.
• Inference
• It is a process by which one proposition is
arrived at and affirmed on the basis of one
or more other propositions accepted (true)
as the starting point.
• Predicate
• It is a relation having constants or
variables as its arguments such as hot (X).
• Whenever X is unified with some value,
predicate becomes true or false.
• hot(sun)
true
• Hot(moon)
false
• One predicate statement can give rise infinite
number of propositions if X takes value from an
infinite domain.
• Logic programming (LP) is based on predicate
logic.
• Predicate logic is an extension of propositional logic.
• LP deals with relations and inference.
• A relation may be defined using predicates.
Example:
• Given predicates, father(X, Y), parent(X, Y) and
male(X), we can define relations (rules) for
grandfather and son as follows:
Rules:
grandfather (X, Y) if father(X, Z),
parent(Z, Y).

son(X, Y) if parent (Y, X),

male(X).
Or
son(X, Y) if male(X),
parent (Y, X).
• The logical reading of the above rules is
as follows:
• "X is the grandfather of Y, if ∃ Z such that X is
a father of Z and Z is parent of Y".
• "X is the son of Y, if Y is a parent of X and X is
male".

• A logic program consists of a set of axioms

and a goal statement.
• The rules of inference are applied to
determine whether the axioms are
sufficient to ensure the truth of the goal
statement.

• The execution of a logic program

corresponds to the construction of a
proof of the goal statement from the
axioms.
• The user has to specify the basic logical
relationships.

• Prolog (PROgramming in LOGic) is an

approximate implementation of logic
programming.
Functional Languages

• Focus on data values described by

• expressions built from function
applications.

• Functional languages emphasize on

• evaluation of expressions, rather than
execution of commands.
• Using functions to combine the basic
values forms the expressions in these
languages.

• A functional program can be considered

as a mapping of inputs to outputs.

• A mathematical function also maps

domain elements (inputs) to range
elements (outputs).
Example: Define a function f as follows:

f : Domain -->Range
where
Domain = {a, b, c}
Range = { p, q, r}

f(a) = r;
f(b) = p;
f(c) = q
 Graphical representation
f

a p
b q
c r

• The domain and range might be infinite.

• So one can define general rule of mapping.

• Consider a function square from Integer to
Integer as follows:
square: Integer --> Integer {fun type}
square(X) = X * X {fun definition}
where, X ∈ Integer

• Here a variable X is called a parameter of

the function definition.

• X stands for any member of domain set.

• At the time of application, a particular
member of the domain is specified.
• Examples
square (5) = 25
square(10) = 100

• Combining other functions, we can create

new functions.

• The most common form of combining

functions in mathematics is composition
For Example:
f ≡ g ο h

• Applying f to argument(s) is defined to be

equivalent to applying h on argument(s)
and then applying g to the result such as:
f(x) ≡ g (h (x))

• Functional programming is characterized

by the programming with values, functions
and functional forms.
• The compositional operator is an
example of a functional form.
• Functional programming is based on the
mathematical concepts of a function.
• It includes a set of primitive functions
and a set of functional forms.
• Pure functional languages perform all
their computations via function
applications.
• The variables in functional
languages are values rather than
memory locations.
• So a variable in functional language
means the same thing no matter where
it appears in the body of a function.
• This makes it easier to understand
the program.
• Functional programs are elegant as
they are small and concise.
• Functional program encourages
thinking at higher levels of
abstraction by providing higher-
order functions.
• A higher-order function has
inputs or outputs that could also be
function abstractions.
• It also has an ability to define functions in
the form of equations by using pattern
matching.

• The list manipulations are simple because

of its simple syntax.

• True functional languages treat functions

as first-class values.
• Many theorem provers and other systems
for mathematics make use of functional
languages.

• A functional program consists of an

expression E (representing both program
and input).

• The expression E is subject to some

reduction rules.
• Reduction consists of replacing some
part P of E by another expression P'
according to the given reduction rules.

• This process of reduction will be repeated until

the resulting expression has no more parts
that can be reduced.

• The expression E’ thus obtained is called

the normal form of E and constitutes the
output of the functional program.
• LISP, Scheme, ML, Miranda and Haskell
are some of the languages to implement
this elegant computational paradigm.

• The basic concepts of functional

programming originated from lambda
calculus.

• It is widely agreed that languages such as

‘Haskell’ and ‘Miranda’ are purely
functional, while ‘SML’ and ‘Scheme’ are
not.
• However, there are some small
difference of opinions about the precise
technical motivation for this distinction.

• Scheme and Standard ML are

predominantly functional but also allow
`side effects' (computational effects
caused by expression evaluation that
persist after the evaluation is completed).
• The evaluation and execution phases are
separated in such a way that the
evaluation phase does not compromise
the standard properties of expressions
and functions.

• Since all functional languages rely on

implicit memory management, garbage
collection is an important component in
any implementation.
• Functional languages manage storage
automatically.
• The user does not decide when to de-
allocate storage.
• The system scans the memory at
intervals marking every thing that is
accessible and reclaiming remaining.
• This operation is called garbage
collection.
• Well-structured software in functional
programming is easy to
• write,
• debug, and
• provides a collection of modules that can be
re-used to reduce future programming costs.
• Conventional languages place conceptual
limits on the way problems can be
modularized.
• Functional languages push those limits
back.
• Use of higher-order functions and lazy
evaluation technique can contribute
greatly to modularity.

• Since modularity is the key to

successful programming,
• functional languages are very important
for the real world applications Artificial
intelligence.
• Functional languages facilitate the
expression of concepts and structures at
a high level of abstraction.

• Functional programming is useful for

developing executable specifications
and prototype implementations.
Mathematical function verses
Imperative Programming Function:

• The most important difference is based

on the notion of a modifiable variable.

• Mathematical function parameters

simply represent some value that is fixed
at function application time.
• A function written in a truly functional
language is a mathematical function,
which evaluates an expression and
returns its value.

• A function written in an imperative

language, such as Fortran, Pascal, or C,
• evaluates the same expression,
• may also change a value in a memory
location having nothing to do with the
expression being evaluated.
• While it may appear harmless, this side
effect prevents the substitution of the
expression's value for the invocation of
the function that evaluates it.
• Another difference is the way functions
are defined.
• Programming functions are defined
procedurally whereas
• mathematical functions are defined in terms
of expression or application of other
functions.
Logic program:
• The interpretation of logic program
cube (X,Y) <-- Y = X * X * X
∀ X,Y (Y is a cube of X if Y = X*X*X)

• It asserts a condition that must hold

between the corresponding domain and
range elements of the function.
• Here cube is a predicate name.
• We can see that cube(2, 8) is true and
cube(2,5) is false.
• Functional program:

cube(X) = X * X * X

• It introduces a functional object to which

functional operations such as functional
composition may be applied.

• Here cube is a function which when applied to

domain value, gives a value in the range such
as cube(2) gives 8 as a result.
Problems with Functional languages:

• In functional languages, complexity (in terms of

space and time) analysis is an area that has been
more or less neglected until recently.

• One of the reasons for this is that it is rather

different from ordinary complexity analysis.

• Some work has been done by Bror Bjerner's and

Sören Holmström
• Functional languages (particularly
lazy ones - those whose
arguments are evaluated when
needed) are difficult to implement
efficiently because
• There are constraints such as
memory management, garbage
collection etc. as compared to
imperative languages.
• Input/output and non-determinism
are weak areas for functional
languages.
• Arrays are a important data structure
for some algorithms.

• Unfortunately the way they are

traditionally used, i.e., with updating, does
not fit well into a pure functional world.

• A different approach is used to handle

arrays and their updates.