計算機プログラムの構造と解釈 1章 手続きによる抽象の構築
- 作者: ジェラルド・ジェイサスマン,ジュリーサスマン,ハロルドエイブルソン,Gerald Jay Sussman,Julie Sussman,Harold Abelson,和田英一
- 出版社/メーカー: ピアソンエデュケーション
- 発売日: 2000/02
- メディア: 単行本
- 購入: 35人 クリック: 1,149回
- この商品を含むブログ (480件) を見る
1章は色々な数式を題材にSchemeの文法について紹介している。データ構造（リスト）については2章まで出てこない。紹介されている内容は大きく以下になる。
文法
出てくる文法は以下の通り。詳細はもうひとつの Scheme 入門とかScheme によるプログラミング入門で確認できる。
- 式
- 合成式
- 変数
- 合成手続き
- 条件式
- スコープ
- 内部定義
- 高階手続き
- lambda
- let
高階手続きで戻り値として手続きを扱えるのは関数型言語の特徴かな？でも、C言語なら関数ポインタを戻り値にできるから、手続き型でもできるか。そもそも、Schemeは関数型言語の特徴を備えた手続き型言語だそうな*1。
手続き作用の置換えモデル
作用的順序と正規順序が存在する。要は、関数を実行する際に引数の評価を遅延させるかどうかが違い。
作用的順序は処理系の実装で「引数を評価し、作用させる」。つまり、ある関数を実行する際は、まず引数を評価して、評価した値で関数を実行する。そのため、問題1.5のように引数によっては無限ループになる。
一方、正規順序は「完全に展開し、簡約する」。つまり、関数を実行する際は、引数を未評価の状態で関数を展開する（実行するわけではない）。関数の呼び出しが続く限り展開を行って、展開できなくなった時点で引数の評価を始める。そのため、問題1.5のようなケースでは無限ループにならない。理由はifが帰結部か代替部のどちらか一方しか評価しないためである。
再帰的手続き
関数の定義内で自身の関数を呼び出すことを再帰的手続きと言う。また、再帰的手続きによって実装できる演算プロセスには再帰的プロセスと反復的プロセスがある。
再帰的プロセスは普通の関数呼び出しである。アセンブラで言うところのCall。具体的にはスタックを積み上げ続ける。なので、再帰した数だけメモリ空間を消費する。メリットは演算対象の定義とほぼ同じイメージで記述できる点である。当然、可読性も高い。
一方、反復的プロセスは関数呼び出し時に、今までの計算結果を引数として渡すことで、スタックを消費せずに処理できる。アセンブラで言うところのJump。デメリットは、現時点での処理結果を引き回す必要があるため、記述時に頭をひねる必要がある。可動性も下がる。ちなみに、末尾再帰と言ったりもする。
