maoeの日記

ここは研究室関連の話題専用です.メインのブログはmaoeのブログです.VMware Playerの情報を求めて飛んできた方は報告: VMware Playerへどうぞ.

SICP勉強会関連はキーワード「SICP勉強会」からどうぞ.

2006-04-25

[][] 次回開催は4/27(木) 14:00からです. 09:48

あとでかく.

追記

定期開催することになりました.月曜14:30からと木曜14:00からの週2回です.

2006-04-08

[][] R5RS,処理系マニュアル 01:44

Scheme仕様RnRSと呼ばれ,バージョン番号がnに入る.現在の最新版はR5RSで,勉強会で使っているGaucheもこれに準拠している.日本語訳もあるので,正確な定義や動作を知りたい時は参照すると良い.

また,Scheme仕様が非常に小さいこともあり,処理系ごとに便利な言語拡張やライブラリを備えていることが多い.Gaucheに関しては国産処理系ということで日本語のドキュメントがある.

2006-04-06

[][] 次回開催は4/10(月) 14:00からです. 01:20

次回は20頁の問題1.9から進めます.ここからしばらく計算量の話が続きます.

[][] 第2回: 手続きによる抽象2 01:37

今回は12頁1.1.7のNewton法による平方根から始めて,1.2.1の線形再帰と反復の終わりまでをやった.一日に4,5時間で週2回という結構なハイスピードで進んでいる.

それでは今日の反省いってみよう.

1.1.7 Newton法による平方根 (p.12)

ここでのポイントは,問題を解決するには解が「何であるか」ではなくて「どうやって求めるか」を記述しなければならないということ.

本にあるように

(define (sqrt x)
  (the y (and (>= y 0)
              (= (square y) x))))

では何も解決しないということを認識するのが重要.ここでは「どうするか」にNewton法を使ったということである.プログラム自体は公式を普通に書き下せばよい.また,豆知識として,Schemeでは真偽値を返す関数*1にはhoge?という名前付けがされる.

参考リンク

問題1.6: なぜifは特殊形式なのか (p.14)

今日一番時間をかけたところ.

要するに

(define (p) (p))
(new-if #t 0 (p))

無限ループしてしまうということ.そのプロセスを作用的順序と正規順序の両方で書き下せるようになればよいのではないかと思う.ちなみに勉強会中にしょっちゅう言及するHaskellは正規順序の評価戦略をとっている*2のでnew-ifを関数として以下のように定義できる.

newIf pred thenClause elseClause = case pred of
                                     True  -> thenClause
                                     False -> elseClause

これをSchemeと同じように評価すると,

p = p
newIf True 0 p
=> 0

無限ループに陥ることなく評価できる.

4/8追記: マクロによる遅延評価

Schemeではマクロを使えばnew-ifを正しく定義できる.

(define (p) (p))
(define-syntax new-if
  (syntax-rules ()
    ((_ predicate then-clause else-clause)
     (cond (predicate then-clause)
           (else else-clause)))))

(new-if #t 0 (p))
=> 0

Schemeマクロに関しては Scheme 入門 15. 構文の定義 にわかりやすく書いてある.

問題1.7: 誤差 (p.14)

典型的な問題.数値計算法の教科書を見直そう.M2M1教科書が違うかもしれないけど,M2の伊理先生の黄色い教科書には誤差の話もNewton法の話も載っている.これは結構苦手だったので,あとで見直してみる.

問題1.8: 立方根の計算 (p.14)

1.1.7と全く同じ.勉強会では触れなかったが,似ているということはもう一段抽象化可能ということ.どのように抽象化できるのか考えてみよう.1.3.4節でこれが出てくる.

1.1.8 ブラックボックス抽象としての手続き (p.14)

ここの前半はほとんど触れていないので本を見ておくと良い.手続きに名前を付けてそれを使って平方根を求めたが,ひとつの手続きの中身を他のものに置き換えても,他の手続きを変更する必要はないことに注目.これは仮引数名も同様である.

後半で重要なのはSchemeでは欠かせないレキシカルスコープの話.仮引数のように束縛されてない変数を自由変数というが,自由変数の値は「自由変数を利用する関数が定義された環境から取ってくる」という性質をレキシカルスコープという.

よく思い出してみると,説明がレキシカルスコープの説明になっていなかったことに気がついた.例が悪かった.簡単に言うと,

(let ((x 0))
  (let ((f (lambda () x)))
    (let ((x 1))
      (f))))

これが1になるのがダイナミックスコープ,0になるのがレキシカルスコープ.参考文献としてPaul GrahamOn Lispを挙げておく(このページをレキシカルで検索)が,この例はCommon LispなのでSchemeでは動作しない.

ここは重要なのでもう一度やろうと思う.

1.2 手続きとその生成するプロセス

1.2.1 線形再帰と反復

スタックを消費していく方が再帰プロセスで,消費の割合がステップ数に線形に伸びる再帰を線形再帰という.それに対して,定数個の変数更新していくタイプを反復的プロセスと呼び,ステップ数が線形なものを線形反復的プロセスと呼ぶ.

つづく

ちょっと説明不足が多い気がするので,あとで書く

*1:SICPでは「述語」と表されている

*2:非正格(non-strict)ともいうし,遅延評価(lazy evaluation)というキーワードが出てくることもある.非正格の反対はそのまんま正格(strict)という.

tito_3Gtito_3G2006/04/07 02:04お疲れ様です. 出来が悪くて, 毎回時間をとらせて申し訳ないです.
なんとなくなんですが, 研究室のwikiっぽいのあると便利かななんて思っちゃったりします. 今回のSICP勉強会なんかや研究関連とか. まぁ, 投稿者も少ない気もしますが...

maoemaoe2006/04/07 02:27時間がかかるのは仕方ないでしょう.基本的に予習も宿題もなしという方針な上に,わざと時間をかけているという面もあるし.気にせずわからないところはじゃんじゃんいってくださいな.
Wikiに関しては研究室内のWikiだと自宅から観覧・更新できないのが痛いところ.レンタルWikiがあればいいんだけどね.レンタルにすると,研究関連を載せたばあい適切なアクセスコントロールが必要だし困ったね.

maoemaoe2006/04/07 02:28何かおすすめあったら教えてください.

菊地#OBです.菊地#OBです.2006/04/09 23:08お久しぶりです.
そういえば,昔 livedoor が Wiki のサービスをやってましたね(今もあるようです).まあ,どこまでアクセスコントロールができるのか分かりませんが...
また,研究室に余っている Sun とかで Web サーバを立てる手もあります.外部からのアクセスには書類が必要ですが,結構簡単ですよ.ただし,メンテンナンスの問題は残りますけど.

maoemaoe2006/04/10 02:10お久しぶりです.菊地さん.livedoor Wikiですか.ありがとうございます.調べてみたところ他にもWIKIWIKI.jpなどがあるようです.研究室の話題を載せる場合はSunかなにかでやるしか無いと考えています.
ところでお仕事の方はどうですか? 順調ですか? といってもまだ1週間ですが.

2006-04-04

[][] 次回開催は4/6(木) 13:00からです. 03:12

今回は問題1.5まで進めました.次回は1.1.7のおなじみニュートン法からです.

[][] 第1回: 環境設定,Emacs,手続きによる抽象1 03:12

記念すべき第1回を開催した.集まったのは3人のM1と私の全4人.初回らしく環境設定から行う.WindowsユーザとFreeBSDユーザとLinuxユーザが入り乱れているためか多少苦労した.

ここの日記では毎回*1勉強会のまとめと,触れられなかった補足事項や訂正事項を書いていこうかと思う.そういうわけで今日の反省いってみよう.

環境設定

WindowsではMeadowGauche Windows版をインストールした.ポイントMeadowショートカット

C:\path\to\meadow -l "C:\path\to\.emacs"

とし,作業フォルダ

C:\path\to\workspace\for\sicp

にすること..emacsの設定はmaoeのブログを参照のこと.また,MeadowMS-IMEにて日本語入力を行うにはさらに.emacs

(setq default-input-method "MW32-IME")
(mw32-ime-initialize)

を追加する必要がある.参考ページFreeBSDLinuxでは普通にEmacs + Gauche.emacsの設定を行えばよい.

ちなみに勉強会では触れなかったが,.emacsに書いてあるmule-ucsとはEmacsUnicodeなどのエンコーディングサポートするためのパッケージで,ASCIIのみを使う分には必要ない.

それと気をつけなければならないことはenvironmentの綴り.oのあとのnを忘れずに!

Emacsの使い方

土居研究室には千葉さんがEmacs使いであるにもかかわらずEmacsユーザがあまりいない.情報工学出身者にとってViEmacs教養のひとつなので,是非とも覚えたい.いろいろなサイトキーバインドの表が載っているが,一度C-h tかメニューの[Help]->[Emacs Tutorial]でいけるチュートリアルをやってみると良い.覚えるのには時間がかかるけど,手を動かすことで少しずつ記憶できるはずである.

SICP 第1章 手続きによる抽象の構築

早速,本の内容に入った.第1節のプログラムの要素に始まり,12頁の問題1.5まで進めた.参加者は皆,B3のときにCommon Lispに触れているということを考慮してだいぶ端折った部分もある.大丈夫だろうか? よく本を見直してみて欲しい.ここまでで重要なことは以下の通り.

  • Schemeは前置記法である.S式でいうと(operator operands)ということ.
  • defineは名前を付けているに過ぎないということ.
  • ここまでの例はすべて置換えモデル(substitution model)で説明できるということ.
  • 手続きを作る唯一の方法はlambdaであるということ*2
  • 評価の順序は,先に展開する正規順序(normal-order)と,先に引数を評価する作用的順序(applicative-order)があり,Scheme前者Haskell後者の評価戦略をとっていること.
  • 正規順序の評価と作用的順序の評価で結果の異なる不思議関数があるということ.

こんな感じ.lambdaと評価順序のところがややこしいところかもしれない.

やってみよう

lambdaに関しては今日やった問題1.3

3つの引数を取り,大きい2つの数の二乗の和を取る手続きを定義せよ.

をdefineを使わずにlambdaだけで表現できるようになればいいのではないかと思う.

評価順序に関してはSICPの1.1.5をよく読むこと.あるいはRubyist MagazineのIoの紹介の後半でmyIfを定義している部分が参考になったりするかもしれない.

その他良い文献があったらどんどん書き込んでいきたいと思う.みんなも参考になったものがあればコメントに書き込んでいって欲しい.来年に今のM1がやるかもしれないしね.

*1:気力が続けば

*2:これは本ではもう少し後になってから出てくる

2006-03-24

おめでとう 01:55

M2B4のみなさま.卒業おめでとうございます.