mrasu’s blog

読んだ物の内容など

計算機プログラムの構造と解釈(1章)

「計算機プログラムの構造と解釈(SICP)」を読み始めました

Structure and Interpretation of Computer Programs(SICP)の翻訳本。 Schemeを利用して、プログラミングパラダイムを考察、実装する本です。
実装のみをしている章は省いています

計算機プログラムの構造と解釈 第2版

計算機プログラムの構造と解釈 第2版


1.0 Scheme

Scheme(Lisp)を使用する。
Lispは標準化をしないので、方言が存在できそれが柔軟さにつながっている。
「受動的」なデータと「能動的」なプロセスをぼかし、手続きをデータとして表現することが、プログラムの議論の土台とするのに適している

1.1 プログラム

1.1.1 式

演算子も、関数のように引数を取ることで表すようだ
(* 2 4)
一見、ポーランドっぽいが、ポーランド記法ではない。

1.1.2 変数

変数を定義できる
変数を定義することは、最も単純な抽象化。
変数と値の記憶をenvironment(global environment)と呼ばれる

1.1.3 combinationの評価

組み合わせ(pair)は
0. 部分式の評価
0. 演算子を被演算子に作用させる
という動きをする。

つまり、
部分式の評価を行うことから再帰が必然であり、演算子に作用しない定義式(define)は特殊である。

1.1.4 合成

(define (square x) (* x x))
(define (sum-of-square x y) (+ (square x) (square y)))
で定義できる

1.1.5 関数の置き換え

  1. 作用的順序
    式を逐次評価する
  2. 正規順序
    式を全て展開したのちに、評価する

効率性の問題から、実際には作用的順序が使用される

1.1.6 条件式

  1. cond
    switch。else がdefaultに相当する
  2. if
    if。第二引数がelse
  3. and, or, not

1.1.7 Newton法による平方根

再帰の定義

改行の場所が難しい

1.1.8 ブラックボックス

  1. 束縛変数(関数内部でのみ有効な変数名。外部からは見えず、意味を持たない)
  2. ブロック構造と静的有効範囲(名前空間とか、jsの即時関数と同じ)

1.2 手続き

1.2.1 線形再帰と線形反復

  1. 線形再帰的プロセス
    再帰で自分を呼び出す時に他の情報を覚えている必要があるための記憶が必要(必要容量は線形に増加する)
  2. 線形反復的プロセス
    呼び出し時の値を記憶せず、再帰が止まるところから実行するため、呼び出し元の記憶が不要

1.2.2 木構造再帰

木を舐めまわして、再帰する

1.2.3 オーダー

オーダー記法とかシータ記法について

1.2.4 べき乗

  • 線形再帰
  • 線形反復
  • 線形再帰よりもオーダ減少(Θ(log n))

1.2.6

Fermat(= フェルマー)の素数性テスト

1.3 高階関数

1.3.1 手続きを引数とする

関数も引数にとれる

1.3.2 lambda

無名で関数を作れ、関数を戻り値にすれば、実行したいときに評価させられる