2018年振り返り

2018年振り返り

 今年はいろいろあったので、振り返りしてみようという気になった。触発されたというのもある。

働いた

 2017年末にはなんか落ち込みが発生して自信をかなり損なっていた時期があったけど、2018年1月からは働きはじめた。対話AIをやっている会社で、それまでSIer (Java)やWeb屋さん(Python)としてやってきたぼくとしては新たなチャレンジだった。とはいえWebまわりをやっているけれど、いろいろなことを学んだし、(Lisperなのに)(遅いけど)対話AI、というか人工知能に興味を持つことができた。神戸大学LISPマシンを見にいったときのことも大きなきっかけである(第7回関西Lispユーザ会に行ってきた)。

読書

 あんま読んでない…。スループットは悪く、年に24冊だった。内訳としては、小説多め。今年は『エコープラクシア』『最後にして最初のアイドル』『リスの生態学』『貨幣の新世界史』『エル・アレフ』『死刑 その哲学的考察』『ペンギンの島』『トランスヒューマンガンマ線バースト童話集』、などなど。SFは収穫多かった。就職祝い(セルフ)に買ったイーガンの直交三部作は本棚をしっかりと支えています。読みたい。あとは、後述するけど音声信号処理関連の読んだけど、まだわからん…。あと、ついに『LET OVER LAMBDA』を読んだよ!! マクロって書いていいんだね!!

太った

 なぜだかわからないけど太った。きっと運動を控えめに、食事を盛大に行ったためだと思われる。怖いので体重を計測していない。帰省しているので、戻ったらまずは計測して、そして、運動をしてやせたい。

プログラミング

 いくつかトピックがあるので分けて書く。

シンセサイザーづくり

 つくってみたいもののひとつだったので、えいやっとつくりはじめてみた。とりあえずノリで実装してみてたけど、平行して書籍を読むこともした。『サウンドプログラミング入門――音響合成の基本とC言語による実装』で基本を押さえ、『サウンドエフェクトのプログラミング―Cによる音の加工と音源合成』でエフェクトのつくりかたを…わからなかったけど…。音を鳴らすのは簡単(でもない)けど、シーケンサを生やすためのイベントスケジューラを書けなくて、実力の不足を実感した。シーケンサ、生えろ。

Nim -> Rust

 興味があったのでNimを去年からいじっていた。初めてのLispをつくってみたり、上のシンセサイザーつくりに利用してみたりした。ただ、なぜか処理系の不具合を踏み抜いたようで、シンセづくりが完全にストップしてしまったのであきらめた。そのままRustに入門して、絶賛勉強中。ちなみにシンセはCommon Lispでもつくりはじめてみた。シーケンサがやっぱり鬼門。

言語を処理でき…そう…?

 去年末はNimでLispをつくっていたけど、仕組みがわからないので引き続き勉強していた。パタヘネ読んだし、仮想機械のサーベイをしたり、実際にCPUエミュレータVMを実装してみたりした。そしてForthとの出会い。そのあたりはこちら『プログラミング言語Forthに魅せられて。』にしたためておいた。定数を扱える、規格の動作をすこしずつ再現できてきているので、もしかしたらいわゆる「ちゃんとした言語」というやつになるかもしれない。

来年は

 いろいろ結実して、生えてきてほしいなあ。

セルオートマトン暗号(未完)

遅刻してますが、この記事はセルオートマトンアドベントカレンダーの23日目の記事です。

あらまし

 離散的な力学系であるところのセルオートマトンは、カオス的なふるまいをすることで知られています。カオス的であるなら、そのふるまいを暗号学的なアレとかソレとかに利用できるのでは…、とはもう研究があるようですがここでは割愛。いっぽうで、セルオートマトンの中には可逆性をもつものがあります(ここらへんも研究がありますが割愛)。

 あとは…わかるね?

 ということでとりあえずElementary Cellular Automataを用いてガッとメッセージの暗号化・複合化を実装しようとしたけど3時間ではだめでした、という残念な記事です。ざんねん。

ソースコード

文字をつらつら書くほど内容はないのでさっさとソースコードを示します。ひさしぶりにビット演算をキメた気がする。以下のことはできています:

  • 局所遷移関数をルール番号から生成(コンパイル時に)
  • 周期的境界条件(キアイで)
  • なんとなく様相を指定回数ぶん遷移
  • ファイルをビットベクタにしてECAの様相に変換しブンまわす

gist.github.com

使用感

 なんとなくこんな感じになります。

CL-USER> (let ((vec (vector 0 0 0 1 0 0 0 1 0)))
           (run 10 vec (make-array (length vec))
                (make-local-transition-fn-from-rule 150)))
#*000100010
#*001110111
#*110100010
#*000110110
#*001000001
#*111100011
#*111010101
#*110010100
#*001110111
#*110100010
#(0 0 0 1 1 0 1 1 0)

 なんとなく大域遷移はできていそう。Roswellスクリプトにしておいたので、引数にファイル名を与えるとファイルの内容で遷移してくれます。しかしビットベクタをバイトベクタとして書き出してしまっているので出力はおかしいですがもうつかれました。

まとめ

 このセルオートマトンという分野、人工生命というだけではなく暗号学の方面の研究もあり、さらに情報の圧縮や、果ては様相の遷移を群と見なして解析する純粋数学的な分野もあり、とてもたのしそうです。やりたい。

参考文献

Common Lisp (Roswell)とDockerで実行可能ファイルをビルド

 この記事はLispアドベントカレンダーの7日目の記事です。

ざっくり

 Common Lispの処理系マネージャ・スクリプティング環境であるRoswellとライブラリバージョン固定化ツールQlotを用いて、

  1. Common Lispのプロジェクト(システム)の実行可能バイナリを作成し、
  2. Common Lisp環境が入っていない人でも実行できるようDockerコンテナ化し、
    • 推し進め、コードに変更があったときでも高速にビルド
  3. Common Lispプロジェクトのビルド環境としてDockerコンテナを利用

します。そしてその結果がこのリポジトリ(のsolsticeブランチ)です。

github.com

背景・動機

 おしごとで書けたり、あとは自分でつくっているプログラムであったりを、ひとつの実行可能ファイルにまとめて、さっと配布したりデプロイしたりしたいなあ、という動機です。

 自分でつくっているプログラムについてはこの記事のやつです。

octahedron.hatenablog.jp

 次のバージョンをめざしていろいろ実験中です。ビューのHTMLや画像をメモリに持ってみたり、テンプレートエンジンをLSXにしてみたり(問題の ツイート)、シングルバイナリ化もそうだし、あと、Dockerコンテナ内高速ビルド(二回目以降)など。

 Dockerコンテナ化には、もともとはおしごとで、パートナーがMac使いだったために発生したものです(ぼくはGNU/Linux使い)。そこでマルチステージビルドによるコンテナイメージの作成過程をキャッシュする方法などを覚え、そこそこストレスのない感じになっています。

RoswellとQlotについて

 去年の拙作のこの記事にも初心者向けな感じで書いていますが、いま一度。

qiita.com

Roswell

 Common Lispには処理系が複数あり、マイナーな言語であるため最新のバージョンがaptのようなパッケージリポジトリに入っていないので、常用している場合にCommon Lisp環境をさっと導入するのはあまり簡単ではありません。

 では、RubyのrbenvやPythonのpyenvのようなものがほしくなるのですが、あります。それがRoswellです。

 Roswellは基本的には処理系マネージャなのですが、そのほかにも以下のような機能が提供されています(公式のREADMEより):

 Common Lisp各処理系のコマンドラインインターフェースはばらばらであり、元来処理系ポータブルなスクリプトを書くことはめんどくさいものでした。Roswellのスクリプティング機能は、処理系ポータブルに設計されており、ひとつのスクリプトを複数の処理系で動かすことができます。非常に便利です。また、Roswellではメモリのダンプイメージ作成機能を(一部の処理系で)備えており、Roswellのスクリプトを読み込んで実行可能ファイルとして吐き出すことも可能です。

 なので、ここではそれらを組み合わせて、実行可能ファイルのコマンドラインインターフェースとしてRoswellを利用しました。

Qlot

 Common Lispでは「システム」(他言語でいうパッケージ)の取得にQuicklispを利用することが多いです。でも、システムのバージョンを個々に指定する機能はないです。そのため依存するシステムのバージョンが導入のタイミングが異なるために変わってしまう、という状況があり得ます。

 そんな状況でお困りのあなたに、Qlotです。Qlotを利用すると、システムの依存システムを固定してしまうことができるので、過去につくったプログラムが依存システムの仕様変更などなどで動かない、ということを防ぐことができます。

 Node.jsのnpmみたいな感じです。

 これまではライブラリ的なもの(inquisitor)や、小さなもの(rosa、依存システムなし)ばかりつくっていたので必要性をあまり感じなかったのですが、依存ライブラリが増えてくると、その必要性を感じはじめて、導入しました。

配布・デプロイまでの道

1. プログラムの実行可能ファイルを作成する

 まず、システムの構成を考えます。どのようなシステムであれ、Common Lispにおける開発にはきっと対話的な環境を利用することでしょう(GNU EmacsとかLemとか)。なので、基本の構造は対話的に呼べるようにします。コマンドラインから呼ぶときには、

  1. Roswellスクリプトの中でシステムをql:quickloadし、
  2. コマンドライン引数をパースして、
  3. 対応した関数を呼ぶ、

という流れにします。ざっくりとしたフォルダ構成はこんな感じです(細部は省略しています)。

.
|-- 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のマルチステージビルド

docs.docker.com

を用いてコンテナのビルド過程を細分化し、各過程をキャッシュしてしまいました(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ならね。

 一度走らせたコンテナであれば、中からファイルを取り出したり、その逆にファイルを入れたりすることができます。なので、リリース環境と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 LispANSI仕様で公式に定義されている日時表現です。プリミティブすぎるので、実際に実用する際には抽象化を施す必要がありそうです。そして、その抽象化をしてくれるライブラリがあるのです。それが次の節で述べる、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>

 たとえばこれを外部サーバのRDBMSUS/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:012:00:00より後なので、tとなるのが正しい)。

 なんでじゃ。なんでなのじゃ…。

調査開始

 時刻の不具合といえばやっぱりタイムゾーンがあやしいです。なのでいろいろ話したり試したり調べたりしてみたところ、次のようなことがわかりました:

 タイムゾーンについてほかの影響要素はないかと調べると、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に直す、ということをやったのですが、それは間違っていたということなの…?

追加調査

 結論からいえば、間違っていました。正しい原因はこうです。
mysqldCommon Lispのプログラムとの間でタイムゾーンの設定が異なると、cl-mysqlがtimestamp (SQLの型)をuniversal timeに変換するときに時間がずれる」

 家で上記の確認をしても、一向に現象が再現できないため、新たな方向で調べはじめました。確認のために書いたコードはこれです。タイムゾーンUTCに設定されたVMを立て、その中で、データベースの作成後にまずcraete-tableinsert-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:

 mysqldTZUTCの状態で固定し、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時間、UTCJSTの間の時間分の差が生まれています。

オチ

 複数のプログラムが協調して動くシステムを構築するとき、とくに日時や時刻を扱う場合には、走らせるソフトウェアの間でタイムゾーンの設定が同じになるように注意しましょう。

Forthを実装する

Forthを実装する

 スタックベース変数いらずのふしぎなプログラミング言語、ForthをCommon Lispで実装しました。というか絶賛開発中のufというもので、これです。

github.com

執筆時点で

  • 整数値のパース
  • 基本的なスタック操作命令と出力
  • ワード(Forthにおける関数)の定義と呼び出し
  • 条件分岐
  • 不完全な(なんだかバグい)REPL

ができます/あります。フィボナッチ数の計算ができるところまでは確認しました。

動機

 先日、自作Lispのためハッシュテーブルの実装について考えたと書きました。

octahedron.hatenablog.jp

 その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))))))))

 そして、解釈器本体です。コードはとても長いというわけではないので意を決して貼ります。

 やっていることはとっても単純で、ワード定義の:;、条件分岐のifelsethenを特別扱いしつつ、そのいずれでもなかった場合は、ディクショナリからのワード探索を行なう、というふうにしました。(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すごいところです。たぶんパーサが簡単な分、Lisp処理系よりも簡単なのではないでしょうか。たぶん実用的にするのにも、基礎ができたらあとはワードを充実させるだけで対応可能っぽいので、DSLにするのにもいいかもしれないです。

 ただ、ifの実装はスタック的な走査を生でゴリゴリ書かないといけないので、ちょっと面倒くさいです。今回の実装では力技で乗り切りましたが……。

これから

 ufの実装は、ifの実装がちょっと汚く、これを如何とすべきか、というところがひとつ。解決の方針としては、そもそもifを解釈しないという方針がありそうです。Forthの仕様書によれば処理系の状態はexecution、interpretation, compilationの3つあるそうですが、ifの項目を見ると、ワード定義の間(ここをcompilation modeというらしい…?)でしか使えないことが書かれています。バイナリコードにコンパイルするときに、ジャンプ先を解決してしまい、実行時にはジャンプ命令で済ませてしまう、というのがおそらく本来の実装方法のようです。なので、まずは仕様書を読み込むかLET OVER LAMBDAを読んでそのあたりを勉強してみようと思います。

 また、フィボナッチ数列を計算できたけど、もっと実際的なプログラムに使ってみたいので、なにか用途を考えなくてはならないなあと思いました。弾幕STGとか、そういうものの低レベル組み込み言語とかにしてみると楽しいかもしれません。

関係ないけど

 wlをVM型にするの、どうしようかなー。必要ないといえば必要ないけど、似非コンパイルVM機械語VMのセット)ができそうなのでやりたいとも思っており。なやましいですね。

第7回関西Lispユーザ会に行ってきた

f:id:t-sin:20181015185937j:plain

 その昔、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.lispLisp meetupでも発表者入れ替わりの合間に雑談は入るので、関西弁によるノリが新鮮だったのでしょうか。

発表

Past and Future of CG on Lisp

docs.google.com

 まずはympbycさんによる、Lispとコンピュータグラフィックスの話です。

 Lispといえばだいたい「人工知能」「Webアプリケーション(Paul Graham)」「ゲーム(クラッシュバンディクー)」と認識されることが多いですが、じつはコンピュータグラフィックスの言語だったこともある、というふうに話が始まります。SymbolicsがCGの部署をもっていたり、Lispで3Dモデルの作成やそれによるアニメーションの製作に使われていた時代もあったよね、と。

 しかし、いまは

Lisp CGの冬 (1999~現在)

 GPUの進化により並列で行列計算を行い、昔はレンダリングするのに何十時間とかかっていたレイトレーシングも、いまやリアルタイムでできるようになりました。いまやモデルそのものアニメーションそのものをすべてシェーダで生成してリアルタイムレンダリングする時代です(参考: shadertoy)。そんな「冬」の時代のコンピュータグラフィックスとは……。

 シェーダをLispで書く

 それを実現するのが、このライブラリ、CEPL。

github.com

 このライブラリは、Common Lispのマクロで記述されたLispっぽいコードを、OpenGLのシェーダ言語GLSLにコンパイルし、REPLからシェーダを書いてOpenGLの中へつっこむことを可能とします!!
 たとえばこれは、リアルタイムで描画されるLispエイリアンのデモ動画です。

www.youtube.com

 たとえばこれは、実装途中のものですがレイトレーシングです。屈折・反射をリアルタイムで描画しています。もちろんCommon Lispで!!

www.youtube.com

 おもしろいですね。ちなみに応用としては以下のようなものが考えられるそうです:

  • 物理シミュレーション
  • ライブコーディング
  • 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のマクロまわりの違いについてのぼくの印象は以下のような感じ:

神戸大学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感度の設定をミスっていて、とってもノイズが乗っていて涙目…)

f:id:t-sin:20181015231337j:plain

 まずは前面外観。これですよ! これがLispマシン!! FAST LISPです!!

f:id:t-sin:20181015231533j:plain

 前面には上から、インタプリタの内部状態と電源操作をするためのパネル、CPUのユニットが横一列に並んている区画、メモリのユニットが並んでいる区画があります。メモリユニット区画の下にあるRamda-16ってなんだったか…設計図とともに説明があり、たしかFAST LISPをコントロールする用のなにかだったような気がするのですが…思い出せない…。

f:id:t-sin:20181015232235j:plain

 ちなみにCPUとメモリの電子部品は手ではんだ付けされたそうです。

f:id:t-sin:20181015232148j:plain

 フロントのパネルに寄った写真です。7は七代目の瀧先生のコンピュータだから、だそうです。FAST LISPでは処理系が利用するスタックがソフトウェアではなくハードウェアで実装されていたので、当時としては速くプログラムを実行できたのではないか、と考察されていました。

 そしてFAST LISPの文字やLISP MACHINE SYSTEMTAKITAC 1979の文字は業者に依頼したというのではなく、ご自分で写されたそうです。なんだか「ステンシル」というワードが聞こえましたがくわしくないのでよくわかりません。

 あっ。ステップ実行とかどうやって操作するんだろうとあの場では思ってたんですが、右下にちゃんとRUN/STEPのスイッチがありますね。なるほどー。

懇親会

 懇親会は阪急・六甲駅そばの中華のお店、六甲苑というところでした。神大出身の友人に話したら、神大の飲み会とかでもよく利用されるお店のようでした。そこで中華を頂きながら、ぼくは言語を作ろうとして低いところに下りていってるけどよくわからん、あとハードウェアよくわからんという話をしてました。そのときわかりやすくていいよと教えてもらったのがこの本です:

 それにハードウェアやるならChiselというハードウェア設計言語も触ると楽しいよと教えていただきました。Chiselで書いてシミュレータ走らせるといいよ、と。

 あとは法哲学や法学のことを聞いたり、LispとCGの発表をされていたympbycさんとGLSLをLispですごいですねとお話をしたり、いろいろなお話ができました。

おわりに

 神戸大学Lispマシン、FAST LISPについての回ということで関西にお邪魔したのですが、それだけでなく、関西のLisperの方々に相手をしていただけたり、たのしいお話を聞けたりと、とても刺激になった関西Lispユーザ会でした。

 また一年後くらい(かそれ以下か)、ぜひまた遊びに行こうと思いました。


そういえば最近Forthを実装して遊んでるのですが、

github.com

Forthがふしぎすぎてよくわからんという話をcxxxrさんにしたら、Let Over LambdaではForthを実装する箇所があってForth入門にいいですよ、と教えてもらいました。そういえば目次にForthあった気がしたなあ、読むか。

ハッシュテーブル考

 このごろ、ハッシュテーブルの実装について考えていました。
 それはひとつに「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