Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 5 / 5 (Foundations of Computer Science)

Assuming p is an ordinary total Boolean predicate, replace success by true and the search's failure exception by false:The Standard ML handler in the printed function belongs to the else expression: it tries the left subtree and, only if that search raises Blair, tries the right. It does not catch a failing label test at the current node. This scope follows the Standard ML grammar, Appendix B. Short-circuit andalso rejects the current label before visiting either child; short-circuit orelse visits the right child only after the left search fails. Structural induction on the binary tree proves that tony returns true exactly when gordonPlain does, and otherwise raises the exception converted by gordon to false. The exception-free test is the root predicate conjoined with the disjunction of the two subtree tests.

The total-predicate assumption matters: if p itself raises Blair, the original handler can catch it, whereas an implementation with no exception handling cannot in general convert that event to a Boolean result. The displayed replacement implements the intended Boolean tree property, not an exception-catching wrapper for arbitrary exceptional predicates.

For a finite binary tree, gordon p t expresses the existence of a root-to-Lf path on which every branch-node label satisfies p. The empty tree has a length-zero path and returns true. At Br(x,left,right), such a path exists precisely when p x holds and at least one child admits such a path. This is the recursive Boolean equation derived in part (i).

The property is neither “all labels in the tree satisfy p” nor “some label satisfies p”. A bad label in an unchosen subtree does not prevent success, but a bad root label prevents every root-to-leaf path. The traversal performs a left-first search for a qualifying path.

The ML exception type exn contains exception packets and is an extensible datatype: an exception declaration introduces a fresh constructor, optionally with an argument. For example:Empty has type exn, and BadIndex has type int -> exn. These packets are ordinary values which can be passed, returned or stored. raise propagates a packet; the resulting expression can have whatever result type its surrounding context requires, because normal evaluation does not return from the raise.

In exception handling, expression handle pattern => recovery evaluates the recovery for a matching exception packet and otherwise propagates the packet outward. The normal expression and recovery must have the same result type. Handlers are dynamically nested, and exceptions raised in the recovery are not handled again by that same handler. A variable pattern catches every packet, whereas a constructor pattern selects a particular exception. Separate fresh exception declarations create distinct identities even if their printed names coincide; exception rebinding instead aliases an existing constructor. exn packages exceptional information; raise and handle determine its control-flow effect.

If f : 'a -> 'b, then the success constructor applied to f x has type 'b result, and the exception alternative has that same type. ThereforeThe zero comparison fixes the labels to type int, and tony with this predicate accepts an int tree and normally produces a Boolean. The requested expression consequently has typeso the wrapper maps an integer tree to a packaged Boolean result or exception packet.

For ta, the packet Ian true means that a normal successful search occurred: ta has at least one root-to-Lf path all of whose branch labels are nonzero. It can be Lf; if nonempty, its root must be nonzero, but labels away from the successful path need not be. For example, Br(1,Lf,Br(0,Lf,Lf)) succeeds despite containing a zero.

For tb, Cherie Blair means that the search raised the designated exception. Every root-to-Lf path has a zero-labeled branch somewhere. Thus tb is nonempty, but its root need not be zero: Br(1,Br(0,Lf,Lf),Br(0,Lf,Lf)) fails. With the supplied total comparison predicate, tony can return only true or raise Blair, never return false. ta admits an all-nonzero path; tb admits none.