the complexity of parameter passing in polymorphic procedures
Our subject is at the confluence of two foundational research areas: formal independence results, and higher order data types. A central problem with polymorphism is the impact of involved polymorphic types on termination of program executions and on the complexity of types occurring therein. It is known thattermination of chains of procedure calls is guaranteed for all polymorphic procedures [5]; however, M. O'Donnell [16] and S. Fortune [4] have independently shown that this statement cannot be proved in usual (Peano's) first-order arithmetic, attesting to the potentially complex effect of polymorphic types. Our main result is that termination of polymorphic argument-passing is a statement that cannot be proved even in full (impredicative) second order arithmetic, a theory whose exceeding strength is briefly illustrated.
complexity polymorphic procedure research formalism order data types terminals effect theory argument