@inproceedings{de642bc4d86940eead4a6df1d3c7b559,
title = "Adventures in time and space",
abstract = "This paper investigates what is essentially a call-by-value version of PCF under a complexity-theoretically motivated type system. The programming formalism, ATR1, has its first-order programs characterize the poly-time computable functions, and its second-order programs characterize the type-2 basic feasible functionals of Mehlhorn and of Cook and Urquhart. (The ATR1-types are confined to levels 0, 1, and 2.) The type system comes in two parts, one that primarily restricts the sizes of values of expressions and a second that primarily restricts the time required to evaluate expressions. The size-restricted part is motivated by Bellantoni and Cook's and Leivant's implicit characterizations of poly-time. The time-restricting part is an affine version of Barber and Plotkin's DELL. Two semantics are constructed for ATR1. The first is a pruning of the na{\"i}ve denotational semantics for ATR1. This pruning removes certain functions that cause otherwise feasible forms of recursion to go wrong. The second semantics is a model for ATR1 's time complexity relative to a certain abstract machine. This model provides a setting for complexity recurrences arising from ATR1 recursions, the solutions of which yield second-order polynomial time bounds. The time-complexity semantics is also shown to be sound relative to the costs of interpretation on the abstract machine.",
keywords = "Languages, Performance, Theory",
author = "Norman Danner and Royer, {James S.}",
year = "2006",
doi = "10.1145/1111037.1111053",
language = "English (US)",
isbn = "1595930272",
series = "Conference Record of the Annual ACM Symposium on Principles of Programming Languages",
publisher = "Association for Computing Machinery (ACM)",
pages = "168--179",
booktitle = "Conference Record of POPL 2006",
address = "United States",
note = "33rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL'06 ; Conference date: 11-01-2006 Through 13-01-2006",
}