Atom Shell をビルドする

GitHub が最近オープンソースで公開した Atom というエディタが話題になっているが、それに使われているフレームワークが Atom Shell というものらしい。GitHub の README.md によると JavaScript や HTML や CSS といった Web テクノロジでクロスプラットフォームなデスクトップアプリケーションが作れるフレームワークなのだそうだ。以前から Microsoft Windows でも HTA (HTML Application) という HTML + JScript/VBScript でデスクトップアプリケーションが作れる技術があったが、あのノリなのかもしれない。もっとも HTA は Internet Explorer 限定だったけど。

試しにソースコードを clone してビルドしてみる。とはいってもドキュメントの通りに進めるだけだった。まずはソースツリーを clone する。

1
2
$ git clone https://github.com/atom/atom-shell.git
$ cd atom-shell

ビルドに必要なものはすべて bootstrap.py を実行することでそろえてくれるようだ。

1
$ ./script/bootstrap.py

あとは build.py を実行するだけ。

1
$ ./script/build.py

最後に test.py を実行して完了!

1
$ cd ./script/test.py

out/Release/Atom.app/Contents/MacOS/Atom に実行ファイルが生成される。

Python でファイルを読むとき

Python でファイルを読むときはいつも

1
2
3
4
5
6
f = open("file.txt")
line = f.readline()
while line:
print line
line = f.readline()
f.close()

のように書いていたけど、こんな書き方しなくても、

1
2
3
4
f = open("file.txt")
for line in f:
print line
f.close()

これでよかったんだ…。効率は良くないかもしれないけど、もっと短く書ける。

1
2
for line in open("file.txt"):
print line

でも Python 2.6 からは with 構文使うのがいいらしい。

1
2
3
with open("file.txt") as f:
for line in f:
print line

これなら with を抜けた後に自動的に f.close() されるようだ。まさに Lisp の with-open-file マクロだな。

フィボナッチ数列

なんとなくフィボナッチ数列を計算したくなった。素朴な実装だとどのくらい遅いのかというと。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>
int fib(int n)
{
if (n == 0) {
return 0;
}
else if (n == 1) {
return 1;
}
else {
return fib(n-1) + fib(n-2);
}
}
int main(int argc, char *argv[])
{
int n = strtol(argv[1], NULL, 10);
printf("%d\n", fib(n));
return 0;
}
実行結果
1
2
3
$ time ./a.out 45
1134903170
./a.out 45 14.84s user 0.02s system 99% cpu 14.916 total

フィボナッチ数列は fib(n) と fib(n-1) の和からなっており、1 だけ異なる引数で二手に分かれて再帰していくので、何度も同じ計算を繰り返すはめになる。したがって、与えられた n に対して計算した結果をキャッシュ(メモ)しておいて、再び同じ n が与えられたらキャッシュから返すようにすれば高速化が望める。これをメモ化という。メモするための記憶領域は別途必要になるが、実行速度の向上はそのオーバーヘッドを遥かに上回る。確か最初は SICP の本か何かで読んだ気がするがだいぶ忘れてて、記憶を頼りに書こうとしたが結局ググってしまったことは内緒。

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
#include <stdio.h>
#include <stdlib.h>
int memo[100];
int fib(int n)
{
if (memo[n]) {
return memo[n];
}
else if (n == 0) {
return 0;
}
else if (n == 1) {
return (memo[n] = 1);
}
else {
return (memo[n] = fib(n-1) + fib(n-2));
}
}
int main(int argc, char *argv[])
{
int n = strtol(argv[1], NULL, 10);
printf("%d\n", fib(n));
return 0;
}

お遊びなのでコードは適当に書いてます。実行速度は先ほどとは歴然の差。

実行結果
1
2
3
$ time ./a.out 45
1134903170
./a.out 45 0.00s user 0.00s system 38% cpu 0.006 total

Lisp の map 関数

Lisp にはリスト操作の map* 関数が 6 種類あるが違いが微妙なのでまとめてみた。まずは基本形の mapcar/maplist を押さえておけばいい感じ。

mapcar/maplist

mapcar は引数にとったリストを構成する各コンスセルの car 部に対して関数を適用し、その結果をリストとして返す。

1
2
3
4
5
(mapcar #'(lambda (x) (* x 2)) '(1 2 3))
;; => (2 4 6)
(mapcar #'+ '(1 2 3) '(4 5 6))
;; => (5 7 9)

maplist は引数にとったリストを構成する各コンスセルの cdr 部に対して関数を適用し、その結果をリストとして返す。

1
2
3
4
5
(maplist #'list '(1 2 3))
;; => (((1 2 3)) ((2 3)) ((3)))
(maplist #'list '(1 2 3) '(4 5 6))
;; => (((1 2 3) (4 5 6)) ((2 3) (5 6)) ((3) (6)))

mapcan/mapcon

mapcan は mapcar 同様に、引数にとったリストを構成する各コンスセルの car 部に対して関数を適用するが、その結果がリストであることを期待して nconc したものを返す。

1
2
3
4
5
6
7
(mapcan #'list '(1 2 3))
;; => (nconc '(1) '(2) '(3))
;; => (1 2 3)
(mapcan #'list '(1 2 3) '(4 5 6))
;; => (nconc '(1 4) '(2 5) '(3 6))
;; => (1 4 2 5 3 6)

mapcon は maplist 同様に、引数にとったリストを構成する各コンスセルの cdr 部に対して関数を適用するが、その結果がリストであることを期待して nconc したものを返す。

1
2
3
4
5
6
7
(mapcon #'list '(1 2 3))
;; => (nconc '(1 2 3) '(2 3) '(3))
;; => ((1 2 3) (2 3) (3))
(mapcon #'list '(1 2 3) '(4 5 6))
;; => (nconc '((1 2 3) (4 5 6)) '((2 3) (5 6)) '((3) (6)))
;; => ((1 2 3) (4 5 6) (2 3) (5 6) (3) (6))

mapc/mapl

mapc/mapl のリスト処理は mapcar/maplist と同様であるが、戻り値は一番目に与えたリストを返すという点で異なる。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(mapc #'(lambda (x) (format t "This is ~a~%" x)) '(1 2 3))
;; This is 1
;; This is 2
;; This is 3
;; => (1 2 3)
(mapc #'(lambda (x y) (format t "~a + ~a = ~a ~%" x y (+ x y))) '(1 2 3) '(4 5 6))
;; 1 + 4 = 5
;; 2 + 5 = 7
;; 3 + 6 = 9
;; => (1 2 3)
(mapl #'(lambda (x) (format t "This is ~a~%" x)) '(1 2 3))
;; This is (1 2 3)
;; This is (2 3)
;; This is (3)
;; => (1 2 3)
(mapl #'(lambda (x y) (format t "append ~a and ~a => ~a~%" x y (append x y))) '(1 2 3) '(4 5 6))
;; append (1 2 3) and (4 5 6) => (1 2 3 4 5 6)
;; append (2 3) and (5 6) => (2 3 5 6)
;; append (3) and (6) => (3 6)
;; => (1 2 3)

map/mapinto (おまけ)

map は一般的なシーケンス型に適用できる mapcar の汎用版。

1
2
3
4
(map 'vector #'+ #(1 2 3) #(4 5 6))
;; => #(5 7 9)
(map 'list #'+ '(1 2 3) '(4 5 6))
;; => (5 7 9)

mapinto は mapcar の結果を第一引数に指定した変数に割り当てる。

1
2
3
4
(map-into a #'+ '(1 2 3) '(4 5 6))
;; => (5 7 9)
a
;; => (5 7 9)

リーダブルコード

だいぶいまさら間が否めないが巷で噂のリーダブルコードを読んだ。いかにしてわかりやすいコードを書くかという点に関して豊富な具体例とともにわかりやすく解説している良書だった。まあコードコンプリートにも書かれている内容だが。ちゃんとコメント書かないと…。

Octopress の記事の日付を更新するスクリプト

Octopress で rake new_post して新しい記事を作成すると、作成日がファイル名になり、ファイル中の date: にも作成した時点の日時が記録される。この日付は作成日ではなくどちらかというと deploy する日にしたいので、指定したファイル名とファイル中の date: を最新に更新するスクリプトを書いた。(SBCL 用)

実行方法は以下の通り。

1
$ sbcl --script update-md.lisp 2014-05-14-hoge.markdown

安全な FIFO の作り方

固定長配列を使って安全な FIFO を実現するときにちょっと便利な方法を思いついたのでメモしておく。次のようなシンプルな FIFO があるとする。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Fifo:
def __init__(self, size):
self.fifo = [0]*size
self.wp = 0
self.rp = 0
def push(self, obj):
self.fifo[self.wp] = obj
self.wp += 1
if self.wp == len(self.fifo):
self.wp = 0
def pop(self):
r = self.fifo[self.rp]
self.rp += 1
if self.rp == len(self.fifo):
self.rp = 0
return r

push() で FIFO にデータを詰めて、pop() で先に push() したデータから取り出せる。

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
print "-------- Test1 --------"
fifo = Fifo(8)
for i in range(4):
fifo.push(i)
for i in range(4):
print fifo.pop(),
print
for i in range(8):
fifo.push(i)
for i in range(8):
print fifo.pop(),
print
print "-------- Test2 --------"
fifo = Fifo(8)
for i in range(9): # ERROR! (Overwrite)
fifo.push(i)
for i in range(8):
print fifo.pop(),
print
print "-------- Test3 --------"
fifo = Fifo(8)
for i in range(8):
fifo.push(i)
for i in range(9): # ERROR! (Overread)
print fifo.pop(),
print
実行結果
1
2
3
4
5
6
7
-------- Test1 --------
0 1 2 3
0 1 2 3 4 5 6 7
-------- Test2 --------
8 1 2 3 4 5 6 7
-------- Test3 --------
0 1 2 3 4 5 6 7 0

Test1 のように FIFO のバッファ容量をオーバーしない限り push() した通りに pop() されている。しかし、Test2 の場合はバッファ容量を超えて push() しているので、先に保存したデータを上書きしてしまっている。Test3 は逆に pop() が多すぎる場合で、データを保存していない場所からデータを読み取ってしまっている。

そこで、データの上書きや読み過ぎを防ぐ SafeFifo というクラスを作りたい。単純にリードポインタとライトポインタを比較するコードを追加すればよいのだが、既存クラスに手を加えたくない場合や、テスト時のみチェック機構が備わっている Safe 版を使いたい場合がある。そこで次のような filled という配列を用意しておき、push() して書き込まれた場所に True を記録し、pop() して読み出された場所は False を記録しておく。上書き/読み過ぎを検出しているので、出力結果がおかしくなることはない。(ただし、当然ながらバッファ容量を超えて push() した分は破棄されてしまう。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class SafeFifo(Fifo):
def __init__(self, size):
Fifo.__init__(self, size)
self.filled = [False]*size
def safe_push(self, obj):
if self.filled[self.wp] == False:
self.filled[self.wp] = True
self.push(obj)
else:
raise Exception('Overwrite at %d' % (self.wp))
def safe_pop(self):
if self.filled[self.rp] == True:
self.filled[self.rp] = False
return self.pop()
else:
raise Exception('Overread at %d' % (self.rp))

Fifo を SafeFifo に置き換えて例外処理を追加した使用例。

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
print "-------- Test1 --------"
fifo = SafeFifo(8)
for i in range(4):
fifo.safe_push(i)
for i in range(4):
print fifo.safe_pop(),
print
for i in range(8):
fifo.safe_push(i)
for i in range(8):
print fifo.safe_pop(),
print
print "-------- Test2 --------"
fifo = SafeFifo(8)
try:
for i in range(9): # ERROR! (Overwrite)
fifo.safe_push(i)
except Exception, e:
print e
for i in range(8):
print fifo.safe_pop(),
print
print "-------- Test3 --------"
fifo = SafeFifo(8)
for i in range(8):
fifo.safe_push(i)
try:
for i in range(9): # ERROR! (Overread)
print fifo.safe_pop(),
except Exception, e:
print e
print

実行結果は以下の通り。

実行結果
1
2
3
4
5
6
7
8
-------- Test1 --------
0 1 2 3
0 1 2 3 4 5 6 7
-------- Test2 --------
Overwrite at 0
0 1 2 3 4 5 6 7
-------- Test3 --------
0 1 2 3 4 5 6 7 Overread at 0

まあ普通はこんなことはやらなくてポインタを比較するだけでいいんだけど。

グローバル変数をクロージャで包む

暇つぶしにリーダブルコードを読んでいたら、JavaScript のコードでグローバル変数で名前空間を汚染しないようにするために、クロージャを利用する例が掲載されていた。クロージャの使い方としてこれは知らなかったのでなるほどと感心してしまった。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var closure = (function () {
var is_called = false;
return function (name) {
if (!is_called) {
console.log("first call with " + name);
is_called = true;
}
else {
console.log("finished");
}
};
}());
closure("foo")
closure("foo")
closure("foo")

ある関数が複数回呼ばれたときに最初の一回のみ関数を実行したい場合、クロージャを使わないなら is_called というグローバル変数で一回目のコールかどうかを管理する。この例はそのグローバル変数をクロージャで包んで外部の名前空間に流出しないようにしている。

実行結果
1
2
3
first call with foo
finished
finished

Common Lisp で書いてみるとこんな感じ。

1
2
3
4
5
6
7
8
9
10
11
12
13
(defparameter *closure* nil)
(setf *closure* (let ((is-called nil))
#'(lambda (name)
(cond ((null is-called)
(format t "first called with ~a~%" name)
(setf is-called t))
(t
(format t "finished~%"))))))
(funcall *closure* "foo")
(funcall *closure* "foo")
(funcall *closure* "foo")

スクリプト実行を効率化するための SBCL コアイメージの作成方法

Common Lisp をスクリプト実行していて困るのが Quicklisp を使ったライブラリのロード方法。SLIME などの REPL 上で実行しているなら一度 ql:quickload してあげれば問題ないが、ターミナルからスクリプト実行する場合は毎回 ql:quickload が走るため時間がかかり効率が良くない。

1
2
3
4
5
(load "~/quicklisp/setup.lisp")
(ql:quickload "getopt")
(use-package :getopt)
;; Codes using getopt package continue below

そこで、あらかじめ必要なライブラリをロードした状態の SBCL のコアイメージを生成して、その上でスクリプトを実行する方法を調べてみた。SBCL には sb-ext:save-lisp-and-die という関数でコアイメージを生成することができるので、以下のようなコアイメージ生成用のスクリプトを実行して sbcl-script という実行可能形式のファイルを生成する。

1
2
3
(load "~/quicklisp/setup.lisp")
(ql:quickload "getopt")
(sb-ext:save-lisp-and-die "sbcl-script" :executable t)
1
$ sbcl --script sbcl-script.lisp

sbcl-script を生成した結果、ファイルサイズは 55509040 byte だった。結構でかい…。

sbcl-script で実行するスクリプトはもはや ql:quickload する必要はないので、ライブラリを使用したコードを書いて気軽にスクリプト実行することができる。

1
2
(use-package :getopt)
;; Codes using getopt package continue below

Common Lisp で getopt ライブラリを使う

Common Lisp に getopt のようなライブラリがあるか調べてみたら、quicklisp に登録されていたので使い方を調べてみた。

getopt-test.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
(use-package :getopt)
(multiple-value-bind (out-args out-opts errors)
(getopt (cdr sb-ext:*posix-argv*) '(("h" :NONE) ("f" :REQUIRED) ("b" :OPTIONAL "bar")))
;; Print each lists returned by getopt
(print out-args)
(print out-opts)
(print errors)
(fresh-line)
;; Handle illegal options
(when errors
(format t "Illegal options: ~{~a ~}~%" errors)
(quit))
;; Print arguments and options
(format t "Arguments are ")
(format t "~{~a ~}~%" out-args)
(dolist (opt out-opts)
(cond ((equal (car opt) "h")
(format t "option h~%"))
((equal (car opt) "f")
(format t "option f is ~a~%" (cdr opt)))
((equal (car opt) "b")
(format t "option b is ~a~%" (cdr opt))))))

getopt には二つの引数を渡していて、一つ目はコマンドライン引数 (文字列のリスト)、二つ目はオプションリストを指定する。オプションリストは以下の 3 要素からなるリストのリストである。

  • NAME: オプションにする文字列 (long name にも対応)
  • HAS-ARG: :NONE (引数なし), :REQUIRED (引数あり), :OPTION (引数は任意) のいずれか
  • VAL: :OPTION 指定のオプションに何も指定しなかった場合のデフォルト値

getopt の戻り値は、オプション以外の引数 (out-args)、オプションと引数のペアのリスト (out-opts)、エラー (errors)という多値で返ってくる。errors が Non-nil であればパースが正常に終了しているので、上記サンプルのように out-opts をループしながら cond で場合分けしてもいいし、連想リスト形式なので assoc してもいいと思う。

1
sbcl --script getopt-test.lisp -f foo -b -h abc xyz
実行結果
1
2
3
4
5
6
7
("abc" "xyz")
(("f" . "foo") ("b" . "bar") ("h"))
NIL
Arguments are abc xyz
option f is foo
option b is bar
option h

なお、Common Lisp の ANSI 標準ではコマンドライン引数の扱いに関して規定していないので、取得方法は処理系依存になるようだ。特に、SBCL は sb-ext:*posix-argv*, CLISP は ext:*args* で取得できるので、本当は処理系の差を吸収するために *features* から実行時の処理系を判定したほうがいいかも。

1
2
3
(defun args ()
#+sbcl (cdr sb-ext:*posix-argv*)
#+clisp ext:*args*)