WEKO3
アイテム
On the Average Size of Turner's Translation to Combinator Programs
https://ipsj.ixsq.nii.ac.jp/records/59891
https://ipsj.ixsq.nii.ac.jp/records/598913bb11d02-0112-489e-9e04-8ecee4d77f2b
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JIP0703004.pdf (656.9 kB)
|
Copyright (c) 1984 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | JInfP(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1984-11-10 | |||||||
| タイトル | ||||||||
| タイトル | On the Average Size of Turner's Translation to Combinator Programs | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | On the Average Size of Turner's Translation to Combinator Programs | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| Department of Mathematics Tokyo Metropolitan University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Mathematics, Tokyo Metropolitan University | ||||||||
| 著者名 |
Teruo, Hikita
× Teruo, Hikita
|
|||||||
| 著者名(英) |
Teruo, Hikita
× Teruo, Hikita
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 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. | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 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. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA00700121 | |||||||
| 書誌情報 |
Journal of Information Processing 巻 7, 号 3, p. 164-169, 発行日 1984-11-10 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-6652 | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
