ラムダ計算入門

この記事は OPENLOGI Advent Calendar 2023 20日目の記事です。 ラムダ計算 (lambda calculus) は関数型プログラミング言語の基礎となる計算モデルです。計算モデルというと難しそうですが、本稿を読む上では「超シンプルなプログラミング言語」くらいに思ってもらえれば十分です。ラムダ計算にはいろいろな拡張や亜種がありますが、ここでは最も純粋なラムダ計算を扱います。このラムダ計算には変数と無名関数と関数の呼び出ししか構成要素がありません。恐るべきことに、数値などのリテラルや四則演算、制御構文などの普通のプログラミング言語が兼ね備えているような機能は直接的には備わっていません。しかし、工夫すると関数だけで全てを表現することができ、その計算能力はチューリングマシン完全であることが知られています。今日はこの面白さを伝えたいと思います。パズルや頭の体操みたいなノリ

[htkymtks]

ラムダ計算についての解説。分かりやすそう〜