Goのコマンドラインツールをセルフアップデートするためのライブラリつくった

突然ですが，Goでコマンドラインツールを書く時，ツールの配布はどうしているでしょうか？

1. go get でインストールできるようにする
2. GitHub 上にリリースして，ダウンロードして使ってもらう
3. システムのパッケージマネージャ（Homebrew など）を使う

などがメジャーかと思います．

ただ，これらの選択肢はどれも問題があります．

go get -u は常にリポジトリの HEAD をインストールしてしまうため，ユーザがインストールしたタイミングに依存したバイナリができてしまいます．これを避けるには dev ブランチを切ってそっちで開発する必要がありますが，Go のツールはそうなってないものが多く，どのタイミングで go get -u したら良いかユーザには容易に判断できません．また，仮に dev ブランチ運用したとしても依存ライブラリの更新のタイミングは制御できず，vendoring などを使う必要があります．

GitHub 上でのリリースは各バージョンごとにテストが通ったものをリリースノート付きでリリースできますが，ユーザが自発的にアップデートを確認し，手でバイナリをダウンロードしてくる必要があります．

システムのパッケージマネージャは上記の問題を解決してくれますが，プラットフォームに依存し，アップデート時に余計な手間も出ます（例えば Homebrew なら homebrew-core へのプルリクなど）．

Go は全てを静的リンクした1つのバイナリを簡単にクロスコンパイルできる利点を持っているため，これをうまく使えないかと思い，go-github-selfupdateをつくりました．この記事ではその紹介をします．

github.com

go-github-selfupdate とは

go-github-selfupdate とは，GitHub 上にある最新のリリースを検知して，自分自身のバージョンよりも高ければ自動で自分自身のバイナリを更新する（セルフアップデート）機能を提供するためのライブラリです．

以下のような流れでセルフアップデートを行います．

1. GitHub の Releases API を使い，プレリリースでない最新のリリースを Git のタグ名から判定してリリース物の URL を取得
2. リリース物をダウンロードし，zip や gzip，tar.gz などの圧縮形式・アーカイブ形式をファイル名から判定し，自動で展開・解凍して目的のバイナリを引っ張ってくる
3. inconshreveable/go-update を使って自身の実行ファイルをダウンロードした新しいものに差し替える

これによって，GitHub で公開している最新の安定版バイナリにそのコマンドから自動検知・更新することができます．

Travis CI や AppVeyor を使って Linux, Windows, macOS でテストし，正常系だけでなく異常系もテストしています（カバレッジ90%以上）． また，inconshreveable/go-update を使っているので，実行ファイルの差し替えに失敗した場合には自動で元の実行ファイルにロールバックしてくれます． zip，gzip，tar.gz の解凍・展開には Go の標準ライブラリを使っています．

使い方

お試し CLI

テストにも使っているお試しの CLI があるので，下記のように試せます．これはリリースページのバイナリにセルフアップデートする（v1.2.3 → v1.2.4）例です．

$ go get -u github.com/rhysd/go-github-selfupdate/tree/master/cmd/selfupdate-example

$ # バージョンを確認
$ selfupdate-example -version
v1.2.3

$ # セルフアップデートを実行
$ selfupdate-example -selfupdate

$ # アップデートされている
$ selfupdate-example -version
v1.2.4

$ # もちろん再度実行してもすでに最新なので何も起きない
$ selfupdate-example -selfupdate
$ selfupdate-example -version
v1.2.4

コード例

セルフアップデートの各段階の処理を関数として公開していますが，一番簡単なのは selfupdate.UpdateSelf() を使うことです．

import (
    "log"
    "github.com/blang/semver"
    "github.com/rhysd/go-github-selfupdate/selfupdate"
)

const version = "1.2.3"

func doSelfUpdate() {
    v := semver.MustParse(version)
    latest, err := selfupdate.UpdateSelf(v, "owner/repo")
    if err != nil {
        log.Println("Binary update failed:", err)
        return
    }
    if latest.Version.Equals(v) {
        // latest version is the same as current version. It means current binary is up to date.
        log.Println("Current binary is the latest version", version)
    } else {
        log.Println("Successfully updated to version", latest.Version)
        log.Println("Release note:\n", latest.ReleaseNotes)
    }
}

（後ほど説明しますが）このライブラリではバージョンの大小比較のためにセマンティックバージョニングを前提としています． UpdateSelf() はツールの現在のバージョンと，ツールがホストされているリポジトリの情報（owner/repo）を受け取り，更新した結果のリリースを表す構造体（selfupdate.Release）とエラーを返します．

エラーはダウンロードしてきたファイルが破損していた場合など，セルフアップデートが実行できなかった場合に返されます．

現在のツールのバージョンが最新だった場合はエラーではないので，latestのVersionフィールドに現在のバージョンと同じ値が返されます． なので，アップデート後のバージョンと今のバージョンを比較する（latest.Version.Equals(v)）ことで実行ファイルの差し替えが行われたかを知ることができます．latest にはバージョンの他にリリースノートやリリースページの URL なども含まれるため，必要な場合は適宜利用できます．

この（ユーザへの出力を含めて）14行だけで実行ファイルをアップデートする仕組みを組み込むことができました．

次にもう少し複雑な例を出してみます． バージョンアップデート前にユーザに「このバージョンにアップデートするけど良い？」と確認を取りたいとします．

import (
    "bufio"
    "github.com/blang/semver"
    "github.com/rhysd/go-github-selfupdate/selfupdate"
    "log"
    "os"
)

const version = "1.2.3"

func confirmAndSelfUpdate() {
    latest, found, err := selfupdate.DetectLatest("owner/repo")
    if err != nil {
        log.Println("Error occurred while detecting version:", err)
        return
    }

    v := semver.MustParse(version)
    if !found || latest.Version.Equals(v) {
        log.Println("Current version is the latest")
        return
    }

    fmt.Print("Do you want to update to", latest.Version, "? (y/n): ")
    input, err := bufio.NewReader(os.Stdin).ReadString('\n')
    if err != nil || (input != "y\n" && input != "n\n") {
        log.Println("Invalid input")
        return
    }
    if input == "n\n" {
        return
    }

    if err := selfupdate.UpdateTo(latest.AssetURL, os.Args[0]); err != nil {
        log.Println("Error occurred while updating binary:", err)
        return
    }
    log.Println("Successfully updated to version", latest.Version)
}

少々長いですが，全体の流れとしては，UpdateSelf() の中でやっている処理をバラして，

1. selfupdate.DetectLatest() で GitHub 上での最新のリリースを検知してアップデートの必要があるかチェック
2. ユーザに y/n で確認するプロンプトを出す
3. selfupdate.UpdateTo() で実行ファイルをダウンロード，解凍・展開，置き換えする

というものです．特に難しい部分は無いはずです．リリースが無い場合は異常系では無いので，selfupdate.DetectLatest() はリリースがあったかどうかとエラーを別に返すようにしています．

リリース物の名前付けルール

どのバイナリがどの環境向けのものかを判別するために，下記のような名前付けでリリース物を配布しているという前提で実装しています．

{cmd}_{goos}_{goarch}{.ext}

{cmd} はコマンドラインツールの名前です．この中に _ を含んでいても構いません． {goos} は OS の種類（runtime.GOOS），{goarch} はアーキタイプ（runtime.GOARCH）です．{.ext} はファイルの拡張子で，何もなし（圧縮なし），.zip，.gz，.tar.gz のいずれかで，対応する圧縮・アーカイブが施されているものとします．

また，セパレータには _ の代わりに - が使え，Windows 限定で .exe.zip のように .exe が付いても大丈夫なようになっています（実行ファイルをそのまま圧縮しても良いように）．

なので，foo-bar をコマンド名とすると下記のようなファイルはリリース物として認識されます．

• foo-bar_linux_amd64
• foo-bar_linux_amd64.zip
• foo-bar_linux_amd64.tar.gz
• foo-bar_linux_amd64.gz
• foo-bar-linux-amd64.tar.gz

リリース名（Git のタグ名）の名前付けルール

go-github-selfupdateは Git のタグを見てそのリリースのバージョンを判定します（リリースタイトルではないので注意）．

タグ名は正規表現で言うと \d+\.\d+\.\d+ を含んでいる必要があり，それより手前の文字列は削除されます．なので，v1.2.3やver1.2.3，release-1.2.3などは全てバージョン 1.2.3 として認識されます．

この命名規則に合致しないもの（例えば nightly など）や，プレリリースに指定されているものなどは単に無視されます．

リリース物の構造

まとめると下記のような構造でリリースすれば正しくgo-github-selfupdateで認識できます．

コマンド名を foo-bar とすると，一例としてリリースは下記のようになります．

• v1.2.4
  • foo-bar_linux_amd64.tar.gz
    • foo-bar
  • foo-bar_darwin_amd64.tar.gz
    • foo-bar
  • foo-bar_windows_amd64.exe.zip
    • foo-bar.exe
  • ...（他のプラットフォーム向けのバイナリ）
• v1.2.3
  • foo-bar_linux_amd64.tar.gz
    • foo-bar
  • foo-bar_darwin_amd64.tar.gz
    • foo-bar
  • foo-bar_windows_amd64.exe.zip
    • foo-bar.exe
  • ...（他のプラットフォーム向けのバイナリ）

難しく考えなくても，gox でクロスビルドしてアーカイブし，ghrでリリースしたりしていれば大体この構造になっているのではないかと思います．

デバッグする

go-github-selfupdate内では（デフォルトで無効な）ログを仕込んでありますので，ツールのデバッグ時には下記のようにしてログを有効にすることで内部でどういう処理が行われているかを標準エラー出力に表示することができます．

selfupdate.EnableLog()

適用例

手前味噌ですが，いくつか自分のツールにはすでに組み込んでみています．

• dot-github: .github ディレクトリのジェネレータ
• dotfiles: dotfiles のシンボリックリンクの管理ツール
• github-clone-all: GitHub からリポジトリをクローンしてくるツール

おまけ CLI ツール

go-github-selfupdateを使い，いくつか簡単なコマンドラインツールも作成しました．

• detect-latest-release: 引数に与えられたリポジトリの最新のリリースを検知するコマンド
• go-get-release: go get のような Go のコマンドをインストールするツール．go get と違い GitHub の最新のリリース物をダウンロードしてきて $GOPATH/bin に配置する

例えば下記のように ghr の安定版をインストールしたり，

$ go-get-release github.com/tcnksm/ghr
Command was updated to the latest version 0.5.4: /Users/rhysd/.go/bin/ghr

下記のように dot-github の最新バージョン（やリリースノートなど）を知ったりすることができます．

$ detect-latest-release rhysd/dot-github
1.3.0

go-github-selfupdateを下地として使っているので，飽くまで前章で解説した名前付けルールに従っているものでしか使えません（それ以外ではリリースが検知できないと思います）．

tj/go-updateとの違い

実はすでに同じ目的のライブラリとして tj/go-update がありますが，下記の点が違います

tj/go-update は

• Windows をサポートしていない
• バージョンのプレフィックスは v のみ許可
• プレリリースかどうかを見ない
• テストが少ない（正常系の1ケースのみ）
• GitHub だけでなく Apex というリリース置き場をサポートしている

まとめ

GitHub 上にある最新のリリースを検知して，自分自身のバージョンよりも高ければ自動で自分自身のバイナリを更新する（セルフアップデート）機能を提供するためのライブラリ，go-github-selfupdateを作成しました．これによって，配布者にとってはリリースの配布がより楽になり，ユーザにとってはリリースされた安定版に手軽にアップデートできるという利点があるのではないかと思います．

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);
});

のように，本来実行される順序でコードを書くことができ（fetch → writeFile），エラー処理も .catch メソッドによって分離できます．

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

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

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

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

ということで，JavaScript で使われているアイデア（Promise）を Vim にポーティングしました．

使い方

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

:Vitalize で Async.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:sh と Promise.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.vim の Web.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:exception で reject すると例外の発生位置が取れなくなってしまいます．そのため，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/.catch と JavaScript 版の .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より引用）

例えば，次の処理を考えてみましょう．

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. コールバックはいずれ resolve か reject のどちらかを呼ぶので，それによって子要素のそれぞれで 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型推論については知っている前提で書きます． ご存知でない場合は，

• 住井先生の MinCaml の型推論実装の解説
• 五十嵐先生の型推論の解説
• 20日目の@uint256_t さんの記事「ヒトでもわかる型推論」

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

TL;DR

• 論文： EXTENSION OF ML TYPE SYSTEM WITH A SORTED EQUATIONAL THEORY ON TYPES (Didier Rémy 1992)
• 実装： https://github.com/rhysd/gocaml/blob/let-polymorphism/sema/infer.go

単相型と多相型

この記事で紹介する多相型型推論の多相的 (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 -> int や bool -> 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) 42 の fun 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 の型を与えているので ?c に int が代入（単一化）され，この関数適用式における 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) になって，等値式の右辺から ?d は bool であると確定します．

もう少し複雑なケース

上記の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) の ?c に f の型である '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_true と pair2 の型はそれぞれ 'd -> (bool * 'd) と (bool * string) となります． よって，多相な関数を返す多相な関数についても呼び出しごとに正しく型が付けられている（引数の型を変えて呼び出しても正しく型を付けられている）ことが分かりました．

そもそもレベルとは何か

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

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

例えば直前の少し複雑な例で，外側のfun 式の戻り値を f から x = y; f にしてみましょう． x と y を比較している（= は等値式）ことから，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) とし，関数の本体に入ります．

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

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

最後に let 式を抜け，汎化されて 'a -> int となりますが，すでに foo の式は int -> int だと判明しているので，単一化により foo は int -> 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 *)

という等値式があった場合，e1 と e2 の型は同じであるはずなので単一化を行いますが，この時 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

コード生成では int や float の Add 実装（足し算処理）を辞書として 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 があるときは汎化を行わず，a は array ?a になって後の代入式で array bool が確定するので a.(0) の型は bool となり，無事 42 と足すところでエラーになります．

まとめ

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