2013/03/15

静的チェックで困った話

Gaucheは型付けも含めて色々動的な言語だけれど、コンパイル時にわかることは なるべく検査するようにしている。例えばローカル定義された関数は、その定義が 変更されないかどうかわかるので、アリティチェックの対象となる。

(define (start/end-vector->shape Vb Ve)
  (define (interleave a b)
    (cond [(null? a) b]
          [(null? b) a]
          [else (cons (car a) (interleave b (cdr a)))]))
  (apply shape (interleave (s32vector->list Vb) (s32vector->list Ve))))

これは今適当に引っ張ってきた関数だけど、interleaveはローカル定義されて 変更されていないので、常に2引数で呼ばれることがわかる。コード中で、interleaveが 1引数や3引数で呼ばれている箇所があれば、コンパイル時にエラーにできる。

グローバルに定義されている関数の場合はちと面倒だ。 実行時に関数定義が変更される可能性があるので、 コンパイル時に呼出側を静的に拒否することはできない。 ただまあ、実行時の関数の置き換えをやりたいのは開発中とか緊急時で、 普段はそうそう必要なものでもないので、Gaucheではユニットテスト時に モジュール毎に検査するのことを推奨している(test-module)。

例外はdefine-inlineで定義された関数で、インライン展開は コンパイル時に行われるから、この関数は開発者が「これは動的に置き換えない」と 宣言したものと解釈でき、コンパイル時の静的検査の対象にできる。 インライン展開される標準関数(consとか)が、シャドウされない限り コンパイル時チェックされるのもこの理由。

さて、ここまでが前置き。

以前、map系関数のインライン展開を試していた時に、 コンパイル時アリティ検査が干渉して困ったことがあった。 実際はmapじゃなかったんだけど、話を単純にするためにこんなナイーブなmapの定義を考える。

(define-inline (map proc xs . xss)
  (if (null? xss)
    ;; (map proc xs) で呼ばれた場合
    (if (null? xs)
      '()
      (cons (proc (car xs)) (map proc (cdr xs))))
    ;; (map proc xs ys zs ...) で呼ばれた場合
    ... 定義省略 ...))

そんで、このmapにローカルで定義された関数を渡したとする。

(define (foo as bs)
  (define (bar a b)
    ...)
  (map bar as bs))

mapがインライン展開されるとこうなる。

(define (foo as bs)
  (define (bar a b)
    ...)
  (let ([xs as]
        [xss (list bs)])
    (if (null? xss)
      (if (null? xs)
        '()
        (cons (bar (car xs)) (map bar (cdr xs)))) ; !!
      ... 複数引数の処理 ...)))

!! の行で、barが1引数で呼ばれている。コンパイラがこれを弾いてしまったのだ。

実際には !! の行は実行されることがない。 ローカル束縛をちゃんと追跡すれば、(null? xss) が常に#fであることが コンパイル時にわかるので、1引数の場合の処理部分はコンパイル時に削除されるべきで、 そうすれば問題は生じなかっただろう。

けれどもこの分岐が単純な (null? xss) でなかったらどうだろうか。 例えば (weird-map info proc . args) みたいなインタフェースで、 procのアリティが外部関数の呼び出しで計算されるものだとしたら?

(define-inline (weird-map info proc args)
  (if (= (calculate-arity-from-info info) 1)
    ;; procは1引数
    ...
    ;; procは複数引数
    ...))

こうなってくるとコンパイル時に静的にprocのアリティを検査して弾くことは難しくなる。

今回はアリティだったけれど、同じことは実行時に属性が検査される あらゆる場所で起こり得る。例えばこんなコード:

(define-inline (do-somethin x)
  (cond
    [(check-it x) (string-length x)] ;; check-itが#tならxはstring
    ...))

プログラマはcheck-itが#tを返したらxが文字列であることを 知っているが、コンパイラにはわからないとする。この関数が 次のようなコンテキストでインライン展開された場合:

(let ((n 3))
  ...
  (do-somethin n)
  ...)

整数がstring-lengthに渡される、という呼び出しがコード中に 出現することになる。そこは一見矛盾しているけれど、 実際には決して実行されないのでコードのコンパイルは通ってくれないと困る。

ナイーブな解法は、こういう箇所にその都度注釈を入れてコンパイラに 情報を伝えてやることだろう。Common Lispの記法を借りればこんな感じ：

  (cond
    [(check-it x)
     (locally (declare (string x))
       (string-length x))]
    ...))

だけどこういう注釈をちまちまつけてると、コンパイラのご機嫌を取ってる気分に なってくるのも確か。さらにdo-somethinの定義が自分の触れない場所に あったりすると不満が募る。(それで不満に感じないなら最初から静的型付き言語を使ってるって)。

問題の根源はコンパイラが十分に情報を持っていないことにある。 静的型付き言語は「コンパイラに型という言語でもって情報を伝える」っていう 方針なわけだけど、型という言語体系にうまく載せられる情報と載せにくい情報があるからなあ。

ひとつの手は全てのプログラムをコンパイラが見ることだ。Stalinがやってるけど、 標準ライブラリも含めてコンパイル時に全部を見ることで、今回の場合だとcheck-itが #tならxが文字列であることを演繹できる。でもこの方法はプログラムが大きくなると コンパイルに時間がかかりすぎて破綻する。

むしろ、コンパイラが使える材料を一種の知識ベースのように 考えて、後付けでいろいろな情報を放り込んでやれないかな。 ここの例でいえば、「(check-it x)が#tを返したらxはstringだよ」っていう情報を check-itの実装者以外でも後から注記できるようにするとか。

ライブラリ関数が使われる箇所でコンパイラが実際にどういう情報を必要とするかを、 ライブラリ実装者があらかじめ全て見通しておくことはできないと思う (「それができるように型システムを整備する」というのが静的型の発想だけど、 そこで完全を目指すと「仕様を全部形式言語で書いておく」なんてところに 行き着いちゃうんじゃないだろうか)。

Lispのカルチャーの一つは、「システムを書いた人より、それを使う人の方が賢い」 という前提だ。なぜなら人は道具を使うことで、その道具に関する新たな知見を「発見」して ゆくから。後付けで作者以外が知識をばらばらに追加してゆくのはこういう思考に 合うかもしれない。

Tag: Programming