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