Compilation from Lambda Calculus with Algebraic Simplification to Record Calculus

• Akimasa, Morihata

抄録

Lambda-p (Morihata, PPL 2016) is an extension of simply-typed lambda calculus. Its characteristic feature is aggressive simplification based on algebraic properties, which is useful to express parallel algorithms. In the previous presentation, the calculus is developed from scratch. This is not satisfactory. Theoretically, relationships with other calculi were unclear; in fact, because of this issue, it was difficult to develop a type system that guarantees efficiency of simplifications. From a practical point of view, it was unclear whether it could be implemented on existing systems. To resolve this problem, in this presentation, a compilation from lambda-p to a record calculus is shown. The compilation consists of two phases. First, lambda-p is translated into a polymorphic-typed record calculus to eliminate the parallel primitive. Then, the polymorphic-typed record calculus is further translated into typeless record calculus to address simplification. The compilation is fairly intuitive, and these two phases provide appropriate operational semantics and type system to lambda-p.

Lambda-p (Morihata, PPL 2016) is an extension of simply-typed lambda calculus. Its characteristic feature is aggressive simplification based on algebraic properties, which is useful to express parallel algorithms. In the previous presentation, the calculus is developed from scratch. This is not satisfactory. Theoretically, relationships with other calculi were unclear; in fact, because of this issue, it was difficult to develop a type system that guarantees efficiency of simplifications. From a practical point of view, it was unclear whether it could be implemented on existing systems. To resolve this problem, in this presentation, a compilation from lambda-p to a record calculus is shown. The compilation consists of two phases. First, lambda-p is translated into a polymorphic-typed record calculus to eliminate the parallel primitive. Then, the polymorphic-typed record calculus is further translated into typeless record calculus to address simplification. The compilation is fairly intuitive, and these two phases provide appropriate operational semantics and type system to lambda-p.

収録刊行物

• 情報処理学会論文誌プログラミング（PRO）

  情報処理学会論文誌プログラミング（PRO） 10 (3), 21-21, 2017-06-16

キーワード

• [発表概要]

詳細情報

• CRID: 1050564287861814784
• NII論文ID: 170000148649
• NII書誌ID: AA11464814
• ISSN: 18827802
• Web Site: http://id.nii.ac.jp/1001/00182204/
• 本文言語コード: ja
• 資料種別: article
• データソース種別:
  • IRDB
  • CiNii Articles