M.Hiroi's Home Page / Common Lisp Programming

WHAT'S NEW

2023/12/01 自作ライブラリ編: ntheory をバージョンアップ (ver 0.2.8)

お気楽 Common Lisp プログラミング入門

2020/01/05 Lisp の基本
最初は Hello, World、Lisp ではリストが主役、シンボルは変数として機能する、代入は変数の値を破壊する、T と NIL は定数、文字列、評価しちゃだめ！、まとめ
2020/01/05 リスト操作の基本
リストの分解、リストの合成、リストの操作は非破壊的、ドットリスト、問題
2020/01/05 数と算術演算
整数、分数、浮動小数点数、複素数、四則演算、数の変換、剰余と累乗、その他、問題
2020/01/05 関数定義
defun は関数を定義する、レキシカル変数とスペシャル変数、let はレキシカル変数を定義する、問題
2020/01/05 述語
述語、等値の術語、数に関する述語、数値を比較する述語、データ型を調べる述語、複数の術語を組み合わせる、問題
2020/01/05 条件分岐
if、when と unless、cond、case、FizzBuzz 問題その前に
2020/01/05 再帰定義
再帰定義は難しいテクニックではない、再帰定義の基本、累乗の計算、累乗の高速化、再帰定義とリスト操作、リストの結合、リストの探索、リストの削除、リストの置換、FizzBuzz 問題、ハノイの塔、問題
2020/01/12 繰り返し
dotimes、dolist、loop、do、平均値を求める、数値積分、素数を求める、問題
2020/01/12 逐次実行
progn、prog1 と prog2、スタックとは？、スタックの実装、push と pop、問題
2020/01/12 高階関数とラムダ式
マップ関数 mapcar、apply、funcall、関数はシンボルで渡すこともできる、キーワード引数、ラムダ式は無名の関数を定義する、マッピング、フィルター、畳み込み、問題 (2020/04/25 問題 7, 8 を追加)
2020/01/12 ラムダリストキーワード
&optional、&rest、&key、&aux、注意事項、問題
2020/01/12 配列
配列の生成、要素のデータ型と初期値の指定、配列のアクセス、ベクタの生成、ベクタとスタック、ベクタによるスタックの実装、vector-push と vector-pop、スタックの拡張、素数を求める (2)、問題
2020/01/12 列関数
単純な列関数、文字、列の探索、列の修正、マッピング、列の連結、畳み込み、ソートとマージ
2020/01/12 リスト操作関数
リストの探索、リストの置換、連想リスト、その他の関数
2020/01/19 ファイル入出力
標準入出力とは？、read と print、ファイルのアクセス、read-line と read-char、write-line と write-char、read-sequence と write-sequence、バイナリファイルの操作、パス名、パスの要素、make-pathname と directory、:if-exists と :if-does-not-exist、問題
2020/01/19 format
整数の出力、浮動小数点数の出力、文字の出力、S 式の出力、format の便利な機能、~(str~)、 ~[str0~;str1~; ... ~;strn~:;default~]、~[ と # の組み合わせ、~{str~}、~*
2020/01/19 末尾再帰
再帰呼び出しを末尾再帰に変換する、二重再帰を末尾再帰に変換する、相互再帰、末尾再帰を手動で繰り返しに変換、補足: 末尾最適化
2020/01/26 数当てゲーム
乱数、数字を 4 つ選ぶ、入力処理を作る、bulls と cows を数える、ゲーム本体を作る、ゲームの実行
2020/01/26 ソートとマージ
挿入ソート、クイックソート、クイックソートの弱点、マージ、マージソート、実行時間の比較
2020/01/26 属性リスト
属性リストの構造、シンボルの構造、属性リストの操作関数、簡単な使用例
2020/01/26 マクロ
マクロの定義、マクロと関数の違い、マクロとコンパイラの関係、スタックの操作、バックォート、マクロ展開後の実行環境、マクロとラムダリストキーワード、分配
2020/01/26 多値
複数の値を受け取る、複数の値を返す、その他、簡単な例題
2020/01/26 レキシカルスコープとクロージャ
レキシカルスコープ、ラムダ式とレキシカル変数、関数の中で関数を定義する、クロージャとは？、関数を生成する関数、カリー化、ジェネレータ、ジェネレータをリセットする、ちょっと難しいかも、補足、問題
2020/01/26 リストの破壊的修正
リスト構造の修正、リストの連結、mapcan と mapcon、リストと反転、リスト操作関数の改良、リストの置換、循環リスト、循環リストのチェック
2020/01/26 列の破壊的修正
列の反転、部分列の置換、列の要素の削除、列の要素の置換
2020/02/02 順列と組み合わせ
順列の生成、バックトラック法の実装、プログラムの作成、高階関数版の作成、順列をリストに格納する、要素の選択、順列の生成 (2)、順列の生成 (3)、組み合わせの生成、組み合わせをリストに格納する、問題、補足: 要素に重複がある場合
2020/02/02 生成検定法
小町算、大町算、覆面算、Eigth Queens Problem、マスターマインド
2020/02/02 構造体
構造体の定義、defstruct のオプション、位置によるコンストラクタ、カプセル化、リストによるキューの実装、循環リストによるキューの実装、ベクタによるキューの実装
2020/02/02 経路の探索
グラフとは？、隣接行列と隣接リスト、連想リストによる方法、バックトラックによる探索、幅優先探索、経路の管理、プログラムの作成、反復深化、反復深化による経路の探索、水差し問題、容器の操作、深さ優先探索による解法、幅優先探索による解法、反復深化による解法
2020/02/09 スペシャル変数とダイナミックスコープ
defvar、ダイナミックスコープ、defconstant と defparameter、スペシャル変数の便利な使い方、スペシャル変数の一時的な宣言、補足: ダイナミックスコープと funarg 問題
2020/02/09 ちょっと特殊な制御構造
block と return-from、block の脱出点はレキシカルスコープ、tagbody と go、使用上の重要な注意、大域脱出、unwind-protect
2020/02/09 ベクタのソートと二分探索
挿入ソート、クイックソート、実行時間の計測、クイックソートの改良、実行時間の計測 (2)、二分探索
2020/02/09 ハッシュ表
ハッシュ法の仕組み、ハッシュ表の基本操作、マップ関数、簡単な例題
2020/02/09 二分探索木
木構造とは？、二分木、節の定義、データの探索、データの挿入、データの削除、巡回 (traverse)、binary-tree の作成、実行例
2020/02/16 整数の論理演算とビット操作
基本的な論理演算、基本的なビット操作、組み合わせの生成、組み合わせに番号を付ける、ちょっと便利なビット操作、ビットが 1 の個数を求める、パズル「ライツアウト」、ライツアウトの解法、高速化、解法プログラム、実行結果、ビット配列 (2023/09/10)
2020/02/16 幅優先探索とスライドパズル
８パズルの説明、幅優先探索による解法、実行結果、双方向探索、最長手数の求め方、プログラムの作成、実行結果、問題
2020/02/16 反復深化と下限値枝刈り法
ペグ・ソリティア、Hoppers、跳び先表とペグの移動、反復深化による Hoppers の解法、実行結果、反復深化による 8 パズルの解法、実行結果、下限値枝刈り法、プログラムの作成、実行結果
2020/02/23 コンディション
例外処理、コンディションの捕捉、簡単な使用例、コンディションの通知、コンディションの定義、ignore-errors、handler-bind、再開、restart-case、パズル Four Four's、数式のパターン、プログラムの作成、実行結果、前置記法と eval
2020/02/23 パッケージの基本的な使い方
パッケージとは？、import と export、provide と require、簡単な例題、マクロをパッケージにまとめる場合
2020/02/23 集合としてのリスト
和集合、積集合、差集合、部分集合、Common Lisp の集合関数、パズル「嫉妬深い夫の問題」、プログラムの作成、実行結果、問題
2020/02/29 ループ機能
基本的な繰り返し、条件実行、ベクタとハッシュ表、複数の for、値の累積、終了条件、ループの脱出と前処理・後処理、変数の定義、分配、簡単な例題、問題
2020/03/07 文字と文字列
文字に関する述語、文字の比較、文字の変換、文字列の比較、文字列の作成と操作
2021/11/06 複素数
Common Lisp の数、無限大、負のゼロ、Common Lisp の複素数、複素数の四則演算、複素数の指数関数と対数関数、複素数の三角関数、複素数の双曲線関数、複素数の平方根、逆三角関数、複素数の逆三角関数、逆双曲線関数、複素数の逆双曲線関数
2022/12/25 Common Lisp / Scheme の繰り返し
do と do*、Scheme の do、do の動作は Common Lisp と Scheme で異なる、リストの総和、行列の総和、Common Lisp のタグはレキシカルスコープ、Scheme の継続、tagbody のタグ

●応用編

2020/03/07 記号のパターンマッチング
パターンマッチング、パターン変数は連想リストで管理する、関数 match の実装、実行例、ユニフィケーション、関数 unify の実装、実行例、補足 : Prolog ライクなユニフィケーション
2020/03/15 電卓プログラムの作成 (前編)
プログラミング言語処理系の基本的な構造、文法の表現、式の構文、字句解析、構文解析、式の入力と評価、実行例、単項演算子の追加、実行例 (2)、構文木の構築
2020/03/15 電卓プログラムの作成 (後編)
変数、関数、変数と関数の操作、字句解析、構文解析、実行例、構文木の構築
2020/03/15 Common Lisp で作る micro Lisp インタプリタ
最小の Lisp 処理系、S 式の評価、変数値と関数値の取得、関数適用と変数束縛、特殊形式の処理、micro Lisp の初期化、REPL (Read-Eval-Print-Loop)、簡単な実行例、レキシカルスコープとクロージャの動作、再帰定義
2020/03/28 Common Lisp で作る micro Lisp コンパイラ
SECD 仮想マシン、SECD 仮想マシンの命令、ld, ldc, ldg, ldgf, ldf, args, app, rtn, sel, join, lset, gset, その他、コンパイラの作成、特殊形式と関数呼び出しのコンパイル、引数とラムダ式本体の評価、局所変数の位置を求める、簡単なコンパイルのテスト、仮想マシンの作成、read-eval-print-loop、簡単な実行例、レキシカルスコープとクロージャの動作、再帰定義
2020/03/28 簡易エキスパートシステムの作成 (前編)
エキスパートシステムと Prolog、Prolog とは？、Prolog のプログラムとは？、パターンマッチングからエキスパートシステムへ、変数の管理方法、バックトラックの管理
2020/03/28 簡易エキスパートシステムの作成 (後編)
プログラムの作成、節の実行、インターフェースの作成、実行例 -- 家系図、実行例 -- 簡単なリスト操作、まとめ
2020/04/05 メモ化と遅延評価
たらいまわし関数、メモ化による高速化、メモ化関数、遅延評価による高速化、delay と force の実装
2020/04/05 継続渡しスタイル
継続とは？、継続渡しスタイルとは？、再帰呼び出しと継続渡しスタイル、二重再帰と継続渡しスタイル、再帰呼び出しの中断、CPS による木の巡回、CPS による継続の保存と実行の再開
2020/04/11 遅延ストリーム (1)
遅延ストリームの構造、遅延ストリームの生成、遅延ストリームの変換、遅延ストリームの操作関数、遅延ストリームの連結、高階関数、stream-map の便利な使い方、stream-flatmap、stream-take-while と stream-drop-while、組 (pair) を生成する遅延ストリーム、補足: 逆畳み込み、(2020/04/20 stream-scan-left を追加)
2020/04/11 遅延ストリーム (2)
遅延ストリームの併合、集合演算、ハミングの問題、順列の生成、８クイーンの解法、木の巡回と遅延ストリーム、ツリーマッチング、エラトステネスの篩、より高速な方法、追記(2020/04/18)、双子素数、プロミスを使わずに遅延ストリームを実装する
2020/04/11 遅延ストリーム (3)
遅延ストリームを遅延オブジェクトで表す、stream-delay、実行速度の比較、追記(2020/04/18)
2020/04/11 シリーズ (series)
シリーズとは？、インストール、シリーズの生成、集積関数、マッピング、フィルター、変換関数、ジェネレータとギャザラ、簡単な例題
2020/05/16 遅延ストリーム (パッケージ編)
遅延評価の仕様、遅延ストリームの仕様、簡単なサンプルプログラム、Scheme の遅延シーケンス、遅延シーケンスの構造、基本関数の作成、簡単な例題
2023/07/15 動的計画法
組み合わせの数、動的計画法による高速化、動的計画法とメモ化、整数の分割、部分和問題、深さ優先探索＋枝刈り、動的計画法による解法、ナップザック問題、プログラムの作成、実行結果
2023/07/15 Algorithm X
敷き詰め問題、Exact Cover Problem、プログラムの作成 (1)、実行結果 (1)、Algorithm X の基本、連結リストによる Algorithm X の実装、プログラムの作成 (2)、実行結果 (2)
2023/07/15 Dancing Links
Dancing Links とは？、Dancing Links の操作方法、データ構造の定義、Dancing Links の生成、行と列の削除、行と列の復元、Dancing Links による Algorithm X の実装、実行結果

●パズルの解法編

2023/07/16 パズルに挑戦！
騎士の巡歴、騎士の交換、地図の配色、どこも平方数、11 パズル
2023/07/16 パズル「フリップ・イット」
パズルの説明、プログラムの作成、フリップ・イットの解答、フリップ・イットの最長手数、ルールの変更
2023/07/16 変形魔方陣
問題１、プログラムの作成、問題２、問題３
2023/07/16 ペグ・ソリテア
ペグ・ソリテアの説明、変形三角盤、跳び先表、大域変数の定義、変形三角盤の下限値、解法プログラム、実行結果、ペグのグループ分け、下限値の改善、実行結果 (2)
2023/07/16 N Queens Problem
8 クイーンの解法、プログラムの作成、実行結果、8 クイーンの高速化、実行結果 (2)、ちょっと便利なビット操作関数、ビット演算による高速化、N Queens Problem の高速化、実行結果 (3)、Appendix : ペグ・ソリテアの高速化
2023/07/16 箱入り娘
パズルの説明、盤面と駒の定義、駒の移動、キューとハッシュ表の定義、幅優先探索による解法、実行結果

●思考ルーチン編

2020/05/16 ミニマックス法と三目並べ
ゲームの木、ミニマックス法、三目並べ、プログラムの作成、勝敗の判定、先手の指し手、後手の指し手、初手の評価値を求める、実行結果、戦略に基づいたプレイ、プログラムの作成 (2)、実行結果 (2)
2020/05/17 アルファベータ法とミニミニリバーシ
ミニミニリバーシ、盤面のデータ構造、反転する石を求める、ミニマックス法のプログラム、実行結果、アルファベータ法、アルファベータ法のプログラム、実行結果 (2)、探索順序の変更
2020/05/24 ネガマックス法とネガアルファ法
ネガマックス法、ネガアルファ法、ネガアルファ法の改良、プログラムの作成、実行結果、4 行 6 列盤リバーシ
2020/05/24 ネガスカウト法
null window search、ネガスカウト法、プログラムの作成、実行結果
2020/05/31 置換表と MTD(f) 法
置換表とは？、ネガマックス法と置換表、プログラムの作成、実行結果、アルファベータ法と置換表、実行結果 (2)、MTD(f) 法、実行結果 (3)

●圧縮アルゴリズム編

2020/05/31 ヒープとハフマン符号
ヒープとは？、ヒープの仕様、構造体の定義、ヒープの構築 (1)、ヒープの再構築、ヒープの構築 (2)、補助関数の作成、実行例、ハフマン符号、ハフマン符号のアルゴリズム、符号木の定義、出現頻度表の作成、ハフマン木の生成、符号化と復号
2020/05/31 ハフマン符号 (2)
エントロピーとは？、ビット入出力処理の作成、ビットストリームの生成、ビットストリームからの入力、ビットストリームへの出力、符号木の取り扱い、符号化のプログラム、復号のプログラム、実行結果
2023/07/15 整数の符号化
符号の種類、γ符号とδ符号、CBT 符号、ゴロム・ライス符号、プログラムの作成、MTF (Move To Front) 法、MTF 法のプログラム、実行結果
2020/05/31 Lisp で算術符号
算術符号の符号化、算術符号の復号、符号化のプログラム、復号のプログラム、適応型算術符号、符号化のプログラム、復号のプログラム
2020/06/07 Lisp でレンジコーダ
レンジコーダの基本的な考え方、レンジコーダの符号化、レンジコーダの復号、符号化のプログラム、復号のプログラム、適応型レンジコーダ
2020/06/07 レンジコーダ (2)
レンジコーダの実装、出現頻度表と累積度数表の作成、符号化のプログラム、桁上がりの処理、符号化の終了処理、ファイルの符号化、復号のプログラム、ファイルの復号、実行結果
2020/06/07 適応型レンジコーダ
静的符号化と動的符号化、Binary Indexed Tree、構造体の定義、累積度数の求め方、出現頻度の求め方、出現頻度の更新、記号の探索、簡単な実行例、出現頻度表の初期化と更新、適応型レンジコーダの符号化、適応型レンジコーダの復号、実行結果
2023/07/15 バイナリレンジコーダ
バイナリレンジコーダと数値の対応、αモデル、バイナリモデル、バイナリレンジコーダのプログラム、バイナリモデルの作成、実行結果
2023/07/15 有限文脈モデル
マルコフ情報源モデル、有限文脈モデル、プログラムの作成、実行結果、適応型レンジコーダの改良、バイナリレンジコーダによる実装
2023/07/15 有限文脈モデル (2)
PPM (Prediction by Partial Matching) とエスケープ記号、エスケープ確率の計算方法、出現頻度表の生成と更新、update exclusion、符号化と復号処理、実行結果、exclusion、exclusion の実装、実行結果 (2)

●micro Scheme 編

2021/07/03 Common Lisp で作る micro Scheme
Scheme の特徴、最小の Lisp 処理系、S 式の評価、関数適用、変数束縛と値の取得、シンタックス形式の処理、read-eval-print-loop、簡単な実行例、レキシカルスコープとクロージャの動作、再帰定義とリスト操作、ダイナミックスコープと funarg 問題
2021/07/03 Common Lisp で作る micro Scheme (2)
マクロの定義、バッククオートの処理、マクロの評価、set! と eqv? の追加、リードマクロ、let、and と or、let*、letrec、名前付き let、begin、cond、case、do
2021/07/03 Common Lisp で作る micro Scheme (3)
継続渡しスタイルによる継続の実装、継続とは？、S 式の評価の修正、シンタックス形式の修正、マクロの修正、関数適用の修正、REPL の修正、簡単な実行例、大域脱出、繰り返しからの脱出、再帰呼び出しからの脱出、イテレータの生成、末尾再帰最適化
2021/07/03 Common Lisp で作る micro Scheme (4)
末尾呼び出しの最適化、m-if と eval-body の修正、m-eval の修正、マクロ展開の修正、簡単な実行例、たらいまわし関数、遅延評価
2021/07/03 Common Lisp で作る micro Scheme コンパイラ
SECD 仮想マシン、SECD 仮想マシンの命令、コンパイラの作成、引数とラムダ式本体の評価、局所変数の位置を求める、簡単なコンパイルのテスト、仮想マシンの作成、read-eval-print-loop、簡単な実行例、レキシカルスコープとクロージャの動作、再帰定義とリスト操作
2021/07/03 Common Lisp で作る micro Scheme コンパイラ (2)
マクロの定義、マクロのコンパイル、バッククオートの処理、簡単な実行例、set! と eqv? の追加、let、and と or、let*、letrec、名前付き let、begin、cond、case、do
2021/07/03 Common Lisp で作る micro Scheme コンパイラ (3)
継続の実装、call/cc のコンパイル、ldct の追加と app の修正、apply の実装、簡単な実行例、大域脱出、繰り返しからの脱出、再帰呼び出しからの脱出、イテレータの生成
2021/07/03 Common Lisp で作る micro Scheme コンパイラ (4)
末尾呼び出しの最適化、コンパイラの修正、仮想マシンの修正、簡単な実行例、たらいまわし関数、遅延評価
2021/07/03 Appendix: ldg, gset 命令の改良
2021/07/03 Appendix: バッククォートの修正
2021/07/03 funarg 問題
funarg 問題とは？、function と quote の違い、ダイナミックスコープで動作する場合、ダイナミックスコープでも動作しない場合、クロージャの導入、クロージャは環境を保持する、クロージャを使用するときの注意点

はじめに

LISP (リスプ, 名前は list processor に由来) は、1958 年にジョン・マッカーシー氏 (John McCarthy) によって開発された「関数型言語」の元祖で、「ラムダ計算」という数学の理論に基づいた言語です。LISP は記号処理が得意な言語で、コンピュータが数値計算だけではなく、他の分野に応用できることを示した最初の言語といえます。人工知能の研究や数式処理といった分野で使われていましたが、他の分野でも活躍しています。現在、ユーザが一番多い処理系はエディタ Emacs に搭載されている Emacs Lisp ではないでしょうか。

LISP は時代とともに変化し、いろいろな言語に影響を与えてきました。たとえば、今では Java やスクリプト言語で当たり前のように使われている機能、不要になったメモリを自動的に回収する「ガベージコレクション (garbage collection)」は LISP で培われた技術です。また、たいていのスクリプト言語で実装されている「クロージャ (closure)」という機能も LISP から取り入れたものです。

LISP は今でも現役の言語です。言語仕様がきれいでコンパクトにまとまっている Scheme と、いろいろな方言に分かれていた LISP を標準化するために制定された Common Lisp という仕様が有名です。知名度は少々劣りますが、ISO (International Organization for Standardization, 国際標準化機構) が 1997 年に策定した ISLisp という仕様もあります。

Common Lisp は 1994 年に ANSI によって標準化されました。この規格 ANSI INCITS X3.226-1994 (R2004) のことを ANSI Common Lisp といい、処理系のことを Common Lisp と呼ぶこともあります。ANSI Common Lisp に準拠した処理系は多数開発されていますが、フリーで有名なところでは CLISP や Steel Bank Common Lisp (SBCL) などがあります。

本稿では、簡単なプログラムを作りながら Common Lisp の基本をゆっくりと解説していこうと思っています。基本的には拙作のページ xyzzy Lisp Programming / Common Lisp 入門をなぞっていきますが、ANSI Common Lisp に合わせた加筆や修正を行おうと思っています。いつものように、お気楽なページにしかなりませんが、興味のある方はお付き合いくださいませ。

●SBCL のダウンロード

本稿では処理系に Steel Bank Common Lisp (SBCL) を使用することにします。SBCL は次のサイトからダウンロードできます。

Download - Steel Bank Common Lisp

SBCL は Windows 用のバイナリが用意されているので、簡単にインストールすることができます。Windows の最新版は version 1.4.14 です (2020 年 1 月)。Linux 系 OS の場合、パッケージ管理システムを使ったほうが簡単でしょう。Ubuntu であれば、次のコマンドで SBCL をインストールすることができます。

sudo apt install sbcl

Ubunts 18.04 (Windows Subsystem for Linux) の場合、sbcl version 1.4.5 がインストールされます (2020 年 1 月)。

●プログラムの実行

シェル (Windows であれば cmd.exe, Unix 系 OS であれば bash など) でコマンド sbcl を実行すると、メッセージとプロンプト * が表示されて SBCL が起動します。

$ sbcl
This is SBCL 1.4.5.debian, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses.  See the CREDITS and COPYING files in the
distribution for more information.
*

この状態で Lisp のプログラムを入力して簡単に実行することができます。これを REPL (read - eval - print - loop, 対話モードのこと) といいます。終了する場合は (quit) と入力してください。Unix 系 OS であれば CTRL-D を入力しても終了することができます。

REPL でソースファイル source.lisp を読み込むときは (load "source.lisp") とします。Common Lisp の場合、拡張子は .lisp が一般的です。このほかに、.lsp や .l が使われることもあります。sbcl の起動時にソースファイルを読み込みたい場合はオプション --load で指定します。

sbcl --load source.lisp

オプション --script を指定すると、sbcl をスクリプト言語のように使うこともできます。

sbcl --script source.lisp

source.lisp を読み込んでプログラムを実行したあと sbcl を終了します。

なお、Windows 版 SBCL はコマンドラインの編集やコマンド履歴をたどることができますが、Ubuntu 版はそのままではできません。この場合、rlwrap をインストールすると便利になります。

sudo apt install rlwrap

あとはシェルで rlwrap sbcl を実行するだけです。簡単なプログラムであれば、これだけでもかなり便利になります。

●簡単なベンチマーク

SBCL はプログラムをネイティブコードにコンパイルする処理系です。REPL から入力されたプログラムもコンパイルしてから実行されます。その実行速度ですが、拙作のページ Algorithms with Python 再帰定義の「たらいまわし関数」を使って調べてみました。

リスト : たらいまわし関数 (Common Lisp)

(defun tak (x y z)
  (if (<= x y)
      z
    (tak (tak (1- x) y z)
         (tak (1- y) z x)
         (tak (1- z) x y))))

それでは実行結果を示します。(tak 22 11 0) を計算しました。実行時間は (time (tak 22 11 0)) で計測できます。

表 : tak(22, 11, 0) の結果
処理系	秒
Python (ver 3.6.9)	69.6
Lua (ver 5.3.3)	37.2
Ruby (ver 2.5.1p57)	25.4
Gauche (ver 0.9.9)	25.3
ocamlc (ver 4.05.0)	10.8
SBCL (ver 1.4.5)	6.38
LuaJIT (var 2.1.0-β)	4.02
Julia (ver 1.3.0)	2.02
SBCL (最適化)	1.57
GCC -O2 (ver 7.4.0)	1.23
ocamlopt (ver 4.05.0)	0.97

実行環境 : Ubunts 18.04 (Windows Subsystem for Linux), Intel Core i5-6200U 2.30GHz

Common Lisp の場合、次のように関数単位でデータ型や最適化の指定を行うことができます。

リスト : たらいまわし関数 (Common Lisp, 最適化の指定)

(defun tak (x y z)
  (declare (type fixnum x y z)
	   (optimize (speed 3) (safety 0)))
  (if (<= x y)
      z
    (tak (tak (1- x) y z)
         (tak (1- y) z x)
         (tak (1- z) x y))))

最適化を指定することで SBCL が GCC と同じくらい速くなるとは驚きました。GCC のコンパイルオプションは -O2 を指定しただけなので、他のオプションを指定するともう少し速くなるかもしれません。興味のある方は、ほかのプログラムでも試してみてください。

権利・免責事項など

ただし、これらのプログラムは無保証であり、使用したことにより生じた損害について、作者「広井誠 (Makoto Hiroi)」は一切の責任を負いません。また、これらのプログラムを販売することで利益を得るといった商行為は禁止いたします。

お気楽 CLOS プログラミング入門

オブジェクト指向の基礎知識
オブジェクトとは？、クラスとインスタンス、メソッド、クラスの定義、インスタンスの生成、メソッドの定義、メソッドの選択、スロットのアクセス、point クラス
双方向リスト
双方向リストとは？、双方向リストの仕様、クラスの定義、データの参照、データの更新、データの挿入、データの削除、畳み込みと巡回、データの変換、その他のメソッド、実行例
継承
継承とは？、単一継承の使い方、スロットとメソッドの継承、スーパークラスに同じスロット名がある場合、データ型の継承、メソッドの選択、複数の引数がある場合、メソッドのオーバーライド
継承 (2)
制限付き双方向リスト、継承は is-a 関係を表す、スタックの実装、キューの実装、ディーキューの実装
多重継承
多重継承の使い方、メソッドの選択、スーパークラスに同じスロット名がある場合、多重継承の問題点、Mix-in、クラス enumerable、イテレータを使う方法
二分木
二分木の仕様、クラスの定義、スロットのアクセス、データの探索、データの挿入、データの削除、巡回、畳み込み、実行例
メソッド結合
:before メソッドと :after メソッド、:around メソッド、補助メソッドはアクセスメソッドにも定義できる
インスタンスの初期化
initialize-instance、ベクタによるキューの実装
共有スロット
共有スロットの設定、共有スロットの継承、共有スロットの衝突、局所スロットと共有スロットの衝突
トライとパトリシア
トライとは？、トライの実装方法、クラスの定義、節の操作関数、データの探索、データの挿入、データの削除、巡回と畳み込み、共通接頭辞を持つデータの探索、実行例
パトリシアとは？、パトリシアのクラス定義、部分列のマッチング、子の探索、最長一致の探索、データの探索、データの挿入、データの削除、共通接頭辞を持つデータの探索、実行例 (その２)
積木の移動
クラスの定義、インスタンスの生成、メソッドの作成、実行例、プログラムの改良
ちょっと寄り道 : 分数を使ったパズル
パズル「小町分数 (1) 」、パズル「小町分数 (2) 」、単位分数の和
2023/07/08 平衡木
仕様、プログラムリスト (AA 木、赤黒木、スプレー木)、実行例、簡単なテスト (AA 木、赤黒木、スプレー木)、タクシー数、プログラムの作成、3 通りの解を求める

●履歴

2003 年 9 月 - 12 月初出
2010 年 4 月 24 日改訂
2020 年 3 月 22 日改訂

使用する処理系を SBCL に変更

はじめに

Common Lisp には CLOS (Common Lisp Object System) というオブジェクト指向システムがあります。CLOS はＣ++や Java とはちょっと違ったオブジェクト指向で、とても興味深いシステムです。ANSI Common Lisp に準拠した処理系であれば CLOS を利用することができます。処理系は多数開発されていますが、フリーで有名なところでは CLISP や Steel Bank Common Lisp (SBCL) などがあります。

本ページでは、SBCL を使って簡単なプログラムを作りながら、CLOS の基本を勉強していきたいと思っております。なお、本ページは M.Hiroi の「覚え書」にすぎません。勘違いや間違いなどもあると思います。何かお気づきの点がありましたら、メールでご指摘いただけると助かります。たいしたことはできませんが、よろしければお付き合いくださいませ。

ところで、Common Lisp は初めてという方は、まず最初にお気楽 Common Lisp プログラミング入門をお読みください。Common Lisp の基本を詳しく説明しています。

権利・免責事項など

ただし、これらのプログラムは無保証であり、使用したことにより生じた損害について、作者「広井誠 (Makoto Hiroi)」は一切の責任を負いません。また、これらのプログラムを販売することで利益を得るといった商行為は禁止いたします。

Common Lisp 入門 : 番外編

Common Lisp 入門の番外編です。このドキュメントは拙作のページで説明したデータ構造やアルゴリズムなどのプログラムを Common Lisp 用に加筆・修正したものです。内容は重複していますが、ご了承くださいませ。

権利・免責事項など

仮想計算機 COMETⅡ

2010/12/12 仮想計算機 COMETⅡの簡易シミュレータ
コンピュータの基本構造、アセンブリ言語とアセンブラ、COMETⅡのハードウェア構成、COMETⅡの命令、命令語の構成、S 式によるプログラムの記述、アセンブラの作成、命令語の生成、アセンブラの実行例
2010/12/19 仮想計算機 COMETⅡの簡易シミュレータ (2)
レジスタとメモリの構成、仮想マシンの作成、データ転送、算術演算、論理演算、比較演算、シフト演算、ジャンプ命令、スタック操作とサブルーチン、その他、プログラムのロードと実行、簡単な実行例
2010/12/26 仮想計算機 COMETⅡの簡易シミュレータ (3)
アセンブリ言語の条件分岐と繰り返し、サブルーチンの使い方、サブルーチンの必要性、引数の渡し方、レジスタの保護、サブルーチンの例題、乗算、除算、再帰呼び出し、整数値の表示、エラトステネスの篩
2011/01/02 仮想計算機 COMETⅡの簡易シミュレータ (4) (修正 2011/01/22)
COMET2A の作成、スタックポインタを汎用レジスタとして使う、局所変数とスタックの関係、LINK 命令と UNLK 命令、乗算と除算、アセンブラの修正、仮想マシンの修正、乗算と除算の追加、LINK と UNLINK の追加、簡単な実行例
2011/01/09 仮想計算機 COMETⅡの簡易シミュレータ (5) (改訂 2011/01/22)
COMET2A 用の簡単なライブラリ、フィボナッチ関数、フィボナッチ関数 (2)、ユークリッドの互除法、バブルソート、選択ソート、単純挿入ソート、クイックソート、８クイーン
2011/01/16 仮想計算機 COMETⅡの簡易シミュレータ (6)
メモリの動的割り当て、malloc の動作、free の動作、メモリの管理方法、ブロックの選択アルゴリズム、Common Lisp での実装、first-fit 法、best-fit 法と worst-fit 法、メモリの解放、簡単なテスト
2011/01/23 仮想計算機 COMETⅡの簡易シミュレータ (7)
COMET2A のメモリ管理プログラム、ヒープ領域の初期化、align 擬似命令の追加、メモリの割り当て、メモリの解放、簡単なテスト
2011/01/30 仮想計算機 COMETⅡの簡易シミュレータ (8)
連結リストの構造、連結リストを操作するサブルーチン、セルのデータ構造、セルの生成と廃棄、リストの生成と廃棄、n 番目のセルを求める、データの参照、データの更新、データの挿入、データの削除、データの変換、連結リストの表示、実行例
2011/02/06 仮想計算機 COMETⅡの簡易シミュレータ (9)
リストを操作するサブルーチン、セル領域の初期化、セルの取得、リストの生成、再帰呼び出しとスタックオーバーフロー、畳み込み、リストの削除、エラトステネスの篩
2011/02/13 仮想計算機 COMETⅡの簡易シミュレータ (10)
ガベージコレクションの基礎知識、マークスイープ法によるゴミ集め、Common Lisp での実装、セル領域の初期化、セルの取得、リスト操作関数の実装、ガベージコレクションの実装、簡単な実行例、COMET2A での実装、マークとスイープ、簡単な実行例 (2)
2011/02/20 仮想計算機 COMETⅡの簡易シミュレータ (11)
順列の生成、リストのマージ、マージソート
2011/02/26 仮想計算機 COMETⅡの簡易シミュレータ (付録)
リストのマージ (破壊的修正)、マージソート (破壊的修正)、32 bit 無符号整数演算

Yet Another Common Lisp Problems

2010/11/21 Yet Another Common Lisp Problems (1)
2010/11/21 解答 (1)
2010/11/28 Yet Another Common Lisp Problems (2)
2010/11/28 解答 (2) (別解 (2012/10/08))
2010/12/05 Yet Another Common Lisp Problems (3)
2010/12/05 解答 (3)
2011/07/16 Yet Another Common Lisp Problems (4)
2011/07/16 解答 (4)
2011/07/23 Yet Another Common Lisp Problems (5)
2011/07/23 解答 (5) (2011/12/25,2012/01/08 別解を追加)
2012/12/02 Yet Another Common Lisp Problems (6)
2012/12/02 解答 (6)

権利・免責事項など

ただし、これらのプログラムは無保証であり、使用したことにより生じた損害について、作者「広井誠 (Makoto Hiroi)」は一切の責任を負いません。また、これらのプログラムを販売することで利益を得るといった商行為は禁止いたします。

参考文献, URL

参考文献

Patrick Henry Winston, Berthold Klaus Paul Horn, 『LISP 原書第 3 版 (1) (2)』, 培風館, 1992
Guy L. Steele Jr., 『COMMON LISP 第 2 版』, 共立出版, 1991
黒川利明, 『LISP 入門』, 培風館, 1982
Ravi Sethi (著), 神林靖 (訳), 『プログラミング言語の概念と構造』, アジソンウェスレイ, 1995
小暮裕明, 『オブジェクト指向のすべて』, ＣＱ出版社, 1990
B.J.コックス, A.J.ノボビルスキ, 『オブジェクト指向のプログラミング』, トッパン, 1992
井田昌之, 『new はやわかり Java』, 共立出版, 1997
Bjarne Stroustrup (著), 『プログラミング言語Ｃ++ 第 3 版』, アジソンウェスレイ, 1998
まつもとゆきひろ, 石塚圭樹, 『オブジェクト指向スクリプト言語Ruby』, 株式会社アスキー, 1999

参考 URL

Common Lisp HyperSpec, (LispWorks)
Lisp - Wikipedia

Common Lisp - Wikipedia

Common Lisp Programming

WHAT'S NEW

CONTENTS

お気楽 Common Lisp プログラミング入門

CONTENTS

●入門編

●応用編

●パズルの解法編

●思考ルーチン編

●圧縮アルゴリズム編

●micro Scheme 編

はじめに

●SBCL のダウンロード

●プログラムの実行

●簡単なベンチマーク

権利・免責事項など

お気楽 CLOS プログラミング入門

CONTENTS

●履歴

はじめに

権利・免責事項など

Common Lisp 入門 : 番外編

仮想計算機 COMETⅡ

Yet Another Common Lisp Problems

権利・免責事項など

参考文献, URL

参考文献

参考 URL