渋谷.cljの資料です。

dcg.md

!SLIDE

clojure.core.logic.dcgの紹介

@halcat0x15a

!SLIDE

これはなに？

core.logicというClojureで論理プログラミングするためのライブラリを使って、Prologの限定節文法(DCG)を実装したもの。

core.logicに含まれている。

!SLIDE

DCGって？

構文解析を行なうための特別な記法。

数式を解析、計算を行う例を用いて使い方を紹介します。

!SLIDE

字句解析

数字の変換

(defne number [m n]
  ([\1 1]) ([\2 2]) ([\3 3])
  ([\4 4]) ([\5 5]) ([\6 6])
  ([\7 7]) ([\8 8]) ([\9 9])
  ([\0 0]))

(assert (= (run 1 [q] (number \0 q))
           [0]))

!SLIDE

数列の変換

(def-->e numbers [s]
  ([[x]] (fresh [n]
           [n]
           (!dcg (number' n x))))
  ([[x . y]] (fresh [n]
               [n] (numbers y)
               (!dcg (number' n x)))))

(assert (= (run* [q] (numbers q (vec "123") []))
           [[1 2 3]]))

!SLIDE

式の変換

(def-->e parse [s]
  ([[x '+ . y]] (numbers x) [\space] [\+] [\space] (parse y))
  ([[x '- . y]] (numbers x) [\space] [\-] [\space] (parse y))
  ([[x '* . y]] (numbers x) [\space] [\*] [\space] (parse y))
  ([[x '/ . y]] (numbers x) [\space] [\/] [\space] (parse y))
  ([[x]] (numbers x)))

(assert (= (run* [q] (parse q (vec "2 - 4 + 8 * 16 / 32") []))
           ['[[2] - [4] + [8] * [1 6] / [3 2]]]))

!SLIDE

DCGはBNFを意識して読むと理解し易いかもしれない。

<foo> ::= <bar> | <baz>

(def-->e foo [f]
  ([_] ['bar])
  ([_] ['baz]))

!SLIDE

構文解析

この形が簡単だが、演算の優先順序が右からになってしまう。

<expression> ::= <term> "+" <expression> | <term> "-" <expression> | <term>
<term> ::= <number> "*" <term> | <number> "/" <term> | <number>
<number> ::= 数字

なので、式を反転し、オペランドも反転する。

!SLIDE

数値

(def-->e number [n]
  ([_] [n]
       (!dcg (project [n] (== (number? n) true)))))

!SLIDE

項

(def-->e term [t]
  ([_] (fresh [x y]
         (number x) '[*] (term y)
         (!dcg (project [x y] (== t (* y x))))))
  ([_] (fresh [x y]
         (number x) '[/] (term y)
         (!dcg (project [x y] (== t (/ y x))))))
  ([_] (number t)))

!SLIDE

式

(def-->e expression [e]
  ([_] (fresh [x y]
         (term x) '[+] (expression y)
         (!dcg (project [x y] (== e (+ y x))))))
  ([_] (fresh [x y]
         (term x) '[-] (expression y)
         (!dcg (project [x y] (== e (- y x))))))
  ([_] (term e)))

!SLIDE

数列を数に変換

(defn numbers->number [n]
  (cond (coll? n) (reduce (fn [a [i n]]
                            (+ a (* n (long (Math/pow 10 i)))))
                          0
                          (map-indexed list (reverse n)))
        :else n))

(assert (= (map numbers->number (run* [q] (numbers q (vec "123") [])))
           [123]))

!SLIDE

計算

(defn eval' [s]
  (run* [q]
    (fresh [x]
      (parse x (vec s) [])
      (project [x] (expression q (reverse (map numbers->number x)) [])))))

(assert (= (eval'' "2 + 2 * 2 - 2 / 2")
           [5]))
(assert (= (eval'' "2 - 4 + 8 * 16 / 32")
           [2]))

!SLIDE

おわりに

COMFRK vol.04 に寄稿しました。

core.logicについてです。

ぜひ買ってね。