##(toc)

1.1. プログラミングの要素

SICPにはすべての強力なプログラミング言語にそなわっている3つの機構を挙 げています．もちろんHaskellにおいても当然この3つの機構がそなわっていま す．

• 基本式：その言語が扱う最も単純な実体を表現するもの
• 組合せ手段：単純なものを組合せて，複雑なものにする方法
• 抽象する手段：組合せに名前を付けて，ひとつのものとして扱う方法

1.1.1. 式

Glasgow Haskell Compiler には ghci という対話モードのインタープリタが 附属しています．ghci とすこし対話してみよう．コマンドラインから ghciとタイプしてみよう．

% ghci    ___         ___ _   / _ \ /\  /\/ __(_)  / /_\// /_/ / /  | |      GHC Interactive, version 6.4.1, for Haskell 98. / /_\\/ __  / /___| |      http://www.haskell.org/ghc/ \____/\/ /_/\____/|_|      Type :? for help.  Loading package base-1.0 ... linking ... done. Prelude>  

Prelude> というプロンプトが表示されれば OK．

そうそう，あれこれ試す前にインタープリタの終了方法をば．終了するには プロンプトが出ている状態で :quit を入力します．

Prelude> :quit Leaving GHCi. % 

再度 ghci を起動して( -v0 オプションを付けると最初のバナーが出ずに すぐにプロンプトが出る)，

% ghci -v0 Prelude>  

Haskell のインタープリタは式を与えられると，それを評価し， その結果を印字します．数字を与えてみましょう．

Prelude> 486 486 

四則演算はどうでしょう．

Prelude> 137 + 349 486 Prelude> 1000 - 334 666 Prelude> 5 * 99 495 Prelude> 10 / 5 2.0 Prelude> 2.7 + 10 12.7 

もちろん，演算子の優先順位もちゃんとあります．

Prelude> 3 + 2 * 5 - 4 9 

括弧ももちろん使えます．

Prelude> (3 + 2) * (5 - 4) 5 

1.1.2. 名前付けと環境

A critical aspect of a programming language is the means it provides for using names to refer to computational objects.

「計算対象に名前を付ける」という機能がプログラミング言語の重要なポイン トです．Haskellでは，一旦計算対象に名前を付けたら，その名前が指し示し ている計算対象が別の計算対象に変えることはできません．

さて，実際に名前をつけてみましょう．っとその前に， Haskell では Scheme の場合とちがい，インタープリタとの対話セッションで は名前付けはできません．Haskell では対話セッションと定義編集は別に行い ます．インタープリタのセッションを終了させてから Emacs を立ち上げます． 編集ファイル名は，とりあえず， sicp112.hs としてください．ファイル名に ついてい拡張子 .hs には意味がありますので，拡張子の.hsは必 ずつけてください．

Prelude> :quit % emacs sicp-1-1-2.hs 

haskell-mode?がインストールされて設定が適切になされ ていれば，Haskellモードで Emacs が起動するはずです．ステータスバーの mode 表示に Haskell の文字があれば OK です．

-E:---  sicp-1-1-2.hs     (Haskell Ind Doc)--L1--C0--All--------------------- 

ステータスバーがこんな感じになっていればいいでしょう．

さて，実際に名前をつけてみましょう．Haskell では名前付けは，= を 使います．

私は調査をどのような居住を行う必要があります

size = 2 

これを使うには，この名前付けをインタープリタにロードします． Emacs 上で C-cC-l (コントロールキーを押しながら c のキーを押す，それか らコントロールキーを押しながら l (エル))をやると，Emacs の画面が2つに 分割されて下半分の領域にghciの対話プロンプトが出ます．

   ___         ___ _   / _ \ /\  /\/ __(_)  / /_\// /_/ / /  | |      GHC Interactive, version 6.4.1, for Haskell 98. / /_\\/ __  / /___| |      http://www.haskell.org/ghc/ \____/\/ /_/\____/|_|      Type :? for help.  Loading package base-1.0 ... linking ... done. Prelude> :load "/home/nobsun/haskell/sicp-1-1-2.hs" Compiling Main             ( /home/nobsun/haskell/sicp-1-1-2.hs, interpreted ) Ok, modules loaded: Main. *Main>  

などと出ていれば OK です．(Emacs の画面の大きさによってはスクロールし てしまって，プロンプトしか見えないかもしれません)

いま名前をつけたものを評価してみましょう．プロンプトの後ろに size とタイプしてリターンキーを押すと size が評価されます．

*Main> size 2 

これを使って計算もできます．

*Main> 5 * size 10 

編集のエリアにもどって(C-xo または編集エリアをクリック)，名前を付けく わえましょう．

size = 2 p = 3.14159 radius = 10.0 

また，C-cC-l をやります.

*Main> :load "/home/nobsun/haskell/sicp/sicp-1-1-2.hs" Compiling Main             ( /home/nobsun/haskell/sicp/sicp-1-1-2.hs, interpreted ) Ok, modules loaded: Main. *Main>  

のようにまたプロンプト *Main> が ghci との対話エリアに表示され るとおもいます．式を入力してみましょう．

*Main> p * radius * radius 314.159 

さらに名前を加えます．

size = 2 p = 3.14159 radius = 10.0 circumstance = 2 * p * radius 

C-cC-l

*Main> circumstance 62.8318 

こんな風に演算結果を指すにも名前を使うことができます．

名前と計算オブジェクトとの対応の集りのことを環境ということがあります． (Haskellでは環境は第一級の計算対象ではないので，プログラミングの際にこ の言葉がでてくることはあまりない．) Haskellでは大域環境(Global Environment)はプログラムをインタープリタに ロードしたときに作られます．式を評価することでは大域環境を変更すること はできません．インタープリタとの対話セッションからは名前を追加できない のはそのためです．

コメントをどうぞ！

1.1.3. 合成式の評価

SICPでは合成式の評価手順を以下のように示している．

• To evaluate a combination, do the following:
  1. Evaluate the subexpressions of the combination.
  2. Apply the procedure that is the value of the leftmost subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands).

先に部分式すべてを評価してから，次に演算子の適用を行うということである． Haskellで評価方法は実は説明しにくい．後の節で関数の話がでてきたところ で説明する．ここではSICPの記述と同じに解釈してもよい．

Haskellでは四則演算は演算子中置記法で書きます．Scheme の

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

という式は，Haskellでは

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

と書きます． 評価結果はおなじです．

% gosh gosh> (* (+ 2 (* 4 6))          (+ 3 5 7)) 390 gosh> (exit) % ghci -v0 *Main> (2 + (4 * 6)) * ((3 + 5) + 7) 390 *Main> :quit % 

これをSICP同様に木にすると以下のようになります．

どこに公務員試験を受けるん

すこし木の形がSchemeとは違いますね．

コメントをどうぞ！

1.1.4. 合成手続

SICP にあるように自乗する関数 square を定義してみましょう． 前にも言ったようにHaskellではインタープリタの対話セッションで 定義を追加できません．emacsを使いましょう．

% emacs sicp-1-1-2.hs 

では square の定義です．

square x = x * x 

square x    =    x   *    x  ↑   ↑   ↑   ↑  ↑   ↑ 自乗   x すわち  x かける x 

と読めますね．Haskell では関数の定義は

<関数名> <仮引数1> ... <仮引数n> = <本体> 

のような形式で書きます．

上の自乗squareの定義を使ってみましょう．すでに書いたように Emacs に Haskell モードが設定されていれば，C-cC-l とやると編集ウィンドウが2つに 割れて片方が編集領域，もう一方がインタープリタとの対話領域になります． 2 の自乗を計算するには，square 2 を評価します．すなわち，プロンプト (*Main> )の後に square 2 と入力してリターンキーを押します．

*Main> square 21 441 *Main> square (2 + 5) 49 *Main> square (square 3) 81 

Haskellでは関数の呼出しは，

<関数> <実引数1> ... <実引数n> 

のように書きます．Haskellでは「関数の呼出し」という表現はあまり使いま せん．「関数の適用」といいます．Haskellでは関数適用の結合力が四則演算 子よりも強いので，square 2 + 5 は (square 2) + 5 に解釈されます．

*Main> square 2 + 5 9 

2つの数の自乗の和を計算する関数 sumOfSquares の定義を追加しましょう． sicp-1-1-4.hs の編集領域にもどって編集します． 名前が sum-of-squares ではないのは Haskellでは名前に'-'文字を使えない からです．

sumOfSquares x y = square x + square y 

前述のように，関数適用の結合力は四則演算子よりも強いので， square x + square y は (square x) + (square y) と同じです．

C-cC-l とやって，sicp-1-1-4.hs をインタープリタにロードしなおします． sumOfSquares 3 4 を評価すると．．．

*Main> sumOfSquares 3 4 25 

さらに

f a = sumOfSquares (a + 1) (a * 2) 

の定義を追加して再ロードして， f 5 を評価すると

*Main> f 5 136 

コメントをどうぞ！

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

置換えモデルの考え方は，Haskellプログラミングでは最も重要な概念です． Haskellでは関数作用の「意味」を定めているのはこの置換えモデルです． Schemeとちがい可変データを持つ関数は存在しないので，このモデルが破綻す ることはありません．

Haskell でも Scheme と同様，関数が引数に適用されるときのプロセスは，置 き換えモデルです．しかし，評価の方法は「完全に展開して，簡約する」とい う正規順序の評価(normal-order evaluation)を行います．

たとえば，

sumOfSquare (5 + 1) (5 * 2)  ⇒ square (5 + 1) + square (5 * 2) ⇒ ● * ● + square (5 * 2)   {● → (5 + 1)} ⇒ 6 * 6 + square (5 * 2) ⇒ 36 + square (5 * 2) ⇒ 36 + ▲ * ▲               {▲ → (5 * 2)} ⇒ 36 + 10 * 10 ⇒ 36 + 100 ⇒ 136 

のように評価が進みます．

コメントをどうぞ！

1.1.6. 条件式と述語

Haskell では条件によって違う値を表すのにはいくつか方法があります． 数値の絶対値を求める関数 abs0 をガードを使う書き方では，

あなたが学校にとどまるべき理由について

abs0 x | x >  0 = x        | x == 0 = 0        | x <  0 = -x 

のようになります． ガードの部分には評価すると論理値になるような式を書 きます．ガードは上から順に評価され，真になったガードに対応する値が採用 されます．どのガードも真にならないような場合には「評価時エラー」になり ます．

abs1 x | x < 0     = -x        | othrewise = x 

最後のガードに，otherwise を置くとこの評価時エラーは起きません． otherwise は Prelude (デフォルトで処理系が読み込むライブラリ)で真値と 定義されています．これは if式を使って書以下のようにも書けます．

abs2 x = if x < 0 then -x else x 

if 式の構文は

if predicate then consequence else alternative

で，必ず then 節と else 節を持ちます．predicate は評価すると真理 値になる式で，これが真の時は consequence がこの if 式の値に，そう でないときは alternative がこの if 式の値になります．

論理値に対する基本演算子は論理積 && と論理和 || があります， 否定関数は，not です．

コメントをどうぞ！

• 練習問題 1.1?
• 練習問題 1.2?
• 練習問題 1.3?
• 練習問題 1.4?
• 練習問題 1.5?

1.1.7. 例：ニュートン法による平方根

ここはほとんどSchemeと同じに書くことができる．

square x = x * x  sqrtIter guess x = if goodEnough guess x                        then guess                       else sqrtIter (improve guess x) x  improve guess x = average guess (x / guess)  average x y = (x + y) / 2  goodEnough guess x = abs (square guess - x) < 0.001  sqrt' x = sqrtIter 1 x 

The sqrt program also illustrates that the simple procedural language we have introduced so far is sufficient for writing any purely numerical program that one could write in, say, C or Pascal. This might seem surprising, since we have not included in our language any iterative (looping) constructs that direct the computer to do something over and over again. Sqrt-iter, on the other hand, demonstrates how iteration can be accomplished using no special construct other than the ordinary ability to call a procedure.

ループのため構文は Haskell にはありません．でも，ちゃんと計算できます (^^)v.

sqrt は標準プレリュードで既に定義されているので，ここでは sqrt' としま す．SICPでは不正確数(inexact number)の計算をさせるために，最初の予想値 を1ではなく1.0としている．Haskellでは型推論によって，sqrt' の計算が倍 精度浮動小数でおこなわれます．上のコードを sicp-1-1-7.hs というファイ ルに保存し，ghci にロードしてから，:type コマンドを使って，sqrt' の型 を知ることができます．

*Main> :type sqrt' sqrt' :: (Fractional a, Ord a) => a -> a 

これは sqrt' の引数の型と返り値の型は一致し，その型は Fractional クラスのインスタンスでありかつ Ord クラスのインスタンスであるというこ とがわかる．型クラスの詳細は別途説明する予定(は未定^^;)です．

上の条件を満す数値型はデフォルトでは Float型とDouble型の2つですが どちらか明示的に宣言されていなければ，Double型になります．

実行結果は，

*Main> sqrt' 9 3.00009155413138 *Main> sqrt' (100 + 37) 11.704699917758145 *Main> sqrt' (sqrt' 2 + sqrt' 3) 1.7739279023207892 *Main> square (sqrt' 1000) 1000.000369924366 

ここで sqrt' の定義に明示的に単精度小数を使うように sicp-1-1-7.hs に 次の型宣言を加える．

sqrt' :: Float -> Float 

再ロードして実行してみると

*Main> sqrt' 9 3.0000916 *Main> sqrt' (sqrt' 2 + sqrt' 3) 1.7739279 *Main> square (sqrt' 1000) 1000.0004 

となる．

コメントをどうぞ！

• 練習問題 1.6?
• 練習問題 1.7?
• 練習問題 1.8?

1.1.8. ブラックボックス抽象としての手続

The importance of this decomposition strategy is not simply that one is dividing the program into parts. After all, we could take any large program and divide it into parts -- the first ten lines, the next ten lines, the next ten lines, and so on. Rather, it is crucial that each procedure accomplishes an identifiable task that can be used as a module in defining other procedures.

SICPの 1章，2章では関数適用の置換えモデルで意味を与えられる範囲ですべ てのプログラミングを行っています．置換えモデルの計算では，原則としては 計算の結果は部分式の評価の順には依存しません．これは命令文を書かれた順 序にしたがって実行する「普通の」プログラミングとは違います．したがって， 行ごとに分けて「上から順に」見ることが重要なのではありません．

Haskellでも where 節を使って内部定義を書けます．たとえば，

sqrt :: Float -> Float sqrt x = sqrtIter 1.0 x  sqrtIter :: Float -> Float -> Float sqrtIter g x | goodEnough g x = g              | otherwise      = sqrtIter (improve g x) x  goodEnough :: Float -> Bool goodEnough g x = abs (square g - x) < 0.001  imporve :: Float -> Float -> Float improve g x = average g (x / g)  square :: Float -> Float square x = x * x  average :: Float -> Float -> Float average x y = (x + y) / 2 

という定義を

sqrt :: Float -> Float sqrt x = sqrtIter 1.0 x   where     sqrtIter g x | goodEnough g x = g                  | otherwise      = sqrtIter (improve g x) x     goodEnough g x = abs (square g - x) < 0.001     improve g x = average g (x / g)     square x = x * x     average x y  = (x + y) / 2 

のように書くことができます．sqrtIter，goodEnough, improve の第二引数は 常に sqrt の第1引数になりますので，

sqrt :: Float -> Float sqrt x = sqrtIter 1.0 x   where     sqrtIter g | goodEnough g = g                | otherwise    = sqrtIter (improve g)     goodEnough g = abs (square g - x) < 0.001     improve g = average g (x / g)     square x = x * x     average x y  = (x + y) / 2 

(2006-03-02) 以下の部分は筆者の勘違いでした． 「where 節のネスト?」を見てください．

ただし，Haskell の where 節はトップレベル でのみ使用でき，ネストさせることはできないことに注意してください． ネストさせたいような場合には，let 式を使います．

コメントをどうぞ！

補足：where節のネスト

2006-03-02

##(include "/Haskell/SICP/nesting-where")