On the Average Size of Turner's Translation to Combinator Programs

スポンサーリンク

概要

• 論文の詳細を見る

• Turner proposed in 1979 an interesting method of implementation for functional programs by first translating them to combinator expressions without variables, and then reducing the graphs they represent. One of the points of concern for this method was the expansion of the sizes of expressions resulting from the translation. Kennaway has recently shown that the worst case of the size of this translation is of order n^2 where n is the size of an original program. In this paper we choose a theoretical definition of an average size of the translation, and show that the order of the average is at most n^<3/2>. Partial results on lower bounds of the average are also shown in the case of programs with one distinct variable. Finally, numerical results for the average size are exhibited.

• 一般社団法人情報処理学会の論文
• 1984-11-10

著者

• Hikita Teruo

  Department Of Computer Science School Of Science And Technology Meiji University

• Hikita Teruo

  Department Of Mathematics Tokyo Metropolitan University

関連論文

• Pipeline patterns generated in process algebra
• Process Composition and Interleave Reduction in Parallel Process Specification
• On the Average Size of Turner's Translation to Combinator Programs

スポンサーリンク