As with all assignments, you must submit this assignment via email to the TA.
The first three questions use the PL-Detective. You will need to refer to Mystery grammar to answer these questions. The most important part of these questions is not the final answer (e.g., the type equality mechanism) but the reasoning that led to the answer. Thus, don't leave the write up to the last minute! Also since the number of attempts you can submit to the PL-Detective (e.g., number of PRINTs that you can execute) is limited, it is worth discussing each submission to the PL-Detective with your group. The limit is set high enough that you can waste about half of the attempts and still get the full score. When you submit a program to the PL-Detective, it tells you how many programs you have submitted without syntax errors so far: note that this is not directly correlated with the limit (for example since the limit is often based on executed PRINT and one of your submissions may not do any PRINT).
Note that the PL-Detective link for each question is different. You must use the appropriate link for each question.
The textbook defines four kinds of storage bindings: static variables, stack-dynamic variables, explicit heap-dynamic variables, and implicit heap-dynamic variables. Of these categories, we will consider only the first three kinds in this question (i.e., ignore "implicit heap-dynamic variables).
Mystery allows programs to declare variables associated with any block (delimited by BEGIN...END). However, declaring variables is just a matter of syntax. The kind of variables that Mystery actually supports (i.e., the semantics) is actually a mystery. In this assignment you will put on your detective hat and try to figure out what kinds of variables Mystery supports. To accomplish this you will submit programs to the PL-Detective, observe any outputs or errors, and make inferences. Based on the output you receive, you may continue the interrogation by submitting another program or decide that you have solved the mystery.
Based on an inspection of its syntax, do you believe that Mystery supports explicit heap-dynamic variables? Explain and justify your answer.
[Skill 4.3] Determine and describe the storage bindings of the variables associated with blocks in Mystery. Use this link to access the PL-Detective. You can use upto a total of four executed PRINT commands in your interrogation (e.g., if you submit two programs, the total number of values the two programs print out combined should not exceed four). Note that programs with syntax errors will not count towards your total since a program with a syntax error will not execute PRINT. You will lose 5% of the points for this question for each additional PRINT that you execute. The PL-Detective keeps track of all programs ever submitted by your group. (Hint: your answer to part (i) should help eliminate some possibilities for part (ii)).
Give the evidence and your reasoning based on which you arrived at your conclusions. The evidence takes the form of programs you submitted and the output you received. The reasoning takes the form of text that describes in detail what conclusions you drew from each program-output pair.
We have studied two type equality mechanisms: name type equality and structure type equality. In this exercise, you will figure out the type equality mechanism used by mystery. As with the previous exercise, you will accomplish this by submitting programs to the PL-Detective and observing the results. Use this link to access the PL-Detective.
For the purpose of this assignment you should assume that an assignment, lhs := rhs, is legal only if the type of lhs and rhs are equal. Assume that the type of a constant number (e.g., 5) is INTEGER.
In this question ignore TYPE declarations in mystery (TYPE declarations are similar to typedef in C and C++. For example, TYPE T = INTEGER in mystery creates a new type name T for the type INTEGER. This declaration is similar to typedef int T in C/C++).
[Skill 5.4] Determine and describe how mystery's defines type equality for ARRAY, PROCEDURE, and subrange types. Your description should be precise and complete enough that a reader can take any two types (where both are array types or procedure types or subrange types) in mystery and determine whether or not they are equal. You may submit up to 8 programs to the PL-Detective. You will lose 5% of the points for this question for each additional program that you use. Submitted programs that fail due to syntax errors (note: type errors are not syntax errors) do not count in your total.
Hint: The issue of whether two types are name or structurally equal comes up only when they are not obviously different. For example, the subrange types [0 TO 10] and [5 TO 20] are obviously different and thus you do not need to to submit a program to the PL-Detective to determine if they are equal or not.
Present an argument for your answer to the previous part. Your argument should include the evidence (programs you submitted to the PL-Detective and the output) along with a carefully reasoned argument explaining how your answer to (i) is justified by your evidence.
[Skills 5.2 and 1.1] Give one point in favor of and one point against mystery's type equality mechanism (which you just discovered). Explain your point referring to the characteristics in Table 1.1 in text.
In this question you will determine how mystery's TYPE declarations affect type equality. In other words, after TYPE T = <some type> are T and <some type> equal? Use this link to submit programs to the PL-Detective.
[Skill 5.4] Determine and describe how mystery's TYPE declarations affect type equality. Write this as if you are writing a language definition: i.e., your answer to this question combined with your answer to question 2 should allow a reader to determine the equality of any two types in mystery's including ones that use type names declared using TYPE. You may submit up to 2 programs to the PL-Detective in your investigation. Each additional program is charged 5% of the points for this question. Submitted programs that fail due to syntax errors (note: type errors are not syntax errors) do not count in your total.
Present an argument for your answer to the previous part. Your argument should include the evidence (programs you submitted to the PL-Detective and the output) along with a carefully reasoned argument explaining how your answer to (i) is justified by your evidence.
[Skills 5.2 and 1.1] Give one point in favor of and one point against the semantics that you just discovered. Explain your point referring to the characteristics in Table 1.1 in text.
[Skill 4.2] Different storage bindings are useful in different situations. This is why most language support more than one storage binding. For example, global variables in C use static, local variables (that are not explicitly marked "static") use stack dynamic, and the variables allocated using "malloc" use explicit heap dynamic. For each of the following storage bindings, write a C or C++ program that demonstrates a realistic use of a variable that uses this storage binding. Discuss why your program exhibits a good use of the storage binding.
static
stack dynamic
explicit heap dynamic
[Skill 5.3] For the following pairs of types (in C++ notation) determine if they are equal by name equality, structural equality, both, or neither:
int and int
class LL1a {int val; LL1a *next; } and class LL2a {int val; LL2a *next; }
class LL1b {int val; LL1b *next; } and class LL2b {int val; LL1b *next; }
class LL1c {int val; LL2c *next; } and class LL2c {int val; LL1c *next; }
LL1c[] and LL1c[]
LL1c[] and LL2c[]
[Synthesis] As we discussed in class, name type equality can create difficulties when writing distributed programs. It seems a paradox that Java has name type equality yet it supports distributed programming (via, for example, RMI and Serialization). Investigate and report on how this works in Java, giving appropriate references and quotes from Java documentation. Note: this will require quite a lot of research (probably on the web) on your part so allocate your time accordingly!