^CSE3322^

Sample Questions

Also see [Code/] and [eg.sml].


  1. For each of the following programming languages, what is the language best known for?
    1. Algol-60
    2. C
    3. Cobol
    4. Fortran
    5. Haskell
    6. Lisp
    7. Miranda
    8. Prolog
    9. Simula
    10. SML

  2. For each of the following individuals, what significant development in programming languages is the individual best known for?
    1. John Backus.
    2. Alonzo Church.
    3. Peter Henderson.
    4. Grace Hopper.
    5. Ada Byron, Countess of Lovelace.
    6. Robin Milner.
    7. Peter Naur.
    8. Christopher Strachey.
    9. John von Neumann.

  3. 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.
  4. What does `first-class value' mean when discussing programming languages. Give examples from C and SML to illustrate their views on first-class values.
  5. Evaluation strategies:
    1. What is strict evaluation (also known as eager evaluation)?
    2. What is non-strict evaluation (also known as lazy evaluation)?
    3. Give an example program that requires non-strict evaluation if the program is to run correctly. Explain why.
    4. Which evaluation strategy is used in:
      1. C
      2. Haskell
      3. Java
      4. Miranda
      5. SML

  6. 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.
    1. length xs > 0
    2. take n (map f s)
    3. append (append a b) c
    4. map f (map g s)
    5. height T > 0
    In each case, briefly say why your expression is more efficient than the given expression. See standard functions: [eg.sml].
  7. 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?
    1. val f1 = foldl (fn x => fn y => x orelse y) false
    2. val f2 = foldl (fn x => fn y => x andthen y) true
    foldl is in [eg.sml].
    1. What does the following function, mystery, calculate? (What, not how.)
    2. What is the function's type?
    3. How does the compiler infer that type?
    4. 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;

  8. 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
    
      abcdef
    e1      
    e2      
    e3      
    e4      
    e5      
    e6      
    e7      
    Put a tick (can call) or a cross (cannot call) in each box.
  9. 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
    
      abcdef
    e1      
    e2      
    e3      
    e4      
    e5      
    e6      
    e7      
    Put a tick (can call) or a cross (cannot call) in each box.
  10. 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?

    1. fun curry fu x y = fu (x,y)
    2. 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.

    1. curry curry
    2. curry uncurry
    3. uncurry curry
    4. uncurry uncurry

  11. 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;
    
    1. What type does isBST actually have in SML?
    2. What language feature would SML need for isBST to have the type  't Tree -> Bool  (where 't can be int, real, char, string, etc.)?
    3. What is the standard work-around in SML for the lack of this language feature?
    4. Rewrite isBST using the standard work-around.

  12. 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]]

  13. 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...).

    1. 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?
       avbvcvdvmv
      a          
      b          
      c          
      d          
      main          
    2. Draw the stack when procedure b is executing. Show all necessary links and registers.
    3. 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*).
    

  14. 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*)
    
    1. What is the program's output if the language uses dynamic binding?
    2. What is the program's output if the language uses dynamic binding?
    3. Give a possible advantage of static binding over dynamic binding.
    4. Give a possible advantage of dynamic binding over static binding.

  15. Overloading:
    1. What is overloading as a programming language concept?
    2. What is context independent overloading as a programming language concept?
    3. What is context dependent overloading as a programming language concept?
    4. Does SML use context dependent overloading or context independent overloading?
    5. Give a simple expression which is ambiguous under context dependent overloading. Say Why.

  16. Garbage collection:
    1. What is a garbage collector in a programming language?
    2. Define the mark-scan garbage collection algorithm.
    3. Give an advantage of a programming language having a garbage collector.
    4. Give a disadvantage of a programming language having a garbage collector.
    5. Give two features of a programming language that require, or strongly imply, the use of a garbage collector in an implementation of the language.

  17. Parameters: Here is a program in a hypothetical language. What is its output if all parameters are
    1. passed by value (by input),
    2. passed by input-output,
    3. passed by reference,
    4. 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]);
     }
    

  18. Parameters: What does the following program print if
    1. parameter x is passed by-reference? Why?
    2. 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
    

  19. 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.

    1. Draw the stack when procedure d is executing.
    2. 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*).
    

  20. 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
    The compiler is in the act of analysing the fragment of program P; show the output of
    1. lexical analysis,
    2. syntax analysis,
    3. semantic analysis, and
    4. code generation.
    for the fragment. State any assumptions that you make.
  21. 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?
    1. abb
    2. bcacb
    3. bbccac
    4. bcacba
    5. bcab

  22. 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
    
    1. The above grammar recognizes a regular language. Give a regular expression for the language of this grammar.
    2. 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.

  23. 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.
    1. Give FOLLOW and FIRST sets for each non-terminal symbol.
    2. Construct the parsing table for a non-recursive predictive parser for this grammar.
    3. Is the grammar LL(1)? If not say why not.
    4. Show how a non-recursive predictive parser will parse the sentence dace using the table that you constructed above.

  24. 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 -> ε
    
    1. Compute FIRST(A), FIRST(B), and FIRST(S).
    2. Compute FOLLOW(A), FOLLOW(B), and FOLLOW(S).
    3. 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.
    4. 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.

  25. 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.
    1. Why is the grammar unsuitable for directly implementing a recursive-descent parser? Identify the production(s) that cause the problem.
    2. Modify the grammar (without changing the language it defines) so that it can be implemented directly in a recursive-descent parser.

  26. 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.
    1. Give the canonical collection of LR(0) items for this grammar (remembering to first augment it with a new start symbol S').
    2. Compute the FOLLOW sets for all non-terminals and give the SLR parsing table (action and goto) for this grammar.
    3. Detail how and SLR parser will parse the sentence abbc using the SLR table you constructed above.

  27. 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
    
    1. Compute
      1. I0 = closure({S' -> .S})
      2. goto(I0, a)
      3. goto(I0, b)
      4. goto(I0, +)
      5. goto(I0, A)
      6. goto(I0, B)
      7. goto(I0, S)
    2. Consider the following LR parsing table for this grammar
      STATE ACTION    GOTO 
      ab+$SAB
      0 s1s2r4r6534
      1 s1 r4  6 
      2  s2 r6  7
      3   s8r6   
      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.


LA for B. Computer Science, B. Software Engineering, B. Science (Computer Science), and double degrees. Faculty of Information Technology (Clayton School of IT), ('05 was School of Computer Science and Software Engineering), Monash University, Australia 3800.
Created with "vi (Linux & Solaris)",   charset=iso-8859-1