第105回 素人くさいSICP読書会（at コントロールプラス株式会社）

event
  • 会場提供ありがとうございました
  • 8人くらい参加。盛況
  • ゴールデンウィークだと参加者が増える。世間と逆だけど、この読書会だといかにも
  • 問題4.13
  • 懸案の宿題
  • hisaさんが発表。頭にダミーを持つデータ形式＋データ主導っぽく
  • 佐野さんが、無理に破壊的操作を使わなくてもconsでフレームを組み立てていけば関数的にできるんじゃね？とか。たしかにできそう。そっちの方がSchemeらしいし
  • ついでにhisaさんが問題4.10で追加する新しい構文「named lambda」を思いついた話
  • 内部で名前を持っていて再帰できる。処理を再帰で書ける無名関数って感じ
  • named lambdaという名前はよくない、とか
  • 問題4.14
  • Louisはprimitive-proceduresの中で(list 'map map)とやった、と
  • 被実装言語の内部で高階関数（ここではmap）に渡される関数は、頭に'lambdaが付いてるか（生のlambdaを渡しても関数定義用のdefineを使っても、結局はこの形に落ちる）、carやcdrといったプリミティブだと頭に'primitiveが付いてるかのどっちか
  • 実装言語のmapをそのまま流用しちゃうと、ふつうのクロージャしか取れないから、頭に目印が付いた変な形式を渡されても困る、と
  • evalを書き換えて高階関数を処理できるかどうかで議論。mapだけなら逃げられるかもしれないけど、高階関数全般に対応するのはかなり大変じゃね？、とか
  • というか、shelarcyさんによるとこの問題の逃げ道は後で出てくるらしい
  • 問題4.15
  • かの有名なチューリングの停止問題
  • ノイマンがゲーデルと同じ結論の論文を提出したのがゲーデルより5日遅かった、とか
  • Lispを使うと（この問題のように）簡単に証明できることがあとでわかった、とか
    • 同じ山を登るのに険しいルートと簡単なルートがあるのと同じ
  • 背理法。問題文にほぼ答えが書いてある。「親切すぎ」（orkenさん）
  • その場ではわかったような気がしたので帰り道に頭の中で復習した
  • pは1引数の手続き。引数として手続きを取れる。おｋ
  • もしhalt?が存在するなら、問題本文にあるようなtryみたいのを記述できる
    • たとえば
    • (define (p x) x)のようなpなら(p p)はlambdaを返して停止する
      • このとき(try p)は無限ループ
    • (define (p x) (x x))のようなpなら(p p)は無限ループで停止しない
      • このとき(try p)は止まる
    • ここまではおｋ。問題なし
  • じゃtryに自分自身を食わせてみよう。(try try)はどうなるか
  • (try try)が停止すると仮定すると
    • 中の処理では(halt? (try try))の部分は#tになるから(run-forever)が走る
    • つまり停止しない
    • (try try)が停止すると仮定すると(try try)が停止しない。思いっきり矛盾
  • (try try)が停止しないと仮定すると
    • 中の処理では(halt? (try try))の部分は#fになるから'haltedを返す
    • つまり停止する
    • (try try)が停止しないと仮定すると(try try)が停止する。同じく矛盾
  • halt?が存在すると仮定すると矛盾が起こる
  • つまりhalt?は存在し得ない
  • 次回は4.1.6から