広範囲なデータ型を対象とした機械的プログラム変換手法の確立

建立多种数据类型的机械程序转换方法

• 批准号: 16700029
• 负责人: 篠埜 功
• 金额: $ 1.47万
• 依托单位: Tohoku University (2005-2006)Japan Advanced Institute of Science and Technology (2004)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2004
• 资助国家: 日本
• 起止时间: 2004 至 2006
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16700029/
• 关键词: プログラム変換; 融合変換; プログラム導出; 線形時間アルゴリズム; 動的計画法; XML; 問い合わせ言語; 機械的導出; regularデータ型

一般にプログラム変換において、データ型毎に変換規則を用意する必要がある。プログラム変換の代表的な例として融合変換があるが、これまで融合変換の研究では、各データ型毎に規則を用意するか、または関手を用いてさまざまなデータ型規則を統一的に記述すると言うことが行われてきた。これに対し、融合変換に、プログラム変換において最も基本的な、関数定義の展開を用いる新たな関数融合方式を提案した(ACM POPL 2007)。この手法では、データ型にかかわらず適用可能な関数の展開を用いるため、データ型ごとに融合規則を用意する必要がなく、また、適用対象の関数定義に特定の形を要求しないため、ユーザー定義の関数が適用対象となる。新たな関数融合方式の核となる考え方は、融合対象の関数をf、gとすると、新しい関数hx=f(gx)を定義し、f、gの定義による展開、簡約など、意味を保つ変換を行い、f、gの連続適用が現れた部分をhで置き換えるというものである。この置き換えを行う規則をfixed point promotion規則として定義した。この変換を行う規則をapply distribution規則として定義した。これらの規則は、複数引数関数の場合にも自然に拡張され、カリー化されている場合にもされていない場合にも成り立つ。提案した新たな規則に基づいて、プログラム(関数定義が1etで入れ子になっている場合)を受け取り融合を行うアルゴリズムを設計し、SML#コンパイラの中間言語上に試験的に実装した。典型的な例で融合変換が成功し、メモリー使用料が半分程度、実行時間が6-8割程度にまで削減され、コード量が数パーセント程度増加する場合もあるという程度である。

通常，在程序转换中，需要为每种数据类型准备转换规则。程序转换的一个典型例子就是融合转换，但是到目前为止对于融合转换的研究要么是为每种数据类型准备了规则，要么是用函子来统一描述各种数据类型的规则。为此，我们提出了一种新的函数融合方法，该方法使用程序转换中最基本的函数定义扩展来进行融合变换（ACM POPL 2007）。该方法使用无论数据类型如何都可以应用的函数扩展，因此不需要为每种数据类型准备融合规则，并且由于它不需要应用函数定义的特定形式，因此用户定义以下函数适用。新函数融合方法的核心思想是，当要融合的函数为f和g时，定义一个新函数hx=f(gx)，并基于执行f和g的定义，并将f和g依次应用的部分替换为h。我们将这种替换的规则定义为定点提升规则。此转换的规则定义为应用分配规则。这些规则自然地扩展到多参数函数的情况，并且无论它们是否被柯里化，都适用。基于所提出的新规则，我们设计了一种接收和融合程序的算法（当函数定义嵌套在1et中时），并在SML#编译器的中间语言上进行实验实现。在典型情况下，融合转换是成功的，内存使用量减少了大约一半，执行时间减少了大约60-80%，在某些情况下还增加了几个百分点的代码量。