計算機プログラムの構造と解釈
SICP: Structure and Interpretation of Computer Programs
計算プロセス (computational process) がプログラムに従ってデータを操作する
Lispでは手続きをデータとして扱う
基本的なデータ、手続きが記述でき、それらを組み合わせたり抽象化できるのが強力なプログラム言語である
組み合わせ (combinations)
(+ 10 34) など
左端は演算子 (operator)
それ以外は被演算子 (operands)
operatorが指定する手続きをoperandsの値である引数 (arguments) に作用させることでcombinationの値を得る
aumy.icon operandsとargumentsの違いが微妙にわからない
前置記法 (prefix notation)
任意個の引数を取る手続きを許す
(+ 1 2 3 4 5 6 7)
入れ子 (nested) にすることを許す
(+ (* 3 5) (- 10 6))
オブジェクトを値とする変数を用意する
define を使って名前を付ける
大域環境 (global environment) に名前とオブジェクトの対を保存する
combinationsの評価は以下の順で行われる
1. combinationの部分式を評価する
2. operatorをoperandsに作用させる
combinationを評価するには，その部分式を評価する必要がある
本質的に再帰的である
tree accumulation
評価する必要のないもの，combinationでない基本的な式の要素
数字列の値はそれが表す数値
基本演算子の値は対応する演算を実行する機械命令の列
それ以外の名前の値はその環境で名前と対応付けられたオブジェクト
(+ x 1) のような式の値について考えるのは，記号 x や + の意味を与える環境について考えない限り無意味である
(define x 3) のようなものは特殊形式 (special forms) であり，組み合わせではない
手続き定義は (define (square x) (* x x)) というように表す
手続きを作り，名前を作るという2つの演算が合成されている
無名関数とかの話っぽいaumy.icon
一般形は $ \texttt{(} \texttt{define} \texttt{(} \langle \textit{name} \rangle\ \langle \textit{formal\ parameters} \rangle \texttt{)}\ \langle \textit{body} \rangle \texttt{)}
合成手続きを引数に作用させる過程は以下
1. 各parameterを対応するargumentsで取り換えて，手続きの本体を評価する
そのようなプロセスを手続き作用の置き換えモデル (substitution model) という
単純なモデルで，特に可変データを考えるとそのうち破綻する
normal-order evaluation
完全に展開し，簡約する
遅延評価
applicative-order evaluation
引数を評価し，作用させる
先行評価
条件式には cond や if を使う
Newton法による平方根の計算
手続きはブラックボックスとして見ることができる
手続きがどう結果を計算するかには関心がない
手続きのparameterの命名は手続きの利用者が気にする必要がない
束縛変数 (bound variable)
手続き定義はparameterを束縛(bind)する
bindされていない変数は自由 (free) である
再帰的プロセス
手続き呼び出しを置き換えていくと (* 4 (* 3 (* 2 1))) のように成長していき，収縮していく
前の計算を覚えておく必要がある
$ n に比例して成長する線形再帰的プロセス
code:factorial1.scm
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
反復的プロセス
置き換えプロセスにおいて収縮しない
状態変数，状態変化時の状態更新規則，プロセスの停止条件の3要素
必要なステップ数が $ n に線形に増加する線形反復的プロセス
code:iterative.scm
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* product counter) (+ counter 1))))
iter 1 1)
木構造再帰
フィボナッチ数を素朴に計算すると出てくる
lambda 無名手続き
(lambda (x) (* x x)) など
let 変数束縛的なやつ
(let ((変数名 値) (変数名2 値2)) 変数を使用する式)
((lambda (変数名 変数名2) 変数を使用する式) 値 値2) に脱糖される
問題1.34
code:1.34.scm
(define (f g) (g 2))
があるとき、(f square) は 4 で (f (lambda (z) (* z (+ z 1)))) は 6
Q. (f f) を評価させるとどうなるか？
A. (f 2) となり、さらに (2 2) になり、2 は手続きではないのでエラーになる
関数の零点の探索
めんどそうだからやらん！
関数の不動点の探索
めんどそうだからやらん！
講義がつまらない時にやってみるとよい: 電卓をラジアンモードにし，不動点が得られるまでcosのボタンを押し続ける．
草
1.3.4 値として返される手続き
めんどそうだからやらんって言って飛ばした内容が出てきた