Island Life

< ピアノレッスン86回目 | 在宅勤務と出勤 >

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

Past comment(s)

jmuk (2013/03/17 07:10:39):

後者は例題としてはよく見かけるのですが、現実のプログラミングではそれほど多くないのではないでしょうか。ほとんどの場合はどちらかの表現がユーザ入力やデータベース内の表現で、もう一方がプログラマにとって扱いやすい表現なため、どこかで変換をかけて正規化することで問題として発現しなくなる系の問題な気がします。 どうしても複数の型がありうる場合はvariant typeとして表現可能ですし、それをライブラリが必要とするものしか受け入れないのだとすると、意図しない型が来た場合にはどうするのか?といった問題もあるのでは(静的型では意図しない型は来ない、動的型では、エラーや例外を返すなどの処理が入る)。 OCamlはduck typingみたいに「このメソッドとこのメソッドを持つオブジェクト型」のような指定があるため、制限は緩めることができるといえるかもしれません。

また、 OCaml の Polymorphic variant (http://caml.inria.fr/pub/docs/manual-ocaml-4.00/manual006.html#toc36) や merd (http://merd.sourceforge.net/types.html) の型システムなどの取り組みも近い問題意識があると思われます。ただ、OCamlもpolymorphic variantは使い過ぎるとわけわからなくなるし標準ライブラリもあまりつかってないし、merdはプロジェクト自体が終わっちゃったので、この辺をどうにかする言語はないのかなあという気分は私も思います。

shiro (2013/03/17 09:43:44):

後者ってのは「データがこの条件を満たす場合にはこういう性質があることがわかる」っていうケースの話ですよね。まだそれを検証に使ったことは無いのですが、最適化に使いたいというケースは非常に良くありまして、Common Lispで型注釈を入れまくるケースの多くはこういうパターンです。(そんでもって、CLを使ってると「こんだけ型注釈入れてるんだからそれ使って検証もできるはずだよなあ」と思うのです。)

バリアント型を使うという発想は、「こういう情報を型で表現するなら」という観点からの発想ですよね。それはそれでわかるのですが、違う観点がある、というのがここしばらくの型絡みの話です。

例えばあるライブラリがインタフェースとしては(Int,Int)を受け取ることになってるけれど、前者のIntが特定の値の時は後者のIntの値の範囲は必ず[0,1023]だよね、ということがわかった。でもライブラリ作者はそこまで見通せてなくて、そういう情報を型にエンコードしていなかった。残念ながらライブラリのコードを変更してもらうことはできない。とか。

型から設計を考えるなら「作った後から性質が判明する」ってこと自体がありえないのかもしれないですが、CLとかSchemeとか書いてるとそういうことってしょっちゅうあるんですよね。

後から判明した型とオリジナルのライブラリのAPIを取り持つアダプタコードを書いて、それが実行時オーバヘッドゼロ(つまりコンパイラに情報を与えるためだけのコード)になるなら、ここで書いた「後付けでコンパイラに情報を教えてあげる」っていうのと等価になるかもしれない。

Post a comment

Name: