Advanced Programming
CO2039
Chapter 1: Stateless Programming
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC BÁCH KHOA
TP.HCM, 03/01/2025
CONTENT
01 IMPERATIVE VS DECLARATIVE
02 CORE PRINCIPLES OF FUNCTIONAL PROGRAMMING
03 CONCLUSION
2
IMPERATIVE VS
01 DECLARATIVE
3
Imperative languages
● Based on von Neumann architecture
● Relies on modifying variables (state changes)
● Use assignment to modify program state
Figure 1: von Neumann
architecture
4
What is a state?
● Programs in imperative languages rely heavily on modifying the values of a
collection of variables, called the state.
● Before execution, the state has some initial value σ.
● During execution, each command changes the state:
σ = σ0 → σ1 → σ2 → … → σn = σ’
5
Declarative languages
● No state → State-oriented computations are accomplished by
carrying the state around explicitly rather than implicitly.
● Uses expressions instead of commands
● Loops are replaced by recursion
● Functional Languages: The underlying model of computation is
function.
● Logic Programming Languages: The underlying model of
computation is predicates.
6
Example: Factorial (1)
n := x; def factorial(x):
a := 1; if x == 1:
while n > 0 do return 1
begin else:
a := a * n; return x *
n := n factorial(x-1)
– 1;
end;
Factorial in Imperative Style Factorial in Functional Style
● The value of the program is the desired factorial rather than storing it in a
store.
● Declarative programming is often described as expressing what is being
computed rather than how.
7
CORE PRINCIPLES OF
02 FUNCTIONAL
PROGRAMMING
8
Functional Programming
● Functions are first class values.
○ A data type is first class if it can be used anywhere, passed to and
returned from functions, assigned to variables
● May also have imperative constructs.
○ Examples: Lisp, Scheme, ML, Erlang
● Pure functional languages have no implicit side-effects or other imperative
features.
○ Examples: Miranda, Haskell
9
Example: Factorial (2)
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)
Factorial in Haskell
10
Why functional programming?
● John Backus (Fortran Creator) argued FP is better than imperative
programming.
● Functional programming removes state and assignments.
● Enables parallel execution (Concurrency without race conditions).
● Algebraic laws
○ Reason about programs
○ Optimizing compilers
11
Von Neumann bottleneck
● Von Neumann bottleneck: pumping single words back and forth between
CPU and store ⇒ Task of a program: change store in some major way.
● It has kept us tied to word-at-a-time thinking
○ Instead of encouraging us to think in terms of the larger conceptual
units of the task at hand.
● The assignment statement is the von Neumann bottleneck of programming
languages ⇒ Pure functional programming languages remove state and
assignments.
● Concurrency possible: order of evaluation doesn’t matter.
12
Referential transparency
● A referentially transparent function is a function that, given the same
parameter(s), always returns the same result.
⇒ Do we have such property in imperative languages?
● If the function has side-effects (updating a global variable, doing input or
output), then f(3) + f(3) may not be the same as 2 * f(3).
○ The second f(3) has a different meaning than the first.
● Purely declarative languages guarantee referential transparency.
● The importance of referential transparency is that it allows a programmer
(or compiler) to reason about program behavior.
13
03 CONCLUSION
14
Conclusion
Imperative vs Declarative Programming
● Imperative: State-based, step-by-step execution
● Declarative: Focus on "what" rather than "how"
Core Principles of Functional Programming
● Pure Functions → No side effects
● Immutability → Data doesn’t change after creation
● Higher-Order Functions → Functions as first-class values
● Recursion replaces loops
Von Neumann Bottleneck
● Traditional imperative programming relies on modifying shared memory
● Functional Programming removes mutable state → better parallelism
15
Thank you for your
attention!
https://www.cse.hcmut.edu.vn
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC BÁCH KHOA
