Midterm: Sample Questions

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-14. 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
• messages, instance versus class variables/methods
• free list, first-fit, coalescing, fragmentation
• heap links, tracing heap links, heap compaction, garbage collection
• mark, sweep, copy collection

ML 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 that takes in a list of vectors and returns a list of vectors that span the same set of vectors while being orthogonal to each other. The idea is that we replace each vector with the residue od it against the remaining vectors. Use foldr.

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);

An 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. For example isEmpty (Append(Empty,Empty)) should return true.
• 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;

Squeak Programming

Implement a BST structure with Node and Tip classes in Squeak.

Implement a flatten message that returns a ConsCell list of all the elements in a BST.

Implement a validFrom:to: message that checks that all values in the tree are between the two given bounds. nil as a bound means the bound is unlimited.

Implement a toBst: message on ConsCell lists that takes an integer n and returns a balanced BST of the first n nodes, and sets its own tail to be the remaining nodes after the first n. The operation is destructive of the list.