Accession Number : ADA307740

Title :   Exceptions Are Strictly More Powerful Than Call/CC.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Lillibridge, Mark

PDF Url : ADA307740

Report Date : JUL 1995

Pagination or Media Count : 9

Abstract : We demonstrate that in the context of statically typed pure functional lambda calculi, exceptions are strictly more powerful than call/cc. More precisely, we prove that the simply typed lambda calculus extended with exceptions is strictly more powerful than Girard's F(w), (a superset of the simply typed lambda calculus) extended with call/cc and abort. This result is established by showing that the first language is Turing equivalent while the second language permits only a subset of the recursive functions to be written. We show that the simply typed lambda calculus extended with exceptions is Turing equivalent by reducing the untyped lambda calculus to it by means of a novel method for simulating recursive types using exception-returning functions. The result concerning F(w) extended with call/cc is from a previous paper of the author and Robert Harper's.

Descriptors :   *PROGRAMMING LANGUAGES, COMPUTER PROGRAM DOCUMENTATION, COMPUTER PROGRAMMING, SEMANTICS, RECURSIVE FUNCTIONS, CALCULUS, MAPPING(TRANSFORMATIONS).

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE