C Model: Memory & Control Flow
Optional Textbook Readings: CP:AMA 6.1–6.4, 7.1–7.3, 7.6,
Appendix E
• the ordering of topics is different in the text
Copyright By PowCoder代写 加微信 powcoder
• some portions of the above sections have not been covered yet
The primary goal of this section is to be able to model how C programs execute.
CS 136 Winter 2022 04: C Model 1
Models of computation
In CS 135, we modelled the computational behaviour of Racket with substitutions (the “stepping rules”).
• all arguments are evaluated to values before a function can be called (“applied”)
• to call (“apply”) a function, we substitute the body of the function, replacing the parameters with the argument values.
(define (my-sqr x) (* x x))
(+ 2 (my-sqr (+ 3 1)))
=> (+ 2 (my-sqr 4))
=> (+ 2 (* 4 4))
=> (+ 2 16)
CS 136 Winter 2022
04: C Model 2
In this course, we model the behaviour of C with two complimentary mechanisms:
• control flow • memory
CS 136 Winter 2022 04: C Model 3
Control flow
We use control flow to model how programs are executed. During execution, we keep track of the program location, which is
“where” in the code the execution is currently occurring. When a program is “run”, the program location starts at the
beginning of the main function.
In hardware, the location is known as the program counter, which contains the address within the machine code of the current instruction (more on this in CS 241).
CS 136 Winter 2022 04: C Model 4
Types of control flow
In this course, we explore four types of control flow:
• compound statements (blocks) • function calls
• conditionals (i.e., if statements) • iteration (i.e., loops)
CS 136 Winter 2022 04: C Model 5
Compound statements (blocks)
We have already seen compound statements (blocks) where a sequence of statements (and definitions) are executed in order.
int main(void) {
trace_int(1 + 1);
assert(3 > 2);
int i = 7;
printf(“%d\n”, i);
// third (i is now in scope)
CS 136 Winter 2022
04: C Model 6
Function Calls
When a function is called, the program location “jumps” from the current location to the start of the function.
The return control flow statement changes the program location to go back to the most recent calling function (where it “jumped from”).
Obviously, C needs to “keep track” of where to go. We revisit this when we introduce memory later in this section.
CS 136 Winter 2022 04: C Model 7
example: function call flow
void blue(void) {
printf(“three\n”);
void green(void) {
void red(void) {
printf(“two\n”);
printf(“five\n”);
int main(void) {
printf(“one\n”);
printf(“six\n”);
printf(“four\n”);
There is a supplemental video for this slide online.
CS 136 Winter 2022 04: C Model 8
Conditionals (if)
We introduced the if control flow statement in Section 02. We now discuss if in more detail.
The syntax of if is
if (expression) statement
where the statement is only executed if the expression is true (non-zero).
if (n < 0) printf("n is less than zero\n");
Remember: the if statement does not produce a value. It only controls the flow of execution.
CS 136 Winter 2022 04: C Model 9
The if statement only affects whether the next statement is executed. To conditionally execute more than one statement, use a compound statement (block).
if (n <= 0) {
printf("n is zero\n"); // execute this
printf("or less than zero\n"); // then this
Using a block with every if is strongly recommended even if there is only one statement. It is good style: it makes code easier to follow and less error prone.
if (n <= 0) {
printf("n is less than or equal to zero\n");
(In the notes, we occasionally omit them to save space.)
CS 136 Winter 2022 04: C Model 10
CS 136 Winter 2022 04: C Model 11
As we have seen, the if statement can be combined with else statement(s) for multiple conditions.
if (expression) {
statement(s)
} else if (expression) {
statement(s)
} else if (expression) {
statement(s)
statement(s)
CS 136 Winter 2022 04: C Model 12
CS 136 Winter 2022 04: C Model 13
If an if block contains a return statement, there may be no need for an else block.
int sum(int k) {
if (k <= 0) {
return k + sum(k - 1);
// Alternate equivalent code
int sum(int k) {
if (k <= 0) {
return 0; }
return k + sum(k - 1);
CS 136 Winter 2022
04: C Model 14
Braces are sometimes necessary to avoid a “dangling” else.
if (y > 0)
if (y != 7)
printf(“you lose”);
printf(“you win!”); // when does this print?
CS 136 Winter 2022 04: C Model 15
The C switch control flow statement (see CP:AMA 5.3) has a similar structure to else if and cond, but very different behaviour.
A switch statement has “fall-through” behaviour where more than one branch can be executed.
In our experience, switch is very error-prone for beginner programmers.
Do not use switch in this course.
CS 136 Winter 2022 04: C Model 16
The C goto control flow statement (CP:AMA 6.4) is one of the most disparaged language features in the history of computer science because it can make “spaghetti code” that is hard to understand.
Modern opinions have tempered and most agree it is useful and appropriate in some circumstances.
To use gotos, labels (code locations) are required.
if (k < 0) goto mylabel;
Do not use goto in this course.
CS 136 Winter 2022 04: C Model 17
With mutation, we can control flow with a method known as looping. while (expression) statement
while is similar to if: the statement is only executed if the expression is true.
The difference is, while repeatedly “loops back” and executes the statement until the expression is false.
Like with if, always use a block ({}) for a compound statement, even if there is only a single statement.
CS 136 Winter 2022 04: C Model 18
CS 136 Winter 2022 04: C Model 19
example: while loop
int i = 2;
while (i >= 0) {
printf(“%d\n”, i);
There is a supplemental video for this slide online.
CS 136 Winter 2022 04: C Model 20
Iteration vs. recursion
Using a loop to solve a problem is called iteration.
Iteration is an alternative to recursion and is much more common in
imperative programming.
// recursion
int sum(int k) {
if (k <= 0) {
return 0; }
// iteration
int sum(int k) {
int s = 0;
while (k > 0) {
s += k; –k;
return k + sum(k – 1); }}
return s; }
CS 136 Winter 2022 04: C Model 21
When first learning to write loops, you may find that your code is very similar to using accumulative recursion.
int accsum(int k, int acc) {
if (k <= 0) {
return acc; }
int iterative_sum(int k) {
int acc = 0;
while (k > 0) {
return accsum(k – 1, k + acc); }}
acc += k; –k;
int recursive_sum(int k) { } return accsum(k, 0);
return acc;
Looping is very “imperative”. Without mutation (side effects), the while loop condition would not change, causing an “endless loop”.
CS 136 Winter 2022 04: C Model 22
Loops can be “nested” within each other.
int i = 5;
int j = 0;
while (i >= 0) {
while (j >= 0) {
printf(“*”);
printf(“\n”);
CS 136 Winter 2022
04: C Model 23
Tracing tools
The provided tracing tools can be used to help you understand your control flow and “see” what is happening in your program.
This can help you debug your code.
The tracing tools do not interfere with your I/O testing.
On your assignments, never printf any unnecessary output as it may affect your correctness results.
Always use our tracing tools to help debug your code.
CS 136 Winter 2022 04: C Model 24
example: tracing tools
int sum(int k) {
trace_msg(“sum called”);
int s = 0;
trace_msg(“loop starting”);
while (k > 0) {
trace_int(k);
trace_int(s);
trace_msg(“loop ended”);
int main(void) {
trace_int(sum(3));
>> “sum called”
>> “loop starting” >> k => 3
>> “loop ended”
>> sum(3) => 6
CS 136 Winter 2022
04: C Model 25
while errors
A simple mistake with while can cause an “endless loop” or “infinite loop”. The following examples are endless loops (for i >= 0).
while (i >= 0)
printf(“%d\n”, i);
while (i >= 0); {
printf(“%d\n”, i);
while (i = 100) { … }
while (1) { … }
// missing {}
// extra ;
// assignment typo
// constant true expression
// (this may be on purpose…)
CS 136 Winter 2022
04: C Model 26
do … while
The do control flow statement is very similar to while. do statement while (expression);
The difference is that statement is always executed at least once, and the expression is checked at the end of the loop.
printf(“try to guess my number!\n”);
guess = read_int();
} while (guess != my_number && guess != READ_INT_FAIL);
CS 136 Winter 2022 04: C Model 27
CS 136 Winter 2022 04: C Model 28
The break control flow statement is useful to exit from the middle of a loop. break immediately terminates the current (innermost) loop.
break is often used with a (purposefully) infinite loop.
while (1) {
n = read_int();
if (n == READ_INT_FAIL) {
break only terminates loops. You cannot break out of an if.
CS 136 Winter 2022 04: C Model 29
The continue control flow statement skips over the rest of the statements in the current block ({}) and “continues” with the loop.
// only concerned with fun numbers
while (1) {
n = read_int();
if (n == READ_INT_FAIL) {
if (!is_fun(n)) {
CS 136 Winter 2022
04: C Model 30
CS 136 Winter 2022 04: C Model 31
The final control flow statement we introduce is for, which is often referred to as a “for loop”.
for loops are a “condensed” version of a while loop. The format of a while loop is often of the form:
setup statement
while (expression) {
body statement(s)
update statement
which can be re-written as a single for loop:
for (setup; expression; update) { body statement(s) }
CS 136 Winter 2022 04: C Model 32
for vs. while
Recall the for syntax.
for (setup; expression; update) { body statement(s) }
This while example
while (i >= 0) {
printf(“%d\n”, i);
is equivalent to
// expression
for (i = 100; i >= 0; –i) {
printf(“%d\n”, i);
CS 136 Winter 2022 04: C Model 33
CS 136 Winter 2022 04: C Model 34
CS 136 Winter 2022 04: C Model 35
Most for loops follow one of these forms (or “idioms”). // Counting up from 0 to n – 1
for (i = 0; i < n; ++i) {...}
// Counting up from 1 to n
for (i = 1; i <= n; ++i) {...}
// Counting down from n - 1 to 0
for (i = n - 1; i >= 0; –i) {…}
// Counting down from n to 1
for (i = n; i > 0; –i) {…}
It is a common mistake to be “off by one” (e.g., using < instead of <=). Sometimes re-writing as a while is helpful.
CS 136 Winter 2022 04: C Model 36
In C99, the setup can be a definition.
This is very convenient for defining a variable that only has local
(block) scope within the for loop.
for (int i = 100; i >= 0; –i) {
printf(“%d\n”, i);
The equivalent while loop would have an extra block. {
int i = 100;
while (i >= 0) {
printf(“%d\n”, i);
CS 136 Winter 2022
04: C Model 37
Any of the three components of a for statement can be omitted. If the expression is omitted, it is always “true”.
for (; i < 100; ++i) {...} // i was setup previously for (; i < 100;) {...} // same as a while(i < 100) for (;;) {...} // endless loop
The comma operator (,) allows for multiple sub-expressions in the setup and update statements of a for loop. Do not use it in this course. See CP:AMA 6.3 for more details.
for (i = 1, j = 100; i < j; ++i, --j) {...}
CS 136 Winter 2022 04: C Model 38
A for loop is not always equivalent to a while loop.
The only difference is when a continue statement is used.
In a while loop, continue jumps back to the expression.
In a for loop, the “update” statement is executed before jumping back to the expression.
CS 136 Winter 2022 04: C Model 39
One bit of storage (in memory) has two possible states: 0 or 1.
A byte is 8 bits of storage. Each byte in memory is in one of 256 possible states.
In this course, we will usually be dealing with bytes and not individual bits.
CS 136 Winter 2022 04: C Model 40
Accessing memory
The smallest accessible unit of memory is a byte.
To access a byte of memory, its position in memory, which is known
as the address of the byte, must be known.
For example, if you have 1 MB of memory (RAM), the address of the first byte is 0 and the address of the last byte is 1048575 (or
Note: Memory addresses are usually represented in hex, so with 1 MB of memory, the address of the first byte is 0x0, and the address of the last byte is 0xFFFFF.
CS 136 Winter 2022 04: C Model 41
You can visualize computer memory as a collection of “labeled mailboxes” where each mailbox stores a byte.
(1 MB of storage)
(one byte per address)
The contents in the above table are arbitrary values.
CS 136 Winter 2022 04: C Model 42
Defining variables For a variable definition, C
• reserves (or “finds”) space in memory to store the variable
• “keeps track of” the address of that storage location
• stores the initial value of the variable at that location (address).
For example, with the definition
int n = 0;
C reserves space (an address) to store n, “keeps track of” the
address n, and stores the value 0 at that address.
CS 136 Winter 2022 04: C Model 43
In our CS 135 substitution model, a variable is a “name for a value”. When a variable appears in an expression, a substitution occurs and
the name is replaced by its value.
In our new model, a variable is a “name for a location” where a value is stored.
When a variable appears in an expression, C “fetches” the contents at its address to obtain the value stored there.
CS 136 Winter 2022 04: C Model 44
When we define a variable, C reserves space in memory to store its value – but how much space is required?
It depends on the type of the variable.
It may also depend on the environment (the machine and compiler).
CS 136 Winter 2022 04: C Model 45
The size operator (sizeof) produces the number of bytes required to store a type (it can also be used on identifiers). sizeof looks like a function, but it is an operator.
int n = 0;
trace_int(sizeof(int));
trace_int(sizeof(n));
sizeof(int) => 4
sizeof(n) => 4
In this course, the size of an integer is 4 bytes (32 bits).
CS 136 Winter 2022 04: C Model 46
In C, the size of an int depends on the machine (processor) and/or the operating system that it is running on.
Every processor has a natural “word size” (e.g., 32-bit, 64-bit). Historically, the size of an int was the word size, but most modern systems use a 32-bit int to improve compatibility.
In C99, the inttypes module (#include
In this course, only use int, and there are always 32 bits in an int.
CS 136 Winter 2022 04: C Model 47
example: variable definition
int n = 0;
For this variable definition C reserves (or “finds”) 4 consecutive bytes of memory to store n (e.g., addresses 0x5000…0x5003) and then “keeps track of” the first (or “starting”) address.
identifier
starting address
C updates the contents of the 4 bytes to store the initial value (0).
CS 136 Winter 2022 04: C Model 48
Integer limits
Because C uses 4 bytes (32 bits) to store an int, there are only 232 (4,294,967,296) possible values that can be represented.
TherangeofCintvaluesis−231 …(231 −1)or −2,147,483,648 . . . 2,147,483,647.
In our CS 136 environment, the constants INT_MIN and INT_MAX are defined with those limit values.
unsigned intvariablesrepresentthevalues0…(232−1) but we do not use them in this course.
CS 136 Winter 2022 04: C Model 49
In the read_int function we provide, the value of the constant READ_INT_FAIL is actually INT_MIN, so the smallest value of int that can be successfully read by our read_int function is −2,147,483,647.
CS 136 Winter 2022 04: C Model 50
If we try to represent values outside of the int limits, overflow occurs.
Never assume what the value of an int will be after an overflow occurs.
The value of an integer that has overflowed is undefined.
By carefully specifying the order of operations, sometimes overflow
can be avoided.
In CS 251 / CS 230 you learn more about overflow.
CS 136 Winter 2022 04: C Model 51
example: overflow
int bil = 1000000000;
int four_bil = bil + bil + bil + bil;
int nine_bil = 9 * bil;
trace_int(bil);
trace_int(four_bil);
trace_int(nine_bil);
bil => 1000000000
four_bil => -294967296
nine_bil => 410065408
Remember, do not try to “deduce” what the value of an int will be after overflow – its behaviour is undefined.
CS 136 Winter 2022 04: C Model 52
Racket can handle arbitrarily large numbers, such as (expt 2 1000).
Why did we not have to worry about overflow in Racket?
Racket does not use a fixed number of bytes to store numbers. Racket represents numbers with a structure that can use an arbitrary number of bytes (imagine a list of bytes).
There are C modules available that provide similar features (a popular one is available at gmplib.org).
CS 136 Winter 2022 04: C Model 53
The char type
Now that we have a better understanding of what an int in C is, we introduce some additional types.
The char type is also used to store integers, but C only allocates one byte of storage for a char (an int uses 4 bytes).
There are only 28 (256) possible values for a char and the range of values is (−128 . . .127) in our Seashell environment.
Because of this limited range, chars are rarely used for calculations. As the name implies, they are often used to store characters.
CS 136 Winter 2022 04: C Model 54
Early in computing, there was a need to represent text (characters) in memory.
The American Standard Code for Information Interchange (ASCII) was developed to assign a numeric code to each character.
Upper case A is 65, while lower case a is 97. A space is 32.
ASCII was developed when teletype machines were popular, so the characters 0 . . . 31 are teletype “control characters” (e.g., 7 is a “bell” noise).
The only control character we use in this course is the line feed (10), which is the newline \n character.
CS 136 Winter 2022 04: C Model 55
32 space 480 33! 491 34″ 502 35# 513 36$ 524 37% 535 38& 546 39′ 557 40( 568 41) 579 42* 58: 43+ 59; 44, 60< 45- 61= 46. 62> 47/ 63?
64@ 80P 96 65A 81Q 97 a 66B 82R 98 b 67C 83S 99 c 68D 84T 100 d 69E 85U 101 e 70F 86V 102 f 71G 87W 103 g 72H 88X 104 h 73I 89Y 105 i 74J 90Z 106 j 75K 91[ 107 k 76L 92\ 108 l 77M 93] 109 m 78N 94^ 110 n 79O 95_ 111 o
CS 136 Winter 2022
04: C Model
ASCII worked well in English-speaking countries in the early days of computing, but in today’s international and multicultural environments it is outdated.
The Unicode character set supports more than 100,000 characters from all over the world.
A popular method of encoding Unicode is the UTF-8 standard, where displayable ASCII codes use only one byte, but non-ASCII Unicode characters use more bytes.
We will not be using Unicode in this course.
CS 136 Winter 2022 04: C Model 57
C characters
In C, single quotes (‘) are used to indicate an ASCII character.
For example, ‘a’ is equivalent to 97 and ‘z’ is 122. C “translates” ‘a’ into 97.
In C, there is no diff
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com