Prolog言語で数独Sudoku

Land of Lispは16章で力尽きてしまいました。そこからいろいろ情報を調べているうちにPrologにたどりついたので、書籍「7つの言語 7つの世界」を本棚から引っ張りだしてPrologをちょっとつかってみました。

Prologをつかってみた感想。

LispをやっていたのでPrologの再起処理は比較的問題ありませんでした。Prologのユニフィケーションでパターンマッチさせる方法はオブジェクト指向言語などとは全然異なる方式なので非常に興味深かったです。あとPrologの書き方がバッカスナウアー記法(BNF)のように感じました。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
valid([]).
valid([Head|Tail]) :-
fd_all_different(Head), valid(Tail).

% パズルを埋める数字と解の数字は一致していなければならない。
% ボードには16のマス目があり、各マス目には1から4の数字が入る
sudoku(Puzzle, Solution) :-
Solution = Puzzle,

Puzzle = [S11, S12, S13, S14,
S21, S22, S23, S24,
S31, S32, S33, S34,
S41, S42, S43, S44],


fd_domain(Puzzle, 1, 4),

Row1 = [S11, S12, S13, S14],
Row2 = [S21, S22, S23, S24],
Row3 = [S31, S32, S33, S34],
Row4 = [S41, S42, S43, S44],

Col1 = [S11, S21, S31, S41],
Col2 = [S12, S22, S32, S42],
Col3 = [S13, S23, S33, S43],
Col4 = [S14, S24, S34, S44],

Square1 = [S11, S12, S21, S22],
Square2 = [S13, S14, S23, S24],
Square3 = [S31, S32, S41, S42],
Square4 = [S33, S34, S43, S44],

valid([Row1, Row2, Row3, Row4,
Col1, Col2, Col3, Col4,
Square1, Square2, Square3, Square4]).

Common LispでC言語?(LISP/c)

Land of Lispの16章まで進みマクロの入門で頭が爆発しそうです。

気晴らしにhacker newsの非公式サイトhckrnews.comをみていたら、LISP/c (Lispsy)を見つけました。CLISPで動作するC言語用のマクロ言語だそうです。まだ何も読んでませんが、CUDAのサンプルなどもあってかなり本格的なようです。しかもファイル数は5つで、そこまでソースコードの量が多くないのも恐ろしいです。

LISPなのにC言語なので、うぅ頭が…

1
2
3
4
(header stdio)
(main
(@printf (str "Hello, world!"))
(return 0))

Common Lispの凄さは、それを知らない人に説明をしても理解してもらえません。でも、このLISP/cは、Lispをさわったことがないプログラマーに、直観的に凄さを伝える良い例ではないでしょうか?

land-of-lisp 16章 マクロ

マクロ実装の基礎

16章では、リストの要素数を求める関数をマクロを使って実装しました。一気にマクロを実装するのではなく、数段階に分けて説明してくれて、マクロの変数展開の失敗例や、デバッグでmarcoexpandを使う方法など、初心者が躓きそうな要点を押さえていて非常に理解しやすかったです。

C言語の#define、#includeなどのマクロはプリプロセスという段階で基本的にはソースコードの置換作業をします。Lispのマクロは、C言語のプリプロセスの段階とおなじ(マクロ展開時といいます)時に、単純な置換ではなく、Lispが実行されて置換・展開作業が行われます。おそらくマクロ展開時と言ってますが、マクロで渡されたものをLispとして評価できるので、Lispを実行できるタイミングが2回ある状態になるのだと思います。(あとで単純なマクロを作成して、引数で渡されたものをマクロ展開時に実行してみようと思います。)

マクロの危険性

以下のようなソースコードが最終的に出来上がり、Lispは括弧とシンボルなど基本的な構造のみなので、何でもできてしまうのが分かりました。

1
2
3
4
5
6
(defun my-length (lst)
(recurse (lst lst
acc 0)
(split lst
(self tail (1+ acc))
acc)))

実際に、reduceを使った実装を見せて、マクロの保守性についてのデメリットにも言及していました。

1
2
3
4
5
(defun my-length (lst)
(reduce (lambda (x i)
(1+ x))
lst
:initial-value 0))

強力すぎる

Lispはマクロでありとあらゆることが出来そうです。言い換えると使うプログラマー側に言語をどのようにするかの決定権があります。地域やプロジェクトごとに好きなように使ってくれという感じでしょうか、これはメリットですが見方によっては柔軟性がありすぎるとも取れます。

いろいろ試したソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
;; letの括弧を省略するマクロ
(defmacro let1 (var val &body body) ; &bodyによりbody変数にはリストでラップされて渡される
;; バッククォートは、シングルクォートと同じでデータとして扱う
;; ただし、,xxxxで変数展開が出来る。
`(let ((,var, val))
,@body))

(defmacro split (val yes no)
(let1 g (gensym) ;; ここはマクロ展開時に実行される
`(let1 ,g ,val
(if ,g
(let ((head (car ,g))
(tail (cdr ,g)))
,yes)
,no))))

(defun test-let1 ()
(princ "UnitTest:test1============")
(fresh-line)
(let1 foo (+ 2 3)
(princ "Lisp is awesome!")
(* foo foo))
(fresh-line))

(defun test-split ()
(princ "UnitTest:split===========")
(fresh-line)
(split (progn (princ "Lisp rocks!")
'(2 3))
(format t "This can be split into ~a and ~a." head tail)
(format t "This cannot be split."))
(fresh-line))

(defun test-split1 ()
(princ "===")
(fresh-line)
(split ()
(format t "aaa")
(format t "bbb"))
(fresh-line))

(defun test-split2 ()
(let1 x 100
(split '(2 3)
(+ x head)
nil)))

;; マクロ展開を確認してみる
(defun test-split3-check ()
(princ "print macroexpand=====")
(fresh-line)
(princ (macroexpand '(split '(2 3)
(+ x head)
nil))))


;;; 再帰呼び出しマクロ
(defun pairs (lst)
(labels ((f (lst acc)
(split lst
(if tail
(f (cdr tail) (cons (cons head (car tail)) acc))
(reverse acc))
(reverse acc))))
(f lst nil)))

(defmacro recurse (vars &body body)
(let1 p (pairs vars)
`(labels ((self ,(mapcar #'car p)
,@body))
(self ,@(mapcar #'cdr p))))) ;; ここの@がわからない, prognの状態になりうるから@を付ける?


(defun runTest ()
(test-let1)
(test-split)
(test-split1)
(test-split2)
(test-split3-check))

(runTest)

(defun my-length (lst)
(recurse (lst lst
acc 0)
(split lst
(self tail (1+ acc))
acc)))

Land of Lisp 14章の説明が素晴らしい

14章の説明が素晴らしい

関数型プログラミングの入門記事を見ると関数型言語のメリットとか、変数は再代入禁止とか、参照透明性とは何か、というのはすごく細かく説明していてなんとなく理解は出来るのですが、どうしても現実をみてしまい、MS-DOSからWindows、Linux、はアセンブラとC言語で動いているし、CPUのレジスターは状態保持しているし、JavaやC#はよく使われていてUnityはインスタンス生成せず、フィールドをIDEで操作できる様が、まさにオブジェクト指向とIDEの融合で…と、いろいろ周りの事を考えてしまいモヤモヤしていました。

Land of Lispの14章はたった10ページですが、C言語やオブジェクト指向言語でプログラミングしてきた人にとって分かりやすく関数型プログラミングのメリットを納得できるかたちで順序立てて説明してくれています。

「14.1 関数型プログラミングって何だ?」ではよくある入門記事の説明と一緒ですが、290ページで、関数型プログラミングスタイルで副作用を含まないコードと、残りの副作用を含む外部とやり取りするコードを明確に分割して、コードを書いていきなさいと助言してくれています。副作用がある部分を明確に分けるというのは、モジュール化やオブジェクトの機能分類と同様で想像しやすくすんなり理解できました。

「14.3 高階プログラミング」では、forループ実装をまず見せて、それを変数をなくした再帰実装にして、最後にmapcarとlambdaに役割分担した実装と説明していきます。この説明と、オブジェクト指向言語などでインスタンス変数をどう使うかや、影響する変数を減らせば保守しやすくなるというのと結びつけて考えることが出来たため、「なるほど、こういうアプローチをすれば確かに変数いらない!」と納得できました。

惜しい

page.295を何も見ないで書いたソースコード

1
2
3
4
5
;; 要素に2を加える
(defun add2 (lst1)
(if (eql lst1 '())
'()
(cons (+ (car lst1) 2) (add2 (cdr lst1)))))

正解

1
2
3
(defun add-two (list)
(when list
(cons (+ 2 (car list)) (add-two (cdr list)))))

Common Lispはwhenがあって、偽の場合NILを返してくれるようです。けれどいい感じに実装できました。

Land-of-lisp 13章の前にSBCLからCLISPに移行する

以下、記事は残しておきますが、この記事で書いてある方法ではSLIMEでCLISPに切り替えられませんでした。

slime-lisp-implementationsなども試しましたが、上手く動作できませんでした。

はじめに

Ubuntu15.10でSLIMEをインストールするときのデフォルトがSBCLだったためそのまま使っていましたが、Common Lispは処理系によって実装を修正しなければいけない場合があります。ちょうどJavaScriptのブラウザー依存に近いです。Land of LispはCLISPを使う前提なためUbuntu15.10上に、CLISPをインストールして、quicklispの再設定とemacsの再設定を行います。

clispのインストール

apt-getだけなので、インストールは簡単です。

1
$ sudo apt-get install clisp

quicklispをclispで使えるようにする

私の環境では、以前SBCLの環境を用意したときに、以下のようにcl-quicklispをインストールしました。

1
sudo apt-get install emacs24-nox slime cl-quicklisp

そのため、/usr/share/cl-quicklisp/quicklisp.lispにファイルがあります。今回はこのquicklispをclispでも使えるようにします。

clisp起動とインストール

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
$ clisp
i i i i i i i ooooo o ooooooo ooooo ooooo
I I I I I I I 8 8 8 8 8 o 8 8
I \ `+' / I 8 8 8 8 8 8
\ `-+-' / 8 8 8 ooooo 8oooo
`-__|__-' 8 8 8 8 8
| 8 o 8 8 o 8 8
------+------ ooooo 8oooooo ooo8ooo ooooo 8

Welcome to GNU CLISP 2.49 (2010-07-07) <http://clisp.cons.org/>

Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2010

Type :h and hit Enter for context help.

[1]>

(load "/usr/share/cl-quicklisp/quicklisp.lisp")を入力して、エンターキーで、quicklispをclispにロードします。

1
2
3
4
5
6
7
8
9
[1]> (load "/usr/share/cl-quicklisp/quicklisp.lisp")
;; Loading file /usr/share/cl-quicklisp/quicklisp.lisp ...

==== quicklisp quickstart loaded ====

To continue, evaluate: (quicklisp-quickstart:install)

;; Loaded file /usr/share/cl-quicklisp/quicklisp.lisp
T

ファイルがロードできたら以下のインストールコマンドをコピペ入力すればインストール完了です。

1
2
3
4
5
6
7
8
[2]> (quicklisp-quickstart:install)

*** - Quicklisp has already been installed. Load #P"/home/satoshiokita/quicklisp/setup.lisp"
instead.
The following restarts are available:
LOAD-SETUP :R1 Load #P"/home/satoshiokita/quicklisp/setup.lisp"
ABORT :R2 Abort main loop
Break 1 [3]>

quicklispのインストールとは、自分のホームディレクトリーに./quicklispディレクトリーを作成して管理することのようです。SBCLで実行したので、(quicklisp-quickstart:install)を行う必要はなかったようです。上記のようにclispで何か間違えたりするとデバッグモードになります。:qを入力してエンターキーで戻ることが出来ます。(quit)でclispが終了できます。

clispが起動したときに使えるようにする

一度、clispを閉じて、再起動してインストール済みの~/quicklisp/setup.lispをロードします。

1
2
3
4
[1]> (load "~/quicklisp/setup.lisp")
;; Loading file /home/satoshiokita/quicklisp/setup.lisp ...
;; Loading file /home/satoshiokita/quicklisp/cache/asdf-fasls/0hq63s/asdf.fas ...
;; Loaded file /home/satoshiokita/quicklisp/cache/asdf-fasls/0hq63s/asdf.fas

あとは、(ql:add-to-init-file)を実行します。

1
2
3
4
5
6
7
8
9
10
11
12
[2]> (ql:add-to-init-file)
I will append the following lines to #P"/home/satoshiokita/.clisprc.lisp":

;;; The following lines added by ql:add-to-init-file:
#-quicklisp
(let ((quicklisp-init (merge-pathnames "quicklisp/setup.lisp" (user-homedir-pathname))))
(when (probe-file quicklisp-init)
(load quicklisp-init)))

Press Enter to continue.

#P"/home/satoshiokita/.clisprc.lisp"

これで、.clisprc.lispが作られました。

正規表現ライブラリーcl-ppcreを使ってみましょう

以下のように(ql:quickload ライブラリー名)を入力すればダウンロードして、ロードしてくれます。(ユーザーのホームディレクトリーにquicklispディレクトリーが作成されそこで管理されます。)

1
2
3
4
5
6
7
[3]> (ql:quickload :cl-ppcre)
To load "cl-ppcre":
Load 1 ASDF system:
cl-ppcre
; Loading "cl-ppcre"
[package cl-ppcre].........
(:CL-PPCRE)

ロードできたらppcre:scanで、”abc”文字列中にbが存在するかスキャンします。結果の先頭行に1と書かれているように正常に動作しています。

1
2
3
4
5
6
[4]> (ppcre:scan "b" "abc")
1 ;
2 ;
#() ;
#()
[5]>

emacs+SLIMEのLispプログラムの変更

~/.emacs.d/init.elで、(setq inferior-lisp-program "sbcl")をclispに指定します。
;; コンパイラー指定
;;(setq inferior-lisp-program “sbcl”)
(setq inferior-lisp-program “clisp”)

SLIME上で動作確認

とくに問題なく使えました。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
CL-USER> (ql:quickload :cl-ppcre)
To load "cl-ppcre":
Load 1 ASDF system:
cl-ppcre
; Loading "cl-ppcre"
[package cl-ppcre]................................
...............................
(:CL-PPCRE)
CL-USER> (ppcre:scan "b" "abc")
1
2
#()
#()
CL-USER>