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 以外の処理系はプログラムをバイトコードにコンパイルするものです。
表 : tak 18 9 0 の結果
| 処理系 | 秒 |
|---|
| Python (ver 2.5.2) | 7.88 |
| Ruby (ver 1.9,0) | 7.42 |
| Gauche (ver 0.8.12) | 3.16 |
| CLISP (ver 2.44) | 2.57 |
| SBCL (ver 1.0.29) | 0.47 |
| GCC (ver 3.4.4) | 0.19 |
| SBCL (最適化) | 0.172 |
- 実行環境 : 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 の場合、最適化を指定しても実行速度はほとんどかわりませんでした。興味のある方は、ほかのプログラムでも試してみてください。
-- 改訂 --------
2010/10/03 たらいまわし関数の実行結果に SBCL (Common Lisp) を追加
Common Lisp 入門 の番外編です。このドキュメントは拙作のページで説明したデータ構造やアルゴリズムなどのプログラムを Common Lisp 用に加筆・修正したものです。内容は重複していますが、ご了承くださいませ。
CONTENTS
- 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 動的計画法
組み合わせの数、動的計画法による高速化、動的計画法とメモ化、整数の分割、部分和問題、分岐限定法による解法、動的計画法による解法、ナップザック問題、プログラムの作成、実行結果
- 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 箱入り娘
パズルの説明、盤面と駒の定義、駒の移動、キューとハッシュ表の定義、幅優先探索による解法、実行結果
『Common Lisp 入門：番外編』の著作権は筆者「広井誠 (Makoto Hiroi) 」が保持します。無断使用や無断転載は禁止いたします。『Common Lisp 入門：番外編』で作成したプログラムはフリーソフトウェアとします。ご自由にお使いください。プログラムの改造や配布もご自由にどうぞ。その際は、出典を明記してくださるようお願いいたします。
ただし、これらのプログラムは無保証であり、使用したことにより生じた損害について、作者「広井誠 (Makoto Hiroi) 」は一切の責任を負いません。また、これらのプログラムを販売することで利益を得るといった商行為は禁止いたします。
Copyright (C) 2003-2012 Makoto Hiroi
All rights reserved.
CONTENTS
- オブジェクト指向の基礎知識
オブジェクトとは？、クラスとインスタンス、メソッド、クラスの定義、インスタンスの生成、メソッドの定義、メソッドの選択、スロットのアクセス、point クラス
- 双方向リスト
双方向リストとは？、双方向リストの仕様、クラスの定義、データの参照、データの更新、データの挿入、データの削除、畳み込みと巡回、データの変換、その他のメソッド、実行例
- 継承
継承とは？、単一継承の使い方、スロットとメソッドの継承、スーパークラスに同じスロット名がある場合、データ型の継承、メソッドの選択、複数の引数がある場合、メソッドのオーバーライド
- 継承 (2)
制限付き双方向リスト、継承は is-a 関係を表す、スタックの実装、キューの実装、ディーキューの実装
- 多重継承
多重継承の使い方、メソッドの選択、スーパークラスに同じスロット名がある場合、多重継承の問題点、Mix-in、クラス enumerable、イテレータを使う方法
- 二分木
二分木の仕様、クラスの定義、スロットのアクセス、データの探索、データの挿入、データの削除、巡回、畳み込み、実行例
- メソッド結合
:before メソッドと :after メソッド、:around メソッド、補助メソッドはアクセスメソッドにも定義できる
- インスタンスの初期化
initialize-instance、ベクタによるキューの実装
- 共有スロット
共有スロットの設定、共有スロットの継承、共有スロットの衝突、局所スロットと共有スロットの衝突
- トライとパトリシア
トライとは？、トライの実装方法、クラスの定義、節の操作関数、データの探索、データの挿入、データの削除、巡回と畳み込み、共通接頭辞を持つデータの探索、実行例
パトリシアとは？、パトリシアのクラス定義、部分列のマッチング、子の探索、最長一致の探索、データの探索、データの挿入、データの削除、共通接頭辞を持つデータの探索、実行例 (その２)
- 積木の移動
クラスの定義、インスタンスの生成、メソッドの作成、実行例、プログラムの改良
- ちょっと寄り道：分数を使ったパズル
パズル「小町分数 (1) 」、パズル「小町分数 (2) 」、単位分数の和
2003 年 9 月 - 12 月 初出
2010 年 4 月 24 日 改訂
はじめに
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) 」は一切の責任を負いません。また、これらのプログラムを販売することで利益を得るといった商行為は禁止いたします。
Copyright (C) 2003-2010 Makoto Hiroi
All rights reserved.
参考文献
●Common Lisp 関連
[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
