• CLEARLY PRINT YOUR NAME HERE:

• A short lisp/C/C++ syntax sheet will be provided with the exam.
• You have 3 hours to complete the exam (9:00-12:00)
• There are 10 questions on the exam, some with multiple parts.
• Questions are worth 10 marks each, your best 9 answer will be used, for a total of 90 marks.
• Answer directly on the exam paper, using the backs of pages if extra space is required.
• The exam is closed book, closed notes, no calculators, phones, or other electronic aids of any form may be used during the exam.
• Be sure to check your exam to make sure all 10 questions and the lisp/C/C++ syntax sheet are included.

Question	Mark
1. Static and dynamic binding [10 marks]
2. OO and let over lambda [10 marks]
3. Type checking and conversions [10 marks]
4. List implementations [10 marks]
5. Dynamic allocation [10 marks]
6. Macros [10 marks]
7. Lexical and dynamic scope [10 marks]
8. Higher order functions [10 marks]
9. Smart pointers [10 marks]
10. Lisp implementation [10 marks]
Exam Total (best 9) [90 marks]

Question 1: Static and dynamic binding [10]

Do the following for lisp, then again for C++:

For each of the following aspects of the language, identify whether binding takes place dynamically or statically. If it takes place dynamically then also identify whether or not it can subsequently be changed later in the same run. Briefly justify each answer.

1. allocating memory space to local variables
2. applying a #define/defmacro to the source code
3. assigning a value to a local constant

Sample Solution
Lisp:
  (1) dynamic, can't change once set:
      memory allocation for a local takes place during execution,
      but that assigned space isn't altered/reallocated during the
      lifetime of that variable
  (2) static:
      macros are applied BEFORE compilation takes place,
      after which all we have is the revised source code
  (3) tricky:
      common lisp doesn't actually have local constants, just global,
      changes to their values are not permitted directly by the compiler,
         e.g. it will disallow the following:
             (defconstant x 1)
             (setf x 2)
      but we can use the pointer-based implementation of lists to work around this:
             (defconstant x 1)
             (defvar L (list x))
             (setf (car L) 2)
             ; x is now 2!
C++:
   (1) dynamic, can't change once set:
       memory for a local variable is created on the stack when the enclosing
       function is called, and remains allocated (in the same location) until
       the function ends
   (2) same as lisp
   (3) similar to lisp:
       local constants are created on the stack along with local variables,
       and direct changes are prevented by the compiler (like lisp) but we
       can change the contents of local constants through pointers to them

Question 2: OO and let over lambda [10]

In C++ we can overload the constructor for an object, providing a variety of ways to initialize the object.

Provide a lisp example using let-over-lambda to achieve a similar effect, and briefly explain any disadvantages of the let-over-lambda approach compared to the C++ approach.

Sample Solution
; example for a circle constructor,
;    accepts optional parameters for
;       x,y coordinates of centre point
;       r   radius of circle
;    these values are checked/applied just
;       prior to the creation of the dispatcher
;    ignores any additional values passed
(defun circle (&optional (x 0) (y 0) (r 1) &rest ignore)
   (let ((ctrX 0) (ctrY 0) (radius 1))
      (labels
          ( ; any local methods go here, print given as an example
            (print () (format t "(~A,~A):~A~%" ctrX ctrY radius)))

      ; use optional params to set circle fields
      (if (numberp x) (setf ctrX x))
      (if (numberp y) (setf ctrY y))
      (if (and (numberp r) (> r 0)) (setf radius r))

      ; now define/return the dispatcher
      (lambda (cmd .....))))

; sample uses
(defvar C1 (circle))  ; uses defaults for all three
(defvar C2 (circle 5)) ; uses 5 for x, defaults for others
(defvar C3 (circle 1 2 3 4 5)) ; uses x=1, y=2, r=3, ignores others
(defvar C4 (circle "foo" 10) ; uses defaults for x,r, 10 for y
(funcall C1 'print)
(funcall C2 'print)
etc

Disadvantages:
 - the big disadvantage is that no inheritance mechanism is supported
   in this fashion (and thus no dynamic binding of methods either)
 - there is no implicit mechanism for handling destructors, if any
   action was desired beyond simple elimination of the memory space
   then the programmer would have to ensure they specifically make
   the necessary call at the desired time
 - the funcall syntax is a little clumsier than C1.print()
 - readability is better/worse than C++ (depending on your point of view)

Question 3: Type checking and conversions [10]

1. Discuss the key differences in type checking between common lisp and C++.
2. Discuss the key differences in type casting and conversion between common lisp and C++.

Sample Solution

(1) type checking:
       - in C++ type checking takes place at compile time
       - in lisp type checking takes place at run time at
            the point when we try to use the value passed,
         but the programmer also has the ability to perform
            their own run-time type checking, e.g. with
            functions like (listp L), (stringp S), etc
       - this means that run time performance suffers more in lisp,
         as the type checking is being done "live" during execution
         rather than by the compiler at compile time
       - it also means the C++ programmer is warned during compilation
         about type mismatches, rather than at runtime, but has less
         flexibility/control over how to handle data types than does
         the lisp programmer

(2) type casting (programmers explicity requesting a type conversion):
       - in C++ this is done with the syntax (typename)(value), e.g.
            (float)(x)
       - in lisp this is done with the syntax (coerce value typename), e.g.
            (coerce x 'float)

    type conversions:
       - in lisp, since it is dynamically typed, the actual type conversions
         generally take place at the point where a value is actually being
         used in an operation, rather than at the point of assigning it to a
         storage location (until that point the value can simply be stored as
         the most suitable type)
       - otherwise type conversions (whether implicit or as a result of a cast)
         behave similarly in both languages, though lisp can give the appearance
         of supporting a wider range of implicit conversions simply because some
         operators/functions perform their own type checking/conversions
         internally at run time

Question 4: [10] List implementations

The C implementation of common lisp actually uses linked lists/pointers to represent lisp lists, but uses arrays to represent lisp vectors.

Discuss the impact this should have on the decision-making process for lisp programmers who are trying to choose between using lists or vectors in their solution for a particular problem.

Sample Solution

(1) depending on what we plan to do with the data we are storing,
    which form we pick could have a noticable impact on runtime:
     - if a vector is being stored internally as a C-style array then
          accessing elements by position is an O(1) operation
       on the other hand, if lists are implemented linked-list style then
          accessing elements by position in an O(N) operation
     - if we are inserting or removing elements from the front of the
       vector then we need to shuffle all the remaining elements forward
       or backward, O(N), whereas it is a constant time operation with
       the list
     - some other operations involve a tradeoff, e.g. inserting an element
       in the midst of a vector involves shuffling the remaining elements, O(N),
       whereas in a list it can take O(N) time to get to the position but is
       then a constant time operation to actually do the insert
     - since resizing a vector likely involves a create/copy/destroy approach,
       we should think carefully about the choice to use vectors if we expect
       frequent resizing

(2) the choice of format also has an impact on storage requirements
     - the linked list format needs to store the pointers as well as the data,
       whereas the vector (array) format does not
     - the array format requires a contiguous section of memory large enough
       to hold the entire vector, whereas the linked list format does not

Question 5: Dynamic allocation [10]

In lectures we discussed the gnu malloc approach to handling dynamic memory allocation and deallocation in C.

In your own words, summarize the key issues and the approach taken to addressing them.

Sample Solution

***NOTE*** this sample solution is more detailed than I would expect from a student solution

Issues:
   - quickly selecting the "right" chunk to allocate in response
     to a request
   - quickly handling the release of a previously-allocated chunk
   - preventing the fragmentation of memory into a large number
     of tiny chunks
   - supporting quick threaded requests/releases

Approaches:
   (1) structuring both the free and allocated chunks in a manner that
      allows traversals and allows easy consolidation of adjacent free chunks
   (2) establishing a search structure to quickly find the right chunk for a request
   (3) dividing memory into arenas, each governing subsequent requests/releases
       that take place within their region, so different threads can get simultaneous
       requests serviced by dealing with different arenas
   (4) establishing an algorithm to apply to (1) and (2) when requests or
       releases take place

(1) Free chunks are stored with their size at both ends, and pointers to the
    next and previous free chunks in their respective lists, e.g.
      +------+----------+---------+--------------+------+
      | size | back ptr | fwd ptr | ...unused... | size |
      +------+----------+---------+--------------+------+
    Allocated chunks also store their size at each end, along with flags
    to indicate how theiy were allocated, e.g.
      +------+-----+-----------------------------+------+
      | size |flags| ... usable data space ...   | size |
      +------+-----+-----------------------------+------+
    The two formats allow traversals forward and backward through either the
    set of all memory chunks or the set of free memory chunks, and allow the
    identification of consecutive free chunks so they can be consolidated.

(2) An extra data structure is used to keep track of the start of:
      - a cache of free memory for each thread
      - the "fastbin" lists of small chunks: e.g. one list for the 32-byte free
        chunks, one for the 64-byte free chunks, etc
      - a search tree structure for lists of larger specific sizes
      - a list of unsorted chunks (for newly released items)
      - really big requests are handled through mmap requests direct to the os

(3) Initially all of (heap) memory might be treated as a single arena,
    but as the number of overlapping requests from different threads increases
    it can be subdivided into ranges, with independent processes assigned control
    of each range (arena) for all subsequent requests/releases within that range

(4) allocation algorithm:
       see if it can be exactly satisfied from the thread cache
       if it's a big request use mmap from the os
       otheriwse if it is small enough check the fastbin for the right fit
       otherwise move all the fastbin stuff to unsorted,
          go through the unsorted chunks and consolidate them,
          inserting them into the search tree
       find the appropriate chunk in the search tree,
          if it is too large then break off the extra
             and treat like a release

    release algorithm:
       store it in the thread cache if there is space
       otherwise, if it is small enough, place it in the right fastbin
       otherwise if it was mmapped then unmap it
       see if it is adjacent to another free chunk, if so consolidate
       place the chunk in the unsorted list

Question 6: [10] Macros

1. Briefly summarize the advantages of C macros over lisp macros.
2. Briefly summarize the advantages of lisp macros over C++ templates.
3. Briefly summarize the advantages of C++ templates over C macros.

Sample Solution

(1) C macros are perhaps simpler to apply and to implement than
    lisp macros, since they are simply text/pattern substitution.

    The conditional aspects of C macros (ifdef/ifndef etc) provide
    a control that is not (or at least not obviously) given through
    lisp macros.

(2) lisp macros are more flexible, and easier to apply to a wider
    range of situations than C++ templates - including better/more
    general support for recursion, identifier generation through gensym,
    and giving fully programmable rewrites of the source code, rather
    than just basic type substitution.

(3) C++ templates are more powerful and flexible than C #define macros,
    in that they are easily applied to more generalized patterns (classes,
    functions, methods) than C macros -- essentially saying "in the next
    templated item, substitute the programmer-provided type T for pattern Y
    throughout.  They also provide simpler/clearer recursive potential.

Question 7: Lexical and dynamic scope [10]

In your own words, describe the difference between lexical and dynamic scoping, and explain two different approaches to implementing dynamic scoping.

Sample Solution
Lexical Scope:

   The variables visible/accessible at any point in a program are
   determined by the set of nested scopes enclosing the current point,
   we can access variables previously declared in any of those enclosing
   scopes.

   Example:
      Suppose we have a global variable w,
      and we have a function f, with a local variable x,
      inside f we have a loop with a local variable y,
      inside the loop we have a block with a local variable z
       -- inside that block we can access any of the four variables, w, x, y, z

    Which variables are accessible can be precisely determined at compile time
    from the nesting structure of the code.

Dynamic Scope:

   In addition to being able to access the variables within the
   current lexical scope(s), within a function we are also able to
   access the variables declared within the preceeding call chain.

   For example, if function f calls function g, which calls function h,
   then inside function h we can also access any variables declared in
   functions g or f.

   Which specific variables are visible at any point in the code may
   depend on the sequence of function calls that brought us to that point,
   and cannot necessarily be predicted at compile time.

Some implementation approaches:

   (1) For each variable name in use within the program,
       maintain a stack of the values associated with that name.

       When a variable is created, e.g. when you enter the block in
       which it is declared, push the variable's value on the stack.
       When the variable is destroyed (e.g. when you finally leave its
       block) pop the variable off the stack.

       The "current" version of the variable will always be the one
       on the top of the stack.

   (2) Maintain a list of variable names and their values (possibly also
       their types), sorted by order of nesting, and when you call or return
       from a function, or when you enter/leave a block, pass the (updated)
       list as an implicit parameter.

   (3) Maintain a global table of scopes, the variables declared within them,
       and their current values (again, possibly also their types).

       Maintain a list of the current nesting of scopes, updating it whenever
       you call/return from a function or enter/leave a block.

       Whenever a variable is referred to, go through your list of scopes to
       identify the most local one that contains the desired variable name.

Question 8: Higher order functions [10]

Give an example of a higher order function in lisp, and outline a way to get similar behaviour using function pointers and templated functions in C++.

Explain any drawbacks with your C++ solution.

Sample Solution

Lisp's sort function takes a comparison function as a parameter:

    (sort '(4 2 1 5 10) '<)

We came up with something very similar, ssort, in lab 10:

    template <class T>
    void ssort(T arr[], int size, bool (*compare)(T x, T y))
    {
        ...
            if ((*compare)(arr[j], min) ... // using the passed function
        ...
    }

Disadvantages:
    - the function pointer syntax needed to create our higher order
      function is more complex/error prone than lisp's built-in support

    - due to C++'s need for compile-time type checking, the function
      passed as a parameter must exactly match the profile given by the
      function pointer, whereas in lisp we can pass any function at all

    - we need to either instantiate versions of the templated function to
      match every compare profile supported, or we must place the template
      itself in the .h file to be included by every program that plans on using
      the template (no such instantiation is required in lisp)

Question 9: Smart pointers [10]

For any two of the four pointer problems listed below, give a short C/C++ code snippet that illustrates the problem and a short snippet of code using smart pointers to solve/avoid the problem:

1. dangling pointers
2. null pointers
3. memory leaks
4. wild pointers

Sample Solution

for each of the four problem examples below
    I'm assuming there exists a class named Object
    with a method named print

dangling pointer:
    Object *p = new Object;
    delete p;
    p->print();

null pointer:
    Object *p = null;
    p->print();

memory leak:
    Object *p = new Object[5];
    p = new Object[10];

wild pointer:
    Object *p;
    p->print();

smart pointers:

   // assuming we have the following declared:
   std::tr1::shared_ptr<Object> p;

   // wild pointers caught:
   p->print();

   // null pointers caught:
   p.reset();
   p->print();

   // dangling pointers caught:
   p.reset(new Object);
   p.reset();
   p->print();

   // memory leaks caught:
   p.reset(new Object);
   p.reset(new Object); // inaccessible original object deleted

Question 10: Lisp implementation [10]

On the following page are four snippets of code taken from cmpinclude.h in the C implementation of gnu common lisp (gcl).

Explain which of the four you find the most surprising and why - in terms of what the code snippet reveals about the implementation of key lisp function(s) and/or data types.

Sample Solution

Which of the four you choose as "most surprising" is of course up to you,
but here are some of my thoughts:

(1) I actually found this the least surprising, given that we already
    know lisp handles lists as a linked lists, with separate portions for
    the head element and tail list.  It does demonstrate the idea that
    there is a generic underlying "object" type to represent any possible
    form of lisp data value.

(2) This is interesting in that it shows the implementation of the generic list
    "object" data type as a union of all possible specific data types, and revealing
    that there is a unique struct associated with the implementation of each of them.

(3) Given part (2) above I would regard (3) as less surprising - giving a named
    enumeration of the different supporting types.  It does provide us with a
    mapping of the different lisp numeric types to the underlying C types.

(4) This gives us a clearer understanding of how exactly lisp is applying
    its different primitive operators (~ | ^ / % etc) as combinations of the
    underlying C operators.  This also shows why/where operations crash when
    passed invalid data types.

// (1) the handling of cons/car/cdr
#define MMcons(x,y) make_cons((x),(y))
#define MMcar(x) (x)->c.c_car
#define MMcdr(x) (x)->c.c_cdr
#define CMPcar(x) (x)->c.c_car
#define CMPcdr(x) (x)->c.c_cdr
#define CMPcaar(x) (x)->c.c_car->c.c_car
#define CMPcadr(x) (x)->c.c_cdr->c.c_car
#define CMPcdar(x) (x)->c.c_car->c.c_cdr
#define CMPcddr(x) (x)->c.c_cdr->c.c_cdr
struct cons {
  object c_cdr;
  object c_car;
};
object make_cons(object,object);
object car(object);
object cdr(object);
object caar(object);
object cadr(object);
object cdar(object);
object cddr(object);

// (2) the definition of objects
typedef union lispunion *object;
union lispunion {
  struct fixnum_struct FIX;
  struct bignum big;
  struct ratio rat;
  struct shortfloat_struct SF;
  struct longfloat_struct LF;
  struct ocomplex cmp;
  struct character ch;
  struct symbol s;
  struct package p;
  struct cons c;
  struct hashtable ht;
  struct array a;
  struct vector v;
  struct string st;
  struct ustring ust;
  struct bitvector bv;
  struct structure str;
  struct stream sm;
  struct random rnd;
  struct readtable rt;
  struct pathname pn;
  struct cfun cf;
  struct cclosure cc;
  struct closure cl;
  struct sfun sfn;
  struct vfun vfn;
  struct cfdata cfd;
  struct spice spc;
  struct dummy d;
  struct fstpw fstp;
  struct ff ff;
  struct mark md;
  struct sgcm smd;
  struct typew td;
  fixnum fw;
  void *vw;
  struct fixarray fixa;
  struct sfarray sfa;
  struct lfarray lfa;
};

// (3) the handling of data types
enum type {
  t_cons, t_start = 0, t_fixnum, t_bignum,
  t_ratio, t_shortfloat, t_longfloat, t_complex,
  t_stream, t_pathname, t_string, t_bitvector,
  t_vector, t_array, t_hashtable, t_structure,
  t_character, t_symbol, t_package, t_random,
  t_readtable, t_cfun, t_cclosure, t_sfun,
  t_gfun, t_vfun, t_afun, t_closure,
  t_cfdata, t_spice, t_contiguous, t_end=t_contiguous,
  t_relocatable, t_other
};
typedef int bool;
typedef long long lfixnum;
typedef unsigned long long ulfixnum;
typedef long fixnum;
typedef unsigned long ufixnum;
typedef float shortfloat;
typedef double longfloat;

// (4) the handling of some operations as inline functions
inline fixnum fixnum_boole(fixnum op,fixnum x,fixnum y) {
  switch(op) {
  case 0: return 0;
  case 017: return -1;
  case 03: return x;
  case 05: return y;
  case 014: return ~x;
  case 012: return ~y;
  case 01: return x&y;
  case 07: return x|y;
  case 06: return x^y;
  case 011: return ~(x^y);
  case 016: return ~(x&y);
  case 010: return ~(x|y);
  case 04:return ~x&y;
  case 02:return x&~y;
  case 015: return ~x|y;
  case 013: return x|~y;
  }
  return 0;
}

inline fixnum fixnum_div(fixnum x,fixnum y,fixnum d) {
  fixnum z=x/y;
  if (d && x!=y*z && (x*d>0 ? y>0 : y<0))
    z+=d;
  return z;
}

inline fixnum fixnum_rem(fixnum x,fixnum y,fixnum d) {
  fixnum z=x%y;
  if (d && z && (x*d>0 ? y>0 : y<0))
    z+=y;
  return z;
}

inline fixnum fixnum_rshft(fixnum x,fixnum y) {
  return y>=sizeof(x)*8 ? (x<0 ? -1 : 0) : x>>y;
}

inline object fixnum_lcm(fixnum x,fixnum y) {
  fixnum g=fixnum_gcd(x,y);
  return g ? safe_mul_abs(x,fixnum_div(y,g,0)) : make_fixnum(0);
}