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

概要

この記事では、無限再帰を検知するための仕組みである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: を定義します。

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関数が正しくなくても再帰を止めます。
安心安全ですね。

実験

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

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で動かしてみましょう。

うごいた！

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

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 ]

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

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

おわりに

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

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