Lisp on Clojure

Clojureの特徴を簡単なLisp評価機を作る過程で紹介します。

作成する評価機は以下のようになります。

(def env (atom {'+ +}))

(eval env '(define double (lambda (x) (+ x x))))

(eval env '(define foo (double (double 3))))

(assert (= (eval env 'foo) 12))

最初に環境envの元でdoublefooを定義します。

doubleは引数xをとり、2つのx+を適用する関数です。

fooは3にdoubleを適用し、その結果にdoubleを適用します。

最後にassertで環境envの元でfooの値が12であることを確認しています。

Atom

Clojureはdefによりvarを作成し、現在のnamespaceに値を束縛します。

通常、varに対する再代入は出来ません。

ここでは可変参照としてatomを使用します。

(def foo (atom 1))
(assert (= @foo 1))

(reset! foo 2)
(assert (= @foo 2))

(swap! foo inc)
(assert (= @foo 3))

@はAtomの現在の値を返します。

reset!を使うことで再代入が可能です。

swap!はAtomの値に関数を適用し、その結果で値を置き換えます。

自己評価式

文字列や数値など、リテラルのみを評価できる単純な評価機から作成します。

評価機は環境と式を引数にとり、環境のもとで式を評価し値を返します。

(defn self-evaluating? [exp]
  (or (true? exp)
      (false? exp)
      (number? exp)
      (string? exp)))

(defn eval [env exp]
  (cond (self-evaluating? exp) exp))

(assert (= (eval (atom {}) 0) 0))
(assert (= (eval (atom {}) "foo") "foo"))

変数の探索

環境はhash-mapで表現します。

式がシンボルの場合はそれを変数として環境から値を参照します。

(defn eval [env exp]
  (cond (self-evaluating? exp) exp
        (symbol? exp) (get @env exp)))

(assert (= (eval (atom {'foo 0}) 'foo)) 0)

hash-mapから値を取り出すにはgetを使います。

Multimethod

Clojureで多相的な関数を定義する方法のひとつにMultimethodが存在します。

defmultiでディスパッチ関数を定義し、defmethodにより対応する値と手続きを記述します。

(defmulti foo (fn [x] x))
(defmethod foo 'foo [x] 0)
(defmethod foo 'bar [x] "bar")
(defmethod foo :default [x] x)

(assert (= (foo 'foo) 0))
(assert (= (foo 'bar) "bar"))
(assert (= (foo 'baz) 'baz))

fooのディスパッチ関数は(fn [x] x)で、単に引数の値でディスパッチします。

対応する値が存在しなかった場合、:defaultが呼ばれます。

特殊形式

特殊形式の判別はリストの先頭を比較する必要があります。

Multimethodを用いることでevalを変更することなく制御構造を追加することができます。

(defmulti eval-form (fn [env exp] (first exp)))

(defn eval [env exp]
  (cond (self-evaluating? exp) exp
        (symbol? exp) (get @env exp)
        (seq? exp) (eval-form env exp)))

分配束縛

letdefnなどの束縛形式では値を分解し、束縛することができます。

(assert (= (let [[fst _ _] '(1 2 3)] fst) 1))
(assert (= (let [[_ snd _] [2 4 6]] snd) 4))
(assert (= (let [[_ & rest] [1 3 5]] rest) [3 5]))

この例は次のように動作します。

  1. fstに一番目の要素を束縛し返す
  2. sndに二番目の要素を束縛し返す
  3. restに二番目から残りの要素全てを束縛し返す

quote

quoteは引数の式を評価せずそのまま返します。

式の分解には分配束縛を用います。

(defmethod eval-form 'quote [env [_ quotation]] quotation)

(assert (= (eval (atom {}) '(quote (foo bar))) '(foo bar)))

if

ifpredicateを評価し、真ならばconsequentを偽ならばalternativeを評価します。

(defmethod eval-form 'if [env [_ predicate consequent alternative]]
  (if (eval env predicate)
    (eval env consequent)
    (eval env alternative)))

(assert (= (eval (atom {}) '(if false "foo" 100)) 100))

define

defineは環境に変数を束縛します。

無名関数(fn [x] (f x))#(f %)のように記述できます。

(defmethod eval-form 'define [env [_ variable value]]
  (swap! env #(assoc % variable (eval env value))))

(let [env (atom {})]
  (eval env '(define foo 0))
  (assert (= (eval env 'foo) 0)))

Threading macro

Clojureでは->->>を使うことでデータの流れがわかりやすくなる、ネストが減るなどの利点があります。

次の例では->->>がどのように展開されるかを示します。

(assert (= (-> [] (conj "foo") (conj "bar") first)
           (first (conj (conj [] "foo") "bar"))))

(assert (= (->> (range 10) (filter odd?) reverse)
           (reverse (filter odd? (range 10)))))

begin

beginは引数の式を逐次評価します。

&で引数の式をシーケンスとして受け取ります。

(defmethod eval-form 'begin [env [_ & exps]]
  (->> exps (map #(eval env %)) last))

(assert (= (eval (atom {}) '(begin (define bar "bar") bar)) "bar"))

Protocol

ProtocolはClojureにおける抽象機構です。

TypeやRecordは定義時にProtocolを実装することができます。

(defprotocol Foo
  (foo []))

(deftype Bar []
  Foo
  (foo [] "bar"))

(defrecord Baz []
  Foo
  (foo [] "baz"))

(assert (= (foo (Bar.)) "bar"))
(assert (= (foo (Baz.)) "baz"))

適用

特殊形式以外のシンボルは関数適用として働きます。

この評価機では2種類の関数が存在します。

これらに対してProtocolを定義します。

(defprotocol Procedure
  (app [f args]))

(defmethod eval-form :default [env [operator & operands]]
  (app (eval env operator) (map #(eval env %) operands)))

lambda

lambdaは無名関数を生成します。

仮引数と実引数のペアで環境を拡張し、式を評価します。

(deftype Lambda [env parameters body]
  Procedure
  (app [lambda args]
    (eval (atom (merge @env (zipmap parameters args))) body)))

(defmethod eval-form 'lambda [env [_ parameters body]]
  (Lambda. env parameters body))

(assert (= (eval (atom {}) '((lambda (x y) y) "foo" "bar")) "bar"))

Primitive function

clojure.lang.IFnはClojureの関数を表すインターフェースです。

extend-protocolにより既存のデータ型に対してProtocolの実装が可能です。

(extend-protocol Procedure
  clojure.lang.IFn
  (app [f args] (apply f args)))

(assert (= (eval (atom {'+ +}) '(+ 2 3)) 5))

これで評価機は完成です。

ClojureScript

ClojureのコードはClojureScriptを使うことでJavaScriptにコンパイルが可能です。

JavaScriptで動作させるには次のように書き換える必要があります。

(extend-protocol Procedure
  function
  (app [f args] (apply f args)))

以下に今回実装した評価機を示します。