11.24

In the algebraic specification of a stack or queue, no mention was made of the possibility that a stack or queue might become full:

full: stack -> boolean

Such a test requires the inclusion of another operation, namely,
size: stack -> integer
and a constant
maxsize: integer

Write a set of axioms for such a stack.

fullstack(createstack) = error
sizeofstack(fullstack) = x
sizeofstack(maxsize) = x

10.27

Suppose that we wanted to state a rule that would make the C dangling reference created by the following function illegal:


int* dangle(void)
{
     int x;
     return &x;
}


Suppose that we decided to make the following statement: the address of a local variable cannot be a returned value and cannot be assigned to a nonlocal variable. 
(A) Can this rule be checked statically?
Yes


(B) Does this rule solve the problem of dangling references created by the use of a stack based environment?
Yes

10.17

Draw the stack of activation records for the following C program after (a) the call to r on line 13 and (b) after the call to p on line 14. Show the control links, and fill in the local names in each activation record. (c) Describe how variables r and x are found on lines 4 and 5 during the execution of p

1. int x;
2. void p(void)
3. {
4.      double r = 2;
5.      printf("%g\n",r);
6.      printf("%d\n",x);
7. }
8. void r(void)
9. {
10.      x = 1;
11.      p();
12. }
13. void q(void)
14. {
15.      double x = 3;
16.      r();
17.      p();
18. }
19. main()
20. {
21.      p();
22.      q()
23.      return 0;
24. }

Main

p

q

r

Free Space

Main

p

q

r

Free Space

10.8

Give the output of the following program written in C syntax using the four parameter passing methods discussed in section 10.3


int i
int a[2];


void p(int x, int y)
{   x++;
     i++;
     y++;
}
main()
{   a[0] = 1;
     a[1] = 1;
     i = 0;
     p(a[i],a[i]);
     printf("%d\n",a[0]);
     printf("%d\n",a[1]);
     return 0;
}


It prints:
1
1


it doesn't increment the values as one might think because they're passed by value, not by reference

10.6

In C,


void f(int x, double y);
void f(int a, double);
void f(int, double z);
void f(int y, double q)
{ if (q> y) printf("ok!\n");
   else printf("not ok!\n");
}


would it be legal to include all of the declarations in the same code file? Explain.


No, it would not, straight C doesn't allow function overloading.  It wouldn't even be allowed in C++ because the function declarations are all of the same form( identical type, name, and order and number of variable types).

8.23

In C++ the equality test == can be applied to arrays, but it tests the wrong thing. Also, the assignment operator = cannot be applied to arrays at all. Explain


The name of an array references the memory address of the first element of the array, so using == does not test if the arrays themselves are equal, but rather whether they exist at the same memory location. The assignment operator =, when applied to an array, would result in two arrays existing in the same location, and so the compiler prevents this.

10.2

What if we wrote an increment procedure in C as follows (remove the parentheses around *x):

void inc (int* x)

{ *x++;

}

Is this legal? If so, what does this procedure do? If not, why not?

Yes, this is legal. It increments the value that x points to

9.35

Test each of the following C/C++ code fragments with a translator of your choice (or rewrite it into another language and test it) and explain its behavior:

(a)
{
int i, n = 3;
for( i = 1; i <= n; i++)
{
printf("i = %d\n, i");
n = 2;
}

the loop runs twice and prints "i = 1" the first time through and "i = 2


(b)
int j;
for(j = 1; j <= 3; j++)
{
printf("j = %d\n", j);
j = 3;
}

it returns "j = 1", then exits the loop

9.34

C++ and java loops are often written with empty bodies by placing all side effects into the tests, such as in the following two examples:

i = 0
while (a[i++] != 0);

for (i = 0; a[i]  != 0; i++);


(a) Are these loops equivalent?
if a[0] is 0, the while loop will not run once. the for loop will run at least once

(b) Are there any advantages or disadvantages to using this style of code? Explain.
It makes it more concise, but can make it more difficult to read

9.31

Here is a legal switch-statement in C/C++

int n = ...;
int q = (n +3) / 4;
switch (n % 4)
{
case 0: do { n++;
case 3: n++;
case 2: n++; 
case 1: n++; 
}while (--q > 0);
}


Suppose that n has the value (a) 0; (b) 1; (c) 5; (d) 8. What is the value of n in each case after the execution of the above switch-statement? Can you state a general rule for the value of n after this code executes? If so, state it. If not, explain why not.

(a) 0
n = 4

(b) 1
n = 2

(c) 5
n = 10

(d) 8 
n = 16

General rule:

if(n>0) output = 2*n

if(n==0) output = 4

if(n<0) output = n

9.22

Show how to imitate a while-statement in C/C++ with a for-statement.


for(int i = 0; i < 2; i++)
{
//stuff inside while loop
if(whilecondition=true)
i=0;
else
i=2;
}

9.21

Show how to imitate a for-statement in C/C++ with a do-statement.


int x = 0;
do
{
cout << y << endl;
y = y - 1;
x++;
}
while(x <= 10);

9.20

Show how to imitate a while-statement in C/C++ with a do-statement.

int dowhile = 5;

do

{

if (dowhile > 0 == true)

{

cout << dowhile << endl;

dowhile--;

}

else break;

}

while(true);

9.10

Suppose that we were to try to write a short-circuit version of and in C as the following function:

Int and (int a, int b)
{
return a ? b : 0
}


(a) Why doesn't this work?

It will evaluate both terms no matter what, which is not short circuiting

9.4

In LISP the following unparenthesized prefix expression is ambiguous:

+ 3 * 4 5 6

It is ambiguous because there are multiple interpretations

Two possible expressions could be.

Expression 1

LISP: ( + 3 (* 4 5 6))

Real Math: (4 * 5 * 6) + 3 = 123

Expression 2

LISP: ( + 3 (* 4 5) 6)

Real Math: (4 * 5) + 3 + 6 = 29

8.47

Given the following C++ declarations,


double* p = new double(2);
void* q;
int* r;


which of the following assignments does the compiler complain about?


q = p;
p = q;
r = p;
p = r;
r = q;
r = (int*)q;
r = static_cast<int*>(q);


r = static_cast<int*>(p);

r = reinterpret_cast<int*>(p);

Try to explain the behavior of the compiler. Will *r ever have the value 2 after one of the assignments to r? Why?

q is void, and so assigning it p is fine
r = reinterpret_cast<int*>(p) forces the conversion regardless of types


the rest produce errors as follows:

p = q                                       cannot convert from void* to double*
r = p                                        cannot convert from double* to int*
p = r                                        cannot convert from int* to double*
r = q                                        cannot convert from void* to int*
r = (int*)q                                q is being used without being initialized
r = static_cast<int*>(q)         q is being used without being initialized
r = static_cast<int*>(p)         cannot convert from double* to int*


r should have the value of 2 after r = reinterpret_cast<int*>(p)

8.31

Write a polymorphic max function in C++ that takes an array of values of any type and returns the maximum value in the array, assuming the existence of a ">" operation


#include <iostream>
using namespace std;


template <typename T>
T max(T x[], int size)
{
T max x[0];
for(int i=0; i<size;i++)
{
max = (x[i]>max)?x[i]:max;
}
return max;
}


template <typename T>
T max(T x[], int size, bool (*gt)(T,T))
{
T max = x[0];
for(int i=1;i<size;i++)
{
max = (*gt)(x[i],max)?x[i]:max;
}
return max;
}


int main()
{
char temparray[4] = {'a','c','f','d'};
cout << max(temparray, 4);
system("Pause");
return 0;
}

8.15

Suppose we used the following C++ code that attempts to avoid the use of a static_cast to print out the internal value of true( see code at end of Sec 8.7)


union
{
    int i;
    bool b;
} x;
...
x.b = true;
cout << x.i << endl;

Why is this wrong(Hint: try assignment x.i = 20000 before x.b = true)


x.i is not initialized, and so will return garbage

8.5

In C,
int x[10];
int y[10];


Why will the statement x = y not compile?


x = y will not compile because the name of an array passes the address of the first element of an array, not the values stored in the array.  In order to copy the array, the assignment statement should be as follows


for(int i=0, i<10, i++)
    {
           x[i] = y[i];
    }

8.3

(a) The Boolean data type may or may not have an order relation (pg332), and it may or may not be convertible to integral types (pg350), depending on the language. Compare the treatment of the Boolean type in at least two of the following languages with regards to these two issues: Java, C++, Ada, ML.

In Java, boolean is a primitive data type.
In Ada, the boolean type is an enumeration type.In C++, the boolean type is a Numeric type. In Java and C++, 0 represents false, while all positive nonzero values evaluate to true. The boolean can be used before or after an operator. Booleans can be cast as integers in both languages, and when doing so, false => 0 and true => 1
(b) Is it useful for booleans to be ordered? convertible to integers?
If booleans were not ordered, they might not be consistently convertible to integers. It is useful to convert booleans to integers for use of booleans in calculations more concisely

7.33

Here is a legal C program with a function variable:

Figure 7.45

Compare lines 6 and 8 of this code to the equivalent code of Figure 7.45 (lines 1 and 3). Why is this version of the code permitted? Why is it not required?

The function fun_var at line 6 is allowed because it has the same parameters as the gcd function it points to, and is essentially a pointer, and so it can store the address of another function with the same parameters

7.32

Why is the following C code illegal?

{
   int x[3];
   x = (int *) malloc(3*sizeof(int));
   ...
}

x is an array, which stores an address. this is the same thing as trying to assign something to an "address of" statement

7.31

Why is the following code illegal?

{

int x;

&x = (int *) malloc(sizeof(int));

...

}

Assignments cannot be made to an "address of" statement

7.26

Given the following C program, draw box- and-circle diagrams of the variables after each of the two assignments to **x (lines 11 and 15). Which variables are aliases of each other at each of those points? What does the program print?


#include <stdio.h>


main()

{

int **x;

int *y;

int z;

x = (int**) malloc(sizeof(int*));

y = (int*) malloc(sizeof(int));

z = 1

*y = 2;

*x = y;

**x = z;

printf(%d\n",*y);

z = 3;

printf("%d\n",*y);

**x = 4;

printf("%d\n,z);

return 0;

}

After 11: All 3 variables are aliases

After 15: y and z are aliases

The program prints 1, then 3, then 4

7.14

The following program prints two integer values; the first value typically is garbage ( or possibly 0, if you are executing inside a debugger or other controlled environment), but the second value might be 2. Explain why.


#include  <stdio.h>


void p(void)
{

int y;

printf("d\n", y);

y = 2;

}

int main()

{

p(); p();

return 0;

}

The first value will be garbage or 0 because y has been instantiated but not initialized.  The second value printed may be 2 because the value of y has by then been initialized to 2, and so may keep its value for the second printf.

8.7

Given the following variable declarations in C/C++


int (*f) (int);
int (*g) (int);
int (*h) (char);


the assignment f = g is fine in C and C++ but the assignment h = g generates a compiler warning in C and a compiler error in C++. Explain


f and g are the same type, whereas h and g are different types. An integer will not fit in the space allocated for a char, and so the compiler complains

7.1

For the languages C and Java, give as precise binding times as you can for the following attributes. Explain your answers.


(a) The maximum number of significant digits in a real number

language implementation time

(b) The meaning of char

language definition time

(c) The size of an array variable

Given the existence of both static and dynamic arrays, this could be either compile or run time

(d) The size of an array parameter

compile time

(e) The location of a local variable

C: load time (static binding)
Java: run time

(f) The value of a constant

C: compile time

Java: compile time or load time, depending on whether or not the "static" keyword is specified

(g) The location of a function

C: load time unless it is declared virtual, in which case it will be bound at run time

Java: either load time or run time

3.7

(define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))

(define (bee n k) (/ (fact n) (* (fact ( - n k)) (fact k))))

(define (binn n k) (if (cond [(= k 0) 1] [(= n k) 1])

                   (+ (bee (- n 1) (- k 1)) (bee (- n 1) k))))

3.5

a.) The factorial function is referentially transparent because it is a function that is only produces one and only one output based on the input.  Unless you do not know what the input will be or there are multiple different inputs;, therefore making the factorial function non referentially transparent.

b.) A function which waits for a key to be pressed then returns pressed key is not referentially transparent because you do know what will be pressed, so using just a value would not be logical.

c.) A function that counts the number of times it is called cannot be a referentially transparent function because it needs to run in order to see what the value is it will output.  

4.17

gcd(U,V,W) :- not(V=0), R is U mod V, !, gcd(V,R,W)
This can be viewed as being tail recursive because it calls itself and will stop once R is U mod V because of the cut.  Tail recursion is when a function calls itself, this is what is occuring in this clause.

4.1

 P Q  P->Q
 T  T   T
 T  F   F
 F  T   T
 F  F   T


nP Q OR
T  T  T
T  F  F
F  T  T
F  F  F

3.8

A) (define (count l) (if (null? l)0 ( + 1 (count (cdr l)))))

B) (define (findmax l) (if (null? (cdr l)) (car l)

     (if (> (car l) (findmax (cdr l)))(car l)

     (findmax (cdr l)))))

C) (define (readnums) (let ((x (read))) (if (= x 0) '() (cons x (readnums)))))

D) (define (findmax l) (if (null? (cdr l)) (car l)

     (if (> (car l) (findmax (cdr l)))(car l)

     (findmax (cdr l)))))

     (define (findmin l) (if (null? (cdr l)) (car l)

     (if (< (car l) (findmin (cdr l))) (car l) (findmin (cdr l)))))

     (define (readnums) (let ((x (read)))

     (if (= x 0) '() (cons x (readnums)))))

    (define (minmax l) (define x l) (cons (findmin x) (list (findmax x))))

    /* Prints out the Min then Max into new list */

E) Quick Sort Scheme

F) Merge Sort Scheme

G) Haskell

pythriple n = [(x,y,z) | x <- [1..n], y <- [x..n], z <- [y..n], x^2 + y^2 == z^2]

Scheme SRFI-42

(define (pythriple n) (list-ec (:range x 1 n) (:range y x n) (:range z y n) (if (= (* z z) (+ (* x x) (* y y))) (list x y z))))

H) 8x 

(define square (lambda (x) (* x x))) 

(define twice (lambda (f) (lambda (x) (f (f x)))))

I)  (define ((inc_n n) x) 

        (cond [(> x 0) ((inc_n (+ n 1)) (- x 1))]

                  [else n]))

1.13

Recursion eliminates the need for loops to be typed out in code, simplifying the code for anyone reading it. Rather than requiring a do while, while, or for loop, a function can simply include a conditional or non-conditional call to itself, effectively stacking a new occurance of the function which starts at its beginning.


The book provides the example of this loop approach


procedure gcd(u,v: in integer; x: out integer) is
       y, t, z: integer;
       begin
             z := u;
             y := v;
             loop
                    exit when y = 0;
                    t := y;
                    y := z mod y;
                    z := t;
            end loop;
            x := z;
       end gcd;


And in contrast, the recursive version


function gcd(u, v: in integer)  return integer is
      begin
             if v = 0
                   return u;
             else
                   return gcd(v, u mod v)
             end if;
       end gcd;


The improved code efficiency and readability is immediately obvious