読者です 読者をやめる 読者になる 読者になる

SICP 孤読書会 - 1.3 高階手続きによる抽象 (1.3.1 〜 1.3.4)

SICP

強力なプログラミ言語は、よくあるパターンに名前をつけて抽象化し、その抽象を使って仕事をする能力を持つ。
抽象化の際、手続きの引数として、数値、文字列などの制限があると抽象化の能力は狭められる。
手続きを引数として取り手続きを値として返す手続きを扱えることにより抽象化の能力は広まる。

手続きを扱う手続きを高階手続き(higher-order procedures)という。

この節では、

  • 高階手続き(higher-order procedures)が強力な抽象機構として役立つこと
  • 言語の表現力を拡大すること

を見ていく。


1.3.1 引数としての手続き

  • aからbまでの整数の和を計算する手続き
  • 与えられた範囲の整数の三乗和を計算する手続き
  • 級数の項の並びの和 \(\frac{1}{1\cdot3}+\frac{1}{5\cdot7}+\frac{1}{9\cdot11}+...\)

を計算する手続きを考える。

これらを実装する際、引数として手続きを利用する。

それにより、共通パターン(抽象)として級数の総和(summation of a series)

\(\sum_{n=a}^b f(n) = f(a)+...+f(b)\)

を導きだすことができる。


問題 1.29 〜 1.33

SICP/ch1/1-29.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-30.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-31.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-32.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-33.scm at master · snufkon/SICP · GitHub

に解答。


1.3.2 lambda を使う手続きの構築

簡単な手続きは lamba を使うことにより定義することができる。

入力に4を足して返す手続きは

(lambda (x) (+ x 4))


lambda によって作られる手続きは define で作られたものと同じ。 (環境で名前に対応づけられてはいないだけ)

(define (plus4 x) (+ x 4))

(define plus4 (lambda (x) (+ x 4)))

は等価。


問題 1.34

SICP/ch1/1-34.scm at master · snufkon/SICP · GitHub

に解答。


1.3.3 一般的方法としての手続き

関数の零点、不動点を探す一般的な方法を見ていく。
また、これらの方法を手続きとして直接表現する方法についても見ていく。

零点 - Wikipedia
不動点 - Wikipedia

1.3.1 同様、引数として手続きを扱うことによりプログラムの表現力が広がる。


問題 1.35 〜 1.39

SICP/ch1/1-35.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-36.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-37.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-38.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-39.scm at master · snufkon/SICP · GitHub

に解答。


1.3.4 値として返される手続き

今度は、値として返される手続きを見ていく。
手続きを返す手続きを作れることにより、プログラムの表現力が更に広がる。

抽象と第一級手続き

合成手続き(関数)は、計算の一般的方法をプログラム言語の要素として表せるため、重要な抽象機構である。
高階手続きがあると、一般的方法を(手続きとして)操作できるようになり、更なる抽象を作り出すことができる。

プログラム言語が計算要素を扱う方法にはいろいろと制限がある。
制限の殆どない要素は第一級(first-class)身分を持つという。

第一級要素は以下の「権利と特権」を持っている。

  • 変数として名前が付けられる。
  • 手続きに引数として渡せる。
  • 手続きの結果として返される。
  • データ構造に組み込める。

Lisp は他のプログラム言語と違い、手続きに完全な第一級身分を授与した。


問題 1.40 〜 1.46

SICP/ch1/1-40.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-41.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-42.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-43.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-44.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-45.scm at master · snufkon/SICP · GitHub
SICP/ch1/1-46.scm at master · snufkon/SICP · GitHub

に解答。


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