Functional Domains of Applicative Languages

Abstract

The expressive power of a particular applicative language may be characterized by the set of abstract directly representable in that language. The common FUNARG and applicative order problems are scrutinized in this way, and the effects of these weaknesses are related to the inexpressibility of classes of functions. Certain computable functions which are inexpressible in the lambda calculus are identified, and it is established that the interpretation of these functions requires a mechanism fundamentally equivalent to multiprocessing. The EITHER construct is proposed as an extension to the lambda calculus, and several theories including this mechanism are presented and proved consistent (in the sense that they introduce no new equivalence into the lambda calculus).

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1974
Accession Number
AD0787796

Entities

People

  • Stephen A. Ward

Organizations

  • Massachusetts Institute of Technology

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Coding
  • Computations
  • Computer Languages
  • Computer Programming
  • Computer Science
  • Computers
  • Construction
  • Decoding
  • Language
  • Notation
  • Numbers
  • Programming Languages
  • Recursive Functions
  • Symbols
  • Theorems

Readers

  • Computational Linguistics
  • Theoretical Analysis.