Midterm: Sample Questions (v 1.0)

This page includes questions by the instructor (John Boyland) that may appear on the midterm. At least one question (of the approx. four questions) on the midterm will be all but exactly the same as on this page.

The material on the exam will come from Chapters 1-18. You should be ready to do any of the exercises from the book that does not require research. At least one of the exam questions will be an exercise from the book.

Conceptual Terms

You should be able to define and explain the following concepts:

• Imperative, Functional, Logic, Object-Oriented
• syntax, semantics
• grammar, CFG, production, nonterminal, terminal, token
• lexical structure, phrase structure
• BNF, EBNF, railroad (syntax) diagram
• ambiguous, precedence, associativity
• (concrete) parse tree, (abstract) syntax tree
• classical sequence: compilation, assembly, linking, loading
• interpreters, virtual machines, load-time/execution-time linking
• binding times
• debuggers
• primitive typs, constructed types
• enumerations, tuples, (tagged or untagged) unions, subtypes
• type annotations, type inference, type checking
• ad-hoc polymorphism, overloading, coercion
• universal polymorphism, subtyping polymorphism, parametric polymorphism
• higher-order function, currying
• definition, scope, block, labelled namespace, implicit/primitive namespace
• static scoping, dynamic scoping
• recursive types
• activation record, activation-specific variable
• static allocation of activation records, stack allocation, heap allocation
• nesting links
• objects, fields, methods
• free list, first-fit, coalescing, fragmentation
• heap links, tracing heap links, heap compaction, garbage collection
• interfaces, abstract classes
• exceptions, error handling
• parameters: by value, by result, by value result, by reference, by macro expansion, by name, by need

Programming

The quicksort function we wrote is very inefficient if the list is already sorted. Modify it (code given) to first check if the list is sorted, and simply return the argument in this case.

Another sorting algorithm that is efficient over sorted lists is Bubble-Sort. Bubble sort swaps two adjacent elements if they are in the wrong order. Implement this in ML using a recursive helper function which makes one pass through the list and returns a possibly reordered list with a boolean indicating whether there was any change. Then use another helper function to repeatedly call the helper function until there are no changes. Your bubblesort function may assume the list being sorted is a list of integers. It should work for any length of list.

Write a ``one-line'' program for a polynomial over a ring to evaluate the polynomial at the ``1'' value for the ring assuming that ``1'' is the identity element for the multiplication operation. Use foldr

evalatone ((a,m,z,i): 'a ring) (poly:'a list) = ...

Write a insertBST function to insert an element into a binary search tree (without attempting to keep the tree balanced) and write a SETadd function that uses it to add an element to a SET, where:

type 'a set = 'a tree * ('a * 'a -> bool);

A appendable sequence is like a list but with efficient append implementation. Internally, an append list is one of three forms: an empty sequence, a sequence of one element, or the appending of two sequences. For example the sequence {1,2,3} could be represented as

Append(Append(Empty,Single(1)), Append(Append(Single(2),Append(Empty,Empty)), Single(3)))

• A data type definition for 'a sequence.
• isEmpty: returns whether a sequence is devoid of elements
• The definition of head to return the first element of a sequence. It is OK to crash if the sequence is devoid of elements.
• A mapseq function that takes a function and then a sequence and returns a sequence of the results of running the function on each element.

Activation records

Given the following program:

fun f1 x = 
  let
    fun f2a f = 
      ...
         f x
      ...
    fun f2b y = 
      let
        fun f3 z = y + z
      in
         ... 
	    (f2a f3)
	 ...
      end
  in
    f2b 3
  end;