SICP 孤読書会 - 1.1 プログラムの要素 (1.1.1 〜 1.1.5)

SICP

プログラム言語は、単純な概念を統合して複雑な概念を構成する手段をもっている。
強力な言語には３つの仕掛けがある。

  • 基本式: 言語が関わる最も単純なものを表す
  • 組合せ法: 単純なものから合成物をつくる。
  • 抽象化法: 合成名に名前をつけ、単一のものとして扱う。

プログラムするときは２つの要素を扱う。

  • データ
  • 手続き

データは処理したい「もの」。 手続きはデータの処理法の記述。


1.1.1 式

式(expression)を入力すると解釈系(インタープリタ)は、その式を評価した(evaluating)結果を表示する。

(+ 1 37 349)

式の並びをカッコで囲み、手続きの作用を表現する式を組合せ(combinations)という。

組合せの値は、演算子が指定する手続きを被演算子の値である引数に作用させて得る。


組合せは入れ子にすることができる

(+ (* 3 5) (- 10 6))


組合せが長くなると人間には分かりづらい。

(+ (* 3
      (+ 2 4)
      (+ 3 5))
   (+ (- 10 7)
      6))


清書系(pretty print)で書くと分かりやすい。 清書系は被演算子が縦に整列するように書く。

どのような複雑な式に対しても解釈系(インタープリタ)は常に同じ動作を繰り返す。

読込 - 評価 - 印字 の繰り返し。

Read - Eval - Print の Loop なため、REPL と略されたりする。

  • Read: 端末から式を読み込む
  • Eval: その式を評価する
  • Print: 結果を印字する
  • Loop: Read、Eval、Print を繰り返す

結果を印字する際には、特にインタープリタに指示する必要はない。
Lisp はすべての式には値があるという約束に従っている。


1.1.2 名前と環境

プログラム言語の重要な点は、

名前を使って計算オブジェクトを指す手段を用意すること。


名前とは、オブジェクトを値(value)とする変数(variable)を識別するもののこと。

Scheme では define を使って名前をつける。

(define size 2)

と入力すると解釈系(インタープリタ)は値 2 と名前 size を対応づける。


一旦、size と 値 2 を対応づけると、名前で値を示すことができる。

size  ;; 評価すると対応づけた値、2 が返ってくる


名前とオブジェクトを対応づけ、後に取り出すため、解釈系(インタープリタ)はこれらを記憶している。

この記憶を環境(environment)という。

計算には他の多くの環境が関わるため、正確には大域環境(global environment)という。


1.1.3 組合せの評価

この小節は重要だと思う。


組合せを評価するには次のことを行う。

  1. 組合せの部分式を評価する
  2. 組合せの最左部分式にある手続き(演算子)を、残りの部分式の値である引数(被演算子)に作用させる


組合せの評価プロセスを達成するには、組合せの各要素の評価プロセスを実行しなければならない。
評価の規則は、再帰的。

組合せに対して、上記の規則を繰り返し適用していくと、評価する必要のない数字列、基本演算子、またはそれ以外の名前など、組合せではない基本的な式の地点へ到達する。

これら基本的な式の値は、以下のように規定する。

  • 数字列の値は、その表す数値とする。
  • 基本演算子の値は、対応する演算子を実行する機械命令の列とする。
  • それ以外の名前の値は、その環境で名前と対応づけられたオブジェクトとする。


環境重要。

(+ x 1)

という式があった場合、記号(+)、記号(x)は環境により意味を与えられる。

環境は評価が行われる文脈を提供する。


式の中には上記の規則とは違った評価規則を持つ式がある。

(define x 3)

もその１つ。特殊形式(special forms)と呼ばれる。

特殊形式は、それぞれに特有の評価規則を持っている。

define以外にもいくつかの特殊形式がある。(ifとか)

Lisp の式の評価規則は、単純な一般規則と少数の特殊形式に特化した規則で出来ている。


1.1.4 合成手続き

define

を使って合成手続き(compound procedure)を定義することができる。

「二乗」の定義はこんなふうに記述することができる。

(define (square x) (* x x))

合成手続きは、他の手続きを組み立てたり、定義する際に利用することができる

x2 + y2 は

(+ (square x) (square y))

引数として２つの数値をとり、それらの二乗の和を作る手続きは、

(define (sum-of-squares x y)
  (+ (square x) (square y)))

と定義することができる。

sum-of-squares を別の手続きを作る際に使うこともできる

(define (f a)
  (sum-of-squares (+ a 1) (* a 2)))

合成手続きは、基本的手続き(+や*など)とまったく同様に利用することができる。


1.1.5 手続き作用の置換えモデル

合成手続きの作用のプロセス

各仮パラメタを対応する引数で取り替え、手続きの本体を評価する。

例をみたほうが分かりやすい。

1.1.4で最後にdefineした f を利用した

(f 5)

を評価してプロセスを確認。

まず、f の本体を取り出す

(sum-of-squares (+ a 1) (* a 2))

仮パラメタaを引数の値5で取り替える。

(sum-of-squares (+ 5 1) (* 5 2))

1.1.3の評価手順にしたがって評価していく

まず、組合せの部分式を評価

  • sum-of-squares -> 環境で対応づけられたオブジェクトに変換される？
  • (+ 5 1) --> 6
  • (* 5 2) --> 10

部分式の評価が終わったら、sum-of-squares を6,10に作用させる。

本体を取り出し、パラメタを引数でおきかえると

(+ (square 6) (square 10))

となる。

同じように評価手順を繰り返していく。

  • + --> 対応する演算を実行する機械命令の列に変換される？
  • (square 6) --> 36
  • (square 10) --> 100
(+ 36 100)

で

136

になる。

上のプロセスを手続き作用の置換えモデル(substitution model)という。

作用的順序と正規順序

1.1.3 で示した方法だけが評価を行う方法ではない。

正規順序の評価というものがある。

  • 作用的順序の評価

    • 1.1.3 の評価方法。
    • 「引数を評価してから、作用させる」評価方法。

  • 正規順序の評価

    • 値が必要になるまで、被演算子を評価しない。
    • 「完全に展開し、簡約する」評価方法。


SICP 孤読書会のメインページはこちら