Life without CONS

Опубликовано 2 июля 2017, 0:18

Can higher-order functional programs solve more problems than first-order programs? Answer: NO, since both program classes are Turing complete. The reason is that higher-order values can be simulated by first-order values: use function "closures" built by the list constructor "CONS".

Complexity theory characterizes the expressive power of "cons-free" programs with different data orders and control structures. We characterize exactly the problems of type [Bool]->Bool solvable by programs with respect to DATA: presence or absence of constructors, and data types (order 0, 1, or higher); and CONTROL: general recursion, tail recursion, primitive recursion. An instance for first-order cons-free programs: general recursion is more powerful than primitive recursion (e.g. "fold") if and only if PTIME properly contains LOGSPACE. (This is a long-standing open problem in complexity.)

Second-order cons-free programs are more powerful than first-order: a function of type [Bool]->Bool is in PTIME iff it is first-order cons-free computable; and in EXPTIME iff it is second-order cons-free computable. (PTIME is known to be a strictly smaller class that EXPTIME.)

Further, deterministic cons-free programs characterize a complexity hierarchy. Programs with data orders 0, 1, 2, ... can solve exactly these problems:

PTIME < EXPTIME < EXP2TIME < ... < ELEMENTARY,

What happens if we add NON-determinism? Using some clever programming with first-order functions as data, Kop and Simonsen obtain a surprising result (2017), that this hierarchy "collapses" at second order:

PTIME < ELEMENTARY = ELEMENTARY = ... = ELEMENTARY

See more on this video at microsoft.com/en-us/research/v...