Scheme プログラミング人門

(技術評論社 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 インタプリタの動作は、いたって簡単です。

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

図 1 「式の評価」

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

シンボル「`+`」	⇒ 関数「足し算をする」(規則 3-b.)
数値「`2`」	⇒ 数値「2」 (規則 3-a.)
数値「`3`」	⇒ 数値「3」 (規則 3-a.)

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

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

シンボル「`*`」	⇒ 関数「かけ算をする」(規則 3-b.)
リスト「`(+ 2 3)`」	⇒ 数値「5」 (規則 3-c.)
数値「`5`」	⇒ 数値「5」 (規則 3-a.)

この後かけ算の関数呼び出しが行われ、無事に (* (+ 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

関数 fact-tail も fact と同じように階乗を計算する関数ですが、こちらは fact と違い末尾再帰を使用しています。末尾再帰とは、「自分自身の呼び出しが関数の最後に評価される」ような再帰呼び出しをいいます。上の例では、fact-tail 中で呼び出している「内側の fact-tail」の返り値そのものが、この「外側の fact-tail の返り値」になりますので、返り値を覚えておくためにスタックを消費しなくてもよいのです。 Scheme の規格 R5RS には「末尾再帰を使えば、再帰呼び出しは実質的に『引数つき goto』とみなせる」と書かれています。このようにして Scheme では複雑な制御構造をすべて再帰呼び出しのみによって表現することができます。この関数 fact-tail がどのように動くのか考えてみてください。

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")))

<document>
 <title> sample </title>
 <section> section 1 </section>
 <section> section 2 
   <subsection> subsection </subsection>
 </section>
</document>

ファイル test.xml の中身

このリストは入れ子になっていて、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 のほうですね。すみません。

Last Modified: Sat Feb 18 17:25:07 EST 2006 (02/19, 07:25 JST)

Yusuke Shinyama