Do you like spaced repetition learning? Have you used Anki or Quizlet? Whether or not spaced repetition works for you, periodically working on flash-card like questions can be a lot of fun, and just may help you retain information. Here are a few problems tied to the course material. Visit them periodically, and feel free to use them in your own spaced repetition learning practice!
Most of the reinforcement questions here deal with language-independent concepts. You should also practice with the language-dependent questions as well.
Most of the reinforcement questions for this class are found on the course notes themselves. So only a few are included here:
/ operator of a PEG and the | operator of a context-free grammar. (Hint: show a case in which the language defined by two “look-alike” grammars, one PEG, one CFG, are different. A ← "a" / "ab" only matches "a", while the similar CFG defines the language {a, ab}.
var x = 2;
function f() { print x; }
function g() { var x = 5; f(); print x; }
g();
print x;
var x = 1;
function f() {return x;}
function g() {var x = 2; return f();}
print g() + x;
let x = 3; let x = 3;
-2**2 in JavaScript and Python. Explain why the evaluation produced the value it did in each language.a+(b-c) and (a+b)-c produce different results?
var x = 5
function f() { x = x * 3 }
function g() { x = x * 5 }
function h(a, b) { return a + x }
print(h(f(), g()))
fallthrough was added.Array but in other languages like Java, Rust, and Swift there exist many parameterized array types?x ? y : z of a typical statically-typed language, what type checking and inference rules would a compiler be required to enforce? 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.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. But many are worth doing for the practice.
8 * (13 + 5), assuming a grammar with variables named Expression, Term, Factor, Primary, and intlit.
Expression
|
Term
/ | \
Term * Factor
| / | \
Factor ( Expression )
| / | \
Primary Expression + Term
| | |
intlit Term Factor
| |
Factor Primary
| |
Primary intlit
|
intlit
8 * (13 + 5).
*
/ \
8 +
/ \
13 5
unless, if,
while, and until operators, which are non-associative.
A and B and C, one may not write A and B or C.
<, <=, ==,
!=, >=, and >), which are
non-associative.
<<
and >>)
*, /,
and %)
+ and -)
**)
- and not are prefix, while ! (for factorial) is postfix.
Because these are non-associative, one cannot write - - 2 or
-5! or 3!!!.
[e1 .. e2] for expressions
e1 and e2), function calls, and of course, parenthesized
expressions.
Assume the existence of variables id, numlit, stringlit, and Call.
Program = Block
Block = (Stmt ";")+
Stmt = Id "=" Exp
| read Id ("," Id)*
| write Exp ("," Exp)*
| while BoolExp loop Block end
Exp = Exp1 (("+" | "-") Exp1)*
Exp1 = Exp2 (("*" | "/") Exp2)*
Exp2 = "-"? Exp3
Exp3 = intlit | id | "(" Exp ")"
BoolExp = BoolExp1 (or BoolExp1)*
BoolExp1 = BoolExp2 (and BoolExp2)*
BoolExp2 = Exp (("<" | "<=" | "==" | "!=" | ">=" | ">") Exp)?
| BoolExp3
BoolExp3 = not? BoolExp4
BoolExp4 = true | false | "(" BoolExp ")"
(a = 3) >= m >= ! & 4 * ~ 6 || y %= 7 ^ 6 & p
int f(int x, int y) {
return y,x?a.p[5]+=7&!y<x<y+++x||+x|*&y-~--y*x^y:0;
}
printf("%08X %#16.7e\n",x---a.p[9]^x|*&p&1,*((float*)&x));
die and split are both list operators):
die "\n">>1,~\$$x^split @a,3|x**$;=>%p&&&p;
(* 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, does the author Michael L. Scott say in his book that “Issues of precedence and associativity do not arise with prefix or postfix notation?” Reword this claim to make explicit the hidden assumption.
public void fail() {
class Failure extends RuntimeException {}
throw new Failure();
}
function g(h) {
var x = 2;
h()
}
function main() {
var x = 5
function f() {
print x + 3
}
g(f)
}
main()
function f(a) {
let x = a - 1
function g() {
print x - 17
}
h(g)
}
function h(p) {
let x = 13
p()
}
f(18)
null and undefined do not get coerced to objects, and non-functions do not get coerced to functions. I would say it's roughly 90% weakly typed. It’s not 100% weakly typed because its designer thought that coercing things to functions and even objects would be going too far, since there is no consensus on the obvious coercion to make.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 means that Java is not completely statically typed. Include in your answer a well-written explanation that shows you truly understand the difference between static and dynamic typing. 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.
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;
c within sort
split
merge
y in the third clause of split?
sort and explain why it is not what you would
expect.
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 typecheck an expression in which an A was used as a B? What problem might you run into?
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]?
double *a[n]; double (*b)[n]; double (*c[n])(); double (*d())[n];
double (*f(double (*)(double, double[]), double)) (double, ...);Describe rigorously, in English, the type of $f$.
x, make it so that *x == x. If this is not possible, state why it is not possible.x, make it so that *x == x. If this is not possible, state why it is not possible.p == *p. If it is not possible to do so, state why no such variable can be defined.
(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?
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 midtest 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 midtest version?
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. (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()).
[a0, a1, ..., an-1]
and returns the list
[a0, f(a1), f(f(a2)),
f(f(f(a3))), ...].
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].
Hint: Do the f(f(f...)) as a separate function. Also
you do not have to make your function tail recursive.
function ss(a) {
function s(i, acc) {
return i == a.length ? acc : s(i+1, a[i]*a[i]+acc)
}
return s(0, 0);
}
def ss(a)
s = Proc.new{|i,acc| i==a.length ? acc : s[i+1, a[i]*a[i]+acc]}
s[0, 0]
end
Given: a list [a0, a1, ..., an-1],
Return: a0*a1 + a2*a3
+ a4*a5 + ....
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;
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;
}
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) == 55because the element at index 2 within the array is 7 and $7^2 + 6 = 55$.
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).
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.
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.
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];
2 2 2 4.
y[1], and that becomes 2 + 1 = 3, so it prints
2 2 3 4.
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.
x = 1;
y = 2;
function f(a, b) {a = 3; print b, x;}
f(x, x + y);
print x;
void f() {
int i;
printf("%d ", i++);
}
int main() {
int j;
for (j = 1; j <= 10; j++) f();
}
Local variable i in subroutine f 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.
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;
call f(2)
print* 2
stop
end
subroutine f(x)
x = x + 1
return
end
nextOdd. 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?
Container:
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?
Person and
subclasses for different jobs (e.g., programmer, manager,
ticket agent, flight attendant, supervisor, student, etc.)
is a lousy design. Give an alternative.
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.)
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).
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.
class Foo {
public int a;
public String b;
}
...
class Bar extends Foo {
public float c;
public int b;
}
Does the representation of a Bar object contain one b field or two?
If two, are both accessible, or only one? Under what circumstances?
Answer for C++, Java, Python, and Scala.
Foo is an abstract class in a C++ program, why is it
acceptable to declare variables of type Foo*, but not of
type Foo? Does this problem even make sense to ask in
Java or Python?
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.
if not T'Terminated then
T.E;
end if;
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.