Paper: The Hierarchy of Finitely Typed Functional Programs (Short Version) (at LICS 1987)

Authors: Assaf J. Kfoury Jerzy Tiuryn Pawel Urzyczyn

Abstract

Finitely typed functional programs are naturally classified by their levels. We prove that this syntactic classification of functional programs corresponds to a semantical classification: the higher the level of functional programs, the more functions they can compute. We achieve this result by a detour through imperative languages that operate on higher-order pushdown stores and higher-order arrays.
A lower bound on the computational power of functional programs of a finite level k is obtained by translating into them the class of flowcharts equipped each with a level-k pushdown store; this translation is based on a call-by-name operational semantics.
An upper bound on the computational power of functional programs of level k is obtained by reducing their spectral complexity to the spectral complexity of flowcharts equipped with level-k arrays; this reduction uses the denotational semantics of our functional language.

BibTeX

  @InProceedings{KfouryTiurynUrzyczy-TheHierarchyofFinit,
    author = 	 {Assaf J. Kfoury and Jerzy Tiuryn and Pawel Urzyczyn},
    title = 	 {The Hierarchy of Finitely Typed Functional Programs (Short Version)},
    booktitle =  {Proceedings of the Second Annual IEEE Symposium on Logic in Computer Science (LICS 1987)},
    year =	 {1987},
    month =	 {June}, 
    pages =      {225--235},
    location =   {Ithaca, NY, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }