Mapping the Space of Programs, Searching the Space of Languages

Fritz Obermeyer

Carnegie Mellon University

Abstract

A program that is simple in one programming language might not be simple in another programming language. We consider a large space of possible languages and study the relative sizes of programs that compute the same functions in those different languages. Then, given a list of functions together with a measure of each function’s “usefulness,” we show how to find a language where the most useful functions in the list have the simplest programs.