iwakih 昏論会読書ページ - 昏論会ウィキ

Abstraction and Perfomance from Explicit Monadic Reflection

概要

モナディックな構文解析なるものを実行するためにモナディックリフレクションというのが便利なのでその具体的方法をSchemeで説明するよ、という内容。

2.構文解析

• 機能的な（関数型な）構文解析の方法として木生成器（Tree producer）というものを考えて実際に行なっている。

Parsing Natural Numbersの冒頭が全然わからない。なぜdigitが出てくるのかずっとわからない。

• 木を生成するProducerという依存型を構成することで構文解析を行う。Producer型のモナド化を行う。

orelseマクロ

(define-syntax orelse 
 (syntax-rules orelse
  ((orelse ?producer1 ?producer2)
   (lambda (ts1)
    (sum-case (?producer1 ts1)
     ((ds ts2) (inl ds ts2))
     ((msg ts2) (?producer2 ts1)))))))

digitプロシージャ

(define digit
 (lambda ()
  (lambda (ts)
   (if (or (null? ts)
        (not (char-numeric? (car ts))))
    (inr "not a digit" ts)
    (inl (car ts) (cdr ts))))))

3.抽象データ型としてのモナド

• モナディックリフレクションはMoggiの"Notion of computation and monads"が初出（ただし、モナディックリフレクションという表現は取られていない。）
• クライスリトリプルはプログラミングをする分には便利な形式だけれど、メタレベルへの移行(level shifting)をすることを考えると、クライスリトリプルではなくモナドの形式の方が便利だ。言い換えると、モナドはリフレクションをする為に便利な形式。

この論文におけるモナドの表現

1. 型構築子Tは持ち上げを行うためのもので、型αを与えた場合、型αの値を生成（返すreturn）するコンピュテーション型に持ち上げる。類義語：αよりも一階層メタなレベルの型に持ち上げる。型をカインドに上げる。
2. mapは関手Tの射関数(arrow function)。map::(α -> β) -> (T α -> T β)
3. unit(return)は値を一階層メタなレベルに持ち上げる演算。unit(α) -> T α
4. multはモナドにおける掛け算で、二重に持ち上げられた型の値を一重の型の値にする。mult:: T(T(α)) -> T(α)

肝心の構文解析とリフレクションにリーチできない。

※モナディックリフレクションって長いから単にリフレクションと書く（一部除く）。リフレクションと書かれているところは全部モナディックリフレクションと読み替える。

付録の解説

• inl
• inr
• add1-or-zero
• sum-case

(define-syntax sum-case
  (syntax-rules ()
    ((sum-case ?exp
       ((?left-var ...) ?left-result)
       ((?right-var ...) ?right-result))
     (gen-var-list (?left-var ...)
       (sum-case-help () ?exp
         ((?left-var ...) ?left-result)
         ((?right-var ...) ?right-result))))))
(define-syntax sum-case-help
  (syntax-rules ()
    ((sum-case-help (?temp ...) ?exp
       ((?left-var ...) ?left-result)
       ((?right-var ...) ?right-result))
     (call-with-values (lambda () ?exp)
       (lambda (tag ?temp ...)
         (if tag
             (let ((?left-var ?temp) ...)
               ?left-result)
             (let ((?right-var ?temp) ...)
               ?right-result)))))))
(define-syntax gen-var-list
  (syntax-rules ()
    ((gen-var-list ()
       (?head (?y ...) ?tail ...))
     (?head (?y ...) ?tail ...))
    ((gen-var-list (?v0 ?v ...)
       (?head (?y ...) ?tail ...))
      (gen-var-list (?v ...)
        (?head (?y ... temp) ?tail ...)))))