SICPと、6.001の話

調べていたところ、「弱LisperがMITでSICP(シクピー)を受講した結果」（ http://qiita.com/kaz-yos/items/d1ecd4bfe9989c290e99 ）というQiita記事を見つけたのでリンクしておきます。噂の(？)SICPを懐かしむチューターたちによって実施されている特別授業に潜り込んだ(？)方によるレポートです。

本題の、以前はSICPだった授業である6.001が、どのようになぜ変わったか、という話がこちらのページ（ http://wingolog.org/archives/2009/03/24/international-lisp-conference-day-two ）にあるのですが、その部分だけ訳してみます。

本文のなかほどの「The "debate" had an interlude, in which Costanza asked Sussman why MIT had switched away from Scheme for their introductory programming course, 6.001.」という所から始まっていますが、そのちょっと先、because〜 から。

because engineering in 1980 was not what it was in the mid-90s or in 2000. In 1980, good programmers spent a lot of time thinking, and then produced spare code that they thought should work. Code ran close to the metal, even Scheme -- it was understandable all the way down. Like a resistor, where you could read the bands and know the power rating and the tolerance and the resistance and V=IR and that's all there was to know. 6.001 had been conceived to teach engineers how to take small parts that they understood entirely and use simple techniques to compose them into larger things that do what you want.

なぜなら、1980年代のエンジニアリングは、90年代中頃や2000年代のそれとは違ったものだったからだ。1980年代には、良きプログラマは思考に時間を掛け、そしてそれが働くべきと考えられる簡潔なコードを作った。コードは金物の近く（close to the metal）で走っていた、Scheme でさえ -- それは全て理解可能だった。例えば抵抗器のように。抵抗器はカラーバーを読むことができ、電力と許容差がわかり、抵抗値がわかれば V=IR それが全ての知るべきことだ。6.001 はエンジニアに、全てがわかっている小さいパーツをどのように扱い、シンプルなテクニックを使ってそれをどのように望むことをする大きなものにまとめ上げるか、を教えるためにあった。

But programming now isn't so much like that, said Sussman. Nowadays you muck around with incomprehensible or nonexistent man pages for software you don't know who wrote. You have to do basic science on your libraries to see how they work, trying out different inputs and seeing how the code reacts. This is a fundamentally different job, and it needed a different course.

しかし今のプログラミングは全くそのようなものではなくなっている、とサスマンは言った。こんにちでは、知らない誰かが書いたソフトウェアの、不十分だったり存在しなかったりするman pageと格闘しなければならない（訳注: ここでman pageを悪い例っぽく挙げているのは「The Rise of “Worse is Better”」のMIT/New-Jerseyの対立っぽい感じがある）。使おうとするライブラリに対して、異なった入力に対しコードがいかに反応するかを見て（seeing how the code reacts）確かめて、それがいかに働くかを見る（see how they work）「基礎科学」（basic science）をする必要がある。これはファンダメンタルに違うジョブであり、違うコースが必要なのだ。

So the good thing about the new 6.001 was that it was robot-centered -- you had to program a little robot to move around. And robots are not like resistors, behaving according to ideal functions. Wheels slip, the environment changes, etc -- you have to build in robustness to the system, in a different way than the one SICP discusses.

And why Python, then? Well, said Sussman, it probably just had a library already implemented for the robotics interface, that was all.

新しい 6.001 の良いことは、ロボットを中心に据えたことだ -- 小さなロボットを動き回らせるようプログラムしなければならない。ロボットは、理想的な関数の通りに働く抵抗器のようではない（are not like）。車輪はスリップするし、環境は変化する、など -- システムにロバストネスに構築しなければならず、それは、SICPが議論しているのとは違ったやり方だ。

そして、なぜPythonか。それはたぶん、単に既にロボットのインタフェースのためのライブラリが実装されてあったこと、それが全てだ。

ARMの設計（デザイン）

Oral History of Sophie Wilson（ http://www.computerhistory.org/collections/catalog/102746190 ）から、ARMの設計（デザイン）に関することのメモ

（主に、6502との関係について）

  • ARM以前のほとんどのマシンで6502を使用しており、6502での経験はあった
  • しかし、他のプロセッサを載せるボード（8ビット機時代によくあったもの）で他のプロセッサも使っていた
  • それでも6502が良い、と思っていた。メモリアクセスの帯域を有効に使っている、という所から（他のプロセッサではそこのバランスに問題があった）
  • （ビデオプロセッサが画面表示に間に合ってアクセスするためには、メモリアクセスにある程度の帯域幅が必要であり、その性能をメインプロセッサも生かせるのが、当時の「バランスの良い」デザイン、ということになるのだろう）
  • ARMの設計（デザイン）については、このバスアクセス帯域について以外には、（命令セット等）6502の影響があったというようには読み取れない

ARMの成功要因は何だろうか？（きしもとの私見による分析を含む）

  • 明解で単純な目標の設定、例えば
  • 6502の代替となること
    • (それまでのマシンでは機械語プログラミング等のテクニックの駆使が必要だったことを、高水準言語でできるように）
  • 「IPM PC 互換機の洪水」に対抗すること
  • スローガン「MIPS for the masses」（この「MIPS」は、プロセッサというよりは（それもあるが）性能のことを指している）。当時、他のRISCプロセッサは、ワークステーションを指向していて高価だった
  • 前述の「他のプロセッサを載せるボード」として、まず動くベンチとなるシステムを作ったこと
  • むやみに大きなプロセッサにしなかったこと（最初のプロセッサは25000トランジスタ）もあって、最初からちゃんと動くものを作ったこと。インタビュー中では、ナショセミのNS320xxがいつまでもまともに動かなかったことと比較している

Macr055発表の反省

プロシンでいただいたコメントとかに対するメモ

再帰的なマクロの例が欲しい

（言い訳: 「マクロに展開されるマクロ」がちゃんと再帰的に扱えれば、あとはそのマクロが自分自身でも同じことだ、と思っていたのですが）質疑応答のかなり最後のほうで、「再帰（によるループ）ができても、ifelseのようなことができないと、再帰すると止まらなくなるので結局使えない。一方ifelseがあればそれと再帰でいろいろできる」というように回答したのだけども、ifelseを紹介したついでとして何か簡単な「再帰的なマクロ」の例があればよかった（多分それで時間もバランスが取れたかもしれない）

プッシュバックの様子とかが可視化されるデモみたいなので説明が欲しい

（デモ用途に限らず、マクロプログラミング（特にデバッグ）に有効だろうと考えていて、インタフェイスを考えてるところ）

予稿のリファレンスの番号がズレている

後から確認したら、「LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.」が出てないか注意しましょう、というオチでした（参照番号が［?］になったりはしていなかったので油断した）。

「m55_define」は長くてうっとうしい

（設計者の弁: ユーザが任意の名前を使えるよう、処理系組込みの名前は「予約名前空間」のようなイメージで全てプレフィクスを付けている）

「例えば def という名前にしたりはできないのか」ともコメントされたので簡単に検討したところ、現在の仕様では全く透過的にはできないことがわかり、定義ではなくエイリアスの機能があったほうが良いかも、と思ったのでその後で簡単に実装した（抜けとかあるかもしれないのでそのうちチェックしたらリポジトリを更新する予定）。

『ソフトウェア作法』は「さくほう」

と読むのだ、と訳者の先生ご本人がおっしゃっていた、とのコメントが。（両方を掛けている、とどこかで読んだ記憶があるんだけどなぁ……）

簡易回転計算

というツイートを見て、少し考えてみました。

角度が θ（以下、全てラジアン（弧度法）とする）で、ごく小さい（ θ ≒ 0 ）時、sin(θ) ≒ θ, cos(θ) ≒ 1 という近似もありますが、それとは少し違う感じです。

ピタゴラスの定理から sin2(θ) ＋ cos2(θ) ＝ 1 という関係がありますが、それを変形すると、互いに sin(θ) ＝ √( 1 ー cos2(θ) ), cos(θ) ＝ √( 1 ー sin2(θ) ) となりますので、それをちょっと考えてみます。すると次のように、cos の側から計算するとうまいこと変形できて、

√( 1 - (127/128)2 ) ＝ √( 1 - 16129/16384 ) ＝ √( 255/16384 ) ≒ ( 16/128 ) ＝ 1/8

のように、cosの側を基準にするとsinがわずかに大きくなっている近似と言えます。

ここでもう少し √( 1 - ((N-1)/N)2 ) について考えてみますと、

√( 1 - ((N-1)/N)2 ) ＝ √( 1 - (N-1)2/N2 )

　　　＝ √( 1 - (N2-2N+1)/N2 )

　　　＝ √( (N2-N2+2N-1)/N2 )

　　　＝ √( (2N-1)/N2 )

　　　＝ √(2N-1) / N

となりますので、2N（か、2N-1）がちょうど平方数になり、かつその平方根がNの約数、というような時にうまく上記の場合のような関係になることがわかります（例示の場合では N = 128、平方数が256=162）。

小さい方を考えてみますと、

N = 98 の時 97/98 と 1/7 （平方数が196=142）

N = 72 の時 71/72 と 1/6 （平方数が144=122）

といったようにして同じような関係は（誤差がだんだん大きくなりながらも）成立していますが、うまく2の冪の計算が8ビット機で使えるのは、1/8が出てくる上記の場合だけでしょう。

process reaperの実験

procctlという、プロセスの属性の一部を制御するAPIはFreeBSD 10で追加されたものですが、10.2 でそれに reaper facility と呼ばれている機能が追加されました。基本的な機能性はLinuxを参考に（Linuxでは prctl(2) というAPIです）、APIの設計はDragonflyBSDをベースにしており、manページもFreeBSDのものよりDragonflyのほうがわかりやくす書かれていますから、そちらを参考にすると良いでしょう。こちらのメイルから始まるスレッドもご参考ください https://lists.freebsd.org/pipermail/freebsd-arch/2014-December/016437.html 。

process reaperとは、子プロセスを作った場合の親プロセスのように、子プロセスが終了してゾンビになった後で、それに対応するwaitシステムコールを発行するプロセスのことを指します（ゾンビの魂(？)を、死神の鎌で刈る（reap）というイメージですね）。しかしこれらのAPIでは、Unixにおいて PID 1 の、通常は init が（あるいは近年のmacOSやLinuxでは違いますが）受け持つ、親プロセスが先に終了したようないわゆる orphan プロセスの親となり、それらが終了した後に wait を発行する、という権利と義務（？）について、init になり代わる、という機能を扱っています。

procctlという関数名ですが、manを見るときは同名のコマンドと被ってますので、man 2 procctlのようにして参照する必要があります。

次にサンプルコードを示します。

最後のほうでforkしていて、子プロセスのほうからはxtermを起動していますので（xtermが無い環境の方は適宜修正してお試しください）、そのxtermの中のシェルから sleep 100 & など適当に時間のかかるプロセスを起動しておいてからxtermを終了し、別のターミナルなどから ps -d などで確認すると、orphan プロセスの親になっているのが確認できるかと思います。

この機能、軽量コンテナのインスタンス毎のinitとして、とかに使うためのものだろうかとか思ってますが、どうなんでしょうか？　（あるいはデーモンマネジャのようなものを実装するのにも使えそうですが）

総和の計算は、なぜどのように難しいのか

プログラミング入門で、forループを使う例題としてよく出てきたりするように、総和計算は一見簡単そうですが、実はどのように難しいのか、という点を書いてみます。

まず、対象が整数であれば、大きな問題はありません。昔のようにintが16ビットの場合は、160*160=25600 でぎりぎりに近く 200*200=40000 ではもう 32767 を超えて溢れますから、intではなくlongを使うといった注意が、以前は必要だったというくらいでしょうか。

一方、対象が浮動小数点の総和は、場合によってはそう簡単ではありません。

場合として、まず、符号が正か負の片方だけであれば簡単です（代表的なものとしては内積など）。ソートして絶対値順に並べ、絶対値が小さい側の端2個のペアを取り出して、その和を計算し、結果をソートされている列の入るべき場所に挿入する、という操作を繰り返せば、基本的には問題はありません。

符号が両方ある場合は、正と負に振り分けてそれぞれ計算し、最後に差をとれば良い、と思うかもしれませんが、それではうまくない場合があります。極端な場合として、正側と負側のそれぞれの合計の絶対値が、2倍以内という近い値になってしまうかもしれません。そうなると桁落ちになります。

桁落ちという現象は、しばしば誤解が見られますが、それ自身は誤差を発生させません。正確には、絶対誤差は増えないが、値が小さくなるために相対誤差が（場合によっては文字通り「桁違いに」）大きくなる、という現象です。

そういったような場合、その絶対誤差は、そこに至るまでの計算過程での情報落ちによる誤差の積み残しの集積になっています。

直感的には、桁落ちの英語が「キャンセル」であるように、総和をとる対象中の、正負それぞれの絶対値の大きい値どうしでキャンセルできるものがあれば、それぞれでキャンセルすれば、「桁落ちは起きているが、情報は失われていない」という状態を維持できるので、それを繰り返してゆけば、正確な計算ができるはずです。

しかし、そのようなヒューリスティック的な計算をいちいちやっていては、総和計算に期待されるような Ｏ(n) に近い効率はとても実現できませんから、実際に提案されている手法は、何らかの方法で積み残しを全部残すであるとか、倍精度浮動小数点で表現可能な値の範囲全体をカバーする巨大な固定小数点で計算するとか、そういった手法になっています。