Paper Info
Title
Recursion Versus Iteration at Higher-Orders
Abstract
We extend the well-known analysis of recursion-removal in first-order program schemes to a higher-order language of finitely typed and polymorphically typed functional programs, the semantics of which is based on call-by-name parameter-passing. We introduce methods for recursion-removal, i.e. for translating higher-order recursive programs into higher-order iterative programs, and determine conditions under which this translation is possible. Just as finitely typed recursive programs are naturally classified by their orders, so are finitely typed iterative programs. This syntactic classification of recursive and iterative programs corresponds to a semantic (or computational) classification: the higher the order of programs, the more functions they can compute.
Year
DOI
Venue
1997
10.1007/BFb0058023
FSTTCS
Keywords
Field
DocType
recursion versus iteration,functional programming,higher order,first order,polymorphism
Discrete mathematics,Programming language,Functional programming,Computer science,Denotational semantics,Theoretical computer science,Syntax,Recursion,Semantics
Conference
ISBN
Citations 
PageRank 
3-540-63876-8
3
0.50
References 
Authors
7
1
Name
Order
Citations
PageRank
A. J. Kfoury146147.34