- (s)
In C and C++ the concepts of "expression" and "command"
are not as separated as in other languages.
For instance, --x is an expression, in the sense that it
returns a result, and also a command, in the sense that it changes the
state of x. (The exact meaning of --x is:
evaluate x-1 and let v be the result,
then store v in the location associated to x,
and return the value v.)
Expression whose evaluation might affect the state are
called "expressions with side effects", and require special care by the
programmer as they cannot be regarded as "pure values". Consider for instance
the following (incorrect) definition of the factorial function:
int fact(int x) {
if (x == 0)
return 1;
else return fact(--x) * x;
}
- What is the result returned by the call fact(3) ?
- Would the definition become correct if we substitute the command
return fact(--x) * x;
with
{int y = x; return fact(--x) * y;} ?
- Would the definition become correct if we substitute the expression
fact(--x) * x;
with
x * fact(--x); ?
(This last question is quite tricky and it is just for curiosity:
it would not be given
at the exam.)
- (s)
Consider the following command c:
begin
x, y : integer
in
x := 1;
y := 1;
begin
x : integer
in
x := 2;
y := x
end;
print(x + y)
end
Assume that env and s are the initial environment and state
(immediately before the execution of c).
Describe (using a drawing if you want):
- The state and environment immediately after the execution of
y := 1
- The state and environment immediately after the execution of
y := x
- What is the value printed by the instruction
print(x + y) ?
- (s)
Consider the following command
begin
x : integer
in x := 1;
begin
y : integer
in y := 2;
begin
x : integer
in x := y;
print(x)
end;
y := x;
print(y)
end
end
Assume that env and s are the initial environment and state.
Describe (using a drawing if you want):
- The state and environment immediately after the execution of
y := 2
- The state and environment immediately after the execution of
x := y
- What are the value printed by the instructions
print(x) and print(y) ?
- (s)
Some imperative languages allow the so-called
multiple assignment, namely a command of the form
x1 , x2 := e1 , e2
The meaning is: Given the initial environment env and state
s, the final state is obtained as follows:
-
let v1 be the result of the evaluation of
e1 in env and s,
-
let v2 be the result of the evaluation of e2 in env and s,
-
put v1 and v2 in the locations associated to x1 and x2
respectively
-
Find a particular case of e1, e2 for which the above command is semantically
different from the following concatenation: x1 := e1 ; x2 := e2
-
Assume having a language with blocks (and declarations inside blocks)
and the (single) assignment, but not the multiple assignment. Write in
this language a command semantically equivalent to x1 , x2 := e1 , e2.
If you prefer, you can define a procedure
-
Use the multiple assignment to write a command which exchanges the values
of two variables x and y (swap).
- (s)
The Fibonacci function can be defined recursively
in Pascal as:
function fibo(n:integer):integer;
begin
if n < 0
then fibo := 0 /* error */
else if n = 0
then fibo := 0
else if n = 1
then fibo := 1
else fibo := fibo(n-1) + fibo(n-2)
end;
Write an equivalent iterative implementation of this function
in C or in Pascal using only
the basic commands of the mini-imperative language
(while, if_then_else, assignment).
Don't use either recursion or data structures like arrays and lists.
- (s)
The following is a recursive function in Pascal
computing the Greatest Common Divisor of two
positive natural numbers x and y, based on
the Euclid's algorithm:
function GCD(x,y:integer):integer;
begin
if x < 1 or y < 1
then GCD := 0 /* error */
else if x = y
then GCD := x
else if x < y
then GCD(x,y-x)
else GCD(x-y,y)
end;
- Is this function tail-recursive?
- Write an equivalent iterative
function in C or in Pascal using only
the basic commands of the mini-imperative language
(while, if_then_else, assignment).
Don't use either recursion or data structures like arrays and lists.
- (s)
For each of the following three while commands, say for which initial values
of x it eventually terminates. Assume that x is
declared as an integer variable.
(1) while x > 0 do x := x - 1
(2) while not (x = 0) do x := x - 1
(3) while x > 0 do x := x + 1
Note1: we say that a while command "terminates"
if the condition eventually becomes false.
This includes the case in which the condition
is immediately false and the body is never executed.
Note2: do not consider the case of "anomalous termination" due
to overflow of the value of x.
-
Exercise 4.2 in Sethi
-
Write a procedure which prints all the prime numbers from 2 to n
(if n is smaller than 2, then
it doesn't print anything).
Remember that a number is prime if it
is not divisible by any number except 1 and itself.)
-
Write a procedure which prints all the factorials of the
numbers from 0 to n
(if n is negative, then
it doesn't print anything).
Remember that the factorial of a natural number
k is the product of all the numbers
from 1 to k if k is positive, and it is 1 if k is 0.