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.
| $A$ | $B$ | $\;\;\neg A\;\;$ | $\;\;\neg B\;\;$ | $A \land B$ | $A \lor B$ | $A \supset B$ | $A \equiv B$ |
|---|---|---|---|---|---|---|---|
| true | true | ||||||
| true | false | ||||||
| false | true | ||||||
| false | false |
| $A$ | $B$ | $A \uparrow B$ | $A \downarrow B$ | $A \oplus B$ | $A \subset B$ |
|---|---|---|---|---|---|
| true | true | ||||
| true | false | ||||
| false | true | ||||
| false | false |
| $A$ | $B$ | $\;\;\neg A\;\;$ | $\;\;\neg B\;\;$ | $A \land B$ | $A \lor B$ | $A \supset B$ | $A \equiv B$ |
|---|---|---|---|---|---|---|---|
| true | true | ||||||
| true | false | ||||||
| true | other | ||||||
| false | true | ||||||
| false | false | ||||||
| false | other | ||||||
| other | true | ||||||
| other | false | ||||||
| other | other |
| $A$ | $B$ | $\;\;\neg A\;\;$ | $\;\;\neg B\;\;$ | $A \land B$ | $A \lor B$ | $A \supset B$ | $A \equiv B$ |
|---|---|---|---|---|---|---|---|
| true | true | ||||||
| true | false | ||||||
| true | other | ||||||
| false | true | ||||||
| false | false | ||||||
| false | other | ||||||
| other | true | ||||||
| other | false | ||||||
| other | other |
$λx.(λx.\;x\;y)\;(λz.\;(x\;λw.\;w)\;(z\;λp.\;p)\;x)\;z$
let y = 3 * x in sqrt(21 + y)?
λy. λx. (times 3 (sqrt (plus 21 y)))λx. λy. times 3 (sqrt (plus 21 y))(λy. (sqrt (plus 21 y))) (times 3 x)sqrt(21 + 3 * x)(λy. (times 3 x)) (sqrt (plus 21 y))
s → s "a" s "b" s
| s "b" s "a" s
| 𝜀
s → x*
x → "a" e | "b" x x
e → ("a" y | "b" x)?
y → "b" e | "a" y y
next(page).footer[2], give (1) the sequence of Unicode Characters, and (2) the token sequence. Assume any reasonable mainstream programming language with function calls, member access, and array indexing.Block = (Statement ";")+Block = NonEmptyListOf ";"? Block = Statement (";" Statement)* ";"Exp4 -> Exp5 ("+" Exp5)*. Which of the following best describes the + operator?
(* 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. 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
f(x).a[2]if (x) while (0) f(x); else if (y <- x) break;
(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));
p <<* a*7 &- 3 &x,1
die and split are both list operators):
die "\n">>1,~\$$x^split @a,3|x**$;=>%p&&&p;
import x from "x"
console.log(93.8 * {x} << x.r[z])
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 ")"
n: Nml i: Ide e: Exp = n | i | e + e s: Stm = i := e | print e b: Block = s+ p: Pro = program b
and here is a purported alternative syntax for the language:
n: Nml i: Ide e: Exp = n | i | e + e s: Stm = i := e | print e | s s p: Pro = program sWhich of the following statements are true?
The lowest precedence operators are the binary unless, if while, and until operators, which are non-associative. The next lowest precedence operators are the logical binary operators, which are left associative amongst themselves, but do not associate with each other, meaning that one while can write A and B and C, one may not write A and B or C. The next lowest precedence operators are the relational operators (<, <=, ==, !=, >=, and >), which are non-associative. Next in precedence come the left associative shift operators (<< and >>) Next come the left multiplicative operators (*, /, and %) Next come the left associative additive operators (+ and -), followed by the right associative exponentiation operator (**), followed by the non-associative unary operators. The unary operators - and not are prefix, while ! (for factorial) is postfix. Because these are non-associative, one cannot write - - 2 or -5! or 3!!!. The most primitive expressions are identifiers, numeric literals, string literals, ranges (of the form [e1 .. e2] for expressions e1 and e2), function calls, and of course, parenthesized expressions.
id, numlit, stringlit, and Call. Provide, for this language fragment, the following:
Programs are made up of a possibly empty sequence of function declarations, followed by a single expression. Each function declaration is of the form $f = (p_1, \ldots, p_m) \Rightarrow e$ where $f$ is the function name (an identifier), each $p_i$ is a parameter (also identifiers) and the result (the “body”) is an expression. 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, remainder) and a unary prefix negation and a unary postfix factorial (!). There’s a conditional expression with the syntax x ? y : z. 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, and dollar signs, beginning with a letter or dollar sign. Function calls are formed with an identifier followed by a parenthesized, comma-separated list of expressions.
gcd = (x, y) => y ? gcd(y, x % y) : x
cube = (x) => x * x * x
"The answer is" + cube(gcd(30, 4!)) + " 😦😦 "
Programs are made up of a non-empty sequence of function declarations, terminated by semicolons, followed by a single expression. Each function declaration starts with the keyword fun followed by the function's name (an identifier), then a parenthesized list of zero or more parameters (also identifiers) separated by commas, then an equals sign, then the body which is a single expression. 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 is also an infix binary operator called then which indicates that both of its expressions be evaluated in order from left to right, with the value of the right expression being the value of the entire then-expression. There's a conditional expression that looks just like the one in Java, C, and Perl (with the question mark and colon). Factorial has the highest precedence, followed by negation, the multiplicative operators, the additive operators, conditional and finally the then operator. 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 are as in C. Identifiers are those non-empty sequences of letters, decimal digits, underscores, at-signs, and dollar signs, beginning with a letter or dollar sign, that are not also reserved words. Function calls are as in C, with the arguments in a comma-separated list of expressions bracketed by parentheses. There are no comments in this language, and whitespace can be used liberally between tokens.
Provide the following:
x = 7 - p * gcd(2, hypot(p, q)) / -1;, assuming a stack-based interpreter with the following stack-based instructions: PUSH <num>, LOAD <var>, STORE <var>, ADD, SUB, MUL, DIV, NEG, HYPOT, and CALL <fun>.