型無しラムダ計算学習用ステップ評価器 Mogul を作っている話 - Qiita

どうも、趣味で関数型言語をやっている者です。 これは 言語実装 Advent Calendar の2日目の記事です。 導入 みなさま ラムダ計算 をご存知でしょうか。 ラムダ計算はある種の関数型プログラミング言語の体系で、変数と関数、そして関数適用というミニマルな構成要素だけでチューリング完全な表現力を持っています。 今回はラムダ計算の中でも特に単純な 型無しラムダ計算 に着想を得て、型無しラムダ計算のステップ評価器を作った(作っている)話について書きます。 既存のモデルへの不満 型無しラムダ計算を具体的な実装に落としたものとしては、有名なところで Unlambda や Lazy_K などがあります。 どちらも SKI コンビネーター理論 に基づいており、 s, k, i という たった3つの組み込み関数でプログラムを記述することが可能 1 です。 かく言う私も Unlambda から型無

[todays_mitsui]

どうも、趣味で関数型言語をやっている者です。やっっと書きました。