CMSI 3802: Programming Language Concepts and Implementation Practice Questions

Here are some long-form exercises for you to work on to improve understanding and retention of course content. Short-form recall questions, designed to be part of your spaced-repetition learning regimen, can be found at the bottom of each page of course notes.

Additional recall questions tied to specific programming languages can be found at the Programming Languages Explorations companion website.

Short Answer Questions

Here are some questions that might be found on an in-class paper-and-pencil exam.

How do Python and JavaScript differ in their approach updating non-local variables?
Python requires the nonlocal (or global) keyword to do this, while JavaScript does not.
What is the difference between the way JavaScript and Rust handle the sequence:
```
let x = 3;
let x = 3;
```
This is a redeclaration error in (strict mode) JavaScript (Identifier 'x' has already been declared). In Rust, two variables are declared, with the second shadowing the first. You do get a warning though, saying the first variable is never used, but there is no error.
What is the difference between an expression and a statement?
An expression produces a value, while a statement does not. Statements perform actions.
How did Go “fix” the most unintuitive aspect of the C switch statement?
It eliminated implicit fallthrough.
Why is it that the simple act of doing an operation 10 times so easy in Ruby but so annoyingly complex in C-like languages?
Ruby has a built-in times method on integers, while C-like languages require a loop with a counter that you don’t care about!
What is tail recursion and why is it useful?
What is the non-deterministic statement of Go? Of Erlang?
What is so awesome about having large structs or arrays be immutable?
You don’t have to copy them. Reference to them can be safely shared.
What does it mean for a type to be extra-lingual?
It means that types are not themselves values.
How does one query the type of an expression at run time in JavaScript? Python? Ruby?
What are the main differences between a type and a class?
What is a mixin?
Why do languages like Ruby have a single type Array but in other languages like Java, Rust, and Swift there exist many parameterized array types?
Type checking is often concerned less with whether two types are identical, but rather when elements of one type T1 can be assigned to an Lvalue constrained to be of type T2. In what situations is this check made?
(1) variable initialization, (2) assignment, (3) passing arguments to parameters, (4) returning from a function.
What is the difference between type conversion and type coercion?
In the conditional expression x ? y : z of a typical statically-typed language, what type checking and inference rules would a compiler be required to enforce?
Checks: the type of x must be boolean and the types of y and z must be compatible. Inference: the type of the entire expression is the least general type of both y and z.
In what sense is the type inference capabilities of ML and Haskell more powerful that that on Go, Rust, Java, and Swift?
Why (do you think) does Java not infer the types of parameters in normal methods but does infer them for lambdas?
I couldn’t find in the definition of C whether the language employs shallow or deep binding. Why?
C doesn’t have nested functions.
What are covariance, contravariance, invariance, and bivariance?
In what way is a record like a dictionary? In what why are they different?
Both records and dictionaries are comprised of key-value pairs. The difference is that records are intended to model the properties of a single thing, while dictionaries are indented to show the values of a single property across many things.
What does it mean for a record or dictionary to be ordered?
What mechanism do many languages use to avoid unions?
If someone talks about static arrays and dynamic arrays, what are they probably referring to?
Given the Python definition def f(): yield 1; yield 2; yield 3, what is wrong with writing for i in f: print(i)? What should we write instead?
In Python, why should you be scared of using default arguments that are lists? Do you have to worry about this in JavaScript?
Python defaults for parameters are evaluated only once, at the time the function is defined. So all calls to the function use the SAME list! If you mutate that list in the function, then that mutation is seen in future calls. JavaScript, on the other hand, evaluates the default on every call.
In Python, len("Hello, 世界") == 9, but in Rust, "Hello, 世界".len() == 13. Why is this?
Python counts the number of code points, while Rust counts the number of bytes. In the UTF-8 encoding, each of the final two characters requires 3 bytes.
What is the first thing you should do in the implementation of an overloaded assignment operator in C++?
Make sure the source and target of the assignment are not the same! Assignment destroys the target before the copy/move, so if you were doing x = x for example, you have to early exit before destroying anything.
Write a C++ expression, using std::fill, that fills the first 100 elements of the C-style array a of integers with 0s.
std::fill(a, a+100, 0)
In JavaScript, how do you set an object’s prototype after the object has already been created?
Object.setPrototypeOf(myObject, theNewPrototype)
In JavaScript, how does one “wait” for a whole bunch of async functions to all ”finish”?
Promise.all(arrayOfPromises).then(callback)
Is JavaScript 100% weakly typed? About what percentage is it? Why, exactly, is it not?
Perhaps 80-90. There are several cases in which TypeError is thrown, such as (1) trying to access a property of null or undefined, (2) trying to call a non-function value, (3) trying to use a non-iterable value in a for-of loop.
In C++, Do the types int, float, and double have fixed bit sizes? If so, what are they? If not, why not?
No, C++ is a systems language whose numeric types map directly to the machine’s underlying registers, using whatever size those registers are.
In Python, the expression list(t), for some tuple t, produces the list containing the elements of t in order. Can you write a function in Haskell to do the same thing, i.e., build a list from some arbitrary tuple? If so, give the Haskell function that does it. If not, explain why Haskell can’t do this.
Haskell can’t! There’s no type for an arbitrary-sized tuple!
In JavaScript, Why is [1,12] < [1,3] true but [1,42] < [1,3] false? Why are both expressions false in Python and Haskell?
JavaScript < turns arrays into strings before comparing, and "1,12" < "1,3". Python and Haskell do numeric element-by-element comparison and 1=1 and 12 > 3.
In Java, if you wanted to average some integers, you could write Stream.of(1,2,3).collect(Collectors.averagingInt(f)) for some particular function f. What should f be here?
x -> x or Integer::new
The Java expression IntStream.range(1, n+1).reduce((x, y) -> x * y) is a good attempt to produce the factorial of n, but it doesn’t produce an integer. What does it produce? How can you modify it (slightly) to produce the integer factorial?
This returns an optional! To get an actual integer, we should use the two-argument version of reduce, passing in 1 as the first argument. You can also do an .orElse(1) at the end.
Suppose r was a (Java) Reader object. How do you get the lowercased lines of the reader into an array, eliminating all duplicates?
r.lines().distinct().map(String::toLowerCase).toArray(String[]::new)
In Python, why should you be scared of using default arguments that are lists? Do you have to worry about this in JavaScript?
Python defaults for parameters are evaluated only once, at the time the function is defined. So all calls to the function use the SAME list! If you mutate that list in the function, then that mutation is seen in future calls. JavaScript, on the other hand, evaluates the default on every call.
In Swift, Are if-let, while-let, or guard-else constructs required to access an element of an optional array? If not, what is a more concise way to access the element?
No, for optional array a and integer i, you get the convenient a?[i].
Define your very own Swift generic linked list as an indirect enumeration, using the definition “A list is either empty or a value (called the head) connected to a list (called the tail).” (Just define the type, you don’t need to include any methods.)
```
indirect enum MyList<T> {
  case empty
  case node(head: T, tail: MyList)
}
```
Why and when do we extend protocols in Swift?
To add functionality to protocols that already exist. And most awesomely, when we need to create default methods for all adopters of the protocol.
For each of the languages JavaScript, Python, Java, C++, and Haskell, is the language’s “null value” a member of the language’s string type (respectively: "string", str, String, std::string, String, [Char]), or if not, what related type is it a member of? For example, if you were asked about Swift, you would say: “nil is not a member of the type String, but it is a member of String?”.
JS: no, null ∈ the Null type.
Python: no, None ∈ NoneType.
Java: YES!!! BILLION DOLLAR MISTAKE!!!
C++: no, nullptr is not in the std::string type, but ∈ char* and std::string*.
Haskell: no, Nothing ∈ Maybe String.
Some languages don’t have loops; they make you use recursion. So, a good programmer should be fluent in translating a function with loops into a recursive one. Here’s an iterative function written in C++:
```
int c(int n) {
  int steps = 0;
  while (n > 1) {
    n = n % 2 == 0 ? n / 2 : 3 * n + 1;
    steps++;
  }
  return steps;
}
```
When written recursively, the function body can reduced to a single expression! Express this function as a one-liner in JavaScript, Python, Java, C++, Swift, Kotlin, or Haskell: your choice! If using Haskell, use guards rather than an if expression.
So many possible answers here. Here is the direct translation (slow):
- JavaScript: function c(n) { return n<=1 ? 0 : n%2===0 ? 1+c(n/2) : 1+c(3*n+1) }
- Python: def c(n): return 0 if n<=1 else 1+c(n//2) if n%2==0 else 1+c(3*n+1)
- Java: static int c(int n) { return n<=1 ? 0 : n%2==0 ? 1+c(n/2) : 1+c(3*n+1); }
- C++: int c(int n) { return n<=1 ? 0 : n%2==0 ? 1+c(n/2) : 1+c(3*n+1); }
- Swift: func c(n: Int) -> Int { return n<=1 ? 0 : n%2==0 ? 1+c(n/2) : 1+c(3*n+1); }
- Kotlin: fun c(n: Int): Int { return n<=1 ? 0 : n%2==0 ? 1+c(n/2) : 1+c(3*n+1); }
- Haskell: c n | n<=1 = 0 | even n = 1+c(n `div` 2) | otherwise = 1+c(3*n+1)
The tail-recursive way is better. Left as an exercise to you.
Given a = [10,20,30,30,40,30], draw a picture of the world after b = delete 30 a that shows you understand persistent data structures. (delete is from Data.List).
The first two nodes are copied; the rest can be shared.
```
  a ------>  10 ----> 20 ----> 30 ----> 30 ----> 40 ----> 30
                                        ^
                                        |
  b ------>  10 ----> 20 ---------------+
```
In Haskell, why are (/ 2) and (/) 2 different functions, but (elem 21) and (elem) 21 are the same function?
Since / is an infix operator, (/ 2) is a right operator section which divides its argument by 2, but (/) 2 is a function which returns 2 divided by its argument! Alternatively, since elem is a regular prefix operator, there is no section here, and (elem 2) and (elem) 2 are just putting parentheses where they already belong anyway.
What kinds of objects do Haskell’s search/lookup/find functions return?
Maybes
Many languages use split to break a string into a list of characters, and join to turn an array of characters into a string. How do you do these two operations in Swift?
Array(s) breaks a string into a list of chars, String(a) joins a list of strings into a single string.
Explain why C++ move constructors and move assignment operators only make sense on r-values and not l-values. You can use a rough code fragment in your explanation.
Why does C++ even have moves, anyway?
When would you choose an atomic variable over a mutex?
In a typical compiler, what does a parser produce?
A syntax tree. Some produce concrete syntax trees, others produce abstract syntax trees.
Why are compilers split into a front end and a back end? Give the two most important reasons.
(1) You can’t help but think of translation without an intermediate conceptual representation. (2) Your front-ends are reusable for many targets, and your backends are reusable for many source languages.
Critique the claim “Writing a transpiler means your compiler needs only a front end and not a backend.” There’s a kernel of truth to it, but it might not be wholly accurate.
You do need a backend to generate the target code from an intermediate representation. Some purists might claim that to be a “real backend” you have to generate some really great, optimized assembly language for a serious target machine, so the claim all hinges on what is meant by “backend.”
Is the program tsc a compiler or a transpiler? Do we care?
Well, it does stand for “TypeScript compiler” so sure, it’s a compiler because it compiles TypeScript into JavaScript. But then again, JavaScript is a high level language so you can call it a transpiler too. Both terms work. Don’t be picky. Don’t be that person. It’s not worth getting worked up about.
How can we make the negation operator and the exponentiation operator not associate with each other? Show a grammar fragment.
Put them on the same “level”:
```
Exp7 = "-" Exp8
     | Exp8 "**" Exp7
     | Exp8
```
For each scenario below, give Ohm grammar rules for Exp, Term, Factor, and Primary that make the expression -2**2:
1. Evaluate to $4$.
2. Evaluate to $-4$.
3. Be a syntax error, while allowing (-2)**2 and -(2**2) to be legal.
Why do language designers put functions like sqrt into a standard library (as opposed to being wired into the language, or left to a “third party” library?
It is so commonly used that most people want or expect it without having to import an external library, and yet, it is not common enough to warrant its own operator wired into the core syntax of a language.
What is wrong with the Ohm rule
```
  WhileStmt = "while" Exp Block
```
How do we fix this problem?
If the expression begins with a letter, Ohm would still match the while statement even if there were no spaces between the word “while” and the expression! To fix this, create a lexical category while = "while" ~idrest and redefine the while statement rule as WhileStmt = while Exp Block.
How do we write a rule for JavaScript-style one-line comments in Ohm?
```
"//" (~"\n" any)* "\n"
```

The Ohm notation

  Factor = "-" Primary  -- negation
         | Primary

is actually an abbreviation for two separate rules. Give those two rules.

  Factor = Factor_negation
         | Primary
  Factor_negation = "-" Primary

The Ohm rule
```
  Exp = Term ("+" Term)*
```
fails to capture what aspect of the + operator in the syntax?
Associativity.
In Ohm, the construct A ~B matches an A that is not followed by a B. How do we match an A that is followed by a B (without consuming the B)?
```
&(A B) A
```
Can an Ohm grammar ever be ambiguous?
Yes and no. It depends. Certainly PEGs can’t be ambiguous due to prioritized choice over non-deterministic choice and their prohibition against left recursion; but Ohm allows left-recursion so you can write:
```
  A = A "+" A  --plus
    | "a"
```
which looks ambiguous. Ohm actually makes the operator here be right associative, so given the fact that Ohm is an implementation and always parses strings exactly one way, then no, its grammars are not ambiguous; however, this isn’t really specified anywhere so maybe yeah, that grammar in some sense is ambiguous. See issues 55 and 56 for more information.
Given categories E (for expression) and T (for term), give an Ohm grammar rule to make the operator • on terms be left-associative.
```
  E = E "•" T  --binary
    | T
```
Given categories E (for expression) and T (for term), give an Ohm grammar rule to make the operator • on terms be right-associative.
```
  E = T "•" E  --binary
    | T
```
Given categories E (for expression) and T (for term), give an Ohm grammar rule to make the operator • on terms be non-associative.
```
  E = T "•" T
```
Here is an attempt to remove the need for operator precedence levels in a language design. Does it work? Why or why not?
```
  E = E binaryop "(" E ")"
    | num
```
It does, but I’ll admit it’s hard to prove. Can someone help?
The parser generator in the Ohm system is unlike most others, in that it is not based on context-free grammars. What theoretical language description mechanism does it use?
Parsing Expression Grammars, or PEGs.
Why do many languages make relational operators non-associative?
Reasonable people can disagree on the meaning of a<b<c. Some people think it should be automatically expanded to a<b && b<c. Others think it should be (a<b)<c.
In a language with string interpolation, what do we usually call the literal portions of a string? What are the interpolated portions called in ESTree?
Quasis.
What is the difference between an expression and a statement?
Expressions produce values; statements don’t. Statements are executed only for their effect.
In many languages, expressions can appear within statements, but not the other way around. In JavaScript, however, statements can appear within expressions. Give an example.
console.log(() => {if (true) return;})
In JavaScript, the left hand side of an assignment is not “just a variable”. What do we call that construct?
A pattern.
Why is division by zero not considered a dynamic semantic error in Java?
An exception is thrown in this case and can be caught, with the program proceeding normally. Throwing and catching exceptions is well-defined and certainly does not violate any language rules.
In Java, the grammar allows x < y < z. So what exactly happens when the compiler encounters this code fragment (assuming all variables are in scope)?
The operator is left-associative so x < y is checked. That is either a type error or a perfectly valid comparison assigned the type boolean. Booleans can’t be compared anyway, so the entire expression is always a type error, detectable at compile time! But it is NOT a syntax error.
Type checking is often concerned less with whether two types are identical, but rather when elements of one type $T_1$ can be assigned to an Lvalue constrained to be of type $T_2$. In what situations is this check made?
(1) variable initialization, (2) assignment, (3) passing arguments to parameters, (4) returning from a function.
In the conditional expression x ? y : z of a typical statically-typed language, what type checking and inference rules would a compiler be required to enforce?
Checks: the type of x must be boolean and the types of y and z must be compatible. Inference: the type of the entire expression is the least general type of both y and z.
How does a semantic analyzer check the legality of mutually recursive functions?
In each block it first analyzes the signatures of each block and adds the function name and signature to the block’s context. Then it analyzes the function bodies (on a second “pass” through the block).

Problems

Here are some problems that require some thinking, and some actual work. They may involve writing little scripts, or making sketches. They aren’t exactly short-answer problems.

Syntax

Translate the following expression into (a) postfix and (b) prefix notation, in both cases without using parentheses:
```
(-b + sqrt(4 × a × c)) / (2 × a)
```
Do you need a special symbol for unary negation? Why or why not?
JavaScript's implicit semicolon insertion is often considered to be poorly designed because the following four cases aren’t exactly intuitive:
```
function f() {
    return
       { x: 5 }
}
```
```
let b = 8
let a = b + b
(4 + 5).toString(16)
```
```
let place = "mundo"
["Hola", "Ciao"].forEach((command) => {
  console.log(command + ", " + place)
})
```
```
const sayHello = function () {
    console.log("Hello")
}
(function() {
    console.log("Goodbye")
}())
```
What is being illustrated in each of the above? Go, Python, Scala, and Ruby all allow line endings to end statements and you don’t hear people complaining about them the way they do about JavaScript. Pick one of these four languages and show why they don’t have problems with these four cases.
In Lisp, most of the arithmetic operators are defined to take two or more arguments, rather than strictly two. Thus (* 2 3 4 5) evaluates to 120, and (– 16 9 4) evaluates to 3. Show that parentheses are necessary to disambiguate arithmetic expressions in Lisp (in other words, give an example of an expression whose meaning is unclear when parentheses are removed). Why then, in one popular textbook (Programming Language Pragmatics by Michael Scott), does it say “Issues of precedence and associativity do not arise with prefix or postfix notation”? Reword this claim to make explicit the hidden assumption.
Scott is assuming all operators have a fixed arity. What he meant to say was: “Issues of precedence and associativity do not arise with prefix or postfix notation assuming all operators have fixed arity.”

Names, Scopes, and Bindings

What is meant by the scope of a binding? Give examples of both spatial and temporal scope, using examples from the programming language of your choice.
Give three examples from C which a variable is live but not in scope. Make sure each example is of a different quality than the others; for example, don’t just hide three global variables in a single function and claim you have three examples.
Give an example of a program in C that would not work correctly if local variables were allocated in static storage as opposed to the stack. For the purposes of this question, local variables do not include parameters.
In C, f(2) should return 2, but if local variables were allocated statically, it would return 3.
```
void f(int x) {
    int a = 2;
    int b;
    if (x < 0) {
        a = 3;
        return 0;
    } else {
        b = f(-x);
        return b + a;
    }
}
```

What would this program output under static scope rules? Under dynamic scope rules?

declare x = 2;
sub f() {print x;}
sub g() {declare x = 5; f(); print x;}
g();
print x;

What does this script print under (a) static scope rules and (b) dynamic scope rules?
```
var x = 1
function f() {return x;}
function g() {var x = 2; return f();}
print g() + x
```
(a) 2, (b) 3

What does this script print under (a) static scoping and (b) dynamic scoping?

var x = 1
function h() {var x = 9; return g();}
function f() {return x;}
function g() {var x = 3; return f();}
print f() * h() - x

What does this script print under (a) static scoping and (b) dynamic scoping?

var x = 1
function h() {var x = 0; return g()}
function f() {return x}
function g() {var x = 8; return f()}
print f() - h() + x

What does this script print under (a) static scoping and (b) dynamic scoping?
```
var x = 100;
function setX(n) {x = n;}
function printX() {console.log(x);}
function first() {setX(1); printX();}
function second() {var x; setX(2); printX();}
setX(0);
first();
printX();
second();
printX();
```
Static scope rules result in an output of 1122, while dynamic rules result in 1121. This is because with static scoping, the second execution of setX changes the global x to 2, so that the last printX in the script prints 2. With dynamic scope, the second setX call changes the local x to 2, leaving the global x unaffected.

Show the output of the following, assuming dynamic scope and (a) deep binding, and (b) shallow binding.

function g(h) {
  var x = 2;
  h()
}
function main() {
  var x = 5
  function f() {
    print x + 3
  }
  g(f)
}
main()

(a) 8, (b) 5

Show the output of the following, assuming dynamic scope and (a) deep binding, and (b) shallow binding.

function f(a) {
  var x = a - 1
  function g() {
    print x - 17
  }
  h(g)
}
function h(p) {
  var x = 13
  p()
}
f(18)

This fragment of Java code illustrates something about scope. Or does it? Relate it to other similar problems we've seen regarding scope. (Don't forget to come across as being articulate and intelligent in your discussion.)
```
public void fail() {
    class Failure extends RuntimeException {}
    throw new Failure();
}
```

Show the output of the following, assuming dynamic scope and (a) deep binding, and (b) shallow binding.

function g(h) {
  var x = 2;
  h()
}

function main() {
  var x = 5
  function f() {
    print x + 3
  }
  g(f)
}

main()

(a) 8, (b) 5

Show the output of the following, assuming dynamic scope and (a) deep binding, and (b) shallow binding.

function f(a) {
  let x = a - 1
  function g() {
    print x - 17
  }
  h(g)
}
function h(p) {
  let x = 13
  p()
}
f(18)

Explain what would need to be done to make deep binding work with dynamic scoping, assuming that association lists were used to implement the scope rules. (Hint: think of turning the association lists into “A-trees.”)
When you call the passed function, save the existing pointer to the top of the association list and replace it with a pointer to just before the point that the function was defined. Then enter the bindings for the new function as a "branch" in the association list (which is now a tree). When the function finally returns, chop off that branch and restore the pointer.
Does the following Python code serve as part of a valid experiment to determine whether Python is statically or dynamically scoped? Why or why not?
```
x = 3
def f():
    print x
def g():
    x = 5
    f()
g()
```
The following is not a valid experiment as to whether Ruby is statically or dynamically scoped. Why not?
```
x = 3
def f(); puts x; end
def g(); x = 5; f(); end
g()
```
In Ada, the declarations
```
X: Integer := X + 1;
T: T;
Y: Real := Y(T);
```
(where global declarations of X, T and T are visible) are all illegal, since a declaration of an identifier hides global declarations of the same name immediately at the point it appears in the text, but the identifier may not be used until its declaration is complete. Give an alternate interpretation under which these declarations would be legal and explain the advantages and disadvantages of it from both the programmer's and the compiler writer's perspectives.
This fragment of Java code illustrates something about scope. Or does it? Relate it to other similar problems we've seen regarding scope.
```
public void fail() {
    class Failure extends RuntimeException {}
    throw new Failure();
}
```

Expressions

Define the terms precedence, associativity, fixity, arity, giving plenty of examples of each.
Write an expression (in as many languages as you can) to produce an array of length 100 filled with 0s. For C++, show three versions: one with raw arrays, one with std::array and one with std::vector, and use std::fill if appropriate.
The Java expression IntStream.range(1, n).reduce((x, y) -> x * y) is a good attempt to produce the factorial of n, but it doesn’t produce an integer. What does it produce? How can you modify it (slightly) to produce the integer factorial?
Write a list comprehension (in as many languages as you can, but of course in at least Python and Haskell) for all pairs (2-tuples) of integers where the first element is in the range 1..5 inclusive and the second is in the range 1..3 inclusive.
Here's an operator chart from some unnamed language. Operators are listed in decreasing precedence (highest precedence operators are at the top of the table; lowest precedence operators are at the bottom). Operators listed on the same line have the same precedence.

Operator(s) Assoc Arity Fixity
§ # 1 Prefix
∀ ⊥ 1 Postfix
% • ¥ L 2 Infix
⊗ ∇ ⇒ R 2 Infix
Draw the expression tree for the following
```
# # A ⇒ # B ∇ C ¥ D % E ∇ F % G • H ⊥ ∀ ⊗ § I ∀
```
```
   ⇒
 /   \
#      ∇
|    /   \
#   #      ∇
|   |    /   \
A   B   %      ⊗
       / \    /  \
      ¥   E  •    ∀
     / \    / \   |
    C   D  %   ∀  §
          / \  |  |
         F   G ⊥  I
               |
               H
```
The expression a–f(b)–c*d can produce different values depending on how a compiler decides to order, or even parallelize operations. Give a small program in the language of your choice (or even one of your own design) that would produce different values for this expression for different evaluation orders. Please note that by "different evaluation orders" we do not mean that the compiler can violate the precedence and associativity rules of the language.

Operator(s)	Assoc	Arity	Fixity
§ #		1	Prefix
∀ ⊥		1	Postfix
% • ¥	L	2	Infix
⊗ ∇ ⇒	R	2	Infix

Types

JavaScript is considered mostly “weakly-typed” because it generally performs coercions. However, in a few cases, it does throw TypeError. What are the cases in which this error is thrown?
In the Java programming language, if the class Dog were a subclass of class Animal, then objects of class Dog[] would be compatible with the type Animal[]. Write a fragment of Java code that shows that this requires dynamic type checking. Include in your answer a well-written explanation that shows you truly understand the difference between static and dynamic types.
If both Dog and Rat are subclasses of Animal, this code
```
Animal[] pets = new Dog[4];
pets[0] = new Rat();
```
compiles fine but when executed throws an ArrayStoreException, that's right, a run-time typecheck error. This means Java is NOT 100% statically typed because this typecheck occurs at run time. A language can only be called 100% statically typed if all type conflicts are detected at compile time.

Here's a variation of M-J. Dominus' Spectacular Example.

local
    fun split [] = ([],[])
      | split [h] = ([h], [])
      | split (x::y::t) = let val (s1,s2) = split t in (x::s1,y::s2) end
    fun merge c ([], x) = x
      | merge c (x, []) = x
      | merge c (h1::t1, h2::t2) =
          if c(h1,h2)<0 then h1::merge c(t1,h2::t2) else h2::merge c(h1::t1,t2);
in
    fun sort c [] = []
      | sort c x = let val (p, q) = split x
                     in merge c(sort c p, sort c q)
                   end;
   end;

During type inference, give the types assigned to
- the parameter c within sort
- the function split
- the function merge
- the y in the third clause of split?
Give the type of sort and explain why it is not what you would expect.
How do you rewrite the function to make it actually do a mergesort?

Here's some code in some language that looks exactly like C++. It is defining two mutually recursive types, A and B.
```
struct A {B* x; int y;};
struct B {A* x; int y;};
```
Suppose the rules for this language stated that this language used structural equivalence for types. How would you feel if you were a compiler and had to type check an expression in which an A was used as a B? What problem might you run into?
Consider the following C declaration, compiled on a 32-bit little endian machine:
```
struct {
    int n;
    char c;
} A[10][10];
```
If the address of A[0][0] is 1000 (decimal), what is the address of A[3][7]?

Explain the meaning of the following C declarations:

double *a[n];
double (*b)[n];
double (*c[n])();
double (*d())[n];

Translate each of the following declarations in C to Go:

double *a[n];
double (*b)[n];
double (*c[n])();
double (*d())[n];

(Either put a check mark next to “Yes” or fill in the “No” part.) Is a null value a member of:
1. The JavaScript type "string"? Yes_________ No, but it's a member of __________________________
2. The Python type str? Yes_________ No, but it's a member of __________________________
3. The Java type String? Yes_________ No, but it's a member of __________________________
4. The C++ type string? Yes_________ No, but it's a member of __________________________
5. The Haskell type [Char]? Yes_________ No, but it's a member of __________________________
In JShell, enter the three commands
```
String[] x = new String[]{"A", "B"}
Object[] y = x
y[1] = 50
```
Omg, Java just gave a run-time error! So can you say “Java is a statically-typed language?” If so, why? If not, what is a better thing to say?
Consider the following declaration in C:
```
double (*f(double (*)(double, double[]), double)) (double, ...);
```
Describe rigorously, in English, the type of f.
Suppose you were designing a programming language (yes it could happen) and you chose the following types: Null, Boolean, Number, String, Array, Dictionary, and Function. Suppose you wanted to make the language 100% weakly typed. In order to do this you would have to come up with a rule for implicitly converting any expression of any type into a reasonable equivalent value in another type, essentially completing this table:

To→
From↴ Bool Num Str Arr Dict Fun
Null false
0 "" [] {}
Bool false→0
true→1
Num 0→false
else true
Str ""→false
else true
Arr []→false
else true
Dict {}→false
else true
Fun true

Explain how you would complete this table.
Many answers are possible for the table filling in. Here are mine:
- Str to Num: The number the string looks like, else NaN if it doesn’t look like a number
- Arr to Num: The length of the array
- Dict to Num: The number of entries in the dict
- Fun to Num: The number of parameters of the function
- Bool to Str: "true" or "false"
- Num to Str: The obvious rendering of the number (in base 10)
- Arr to Str: The obvious rendering of the array, with square brackets and commas, with some special marker to prevent infinite strings
- Dict to Str: The obvious rendering of the dict, with braces, colons, and commas, with some special marker to prevent infinite strings
- Fun to Str: The source code, nicely formatted according to some specific rules
- Anything except null (or another Arr) to Arr: A single element array containing its value. It is possible to have special cases for Strs — make an array of its characters — and Dicts — {"a":"b", "c":"d"} ⇒ ["a","b","c","d"].
- Anything (except another Dict) to Dict: Probably just {}. I suppose for arrays we can do ["a","b","c","d"] ⇒ {"a":"b", "c":"d"}.
- Anything to Fun: A no-arg function returning that value.

Pointers and References

If possible, write programs in Go, Rust, and C++ to create a situation in which variable “points to itself.” That is, for some variable x, we have *x == x. If this is not possible, state why it is not possible.
If possible, write programs in Modula 3 and Ada to create a situation in which variable “points to itself.” That is, for some variable X, we have X^ = X in Modula 3 or X.all = X (in Ada). If this is not possible, state why it is not possible.
In C++ you can say (x += 7) *= z but you can’t say this in C. Explain the reason why, using precise, technical terminology. See if this same phenomenon holds for conditional expressions, too. What other languages behave like C++ in this respect?
Assume the existence of the following C++ classes:
```
#include <list>
class Animal {};
class Dog: public Animal {};
class Cat: public Animal {};
Animal a; Animal* ap; Dog d; Dog* dp; Cat c; Cat* cp;
list<Animal> animals; list<Dog> dogs;
```
1. Circle the allowable assignments:
  a = d;
  ap = &d;
  d = a;
  dp = &a
  dp = (Dog*)(&a);
  dp = (Dog*)cp;
  ap = new Dog;
  ap = &(new Cat)
  d = Dog(a)
2. Is the assignment animals = dogs okay? Why or why not? Be clear. There is something that needs to be said to get full credit.

Control Flow

The following pseudocode shows a mid-test loop exit:
```
while (true)
    line := readLine();
    if isAllBlanks(line) then exit end;
    consumeLine(line);
end;
```
Show how you might accomplish the same task using a while or repeat loop, if mid-test loops were not available. (Hint: one alternative duplicates part of the code; another introduces a Boolean flag variable.) How do these alternatives compare to the mid-test version?
Assume we wanted to write a function called If in Java or C or JavaScript, such that the call If(c, e1, e2) would return e1 if c evaluated to true, and e2 if it evaluated to false. Show why, in these languages, such a function is absolutely not the same as the conditional expression c?e1:e2. You can show a code fragment that would return different results based on whether the function were called versus the conditional expression were evaluated.
In Java, C, and JavaScript, all function arguments are evaluated before they are called. The evaluation of (p==null ? null : p.value) is null-safe, whereas the call If(p==null, null, p.value) is not: it throws a NullPointerException if p is null. A more blatant example can be seen in the difference between (true ? 1 : formatMyHardDrive()) and If(true, 1, formatMyHardDrive()).
Frank Rubin used the following example (rewritten here in C) to argue in favor of a goto statement:
```
int first_zero_row = -1;              /* assume no such row */
int i, j;
for (i = 0; i < n; i++) {             /* for each row */
    for (j = 0; j < n; j++) {         /* for each entry in the row */
        if (A[i][j]) goto next;       /* if non-zero go on to the next row */
    }
    first_zero_row = i;               /* went all through the row, you got it! */
    break;                            /* get out of the whole thing */
    next: ;
}                                     /* first_zero_row is now set */
```
The intent of the code is to set first_zero_row to the index of the first all-zero row, if any, of an n × n matrix, or -1 if no such row exists. Do you find the example convincing? Is there a good structured alternative in C? In any language? Give answers in the form of a short essay. Include a good introductory section, a background section describing views on the goto statement throughout history, a beefy section analyzing alternatives to Rubin's problem, and a good concluding section. Talk about solutions in at least three languages. You may find higher order functions such as every, some, and forEach to be helpful.
Critique this candidate solution to Rubin’s problem of finding the first all-zero row in a two-dimensional array (matrix):
```
function indexOfFirstAllZeroRow (a) {
  return a.map(row => row.every(x => x === 0)).indexOf(true)
}
```
This solution is clear, but inefficient. It examines every element of every row, even after it has found a non-zero element in a row. A more efficient solution would short-circuit the search for each row as soon as a non-zero element is found, something like:
```
function indexOfFirstAllZeroRow (a) {
  for (let i = 0; i < a.length; i++) {
    if (a[i].every(x => x === 0)) {
      return i;
    }
  }
  return -1;
}
```
However, findIndex short circuits!
```
function indexOfFirstAllZeroRow (a) {
  return a.findIndex(row => row.every(x => x === 0))
}
```
Critique this candidate JavaScript solution to Rubin’s problem of finding the first all-zero row in a two-dimensional array (matrix):
```
function firstAllZeroRow (a) {
  let result = -1
  a.some((row, i) => {
    return row.every(x => x === 0) ? ((result = i), true) : false
  })
  return result
}
```
This solution is clever, but less clear than a straightforward loop. It uses the side effect of assigning to result within the some callback, which can be confusing. A more straightforward approach would be to directly use findIndex, as shown in the previous answer.
Critique this candidate Python solution to Rubin’s problem of finding the first all-zero row in a two-dimensional array (matrix):
```
def first_all_zero_row(a):
    return next((i for i,row in enumerate(a) if all(x == 0 for x in row)), -1)
```
This solution is concise and leverages Python's generator expressions effectively, though it could be considered a bit dense. A for-loop, though longer, would probably be considered Pythonic.

Functions

Some languages do not require the arguments to a functions call to be evaluated in any particular order. Is it possible that different evaluation orders can lead to different arguments being passed? If so, give an example to illustrate this point, and if not, prove that no such event could occur.
In C++ and Java, it is not permitted to have two functions that differ only in return type overload each other. In Ada, it is allowed. What is the reason for this situation? Even though other languages do allow this flexibility in overloading, the compiler needs some sophistication. What exactly is involved? Be very precise in your explanation and illustrate it with code fragments.
Write a function that accepts a function $f$ and a list $[a_0, a_1, \ldots, a{_n-1}]$ and returns the list $[a_0, f(a_1), f(f(a_2)), f(f(f(a_3))), \ldots]$. For example, if you pass as arguments the function that doubles its inputs, and the list $[4, 3, 1, 2, 2]$, then the return value would be $[4, 6, 4, 16, 32]$.

Rewrite this old-fashioned JavaScript function in modern JavaScript:

function zip3(point, array) {
  return [[point.x, array[0]], [point.y, array[1]], [point.z, array[2]]];
}

Do the following in JavaScript, Python, Java, C++, and Haskell. Write a function expression that does curried multiplication. For example, your expression e should be such that e(8)(3) would produce 24. By function expression I mean an “anonymous function.” Don’t give a function declaration; give the expression. (Okay, here it is in Python: lambda x: lambda y: x * y. Just do the other four. One line each please.)
Why is it impossible to have a function in Haskell that accepts an arbitrary list and returns a tuple containing all of the list elements in the given order? And why is it impossible to have a function in Haskell that does the reverse (arbitary tuple to list)? (Please be brief: it’s the same reason for both parts!)
Write an Haskell function called toList3 that accepts a three-element tuple and produces the corresponding three-element list (it‘s trivial). Include the type signature. Use pattern matching.
Java rejects pattern matching of function parameters. Java also rejects defaults for parameters. (a) Briefly, in one sentence only, why are the Java desginers cramping your style in these two areas? (It is the same reason for both.) (b) What are you supposed to use instead of default parameters?
Write a tail-recursive function or method (in as many languages as you can) that produces the sum of squares in an array. This is just to give you practice with tail-recursion; I know there are better ways to compute the sum-of-squares.
A possible JavaScript solution is:
```
function ss(a) {
  function s(i, acc) {
    return i == a.length ? acc : s(i+1, a[i]*a[i]+acc)
  }
  return s(0, 0);
}
```
A possible Ruby solution is:
```
def ss(a)
  s = Proc.new{|i,acc| i==a.length ? acc : s[i+1, a[i]*a[i]+acc]}
  s[0, 0]
end
```
Write a tail-recursive function to compute the minimum value of an array or list in Python, C, JavaScript, Go, and perhaps a few other languages. Obviously these languages probably already have a min-value-in-array function in a standard library, but the purpose of this problem is for you to demonstrate your understanding of tail recursion. Your solution must be in the classic functional programming style, that is, it must be stateless. Use parameters, not nonlocal variables, to accumulate values.
Write a code fragment (in as many languages as you can) that fills an array, indexed from 0 through 9, such that slot i of the array contains a function (or pointer to a function if your language demands it) that divides its argument by the square of i.
Write a tail recursive function (in as many languages as you can) that takes in an array, and returns a new array just like the old one, except with the values at even-numbered indexes removed. (It is okay to use a "helper" that is tail-recursive). For example:
```
withoutEvens([4,6,true,null,2.3,"xyz"]) => [6,null,"xyz"]
```
In as many languages as you can (but include C, Java, JavaScript, and Python for sure), write a pair of functions, $f$ and $g$, such that every time you call $f$, you get back 5 less than the result of the previous call to $f$ or $g$, and every time you call $g$, you get back double the absolute value of the result of the last call to $f$ or $g$. The initial value is 0. It is possible to do this in one line of Perl.
Write the following function in Standard ML, where your implementation must be tail recursive.
Given: a list [a₀, a₁, ..., a_n-1],
Return: a₀*a₁ + a₂*a₃ + a₄*a₅ + ....

For example, if given [3, 5, 0, 28, 4, 7] we return 15 + 0 + 28 = 43. If there are an odd number of elements in the list, assume there is an extra 1 for padding.

Here is, by the way, a non-tail-recursive formulation:
```
fun sum_of_prods [] = 0
  | sum_of_prods (x::nil) = x
  | sum_of_prods (x::y::t) = x * y + sum_of_prods t;
```
Write a JavaScript function, without using eval, that accepts an array of integers $a$, and a function $f$, and returns an array of functions, each of which, when called, invokes $f$ on the corresponding element of $a$. For example, if your function was called $g$, then calling g([6,3,1,8,7,9], dog) would return an array of functions $p$ such that, for example, calling p[3]() would invoke dog(8).
```
function g(a, f) {
    var b = [];
    for (var i = 0; i < a.length; i++) {
        b[i] = function(i){return function(){f(a[i])};}(i);
    }
    return b;
}
```
Write some JavaScript that adds a new method to arrays so that if I call this method on an array with two parameters $f$ and $g$, I get back a new function which, when called with one argument $k$, returns the composition of $f$ and $g$ applied to the $k$th element of the original array. Hint: If we defined the functions square and addSix the obvious way, and we called this new method weird, then:
```
[4, 6, 7, 3, 5, 2, 4].weird(addSix, square)
```
would return the function z such that
```
z(2) == 55
```
because the element at index 2 within the array is 7 and $7^2 + 6 = 55$.
In Go, Rust, Swift, C, and C++ arrays and records can be allocated on the stack, not just on the heap. When making assignments of aggregates to variables, compilers usually generate code to deposit the values in temporary storage. Why is this necessary in general? After all, in
```
Weekdays := Day_Set(False, True, True, True, True, True, False);
```
we could construct the aggregate directly in the variable Weekdays. Give an example of an assignment statement that illustrates the necessity of constructing an aggregate in temporary storage (before copying to the target variable).
In Java, you generally implement callbacks via registration of listeners that implement a known interface, rather than using method pointers. Create a Swing component called AngleReader which displays a picture of a circle and notifies all its listeners of the angle, in degrees, that the mouse cursor makes with the horizontal axis of the circle as the mouse moves over it.
Complete the following definition of a dot product function in ML:
```
val dot =
    let
        fun transpose ... =
    in
        ....
    end;
```
The transpose function should work like this
```
transpose ([x1,...,xn],[y1,..,yn]) = [(x1,y1),...,(xn,yn)]
```
raising Domain if the arrays have different lengths. The body of the definition of dot (between the in and end) should contain only instances of the functions transpose, o, foldr, map, op*, op+, and the value 0.
Explain what is printed under (a) call by value, (b) call by value-result, (c) call by reference, (d) call by name.
```
x = 1;
y = [2, 3, 4];
function f(a, b) {b++; a = x + 1;}
f(y[x], x);
print x, y[0], y[1], y[2];
```
1. Under call by value, the arguments do not change; so the script prints 1 2 3 4.
2. Under call by value/result, the increment of x does not take place until after the subroutine returns. It prints 2 2 2 4.
3. Under call by reference, the increment of b changes x immediately, so the new value of x, namely 2, is used to update a, which is still y[1], and that becomes 2 + 1 = 3, so it prints 2 2 3 4.
4. Under call by name, b++ changes x immediately so x becomes 2. Then, since a refers to the expression {y[x]}, it will need to compute y[2] which is 3. The script prints 2 2 3 3.
Show the output of the following code fragment under call by value, (b) call by value-result, (c) call by reference, and (d) call by name.
```
x = 1
y = [2, 3, 4]
function f(a, b) {a--; b = x - 1}
f(x, y[x])
print x, y[0], y[1], y[2]
```
Explain what is printed under (a) call by value, (b) call by value-result, (c) call by reference, (d) call by name.
```
x = 1;
y = 2;
function f(a, b) {a = 3; print b, x;}
f(x, x + y);
print x;
```
1. Value: 3 1 1
2. Value-Result: 3 1 3
3. Reference: 3 3 3
4. Name: 5 3 3
Using your favorite language and compiler, write a program that determines the order in which subroutine arguments are evaluated.
Consider the following (erroneous) program in C:
```
void do_something() {
    int i;
    printf("%d ", i++);
}
int main() {
    int j;
    for (j = 1; j <= 10; j++) do_something();
}
```
Local variable i in subroutine do_something is never initialized. On many systems, however, the program will display repeatable behavior, printing 0 1 2 3 4 5 6 7 8 9. Suggest an explanation. Also explain why the behavior on other systems might be different, or nondeterministic.
Give an example which shows that default parameters are unnecessary in C++ because you can always get the desired effect with overloading.

What does the following program output?

with Ada.Text_IO, Ada.Integer_Text_IO;
use Ada.Text_IO, Ada.Integer_Text_IO;

procedure P is
  A: Integer := 4;
  type T is access Integer;
  B: T := new Integer'(4);
  C: T := new Integer'(4);

  procedure Q (X: in out Integer; Y: T; Z: in out T) is
  begin
    X := 5;
    Y.all := 5;
    Z.all := 5;
  end Q;

begin
  Q (A, B, C);
  Put (A);
  Put (B.all);
  Put (C.all);
end P;

In some implementations of an old language called Fortran IV, the following code would print a 3. Can you suggest an explanation? (Hint: Fortran passes by reference.) More recent versions of the Fortran language don’t have this problem. How can it be that two versions of the same language can give different results even though parameters are officially passed "the same way." Note that knowledge of Fortran is not required for this problem.
```
      call f(2)
      print* 2
      stop
      end
      subroutine f(x)
          x = x + 1
          return
      end
```

Modules, Classes, and Abstract Data Types

Make a module (in as many languages as you can) with a function called nextOdd (or next_odd or nextodd depending on the language’s culture). The first time you call this subroutine you get the value 1. The next time, you get a 3, then 5, then 7, and so on. Show a snippet of code that uses this subroutine from outside the module. Is it possible to make this module hack-proof? In other words, once you compile this module, can you be sure that malicious code can’t do something to disrupt the sequence of values resulting from successive calls to this function?
Make a module (in as many languages as you can) that contains (1) a (private) string, initialized to "MI", (2) a function which retrieves the value of this string, and (3) four other methods, each of which changes the string to another string according to the following:
- If the current string ends in an "I", add "U", e.g. "MI" → "MIU".
- Append the second through last characters of the string onto itself, e.g. "MIIU" → "MIIUIIU".
- Replace any occurrence of "III" with "U", e.g. "MUIIIU" → "MUUU".
- Remove any "UU", e.g. "MIUUUI" → "MIUI".
Remember, the point is that the string inside the module can not be changed by any operation other than the four defined above.
Here is an implementation in JavaScript:
```
const mu = (() => {
  let data = "MI"
  return {
    value: function () {
      return data
    },
    rule1: function () {
      if (/I$/).test(data) data += "U"
    },
    rule2: function () {
      data = data + data.slice(1)
    },
    rule3: function () {
      data = data.replace(/III/, "U")
    },
    rule4: function () {
      data = data.replace(/UU/, "")
    }
  }
})()
```
What can’t you do with a Perl package named m, s, or y?
Consider the implementation of a Container class framework with the following abstract base class Container (here using C++ syntax):
```
template <class Item>
class Container {
public:
  unsigned numberOfItems() {return currentSize;}
  bool isEmpty() {return currentSize == 0;};
  virtual void flush() = 0;
  ~Container() {flush();}
private:
  unsigned currentSize;
};
```
Here the idea is that each particular (derived) container class shall implement its own flush() operation (which makes sense because different containers are flushed in different ways: there may be arrays, linked lists, rings or hashtables used in the representation), and when a container is destroyed its flush() operation will be automatically invoked. However, the idea is flawed and the code as written causes a terrible thing to happen. What happens?

Object-Orientation

What philosophers call a class mathematicians call a set (i.e., a collection of unordered, unique, values). So, a philosopher says that every member of a subclass is also a member of the superclass. But a C++ programmer says that every member of a superclass is also a member of its subclass! What is going on here?
Write a three-page paper on the nature of identity in object oriented philosophy. Include some code fragments to illustrate your main points.
It is certainly possible to make a Person class, then subclasses of Person for different jobs, like Manager, Employee, Student, Monitor, Advisor, Teacher, Officer and so on. But this is a bad idea, even though the IS-A test passes. Why is this a bad idea and how should this society of classes be built?
“One of the most important ways in which object oriented programming helps us to manage complexity is through the ability to group related classes into a hierarchy of subclasses and superclasses. Dynamic binding (run-time polymorphism) allows us to operate on collections of objects from different classes in a hierarchy safely. Furthermore, systems which are programmed using dynamic binding are more easily extensible.” Critique this claim. Is it true, false, or a mix of both?
Why is it said that implementation inheritance is at odds with encapsulation?
Inheritance is not always appropriate. Discuss the reasons why a design with a superclass Person and subclasses for different jobs (e.g., programmer, manager, ticket agent, flight attendant, supervisor, student, etc.) is a lousy design. Give an alternative.
In designing a class hierarchy in C++, when should you make an operation virtual and when should you make an operation non-virtual? Give examples.
Write a Perl “class” for machine parts that have an identification number (a positive integer divisible by 5), a weight (a positive floating-point number) and a name (which must consist entirely and exclusively of alphabetic characters). Provide a “constructor” that takes in a string consisting of the id, weight, and name, respectively in which
- the string may have leading and trailing spaces
- the three fields are separated by a vertical bar
- the weight is not expressed in scientific notation: it can have an integral value, but if it does have a decimal point, then it is followed by a non-empty fractional part. There is no "E" part, ever. It's simple.
The constructor will check for a valid argument by matching against a regex, and if all is cool, will split the string to assign to its fields.
Write a Python class for students that have an id, name, birthday, and transcript. The transcript is a dict, indexed by semester name, whose values are dicts mapping course numbers to grades. Supply methods to read the id, read and write the name, read and write the birthday, get the grade for a given course (in any semester), and add an item to the transcript. Did you encapsulate (i.e. hide) the properties inside the class so they were protected from direct access from outside the class? Why or why not?
Find some old “procedural” code you have written and rewrite in an object-oriented fashion. I don’t mean that you have to use inheritance or polymorphism; all I am really looking for is that you wrap some functions up in a sensible class.
A common pattern that comes up a lot is the need to assign unique identifiers to objects of a given class, for example:
```
class Item {
    private int id;
    private static int numberOfItemsCreated = 0;
    public Item() {id = numberOfItemsCreated++;}
    // pretend that there are more members here...
};
```
As you can see, every item that gets created will get a unique id. Because this pattern occurs frequently, it might be nice to generalize this and make make something reusable out of it so we don’t have to write this code inside every class that needs ids. Perhaps we need an interface or abstract class. Tell me why these two suggestions won’t work with a detailed, technical answer. Then tell me something that will work. (Note: there is nothing wrong with the access modifiers above; the problems with my two suggestions have to do with the nature of interfaces and abstract classes.)
Given a utility class, can you always rewrite it as a singleton? Given a singleton, can you always rewrite it as a utility class? If so, when would you choose one over the other?
Explain how, in C++, you can get access to, and indeed modify, a protected component of an object that someone else declared. As a concrete example, let's say someone has declared
```
class C {protected: int x; ...};
C c;
```
then your job is to assign a new value to c.x. Assume there are no public operations of C that modify x that you know of. Also, do not use any preprocessor tricks (like #define protected public).
What makes more sense, to inherit a list from a stack or a stack from a list?
Why did the designers of the C++ standard library containers emphatically reject an inheritance hierarchy of containers?
In C++ you can write
```
class C {int x;};
C c;
C* p = &c;
cout << p;
```
and there is no compile-time nor link time error, despite the fact that operator<<(C*) is not a member of ostream (since that class was declared before you declared C), nor for that matter did anyone declare the global function
```
    ostream& operator<<(ostream&, C*);
```
So why does it all work? Explain exactly what gets printed and why.
What happens to the implementation of a C++ class if we “redefine” a field in a subclass? For example, suppose we have:
```
class Base {
    public int a;
    public String b;
}

class Derived extends Base {
    public float c;
    public int b;
}
```
Does the representation of a Derived object contain one b field or two? If two, are both accessible, or only one? Under what circumstances? Answer for C++, Java, Python, Kotlin, Scala, or any similar language.
If Dog is an abstract class in a C++ program, why is it acceptable to declare variables of type Dog*, but not of type Dog? Does this problem even make sense to ask in Java or Python?

Concurrency

Write a short paper distinguishing actors, goroutines, and coroutines, using examples from at least three programming languages.
Compare and contrast each of the following synchronization mechanisms: locks, barriers, mutexes, countdowns, semaphores, condition variables, and semaphores. For each, show how do define the mechanism in Java and in Go, if the language supports them directly, with a small example.
Discuss the difficulties of implementing a secure Post Office object in Ada, Erlang, Go, or Rust that meets the following requirements. The post office is to maintain a collection of P.O. boxes, each belonging to some task. Any task can put a letter into another task's box, but only the owner of a particular box can open it and read the letters.
A relay is an agent task created by one task to relay a message to another. For example, if a calling task wishes to send a message to another but does not wish to wait for a rendezvous, the caller can create a relay task to send the message. (Note that relays are only appropriate to use when there are no out parameters in the called entry.) Sketch in detail a body for an Java thread, Kotlin coroutine, Ada task, Erlang process, or Go goroutine that uses a relay to invoke a service of another agent, passing a message in the invocation.
In Ada, if two tasks are executing a Put procedure at the same time, their outputs may be interleaved. (This could produce amusing and even distasteful results, e.g. writing "sole" in parallel with "ash") Show how to set things up so only one task is writing at a time.
Why do Java programmers not have to worry about the situation in the previous problem (interleaving of text output written to a stream)?
One of the nice features of Quicksort is that it allows a great deal of parallelism in an implementation. After partitioning, the slices on either side of the pivot can be sorted in parallel. It is very easy to set things up to do this in languages such as occam, but tedious in Ada and Java. Code up a parallel version of Quicksort in Ada or Java and explain why it is messy.
In Ada, what happens when you try to call an entry in a task that has terminated? Comment on the following code fragment as a possible approach to calling entry E of task T only if T has not terminated.
```
if not T'Terminated then
    T.E;
end if;
```
In Java, what happens if you invoke a method on a thread that has completed?
Two JavaScript programmers are arguing over the best way to implement a little timer widget. The first programmer prefers:
```
let countDown = function () {
    let i = 10;
    let update = function () {
        document.getElementById("t").innerHTML = i;
        if (i-- > 0) setTimeout(update, 1000);
    }
    update();
}
```
The second argues that this is better:
```
let countDown = function () {
    let update = function (i) {
        document.getElementById("t").innerHTML = i;
        if (i-- > 0) setTimeout(function () {update(i)}, 1000);
    }
    update(10);
}
```
Your role is to figure out which programmer is right, if any. Make a fairly extensive list of the pros and cons of each approach. Your list will be graded on completeness, neatness, correct usage of terminology (don’t forget to mention "anonymous function" and "closure"), and how articulately you express yourself. Bad grammar will impact your grade negatively. You may want to consider readability and (especially) performance.

Metaprogramming

What is it about Ruby that make its metaprogramming facilities among the most powerful and expressive of all major programming languages?

Syntax

Suppose we added to EBNF the form $A\verb!^!B$ which denotes $A \mid ABA \mid ABABA \mid \ldots$. Such a form makes it convenient to write rules involving separators, such as
```
    IDLIST → ID ^ ","
```
This form can also be used to model a construct representing one or more $A$s, rather than using $AA^*$ or $A^*A$. Show how to do this.

Let $\varepsilon$ represent the empty string. Then we can use $A\verb!^!\varepsilon$.
Here are a few Ohm grammar rules from the Ada programming language:
```
    Exp     = Exp1 ("and" Exp1)* | Exp1 ("or" Exp1)*
    Exp1    = Exp2 (relop Exp2)?
    Exp2    = "-"? Exp3 (addop Exp3)*
    Exp3    = Exp4 (mulop Exp4)*
    Exp4    = Exp5 ("**"  Exp5)? | "not" Exp5 | "abs" Exp5
    comment = "--" ~"\n" any
```
1. What can you say about the relative precedences of and and or?
2. If possible, give an AST for the expression X and Y or Z. (Assume, of course, that an Exp5 can lead to identifiers and numbers, etc.) If this is not possible, prove that it is not possible.
3. What are the associativities of the additive operators? The relational operators?
4. Is the not operator right associative? Why or why not?
5. Why do you think the negation operator was given a lower precedence than multiplication?
6. Give an abstract syntax tree for the expression -8 * 5.
7. Suppose the grammar were changed by dropping the negation from Exp2 and adding - Exp5 to Exp4. Give the abstract syntax tree for the expression -8 * 5 according to the new grammar.
The official grammar of the C programming language has over a dozen levels of operator precedence defined within the grammar. Write this subset of C syntax using Ohm.
Describe each of the following languages in both EBNF and Ohm:
1. $\{w \in \{a,b,c\}* \mid w \mathrm{\;has\;at\;most\;one\;occurrence\;of\;any\;symbol}\}$
2. $\{a^mb^nc^{m+n} \mid m \geq 1 \wedge n \geq 1 \}$
3. Palindromes over $\{a, b\}$
4. $\{a^mb^n \mid m \geq n \}$
5. Strings of parentheses, brackets and braces, all properly balanced and nested
6. Semicolon terminated statements
7. Comma separated expressions
8. Strings over $\{a, b, c, d, e\}$ containing at most one occurrence of any symbol
EBNF generally uses
- $A\:B$ to mean exactly one $A$ followed by exactly one $B$
- $A?$ to mean zero or one $A$
- $A^*$ to mean zero or more $A$s
- $A \mid B$ to mean either exactly one $A$ or exactly one $B$
Suppose I wanted to add a new one:
- $A_1 \# A_2 \# ... \# A_n$ to mean “a non-empty string in which each of the $A_i$s appears zero or one times, but in any order.”
Show how to write $A \# B \# C$ using only the conventional EBNF markup.

$A \mid B \mid C \mid AB \mid AC \mid BA \mid BC \mid CA \mid CB \mid ABC \mid ACB \mid BAC \mid BCA \mid CAB \mid CBA$
Suppose we are designing a language and wish that no identifier could be exactly three characters long and end with "oo" (or "oO" or "Oo" or "OO").
1. Write a regex for alphanumeric strings beginning with a letter that are not three characters long ending case-insensitively with "oo".
2. Give a (lexical) Ohm rule to define identifiers as any string of alphanumerics and underscores, beginning with a letter, that satisfies our wish.
We’ve seen that one way to deal with ugly code in curly brace languages is to require blocks in compound statements; for example:
```
    IfStmt = "if" "(" Exp ")" Block
             ("else" "if" "(" Exp ")" Block)*
             ("else" Block)?
    Block  = "{" STMT* "}"
```
What if we tried the same approach in a language with a syntax like Ruby (or Fortran or Modula — languages using a terminating end)? We might get a grammar like this:
```
    IfStmt = "if" Exp "then" STMT+
             ("else" "if"  Exp "then" STMT+)*
             ("else" STMT+)?
             "end"
```
Is this grammar left recursive? Is it $LL(k)$? Why or why not? Is this bad?
Is this grammar an $LL$ grammar?
```
    A → B C
    B → a | b?c?
    C → c | BA
```
If this grammar is not $LL$, make one that is (that defines the same language of course). Give a set of syntax diagrams for the original diagram, and if another is needed, for the new grammar as well.
Here’s an Ohm grammar:
```
    S = A M
    M = S?
    A = "a" E | "b" A A
    E = ("a" B | "b" A)?
    B = "b" E | "a" B B
```
1. Describe in English, the language of this grammar.
2. Draw a parse tree for the string "abaa"
3. Prove or disprove: “This grammar is $LL(1)$.”
4. Prove or disprove: “This grammar is ambiguous.”
Here’s a grammar that’s trying to capture the usual expressions, terms, and factors, while considering assignment to be an expression.
$ \begin{array}{lcl} \mathit{Exp} & \longrightarrow & \textit{id}\;\texttt{":="}\;\textit{Exp} \;|\; \mathit{Term}\;\mathit{TermTail}\\ \mathit{Term} & \longrightarrow & \mathit{Factor}\;\mathit{FactorTail}\\ \mathit{TermTail} & \longrightarrow & (\texttt{"+"}\;\mathit{Term}\;\mathit{TermTail})? \\ \mathit{FactorTail} & \longrightarrow & (\texttt{"*"}\;\mathit{Factor} \mathit{FactorTail})? \\ \mathit{Factor} & \longrightarrow & \texttt{"("}\;\mathit{Exp}\;\texttt{")"} \;|\; \textit{id} \end{array} $
1. Prove that this grammar is not $LL(1)$.
  Both alternatives for Exp expand to a string beginning with id.
2. Rewrite it so that it is $LL(1)$.
3. Rewrite the grammar as a PEG.
4. Write the grammar using Ohm, using left-recursion.
Astro is a really tiny language, so we'd like to make Astro++. This new language adds an if-statement, a while statement, a break statement, and relational operators. The while statement should start with the keyword while, followed by a test expression, followed by a block (a curly-brace delimited sequence of statements). The if-statement should start with the keyword if, followed by a test expression, then a block, then an optional else-part which is the keyword else followed by either a block or another if-statement. Neither the while statement nor the if statement should end with a semicolon. The break statement is only allowed to appear in a while statement’s block. The relational operators are the same as those in Python and are to be NON-associative. All of the relational operators are on the same precedence level, lower than all other operators. Give the syntax of Astro++ using Ohm. Hint: Check your grammar with the Ohm Editor so that you don’t needlessly throw away points.

Regular Expressions

Write a function in the language of your choice that returns whether its input string is a three character alphanumeric string ending, case insensitively, in "oo". Do this by matching against a regular expression.
Describe, in English, the languages expressed by these regular expressions:
1. [01]*(10111[01] | 11[01][01][01][01])[01]*
2. ([bc]*a[bc]*a[bc]*)*
3. 0*1 | 0*10
4. c*a[ac]*b[abc]*
Write regular expressions that:
1. Match octal constants in C
  0[0-7]*
2. Match hexadecimal numerals divisible by 8 (signed or unsigned!)
3. Match strings that begin with unsigned 32-bit hexadecimal numerals divisible by 16
4. Match entire strings that are sixteen-bit hexadecimal numerals (signed or unsigned!) divisible by 8
5. Match entire strings that are unsigned binary numbers, of any size, divisible by 8
6. Match floating point constants that are not allowed to have an empty fractional part and can have no more than three digits in the exponent part
7. Match floating point constants that are allowed to have an empty fractional part and can have no more than four digits in the exponent part
8. Match identifiers that are strings of letters, digits, and underscores, that begin with a letter, are not allowed to end with an underscore, and cannot contain two successive underscores anywhere in the text.
9. Match non-empty words consisting of the letters a-z whose first and second halves are the same (i.e., in set notation: {ww | w ∈ {a..z}+})
10. Match entire character strings that contain neither the substring "return" nor "retry"
11. Match entire strings of that must be made up of lowercase Basic Latin letters only and that contain neither the substring "exit" nor "exec"
12. Match entire strings that contain neither the substring "exit" nor "exec"
13. Match all words in a string (use \b for word boundaries) that are preceded by the word “the”.
14. Match words containing two adjacent double-letters.
15. Match strings of digits not preceded by a dash.
  (?<!-|\d)\d
Write JavaScript regular expressions for the following. Please take advantage of character classes, lookarounds, and backreferences where they apply.
1. Canadian Postal Codes (make sure to prohibit D, F, I, O, Q, U)
2. Legal Visa® Card Numbers, ignoring the Luhn checksums, i.e., accept 4 + 15 digits or 4 + 12 digits.
3. Legal MasterCard® Numbers, ignoring the Luhn checksums, i.e., accept 51-55 + 14 digits or 2221-2720 + 12 digits.
4. Strings of Basic Latin letters except those strings that are exactly three letters ending with two Latin letter o’s, of any case.
5. Binary numerals divisible by 16.
6. Decimal numerals in the range 8 through 32, inclusive.
7. All strings of Unicode letters, except python, pycharm, or pyc.
8. Floating point constants that are allowed to have an empty fractional part, but whose exponent part is required and can have no more than three digits in the exponent part
9. Palindromes over the letters a, b, and c, of length 2, 3, 5, or 8
10. Python string literals. Don't get too fancy here—just translate what you see in the Python Reference linked above into Ohm notation.

Language Features

C does not allow structures (i.e., non-atomic objects) to be tested for equality. Ada does. Maybe the designers of C wanted to keep things simple. How exactly would equality operations for structures complicate a C compiler or the runtime system?
If possible, write a program in Modula 3 that makes a variable point to itself. That is, for some designator X, make it so that X^ = X. If this is not possible, state why it is not possible.
If possible, write a program in Ada that makes a variable point to itself. That is, for some designator X, make it so that X.all = X. If this is not possible, state why it is not possible.
If possible, show how to make a Standard ML variable x of type x such that x.x = x, or state why this is impossible.
In C++ you can say (x += 7) *= z but you can’t say this in C. Explain the reason why, using precise, technical terminology. See if this same phenomenon holds for conditional expressions, too. What other languages behave like C++ in this respect?
Consider the continue statement of C.
1. What kind of static semantic checks are required for this statement?
2. Give an example piece C code that has a continue statement in it, and show the intermediate and target code for it.
Some languages do not require the parameters to a subprogram call to be evaluated in any particular order. Is it possible that different evaluation orders can lead to different arguments being passed? If so, give an example to illustrate this point, and if not, prove that no such event could occur.

Ada allows subprograms to be objects, as in the following code fragment:

type Real_To_Real is access function (Real) return Real;
type Foo is access procedure (Integer; in out Boolean);
Sine, Cosine: Real_To_Real;
P: Foo;
Q: Real_To_Real;
function Integrate (F: Real_To_Real; A, B: Real);
...
function Square (X: Real) return Real is
begin
    return X * X;
end;
...
Put (Integrate(Square'Access, 3, 10));
Q := Cosine;
if Q(Pi) > X then ...

Describe the semantic rules relating to this facility in Ada, and how you would enforce them in a compiler.

It is a well-known irritation that Ada does not allow you to write array aggregates for zero- or one-element arrays, e.g., A := (3) gives a static semantic error when $A$ is a one-element array of Integer. Why is this so? Propose a (trivial) syntactic extension to Ada that would remove this irritation.
In Ada, the declarations
```
X: Integer := X + 1;
Foo: Foo;
Bar: Real := Bar(Foo);
```
(where global declarations of X, Foo and Bar are visible) are all illegal, since a declaration of an identifier hides global declarations of the same name immediately at the point it appears in the text, but the identifier may not be used until its declaration is complete. Give an alternate interpretation under which these declarations would be legal and explain the advantages and disadvantages of it from both the programmer’s and the compiler writer’s perspectives.
In C++ it is not permitted to have two functions that differ only in return type overload each other. In Ada it is allowed. What is the reason for this situation? Even though Ada does allow this flexibility in overloading, the compiler needs some sophistication. What exactly is involved? Be very precise in your explanation and illustrate it with code fragments.
Some programming languages require that in order to have mutually recursive functions, the programmer first define the first function’s signature (name, return types, parameters and parameter types), then the entire second function, then the entire first function. For example, in C++:
```
int f(int x, char y);
void g(int x) {if (x < 0) f(2, 'c');}
int f(int x, char y) {g(randomInteger());}
```
In C++, when f is finally declared, the names of the formal parameters don’t have to be repeated exactly as they appeared in the incomplete specification. But in Ada they do. Explain why the Ada rule makes life much easier for the compiler writer.
Many languages have a syntax rule
```
    DESIGNATOR  →  DESIGNATOR  "."  ID
```
for specifying variables made up from a record and a field of the record. But sometimes it can have the additional interpretation that the DESIGNATOR to the left of the dot was the name of a (visible) subprogram and the ID was an object declared immediately inside that subprogram. Show how to rearchitect the entity class hierarchy to support this.
An online troll suggested that JavaScript was really confusing because it uses square brackets for array expressions, instead of simple parentheses. "After all," this person says, "in English we don’t use square brackets much if ever, so it should have had regular parentheses." Can we change JavaScript to work this way, and in doing so, affect only array expressions, that is, not cause any ambiguities in existing JavaScript code not involving arrays? If so, show what the following would look like:
1. The assignment of a four-element array expression to a variable
2. The assignment of a one-element array expression to a variable
3. The assignment of a zero-element array expression to a variable.
and explain why your solutions satisfy the restriction that the change only affects expressions with array expressions.
How do JavaScript and Rust treat the following:
```
let x = 3;
let x = 3;
```
Describe how the languages Java and Ruby differ in their interpretations of the meaning of the keyword private. You can use an AI assistant for help, but please trim down the long-winded applications those tools are known for, and give a concise explanation that proves you truly understand the difference.
Some languages do not require the parameters to a function call to be evaluated in any particular order. Is it possible that different evaluation orders can lead to different arguments being passed? If so, give an example to illustrate this point, and if not, prove that no such event could occur.
Some languages do not have loops. Write a function, using tail recursion (and no loops) to compute the minimum value of an array or list in Python, C, JavaScript, and in either Go, Erlang, or Rust (your choice). Obviously these languages probably already have a min-value-in-array function in a standard library, but the purpose of this exercise is for you to demonstrate your understanding of tail recursion. Your solution must be in the classic functional programming style, that is, it must be stateless. Use parameters, not nonlocal variables, to accumulate values. Assume the array or list contains floating-point values.

Your friend creates a little JavaScript function to implement a count down, like so:

function countDownFrom10() {
  let i = 10;
  function update() {
    document.getElementById("t").innerHTML = i;
    if (i-- > 0) setTimeout(update, 1000);
  }
  update();
}

Your other friend says “Yikes, you are updating a non-local variable! Here is a better way:”

function countDownFromTen() {
  function update(i) {
    document.getElementById("t").innerHTML = i;
    if (i-- > 0) setTimeout(update(i), 1000);
  }
  update(10);
}

What does your second friend’s function do when called? Why does it fail? Your friend is on the right path though. Fix their code and explain why your fix works.

Abstract Syntax

Draw the AST for the following JavaScript program, using the level of detail we used during class. You can use my JS AST Viewer to guide you and check your work, but remember, the drawing you need to produce for full credit will be far less verbose than the tool’s output. (Remember, the tool uses a third-party parser, esprima-next, that provides a complete ESTree-compliant AST, which is far more verbose than expected for hand-drawn ASTs.)
```
let [x, y] = [0, 0];
console.log(93.8 * 2 ** x + y);
```

Draw the AST for the following JavaScript program.

import x from "x"
console.log(93.8 * {x} << x.r[z])

Draw the AST for the following JavaScript program.
```
const x = x / {[x]: `${x}`}[x]("y")
```
For the following JavaScript fragment (not a complete program), draw the AST.
```
class C {
  f({a, b: c}) {return ([a,f]) => C}
}
```

Draw a JavaScript abstract syntax tree for the following script.

let [x, y] = Array.repeat(10|-2, 2);
function f({x, y}, ...p) {
  return q => `"Say ${y/p[0].x} today`;
}

Show a Java abstract syntax tree for:

static protected synchronized long g(Object... m) {
    for (int y : f(x)) {
        x = p.data[0] * (3<<   7|-  x---c);
    }
}

Draw the abstract syntax tree for the following C fragment:

for (int i = x-3; q<=4&m.z[r |- 4]&2-8*r>- 5/~x;) {
    while (a) {
        y;
        2,y;
    }
}

Draw the abstract syntax tree for this C function declaration:

void f(int x,...) {
    struct e {
        double x;
        struct e *c[10];
        char* (*f)();
    };
    struct e p;
    exit(p.c[1]->f()[6 |~ x+2 >> x]);
}

Draw the abstract syntax tree for this C function declaration:
```
int abc() {
      return x = 4&x---*&y.m[-9];
}
```

Give an abstract syntax tree for the following Java code fragment:

if (x > 2 || !String.matches(f(x))) {
    write(-3 * q);
} else if (! here || there) {
    do {
       while (close) tryHarder();
       x = x >>> 3 & 2 * x;
    } while (false);
    q[4].g(6) = person.list[2];
} else {
    throw up;
}

Draw the abstract syntax tree for the following Java compilation unit. (Make sure it is fairly abstract):

package p;
class C implements A {
    public static A x = new   t[3];
    Socket s () {
        while (x -  6>p  |    e || q +- p) {
            this.x[3] = !v+++t;
        }
    }
    {System.out.println("ooh");}
}

Draw the AST for the following C fragment:

(a = 3) >= m >= ! & 4 * ~ 6 || y %= 7 ^ 6 & p

Assembly and Machine Language

Write an assembly language program that displays a multiplication table of size 12 × 12.
Write in assembly language a translation of the following C function
```
double f(int x, double y) {
    return 4 * x + y;
}
```
Under what circumstances can you safely replace the x86 code fragment
```
        je    L6
        jmp   L4
L6:
```
with the single instruction jne L4?
Show that the addressing modes immediate, absolute memory, and register indirect can be simulated by register and register-offset alone.
Show the target code that is generated for the source statement X := Y; where X and Y are both 32-bit integers that are one step down the static chain from the current subprogram, by a code generator which emits access code for the two values independently. Assume $X$ is at offset $-8$ and $Y$ is at offset $-12$. How many registers are used? Then generate code for this statement by hand, intelligently.
Suppose the variable $A$ was declared in an Ada program with
```
type array (21..38) of String(1..10)
```
and happened to have offset $-42$ in the frame of the subprogram in which it was declared. Suppose further that the variable J was declared in the same subprogram and had offset $-26$.
1. Show the target code that loads the value of A(J-1) into register eax that would be generated naïvely. Do not forget to show the bounds checking!
2. Show target code to load the value of A(J-1) into register eax in which the "-1" computation is folded in to the computation of the base address of A. Note that the bounds checking code will look a little different than in part (a).
Write an assembly language program that takes zero or more command line arguments, which should all be integers, and displays the average of the parameters to standard output.
Occasionally a compiler may output a sequence such as
```
        mov    [ebp-8], eax
        mov    eax, [ebp-8]
```
The second instruction might be able to be removed. But whether we are able to remove this instruction is undecidable. Why, exactly?
The x86 has an enter instruction which automatically makes a display. Research this instruction. Suppose a Carlos program had the following structure (indentation determines nesting):
```
    function f, parameters: [x,y], locals: [a]
        function g, parameters: [c], locals: [p,q,r,s]
            function h, parameters: [a], locals: []
        function k, parameters: [], locals: [z]
```
1. Show what the runtime stack looks like from the call sequence f→g→k→g→h→h→f→k
2. What does the generated assembly language look like when trying to access the value of f.x from h?
3. Which parts of the Carlos compiler need to be rewritten to use this instruction?
The ENTER instruction is rarely used because it is slow. Show how slow it is by doing the following. Prepare a table with four columns. The left column will be:
```
    enter n, 0
    enter n, 1
    enter n, 2
    enter n, 3
    ...
```
and so on. The second column will be the number of clock cycles required on a Pentium for the particular ENTER instruction. The third column will be code equivalent to the ENTER instruction. For example, ENTER n, 1 is equivalent to:
```
    push ebp
    mov  ebp, esp
    push ebp
    sub  esp, n
```
The fourth column will be the number of clocks for the code in column 3.
Show x86 code for the expression
```
    x / y > (3 * x) || z || x < 3
```
where the "||" operator is short-circuit, and the variables $x$, $y$, and $z$ are all integer variables. Put the value of the expression in eax. Write the best possible code you can for the Pentium 4 processor.
Write an assembly language function to compute $\frac{\sin(\log(x))}{y-7}$ where $x$ and $y$ are two double (64-bit float) parameters. Use the x86 C calling convention. Also write a C program that calls the function and displays the result.
Write an assembly language function to compute the log base a of b, where x and y are two double (64-bit float) parameters. Use the x86 C calling convention. Write a C program for the unit tester (with at least 10 assert statements).
Write an assembly language function to compute $\frac{y}{\sin \log \mathrm{atan2}(y,x)}$ where $x$ and $y$ are two double (64-bit float) parameters. Use the x86 C calling convention.
Write an x86 assembly language program that sets every third byte of the three megabyte section of memory starting at address $b$. Use the MMX registers.
Write an assembly language function that returns the dot product of two single-precision floating point arrays using the XMM registers. Implement a unit tester in C.
Write an x86 assembly language function that returns the sum of the reciprocals of all the elements in an array of doubles. Use the C calling convention (so the function accepts the array and a length).

Write an assembly language version of the following, using an LEA instruction for the 3n+1 computation:

    int C(int n) {
        int count = 0;
        while (n != 1) {
            n = (n % 2 == 0) ? n / 2 : 3 * n + 1;
        }
        return count;
    }

Show both naive and optimized intermediate code (entity graph), and both naive and optimized assembly language for:
```
    if (x % 4096 == 0) {printf("Don't say \66;\6f;\6f;!");}
```
Hint: you need strength reduction, too.
One kind of strength reduction is replacing division by a power of two with an arithmetic right shift, for example
```
    sar eax, 10          to divide by 1024
    sar eax, 8           to divide by 256
```
This optimization is not safe. Explain why. Show how to make it safe, and explain both why your optimization works and why it is safe.
Write an x86 assembly language function that takes in four doubles and returns the product of the largest and the smallest argument. Assume the function will be called from a C program built under gcc running on a Pentium II or above. Note that you need to respect the calling convention. Do not use conditional jumps in your code.
Give highly optimized x86 code for the following:
```
    for j := 5 to y do
        y := j * 7 + c;
        printInteger(y - 4);
    end loop;
```
where y and c are local variables in the current procedure at offsets -12 and +16 respectively. Remember that the range is evaluated only once, the whole loop is skipped on the empty range, etc.). Make sure you respect the overflow semantics! Identify any induction expressions and explain how you optimized them. Compare your hand-written code with that generated by a real compiler.
Write an x86 assembly language function to return the product of its input (which must be a double) and 7.0, without using multiplication or loops. USE AT MOST 4 ADDITIONS. The return type is double. Assume the function will be called from a C program built under gcc.
Write the following in assembly language (use the C calling convention). It is supposed to compute a*log₁₀(b). Use the fyl2x and fldl2t instructions.
```
    double f(double a, double b);
```

What does this code do? For what ranges of n does it make sense?

    mov eax, n
    shl eax, 23
    add eax, 3f800000h
    mov [esp-4], eax
    fld dword [esp-4]

Generate code for the following basic block:

    y := x * 4 + z;
    z := p * y;
    y := z;
    x := z / y << x;

Runtime Systems

A naïve way to implement a runtime system for a language with exceptions is to place two return addresses in an activation record. Sketch a small Ada or C++ function that can throw (a possibly user-defined) exception, and a code fragment that calls the function. Give a stack frame layout with two return addresses, one is the normal return address and the other is the address of the handler in the caller. Show the assembly language for the caller and the function itself.
Discuss advantages and disadvantages of a subprogram call implementation in which (a) the calling subprogram saves all registers and (b) the called subprogram saves all registers. Explain why the x86’s C calling convention is a nice compromise.
In a language that supports recursion, there may be multiple activations of a subprogram on the dynamic chain, and hence stack allocations of frames are generally used. However, subprograms that do not themselves make calls need not use stack frames. More generally, any subprogram that can never appear twice on a dynamic chain does not require a stack frame. Describe how to compute the set of all such subprograms at compile time.
What exactly must be the case for a subprogram to not need a static link in its stack frame? Think up as many cases as possible.
In Ada, C, and C++ arrays and records (structs) can be allocated on the stack, not just on the heap. When making assignments of aggregates to variables, compilers usually generate code to deposit the values in temporary storage. Why is this necessary in general? After all, in
```
    Weekdays := Day_Set(False, True, True, True, True, True, False);
```
we could construct the aggregate directly in the variable Weekdays. Give an example of an assignment statement that illustrates the necessity of constructing an aggregate in temporary storage (before copying to the target variable).

Errors

Classify the following as a syntax error, static semantic (contextual) error, or not a compile time error. In the case where code is given, assume all identifiers are declared, have the expected type, and are in scope. All items refer to the Java language.
1. x+++-y
2. x---+y
3. incrementing a read-only variable
4. code in class C accessing a private field from class D
5. Using an uninitialized variable
6. Dereferencing a null reference
7. null instanceof C
8. !!x
9. x > y > z
10. if (a instanceof Dog d) {...}
11. var s = """This is weird""";
12. switch = 200;
13. x = switch (e) {case 1->5; default->8;};
Identify the following errors as syntactic, static semantic, or dynamic semantic (runtime): If no language is mentioned for a particular case, it probably does not matter. Assume either C or Ada and write your assumption.
1. Redeclaration of an identifier.
2. Unbalanced parentheses.
3. Applying an operator to an element of the wrong type.
4. Array index out of bounds (in C, in Ada, ...).
5. Division by zero.
6. Semicolon after a block in C.
7. Wrong number of arguments supplied to a call.
8. Assignment of a variable of type T to a variable of type subtype of T where the first variable is out of the range of the second in Ada.
9. An unwanted infinite loop.
10. Dereference of a null pointer.
11. Application of the "." to an identifier which is not a field of the record.
12. Use of an uninitialized variable.
Which if the following expressions are legal in Java (assuming $x$ and $y$ are integer variables)? State why they are legal or why they are not.
1. x---y
2. x-----y
Classify the following as a syntax error, semantic error, or not a compile time error at all. In the case where code is given, assume all identifiers are properly declared and in scope. All items refer to the Java language.
1. x+++-y
2. x---+y
3. incrementing a read-only variable
4. accessing a private field in another class
5. Using an uninitialized variable
6. Dereferencing a null reference
7. null instanceof C
8. !!x
Classify the following as (a) lexical error, (b) syntax error, (c) static semantic error, (d) dynamic semantic error, or (e) no error.
1. A function call with no matching signature in Java.
2. A function call with no matching signature in C.
3. x < y < z in Carlos, where x and y are ints and z is a boolean.
4. x < y < z in C, where x and y and z are all ints.
5. 3[a] in Carlos, where a is an array variable.
6. 3[a] in C, where a is an array variable.
7. char x = '\a'; in Carlos.
8. char x = '\a'; in C.
9. Value returning function without a return statement, in Carlos.
10. Value returning function without a return statement, in C.
11. Semicolon after a block, in Carlos.
12. Semicolon after a block, in C.
Classify each of the following, assuming a typical statically typed language, as a (a) lexical error, (b) syntax error, (c) static semantic error, (d) dynamic semantic error, or (e) no error.
1. Invoking an array constructor that accepts a length and produces an empty array of that length, with a negative argument
2. Semicolons instead of commas in identifier lists
3. An identifier that is 33 characters long
4. Applying a length operator or function to a read-only array variable
5. Applying a length operator to a struct
6. Applying the sin standard function to an integer
7. The expression x < y < z where $x$ and $y$ are integers, and $z$ is a boolean.
8. Having the wrong number of arguments in a struct’s constructor.
1. Dynamic semantic
2. Syntax
3. No error
4. No error
5. Static semantic
6. No error
7. Syntax
8. Static semantic
Find as many linter errors as you can in this Java source code file (C.java):
```
import java.util.HashMap;

class C {
    static final HashMap<String, Integer> m = new HashMap<String, Integer>();

    static int zero() {
        return 0;
    }

    public C() {
    }
}
```
You can use SonarLint or FindBugs or FindSecBugs or PMD or whatever you prefer. You might even need to use a combination of tools because it is possible no tool finds them all. (Please note you are not expected to already know what all the issues are here. The idea is to practice with tools and have good discussions with teammates. Find as many as you can, and read and understand each problem that is reported to you so you learn (1) what kinds of potential bugs and security problems can exist even in compilable and runnable code, and (2) the kinds of things that a static analyzer can detect.)

Compilation in Practice

Find, and link to, real-life examples of self-hosting and cross compilers.
Suppose a new computer called the X1234 has just come out and it doesn’t have a Swift compiler. But you want to make a resident Swift compiler on that machine. Fortunately you have a resident Swift compiler that runs on a MIPS machine. Describe exactly how you can construct the desired resident Swift compiler for the X1234 using the one for the MIPS.

Programming Problems

Keep sharp by practicing your programming skills.

Write a function or method (in as many languages as you can) that randomly permutes a string. You should be able to permute the characters in the string easily in most languages, but if your language supports a way to get the graphemes of a string, then scramble those.
Write a function or method (in as many languages as you can) that generates powers of some base and sends them to a callback as they are generated, up to some limit.
Write a generator function (in as many languages as you can, provided they support generators) that generates powers of some base up to some limit.
Write a function or method (in as many languages as you can) that doubles each item in an list, e.g. for input [1,2,3], the output is [1,1,2,2,3,3]. If your language allows adding methods to an array class (or provides for extensions), use that feature.
Write a command line script (in as many languages as you can) that writes successive prefixes of its first input argument, one per line, starting with the first prefix, which is zero characters long.
Write a command line script (in as many languages as you can) that reports the number of non-blank, non-commented lines in the file named by the first argument. Blank lines are those that have either no characters or consist entirely of whitespace; commented lines are those that begin with the # character.
Write a function (in as many languages as you can) that accepts a number of U.S. cents and returns a tuple containing, respectively, the smallest number of U.S. quarters, dimes, nickels, and pennies that equal the given amount. If your language has adivmod operator, write two solutions, one using the operator and one that does not.
Write a function (in as many languages as you can) that accepts a string and returns the string which is equivalent to its argument but with all ASCII vowels removed.
Consider the problem of determining whether two trees have the same fringe: the same set of leaves in the same order, regardless of internal structure. An obvious way to solve this problem is to write a function fringe that takes a tree as argument and returns an ordered list of its leaves. Then we can say:
```
def same_fringe(t1, t2):
    return fringe(t1) == fringe(t2)
```
However, fully computing the fringes of both trees is extremely inefficient, given that you should be able to return false at the first mismatch, so the fringes should be computed lazily. Write an efficient (lazy) version of same_fringe in as many languages as you can.
Write a function (in as many languages as you can) that interleaves two lists. If the lists do not have the same length, the elements of the longer list should end up at the end of the result list. For C++, write this three ways: using C-style arrays, using std:array, and using std::vector.
Write (in as many languages as you can) two functions (called f and g) such that every time you call f, you get back 10 less than the result of the previous call to f or g, and every time you call g, you get back three times the absolute value of the result of the last call to f or g. Here's a catch: you must arrange things so that any "state" you need is completely private to f and g.
Write a function (in as many languages as you can) to return the number of Basic Latin vowels in a string, as a one liner making use of regular expressions if your language supports them.
Write a function (in as many languages as you can) to return whether a given string is in the set, using regular expression matching.
1. Strings of characters beginning and ending with a double quote character, that do not contain control characters, and for which the backslash is used to escape the next character. (These are similar to, but not exactly the same as, string literals in C.)
2. The paren-star form of comments in Pascal or ML: strings beginning with (* and ending with *) that do not contain *). Note comments "don’t nest".
3. Numbers in JSON.
4. All non-empty sequences of letters other than "read", "red", and "real".

Given this starter code for a Python binary tree:

class BinaryTree:
    pass
class Empty(BinaryTree):
    def size(self):
        return 0
class Node(BinaryTree):
    def __init__(self, data, left, right):
        self.data = data
        self.left = left
        self.right = right
    def size(self):
        return 1 + self.left.size() + self.right.size()

Implement methods preorder, inorder, postorder, height, and width.

Given this starter code for a Haskell binary tree:

data BinaryTree a = Empty | Node a (BinaryTree a) (BinaryTree a)

size: BinaryTree a -> Int
size [] = 0
size (Node data left right) = 1 + size left + size right

Implement functions preorder, inorder, postorder, height, and width.

Implement a concurrent priority queue in Ada two ways: (1) with a server task to provide synchronization and (2) with a protected object.
Implement a concurrent priority queue in Go two ways: (1) with a goroutine to provide synchronization via select statements and (2) using a mutex.

Program Analysis

There are a number of skills beyond just slinging code that will set you apart from peers. These include being able to explain what programs are saying (or doing), being able to explain why certain programs are incorrect or insecure, and being able to explain why certain programs are correct or secure. Here are a few such problems.

Consider this Python script:
```
a = [lambda: i for i in range(10)]
b = [a[i]() for i in range(10)]
```
At the end of this script, what is the value of b? Explain in detail why this is. Support your analysis with a sketch.
Consider this old-fashioned JavaScript script that uses the hated var that you should never use in your own code:
```
var a = [];
for (var i = 0; i < 10; i++) {
    a[i] = function () {return i;}
}
var b = [];
for (var j = 0; j < 10; j++) {
    b[j] = a[j]();
}
```
At the end of this script, what is the value of b? Explain in detail why this is. Support your analysis with a sketch.
For each of the following code fragments, explain what happens when evaluating them. Make sure you convey in your explanation a thorough understanding of Ruby objects, classes, singleton classes, etc.
```
dog="spike"; class <<dog; def bark = "arf"; end; dog.bark
```
Evaluates to "arf", since we essentially gave this one dog its own bark method, by attaching it to its own singleton class.
```
class <<"sparky"; def bark = "woof"; end; "sparky".bark
```
```
class <<"sparky"; def bark = "woof"; end; "sparky".bark
```
```
dog="sparky"; class <<dog; def bark = "woof"; end; dog.bark
```
Evaluates to "woof", because we attached the bark method to the object referenced by the variable dog, through its metaclass.
```
class <<"sparky"; def bark = "woof"; end; "sparky".bark
```
Raises a NoMethodError because the object in whose metaclass we added the bark method WAS NOT the same string object we tried to call bark on.
```
class <<:sparky; def bark = "woof"; end; :sparky.bark
```
Raises a TypeError because Ruby does not allow metaclasses on symbol objects. Maybe this is because Ruby treats symbols in such a super-special way an never puts them in the object pool. It probably holds them as plain old small integers.
```
class <<2; def bark = "woof"; end; 2.bark
```
raises a TypeError for the same reason as for symbols.
```
class Counter
  attr_reader :val; @val = 0; def bump(); @val += 1; end
end
Counter.new.bump; Counter.new.val
```
A programmer tried to write a Ruby dot-product method.
1. Their first attempt was:
```
def dot(a, b)
  a.zip(b).map{|x,y| x*y}.inject{|x,y| x+y}
end
```
  but a unit test failed. What was this test, and why did it fail?
  The first unit was assert_equal(dot([], []), 0) and it failed because her method returned nil, not 0.
2. They fixed that problem with:
```
def dot(a, b)
  a.zip(b).inject(0){|x,y| x+y[0]*y[1]}
end
```
  but when running a unit test with the first array longer than the second, a TypeError was raised. They fixed by raising an ArgumentError if the arguments to dot had different lengths. Show the fixed up method.
```
def dot(a, b)
  raise ArgumentError if a.length != b.length
  a.zip(b).inject(0) {|x,y| x+y[0]*y[1]}
end
```
3. Then they got fancy and put her method into the array class:
```
class Array
  def *(a)
    # working code here
  end
end
```
  And the unit tests worked: [3,4,2] * [1,5,0] == 23 for example. But this fancy * definition had a very nasty side effect, which, if she did this in real production code, would have probably broken something big time. Why is this solution so dangerous?
  There is already a * operator in the array class; any new definition replaces the old one. Old code using Array * int and Array * string will break badly, because ints and strings can’t be converted to arrays.

What's wrong with this Java code, if anything, and why?

class Pair implements Cloneable {
    private Object first, second;

    public Pair(Object x, Object y) {first = x; second = y;}
    public first() {return first;}
    public second() {return second;}
}

Optimization

Give three examples of how aliasing can occur (you can use examples from several different languages). How does aliasing make copy propagation difficult? When, if ever, can an algorithm determine that a entity cannot possibly be aliased?
Optimize the following. Show your work (that is, show a few intermediate steps toward your final solution, recording the optimizations you performed. You can abbreviate CP=copy propagation, CF=constant folding, DCE=dead code elimination. You’ll want to use more than just these three techniques.
```
    L1:
        r0 := x
        z := 6
        r1 := 4 - r0
        r2 := 3 >= r1
        if r2 == 0 goto L2
        r3 := y + 4
        r4 := *r3
        z := r4
    L2:
```

Write, by hand, a super-efficient Squid fragment for the following Carlos fragment:

    struct s {int x; int y; string s;}
    s a = new s {
        codepoint(getChar()), codepoint(getChar()), getString()};
    while (a.x++ < a.y) {print($a.s[1]);}

Here’s some Hana code that prints the elements of an integer array separated by commas:
```
    for (int i = 0; i < #a; i++) {
        print($a[i]);
        print(", ") if (i != #a-1);
    }
```
With optimizations turned off, my compiler produces:
```
p0:
  copy 0, i1
L0:
  copy [i0-4], r0
  less i1, r0, r1
  jz r1, L1
  assert_not_null i0
  copy [i0-4], r2
  assert_in_range i1, 0, r2
  mul i1, 4, r3
  add i0, r3, r4
  copy [r4], r5
  to_string r5, r6
  param r6
  call __print, 4
  copy [i0-4], r7
  sub r7, 1, r8
  not_equal i1, r8, r9
  jz r9, L2
  param s0
  call __print, 4
L2:
  inc i1
  jump L0
L1:
  exit
s0:
  [44, 32]
```
1. Describe, in high-level terms, what each of the assert tuples are doing. Are both of them necessary? Why or why not?
2. Rewrite this code fragment showing what it would look like without using the variable i (but rather stepping through the array elements by incrementing an internal pointer). Note that this problem does not require you to know anything about how optimizers work. You are only being asked to show off your understanding of Squid to come up with a super-efficient Squid tuple sequence for a specific algorithm.
Suppose we have a compiler in which the ASTs for short-circuit or-expressions were modeled as binary expressions, instead of as a single node with two or more disjuncts.
1. Draw the AST for x || y || z under this assumption.
2. Write out the tuple sequence produced by a naive translation of this tree.
3. Write out a more efficient sequence of tuples (Hint: only one temporary should be needed).
4. How would an optimizer detect that sequence is lousy (by looking only at the tuples)? What kind of transformations would an optimizer do (at the tuple level) to turn the lousy tuple sequence into the good one?
5. Explain how treating these operators an $n$-ary rather than binary, simplifies this issue a great deal. Use a tree grammar in your explanation.

Code Generation

For the following C function:
```
int f(const int n) {
  return n % 2 == 0 ? n / 2 : 3 * n + 1;
}
```
give both a highly optimized WebAssembly translation and a highly optimized x86-64 translation. You do not have to do this by hand; instead, use the Compiler Explorer, and set the optimization to -O3. Include comments in the translated code.

Little Languages

Here is a cool little functional language:
```
PROGRAM →  (DECL ';')* EXPR
DECL    →  'val' ID '=' EXPR
        | fun ID '(' PARAMS? ')' '=' EXPR
EXPR    →  NUMLIT | ID | UOP EXPR | EXPR BOP EXPR
        | EXPR '?' EXPR ':' EXPR |  ID '(' ARGS? ')' | '(' EXPR ')'
PARAMS  →  ID (',' ID)*
ARGS    →  EXPR (',' EXPR)*
UOP     →  '-' | 'abs' | 'not'
BOP     →  '+' | '-' | '*' | '/' | 'mod' | 'and' | 'or' | '==' | '<'
```
1. Why is this called a functional language?
2. Is the grammar ambiguous? Why or why not?
3. Give a hierarchy of entity classes for this language.
4. Write a Greatest Common Divisor function in this language.
5. Give three examples of syntax errors and three examples of static semantic errors in this language. Make sure to write down all your assumptions; I did not give you any semantics so you will have to make up something reasonable.
Here is a small expression language:
```
    Exp     →  Exp Exp op  | intlit
    op      →  "+"  |  "-"  |  "*"  |  "/"
```
1. What language is this?
2. Is the grammar ambiguous? Why or why not?
3. Is it $LL(k)$ for any $k$? If so, for which $k$? If not, why not?
4. Give a class hierarchy of entities for this language.
5. Give an attribute grammar for this language that can be used to evaluate expressions.
6. Give an attribute grammar for this language that attaches a "nesting level" to each identifier. You will have to make a slight modification to the original grammar for this to make sense.
This little language looks like an abstraction of something you might see in a real programming language. What, exactly? And is the grammar $LL(k)$?
```
    G -> (S s G)?
    S -> V q e | i f E g | V x
    V -> i | V d i | V a E a
    E -> n | V
```

Remove the left recursion from this grammar:

    B -> (a|b)*A | bba*c
    A -> Ac | d

Consider a language for describing vector graphics. An example program in this language (formatted ugly to highlight the fact that line breaks do not matter) is:

    down deg color 1 0 0 left
    90 forward 4 color 0 0 1 [ left 90
    forward 1.5 ] right 90 forward 1.5 up

This program draws the letter T with a red vertical line of size 4 units and topped with a 3 unit blue line. A program is a sequence of instructions. The instructions are:

Instruction	Description
`deg`	switch to degree mode
`rad`	switch to radians mode
`down`	put the pen down so movements draw lines
`up`	pick the pen up so movements don't draw anything
`left θ`	turn counterclockwise by angle `θ`
`right θ`	turn clockwise by angle `θ`
`forward n`	draw a line by moving forward n units.
`backward n`	draw a line by moving backward n units.
`color r g b`	set color (r,g,b), values are floats in the range 0 to 1.
`[`	save current state
`]`	restore previously saved state

Give an Ohm grammar for this. Also answer: is it even possible to give an unambiguous CFG for this language? Why or why not?

Here is a description of a language. Programs in this language are made up of a possibly empty sequence of function declarations, followed by a single expression. Each function declaration starts with the keyword func followed by the function’s name (an identifier), then a parenthesized list of zero or more parameters (also identifiers) separated by commas, then the body, which is a sequence of one or more expressions separated (NOT terminated) by semicolons with the expression sequence terminated with the keyword end. Expressions can be numeric literals, string literals, identifiers, function calls, or can be made up of other expressions with the usual binary arithmetic operators (plus, minus, times, divide) and a unary prefix negation and a unary postfix factorial (!). There’s a conditional expression with the syntax y if x else z. Factorial has the highest precedence, followed by negation, the multiplicative operators, the additive operators, and finally the conditional. Parentheses are used, as in most other languages, to group subexpressions. Numeric literals are non-empty sequences of decimal digits with an optional fractional part and an optional exponent part. String literals delimited with double quotes with the escape sequences \', \", \n, \\, and \u{hhhhhh} where hhhhhh is a sequence of one-to-six hexadecimal digits. Identifiers are non-empty sequences of letters, decimal digits, underscores, at-signs, and dollar signs, beginning with a letter or at-sign, that are not also reserved words. Function calls are formed with an identifier followed by a comma-separated list of expressions bracketed by square brackets. Comments are -- until the end of the line. Write a single example program that covers every aspect of this definition.
For the language described in the previous exercise, write a complete syntactic description of this language in Ohm. (Hint: use the Ohm editor to check your work. Use your everything-program from the previous exercise as a positive test, but write a few negative tests, too, so that you can check that your grammar does not “match too much.” When grading, I will copy-paste your submitted solution into the Ohm editor with my own detailed test suite).

To→ From↴	Bool	Num	Str	Arr	Dict
Null	false	0	""	[]	{}
Bool		false→0 true→1
Num	0→false else true
Str	""→false else true
Arr	[]→false else true
Dict	{}→false else true
Fun	true