Scalaで型レベルのラムダ計算 - 貳佰伍拾陸夜日記新しい言語をさわったらとりあえずラムダ計算のインタプリタを実装するよね! Scalaでふつうにラムダ計算のインタプリタを実装するのはあまりに簡単*1なので, 型レベルでやってみた. まじめな話をしておくと, C++のテンプレートがチューリング完全なのは有名な話だけど, Scalaではどうなのか気になった. 以前C++のテンプレートでラムダ計算のインタプリタを実装したのと同様のことができるか思考実験してみると, だいたいできそうに思えたのでやってみた. できたもの 例 import lambda._ case class Equals[A >: B <: B, B]() // 型レベルの同値性チェック用 type S = x ->: y ->: z ->: ( x @@ z @@ (y @@ z) ) type K = x ->: y ->: x type result = ( S @@ K
