止めて無限再帰 スタックが〜スタックが〜苦しくなるぅ〜

# 概要
この記事では、無限再帰を検知するための仕組みであるmeasure関数のSmalltalk実装を紹介します。

# はじめに
みなさんのVMは快調に走っているでしょうか。
CogVMをお使いの皆さんはきっとJITをブイブイいわせてカッ飛ばしていることでしょう。
SpurやSistaでさらにブッ飛んでいるでしょうか。
VMが速くなることは素晴らしいことですが、ちょっと困ったことがあります。
私のようにオッチョコチョイなプログラマは、つい再帰で無限ループさせちゃいます。
そしてVMが速いとぶっ壊れてしまうまでの猶予が短くなってしまいます。
そう、私のイメージがよく壊れるのはVMが速いせいなのです。

# measure 関数による停止性の検証
と、自分がヘッポコなのを他人のせいにしても仕方ないので、なんとかしたいと思います。
再帰プログラムの停止性を検証する手法として、measure関数というものがあります。
どんなものかというと、再帰関数と同じ引数をとって、自然数を返り値とする、かつ、再帰が深くなるに従って単調減少する関数 (measure関数) を用意してあげる、それだけです。
これだけで再帰が停止するかどうかを確認できます。

どんな仕組みかというと…
どんな深い再帰にも、最初の1回目があります。その時のmeasure関数の値を仮に10としましょう。
ここで、measure関数は再帰するたびに返り値が小さくなります。
つまり、次の再帰の時には必ず9以下の値になります。
さらに次の再帰の時にはもっと小さな値になります。
どんどん小さくなっていきますが、モノには限度というものがあります。
そう、返り値は自然数なので、どんなに小さくても 0 より小さくはなりません。
ここで、0が自然数かどうかという宗教論争は横に置きましょう。
つまり、再帰はどんなに深くても、最大でも再帰の最初の1回目の measure 関数の値+1回しか再帰できません。
**measure 関数が本当に再帰のたびに単調減少すれば。**

# Smalltalk での measure 関数
でもSmalltalkでそんなことを事前に保証することは難しいですね。
だから実行時にそれを確認しましょう。そう、 thisContext でね。
ようするに 自分の measure の値が 0以上の整数で、かつ、 sender の measure の値よりも小さいことを確認すればよいのです。
このルールが守られている限り、再帰は有限回数で停止します。

# Smalltalk での実装
さあ、実装の時間です。まずは Object>>measure: を定義します。

```smalltalk:Object
measure: tmpVarName
	| context measure receiver selector |
	context := thisContext sender.
	measure := context tempNamed: tmpVarName asString.
	(measure isInteger and: [measure >= 0])
		ifFalse: [ ^ self error: 'Invalid measure.' ].
	receiver := context receiver.
	selector := context selector.
	context := context sender.
	[ context notNil ]
		whileTrue: [ (context selector = selector and: [ context receiver == receiver ])
				ifTrue: [ | pred |
					pred := context tempNamed: tmpVarName asString.
					measure < pred
						ifFalse: [ self error: 'Invalid recursion' ].
					^ self ].
			context := context sender ]
```

実装はこれでおしまい。

動かし方は簡単で、引数として一時変数の名前を渡してあげます。
すると、コンテキストをたぐって再帰の sender 側のコンテキストでの同名の一時変数の値と比較します。
整数じゃなかったり、0より小さかったり、sender 側の値よりも小さくなってなかったら、エラーで止まります。
そう、measure関数が正しくても再帰は止まり、measure関数が正しくなくても再帰を止めます。
安心安全ですね。

# 実験
では動かしてみましょう。
文字列をひっくり返すだけの簡単な例題です。
まずはちゃんと再帰が停止する例。

```smalltalk:SmalltalkAdvent2016
reverse: aString
	| size |
	size := aString size.
	self measure: 'size'.
	^ aString
		ifEmpty: [ aString ]
		ifNotEmpty: [ (self reverse: (aString copyFrom: 2 to: aString size)) copyWith: aString first ]
```

この例では、 String>>size を measure 関数として利用しています。
その値を ```size``` という一時変数でとっておいて、 ```self measure: 'size'``` で ```size```の値が measure 関数の規則にのっとっているかを検査します。

さあ、Playgroundで動かしてみましょう。

<img width="929" alt="スクリーンショット 2016-12-02 5.08.58.png" src="https://qiita-image-store.s3.amazonaws.com/0/59918/bb2d9ab7-480d-20a7-e7c6-0b59050fcb20.png">

うごいた！

では、再帰が停止しない例。

```smalltalk:SmalltalkAdvent2016
wrongReverse: aString
	| size |
	size := aString size.
	self measure: 'size'.
	^ aString
		ifEmpty: [ aString ]
		ifNotEmpty: [ (self wrongReverse: (aString copyFrom: 1 to: aString size)) copyWith: aString first ]
```

あー、いかにもやっちゃいそうなミスですね。
動かしてみましょう。（万一のためにイメージを保存してから）

<img width="930" alt="スクリーンショット 2016-12-02 5.16.08.png" src="https://qiita-image-store.s3.amazonaws.com/0/59918/6a792ffc-0078-a4f2-9458-c0f6ee40c726.png">

はい、measure関数の値が小さくならなかったために、**ちゃんと**停止しました。エラーで。

# おわりに
実際にこれを使うのはテスト時がいいです。
thisContext への操作はコストがかかるからです。
そして再帰はホットスポットになりやすい部分なので、パフォーマンスへの影響は小さくないでしょう。

だいたい、無限再帰でイメージぶっこわしちゃうのは、再帰するコードを書いた直後なので、その時だけ measure 関数のような仕組みでプロテクトしてあげれば、まあそれでいいのではないでしょうか。
Smalltalkだし。