Multi-Stage Programming with Dependent Types: Theory and Implementation

具有依赖类型的多阶段编程：理论与实现

• 批准号: 22H03563
• 负责人: 亀山 幸義
• 金额: $ 11.07万
• 依托单位: University of Tsukuba
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-04-01 至 2026-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-22H03563/
• 关键词: プログラム生成; プログラム特化; 型システム; 依存型; 仕様記述; 段階的計算; プログラム解析・検証; 計算エフェクト; オフショアリング

研究初年度となる２０２２年度は、本研究の基盤となる段階的計算体系において、計算リソース（メモリ量など）や生成されたコードのサイズ・性能などの量を扱うプログラム生成技法とその実例について調査を行った。特に、依存型を用いない従来型の型システムにおいてこれらの量的な情報をもとに質の高いプログラムを生成したりプログラム解析・検証を行った成功例について詳細に検討を行った。そのような研究の１つとして、亀山らが開発してきたプログラム生成・解析・検証を統一して行うフレームワークについて、暗号分野の適用事例をさらに洗練させて性能向上を果たした。特に、従来は、数論的変換関数だけの実装にとどまっていたのに対し、本研究では、多項式乗算など、より大きな関数を適用対象として、高性能コードの生成とその正しさの検証を同時に達成することに成功した。上記と並行して、コード重複を回避する段階的計算において重要となる計算エフェクトについて理論・実装の両面からの研究を行い、代数的エフェクトと限定継続コントロールオペレータの関係を解明したり、限定継続コントロールオペレータに関する統一的型システムを与えることに成功した。さらに、高性能コード生成において鍵となる技術の１つである「オフショアリング」の実装および応用例の作成を進めた。オフショアリングは、コード生成器を記述する高レベル言語と、生成されるコードを記述する低レベル言語の橋渡しをする技術であり、現代的な高性能コードの生成においては必須とされる技術である。段階的計算を実現するプログラミング言語MetaOCamlにオフショアリング機能を標準装備することに生成するとともに、C言語へのオフショアリングに関する従来手法において変数の取り扱いに問題がある事を発見して、改善手法を提案した。

在2022财年，研究的第一年，在渐进的计算系统中，这是本研究的基础，程序生成技术和计算资源的实际示例（例如内存量），生成的生成的规模和性能代码已完成。特别是，我们研究了基于这些不使用依赖类型的常规类型系统中的这些定量信息，研究了生成高质量程序，程序分析和验证的成功示例。作为其中一项研究，通过进一步完善密码领域的应用，可以进一步改善了由Kameyama和其他人开发的计划生成，分析和验证的框架。过去，仅实现了数值转换函数的实现，但是在这项研究中，高性能代码的产生及其正确性，例如多边乘法乘法乘法乘法乘以乘法实现。与上述同时，从理论和实施计算效应中进行研究，这些效应在基于步骤的计算中很重要，以避免代码重复，阐明代数效应与有限的连续控制操作员之间的关系，以及有限的连续控制。运营商的统一系统。此外，实施“ Off -Shoring”，这是高性能代码生成中的关键技术之一，以及创建应用程序示例。 Offshoring是一项新娘，该技术描述了代码生成器的低级语言和描述生成代码的低级别语言。实现逐步计算的编程语言是作为标准设备生成的，并通过发现在传统的C语言中处理变量存在问题，提出了改进方法。

项目成果

Unified Program Generation and Verification: A Case Study on Number-Theoretic Transform

统一程序生成与验证：数论变换案例研究

• DOI: 10.1007/978-3-030-99461-7_8
• 发表时间: 2022
• 期刊: Lecture Notes in Computer Science
• 作者: S. Nakano;S. Fujita;A. Kadokura;Y. Tanaka;R. Kataoka;A. Nakamizo;K. Hosokawa;S. Saita;Masahiro Masuda and Yukiyoshi Kameyama
• 通讯作者: Masahiro Masuda and Yukiyoshi Kameyama

A Functional Abstraction of Typed Invocation Contexts

类型化调用上下文的功能抽象

• DOI: 10.46298/lmcs-18
• 发表时间: 2022
• 期刊: Logical Methods in Computer Science
• 影响因子: 0.6
• 作者: Cong Youyou;Ishio Chiaki;Honda Kaho;Asai Kenichi
• 通讯作者: Asai Kenichi

Generating Programs for Polynomial Multiplication with Correctness Assurance

• DOI: 10.1145/3571786.3573017
• 发表时间: 2023-01
• 期刊: Proceedings of the 2023 ACM SIGPLAN International Workshop on Partial Evaluation and Program Manipulation
• 作者: Ryohei Tokuda;Yukiyoshi Kameyama

shift/reset を含む型付き言語における Reflection 証明

类型化语言的反射证明，包括移位/重置

• 发表时间: 2023
• 作者: 本田 華歩;山本 充子;浅井 健一
• 通讯作者: 浅井 健一

Understanding Algebraic Effect Handlers via Delimited Control Operators

通过定界控制运算符了解代数效应处理程序

• 发表时间: 2022
• 作者: 木伏紅緒;新澤庸介;神崎素樹;Youyou Cong
• 通讯作者: Youyou Cong