- For each of the following programming languages,
what is the language best known for?
- Algol-60
- C
- Cobol
- Fortran
- Haskell
- Lisp
- Miranda
- Prolog
- Simula
- SML
- For each of the following individuals,
what significant development in programming languages is the individual
best known for?
- John Backus.
- Alonzo Church.
- Peter Henderson.
- Grace Hopper.
- Ada Byron, Countess of Lovelace.
- Robin Milner.
- Peter Naur.
- Christopher Strachey.
- John von Neumann.
- What is `orthogonality' as used when discussing the design of
programming languages?
Given an example where orthogonality has not been applied
in the design of C, Java or SML.
Given an example where orthogonality has been applied
in the design of C, Java or SML.
- What does `first-class value' mean when discussing programming languages.
Give examples from C and SML to illustrate
their views on first-class values.
- Evaluation strategies:
- What is strict evaluation (also known as eager evaluation)?
- What is non-strict evaluation (also known as lazy evaluation)?
- Give an example program that requires
non-strict evaluation if the program is to run correctly.
Explain why.
- Which evaluation strategy is used in:
- C
- Haskell
- Java
- Miranda
- SML
-
Given
- fun length [] = 0
- | length (_ :: t) = 1+length t;
- fun append [] L2 = L2
- | append (h::t) L2 = h :: append t L2;
- datatype 'et Tree = EmptyTree | Fork of ('et Tree) * 'et * ('et Tree);
- fun height EmptyTree = 0
- | height (Fork(L,e,R)) = 1+ Int.max(height L, height R)
-
- Each of the following SML expressions is inefficient;
for each one give an efficient SML expression that calculates the same result.
- length xs > 0
- take n (map f s)
- append (append a b) c
- map f (map g s)
- height T > 0
In each case, briefly say why your expression is
more efficient than the given expression.
See standard functions: [eg.sml].
- For each of the following SML functions,
what does the function calculate? (What, not how.)
What is the type of function f1?
How does the compiler infer the type of f1?
- val f1 = foldl (fn x => fn y => x orelse y) false
- val f2 = foldl (fn x => fn y => x andthen y) true
foldl is in [eg.sml].
-
- What does the following function, mystery, calculate? (What, not how.)
- What is the function's type?
- How does the compiler infer that type?
- Give an equivalent 1-line, 1-expression definition of mystery
that uses [standard functions].
- fun mystery f z g [] _ = z
- | mystery f z g _ [] = z
- | mystery f z g (x::xs) (y::ys) =
mystery f (f z (g x y)) g xs ys;
- Here is a skeleton SML program with six functions (a, b, c, d, e, f)
and seven expressions (e1, e2, e3, e4, e5, e6, e7).
For each expression indicate which functions the expression can call and which it cannot call.
let fun a() =
let fun b() = e1
and c() = e2
in e3
end
and fun d() =
let fun e() = e4
and f() = e5
in e6
end
in e7
end
| a | b | c | d | e | f |
e1 | | | | | | |
---|
e2 | | | | | | |
---|
e3 | | | | | | |
---|
e4 | | | | | | |
---|
e5 | | | | | | |
---|
e6 | | | | | | |
---|
e7 | | | | | | |
---|
Put a tick (can call) or a cross (cannot call) in each box.
- Here is a skeleton SML program with six functions (a, b, c, d, e, f)
and seven expressions (e1, e2, e3, e4, e5, e6, e7).
For each expression indicate which functions the expression can call and which it cannot call.
let fun a() =
let fun b() = e1;
fun c() = e2
in e3
end;
fun d() =
let fun e() = e4;
fun f() = e5
in e6
end
in e7
end
| a | b | c | d | e | f |
e1 | | | | | | |
---|
e2 | | | | | | |
---|
e3 | | | | | | |
---|
e4 | | | | | | |
---|
e5 | | | | | | |
---|
e6 | | | | | | |
---|
e7 | | | | | | |
---|
Put a tick (can call) or a cross (cannot call) in each box.
Here are some SML function definitions.
For each function, what is the type of the function and,
briefly, how does the compiler infer that type?
- fun curry fu x y = fu (x,y)
- fun uncurry fc (x,y) = fc x y
Here are some expressions.
For each expression, is the expression valid or invalid?
If it is valid what is its type.
If it is invalid say why.
- curry curry
- curry uncurry
- uncurry curry
- uncurry uncurry
- We would like the following function, isBST, to have
the type 't Tree -> Bool
(where 't can be int, real, char, string, etc.)
but isBST does not have that type in SML.
(* ?is a given binary tree a binary search tree? *)
fun isBST EmptyTree = true
| isBST (Fork(L,e,R)) =
let fun check _ EmptyTree = true
| check p (t as Fork(_,e,_)) = p e andalso isBST t
in check (fn e' => e' < e) L andalso
check (fn e' => e' > e) R
end;
- What type does isBST actually have in SML?
- What language feature would SML need for isBST to
have the type 't Tree -> Bool
(where 't can be int, real, char, string, etc.)?
- What is the standard work-around in SML for the lack of
this language feature?
- Rewrite isBST using the standard work-around.
- Types, SML:
- What does the following expression compute
- hd (hd [[11, 12], [21, 22], [31, 32]] )
- where hd returns the first element of a non-empty list.
-
- Given the following function definition
- fun twice f x = f(f x)
- what is the type of twice?
- How does SML infer the type of twice?
- Is the following expression valid, and if so what does it compute,
or is it invalid, and if so why?
- twice hd [[11, 12], [21, 22], [31, 32]]
- Block Structure:
Below is the skeleton of a Pascal program.
Pascal is a recursive block-structured language.
A procedure's local variables, if any,
are declared between the procedure's heading and
the `begin' of the `begin ... end' containing its code.
A call of a procedure, p, cannot appear in a program
until after the procedure heading (procedure p...).
- For each procedure (a, b, c, d, main),
which of the variables (av, bv, cv, dv, mv) can the procedure use and
which ones is it not able to use?
- Draw the stack when procedure b is executing.
Show all necessary links and registers.
- Refering to the stack,
describe how b accesses each of the variables that you listed
it as being able to use.
program main(input, output);
var mv:int;
procedure a;
var av:int;
procedure b;
var bv:int;
begin(*b*)
...
end(b*);
begin(*a*)
...
b (*a calls b*)
end(*a*);
procedure c;
var cv:int;
procedure d;
var dv:int;
begin(*d*)
...
a (*d calls a*)
end(*d*);
begin(*c*)
...
d (*c calls d*)
end(*c*);
begin(*main*)
...
c (*main calls c*)
end(*main*).
- Binding:
Given the following program in a hypothetical language
begin(*main*)
var i :int;
i := 10;
procedure a (*a is called twice*)
begin(*a*)
print(i)
end(*a*);
procedure p
begin(*p*)
var i :int;
i := 20;
a (*p calls a*)
end(*p*);
p; (*main calls p*)
a (*main calls a*)
end(*main*)
- What is the program's output if the language uses dynamic binding?
- What is the program's output if the language uses dynamic binding?
- Give a possible advantage of static binding over dynamic binding.
- Give a possible advantage of dynamic binding over static binding.
- Overloading:
- What is overloading as a programming language concept?
- What is context independent overloading as a programming language concept?
- What is context dependent overloading as a programming language concept?
- Does SML use context dependent overloading or context independent overloading?
- Give a simple expression which is ambiguous under
context dependent overloading. Say Why.
- Garbage collection:
- What is a garbage collector in a programming language?
- Define the mark-scan garbage collection algorithm.
- Give an advantage of a programming language having a garbage collector.
- Give a disadvantage of a programming language having a garbage collector.
- Give two features of a programming language
that require, or strongly imply,
the use of a garbage collector in an implementation of the language.
- Parameters:
Here is a program in a hypothetical language.
What is its output if all parameters are
- passed by value (by input),
- passed by input-output,
- passed by reference,
- passed by name.
You must give reasons.
int i;
p(int x, int y)
{ i += 1;
x += 1;
y += 1;
}
main()
{ int a[5];
a[0]=0; a[1]=1; a[2]=2; a[3]=3; a[4]=4;
i = 1;
p(i, a[i]);
print(i, a[0],a[1],a[2],a[3],a[4]);
}
- Parameters: What does the following program print if
- parameter x is passed by-reference? Why?
- parameter x is passed by-name? Why?
begin
int n;
n:=1;
function g()
begin n:=n+1; return n
end(*g*);
procedure increment( x )
begin x := x+1
end(*increment*);
int[5] a;
a[0]:=0; a[1]:=10; a[2]:=20; a[3]:=30; a[4]:=40;
increment( a[g()] );
print(n);
print(a[0], a[1], a[2], a[3], a[4])
end
- Procedure formal parameters:
Here is the skeleton of a Pascal program.
Pascal is a recursive block-structured language.
A procedure's local variables, if any,
are declared between the procedure's heading and
the `begin' of the `begin ... end' containing its code.
- Draw the stack when procedure d is executing.
- When procedure d is executing,
specify in detail how procedure d accesses variable cv?
program main(input, output);
procedure a(procedure b(x:real));
begin(*a*)
b(3.4); (*a calls its parameter b*)
....
end(*a*);
procedure c(y:real);
var cv:int;
procedure d(z:real);
begin(*d*)
cv:=cv+z; (*d accesses cv*)
...
end(*d*);
begin(*c*)
cv:=y;
....
a(d) (*c calls a, passing d to it*)
end(*c*)
begin(*main*)
c(1.2); (*main calls c*)
...
end(*main*).
- Code generation:
Here is a fragment of a program, P, written in a language, L.
...;
sumSq := sumSq + a[i]*a[i]; (*i.e. dot product a[].a[]*)
...
sumSq, i and a[] are local variables of the current procedure.
sumSq is a variable of type real,
i is an integer variable, and
a[] is an array of reals.
L is a recursive block-structured language.
Consider a compiler for language L and
a machine with the following features
- 16 integer/index registers, R0 to R15,
- 16 floating-point registers, F0 to F15,
- instructions of the form
- <reg> := <address> --load contents of address into reg
- <address> := <reg> --store contents of reg at address
- <reg> := <reg> --e.g., R6 := R2
- <reg> <op>= <reg> --e.g., R6 += R2
- <reg> <op>= <address>
--e.g., F3 += 28(R2)
where <reg> is R0 to R15 or F0 to F15,
<op> is + | - | * | / |,
<address> is <number> | <number>(<iReg>), and
<iReg> is R0 to R15
The compiler is in the act of analysing the
fragment of program P;
show the output of
- lexical analysis,
- syntax analysis,
- semantic analysis, and
- code generation.
for the fragment.
State any assumptions that you make.
- Consider the context-free grammar
with terminal symbols a, b and c,
non-terminals A and B where A is the start symbol, and
productions
A -> B A B | a
B -> b | c | ε
Which of the following strings is not in the language of the grammar?
- abb
- bcacb
- bbccac
- bcacba
- bcab
- Consider the following regular grammar,
with terminals a and b,
non-terminals S and X, and start symbol S.
S -> X
X -> a X
X -> a
X -> b X
X -> b
- The above grammar recognizes a regular language.
Give a regular expression for the language of this grammar.
- Add attributes and attribute computation rules and conditions
to the grammar above so that it recognises non-empty strings
with an equal numbers of a's and b's.
I.e., aabbab should be in the language of the new grammar
but aaabb should not.
Indicate whether the attributes are inherited or synthesized.
- Consider the context-free grammar
S -> X S | d S | ε
X -> Y | Z b | a Y
Y -> c Z
Z -> e
The symbols S, X, Y and Z are non-terminals, and S is the start symbol.
The terminal symbols are a, b, c, d, and e.
- Give FOLLOW and FIRST sets for each non-terminal symbol.
- Construct the parsing table for a non-recursive predictive
parser for this grammar.
- Is the grammar LL(1)?
If not say why not.
- Show how a non-recursive predictive parser will parse the
sentence dace using the table that you constructed above.
- Consider the
following grammar with terminals a, b and +, and
non-terminals S, A and B where S is the start symbol, and
productions
(P1) S -> A + B
(P2) S -> B
(P3) A -> a A
(P4) A -> ε
(P5) B -> b B
(P6) B -> ε
- Compute FIRST(A), FIRST(B), and FIRST(S).
- Compute FOLLOW(A), FOLLOW(B), and FOLLOW(S).
- Consider the following LL(1) parsing table for a predictive table parser
| a | b | + | $ |
S | P1 | P2 | P1 | |
A | P3 | | P4 | |
B | | P5 | | P6 |
where Pi refers to the ith production
in the above grammar.
Detail how the sentence a+b would be parsed with a
predictive table parser using this table.
For each step of the process give the parser action,
input, and stack state.
- Is the parsing table given above the correct LL(1) predictive
table for this grammar?
If not, identify and correct the errors in the table.
- Consider the context-free grammar
A -> X S | d S | ε
X -> Y | Z b | a Y
Y -> c Z
Z -> e
The symbols S, X, Y and Z are non-terminals, and S is the start symbol.
The terminal symbols are a, b, c, d, and e.
- Why is the grammar unsuitable for directly implementing
a recursive-descent parser?
Identify the production(s) that cause the problem.
- Modify the grammar (without changing the language it defines)
so that it can be implemented directly in a recursive-descent parser.
- Consider the context-free grammar
S -> a X
X -> b X | b Y
Y -> c
The non-terminals are S, X and Y; S is the start symbol;
the terminals are a, b and c.
- Give the canonical collection of LR(0) items for this grammar
(remembering to first augment it with a new start symbol S').
- Compute the FOLLOW sets for all non-terminals and give the
SLR parsing table (action and goto) for this grammar.
- Detail how and SLR parser will parse the sentence abbc
using the SLR table you constructed above.
- Consider the
augmented grammar which consists of
the terminals a, b and +,
the non-terminals S, A and B, and
the productions
(P1) S -> A + B
(P2) S -> B
(P3) A -> a A
(P4) A -> ε
(P5) B -> b B
(P6) B -> ε
with the new start symbol S' and the additional production
(P0) S' -> S
- Compute
- I0 = closure({S' -> .S})
- goto(I0, a)
- goto(I0, b)
- goto(I0, +)
- goto(I0, A)
- goto(I0, B)
- goto(I0, S)
- Consider the following LR parsing table for this grammar
STATE |
ACTION |
|
GOTO |
a | b | + | $ | S | A | B |
0 | s1 | s2 | r4 | r6 | 5 | 3 | 4 |
1 | s1 | | r4 | | | 6 | |
2 | | s2 | | r6 | | | 7 |
3 | | | s8 | r6 | | | |
4 | | | | r2 | | | |
5 | | | | acc | | | |
6 | | | r3 | | | | |
7 | | | | r5 | | | |
8 | | s2 | | | | | 9 |
9 | | | | r1 | | | |
- where si is shift and stack state i,
- rj is reduce using production Pj,
- acc is accept.
- Detail how the sentence a+b would be parsed with
an LR parser using this table.
For each step of the process give the parser action (shift/reduce),
input and stack state.