ラムダ計算は, 多くのプログラミング言語, とくに関数型言語の原形になっています. ラムダ計算について理解しておくことは, 多くのプログラミング言語の習得に役立つでしょう. ラムダ計算はチューリング完全で, 計算能力としてはふつうのプログラミング言語と同じです. ラムダ計算で計算を書く訓練をしておくことは, 任意の計算を関数のみを使って(他の制御構文を用いずに)書くときに役立ちます. ふつうに書いたら煩雑な処理を, 関数型言語のやり方で書くとすっきりすることが多々あり, コードを自由自在に書くためには必須の考え方と言えるでしょう. 項 ラムダ計算の式を項(term)と言います. 項は変数, 抽象, 適用のいずれかです. 変数 変数(variable)はふつう1文字で書きます. 変数には関数内の束縛変数(bound variable)か自由変数(free variable)かという区別があり
俺が如何なる考え方にてSKIコンビネータにてConsを作ることができたかを記録しておく。 もっと別の経路でやれば短くなるのかもしれないが。 この記事はS(KS)KとかS(K(SI))Kとかが、見た瞬間に何なのかわかるくらいの人向けなので、わからない人は別のところで勉強してからが良いかと。 まあ知らなくても見てればわかる人にはわかるだろうけど。 目的物 今回作るのは、Cons。 (Cons a b) f → f a b となるように作る。 こうすることで Car=True=K , Cdr=False=KI=SK と表記できるのは周知の事実である。 また、これを求める途中で(Cons a b)全体(つまりcar部とcdr部が埋め込まれた状態)の表記も求めることになる。 前提 基本的にS,K,Iは大文字、それ以外の変数には小文字アルファベットをあてる。 また、頻出のコンビネータとして以下のものに
ことり: ねぇ、この前ね、λ式はみんなこんな感じの関数“S”と“K”だけで表現できるって聞いたんだけど、本当?
このページは、Combinatory Logic Tutorialの翻訳です。 http://homepages.nyu.edu/~cb125/Lambda/ski.html 基本的に超訳です。 訳の正しさは全く保証されません。 訳のおかしい部分は多数あります。 翻訳元サイトの許可を取ったりはしていません。 無認可です。 訳者による前書きと感想コンビネータ論理チュートリアル 訳者による前書きと感想 訳してみたものの、ちょっと、たったこれだけの説明では、はじめてコンビネータ論理を知った人が読んで充分に理解できるとは思えない。 どうも、この文書は、原文の上位ディレクトリにあるLambda tutorialを読んだ後に読むべきものっぽいようだ。 しかし、流石にこっちまで訳す気力は無い。 そういう訳で、これだけを読むよりは、Unlambdaのチュートリアルを読んだ方がずっと、コンビネータ論理を理解
講義ノートの目次へ ラムダ計算は,コンピュータ・サイエンスの重要な1分野。 「λ」を使って各種の関数を記述し,λどうしの計算方法を習得すれば・・・ HaskellやF#などの関数型言語を習得するために役立つ。 プログラミングにおいて,関数についての理解を深めることができる。 複雑なアルゴリズムを簡易に記述して,挙動や性質を予測することができる。 計算機科学の,より深い専門的な話題を理解するための足がかりを得られる。 などのメリットがある。 下記に,独学でλ計算を勉強するための, 入門レベルの講義ノートやWebページを掲載する。 読みやすい便利なもの・わかりやすいものから,応用的なものへと並べてある。 質の高いものだけを精選し,わかりづらい資料は除外してある。 ラムダ計算の概要 ラムダ計算の基礎 ラムダ計算の応用 復習のための問題(入門レベル) ※λ計算を利用した計算量・計算複雑性・計算可能
先日YコンビネータのきしださんのYコンビネータのエントリが話題になっていました。 ずいぶん日にちが経ってしまいましたが、自分も、自分なりにYコンビネータのあたりを絵解きで整理してみたいと思います。きしださんのエントリタイトル*1に引っ掛けて、目標として、自分の父親(非プログラマ。その辺のおっさん)でも解る内容を目指します。 なぜ不動点演算子というのか、不動点だったらなぜ再帰なのか、この辺りも含めて、実感を持って納得できればいいなと思います。 きしださんのエントリのおさらい 本題の前に、きしださんのエントリをおさらいしておきます。 Yコンビネータはただのオモチャじゃないんだよ 関数だけで色んな事が出来る 条件分岐をする関数ってのもある。 再帰(ループ)を作れる関数もある。←これがYコンビネータ。 数値も関数で表現できる。 つまり、関数だけで、条件分岐も、再帰(ループ)も、数値も作れちゃう!!
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く