初学者が３日で習得できる GAL における Lisp プログラミング

{佐々木建昭（筑波大学・数学系） \atop （１９９４年５月）}

0 はじめに

本小冊子は、数式処理システム GAL （General Algebraic Language / Laboratory ：筆者の研究室で開発中）でのシステム・プログラミングを念頭において、記号処理言語 Lisp を初学者に極めて短期間に分かり易く伝授することを目的に書かれた。 GAL は Lisp を母言語としており、システム・プログラミングには Lisp の知識が不可欠なのである。初学者としては、数式処理はおろか、コンピュータも全く知らない者を想定している。

Lisp とはリストというデータを扱う計算機言語で、本来は数式処理を実現するために考案された。リストは非常に簡単な構造で操作も容易だが、その表現力は極めて高く、文章や３次元位置関係などの複雑な構造のデータを簡潔に表現できる。 Lisp も簡単な言語だが、驚くべき強力な機能を有しており、代表的な計算機言語の一つに数えられている。人工知能なる分野に興味のある学生諸君には必須の知識である。

本稿に述べる Lisp は本来の Lisp ではなく、素人に分かり易い形式に表現方法を変換した Lisp である。この Lisp は GAL 上でしか稼働せず汎用性がないが、文法は Lisp そのものであり、初学者にとっては本来の Lisp より親しみ易いはずである。しかも、本稿の形式の Lisp は言語としては GAL の数式処理言語と非常に似ており、本稿を読了した読者は GAL の言語を容易に習得できよう。

本稿は、 Lisp の本質を素早く伝授するために、記述と説明を必要最小限に押えている。言語を習得するには実際に使用するのが一番であり、当然それはプログラミング言語にも当てはまる。読者には、本稿で Lisp とそのプログラミングの輪郭をつかんだならば、次には実際のプログラミングで実力をつけていただきたい。 Lisp の詳細はその過程で自然と分ってくるだろう。本稿は各章が大体１日で学習できる分量である。全体で４章だが、最後の章は初学者には必ずしも必要でない。第４章では、簡単な記述ながら、かなり程度の高いプログラミング技法を扱う。

なお、コンピュータとプログラミングは麻薬のようなもので、はまると抜けられなくなり、結果的に本来の道から逸脱する人が多く見うけられる。

コンピュータおたくとプログラミング中毒患者にならぬよう注意しよう！

1 リストとアトム

リスト (list) とは順序つき集合のようなものである。実際、リストとその演算は順序つき集合で完全に実現することができる。実際のリストはその要素が次々とリストとなる構造（入れ子構造）をしており、この入れ子構造が数式や文書などの複雑なデータを表現できる秘訣なのだが、基本的には非常に簡単な単位から組み立てられている。本章では、リストの概念の誕生から、言語 Lisp の発明までを足早にたどる。そして、リストで数式をどのように表現するのか、簡単に説明する。

1.1 構造をもつデータ

図１は現在の計算機のメモリ構造を示している。メモリには基本単位があり、各単位には K 桁以下の２進数が収納される。したがって、基本単位で表現できる整数は絶対値が 2^{K−1} 以下に限定される。実数は、 m と e を整数として、 m × 2^{e} の形で表現されるが、これを浮動小数 (floating-point number) という。複素数は二つの浮動小数の組で表現される。当然、実数も複素数も、基本単位で表現できるのは有限個の数のみである。

扱う整数と実数・複素数を、上記のようにメモリの基本単位（のいくつか）で表現できるものに限定するならば、計算機構は単純になる。実際、メモリの基本単位に収納されている二つの実数・複素数に四則演算を施し、メモリの基本単位で表現可能な数で結果を近似して、再びメモリの基本単位に収納するのである。当然、巨大な数どうしを掛けると表現しきれない数となる (オーバーフローする) が、 K = 64 とでもしておけば、実用的科学技術計算で困ることはほとんどない。これが数値計算である。

では、数式はどうであろうか？式や文章は、ごく短いものでもメモリの基本単位には入り切らない。さらに、たとえば多項式は変数・指数・係数から成っており、同じ数でも数式のどの部分にあるかで意味が異なる。同じことは文章についても言える。すなわち、数式や文章は「構造を持つデータ」なのである。

address 収納データ  address 収納データ
１番地データ１１番地１２３
２番地データ２５番地
３番地データ３３番地＊＊＊＊＊
４番地データ４＊＊＊＊＊
５番地データ５５番地４５６７８
６番地データ６７番地
７番地データ７７番地９０１２３
８番地データ８終了
⋮  ⋮  ⋮  ⋮

図１メモリの概念図図２ポインタで連結

1.2 ポインタでメモリを連結する

一体、数式や文章などの構造を持つデータを、図１のような平坦なメモリ構造の上でいかに表現するのだろうか？これは、一見難しい問題に思えるが、実は簡単なアイデアで見事に解決された。前節では番地と収納データは全く無関係として扱ったが、番地も収納データとして扱うのである。収納されたデータが番地であるとき、それをポインタ (pointer) と呼び、ポインタはそれが指す番地へデータが連続していることを意味するとする。ポインタと真のデータの区別は、たとえば「データとして収納された２進数の最初の数字が０なら真のデータを、１ならポインタを表す」とでも決める。データとしての数と記号の区別も同じようにつける。

例として、メモリの基本単位では５桁以下の整数しか表現できないとし、このメモリ構造のもとで長大な整数 1234567890123 を表現してみよう。まず、メモリを図２のように２個ずつ対にし、各対を一組として扱う。次に、上記の整数を次のように分割する。

                            123  45678  90123

いま、１, ５, ７番地は空いているが、３番地には既に他のデータが入っているとしよう。このとき、分割された三つの数を１, ５, ７番地に図２のように収納し、長大な数自体は１番地に収納されたとする。上述のポインタの意味から、これは次のように解釈される。「データは１番地の 123 で始まり、５番地に続いて 45678 で、７番地に続いて 90123 で、それで終了」と。かくして、長い整数が現在のメモリ構造で表現できた。

1.3 点対とリストの概念へ

図２における長大な数の表現を抽象化して、次の形に表す。

           123     •  → 45678     •  → 90123     終了

                 図３長大な数 1234567890123 の「箱表現」

この表現は、ポインタによるメモリの連結を明示して素人にも分かり易いが、長い表現を書くには不便である。そこで、図３を次のように表わす。

                           (123  45678  90123)

この表現をリスト (list) と呼ぶ。リストは、要素がまたリストとなる「入れ子構造」をしていてもよく、以下のように定義される。

• リストの基本単位は図３における一つの「箱」である。箱一つに対応するリストを点対 (dotted pair) とよび、次のように表す。

                          a       b  ⟹ (a . b)

• 点対の前部と後部（上記の a と b ）は、真のデータでもポインタでもよい。 • 点対の後部がポインタのとき、次のように簡単に表す。

                     (a . (b . (c . d))) ⟹ (a b c . d)

• 特に、最後の要素（上記の d ）が図２, ３の終了記号のとき、次のように表す。

                      (a . (b . (c . 終了))) ⟹ (a b c)

• 終了記号は、リストから要素を全て除いたものゆえ、 () とも表わされる。

1.4 多項式をリストで表現してみよう

例１１変数多項式 P (x) = 2x^{5} − 3x^{3} + 4 をリストで表現してみよう。１変数多項式は変数に関する項の和であり、各項は指数と係数の対で指定される。したがって、 P (x) はたとえば次のように表現できる。

(x (5 . 2) (3 . − 3) (0 . 4))  (1)

注釈リストの最初の要素は変数を表し、２番目以降の要素は (指数 . 係数) の形で項を表し、項は指数の大きい順に並べられている。

上例が示すように、構造を持つデータをリストで表現するには、リストとその要素に対し人間が意味をつけてやる必要がある。数式処理システムとは、この意味づけを基に、各演算手順に対応するリストを次々と作っていくプログラムなのである。

多項式表現は (1) に限られる訳ではなく、別の意味づけをすれば別の表現が得られる。たとえば、係数０の項も表示して P (x) = 2x^{5} + 0x^{4} − 3x^{3} + 0x^{2} + 0x + 4 とすれば、

((x . 5) 2  0 − 3  0  0  4)  (2)

と表現できる（第１要素の５は次数を表す）。 (1) は疎な表現と呼ばれ、 GAL で採用されている。 (2) は密な表現と呼ばれ、これを採用しているシステムもある。その他にも多くの表現が可能であるが、実際のシステムで数式をどう表現するかについては、処理効率の良さとプログラミングの容易さとともに、複雑で多岐にわたる数式を全体としてどう調整して混乱なく扱うか？を第一義に考えなければならない。

(1) 式の係数部を多項式で置き換えれば、多変数多項式の表現が得られる。

例２多変数多項式 P (x, y) = (2y^{2} + 1)x^{5} − (3y + 2)x^{3} + 4 を (1) の形式で表現する。

           (x (5 y (2 . 2) (0 . 1)) (3 y (1 . -3) (0 . -2)) (0 . 4))

問題１上記の多変数多項式を「箱表現」してみよ。

1.5 記号の最小単位…アトム

リストを分解していくと、最後にはこれ以上分解できない最小単位に行きつく。これをアトム (atom) という。アトムは “Backus の記法” では以下のように定義される。（以下で、 ⟨⋯⟩ はデータ型 (deta type) を表し、記号 ::= は「左辺は右辺で定義される」、記号 | は「あるいは」、という意味をそれぞれ表す。）

⟨ アトム ⟩ ::= ⟨ 数 ⟩ | ⟨ 記号子 ⟩ | ⟨ 文字列 ⟩
⟨ 数 ⟩ ::= ⟨ 整数 ⟩ | ⟨ 有理数 ⟩ | ⟨ 浮動小数 ⟩ | ⟨ 浮動複素数 ⟩

    ⟨ 記号子 ⟩ ::= apple, SASAKI, JamesBond007 などの文字列（下記を参照）

⟨ 文字列 ⟩ ::= ′′This is a string′′ のように、文字′′と′′で囲まれた文字の列

数 (number) の長さは無制限である。長大な数は、計算機内部ではリストで表現されているが、文法的にはリストでなくアトムとして扱われる。

記号子 (identifier) は英文字（A, a, ⋯, Z, z）と数字（1, 2, ⋯, 9, 0）および特殊文字（∗, /, !, ?, など）から作られる。先頭文字は数字であってはならない（Bond007 はよいが 007Bond はダメ）。また、特殊文字はその前に！をつける必要がある（これ

     をエスケープ記号という）。たとえば、 !*isOK, !*! isOKtoo, Ofcourse!!isOK の

ように使用する。記号子の長さは３０字以内に制限されていることが多い。

文字列 (string) 中の文字はなんでもよいが、文字′′ だけは′′ ′′ と入力する必要がある。記号子にはその値と性質の情報（下記を参照）を付与できるが、文字列には付与できない。文字列は長さに制限がなく、専ら印刷文などに用いられる。

特別な記号子として nil と t がある。 nil は英語で空虚を意味し、リストの終了記号、すなわち空リスト () に使用される。さらに、質問に対する答 False の意味にも用いられる。 t は質問に対する答 True の意味に用いられる。

処理系によっては浮動小数と浮動複素数がなかったり、ときには有理数さえなかったりする。また、大文字と小文字の区別がない処理系もある。

1.6 記号子の値…代入文

記号子に値 (value) を与えたり、取り出したりすることができる（文字列にはできない、念のため）。値の概念は実際のプログラミングにとっては極めて重要である。

記号子に値を与えるには代入記号 := を用いる。たとえば、

                            pi := 3.141593 ;  (3)

と入力すると、記号子 pi に値 3.141593 が与えられる。上記の文を代入文 (assignment statement) という。逆に、記号子 pi の値を取り出すには単に pi と入力すればよい。

pi ; ⟹ 答として 3.141593 が得られる  (4)

上記において、入力の最後の ; は文の終りを意味する終端子 (terminator) である。

1.7 記号の入力と記号評価…′

ここで注意深い人は混乱するだろう。 (4) の入力で pi の値が取り出されるならば、 (3) の入力における pi の値はどうなるのか？一体、記号はどのようにして入力するのか？ Lisp では以下のような規則を定めて混乱が生じないようにしている。

評価規則１入力された記号子は、代入記号 := の左辺に現れない限り、常にその値で置き換えられる（これを記号の評価 – evaluation）という。記号子が := の左辺に現れたときは、例外的に記号評価をしないで、入力記号そのものとして扱う。

評価規則２記号子あるいはリストの直前に引用符′ をつけて入力したときは、引用符に続く記号子あるいはリストをそのまま入力の答とする。

評価規則３数、文字列、および記号子 t と nil だけは特別に入力そのものが値となる（言い替えると、これらの記号を評価した答はその記号そのものである）。

記号子に関しては評価が基本モードであること、すなわち、何もしなければ（′ を付けなければ）値で置き換えられることを銘記しよう。したがって、値を持たない記号子を引用符なしで入力するとエラーになるのである！

たとえば、変数 x の多項式 x^{3} + 2x^{2} − 3 に対する４節のリスト表現を入力し、それを記号子 poly の値とするには、次のようにすればよい（実際のシステムではもっと上手に行なうが…）。

                 poly := '(x ((3 . 2) (2 . 2) (0 . -3)));

1.8 記号処理言語 Lisp

Lisp とはリスト処理を主目的とする計算機言語（計算機に対するリスト処理の種々の命令を文法化して言語化したもの）であり、語源は List Processor である。１９５０年代の末に MIT で J. McCarthy を中心とするグループにより考案された。 Lisp は数学者 A. Church のλ 計算 (Lambda calculus) をベースにしており、数学的なクセがある。

Lisp 処理系とは、ユーザから入力された Lisp の命令をコンピュータの機械語に翻訳し、文法どおりの答が得られるようにしているソフトウェア（計算機プログラム）のことである。非常に複雑なプログラムで、素人が書けるものではないが、多くの処理系が開発され市販されている。 GAL が乗っかっているのは、 Utah 大学の A. C. Hearn 氏らにより文法が整備された Standard-Lisp に基づき、奈良女子大学の加古富志雄氏により開発された NSL (Nara Standard-Lisp) である。 Lisp に関しては、処理系が完全に文法を実現していなかったり、さらに文法自体に多くの流儀があるので注意を要する（たとえば、３章と４章に述べる関数でさえ、いくつかは処理系によって関数名あるいは定義が異なっている）。 NSL は Lisp のなかでは小型の部類に属するが、数式処理を行なうには十分である。 NSL は小型であるだけに高速で、しかも国産システムなので、新しいデータ型を簡単に導入できたりバグがすぐとれるなど、大変便利である。

2 純 Lisp

純 Lisp とは、次節に述べる５つの基本関数と条件文処理機能、関数定義・評価機能、および入出力機能だけを備えた Lisp である。その機能は最小限のものであるが、驚くべきことに、これだけでリストに関する基本的な処理ができるのである（実用的な数値計算などはもちろんできないが）。純 Lisp を学ぶことにより、読者はリスト処理の基本とは何かが分るだろう。

2.1 純 Lisp の５関数

Lisp における関数 (function) とは、引数 (argument) に与えられた数やリストなどのデータに対して作用し、数やリストなどを答として返したり出力命令などを発するものである。リストに関する処理の基本は以下の５つの関数である。

car : １引数関数、引数に与えられた点対の前部（左部）を答として返す
cdr : １引数関数、引数に与えられた点対の後部（右部）を答として返す
cons : ２引数関数、２個の引数を前部と後部とする点対を答として返す
atom : １引数関数、引数がアトムのときのみ t （真： True を意味）を返す
eq : ２引数関数、引数が同じアトムまたはポインタのときのみ t を返す

注釈： atom と eq の答が t でないときは nil （偽： False を意味）が返される。注釈： eq は長大な数に対しては文法どおりに動作しないことが多い（下記を参照）。

例１ car('(a . b)) の答は a,   cdr('(a . b)) の答は b
     car('(a b c)) の答は a,   cdr('(a b c)) の答は (b c)
例２ cons('a,'b) の答は (a . b),   cons('a,'(b c)) の答は (a b c)
例３ atom(3.14159) の答は t,   atom('(a b c)) の答は nil
例４ U の値が数 3.14159, V の値が数 2.71828 のとき、 eq(U,V) の答は nil

U の値がリスト(a b c) のとき、 eq(U,U) の答は t

次の問題を考えてみよ（問題 3,4,5 の解答は以下を読めばわかる）。

問題１ U の値が記号子 a のとき cons(U,nil) の答は？

問題２ U の値がリスト(a) のとき cdr(U) の答は？、 car(nil), cdr(nil) の答は？
問題３ U の値がリスト() のとき atom(U) の答は？、 atom(1.234567890123) の答は？

問題４ U の値がリスト(a b c), V の値がリスト(a b c) のとき eq(U,V) の答は？

問題５ eq(1.2345678901234567,1.2345678901234567) の答は？

（補足１） cons(U,V) は U と V の値を要素とする点対を空メモリのどこかに作る。したがって、リストが外面的に全く同じものであっても、 eq で t と判定されるとは限らない。たとえば、 cons(2,3) を２度実行すると、外面的に同じリスト(2 . 3) が生成されるが、それらはメモリ内の違った場所に作られる。したがって、

                    eq(cons(2,3),cons(2,3)) の答は nil

となる。外面的に同じリストに eq を適用した場合、それらが内部的にも同じリスト（同じポインタをもつリスト）であるときのみ t が答として返り、それ以外は nil が返る。リストの同一性は後に述べる関数 equal で判定すべきである。

（補足２）上の定義によれば、数の同一性は eq で判定できるはずだが、多くの Lisp 処理系では長大な数に対して判定できない。それは、長大な数は計算機内部でリストとして表現されており、 eq は高速に実行するため「メモリ内で同一のアドレスであるか否か」で決められるからである。 eq はこのように定義されるものとした方がよかろう。記号子の場合には、たとえ長くても、入力の際にチェックされて同じ記号子は一つしか作られないから、 eq で同一性が判定できる。

2.2 条件文… if then else

次のような文を条件文 (conditional statement) という。

もし  Cond1(X) が真なら F unc1(X) を答とし、
そうでなくて Cond2(X) が真なら F unc2(X) を答とし、
それ以外は  F unc3(X) を答とする。

このような文はプログラミングでは絶対的に必要だが、 Lisp では次のように書く。

                  if       eq(Cond1(X),t) then Func1(X)
                   else if eq(Cond2(X),t) then Func2(X)
                   else                        Func3(X);

この形式を McCarthy の条件式 (conditional expression) という。

重要な注意条件部（上例で Condk(X) にあたる部分）は t と nil 以外の値になることが多く、 nil でなければ t と解釈される。したがって、上のように書くと正しく働かないことがある。次のように書くと正しく働くので、以後はこのように書くこと。

                       if       Cond1(X) then Func1(X)
                        else if Cond2(X) then Func2(X)
                        else                  Func3(X);

補足１条件文では、 else-if 節はいくら多くつないでもよい。また、上例の最後の行を除いたような文、すなわち最後の行が else if で終る文でもよい。補足２条件文の中に条件文を何重に書いてもよい。ただし、この場合には内部の条件文

は最後が else 節で終了しなければならない（else-if 節で終了するのは論理的におかしい）。たとえば、次の文は文法的に正しい。

             if       Cond1(X) then
                   if Cond1(Y) then Func11(X,Y) else Func12(X,Y)
              else if Cond2(X) then
                   if Cond2(Y) then Func21(X,Y) else Func22(X,Y);

2.3 関数定義… proc 文

本節では、 car や cons などを組み合わせて新しい関数を定義する方法を学ぶ。例として、リスト (a_{1} a_{2} ⋯ a_{m}) と (b_{1} b_{2} ⋯ b_{n}) を合併したリスト (a_{1} a_{2} ⋯ a_{m} b_{1} b_{2} ⋯ b_{n}) を作る関数 append を定義してみよう。

              procedure append(A,B) ==
                        if eq(A,nil) then B
                         else cons(car(A),append(cdr(A),B));

ここで、宣言語 procedure は proc と短縮してもよい。上記において、 A と B を仮引数という。前節の条件文に対する注意を思い起こすと、次のようにも定義できる。

           proc append(A,B) ==
                if A then cons(car(A),append(cdr(A),B)) else B ;

条件部をこのように表すのは簡単で分かり易いので、覚えておくとよいだろう。

Proc 文で定義された関数に対し、仮引数を実際のデータ（これを実引数という）で置き換えて入力すると、その関数が計算される。例として、上記の関数 append に実引数として A = (a1 a2 a3), B = (b1 b2) を与えた場合の計算を追跡してみよう。

             append((a1 a2 a3),(b1 b2))
           = cons(a1, append((a2 a3),(b1 b2)))
           = ........ cons(a2, append((a3),(b1 b2)))  )
           = ................. cons(a3, append(nil,(b1 b2)))  ))
           = .......................... (b1 b2)  )))
           = ................. cons(a3, (b1 b2))  ))
           = ........ cons(a2, (a3 b1 b2))  )
           = cons(a1, (a2 a3 b1 b2))
           = (a1 a2 a3 b1 b2)

関数の計算では、 Lisp 処理系は定義式をそのまま実行するのだが、定義式において関数が現れたときは、まず引数の部分を先に計算していることが分かる。 append の定義式と動き方をじっくり比較検討していただきたい。

2.4 関数と評価規則

まず、関数というものの定義を Backus の記法で与えておこう。

⟨ 関数 ⟩ ::= 記号子 (引数 1, ⋯, 引数 n) なる形式
⟨ 引数 ⟩ ::= ⟨ アトム ⟩ | ⟨ ′ つきのリスト ⟩ | ⟨ 関数 ⟩ | ⟨Proc 文以外の文 ⟩

関数を計算することを Lisp では関数の評価 (evaluation) という。

評価規則４ Lisp では F unc(arg_{1}, ⋯, arg_{n}) なる形式は全て関数とみなされる。 Proc 文以外では、関数は全て評価される（評価が基本モードである）。

評価規則５関数の評価においては、実引数を先頭から順に評価し、それが完了してから関数の定義式を実行する（これを値呼び出し– call by value –という）。

関数の引数を次々と関数で表現することにより、文章などの複雑な構造が関数という非常に簡単な形式で表現できる。リスト構造のデータと共に、これは Lisp の大きな特徴である。計算手順をすべて関数の形で表現する計算機言語を関数型言語という。

前節の append のように、関数の引数部にその関数自身を書き込んで関数定義することを再帰的定義 (recursive definition) という。このような定義法は、数式の計算にとっては極めて自然な方法である。たとえば

\frac{d}{dx}(f(x) · g(x)) = \frac{df(x)}{dx} · g(x) + f(x) · \frac{dg(x)}{dx}

では、左辺の計算がより簡単な右辺の計算に帰着されたとみなせるが、これは積の微分が微分の積で再帰的に定義されていることを意味する。

例５リスト U のコピーを作る関数 copy(U) を定義してみよう。コピーとは、外面的には同じだが、メモリ内部では違った場所に収納されるリストである。

            proc copy(U) == if atom(U) then U
                             else cons(copy(car(U)),copy(cdr(U)));

例６二つのリスト U と V の等価性を判定する関数 equal(U,V) を定義してみよう。

                proc equal(U,V) ==
                     if atom(U) then if atom(V) then eq(U,V)
                                     else nil
                      else if not equal(car(U),car(V)) then nil
                      else        equal(cdr(U),cdr(V)) ;

（注釈） not は t を nil に、 nil を t に変換する関数である（次章を参照）。（注釈）上の定義はアトムの同一性を eq で判定している点で不十分である。

2.5 入出力と計算の実行

入力 (input) については既に各所でふれてきたが、ここでまとめておこう。

⟨ 入力 ⟩ ::= ⟨ アトム ⟩ | ⟨ ′ つきのリスト ⟩ | ⟨ 関数 ⟩ | ⟨ 文 ⟩

入力されたアトムとリストは評価規則１と２と３により、関数は評価規則４と５により、それぞれ評価される。代入文では代入が実行され、 Proc 文では関数が定義される。

次のように入力すると、 [入力] なる入力の答が出力 (output) される。

[入力] ;

答を出力したくないときは、次のように終端子としてセミコロンを２個打ち込めばよい。

[入力] ; ;

なお、入力中にエラーがある場合には、エラーメッセージが出力されて計算は停止する。 Lisp による計算の実行は次のような手順になる。

Proc 文で多数の関数を定義する ; ; ⇓ 問題を文と関数を使って記述する ; （データは引用符′ で入力する） ⇓ 問題に対する答

もちろん、問題をいくつ入力してもよく、問題と問題の間で関数定義を行なってもよい。

問題６リスト U の最後の要素を返す関数 last(U) を定義せよ。問題７リスト U が要素として X を含むならば t を、含まなければ nil を返す関数

member(X,U) を定義せよ。同一性判定は equal で行なえ。問題８リスト U が要素あるいは要素の中のどこかに X を含むならば t を、含まなけれ

     ば nil を返す関数 partp(X,U) を定義せよ。

問題９リスト U が X と等しいか、あるいは要素の中のどこかに X を含むならば、 X と等しい部分をすべて Y で置き換える関数 subst(X,Y,U) を定義せよ。

3 実用的 Lisp

数式処理システムなどの大規模プログラムでは、前章に述べた equal や copy のような関数を何百、何千と定義する必要がある。そして何よりも、データ型検査と数値演算のための高速な関数を必要とする。そのため、実用的 Lisp は汎用性の高そうな関数を多く装備している。本章では、それらの関数の中から重要なものを厳選して簡単に説明する。初学者は本章の関数を使いこなせれば合格である。なお、以下では

X と Y は任意の型のデータを、

U と V は限定された型のデータ（ほとんどがリスト）を、 M と N は数を表すものとする。

また、１変数関数では、 car(X) ⟺ car X のように、 ( ) を省略してもよい。

3.1 質問関数（predicate）

大抵の関数が質問関数として使える（2.2 節の「重要な注意」を参照）。

データ型を検査する関数 atom(X) ２章で説明ずみ。 complexp(X) X が ⟨ 複素数 ⟩ のとき t を返す。 complp(X) としてもよい。 fixp(X) integerp(X) と同じである。 floatp(X) X が ⟨ 浮動小数 ⟩ のとき t を返す。 idp(X) X が ⟨ 記号子 ⟩ のとき t を返す。 integerp(X) X が ⟨ 整数 ⟩ のとき t を返す。 intp(X) としてもよい。 numberp(X) X が ⟨ 数 ⟩ のとき t を返す。 pairp(X) X が ⟨ リスト ⟩ （点対でもよい）のとき t を返す。 rationalp(X) X が ⟨ 有理数 ⟩ のとき t を返す。 ratnp(X) としてもよい。 stringp(X) X が ⟨ 文字列 ⟩ のとき t を返す。

一般の質問関数 eq(X, Y) ２章で説明ずみ。 equal(X, Y) X と Y が同じアトムあるいはリストのとき t を返す。

リストは外面的に同じでさえすれば t が返る。

member(X, U) X がリスト U の要素であるとき True ( t とは限らない) を返す。

要素の同一性判定は equal で行なわれる。

memq(X, U) X がリスト U の要素であるとき True ( t とは限らない) を返す。

要素の同一性判定は eq で行なわれる。

null(X) X が空リスト ()、すなわち nil のとき t を返す。

数に対する質問関数 eqn(M, N) M と N が同じ型の同じ大きさの数のとき True ( t とは限らない) を返す。

数はいくら長大でもよい。

evenp(N) N が ⟨ 偶数 ⟩ のとき t を返す。 minusp(N) N が ⟨ 負の数 ⟩ のとき t を返す。 oddp(N) N が ⟨ 奇数 ⟩ のとき t を返す。 onep(N) N が整数 1 あるいは浮動小数 1.0 のとき t を返す。 plusp(N) N が ⟨ 正の数 ⟩ のとき t を返す zerop(N) N が整数 0 あるいは浮動小数 0.0 のとき t を返す。 greaterp(M, N) M > N であるとき t を返す。 lessp(M, N) M < N であるとき t を返す。 geq(M, N) M ≥ N であるとき t を返す。 leq(M, N) M ≤ N であるとき t を返す。 greaterp(M, N), lessp(M, N), geq(M, N), leq(M, N) はそれぞれ次のように書いてもよい。

M > N, M < N, M >= N, M <= N

3.2 論理演算関数

論理演算関数は、本来の意味の２値論理演算に用いられる以上に、条件文の条件節において、「条件１および条件２および…条件 k ならば」のように用いられる。

and(X_{1}, X_{2},…, X_{n}) X_{1} ⋀ X_{2} ⋀ ⋯ ⋀ X_{n} を返す。 n ≥ 2 でなければならない。 or(X_{1}, X_{2},…, X_{n}) X_{1} ⋁ X_{2} ⋁ ⋯ ⋁ X_{n} を返す。 n ≥ 2 でなければならない。 not(X) X が True ( t とは限らない) なら nil を、 nil なら t を返す。

これらの関数は、次のように内置／前置形式で書いてもよい。

and(X_{1}, X_{2},…, X_{n}) ⟺ X_{1} and X_{2} and ⋯ and X_{n}
or(X_{1}, X_{2},…, X_{n}) ⟺ X_{1} or X_{2} or ⋯ or X_{n}
not(X) ⟺ not X

注意 X_{1} and X_{2} or X_{3} and X_{4} は and( or( and(X_{1}, X_{2}), X_{3}), X_{4}) と、 X_{1} and not X_{2} and X_{3} は and(X_{1}, not(X_{2}), X_{3}) と、それぞれ解釈される。すなわち、 not は and と or より優先的にくくられ、 and と or は同順位として前から順にくくられる。間違えそうなときは関数形式で書いておくのが無難である。

3.3 数値演算関数

数値に関しては、以下のように多くの関数がそろっている。負数の除算の剰余をどうするかなど、細かいことはマニュアルを参照されたい。

abs(N) N の絶対値を返す。 add1(N) N + 1 を返す。 difference(M, N) M − N を返す。 divide(M, N) M/N の商と剰余の点対 (商 . 剰余) を返す。 expt(M, N) M^{N} を返す。 fix(N) N の整数部分を返す。 float(N) N を浮動小数化して返す。 max(N_{1},…, N_{m}) N_{1},…, N_{m} の最大値を返す。 m ≥ 2 でなければならない。 max2(M, N) M と N の大きい方を返す。 min(N_{1},…, N_{m}) N_{1},…, N_{m} の最小値を返す。 m ≥ 2 でなければならない。 min2(M, N) M と N の小さい方を返す。 minus(N) −N を返す。 plus(N_{1},…, N_{m}) N_{1} + ⋯ + N_{m} を返す。 m ≥ 2 でなければならない。 plus2(M, N) M + N を返す。 quotient(M, N) M/N の商を返す。 remainder(M, N) M/N の剰余を返す。 sub1(N) N − 1 を返す。 times(N_{1},…, N_{m}) N_{1} × ⋯ × N_{m} を返す。 m ≥ 2 でなければならない。 times2(M, N) M × N を返す。

minus, expt, quotient, plus, times の各関数は、それぞれ次のように書いてもよい。

−N, M ∗ ∗N あるいは Mˆ N, M/N, N_{1} + ⋯ + N_{m}, N_{1} ∗ ⋯ ∗ N_{m} 数値演算子や代入記号などを混合して用いる場合、それらの優先順位は次のようになっている。

∗ ∗ ˆ > ∗ / > + − > = > < >= <= > not > and or > := ここで、 > は左辺が右辺より高順位であることを示し、順序がつけられてないものは入力順にくくるものとする。

3.4 基本的リスト処理関数

car(U), cdr(U), cons(U, V) ２章で説明ずみ。 cadr(U), etc. cadr(U) = car( cdr(U))。 car と cdr の４個までの組合せがある。

たとえば、 cadadr(U) = car( cdr( car( cdr(U))))。

append(U, V) リスト U の各要素を順序を保ってリスト V の前方に付加する。 assoc(X, U) U は ( (E_{1} . U_{1}) (E_{2} . U_{2}) ⋯ (E_{n} . U_{n}) ) なる形のリスト (連想リスト)。

equal(X, E_{i}) = t ならば (E_{i} . U_{i}) を、そうでなければ nil を返す。

assq(U, V) assoc と同じだが、同一性判定を eq(X, E_{i}) で行なう。 copy(U) リスト U のコピーを作って返す。 delete(X, U) リスト U が equal(X, E) = t なる要素 E を含むとき、最初に現れる E を

U から除いたリストを返す。 U が X を含まなければ U を返す。

intersection(U, V) リスト U と V を集合に見立てたときの積集合にあたるリストを返す。 length(U) リスト U の長さ（要素の個数）を返す。 list(X_{1},…, X_{n}) X_{1},…, X_{n} を要素とするリスト (X_{1},…, X_{n}) を返す。 reverse(U) リスト U の要素を逆順にしたリストを返す。 subst(X, Y, U) リスト U の中に現れる全ての Y を X で置き換えたリストを返す。 union(U, V) リスト U と V を集合に見立てたときの和集合にあたるリストを返す。

3.5 印刷のための関数… print その他

印刷関数は、プログラム中でメッセージなどを印刷するときに使う（次節の例を参照）。

print(X) アトムあるいはリストである X をプリンターヘッドの現在の位置に印刷したあと、

改行してプリンターヘッドを左端へ戻す。

prin1(X) アトム X をプリンターヘッドの現在の位置に印刷する。改行はしない。 terpri( ) 何も印刷せず、改行してプリンターヘッドを左端へ戻す。

3.6 ファイルの使用… input, output 文

大規模プログラムの作成には、ファイル (file) が不可欠である。例１ファイル testprogram から入力し、答をファイル result.test に出力する。

                  output ′′result.test′′ ;  input testprogram ;

注釈ファイル名が特殊文字を含むときは′′ で囲って入力する。上記で、入力ファイルの指定前に出力ファイルの指定を行なう理由は明白であろう。

3.7 プログラム機能…グループ文、 begin 文

「Fortran 流のプログラミングに慣れているのですが、そのようには書けませんか？」とか、「再帰的な関数定義はエレガントだが、それだけで大きなプログラムが書けるの？」と言う人のために、 Lisp はグループ文と begin 文を用意している。

例２数 m と n を引数として入力し、その和と積を計算して、

     「Wa = m+n,   Seki = mn」と印刷する関数 WaSeki を定義する。
             proc WaSeki(m,n) ==
                << prin1(′′  Wa =  ′′); prin1(m+n);
                   prin1(′′ Seki =  ′′); prin1(m*n); terpri() >>;;

例３リストを要素とするリスト U の最長要素の長さを返す関数 longest を定義する。

               proc longest(U) ==
                    begin local ml,l;   ml := length(car U);
                      LP: if null(U:=cdr U) then return ml ;
                          if (l:=length car U) > ml then ml:=l ;
                          goto LP;  end;;
注釈１本章最初の注意により、 length(car(U)) を length(car U) などと書いた。
注釈２ n:=length(car U) > ml と書くと n:=(length(car U) > ml) の意味になる。

例２で、「<< ... >>」なる形式をグループ文という。グループ文では、 << ... >> 内の

各文が先頭から順に評価され、最後の文の評価結果がグループ文全体の答となる。例３で、「begin ... end」なる形式を begin 文という。その仕様は以下のとおりである。

• begin 文では、 goto 文による飛び越しを除いて、先頭の文から順に実行される。

• begin 文では、その文中でだけ有効なプログラム変数（上例では ml と l）を使える。プログラム変数は local a,b,c; のように、 local 文で宣言する必要がある。

• return 文は begin 文の答を返す。単に return; とすると nil が返される。

• goto 文は指定されたラベル（上例では LP）の位置へ実行を移す。ラベルは、トップレベルの文（他の文や関数の中にない文のこと）の前にのみ書くことができ、必ず後ろにコロンをつける必要がある。（goto 文ではコロンは不要。）

• return 文と goto 文は何個でも書けるが、トップレベルに単独で書くか、あるいはトップレベルの条件文の then 節として、またはグループ文の最後の文としてのみ書くことができる。関数の中に書くことは許されない。

• begin 文や条件文の中で begin 文を書いてもよい。

4 本格的プログラミングのための機能

本章は、初学者のレベルを越えて、本格的なプログラミングを目指す人のためのものである。既に読者には Lisp が簡単な言語であることを理解してもらえたと思うが、 Lisp はその簡単さゆえに驚嘆すべき能力を与えられた。それは、 1) 記号と関数の評価機構のユーザへの解放と、 2) データであるリストとプログラムである関数の相互変換性である。本章では、これら以外にも多くの有用な技法を紹介するが、入出力のことなどプロの領域に関することは省略する。

4.0 閑話休題…本来の Lisp と処理系の動き

「本当の Lisp がどんなものか知らないと不安で…」という読者のために。以下に見るように、本来の Lisp では、アトムを除いて全てがリスト形式で表現される。それは、形式的な単純さを越えて、実際的に重要な意味をもつことが後で分かる。

• アトムとリストの定義は本稿と全く同じ。

• 関数 F unc(arg1,…, argk) は (Func arg1 ... argk) とリスト形式で表される。

• 引用符は関数 quote で表される。たとえば、「′a」は (quote a) となる。

• 代入文「a := value ;」も関数 setq で (setq a value) と表される。

• 条件文も関数 cond で表される。たとえば、 2.2 節の条件文は次式となる。

     (cond ((Cond1 X) (Func1 X)) ((Cond2 X) (Func2 X)) (t (Func3 X)))

• 関数定義もまた関数で表される。たとえば、 2.3 節の append の定義は次式となる。

     (de append (A B) (cond ((eq A nil) B) (t ...)))

ここで、 de は関数定義のための関数である。

• グループ文と begin 文もまた関数 progn と prog でそれぞれ表現される。同様に input, output 文も関数で表現されるが、少々複雑である。

Lisp の処理系がどのように動作するか、簡単に説明しておこう。 Lisp 処理系を起動すると、スーパバイザ (supervisor) と呼ばれる関数が動き始める。スーパバイザは入力から、演算、出力、エラー処理まで全てを取り仕切る関数で、処理系を止めるまで動き続けている。スーパバイザは、まずリーダ (reader) と呼ばれる関数にユーザからの入力を待てと命令する。ユーザが何かを入力すると、リーダはそれを読みとり、文法的に正しいかどうかチェックして、計算機内部で処理可能な形に翻訳し、スーパバイザに結果を返す。スーパバイザはその結果をエヴァリュエイタ (evaluator) と呼ばれる関数に渡して評価させる（計算を実行させる）。最後に、計算結果を出力すべきときは、プリンタ (printer) と呼ばれる関数に渡して答を出力させる。そして、ユーザからの次の入力を待つ。この一連の仕事を、 STOP 命令が来るまで繰り返すのである。

4.1 デバッグ機能… trace, untrace

4.2 記号子の性質リスト… put, get, remprop

4.3 鋭いが恐ろしい関数… rplaca, rplacd

4.4 連続領域の利用… mkvect, putv, getv

4.5 関数名を引数とする関数… funcall, etc.

4.6 エラーの復元処理… errorset, error

4.7 Lisp の評価関数… eval

4.8 データとプログラムの相互変換性

Appendix

問題６  proc member(X,U) ==  || X /= nil ||
                   if           eq(U,nil)    then nil
                    else if  equal(X,car(U)) then t
                    else    member(X,cdr(U));;
問題７ proc last(U) ==  || X /= nil ||
            if eq(cdr(U),nil) then car(U) else last(cdr(U));;
問題８  proc partp(X,U) ==  || X /= nil ||
                    if          eq(U,nil)    then nil
                     else if equal(X,car(U)) then t
                     else if partp(X,car(U)) then t
                     else    partp(X,cdr(U));;
問題９ proc subst(X,Y,U) ==
            if       equal(X,U) then Y
             else if  atom(U)   then U
             else cons(subst(X,Y,car(U)),subst(X,Y,cdr(U)));;