Concurrent Clean : インライン化と停止性

http://www.tom.sfc.keio.ac.jp/~sakai/d/?date=20050724#p01

• • via: http://d.hatena.ne.jp/amachang/20080124/1201199469

前に調べようと思って忘れてた件にたどり着いた。で、次の論文をちょっと見てみた。
http://research.microsoft.com/%7Esimonpj/Papers/inlining/

data U = MkU (U -> Bool)

russel :: U -> Bool
russel u@(MkU p) = not $ p u

x :: Bool
x = russel (MkU russel)

Cleanでは、このプログラムは普通にコンパイルできるのだけれど、それはなぜかという問題。
Haskellでこれが止まらない理由は、上の論文のp.6に書かれていることには、russel関数は小さくて再帰関数ではないのでinline化しようとするけれど、実際にinline化すると元の式に戻ってしまうので、inline化処理が止まらないということになるらしい。
Cleanがどういう処理をしているか詳しい資料を知らないし、そのへんのソースを読み解いたわけではないので、日頃生成されたABCコードを眺めている感覚の話なのだけれど、Cleanのコンパイラはあまりinline化に熱心ではないためではないかと思う。例えば、次のようなプログラムですら、Cleanはinline化しない。

module Main

import Int

Start = id (1 + 2)

id a = a

生成されるABCコードは次の通り。idの呼び出しだけでなく、(1 + 2)の部分もそのままになっている様子がわかる。

s1
	pushI 2
	pushI 1
	addI
	buildI_b 0
	pop_b 1
.d 1 0
	jsr s2
.o 1 0
	pushI_a 0
	pop_a 1
.d 0 1 i
	rtn
.o 1 0
s2
.d 1 0
	rtn

Cleanがinline化に消極的なのは、１つには、inline化を明示的に指定することができるマクロが関数以外にプログラムの機能として存在するためではないかと思う。たとえば、次のように書けば、idの呼び出しはinline化されて消去される。

module Main

import Int

Start = id (1 + 2)

id a :== a