PowerPoint Presentation
CS 345
Lecture 7
Review of Answers to Lab #2
5% growth per year for 4 years
Imperative Java
public static double numStudents(int year) {
double students = 4000.0;
int check = 0;
while(check < year) {
students = students * 1.05;
check++;
}
return students;
}
public static void main(String[] args){
System.out.print(numStudents(4));
}
4862.025000000001
Functional Racket
(define (num-students years)
(if (= years 0)
4000
(* 1.05 (num-students (- years 1)))))
> (num-students 4)
(* 1.05 (num-students 3))
(* 1.05 (* 1.05 (num-students 2)))
(* 1.05 (* 1.05 (* 1.05 (num-students 1))))
(* 1.05 (* 1.05 (* 1.05 (* 1.05 (num-students 0))))
(* 1.05 (* 1.05 (* 1.05 (* 1.05 4000))))
(* 1.05 (* 1.05 (* 1.05 4200)))
(* 1.05 (* 1.05 4410))
(* 1.05 4630.5)
4862.025000000001
Viral growth over 10 minutes
Imperative Java
public static int[] goViral(int mins, int ppl) {
int[] arr = new int[mins];
for(int i = 0; i < mins; i++) {
ppl = ppl * 3;
arr[i] = ppl;
}
return arr;
}
public static void main(String[] args){
int[] test = goViral(10, 1);
for(int i = 0; i < test.length; i++) {
System.out.print(test[i] + " ");
}
}
3 9 27 81 243 729 2187 6561 19683 59049
Functional Racket
(define (viral-growth mins ppl)
(if (= mins 0)
'()
(cons (* 3 ppl) (viral-growth (- mins 1) (* 3 ppl)))))
> (viral-growth 3 1)
(cons 3 (viral-growth 2 9))
(cons 3 (cons 9 (viral-growth 1 27)))
(cons 3 (cons 9 (cons 27 (viral-growth 0 81))))
(cons 3 (cons 9 (cons 27 ‘() )))
= ‘(3 9 27)
repeated in Racket
What you might have wanted to do:
increase the arity to access the argument to f
What you were asked to do:
(define (repeated f count)
(…
Smaller arity: only two arguments
Instead, grab the argument to f using a lambda function that will be returned to the calling function
Suggestion for how to think about this problem
Think about the base case separately
count governs the number of recursive applications, so what should happen when count is 0?
Well, what does it mean to apply a function not at all (0 times) to an argument?
(lambda (x) x) Just return the argument
Think about what the recursive case is supposed to achieve: (f1 ( f2 … (fcount x)…)count
“f applied count times to x”:
(lambda (x) (f ((repeated f (- count 1)) x)))
Functional programming has a declarative quality:
Your code describes what a quantity is, not how to program it in steps
repeated Answer
(define (repeated f count)
(lambda (x)
(if (= count 0)
x
(f ((repeated f (- count 1)) x)))))
Let’s trace the evaluation
((repeated add-one 2) 3)
((lambda (x) (add-one ((repeated add-one 1) x))) 3)
(add-one ((repeated add-one 1) 3))
(add-one ((lambda (x) (add-one ((repeated add-one 0) x))) 3))
(add-one (add-one ((repeated add-one 0) 3)))
(add-one (add-one ((lambda(x) x) 3)))
(add-one (add-one 3))
(add-one 4)
5
Participation Quiz
Answers to participation quiz are here:
https://docs.google.com/document/d/10txliEpsE3Tc37G0GJY9aFU963xOMMx0AnWlFMvJYI4/edit?usp=sharing
Today’s new topic:
Why write your program with a functional programming language?
The typical, general defense of functional programming over imperative programming is threefold:
Many people find that the declarative (“what, not how”) programming style of functional programming is easier to read, reason about, and debug. (Subjective!)
The format of functional code can be closer to the original problem statement, especially when the original problem is mathematically formulated
Concurrency becomes much easier to implement
Today: Why concurrent programming is more difficult in imperative languages
We’ll focus on imperative-style Java
What’s concurrency?
From Wikipedia:
“Concurrency is the ability of different parts or units of a program, algorithm, or problem to be executed out-of-order or in partial order, without affecting the final outcome. This allows for parallel execution of the concurrent units, which can significantly improve overall speed of the execution in multi-processor and multi-core systems.” (Emphasis mine)
In both Java and Racket (and many other programming languages), concurrency is achieved with multiple threads
What is a Thread?
A thread is a unit of execution by a CPU. It’s a collection of instructions that, together, form some specific task. A thread is a single sequence of instructions.
This Java program has one thread:
This program has two threads
Seems simple enough. So why exactly is imperative concurrency a pain?
Race conditions!
What’s happening here?
balance = balance – amount
Get the current balance amount
Evaluation (balance – amount)
Write the new quantity back into the balance register
What is a race condition?
Race conditions can generate different and unexpected outputs that are dependent on execution order. Not good! We want the same output every time.
Race conditions happen when data is shared across threads, and those threads access and mutate the data at the same time.
The solution to a race condition is to coordinate access to shared data. We’ll discuss two such solutions:
synchronized keyword
Atomic classes
Solution #1: synchronized
Obtain object’s intrinsic lock with the synchronized keyword
The lock prevents two or more threads from calling the methods of the same object at the same time.
If two threads grab the lock at the same time, only one succeeds, and the second has to wait until the first thread releases the lock before it can grab the lock and continue operation.
The programmer still has to watch out for “deadlock”
Deadlock
Deadlock is when two or more threads are blocked from execution, because they are waiting for each other to release their locks on a resource
Solution #2: Atomic Classes
The problem of deadlock cannot be solved with the synchronized keyword alone. So, Java 5 (2004) came up with an alternative solution to race conditions: Atomic classes.
When computer code is considered “atomic,” it cannot be interrupted during its execution, because it cannot be found in an intermediate state.
java.util.concurrent provides atomic classes like AtomicInteger and AtomicBoolean that allow multiple operations to be treated atomically.
Can you think of products or applications that would be clearly improved by being multithreaded?
Web browsers and web servers
Document editors
Games and animation
Big data processing
Let’s Review: What’s the Big Picture?
Imperative concurrency is harder because concurrency with shared state is harder to program
Programs are concurrent when different parts of the program can be executed in different orders or at the same time
Concurrency is needed to take advantage of multiple cores (especially on the cloud, compute instances are small but you typically work with many of them)
The problem with imperative programming is that shared state can invite “race conditions” in concurrent programs
Solving race conditions imperatively requires putting locks on all shared variables (whereby access to mutable variables is prevented until a previous thread of execution has completed) or the use of Atomic classes (whereby certain methods cannot be interrupted in the first place)
Preview of where we’re going:
Without shared state, concurrency is straightforward – even trivially so: no shared state, no race conditions.
Functional programming is definitionally programming without shared mutable state, and so it makes concurrency easier.
/docProps/thumbnail.jpeg