• CLEARLY PRINT YOUR NAME HERE:
• You have 3 hours to complete the exam (9:00-12:00)
• There are 9 questions on the exam, worth 12 marks each.
• Your best 8 answers will be used, for a total of 96 marks.
  Your marks from questions 1, 2, and 3 will replace your midterm mark if they are higher
• Answer directly on the exam paper, using the backs of pages if extra space is required.
• The exam is open book and open notes, but no calculators, phones, or other electronic aids of any form may be used during the exam.
• Many of the questions are quite open-ended, the expectation is that students spend approximately 20 minutes per question.
• Be sure to check your exam to make sure all 9 questions are present.

Question	Mark
1. Macros in Lisp and C++ [12 marks]
2. Higher order functions and closure in Lisp and C++ [12 marks]
3. Functions and Parameter passing in Lisp and C++ [12 marks]
4. Static and dynamic binding of variable attributes [12 marks]
5. Data types, operators, and expressions [12 marks]
6. Function pointers and smart pointers [12 marks]
7. Blocks, repetition, and selection [12 marks]
8. Data types and conversions [12 marks]
9. Compiler optimization [12 marks]
Exam Total [96 marks]

Question 1: Macros in Lisp and C++ [12]

Part I: A lisp macro is shown below.

Provide a C preprocessor macro that provides comparable functionality, and discuss any disadvantages in the macro you provided compared to the lisp macro.

; usage: (divides X Y), e.g. (divides 4 12)
;     the macro call is replaced with a cond expression
;     that evaluates to true iff X and Y are integer values
;     and the remainder after dividing Y by X is 0
(defmacro divides (denominator numerator)
   `(cond
       ((not (integerp ,denominator)) nil)
       ((not (integerp ,numerator)) nil)
       ((= ,denominator 0) nil)
       ((= (mod ,numerator ,denominator) 0) t)
       (t nil)))

SAMPLE SOLUTION // we need divides(X, Y) to be replaced by an expression // that evalutes to 0 or 1 // Thus this *cannot* be a code block (enclosed in { }) // nor can it be a series of if/else calls with returns // All the brackets are necessary to ensure correct precedence // of operators should D or N be expressions // Note also that true/false are not defined in C, // hence the use of 0 and 1 // // Disadvantages: // This does not do type checking to ensure D and N are // of type integer, and if D is an expression with // side effects then the effects are applied twice. // It also does not distinguish between false because // D is 0 and false and false because D does not divide N. #define divides(D, N) (((D) != 0) && (((N) % (D)) == 0))

Part II: A C preprocessor macro is shown below.

Provide a lisp macro that provides comparable functionality, and discuss any advantages of the lisp macro over the C macro.

// useage: swap(Vartype, Var1, Var2), e.g. swap(int, X, Y)
//    assuming Var1 and Var2 are variables of type Vartype,
//    this replaces the swap call with instructions to exchange
//    the values of Var1 and Var2
#define swap(Vartype, Var1, Var2) \
   { Vartype Var1##Var2 = Var1; Var1 = Var2; Var2 = Var1##Var2; }

SAMPLE SOLUTION (defmacro swap (X Y) (let ((tmp (gensym))) `(let ((,tmp ,X)) (if (and (symbolp ,X) (symbolp ,Y)) (block DOSWAP (setf ,X ,Y) (setf ,Y ,tmp)))))) ; advantages: ; - no need for type checking ; - no possibility of repeated side effects ; - gensym guarantees a unique variable name, unlike ##

Question 2: Higher order functions and closure in Lisp and C++ [12]

In lab 4 we considered how to use closure in lisp, having one function write and return customized variants of another function. (Lab 4 was the one in which we created a drawBoxBuilder function, that built and returned a function whose role was to draw boxes of specific sizes/shapes.)

Compare the use of closure in lisp to the use of templated functions in C++, where it is the compiler's role to create the "customized" versions of the templated function.

SAMPLE SOLUTION In C++ templates, the customization is limited to straight pattern replacement, where the pattern and its replacement are both data types. The instantiation choices must also be known at the time the file containing the template is compiled. In Lisp closures, the style of function built is based on the parameters supplied, and has endless composition possibilities - being able to return totally different/unrelated functions. Note that (unless explicitly done later) the function returned by the closure is not compiled, and therefor not as 'fast' at runtime as functions statically built and compiled.

Question 3: Functions and Parameter passing in Lisp and C++ [12]

Lisp's handling of variable numbers of function parameters is far more flexible than that of the C/C++ varargs approach.

For the average function described below, provide one lisp implementation (using &rest) and one C/C++ implementation (using vararg).

average: given 1 or more floating point data values as parameters,
   average computes and returns the mean of those values
   (the sum of all the values divided by the number of values)

SAMPLE SOLUTION // assumes inclusion of stdarg double average(int numArgs, ...) { // error checking for valid number of arguments if (numArgs < 1) return 0; // set up the argument list va_list argList; va_start(argList, numArgs); // take the sum of all arguments double sum = 0; for (int i = 0; i < numArgs; i++) { double arg = va_arg(argList, double); sum += arg; } // clean up the arg list va_end(argList); // return the average return (sum / numArgs); } (defun average(&rest args) (let ((numArgs (length args)) (total (apply '+ args))) (cond ((< numArgs 1) nil) (t (/ total numArgs)))))

Question 4: Static and dynamic binding of variable attributes [12]

In lisp, we found it is possible to check at run time if a variable name (symbol) is currently bound to a value (using boundp), and we learned it is also possible to define additional properties/value pairs to associate with the symbol.

Propose a way this could be implemented in the C language, and discuss both the potential uses and drawbacks associated with your proposed implementation of the feature.

SAMPLE SOLUTION The compiler currently associates each variable name in the program with a memory location or register, and when generating code it substitutes the location wherever the name is used, thus the names themselves are totally unknown at runtime. However, since there is no dynamic scoping to worry about in C, wherever an existence check appears in the code the compiler already has an implicit check (i.e. compile time undeclared variable error). The issue of runtime binding of properties to a variable name is more complex. To see/update at runtime the properties associated with a variable name it would be necessary to maintain a searchable collection of variable names and current property lists, or to augment each variable with an extra pointer to its associated property list. One possibility would be to use a linked list of properties, with each property represented as a pair of strings (key and value). Thus the collection (at least in a simplistic implementation) might look like struct KVPair { string key, value; KVPair *next; }; struct Symbol { string unique_name; // some kind of unique identifier for the var KVPair *plist; // currently associated properties }; The advantages would be the abilities to perform runtime checks for variable property lists, the disadvantage would be the extra runtime overhead to maintain the searchable collection. Possible uses would include enhanced error checking - e.g. having properties to indicate variable state (e.g. "isInitialized", "isDeallocated" etc).

Question 5: Data types, operators, and expressions [12]

The ++ operator has relatively intuitive meaning for numeric values and chars, but less so for pointers.

In the following example, the address stored in ptr goes up by 4 when we apply the ++ operator:

int arr[6] = { 0, 0, 0, 0, 0, 0 };
int *ptr = arr;
ptr++;

Similarly, ++ makes the address go up by 2 for arrays of shorts, and by 1 for arrays of chars.

The address of ptr goes up by 20 if we use the following:

int arr[6] = { 0, 0, 0, 0, 0, 0 };
int *ptr = arr;
ptr += 5;

int arr[6] = { 0, 0, 0, 0, 0, 0 };
int* ptr = arr;
unsigned long p = ptr;
p++;
ptr = p;

SAMPLE SOLUTION The pointer math operators are based on the assumption that the underlying data is stored in an array form, i.e. int *p means that p points at one of a sequence of ints. If we apply pointer math to increment a pointer then the assumption is that we want to iterate through the sequence of values, i.e. p++ means adjust p to point to the next int, not simply the next byte in memory. Thus the implementation of p++ is to add the size of an int to the address currently stored in p - i.e. add 4 if p points to an int, add 8 if it points to a long, add 2 if it points to a short, add 1 if it points to a char, etc.

Question 6: Function pointers and smart pointers [12]

In lab 10 we used templated function pointers to try to emulate a higher order function, reduce, in C++. The profile in the sample solution looked like this:

template <class T>
T reduce(T (*f)(T,T), T arr[], int size);

In lab 11, on the other hand, we used templated smart pointers to try to share access to dynamically allocated objects. The syntax for creating an array of smart pointers for objects of class C looked like

std::tr1::shared_ptr<C> arr[arrSize];

Suppose we wanted to instantiate reduce for a function f whose parameters were shared_ptrs to objects of type C.

1. Show what the instantiation syntax would look like.
2. Either discuss a cleaner syntax that could be used to improve this (i.e. syntactic changes to C++) or discuss why you feel a syntax revision is be unnecessary.

SAMPLE SOLUTION (i) to instantiate reduce we would need to replace each T with std::tr1::shared_ptr<C> in the statement: template T reduce<T>(T (*f)(T,T), T arr[], int size); needless to say, this is an ugly instantiation statement: template std::tr1::shared_ptr<C> reduce<std::tr1::shared_ptr<C>> (std::tr1::shared_ptr<C> (*f)(std::tr1::shared_ptr<C>,std::tr1::shared_ptr<C>), std::tr1::shared_ptr<C> arr[], int size); (ii) it would be nice if we could instead use an instruction like instantiate(T, std::tr1::shared_ptr<C>) template T reduce<T>(T (*f)(T,T), T arr[], int size); and then rely on the compiler to perform the substitutions for T without the programmer needing to worry about typos in the resulting mess While not a truly necessary addition to the language, it may be a handy one. The flip side is, typedefs are already provided, so if one were to typedef the std::tr1::shared_ptr<C> then the appearance of the instantiation would be greatly simplified and the need for the extra instantiation syntax would be eliminated.

Question 7: Blocks, repetition, and selection [12]

Many languages provide a "foreach" loop, that allows one to iterate through the elements of an array, but C and C++ do not.

Suppose C supported a version of foreach with syntax like this:

foreach (arrayName, element) {
   ... do something with the current element ...
}

(ii) Is this a feature that should be added to C? Discuss why or why not.

SAMPLE SOLUTION (i) The basic idea would be simple if the compiler knew the array size, e.g. (here assuming the compiler knows the array size is N) foreach (someArray, elementName) { ... do something with elementName ... } is replaced by the compiler with for (int elementName = 0; elementName < N; elementName++) { ... do something with someArray[elementName] ... } Unfortunately, since pointers and arrays are treated nearly interchangably, the compiler would need to insert a mechanism for recording where the end of an array is - either storing its size or storing some kind of termination value (like with the '\0' for char arrays). For example, suppose we did something like ptr = &(arr[i]); and then used foreach on ptr, what would the compiler do? One thing not clear from the example is how it would handle multi-dimensional arrays, this would need to be clarified. (ii) The need to add this to the language is debatable. While it is a nice extra, the programmer can already achieve the desired effect with the simple for loop mentioned above, though it does dump the problem of tracking the array size or endpoint in the lap of the programmer.

Question 8: Data types and conversions [12]

C does not support a generic list type where the individual elements can be of varying data types. It does, however, support a union type.

A union type specifies a list of allowable types, e.g. the union below permits an item to have type int, char, float, or char*:

union Q8Type {
   int i;
   char c;
   float f;
   char* cptr;
}

To assign or look up values in the variable we use the field name to specify what type of data we think the variable should currently store, e.g.

   myVar.i = 13;   // store integer 13 in myVar
   myVar.f = 3.5;  // overwrite myVar with float 3.5
   myVar.c = 'x';  // overwrite myVar with char 'x'

Discuss how unions and arrays could be combined to create list-like functionality in C, and the disadvantages of this approach compared with lisp lists.

SAMPLE SOLUTION One possibility would be to use a union to create a data type that could hold the data for an individual list element, e.g. union ListData { int i; char c; float f; char* cptr; }; An enumerated type could then be used to list the supported element types: enum ListType { INT, FLOAT, CHAR, CHARPTR }; A list element would then be composed of two parts, data and type, e.g. struct ListElement { ListData currData; ListType currType; }; A list could then be stored as an array of ListElements. Or perhaps a ListElement pointer, *next, could be added to the ListElement struct so we could support linked lists of ListElements. While this would allow us to pass variably-typed lists around as data, it does rely on the programmer correctly setting/using the ListElement type, and is limited to the collection of types defined in the union+enum. If the largest data type supported is substantially larger than the data type actually in use at run time, then there can also be significant waste of memory space.

Question 9: Compiler optimization [12]

1. Given the C code below for a compound boolean expression and the resulting assembly language produced by the compiler, does the compiler use short circuiting? Justify your answer.

   int f(int w, int x, int y, int z) { if ((w < x) && (x < y) && (y < z)) return 1; else return 0; }

   .globl f .type f, @function f: pushq %rbp movq %rsp, %rbp movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl %edx, -12(%rbp) movl %ecx, -16(%rbp) movl -4(%rbp), %eax cmpl -8(%rbp), %eax jge .L2 movl -8(%rbp), %eax cmpl -12(%rbp), %eax jge .L2 movl -12(%rbp), %eax cmpl -16(%rbp), %eax jge .L2 movl $1, %eax jmp .L3 .L2: movl $0, %eax .L3: popq %rbp ret

   SAMPLE SOLUTION We can see that variables w through z are being stored at offsets 4-16 from the base pointer (rbp), and that following the comparison of w and x, if the the comparison fails the control immediately jumps to .L2 to set up the return. This means that the subsequence comparisons are not evaluated, i.e. it IS using short circuiting.

2. Given the C code below for a tail recursive function and a call to it, and the resulting assembly language produced by the compiler, does the compiler optimize tail recursive calls? Justify your answer.

   int f(int index, int final, int total) { if (index > final) { return total; } return f(index+1, final, total+index); }

   .globl f .type f, @function f: pushq %rbp movq %rsp, %rbp subq $16, %rsp movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl %edx, -12(%rbp) movl -4(%rbp), %eax cmpl -8(%rbp), %eax jle .L2 movl -12(%rbp), %eax jmp .L3 .L2: movl -12(%rbp), %edx movl -4(%rbp), %eax addl %eax, %edx movl -4(%rbp), %eax leal 1(%rax), %ecx movl -8(%rbp), %eax movl %eax, %esi movl %ecx, %edi call f .L3: leave ret

   SAMPLE SOLUTION Optimization of tail recursion involves either replacing the recursive calls with a loop, or at least ensuring that we reuse the current frame's stack space for the recursive call. In this case we can see from the "call f" instruction that the recursive calls are still in place, and we can see it uses the standard calling process of putting the parameters into the registers before the call and pushing them onto the stack in the callee, so this does NOT optimize tail recursion.

3. Given the C program below that defines and uses a struct, and the output produced when the program runs, does the compiler optimize the struct layout to save space? Justify your answer.

   #include <stdio.h> struct Data { char C0; char C1; long L2; char C3; int I4; long L5; char C6; long L7; char C8; char C9; }; int main() { struct Data D = { 'a', 1, 'b', 2, 3, 'c', 4 }; printf("The size of a char is %d bytes\n", sizeof(char)); printf("The size of an int is %d bytes\n", sizeof(int)); printf("The size of a long is %d bytes\n", sizeof(long)); printf("The address of D is %p\n", &D); printf(" field C0 address is: %p\n", &(D.C0)); printf(" field C1 address is: %p\n", &(D.C1)); printf(" field L2 address is: %p\n", &(D.L2)); printf(" field C3 address is: %p\n", &(D.C3)); printf(" field I4 address is: %p\n", &(D.I4)); printf(" field L5 address is: %p\n", &(D.L5)); printf(" field C6 address is: %p\n", &(D.C6)); printf(" field L7 address is: %p\n", &(D.L7)); printf(" field C8 address is: %p\n", &(D.C8)); printf(" field C9 address is: %p\n", &(D.C9)); return 0; }

   The size of a char is 1 bytes The size of an int is 4 bytes The size of a long is 8 bytes The address of D is 0x7ffe06ef42f0 field C0 address is: 0x7ffe06ef42f0 field C1 address is: 0x7ffe06ef42f1 field L2 address is: 0x7ffe06ef42f8 field C3 address is: 0x7ffe06ef4300 field I4 address is: 0x7ffe06ef4304 field L5 address is: 0x7ffe06ef4308 field C6 address is: 0x7ffe06ef4310 field L7 address is: 0x7ffe06ef4318 field C8 address is: 0x7ffe06ef4320 field C9 address is: 0x7ffe06ef4321

   SAMPLE SOLUTION Examining the allocation of values to memory we can see that if we treat C0's address as 0, the offsets to the remaining fields are (showing in decimal rather than hex): C0: 0 (C0 has size 1) C1: 1 (C1 has size 1) .... 6 unused bytes ... L2: 8 (L2 has size 8) C3: 16 (C3 has size 1) .... 3 unused bytes ... I4: 20 (I4 has size 4) L5: 24 (L5 has size 8) C6: 32 (C6 has size 1) .... 7 unused bytes ... L7: 40 (L7 has size 8) C8: 48 (C8 has size 1) C9: 49 (C9 has size 1) Thus we see the fields are stored in order, and that the compiler is inserting padding between fields where necessary to ensure the alignment boundaries are maintained, i.e. the compiler is NOT rearranging the fields to optimize storage.