Compare rst-order functional programs with higher-order programs allowing functions as function parameters. Can the the rst program class solve fewer problems than the second? The answer is no: both classes are Turing complete, meaning that they can compute all partial recursive functions. In particular, higher-order values may be rst-order simulated by use of the list constructor \cons" to build function closures. This paper uses complexity theory to prove some expressivity results about small programming languages that are less than Turing complete. Complexity classes of decision problems are used to characterize the expressive power of functional programming language features. An example: second-order programs are more powerful than rst-order, since a function f of type Bool]->Bool is computable by a cons-free rst-order functional program if and only if f is in ptime, whereas f is computable by a cons-free second-order program if and only if f is in exptime. Exact characterizations are given for those problems of type Bool]->Bool solvable by programs with several combinations of operations on data: presence or absence of constructors; the order of data values: 0, 1, or higher; and program control structures: general recursion, tail recursion, primitive recursion. Does the programming style we use a ect the problems we can solve, or the e ciency of the programs we can write to solve a given problem? Some questions especially relevant to this journal: 1. Does the use of functions as data values give a greater problem-solving ability? 2. Is recursion more powerful than iteration? 3. Would the use of a strongly normalizing programming language, as proposed by several researchers, including (Crockett, Spencer, 1991) , (Voda, 1994) , (Turner, 1996) , and (Lloyd, 1999) , impose any limitations on the problems that can be solved? This paper gives some answers to these questions, when restricted to simply typed functional programs without \cons". In particular, the answer to question 1 is This research was partially supported by the Danish Natural Science Research Council (DART project). \yes," higher-order programs can solve problems that rst-order programs cannot. The answer to question 2 for rst-order programs is \yes" if and only if ptime 6 = logspace (and so not likely to be decided in the foreseeable future). A partial (positive) answer to question 3 will be given later. Programming styles. Factors that a ect e ciency and ease of programming include the forms of control that are used: general recursion, primitive recursion, tail recursion, exceptions, backtracking, etc.; the data operations used: is data basic or higher order, is it untyped or typed by various regimes, are \logic variables" allowed, etc.; and other semantic issues: eager or lazy evaluation, memoization of function results, presence or absence of a global state, static or dynamic name binding, etc. Our main goal is to understand (and delineate) the expressive power of various programming language features. In general, one can distinguish between absolute expressivity questions and relative expressivity questions. An \absolute expressivity" question on programming language feature X: \Do there exist problems that can be solved by programs with feature X, and cannot be solved without feature X?" A \relative expressivity" question: \Is there a problem that can be solved both with and without feature X, but such that any solution without feature X is necessarily less e cient than some solution using X?" (E ciency will measured by time usage throughout this paper.) How can expressivity questions be formulated in a precise and meaningful way, and how can their answers be found? Our approach is to use complexity theory, which provides a powerful means to classify problems according to their solution difculty. In particular, there are theorems proving that, under suitable assumptions, increasing the available computation time provably enlarges the class of problems that can be solved, with analogous results for other resources such as memory. An obstacle to studying absolute expressivity. Absolute expressivity questions are irrelevant to su ciently strong languages. The reason is that any Turing complete language can compute all partial recursive functions (modulo data encoding) { and thus in an absolute sense all are equally expressive. We get around this by studying Turing-incomplete sublanguages. Obstacles to studying relative expressivity. One di culty is the existence of many rather e cient simulations of one programming language feature by others. A consequence is that in a strong language it is hard to answer relative expressivity questions since any expected complexity di erences would be very small. This is due to the ability e ciently to \program your way around a problem" in a su ciently strong language. Two related facts of this sort follow. (Running time is measured as the number of atomic computational steps as a function of input length n.) A random-access machine can simulate a rst-order or higher-order functional program (or Turing machine) with at most a constant slowdown. A rst-order functional program can simulate a random-access machine with at most a logarithmic slowdown, from time T(n) to T(n) log T(n). Such results tend to minimize the meaning of di erences in programming paradigm, provided the languages involved are su ciently rich in ways to \program around." Our approach to studying expressivity. A language having unbounded storage/memory for data values, plus control allowing an unbounded number of operations on data values, will almost certainly be Turing complete. A way around this obstacle is progressively to restrict language features, removing one at a time until the resulting programming language is no longer Turing complete, and then to use computability and complexity theory to compare the absolute expressive power of the resulting \minilanguages." The e ect is to study expressivity of language constructions using complexity theory to compare di erent choices of language features. We precisely characterize, in terms of complexity classes, the e ects on expressive power of various combinations of three program restrictions. The rst concerns creation of new storage: are constructors of structured data allowed, or not? The second concerns the order of data values: 0, 1, or higher. The third concerns program control structures: general recursion, or only tail recursion, or only primitive recursion. The links are summed up in the table of Figure 2 .1, and con rm programmers' intuitions that higher-order types indeed give a greater problem-solving ability. In this paper we prove only the results of rows 3 and 4, the others being included for the sake of context. Many combinations are Turing-complete, so such programs compute all the partial recursive functions. A classic Turing-incomplete language is got by restricting data to order 0 and control to \fold." Such programs compute the primitive recursive functions. Figure 2 .1 shows the e ect of higher-order types on the computing power of programs of type Bool]->Bool. Each entry is a complexity class, i.e., the collection of decision problems solvable by programs restricted by row and column indices. ro stands for \read-only," i.e., programs without constructors, and rw stands for \read-write." say meaningful things about programming languages. Complexity theory is traditionally used to classify hardness of decision problems, so we need to link decision problems with programs and their computations. Linking decision problems and functional programs. In complexity theory a decision problem A is a set of strings over a nite alphabet , so A . A solution to the problem is an algorithm that, given any x = a 1 a 2 : : : a n 2 , decides whether or not x 2 A. We can without loss of generality choose = f0; 1g, since larger alphabets can be encoded as bit strings. The characteristic function f A of set A f0; 1g , of type type f A : f0; 1g ! f0; 1g, satis es for all a 1 ; a 2 ; : : : ; a n 2 f0; 1g f(a 1 a 2 : : : a n ) = if a 1 a 2 : : : a n 2 A then 1 else 0 Henceforth we shall identify 0,1 with False, True and encode string a 1 a 2 : : : a n as boolean list a 1 ; a 2 ; : : : ; a n ], making the analogy between decision problems and programs with input-output type Bool] -> Bool exact. More generally, Figure 2 .1 concerns computational power of fully typed functional programs whose internal types are limited to ones formed from Bool and Bool] by function spaces ! 0 and Cartesian products 0 . No type of numbers is included, since if the numbers are bounded they can be simulated by tuples of Booolean variables; and if the numbers are unbounded, strange and unrealistic computations can be performed (as will be seen below). Further  The column indices restrict the orders of program data types. An \order k + 1" program can have functions of type ! 0 where data type is of order k. Thus, for instance, the rst column describes rst-order programs, whose parameters are booleans or lists of booleans. Each entry is the collection of decision problems solvable by programs restricted by row and column indices. Row 1: These program classes are all Turing complete. Consequently they can accept exactly the recursively enumerable subsets of f0; 1g . Row 2: These programs have unlimited data operations and types, but control is limited to primitive recursion, familiar to functional programmers under the name \fold right". 1 Such rst-order programs accept exactly the sets whose characteristic functions are primitive recursive (true regardless of whether data are strings or natural numbers). Higher-order primitive recursive functions appeared in G odel's System T many years ago (Girard, Lafont, Taylor, 1989) , (Voda, 1997) . They are currently of much interest in the eld of constructive type theory due to the Curry-Howard isomorphism, which makes it possible to extract programs from proofs. Primitive recursion comes because of proofs by induction; extraction of programs using general recursion is much less natural. Row 3: These programs have unlimited control, but allow only read-only access to their data. List destructor operations hd and tl are allowed, but not the constructor cons. Even though this may seem a draconian restriction from a programmer's viewpoint, the class of problems that can be solved is respectably large. Order 1 programs can solve any problem that lies in ptime; order 2 programs, with rst-order functions as data values, can solve any problem in the quite large class exptime, etc. In general, any increase in the order of data types leads to a proper increase in the solvable problems, since it is known that ptime is properly contained in exptime, and so on up the hierarchy. Row 4 characterizes read-only programs restricted to tail recursion, in which no function may call itself in a nested way. Order 1 tail recursive programs accept all and only problems in logspace, a well-studied subset of ptime. Higher-order tail recursive programs accept problems in the (properly) larger space-bounded classes pspace, expspace, etc. (Tail recursion is of operational interest because at run time (assuming eager evaluation, i.e., call-by-value semantics) the call stack depth has a constant depth bound, regardless of input data. Such a program may be converted to nonrecursive imperative form by replacing each function call by a GOTO, and realizing function parameter passing by assignments to global variables.) 1 Kleene's de nition of primitive recursion is a bit more general than \fold right," but is easily programmed using fold right and composition. See (Hutton, 1999) for details. Row 5 characterizes read-only programs restricted so all recursion must be expressed using \fold right," i.e., only primitive recursion is allowed. Order 1 read-only primitive recursive programs accept only problems in logspace and are thus equivalent to tail-recursive programs. At higher orders this equivalence vanishes; the primitive recursive read-only programs' abilities to solve decision problems grow only at \half speed": a data order increase of 2 is needed to achieve the same increase in decision ability that an increase of 1 achieved for general or tail recursive programs. Limit of rows 3, 4 and 5 It is clear that the union of the classes in row 3 equals the union for row 4 and for row 5. This is the class of problems solvable in time bounded by 2 2 2 n , where the height of the exponent stack is any natural number. This is well-known as the class of elementary sets, and was studied by logicians before complexity theory began. Scope and contribution of this paper. The results in Rows 1 and 2 are classical, and not repeated here. We prove the results in rows 3 and 4 of Figure 2 .1. The results in Row 4 appear to be new; and the results in Row 3, while in a sense anticipated by (Goerdt, 1992) , are here proven for the rst time in a programming language context. The results in Row 5 are obtained from (Goerdt, 1992) and (Goerdt, Seidl, 1996) by re-interpreting results from nite model theory as sketched in the Appendix. It has long been known that order k + 1 primitive recursive programs are properly more powerful than order k primitive recursive programs, i.e., prim k rec. prim k+1 rec. This is of little practical interest, however, since even the order 0 class prim.rec. is enormous, properly containing such classes as nptime and elementary. Does the use of functions as data values give a greater problem-solving ability? By Figure 2 .1 the answer is \no" for unrestricted programs, and \yes" for all the restricted languages we consider. The only uncertainty is with the read-only primitive recursive programs; for these, an increase in data order of at least 2 is needed in order to guarantee a proper increase in problem-solving power. Is general recursion more powerful than tail recursion? For rst-order read-only programs, this question has classical import since, by the table's rst column (rows 3, 4) this is equivalent to the question: Is ptime a proper superset of logspace? This is, alas, an unsolved question, open since it was rst formulated in the early 1970s. An equivalent question (rows 3, 5): Is general recursion more powerful than primitive recursion? However the situation is di erent for second and higher orders. For higher-order read-only programs, the question of whether general recursion is stronger than tail recursion is also open, equivalent to exptime pspace? But the answer is \yes" when comparing general recursion to primitive recursion, since it is known that exptime properly includes ptime. On strongly normalizing languages. If we assume as usual that programs in a strongly normalizing language have only primitive recursive control, there exist problems solvable by read-only general recursive programs with data order 1; 2; 3; : : :, but not solvable by read-only strongly normalizing programs of the same data orders. This suggests an inherent weakness in the extraction of programs from proofs by the Curry-Howard isomorphism. Row 3, column 1 of Figure 2 .1 asserts that rst-order cons-free read-only programs can solve all and only the problems in ptime. Upon re ection this claim seems quite improbable, since it is easy (without using higher-order functions) to write cons-free read-only programs that run exponentially long before stopping. For example: f x = if x = ] then true else if f(tl x) then f(tl x) else false runs in time (2 n ) on an input list of length n (regardless of whether call-by-value or lazy semantics are used), due to computing f(tl x) again and again. What is wrong? The seeming paradox disappears once one understands what it is that the proof accomplishes 2 . It has two parts: Construction 1 shows that any rst-order cons-free read-only program decides a problem in ptime. Method: show how to simulate an arbitrary rst-order cons-free read-only program by a polynomial-time algorithm. Construction 2 shows that any problem in ptime is computable by some rstorder cons-free read-only program. Method: show how to simulate an arbitrary polynomial-time Turing machine by a rst-order cons-free read-only program. The method of Construction 1 in e ect shows how to simulate a cons-free readonly program faster than it runs. It is not a step-by-step simulation, but uses a nonstandard \memoizing" semantic interpretation. (For the example above the value of f(tl x) would be saved when rst computed, and fetched from memory each time the call is subsequently performed.) The method of Construction 2 yields programs that almost always take exponential time to run; but this is not a contradiction since by Construction 1 the problems they are solving can be decided in polynomial time. 3 Related work and acknowledgements Much work that relates complexity and logical or programming languages has different starting points and motivations. Many papers have as goal to characterize 2 For rst-order cons-free read-only programs see (Jones, 1997; Jones, 1999) , which uses a technique from (Cook, 1971) . For higher-order read-only programs, see Theorem 7.17 later in this article. resource-bounded computational complexity classes in terms of logical, recursiontheoretic or other formalisms. Examples (ordered by increasing distance from programming languages) include recursive functions, the lambda calculus, program schemata, nite model theory, and category theory. Work directly relating programming languages and complexity theory. This paper's aim is precisely to characterize the computational power of several restrictions of a realistic programming language. (Jones, 1999) is one of the few papers focused on that interface; it characterizes the power of rst-order read-only programs in complexity terms. The logspace and ptime entries in column 1 appear there, and in (Jones, 1997) as Theorems 24.1.7, Corollary 24.2.4 and Theorem 24.2.5. Here these results are extended to arbitrary nite data orders, and to tail recursive programs. The results have still deeper roots. The logspace result strengthens a \folklore" result on multihead read-only Turing machines; and the ptime result corresponds to a result on \two-way auxiliary pushdown automata" proven by Cook, before his P-NP paper (Cook, 1971) . The contribution of (Jones, 1997; Jones, 1999) was to re-express Cook's result using a recursive programming language. Relative expressivity. A signi cant step forward in relative expressivity (a eld with many conjectures but few proven results) was (Pippenger, 1997), which showed that pure LISP must be slower by a logarithmic factor than \impure" LISP. More precisely, a certain problem (applying a permutation on-line) was proven to require time (n log n) in pure Lisp, but to be solvable in time O(n) in impure Lisp with setcar and setcdr. Interestingly, (Bird, Jones, De Moor, 1998) show that the same problem can be solved in time O(n) in a language with lazy evaluation, so such languages are intrinsically faster than rst-order eager languages. A proof that their construction actually runs in linear time is found in (Neergaard, 1999) . Recursive function and category theory. Recursive function de nition schemes can be regarded as de ning programming languages, for instance the primitive recursive function de nitions, and the subhierarchy studied by (Grzegorczyk, 1953) and others. (Cobham, 1964) gave an early characterization of ptime involving external size bounds analogous to those of Grzegorczyk, but using recursion on notation. (Voda, 1994) relates primitive recursion and subrecursion to programming languages, using a data structure like that of (Jones, 1997 ). An \intrinsic" approach characterizing ptime by tiered recursion on notation 3 is seen in (Bellantoni and Cook, 1992) , and has inspired much work since then, some involving categorical concepts (Bellantoni, Niggl, Schwichtenberg, 1998; Hofmann, 1999) . Typed lambda calculi. A series of papers by Leivant (some with Marion) characterize complexity clases in terms of simply typed lambda calculi with recurrence constants, 3 The idea is that recursion over inputs is allowed ( rst tier), but not recusrsion over computed values (second tier). A type system keeps track of the tier levels. including (Leivant, 1989; Leivant and Marion, 1993; Leivant and Marion, 1999) . In particular they study calculi extended by functions and operations on an algebra of words over f0; 1g, and characterize ptime, pspace and several other classes. The earlier works had rather complex formulations mostly related to rami ed recurrence, but (Leivant, 1999) Program schemata. (Paterson, Hewitt, 1970 ) was a pathbreaking early paper, and recursion removal has been a recurring theme in this eld. Complexity characterizations related to data types appear in (Kfoury, Tiuryn, Urzyczyn, 1987) and (Kfoury, Tiuryn, Urzyczyn, 1992) . The di erence between recursion and iteration when higher order data are involved is studied in (Kfoury, 1997; Kfoury, 1999). From a schematic viewpoint, answers to the questions asked about program behavior must be valid for all possible interpetations of the domains and base functions appearing in a given program. Such results are less directly relevant to programming languages than ours; programmers naturally use a single, xed data interpretation. Finite model theory. Many complexity characterizations have been made of problems involving nite model theory, with (Jones, Selman 74) apparently the rst in a eld developed quite considerably since then (Gurevich, 1983; Gurevich, 1984; Immerman, 1987; Goerdt, 1992) . There is a natural connection between computation by read-only programs and in nite model theory as de ned by Gurevich and others, close enough that some complexity characterizations from nite model theory imply corresponding results about read-only programs. The connection requires enough de nitional machinery, though, that to avoid breaking the continuity of the presentation we defer it to an Appendix. The only results we do not prove here using functional programming are those of row 5. Finite model versions of the logspace and ptime entries in column 1 were shown by Gurevich. Goerdt proved nite model versions of all of row 3. Some rather complex constructions establish the rst 4 columns in row 5 in (Goerdt, 1992; Goerdt, 1992); and (Goerdt, Seidl, 1996) shows that the space-time alternation extends to arbitrary data orders. Acknowledgements. Thanks are due to Bruce Kapron, for pointing out the similarity between Gurevich and Goerdt's nite model theory results with mine on rst-order read-only programs; to the anonymous referees; to Amir Ben-Amram for many useful dis-
In REF Jones characterizes PTIME by means of simple constructor free programs.
The Expressive Power of Higher-order Types or, Life without CONS
J. Funct. Program.
J. Funct. Program.
Computer Science