Transcript COMPUTATIONAL MODELS

COMPUTATIONAL MODELS
Chapter No. 1
What Is Computational
Model?
The common basis of programming
language and computer architecture is
known as computational model.
Provides higher level of abstraction than
the programming language and the
architecture.
Computational model is the combination
of the above two.
What Is Computational
Model? cont’n
E.g Von Neuman Architecture and
imperative languages, reduction
architecture and functional languages.
What Is Computational
Model? cont’n
What is a computer program?
 It is an executable representation of some algorithm
designed to solve some real world problem.
 There are thus two elements to a computer program:
 Logic - what we what the program to achieve.
 Control - how we are going to achieve the end goal.
ALGORITHM = LOGIC + CONTROL
Imperative Languages
Model of computation based on a step by step
sequences of commands.
Program states exactly how the result is to be
obtained.
Destructive assignment of variables.
Imperative Languages
con’t
Order of execution is crucial, commands can
only be understood in context of previous
computation due to side effects.
Control is the responsibility of the programmer.
E.g ALGOL, Pascal, Ada and C
Functional Languages
A program in a functional language consists of a
set of (possibly recursive) function definitions
and expression whose value is output as the
program's result.
Functional languages are one kind of declarative
language.
Declarative languages allow the programmer
to concentrate on the logic of an algorithm
(declarative languages are goal driven,control is
not the concern of the programmer)
Declarative Langauge
 Model of computation based on a system where
relationships are specified directly in terms of the
constituents of the input data.
 Made up of sets of definitions or equations describing
relations which specify what is to be computed, not how
it is to be computed.
 Non-destructive assignment of variables.
 Order of execution does not matter (no side effects).
 Expressions/definitions can be used as values.
 Programmer no longer responsible for control.
Interpretation of the Concept
of a Computational Model
 The computational model comprises of three sets of
abstraction:
Computational Model
Basic Items of
Computation
Problem Description
Model
Execution
Model
Basic Items of Computation
This is the specification of the items the
computation refers to the kind computations
(operations) that can be performed on them.
E.g of items of computations are:
data, objects or messages, arguments and
functions, elements of sets and predicate
declared on them.
Problem Description Model
 Refers to both style and method of problem description.
Problem Description Model
Style
Method
Problem Description Style
It specifies how the problems in a particular
computational model are described.
Style
Procedural
Declarative
Procedural Style
In a procedural style the algorithm for solving
the problem is stated. A particular solution is
then declared. (Imperative languages uses
procedural style)
int nfac (int n) {
int fac = 1;
if (n > 0)
for ( int i = 2; i <= n; i++ )
fac = fac * i;
return fac; }
Declarative Style
Facts and relationships related to the problem
have to be stated.
Declarative Style
Using Functions
(applicative
computational
model)
Using predicts (predict
logic based
computational model)
Declarative Style
 Functional style
relationships are
expressed using
functions.
 E.g. (square (n)
(* n n))
 This is a function
square,that express the
relationship between the
input n and the output
value n*n.
 Logic style
relationships are
declared using
expressions known as
clauses.
 E.g. square(N, M):M is N*N
 Clauses can be used to
express both facts and
rules.
Problem Description Method
Procedural style
the problem
description model
states how a solution
of the given problem
has to described.
Declarative style
the problem
description model
states how the
problem itself has to
be described.
Execution Model
Execution model consists of three components.
Execution Model
Interpretation of
the computation
Execution Semantics
Control of the
execution
sequence
Interpretation of the Execution
 How to perform the computation?
 It relates to problem description method
 Problem description method and the interpretation of
the computation mutually determines and presumes
each other.
 In Von Neumann computational model, problem
description is the sequence of instructions which specify
data and sequence of control instructions and the
execution of the given sequence of instructions is the
interpretation of the computation.
Execution Semantics
 A rule that prescribes how a single execution step is to
be performed.
 The rule is associated with the chosen problem
description method and how the execution of the
computation is interpreted.
Execution Semantics
Execution Model
State transition
semantics
Dataflow
semantics
Reduction
semantics
SLDresolution
Control of the Execution
Sequence
Control of the execution
sequence
Control
Driven
Data
Driven
Demand
Driven
Control Driven
In control driven execution it is assumed there
exist a program consisting of sequence of
instructions.
The execution sequence implicitly given by the
order of the instructions
Explicit control instructions can also be used to
specify a departure from the implicit execution
sequence.
Data Driven
It is characterized by the fact that an operation
is activated as soon as the data is available.
Also, known as eager evaluation.
Demand Driven
The operations will be activated only when their
execution is needed to achieve the final result.
Also known as lazy evaluation because the
‘delayed until needed ‘ philosophy is applied.
Relationships Between the Concepts of
Computational Model, Programming
Language and the Architecture
Computational
model
Implementation
tool
Programming
language
Specification tool
Computer
architecture
Basic Computational Models
Turing
von Neumann
dataflow
applicative
object based
predicate logic based
Von Neumann Computational
Model
Basic items of computation
data is the basic item of computation
data items are identified by names in order to
distinguish between different data items used in the
same computation.
The named entities are known as variables in a
programming language and in architectures
Multiple data assignments are allowed.
Von Neumann Computational
Model
Problem description model
The computational task is specified as a sequence of
instructions (Procedural Model).
Execution model
the computation is performed according to the given
sequence of instructions.
Instruction execution follows a state transition
semantics and the model behaves just like finite state
machine.
Each instruction transfers the state of the machine to
the present state to next one, in a definite way as
specified by the semantics of the instruction.
Computational Model
Corresponding
programming
languages
Corresponding
architectures
Key Concepts Related to
Computational Model
Granularity
From computational model’s point of view granularity
is interpreted as the complexity of the items
computation.
From parallel architectures point of view granularity
is interpreted as size of parallel computations that
can be executed without any synchronization or
communication..
Granularity can be classified as fine grained and
coarse grained.
Granularity Example
Granularity
Low
High
Language Class
Conventional
assembly
language
Conventional
High
language
Fig 1.21 The interpretation of granularity for programming languages
Key Concepts Related to
Computational Model
Typing
the concept of typing is used at a higher level in
connection with programming languages but from
computational model’s point of view typing of
languages and architecture is closely related.
In typed languages there exist a concept of data type
and the compiler or interpreter checks the
consistency of the types used in function invocation,
expressions etc.
the language may be strongly typed or weakly typed.
Strongly typed languages are Pascal, Miranda, hope,
C
Typing
Weekly type languages are LISP, FP. They are also
know as untyped languages
Typed architectures are commonly known as tagged.
They provide a mechanism for typing the data being
stored or processed, by extending the data word by
tag.
The tag contain the type identification and usually 35 bits long.
Tagging bridge the gap between untyped
architecture and weakly typed language