New version page

UT CS 345 - Final Exam

Upgrade to remove ads

This preview shows page 1-2 out of 7 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

CS 345—Fall 2002 page 1 of 7 SuggestedFinal Exam A Solutions2 January 20031. [20] Here, as a reminder, are some examples of Haskell type expressions:Inta -> bTree a -> (a -> Int) -> [Employee]((Int, Bool) -> (Int,Bool,Bool)) -> [(Int,Bool)]Write an EBNF grammar for Haskell type expressions (not including type-classcontexts such as “Eq => ”). Remember that the operator (->) is right-associative.Type ::= Id { Id } | ‘ [’ FunType ‘ ]’ | ‘ (’ FunType { , FunType } ‘)’FunType ::= Type | Type -> FunTypeId ::= Letter { Letter | Digit }Letter ::= a | b | … | z | ‘ A’ | ‘ B’ | … | ‘Z’Digit ::= 0 | 1 | … | 92. [10] Translate the following Haskell function> q :: Int -> Int -> Int> q x d = if x<d then 0 else 1 + q (x-d) da. into an equivalent Haskell function which uses only tail recursion> q1 :: Int -> Int -> Int> q1 x d = let quot x q = if x<d then q else quot (x-d) (q+1) in quot x 0b. into an equivalent C function which uses no recursion at all (and uses no divisionoperators).int q2( int x, int d ){int q = 0;while( x >= d ){x = x - d ;q = q + 1}return q;}3. [10] Use the method of weakest preconditions to determine the truth (or otherwise) ofthis proposition:{x < y+ 3 } x , y := y – 1 , x +5 {y < x + 2 }.w p “ x , y := y – 1 , x + 5 ” (y < x + 2 )= {def. ‘:=’}(y < x + 2 )x , yy – 1 ,x + 5 = {substitution}x + 5 < y – 1 + 2 )= {simplification}x < y – 4‹/ {predicate calculus, counterexample: let x = 2, y = 0}x < y + 3So the proposition is false. !CS 345—Fall 2002 page 2 of 7 SuggestedFinal Exam A Solutions2 January 20034. [10] Translate the following guarded-command program into C. Assume that the type ofall variables is integer.do x < y Æ x ,y := x+y,x –y I x > y Æ x := z–y ; y := x–z odA solution:while ( x != y ){ if ( x < y ){ int t = x+y; y = x-y; x = t; } else { x = z-y; y = x-z; }}5. [10] Give the type (if any) of the following expression, assuming that integer and boolare distinct typesif x <21 or 3<6 then x +5 else z<4a. assuming static type checkingtype error: the true branch has type integer, and the false branch has type bool.b. assuming dynamic type checkingthe type is int because the guard is true6. [5] Given this program fragment:struct R { int x; double y; };R x[20];cout << x[10];and assuming that sizeof( int ) = 4 and sizeof( double ) = 8 , rewrite the expression x[10]to give the same result without using array indexing:*(x+10)CS 345—Fall 2002 page 3 of 7 SuggestedFinal Exam A Solutions2 January 20037. [15] What is output by the following programint x = 4;function pow( int n, int exp ) : int;{int r = 1;while( exp > 0 ){r := r * n;exp := exp - 1;}return r;}function inc( int k ) : int{k := k+1;return k;}procedure main(){print( pow( inc(x), 3 ) ); print( x );}a. assuming that arguments are bound to parameters by value125 (i.e., 5 * 5 * 5) 4b. assuming that arguments are bound to parameters by name210 (i.e., 5 * 6 * 7) 7c. Rewrite the functions so that call-by-name gives the same results as call-by-value.function pow( int n, int exp ) : int;{int r = 1;int n1 = n;int e = exp;while( exp > 0 ){r := r * n1;e := e - 1;}return r;}function inc( int k ) : int{return k+1;}CS 345—Fall 2002 page 4 of 7 SuggestedFinal Exam A Solutions2 January 2003 8. [20] The following fragmentary program text contains a type definition, declarations ofseveral variables, and five references to the variables. After each variable reference is apair of braces containing a letter (for example, { A }); for each such letter, there is a linein the table following the program.To answer this question, write the address information that a compiler would generatefor each of the variable references in the appropriate line of the table. Assume• a typical stack implementation• space allocation for variables in the order in which they are declared, beginning withoffset 0• no requirement that variables be aligned on word boundaries.Assume that addresses identify bytes, and that the basic data types’ space requirements(in bytes) are as follows:bool: 1 char: 2 int : 4 float : 10The program: type ST = record n : char; case b : bool of false : (x : int ) true : (y : float ) end end ; a : int [5]; b : ST; c : char; procedure doit() b : float ; c : bool; begin ... a[2] { A } ... c { B } end doit; procedure main() r : ST; s : char; begin ... b.x { C } ... c { D } ... r.y { E } ... end main;Answer by filling in the table. Indicate the distinction between local and global variablesby appending a G to global-variable references. If a reference is invalid, explain. Partialcredit may be given for incorrect answers, but only if you’ve shown your work.First we compute the space requirements for type ST:n char 2 0-1b bool 1 2-2x int 4 3-6y float 10 3-12Then we build a table for each block showing each variable’s size and its address(es) in itsblock’s activation record.(global) a int[5] 4*5 = 20 0–19b ST 13 20-32c char 2 33–34doit b float 10 0-9c bool 1 10-10main r ST 13 0-12s char 2 13-14Then we use the address information to fill in the references’ activation-record addresses:A. 8 G (= 0+2*4)B. 10C. 23 GD. 33 GE. 3CS 345—Fall 2002 page 5 of 7 SuggestedFinal Exam A Solutions2 January 20039. [10] Suppose variables A and B are both 4-element arrays of integers, and the followingcode is executed:for i = 0 to 3 do A[i] := 1;A[1] := 2;B := A;A[2] := 3;B[3] := 4Give the post-execution values of A and B by filling in the following tables, assuming thevariables havea. value semantics.0123A1231B1214b. reference semantics.0123A1234B123410. [10] This C++ struct represents fractions by their integer numerators and denominators.struct Fraction{int numerator, denominator;};The following code normalizes fractions:Fraction f;if( den( f ) < 0 ){num( f ) = - num( f );den( f ) = - den( f );}int cd = gcd( num( f ), den( f ) );num( f ) = num( f ) / cd;den( f ) = den( f ) / cd;Define the functions num and den so that this code would work.int& num( Fraction& f ) { return f.numerator; }int& den( Fraction& f ) { return f.denominator; }11. [5] You are given the following C++ definition:template <typename T>T min( T x, T y ){ return x < y ? x : y; }Define min in Haskell, making its meaning as similar as possible to the C++ …


View Full Document
Download Final Exam
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Final Exam and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Final Exam 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?