Skip to content

脱関数化を実用する

Jump to bottom Edit New page
Yusuke Matsushita edited this page Mar 5, 2015 · 2 revisions

このページは、Oliver Danvy and Lasse R. Nielsen. Defunctionalization at work. BRICS RS-01-23, Department of Computer Science, University of Aarhus, Denmark, June 2001. (Extended version : Oliver Danvy and Lasse R. Nielsen. Defunctionalization at work. In Proceedings of the 3rd ACM SIGPLAN international conference on Principles and practice of declarative programming (PPDP '01). ACM, New York, NY, USA, 162-174.) の日本語訳です。

脱関数化を実用する

オリバー＝ダンヴィー・ラッセ＝R＝ニールセン

BRICS (Basic Research in Computer Science (http://www.brics.dk/), funded by the Danish National Research Foundation)
計算機科学科 オーフス大学
Ny Munkedage, Building 540, DK-8000 Aarhus C, Denmark
Email: danvy@brics.dk, lrn@brics.dk

概要

レナルズの脱関数化 (defunctionalization) テクニックは、高階の (higher-order) 関数型プログラム全体を一階の (first-order) プログラムに変換する。私たちはこの変換の実用的な応用を研究し、高階の記述と一階の記述という一見関係ない両者の間にある新しい関係性を明らかにする。結果として、脱関数化が新しい関係性を明らかにする糸口であり、かつ一階の世界と高階の世界の間で既存の結果を受け渡しするための懸け橋であるように見えてくるだろう。

目次

  • [1 背景と導入](脱関数化を実用する 1#section1)

    • [1.1 静的な個数のクロージャのある高階のプログラムのサンプル](脱関数化を実用する 1#section1-1)

    • [1.2 動的な個数のクロージャのある高階のプログラムのサンプル](脱関数化を実用する 1#section1-2)

    • [1.3 脱関数化とはつまり](脱関数化を実用する 1#section1-3)

    • [1.4 関連研究](脱関数化を実用する 1#section1-4)

    • [1.5 この研究](脱関数化を実用する 1#section1-5)

  • [2 リストと木を処理するプログラムの脱関数化](脱関数化を実用する 2#section2)

    • [2.1 二分木をリストへと平坦化する](脱関数化を実用する 2#section2-1)

    • [2.2 リストの高階な表現](脱関数化を実用する 2#section2-2)

    • [2.3 チャーチ符号化された非再帰的データ構造の脱関数化](脱関数化を実用する 2#section2-3)

    • [2.4 チャーチ符号化された再帰的データ構造の脱関数化](脱関数化を実用する 2#section2-4)

    • [2.5 脱関数化の結果のチャーチ符号化](脱関数化を実用する 2#section2-5)

    • [2.6 要約と結論](脱関数化を実用する 2#section2-6)

  • [3 CPS変換された一階のプログラムを脱関数化する](脱関数化を実用する 3#section3)

    • [3.1 文字列のパース](脱関数化を実用する 3#section3-1)

    • [3.2 継続ベースのプログラムの変換](脱関数化を実用する 3#section3-2)

    • [3.3 要約と結論](脱関数化を実用する 3#section3-3)

  • [4 脱関数化を踏まえた二つの構文論](脱関数化を実用する 4#section4)

    • [4.1 算術式](脱関数化を実用する 4#section4-1)

      • [4.1.1 算術式の構文論](脱関数化を実用する 4#section4-1-1)

      • [4.1.2 実装](脱関数化を実用する 4#section4-1-2)

      • [4.1.3 再関数化](脱関数化を実用する 4#section4-1-3)

      • [4.1.4 直接的スタイルに戻る](脱関数化を実用する 4#section4-1-4)

    • [4.2 値渡しラムダ計算](脱関数化を実用する 4#section4-2)

      • [4.2.1 値渡しラムダ計算の構文論](脱関数化を実用する 4#section4-2-1)

      • [4.2.2 実装](脱関数化を実用する 4#section4-2-2)

      • [4.2.3 再関数化](脱関数化を実用する 4#section4-2-3)

      • [4.2.4 直接的スタイルに戻る](脱関数化を実用する 4#section4-2-4)

    • [4.3 要約と結論](脱関数化を実用する 4#section4-3)

  • [5 脱関数化の前後で正当性証明を比較する：正規表現のマッチ](脱関数化を実用する 5#section5)

    • [5.1 正規表現](脱関数化を実用する 5#section5-1)

    • [5.2 二つのマッチャー](脱関数化を実用する 5#section5-2)

      • [5.2.1 高階のマッチャー](脱関数化を実用する 5#section5-2-1)

      • [5.2.2 一階のマッチャー](脱関数化を実用する 5#section5-2-2)

    • [5.3 二つの正当性証明](脱関数化を実用する 5#section5-3)

      • [5.3.1 高階のマッチャーの正当性証明](脱関数化を実用する 5#section5-3-1)

      • [5.3.2 一階のマッチャーの正当性証明](脱関数化を実用する 5#section5-3-2)

    • [5.4 二つの正当性証明の比較](脱関数化を実用する 5#section5-4)

    • [5.5 要約と結論](脱関数化を実用する 5#section5-5)

  • [6 結論と論点](脱関数化を実用する 6#section6)

  • [謝辞](脱関数化を実用する 7#section7)

  • [A 高階のマッチャーの正当性証明](脱関数化を実用する A#sectionA)

  • [B 一階のマッチャーの正当性証明](脱関数化を実用する B#sectionB)

  • [参照](脱関数化を実用する 8#section8)

  • [図1 正規表現の高階な継続ベースのマッチャー](脱関数化を実用する 5#fig1)

  • [図2 正規表現の一階のスタックベースのマッチャー](脱関数化を実用する 5#fig2)

Add a custom footer

  • Home

  • [拡張可能作用 ― モナド変換子に取って代わるもの](拡張可能作用 ― モナド変換子に取って代わるもの)

    [1](拡張可能作用 ― モナド変換子に取って代わるもの 1#section1) / [2](拡張可能作用 ― モナド変換子に取って代わるもの 2#section2) / [3](拡張可能作用 ― モナド変換子に取って代わるもの 3#section3) / [4](拡張可能作用 ― モナド変換子に取って代わるもの 4#section4) / [5](拡張可能作用 ― モナド変換子に取って代わるもの 5#section5) / [6](拡張可能作用 ― モナド変換子に取って代わるもの 6#section6) / [7](拡張可能作用 ― モナド変換子に取って代わるもの 7#section7) / [謝辞](拡張可能作用 ― モナド変換子に取って代わるもの 8#section8) / [参照](拡張可能作用 ― モナド変換子に取って代わるもの 9#section9) / [図1](拡張可能作用 ― モナド変換子に取って代わるもの 2#fig1) / [図2](拡張可能作用 ― モナド変換子に取って代わるもの 3#fig2) / [付録](拡張可能作用 ― モナド変換子に取って代わるもの 付録)

  • 脱関数化を実用する

    [1](脱関数化を実用する 1#section1) / [2](脱関数化を実用する 2#section2) / [3](脱関数化を実用する 3#section3) / [4](脱関数化を実用する 4#section4) / [5](脱関数化を実用する 5#section5) / [6](脱関数化を実用する 6#section6) / [謝辞](脱関数化を実用する 7#section7) / [A](脱関数化を実用する A#sectionA) / [B](脱関数化を実用する B#sectionB) / [参照](脱関数化を実用する 8#section8) / [図1](脱関数化を実用する 5#fig1) / [図2](脱関数化を実用する 5#fig2)

Clone this wiki locally