M.Hiroi's Home Page

Common Lisp Programming

お気楽 ISLisp プログラミング超入門

[ Home | Common Lisp | ISLisp ]

Easy-ISLisp の機能

Easy-ISLisp (EISL) は 笹川さん が開発されている ISLisp に準拠した Lisp 処理系です。Easy-ISLisp は GitHub で公開されています。

インストール方法や使い方は ドキュメント (日本語) に書かれていますので、そちらをお読みください。M.Hiroi は ver2.65 (2022 年 12 月時点の最新版) を Ubunts 20.04 (WSL1) にインストールしました。

●コンパイラ

Easy-ISLisp にはコンパイラが搭載されています。Lisp プログラムをC言語に変換し、それを 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 integerindex 番目のビットが 1 ならば真を返す
logcount integerinteger が正ならば 1 のビットの数を、負ならば 0 のビットの数を返す
ash integer countcount が正ならば 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
-- note --------
Easy-ISLips ver2.65 の logbitp には不具合があります ver2.70 では修正されています。笹川さんに感謝いたします。

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 の個数を求める

次は、ビットが 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 の個数に関係なく高速に動作します。興味のある方は試してみてください。

●ハッシュ表 (2)

このたび、笹川さんが開発されている 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

参考 URL 1 によると、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) くらいが限界のように思います。タクシー数を求めるのは難しい問題だと実感しました。

●参考 URL

  1. タクシー数 - Wikipedia
  2. 天才数学者ラマヌジャンのタクシー数の研究, (猫野さん)

Copyright (C) 2022-2023 Makoto Hiroi
All rights reserved.

[ Home | Common Lisp | ISLisp ]