Route 477

■ [lisp] 純Lispは関数5つだけでどうやってチューリング完全になるのか？

Wikipediaの「純Lisp」の項を見ると、5つの基本関数だけでチューリング完全だよーみたいなことが書いてある。 でも実際にはcar/cdr/cons/eq/atomだけじゃ分岐も再帰もできなくね？という疑問をどっかで見て、リンクされてる論文を 見てみたりもしたけどよく分かんなかったのだけど、 id:kazu-yamamotoさん の講演資料を見てようやく分かった。

5つの関数
 car 
 cdr 
 cons 
 eq 
 atom 
2つの特殊形式
 quote 
 cond 
関数定義の機能     
 lambda 
 label (defineのこと)

要するに、condとかは特殊形式だから「5つの基本関数」には入らないと(笑)。まぁそりゃそうだけどさ。