[Clojure]trampolineを理解する

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は

1. (trampoline f & args)でfをargsとともに呼ぶ。

2. fが関数fnを返す場合は、その関数を引数なしで呼ぶ。

3. fnが関数でない値を返すときは、その値を返す。fnが関数を返す場合は、このプロセスを繰り返す。

という動作をする関数ということです。

## trampolineの使用例

例として、trampolineを使って、「ｘの値が10になるまで一つずつ増やしながプリントする」関数を作ってみます。

```Clojure
(defn print-until-ten [x]
  (if (< x 10)
    (do (println x) (print-until-ten (inc x))
        x)))
```
上の関数では、xの値が10より小さい場合は、xの値をプリントしたあと、自分自身を再帰呼出ししています。そして、xの値が10以上のときはxを返します。

この関数を初期値とともにtrampolineに渡してみます。

```Clojure
(trampoline print-until-ten 0)
```

上の式を評価すると、以下の結果を得ました。

```
0
1
2
3
4
5
6
7
8
9
```

ただ、このような関数を書くのであれば、loopを使って書くのが一般的ではないでしょうか。

```Clojure
  (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)](https://ja.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3)を作る事ができます。

FSMとは、有限な「状態」と他の状態へ移行する条件が定義されているモデルのこと。身近な例を挙げると、エレベーターはFSMになっているといえます。

というのも、エレベーターでは

「ドアが閉まった状態」

「ドアが開いた状態」

という２つの「状態」を定義できます。そして

「他の階に移動する」

というアクションは、「ドアが閉まった状態」でしか実行できません。

このように、FSMでは有限個の状態に対して、それぞれの状態で可能なアクションがあり、そのアクションによって次の状態への移行していきます。

### trampolieを使ったエレベーターFSM

```Clojure
(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を返します。

```Clojure
  (elevator-fsm [:close :up :down :up :open :exit]) ;; => true

  (elevator-fsm [:open :up]) ;; => false 
```
このようにtrampolieを使うとFSMが実装できます。

## FSMのライブラリー紹介

上のコードは4つの状態だけを扱うFSMですが、それでもかなり長い関数になってしまいました。もっと状態や移行の条件が増えれば、FSMを上のようにletfnを用いて作成するのは辛くなるでしょう。

そんな時は

[reduce-fsm](https://github.com/cdorrat/reduce-fsm)

というライブラリーが利用可能です。reduce-fsmを使うと、FSMが楽に実装できます。

## 参考サイト

[Clojure docs:trampoline](https://clojuredocs.org/clojure.core/trampoline)