Y Combinator in Vim

つい最近 Y Combinator なるものの存在を知った。理解を深めるために、試しに自分で書いてみることにした。…Vimで。

無名関数

そもそもVimでは無名関数は使えないので正確には Y Combinator とは呼べないのかもしれないけれど、まあそれっぽい動きをするもの、と言うことで。

関数オブジェクト

Vimでは関数を第一級オブジェクトとして使用するためには function() などで関数名を指定して作成する必要がある。
が、ここでは動的に関数を作りたい。幸いVimには辞書上に関数を定義できる(:h numbered-function)ので、関数は以下のように作ることにする。

let c = {}
function! c.call()
  ...
endfunction

ここでcallと言う名前を固定にして、cを関数オブジェクトとして扱うことにする。つまり関数を呼ぶ場合は c.call() とする必要がある。cと言う名前が付いているので無名関数じゃない。

スコープ

Vimは関数内で関数を定義することもできる。が、本当に定義できるだけで、外側の関数と内側の関数の間には何の関係もない。つまり、内側の関数から外側の関数の変数にアクセスできない。
これは非常に困る。

そこで、関数オブジェクトに上位スコープの関数オブジェクトを入れておいて、それを順次参照する関数を用意することにした。
で、そのために作った関数オブジェクトファクトリが以下。

function! Callable(...)
  let callable = {}
  function! callable.get(name)
    let s = self
    while !has_key(s, a:name)
      if !has_key(s, 'super')
        return
      endif
      let s = s.super
    endwhile
    return s[a:name]
  endfunction

  for i in a:000
    if type(i) == type({})
      let callable.super = extend(get(callable, 'super', {}), deepcopy(i))
    endif
  endfor
  return callable
endfunction

get()しかないけど、今回はget()しか使わないのでset()は省略。
Callable() の引数に上位スコープの変数が入った辞書を渡す。
つまり、関数を作るには以下のようにする。

let c = Callable({'var' : 'val'})
function! c.call()
  let var = self.get('var') " => 'val'
endfunction

作った関数内で self.get(variable_name) すると上位スコープの変数が参照できる。

Y Combinator

材料がそろったので実際に Y Combinator を書いてみる。
今まで見てきてわかるように、Vimでは引数の中で直接関数オブジェクトを定義するとか器用なまねはできないので、最初に作った関数をコピーして使ってる。
なんかもう Y Combinator の定義が怪しい気がするが、本人わかってないのであまり気にしないことにする。

function! Y(f)
  let c = Callable(a:)
  function! c.call(g)
    let c = Callable(a:, self)
    function! c.call(m)
      return self.get('f').call(self.get('g').call(self.get('g'))).call(a:m)
    endfunction
    return c
  endfunction
  return c.call(deepcopy(c))
endfunction

こんな感じでたぶん合ってるはず。

実際に使ってみる

よくある階乗の例をやってみる。

function! s:fact()
  let c = Callable()
  function! c.call(fact)
    let c = Callable(a:)
    function! c.call(n)
      return a:n <= 1 ? 1 : self.get('fact').call(a:n - 1) * a:n
    endfunction
    return c
  endfunction
  return Y(c)
endfunction

echo s:fact().call(10)
" => 3628800

うん。ちゃんと動いてるようだ。ついでにフィボナッチもやってみる。まあ対して変わらんけれども。

function! s:fib()
  let c = Callable()
  function! c.call(fib)
    let c = Callable(a:)
    function! c.call(n)
      return a:n <= 1 ? a:n : self.get('fib').call(a:n - 1) + self.get('fib').call(a:n - 2)
    endfunction
    return c
  endfunction
  return Y(c)
endfunction

echo s:fib().call(10)
" => 55

問題なさそう。

まとめ

またつまらぬものを書いてしまった…。