Transcript Chapter 8

Chapter 8
Alternative Programming
Paradigms
Paradigm


A paradigm is a model or mental framework for
representing or thinking about something.
Programming in a procedural language consists of:
• Planning the algorithm
• Capturing the “unambiguous and effectively computable
operations” as program instructions

Alternative paradigms for programming
languages include viewing a program’s actions as:
• A combination of various transform upon items
(functional programming)
• A series of logical deductions from known facts (logic
programming)
• Multiple copies of the same subtask or multiple subtasks
of the same problem being performed simultaneously by
different processors (parallel programming)
Functional Programming





LISP (LISt Processing)
FP (Functional Programming)
A functional programming language views
every task in terms of functions.
Here ‘function’ means something like a
mathematical function – a recipe for
taking an argument and doing something
with them to compute a single value.
Example: the function f(x)=2x transform
the argument 3 into 6.
Primitive Functions




Certain functions, called primitive functions or
just primitives, are defined as part of the
language.
Other functions can be defined and named by the
programmer.
Example: (using Scheme, a functional
programming language derived from LISP)
(define (double x)
(* 2 x))
(define (square x)
(* x x))
(define (polynomial x)
(double (square x))
Also called applicative languages.
LISP






LISP processes lists of things.
The argument to functions are often
lists.
nil: empty list
(list 3 4 5)
(car (list 3 4 5)) returns 3
(cdr (list 3 4 5)) returns (4 5)
Adding Non-negative Integers





(define (adder input-list)
(cond ((null? input-list) 0)
(else (+ (car input-list)
(adder (cdr input-list))))))
(adder (list (3 4 5))) returns 12
adder is a Recursive function
A functional language allows for clarity of thought;
data values are transformed by flowing through a
string of mathematical functions.
Adds another layer of abstraction to the
programmer.
Logic Programming




Various facts are asserted to be true, and on the
basis of these facts, a logic program can infer or
deduce other facts.
When a query (a question) is posed to the
program, it begins with the storehouse of facts
and attempt to apply logic deductions, in as
efficient a manner as possible, to answer the
query.
Sometimes called declarative languages because
their programs, instead of issuing commands to
do something, make declarations or assertions
that various facts are true.
Used to write expert systems.
Prolog





PROgramming in LOGic
Originally intended as a tool for natural
language processing
Prolog programs consist of facts and rules.
A fact expresses a property about a single
object or a relationship among several
objects.
Examples:
president(lincoln,civil_war)
before(fdr, kennedy)
Examples

A query:

?-president(loncoln,civil_war),before(lincoln,fdr)
?-before(lincoln,fdr) will return Yes.

?-president(lincoln,X)
X is a variable in Prolog (variables must begin with
upper-case letters)

Derive new facts:
• precedes(X,Y) if before(X,Y)
• precedes(X,Y) if before(X,Z) and
precedes(Z,Y)
Prolog Rules


A prolog rule is a declaration of an “if
A then B” form
Example:
precedes(X,Y) :- before(X,Y)
precedes(X,Y) :- before(X,Z), precedes(Z,Y)

Figure 8.12: A Prolog Program

earlier(X,Y) :president(R,X),president(S,Y),precedes(R,S)
The Logic Programming Paradigm
Facts
Rules
Knowledge
base
Query
Inference Engine
Response
Parallel Programming



“Grand Challenge” computing
problems
SIMD: single instruction, multiple
data stream
MIMD: multiple instruction, multiple
data stream