Functional Programming

Scheme の基礎知識 [1]

まずは最初に Hello, World と画面に表示させるプログラムを作りましょう。エディタで次のプログラムを打ち込んでください。ファイル名は hello.scm としましょう。本稿ではファイルの拡張子に .scm を使うことにします。

リスト : Hello, World を表示するプログラム

(display "Hello, World\n")

左右の括弧 ( ) や " の数が合わないとエラーになりますので注意してください。また、Gauche を使う場合、display は小文字で書いてください。空白は何個書いてもいいですが半角文字を使ってください。全角文字はいけません。

入力に誤りがないことを確認して、それでは実行してみましょう。

$ gosh hello.scm
Hello, World
$

うまく実行できましたか。正常に終了すれば、シェルのプロンプトが表示されます。

なお、このプログラムは Scheme の仕様 R7RS では動作しません。Gauche の場合、コマンド gosh にオプション -r7 を指定すると R7RS モードで動作します。

$ gosh -r7 hello.scm
*** ERROR: unbound variable: display
    While loading "./hello.scm" at line 1

プログラムが書かれているファイルのことをソースファイルとか、スクリプトファイル (もしくは単にスクリプト) といいます。R7RS のスクリプトは、ライブラリを読み込む import から始める必要があります。プログラムは次のようになります。

リスト : Hello, R7RS world の表示 (hello_r7.scm)

(import (scheme base) (scheme write))
(display "Hello, R7RS World\n")

(scheme base) は base ライブラリを指定します。ここには Scheme の基本的な機能が定義されています。(scheme write) は write ライブラリを指定します。ここにはデータを出力するための機能 (display など) が定義されています。

$ gosh -r7 hello_r7.scm
Hello, R7RS World
$ gosh hello_r7.scm
Hello, R7RS World

Gauche は最初の import が R7RS の形式と一致すれば、スクリプトを R7RS モードで実行します。本稿は R7RS-small の勉強が主な目的なので、Gauche はできるだけ R7RS モードで起動することにします。

●Scheme (Lisp) はリストが主人公

それでは、このプログラムを分解してみましょう。

このプログラムで気がついたことがあると思います。まず、左右のカッコで閉じられていますね。これは Lisp / Scheme の特徴で、カッコ自身に意味があるのです。これを「リスト (list)」といいます。カッコは半角でなければいけません。

リストはデータを格納することができます。リストの中に格納されたデータを「要素」といいます。上図の場合では、display と "Hello, World" が要素です。要素と要素の間は半角の空白で区切ります。カッコと要素の間は空白で区切らなくても大丈夫です。

一般に、リストは表、一覧表、名簿という意味がありますが、Lisp / Scheme では、カッコに中に要素を一列に並べたものをリストとして扱います。Lisp という名称の由来である「LISt Processor」からもわかるように、Lisp / Scheme の世界ではリストが主人公なのです。

●リストの構造

リストは貨物列車にたとえるとわかりやすいでしょう。車両に相当するものを「コンスセル (cons cell)」とか「ペア (pair)」といいます。貨物列車には多数の車両が接続されて運行されるように、リストは複数のコンスセルを接続して構成されています。ひとつのコンスセルには、貨物 (データ) を格納する「CAR (カー)」という場所と、連結器に相当する「CDR (クダー)」という場所からなっています。次の図を見てください。

上図ではコンスセルを箱で表しています。左側の CAR がデータを格納する場所で、CDR が次のコンスセルと連結しています。今回の例では、先頭のコンスセルの CAR には display というデータが格納され、CDR は次のコンスセルと連結しています。2 番目のコンスセルには CAR に "Hello, World" というデータが格納されています。

このあとに接続されるコンスセルはもうないので、CDR にはリストの終わりを示す特別なデータが格納されます。このデータについては次回以降で詳しく説明しますが、とりあえずリストの終わりを示すデータがあることを覚えておいて下さい。

●関数の実行

リストにはもうひとつ重要な役割があります。それは、あらかじめ決められている処理を実行する機能です。これを「関数 (function)」または「手続き (procedure)」と呼びます。関数は数学で使われている用語ですね。たとえば、2 つの値を足す関数を考えてみましょう。

 f(x, y) = x + y

 f(1, 1) = 2,  f(1, 2) = 3,  f(2, 2) = 4 ...


       図 : 2 つの値を足す関数

関数 f は x と y が与えられると、その値が決まります。Lisp / Scheme の場合、リストが入力されると第 1 要素を関数として取り扱い、定義されている処理を実行します。たとえば、f(1, 2) を Scheme で表現すると (f 1 2) となります。f が関数名で、1 と 2 が関数に与えられる「引数 (argument または parameter)」といいます。引数は「ひきすう」と読みます。これが関数に入力されるデータとなります。

関数名がカッコの中に入っているのが Lisp / Scheme の大きな特徴です。そして、関数が出力する値を「返り値」といいます。f(1, 2) の場合は 3 が返り値となります。最初のプログラムは Hello, World を画面に表示するものです。先頭の要素 display が関数名を表していて、次の要素が関数に与えられる引数です。display は引数を画面に出力する関数なのです。ただし、画面に出力することが display の返り値ではありません。

結果を出力すること以外に、ほかに影響を与える操作を「副作用 (side effect)」といいます。数学の関数には副作用は存在しませんが、コンピュータの場合、画面に出力すること以外にも、いろいろな副作用が存在します。

一般に、関数は値を返しますが、値を返さない関数もあります。これは、副作用を行うことが目的なので、関数と呼ばずに「手続き」といって区別することがあります。簡単にいえば、値を返さない関数を手続き ^[*1] というわけです。本稿では、とくに区別をしないで関数と呼ぶことにします。display がどのような値を返すのかは、あとで説明することにします。

●シンボルと文字列

display のような名前を表すデータを、Lisp / Scheme では「シンボル (symbol)」といいます。シンボルはアルファベットや記号を使って表すことができます。ただし、カッコ ( ) などのような特別な記号をシンボルに含めることはできません。次の例はすべてシンボルです。

 a b c foo bar baz scheme-programming


       図 : シンボルの例

伝統的な Lisp や Common Lisp では、シンボルで使用する英大小文字を区別しません。Scheme の場合、R6RS 以降から英大小文字を区別するようになりました (Gauche は前から区別していました)。したがって、a と A は異なるシンボルとして区別されます。

シンボルはデータや関数など Scheme で操作できる「値」を保持することができます。これに対して、第 2 引数 "Hello, World\n" は二重引用符 (ダブルクォート) で囲まれています。このようなデータを「文字列 (string)」 ^[*2] といいます。文字列は、文書を表すデータと考えればいいでしょう。文字列の中にはアルファベットのほかにも、ほとんどの記号を書くことができます。

文字列中に含まれる \n は改行を表します。このような記号を「エスケープシーケンス」といいます。これは、画面に表示することができない文字を表すのに用いられる方法です。\n のほかによく使われるエスケープシーケンスが「タブ (tab)」を表す \t です。タブはキーボードの左端にある TAB のことです。エディタやワープロで文書を書いているとき、このキーを押すとカーソルがいっきに何文字分か移動しますね。タブは決められた位置までカーソルを移動する働きをします。最初のプログラムを "\tHello, World\n" と変更した場合、次のような動作になります。

$ gosh hello.scm
        Hello, World
$

タブによって表示位置が移動しましたね。とりあえず \n が改行で \t がタブを表すことを覚えておきましょう。

●式の計算

もう少し別のプログラムを見てみましょう。次のプログラムを打ち込んでください。

リスト : 足し算の例

(+ 1 2 3)

いちいちファイルに書くのも面倒なので、直接キーボードから入力することにしましょう。

$ gosh
gosh>   <-- 入力待ちであることを示すプロンプト

$ gosh -r7
gosh[r7rs.user]>

シェルでコマンド gosh を実行すると、Gauche が起動して gosh[r7rs.user]> というプロンプトが表示されます。R7RS モードの場合は gosh[r7rs.user]> と表示されます。この状態からプログラムを入力することができます。入力の最後には必ずリターンキーを押して下さい。Lisp / Scheme では、これを REPL (Read - Eval - Print - Loop) といいます。他の関数型言語やスクリプト言語では、対話モードと呼ぶこともあります。

REPL で (exit) と入力する、または Ctrl + D (Windows の場合は Ctrl + Z) を入力すると、Gauche を終了することができます。exit は Gauche を終了する関数です。exit が実行されると、Gauche の実行を終了してシェルに戻ります。

それでは、先ほどのプログラムを入力してみましょう。

gosh[r7rs.user]> (+ 1 2 3)
6
gosh[r7rs.user]>

6 という値が表示されました。この値を見ればおわかりのように、+ は足し算を行う関数です。引数は 1 と 2 と 3 ですね。これらの引数は整数を表すデータです。関数 + は引数を足し算した結果を返します。

Gauche では、プロンプトが表示されている状態でプログラムが実行されると、その返り値を表示するようになっています。+ という関数に値を表示する機能はありませんので注意してください。したがって、ファイル test.scm に (+ 1 2 3) と書いて実行しても結果は表示されません。

リスト : 結果は表示されない

(import (scheme base))
(+ 1 2 3)

$ gosh test.scm
$

この解決方法は、あとで説明することにしましょう。

それから、数式の書き方にも注意してください。Lisp / Scheme の場合、必ずリストの先頭要素に関数を書くので、1 + 2 + 3 というような私たちがいつも使う数式を入力することはできません。実際に (1 + 2 + 3) を実行するとエラーになります。ご注意ください。

ところで、display の返り値について、まだ説明していませんでしたね。これは、キーボードから最初のプログラムを直接打ち込んでみればわかります。

gosh[r7rs.user]> (display "Hello, World\n")
Hello, World
#<undef>
gosh[r7rs.user]>

最初の Hello, World が display によって画面に出力されたもので、次の #<undef> が display の返り値を表示したものです。display は画面にデータを出力する副作用が目的なので返り値に意味はありません。Scheme の仕様書 (R5RS, R7RS-small) を調べてみても display の返り値は未定義となっています。このような場合、返り値は Scheme 処理系に依存していて、Gauche では #<undef> を返します。

●複雑な式を計算する

それでは、もう少し複雑な計算をしたい場合はどうするのでしょうか。たとえば、10 * 11 + 12 * 13 という計算を行ってみましょう。Lisp / Scheme では、次のようにプログラムすることができます。

gosh[r7rs.user]> (+ (* 10 11) (* 12 13))
266
gosh[r7rs.user]>

さて、だいぶ複雑になりましたね。まずカッコが二重になっていることに驚かれるかもしれません。リストはデータを格納する容器であると説明しました。リストも Scheme で扱うことのできるデータです。したがって、リストの中にリストを格納することができるのです。

上図のように、リストは階層構造を作ることができますが、いちばん上の階層を「トップレベル (top level)」といいます。リストを入れ子にできることが Lisp / Scheme の大きな特徴のひとつです。こうなるとリストを貨物列車にたとえることはできませんね。

もうひとつ大事なことがあります。それは、関数を実行する前に引数の値をチェックすることです。このとき、引数がリストであれば、そのリストをプログラムとして実行します。

(+ (* 10 11) (* 12 13))

引数のリストを実行する

(* 10 11) => 110
(* 12 13) => 156

その結果を + に渡す

(+ 110 156) => 266


図 : 計算を実行する様子

+ の引数はリストなので、まず (* 10 11) を実行します。* は乗算を行う関数です。引数は 11 と 12 の数値ですので、そのまま * に渡されて実行されます。その結果が 110 です。次に、(* 12 13) が実行され、同様に 156 という結果が得られます。その結果を + に渡して 266 という結果が得られるのです。

ここまで説明すれば (+ 1 2 3) をファイルに書いても、実行結果を表示させることができます。いちばん最初のプログラムで説明したように、display は引数を表示する関数でしたね。display を使って結果を表示すればいいのです。

リスト : 計算結果を表示する

(import (scheme base) (scheme write))
(display (+ 1 2 3))
(newline)

display の引数に (+ 1 2 3) を与えます。display が実行される前に引数 (+ 1 2 3) が実行され、その結果 6 が display に渡されて画面に表示されます。newline は改行文字を出力する関数です。Lisp / Scheme はファイルに書かれたプログラムを上から順番に実行します。display を実行したあと、newline が実行されます。

$ gosh test.scm
6
$

このように、display を使って計算結果を表示することができます。

●関数とプログラミング

display, +, * のように、Scheme 処理系にあらかじめ組み込んである関数を「プリミティブ (primitive)」といいます。プログラムを作る場合、単純な処理ならばプリミティブを実行するだけで済むのですが、一般には複数のプリミティブを組み合わせて目的の処理を実現します。

プログラミングは、模型を組み立てる作業と似ています。プリミティブが部品に相当し、それを使って全体を組み立てるのです。ところが、模型が大きくなると、一度に全体を組み立てるのは難しくなりますね。そのような場合、全体をいくつかに分割して、まずその部分ごとに作ります。最後に、それを結合して全体を完成させます。これは模型に限らず、自転車からロケットまであらゆる分野で使われている手法 ^[*3] でしょう。

これは、プログラミングにも当てはまります。実現しようとする処理が複雑になると、一度に全部作ることは難しくなります。そこで、全体を小さな処理に分割して、ひとつひとつの処理を作成します。そして、それらを組み合わせて全体のプログラムを完成させるのです。

ひとつひとつの処理を作成する場合、それらの処理をプリミティブのようにひとつの部品として扱えると便利です。つまり、小さな部品を作り、それを使って大きな部品を作り、最後にそれを組み合わせて全体を完成させるのです。

どのようなプログラミング言語にも、ユーザーが部品を作成して、それを簡単に使うことができるようになっています。Lisp/ Scheme の場合、部品は関数のことを意味します。つまり、Lisp / Scheme では関数を定義していくことでプログラミングを行うのです。

●関数定義

それでは、実際に関数を定義してみましょう。簡単な例として、数を 2 乗する関数を作ります。Scheme の場合、関数を定義するとき define という関数を使います。

リスト : 数を 2 乗する関数

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

さて、リストの中にリストが出てきましたね。通常の関数では、引数である (square x) や (* x x) は実行されるはずです。ところが、define の場合は引数を実行しません。define は関数を定義することが目的なので、与えられた引数を実行しても意味がありません。このように、通常の関数とは違う特別な処理を行う関数を「特殊形式」とか「シンタックス形式」といいます。このほかにも、よく使われるシンタックス形式がいくつかありますが、出番がきたら説明することにします。

define の構文を下図に示します。

define は数式と比較するとわかりやすいでしょう。

それでは、説明は後回しにして実際に実行してみます。

gosh[r7rs.user]> (define (square x) (* x x))
square
gosh[r7rs.user]> (square 4)
16

Gauche の場合、define は正常に関数を定義できたら、関数名のシンボルを返します。square を実行するには、今まで説明したようにリストの先頭に square を、その後ろに引数をセットすれば、square に定義された処理内容を実行できます。

それから、関数定義で使用する引数のことを「仮引数」、実際に与えられる引数を「実引数」といいます。define での定義には x を使っていますので、これが仮引数となります。そして、(square 4) の 4 が実引数となります。

それでは、define について説明します。define に続いて定義する関数名と引数名をリストの中に書きます。関数名と引数名はシンボルを使います。文字列や数値ではいけません。定義された処理内容は関数名で指定したシンボルに格納されます。引数名として与えられたシンボルは、その関数の処理内では「変数」としての働きをします。

そして、最後に処理内容を定義します。今回の処理内容は、(* x x) のひとつですが、define では複数個の処理を定義することができます。その場合は、リストに並べた順に実行していきます。そして、最後に実行された処理の結果を、その関数の実行結果として返します。

●変数とは？

ここで、「変数 (variable)」の話をしましょう。

変数はメモリのある領域に設定されます。これは、プログラミング言語 (この場合は Scheme 処理系) が行ってくれます。設定されたメモリ領域は、変数名を使ってその内容を読み書きすることができます。メモリ領域と変数名の対応もプログラミング言語が面倒を見てくれます。

関数を実行する場合、Scheme 処理系は仮引数に対応するメモリ領域を割り当て、その領域に実引数を書き込みます。変数に値を書き込むことを「代入 (assignment)」 ^[*4] といいます。関数 square では、実行時に仮引数 x が変数として用意され、そこに実引数 4 が代入されます。

それでは、変数の値を読み出す場合はどうするのでしょうか。関数 square の本体を見て下さい。(* x x) となっていますね。ここで、プログラムが実行されるときの規則を思い出して下さい。* が実行される場合、その引数の値をチェックしましたね。それがリストであれば、それをプログラムとして実行しました。ここで、もうひとつ重要な規則を説明します。引数がシンボルの場合、そのシンボルに格納されている値を取り出して実行する関数に渡します。

(defun square (x) (* x x))

(square 4)          ; x <= 4 仮引数に代入

(* x x)             ; 本体の実行

(* 4 4)             ; x の値は 4

16                  ; 実行終了


    図 : 関数 square の実行経過

つまり、変数から値を取り出したい場合は、シンボルをそのまま書けばよいのです。(* x x) は関数 * に 4 と 4 が渡されて 16 という結果が得られます。これが関数の返り値となります。

関数の実行が終了すると、仮引数 x の値は代入する前の値に戻されます。つまり、x の値が 4 と定まっているのは、関数 square が実行されている間だけなのです。「前の値に戻される」ことも重要なことなのですが、このことについては次回以降に説明します。

●まとめ

今回はここまでです。最後に、今まで説明したことについて、簡単に復習しておきましょう。

いままで使ってきたデータの種類には、リスト (list)、整数値 (integer)、文字列 (string)、シンボル (symbol) があります。データの種類を「型 (type)」といいます。このほかにも、「ベクタ (vector)」や「文字 (character)」など重要なデータ型 (data type) がいくつかあります。

Lisp / Scheme では、すべてのデータをまとめて「S 式 (symbolic expression)」または「フォーム (form)」と呼びます。S 式は「アトム (atom)」と「リスト (list)」に分けられます。アトムとは、リスト以外のデータすべてのことを意味します。したがって、整数値や文字列やシンボルはアトムになります。

Lisp / Scheme は S 式の値を計算することで動作します。値を計算することを「評価 (evaluation)」するといいます。評価規則はデータ型によって決められています。Scheme の規則を以下に示します。

1. リスト
   リストの先頭要素を評価し、その値が関数であればそれを実行して結果を返す。たとえばシンボルの場合、その値 (関数) を取り出して実行し、その結果を返す。ほかの要素は引数として関数に渡される。
2. シンボル
   そのシンボルに格納されている値を返す。
3. その他
   自分自身を返す。

たとえば、(+ 1 2 3) を実行する場合、関数 + を実行する前に、引数の 1, 2, 3 を「評価」します。この場合、引数がリストやシンボルでないので、そのまま関数に渡されるのです。評価しても自分自身になるデータ型を「自己評価フォーム」といいます。通常の関数では、引数は必ず評価されることを覚えておいて下さい。

ただし、シンタックス形式の場合は引数を評価しないことがあります。define は引数を評価しませんでしたね。通常の関数は引数を評価するが、シンタックス形式は関数によって違うことに注意して下さい。

次回は「変数」と「評価」について、もう少し詳しく説明します。

●問題

次の関数を定義してください。

1. 引数を三乗する cubic
2. 引数を 1/2 にする half
3. 二つの引数の平均値をとる medium
4. 二つの引数の二乗の平均値をとる square-medium
5. 1 から n までの総和を求める関数 sum n
• 公式 \(1 + 2 + \cdots + n = \dfrac{n(n + 1)}{2}\) を使うと簡単

●解答

gosh[r7rs.user]> (define (cubic x) (* x x x))
cubic
gosh[r7rs.user]> (cubic 3)
27
gosh[r7rs.user]> (cubic 9)
729

gosh[r7rs.user]> (define (half x) (/ x 2))
half
gosh[r7rs.user]> (half 10)
5
gosh[r7rs.user]> (half 5)
5/2
gosh[r7rs.user]> (half 2.5)
1.25

gosh[r7rs.user]> (define (medium x y) (half (+ x y)))
medium
gosh[r7rs.user]> (medium 2 4)
3
gosh[r7rs.user]> (medium 5 6)
11/2
gosh[r7rs.user]> (medium 5.0 6.0)
5.5

gosh[r7rs.user]> (define (square-medium x y) (half (+ (* x x) (* y y))))
square-medium
gosh[r7rs.user]> (square-medium 2 3)
13/2
gosh[r7rs.user]> (square-medium 2.0 3.0)
6.5

gosh[r7rs.user]> (define (sum x) (half (* x (+ x 1))))
sum
gosh[r7rs.user]> (sum 10)
55
gosh[r7rs.user]> (sum 100)
5050
gosh[r7rs.user]> (sum 1000)
500500