Easy-ISLisp (EISL) は笹川さんが開発されている ISLisp に準拠した Lisp 処理系です。Easy-ISLisp は GitHub で公開されています。
インストール方法や使い方はドキュメント (https://github.com/sasagawa888/eisl/blob/master/README-ja.md) に書かれていますので、そちらをお読みください。M.Hiroi は ver2.65 (2022 年 12 月時点の最新版) を Ubunts 20.04 (WSL1) にインストールしました。
Easy-ISLisp にはコンパイラが搭載されています。Lisp プログラムをＣ言語に変換し、それを GCC でコンパイルします。オブジェクトファイルが生成されるので、それを動的にリンクします。これで、コンパイルされた関数を使用することができます。いつものように「たらいまわし関数」で試してみましょう。
リスト : たらいまわし関数 (tak.lsp)
(defun tak (x y z)
(if (<= x y)
z
(tak (tak (- x 1) y z)
(tak (- y 1) z x)
(tak (- z 1) x y))))
コンパイルは簡単です。eisl を起動するときに -c オプションを付けます。あとは REPL で (compile-file "tak.lsp") とするだけです。これでオブジェクトファイル tak.o が生成されます。動的リンクも簡単で、(load "tak.o") とするだけです。実行結果は次のようになりました。
$ eisl -c Easy-ISLisp Ver2.65 > (compile-file "tak.lsp") type inference initialize pass1 pass2 compiling TAK finalize invoke CC T > (load "tak.o") T > (time (tak 22 11 0)) Elapsed Time(second)=21.609437 <undef> 実行環境 : xubuntu 20.04 on (WSL1), Intel Core i5-6200U 2.30GHz
SBCL にはかないませんが、Lisp プログラミングを楽しむには十分すぎる速度を叩き出しています。インタプリタでデバッグして、コンパイラで高速化する、まさに Lisp らしい開発環境だと思います。
Easy-ISLisp には型推論とデータ型を指定する機能があります。この機能を使うとたらいまわし関数はもっと速くなります。型推論については下記のページを参照してください。
引数のデータ型を小整数 (fixnum) に指定して試してみます。プログラムは次のようになります。
リスト : たらいまわし関数 (tak1.lsp)
(defun tak (x y z)
(the <fixnum> x) (the <fixnum> y) (the <fixnum> z)
(if (<= x y)
z
(tak (tak (- x 1) y z)
(tak (- y 1) z x)
(tak (- z 1) x y))))
Easy-ISLisp の場合、データ型の指定には the という構文を使います。これで引数 x, y, z のデータ型が fixnum であることをコンパイラに教えることができます。実行結果は次のようになりました。
$ eisl -c Easy-ISLisp Ver2.65 > (compile-file "tak1.lsp") type inference initialize pass1 pass2 compiling TAK finalize invoke CC T > (load "tak1.o") T > (time (tak 22 11 0)) Elapsed Time(second)=2.969726 <undef>
7 倍ちょっと高速化することができました。SBCL で最適化を施すと約 1.57 秒になるので、それよりも少し遅い結果になりましたが、最適化の効果は十分に出ていると思います。Easy-ISLisp を開発している笹川さんに感謝です。興味のある方はいろいろ試してみてください。
Lisp の場合、データ構造を表すのにリストがよく使われます。ところが、問題によってはリストよりもビットで表した方が、プログラムを作るのに都合がよい場合もあります。ISLisp の場合、整数の論理演算やビット操作は仕様に規定されていませんが、Easy-ISLisp のライブラリ bit には Common Lisp ライクな関数が用意されています。
基本的な論理演算を行う主な関数を下表に示します。
| 関数名 | 機能 |
|---|---|
| logand integer1 integer2 | ビットごとの論理積を返す |
| logior integer1 integer2 | ビットごとの論理和を返す |
| logxor integer1 integer2 | ビットごとの排他的論理和を返す |
| lognot integer | ビットごとの論理的な否定を返す |
Easy-ISLisp の場合、logand, logior, logxor は 2 引数の関数として定義されていることに注意してください。これらの関数を使用するときはライブラリ bit を import してください。
> (import "bit") T
logand は引数に対するビットごとの論理積を返します。
> (logand #b0101 #b0011) 1
#b0101
and #b0011
-----------
#b0001
logior は引数に対するビットごとの論理和を返します。
> (logior #b0101 #b0011) 7
#b0101
or #b0011
----------
#b0111
logxor は引数に対するビットごとの排他的論理和を返します。
> (logxor #b0101 #b0011) 6
#b0101
xor #b0011
-----------
#b0110
lognot は引数に対するビットごとの論理的な否定を返します。
> (lognot 0) -1 ; #b1111 .... 1111 > (logand 0 -1) 0 > (lognot 1) -2 ; #b1111 .... 1110 > (logand 1 -2) 0
基本的なビット操作関数を下表に示します。
| 関数名 | 機能 |
|---|---|
| logtest intger1 integer2 | (not (zerop (logand integer1 integer2))) と同じ |
| logbitp index integer | index 番目のビットが 1 ならば真を返す |
| logcount integer | integer が正ならば 1 のビットの数を、負ならば 0 のビットの数を返す |
| ash integer count | count が正ならば count ビットだけ左シフト、負ならば右シフトする |
logtest は logand の結果が 0 であれば NIL を、そうでなければ T を返します。
> (logtest 3 1) T > (logand 3 1) 1 > (logtest 3 4) NIL > (logand 3 4) 0
logbitp は添字 index の位置にある integer のビットが 1 ならば T を返します。逆に 0 ならば NIL を返します。ビットの位置は配列と同じく 0 から数えます。
> (logbitp 0 #b0101) T > (logbitp 1 #b0101) NIL
logcount は integer が正の値であれば 1 のビットを数えて返します。負の値であれば 0 のビットを数えて返します。
> (logcount 13) 3 ; #b...0001101 > (logcount -13) 2 ; #b...1110011
ash は integer を count ビット左シフトします。下位ビットには 0 が挿入されます。count が負の値であれば count ビット右シフトします。この場合、正の整数では上位ビットに 0 が挿入されます。負の整数では 1 が挿入されます。これを「算術シフト」といいます。
> (ash 1 8) 256 > (ash -1 8) -256 > (ash 256 -8) 1 > (ash -256 -8) -1
最も右側 (LSB 側) にある 1 を 0 にクリアする、逆に最も右側にある 0 を 1 にセットすることは簡単にできます。
(1) 右側にある 1 をクリア => x AND (- x) x : 1 1 1 1 x - 1 : 1 1 1 0 ---------------- AND : 1 1 1 0 x : 1 0 0 0 x - 1 : 0 1 1 1 ---------------- AND : 0 0 0 0 (2) 右側にある 0 を 1 にセット => x OR (x + 1) x : 0 0 0 0 x + 1 : 0 0 0 1 ---------------- OR : 0 0 0 1 x : 0 1 1 1 x + 1 : 1 0 0 0 ---------------- OR : 1 1 1 1
上図 (1) を見てください。x から 1 を引くと、右側から連続している 0 は桁借りにより 1 になり、最初に出現する 1 が 0 になります。したがって、x AND (x - 1) を計算すると、最も右側にある 1 を 0 にクリアすることができます。(2) の場合、x に 1 を足すと、右側から連続している 1 は桁上がりにより 0 になり、最初に出現する 0 が 1 になります。x OR (x + 1) を計算すれば、最も右側にある 0 を 1 にセットすることができます。
また、最も右側にある 1 を取り出すことも簡単にできます。簡単な例として 4 ビットの整数値を考えてみます。負の整数を 2 の補数で表した場合、4 ビットで表される整数は -8 から 7 になります。次の図を見てください。
0 : 0000
1 : 0001 -1 : 1111 1 AND (-1) => 0001
2 : 0010 -2 : 1110 2 AND (-2) => 0010
3 : 0011 -3 : 1101 3 AND (-3) => 0001
4 : 0100 -4 : 1100 4 AND (-4) => 0100
5 : 0101 -5 : 1011 5 AND (-5) => 0001
6 : 0110 -6 : 1010 6 AND (-6) => 0010
7 : 0111 -7 : 1001 7 AND (-7) => 0001
-8 : 1000
図 : 最も右側にある 1 を取り出す方法
2 の補数はビットを反転した値 (1 の補数) に 1 を加算することで求めることができます。したがって、x と -x の論理積 x AND (-x) は、最も右側にある 1 だけが残り、あとのビットはすべて 0 になります。
次は、ビットが 1 の個数を数える処理を作ってみましょう。Common Lisp や Easy-ISLisp には関数 logcount がありますが、私達でも簡単にプログラムすることができます。次のリストを見てください。
リスト : ビットカウント
(defun bit-count (n)
(for ((n n (logand n (- n 1)))
(c 0 (+ c 1)))
((= n 0) c)))
整数 n の右側から順番に 1 をクリアしていき、0 になるまでの回数を求めます。とても簡単ですね。
整数を 32 bit に限定する場合、次の方法で 1 の個数をもっと高速に求めることができます。
リスト : ビットカウント (2)
(defun bit-count32 (n)
(let* ((a (+ (logand n #x55555555) (logand (ash n -1) #x55555555)))
(b (+ (logand a #x33333333) (logand (ash a -2) #x33333333)))
(c (+ (logand b #x0f0f0f0f) (logand (ash b -4) #x0f0f0f0f)))
(d (+ (logand c #x00ff00ff) (logand (ash c -8) #x00ff00ff))))
(+ (logand d #xffff) (ash d -16))))
最初に、整数を 2 bit ずつに分割して 1 の個数を求めます。たとえば、整数 N を 4 bit で考えてみましょう。5 を 2 進数で表すと 0101 になります。N と論理積を計算すると 0, 2 番目のビットが 1 であれば、結果の 0, 2 番目のビットは 1 になります。同様に N を 1 ビット右シフトして論理積を計算すると、1, 3 番目のビットが 1 であれば、結果の 0, 2 番目のビットは 1 になります。あとは、それを足し算すれば 2 bit の中にある 1 の個数を求めることができます。
変数 A には 2 ビットの中の 1 の個数が格納されています。左隣の 2 ビットの値を足し算すれば、4 ビットの中の 1 の個数を求めることができます。次に、左隣の 4 ビットの値を足し算して 8 ビットの中の 1 の個数を求め、左隣の 8 ビットの値を足し算して、というように順番に値を加算していくと 32 ビットの中にある 1 の個数を求めることができます。
bit-count は 1 の個数が多くなると遅くなりますが、bit-count32 は 1 の個数に関係なく高速に動作します。興味のある方は試してみてください。
このたび、笹川さんが開発されている Easy-ISLisp が ver 2.98 にバージョンアップしました (2023 年 5 月末日)。このとき、拙作のプログラム「ハッシュ表」をライブラリに追加していただきました。笹川さん、ありがとうございます。本ページで作成したプログラムはフリーソフトウェアとして公開しています。どうぞご自由にお使いくださいませ。
拙作のハッシュ表は素朴な実装なので、基本的な機能しか用意しておりません。Python の辞書のように、ハッシュからキーや値、キーと値のペアを求める総称関数があると便利かもしれません。関数名を keys, values, items とすると、これらの関数は関数 maphash や畳み込みを行う関数 reducehash を使うと簡単に定義することができます。次のリストを見てください。
リスト : ハッシュ表の操作関数
(defgeneric reducehash (f a h))
(defgeneric keys (h))
(defgeneric values (h))
(defgeneric items (h))
;; 畳み込み
(defmethod reducehash (f a (h <hash>))
(for ((i 0 (+ i 1)))
((>= i (hash-size h)) a)
(for ((xs (aref (hash-table h) i) (cdr xs)))
((null xs))
(setq a (funcall f a (caar xs) (cdar xs))))))
;; キーを取り出す
(defmethod keys ((h <hash>))
(reducehash (lambda (a k v) (cons k a)) nil h))
;; 値を取り出す
(defmethod values ((h <hash>))
(reducehash (lambda (a k v) (cons v a)) nil h))
;; キーと値を取り出す
(defmethod items ((h <hash>))
(reducehash (lambda (a k v) (cons (list k v) a)) nil h))
reducehash f a h はハッシュ表 h の要素 (key, val) に関数 f を適用して畳み込みを行います。f の第 1 引数が累積値、第 2 引数が key で第 3 引数が val になります。
Easy-ISLisp での簡単な実行例を示します。
> (load "hash.lsp")
T
> (defglobal h (create (class <hash>)))
H
> h
<instance>
> (sethash h "foo" 10)
10
> (sethash h "bar" 20)
20
> (sethash h "baz" 30)
30
> (keys h)
("foo" "baz" "bar")
> (values h)
(10 30 20)
> (items h)
(("foo" 10) ("baz" 30) ("bar" 20))
それではハッシュ表の簡単な例題として、「タクシー数」を取り上げます。不定方程式 X3 + Y3 = Z には整数解が存在します。たとえば、Z = 2 のときの解は 13 + 13 の一通りしかありませんが、Z の値によっては複数の解が存在します。そして、n 通りの解が存在する Z の中で、最小の値をタクシー数 (taxicab number) といい、n 番目のタクシー数を Ta(n) と書きます。Ta(1) と Ta(2) を示します。
Ta(1) = 2 = 13 + 13
Ta(2) = 1729 = 13 + 123
= 93 + 103
タクシー数 - Wikipedia によると、Ta(n) はすべての整数 n に対して存在することが証明されていて、今までに Ta(1) から Ta(6) までのタクシー数が知られているそうです。
本ページでは問題を簡単にして、次式を満たす整数 a, b, c, d を列挙することにします。
a3 + b3 = c3 + d3
最近のパソコンは高性能なので、単純な四重ループでも簡単に解くことができます。次のリストを見てください。
リスト : タクシー数
(defun taxi (n)
(for ((a 1 (+ a 1)))
((< n a))
(for ((b a (+ b 1)))
((< n b))
(for ((c (+ a 1) (+ c 1)))
((< n c))
(for ((d c (+ d 1)))
((<= b d))
(let ((e (+ (* a a a) (* b b b))))
(if (= (+ (* c c c) (* d d d)) e)
(format (standard-output) "~D: (~D, ~D), (~D,~D)~%" e a b c d))))))))
引数 n が整数の上限値を表します。重複解を削除するため、以下の条件を設定してます。
1. a <= b # a と b を交換した式を削除 2. c <= d # c と d を交換した式を削除 3. a < c # (a, b) と (c, d) を交換した式を削除 4. d < b # 不要な探索を削除
条件 3 で c は a よりも大きくなるので、d は必ず b よりも小さくなります。これを条件 4 で表しています。あとはとくに難しいところはないと思います。
それでは実行してみましょう。
$ eisl Easy-ISLisp Ver2.98 > (load "taxi.lsp") T > (time (taxi 50)) 1729: (1, 12), (9,10) 4104: (2, 16), (9,15) 13832: (2, 24), (18,20) 39312: (2, 34), (15,33) 46683: (3, 36), (27,30) 32832: (4, 32), (18,30) 110656: (4, 48), (36,40) 110808: (6, 48), (27,45) 40033: (9, 34), (16,33) 20683: (10, 27), (19,24) 65728: (12, 40), (31,33) 64232: (17, 39), (26,36) Elapsed Time(second)=0.408518 <undef> > (time (taxi 100)) 1729: (1, 12), (9,10) 4104: (2, 16), (9,15) 13832: (2, 24), (18,20) ・・・省略・・・ 1016496: (47, 97), (66,90) 1009736: (50, 96), (59,93) 684019: (51, 82), (64,75) Elapsed Time(second)=6.987033 <undef>
整数の範囲を 50 から 100 に増やすと、実行時間はかなり遅くなります。
それではプログラムの高速化に挑戦してみましょう。次のようにハッシュ表を使うともっと速くなります。
リスト : タクシー数 (2)
(import "list")
(import "combination")
(import "hash")
(defun taxi-fast (n)
(let ((ht (create (class <hash>))))
(combination
(lambda (xs)
(let* ((a (first xs))
(b (second xs))
(k (+ (* a a a) (* b b b)))
(v (gethash ht k)))
(if v
(format (standard-output) "~D: ~A, ~A~%" k xs (first v)))
(sethash ht k (cons xs v))))
2
(iota 1 n))))
組み合わせを生成する関数 combination を使って 2 つの整数 (xs) を選び、変数 a と b にセットします。それから、その 3 乗和を計算して変数 k にセットし、ハッシュ表 ht から k の値 v を求めます。v が nil でなければ、a3 + b3 = c3 + d3 を満たす解を見つけることができました。format で解を表示します。最後に、k と (cons xs v) をハッシュ表に登録します。
それでは実行してみましょう。
$ eisl Easy-ISLisp Ver2.98 > (load "taxi.lsp") T > (time (taxi-fast 50)) 1729: (9 10), (1 12) 4104: (9 15), (2 16) 39312: (15 33), (2 34) 40033: (16 33), (9 34) 13832: (18 20), (2 24) 32832: (18 30), (4 32) 20683: (19 24), (10 27) 64232: (26 36), (17 39) 46683: (27 30), (3 36) 110808: (27 45), (6 48) 65728: (31 33), (12 40) 110656: (36 40), (4 48) Elapsed Time(second)=0.049371 <undef> > (time (taxi-fast 100)) 1729: (9 10), (1 12) 4104: (9 15), (2 16) 39312: (15 33), (2 34) ・・・省略・・・ 684019: (64 75), (51 82) 1016496: (66 90), (47 97) 885248: (72 80), (8 96) Elapsed Time(second)=0.207389 <undef>
n = 100 の場合、約 35 倍高速化することができました。ハッシュ表の効果は大きいですね
ご参考までに a3 + b3 = c3 + d3 = e3 + f3 の解を求めてみました。
> (time (taxi3 500)) 87539319: (255 414), (228 423), (167 436) 119824488: (346 428), (90 492), (11 493) Elapsed Time(second)=6.822346 <undef>
87539319 が Ta(3) になります。taxi3 は format で解を表示する条件を (= (length v) 2) に変更しただけです。整数の上限値を増やすと、もっと時間がかかるようになります。Ta(4) は大きな値になるので、このような力任せのプログラムだと M.Hiroi の実行環境では Ta(3) くらいが限界のように思います。タクシー数を求めるのは難しい問題だと実感しました。