Question 1

Consider a progamming language with the following statements:
y := 2;
z := x + y; write(z);
Execution of these statements prints the value 6 on the console. Is this a declarative, imperative, or functional language?

Question 2

Consider the following record definitions that create two structures named. Score and Piece.

record                 record (
key string;          time long;
time long;           key string;
Score )                Piece

Now consider the following statements, which execute successfully:

1 Score x = new Score( );
2 tai. key = "C#";
3 Score y = x;
4 y. time = 3600;

Based on this example, briefly describe the properties of type system of the corresponding programming language. Pay attention to each of the statements since there are a few obvious statements you can make (e.g. weakly vs. strongly typed, etc.).

Question 3

Consider the g-rammar:

statement                assign
statement                sub call
assignillent              id = expression

sub call                    id ( arguments )
head

tail                           operatioli express i071

tail
head                       id
head                      sub call
head                      (expression)
operation              argunients
arg tail
arg tail

(Note: Epsilon, a, denotes an empty string and id is any alphabetic token. e.g. foo.)

Construct a parse tree for the input string:
                                                               foo(a b)

Question 4

Using the grammar in the previous question, add the production rules necessary to extend this grammar to include the definition of a subroutine. For example,

subroutine foo (x, y) z = x + y
bar (z)
}

Are the following Lambda Calculus expressions well-forced? (Assume an Applied calculus, where the operators (+ - * l ) are legal well-formed terms in the language and parentheses are allowed.)

Are the following Lambda Calculus expressions well-formed? (Assume an Applied calculus, where the operators (+ - * ) are legal well-formed terms in the language and parentheses are allowed.)

Question 5

y . x + y

Question 6

Question 7

ka + b)

Question 8

Which variable, if any, occurs free in the following Lambda Calculus expression? Xx . Ay. x (Ax. x) y (Ay. y) z (Az. z)

Questions 9 - 12 let.
zero E 'XX X
one E succ zero two E succ one
SUCC E 7i, . (As. (s cadr) n) cadr = X . . v
(Note: cadr is a Lisp utility function that returns the second element in a list. In this case, realize that it's returning the second argument in a two parameter Curried function. That is, it's selecting the second argument. Don't worry about Currie functions. We mention it only because currying allows the representation of multiple argument functions since any multi-argument function can be rewritten as an equivalent function that accepts one argument.)

Question 9

Using the inference rules of Lambda Calculus, show that
one cadr = zero
(There is only one tricky substitution. use parentheses to keep it straight.)

Question 10
Using the inference rules of Lambda Calculus, show that
two cadr cadr = zero
(There is only one tricky substitution, use parentheses to keep it straight.)

Question 11
Given that cadr selects the second argument of a two parameter Curried friction.
Write a three parameter (Curried) Lambda Calculus function, ‘caddr. that selects the third parameteriargument.

Question 12
Write a three parameter (Curried) Lambda Calculus function 'second'. that selects the second argument

Question 13
Consider the assignment statement:
= y = z = 0;
"Many languages support multiple target variables for a single source expression. A common use of such a construct is to initialize two or more variables to the same value. The previous assignment statement initializes all three variables to zero.

The previous quote describes the semantics of the previous assignment statement. As semantic descriptions can be characterized along two primary dimensions, which two categories of semantics best describe the previous statement?

Question 14

Consider the following code:
1 int i, j;
2 void bar(int x)
3 int k, 1;
4 J = 2 * x;
5 x = x + 1;
6
7 1
8 void foo(int y, int z)
9 float j, k;
10 bar(i);
11 = 3;
12
13 }
14 void baz() [

15
16
17
18
19
20 int b, i = 5; foo(b, bar(i); c;
b =
c); 3; c = 2;

Assuming execution starts with line 14, subsequent execution of this code provides examples of both Lexical (static) and Dynamic scoping.
Briefly describe when and how each of these scoping examples occurs. In your description. include the line numbers in the order of execution. For example. all executions will begin by sequentially executing lines: 14, 15, 16, ...
Consider the following code, which
• defines a linked-list structure named 'item' (lines 4-7) and
• two variables named 'top and ‘p' (line 9).
• Both of these variables that have a pointer data type named 'link' (line 3) (i.e. they are pointers to an 'item' record).
• Execution of this program begins at line: 10.
The program is both simple and silly.
• it reads a character fiord the console, acids it as a new item in the list (lines 12-18),
• it then deletes all of the items in the list (lines 19-24)

PROGRAM ricksList (input, output) I
TYPE
link = "item; item = RECORD
next ' link;
data : char

END;
VAR
top, p : link; BEGIN
base := NIL; WHILE NOT eof DO BEGIN
new(p); read(pA.data); p" .next := top;
top := p;
END; {while'
WHILE top <> NIL DO BEGIN
p := top;
top := p^.next; dispose(p);
END; { while } END; { ricksList

Question 15

Based on the above example. what type of memory management (implicit or explicit) does this programming language utilize?

Question 16

Based on the above example, does this language utilize strong or weak typing?

Question 17

Based on the above example. does this language utilize implicit or explicit declarations.

Question 18

Based on this example, what type of bindings (dynamic or static) does this programming language support?
Consider the following factorial function (it's not Lisp):

(define (fact n) (if (eqv? n 0) 1
(* n (fact (- n _)))))

Question 19
Based on this example, describe two properties associated with this language's type system (they are obvious).

Question 20

Consider the Lisp function:
#' ( lambda ( x y )
x )
Is this an example of a first class function or an anonymous function?

Question 21

Consider the following Java method:
1 public void noop() t
Boolean flag = false;
4 if (true) {
5 flag = "false";
6 }
7 }

Line 5 results in a compile-time compiler error. What type of semantics is in play here?

Question 22
Consider the Prolog code:
male(albert). male(edward). female(alice). female(Victoria).
parents(edwardrVictoria,albert). parents(alicerVictoria,albert).
sister of(X,Y) :- female(X), parents(X,M,F), parents(X,M,F).
To ask whether Alice is the sister of anyone. the appropriate query is:
?- sister of(alice,X).
Briefly describe what happens when Prolog executes this query?

Question 23
Consider the following Logical Programming language (i.e. Prolog-like) code:
speaks (rick, german).
talkswith(X,Y) speaks(X,L), speaks(Y,L), X 1 Y.

Question 24
In your own words, why is language in Question 21 declarative and the language in Question 14 nor?

Question 25
Consider the following granmnar:
xpress1011 -> tertian: expression = expression
tertictn. secondary I expression + serondart,
secoildark. primaly secondary * prinian.
priina?7. literal variable 1( expression
/item/ 1, 2, 3, ...
variable a. b, c,

Does this grammar specify an abstract or concrete syntax? [Hint: there's one huge give away.]

Question 26

Substitute the following production rule for the expression rule in Question 2.6. eNpres s loll -. literal expression + expression expression - expression

Give two parse trees that delnollstrate that this new grammar is ambiguous.