Clojureにはtramplineという面白い関数があります。
trampolineのドキュメントを見てみると、
clojure.core/trampoline
[f]
[f & args]
Added in 1.0
trampoline can be used to convert algorithms requiring mutual
recursion without stack consumption. Calls f with supplied args, if
any. If f returns a fn, calls that fn with no arguments, and
continues to repeat, until the return value is not a fn, then
returns that non-fn value. Note that if you want to return a fn as a
final value, you must wrap it in some data structure and unpack it
after trampoline returns.
と書いてあります。ポイントをまとめると、trampolineは
(trampoline f & args)でfをargsとともに呼ぶ。
fが関数fnを返す場合は、その関数を引数なしで呼ぶ。
fnが関数でない値を返すときは、その値を返す。fnが関数を返す場合は、このプロセスを繰り返す。
という動作をする関数ということです。
trampolineの使用例
例として、trampolineを使って、「ｘの値が10になるまで一つずつ増やしながプリントする」関数を作ってみます。
(defn print-until-ten [x]
(if (< x 10)
(do (println x) (print-until-ten (inc x))
x)))
上の関数では、xの値が10より小さい場合は、xの値をプリントしたあと、自分自身を再帰呼出ししています。そして、xの値が10以上のときはxを返します。
この関数を初期値とともにtrampolineに渡してみます。
(trampoline print-until-ten 0)
上の式を評価すると、以下の結果を得ました。
0
1
2
3
4
5
6
7
8
9
ただ、このような関数を書くのであれば、loopを使って書くのが一般的ではないでしょうか。
(defn print-until-ten-loop [x]
(loop [cur x]
(when (< cur 10) (println cur)(recur (inc cur)))))
それでは、どのような場合にtrampolineを使いたくなるのでしょう？
trampolieを使ってFSM（Finite State Mashine)を作る
FSMとは？
trampolineとletfnを組み合わせると、簡単な
FSM(Finite State Mashine)を作る事ができます。
FSMとは、有限な「状態」と他の状態へ移行する条件が定義されているモデルのこと。身近な例を挙げると、エレベーターはFSMになっているといえます。
というのも、エレベーターでは
「ドアが閉まった状態」
「ドアが開いた状態」
という２つの「状態」を定義できます。そして
「他の階に移動する」
というアクションは、「ドアが閉まった状態」でしか実行できません。
このように、FSMでは有限個の状態に対して、それぞれの状態で可能なアクションがあり、そのアクションによって次の状態への移行していきます。
trampolieを使ったエレベーターFSM
(defn elevator-fsm [cmds]
(letfn [
;; 一階でドアが開いた状態
(ffopen [[action & r]]
(case action
:open (ffopen r)
:close (ffopen r)
false))
;;一階でドアが閉まった状態
(ffclose [[action & r]]
(case action
:open (ffopen r)
:close (ffclose r)
:up (sfclose r)
false))
;;二階でドアが閉まった状態
(sfclose [[action & r]]
(case action
:open (sfopen r)
:close (sfclose r)
:down (ffclose r)
false))
;;二階でドアが開いた状態
(sfopen [[action & r]]
(case action
:exit true
:open (sfopen r)
:close (sfclose r)
false
))]
(trampoline ffclose cmds)))
上の関数は
ffcloe, ffopen, sfclose, sfopen
という4つの状態と、
:open, :close, :up, :down, :exit
という4つのアクションからなるFSMを実装しています。モデルとしては、一階と二階を移動するエレベーターを考えています。
この関数は通常のエレベーターのように、「一階から出発し、ドアを閉め、二階にあがり、ドアを開け、外に出る」という動作を想定し、それに対応するコマンドを受け取るとtrueを返します。また、二階から一階へ戻ることもできるとします。しかし、例えばドアを開けた状態で上に行こうとするなど、不正なコマンドを受け取るとfalseを返します。
(elevator-fsm [:close :up :down :up :open :exit]) ;; => true
(elevator-fsm [:open :up]) ;; => false
このようにtrampolieを使うとFSMが実装できます。
FSMのライブラリー紹介
上のコードは4つの状態だけを扱うFSMですが、それでもかなり長い関数になってしまいました。もっと状態や移行の条件が増えれば、FSMを上のようにletfnを用いて作成するのは辛くなるでしょう。
そんな時は
というライブラリーが利用可能です。reduce-fsmを使うと、FSMが楽に実装できます。