構造化可逆言語から非構造化可逆言語への翻訳系の試作

• メンバー：宮本昌武，水野幹大，野端祐人
• 題目：構造化可逆言語から非構造化可逆言語への翻訳系の試作

配属時の希望

• 宮本昌武：プログラミング
• 水野幹大：プログラミング言語理論（大学院では，λ計算・型理論・OCamlの研究室を志望）
• 野端祐人：プログラミング言語理論

報告書

• 2019年8月3日 字句解析器と構文解析器 p.150問11.7（水野）
• 2019年11月15日 文献調査（宮本[AsYa19]， 水野[IeMi18]）
  • （野端君の3年Q3において行っていた論文調査は，直接本プロジェクトに用いられない．）
    野端：[YoYo18b] 横山哲郎，横山知郎：ハミルトン曲面流に対応する流れの向きを考慮した極大語の列挙アルゴリズム，電子情報通信学会和文論文誌D, Vol.J101-D, No.8, pp.1220–1222 (2017).
• 2019年11月21日 ラムダ式の翻訳器（レポート（新美，野端，諏訪），実装，添削後の実装, GitHub上のプライベートリポジトリ）
• 2020年1月15日 卒業研究の題目と要旨
• 2020年5月5日 卒業研究進捗状況
• 2020年6月19日 進捗状況報告 資料
• 2020年6月25日 進捗状況報告 資料

計画

• 基礎の学習，関連研究調査
  • 入門書を復習して自分の言葉でレポートをまとめる
    • [TaNH99]1章序論を読んでプログラム意味論の初歩についてまとめる
    • [OhGN99]14章プログラム実行のモデルを読んでコンパイラの初歩についてまとめる．水野君と宮本君Q3のレポートとプログラムの内容も加筆して用いること
      第II部を読み直してプログラミング言語についての基礎を復習する
  • 文献調査結果をまとめる．[AsYa19]2019Q3宮本君担当，[IeMi18]2019Q3水野君担当， [WiOD12] [WSSD16]宮本君担当，[ThAG12]野端君担当，[Fran99]水野君担当
  • 参考文献を読んで内容を自分の文章でまとめる
• 実装の方針の決定：以下の選択肢がある
  1. 新美君や竹市君の実装を使わず別言語（OCamlでなくHaskell）で実装する．
  2. 新美君や竹市君の実装を使う．OCamlで実装する。拡張部分に自分たちの貢献をする。
• SRL2RLの設計・実装
  • SRLとRLの構文をBNFで書く → 字句解析器・構文解析器・プリティプリンタを書く
  • SRLとRLの表示的意味論/操作的意味論を書く
  • SRLからRLへの翻訳規則を書く
  • SRLからRLへの翻訳器をOCamlで実装する
  • SRL/RLの評価規則を書く → SRL/RLのインタプリタをOCamlで実装する
  • SRL/RLの逆変換規則を書く → SRL/RLの逆変換規則をOCamlで実装する
• SRL/RLの拡張
  • [Mori09a][Mori09b]で行われた拡張
  • 自分たちで考えた拡張

研究ミーティング

• 2020/6/12 15:15-16:40 資料
• 2020/7/20 16:00-17:00
• 2020/08/27 16:00-17:10 水野君

参考文献

• 3年次Q1Q2の輪読で用いた入門書
  • [OhGN99] 大堀 淳，ジャック ガリグ，西村 進：コンピュータサイエンス入門〈アルゴリズムとプログラミング言語〉，岩波書店 (1999)．
    ガリグ先生の1年生用の教科書の内容も卒論で直接的に用いられることと思います。
  • [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年次実験（ソフトウェアサイエンス実験）：インタープリタや簡単なコンパイラの作成の解説がある．
• BNF Converter
• [IeMi18] 家崎雄太，水野竣太郎：可逆線形探索，南山大学2017年度卒業論文(2018).
• Jacques Garrigue の講義情報
  水野君はガリグ先生の研究に興味があるとのことでしたが、このセミナーのところの少人数クラスや卒業研究は関係が深いものです。While言語のインタプリタをOCamlで実装したりCoqを用いたりしているようです。（2020/3/17）
• 2019 年度 Q2 情報科学概論 演習 処理系の実装 PDF
• [WSSD16] Wille, R., Schönborn, E., Soeken, M., Drechsler, R.: SyReC: A hardware description language for the specification and synthesis of reversible circuits, Integration, Vol.53, pp.39-53 (2016). https://doi.org/10.1016/j.vlsi.2015.10.001
  • [WiOD12] Wille, R., Offermann, S., Drechsler, R.: System Specification and Design Languages, Chapter 13 SyReC: A Programming Language for Synthesis of Reversible Circuits, Kaźmierski, T. J. and Morawiec, A., (Eds.), Vol.106, pp.207-222, Springer-Verlag (2012). http://dx.doi.org/10.1007/978-1-4614-1427-8_13 (2021-01-25現在電子図書館よりアクセス不可，local copy)
    可逆ハードウェア記述言語SyReCとその翻訳器【宮本君担当】
• [ThAG12] Thomsen, M. K., Axelsen, H.B., and Glück, R.: A Reversible Processor Architecture and Its Reversible Logic Design, Reversible Computation, A. Vos and R. Wille (Eds.), Springer-Verlag, LNCS 7165, pp.30-42 (2012). 南山大学図書館電子ジャーナル
  可逆機械語【野端君担当】
• [Fran99] Frank, M. P.: Reversibility for Efficient Computing, PhD Thesis, MIT (1999) http://dx.doi.org/1721.1/9464 著者のバージョン
  翻訳器R2PISA【水野君担当】
• GitHub上のリポジトリ：SRL2RL，BNFCとHaskell/Javaを用いたPetitのインタープリタ，Haskell(構文解析器はParsec)を用いたPetitのインタープリタ
• 計算能力
• [AoYo18] 青木 崚, 横山 哲郎: 可逆プログラミング言語R-WHILEの可逆チューリング完全性, 電子情報通信学会論文誌D, Vol.J101-D, No.9, pp.1372--1375(2018).