1. Write a short code segment in which the presence/absence of short-circuiting will significantly impact the program behaviour, and explain why this is so.
2. Re-write the code so that it is correct regardless of whether the language implementation includes or does not include short-circuiting.

 Sample solution
 (1) if ((x != 0) && (y / x > 1)) {
        ....
     }
     // if short circuiting is not used this crashes on x == 0
 
 (2) if (x != 0) {
        if (y / x > 1) {
           ....
        }
     }

1. Global and local variables
2. Stack-dynamic and heap-dynamic variables
3. Implicit and explicit type conversions
4. Widening and narrowing conversions

 Sample Solution

#include <iostream.h>

int myglobal;  // global

void fillarray()
{
   int *ptr; // local
   ptr = new int[10]; // heap dynamic

   for (int i = 0; i < 10; i++) { // i is stack dynamic
       ptr[i] = 1.5 * i;          // implicit, narrowing conversion
   }
}

void main()
{
   float f;
   f = (float)(3 + 4); // explicit, widening conversion
}

1. Outline the major concerns associated with allowing multiple entry points to a counter-controlled loop.
2. Assuming you were to design a language allowing multiple entry points to such loops, describe how you would address these concerns, and what impact your approach would have on programmers who wished to use your language.

 Sample Solution
Concerns

   - counter may not be declared/allocated/initialized
   - important error checking may be bypassed
   - desired side effects may be bypassed
   - code readability and maintainability suffers
     since we can't be sure which entry point
     has been used 

Many design possibilities here, some suggestions were

   - clearly label each entry point with the
     preconditions for that entry point,
     then leave use in the hands of the programmer
 
     this is efficient and readable, but there
     is no guarantee it will be used correctly

   - include appropriate error checking and exception 
     handling (addressing initialization etc) at each 
     entry point

     this detracts from run-time efficiency,
     but addresses concerns about misuse

   - have correctly-initialized non-local variables
     encompassing the scope of any counters used,

     handles first concern, but not others

1. Suppose you are working with a C-like language, with the major difference being this language uses dynamic scoping rules. Write a Fibonacci function that works correctly without using global variables and without passing parameters.
2. Write another Fibonacci function that works correctly regardless of whether static or dynamic scoping is used (you may use parameters for this one).

 Sample Solution
We *must* assume we know the name of the non-local variable
  that holds the desired "parameter" value,
in both versions below we assume N

Iterative version              Recursive version
int fibonacci()                int fibonacci() {
    int prev = 1;                  if (N < 2) return N;
    int next = 1;                  int temp = N;
    int counter = 2;               return fib2();
    while (counter < N) {      }
      next = next + prev;
      prev = next - prev;      int fib2() {
      counter++;                   int N = temp - 1;
    }                              int result = fibonacci();
    return next;                   N--;
}                                  result += fibonacci();
                                   return result;
                                }

Describe the limitations and any potential advantages associated with such a language.

 Sample Solutions
There are many limitations, including:
   - attribute binding and type checking takes place dynamically,
     so much slower in execution
   - difficult to read and maintain due to the possibly advanced
     nature of "side effects"
   - possible parameter collision on pass-by-result if same 
     name passed for multiple parameters
   - pass by result implementation issues can lead to portability problems

The primary advantage is in flexibility:
   - pass by name can be *very* flexible,
     allowing same function to be used for a variety of
     purposes based on the parameters passed

Question 6:
Under what circumstances is an imperative style of programming likely to be superior to (or more desirable than) all of the following: an object-oriented style, a functional-programming style, and a logic-programming style. Justify your answer.

Question 7:
Scoping issues in an object-oriented programming language are more complex than in strictly imperative programming languages.

For the C++ programming language in particular, identify all the different scopes which must be addressed, and any significant language design and implementation issues associated with each scope.

Question 8:
Exception handling mechanisms provide a alternative to the standard program flow-of-control (in terms of loops, subroutine calls, etc).

Using C++ as a specific example, explain the potential dangers associated with the use of exception handlers, and hence the ways in which exception handling should not be used.

Question 9:

Suppose we are using a language whose syntax is identical to C++, but in this language it is left to the language implementor to decide whether static scoping or dynamic scoping is used. (I.e. they choose whether to use static scoping and the language is thus identical to C++, or to use dynamic scoping - in which case the behaviour of programs could be significantly different.)

Write a program that will compile and run under either version, and which correctly identifies and displays which implementation style has been chosen.

SAMPLE SOLUTION

For this one, you need a program that will work correctly using static scoping,
but has different (though still valid) behaviour using dynamic scoping.

To do so, you'll need two variables with the same name,
   overlapping static scopes, and different values under dynamic scoping.

For example:
#include <iostream.h>

int N = 0; // global scope

void scope();

void main()
{
   int N = 1; // local scope
   scope();
}

void scope()
{
   if (N > 0) cout << "dynamic scoping" << endl;
   else cout << "static scoping" << endl;
}

Question 10:

Suppose your supervisor comes to you to ask for help debugging some legacy code written in two languages you are unfamiliar with.

Provide appropriate comments describing the behaviour of the code segments shown below (each of which is actually intended to compute the same thing) and attempt to identify and fix the problem for each.

Function 1: in the language Forth

: F recursive

  DUP 0 >

  IF

     DUP 1 - F *

  ELSE

     DROP 1

  ENDIF

Function 2: in the language K

f: {


   if[ x>1; :x * f[x-1] ]


   :0


}

SAMPLE SOLUTION
Both functions compute factorials recursively,
  the trick is in identifying how

In Forth, the "current value" is implicitly tracked through a stack,
   which is why you never see it explicitly used in the code
The DROP command is effectively carrying out a return via the top of stack

The notation used is postfix, as most people picked up on,
    but that holds for the IF statement as well as the expressions
i.e. (blah) IF X ELSE Y 
     would translate to 
     if (blah) X; else Y; 
     in a C-like language

Thus the code segment below corresponds to 
     if (N > 1)
        compute/return N * F(N-1)
     else 
        compute/return 1

: F recursive
  DUP 1 >
  IF
     DUP 1 - F *
  ELSE
     DROP 1
  ENDIF

In K the syntax was clearer for most people,
   with the minor catch of using : to designate return values
i.e.
   if (x > 1) return x*f(x-1)
         else return 0
The bug here, of course, is that the recursion always winds
   down to x==0, which winds up giving all factorials as
   having value 0 when you multiply out
You can fix the bug by setting the "else" line to
   :1

f: {
   if[ x>1; :x * f[x-1] ]
   :1
}

Question 11:

1. Outline the major concerns associated with allowing automatic resizing of arrays. I.e. if the user has an array of 10 elements, and assigns a value to position 23, then the array is automatically resized to hold at least 23 elements.

2. Assuming you were to design a language allowing this, describe how you would address the concerns of part 1, and what impact your chosen approach would have on programmers who wished to use your language.

SAMPLE SOLUTION

There are lots of possibilities here,
I'll cover a few of the critical issues and some
   common solutions and implications.

Issue: bounds checking on arrays
   - automatic resizing on out-of-bounds access means that
     the compiler must insert an array-bounds check for every
     array access, but it also means that from a programmer
     perspective they get no warning if an out-of-bounds access
     is actually made in error
Possible approaches and impact:
   - tough, live with it: the simplest implementation approach
     if we're going with resizing, the most efficient but least
     safe from a programmer perspective
   - automatically generate warnings on out-of-bounds access:
     safer, but undesirable for programmers who specifically want
     to use the automatic resizing as a regular feature
   - provide optional instructions and/or compiler flags which
     generate warnings on out-of-bounds access: good compromise,
     but places higher knowledge burden on programmers

Issue: how much extra space is allocated
Possible approaches and impact:
   - exactly enough to include the newest index:
     this avoids wasting memory by allocating larger-than-needed
     array segments, but if the programmer repeatedly enlarges 
     the array by small increments this results in frequent resizing,
     which may have significant overhead
   - determine and automatically allot a maximal amount of
     extra storage for arrays: if successful, this allows substantial
     growth room for the array, but results in large quantities of
     wasted memory - especially if the program creates numerous arrays
     (e.g. a linked list of structs, each of which includes a tiny array
      as one of the data fields)
   - increase the array size by a fixed fraction of its existing size
     (e.g. double the size, or increase by 50% of current size, etc):
     probably a reasonable compromise, in that it does waste some memory
     space, but the space wasted is limited in fixed proportion to the
     memory space actually required

Issue: how and where is the new storage area selected
Possible approaches and impact:
   - find a new memory segment large enough for the whole array and copy it:
     this means recopying the entire array-to-date on every single resizing,
     which makes the resizing operation itself slow and costly for large arrays.  
     It also means that any pointers into the old array space are now invalid.
   - create a linked list of memory segments, each holding a subset of the array:
     this means that accesses to array elements must now account for which 
     subsection of the array is being accessed, and determine the offset from the
     start of that subsection.  This slows down each array access operation,
     but means that the resizing operation itself is less costly than in the
     previous approach.  Also, since data is never being moved, pointers to
     individual array elements are never rendered invalid.  However, because
     the array elements are no longer stored contiguously in memory this also
     means that simple memory traversals from the start of the array to the end
     are no longer valid.

Issue: how can we resize multidimensional arrays?
Possible approaches and impact:
   - disallow resizing of arrays with more than one dimension:
     the simplest approach, though the least flexible from a programmer viewpoint
   - resize only the dimension whose index is out of bounds:
     simple and effective, but invalidates data structures with strict size ratios
     (e.g. resizing one dimension of what is supposed to be a square matrix)
   - resize all dimensions by the same amount (fixed amount, or proportionately):
     the most versatile, but also the most difficult to code and is most likely
     to waste memory if the other dimensions didn't need to be resized

Question 12:

Suppose an implementation of C++ supports a Deallocate function to free memory as follows:

• Deallocate takes as a parameter a pointer to the start of the relevant heap-dynamic memory section. I.e. you make calls such as Deallocate(ptr);
• Deallocate puts the memory section in a queue to be deallocated, but doesn't actually free the memory space until the next time deallocate is called. I.e. if you called Deallocate(x); Deallocate(y); the space for x isn't genuinely freed until you make the call for y.
• Deallocate does not change the value of the pointer passed to it, thus the pointer could still be used to access the old memory space.

Your task is to write a SafeDeallocate routine, that takes a pointer as a parameter, somehow calls Deallocate in a way that guarantees the specified memory space is genuinely freed before SafeDeallocate completes, and sets the passed pointer to NULL to help safeguard the old memory space.

Next, discuss any drawbacks associated with the use of the SafeDeallocate routine.

SAMPLE SOLUTION

As most folks picked up on you just need to call Deallocate twice.
The only real catches are
   (1) making sure the pointer is passed by-reference
   (2) deciding on what specific pointer to give the second
       call to deallocate.

// one possibility, if Deallocate does something appropriate with
//     a NULL pointer, is as follows:
void SafeDeallocate(void* &ptr)
{
   Deallocate(ptr);
   ptr = NULL;
   Deallocate(ptr);
}

// if you can't trust Deallocate with null pointers,
//    but it will work ok with a pointer that has already
//    been deallocated, then you could try
void SafeDeallocate(void* &ptr)
{
   Deallocate(ptr);
   Deallocate(ptr);
   ptr = NULL;
}

// if you don't trust deallocate with either of those cases,
//    then you could create a pointer to a single char,
//         dynamically allocated,
//         then call free on both
void SafeDeallocate(void* &ptr)
{
   Deallocate(ptr);
   char *tmp = new char;
   Deallocate(tmp);
}

All three methods suffer from efficiency problems,
and without more knowledge about what deallocate does
we could encounter problems with the first two version.

Another issue is that you are deliberately choosing to
override or bypass the normal working of Deallocate - perhaps
there was a sound reason or requirement behind the "queued deallocation"
process.

Yet another issue is that of safety from dangling pointers.
We are explicitly safeguarding the deallocated memory
from access via the passed pointer, but of course we cannot
do so for any other existing pointers to the deallocated memory.
The "SafeDeallocate" might mislead a programmer into thinking
the deallocation is genuinely safe, instead of only partially so.

int GetLargest()
{
   int max = 0;
   int mostrecent = 0;
   do {
      cin >> mostrecent;
      if (mostrecent > max) max = mostrecent;
   } while (mostrecent >= 0);
   return max;
}

For example, typical recursive factorial solutions are often "almost tail recursive", as illustrated in the pseudo-code below:

Factorial(N)
  if (N == 1) return 1;
  else return N*factorial(N-1);

(ii) In an object oriented language, should a derived class be able to make a protected inherited feature hidden? Justify your answer.

(iii) In an object oriented language, should a derived class be able to make an protected inherited feature unprotected? Justify your answer.

(ii) Now suppose in the same try block you also have some code which must be executed only when an exception does not occur - explain where you would need to put this code and why.

(i) Consider the (legal) C program shown below and describe the values of n and q output by the program.

(ii) Discuss the program and what it illustrates about C as a programming language in terms of style, readability, maintainability, and flexibility.

#include <iostream>
using namespace std;
int main() {
   int n;
   cout << "Enter an integer" << endl;
   cin >> 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);
   }
   cout << "n:" << n << ", q:" << q << endl;
   return 0;
}

(i) Compare and contrast the two approaches in terms of efficiency and maintainability.

(ii) Suppose you were designing a programming language that could only support one of the following three features: loops, recursion, or goto statements.

Select which feature should be supported and justify your decision.

#include <iostream>
using namespace std;

void p(int i) { cout << i << endl; }

void fgoto(int l, int h, void (*g)(int))
{
   int x = l;
   L1: 
      if (x > h) goto L2;
      g(x);
      x++;
      goto L1;
   L2: 
      return;
}

void frecurse(int l, int h, void (*g)(int))
{
   if (l > h) return;
   g(l);
   frecurse(l+1, h, g);
}

int main()
{
   fgoto(1, 10, p);
   frecurse(1, 10, p);
   return 0;
}

Describe a way of combining this to implement a lisp-like eval function in C++, and the difficulties/shortcomings in such an approach compared to lisp's eval.