Vim script で ES6 Promise 実装した

Vim Advent Calendar 2017 の19日目の記事です.Vim script で ES6 の Promise を実装した話を書きます.

もし Vim script が分からなくても,最後の章「Promise の実装の詳細」は Vim script とは独立した内容になっているので,Promise の実装に興味があれば読んでみてください.

TL;DR

実装はこちら

Promise とは

ES6 (ES2015) で ECMAScript に標準に導入された非同期処理を扱うためのライブラリです. これを使うことにより,「未来のある時点でいずれ値を持つ」値を扱うことができ,ES5 まではコールバックで扱う必要があった非同期処理を逐次処理的な書き方で書きつつ,エラーも一貫した方法で扱えます.

例えば,ネットワークのどこかから取ってきたデータをファイルに保存する処理は,ネットワークからの fetch とファイルへの保存の2回の非同期処理を挟むので

fetch('https://example.com', function (err, data) {
    if (err) {
        console.log('Error', err);
        return;
    }
    writeFile('data.txt', data, function (err) {
        if (err) {
            console.log('Error', err);
            return;
        }
        console.log('Done!');
    });
});

のようにネストしたコールバックとエラーハンドリングで処理がぶつ切りになってしまうのですが,Promise を使うと

fetch('https://example.com').then(function (data) {
  return writeFile('data.txt', data);
}).then(function () {
  console.log('Done!');
}).catch(function (err) {
  console.log('Error', err);
});

のように,本来実行される順序でコードを書くことができ(fetchwriteFile),エラー処理も .catch メソッドによって分離できます.

なぜ Promise を Vim script で実装したのか

Vim 7.4 までは,Vim script は基本的にユーザからの入力をブロッキングして処理をするようになっていました.そのため,Vim プラグイン作者たちは vimproc という Vim script から popen や socket などを扱える C ライブラリを書いたり, CursorHold イベントを繰り返し発火させてポーリングするなど,様々なワークアラウンドで対処してきました.

ですが,Vim 8 になり,jobchannelterminal といった,ユーザの処理をブロックしない非同期処理の機能が続々と入りだしました(一部は Neovim が先に実装したアイデアが Vim8 にポーティングされました).

これによって Vim プラグインワークアラウンドを使わずともユーザの入力をブロックしない快適なプラグインをつくる下地を手に入れると同時に,非同期処理と戦わなければならなければならなくなりました. しかしコールバック方式では,少し処理が複雑になったりエラー処理を真面目にやると,すぐメンテナンス性が低下してしまうのは JavaScript での経験で分かっています. さらに,ちょうど同じ時期に Vim8(および後に Neovim にも)ラムダ式が入りました.

ということで,JavaScript で使われているアイデア(Promise)を Vim にポーティングしました.

使い方

vital.vim の標準モジュール入りを目指して実装しています.現在はまだプルリクの段階ですが,あとはテストとドキュメントを整備すればレビュー可能になる予定です. master にマージされました!標準で利用することができます

:VitalizeAsync.Promiseプラグインに入れるか,vital#vital#import('Async.Promise') でインポートすることで試せます.

API はそれなりに ECMAScript と互換なので,ECMAScript の Promise を知っている人はほぼドキュメントを見なくても使うことができると思います.

MDN の Promise のドキュメントを見ていただいたほうが分かりやすいかもしれません. 詳細な仕様が知りたい!というマッチョな方はECMA-262の仕様を見ていただいても良いでしょう.

let s:Promise = vital#vital#new().import('Async.Promise')

" Promise な値を生成する
let p = s:Promise.new({resolve -> resolve(42)})
let p = s:Promise.new({_, reject -> reject('error!')})

" resolve する値が定数のときの省略形(上記と同じ)
let p = s:Promise.resolve(42)
let p = s:Promise.reject('error!')

" .then() で非同期な処理に順番を付ける (20 と出力される)
let p1 = s:Promise.new({resolve -> resolve(10)})
           \.then({i -> i + 10}).then({i -> execute('echom i', '')})

" .catch() で例外を補足できる
let p2 = s:Promise.new({-> execute('throw "ERROR!"')})
           \.catch({err -> execute('echom string(err)', '')})
" Output: { 'exception' : 'ERROR!', 'throwpoint' : '...' }

" .all() で待ち合わせ
call s:Promise.all([p1, p2]).then({-> execute('echom "Both p1 and p2 done!"', '')})

" .race() でどれか1つ少なくとも完了
call s:Promise.race([p1, p2]).then({-> execute('echom "Either p1 or p2 done!"', ''}))

詳細は help ドキュメントを参照してください.

具体例

これだけではピンとこないかもしれないので,具体例を少し見てみましょう.ここではコードを少し簡略化して書いています.実際に使う場合はもう少し考慮しないといけないエッジケースがある場合がありますので,ご注意ください.

タイマー

一番分かりやすいタイマー機能で Promise を使ってみます. Vim script の timer は指定したミリ秒時間後にコールバックで指定した処理を遅らせられる機能です. ですので,下記のようにして wrap して Promise オブジェクトを返す関数をつくることで,一定秒数後に発火する処理を Promise を使って書けるようになります.

let s:Promise = vital#vital#new().import('Async.Promise')

function! s:wait(ms)
  return s:Promise.new({resolve -> timer_start(a:ms)})
endfunction

call s:wait(500).then({-> execute('echo "After 500ms"', '')})

Next tick

タイマーのコールバックは Vim が入力待ちの時(busy でない時)に発火するとドキュメントに明記されています. よって,他にもっと大切な処理がある場合はそちらを優先し,優先度の低い処理は Vim が入力待ちになるまで遅らせるのに使えます.

function! s:next_tick()
  return s:Promise.new({resolve -> timer_start(0, resolve)})
endfunction

call s:next_tick()
  \.then({-> 'ここで優先度の低い処理をする'})
  \.catch({err -> execute('echom ' . string(err), '')})

タイマーの待ち時間を 0 に指定しているので,Vim が入力待ちになった(=優先度の高い処理が完了した)直後に .then で指定した処理が行われます.

ジョブ

Promise が最も威力を発揮するのはjob機能だと思います.job は非同期にコマンドを実行し,コールバックで channel を通してコマンドと標準入出力のやりとりをします.

ここでは job を wrap し,非同期にコマンドを実行する処理を Promise で書くとどうなるかを見てみます.

let s:V = vital#vital#new()
let s:Promise = s:V.import('Async.Promise')

function! s:read_to_buf(buf, chan) abort
  for part in ['err', 'out']
    let out = ''
    while ch_status(a:chan, {'part' : part}) ==# 'buffered'
      let out .= ch_read(a:chan, {'part' : part}) . "\n"
    endwhile
    let a:buf[part] = out
  endfor
endfunction

function! s:sh(...) abort
  let cmd = join(a:000, ' ')
  let buf = {}
  return s:Promise.new({resolve, reject -> job_start(cmd, {
              \   'close_cb' : {ch ->
              \     s:read_to_buf(buf, ch)
              \   },
              \   'exit_cb' : {ch, code ->
              \     code ? reject(buf.err) : resolve(buf.out)
              \   },
              \ })})
endfunction

ここでは非同期にシェルコマンドを実行する s:sh() 関数を定義しています.

s:read_to_buf() は与えられた channel からバッファされた標準入出力と標準エラー出力を読み出し,引数 buf で与えられた辞書に保存するヘルパー関数です.

一番肝なのは return s:Promise.new(...) の部分です.close_cb はコマンドからの出力が終わり channel が閉じられるタイミングで発火するので,ここでコマンドからの出力を読んでおきます.さらにコマンドの実行が終わるタイミングで発火する exit_cbステータスコードを受け取り,0(成功)なら標準出力と共に Promise を resolve,非0(失敗)なら Promise を reject します.

早速,まずは試しに ls -l コマンドに使ってみましょう.

call s:sh('ls', '-l')
  \.then({out -> execute('echom ' . string('Output: ' . out), '')})
  \.catch({err -> execute('echom ' . string('Error: ' . err), '')})

これだけで,コマンドを非同期に実行して,その出力に対して何か処理をするというコードが,しかも逐次的に書けるようになりました.

コマンドが失敗した場合は .catch() で指定した処理が発動します.

もう少し複雑な例を見てみます. 4つのリポジトリを一気に clone し,全て完了したタイミングで何か処理をしたいとします.ですが,ネットワークの状態やリポジトリのサイズなどにより,どのリポジトリの clone が最後に完了するかは分かりません.

call s:Promise.all([
\   s:sh('git', 'clone', 'https://github.com/thinca/vim-quickrun.git'),
\   s:sh('git', 'clone', 'https://github.com/tyru/open-browser-github.git'),
\   s:sh('git', 'clone', 'https://github.com/easymotion/vim-easymotion.git'),
\   s:sh('git', 'clone', 'https://github.com/rhysd/clever-f.vim.git'),
\]).then({-> exeute('echom "All repositories were successfully cloned!"', '')})
  \.catch({err -> execute('echom "Failed to clone: " . ' string(err), '')})

s:shPromise.all を使えば,これだけで OK です.

.then の中の処理は4つのリポジトリの clone が全て完了した時点で発火します.また,4つのリポジトリのうち,1つでも clone が失敗すれば,.catch の中の処理が呼ばれてエラー処理を行うことができ,.then の中の処理は呼ばれません.

次の例は,タイムアウト付きのコマンド実行です. 特定のコマンドを実行したい,しかし時間がかかりすぎるときはエラーにするか,別の処理をしたいというケースです

call s:Promise.race([
\   s:sh('git', 'clone', 'https://github.com/vim/vim.git').then({-> v:false}),
\   s:wait(10000).then({-> v:true}),
\]).then({timed_out -> execute(timed_out ? 'Timeout!' : 'Cloned!', '')})

上記で定義した,一定ミリ秒待ってから発火する Promise を返す関数 s:wait() と,Promise.raceを使います.

Vimリポジトリを clone する処理をする Promise オブジェクトと,10秒間待つ Promise オブジェクトのうち,速いほうで resolve されるので,10秒内に clone できなければ待たずに次の処理にいく,ただしタイムアウトしたかどうかは引数 timed_out で知ることができるという処理になっています.

このように,繰り返さない非同期処理(未来のある時点以降は値を持つような処理)を組み合わせる際に,Promise は非常に強力な道具であることが分かりました.また,最後に .catch でエラー処理をぶら下げておけば,それまでのうちどこでエラーが起きても最終的に .catch の処理内で拾うことができるため,エラー処理が簡潔になります.

最後にさらに実践的な例を見てみます. GitHub API を叩いて,Vimリポジトリのうちもっとも :+1: リアクションが多い issue の URL を取得してみましょう.

まずは GitHub Search API を呼ぶ関数をつくってみます.

let s:HTTP = s:V.import('Web.HTTP')
function! s:github_issues(query) abort
    let q = s:HTTP.encodeURIComponent(a:query)
    let url = 'https://api.github.com/search/issues?q=' . q
    return s:sh('curl', url).then({data -> json_decode(data).items})
endfunction

vital.vimWeb.HTTP モジュールを使って検索クエリをエンコードし,先ほど定義した s:sh() 関数と curl でリクエストを送り,結果を json_decode 組み込み関数でパースして返すだけです.たった6行ですね.

次にこれを使って API を使ってみます.

call s:github_issues('repo:vim/vim sort:reactions-+1')
    \.then({issues -> execute('echom ' . string(issues[0].url), '')})
    \.catch({err -> execute('echom ' . string('ERROR: ' . err), '')})

合計たった9行で実装できました.エラーも .catch で処理できています.ちなみに最も👍の多い issue は #1735 でした.

今回は試していませんが,Neovim のリモートプラグインへの RPC 経由の request も同様にうまく扱えると思います.(request を送り,結果が返ってくる Promise オブジェクトを定義)

Vim script 版の JavaScript 版との違い

例外が投げられた時の処理

JavaScript とは違い,Vim script では文字列を例外として throw します.:catch 節内では throw された文字列を v:exception で取りますが,例外が発生した位置はそれとは別に v:throwpoint で取得します. このため,例外が投げられた時に単純に v:exceptionreject すると例外の発生位置が取れなくなってしまいます.そのため,Async.Promise では throw された文字列で reject する代わりに {'exception' : v:exception, 'throwpoint' : v:throwpoint} という辞書で reject するようになっています.

" Output: { 'exception' : 'ERROR!', 'throwpoint' : '...' }
call s:Promise.new({-> execute('throw "ERROR!"')})
     \.catch({err -> execute('echom string(err)', '')})

これによって .catch() の中では例外の中身と例外が発生した場所の両方を知ることができます. s:Promise.new() の中で reject() を呼んだ場合や .then() または .catch() の戻り値に reject された Promise の値を指定した時など, 例外が投げられる以外の原因で Promise が reject されたときは JavaScript 版と同じです.

" Output: 'ERROR!'
call s:Promise.new({_, reject-> reject('ERROR!')})
     \.catch({err -> execute('echom string(err)', '')})

.then()や.catch()の発火のタイミング

Vim script 版の .then/.catchJavaScript 版の .then/.catch では引数に指定された関数の発火タイミングが違います.

Vim script 版では下記の(1)〜(3)の順序で処理が行われる(引数で渡された関数が同期的に実行される)のに対し,

(1)
call s:Promise.new({resolve, reject -> (2)}).then({-> (3)})
(4)

JavaScript 版では下記の(1)〜(3)の順序で処理が行われます(引数で渡された関数が非同期的に実行される).

(1)
new Promise((resolve, reject) => (2)).then({-> (4)})
(3)

Vim script でも .then の中でタイマーを噛ませば同じ処理は行えるのですが,頻繁に呼ばれるので,ただでさえ遅い Vim script を無駄に遅くしたくないという意図でこの挙動になっています.(最終的には要ベンチマーク

ご指摘をいただいて修正しました.@azu_reさん,ありがとうございました.

この違いはプルリクのブランチの最新で撤廃されました.現在は .then.catch が呼ばれた段階でレシーバの Promise オブジェクトがすでに settled になっていても,引数に渡された関数は timer_start をはさんで非同期に実行されることが保証されるようになりました.これによって,実行は .then.catch の単位で行われることが保証され,ユーザの入力を優先するようになります.ベンチマークを取ったところ timer_start をはさんでも1回の実行は(手元の環境で)1ms 未満と問題無さそうだったため処理を変更しました.

Promise の実装の詳細

実装はこちら

ここからは Promise がどういったもので,どのように実装されているのかを説明します.Vim script に限らない話になっています.このライブラリは es6-promise という polyfill ライブラリ(ES5 まででも ES6 Promise を使えるようにするための shim)の実装を参考にしています.

Promise の内部状態の遷移

まずは,Promise が内部でどうやって非同期処理の状態を管理しているかについて説明します.

Promise には内部的に 'pending', 'fulfilled', 'rejected' という3つの状態のうちいずれかを持っています.

  • pending: 処理が未完了の状態
  • fulfilled: 処理がエラー無く完了した状態
  • rejected: 処理中にエラーが発生した状態

pending から fulfilled または rejected へは一方向の遷移になります.つまり,Promise オブジェクトが生成された直後の状態は pending であり,その後 fulfilled か rejected のどちらかに遷移するか,または永遠に pending のままになります.この pending から fulfilled/rejected への遷移処理は publish と呼ばれ,fulfilled か rejected になった状態を settled と呼んでいます.(下図はMDNより引用

f:id:rhysd:20171219000507p:plain

例えば,次の処理を考えてみましょう.

const p1 = new Promise(resolve => resolve('OK') /* (2) */);
const p2 = p1.then(() => { throw 'OOPS'; /* (3) */ });
const p3 = p2.catch(reason => console.log('ERROR:', reason) /* (4) */);
const p4 = p3.then(() => 'END' /* (5) */);
/* (1) */

処理は上記の (1)〜(5) の順番に実行されます.

表にすると,各 Promise の値 p1, p2, p3, p4 の状態は下記のように遷移していきます.

実行フェーズ p1 p2 p3 p4
(1) pending pending pending pending
(2) fulfilled pending pending pending
(3) fulfilled rejected pending pending
(4) fulfilled rejected fulfilled pending
(5) fulfilled rejected fulfilled fulfilled

p1 から p2 に順番に Promise の遷移が伝搬している様子がわかると思います.

Promise 内部のデータ構造

内部では .then などで Promise の値がネストするたびに,Promise の値は自分の次に処理されるべき Promise の値を子として持ちます.なので,実は Promise は内部的には木構造になっています.

上記の例のように Promise は直列に処理を行うことが多いので,直感的には単方向リストでは?と思うかもしれません.ですが,実は次のような場合がありえます.

const p1 = new Promise(resolve => resolve(42));
const p2 = p1.then(() => 10);
const p3 = p1.then(() => 20);

この場合,Promise のツリーはイメージとしては

{
  result: 42 /*p1*/,
  children: [
    { result: 10 /*p2*/, children: [] },
    { result: 20 /*p3*/, children: [] },
  ]
}

となります.実際には各 Promise の値は上記の3状態のいずれかを表すメンバーと,子要素の resolve された時または reject された時に呼ばれるコールバック関数を配列で保持しています.

Promise {
    state: 'pending',
    result: undefined,
    children: [ Promise{...}, Promise{...} ],
    on_fulfilled: [ resolved_fun1, resolved_fun2 ],
    on_rejected: [ rejected_fun1, rejected_fun2 ],
}

よって,new Promise で値をつくり,それに対して .then.catch を呼び…という処理は実は内部で木構造を構築する処理をしています..then を読んだ時,すでにレシーバ(=親)の Promise オブジェクトが fulfilled か rejected になっていれば,.thenまたは.catchの中身は即座に実行されますが,そうでなければ子は親からのコールバックを待って pending 状態のまま親の子として .then.catch のコールバックと共に登録されます.この処理を subscribe と呼んでいます.

次に,生成された Promise オブジェクトがどう resolve/reject されていくかを見てみます.

new Promise(resolve => resolve(42)) のコールバック内で,resolve(42) が呼ばれる時に何が起きているのでしょうか.

  1. resolve() が呼ばれる
  2. resolve() で引数に与えられた値が Promise の結果として保存される(これより後で .then を追加されても大丈夫なように)
  3. Promise の状態を fulfilled に変更します
  4. 親が fulfilled で終了したので,子要素の Promise オブジェクトそれぞれについて,on_fulfilled のほうのコールバックを呼びます
  5. コールバックはいずれ resolvereject のどちらかを呼ぶので,それによって子要素のそれぞれで 1. からまたスタートします

このようにして,木の根から葉へと,親の状態に応じたコールバック(on_fulfilled or on_rejected)を実行しながら葉へと向かって非同期処理が走っていくようになっています.

なんとなくイメージは掴めましたでしょうか?もしさらに詳しく知りたければ,es6-promise を clone して各所に console.log を挟み,実際に処理を走らせてみると様子が分かると思います.

まとめ

Vim script で ES6 Promise のライブラリを実装しました.現在はまだプルリク中ですが,いずれ(年内目標で)vital.vimで使えるようにしたいと思っています. メンテナンス性を損なうこと無く,よりユーザが快適に使えるプラグインの作成の役に立てば良いなと思っています.

OCaml でも採用されているレベルベースの多相型型推論とは

言語実装 Advent Calendar 2017 の16日目の記事です. GoCaml という OCaml のサブセットな言語を実装していて,多相型の型推論を実装するために論文を読んだり OCaml の実装をちょっと追ったりしていたので,その知識を整理する意味でこのエントリを書いています.

この記事では OCaml型推論器のベースになっている「レベルベースの多相型型推論アルゴリズム」について概略を直感的に説明しようと思います. 理論的になぜこのアルゴリズムで正しく動作するのかについてはこの記事で概要を把握した上で論文 のほうを読んでいただければ理解が速いと思います.

また,この記事では最もシンプルな単相型のHM型推論については知っている前提で書きます. ご存知でない場合は,

あたりに分かりやすい解説がありますので,そちらを先に読むことをおすすめします.

TL;DR

単相型と多相型

この記事で紹介する多相型型推論の多相的 (polymorphic)というのは単相的(monomorphic)に対してそもそもどう違うのかについて説明します.

単相的な型システムでは全ての値は1つの型を取ります.なので,

let id = fun x -> x in id 42

とすると引数を1つ取りそのまま返す関数 id の型は int -> int になります.なので,別の箇所で id true のように bool 型の値を引数に取ろうとすると,引数の型は int なので bool の値は渡せないとコンパイルエラーになってしまいます.

また,

let id = fun x -> x in ()

のように id が未使用だと引数および戻り値の型が確定しないためコンパイルエラーになってしまいます.これは関数だけでなく option などについても同様で,

let o = None in
o = Some 42; (* o は option int 型 *)
o = Some true; (* エラー,int v.s. bool *)

let o2 = None in ()
(* エラー,o2 の型(option の中身の型)が不明 *)

一方多相型な型システムでは値が任意の型を持つことが許されています.任意の型を取ることができる型変数(型スキームと呼ばれています)は,他の型と区別するために頭にクォートを付けて ('a, 'b, ...)のように書きます.

let id = fun x -> x in (* id の型は 'a -> 'a *)
id 42; (* ここで id の型は int -> int *)
id true; (* ここで id の型は bool -> bool *)

let id2 = fun x -> x in ();
(* id2 の型は 'a -> 'a に確定しているので未使用でも OK *)

let o = None in ()
(* o の型は option 'a *)

単相的な型システムでは id の型は定義した時点では引数と戻り値の型が同じであることしか分からず,後の id の使われ方によって型が確定します. 一方で多相的な型システムでは id を定義した時点で任意の型の引数1つを取りその型の戻り値を返す関数として型が確定します. id 関数は使われる際の引数の型によって int -> intbool -> bool などとして扱うことができますし,定義時に型が確定しているので定義した後に使用しなくてもエラーになりません.

多相型型推論アルゴリズム

単相型HM型推論を多相に拡張したものはざっと調べただけでも3種類ほどあって,

  1. Algorithm W: 最もオーソドックス,型の集合と束縛された型変数の置換表を使って単一化する
  2. Algorithm M: Algorithm W を改善(高速化)したもの.Algorithm W が構文木トップダウンに見て推論していく一方,Algorithm M はボトムアップに推論していく.W の逆なので M
  3. Level-based HM: level という値を導入することで置き換え表を使わず多相型を扱えるようにしたもの.アルゴリズムがシンプルになり実行効率も高い

どれも ML の let 式(変数への代入式)の右辺でのみ値が多相になります.なので let f = fun x -> x in ...f の型は多相的ですが,(fun x -> x) 42fun x -> x の型はそうではありません.

今回は GoCaml で 3. のアルゴリズムを実装したので,その解説をします.

レベルベースの多相型HM型推論アルゴリズム

OCaml型推論のベースにもなっているアルゴリズムです.論文を読んでみてもかっこいい名前とかはついていないので,ここでは単にレベルベースの Hindley-Milner 型推論アルゴリズムと呼んでいます(正式名称ではないです).

詳細については 論文 にあります.論文内ではアルゴリズムが正しいことの証明と,Caml-Light という小さい ML のサブセットを用いた実装例が載っています. 論文内ではレベルのことを rank と呼んでいますが,この記事では OCaml の実装に合わせてレベルと呼んでいます(rank だと Rank N 多相などの他の用語と紛らわしかったのかもしれません).

解説はいいから Real World な実装が読みたいというマッチョな方は OCaml の ctype.ml あたりを読むと良いと思います.

具体例で見てみる(関数 id

難しい話は抜きにして,まずは具体例を見ていきたいと思います.

let id =
    fun x -> x
in
id 42;
id true

まずは解説内で用いる凡例について説明します.

  • 'まだ型が不明である'ことを表す型変数は頭に ? をつけて ?a, ?b のように表します
  • '任意の型を取れる'ことを表す型変数は頭に ' をつけて 'a, 'b のように表します
  • レベルを型変数のあとに括弧を付けて表します.たとえば ?a(1) はレベル1,'b(2) はレベル2であることを表します

基本的には単相型のHM型推論と同じで,コードを上から順に(構文木トップダウンで)見ていきます.

まずレベルは 0 からスタートし,let 式の右辺に入った時にレベルが 1 上がります. そして右辺から戻ってきて次の式に入る時にレベルはもとの値(ここではレベル 0)に戻ります. なので,今回の例でのレベルは次のようになります.

(* level 0 *)
let id =
    (* level 1 *)
    fun x -> x
in
(* level 0 *)
id 42;
id true

それでは型推論の処理を順に見ていきます.

(* level 0 *)
let id =

まずは最初の let 式を見ます.この時点ではまだ代入の右辺の型が分からないので,id の型は ?a(0) となります.

    (* level 1 *)
    fun x -> x

次に右辺に入ります.ここでは関数を1つ定義しています.引数は1つなのでまずは ?b(1) -> ?c(1) という型になり,その戻り値が x そのままであることから ?c?b が代入(単一化; unification)されて fun 式の型は ?b(1) -> ?b(1) となります. ここまで(レベルという値を導入した以外は)単相型のHM型推論と同じです.

let 式の右辺を出た直後で右辺の型の 汎化(Generalization) を行います. 汎化とは,型が不明な型変数(ここでは ?b)のうち,右辺に入る前のレベルより高いレベルの型変数のみを任意の型を取れる型変数 'a に書き換える処理です. ここでは,右辺の型は ?b(1) -> ?b(1) であり,let 式のレベルは 0 ですので,?b(1)'a に書き換わり,右辺の型は 'a -> 'a となります.

これを id の型 ?a(0) に代入(単一化)して,id の型は 'a -> 'a となります.

(* level 0 *)
id 42

id を定義する側が型付けできたので,次は id を使う側を見ていきます.ここでは関数 id に引数 42 を適用しています.

変数が参照されるタイミングで,その変数に対してインスタンス化(Instantiation)という処理が入ります. インスタンス化は汎化と逆の処理で,型の中にある任意の型を取れる型変数 'a を型が不明な型変数 ?c に変換しながら新しい型を生成します. ここでは id の型 'a -> 'a から 'a を置き換えながら新しい型 ?c(0) -> ?c(0) を生成します.

さらに引数に 42 という int の型を与えているので ?cint が代入(単一化)され,この関数適用式における id の型は int -> int に確定し,id 42 の型は int になります.

id true

最後の行についても同様に,'a -> 'a から 'a を置き換えながら新しい型 ?d(0) -> ?d(0) が生成され,引数 true から,この関数適用式における id の型は true -> true となります.

このようにして,任意の型を取れる型変数を含んだ変数 id に複数種類の型を与えて適用した場合でもうまく扱うことができます.

具体例で見てみる(option 型の値)

let o =
    None
in
o = Some 42;
o = Some true

前回同様にレベルをつけていきます.

(* level 0 *)
let o =
    (* level 1 *)
    None
in
(* level 0 *)
o = Some 42;
o = Some true

流れは前回とほぼ同様です.

    None

右辺の型は None 式から option ?b(1)option の値であることは分かるが,中身の型は不明)になります.

これを汎化して,o の型は let 式のレベル 0 より高い ?b(1)'a に置き換えて option 'a となります.

(* level 0 *)
o = Some 42;

o を使う側の流れも大体同じです.

o を参照した時点で o の型のインスタンス化が行われ,この等値式の左辺における o の型は 'a が新しい型変数 ?c(0) に置き換わって option ?c(0) になります.さらに等値式の右辺が option int であることから,ここでの o の型は option int となります.

o = Some true

についても同様にここでの左辺 o の型は option ?d(0) になって,等値式の右辺から ?dbool であると確定します.

もう少し複雑なケース

上記の2つのケースでは簡単すぎて,汎化する際の「レベルより高いレベルの型変数のみを任意の型を表す型変数に置換する」というのがどう効いてくるのか分からないため,もう少し複雑なケースを見てみます.

let make_pair =
    fun x ->
        let f =
            fun y -> (x, y)
        in
        f
in
let pair_with_42 = make_pair 42 in
let pair = pair_with_42 3.14 in
let pair_with_true = make_pair true in
let pair2 = pair_with_true "foo" in

make_pair は引数 xを取って,'引数y を取ってタプル x, y を返す関数' を返す関数です. 例えば,((make_pair 42) true)int * bool な型の値 42, true を生成します. 引数を2つ取ってそのペアを返す関数がカリー化されているとも見られると思います.

ネストが深くなりちょっと複雑に見えますが,まずはレベルを明示してみます. let 式の右辺の中ではレベルが1上がるのでした. let 式が2つネストしているので,レベルは最大で2まで上がるはずです.

(* level 0 *)
let make_pair =
    (* level 1 *)
    fun x ->
        (* level 1 *)
        let f =
            (* level 2 *)
            fun y ->
                (* level 2 *)
                (x, y)
        in
        (* level 1 *)
        f
in
(* level 0 *)
let pair_with_42 =
    (* level 1 *)
    make_pair 42
in
(* level 0 *)
let pair =
    (* level 1 *)
    pair_with_42 3.14
in
(* level 0 *)
let pair_with_true =
    (* level 1 *)
    make_pair true
in
(* level 0 *)
let pair2 =
    (* level 1 *)
    pair_with_true "foo"
in
pair2

一行ずつ見ていきます.

(* level 0 *)
let make_pair =

この時点では makr_pair の型は不明なので,型は ?a(0) となります.右辺に入るのでレベルが上がります.

    (* level 1 *)
    fun x ->

この時点で引数1つであることが分かるので,外側の fun 式の型が ?b(1) -> ?c(1) となります.

        (* level 1 *)
        let f =

ここで2つ目の let 式が現れました.同様に,f の型は ?d(1) となります.ここで右辺に入るとレベルが上がります.

            (* level 2 *)
            fun y ->

さらに1引数の内側の fun 式が現れました.これもこの時点では戻り値型,引数の型ともに不明なので,同様に ?e(2) -> ?f(2) となります.

                (* level 2 *)
                (x, y)

内側の fun 式の body 部分は2要素のタプル生成式になっています.ここで外側の関数の引数と内側の関数の引数をペアにしているので,その型は ?b(1) * ?e(2) となります.

ここから,内側の関数の戻り値型 ?f に代入して 内側の fun 式の型は ?e(2) -> (?b(1) * ?e(2)) となりました.

内側の fun 式を抜けたところで内側の let 式の右辺を抜けるので,右辺の型 ?e(2) -> (?b(1) * ?e(2)) を汎化します.let 式のレベルは 1 ですすから,1 より 大きいレベルの型変数を任意の型を取れる型変数に置き換えます. 結果として,内側の let 式の右辺の型は ?e(2)'a に置き換わり,'a -> (?b(1) * 'a) になります.?b はレベル1なのでまだそこに何の方が来るかは不明なままです.

これによって内側の関数 f の型は ?d に代入(単一化)して 'a -> (?b(1) * 'a) となりました.

        (* level 1 *)
        f

次に外側の fun 式に戻ってきました.ここでは戻り値が f となっています. これによって,外側の fun 式の型は ?b(1) -> ?c(1)?cf の型である 'a -> (?b(1) * 'a) を代入(単一化)し,?b(1) -> 'a -> (?b(1) * 'a) となります.

外側の fun 式を抜けると,ようやく外側の let 式を抜けることができたので,ここで外側の let 式の右辺の型 ?b(1) -> 'a -> (?b(1) * 'a) を汎化します. 外側の let 式のレベルは 0 なので,?b(1) が任意の型を取れる型変数に置き換わり,'b -> 'a -> ('b * 'a) となります.

これを make_pair の型 ?a に代入(単一化)して make_pair の型は 'b -> 'a -> ('b * 'a) となりました.

次に使われている箇所を見ていきます.

(* level 0 *)
let pair_with_42 =
    (* level 1 *)
    make_pair 42
in

let 式の右辺の内側で make_pair を参照しています.変数が参照される箇所ではインスタンス化が起こるのでした. make_pair の型の中の任意の型を取れる型変数を型が不明な型変数に置き換えて,'b -> 'a -> ('b * 'a)?g(1) -> ?h(1) -> (?g(1) * ?h(1)) となります.

ここに引数 42 を適用しているので,適用された make_pair の型は ?g(1)int を代入して int -> ?h(1) -> (int * ?h(1)) となります. よってこの関数適用の結果の型は ?h(1) -> (int * ?h(1)) となります.

ここで let 式を抜けるのでレベル0で ?h(1) が汎化され,pair_with_42 の型が 'c -> (int * 'c) となりました. ちゃんと最初の引数が int であったことが反映された型になっています.

(* level 0 *)
let pair =
    (* level 1 *)
    pair_with_42 3.14
in

次の let 式もほぼ同様ですが,変数参照 pair_with_42 の型は 'c -> (int * 'c)インスタンス化して ?i(1) -> (int * ?i(1)) となり,float 型で関数適用されているので,関数適用の結果は (int * float) となります. ここで let 式を抜けて,型変数は右辺の中になくなったので汎化では特に何も起こらず,pair の型は (int * float) となり正しく型を付けることができました.

これとまったく同様にして,pair_with_truepair2 の型はそれぞれ 'd -> (bool * 'd)(bool * string) となります. よって,多相な関数を返す多相な関数についても呼び出しごとに正しく型が付けられている(引数の型を変えて呼び出しても正しく型を付けられている)ことが分かりました.

そもそもレベルとは何か

今まで特に深くは言及せずレベルを使ってきましたが,つまるところこのレベルとは何を表すのでしょうか.

レベルは実は 'freshness' を表しています.ある型変数 ?a が導入された時に,型変数の数値が大きいほど,その型変数が新しいことを示しています. これと「let 式のレベルより高いレベルの型変数のみを任意の型を表す型変数に置換する」という汎化の条件をあわせることで,let 式よりも外の変数由来の型変数 ?a が,その let 式で汎化されて 'a になることを防ぎ,let 式の中で定義された変数由来の型変数のみを任意の型を取れる型変数として汎化するようにしています.

例えば直前の少し複雑な例で,外側のfun 式の戻り値を f から x = y; f にしてみましょう. xy を比較している(= は等値式)ことから,x と y は同じ型であることが期待されています. 上記の例の x の型 ?bは内側の let 式では汎化されず ?b のまま残っていますので,x = y の時点で y の型 'a を代入(単一化)することができ,x の型は正しく 'a となります. もし ?b が内側の let 式の右辺を抜けた直後の汎化の時点で 'b となってしまったら,x の型が y の型と同じという情報は外側の fun 式の中で反映されなくなってしまうでしょう.

再帰

このアルゴリズムを実装していく上で少しハマったので,ここで紹介しておきます.再帰の場合です.

(* level 0 *)
let rec foo =
    (* level 1 *)
    fun x -> if true then 42 else (foo 10)
in

問題なのは if 式の中で foo再帰的に呼ばれているところです.

順を追って見ていきます.

まず foo の型は ?a(0) として定義され,let の右辺に入ります.

次に fun 式の型を ?b(1) -> ?c(1) とし,関数の本体に入ります.

ここで fooint 1引数の関数であることが判明するので foo の型 ?a(0)int -> ?d(1) となります.

さらに if 式の then 節が int なことから,foo の型は int -> int となり,fun 式の型は ?b(1) -> int となります.

最後に let 式を抜け,汎化されて 'a -> int となりますが,すでに foo の式は int -> int だと判明しているので,単一化により fooint -> int になってしまいます.

つまり,foo は一見 'a -> int となっても良さそうに見えますが,実際は再帰していて引数の型が関数本体内で判明している場合は,その関数は多相になりません. なので,foo 3.14 のように呼び出そうとするとコンパイルエラーになります.

OCaml では let rec foo: 'a -> int のように型を明示してやることでこれを回避できるようです.

エッジケースをカバーするためのレベルの調整

ここまで説明したアルゴリズムで概ねうまく動きますが,実はうまく動かないエッジケースがあり,それを解消するために型変数のレベルを調節する処理が単一化をする際の occur check の中にあります. occur check は単一化しようしている2つの型のうち一方が他方に含まれていないかをチェックする処理ですが,チェックする2つの型が両方とも型変数だった場合に特別な処理を行います.

具体的には,もし右辺側の型変数のレベルのほうが左辺側の型変数より大きい時,右辺側のレベルを左辺側のレベルに合わせます. なので,

e1 = e2
(* e1 の型は ?a(1) -> int *)
(* e2 の型は ?b(2) -> int *)

という等値式があった場合,e1e2 の型は同じであるはずなので単一化を行いますが,この時 e2 の型は ?b(1) -> int に書き換わります.これによって汎化が正しく行われます.

型推論が実装できた次に待っているもの

ここまででレベルベースの多相型型推論は終わりです.しかし,型推論を実装しただけでは多相型は実装できません. 実際には任意の型を取れる型の値をどうアセンブラに落とすかや,後から変更できる値の扱いをどうするかなどの問題が残っています. 本当はそこまで書きたかったのですが,実装が終わっていないので概略のみを書きます.

汎化された値のコード生成

let f = fun x -> x in f 10; f true

というコードがあった時,x の値は実際はどのようなアセンブリコードに落とせば良いでしょうか.やり方は大きく3つあります.

1. 任意の型の値を1ワードで表現する

任意の型の値が1ワード(数値は64bit整数や浮動小数点数,それ以外はポインタ)とすれば,f は単に1ワードの引数を取る関数としてコード生成できます.値の型によって処理を分岐する必要があるので,実行時にオーバーヘッドが発生します.

2. 'a が取りうる型ごとに型を具体化してしまう

let f_int = fun (x:int) -> x in
let f_bool = fun (x:bool) -> x in
f_int 10;
f_bool true

のように,取りうる型ごとに別の関数を定義してしまいます.バイナリサイズが大きくなったり分割コンパイルが困難になりますが,実行時に 1. のようなオーバーヘッドが発生しません.

上記の 1. については型クラスを定義できるようにし,引数が実装している型クラスの処理に対応する辞書を f に別途渡すことでオーバーヘッドを低減する実装もあります. Haskell などで採用されている方式です.足し算ができることを表す型クラス Add があって下記のように f を定義したとき,

let f = fun (x: Add) -> x + x in f 10; f 3.14

コード生成では intfloatAdd 実装(足し算処理)を辞書として f の隠し引数に渡してやり,それを関数内で使って + の処理を行います.

id:mod_poppo さんの指摘に従って一部修正しました)

値制約

例で説明したケースでは問題ありませんでしたが,実は多相型型推論は変数が可変な場合にうまく行きません.

(* 空の配列を可変な変数 a に束縛 *)
let a = ref [| |] in
(* true を要素に持つリストを代入し直す *)
a := [| true |];
(* 最初の要素は true であるはずなのに 42 と足せてしまう *)
42 + a.(0)

今まで説明してきたアルゴリズムをそのまま適用すると,a の型は array 'a となり,3行目では aインスタンス化が行われて要素アクセス a.(0)a の型は array int となり,bool の配列にも関わらず,要素を42と足せてしまいます.これでは型安全ではなくなってしまいます.

これを避けるために,値制約(value restriction)を導入します.let 式の右辺に特定の式が来た場合は汎化を行わないという制限を加えることで,これを回避します. 上記の例では ref があるときは汎化を行わず,aarray ?a になって後の代入式で array bool が確定するので a.(0) の型は bool となり,無事 42 と足すところでエラーになります.

まとめ

レベルベースな多相型型推論アルゴリズムについて順を追って詳細に説明してみました. 初めてこのアルゴリズムを見る人にも理解しやすいようにしたつもりです. 自作言語などで単相型の型システムから多相型に拡張する際などに参考にしていただけると幸いです.

Vim 進捗旅行

木曜日午後〜日曜日午前中の4日間,Vim コミュニティつながりの知人と旅館に泊まり込んでもくもく作業する合宿的な旅行に行ってきました.

f:id:rhysd:20171127025245p:plain

当日の様子や旅館の便利情報についてはすでにブログ記事にまとめられているのでそちらを読んでいただいて,この記事内では僕がやった作業内容を備忘録的に書いておきます.

今回やったこと

neovim-componentNyaoVimPolymer v2 対応

今回の一番でかい成果はウェブアプリフレームワーク Polymer v1 を使って書いていたアプリを v2 にアップデートしたことでした.

NyaoVim という Neovim のフロントエンドなデスクトップアプリを Polymer と Electron を使ってつくっています.Neovim フロントエンドというのは,裏でヘッドレスな Neovim を起動して標準入出力経由の RPC で描画情報やユーザのキー入力などをやりとりすることで Neovim の表面部分を実装したものです.NyaoVim では Electron をフレームワークとして使うことで Neovim エディタのスクリーン部分を WebComponents のカスタム要素として描画することで,元来 Vim にはなかった,ユーザが自由に UI を拡張できる仕組みをウェブの技術を用いて提供します.

Web Components と Electron でつくる Neovim フロントエンドの未来 github.com

このアプリは Polymer という WebComponents をベースにしデータバインディングを乗っけた薄いコンポーネントライブラリを使って実装しています.ユーザは設定を <template> 要素と JavaScript を使って HTML ファイル(nyaovimrc.html)で書きます.<template> を使うことで自由にカスタム要素で作られた UI プラグインを配置でき,挙動を Polymer のデータバインディングを使ってカスタム要素の属性を使ってカスタマイズできます.NyaoVim を作り始めた当初は Polymer v1.3 ぐらいで,それ以降も v1 を使い続けていましたが,さすがにそろそろ v2 に移行すべきだと思って半年ぐらい経ってしまったので良い加減やることにしました.

Polymer v1 は WebComponents v0 時代につくられたということもあり,Polymer v2 では WebComponents v1 の仕様への乗り換えが行われました.それもあってか,カスタム要素定義の仕方やライフサイクルの扱いが大きく変わっています(見た感じデータバインディングについては大きくは変更なし). 公式にある Polymer 2.0 アップグレードガイド を読みつつ下記の手順で進めました.

  1. レガシースタイルのまま v1 から v2 に乗り換える
  2. ES2015 class を使った新しいスタイルに乗り換える
  3. 壊れた部分やテストを直す
  4. 関連 UI プラグインを Polymer v2 向けに修正する

最初の時点でまずは依存する Polymer のバージョンを v2 に上げます.Polymer v2 は移行のために v1 のレガシーなスタイルもある程度対応しているので,まずはバージョンだけ上げてアプリを起動してみてうまく動いていないことを確認し,修正していきます.

Polymer v1 までは外からもカスタム要素の中身が見えるのがデフォルトになっていたため,カスタム要素を構成する要素を取るのに雑に document.querySelector を使ってしまっていたのですが,v2 からは完全に見えなくなる(document.querySelector で要素を取ろうとしても null になる)ので,Polymer の APIthis.$ など)を使って要素を取ってくるように正しました. また attached コールバックの発火タイミングが変わっていて DOM の要素のサイズが取れなかった(NyaoVim では Neovim 起動時にエディタのサイズ(行数と桁数)を指定するためにフォントサイズと要素サイズから計算する必要がある)ので,Polymer.RenderStatus.beforeNextRender を使って,要素の first paint(次の request animation frame 発火直後)まで処理を遅延するようにしました.

Polymer({
    is: 'x-foo',
    // ...
    attached: function() {
        // <x-foo> が DOM に挿入された直後に実行される
        Polymer.RenderStatus.beforeNextRender(this, function() {
            // <x-foo> がページ内に描画された直後に実行される
        });
    }
});

次に Polymer v2 からは独自のファクトリ関数ではなく WebComponents v1 のカスタム要素のように ES2015 class を使って要素を定義することができるので,それを使ってレガシースタイルの要素を class による実装に移行します.

class XFoo extends Polymer.Element {
    static get is() { return 'x-foo'; }
    static get properties() {
        return {...};
    }
}
customElements.define(XFoo.is, XFoo);

Polymer v2 は標準の API を直接使えるところはなるべく使うという方針なので,カスタム要素の定義は標準の customElements.define を使います.また,v1 のレガシースタイルで用意されていた attached, connecteddisconnected といったライフサイクル系のコールバックは標準の attachedCallbackconnectedCallbackdisconnectedCallbback などのカスタム要素標準のコールバックを使って書き換えていきます.また,ユーザがデータバインディング経由でカスタム要素の属性の値を変更した場合は同様に標準の attributeChangedCallback を使って知ることができます.NyaoVim は TypeScript で書いていて,DefinitelyTyped の型定義は v1 のもので古かったのですが, v2 向けの型定義を書いている人を発見したので拝借して使わせてもらいました.

最後に,これらの変更によって壊れたテストや NyaoVim の UI を拡張するためのプラグインmarkdown プレビューやツールチップなど)の修正を行いました.E2E テストでカスタム要素の中を直接覗いていたのが v2 で不可視になったことによりテストできなくなったため,一番外側のカスタム要素に生やしてあったプロパティを経由するようにしたりなどの変更をしました.

まだできていないこと:

  • React の DOM を ShadowRoot を貼り付けたカスタム要素下の子要素にマウントすると React コンポーネント <div onClick={...}\> などのコールバックがなぜか発火しない
  • Web Component の中身が見えなくなったので,E2E テストでコンポーネントの中身をテストできなくなってしまった.web-component-tester あたりを使えば良さそう

UIプラグインの中に React で動的な処理を書いたアプリをカスタム要素で wrap したものがあったのですが,onClick が発火しなくなってしまい使えなくなってしまいました.誰か何か知っていたら教えてほしい…

clever-f.vim のテストを themis.vim に移行しテストカバレッジを取れるようにした

clever-f.vimVimfマッピングを拡張するプラグインで,使い続けているプラグインの1つです.

最近 covimerage という Vim の profilng 機能による実行ログを利用して Vim script のカバレッジを取るツールが(一部で)話題になっていて,@haya14busaさんのおかげで,どうやら結構簡単に導入できそうだということで導入してみました.

clever-f.vim には50弱のテストケースがあって,今までは vim-vspec を使ってテストを書いていたのですが,どうやら vim-vspec はテスト前 (bootstrap.vim)に特定の処理を挟むことができないらしいので,themis.vim を使って書き直しました.:profile でプロファイルを取る処理を入れる必要があります.

themis.vim:Describe:It を使った spec スタイルをサポートしているのでほぼ問題なく全てのテストを移行できました.

次に Travis CI を使って LinuxmacOScovimerage をインストールし,.themisrc:profile を使ってテスト中の profile を取り,covimerage を使ってカバレッジレポートを生成して codecov にアップロードする処理を入れます.

Dashboard ⋅ rhysd/clever-f.vim f:id:rhysd:20171127025717p:plain

このように Vim プラグインのテストカバレッジを取ることができました.今後はテストできない箇所のテストをちまちま追加していきたいと思っています.

1点うまくいかなかったのは,clever-f.vimmigemo 対応をする部分のコード がなぜか「UTF-8 でデコードするには不正なシーケンスが含まれている」というエラーで covimerage ではうまくパースできず外さざるをえなかった点です.

もくもく合宿の所感

タスクを詰め込みすぎない(どうせ全部できない)

3泊4日ということもあり,タスクを詰め込みがちですが,詰め込んでもどうせできないのでその日に必ずこれをやるというのを設定しておくのが良さそうでした.もくもく会は独りで集中して作業するのに比べると作業速度は落ちるので,あまり期待しすぎないのが大事な気がしました. 自分のリポジトリに来た issue 対応を合間にやったり,とあるアプリに初めてメールで脆弱性レポートが送られてきたり,他のメンバーの Splatoon2 プレイを見ていたのもあって,メインの作業は思ったほど進みませんでした.

ただその分,他のメンバーが踏んだ興味深いバグを一緒に追ってみたり,手元で温めているアイデアを他メンバーと議論・相談したり,分からないところのヘルプを頼んだりできて有意義だったと思います.(i.e. autoload 内のスクリプト:sourceruntime で読んではいけないことを知った)

2泊3日がベストっぽい

実は今年の4月頃にも一度同じところに1泊2日で行ったのですが,1泊2日は短すぎたので今回は3泊4日に挑戦という流れでした.3泊4日はしっかり時間が取れて1泊2日より良かったですが,若干だれてしまう感じだったので2泊3日が自分の中ではベストかなぁと思いました.

尊師スタイル

今回は HHKB を持っていったので,内蔵キーボードを Karabiner で無効にして尊師スタイルしてみたところ,(MacBook Pro 2016 late の残念なキーボードに比べて)はるかに打ちやすくて最高でした.これからもくもく会はこのスタイルで行きます.しかしセパレート型の持ち運び向けキーボードがベストっぽい…

旅行中のツイートハイライト