Lisp入門(Common Lisp版APG4b)第1章

1章

1.00 はじめに

APG4bになるべく近づけて書きました。必ずAPG4bを同じ場所を参照してください。特に問題はサンプルと解答例しかありません。
Lispでの重要キーワードをそれなりに入れましたが不足や修正があればコメントお願いします。
(発展的)と書かれている節は発展的な内容が含まれます。

プログラム言語

AtCoder公式APG4bではC++という言語を用いて解説しています。この文書ではLispという言語のうちの一つ、Common Lispでの解説をします。
Lispは関数型プログラミング言語の一つで、派生して様々な言語が方言として生まれました。この方言は例えばclojure、schemeなどがあります(参考:付録-様々なLisp)。この文書ではそのうちの一つ、Common Lispという言語について書いています。

プログラムの実行方法

APG4b(やそのいくつかの派生)ではコードテストでの利用を推奨していますがLispにおいては手元に環境があったほうが良いです。
理由として、Common Lispの代表的な見た目である大量の括弧の対応を見やすくする点があります。慣れないうちは括弧の対応を間違えやすく、テキストボックスではバグを見逃す原因になります。
環境設定については付録に記しました。

REPL

LispではREPL(Read-Eval-Print-Loop)という逐次実行システムを用いてプログラムを組むことがほとんどです。これはプログラムの一部分のみを実行することでプログラムの作成と修正を簡単に行うことができます。

問題提出練習

以下のコードをソースコードのテキストボックスにコピー、ペーストしましょう。
言語を"Common Lisp(SBCL2.0.3)"に変更しておいてください。

(format t "Hello, world!~%")

1.01 出力とコメント

プログラムの基本形

次のコードはCommon Lispでの何もしないコードです。

C++等の言語とは違いmain関数等は書く必要はありません。

出力

先ほどのコードを見てみましょう。

(format t "Hello, world!~%")

このformatは文字を出力(画面に表示)する関数です。関数はコンピュータに対する指示の塊であり、format関数であれば画面に何かの文字を表示する機能があります。

複数の出力

formatを複数並べることで複数の出力を行うことができます。

(format t "a")
(format t "b~%")
(format t "cd~%")

この~%は改行文字を意味する記号です。
formatは~から始まるものは全てこの指示記号です。~自体を出力するには~~とします。

文字列の出力

文字列を出力するには~Aを使います。そして出力する文字列を後ろに付け加えます。

(format t "~A" "test")

数値の出力

formatの~Aは数字も出力できます。

(format t "~A" 2525)

format以外の出力方法

Common Lispでの出力はいくつかの方法が存在しますが、主に用いるのは2種類です。

format

formatは高度な出力のための関数です。formatは独自の記法を用いて複雑な処理を含めた高級な出力を行うことができます。例えば、以下のコードは受け取った数字を英語にして出力するコードです。

(format t "~R" 1234567890)

formatのtの部分は出力先を示します。tの場合標準出力(画面や"実行結果")に出力し、nilの場合返り値とします(返り値についてはx章参照)。
第二引数はformatの出力方法を書きます。 ~Aは基本的になんでも出力できます。 ~%は改行を出力します。

princ

Common Lispでは文字列、数字などほぼ全ての要素をprinc関数で出力することができます。
princは改行を出力しないため、改行が不要な場合に用います。

print

デバッグその他の目的ではprintも用いられます。引数を出力したのちに改行を出力します。
改行の出力は不定であり、AtCoderでの提出での使用は推奨できません。

コメント

コメントはプログラムとしてなんの効果もない部分です。注記やメモ書きなど人間向けに書かれます。

;単行コメント 改行までコメントになる
#|
    複数行コメント
|#

です。

全角文字

Common Lispは全角文字も使用することができます。後述する関数や変数の名前にも全角文字を使用することができます。しかし半角スペースの代わりに全角スペースを用いることができなかったり、読みづらかったりするので基本的にはコメントや文字列以外は半角文字で書くことを推奨します。

EX1 コードテストと出力の練習

サンプルプログラム

(format t "Hello, world!~%")
(format t "Hello, AtCoder!~%")
(format t "Hello, Lisp!~%")

解答例

(format t "こんにちは~%")
(format t "AtCoder~%")

1.02 プログラムの書き方とエラー

関数と引数

(注記) この文書ではマクロとスペシャルフォームを説明するまではこれら二つを関数として書きます。
マクロとスペシャルフォームの解説はif、比較、論理の章にあります。
Common Lispではスペースと改行は同じ意味を持ちます。
Common Lispでは括弧全体をS式または式と呼び、S式内のものを以下のように呼びます。

例えば以下のプログラムであれば、format関数に第一引数t、第二引数"Hello, world!~%"というように呼びます。

(format t "Hello, world!~%")

LispではS式が実行されることを評価する、と言います。評価された変数は必ず何かの値を返します。これを返り値や戻り値と呼びます。

評価順序

(四則演算に必要なためこの章で説明します。)

数学では例えば、
$1∗((2-3)+(4-5))∗((6+7)+8)$
のような数式であれば、このように計算します。

1. $1∗((2-3)+(4-5))∗((6+7)+8)$を計算しようとする
2. $((2-3)+(4-5))$を計算しようとする
3. $(2-3)$を計算する
4. $(-1 + (4 - 5))$を計算しようとする
5. $(4 - 5)$を計算する
6. $(-1 + -1)$を計算する
7. $-1*-2*((6+7)+8)$を計算しようとする
   ...

Common Lispの関数の評価順も同様に、

(A 1 (B (C 2 3) (D 4 5)) (E 6 7))
のような式であれば

1. (A 1 (B (C 2 3) (D 4 5)) (E 6 7))を評価しようとする
2. (B (C 2 3) (D 4 5))を評価しようとする
3. (C 2 3)を評価する
4. 返り値としてXが返る
5. (B X (D 4 5))を評価しようとする
6. (D 4 5)を評価する
7. 返り値としてYが返る
8. (C X Y)を評価する
9. 返り値としてZが返る
10. (A 1 Z (E 6 7))を計算しようとする
    ...

正確にいえば、関数を評価するためには全ての引数の返り値が必要であるため、もし第一引数の関数の引数があればその引数を返り値を得るまで評価し、さらにその引数があれば評価し、終わったら第一引数の関数を評価し、次に第二引数の関数の引数を評価し...を繰り返します
(発展的:つまり深さ優先探索と同じ順に評価されます。またこれはポーランド記法の評価順と同じです)。これは
以下の例ではformat関数の第二引数にformat関数を含めた例です。実行結果を予測して実行してみましょう。

(format t "a"
    (format t "b"
            (format t "c"))
    (format t "d"))

関数の名前と引数、引数と引数の間にはスペースを入れます。スペースはいくつあってもよく、スペースと改行は同じ意味を持ちます。
以下のプログラムは全く同じように動作します。

(format t "Hello, world!~%")
(format          t         "Hello, world!~%"            )
(format
    t
    "Hello, world!~%")

インデント

上記の特徴通り、改行がなくても問題なく動作しますがプログラマである人間が読みづらいため適度に改行して読みやすくします。改行した後適度にスペースを入れたスペースをインデントと呼びます。
slimeは自動的にインデントを調整します。あまり自分で調整する必要はないですがルールを記述しておきます。

エラー

エラーは何かしらの問題でプログラムが実行できなくなった時に起こります。例えば、数値を0で割った時、必要な引数がなかった時などに起こります。
Common LispのREPLではエラーを起こすとデバッガが立ち上がります。
この機能は高度かつ複雑なので今はaboatで抜けてください
(発展的:正確にはコンディションシステムというもので、途中から評価できたりエラー部分だけ別の式に入れ替えたりなど様々な機能があります)。
また、エラーとは違うWARNINGが出る場合があります。これはエラーの出る可能性を示したもので、評価できる可能性がありますが意図しない動作になる恐れがあります。
WARNINGの深刻度によってSTYLE-WARNING<WARNING<ERRORが発生します。
これらの情報はバグの修正(デバッグ)に役立つ可能性があります。

EX2 エラーの修正

サンプルプログラム

(format t "いつも252~%
(format t "AtCoderくん~%"))")

解答例

(format t "いつも2525~%")
(format t "AtCoderくん~%")

1.03 四則演算

Common Lispには演算子が存在しません。全てが関数です。もちろん優先順位も存在しません。先ほどの評価順通り評価されます。括弧の深い部分から評価する順序は一般的な数学式の括弧と同じように扱うことができます。

四則演算

四則演算	関数
足し算	+
引き算	-
掛け算	*
割り算	/

この4つの関数は引数をいくつでも取ることができます。

(+ 1 2 3);;-> 6 (1 + 2 + 3)
(- 1 2 3);;-> -4 (1 - 2 - 3)
(* 1 2 3);;-> 6 (1 * 2 * 3)
(/ 2 3 4);;-> 1/6 (2 / (3 * 4))

/はC++などほとんどの言語と違い分数で値が返ります。小数に直すには型の変換(次章参照)を用いて(coerce 'long-float x)にします。
剰余は(mod x y)です。
べき乗は(expt x y)です。
丸め演算はどの方向にどのように丸めるかで4種類の関数が存在します。

EX3 計算問題

サンプルプログラム

(format t "~A~%" #|ここに式を書く|#)

解答例

(format t "~A~%" (* 1/2 100 (+ 100 1)))

1.04 変数と型

変数

Common Lispでは変数はシンボルに値を代入した要素が用いられます。
Common Lispには変数が3種類あります。
定数を除き、代入する方法は共通して(setf 変数 値)です。
変数に代入することを主にLispでは束縛すると言います。
Common Lispでは変数や後述する関数は大文字小文字の区別はありません。

シンボル

シンボルは値を格納できるスロットがあるデータの格納場所です。Common Lispでは先頭に'のつくリストでない要素はシンボルとして扱われます。比較はequalで行います。またread関数で文字列が入力された場合もシンボルを返します。

(if (equal 'OK (read));OKと入力すると"input is OK"を出力する
    (format t "input is OK")
    (format t "input is not OK"))
;(普通はこういった処理は後述する文字列で行われます)

スペシャル変数

スペシャル変数は他の言語ではグローバル変数に相当する変数で、生成されてからLisp自体を終了するまで残り続ける変数です(注:パッケージによって分けることができますがパッケージはこの文書では扱いません)。
慣習的に*abc-def*のような名前をつけます。defparameter関数で生成します。

レキシカル変数

レキシカル変数はローカル変数とも呼ばれる、特定の関数内のみで用いられる変数です。例えば、以下はlet関数でレキシカル変数aを生成する例です。

(let ((a 1))
  (format t "~A" a));;->1
(format t "~A" a);;->エラー！(aはlet内でしか使えないため)

letとlet*

letは代表的なレキシカル変数を生成する関数です。
似たような名前の関数にlet*があります。一見同じように動作しますがletは複数のレキシカル変数を同時に、let*では順番にに値が束縛されます。

(let* ((a 1)
       (b (+ a 1)))
      (princ b))
#|letではaとbは同時には束縛できないためエラーになる
(let ((a 1)
      (b (+ a 1)))
  (princ b))
|#

破壊的関数、非破壊的関数(発展的)

defvar関数のような関数外部に影響する関数を破壊的関数と呼びます。逆に算術関数のようなそうでない関数を非破壊的関数と呼びます。破壊的関数には例えば入出力に関係する関数や変数を書き換える関数も含まれます。これらの破壊的な操作を副作用と呼びます。破壊的な操作は関数の外環境も考慮する必要があるので減らした方が良いですが、破壊的関数でなければできない操作があることもまた一つの特徴です。

型

Common Lispの数学型は

数学型	Common Lispの型
整数	fixnumまたはbignum
小数	floatまたはlong-float
分数	ratio

などがあります。
C++とは異なり異なる型同士の計算も代入も自動的に型変換で適切な型に変換されます。
型を変換したい場合coerce関数を用います。coerce関数の第一引数はシンボルとして入力します。

(coerce 'long-float 1/2);;-> 0.5

EX4 ◯年は何秒？

サンプルプログラム

(let ((seconds (* 365 24 60 60)))
  (format t "~A~%" #|1年は何秒か|#)
  (format t "~A~%" #|2年は何秒か|#)
  (format t "~A~%" #|5年は何秒か|#)
  (format t "~A~%" #|10年は何秒か|#))

解答例

(let ((seconds (* 365 24 60 60)))
  (format t "~A~%" seconds)
  (format t "~A~%" (* 2 seconds))
  (format t "~A~%" (* 5 seconds))
  (format t "~A~%" (* 10 seconds)))

1.05 実行順序と入力

評価順序

先に説明した通り基本的には引数の評価順の通り評価されます。

暗黙のprogn

まず、prognとはいくつかの式を受け取って順に評価し、最後の式の返り値を返す関数(スペシャルフォーム)です。つまり、基本的には括弧が深いところから順に括弧の外側に向かって評価される関数(スペシャルフォーム)です。例えば、ifのような一つの式しか用いることができない場所で用います。

(if (or t nil)
    (progn (format t "~A" "t or nilは")
           (format t "~A~%" "t"))
    (progn (format t "~A" "t or nilは")
           (format t "~A~%" "nil")))
#|(if (or t nil) ;こう書くことはできない
(format t "~A" "t or nilは")
(format t "~A~%" "t")
(format t "~A" "t or nilは")
(format t "~A~%" "t")
)|#

例えばletは

(let (())
  (format t "Hello, world1!~%")
  (format t "Hello, world2!~%"))

のように書きますが、これは

(let (())
  (progn (format t "Hello, world1!~%")
         (format t "Hello, world2!~%")))

と等価です。これは暗黙のprognと呼ばれる機能で、S式をいくつも連ねて書くことができます。例えばlambdaやcond、letには暗黙のprognがあります。このため、lambdaやletにはS式を複数とって評価することができます。

入力

Common Lispの入力はread関数とread-line関数で行います。
read関数は数字、小数などなんでも読み込むことができます。
数値でない場合、シンボルとして受け取ります。
read-line関数は入力を文字列として読み込みたいときに利用します。

EX5 A足すB問題

サンプルプログラム

(let ((seconds (* 365 24 60 60)))
  (format t "~A~%" seconds)
  (format t "~A~%" (* 2 seconds))
  (format t "~A~%" (* 5 seconds))
  (format t "~A~%" (* 10 seconds)))

解答例

(let ((seconds (* 365 24 60 60)))
  (format t "~A~%" seconds)
  (format t "~A~%" (* 2 seconds))
  (format t "~A~%" (* 5 seconds))
  (format t "~A~%" (* 10 seconds)))

1.06 1.07 if、比較、論理

真偽値

Common Lispの真偽値はC++とは違い、nilなら偽、それ以外なら真です。なので偽はnilのみ、それ以外は数値も文字列も全部真です。真偽値も用意されており、真の場合t、偽の場合nilです。

if

ifは第一引数がtの時第二引数、nilの時第三引数を評価します。
複数の式を並べる場合prognで囲います。

(if (or t nil)
    (progn (format t "~A" "t or nilは")
           (format t "~A~%" "t"))
    (progn (format t "~A" "t or nilは")
           (format t "~A~%" "nil")))

スペシャルフォーム(発展的)

ifに対して何か違和感を持ちませんか？普通の関数は第一引数から順に全て評価されるのにifは第一引数で評価するかしないかを変えます。
こういった引数によって評価をしたりしなかったりできるものをスペシャルフォームと言います。ifは関数ではなくスペシャルフォームです。
スペシャルフォームはコンパイラに組み込まれた機能で、Common Lispの機能のみでは作ることができません。

cond

ifのような機能を持つ関数として、condがあります。これはパターンマッチとも呼ばれる機能で、他の言語のswitch文などに相当します。

(let ((x 1))
  (cond ((= x 3) (format t "xは3"))
        ((= x 2) (format t "xは2"))
        ((= x 1) (format t "xは1"))
        (t (format t "xはそれ以外"))))

比較

Common Lispの数字の比較は他の言語と同じく、それぞれ
= < <= > >=
です。論理を反転したい場合にはnot関数を使います。notは真偽値を受け取って逆の真偽値を返す関数です。

(if (not (< 1 2))
    (format t "1<2 の反対はt")
    (format t "1<2 の反対はnil"))

論理

not関数は真偽値を受け取って逆の真偽値を返す関数です。
and関数(マクロ)はnilを見つけるまで評価して最後までtであればt、そうでなければnil
or関数(マクロ)はtを見つけるまで評価して最後までnilであればnil、そうでなければtを返します。

マクロ

andとorも純粋な関数とは違い引数が評価されたりされなかったりします。
これはマクロという機能で、展開するとスペシャルフォームや関数のかたまりに展開されます。
この文書では関数とマクロの詳細には触れませんが、評価順が異なるということのみ留意してください。

EX6 電卓をつくろう

サンプルプログラム

(let ((a (read))
      (op (read))
      (b (read)))
  (cond ((equal op '+) (format t "~A~%" (+ a b)))
;ここにプログラムを追記
))

解答例

(let ((a (read))
      (op (read))
      (b (read)))
 (cond ((equal op '+) (format t "~A~%" (+ a b)))
       ((equal op '-) (format t "~A~%" (- a b)))
       ((equal op '*) (format t "~A~%" (* a b)))
       ((and (equal op '/) (not (= b 0)))
        (format t "~A~%" (floor a b)))
       (t (format t "error~%"))))

1.08 変数のスコープ

スペシャル変数とレキシカル変数の話は先ほど書いたので補足的な内容のみ記します。

多重let

letが重なる場合どのような作用をする場合、もっとも内側の定義が利用されます。

(let ((a 1))
  (let ((a 2))
    (format t "~A~%" a)))
;;->2

これは、letは新しい変数を作るため同じ名前をつけても一番内側の定義に従います。変数に変更を加えた場合も一番内側の変数のみ変更されることに留意してください。

EX7 bool値パズル

サンプルプログラム

(let ((a #|t または nil|#)
      (b #|t または nil|#)
      (c #|t または nil|#))
  ;ここから先は変更しないこと
  (if a (format t "At") (format t "Yo"))
  (cond ((and (not a) b) (format t "Bo"))
        ((or (not b) c) (format t "Co")))
  (cond ((and a b c) (format t "foo!"))
        ((and t nil) (format t "yeah!"))
        ((or (not a) c) (format t "der")))
  (format t "~%"))

解答例

    (let ((a t)
          (b nil)
          (c t))
                                           ;ここから先は変更しないこと
     (if a (format t "At") (format t "Yo"))
     (cond ((and (not a) b) (format t "Bo"))
           ((or (not b) c) (format t "Co")))
     (cond ((and a b c) (format t "foo!"))
           ((and t nil) (format t "yeah!"))
           ((or (not a) c) (format t "der")))
     (format t "~%"))

1.09 複合代入

変数にいくらか足したり引いたりしたあと代入する、という効果は1つのマクロで書くことができます。
incfマクロは引数を1つか2つ受け取り、1つ目の引数を2つ目の引数分、省略されれば1足して代入します。
逆にdecfマクロは引数を1つか2つ受け取り、1つ目の引数を2つ目の引数分、省略されれば1引いて代入します。

(let ((a 1))
    (format t "~A~%" a);;->1
    (incf a)
    (format t "~A~%" a);;->2
    (decf a 10)
    (format t "~A~%" a);;->-8
    )

マクロの効用(発展的)

このように変数を受け取って代入するような機能を実装できるのはマクロにしかできない機能です。
関数では変数の中身を取り出してしまうため、変数を変数として扱うことができるのはマクロにしかできません。しかし、これは同時に変数を通じてマクロの外側を破壊する破壊的なマクロであるため作成と使用には注意を払ってください。

EX9 複合代入演算子を使おう

サンプルプログラム

(let ((x (read))
       (a (read))
       (b (read)))
  (incf x)
  (format t "~A~%" x)
      #|ここにプログラムを追記|#)

解答例

(let ((x (read))
      (a (read))
      (b (read)))
  (incf x)
  (format t "~A~%" x)
  (setf x (* x (+ a b)))
  (format t "~A~%" x)
  (setf x (* x x))
  (format t "~A~%" x)
  (decf x)
  (format t "~A~%" x))

(let ((x (read));setfの返り値は代入された後の値のためこれも動きます
      (a (read))
      (b (read)))
  (format t "~A~%" (incf x))
  (format t "~A~%" (setf x (* x (+ a b))))
  (format t "~A~%" (setf x (* x x)))
  (format t "~A~%" (decf x)))

1.10 1.11 繰り返し

補足
この説明を読む前にloopマクロの章を読んだ方が良いかもしれません。ただし必須ではありません。どちらの方がいい、というのも特にありません。

while

Common LispにはC++のwhileに相当する関数は存在しません。

do

C++のfor文に相当する関数はdoマクロです。
第一引数で使用するローカル関数を定義し、名前、初期値、更新式を書きます。第二引数には終了条件と返り値を書きます。第三引数から先はループするときに評価する式を書きます。

(do ((k 1 (1+ k))
     (j '(1 2 3 4 5 6) (cdr j)))
    ((> k 5) nil)
  (format t "~A ~A~%" k j))

break、continue

do文関数中ではreturn関数(マクロ)を使用することができます。returnが評価されると一番近いdoマクロから抜けることができます。
continueに相当する関数はありません。ifとprognで用いると良いでしょう。

loopマクロ

loopマクロはループ構造を簡単に書くことのできるマクロです。このマクロは非常に強力でほとんどのループ構造を簡単に書くことができます。APG4bのrepマクロのような自作機能ではなく組み込まれているマクロです。
これもformat関数のようにかなりの数の機能があるので抜粋して説明します。

変数宣言

例の:for kの部分は変数宣言を行なっています。

(loop :for k :from 1 :upto 10 :by 1 :do(format t "~A~%" k))

これは、fromで指定した1からuptoで指定した10までbyで指定した1を足しながらkに束縛して繰り返します。
もしくは、repeat n でn回のループを作ることができます。

(loop :repeat 5 :do(format t "test~%"))

実行部

do項は実行部です。do項は毎ループで実行されます。
if項を用いることで分岐でき、else項でifに合わない条件で分岐します。

その他

その他にもcount、sum、maximizeなど便利な様々な項があります。

loopマクロの是非(とLispのマクロの是非)

(経験者向け) 注記 本家APG4bに書いてあるので書きます。 loopマクロの是非はLisp上級者でも意見が別れます。やはり普通とは異なる構文や複雑な節などが原因だと思われます。しかしLispのマクロは標準でも用意されているほど欠かせないものであり、マクロなしにCommon Lispを書くことは無理と言っても過言ではありません。 LispのマクロはC++などの単なる構文拡張とは違い安全に利用することができ、また利用者もほとんどマクロについて意識せず利用することができます。現にandやor、果てはdefunやsetfなどの基礎的な部分にも利用され、安全に大きな力を引き出すことができます。

EX10 棒グラフの出力

サンプルプログラム

(let ((a (read))
      (b (read)))
  #|ここにプログラムを追記|#)

解答例

(let ((a (read));loopマクロ版
      (b (read)))
  (format t "A:")
  (loop :repeat a
        :do(format t "]"))
  (format t "~%")
  (format t "B:")
  (loop :repeat b
        :do(format t "]"))
  (format t "~%"))

(let ((a (read));doマクロ版
      (b (read)))
  (format t "A:")
  (do ((k 0 (+ 1 k)))
      ((= a k) nil)
      (format t "]"))
  (format t "~%")
  (format t "B:")
  (do ((k 0 (+ 1 k)))
      ((= b k) nil)
      (format t "]"))
  (format t "~%"))

EX11 電卓をつくろう2

サンプルプログラム

(let ((n (read))
      (a (read)))
  #|ここにプログラムを追記|#)

解答例

(let ((n (read));loopマクロ版
      (a (read)))
  (loop :for k :from 1 :upto n
        :do(let ((op (read))
                  (x (read)))
             (cond ((equal op '+)
                    (format t "~A:~A~%" k (setf a (+ a x))))
                   ((equal op '-)
                    (format t "~A:~A~%" k (setf a (- a x))))
                   ((equal op '*)
                    (format t "~A:~A~%" k (setf a (* a x))))
                   ((equal op '/)
                    (if (= x 0)
                        (progn (format t "error~%")
                               (loop-finish))
                        (format t "~A:~A~%" k (setf a (truncate (/ a x))))))))))

(let ((n (read));doマクロ版
      (a (read)))
  (do ((k 1 (1+ k)))
      ((> k n) nil)
    (let ((op (read))
          (x (read)))
      (cond ((equal op '+)
             (format t "~A:~A~%" k (setf a (+ a x))))
            ((equal op '-)
             (format t "~A:~A~%" k (setf a (- a x))))
            ((equal op '*)
             (format t "~A:~A~%" k (setf a (* a x))))
            ((equal op '/)
             (if (= x 0)
                 (progn (format t "error~%")
                        (return))
                 (format t "~A:~A~%" k (setf a (truncate (/ a x))))))))))

1.12 文字列、配列

Lispではいくつかのデータが格納された変数をシーケンスと呼びます。
ベクタは高速にアクセスできる、他の言語の配列に相当する型です。
例えばCommon Lispの文字列はベクタで表現されます。文字列のベクタに格納されている要素は文字です。

文字

直接記述するには#\aのように書きます。文字を比較するのはchar=関数です。
文字をASCIIコードに変換するにはchar-code関数、逆はcode-char関数です。

リーダマクロ(発展的)

#\aや#'+などの記法はリーダマクロと呼ばれる機能で、読み込み時にS式に展開されるマクロの一種です。特に意識することはないと思いますが用語は覚えておいてください。

シーケンス操作関数

シーケンスのアクセス方法は(elt シーケンス n番目)です。n番目は0から始まります。
シーケンスの長さを取るには(length シーケンス)です。長さは1から始まることに注意してください。

検索と計数

検索と計数のための関数として、findとcount、removeがあります。
findはシーケンスに含まれる場合「検索した要素」、ない場合nilを返します。
countは要素の個数を数えます。
removeは一致する要素を削除したシーケンスを返します。
これら3つの関数にはそれぞれ-if、-if-notがあります。
これは関数を受け、要素ではなく関数を引き、nilでない要素に対して作用するようになります。

1. mapとreduce

シーケンスを操作する関数の代表的な例としてmap関数とreduce関数があります。
これを使いこなすことによってより簡潔に書くことができます。

例えば以下のように用います。

(reduce #'max '(1 2 3 4 5));一番大きい要素を得る

EX12 足したり引いたり

サンプルプログラム

(let ((s (read-line)))
  #|ここにプログラムを追記|#)

解答例

(let ((s (read-line));loopマクロ版
      (answer 1))
  (loop :for k :from 1 :upto (1- (length s)) :by 2
        :do(if (char= #\+ (elt s k))
              (incf answer)
              (decf answer)))
  (format t "~A~%" answer))

1.13 リスト

(注記)本来なら配列はベクタに相当するのでベクタで紹介すべきですがリストの説明を含めるためこの章で説明します。
Common Lispのベクタ以外のシーケンスにリストがあります。
リストとベクタの違いは速度と柔軟性にあります。
リストは柔軟性に富み、シーケンスだけでなく木構造などを表現することもできます。しかし、アクセスは先頭からたどるため長さぶんの時間が掛かります。
ベクタは高速に動作し、定数時間でアクセスできますが長さを固定する必要があります。
またnilは何も入っていないリストと等価です(空リストと呼びます)。

consセル

Common Lispではリストはconsセルの塊で構成されます。consセルはcar、cdrで構成され、一列のリストは以下の図のように表現されています。

シーケンスの変換

シーケンスを別の型に変換するにはconcatenate関数を使います。

EX13 平均との差

サンプルプログラム

(let ((n (read))
      (points (loop :repeat n :collect (read))))
  #|ここにプログラムを追記|#)

解答例

(let ((n (read));シーケンス関数版
      (points (loop :repeat n :collect (read)))
      (means 0))
  (setf means (floor (/ (reduce #'+ points) n)))
  (mapcar (lambda (x)
            (format t "~A~%" (abs (- x means))))
          points))

(let ((n (read));loopマクロ版
      (points (loop :repeat n :collect (read)))
      (sum 0)
      (means 0))
  (loop
        :for k :from 0 :upto (1- (length points))
        :do(setf sum (+ sum (elt points))))
  #|
  (setf sum ;loopマクロのinとsumを利用したコードです。上より高速です。
  (loop
    :for k :in points
    :sum k))
  |#
  (setf means (floor (/ sum n)))
  (loop
    :for k :from 0 :upto (1- (length points))
    :do(format t "~A~%" (abs (- x means))))
  #|
  (loop loopマクロのinとsumを利用したコードです。上より高速です。
    :for k :in points
    :do(format t "~A~%" (abs (- k means))))
  |#
  )

1.14 1.15 関数

関数

関数の定義はdefun、またはlabelsで行います。
defunはグローバルな関数、labelsはレキシカルな関数を作ります。
Common Lispの関数の返り値は最後に評価された式です。
以下はローカル関数fを定義し評価する例です。

(labels ((f (x y)
          (if (< x y)
              x
              y)))
 (format t "~A~%" (f 1 2)))

もし1番目や2番目の返り値を返したい場合、prog1やprog2を用います。

EX14 三人兄弟の身長差

サンプルプログラム

(let ((a (read))
      (b (read))
      (c (read)))
#|ここにプログラムを追記|#)

解答例

(let ((a (read))
      (b (read))
      (c (read)))
  (format t "~A~%" (- (max a b c) (min a b c))))
  (let ((height (loop :repeat 3 :collect (read))));シーケンス関数版
     (format t "~A~%" (- (reduce #'max height) (reduce #'min height))))

EX15 三人兄弟へのプレゼント

(labels ((sum (scores)
           #|
           1人のテストの点数を表す配列から合計点を計算して返す関数
           引数 scores: scores.at(i)にi番目のテストの点数が入っている
           返り値: 1人のテストの合計点
           |#
           #|ここにプログラムを追記|#)
         (output (sum-a sum-b sum-c)
           #|
           3人の合計点からプレゼントの予算を計算して出力する関数
           引数 sum-a: A君のテストの合計点
           引数 sum-b: B君のテストの合計点
           引数 sum-c: C君のテストの合計点
           返り値: nil
           |#
           #|ここにプログラムを追記|#)
         #|ここから先は変更しない|#
         (input (n)
           #|
           n個の入力を受け取ってリストに入れて返す関数
           引数 N: 入力を受け取る個数
           返り値: 受け取ったn個の入力のリスト
           |#
           (loop :repeat n :collect (read))))
      (let ((n (read));科目の数nを受け取る
            (a (input n));それぞれのテストの点数を受け取る
            (b (input n))
            (c (input n))
            )
        (output (sum a) (sum b) (sum c))))

解答例

(labels ((sum (scores);列関数版
           #|
           1人のテストの点数を表す配列から合計点を計算して返す関数
           引数 scores: scores.at(i)にi番目のテストの点数が入っている
           返り値: 1人のテストの合計点
           |#
           (reduce #'+ scores))
         (output (sum-a sum-b sum-c)
           #|
           3人の合計点からプレゼントの予算を計算して出力する関数
           引数 sum-a: A君のテストの合計点
           引数 sum-b: B君のテストの合計点
           引数 sum-c: C君のテストの合計点
           返り値: nil
           |#
           (format t "~A~%" (* sum-a sum-b sum-c)))
         #|ここから先は変更しない|#
         (input (n)
           #|
           n個の入力を受け取ってリストに入れて返す関数
           引数 N: 入力を受け取る個数
           返り値: 受け取ったn個の入力のリスト
           |#
           (loop :repeat n :collect (read))))
  (let ((n (read));科目の数nを受け取る
        (a (input n));それぞれのテストの点数を受け取る
        (b (input n))
        (c (input n)))
    (output (sum a) (sum b) (sum c))))

(labels ((sum (scores);loopマクロ版
           #|
           1人のテストの点数を表す配列から合計点を計算して返す関数
           引数 scores: scores.at(i)にi番目のテストの点数が入っている
           返り値: 1人のテストの合計点
           |#
           (loop :for k :in scores
                 :sum k))
         (output (sum-a sum-b sum-c)
           #|
           3人の合計点からプレゼントの予算を計算して出力する関数
           引数 sum-a: A君のテストの合計点
           引数 sum-b: B君のテストの合計点
           引数 sum-c: C君のテストの合計点
           返り値: nil
           |#
           (format t "~A~%" (* sum-a sum-b sum-c)))
         #|ここから先は変更しない|#
         (input (n)
           (loop :repeat n :collect (read))))
  (let ((n (read));科目の数nを受け取る
        (a (input n));それぞれのテストの点数を受け取る
        (b (input n))
        (c (input n))
        )
    (output (sum a) (sum b) (sum c))))

付録

他の言語について

Lispにはいくつかの方言があり、それぞれに特徴があります。ここではAtCoderで使うことのできるLisp方言を紹介します。

scheme

AtCoderでもschemeで解いている方がいらっしゃいます。実行時間もそれなりに早く、遅延評価や継続などのCommon Lispにはない機能を用いることができます。

racket

(よくわかっていないので明言を避けます)

clojure

clojureはJVM上で動くLispの一方言です。JVMの機能を使えることや遅延評価を標準で実装していることなどが特徴です。
clojureはJVMの起動時間が入ってしまい実行時間を圧迫してしまうためAtCoderではあまり利用されていません。

環境設定

Common Lispの最低限の環境として、括弧の対応の表示(と調整機能)とREPLが利用できることを確認してください。

portacle

もっとも簡単な手段としてportacleというパッケージがあります。これはSBCLやemacsなどの環境をまとめたパッケージで、Windows、MacOS、Linuxそれぞれで動作することができます。
https://portacle.github.io/
(使い方は後で書き足します…)

MacOSの注意点

MacOSではそのままでは動作せずPortacle.appをprojectsディレクトリに移動する必要があります。

emacs

emacsで使用するにはslimeを利用することを推奨します。

spacemacs

emacsの派生であるspacemacsを利用するとより簡単に環境を構築することができます。

vim

vimで使用するにはslimvを利用することを推奨します。