Accession Number:

AD0787796

Title:

Functional Domains of Applicative Languages

Descriptive Note:

Scientific interim rept.

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE PROJECT MAC

Personal Author(s):

Report Date:

1974-09-01

Pagination or Media Count:

121.0

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.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE