Common Lispのライブラリ事情

ANSI Common Lispでは、ライブラリのフォーマットについてあまりちゃんとした仕様が存在しません。

当然、ライブラリを扱えないのは不便極まりないことですから、その点をカバーするためのシステムが存在します。

• REQUIRE, PROVIDE 現在非推奨の、ANSI Common Lispに存在する唯一のライブラリ管理システムです。

• ASDF デファクトスタンダードのライブラリ管理システムです。

• QuickLisp ASDFを使用したライブラリのコレクションです。 Rubyにおけるgem、HaskellにおけるHackageのような立ち位置です。

• Roswell Common Lispの開発環境を管理するためのツールです。 ASDFの機能を拡張し、GithubからのライブラリDLなど、モダンな機能が追加されています。

REQUIRE, PROVIDE

ANSI Common Lispに存在するライブラリ管理システムです。 ‘(require :hoge)'でファイルを読み込み、そのファイルで’(provide :hoge)‘されていれば、2回目以降の’(require :hoge)‘では何も行われません。

これは無駄なロードを防ぐための仕組みです。

しかし、REQUIREがどこのファイルを読みにいくかは処理系の実装に依存しています。 処理系ポータブルなコードを書くには非常に不便です。

そこで、Common Lispでは主に"ASDF"というシステムをつかってライブラリを管理します。

ASDF

ASDFは、Common Lispのソースコードをsystemとしてまとめ、ビルドし、ロードするためのツールです。

例えば、Makefile的なものを、(systemname).asdとして書いてASDFのロードパス下においておくと、

(in-package :cl-user)
(asdf:defsystem :foobar ;; 定義するsystem名
    :description "A sample Lisp system."
    :version "0.0.1"
    :author "Joe <joe@example.com>"
    :licence "Public Domain"
    :depends-on (:alexandria :serapeum) ;; 依存するパッケージ
    :components ((:file "foobar" :depends-on ("utils")) ;; systemに含まれる.lispファイルを、(systemname).asdからみた相対パスで
                 (:file "utils")))

次のようにロードすることができます。

* (require 'asdf)
* (require 'foobar)

require, ASDF, quicklispを正しく使う | κeenのHappy Hacκing Blogや 独学Common Lisp に詳しい内容があるので、そちらも参照することをおすすめします。

packageとsystemの違い

Packages, systems, modules, libraries - WTF?

TODO: ちゃんと書く

Quicklisp

Quicklispは、Rubyにおけるgem、HaskellにおけるHackageのようなシステムです。 次のようにsystemをロードできます。

* (ql:quickload :alexandria)
* (ql:quickload '(cl-annot trivia))

また、(ql:system-apropos substring)で検索、(ql:update-all-dists)でアップデート、(ql:update-client)でQuicklisp本体のアップデートができます。

QuickdocsにはQuicklispでロードできるすべてのsystemのドキュメント、プロジェクトページへのリンクなどが掲載されています。

TODO: Quicklispへ自分のsystemを追加する方法

Roswell

Roswellには、コマンドラインでQuicklispからライブラリやソフトウェアをダウンロードする機能があります。

$ ros install qlot        # Quicklispからダウンロードします。
$ ros install fukamachi/qlot # Githubからダウンロードします。

TODO: ASDFのdepends-onとかにもgithubのリポジトリを指定できる様になったはずだけど試してないので試して書く

参考文献

• require, ASDF, quicklispを正しく使う | κeenのHappy Hacκing Blog
• ASDF - Another System Definition Facility
• Quicklisp beta
• GitHub - roswell/roswell: intend to be a lisp installer and launcher for major environment that just work.

Clozure CLをちょっと早くする

Clozure CLのLispの部分をコンパイルしてうんたらかんたらして起動とかを早くする。

? (ccl:compile-ccl)

フィボナッチ数の20番目を計算してテスト

#!/bin/sh
#|-*- mode:lisp -*-|#
#| <Put a one-line description here>
exec ros -Q -- $0 "$@"
|#
(progn ;;init forms
  (ros:ensure-asdf)
  ;;#+quicklisp (ql:quickload '() :silent t)
  )

(defpackage :ros.script.fib.3691033179
  (:use :cl))
(in-package :ros.script.fib.3691033179)

(defun fib (n)
  (case n
    ((0 1) 1)
    (t (+ (fib (- n 1)) (fib (- n 2))))))

(defun main (&rest argv)
  (declare (ignorable argv))
  (princ (fib 20))
  (terpri))
;;; vim: set ft=lisp lisp:

起動時間も見たいのでRoswell scriptで

$ ros build fib.ros
$ #ビルド前
$ time ./fib.ros
10946
./fib.ros  1.51s user 0.14s system 98% cpu 1.671 total
$ #ビルド後
$ time./fib.ros
10946
./fib.ros  0.37s user 0.09s system 96% cpu 0.482 total

Roswell scriptでshebangツライときの覚え書き

ANSI Common Lispではshebangの存在は考慮されない。 しかし、Roswell scriptのデバッグをSlimeでしていると、shebangでリードエラーが起きてツラくなる。 その回避方法。

Roswellは起動時に、$HOME/.roswell/init.lispを実行する。 また、ros:ignore-shebang関数で、リードマクロにshebang行の読み飛ばしが追加される。

$HOME/.roswell/init.lisp

(ros:ignore-shebang)

このように設定しておけば、shebangの行を読み飛ばすので幸せになれる。

RoswellでCommon Lisp環境をセットアップする 2016秋

（2017-3-11更新）RoswellでCommon Lisp環境をセットアップする - ギークもどきの日記帳

Roswellとは (ざっくりと)

Common Lispの処理系やQuicklispのインストール、処理系ごとのオプションの違いの吸収などを行うすごい便利なツール。 Common Lisperなら使って損はない。

インストール

参照Wiki

Home · roswell/roswell Wiki · GitHub

Arch Linux

AURに登録されているので、yaourtでインストールできる。

$ yaourt -S roswell

Homebrew

$ brew install roswell

Windows

Home · roswell/roswell Wiki · GitHub

使っているOSのbitに合わせて、32bitならRoswell-i686.zip、64bitならRoswell-x86_64.zipをダウンロードし解凍、PATHを通す。

ソースからビルド

INSTALL.md参照。

Replの起動

ros runコマンドでREPLが起動する。

$ ros run
* (+ 1 2)

3
* (quit)
$ 

---

また、roswellはデフォルトでsbcl-1.2.11のバイナリ版を使う。 他の処理系や最新版のsbclを使いたいときは、以下の手順でインストールする。

処理系のインストール (例: Clozure CL)

$ ros install ccl-bin

処理系の切り替え (例: Clozure CL)

$ ros use ccl-bin
$ ros run
Welcome to Clozure Common Lisp Version 1.11-r16635  (DarwinX8664)!

CCL is developed and maintained by Clozure Associates. For more information
about CCL visit http://ccl.clozure.com.  To enquire about Clozure's Common Lisp
consulting services e-mail info@clozure.com or visit http://www.clozure.com.

? 

インストールできる処理系のリストは、ros list versionsで確認できる。

$ ros list version
candidates for ros list versions [impl] are:

abcl-bin
allegro
ccl-bin
clasp
clisp
cmu-bin
ecl
quicklisp
sbcl-bin
sbcl

インストールできるバージョンは、ros list versions [処理系の名前]で確認できる。

$ ros list versions sbcl
Installable versions for sbcl:
Checking version to install....
1.3.15
1.3.14
1.3.13
1.3.12
1.3.11
1.3.10
1.3.9
1.3.8
1.3.7
1.3.6

SLIME

みんなだいすきSLIMEも簡単に使える。 ros emacsで、.emacs.dの設定なしにSLIMEを使えるemacsが起動する。すごい便利。

普通のemacsで使うには以下の手順を踏む。

$ ros install slime

続いて~/.emacs.d/init.elに次の行を追記する。

(load (expand-file-name "~/.roswell/helper.el"))

より詳しい設定方法は、

Home · roswell/roswell Wiki · GitHub

を参照のこと。

Roswell Script

Common LispではRubyやPythonと異なり、プログラムをロードしたREPLを用いることが多い。 スクリプト言語のようにバッチ処理を実行するには、処理系ごとに異なった方法を取らねばならず少し不便を感じる。

その点を解決するため、RoswellにはRoswell Scriptという仕組みがある。 ros init <ファイル名>で、Roswellがインストールされている環境上で、単体で実行できるCommon Lispが生成される。

$ ros init fact
Successfully generated: fact.ros

$ cat fact.ros
#!/bin/sh
#|-*- mode:lisp -*-|#
#| <Put a one-line description here>
exec ros -Q -- $0 "$@"
|#
(progn ;;init forms
  #+quicklisp (ql:quickload '() :silent t))

(defpackage :ros.script.fact.ros.3685511769
  (:use :cl))
(in-package :ros.script.fact.ros.3685511769)

(defun main (&rest argv)
  (declare (ignorable argv)))
;;; vim: set ft=lisp lisp:

このファイルはEmacsとVimの両方でCommon Lispのソースコードとして認識される。

main関数がエントリーポイントとなる。main関数の引数には、適切にパースされたコマンドライン引数が渡される。 例えば、引数の階乗を返すコマンドは下のようになる。

#!/bin/sh
#|-*- mode:lisp -*-|#
#| Calculating the factorial of given number
exec ros -Q -- $0 "$@"
|#

;;; 今回は使用しないのでコメントアウト
;; (progn ;;init forms
;;   #+quicklisp (ql:quickload '() :silent t))

(defpackage :ros.script.fact.ros.3685511769
  (:use :cl))
(in-package :ros.script.fact.ros.3685511769)

(defun fact (n)
  (if (zerop n)
        1
              (* n (fact (1- n)))))

(defun main (n &rest argv)
  (declare (ignorable argv))
  (format t "~&Factorial ~D = ~D~%" n (fact (parse-integer n)))
  0 ; 実行成功
)

;;; vim: set ft=lisp lisp:

実行例

$ ./fact.ros 3
Factorial 3 = 6

$ ./fact.ros 10
Factorial 10 = 3628800

さらに、Roswellがインストールされていない環境でも（おそらく）動作するexecutableも作れる。 ただし、処理系やライブラリのイメージを含むため、ファイルサイズが50MiBぐらい大きくなる。レッツブルジョア!!

$ time ./fact.ros 10
Factorial 10 = 3628800
./fact.ros 10  0.43s user 0.09s system 98% cpu 0.530 total

$ ros build fact.ros

$ time ./fact 10
Factorial 10 = 3628800
./fact 10  0.00s user 0.01s system 89% cpu 0.018 total

$ du -ah
 54M     ./fact
4.0K     ./fact.ros

割りと速くなった。気がする。もっと計算量の多い処理だと大きく変わるかも。

Ros scriptでライフゲーム

Ros scriptでライフゲーム書いた。

lifegame.rosに実行可能権限を与えたあと、./lifegame.rosで起動する。

Enterキーを押すと一世代進む。 正整数を入力すると、その分がアニメーション付きで進む。

./lifegame.ros *width* *height* *wait-time*

iotaからunfoldをつくる Common Lisp編

まず、iotaを定義する。 簡潔にするため、オプション引数は使わない。

(defun iota (limit seed step)
  (if (> seed limit)
    nil
    (cons seed (iota limit (+ seed step) step))))

(> seed limit)を一般化して、終了条件を指定できるよう変更する。

(defun func1 (pred seed step)
  (if (funcall pred seed)
    nil
    (cons seed (func1 pred (+ seed step) step))))

(+ seed step)を一般化して、seedの変化を指定できるよう変更する。

(defun func2 (pred next-gen seed)
  (if (funcall pred seed)
    nil
    (cons seed (func2 pred next-gen (funcall next-gen seed)))))

最後に、mapcar関数と合成する。

(defun func3 (pred fn next-gen seed)
  (if (funcall pred seed)
    nil
    (cons (funcall fn seed)
          (func3 pred fn next-gen (funcall next-gen seed)))))

もっと単純に、こうしてもいい。

(defun func3 (pred fn next-gen seed)
  (mapcar fn (func2 pred next-gen seed)))

これでunfold関数の完成。

(defun unfold (p f g n)
  (if (funcall p n)
    nil
    (cons (funcall f n)
          (unfold p f g (funcall g n)))))

参考URL

• Common Lisp 入門 : 番外編
• scheme - "unfold" for common lisp? - Stack Overflow

Scheme 継続

もうひとつのScheme入門 16. 継続を写経した。

「継続」は、計算において必ず存在する。 しかし、明示的に扱われることが少ない。

例えば、

(* 3 (+ 1 2))

のような計算があるとき、(+ 1 2)を評価した後の残りの計算は、(* 3 _)である。 この部分を継続と呼ぶ。

継続渡しスタイル

継続は、第一級関数をもつ言語であれば、CPS(継続渡しスタイル)によってあつかうことができる。

これは、関数が値を返す部分に、計算結果をどんな関数に渡すのかを引数で指定する方法。

(define (id x)
  x)

(define (k+ a b k)
  (k (+ a b)))

(define (k* a b k)
  (k (* a b)))

この関数群を使って、先ほど示したコードを書くとこうなる。

(k+ 1 2 (lambda (x) (k* 3 x id)))

関数適用の順番が入れ替わっている。

再帰関数のCPS化

(define (fact n)
  (if (= n 1)
      1
      (* n (fact (- n 1)))))

(define (kfact n k)
  (if (= n 1)
      (k 1)
      (kfact (- n 1) (lambda (x) (k (* n x))))))

一つ目が通常の階乗。二つ目がCPS階乗。 CPS版は末尾再帰になっている。 このように、再帰関数をCPS化することで、末尾再帰に変換できる。 Schemeは末尾再帰をループに最適化するので、とても嬉しい。

call/cc

call/ccを使うと、継続によるジャンプができる。

> (* 3 (call/cc (lambda (k) (+ 1 2))))
9 ;継続が呼ばれていないので、普通の式と同じ
> (* 3 (call/cc (lambda (k) (+ 1 (k 2)))))
6 ;継続kが呼ばれ、(* 3 2)を計算し、トップレベルに6が返る

(define cc)
(* 3 (call/cc (lambda (k)
                 (set! cc k)
                 (+ 1 2))))

> (+ 100 (cc 3))
9
> (+ 100 (cc 100))
300

継続を呼ぶと、その後の式を無視してトップレベルに戻る。

具体的な使用方法は後でまとめる。