UCBerkeley CS61A Structure and Interpretation of Computer Programming Week2

だいぶ間が開いてしまったがSICPのWeek2。
http://itunes.apple.com/WebObjects/MZStore.woa/wa/viewiTunesUCollection?id=354818464#ls=1


教科書はオンラインで読むこともできる。
Structure and Interpretation of Computer Programs（SICP)http://www-mitpress.mit.edu/sicp/full-text/book/book.html

宿題や試験の内容はこちら。（宿題はCourse Reading Vol1にある。）
http://www-inst.eecs.berkeley.edu/~cs61a/fa10/

Lecture 3

主な内容

• Function as Arguments( Higher-order function )
• 関数の表記について（ |-> という表記 )
• lamda関数

関数の表記 |-> "maps to"についての説明はなんとなく聞くことになるけど、SICP 69ページのFixed-Pointの計算でsquare rootを計算するところでその理解が必要になる。（詳しくは後述）

lamda関数については、その歴史から話が始まる。アロンゾチャーチという人が、数学を関数を元に説明しようとしたところから始まっている、というような話だった。その後、AI研究者のジョンJohn McCarthyが、その考え方をLispに取り入れたとのこと。

Lecture 4

主な内容

• First Class Data
• Functionを返すFunction
• letについて

基本的には高階関数の話

宿題

宿題はSICPのSection1.3を読むこと。Section1.2は飛ばしてあとでやるとのこと。読むに当たって知っておいた方が良さそうな英単語は
converge 収束する
differentiable 微分可能
derivative 導関数

いくつか注意が必要なところがあったので、メモ。
まず、SICP67-68は飛ばしてもよい。これは宿題の指示にも書いてある。

それから、その次の「Finding fixed points of function」というところ。まずFixed pointが何なのか分からないといまいちピンとこない。日本語では不動点 http://ja.wikipedia.org/wiki/%E4%B8%8D%E5%8B%95%E7%82%B9 となるらしい。これを一通り見ればどういうことなのか分かる。
それから、69ページのこのFixed pointの計算を使ってルートを解くところで、y |-> x/y とかなっていて、x,yの二つの変数が出てきてそれでどうして計算ができるのかと一瞬戸惑うのだが、よく見ればこれはyの関数であって、xは定数であることが分かる（このことに気づかないと理解するのに時間がかかる。）。
これは、まさに授業中に言っていたことだ。ax+bとかあったら、勝手にxを変数だと思い込むくせが悪いのだろう。正確な関数の記述はx |-> ax+b ということだ。

読み終わったら、指示にしたがってSICPの練習問題を解く。
教科書の練習問題は、基本的なことが主なので問題ない。
難しかったのはCourse ReaderのWeek2のExtra for expertsの問題。
これはできなかった。なんとなく考え方としては関数を返す関数を書いて・・・2重にすれば・・・などと考えたけどうまくいかなかった。決して方向性は間違っていなかったようなきがするけど。

これはY Combinatorというものらしい。詳しくは以下を参照
http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html

UCBerkeley CS61A Structure and Interpretation of Computer Programming Week1

いろいろな大学が授業の様子をYouTubeやiTunesUで公開しているというのは、いままでもブログに何度か書いてきた。
ここへ来て、真面目に順番に授業を受けようと思い、始めている。
一つ受ける度に、ブログにそのまとめを載せていこうと思う。これから、この教材を使って勉強しようとする人のガイドになればと思う。

第一段はUCBerkeleyのCS61A(Structure and Interpretation of Computer Programming)。授業は以下のサイトにある。
http://itunes.apple.com/WebObjects/MZStore.woa/wa/viewiTunesUCollection?id=354818464#ls=1



教科書は有名な本だが、Structure and Interpretation of Computer Programs（SICP)となっている。教科書はオンラインで読むこともできる。
http://www-mitpress.mit.edu/sicp/full-text/book/book.html

また、宿題や試験の内容がここにある。（宿題はCourse Reading Vol1にある。）
http://www-inst.eecs.berkeley.edu/~cs61a/fa10/

スケジュールを見ると、大体一週間に2～4講義分ぐらい進むらしい。Course Reading Vol1には、Week1、Week2とかかれていて、それぞれやることが書いてあるので、それに併せて、ビデオを見ながら進めようと思う。
やり方としては先に教科書を読んでビデオを見て、宿題をやってもよいし、先にビデオを見て宿題をやってから本を読んでもよいし、教科書と授業の順番はどうでもよいと思う。
僕はビデオを見て、教科書を読んで、宿題を行うという順で行った。

この授業にはCourse Reading Vol1とVol2という二つがある。
Vol1はセメスターごとに少しずつ変更になる内容のもので、宿題などが載っている。先ほどのサイトからダウンロードできる。Vol2は、セメスターごとにほとんど変更のないもので、毎回同じものを使っているらしい。これもダウンロードできる。ただし最初のうちは関係なさそうなので、用意するのは教科書とVol1があれば大丈夫。（残念ながらビデオの授業のCourse Readingそのものは手に入れることはできそうにないので、現在配られているものを利用している。）

授業で使われているSchemeプログラムはSTkというものらしく、さきほどのコースのウェブサイトからダウンロードできる。

今回はWeek1

• 教材Vol1: Week1
• 教科書: Section 1.1
• iTunesU: Lecture1 - Lecture2

Lecture1

主な内容は
-Schemeの使い方
-- 簡単な計算
-- 関数定義
-コースオーバービュー

Schemeの使い方では、たった40分程度だが、先生は「これでSchemeの90%はみんな理解したことになる」と言っている。それぐらい簡単なものだということを言っている。

コースのオーバービューとしては、「プログラミングは"very very easy"だ。中学生でもできる。それは天才だからじゃなくて、簡単だからだ。」というのを強く言っていたのが印象的だった。
残念ながらこのiTunesUのビデオはなぜか途中で切れたようになっている。

Lecture2

おもな内容は
-コースオーバービューの続き
-- Functional Programmingを学ぶ意味
-- コンピュータの抽象化
- -宿題や試験についての注意
-Schemeの使い方その２
-- 条件分岐
-- Applicative orderとNormal order

「Functional Programmingを学ぶ重要性の一つは、今日のプログラムが並列性を持つようになってきているからである。」とか、コンピュータの抽象化についての話と続く。
さらにSchemeの使い方が続く。主に条件分岐やApplicative OrderやNormal Orderなどの話がメイン
Functional Progurammingを行っている限り、Applicative OrderかNormal Orderかは関係ない。つまり結果が計算の順番によらないということを強調していた。並列処理プログラムを書くときの重要な考え方なんだろう。

宿題

さてビデオを見た後で、宿題に取りかかる。
Homework Week1を読むと、まず、教科書のセクション1.1と1.3を読むようにと書いてある。おおよそビデオで習ったことなので話はスムーズにす進む。ただし、1.3の内容は来週の予習となっている。

宿題はプログラムを書くものが多いので、環境を整える必要がある。コースのウェブサイトにあるリンクから各環境用のSTkをインストールする。授業で使われているScheme処理系はfirstやbfといった関数が予め定義されている。これはstk-simplyというプログラムを利用すればよいことになっている。（普通のSTkにはこれらの関数はない。）

宿題には教科書の一部の問題を解くようにと指示されていたり、その場に問題が載っていたりする。
ひとまず、Week1の宿題の問題をすべて実際に解いてみた。簡単なものもあれば、難しいものもある。
デバッグの方法がよくわからないので、うまく動かないと頑張ってどこが悪いのか探さなくてはいけない。慣れてくると意外とすんなりと書けるようになってくる。