スポンサーリンク

「ラムダ計算」を独学で学習するための,講義ノートやPDFのリンク集 (復習用の問題付き)


ラムダ計算は,コンピュータ・サイエンスの重要な1分野


「λ」を使って各種の関数を記述し,λどうしの計算方法を習得すれば・・・

  • HaskellやF#などの関数型言語を習得するために役立つ。
  • プログラミングにおいて,関数についての理解を深めることができる。
  • 複雑なアルゴリズムを簡易に記述して,挙動や性質を予測することができる。
  • 計算機科学の,より深い専門的な話題を理解するための足がかりを得られる。

 
などのメリットがある。


下記に,独学でλ計算を勉強するための,

入門レベルの講義ノートやWebページを掲載する。


読みやすい便利なもの・わかりやすいものから,応用的なものへと並べてある。

質の高いものだけを精選し,わかりづらい資料は除外してある。

※λ計算を利用した計算量・計算複雑性・計算可能性理論のノートはこちら

ラムダ計算の概要

さらっと見る:

ラムダ計算 - Wikipedia
http://ja.wikipedia.org/wiki/%E3%83%A...

  • 関数の定義と実行を抽象化した計算体系。ラムダ算法とも
  • ラムダ計算は「計算可能な関数」とはなにかを定義するために用いられる
  • 計算の意味論や型理論など、計算機科学のいろいろなところで使われており、LISP、ML、Haskellといった関数型プログラミング言語の理論的基盤


数理科学的バグ撲滅方法論のすすめ - 第16回 すべてのものは関数である:ITpro
http://itpro.nikkeibp.co.jp/article/C...

  • λ計算(ラムダ計算)という計算モデルは,関数型言語のモデルとなっている基礎理論
  • その計算モデルでは、「すべてのものを関数で表す」ことができる。つまり,チューリングマシンで可能な計算は、すべて関数で表せる
  • λ抽象「λx. e」は、OCamlの「fun x -> e」に相当する構文

ラムダ計算の基礎

わかりやすさを重視したスライド(初歩なので要熟読):

ラムダ計算入門
http://www.slideshare.net/_yingtai/la...

  • ラムダ記法,カリー化,データ型



簡単なプログラミング言語とのアナロジーで解説:

JavaScriptで学ぶ・プログラマのためのラムダ計算 - 檜山正幸のキマイラ飼育記
http://d.hatena.ne.jp/m-hiyama/200702...

  • ラムダ計算の記法と,JavaScript記法との対応一覧表


JavaScriptで学ぶ・プログラマのためのラムダ計算 問題集 - 檜山正幸のキマイラ飼育記
http://d.hatena.ne.jp/m-hiyama/200702...

  • 練習問題・腕試しとしてgood


京大の講義ノートPDF(定義から厳密に勉強できる):

京都大学数理解析研究所 計算機科学研究分野
http://www.kurims.kyoto-u.ac.jp/~cs/l...


コンピュータ・サイエンス入門 ラムダ計算 第1回目資料
http://www.kurims.kyoto-u.ac.jp/~cs/c...

  • 8ページ。


コンピュータ・サイエンス入門 ラムダ計算 第3回目資料
http://www.kurims.kyoto-u.ac.jp/~cs/c...

  • 8ページ。


しっかりした教科書:

『計算論理学』講義資料
http://logic.cs.tsukuba.ac.jp/~kam/le...

  • 筑波大の講義ノート,57ページ。型のない場合と型のある場合に分けてラムダ計算を解説。

 ラムダ記法と(型のない)ラムダ計算
 構文の定義方法(BNFと帰納的定義)
 命題論理
 CALシステムを使った演習
 PROPゲーム
 型付きラムダ計算
 関数型プログラム言語の体系
 計算体系と論理体系の関係


ここまでのまとめ(概観して理解できればOK)

ラムダ計算をちょっと勉強してみたので、忘れないうちに書いておく - Log for Backup - Naoki_Rinの学習
http://d.hatena.ne.jp/naokirin/201203...


ラムダ計算基礎文法最速マスター - 貳佰伍拾陸夜日記
http://d.hatena.ne.jp/tarao/20100208/...


lambda.pdf(「計算モデルの数理」の授業資料)
http://research.nii.ac.jp/~hu/pub/tea...

  • 最もコンパクトで,なおかつ高度なまとめスライド

ラムダ計算の応用

プログラミング言語として表現:

lambda.pdf:ラムダ計算入門(計算機ソフトウェア工学の授業資料)
http://www.kb.ecei.tohoku.ac.jp/~sumi...

  • MLやObjective Caml (OCaml)のサンプルコードを駆使して説明


目を通しておきたい記事のリスト:

「ラムダ計算」の検索結果一覧 - 檜山正幸のキマイラ飼育記
http://d.hatena.ne.jp/m-hiyama/archiv...


ラムダ計算の勉強用の書籍や本のリスト:

ラムダ計算の勉強のしかた、プログラム意味論 - きしだのはてな
http://d.hatena.ne.jp/nowokay/20110926

英語のテキストをダウンロードしたい場合:

オンラインで入手できる数理論理学・数学基礎論のテキスト
http://klapaucius.web.fc2.com/logic/o...

  • 「An Introduction to Lambda Calculi and Arithmetic」

復習のための問題(入門レベル)

ラムダ計算における重要キーワードを下記に列挙した。

それぞれについて,何を意味するのか,わかりやすく説明しなさい。

  • λx.xなどのラムダ式や項
  • 関数の適用
  • β-簡約と,関数の正規形
  • α-変換と,束縛変数
  • 高階関数とカリー化
  • チャーチ数による自然数の定義
  • コンビネータの種類と使い方
  • 関数の計算可能性
  • 関数の停止性



関連する記事:

「オペレーティングシステム論」の講義資料・ノートPDF。OSのプロセス管理やメモリ管理,ファイルシステムを勉強
http://language-and-engineering.hatenablog.jp/entry/20140510/OperatingSystemL...


大学の「情報理論」(暗号を含む) の講義ノートPDF。代数学を使った情報量・符号化・通信路の理論
http://language-and-engineering.hatenablog.jp/entry/20140519/InformationTheor...


「コンピュータ・アーキテクチャ」の講義ノートPDF。大学の情報科学の入門用教科書 (プロセッサやハードウェア)
http://language-and-engineering.hatenablog.jp/entry/20140509/ComputerArchitec...


「自然言語処理論」の講義ノートPDF。形態素解析や文脈自由文法,知能機械による言語処理の扱い
http://language-and-engineering.hatenablog.jp/entry/20140511/NaturalLanguageP...