日々の流転

λ. コンビネータ

「コンビネーター計算は、λ計算と同等のことを変数やλ抽象を持たず、ただ適用だけをもつシステムで実現しようとしたものであって、λ計算とは別物」というのは同意。

ただ、(コンビネータ計算ではなく)ラムダ計算の文脈では、単に「自由変数を含まないλ式」という意味で結構広く使われているように思いますし、私もそのように理解してました。本来は誤用だったのかも知れませんが、すっかり定着してしまっているように思います。

調べてみると、Simon Peyton Jones の The Implementation of Functional Programming Languages の p.224 には「A combinator is a lambda expression which contains no occurences of a free variable [Barendregt, 1984]」と書いてあります。ちょっと探した限りではバーレンドレヒト以前でこの意味で使っているのは見当たらなかったので、この用法はやっぱりバーレンドレヒトが起源なのかも。それはそれでちょっと面白いなぁ。