関数型プログラミング事始め (13) リストは全能 - Lisp超入門2

関数型プログラミングがはじめての方へ贈る入門の書
前節：Lispは前置形式　次節：変数と名前 
参考書：
・五味 弘「はじめてのLisp関数型プログラミング」技術評論社(2016)
・大山口 通夫、五味 弘「プログラミング言語論」コロナ社(2008)
・五味 弘「関数型プログラミングと数学(ITと数学)」技術評論社(2021)

Lispの基本データはLispの名前の示す通り、リストです。リストこそがすべてのデータ構造の基本です、たぶん。ここではリストの基本的な操作を紹介します。そしてLispではもちろん、Lisp以外の言語でもリストを使いこなしてください。

(5) Lispのデータ構造: リスト

リストは1,2,3,4,5のようにデータの値が連なる構造を持ちます。リストの定義はこれだけですので、非常にシンプルで、他のデータ構造の基礎になるデータ構造です。

最初にも述べたように、LispはList Processing(リスト処理)から名づけられたプログラミング言語で、リスト処理を基本とする言語です。

それでは早速ISLispでこのリストを経験してみましょう。まずはislispを起動してください。なおISLisp処理系はLisp処理系の導入で紹介していますので参照してください。

> ISLisp Version 0.80 (1999/02/25)
>
ISLisp>

ISLispのトップレベルで、'(1 2 3)と入力してみてください。

ISLisp>'(1 2 3)
(1 2 3)

そうすると(1 2 3)が返ります。これが1,2,3を要素とするリストになります。

リスト操作でデータを取り出すゲッタ関数としては、最初の要素を取り出す関数 car (カー)と2番目以降の要素のリストを返す cdr (クダー)があります。

ISLisp>(car '(1 2 3))
1
ISLisp>(cdr '(1 2 3))
(2 3)

リストを生成するジェネレータ関数には、要素をリストの先頭に繋げたリストを生成する関数 cons (コンス)があります。

ISLisp>(cons 1 '(2 3))
(1 2 3)

car、cdrとconsは逆関数の関係になります。つまり (cons (car x) (cdr x)) = x という関係になり、元に戻ります。

次に要素がない空リストは()のように表します。ここでLispでは空リストと等価なものとしてnil (ニル)という特別なデータを用意しています。つまり()とnilは同じものと思ってください。

以上がLispにおけるリスト処理の基本です。この3個の関数だけでリスト処理が全部行えます。この3個の関数と条件分岐 condまたはif、等価関数eqを加えたものがLispの基本5関数と呼ばれています。

例えば、任意のリストは()とconsで以下のように生成できます。

ISLisp>(cons 1 (cons 2 (cons 3 ())))
(1 2 3)

Lispのトップレベルの入力で'(1 2 3)としたときは、この入力データを受け取ったLispのリーダでは上記のように(cons 1 (cons 2 (cons 3 ())))と解釈することになります。

(参考) 関数名の謎1 car,cdr,nil

ところでリストの先頭の要素を取り出す関数はなぜ car なのでしょうか。cdrやnilもどうしてcdr,nilなのでしょうか。
などconsはconstruct(構成)というイメージはわかるかと思います。

carはContents of Address part of Registerの略で、レジスタのアドレス部の内容という意味になります。cdrはContents of Decrement part of Registerの略で、後半部の内容の意味です。

これだけでは意味不明ですが、リストのcar部とcdr部のポインタからなるコンスセルをIBM704マシンでは1ワードのレジスタで実装していました。コンスセルのcar部を取り出すのが、IBM704マシンの1ワードのアドレス部だったので、上記のように名づけられました。cdr部も同様です。
詳細ははじめてのLisp関数型プログラミングのp.33を参照してください。

nilはラテン語の「無」から名づけられました。ニヒル(nihil)が変化してnilになったようです。

Lispは古典芸能の部類に入ります。このため、過去からの伝統美がありますので、名称も含め、色々なところを暖かい目で鑑賞してください。

その他のリスト処理関数

リスト処理の基本は紹介したようにcar、cdr、consになります。しかしLispでは便利さのためにいろいろなリスト処理関数が用意されています。でもこれらの関数は上記の3個の基本関数から作ることができます。

その関数には、append(リストの連結)やreverse(逆順のリスト生成)などがあります。
詳細はLispは前置形式の「（付録）ISLisp 関数一覧」を参照してください。

ISLisp>(append '(1 2 3) '(4 5 6))
(1 2 3 4 5 6)
ISLisp>(reverse '(1 2 3))
(3  2 1)

なお appanedやreverseはcar,cdr,consのみを使って実装できます。これについては後述します。

（次回予告）Lisp超入門3

次回もOK! ISLisp処理系を使って、Lispの超入門の第3回を紹介する予定です。お楽しみに。

参考：プログラミング言語はどれがお得？(前編）｜五味弘 (note.com)
参考：プログラミング言語はどれがお得？(後編）｜五味弘 (note.com)