2018年度未改訂2018年1月21日
[ 前の資料 | 講義ホームページ・トップ | 次の資料 ]
2018年度未改訂
Lisp は John McCarthy1 によって提案されたFORTRAN についで古い高水準プログラミング言語である．数々の方言とその実装があるが，特に有名なものは Common Lisp と Scheme である．"Lisp" は，ひとつのプログラミング言語というよりも，以下のような共通の特徴を持った言語族を表す名前といったほうがよいかもしれない．
ここでは Scheme の簡単な紹介をしながら2分探索木のプログラムまで見ていく．Scheme の処理系も多数利用可能(Scheme 自身は非常に小さい言語なので，実装の多くは独自拡張がされている)だが，Gauche (開発者が川合史朗さんという日本人なので日本語ドキュメントが充実している), Racket (Dr. Racket という専用 IDE がついている)あたりが手軽に使えるだろうか．あとは，JavaScript で実装されていてブラウザで実行できる Biwa Scheme は少し試しに使ってみる分には手軽かもしれない．
以下，Lisp や Scheme という言葉がほとんど同じ意味ででてくるが，一応，以下は Scheme 特有の話で，Lisp 一般の話の場合にのみ "Lisp" と書いているつもりである．
Scheme の概要をプログラム例を交じえて紹介する．二分探索木がプログラムできるための最短ルートを通る．
Scheme には入力を即座に実行して結果を表示する対話的処理系が用意されていて，インタラクティブにプログラムの実行を進めることができる．Scheme では入力された式を値に評価することでプログラムの実行が進むので，対話的処理系は電卓のようなものである．Lisp 系言語の第一の特徴は，演算子や関数は全て前置でしかも部分式毎に括弧 () をつけることである．例えば \(1 + 2 \times 3\) という式は以下のように表される．
> が処理系による入力プロンプトの記号で以降が実際の入力である．次の行に入力された数式の計算結果(値と呼ぶ) 7 が表示されている．この時点で，既に括弧の多さにめげているかもしれないが2，実は，この「前置・括弧づけ」構文のおかげで式が簡潔に書ける場合もある．以下は 1 から 10 までを足す式である．
このように Scheme の + (や他の四則演算)の引数はふたつに限らず好きなだけ(実は0個でもよい!)与えることができる．このことを「+ は可変長引数を取る」という．Lisp/Scheme の構文・ライブラリ関数では様々なものが可変長になっているので，それを知っておくと役に立つ場面が多い．
次は比較演算である．数値を比較する際には =，大小比較には <，>，<=，>= を使う．(C の != 相当は標準ではないので1引数関数 not と組み合わせる．また，数値以外のデータの等しさを判定する際には別の関数を使う．ここに出てきた比較演算はあくまで数値同士の比較である．等しさをデータの種類に限らず比較する eq? や eqv? といった関数もあるが，詳しくは扱わない．)
このように比較演算の結果は真偽値定数 #t, #f で表される．他の基本的なデータとしては，浮動小数点数(3.14)，複素数(1+2i)，有理数(3/5)，文字列("foo")，文字(#\a)などがあるがここでは詳しく紹介しない．また，他の言語にあまりないデータとしてはシンボルと呼ばれるものがある．シンボルについては後ほど詳しく見る．
一般的に関数(+ や = も関数である)を呼ぶ時には (〈関数〉 〈引数式1〉 ... 〈引数式n〉) という形になる．区切りには空白を使う．
Scheme で式の計算結果に名前をつけるには define という構文3を使う．
define は (define 〈識別子〉 〈式〉) という形で，〈識別子〉を〈式〉の計算結果に束縛する．(入力結果は何も出ていないが，定義された名前が表示されることもよくある．) Lisp/Scheme では処理系依存ながら識別子にかなりの種類の記号が使えて，x，a24，Foo などの英数字列だけでなく，x+y12 や a->b，など記号混じりの英数字列，はたまた ^_^ など記号だけからなる列も識別子として使える．Scheme で識別子として使えない記号には，;，括弧 ( )，アポストロフィ '，バッククオート`，#，, などがある．空白がないと区切られないので，このような識別子の範囲が広く取れる．(; は Java や C の // と同じで行末までがコメントになる．)
OCaml と同様に，式の計算結果がまずあって，それに名前を付けるので変数の宣言だけをする，ということはできない．また，そもそも型検査をしないので，変数の型を指定する必要もない．
Scheme の主要なプログラム構成要素も関数である．関数も define を使って宣言する．関数の定義の構文は，
となる．〈パラメータ1〉〜〈パラメータn〉 の値を受け取って，〈式〉を計算してその値を返す．OCaml と同様，特に return などを使う必要はなく計算式のみ書けばよい．例を見てみよう．
> (define (average x y)
(/ (+ x y) 2))
average
> (average 5 7)
6
> (average 10 3)
13/2
> (average 3.14 4)
3.5700000000000003
> (average "2.0" 4)
*** ERROR: operation + is not defined between 4 and "2.0"
...Lisp は型検査を行わないので最後の例のように，おかしな引数を与えても，取りあえず関数が呼ばれ，実際に計算できなくなったところでエラーが発生する．今回は + は文字列に対して定義されていないためにエラーになった．しかし，他の例が示すように，+ や / が実行できる限りは何を与えてもよく，コンパイル時に型で縛られる OCaml, Java と対照的である．
条件によって異なる値を計算したい時にはif式やcond式を使う．まず，if式をみてみよう．if式は
という形で，〈条件〉が真ならば，〈式1〉 の値が，偽ならば〈式2〉の値がif式全体の値になる，というものである．例えば，絶対値を計算する関数 abs は以下のように書ける．
上で「〈条件〉が真ならば」と書いたが，Scheme では #f 以外の値は全て真として扱われる．このことは非常によく活用される．例えば，検索を行うような処理では，単に検索対象の有無を表す #t/#f ではなく，検索対象が見つかった場合にはそれに関する情報(例えば辞書を見出し語によって検索するのであれば，その本文)を返し，見つからなかった場合に #f を返すことにするのがふつうである．#f 以外は全て真なので，検索が成功したかで場合わけをするならば (if (lookup ...) ...) と書ける．OCaml でいうならオプション型を，単に Some に相当するデータと #f を混在させることで実現しているともいえる．これは型検査がないからこそできる芸当ともいえる．
if式はふた通りに分岐するための構文だが，それ以上に分岐したい場合にはcond式を使う．cond式は
という形で，〈条件1〉から〈条件n〉までで最初に真になった条件を〈条件i〉である時に，〈式i〉を全体の値とするものである．最後の〈条件n〉には「それ以外の場合」という意味になるキーワード else を使うことができる．
if も define と同様，括弧でくくられているが関数呼び出しではない特別な構文である．4 Lispの式 (a1 a2 ... an) は，通常，関数 a1 を 引数 a2 ... an で呼ぶという意味で，a2 から an も式だと思って必ず計算するが，a1 が define や if など特別な記号の時には，a2 ... an は計算しないことがある．これは重要で，例えば (if (> a 0) (/ 100 a) -10) という式を考えてみよう．もし，if のあとの3つの式が条件分岐の前に先に計算されてしまうとすると a が 0 の場合にゼロ除算が発生してしまう．(define x 100) にしても(これから定義する) x の値を求めてはいけないのである．
再帰関数は通常の関数と同じように定義してよい．
fact に 0 (や負数)を与えた場合は，この計算は
(fact 0)
→ (* 0 (fact -1))
→ (0 * (* -1 (fact -2)))
→となって止まらず，ついには(式が大きくなり過ぎて)メモリが足りなくなってエラーになってしまう．
式の計算中，値に一時的に(局所的に)名前をつけることができる．これが「let 式」である．let式の構文は
であり，直観的には「〈本体式〉の計算中，〈変数i〉を〈式i〉(の値)とする」という意味で，〈式1〉〜〈式n〉を計算し，その値に〈変数1〉から〈変数n〉という名前をつけ，〈本体式〉の値を計算する．
この〈変数i〉の有効範囲は〈本体式〉だけで，〈本体式〉の外側では使用することができない．
また，〈式1〉〜〈式n〉でも使用できない．
Scheme には let* という let と同様の構文があって，let と形は同じだが，定義は〈変数1〉から順番に行われるので，〈式i〉の中では〈変数1〉〜〈変数i-1〉までを参照することができる．
また，以下のように，関数定義の本体で let を使うこともできる．
Scheme ではdefineやletの〈本体式〉の前に定義を並べることで関数の局所定義(Scheme 用語では 内部定義(internal definition) という)をすることができる．
> (define (cube-sum n)
(define (cube n) (* n n n))
(if (zero? n) 0
(+ (cube n) (cube-sum (- n 1)))))
> (cube-sum 3)
36この例では，再帰的に \(1^3 + 2^3 + \cdots + n^3\) を計算するために，(局所的に)3乗関数を定義している．この式の外側では cube は使用できない．
OCaml を知っていると，Scheme の define と let は，機能が似ているのに使える場所などが微妙に異なっていることに混乱するかもしれない．違いを整理しておこう，
内部定義のdefineは，関数の本体式，let の本体式など限られた場所でしか使えない．よって，複雑な式の途中で関数を定義したいなあ，と思っても define ではできない．
let と匿名関数(Scheme では (lambda (〈パラメータ1〉 ... 〈パラメータn〉) 〈本体式〉) という構文になる)を組み合わせて，以下のように関数を局所的に定義することもできる．
これなら式のどこでも関数を定義することができる．しかし let は再帰的定義には使えない．
let の仲間で，再帰関数を定義するためのに letrec という構文があり，のようなことができる．
letrec で読み替えることができ，上の cube-sum は> (define (cube-sum n)
(letrec ((cube (lambda (n) (* n n n))))
(if (zero? n) 0
(+ (cube n) (cube-sum (- n 1))))))と同等である．(再帰的でなくても常に letrec で読み替えればよい．)
このように書くとトップレベルの define と letrec だけあればいいのではないか，という気がしてくる．ある意味ではその通りであるが，関数定義の入れ子をするのに別の構文を使わなければいけないとしたら，それはそれで不便である．おそらく(ここからは想像に近いが)，Scheme が設計された当時は，関数・手続きと，整数などのふつうデータを区別する(匿名関数もない)言語が一般的であり，関数に名前をつける構文と，データに名前をつける構文(そもそも，データは名前をつける対象ではなく，変数(メモリ)を宣言してそこに書き込むもの，という考えの方が一般的であったはず)を区別する方が自然だったのではないか．
Scheme のトップレベル定義は(OCaml と違って)，同じ名前を二度使うと，書き変わってしまう．例えば，以下のように circle_area 関数のような，トップレベルで定義された別の名前(ここでは pi)を参照する定義を考えてみよう．
さて，pi を再定義すると，実は circle_area の挙動が変わってしまう．
このように，Scheme ではトップレベル定義は書き換えることが可能である．これはインタラクティブ処理系を使っている時には便利で，定義の一部だけを変更したい場合，その定義だけを再入力すればよいからである．(OCaml であれば，再入力したものを参照している全ての定義も入力し直す必要がある．)
また，関数定義のように定義時に計算が伴わない場合，未定義の変数があっても全く構わない(これも定義時に型検査をしないことによる恩恵(？)といえよう)．つまり，上で pi より先に circle_area が定義できる，ということである．(もちろん circle_area が呼び出されるまでには pi が定義されている必要がある．)このことを利用すると，相互に呼び合うような関数—相互再関数—をひとつずつ，別々に定義することができる．以下は，与えられた数が偶数かどうか，奇数かどうかを判定する関数 even? と odd? を相互再帰で定義した例である．
(define (even? n)
(if (zero? n) #t (odd? (- n 1))))
(define (odd? n)
(if (zero? n) #f (even? (- n 1))))このふたつの定義は隣接している必要すらない．
(- 10 20)(- 20 30 40)(- 10)(-)与えられた正整数 \(n\) に対し (\(1^2 + 2^2 + \cdots + n^2\)) を計算する再帰関数 squaresum を定義せよ．(引数\(n\)が負である場合の動作はどう定義してもよい．)
与えられた正整数 \(n\) に対し，\(n\) 番目のフィボナッチ数を計算する再帰関数 fib を定義せよ．(引数\(n\)が負である場合の動作はどう定義してもよい．)
ユークリッドの互除法を使ってふたつの正整数 \(n\), \(m\) の最大公約数を計算する再帰関数 gcd を定義せよ．(引数\(n\)が負である場合の動作はどう定義してもよい．)
(解答5)
Lisp の基本的なデータ構造は リスト(list) である．6
リストは，非常に大雑把にいうとデータをいくつか並べたものであるが，「n 番目の要素」に直接アクセスできる配列とは違い，
Lisp で，リストを作るには list 関数を使う．list 関数は可変長引数を取り，引数の値を並べたリストを作る．
(2 4 6) という表記は，(リストの) 外部表現(external representation) と呼ばれ，入出力のために使われる Lisp のデータの記法である．見ての通り，Lisp ではデータの外部表現に，プログラムと同じく「()でくくられた列」(これを S式(S-expression) という)を使っている．(2 4 6) は「2, 4 ,6 を並べたリスト」の外部表現であるが，これをそのまま処理系に入力するとプログラムとして解釈されてしまう．特に，この形は関数呼び出しなので，2 は関数ではない，などというエラーになる．
この，プログラムとデータに同じ記法を使うというのは，Lisp の非常に面白い(かつ，初心者を混乱させる)点のひとつである．
もちろん作ったリストは変数に格納することもできる．また，リストには違う種類のものを並べてもよいし，入れ子にすることもできる．
> (define a (list 1 2 3))
> (define b (list 1 "one" 3.14))
> (define c (list 0 a b))
> c
(0 (1 2 3) (1 "one" 3.14))最後の c は，入れ子の例で整数 0, リスト (1 2 3)，リスト (1 "one" 3.14) を並べたリストとなっている．
リストの先頭要素を取り出すには組込みの car という関数を使う．
また，与えられたリストの(先頭を除いた)後続リストを取り出すには cdr (クダー)という関数を使う．
さて，後続リストを取る操作を続けるとどうなるかも見ておこう．
> (cdr (cdr a))
(3)
> (cdr (cdr (cdr a)))
()
gosh> (cdr (cdr (cdr (cdr a))))
*** ERROR: pair required, but got ()(cdr (cdr a)) が「a の後続の後続」なので，先頭ふたつを除去した (3) すなわち，3 がひとつ並んだリストになる．さらに後続を取って得られた () は，要素が0個の空のリスト(の外部表現)である．空リストからは先頭要素が取り除けないので，エラーになる．(エラーメッセージの「pairが必要とされている」という部分は，Lisp を理解する上で重要なのだが，今はふれない．)
car と cdr を組み合わせてリストの奥深くの要素を取り出すことは日常茶飯事なので，Scheme では，cadr や caddr といった car と cdr の合成関数が用意されている．
> (cddr a) ;; same as (cdr (cdr a))
(3)
> (caddr a) ;; same as (car (cdr (cdr a)))
3
> (cdddr a) ;; same as (cdr (cdr (cdr a)))
()また，既存のリストの先頭に要素を加えるには cons という関数を使う．
要素を加える，といっても，(cons 100 a) を実行したからといって a の内容が書き変わるわけではなく，単に a の値であるところのリスト (1 2 3) の先頭に 100 を追加したリストを作っているだけ，ということにはくれぐれも注意してもらいたい．
また，与えられたデータが空リストか判定するには null? という関数を使う．空でないリストである(つまり car/cdr を呼んでよい)ことを確かめるには pair? を使う．(「空でないリストである」はやや不正確．)
> (null? (cdr (cdr (cdr a))))
#t
> (null? (cdr (cdr a)))
#f
> (null? (+ 1 1)) ;; (+ 1 1) の値 2 はもちろん空リストではない
#f
> (pair? (cdr (cdr (cdr a))))
#f
> (pair? (cdr (cdr a)))
#t
> (pair? (+ 1 1)) ;; (+ 1 1) の値 2 はもちろん空でないリストでもない
#f上の例のように，リストの要素としては，Scheme のデータであれば何でも並べてもよいが，ここで重要なデータを導入する．それが シンボル(symbol) である．
シンボルは，識別子(変数など，ものの名前)を表すためのデータである．先に登場した x，a24，Foo, x+y12, a->b，^_^ は全て，シンボル(の外部表現)である．シンボルは文字列に近いが，置換や部分文字列検索などができる文字列とは違って，シンボル同士の同一性だけが興味の対象となるデータである．「シンボルの 3 文字目」などといったことは考えない．等しさだけにしか興味がないので，内部的には文字列よりも効率的に表現・実装できる．
シンボルは，名前の前にクオート ' をつけることで作ることができる．
プログラムの文面として与えられた 'a と a は厳格に区別しなければならない．前者はシンボル a を作るための表現，後者は，変数 a の値を取り出すための表現である．
シンボルは，他のデータと同じように変数に格納することができるし，リストの要素とすることもできる．
シンボル同士の同一性は関数 eq? で調べることができる．
「こんな等しいかどうかの比較しかできないデータ，何に使うの？」と思うかもしれないが7，シンボルは後で見るように，OCaml のコンストラクタ，C言語の列挙型のように使える(しかも C と違って整数ではないので間違えて足し算など比較演算以外の演算をしたら，きちんとエラーになってくれる!)ので，データ構造を実現する時には非常に便利である．
少し寄り道になるが，ここで Lisp の特徴である，プログラムの構文とデータに同じ表記が使われることのパワーを紹介したい．まず，以下のように，「外部表現がLispプログラムに見えるようなデータ」を作ることができる．
Lisp 処理系には通常 eval という，データをプログラムとして解釈する(もう少し正確にいうと「与えられたリストから，その外部表現をプログラムだと思って実行する」)関数が用意されている．例えば，上の exp を引数として eval 関数を呼ぶと以下のようになる．
すなわち，exp の値であるところのリスト (+ 1 2 3) をプログラムだと思って実行した値 6 を返しているのである．(第二引数の (scheme-report-environment 5) はおまじないだと思ってください．)
eval は様々な言語に見られる機能だが，多くの場合，プログラムを表すデータとして文字列を使っている．Lisp では，S式というより構造化されたデータを使うので，プログラムではないものを実行してしまう可能性が低くなっている．(とはいえ，きちんと動くプログラムをプログラムで生成するのは難しいものである．)
「シンボルは名前の前にクオートをつけて作る」と説明したが，実は Lisp のクオートには「その後に続くS式を外部表現として持つようなデータを作る」という役割がある．これだけでは何を言っているかわかりにくいと思うので例をいくつか挙げる．
> (define one-to-three '(1 2 3)) ;; same as (list '1 2 3)
> (car one-to-three)
1
> (define complex-list '(+ (/ 2 4) a b)) ;; same as (list '+ (list '/ 2 4) 'a 'b)
> (cadr complex-list)
(/ 2 4)
> (caddr complex-list)
a
> (cadddr complex-list)
bつまり '(1 2 3) は (1 2 3) という外部表現を持つリスト—これは (list 1 2 3) の結果であった—を直接作ることができるのである．
「リンゴが赤い」は6文字の文である
という時のような，意味のある言葉を引用符で括って文字列(データ)と見做す機能を 引用(quotation) と呼ぶ．
引用はクオート記号 ' の後のS式 全体 をデータだとするための機能だが， 擬似引用(quasi-quotation) は，引用中に(データではなく)プログラムとして実行される部分を残したような記法である．日本語の例に戻ろう．例えば，引用符中の英文字は変数でそれが指す内容で置き換えると約束しておくと，
S が「リンゴ」である時「Sが赤い」は6文字である
などと言える．(もちろん，この文章が正しいのは，上の約束のように，どこは引用ではなく意味を考えなければいけないかが事前に示されているおかげである．約束がなければ4文字であろう．)
Lisp では疑似引用をバッククオート`で表し，意味を考えてほしい，すなわち，計算をしてほしい部分にコンマ(アンクオート(unquote) という)をつける．
> (define subj 'apple)
> (define x `(an ,subj is red)) ;; same as (list 'an subj 'is 'red)
> x
(an apple is red)
> (define subj2 '(an apple))
> `(,subj2 is red)
((an apple) is red)擬似引用中の ,subj の部分は変数 subj の値であるところのシンボル 'apple' になったわけである．最後の例で結果が (an apple is red) にならないことには注意したい．
こんなこともできる．
(define (make-quoted-square e) `(* ,e ,e))
> (make-quoted-square 3)
(* 3 3)
> (make-quoted-square (make-quoted-square 3))
(* (* 3 3) (* 3 3))
> `(abs ,(make-quoted-square '(/ 4 2))) ;; same as (list 'abs (make-quoted-square '(/ 4 2)))
(abs (* (/ 4 2) (/ 4 2)))C言語の printf 関数や，Ruby などでみられる，文字列中に計算式を埋め込む機能も疑似引用の一種と考えられる．
執筆中
Lisp のリストは，OCaml でいうなら car と cdr というふたつのフィールドを持つレコードだと考えることができる．このフィールドは実は書き換え可能 (mutable) で，set-car! と set-cdr! という組込み関数で書き換えることができる．[^lisp21]cdr は(基本的に)後続リストを表すので書き換える場合にはリストで書き換えることになる．
[^lisp21:] Scheme では，書き換えを行う関数の名前は ! で終えるという慣習がある．
> (define l1 (list 1 2 3))
> l1
(1 2 3)
> (set-car! l1 5)
> l1
(5 2 3)
> (set-cdr! l1 (list 9 8 7 6))
> l1
(5 9 8 7 6)l1 は当初の定義では 1 が car で (2 3) が cdr であるが，car を 5 で書き換えることで，(5 2 3) に，cdr を (9 8 7 6) で書き換えることで，(5 9 8 7 6) になった．
先頭要素ではないところを書き換えたい場合には，cdr を使って，書き換えたいところまで辿ってから set-car! や set-cdr! を使う．
> (set-car! (cddr l1) 20)
> l1
(5 9 20 7 6)
> (set-cdr! (cdddr l1) (list))
> l1
(5 9 20 7)二番目の例では，(cdddr l1) は (7 6) を示しているが，これの後続 (6) を空リストで書き換えているで，7 で打ち切りになったようなリストになっている．
Lisp のリスト構造と基本操作は OCaml に翻訳して考えると(リストの要素は簡単のため整数に限る)以下のように定義できる．
type list =
Empty
| Cons of {
mutable car: int;
mutable cdr: list;
}
let cons a l = Cons {car=a; cdr=l}
let car l =
match l with
Empty -> invalid_arg "car: argument is empty!"
| Cons of {car = a} -> a
let cdr l =
match l with
Empty -> invalid_arg "cdr: argument is empty!"
| Cons of {cdr = l} -> l
let setcar l a =
match l with
Empty -> invalid_arg "cdr: argument is empty!"
| Cons of pair -> pair.car <- a
let setcar l l' =
match l with
Empty -> invalid_arg "cdr: argument is empty!"
| Cons of pair -> pair.cdr <- l'OCaml に書き換えなどを逐次実行するために e1 ; e2 という形式があったのと同じように，Scheme でも逐次実行のための形式が用意されている．それが begin 構文である．(begin 〈式1〉 ... 〈式n〉) で〈式1〉から順に評価を行い，〈式n〉の値が begin 全体の値となる．\(n-1\)番目の式の値は捨てられるので，ここには通常書き換え(や入出力)などが置かれる．
> (define (swap-fst-snd! l)
(let ((snd (cadr l)))
(begin
(set-car! (cdr l) (car l)) ;; assign the first element into the second slot of l
(set-car! l snd)))) ;; assign the second element into the first slot of l
> l1
(5 9 20 7)
> (swap-fst-snd! l1)
> l1
(9 5 20 7)また，let などのいくつかの構文では，begin を書かなくても式を複数並べて逐次実行することができる．上の begin は省略して，
と書いてもよい．
Lisp をはじめとした，コンパイル時に型検査をしない言語を 動的型付言語(dynamically typed language) という．動的型付言語では，コンパイル時に型検査をしない代わりに，基本的な演算を行う際に引数が適切なものであるかを検査し，適切なものではない場合には例外やエラーを発生させる．動的型付言語では，プログラマにデータの種類を判定するための手段が提供されていることが多い．例えば，Scheme では number? という(#t/#fを返す)関数で，データが数値かどうかを判定することができる．このような関数をしばしば型検査述語と呼ぶ．Scheme での代表的な型検査述語を以下にまとめておく．
| 型検査述語 | 該当する(#t が返る)データ |
|---|---|
boolean? |
#t と #f |
symbol? |
シンボル |
procedure? |
関数 |
pair? |
cons で作られるいわゆる「コンスセル」 (≒ 空でないリスト) |
number? |
数値(整数，有理数，浮動小数点数，複素数など) |
string? |
文字列 |
null? |
空リスト |
型検査述語は，不適切な入力を検出する以外にも，データの種類によって異なる処理を行うようなプログラムを書くのにも有用である．例えば，Java では + を数値の加算だけでなく，文字列の連結にも使うが，このような，引数のデータの種類によって分岐する処理を簡単に書くことができる．一方で，ひとつの関数で深い考えもなくどんなデータが来ても対処できるようにプログラムを書いてしまうと，組み合わせた時に，挙動がわかりづらくなるという欠点もある．
OCaml のような言語でも，ヴァリアントを使って動的型付言語の値の構造をある程度模倣することができる．例えば，真偽値，整数値，(二引数)関数，リストを混ぜて使うのであれば以下のような型定義を行えばよいだろう．
type schemeval =
Boolean of bool
| Integer of int
| Procedure of schemeval * schemeval -> schemeval
| Null
| Cons of {
mutable car : schemeval;
mutable cdr : schemeval
}型検査述語はコンストラクタを検査する関数として実装することができる．
let integerQ v = (* "Q" is for the question mark *)
match v with
Integer _ -> Boolean true
| _ -> Boolean false足し算などの基本的な演算を行う関数は，引数の種類をコンストラクタでチェックしてから実際の演算を行う以下のような関数として表すことができる．
let plus = Proceduce (fun (v1, v2) ->
match v1, v2 with
Integer i1, Integer i2 -> Integer (i1 + i2)
| _, _ -> invalid_arg "plus: invalid argument(s)!")関数は Procedure というコンストラクタがついた(OCaml の)関数なので，匿名関数をコンストラクタに渡す形で書いている．引数 v1 と v2 が Integer かを検査した上で OCaml の足し算 + を使って計算をしている．結果には再びコンストラクタをつけて schemeval 型の値にしている．
以下のように2分木を表現することにする．
(Lf)(Br 〈整数〉 〈左部分木〉 〈右部分木〉)これに対応して，新しい枝や葉を作る関数 newbranch と newleaf，引数が葉/枝かどうかを調べる関数，枝から，部分木や格納された値を取り出す関数を以下のように定義する．
;; constructor functions
(define (newbranch l v r) (list 'Br v l r))
(define (newleaf) (list 'Lf))
;; predicates to see if a given tree is a leaf (or a branch)
(define (leaf? t)
(eq? (car t) 'Lf))
(define (branch? t)
(eq? (car t) 'Br))
;; selector functions
(define (branch-value t) (cadr t))
(define (branch-left t) (caddr t))
(define (branch-right t) (cadddr t))データ表現の約束とこれまでのところが理解できれば，それらの組み合わせとして理解できるだろう．newleaf は，引数が0個の関数として定義している．呼び出しは (newleaf) という形になる．newbranch の引数の順番は他の言語での実装方法にあわせて，左部分木，値，右部分木の順とした．(リストを使った表現で値を先にしたのは整形表示した時にわかりやすそう，くらいの理由である．)引数が葉か枝か判定する関数 leaf? と branch? もデータのリストとしての表現が理解できれば特に難しいことはないはずである．ただし，両関数ともに，引数が非空リストである(つまり，car が適用できる)ことを仮定しているために，誤ってそうでない値に適用した時にはエラーで実行が終了する．引数 t がなんであっても，#t か #f のどちらかを返すようにしたい，という場合には，以下のような定義も考えられる．
and は直観的には論理積なので，この関数の意味は「t がペアで，かつその car がシンボルの時に真となり，それ以外の場合には偽となる」になる．ちなみに，このandは，関数ではなく構文の一種で，左から順に式を評価していって偽(#f)になった時には偽を返す(この場合残りの式は評価されない)，全て真(#f以外)になった時には最後の式の値を返す，というものである．t がペアでない場合には，そもそも (car t) がエラーになってしまうので，その前に (pair? t) を使って，(非空)リストになっていることを確認しているわけである．
どちらの定義を取るかは，やや悩ましいところである．間違った・想定されていない入力に対してはエラーで止まるようにする，というが優先される場合には前者がよいだろう．一方，入力が間違っていたとしても，それが「葉ではない」ことは確かなので，#f を返すことにして，プログラムの実行を止めないようにした方がよい場合もあるだろう．
今後，2分木データの操作は上の関数のみを用いて行うことにする．もちろん，上で決めた表現を念頭に，直接 list や car や cdr で2分木の複雑な操作を書いてもよいのだが，上のように，データを作る関数，データの種類を調べる関数，データから中身を取り出す関数を定義してワンクッション置くのも抽象化のために重要である．例えば，データの表現をあとで変更したくなった場合にも，これらの関数を変更するだけで済む．ただ，Scheme には，car などのデータの中身を直接いじる関数を使わせないように 強制する 仕組みがなく，全てプログラマの注意に頼らなければいけないのが辛いところである．
;; (Recursive) function find, which returns whether given integer n exists in BST t.
(define (find t n)
(cond
((leaf? t) #f)
((branch? t)
(let ((l (branch-left t))
(v (branch-value t))
(r (branch-right t)))
(cond
((= n v) #t)
((< n v) (find l n))
(else (find r n)))))));; (Recursive) function insert, which, given BST t and a new element n, returns
;; a new binary search tree with n.
(define (insert t n)
(cond
((leaf? t)
(newbranch (newleaf) n (newleaf)))
((branch? t)
(let ((l (branch-left t))
(v (branch-value t))
(r (branch-right t)))
(cond
((= n v) t)
((< n v) (newbranch (insert l n) v r))
(else (newbranch l v (insert r n))))))));; Function min, which, given BST t, returns the minimum value stored in t.
;; If t is empty, it signals a run-time error.
(define (min t)
(cond
((leaf? t) (error "Invalid argument" t))
((and (branch? t)
(leaf? (branch-left t)))
(branch-value t))
(else (min (branch-left t)))))
;; (Recursive) function delete, which, given BST t and an element n to
;; be deleted, returns a new binary search tree without n. If n is not
;; stored in t, it returns t as it is.
(define (delete t n)
(cond
((leaf? t) t)
((branch? t)
(let ((l (branch-left t))
(v (branch-value t))
(r (branch-right t)))
(cond
((= n v)
(cond
((and (leaf? l) (leaf? r)) (newleaf))
((and (branch? l) (leaf? r)) l)
((and (leaf? l) (branch? r)) r)
(else
(let ((m (min r)))
(newbranch l m (delete r m))))))
((< n v) (newbranch (delete l n) v r))
(else (newbranch l v (delete r n))))))))min で使われている error 関数は，実行時エラーを表す(実行を中断させる)ための関数である．言語仕様には入っていないが，多くの処理系で利用できる．
構文にさえ慣れれば，どの関数の処理もこれまで見た他言語のものとさほど変わっていない．Scheme の実装によってはパターンマッチ拡張があるので，それを使って書き換えると，もう少しすっきりするように思われる．
短命な2分探索木は，書き換えを行う set-car! を使って，枝の書き換えを行う関数を定義すれば，あとはアルゴリズムは OCaml などでみたものと同じであるので対応が取れるだろう．
枝の書き換え関数として，格納している値を書き換える set-branch-value!，左部分木を書き換える set-branch-left!，右部分木を書き換えると set-branch-right! を用意する．これらは，本質的にはリストの第二要素(cdr の car)，第三要素 (cddr の car)，第四要素 (cdddr の car) を書き換えるので，以下のような定義になる．
;; mutator functions
(define (set-branch-value! t newval)
(set-car! (cdr t) newval))
(define (set-branch-left! t newleft)
(set-car! (cddr t) newleft))
(define (set-branch-right! t newright)
(set-car! (cdddr t) newright));; (Recursive) function insert, which, given BST t and a new element n, returns
;; a new binary search tree with n.
(define (insert t n)
(cond
((leaf? t)
(newbranch (newleaf) n (newleaf)))
((branch? t)
(let ((l (branch-left t))
(v (branch-value t))
(r (branch-right t)))
(cond
((= n v) t)
((< n v)
;; sequential execution without begin
(set-branch-left! t (insert l n))
t)
(else
;; sequential execution without begin
(set-branch-right! t (insert r n))
t))))))cond で述語が成立した時に実行する式も begin なしで複数並べて逐次実行することができる．ここでは set-branch... を実行した後に書き換えられた木 t を返していることになる．
;; (Recursive) function delete, which, given BST t and an element n to
;; be deleted, returns a new binary search tree without n. If n is not
;; stored in t, it returns t as it is.
(define (delete t n)
(cond
((leaf? t) t)
((branch? t)
(let ((l (branch-left t))
(v (branch-value t))
(r (branch-right t)))
(cond
((= n v)
(cond
((and (leaf? l) (leaf? r)) (newleaf))
((and (branch? l) (leaf? r)) l)
((and (leaf? l) (branch? r)) r)
(else
(let ((m (min r)))
(set-branch-value! t m)
(set-branch-right! t (delete r m))
t))))
((< n v)
(set-branch-left! (delete l n))
t)
(else
(set-branch-right! (delete r n))
t))))))let も変数束縛を並べた後に評価する式の部分は begin なしで複数並べて逐次実行することができる．
[ 前の資料 | 講義ホームページ・トップ | 次の資料 ]
1927--2011. Artificial Intelligence (「人工知能」)という用語を提唱したことでも有名である．(その他，計算機科学の黎明期に多大な貢献をしている．Lisp の発明・開発ももちろんそのひとつである．)↩︎
実は Lisp/Scheme プログラマは括弧が目に入っていないという説がある．ただし適切に字下げされているプログラムを読む時に限る．↩︎
Lisp では，特別な機能を持つ構文を 特殊形式(special form) と呼ぶが，proper な Scheme 用語ではないのでここでは単に構文ということにする．↩︎
cond はマクロという機能を使って，実行前に if 式を組み合せた等価な式に展開されるので，厳密にはプリミティブな構文ではない．↩︎
解答例
↩︎そもそも，"Lisp" という名前は list processing に由来しているくらいである．↩︎
本当に比較しかできないわけではなく，文字列・シンボル間の相互変換をするための関数はある．↩︎
Copyright 五十嵐 淳, 2016, 2017, 2018, 2019, 2020