可逆プログラミング言語ROOPL++のインタープリタの実装

• メンバー：青柳 祐樹, 新美 伊織, 竹市 翔哉，脇坂 怜輝
• 題目：可逆プログラミング言語 ROOPL++ のインタプリタの実装
• @overleaf, @github

配属時の希望

• 青柳 祐樹：可逆計算
• 新美 伊織：可逆計算
• 竹市 翔哉：プログラミング

報告書

• 2019年8月3日 字句解析器と構文解析器 p.150問11.7（新美）
• 2019年10月8日 字句解析器と構文解析器 亀山先生課題2-3, 2-4, 2-5 （青柳, 新美, 竹市）
• 2019年10月8日 卒業研究中間発表会の発表内容に関する参考文献調査（3年Q3において流れの研究の論文調査を行っていた．直接本プロジェクトに用いられない．）
  • 青柳：[KaNa19] 加藤舞，内藤綾香：多重連結領域上の安定非圧縮流の解析，南山大学2018年度卒業論文(2019).
  • 新美：[NKYY19] 内藤綾香，加藤舞，横山哲郎ほか：円板上の非圧縮流の反転の解析，情報処理学会第81回全国大会講演論文集，pp.319–320 (2019).
  • 竹市：[SaYS14] 坂上貴之，横山知郎，澤村陽一：二次元多重連結領域内における構造安定な非圧縮流れの文字列表現アルゴリズム，数理解析研究所講究録，Vol.1900, pp.11–25 (2014).
• 2019年10月29日 亀山先生課題 課題3-1, 3-2, 4-1 処理系の作成 （青柳, 新美 竹市）
• 2019年11月21日 ラムダ式の翻訳器（レポート（新美，野端，諏訪），実装，添削後の実装）
• 2020年1月15日 エンジニアリングデザインに関する課題．青柳，新美，竹市：SRLからRLへの翻訳機の実装，2019年度Q4期末レポート(2020)．ソースコード
• 2020年1月15日 卒業研究の題目と要旨
• 2020年5月6日 進捗報告（添削後）
• 2020年7月13日 研究ミーティングのメモ
• 2020年7月17日
  • 分担ができましたね
  • SRL2RLに関するレポートも含めては？
  • 細かくチェックしていませんが，READMEよくできています。
  • 参考文献のまとめは論文に書いてあることをフォローするのは良いことです。さらに自分の視点から自分のことばでまとめられるとよいでしょう。引き続き既存の論文に記載してある背景・目的・アプローチ・限界をまとめていってください。参考文献において他の参考文献がどのように引用されているかをお手本にするとよいでしょう。
  • 脇坂怜輝くんはテストケースを作成してコミットできていますね。今後しばらくはテストケースの作成を継続してください。コードカバー率を上げるようにテストケースを作って下さい。私もコミットしたコードを確認します。
• 2020年9月4日13:00-14:00 脇坂怜輝君 ミーティング

  以下をそれぞれ箇条書きで書いてください→10/7の発表スライドに入れる内容です。

  1. インタープリタの設計
  2. どこをテストするのか
  3. テストケース
• 2020年9月7日11:00- 脇坂怜輝君 ミーティング

  9/21(月)までに以下を行って発表スライド6枚を完成させる。

  1. インタープリタの設計: 「コンピュータサイエンス入門」のプログラミング言語Petitの解説を参考に，復習をする（特にまとめる必要は無い）
  2. 「単体テストとは」を調べてレポートに書く。「ソフトウェア工学基礎」でも学んだ内容を復習すると良い。使用しているunit test frameworkはOUnit
  3. どこをテストするのか：テストする場所を箇条書きで列挙する
  4. テストケースのソースコードを説明する。OUnitの書き方の解説から書くと良い。
• 2020年9月15日(火)12:30- ミーティング

計画

• SRL2RLについて文章でまとめる．
• 可逆プログラミング言語の調査をして文章にまとめる．
• 以下を調査し実行し文章でまとめる．
  ROOPL2PISA，PISAインタプリタ(MITの博士課程学生のpendvmとフロリダ大の学部学生Andrew DickinsonのPhPISA, コペンハーゲン大の学部学生のPendVM, FrankのR)
• ROOPLのサンプルプログラムの作成
• ROOPLの構文，表示的意味論の記述
• ROOPLの字句解析器，構文解析器を作る

参考文献

• 3年次Q1Q2の輪読で用いた入門書
  • [OhGN99] 大堀 淳，ジャック ガリグ，西村 進：コンピュータサイエンス入門〈アルゴリズムとプログラミング言語〉，岩波書店 (1999)．
  • [TaNH99] 田辺 誠，中島玲二，長谷川真人：コンピュータサイエンス入門〈論理とプログラム意味論〉，岩波書店 (1999)．
• SRLからRLへの翻訳器の制作([YoAG16]のFig.21)に関する参考文献
  • [YoAG16] Yokoyama, T., Axelsen, H.B., and Glück, R.: Fundamentals of reversible flowchart languages, Theoretical Computer Science, Vol.611, pp.87-115, (2016) PDF
    Fig.18-20 逆変換器, Fig.24 変換例; Fig.21 SRLからRLへの翻訳器; RLからSRLへの翻訳器; Fig.24-25 RLプログラムとSRLプログラムの例
  • [Mori09a] Moriyama, K.: Theoretical properties of reversible flowchart programming languages, コペンハーゲン大学コンピュータ科学科，2年次生期末レポート 29p. (2009)
  • [Mori09b] Moriyama, K.: An Introduction to Reversible Programming Using Simple Reversible Flowchart Languages, コペンハーゲン大学コンピュータ科学科，2年次生期末レポート，74p. (2009)
• 青柳裕樹，水野幹大，新美伊織，野橋祐人，竹市翔哉：SRL から RL への翻訳機の実装，2019年度Q3エンジニアリングデザイン期末レポート(2019).
• [AsYa19] 浅野早紀，山口春樹：可逆な深さ優先探索，南山大学2018年度卒業論文(2019).
  宮本君2019Q3の文献調査
• [IeMi18] 家崎雄太，水野竣太郎：可逆線形探索，南山大学2017年度卒業論文(2018).
  水野君2019Q3の文献調査
• 筑波大学 情報科学類 3年次実験（ソフトウェアサイエンス実験） ：インタープリタや簡単なコンパイラの作成の解説がある．
• 可逆オブジェクト指向言語
  • [Cser18] Cservenka, M.H.: Design and Implementation of Dynamic Memory Management in a Reversible Object-Oriented Programming Languaeg, Master's Thesis, Copenhagen University (2018). arXiv:1804.05097.
  • [Schu18] Schultz, U.P., Reversible Object-Oriented Programming with Region-Based Memory Management, Proc. Reversible Computation, Kari J., Ulidowski I. (Eds.), Lecture Notes in Computer Science, Vol.11106, Springer (2018), DOI: 10.1007/978-3-319-99498-7_22
  • [Haul17] Haulund, T.: Design and Implementation of a Reversible Object-Oriented Programming Language, Master's Thesis, Copenhagen University (2017). arXiv:1707.07845.
  • [HaMG17] Haulund, T., Mogensen, T.Æ., and Glück, R.: Implementing reversible object-oriented language features on reversible machines, Proc. Reversible Computation, Phillips, I., Rahaman, H. (Eds.), Lecture Notes in Computer Science, Vol.10301, pp.66–73, Springer (2017), DOI: 10.1007/978-3-319-59936-6_5.
  • [ScAx16] Schultz, U.P. and Axelsen, H.B.: Elements of a reversible object-oriented language, Proc. Reversible Computation, Devitt, S., Lanese, I. (Eds.), Lecture Notes in Computer Science, Vol.9720, pp.153–159. Springer (2016), DOI: 10.1007/978-3-319-40578-0_10.
• 可逆的な表示的意味論
  • [GlKY19] Glück, R., Kaarsgaard, R. and Yokoyama, T.: Reversible Programs Have Reversible Semantics, Reversibility in Programming, Languages, and Automata (RPLA 2019) (2019). 学外
    コペンハーゲン大学の学生のプロジェクトHermes2C @github
• 暗号化
• [Moge20] Mogensen, T.Æ.: Hermes: A Language for Light-Weight Encryption, Proc. Reversible Computation, Lanese, I. and Rawski, M., pp.93-110, Springer-Verlag (2020).
• 量子計算
• [Grus99] Gruska, J.: Quantum Computing, McGraw-Hill (1999).
• ソフトウェア
  • BNF Converter
  • ROOPL to PISA コペンハーゲン大3年生
  • Pendulum VM (PISAインタープリタ) コペンハーゲン大3年生
  • PISAオンラインインタプリタPHPISA フロリダ大学学部生
  • pendvm, phpisa, Rコンパイラのアーカイブ
  • ROOPL++のLanguage Architecture
• OCaml
  • OUnit @GitHub