Proofs as Programs
unofficial copies [PDF], [PS]

by Joseph L. Bates and Robert L. Constable

ACM Transactions on Programming Languages and Systems, vol. 7, no. 1, pp. 53-71, (also Cornell University Technical Report 82-530), 1985.


The significant intellectual cost of programming is for problem solving and explaining and not for coding. Yet, programming systems offer mechanical assistance exclusively with the coding process. Here we describe an implemented program development system, called PRL ("pearl"), that provides automated assistance with the hard part. The program and its explanation are seen as formal objects in a constructive logic of the data domains. These formal explanations can be executed at various stages of completion. The most incomplete explanations resemble applicative programs, the most complete are formal proofs.