Common Lisp Programming

WHAT'S NEW

• 2017/02/26 遅延ストリーム (3), シリーズ (series) を追加
• 2017/02/19 遅延ストリーム (1), (2) を改訂

CONTENTS

• CLISP について (改訂 2010/10/03)
• Common Lisp 入門
  • 番外編
  • データ構造とアルゴリズム
  • パズルの解法
  • Yet Another Common Lisp Problems
• お気楽 CLOS プログラミング入門
• お気楽 ISLisp プログラミング超入門 (別ページへ移動)
• 参考文献

CLISP について

CLISP は GNU GPL ライセンスで配布されている Common Lisp です。Windows 用のバイナリも用意されているので、簡単にインストールすることができます。CLISP からダウンロードのページへ複数のリンクが張られているので、適当なページからダウンロードしてください。 M.Hiroi は SourceForge の CLISP - an ANSI Common Lisp からダウンロードしました。

CLISP はプログラムをバイトコードにコンパイルする方式です。CMUCL や SBCL のようなネイティブコードにコンパイルする処理系にはかなわないと思いますが、バイトコードにコンパイルする方式では速い方だと思います。実際に拙作のページ Memorandum 2000 年 10 月 24 日 の「たらいまわし関数」で実行速度を比較してみました。

リスト : たらいまわし関数 (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))))

CLISP の場合、関数単位でコンパイルすることができます。(compile 'tak) としてください。これで tak をコンパイルすることができます。または、関数 compile-file でファイルをコンパイルし、関数 load でプログラムをロードすることもできます。たとえば、ファイル名を tak.lisp とすると、(compile-file "tak.lisp") で tak.lisp がバイトコンパイルされ、結果がファイル tak.fas に出力されます。次に (load "tak.fas") とすれば、バイトコンパイルされたプログラムをロードすることができます。

それでは実行結果を示します。(tak 18 9 0) を計算しました。実行時間は (time (tak 18 9 0)) で計測できます。使用した Common Lisp は CLISP ver 2.44 と SBCL ver 1.0.29 です。SBCL も Windows 用のバイナリが用意されているので、簡単にインストールすることができます。ただし、Windows 版 SBCL はまだ開発途中で、安定したバージョンはありません。ご自分の責任でご使用ください。

比較のため、Python, Ruby, Gauche (Scheme), Ｃ言語 (GCC) の実行結果を示します。GCC と SBCL 以外の処理系はプログラムをバイトコードにコンパイルするものです。

• 実行環境 : Windows XP, celeron 1.40 GHz

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 を指定しただけなので、他のオプションを指定するともう少し速くなるかもしれません。ちなみに CLISP の場合、最適化を指定しても実行速度はほとんどかわりませんでした。興味のある方は、ほかのプログラムでも試してみてください。

Common Lisp 入門：番外編

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

CONTENTS

• 2008/10/26 継続渡しスタイル
  継続とは？、継続渡しスタイルとは？、再帰呼び出しと継続渡しスタイル、二重再帰と継続渡しスタイル、CPS の便利な使い方
• 2008/10/26 リスト操作と高階関数 (1)
  マッピング、フィルター、畳み込み、畳み込みの使用例、リスト操作関数の一般化、追記 (2009/11/22)
• 2008/11/02 リスト操作と高階関数 (2)
  iota と tabulate、解きほぐし、リストの分割、木の操作関数
• 2008/11/02 メモ化と遅延評価
  たらいまわし関数、メモ化による高速化、メモ化関数、遅延評価による高速化、delay と force の実装
• 2017/02/19 遅延ストリーム (1)
  遅延ストリームの構造、遅延ストリームの生成、遅延ストリームへの変換、遅延ストリームの操作関数、遅延ストリームの連結、高階関数、stream-map の便利な使い方、stream-flatmap、stream-take-while と stream-drop-while、エラトステネスの篩、より高速な方法
• 2017/02/19 遅延ストリーム (2)
  遅延ストリームの併合、集合演算、ハミングの問題、順列の生成、遅延ストリーム版、８クイーンの解法、木の巡回と CPS、木の巡回と遅延ストリーム、ツリーマッチング
• 2017/02/26 遅延ストリーム (3)
  遅延ストリームを遅延オブジェクトで表す、stream-delay、実行速度の比較、問題点
• 2017/02/26 シリーズ (series)
  シリーズとは？、インストール、シリーズの生成、集積関数、マッピング、フィルター、変換関数、ジェネレータとギャザラ、簡単な例題
• 2009/08/09 Common Lisp で作る micro Scheme
  Scheme の特徴、最小の Lisp 処理系、S 式の評価、関数適用、変数束縛と値の取得、シンタックス形式の処理、read-eval-print-loop、簡単な実行例、レキシカルスコープとクロージャの動作、再帰定義とリスト操作、ダイナミックスコープと funarg 問題
• 2009/08/15 Common Lisp で作る micro Scheme (2)
  マクロの定義、バッククオートの処理、マクロの評価、set! と eqv? の追加、リードマクロ、let、and と or、let*、letrec、名前付き let、begin、cond、case、do
• 2009/08/22 Common Lisp で作る micro Scheme (3)
  継続渡しスタイルによる継続の実装、継続とは？、S 式の評価の修正、シンタックス形式の修正、マクロの修正、関数適用の修正、REPL の修正、簡単な実行例、大域脱出、繰り返しからの脱出、再帰呼び出しからの脱出、イテレータの生成、末尾再帰最適化
• 2009/08/29 Common Lisp で作る micro Scheme (4)
  末尾呼び出しの最適化、m-if と eval-body の修正、m-eval の修正、マクロ展開の修正、簡単な実行例、たらいまわし関数、遅延評価
• 2009/09/26 Common Lisp で作る micro Scheme コンパイラ
  SECD 仮想マシン、SECD 仮想マシンの命令、コンパイラの作成、引数とラムダ式本体の評価、局所変数の位置を求める、簡単なコンパイルのテスト、仮想マシンの作成、read-eval-print-loop、簡単な実行例、レキシカルスコープとクロージャの動作、再帰定義とリスト操作
• 2009/09/27 Common Lisp で作る micro Scheme コンパイラ (2)
  マクロの定義、マクロのコンパイル、バッククオートの処理、簡単な実行例、set! と eqv? の追加、let、and と or、let*、letrec、名前付き let、begin、cond、case、do
• 2009/10/03 Common Lisp で作る micro Scheme コンパイラ (3)
  継続の実装、call/cc のコンパイル、ldct の追加と app の修正、apply の実装、簡単な実行例、大域脱出、繰り返しからの脱出、再帰呼び出しからの脱出、イテレータの生成
• 2009/10/04 Common Lisp で作る micro Scheme コンパイラ (4)
  末尾呼び出しの最適化、コンパイラの修正、仮想マシンの修正、簡単な実行例、たらいまわし関数、遅延評価
  2012/03/04 Appendix: ldg, gset 命令の改良
  2013/08/24 Appendix: バッククォートの修正
• 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 無符号整数演算
• 2015/05/23 funarg 問題
  funarg 問題とは？、function と quote の違い、ダイナミックスコープで動作する場合、ダイナミックスコープでも動作しない場合、クロージャの導入、クロージャは環境を保持する、クロージャを使用するときの注意点、(追記 2015/06/06)

データ構造とアルゴリズム

• 2003/12/03 Lisp で算術符号
  算術符号の符号化、算術符号の復号、符号化のプログラム、復号のプログラム
• 2003/12/03 Lisp で適応型算術符号
  符号化のプログラム、復号のプログラム
• 2003/12/03 Lisp でレンジコーダ
  レンジコーダの基本的な考え方、レンジコーダの符号化、レンジコーダの復号、符号化のプログラム、復号のプログラム
• 2003/12/03 二分木：データの削除
  二分木からデータを削除する、プログラムの作成
• 2003/12/03 2 色木（その１）
  2 色木とは？、二分木の回転操作、データの挿入、プログラムの作成、実行例
• 2003/12/03 2 色木（その２）
  データの削除、木の修正、プログラムの作成、バランスの修正、実行例
• 2006/06/03 スプレイ木
  スプレイ操作の基本、Top-Down Splay、Splay 操作のプログラム、データの探索、データの挿入、データの削除
• 2010/09/26 ヒープとハフマン符号
  ヒープとは？、ヒープの仕様、構造体の定義、ヒープの構築 (1)、ヒープの再構築、ヒープの構築 (2)、操作関数の作成、実行例、ハフマン符号、ハフマン符号のアルゴリズム、符号木の定義、出現頻度表の作成、ハフマン木の生成、符号化と復号
• 2010/10/03 ハフマン符号 (2)
  エントロピーとは？、ビット入出力処理の作成、ビットストリームの生成、ビットストリームからの入力、ビットストリームへの出力、符号木の取り扱い、符号化のプログラム、復号のプログラム、実行結果
• 2010/10/10 レンジコーダ (2)
  レンジコーダの実装、出現頻度表と累積度数表の作成、符号化のプログラム、桁上がりの処理、符号化の終了処理、ファイルの符号化、復号のプログラム、ファイルの復号、実行結果
• 2010/10/17 適応型レンジコーダ
  静的符号化と動的符号化、Binary Indexed Tree、構造体の定義、累積度数の求め方、出現頻度の求め方、出現頻度の更新、記号の探索、簡単な実行例、出現頻度表の初期化と更新、適応型レンジコーダの符号化、適応型レンジコーダの復号、実行結果
• 2010/10/24 整数の符号化
  符号の種類、γ符号とδ符号、CBT 符号、ゴロム・ライス符号、プログラムの作成、MTF (Move To Front) 法、MTF 法のプログラム、実行結果
• 2010/10/31 バイナリレンジコーダ
  バイナリレンジコーダと数値の対応、αモデル、バイナリモデル、バイナリレンジコーダのプログラム、バイナリモデルの作成、実行結果
• 2010/11/07 有限文脈モデル
  マルコフ情報源モデル、有限文脈モデル、プログラムの作成、実行結果、適応型レンジコーダの改良、バイナリレンジコーダによる実装
• 2010/11/14 有限文脈モデル (2)
  PPM (Prediction by Partial Matching) とエスケープ記号、エスケープ確率の計算方法、出現頻度表の生成と更新、update exclusion、符号化と復号処理、実行結果、exclusion、exclusion の実装、実行結果 (2)
• 2012/01/14 動的計画法
  組み合わせの数、動的計画法による高速化、動的計画法とメモ化、整数の分割、部分和問題、分岐限定法による解法、動的計画法による解法、ナップザック問題、プログラムの作成、実行結果
• 2014/01/26 Algorithm X
  敷き詰め問題、Exact Cover Problem、プログラムの作成 (1)、実行結果 (1)、Algorithm X の基本、連結リストによる Algorithm X の実装、プログラムの作成 (2)、実行結果 (2)
• 2014/02/01 Dancing Links
  Dancing Links とは？、Dancing Links の操作方法、データ構造の定義、Dancing Links の生成、行と列の削除、行と列の復元、Dancing Links による Algorithm X の実装、実行結果

パズルの解法

• 2003/12/10 パズル「フリップ・イット」
  パズルの説明、プログラムの作成、フリップ・イットの解答、フリップ・イットの最長手数、ルールの変更
• 2005/02/06 三目並べ
  ゲームの説明、プログラムの作成、実行結果
• 2005/02/25 変形魔方陣
  問題１、プログラムの作成、問題２、問題３
• 2010/09/05 ペグ・ソリテア
  ペグ・ソリテアの説明、変形三角盤、跳び先表、大域変数の定義、変形三角盤の下限値、解法プログラム、実行結果、ペグのグループ分け、下限値の改善、実行結果 (2)
• 2010/09/12 N Queens Problem
  8 クイーンの解法、プログラムの作成、実行結果、8 クイーンの高速化、実行結果 (2)、ちょっと便利なビット操作関数、ビット演算による高速化、N Queens Problem の高速化、実行結果 (3)、Appendix : ペグ・ソリテアの高速化
• 2010/09/19 箱入り娘
  パズルの説明、盤面と駒の定義、駒の移動、キューとハッシュ表の定義、幅優先探索による解法、実行結果

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)

権利・免責事項など

『Common Lisp 入門：番外編』の著作権は筆者「広井誠 (Makoto Hiroi) 」が保持します。無断使用や無断転載は禁止いたします。『Common Lisp 入門：番外編』で作成したプログラムはフリーソフトウェアとします。ご自由にお使いください。プログラムの改造や配布もご自由にどうぞ。その際は、出典を明記してくださるようお願いいたします。

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

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

CONTENTS

• はじめに
• 権利・免責事項など

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

はじめに

Common Lisp には CLOS (Common Lisp Object System) というオブジェクト指向システムがあります。CLOS はＣ++や Java とはちょっと違ったオブジェクト指向で、とても興味深いシステムです。残念ながら xyzzy Lisp は CLOS をサポートしていませんが、CLOS を利用できるフリーの Lisp 処理系がいくつかあります。

その中で Windows でも動作する処理系に CLISP があります。この CLISP を使って、CLOS でオブジェクト指向を勉強しながらプログラミングを楽しもう というのが本ページの趣旨であります。まあ、実際に CLOS を使うのは M.Hiroi も初めてなので、少しずつですが勉強したことをこのページで公開できればいいなと思っています。お付き合いのほどよろしくお願いいたします。

ところで、Common Lisp は初めてという方は、まず最初に xyzzy Lisp Programming：Common Lisp 入門 をお読みください。Common Lisp の基本を詳しく説明しています。

権利・免責事項など

『お気楽 CLOS プログラミング入門』の著作権は筆者「広井誠 (Makoto Hiroi) 」が保持します。無断使用や無断転載は禁止いたします。『お気楽 CLOS プログラミング入門』で作成したプログラムはフリーソフトウェアとします。ご自由にお使いください。プログラムの改造や配布もご自由にどうぞ。その際は、出典を明記してくださるようお願いいたします。

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

参考文献

1. Patrick Henry Winston, Berthold Klaus Paul Horn, 『LISP 原書第 3 版 (1) (2)』, 培風館, 1992
2. Guy L. Steele Jr., 『COMMON LISP 第 2 版』, 共立出版, 1991
3. 小暮裕明, 『オブジェクト指向のすべて』, ＣＱ出版社, 1990
4. B.J.コックス, A.J.ノボビルスキ, 『オブジェクト指向のプログラミング』, トッパン, 1992
5. 井田昌之, 『new はやわかり Java』, 共立出版, 1997