One of the problems with programming using higher-order procedures is the absence of formal tools for analyzing the time and space complexity of such procedures. This absence is partially due to the fact that the current mathematical models of computation for higher types are very divorced from the complexity-theoretic concerns. The aim of this project is to work toward constructing a usable, realistic complexity theory for higher-order computation. This research model is partially based on Cook and Kapron's basic feasible functionals (BFFs), which are a class of finite-type functionals that are intended to be the finite-type analogue of PF, the polynomial-time computable functions. At type-2 there is a reasonable body of work which appears to confirm that type-2 BFFs are a reasonable type-2 analog of PF. Natural non-sequential extensions of the type-2 BFFs are investigated and a theory of non-sequential `polynomial-time` functionals is constructed. This extended theory of type-2 BFFs is also used to develop a theory of computational complexity for machine learning. Unlike the situation for type-2, for type-3 (and above), there is not the weight of evidence that the BFFs are a reasonable analog of PF. This research tests several models (partly based on the type-2 complexity) at type-3, by analyzing some higher-order algorithms involving monads, continuations, and other higher-order constuctions. An intermediate goal is to use the experience gained from this work on the complexity of finite-type functionals, to develop `complexity theoretic` solutions to domain equations. Such solutions have the potential of providing settings in which one could examine both semantic and complexity-theoretic features of languages such as ML.
