Comparative Programming Languages Assignment
Part A -
Question 1 -
(1) Name two historically significant programming languages that were developed before 1960.
(2) What category or paradigm of programming language has a structure dictated by the von Neumann computer architecture?
(3) What is one advantage and one disadvantage of using an interpreter compared with using a compiler?
(4) List the tokens in the following C statement:
x+=p- >val+1;
(5) Write a single EBNF rule for the language defined by the following syntax graph.
(6) Describe in English language the sentences produced by the following grammar.
S → aSbb | X
X → cX | c
(7) Given the grammar
declist → decl declist | ∈
decl → type varlist ;
type → int | float | char
varlist → ident , varlist | ident
ident → a | b | x | y
Produce a leftmost derivation for the following sentence of the language: int x, y; char a;
(8) Write BNF grammar rules for a language that is comprised only of sentences described as follows:
A sequence of one or more occurrences of an a symbol, followed by either zero or more z symbols or just one x symbol, followed by a sequence of one or more b symbols.
(9) The following fragment of grammar describes the syntax of the exponentiation operator. What is the associativity of the operator as defined here?
factor → expr ** factor | expr
(10) What are the two major styles of parser? In each case, what derivation order do they attempt to construct for the sentence being parsed?
(11) Name a variable attribute which is bound at
(a) compile time
(b) link time
(c) run time
(12) Define what is meant by the lifetime of a variable.
(13) What is a type error?
(14) What is type coercion?
(15) What kind of programming error can arise when implicit variable declarations are permitted in a language?
(16) Describe one of the common programming errors which can arise when using pointers.
(17) Consider the array x : array [0..10, 5..10] of double If a double occupies 8 bytes, and access is in row major order, what is the byte offset (the number of bytes from the beginning of the array, starting from zero) of the element x[7, 6]?
(18) What is an overloaded operator?
(19) What is short circuit expression evaluation? Give an example of a C expression which can be evaluated in this way.
(20) What advantage is gained by providing user-located loop control statements in a programming language?
(21) Using an example, explain how operand evaluation order can affect the result of expression evaluation when a functional side effect is present.
(22) What is the static parent of a subprogram?
(23) What is a formal parameter?
(24) Consider the following program, written in a C-like language.
int x;
void f(int a) {a = a+2; x = x+1;}
void main() {
x = 1;
f(x);
printf("x=%d\n",x);
}
What value of x will be printed by the main program under each of the following conditions? Imagine that formal parameter a of function f is being passed:
i. by value
ii. by value-result
iii. by reference
(25) Consider the C function
int myFun(a: int; b: char){
x, y: float;
.....
}
Draw the layout of the activation record for this function. The ordering of elements is important -assume that the stack grows upwards.
(26) What is the advantage of separate compilation over independent compilation?
(27) A static chain links a set of activation record instances together. How are these instances related?
(28) Why do the actual parameters appear in an activation record below (that is, they are pushed onto the stack before) the local variables?
(29) Consider the following skeletal program, written in a language with static scope.
procedure Main;
procedure A;
procedure B;
procedure C;
begin { C }
end { C }
begin { B }
end { B }
procedure D;
procedure E;
begin { E }
end { E }
begin { D }
end { D }
begin { A }
end { A }
begin { Main }
end { Main }
Imagine that the following procedure calls have taken place:
Main calls A
A calls D
D calls E
E calls B
B calls C
i. Draw the run time stack showing just activation record instances and static links at the time when C is executing. Do not show contents of each activation record instance, apart from the static link.
ii. List the names of procedures that can be called from procedure B.
(30) What are the two key features of an Abstract Data Type?
(31) What is an exception?
(32) What is the advantage of using language defined exception handler features to deal with exceptions rather than using standard techniques such as calling an error procedure?
(33) What are the two key features of an Object Oriented language, beyond those provided by an Abstract Data Type?
(34) What key advantage of using an abstract data type is weakened when inheritance is employed?
(35) Under what conditions is a derived class a subtype of its parent?
Question 2 -
In this question you are required to write a number of small Haskell functions. You may use any Standard Prelude function in writing these functions. If you need, you may write other functions in order to implement the functions specified below; if you do so, be sure to show their definitions. One of the definitions use the Maybe data type. Recall that the Maybe type has definition:
data Maybe a = Nothing | Just a
(1) Write the function
replace :: Eq a => a -> a -> [a] -> [a].
The application replace a b list will replace all occurrences of a in list with b.
(2) Write the function
posn :: Eq a => a -> [a] -> Maybe Int.
posn looks for an item in a list. If found it returns Just n where n is its position (starting from zero). Otherwise it returns Nothing. For example:
posn 'c' "abcde" ⇒ Just 2
posn 'a' "abcde" ⇒ Just 0
posn 'f' "abcde" ⇒ Nothing
(3) Write the function
merge :: Ord a => [a] -> [a] -> [a].
merge takes two lists sorted in ascending order and merges them into one sorted list. Lists can be of unequal length and may be empty.
Question 3 -
In this question you are required to write a number of Prolog relations. You may need to define other relations in order to answer the questions below.
(1) Evaluate the following equalities and write down the values for the variables H and T.
i. ?- [the, cat, [cat, sat]] = [H | T].
ii. ?- [the, [cat, sat], down] = [_,H | T].
(2) Define the relation replace (A, B, L1, L2) such that the list L2 is the same as list L1, except that all occurrences of A in L1 are replaced by B. For example:
?- replace (a, b, [a, b, a, c], X). ⇒ X = [b, b, b, c].
(3) Assume the presence of a database of parent relations. parent (X, Y) asserts that X is a parent of Y.
i. Write the relation cousin(X,Y) that is true when two persons are cousins.
ii. Write the relation stepsib(X, Y) that is true when two people share only one (but not both) parents.
Part B -
Question 1 -
(1) Name or describe an abstraction feature of a programming language.
(2) Name two (2) languages with statement syntax that is very similar to that of the C language.
(3) Name a language feature whose use can enhance the reliability of programs written in that language.
(4) Why is readability of a programming language important?
(5) What are the three extra constructions present in Extended BNF (EBNF) compared to BNF?
(6) List the tokens in the following C statement:
x+=p->val+1;
(7) Write a single EBNF rule for the language defined by the following syntax graph.
(8) Describe in English language the sentences produced by the following grammar.
S → aSb | aXb
X → y | z
(9) Given the grammar
declist → decl declist | ∈
decl → type varlist ;
type → int | float | char
varlist → ident , varlist | ident
ident → a | b | x | y
Produce a leftmost derivation for the following sentence of the langage: int x, y; char a;
(10) How can a grammar be proven to be ambiguous?
(11) What form of grammar rule is required to produce right associativity in expressions?
(12) What derivation order does a LR parser employ in parsing a sentence of a language?
(13) What is the lifetime of
(a) a stack-dynamic variable
(b) an explicit dynamic variable
(14) What is a type error?
(15) What is meant by strong typing?
(16) What kind of programming error can arise when implicit variable declarations are permitted in a language?
(17) What is meant by the scope of an identifier?
(18) The "lost variable" problem when using heap dynamic variables leads to a so-called "memory leak". Describe a situation that demonstrates this problem.
(19) Consider the array x: array [0..10, 20..30] of double If a double occupies 8 bytes, and access is in row major order, what is the byte offset (the number of bytes from the beginning of the array, starting from zero) of the element x[7, 25]?
(20) What is short circuit expression evaluation? Give an example of a C expression which can be evaluated in this way.
(21) What is the minimum number of loop iterations possible for a pre-tested loop?
(22) Ada and Modula-2 use explicit end of statement keywords and sequences of statements, like this:
ifStmt → if expr then stmtList else stmtList end
C and Pascal use blocks and no statement terminating keyword, like this (using Pascal syntax):
ifStmt → if expr then block else block
block → stmt | begin stmtList end
Give one advantage for using each of these two approaches.
(23) What is the dynamic parent of a subprogram?
(24) Consider the following program, written in a C-like language.
int x;
void f(int a) {a = a+2; x = x+1;}
void main() {
x = 1;
f(x);
printf("x=%d\n",x);
}
What value of x will be printed by the main program under each of the following conditions? Imagine that formal parameter a of function f is being passed:
i. by value
ii. by value-result
iii. by reference
(25) What parameter passing mode (in, in-out or out) do the following parameter passing mechanisms implement?
- call-by-value
- call-by-reference
- call-by-result
- call-by-value-result
(26) Why are the return address and parameters placed in a procedure's activation record before its local variables?
(27) Consider the following skeletal program, written in a language with static scope.
procedure Main;
procedure A;
procedure B;
procedure C;
begin { C }
end { C }
begin { B }
end { B }
procedure D;
procedure E;
begin { E }
end { E }
begin { D }
end { D }
begin { A }
end { A }
begin { Main }
end { Main }
Imagine that the following procedure calls have taken place:
Main calls A
A calls D
D calls E
E calls B
B calls C
i. Draw the run time stack showing just activation record instances and static links at the time when C is executing. Do not show contents of each activation record instance, apart from the static link.
ii. List the names of procedures that can be called from procedure B.
(28) Give two ways in which overloaded subprograms of the same name must differ from each other in order to be valid definitions.
(29) What are the two key features of an Abstract Data Type?
(30) Give one advantage of using an abstract data type.
(31) What is an exception?
(32) What is the advantage of using language defined exception handler features to deal with exceptions rather than using standard techniques such as calling an error procedure?
(33) What are the two key features of an Object Oriented language, beyond those provided by an Abstract Data Type?
(34) Describe one significant design decision faced by designers of object oriented languages?
Question 2 -
In this question you are required to write a number of small Haskell functions. You may use any Standard Prelude function in writing these functions. If you need, you may write other functions in order to implement the functions specified below; if you do so, be sure to show their definitions.
One of the definitions use the Maybe data type. Recall that the Maybe type has definition:
data Maybe a = Nothing | Just a
(1) Write the function
cap :: String -> String.
The application cap str will replace the initial letter of each word in str with a capital letter. Assume that str contains words separated by one or more space characters (you do not need to consider other whitespace such as tabs and newlines).
Hint: Use the toUpper function from the Char module to help in writing this function.
(2) Assume the definition:
data Tree x = Node x (Tree x) (Tree x) | Nil.
Write the function
lookT :: Ord a => a -> Tree (a,b) -> Maybe b that searches a binary tree of (key,value) pairs. The values are stored in sorted order: for each node, the left subtree contains only nodes with keys less than the node's key, while the right subtree contains only nodes with keys greater than the node's key. lookT key tree searches tree and returns the value associated with key, if a matching key value is found. Otherwise it returns Nothing. The function should only search in sub-trees likely to contain key.
(3) Write the function
mrep :: [String] -> String -> String.
mrep xs str returns str, where successive occurrences of the '$' character in str are replaced by successive elements in xs. The length of xs does not need to match the number of '$'.
Question 3 -
In this question you are required to write a number of Prolog relations. You may need to define other relations in order to answer the questions below.
(1) Define the relation maxList(L,N) such that N is the maximum value that appears in the (non-empty) list L.
(2) Assume the presence of a database of family relations:
parent(X,Y) asserts that X is a parent of Y, and
husband(H,W) asserts that H is the husband of W.
i. Write the relation spouse(X,Y) that is true whenever X is married to Y.
ii. Write the relation inlaw(X,Y) that is true whenever Y is a parent-in-law of X. (A person's parents-in-law are that person's spouse's parents.)
iii. Write the relation sibinlaw(X,Y) that is true whenever Y is a brother-in-law or a sister-in-law of X. (A person's sistersin-law are that person's spouse's sisters; similarly for brothers-inlaw.)
Attachment:- Assignment Files.rar