関数型言語 Lisp

関数型言語 Lisp

Lisp を少し勉強したのは、バブルまっさかりの頃だった。 そしてバブル崩壊とともにLispも忘れてしまった。 久しぶりに今になって、少し思い出そうとしている。

インストール

Common Lispの処理系として、Vine Linux で apt 化されているのが CLisp だった。 これを apt-get install clisp としてインストールした。

CMUCL のインストール

CLisp をインストールしたあと、まったくLisp の勉強をしなかった。 その後、Vine Linux 4.1 の環境自体がこわれてしまった。 このとき、バックアップをとっていなかったため、データも失われた。 その後、新たに Vine Linux 5.1 を入れた。 新たな処理系としては、CLisp ではなく、CMUCL をインストールした。 これは、ダグ・ホイトの LET OVER LAMNDA で第一に推薦されている処理系である。

起動と終了

起動は単に lisp である。これで、対話式の環境が立ち上がる。

$ lisp
CMU Common Lisp 20a (20A Unicode), running on localhost.localdomain
With core: /usr/local/lib/cmucl/lib/lisp-sse2.core
Dumped on: Tue, 2009-09-29 00:12:34+09:00 on usrtc3154
See <http://www.cons.org/cmucl/> for support information.
Loaded subsystems:
    Unicode 1.5 with Unicode version 5.1.0
    Python 1.1, target Intel x86
    CLOS based on Gerd's PCL 2008-11-12 16:36:41
* 

終了はどうするか、わからなかった。どうやら、次らしい。

* (cl-user::quit)
$

その後 Windows に変わる

その後、Windows が標準環境となった。そこで、CLisp に再度もどした。

Wang のアルゴリズムの実装

論理学における Wang のアルゴリズムを実装した。 といっても、萩谷昌己氏の教科書をまねしただけである。 なお、同氏の実装では関数 memq が組み込まれていることが前提だが、 私がためした CLisp では memq が備わっていないため、マクロを書いた。 マクロは On Lisp に基づいている。

(defmacro memq (obj lst)
	`(member ,obj ,lst :test #'eq))

(defun intersect (x y)
	(if (null x)
			nil
		(if (memq (car x ) y)
				t
			(intersect (cdr x) y))))

(defun wang (l la r ra )
	(if (null l)
			(if (null r)
					(if (intersect la ra)
							t
						nil)
				
				(let ((r0 (car r)) (r1 (cdr r)) )
					(if (atom r0)
							(wang l la r1 (cons r0 ra))
						(case (car r0)
							(not (wang (cons (cadr r0) l) la r1 ra))
							(and (and (wang l la (cons (cadr r0) r1) ra)
												(wang l la (cons (caddr r0) r1) ra)))
     							(or (wang l la
														(cons (cadr r0) (cons (caddr r0) r1)) ra))
			    				(implies (wang (cons (cadr r0) l) la
																 (cons (caddr r0) r1) ra))))))
		
		(let ((l0 (car l)) (l1 (cdr l)))
					(if (atom l0)
							(wang l1 (cons l0 la) r ra)
						(case (car l0)
							(not (wang l1 la (cons (cadr l0) r) ra))
							(and (wang (cons (cadr l0) (cons (caddr l0) l1)) la r ra ))
							(or (and (wang (cons (cadr l0) l1 ) la r ra)
											 (wang (cons (caddr l0) l1 ) la r ra)))
							(implies (and (wang l1 la (cons (cadr l0) r) ra)
														(wang (cons (caddr l0) l1) la r  ra))))))) )
	

参考書

LISP, Prologに、 私が今まで読んできた本をまとめた。

まりんきょ学問所 ＞ 関数型言語手習い ＞ 関数型言語 Lisp