Scheme プログラミング人門

back

(技術評論社 Software Design誌 2000年 7月号 に掲載された、「Scheme への招待 〜 GNU標準のスクリプト言語入門」の 記事を加筆修正したものです *1)

はじめに

みなさんは Lisp をご存じでしょうか。Lisp は 1950年代後半*2に John McCarthy によって 開発されたプログラミング言語で、 おもに記号処理などの分野で今も利用されています。 Scheme は Lisp から派生した言語のひとつで、 Guy Lewis Steele Jr. および Gerald Jay Sussman によって 1975年に開発されました。Scheme はよく 「Lisp の方言」などと呼ばれますが、Lisp よりも簡単な仕様 で、それでいて複雑なプログラミングが可能なように設計されています。 どのプログラミング言語にも長所と短所がありますが、Scheme の長所には

• 単純で、覚えやすい。
• アルゴリズムをすっきり記述できる。
• リスト処理、木構造の処理がしやすい。

といったことがあります。これに加えて、最近では

• GNU の標準スクリプト言語になっている

という長所も加わりました。あの Gimp が 内蔵しているスクリプト言語は Guile と 呼ばれる Scheme インタプリタの一種であり、ユーザはこれを使っ てバッチ処理を行ったり、イメージに適用する特殊効果をプログラミング できます。いっぽう Scheme の短所は

• 型宣言がないため、エラーが見つかりづらい。
• カッコが多く、慣れるまではプログラムが読みづらい。
• Perl や Tcl/Tk と違い、ひとつの言語仕様にいろいろな実装が存在する。

といったことがあげられます。今回は、Scheme の 2つの長所、「アルゴリズムを すっきり記述できる」「リスト処理がしやすい」という点を利用して、 簡単な XML パーザもどきを 製作してみましょう。今回の記事では例として GNU の Guile を 使いますが、ここに掲載したプログラムは Scheme の標準規格である R5RS に基づいており、ほとんどの Scheme 実装で 動作します。末尾に各実装の特徴と、入手方法を簡単にまとめてあります。
(注: Windows をお使いの方は、Guile のかわりに後述の STk を 使って実行できます)

Scheme を使ってみる

では Scheme 実装のひとつである、Guile を 実際にインストールして使ってみましょう。 Guile のソースコード はGNU の 各ミラーサイト (本家は ftp://ftp.gnu.org/pub/gnu/guile/) から入手できます。 現在の安定バージョンは 1.3.4です (注: 2000年 12月現在は 1.4)。 tarball をとってきたら、ふつうに展開し、

 % ./configure
 % make
 % make install

でインストールできます。この後、ホームディレクトリに .guile という ファイルを作成し、以下のように書いておきます:

 (use-modules (ice-9 readline))
 (activate-readline)

こうしておくと、コマンドライン入力に readline ライブラリを使うため 操作性が向上します。では起動してみましょう。

 % guile
 guile>

Guile のプロンプトが現れました。Scheme はインタプリタ型言語ですので C や Java などと違い、基本的にはコンパイルをする必要がありません。 ユーザの入力したテキストは、読み込まれるとすぐに実行されます。ここで、 たとえば次のような式 (expression) を入力してみましょう。これは (2+3)*5 を計算するプログラムです :

 guile> (* (+ 2 3) 5)
 25

Scheme においては「式の評価 (evaluation)」がプログラムの実行にあたります。 ここでは (* (+ 2 3) 5) という式をインタプリタが評価し、25 という計算結果を返しました。記号「*」や「+」などは Scheme の関数名です。 Scheme インタプリタは関数電卓のように、入力された式を評価しては その計算結果を返すという動作をひたすらくり返します。では次のように 入力してみましょう:

 guile> (define x 4)  … [1]
 guile> (* x 2)       … [2]
 8

式 [1] には define という文字が見えます。この式が評価されると、 インタプリタは新しい変数を定義します (Scheme では変数に値を定義する ことを「束縛 (binding)」と呼びます)。ここでは式 [1] によって変数 x に 4 という数値を束縛し、式 [2] でその値を参照しています。お気づきのように 式 [1] は値を返していません。Scheme においては変数を定義するという 動作やファイル入出力などは、計算をするというよりはむしろ関数の 評価にともなって起こる現象とみなされ「副作用」と呼ばれます。 C や Java など多くの言語ではこのような副作用をひんぱんに 使用しますが、副作用は効率のよいプログラムを可能にする反面、意図しない 随伴現象が起こりやすく、変数の変化が追いにくいという欠点をもっています。 Scheme ではこうした副作用をなるべく使わずにプログラムが 組めるような配慮がなされています。

Scheme の動作

では Scheme の言語仕様の説明に移りましょう。Scheme インタプリタの 動作は、いたって簡単です。

1. 最初に、インタプリタは端末あるいはファイルからの 式の入力を待つ。これはシンボルまたはリストの文字表現である。
2. インタプリタは入力された式を 「Scheme オブジェクト」と呼ばれる内部表現に変換する。
3. この Scheme オブジェクトを以下の規則に従って評価する。 Scheme オブジェクトにはいくつかの型があり、インタプリタは 入力されたオブジェクトの型によって動作を変える (図1):
   1. オブジェクトが数値型や文字列型ならば、それ自身を返す。
   2. オブジェクトがシンボル型ならば、インタプリタはそれを 変数名と解釈し、その変数に現在束縛されている Scheme オブジェクトを返す。
   3. オブジェクトがリスト型ならば、インタプリタはまず その要素すべてを再帰的に評価する。このとき リストの先頭要素が関数型ならば、 残りの要素すべてを引数としてその関数を呼び出し、その値を返す。
4. 評価した値を表示し、1. にもどる。

図 1 「式の評価」

先ほどの例で見てみましょう。(* (+ 2 3) 5) という式が 入力されると、Scheme インタプリタはまずここからメモリ上に リスト型オブジェクトを 作ります。このリストには要素として「*」「(+ 2 3)」 「5」などのオブジェクトが 含まれており、 (+ 2 3) はまたもやリスト型になっています。 オブジェクトの型は、その 字句的な特徴から決められます。「5」や「2」は 数字で始まっているので数値型とみなされ、「*」や「+」 および変数を表す「x」などはすべてシンボル型です (Scheme ではアルファベットでない文字もシンボルに含むことができます)。この 入れ子になったリストを評価するために、インタプリタはまず 3-c. の規 則を適用し、「*」「(+ 2 3)」「5」の 各オブジェクトをそれぞれ再帰的に 評価しようとします。まず内側のリスト (+ 2 3) を先に考えましょう。 このリストの各要素は次のように評価されます:

このリストの先頭要素は関数型オブジェクトになります。Scheme では 関数名と変数名は区別されません。これは Scheme インタプリタによって たまたま最初に「足し算をする」という組み込み関数が 「+」というシンボルに束縛されていただけで、この シンボルに後から数値を束縛してやれば、「+」というシンボルは 変数として使うこともできます。Scheme の関数は、数値や 文字列と同じようにオブジェクトとして扱われているので、このような 芸当ができるのです。さて Scheme インタプリタはこの「2」と「3」という 2つのオブジェクトを「足し算をする」関数に渡し、その返り値を 得ます。これを関数の「適用 (application)」と呼びます。 この関数は数値型オブジェクト「5」を返します。ここ で注意していただきたいのは、「+」という文字表現が表しているものは あくまでシンボル型であって関数型ではないということです。シンボル 型オブジェクトは文字表現をもっていてユーザが直接見たり入力したりで きますが、関数型オブジェクトはそのような文字表現をもっていません。 ユーザはシンボルを評価することによってのみ、関数型オブジェク トを手に入れられるのです。しかしこれだけでは新しい関数が作れない と思われるかもしれません。これについてはあとで解説します。

とにかく、このようにして式 (+ 2 3) を評価した値である数値 「5」が得られました。このように評価は再帰的に行われ、 最終的にはリスト (* (+ 2 3) 5) の各要素が次のように 評価されることになります:

この後かけ算の関数呼び出しが行われ、無事に (* (+ 2 3) 5) が 評価されるというわけです。

さて、Scheme の式はほどんどが以上のような手順で評価されるのですが、 例外もあります。それがたとえば先にあげた define の場合です。リスト の先頭要素が define だと、 Scheme は 2番目の要素 (この例では x とい うシンボル) を評価しません。2番目の要素はシンボルのままで扱われ、 このシンボルに 3番目の値が束縛されるのです。このような特殊な形の式を 「構文 (syntax)」と呼びます。Scheme プログラミングを行うためには いくつかの組み込み関数と、define のようなよく使われる代表的な構文 を覚える必要があります。

関数定義と制御構造

Scheme のもうひとつの特徴は、繰り返しやループ構造をすべて 「再帰呼び出し (recursive call)」によって実現できることです。 じつは Scheme にはほとんどのプログラミング言語でサポートされている while や for といった制御構造がありません。Scheme ではこれらと 同じ機能をすべて再帰呼び出しによって実現することができます。 代表的な例として、与えられた数 n の階乗 n! を計算する関数 fact を定義してみましょう:

 guile> (define fact
 ...      (lambda (n) (if (= n 0) 1
 ...                      (* (fact (- n 1)) n))))
 guile> (fact 5)
 120

Scheme では関数もひとつのオブジェクトなので、関数を定義すると きも変数の定義と同じ define を使います。ただしこの場合は変数に数値 型や文字列型オブジェクトを束縛するのではなくて、関数型オブジェク トを束縛します。しかし、前述したように関数型オブジェクトはユーザ が直接キーボードから入力することはできません。このために Scheme に は lambda という特別な構文が用意されています:

 (lambda (シンボル1 シンボル2 ... シンボルm) 式1 式2 ... 式n)

lambda 構文が評価されると、 与えられた情報から新しく関数型オブジェクトが つくられ、返されます。この関数は m個の引数をとり、式 1 から 式n までをこの順序で評価したあと、最後の式 n の 値をこの関数の値として返すようなものになっています。 渡された引数はローカル変数として、 それぞれ シンボル1 から シンボルm に束縛されます。C 風に書くと:

 (define newproc (lambda (a b c) (proc1 a) (proc2 b) (proc3 c)))

は、

 newproc(a, b, c)
 {
   proc1(a);
   proc2(b);
   proc3(c);
 }

という関数定義をおこなうのと同じと考えることができます。この関数 fact は内部で条件分岐をおこない、 n の値が 0 のときは 1 を返し、 それ以外のときはさらに自分自身を再帰的に呼び出しています。if は 条件分岐をおこなう構文です:

 (if 式1 式2 式3)

まず式1 を評価したあと、その結果が真ならば式2 が、偽ならば式3 が評 価され、その値が返されます。これは C言語における ? 演算子に 似ています。関数 (= x y) は 与えられた 2つの数値 x と y が等しけ れば #t、そうでなければ #f の 真理値型オブジェクトを返します(しかし、式1 の値はべつに 真理値型でなくてもかまいません。Scheme では #f 以外の値は 型にかぎらず、すべて真とみなされるからです)。このようにして fact は n を減らしながら自分自身を繰り返し呼び出して計算を行います。

しかし、再帰呼び出しはふつう 1回の呼び出しごとにメモリ上のスタック 領域を消費するため、無限に自分自身を呼び出しつづけることはできません。 これを解決するために Scheme では「末尾再帰 (tail recursion)」と 呼ばれる形式をサポートしており、無限に続く再帰呼び出しを可能にしています。 以下の例を見てください:

 guile> (define fact-tail
 ...      (lambda (n x) (if (= n 0) x 
 ...                        (fact-tail (- n 1) (* n x)))))
 guile> (fact-tail 5 1)
 120

XML パーザもどきを作る

ここからは実際の XML パーザもどき parsexml.scm を使って説明を進め ていきます。XML の言語構造はタグで囲まれたテキストの中にさらにタグ があり…という具合に入れ子構造をなしています。これは計算機科学で 「木 (tree) 構造」と呼ばれるものです (図2)。

図2 「XML 言語の木構造」

したがってこのデータ構造としてリスト型オブジェクトを使えば、Scheme で効率のよい操作が行えそうです。なにはともあれまず実行してみましょ う。以下のように入力します (あるいは、シェルから % guile -l parsexml.scm と入力することにより直接実行することもできます) :

 guile> (load "parsexml.scm")

ファイルからプログラムを読み込む場合、Scheme インタプリタはこれら の式があたかもこの順序で端末から入力されたかのようにふるまいます。 したがって、このプログラムでは最初に「(define last-char ...)」の部 分が評価されるわけです。「;」以降はコメントとして扱われます。 parsexml.scm を ロードすると関数 parse-xml-file が 定義されますが、これはファイル名を引数として与えると、 その木構造をリストとして返すような関数です。 たとえばファイル test.xml の 「木」を変数 tree1 に束縛するには次のように入力します:

 guile> (define tree1 (parse-xml-file "test.xml"))
 guile> tree1
 (<document> (<title> "sample") (<section> "section" "1")
 (<section> "section" "2" (<subsection> "subsection")))

このリストは入れ子になっていて、XML のタグはリストの先頭にそれぞれ <document> などのシンボル型オブジェクトとして表現され、実際の文章 は記号 "〜" で囲まれている文字列型オブジェクトとして表現されていま す。つぎに同じく parsexml.scm 中で定義されている関数 search-xml を使って、 この tree1 から <subsection> タグを もつ部分木だけを抜き出してみましょう:

 guile> (search-xml (lambda (t) (eq? '<subsection> (car t))) tree1)
 ((<subsection> "subsection"))

関数 search-xml は、 引数として検索対象の木と、ひとつの関数オブジェクトをとります。 search-xml は与えられた条件をみたすような 部分木すべてを tree1 から探しだしてくるのですが、 この関数の便利なところは その検索条件としてなんらかの値や文字列を与えてるのではなく「条件を満 たすときに真を返すような関数」を与えていることです。ここで lambda 構文によって作られている関数は引数 t に 1つの部分木 (リスト) をとり、それが検索条件をみたすとき、 つまりここではリストの先頭に <subsection> シンボルが ついているときに真を返します。search-xml は リスト tree1 中の要素ひとつひとつをこの関数に渡し、それが真を返す 要素のみをピックアップしてリストにします。これは結果として「リスト のリスト」になりますので、この結果には括弧が 2重についています。関 数をオブジェクトとして使うことによって、好みに応じた別の関数を既存 の関数 search-xml に“埋め込む”ことができるのです (図3)。

図3 「関数オブジェクトを埋め込む」

ここで使われている関数 eq? は 2つのシンボルが等しいときに真を返す組み込み関数であり、 car はリストの先頭の要素だけをとりだす組み込み関 数です。parse-xml-file によって返された形式では、 リストの先頭の要素はつねにタグを表すシンボルになっていますから、 先頭のシンボルが <subsection> に 等しいかどうかを調べれば、このリスト t 全体が 該当するものかどうかわかります。<subsection> シンボルの前についている「'」という記号はシンボルの一部ではなく、 このシンボルを「引用する (quote)」ことを表しています。 Scheme の規則ではふつうシンボルは自動的にその変数の中身に 評価されてしまいますが、ここでは関数 eq? に シンボル型のオブジェクトそのものを 定数として渡したいのであって、そのシンボルを評価した内容を渡したい わけではありません。したがって、このようにシンボルを評価させない工 夫が必要になります。同じようにリスト型オブジェクトも 「'」 を使うこと によって、評価させずに定数として扱うことが可能になります。

search-xml に関数を渡せるという利点は、 じつはかなり強力です。これによって 検索ルーチンを作りなおすことなしに、どんな複雑な条件でも検索させることが できます。次の例をみてください:

 guile> (define is-a? (lambda (tag t) (eq? tag (car t))))
 guile> (search-xml
 ...     (lambda (t1)
 ...       (and (is-a? '<section> t1)
 ...            (not (null? (search-xml 
 ...                   (lambda (t2) (is-a? '<subsection> t2)) t1)))))
 ...     tree1)
  ((<section> "section" "2" (<subsection> "subsection")))

これは「<subsection> 木を最低ひとつ含むような <section> 木」を検索したところです。 外側の search-xml に与えられる関数は「リスト t1 が <section> タグをもち、さらにリスト t1 中に 『<subsection> をもつようなリスト』が みつかれば真を返す」というものです。組み込み関数 and は2つ以上の真理値の論理積を求め、not は真理値を反転させます。 null? はその引数が要素をもたない「空」リスト () であるかどうかの検査です。この関数はさらに内部で search-xml を呼び出していますが、(not (null? (search-xml ...))) という部分は search-xml の 検索結果が空リストでない、つまり最低ひとつは <subsection> タグをふくむ木があるかどうかをテストしていることになります。 Scheme プログラミングで非常に強力なのはこのように 必要に応じてその場で関数を生成し、すぐ使用できることです。 この例では、内側の search-xml が呼び 出されるたびに新しい関数オブジェクトが生成されていることになります。 SQL をご存じの方なら、このような書き方は SQL における SELECT 文に似ていると 思われるかもしれません。 Scheme ではこのように「関数オブジェクトを引数として受けとる」ような 関数を作ることでいろいろな操作を一般化した形で書くことができ、 「アルゴリズムがすっきり記述できる」という利点が生まれます。

プログラムの説明

このプログラム parsexml.scm の 簡単な説明をしておきます。 最初に字句解析をおこなうルーチンがあり、ここでファイルから文字列を読み出し、 それをいくつかの「トークン (token)」と呼ばれる文字列型オブジェクトに 切り分けています。ここでは簡単のため、すべてのテキストは英数字で あるとし、タグとテキストの間にはかならず空白あるいは改行がはさまれ ると仮定しています。最初の 3つの関数 last-char, begin-tag?, end-tag? は 切り分けられた文字列オブジェクトが 「<〜>」あるいは「</〜>」という形を しているかどうか判定し、もしそうならばその文字列をシンボルに 変換して返すという関数です。文字列を操作するために string-length や string-ref, string-append, substring といった組み込み関数を使っています。 #\< や #\> は文字型の定数表現 で、string-ref によって文字列型オブジェクトの任意の位置から文字型 オブジェクトを取り出して比較できます。Guile は正規表現によるパター ンマッチングをサポートしているため、それを使えばこれらの処理はもっ と簡単に実現できますが、ここではあえて R5RS で定義されている関数 のみを使いました。

注目していただきたいのは begin-tag? と end-tag? 両方で 使われている and 構文の使い方です。and 構文は 左から引数を評価していきますが、結果が判明した時点の引数を返します。 Scheme においては真理値型の #f 以外の オブジェクトはすべて真と解釈されるため、この and は最後まで 評価が進むと真理値のかわりにシンボルを返すようになっています。この ように Scheme プログラミングでは成功したときにその値を返し、失敗し たときは #f を返すようにしておくと便利です。

get-token1 では、ファイルから文字を読み込むのに read-char 関数や eof-object? 関数、そして「ポート (port) 型」の オブジェクトを扱っています。これは C でいうところの FILE 構造体のようなものと 思ってください。さらに、ここではリスト操作の重要な関数 cons を使用して います。cons は以下の例のように「リストの先頭に新しい要素をひとつ 追加したリスト」を返します:

 guile> (cons 'a '(b c))
 (a b c)

しかし、cons を使って要素を追加していくと、最終的にリストの順序は 追加した順序と逆になってしまいます。これを元にもどすために関数 reverse が使われています。let* という構文は 一時的に使用するローカル変数を束縛し、 新たな変数スコープを作成します。また cond 構文によって 条件分岐をいくつも並べたように書くことができます。

各実装の紹介

最後に、ここで取りあげた以外の Scheme プログラミング環境をいくつか 紹介します。これらはどれも基本的にオープンソースで公開されており、 ユーザがフリーで入手や改造ができるようになっています。ほとんどの実 装は Scheme の標準規格である R5RS に準拠していますが、R5RS は非常 に貧弱な入出力関数しか定義していないため、おのおのに独自の拡張が なされています。

まず Scheme のホームページともいえる URL を紹介します。R5RS をはじ めとする各種のドキュメントや実装の置かれているサイトにリンクされて います: http://www.swiss.ai.mit.edu/projects/scheme/index.html
日本では、 富山大学の木村 巌さんのページ が総合索引としておすすめです。

Scheme の言語仕様としてつねに手元に置いておきたい R5RS は、Suzuki Hisao さんによるすぐれた日本語訳があり、新山のサイトにも置かれています。 この文章の用語もほぼこの訳に従いました: http://tanaka-www.cs.titech.ac.jp/%7Eeuske/scm/r5rs.html

SCM は Aubrey Jaffer 氏によって公開されている Scheme インタプリタ で、実行速度は数ある Scheme インタプリタの中でも最速を誇ります。ま たJaffer 氏は SLIB と呼ばれるライブラリの作者でもあり、これは仕様 のことなる Scheme 実装上で共通のコードを走らせるためのScheme コー ドです。SCM には Hobbit と呼ばれるコンパイラも用意されています。 http://swissnet.ai.mit.edu/~jaffer/SCM.html

STk は Scheme 関数から Tk のインターフェイスを使えるようにしたイ ンタプリタで、Erick Gallesio 氏によって公開されています。Tk を使っ たグラフィカルな開発環境が付属しており、Windows でも動作します。ほ かにも正規表現によるパターンマッチングやソケット通信、C で作成した ライブラリのダイナミックリンクなど多くの機能をそなえています。 http://kaolin.unice.fr/STk/STk.html
(注: STk はこちらにもミラーしておきました。ftp://tanaka-www.cs.titech.ac.jp/home/euske/STk/ なお、STk は新山が研究上のシステムを構築するプラットフォームとしても 使っています。詳しくは Kairai ホームページ をどうぞ)

Bigloo は Manuel Serrano 氏によって公開されている Scheme コンパイ ラで、Scheme ソースコードを C に変換してバイナリを生成します。コン パイラの場合、Scheme のメリットがすべて亨受できるというわけではな く、動的なオブジェクトの変更や一部の末尾再帰などに対応していない部 分もあります。ですが実行速度はインタプリタの 10倍以上であり、実用 的な用途にも十分使用できます。 http://kaolin.unice.fr/bigloo/bigloo.html

また、書籍では Scheme の作者 Sussman らが書いた 「計算機プログラムの構造と解釈 第2版」 (G. J. サスマン, H. エイブルソン, J. サスマン著, 和田 英一訳, ピアソン・エデュケーション発行 2000年 ISBN 4-89471-163-X, 原題: ``Structure and Interpretation of Computer Programs, 2nd Edition'') がおすすめです。これは Scheme プログラミングに限らず、コンピュータサイエンスに 関するとてもよい教科書となっています。

注:

1. 掲載のいきさつ: 4月の中ごろ、技術評論社のある方から 突然メールをいただき、書かせてもらうことになった。なんでも UNIX スクリプト言語の 特集をやるが、Scheme の書き手がいないので、サーチエンジンで Scheme を検索したところぼくの Scheme ページ に引っかかったとかで。

2. 掲載時、ぼくはここを「1970年代」としてました。 70年代に開発されたのは Scheme のほうですね。すみません。