King Fahd University of Petroleum and Minerals		
	Department of Information and Computer Science		
	ICS 313:  Fundamentals of Programming Languages		
	Fall 1999-2000		
Date: 05-October-1999	Key to Major Exam I: Basics of Programming Languages & Imperative Paradigm	Time Slot: 6:00 p.m. – 7:30 p.m.	
Duration: 90 minutes		Total Points: 100	

1.	[Short Questions – (7*5 = 35 points)]
Briefly answer any seven of the following:
(i)	Describe the major steps involved in the compilation of a C-program by a C-language compiler.
The major steps/phases include: Lexical analysis which converts a character sequence into a token-sequence, Syntax analysis that builds an implicit/explicit parse-tree based on the C-grammar rules over the token sequence, Semantic analysis like type checking, intermediate code generation, code optimization, and target code generation.

(ii)	What is a translator? What is an interpreter?
A translator is a program that transforms one representation into another representation. In the context of computer applications like compilers, they transform a sequence of instructions in one language into an equivalent sequence in another language. An interpreter is a machine/program that performs/obeys the intended operation as specified in a program one at a time. If it produces any output, it is a consequence of interpreting some operations with side effects.

(iii)	Discuss four major contributions of ALGOL to the programming language community.
Block structuring, Portability at source program level, Two different parameter passing techniques (by name and by value), information hiding (blocks and subprograms), separation between scope and life-time (own), static scope rules, formal syntax description.

(iv)	PL/I was designed to replace two languages. What are those languages? Explain the motivation and the consequences.
PL/I was designed to replace the Fortran and Cobol languages so that one language can serve the scientific application development as well as business application development. Unfortunately, it could not succeed in either of its endeavors.

(v)	What features of SIMULA 67 are now important parts of some object-oriented languages? Explain those features. 
The notions of classes to support co-routines is a fundamental notion of object-orientation these days. Likewise the notion of class instances needed for simulation objects is indeed the modern notion of objects. In addition to all of these the hidden notions of data abstraction, encapsulation and information hiding were all there, although not recognized until much later.

(vi)	What three concepts were the basis of object-oriented programming? Explain.
1. Data abstraction 2. Inheritance, and 3. Dynamic binding.

(vii)	Describe the operation of a general language recognizer and a general language generator.
A language recognizer for a given language L, processes sentences in the vocabulary of L, and either passes the sentence as a valid member of L or rejects saying that it is not a legal sentence in L. All compilers have such recognizers in them. A language generator on the other hand is capable of generating valid sentences in a language L.

(viii)	Define the concepts of binding and binding time. Explain the different times when binding can occur.
The concept of binding refers to associating a property with an attribute of an object. The time of such association is referred to as binding time. Some commonly occurring binding timings are: language definition time – fixing operators and their semantics and the symbols for them; language implementation time which are decisions made during the implementation stage – fixing a maximum length on an identifier, fixing a limit on the array size or dimensions etc.; compilation time – fixing an offset in bytes for a field in a structure relative to the beginning of the structure; linking/loading time – picking appropriate routines from libraries and resolving references to those library functions; run/execution-time – decisions that get made during the execution time such as associating a variable with a particular memory location in a virtual memory context or even linking to the “proper copy” of a non-local reference etc.

(ix)	What are the design issues for character string types? Define three operations on strings.
1. Is it a primitive type or just a special kind of array? 2. Is the length of objects static or dynamic? Some operations include: Assignment, Comparison (=, >, <, !=), Concatenation, Substring extraction, Pattern matching and replacement.

(x)	What are the two common problems with pointers? Explain with examples.
The two major problems with pointers are: dangling references and garbage creation due to lost access as a consequence of pointer destruction in an assignment statement.
If p and q are pointer variables to a certain type T, and q refers to an already allocated data element of type T, the assignment statement p = q will give a handle to T from p. Subsequent disposal of the data element either by freeing up p or q will reclaim space leaving one of those pointer variables pointing to a place which is no-longer valid.
In the above example, if p refers to an already allocated element the assignment would destroy the access to that element. If there are no other references to the data element then it would have become inaccessible or unreachable thus amounting to garbage.

(xi)	Describe the lazy and eager approaches to reclaiming garbage. Whose job is it to reclaim garbage?
In the lazy approach to reclaiming garbage nothing is done until the free space runs out when a request is made for a new element at which point the program under execution is suspended, and memory cells in use are identified by initiating a reachability test recursively starting from the program variables. All but the reachable space is reclaimed into the free-space before resuming the suspended program.
In the eager approach to garbage collection, detailed count of references with each allocated element is maintained. Each assignment of the form p = q causes a decrease to the count of item referred to by p and an increment to that referred to by q. At the time of allocation the count is initialized to 1. Once the count reaches zero, and only then, the space is reclaimed.
In most earlier systems the run-time support of the language used to take care of garbage-collection. But, in modern languages like Java, part of the work is done by the compiler in keeping the code for reference-count maintenance and the other part by means of a background thread that hunts for free space. 

(xii)	Define union, free union and discriminated union.
A union refers to a modeling technique wherein different kinds of data items need to be catered for and it is known that only one of them will be in use at any point in time.
A union differs in that sense from that of a structure wherein all components of a structure are needed all the time and only one of the components of a union is needed at a time.
Such temporal disjointedness will provide an opportunity for space savings through the allocation of space enough to hold any of the components, i.e., the maximum of them.
Languages that are less picky about type-checking, e.g. C provide a free union wherein a user can simply refer to whichever component name and proceed with its use.
Languages like Algol 68 and its derivatives Pascal and Ada support the version called discriminated union, where in two portions of space is allocated. A fixed portion and a variable portion. One of the members, called tag, of the fixed portion will be used to decide on the format or layout of the variable portion. The contents of the tag will be used to choose the format of the variable portion.

2.	[Derivations, Proofs, and Illustrations – (30+10+10 = 50 points)]

(a)	Context Free Grammar Related  (3*10 = 10 points)
Consider the following grammar. For your convenience rules are given labels. In your answer you can refer to those rule numbers and also use the abbreviations: <p> for <program>, <s> for <statement>, <sl> for <statement list>, <v> for <variable>, <e> for <expression>
 
Grammar 1

R1:	<program> 			 begin <statement list> end
R2:	<statement list> 	 <statement>
R3:	<statement list> 	 <statement list> ; <statement>
R4:	<statement> 		 <variable> = <expression>
R5:	<variable> 			 A | B | C 
R6:	<expression> 		 <variable>
R7:	<expression> 		 <variable> + <expression>
R8:	<expression> 		 <expression> – <expression>

(i)	Show the right-most derivation of    begin A = A  – B – C end
             <program>
apply R1 	 begin <statement list> end
apply R2 	 begin <statement> end
apply R4 	 begin <variable> = <expression> end
apply R8 	 begin <variable> = <expression> - <expression> end
apply R8 	 begin <variable> = <expression> - <expression> - <expression> end
apply R7 	 begin <variable> = <expression> - <expression> - <variable> end
apply R5 	 begin <variable> = <expression> - <expression> - C end
apply R7 	 begin <variable> = <expression> - <variable> - C end
apply R5 	 begin <variable> = <expression> - B - C end
apply R7 	 begin <variable> = <variable> - B - C end
apply R5 	 begin <variable> = A - B - C end
apply R5 	 begin A = A - B - C end

(ii)	Either argue that the given grammar is unambiguous or exhibit a sentence and with different derivations that yield the same sentence. In the latter case, modify Grammar 1 to produce Grammar 2 that is unambiguous.

The given grammar is ambiguous. For example, the above could equally have been derived using another right-most derivation as below:
                       <program>
apply R1 	 begin <statement list> end
apply R2 	 begin <statement> end
apply R4 	 begin <variable> = <expression> end
apply R8 	 begin <variable> = <expression> - <expression> end
apply R7 	 begin <variable> = <expression> - <variable> end
apply R5 	 begin <variable> = <expression> - C end
apply R8 	 begin <variable> = <expression> - <expression> - C end
apply R7 	 begin <variable> = <expression> - <variable> - C end
apply R5 	 begin <variable> = <expression> - B - C end
apply R7 	 begin <variable> = <variable> - B - C end
apply R5 	 begin <variable> = A - B - C end
apply R5 	 begin A = A - B - C end

The following variant eliminates the above-illustrated ambiguity.
Grammar 2

R1:	<program> 			 begin <statement list> end
R2:	<statement list> 	 <statement>
R3:	<statement list> 	 <statement list> ; <statement>
R4:	<statement> 		 <variable> = <expression>
R5:	<variable> 			 A | B | C 
R6:	<expression> 		 <variable>
R7:	<expression> 		 <variable> + <expression>
R8:	<expression> 		 <variable> – <expression>

(iii)	Is the grammar suitable for a top-down (recursive-descent) parser implementation in the form given above? Justify. If not give an equivalent grammar that is suitable for the implementation of a top-down parser.

Neither of the above two grammars is in a suitable form for the implementation of a recursive-descent parser. The reason for that is the occurrence of the symbol on the LHS as the first symbol of the RHS. See for example rules R3and R8 of grammar 1. The following variant fixes that through a simple rewriting.

Grammar 3

R1:	<program> 			 begin <statement list> end
R2:	<statement list> 	 <statement>
R3:	<statement list> 	 <statement> ; <statement list>
R4:	<statement> 		 <variable> = <expression>
R5:	<variable> 			 A | B | C 
R6:	<expression> 		 <variable>
R7:	<expression> 		 <variable> + <expression>
R8:	<expression> 		 <variable> – <expression>

(b)	Axiomatic Semantics Related  (10 points)
Derive the weakest pre-condition for either one of the following program fragments.
y = 2 * x + 1;
x = y – 2;
y = 2 * x + 1;
x = y – 2;
{ x > 10 }	if (a > 0)
    b = b – 1
else
    b = b + 1
{ b > 0 }	

First Choice:
The given block corresponds to a sequence with a given post condition. The sequence is made out of four assignment statements. The precondition for the fourth assignment statement is:
Y – 2 > 10, i.e., y > 12
With this as the post-condition for the third assignment statement, its precondition will be:
2 x + 1 > 12, i.e., x > 11/2.
Continuing the argument, the precondition for the second statement will then be: y – 2 > 11/2, i.e., y > 15/2.
Finally, the desired precondition for the first statement and hence the whole sequence will be:
2 x + 1 > 15/2, i.e., x > 13/4.

Second Choice:
The post condition for the selection statement is b > 0.
There are two assignment statements, one in the then part and another in the else part. Employing the axiom of assignment statement, we will have a pre-conditions of b – 1 > 0, i.e. b > 1 and b + 1 > 0, i.e., b > -1 for the then and else parts respectively.
Since b > 1  b > -1 the rule of consequence allows us to use b > 1 as the precondition for the selection statement.

(c)	Scope Rules  (5*2 = 10 points)
Consider the following program skeleton:

#include <stdio.h>
int i = 1;		 	/*  Reference A */

void f1() {
    /* * * * */
    printf(“%d\n”, i);
}

void f2() {
    int i = 2;		/*  Reference B */
    /* * * * */
    f1();
}

int main() {
    int i = 3;		/*  Reference C */
    /* * * * */
    f1();
    f2();
}

(i)	Assuming that dynamic scoping is employed, trace the above program through, listing the bindings of references to different variables. Also show the output produced.

Assume that the above program is for a language that employs dynamic scoping:
In main() reference to i is that of i declared at C.
In the call to f1() from main(), the reference to i, is to that i declared at C. 
In the call to f2() from main(), the reference to i, is to that i declared at B; in the subsequent call to f1() from there the reference to i is that declared at B, as it is the latest reference.
If the printf() is executed according to the semantics of the C-language, then it would have produced an output of :
3
2

(ii)	Assuming that static scoping is employed, trace the above program through, listing the bindings of references to different variables. Also show the output produced.

Assume that the above program is for a language that employs static scoping:
In main() reference to i is that of i declared at C.
In the call to f1() from main(), the reference to i, is to that of the global i declared at A. 
In the call to f2() from main(), the reference to i, is to that i declared at B; in the subsequent call to f1() from there the reference to i is that of global declared at A, as it is the reference available in its nearest enclosing nesting level.
If the printf() is executed according to the semantics of the C-language, then it would have produced an output of :
1
1

3.	[Implementing Mechanisms – (15 points)]

(a)	Homogeneous Multi-Dimensional Aggregation – 2 Dimensional Arrays  (15 points)
Consider the problem of multiplying two matrices. Given A = (aij)mxn and B = (bjk)nxp the product of A and B is defined to be a new matrix C = (cik)mxp where cik =  aij * bjk for j = 1 to n.
(i)	Give declarations and code in the C-programming language to do the above, ignoring the issue of reading a’s & b’s and printing c’s.
#define	m	10
#define	n	20
#define	p	30

float	A[m][n];
float	B[n][p];
float	C[m][p];
int	i, j, k;

/* Reading A and B  ignored. */
/* Iterate through the rows of A */
for (i = 0; i < n; i++)
    /* Iterate through the columns of B */
    for (k = 0; k < p; k++) {
        /* Compute the dot-product of ith row of A and jth column of B */
        c[i][k] = 0.0;
        for (j = 0; j < n; j++)
            c[i][k] += a[i][j] * b[j][k];
    }
/* Printing A, B, C */

(ii)	What would you do if you have to use a language that only supports one-dimensional arrays? Adapt your code to this situation. 
Simulate the two dimensional arrays by one-dimensional arrays and replace the references that index into the multi-dimensional array into that of a one-dimensional array using an accessor function. The above code can be adapted into the following:

#define	m	10
#define	n	20
#define	p	30

float	A[m*n];
float	B[n*p];
float	C[m*p];
int	i, j, k;

/* Reading A and B  ignored. */
/* Iterate through the rows of A */
for (i = 0; i < n; i++)
    /* Iterate through the columns of B */
    for (k = 0; k < p; k++) {
        /* Compute the dot-product of ith row of A and jth column of B */
        c[i*p+k] = 0.0;
        for (j = 0; j < n; j++)
            c[i*p+k] += a[i*m+j] * b[j*p+k];
    }
/* Printing A, B, C */

(iii)	Comment on the similarity of changes you made to the task of a compiler when it encounters a multi-dimensional array.

Even a compiler will produce equivalent code like the above so that it can simulate a multi-dimensional array – which is a logical abstraction provided by the language to the programmer for facilitating the modeling of homogeneous multi-dimensional aggregate items – using a one-dimensional arrays. It replaces each reference by an index computing function or accessor function like the above. Of course, they go a step further in deriving an incremental version of the accessor function so that the calculations can be made much more efficiently.

(b)	Data Modeling(15 points)
Consider a university registration system. Model the appropriate data items that are needed to keep track of student information including name, id, major, GPA, probationary status, grades, and course information. You may assume that you will be using a programming language, which supports only the primitive types int, char, boolean, float and the mechanisms of arrays, records, pointers, and unions for the purpose of creating new types. (Hint: you could model a string to be an array of characters). Use a certain type only when nothing else better suites your purpose. In particular, use strings only if you can justify that nothing else is appropriate. Illustrate the use of each of the type constructor mechanisms at least once in the overall type declarations. Justification of your answer is perhaps more important than your decisions themselves.

The task in front of us is to model the information regarding a student, grades, courses etc. in a university registration system. The focus here is not on comprehensiveness but the illustration of using appropriately all the mentioned primitive types as well as type constructor mechanisms one or more times.
The ID of a student is normally a six-digit number with the first two digits signifying the year of joining the university. The types of expected operations on the ID field are just read and one could model this by means of an integer for space efficiency (A string can also be used, but it takes more space). The status of a student can be good or on-probation. This can easily be modelled by a boolean quantity, isOnProbation (or may be as isOnGoodStanding). The GPA is a real number taking values between 0 – 4.0 with a precision of three or more decimal digits. Since arithmetic is performed on it and since it gets recomputed and updated every term, it is appropriate to model it as a float. Coming to the name, there are several components. The first name, last name and zero or more middle initials. The first name and last name can be strings can be modeled as strings since they are expected to be sequences of arbitrary letters. The number of middle-initials to choose is not immediately clear, although each one of them can be a character. A homogeneous aggregate of middle names appears to be appropriate to facilitate easy modification if the need arises to increase the number of middle-initials to maintain. Since the first name and the middle initials are of different types, it is appropriate to model all the components of a name (first, middle, last) as though they form a heterogeneous aggregate.
Now coming to the issue of maintaining grades for students in courses, it will be a waste of space to keep duplicating the course information in the student record of each person who takes it. One could easily maintain a reference to course information by having a reference or number like ics313. Each grade is an association of <course reference/number, section number, term, grade>. They could respectively be modeled as a string (or enumeration if the courses do not change in the univesity), byte, short, and a character. Due to the heterogeneity of components they can all be assembled in a record/structure. A student will have several such records as part of his grade information. Since they are all of the same kind, grades can be an array of maximum number of courses a student is expected to take.
The major of a student refers to a department code. Since, departments (are expected to) last much longer than typical applications, and as there are only a few dozen departments, they could be modeled as an enumeration too. But for applications that last better they can be modeled as strings. The course requirements for a student vary based on the major of the student. The number of grades to be maintained will also vary according to the department. In these cases, the full information in the student record can be partitioned between a fixed portion that is common to all and a particular portion that is dependent on the major of the student. Since a student is expected to take one major, the major field can be used as a discriminant tag to choose the appropriate layout for the major-dependent part. Since a person can be only in one major at a time, it will be sufficient to model the maximum needs of all the alternatives. This will be a case of overlaying or union in C-like languages.
Putting all of them together the following kinds of declarations are appropriate:

Type
   String = array of a certain fixed size of characters.
   MajorType = enumeration of (acct, arch, …, ics, … );
   GradeType = structure of {CourseReferenceType course, byte section, short term, char grade}
   CourseReferenceType = reference to a CourseRecordType that holds information about the course
   NameType = structure of { String firstName, String lastName, array-of-characters middleInitials }
   StudentRecordType = structure of {
	NameType name, long id, float GPA, boolean isOnProbation,
       MajorType major,
       Case major of {
          ics: array of 43 GradeType elements for grades;
          mgmt: ***
      }
}     

Notes:

•	Check the posted solutions (MajorExam-Ikey.rtf) for expected answers.
•	Question 1 is graded by Dr. Sahalu Junaidu.
•	Question 2 is graded by Dr. Talal Maghrabi
•	Question 3 is graded by S. Ghanta
•	If you have any specific concerns regarding a particular question, you may contact the appropriate instructor who graded that question. For any broader issues or general issues, you may consult your instructor.

Comments
General to All Questions

•	Read the question carefully. As a correct solution to an improperly understood question will fetch you no score.
•	A common mistake in spelling: use of P instead of B. Pay particular attention to those words that have a P in them. Whether you spell/pronounce a word correctly or incorrectly, you take the time to use it either in writing or when you speak. The difference in terms of effort between a properly done job and a sloppy job is not much. The results however, in terms of your comprehensibility to others, vary dramatically. In one case the message goes through smoothly and in the other case it is considered non-sense. Why not recognize this and take steps to rectify the situation gradually? The biggest challenge is the recognition of the above and willingness to pay attention.
•	A similar remark about the need for proper formation of comprehensible sentences.

Related to Question 1

•	Aliasing means two pointers pointing to the same cell.	 Why is this a problem?
•	In short answers, try to be as brief as possible, addressing the issue on hand.

Related to Question 2

•	Right most derivation is sought and not the left-most derivation.
•	In left-most or right-most derivations, you apply one rule at a time. 
•	An easy way of establishing ambiguity is by presenting a sentence with two distinct left-most (or right-most) derivations.
•	Mixup between static scoping and dynamic scoping. 
•	You are expected to trace the programs and note the appropriate bindings to the variables.
•	Arithmetic errors: 
•	11/2 + 2 = 15/2 			not 13/2
•	y – 2 > 10  y > 12		not 8

Related to Question 3

•	A proper program with 2D array declarations is expected. It then needs to be converted using only 1-D array support. Such a transformation involves simulating a 2D array using 1D arrays. 
•	Missing declarations
•	Missing initialization
•	Incorrect loop variable
•	Inappropriate limits to the loop variables
•	Inadequate dimensions in the declarations
•	Throwing arbitrary terms like slicing will not make your answer a proper one. You need to use the terms in the proper context.
•	A person uses one array per row of the matrix.
•	Do you change your program just because the data was changed from, say a 3x3 matrix to 4x4?
•	In the modeling problem, you are expected to model the various information appropriately with good justification. When you do so, you would find yourself using almost all the primitive types mentioned as well as the type constructor mechanisms. See the detailed solution presented above with particular emphasis on justification.
•	You were explicitly asked not to use Strings unless nothing else suits the purpose better. You go to the other extent of using strings only that too without any justification.