L7: Mutable Data

CS1101S: Programming Methodology

Low Kok Lim

September 30, 2022

CS1101S: Programming Methodology L7: Mutable Data 1

Outline

State (3.1)

Mutable Data (3.3)

CS1101S: Programming Methodology L7: Mutable Data 2

Announcements

Robotics Missions (and Quest)

Mission: Robotic Trials
• Opened yesterday; to complete and be graded in Studio S8
Mission: Moving about on Planet Y
Mission: Finding ELDRIC
Quest: PID Stop

Sumobot Competition
15-Oct-2022, Saturday, 3pm-7pm, in COM1-SR1
Two competitions: Sumobot & Robot Talent Show
Studios have to sign up next week
Rules will be announced next week

CS1101S: Programming Methodology L7: Mutable Data 3

Announcements

No Forum Hours this week

Winners of The Choreographer contest

To be presented by Grandmaster Sanka

CS1101S: Programming Methodology L7: Mutable Data 4

Reminder on Collaboration on Missions/Quests

You can discuss missions/quests with friends and Avengers

You must do the actual programming yourself
Do not copy programs from other students or previous batches
We focus on individual learning and skills
We want to know your progress, and help you to overcome your
weaknesses
Submitting other people’s work as your own is considered
Plagiarism, and is an offence and will be punished by NUS
Offender will be reported to disciplinary board
Offence will go into student’s official records with the University

NUS policy on plagiarism

https://www.comp.nus.edu.sg/cug/plagiarism/
https://www.usp.nus.edu.sg/curriculum/plagiarism/

CS1101S: Programming Methodology L7: Mutable Data 5

Module Overview

Unit 1 — Functions (textbook Chapter 1)

Getting acquainted with the elements of programming, using
functional abstraction
Learning to read programs, and using the substitution model
Example applications: runes, curves

Unit 2 — Data (textbook Chapter 2)

Getting familiar with data: pairs, lists, trees
Searching in lists and trees, sorting of lists
Example application: sound processing

CS1101S: Programming Methodology L7: Mutable Data 6

Module Overview

Unit 3 — State (parts of textbook Chapter 3)

Programming with stateful abstractions
today
Mutable data processing
Arrays, loops, searching in and sorting of arrays
Reading programs using the environment model
Example applications: robotics, image/video processing

Unit 4 — Beyond (parts of textbook Chapters 3 and 4)

Streams
Metalinguistic abstraction
Computing with Register Machines / Logic Programming /
Concurrency

CS1101S: Programming Methodology L7: Mutable Data 7

Source §3

New language: Source §3

See language documentation at

https://docs.sourceacademy.org/source_3/

Source Academy Playground is using Source §3 from now on

CS1101S: Programming Methodology L7: Mutable Data 8

Outline

State (3.1)

Mutable Data (3.3)

CS1101S: Programming Methodology L7: Mutable Data 9

 State

So far ...

Our computation has been functional

Given same argument, function always returns same result*

Memoryless / stateless — each function call is independent of

the past, and of the future

Makes it easy to reason about program behavior

• Use substitution model of evaluation

CS1101S: Programming Methodology L7: Mutable Data 10

 State

Functional Programming

Example:
factorial(5) always gives 120
• No matter how many times you call it, or when you call it

Compare with a bank account:

Suppose it starts with $100
Function withdraw returns the balance if there is enough $,
otherwise also displays error message
withdraw(40); ➔ 60
withdraw(40); ➔ 20
withdraw(40); ➔ 20 "Insufficient funds"
withdraw(15); ➔ 5

CS1101S: Programming Methodology L7: Mutable Data 11

 State

State

Identical calls to withdraw produce different results

Bank account has “memory”

It remembers something about the past
It has state

Functional programming does not allow our programs to have

state
We need to use assignment

CS1101S: Programming Methodology L7: Mutable Data 12

 State

Simple Bank Account — Using Assignment

function make_account(initial_balance) { Show in
let balance = initial_balance; Playground

function withdraw(amount) {
if (balance >= amount) {
balance = balance - amount;
return balance;
} else {
display("Insufficient funds");
return balance;
}
}
return withdraw;
}
const W1 = make_account(100);
W1(40); ➔ 60
W1(40); ➔ 20
W1(40); ➔ 20 "Insufficient funds"

CS1101S: Programming Methodology L7: Mutable Data 13

 State

Simple Bank Account — Functional Approach

function fn_make_account(initial_balance) { Show in
const balance = initial_balance; Playground

function withdraw(amount) {
if (balance >= amount) {
return fn_make_account(balance - amount);
} else {
display("Insufficient funds");
return fn_make_account(balance);
}
}
return withdraw;
}

const W1 = fn_make_account(100);
const W2 = W1(40); ➔ fn_make_account(60)
const W3 = W2(40); ➔ fn_make_account(20)
const W4 = W3(40); ➔ fn_make_account(20) "Insufficient funds"

CS1101S: Programming Methodology L7: Mutable Data 14

 State

Variable Declaration Statement

let name = expression;

Declares a variable name in the current scope and initializes its

value to the value of expression

From now on, name will evaluate to the value of expression

Note that from Source §3 onwards, function parameters are

variables

CS1101S: Programming Methodology L7: Mutable Data 15

 State

Assignment Statement

name = expression;

name is a variable; not evaluated

expression is evaluated, then its value is assigned to the

variable name

From now on, name will evaluate to the value of expression

CS1101S: Programming Methodology L7: Mutable Data 16

 State

Example

let balance = 100;

balance; ➔ 100

balance = balance – 20;

balance; ➔ 80

balance = balance – 20;

balance; ➔ 60

CS1101S: Programming Methodology L7: Mutable Data 17

 State

Multiple Accounts

const W1 = make_account(100);
const W2 = make_account(100);

W1(50); ➔ 50
W2(70); ➔ 30
W2(40); ➔ 30 "Insufficient funds"
W1(40); ➔ 10

W1 and W2 are completely independent

Each has its own state variable balance
Withdrawals from one do not affect the other

CS1101S: Programming Methodology L7: Mutable Data 18

 State

Assignment: Pros

Assignment allows us to create objects with state

State allows objects to behave differently over time

CS1101S: Programming Methodology L7: Mutable Data 19

 State

Assignment: Cons

Harder to reason about programs

Harder to debug
Harder to verify correctness

Substitution model of evaluation breaks down!

Not powerful enough to explain state
Need a more sophisticated model — Environment Model

CS1101S: Programming Methodology L7: Mutable Data 20

 State

Substitution Model Breaks Down

Consider
function make_simplified_withdraw(balance) {
return amount => {
balance = balance - amount;
return balance;
}
}

Use substitution model to evaluate

(make_simplified_withdraw(25))(20);

CS1101S: Programming Methodology L7: Mutable Data 21

 State

Substitution Model Breaks Down

Use substitution model to evaluate

(make_simplified_withdraw(25))(20);

(amount => { balance = 25 – amount; return 25; })(20);

balance = 25 – 20; return 25; // WRONG!

It returns 25, which is wrong!

CS1101S: Programming Methodology L7: Mutable Data 22

 State

Why Substitution Model Breaks Down?

Substitution model considers a constant/variable as just a

name for a value
Its value will not change
Therefore, one can be substituted for the other

But assignment considers a variable as a “container”

holding a value
The contents of the container may be changed over time
The container is maintained in a structure called an environment

CS1101S: Programming Methodology L7: Mutable Data 23

Outline

State (3.1)

Mutable Data (3.3)

CS1101S: Programming Methodology L7: Mutable Data 24

 Mutable Data

Mutable Data

Assignment gives us the ability to create mutable data, i.e.

data that can be modified
E.g. bank account

In Source §1 and §2, all our data were immutable. We had

Constructors, selectors, predicates, printers
But no mutators

CS1101S: Programming Methodology L7: Mutable Data 25

 Mutable Data

Mutable Pairs

Now we will allow mutators in order to create mutable data

structures

After creating a pair with pair

The head can be changed using set_head
The tail can be changed using set_tail

Mutating mutable pairs

set_head(p, x) changes head of pair p to x
set_tail(p, x) changes tail of pair p to x

CS1101S: Programming Methodology L7: Mutable Data 26

 Mutable Data

set_head Example

Effect of set_head(x, y)

x c d x c d

a b a b

y e f y e f

CS1101S: Programming Methodology L7: Mutable Data 27

 Mutable Data

set_tail Example

Effect of set_tail(x, y)

x c d x c d

a b a b

y e f y e f

CS1101S: Programming Methodology L7: Mutable Data 28

 Mutable Data

Be Careful with Mutators!

Example:
const a = list(1, 3, 5);
const b = list(2, 4);
const c = append(a, b);
c; ➔ [1, [3, [5, [2, [4, null]]]]]

set_head(b, 9);
b; ➔ [9, [4, null]
c; ➔ [1, [3, [5, [9, [4, null]]]]]

Mutating b changes c as well !!!

What is happening?

CS1101S: Programming Methodology L7: Mutable Data 29

 Mutable Data

Recall the append function

function append(xs, ys) {
return is_null(xs)
? ys
: pair(head(xs), append(tail(xs), ys));
}
const a = list(1, 3, 5);
const b = list(2, 4);
const c = append(a, b);

a 1 3 5

b 2 4 pairs reused

c 1 3 5 new pairs

CS1101S: Programming Methodology L7: Mutable Data 30

 Mutable Data

Mutation and Sharing

Before set_head(b, 9) a 1 3 5

b 2 4

c 1 3 5

After set_head(b, 9) a 1 3 5

b 9 4

c 1 3 5

CS1101S: Programming Methodology L7: Mutable Data 31

 Mutable Data

Be Careful with Mutators!

Another example:
const a = list(1, 2, 3);
set_tail(tail(tail(a)), a);

Cyclical structure!

a 1 2 3

What is length(a)?!

CS1101S: Programming Methodology L7: Mutable Data 32

 Mutable Data

Mutable (“Destructive”) List Processing — Append

Wanted:
A function to append two lists and return the result list
No new pair must be created
Result list is constructed from existing pairs of input lists

CS1101S: Programming Methodology L7: Mutable Data 33

 Mutable Data

“Destructive” Append

Example:
const a = list(1, 3, 5); a 1 3 5
const b = list(2, 4);
b 2 4

const c = d_append(a, b); c

a 1 3 5

b 2 4

c; ➔ [1, [3, [5, [2, [4, null]]]]]

a; ➔ [1, [3, [5, [2, [4, null]]]]]
b; ➔ [2, [4, null]]

CS1101S: Programming Methodology L7: Mutable Data 34

 Mutable Data

“Destructive” Append

Implementation:
Show in
Playground
function d_append(xs, ys) {
if (is_null(xs)) {
return ys;
} else {
set_tail(xs, d_append(tail(xs), ys));
return xs;
}
}
xs 1 3 5

ys 2 4

CS1101S: Programming Methodology L7: Mutable Data 35

 Mutable Data

“Destructive” Map

Example:
const a = list(1, 2, 3);
a 1 2 3

d_map(x => x * 2, a);

a 2 4 6

a; ➔ [2, [4, [6, []]]]

CS1101S: Programming Methodology L7: Mutable Data 36

 Mutable Data

“Destructive” Map

Implementation:
Show in
Playground
function d_map(fun, xs) {
if (!is_null(xs)) {
set_head(xs, fun(head(xs)));
d_map(fun, tail(xs));
} else { }
}

xs 1 2 3

CS1101S: Programming Methodology L7: Mutable Data 37

Summary

Assignment allows us to create state

Assignment allows us to create mutable data structures

Substitution model breaks down with assignment

set_head and set_tail mutate pairs & lists

Be careful when mutating things!

CS1101S: Programming Methodology L7: Mutable Data 38