Selectively Delayed Evaluation Through Program Transformation

概要

論文の詳細を見る
By selectively delaying evaluation of S-expressions in LISP, one can avoid overheads of conventional (indiscriminately) delayed evaluation schemes without losing their advantages. Selectively delayed evaluation is guided by the strategy "never delay the evaluation of the first argument (car part) of cons." This strategy restricts the possible forms for representing S-expressions to the following three: (1)explicit form not being delayed at all, (2)an intermediate form with only cdr part being delayed and (3)an implicit form being delayed on the whole. These forms are distinguished from one another by a translator, which generates object LISP programs which are executable in any conventional LISP system without run time checks on the forms, and whose execution corresponds, in effect, to delaying evaluation of selected S-expressions in source LISP programs. With this method, potentially infinite lists in cdr direction can be dealt with, and the heap storage space requirement was reduced from O(2^n) to O(n) with 28% loss of run time speed for a program which generated all the elements of the powerset of a set containing n elements.
一般社団法人情報処理学会の論文
1982-12-20