PROGRAMMING

PARADIGMS
CS 322 - PROGRAMMING
LANGUAGES
WHAT IS A
PROGRAMMING
PARADIGM?
DEFINITION
Paradigm: "A philosophical and theoretical framework of a scientific school or
discipline within which theories, laws, and generalizations and the experiments
performed in support of them are formulated; broadly: a philosophical or theoretical
framework of any kind"

http://www.merriam-webster.com/dictionary/paradigm
PARADIGMS AS ‘WAYS OF ORGANIZING
THOUGHT’
Programming paradigm
=
The basic structuring of thought underlying the programming activity

e.g.. when you think of a programming problem, what are you thinking of?
• the sequence of actions to perform (first download the file, then display it)
• how to divide the problem-space into sub-tasks (to compute the spanning tree, i can divide the
graph arbitrarily in two, and then …)
• what are the agents involved (sensors, a simulator, a renderer, …)
• what data do we need to handle? do we need intermediate representations? what are the
relations between the different forms?
PARADIGMS AS ‘WAYS OF ORGANIZING
THOUGHT’
Note that the same way of thinking is not adapted to all problems. Hence, it is important to know
many paradigms!

To each paradigm corresponds a "(mental) model of the computer"

How do you think of your computer?
• A bunch of transistors? (Very hard to reason at this level…)
• Memory + instructions (von Neumann model)
• Rewriting engine (substitution model)
• (evaluator of) Mathematical functions
• A network: a number of units of execution communicating with messages
• A prover of theorems (search model)
• …
PARADIGMS AND LANGUAGES
Paradigms are underpinned by programming
language features.
"If you cannot formulate it, you can't think it"

The big-bang of languages

• In the old days: languages were built around a
central idea, crystallized in a paradigm.
• Explosion in the number of languages
• Now, there is a lot of cross-fertilization
between languages: real-world languages
implement apparently random collections of
features.
• A given paradigm needs a specific set of
features to be supported.
FLUIDITY BETWEEN PARADIGMS
As a working programmer, you will often look at a program and think: "this is a big mess". Your
problem is to make sense of this mess. Perhaps the code was written using the "wrong" paradigm;
perhaps the features to support the paradigms are not available to the programmers, and they used
a wrong method for the implementation.

• We will learn to properly encode features using others

• By doing so we will also learn to recognize "a mess" as an encoding of some feature(s) into
others.
A REMARK ON PARADIGM SHIFT
After writing many programs, you may notice patterns emerging. These patterns may become
codified, either informally (cf. "Design Patterns", the seminal book) or formally within the language
(cf. Haskell type-classes).

Eventually, all programming may revolve around a number of patterns; the old ways are abandoned.
This is the paradigm shift: a new way of thinking appears. Eventually, a new programming language
may be developed to support the "patterns" directly.
ABSTRACTION
AND TYPES
ABSTRACTION AND TYPES
Types are essential to get a quick overview of what a program is "about". Very useful when facing
unknown programs! We use them a lot in this course to structure the thinking about programs.
The colon ':' is used to denote the typing relation:

someValue : ItsType

1. Examples
• 0 : Int
• 1 : Int
• 1 : Natural
• 'c' : Char
• "hello" : String
• 0.5 : Float
• (1/2) : Rational
ABSTRACTION AND TYPES
2. Feature: naming things
One could write a program to compute the area of the floor of the copper-dome as follows, assuming
the floor is a circle of radius 20 meter.

area = 20 * 20 * 3.141592

It is error-prone to write the radius multiple times. (if someone were to give a better measure for the
radius, or a better approximation for π, I might forget to update one of the instances in the program.)
Furthermore it might be useful to give a meaningful name to the value. Hence most programming
languages allow you to write:

radius = 20
pi = 3.141592
area = radius * radius * pi
ABSTRACTION AND TYPES
3. Feature: Parametrization and function types
Now is a good time to see our first programming language feature. This feature is so ubiquitous that
nearly every language has it. (Can you think of a counter-example?). In fact, you may not have
thought of it as a "feature" at all so far. We are talking about the ability to abstract over parameters.

Consider a simple value like this:

greetMe : String
greetMe = "Hello, Jean-Philippe! How are you today?"

That's very useless as a program! We want to be able to greet more than one person. To do so, we
should and parametrize (or abstract) over the name of the person greeted.
ABSTRACTION AND TYPES
As an intermediate step, let us name the part we wish to abstract over:

name = "Jean-Philippe"
greet = "Hello, " ++ name ++ "! How are you today?"

Now, we can leave the name abstract. (Most programming languages require the programmer to
mark abstract things explicitly. In this example we write the parameter inside parentheses):

greet(name) = "Hello, " ++ name ++ "! How are you today?"

When using abstraction, programs get more complicated. In particular, it might not be so clear that
every value can be used for the parameter. What if name is a floating point number? In this simple
example it is pretty obvious, but in reality things get hairy pretty fast.
ABSTRACTION AND TYPES
In our example, we may declare that the above code makes sense only when name is a string (more
precisely any string); and in that case greet(name) is also a string. Equivalently, we will say that
greet is a function converting a string into another string, and we will write:

greet : String → String

The flip side of abstraction is application (or use). Given an abstract piece of code, one can use it as
many times as desired on concrete cases.

greet "dog"
greet "there children!"

Philosophical remark: if there is no application possible; abstraction is useless — so they really are
two sides of the same coin.
ABSTRACTION AND TYPES
4. Aside: Functions as a special kind of relations?
(Will be revisited when we see logic programming) You may have encountered the arrow notation for
types earlier in your studies, in the context of maths. Usually, math is built on top of set theory, and
hence functions are defined as a special kind of relation. (We will revist this idea in the chapter on
logic programming.)

However, in this course, we take the view that arrow (function) type is a primitive (foundational)
notion, based on the intuition discussed previously.
ABSTRACTION AND TYPES
5. Model: substitution
• The meaning of application is substitution.
area 20 ⟶ (\r -> r * r * pi) 20 ⟶ 20 * 20 * pi ⟶ 400 * pi ⟶ …
• 2. remember 'inlining'
inlining usually means 'substitution' of the reference by its value.
• pitfall: name-capture
Example:
area r = let r2 = r * r in r * pi
ringArea r1 r2 = area r2 - area r2
To avoid name-capture (or any kind of side-effect) evaluate the arguments first!
ABSTRACTION AND TYPES
6. Higher-order abstraction
Will be revisited when we see functional programming.
"What can be named/abstracted on" is an important characteristic of programming languages.
Consider you favorite programming language. Does it support abstraction over:
• integers?
• characters?
• strings?
• arrays?
• matrices?
• blocks of code?
• functions?
• types?
• modules?
• …
IMPERATIVE
PROGRAMMING
MODEL: VON NEUMANN COMPUTER
"von Neumann" model of the computer:
• Memory cells
• Program (assignments, arithmetic, logic, (conditional) jumps)

This is similar to what you may find in a cookbook:

Ingredients:
• Pasta
• Water
• Boil water
• Throw pasta in water
• Taste
• if too hard, then goto 2.
MODEL: VON NEUMANN COMPUTER
Model: Turing machine
An idealised version of the von Neumann computer is the "Turing Machine" (invented by Alan Turing).
The memory of the turing machine consist of an infinitely-long 1-dimensional tape divided into equal-
size pieces each containing one bit.

The "computing" is performed by a transition function from the internal state of the machine, and the
current symbol on the tape, to a new state and an instruction, which can be either to move the tape
or write a symbol (bit) at the current position.

This extremely idealised machine is interesting from a theoretical viewpoint, because it is at least
powerful as the von Neumann computer, while being even simpler. Furthermore, any computer (and
any programming interface built on top of it) can be reduced to a Turing machine.
A programming language is said to be "Turing-complete" if one can do as much as a Turing machine
in it.
EXAMPLE: SORTING
1. Feature: GOTO
A pretty basic feature of imperative language is the jump (also known as "GOTO"). A goto is an instruction to jump to a
particular point in the program. Sometimes, a condition is associated with the jump: the jump is performed only if the
condition is true.
Based on your understanding of GOTO, try to figure out what the following code does. Do you find it easy to
understand? In the next section we will propose an improvement.
-- Assume A : array of comparable items
begin:
swapped = false
i := 1;
loop:
if A[i-1] <= A[i] goto no_swap
swap( A[i-1], A[i] )
swapped = true
no_swap:
i := i+1
if i < n then goto loop
if swapped goto begin
EXAMPLE: SORTING
2. Feature: Loops & Ifs
It has been noted that programs written using only gotos in arbitrary ways are pretty hard to understand. (One
sometimes refers to this sort of programs as "spaghetti code")
Therefore, usage of gotos should be restricted to a few easy patterns (loops; or conditional execution). Nowadays gotos
have almost disappeared from usage and all code is written using special-purpose instructions for the above patterns.
This is an instance of paradigm shift.
Here is a program doing the same as the above, but using only loops and if. Is it easier to understand?
-- Assume A : array of comparable items

swapped = true
while swapped
swapped = false
for each i in 1 to length(A) - 1 inclusive do:
if A[i-1] > A[i] then
swap( A[i-1], A[i] )
swapped = true
end if
end for
EXAMPLE: SORTING
3. Feature: procedures
The above code is parametric over the array A. If the language supports abstraction over arrays we should take
advantage of it and present the above program as a procedure.

procedure bubbleSort( A : array of comparable items )

swapped = true
while swapped
swapped = false
for each i in 1 to length(A) - 1 inclusive do:
if A[i-1] > A[i] then
swap( A[i-1], A[i] )
swapped = true
end if
end for
end
end procedure
TRANSFORMATION: LOOPS ⟶ GOTOS
1. Source
Consider the following loop:

while i > 0 do
a[i] := b[i]
i := i-1
TRANSFORMATION: LOOPS ⟶ GOTOS
2. Target
It can be encoded into the following code, which uses only (conditional) jumps:

test:
p := not (i>0)
if p then goto done
a[i] := b[i]
i = i-1
goto test
done:

Note in passing that such a job is typically performed by a C (or Java…) compiler. Indeed,
the computer code has no notion of loop, it only knows about jumps.
TRANSFORMATION: LOOPS ⟶ GOTOS
3. Feature: do … until

do
body
until cond

is translated to

loop:
body
if not (cond) goto loop;

In fact the above transformation is parametric on the condition and body of the loop. Hence
we may just abstract over these parts. We will present the next transformation in this format.
TRANSFORMATION: LOOPS ⟶ GOTOS
4. In-class exercise: insertion sort
TRANSFORMATION: IF THEN ELSE ⟶ GOTOS
1. Source
Assuming a Boolean-valued expression cond and two blocks of code part1 and part2, and the
following pattern:

if cond then
part1
else
part2
TRANSFORMATION: IF THEN ELSE ⟶ GOTOS
2. Target
It can be translated into:

p := not(cond)
goto label2 when p is true
part1
goto done
label2:
part2
done:
TRANSFORMATION: IF THEN ELSE ⟶ GOTOS
3. Computed jumps
Most computers also feature computed (indirect) jumps. That is, one does not jump to a fixed label, but to a
variable one. This is once more an example of abstraction: the computed goto is a goto which is "abstract" over its
target.
For example using a computed jump one may translate if as follows:

if cond then
target = label1;
else
target = label2;
goto target
label1:
part1
goto done
label2:
part2
end
done:
REVERSE TRANSFORMATION: (GOTOS ⟶
LOOPS)
The reverse transformation (from jumps to structured constructions) is not so easy. That is,
there is no general formula that gives you structured/"beautiful" code from "spaghetti" code
made up of arbitrary gotos. Inventing a beautiful structure requires a creative leap! A good
first step is to try to recognize the patterns generated above and reconstruct the source from
them… But it fails on true spaghetti code.
TRANSFORMATION: INLINING PROCEDURE
CALLS
This is the reverse of naming code blocks.

1. Source 2. Intermediate 3. Final

procedure g(by ref. x,y) procedure f(x,y) a := a + b

x := x + y x := x + y a := a + 1
x := x + 1 b := b + a
procedure f(by ref. x,y) y := y + x
g(x,y)
x := x + 1 f(a,b)
g(y,x)

f(a,b)
FEATURE: PARAMETER PASSING BY VALUE
Passing a parameter by value is equivalent to making a copy of the parameter before passing it to the function procedure.
This means that, if the function/procedure updates the parameter, the argument remains untouched at the call site.

This is what happens in C (pitfall: arrays) and (by defaut) in C++.

void updateOrNot(int x) {
x = 12;
}

int main(void) {
int x = 56;
updateOrNot(x);
return x;
}

// use echo $? to see the result

// substitution model meaning?

FEATURE: PARAMETER PASSING BY REFERENCE
1. Example

#include <stdio.h>

void updateOrNot(int &y) {

y = 12;
}

int main(void) {
int x = 56;
updateOrNot(x);
printf("%d\n",x);
return x;
}

// use echo $? to see the result

// substitution model meaning?

// von neumann model meaning?
FEATURE: PARAMETER PASSING BY REFERENCE
2. Meaning in the substitution model
Consider a declaration of the procedure 'swap' together with a number of calls:

procedure swap(by reference x, by reference It is equivalent to the following program:

y)
local var tmp; tmp := x;
tmp := y; y := x;
y := x; x := tmp;
x := tmp; ...
swap(x,y)
...
...
tmp := x;
...
y := x;
swap(x,y)
x := tmp;
...
... In other words: if parameters are passed
...
... by reference, calling the
swap(x,z)
tmp := x; function/procedure is equivalent to
z := x; copying its body at the call site. (pitfall:
x := tmp; name capture; side effects)
FEATURE: PARAMETER PASSING BY REFERENCE
3. Why is passing by reference useful?
• Passing by reference means that the programmer can name blocks of code.
• "expressive power" : you can factor out parts of the computation that update any (sub-
part of) the state
• save time : no need to copy around things
FEATURE: PARAMETER PASSING BY REFERENCE
4. Reminder: References (aka. pointers)
1.Example
#include <stdio.h>

int x = 777;
int y = 888;

int* p = &x;

int main () {
printf("%lx\n", (long) &p);
printf("%d\n", *p);
return 0;
}
FEATURE: PARAMETER PASSING BY REFERENCE
2. Example
Assume a variable x:
x : Integer {-Variable -}
x : int;

Then
addressOf(x) : PointerTo Integer
&x : int*;

≃ where in the memory is the variable x

We could express this with the following typing for addressOf:

addressOf : Integer {-By Ref-} → PointerTo Integer
FEATURE: PARAMETER PASSING BY REFERENCE
3. "De-reference"
variableAt : PointerTo Integer → Integer

or

p : Integer ⊢ variableAt(p) : Integer

or, borrowing some C syntax

p : int ⊢ *p : int
TRANSLATION: FROM REFERENCE-PARAMETERS TO
5. We can give a meaning to reference parameters in the von Neumann model as well, by using pointers.
POINTERS
1.Source:
(Supposing the language supports passing arguments by reference:)
procedure increment(by ref. x : Int)
x := x + 1

with a call
increment(y)

or in C++ syntax:
void increment(int &x) {
x = x+1;
}

with a call
increment(y);
TRANSLATION: FROM REFERENCE-PARAMETERS TO
POINTERS
2. Target
(Assuming the language supports pointers:)
increment(x : PointerTo Int)
variableAt(x) := variableAt(x) + 1

and the call

increment(addressOf(y))

or in C syntax:
void increment(int *x) {
*x = *x+1;
}

with a call
increment(&y);
THANK YOU