Assignment 8
Due 10/26/04 12:30 p.m.
(Must be done with your group)

1. [skills 15.1] Write an integer linked list abstract data type in either C++ or Java.   Your linked list implementation needs to support only these two operations: addFirst which takes an integer argument and adds a new node with that integer value to the head the linked list; and removeFirst which removes the head of the linked list and returns the removed integer.  Pay attention to what parts of your implementation are public and what parts are private.  Discuss why your implementation is an abstract data type. Be sure to test your code with a C++ or Java compiler before you submit it.
2. [skill 15.2] Convert the linked list ADT in the previous question to be generic so that it works on arguments of any type.  Demonstrate how you will use your generic class.
3. [skills 14.1 and 14.2] Write a routine in C++ that takes an array, the length of the array, and an element and returns the position of the element in the array.  For example, given the array with values [2,4,6,8] and element 6, the routine should return 2 (since counting from 0, 6 occurs at position 2 in the array).  Your routine should use templates to enable your routine to be reusable for different element types.  Be sure to test your code with a C++ compiler before you submit it.
4. [skill 14.3] Give a concrete example where you feel that parametric polymorphism is more suitable than inclusion polymorphism.  Give a concrete example where you feel that inclusion polymorphism is more suitable than parametric polymorphism.  Justify your answers.
5. [skill 14.4] Write a generic "greater-than" function that (a) takes two objects as arguments, each of which has a "value" method which returns an integer; and (b) returns the argument whose "value" method returns the larger integer.  Your generic function should constrain its type argument so that types without "value" method cannot be used.  Note that C++ does not support constraints on type parameters.  Java will in the next major release.
6. [synthesis] This question will touch on most of the concepts that we have covered so far (notable omissions ADT and generics) and thus it may be a particularly good one to use in your preparation of the midterm.  For this assignment, I will not limit the number of attempts to the PL-Detective.  Use as many as you want as long as you use the link given below.

   In this question you will design the full semantics of the MYSTERY language.  Use this link to submit programs to the PL-Detective.  As part of this question you will need to pick semantics for each dimension  provided by the PL-Detective (e.g., scoping).  The PL-Detective link given above has a link to a web page which describes all the options in detail.

   For each of your choices (e.g., scoping) you must justify your choice using arguments based on the characteristics in Section 1.3 of text.  We will grade you based on the quality of your arguments and to the extent you have thought about how language features interact (e.g., some of the choices in parameter-passing and type-passability may interact with each other).  More specifically, we will see if your arguments (i) provide good and complete justification for your choices; and (ii) demonstrate that you understand the implications of your choices (e.g., if a given combination of choices requires many things to be checked at run time, your discussion should point that out).

   You should assume that MYSTERY uses deep binding (page 382).  If you have other questions about  MYSTERY's fixed semantics (e.g., does MYSTERY use deep or shallow binding) you should figure these out by probing the system (much as you have been doing in the earlier assignments). 

   It is worth remembering that there is no single "perfect" language: if there was such a language then there would be no need for any other language.  In other words, there is no single "right" answer that I'm looking for: We are looking for evidence that you understand the concepts that we have covered so far, have thought about their interactions, and can provide good arguments to justify your choices.

   Extra credit: The menu options in the PL-Detective enable you to pick between more than a thousand different semantics.  Thus, we won't be surprised if some combinations do not behave as expected (bugs!).  If you find any bugs in this exploration please record it in your submission and also indicate why you believe you have found a bug.  You will receive 20% of the points of this question for each correct bug report! Maximum extra credit points: 100% of the points for this question (i.e., five successful bug reports).