無駄と文化

実用的ブログ

不動点コンビネータで無名再帰を作る流れをおさらい

f:id:todays_mitsui:20190704021651p:plain


どうも、趣味で関数型言語を書いている者です。
長らく関数型言語やってなかったら無名再帰を忘れかけていたので、おさらいがてら不動点コンビネータで無名再帰を作る流れを書き下します。

以下、Haskell の文法で書かれたコードをもとに説明していきます。


無名再帰とは?

まずはモチベーションの確認から。
通常、再帰関数は、

sum :: Num a => [a] -> a
sum []     = 0
sum (x:xs) = x + sum xs

といったように、関数定義の中で自分自身を呼ぶことで再帰処理を記述できます。
この例では、 sum (x:xs) = x + sum xs の部分で自分自身を読んでいますね。

では、

  • 関数に名前を付けることができない
  • 関数定義の中で自分自身を呼ぶことができない

というような制限プレイの中で再帰をしたくなったらどうすればいいでしょうか?
そんな要望に応えるために人類は 無名再帰 という方法を編み出しました。その名の通り、関数名に依らない再帰処理の方法です。

今回は無名再帰の具体的な作り方を見ていきます。


不動点コンビネータ (Y コンビネータ)

いきなりですが 不動点コンビネータ というやつがあります。 形式的な定義はこうです。

fix :: (a -> a) -> a
fix g = g (fix g)

見ての通り、関数 g を引数に取り、自分自身 fix g を引数として g を呼び出します。
ちょっと何がしたいのか分からない感じの関数ですね。では実際にこの fix に引数を与えた式を運算してみましょう。1

fix g
=> g (fix g)
=> g (g (fix g))
=> g (g (g (fix g)))
=> g (g (g (g (fix g))))
...
=> g (g (g (g (... (g (fix g)) ...))))

というように延々と関数の呼び出しが繰り返されます。
この 関数の呼び出しが延々と繰り返される というやつは、多くの言語の多くの状況で実際にやってみると 処理が無限にループして停止しない という扱いになるでしょう。

そんな関数が役に立つのか?
大丈夫、話はもう少しだけ続きます。


引数を消去する関数を与えてみる

今度は fix引数を消去する関数 を与えてみましょう。
例えば、定数関数 const を持ち出して、

const :: a -> b -> a
const x _ = x

const 0fix に与えてみます。

fix (const 0)
=> const 0 (fix (const 0))
=> 0

というわけで、式は 0 に評価されて停止しました。
このように fix に与える引数によっては無事に停止して値を返すことがあるのです。

これは Haskell をはじめとする遅延評価戦略の言語では 関数の展開はその結果が必要とされるまで行われない からですね。 とっても Lazy なんです。
const に渡された第二引数は計算結果に必要無いため評価も展開もされずに捨てられます。それがたとえ fix g であっても。


複数の引数を与えてみる

ここまでで、

  • 不動点コンビネータ は関数の呼び出しを延々繰り返すような動作をすること
  • 引数を消去する関数を渡せば停止させることもできること

を見ました。

再帰処理らしいことをしようとしたら 特定の条件で終了させる ということをしたくなるはずです。
では、終了条件を表現する前段階として複数の引数を渡してみましょう。

fix に次のような gn を渡します。

g _ n = if n == 0 then 0 else 1
n = 42

すると fix g n は次のように運算されます、

fix g n
=> g (fix g) 42
=> if 42 == 0 then 0 else 1
=> 1

はい、というわけで。fix に2つ以上の引数を渡すと2つめ以降の引数は g に渡されることが分かりました。
fix を1変数関数として見ていたときには使いどころが分かりづらかったのが、 何か実用的な式を組み立てられそうな気がしてきた と思いませんか?


実用的な計算例: 階乗計算

いよいよ不動点コンビネータを使った実用的な例を見ていきましょう。
0以上の自然数 n の階乗 fact n 2 を計算してみましょう。

階乗関数 fact を定義するための補助関数 fact' を次のように定義します。

fact' next n = if n == 0 then 1 else n * next (n - 1)

これを fix に与えて運算してみましょう。

fix fact' n
=> fact' (fix fact') n
=> if n == 0 then 1 else n * fix fact' (n - 1)

はい! else 節に注目してください fix fact' (n - 1) という形で再帰的構造が見えていますね。

n にも具体的な値を入れてみましょう。 fix fact' 3 を運算します。

fix fact' 3

-- fix の定義に従い fix fact' を展開
=> fact' (fix fact') 3

-- fact' の定義に従いfact' (fix fact') 3 を展開
=> if 3 == 0 then 1 else 3 * fix fact' (3 - 1)

-- 条件に従って if 式を評価
=> 3 * fix fact' (3 - 1)
=> 3 * fix fact' 2

-- 以下、繰り返し
=> 3 * fact' (fix fact') 2
=> 3 * (if 2 == 0 then 1 else 2 * fix fact' (2 - 1))
=> 3 * 2 * fix fact' (2 - 1)
=> 3 * 2 * fix fact' 1

=> 3 * 2 * fact' (fix fact') 1
=> 3 * 2 * (if 1 == 0 then 1 else 1 * fix fact' (1 - 1))
=> 3 * 2 * 1 * fix fact' (1 - 1)
=> 3 * 2 * 1 * fix fact' 0

=> 3 * 2 * 1 * fact' (fix fact') 0
=> 3 * 2 * 1 * (if 0 == 0 then 1 else 0 * fix fact' (1 - 1))
=> 3 * 2 * 1 * 1

=> 6

このように fix fact' 3 によって fact 3 を計算することができました。
つまり、

fact n = fix fact' n

として階乗関数 fact を定義することができました。


何が起こっている?

あらためて fact'fact の定義を見てみましょう。

fact' next n = if n == 0 then 1 else n * next (n - 1)

fact n = fix fact' n
-- fact = fix fact' と書いても良い

fact' の定義にも fact の定義にも自分自身を呼び出す記述はありませんから、今回のテーマ通り 自分自身を呼び出すことなく再帰処理を実現できた ということになります。
さらに fact' の定義をよく見ていると仮引数の next をまるで再帰呼び出しのように使っていることが分かります。

形式的な知識としてはこうです。

  • fix に関数 g を与えることで関数 f が得られる
  • fg よりも引数が一つ少ない関数として振る舞う
  • g の第一仮引数 next の呼び出しは、f の再帰呼び出しのように振る舞う

掴めてきましたか?実際に紙に手書きで運算してみるとより理解が深まるかも知れません。


一般化してみる

せっかく関数型言語という 抽象的な道具 を持ち出しているのでもっと一般化しましょう。
一般の再帰処理に必要な要素は以下のようなものです、

  • cond : 再帰の終了条件
  • process : 再帰呼び出し時の計算処理
  • initial : 再帰呼び出し時の初期値

これらが与えられたとき、不動点コンビネータを用いた再帰処理は以下のように作られます。

g next n = if cond n then initial
                     else process next n

f = fix g

ちなみに先ほどの階乗関数の場合、

cond = (== 0)
process = \next n -> n * next (n - 1)
initial = 1

です。

さらに cond, process, initial の組から g を作る関数 h を考えてみると、

h cond process initial = \next x ->
    if cond x
        then initial
        else process next x

となります。

f, g, h を一気にまとめると、
cond, process, initial の組が与えられたとき、対応する再帰処理を実現する関数 f は、

f = fix $ \next x ->
    if cond x
        then initial
        else process next x

と書けることが分かります。


実際に REPL で試す

ここまで書いてきたことは、実際に動く Haskell プログラムに落とし込むこともできます。
実際に無名再帰を使ってリストの総和を求める mySum を定義してみました。


こいつ、動くぞ!


はい、


まとめ

というわけで不動点コンビネータ fix を使って無名再帰を実現する方法について書いてきました。

ちなみにこの記事は 型無しラムダ計算インタプリタ Mogul 言語 で『無名再帰でも書くかー』と思ってみたものの無名再帰の書き方をすっかり忘れていたため、思い出しがてら書かれました。
コンビネータ理論を確立してくれた先人に感謝します。


私からは以上です。


  1. Haskell では Control.Monad.Fix モジュールを import することで実際に fix を使えるようになります

  2. 形式的な定義で fact n = n * (n - 1) * (n -2 ) * ... * 2 * 1 という計算です

サービス・プロジェクト改善のモチベーション

この記事は GYOMUハック/業務ハック Advent Calendar 2018 の5日目の記事です!
4日目の担当は Kouta Sasaki さん、6日目の担当は otoan_u さんです。

f:id:todays_mitsui:20181205192929j:plain

どうも、未経験からたったの7年でエンジニアになった三井です。

プログラムを書き始めて16年ほど、プログラムを業務に活かしはじめて7年ほどになります。
今年に入って人生で初めて「プログラマ」という肩書きで働き始めました!ちなみに昨年は管理部所属で情シスやってました!

プログラマやり始めて1年経ったので、なんとなく自社サービス・自社プロジェクトを改善していくモチベーションについて書きますね。


機能追加と改修・修正が繰り返されてゆく自社サービス

企業としてサービスを開発し、提供している場合、リリースして終わりというわけにはいかず、当然 機能追加と改修が繰り返されていくことになります。
もし大きな不具合が見つかれば急いで修正ですね。

そんな機能追加と改修・修正が繰り返されてゆく自社サービスの質を高く保っていくために重要なことがあります。
それは開発チームのモチベーションを高く保つことです。

チームのモチベーションが低ければ、サービスの質はだんだんと低下していく傾向にありますし。
逆にモチベーションを高く保つことで、リリース当初は荒削りだったサービスの質を徐々に高めていくこともできます。


サービスをより良くしていくためのモチベーション

では、サービスをよりよくしていくレベルでモチベーションを高く保つために必要な要素って何でしょう?
いろいろな切り口からいろいろな回答を上げることができそうですが、私は現場に立ってサービスを作っていく側として一つ確証に近いものを持っています。

モチベーションを高く保つために必要な要素、それは、
プロジェクトに関わるエンジニア一人ひとりが『このサービスは我々のものだ!』と感じられること です。


エンジニア一人ひとりが『このサービスは自分のもの』と感じられていれば、機能や仕様について各々が主体的に考えることが出来るようになり、自ずとクオリティも高まっていきます。
逆に、エンジニアが『自分のものではないサービスを仕方なくメンテしている』と感じてしまうと、機能追加には消極的になり、見直しが必要な仕様でも放置して開発を進めてしまいがちです。

プロジェクトメンバーが『このサービスは我々のもの』と感じられるために有効な仕掛けはいくつかあります。
今回はその中でも最も簡単な方法について書きます。


最も簡単で、強力な方法

最も簡単な方法とは バージョン管理 です。
『え、それだけ?』と思いましたか?それだけです。

弊社には会社の歴史から見て比較的古くから続く バージョン管理されていないプロジェクト がありました。ちょっとした CMS なのですが、弊社のビジネスにとっては地味に大切なものです。
このプロジェクト、Git リポジトリに変更を記録してはいるもののバージョン番号は振られていないし、コードも書き足し書き足しで秘伝のタレと化していました。

私が今年の1月にそのプロジェクトに join してすぐに、そのサービスに関わることを億劫に感じている自分に気付きました。

  • ちょっとの機能追加を重く考えてしまっている
  • 修正作業のやる気がおきない

そんな感情です。
なんだかプロジェクトを自分でコントロールしている気がしないし、改善しているはずなのに楽しくないのです。

いま思えば、改善が「見えない」ことが何よりもストレスだったのだろうと思います。


附番せよ、記録せよ、

バージョン管理のキモは 今すぐ始められて、目に見える ことにあります。
上記のプロジェクトにもバージョン番号を振るようにしました。

とはいえ最初は適当です。長い事やってるプロジェクトなので v3.0.1 から始めました。


バージョン番号の運用方法をもう少し具体的に、

  1. 週に1回のペースでリリースしてバージョン番号を上げる
  2. 修正リリースでもマイナーバージョンをガンガン上げていく
  3. Git Commit 時にコミットメッセージにプレフィックスを導入
  4. チーム向けにリリースノートも書きはじめた

するとどうでしょう。たったのこれだけで機能追加や不具合修正に やりがい 的なものを感じるようになりました。

もちろん、バージョン番号を振るなんて改善の見える化において初歩の初歩なんです。
それでも!バージョン管理 する/しない の間には大きな隔たりがあるのです。


さて、上記の運用ルールには一つひとつに狙いがあります。
それを具体的に見ていきましょう。


1. 週に1回のペースでリリースしてバージョン番号を上げる

本プロジェクトにおいて、それ以前に 定期リリース という概念はありませんでした。
それを大きく変えて、 機能追加がある限りは週1回のペースでマイナーバージョンを上げてリリースする ようにしました。

基本は月曜日の朝にバージョンを上げるかどうかの判断をし、上げると決めたら13時を目処にリリースに向けた作業をする流れです。


そうするとバージン番号がガンガン上がっていきます。
大きな機能追加があれば月曜でなくともリリースするので、もうどんどんバージョン番号がインクリメントされます。楽しい😉

人間は数字が少しずつインクリメントされるのを見るだけでテンションが上がってしまう生き物なんですよ。
楽しさは何よりもモチベーションの源になります。

※ ピンと来ない人は自分の預金通帳の残高が1秒間に1円ずつ増えていくのを想像しましょう


2. 修正リリースでもマイナーバージョンをガンガン上げていく

これは人にも依ると思いますが、私にとって不具合の修正作業はとてもネガティブなものでした。
だって、不具合を出した事は恥だし、修正って生産的じゃないし。

しかし!修正リリースでも積極的にバージョン番号を上げる方針にしました。
修正に付きまとうネガティブな感情をやわらげたくて。

これは一種の「問題の再定義」になっています。
非生産的な修正作業という認識を組み替え、バージョン番号が上がっていくさまを見せることで『これだけ不具合をぶっ潰して、サービスをより良いものにした!』と思えるようになったんですね。
これも改善の見える化です。


3. Git Commit 時にコミットメッセージにプレフィックスを導入

この手法は三井が発明したものではないので 参考記事 を見てもらいたいんですが。
バージョン番号の付番と同時に、Git 運用時のルールとして 「コミットメッセージのプレフィックス」 を導入しました。

プレフィックスを付けることのメリットは枚挙に暇が無いですが、メインは、

「お!このタイミングでめっちゃいい機能が追加されとるやんけ!」

とか

「お!ここらへんでめっちゃ不具合潰していい感じにしとるやんけ」

とか後から振り返って楽しむ用です。


4. チーム向けにリリースノートも書きはじめた

上記のようなことをして改善の見える化が出来るようになったので、次のステップとして、隔週のペースでリリースノートをまとめるようにしました。
とはいえまずはチームメンバー向けです。

リリースノートと言うと、本体のサービス改善とは別の作業のような気がしてしまいますが、
プロジェクトチームから外に向けては やってる感 を見せる事が出来ますし。
他部署の人間的には 新機能にいち早くキャッチアップするきっかけ になっているんじゃないかなと思います。

言ってみれば、エンジニアだけでなく会社全体で『このサービスは我々のもの!』と思うための仕組みですね。


まとめ

今回はエンジニアチームのモチベーションを高める簡単な、でも強力な方法、バージョン管理について書いてみました。

社内で使うちょっとしたツールであれ、ビジネスの基幹に関わるサービスであれ、自社開発しているものであれば積極的に・おおげさにバージョン管理してみましょう。
「小さなツールだから...」なんてのは関係ありません。

バージョン番号を附番し、記録をはじめた瞬間からそのサービス・プロジェクトは 我々の物 になります。
そしてサービス・プロジェクトが我々の手中にある限り、それを無限により良くしていくことができるのです。
そう、他でもない、我々の手でね。


私からは以上です。