Nuprl's Class Theory and Its Applications

unofficial copies [PDF], [PS]

by Robert L. Constable and Jason Hickey

Foundations of Secure Computation, F. L. Bauer and R. Steinbruggen (eds.), pp. 91-115, IOS Press:Amsterdam, 2000.


This article presents a theory of classes and inheritance built on top of constructive type theory. Classes are defined using dependent and very dependent function types that are found in the Nuprl constructive type theory. Inheritance is defined in terms of a general subtyping relation over the underlying types. Among the basic types is the intersection type which plays a critical role in the applications because it provides a method of composing program components. The class theory is applied to defining algebraic structures such as monoids, groups, rings, etc., and relating them. It is also used to define communications protocols as infinite state automata. The article illustrates the role of these formal automata in defining the services of a distributed group communications system. In both applications the inheritance mechanisms allow reuse of proofs and the statement of general properties of system composition.