On the Power of Applicative Languages.

摘要

The expressive power of applicative structures is investigated (particularly APL one-liners) with the result that all practically computable functions are one-liner expressible. In particular, the class of functions computable by one-liners contains the elementary functions. The problem of reducing the intermediate storage requirements for evaluating applicative structures is shown to be solvable with only modest execution time degradation. The prospect of improving these results is discussed in connection with an outstanding conjecture concerning a time-space relationship. (Author)