Prologの処理系をTypeScriptで書いてみた

言語仕様の一部しか実装していませんが、一応動くものができたので公開してみます。(v10以降の)Node.jsが必要です。

github.com

Prologとは

論理型プログラミング言語の一つです。論理学をプログラミング言語に落とし込んだようなもので、「ある論理式の集合からある論理式が導けるか」みたいなものが判定できます。もう少し広げて、(論理式内に自由変数を導入し)「論理式の集合が与えらたとき、その中の各自由変数をどのような項で代入するとゴールとなる論理式が導けるか」というクエリの処理が可能です。

Wikipediaの記事が恐ろしいほど詳しいです。よく使われる処理系としてSWI-Prologがあります。

使い方

npmパッケージとして公開しています。以下のようにして使えます。

$ npm install ts-prolog -g
$ ts-prolog

使用例

以下のようなファイルをrules.plとして保存します。足し算の定義や掛け算の定義、自然数の定義などが書いてあります。

mult(z, X, z).
add(z, Y, Y).
add(s(X), Y, s(Z)) :- add(X, Y, Z).
mult(s(X), Y, Z) :- mult(X, Y, P), add(P, Y, Z).
nat(z).
nat(s(X)) :- nat(X).

以下のような形で使用できます。足し算してみたり、掛け算してみたり、自然数の集合を取得してみたり、足し算と掛け算の2つ式を連立方程式としてその解を求めたり、ということをしています。

$ ts-prolog
> ['rules.pl'].
fact added: mult(z, X, z)
fact added: add(z, Y, Y)
rule added: add(s(X), Y, s(Z)) :- [add(X, Y, Z)]
rule added: mult(s(X), Y, Z) :- [mult(X, Y, P), add(P, Y, Z)]
fact added: nat(z)
rule added: nat(s(X)) :- [nat(X)]

> add(s(z), s(s(z)), X).
[X -> s(s(s(z)))]  (ENTER)
search finished

> add(s(z), X, s(s(s(z)))).
[X -> s(s(z))] (ENTER)
search finished

> mult(s(s(z)), s(s(s(z))), X).
[X -> s(s(s(s(s(s(z))))))] (ENTER)
search finished

> nat(X).
[X -> z] (ENTER)
[X -> s(z)] (ENTER)
[X -> s(s(z))] (ENTER)
[X -> s(s(s(z)))] (ENTER)
[X -> s(s(s(s(z))))] (Ctrl-C)

> add(X, Y, s(s(z))).
[X -> z, Y -> s(s(z))] (ENTER)
[X -> s(z), Y -> s(z)] (ENTER)
[X -> s(s(z)), Y -> z] (ENTER)
search finished

> add(X, Y, s(s(z))), mult(X, Y, s(z)).
[X -> s(z), Y -> s(z)] (ENTER)
search finished

実装について

パーサ

特にライブラリは使わずに、自分で簡単なものを実装してみました。LR構文解析器などを作っても良かったのですが、比較的文法が単純なことから、正規表現などをつかってゴリゴリやってしまっています。完璧ではないはずです。

本体

  • ファンクタ(「使用例」のadd, natなど)を表すFunctorクラス
  • 定数(「使用例」のzなど)を表すConstantクラス
  • 変数(「使用例」のX, Yなど)を表すVariableクラス
  • ファンクタの項への適用(add(X, Y, Z)など)を表すApplicationクラス

を定義し、項を表すTerm型をtype Term = Functor | Constant | Variable | Applicationのようにして定義しています。

また、次のようなクラスも用意しています。

  • 述語を表すPredicateクラス
  • ファクト(例: nat(z).でゼロは自然数であることを表現する)を表すFactクラス
  • ルール(例: nat(s(X)) :- nat(X).でXが自然数ならばXに1を足したものが自然数であることを表現する)を表すRuleクラス
  • ゴール(例: nat(X).で自然数であるようなものを探したいことを表現する)を表すGoalクラス

ゴールとファクト/述語を単一化(unification)するために制約を表すConstraintクラスを用意しており、Constraint.unify(terms: Term[])によって、単一化ができるようになっています(自由変数への項の代入を表すSubstitutionクラスを返します)。

一番メインとなるのがSpaceクラスで、これはルールの集合とファクトの集合です。Space.query(goals: Goal[])によって、その空間内での探索が始まります。これは基本的には「自由変数から項へのマッピング」の列を返します。例えば上の例だとnat(X)[[X -> z], [X -> s(z)], ...]のようなものを返します。これは無限列になることがしばしばあるため、イテレータを返すようにしています。

SWI-PrologなどはDFSですが今回はキューを用いてBFSでやってみています。無限ループに陥るゴールの集合が少し変わります。自分はこちらのほうが直感的な気がします。

CLI

インターフェイスについては特にユーザーランドのライブラリなどは用いず、Node.jsコアのreadlineモジュールを利用しました。Ctrl-Cのキャプチャなど、案外いろいろなことができます。

ユーザーからのインプットを受け取り、次のようなことをします。

  • ファイルの読み込みが要求されたらそのファイルを開いてルールとゴールを追加する
  • クエリ(ゴールの集合)が入力されたらそれに対する答え(自由変数から項へのマッピング)を一つずつ(すべての探索が終了するかCtrl-Cが押されるまで)出力する

ソースコード

こちらで公開しています。なにか質問や疑問、バグなどあれば教えていただけると嬉しいです。

github.com

Dockerイメージのビルド時にシンボリックリンクの実体を含める

タイトルがわかりにくいですが...

事の発端

以下のような構成のディレクトリがあったとします。

  • /foo (共有したいファイル)
  • /bar/foo (/fooへのシンボリックリンク)
  • /bar/Dockerfile
  • /baz/foo (/fooへのシンボリックリンク)
  • /baz/Dockerfile

そして、{bar,baz}/DockerfileCOPY foo ...のような記述があったとします。

そのとき、fooとbarの各ディレクトリにおいてdocker build .のようなコマンドで(そのディレクトリをコンテキストとして)dockerイメージをビルドしようとするとエラーが出ます。具体的にはCOPY failed: Forbidden path outside the build contextと言われます。

「それはそう」という感じなのですが、このような場面において「ファイルを追加する際、それがシンボリックリンクならばそれをたどって実体をイメージに追加する」といったことができても便利なのではないかと思ったりすることがありました。

解決策

ここでなるほどと思う解決策を見つけました。

docker build .の代わりにtar -czh . | docker build -ようにすればよい」というものです。

具体的にはこのような感じのことが起こっています。

  • tar -czh .で、カレントディレクトリをgzipにアーカイブする。その際、シンボリックリンクが存在した場合はそれをたどり、辿った先のファイルの内容でそのリンクを置き換える(-hオプション)。
  • それをコンテキストとしてdocker buildにわたす。

なるほどなあという感じですね。

実際にやってみると、このようにうまくいきます。

$ echo 'foo' > foo
$ mkdir bar
$ cd bar
$ ln -s ../foo foo
$ cat <<EOF >Dockerfile
FROM busybox
WORKDIR /work
COPY foo .
EOF
$ tar -czh . | docker build -
Sending build context to Docker daemon  10.24kB
Step 1/3 : FROM busybox
 ---> e4db68de4ff2
Step 2/3 : WORKDIR /work
 ---> Using cache
 ---> 2daef8292bd0
Step 3/3 : COPY foo .
 ---> Using cache
 ---> 1ec7cbed7c90
Successfully built 1ec7cbed7c90
$docker run -it 1ec7cbed7c90
/work # cat foo
foo

tar -czh . | docker build -docker build .におきかえるとエラーがでることも確認できます。


ちなみに執筆時点でのdockerのバージョンは以下の通りでした。

$ docker --version
Docker version 18.09.2, build 6247962

Docker上のUbuntuでmanページなどを見れるようにする

問題

コンテナにおいてイメージサイズの小ささは正義です。 そのため、UbuntuのDockerイメージはいろいろなものを削り落としています。その削り落とされているものの一つとして、manページが挙げられます。

例えば、次のようにUbuntuのイメージからコンテナを起動してmanコマンドを実行するとエラーがでます。

$ docker run -it ubuntu:18.04
root@[...]:/# man read
bash: man: command not found

「Mac上のDockerコンテナでLinuxのシステムプログラミングをしたい」という状況にあり、どうにかならないかと思っていました。

解決策

つまらないのですが、コンテナ内でunminimizeというプログラムを実行することにより解消することができます。

実際にコンテナ内のシェルでunminimizeを実行すると次のようになります。「インタラクティブな使用がメインでないシステムに不要なパッケージやコンテンツは削除されているよ。このコマンドはそれを復活させるよ。少し時間かかるけれどそれでもよければyを入力してね。」(超意訳)みたいなことを言われます。

$ unminimize
This system has been minimized by removing packages and content that are
not required on a system that users do not log into.

This script restores content and packages that are found on a default
Ubuntu server system in order to make this system more suitable for
interactive use.

Reinstallation of packages may fail due to changes to the system
configuration, the presence of third-party packages, or for other
reasons.

This operation may take some time.
Would you like to continue? [y/N]y

yを入力し、処理が終了すると実際にmanコマンドが使えるようになっていることがわかります。

$ which man
/usr/bin/man

unminimize済みのイメージを作るともちろんサイズはかなり大きくなります。普通のUbuntuのイメージは100MBくらいなのですが、以下のようなDockerfileを作成してイメージをビルドしてみると400MBくらいになりました。

FROM ubuntu:18.04
RUN apt-get update && yes | unminimize

安全で軽量なコンテナランタイム「gVisor」について

f:id:k-kty:20190505233414p:plain
gVisorのロゴ

「少し聞いたがことある」程度だったのですが、Software Engineering Dailyというポッドキャストのエピソードで耳にしたのを機に、gVisorについて調べてみました。そして日本語の情報もあまり多くなかったので軽く記事にしました。

gVisorとは

gVisorは、安全かつ軽量なコンテナのランタイムです。2018年のKubeConでGoogleから発表されました。

この記事では

  • なぜgVisorが開発されたのか
  • gVisorの仕組み・特徴

などを見ていきます。

なぜgVisorが開発されたのか

分離された環境を簡単に用意できるコンテナ技術は、開発においてもデプロイにおいても大変便利ですが、セキュリティ面での分離はできません。

カーネル(+仮想的なマシンリソース)を複数用意することになる仮想マシンに比べ、「一つのカーネルをうまく共有して使う」ようになっているコンテナにはパフォーマンス面でのメリットがあります。しかし、そのメリットと表裏一体となってセキュリティ面でのデメリットが存在します。カーネルの脆弱性の影響をもろにうけてしまうわけです。

実際、CVE-2016-5195というLinuxカーネルの脆弱性のPoCの中に、Dockerコンテナ内からホストマシンのrootを奪取してしまうというものがあったようです。

よって、悪意のある処理が含まれうるコンテナを実行する必要のある組織(例えばIaaSを提供している企業)は「ホストマシン上で直でコンテナを動かす」ということはできません。そして、各コンテナに対して仮想マシンを用意するなどしなくてはならず、リソース利用の効率やパフォーマンスの面で問題がありました。

そのジレンマへの一つのアプローチとしてgVisorが開発されました。

gVisorの仕組み・特徴

gVisorは「ユーザー空間で動くカーネル」のようなものです。コンテナ内のアプリケーションが出したシステムコールをインターセプトして処理します。

Linuxの各システムコールの実装に対応する実装がgVisor内にあり、アプリケーションが出したシステムコールは(gVisorによって横取りされ)その実装によって処理されます。そして、gVisorが必要に応じてホストOSに対してシステムコールを投げるようになっています。gVisorからホストOSに対して発行されるシステムコールの種類は意図的に絞られています。(Linuxのseccompというのがありますね)。

アプリケーションから「数多くの種類の」システムコールを「ホストのカーネルに直接」発行することができてしまう通常のコンテナランタイムと比べると、明らかに安全になっていることがわかります。システムのうちアプリケーションから直接アクセス可能な部分を最小限にする、すなわちアプリケーションとシステムの分離のレベルを上げることでセキュリティを向上させているわけです。

また、(仮想的なマシンリソースを用意する必要がある)仮想マシンを用いた仮想化に比べるとオーバーヘッドは小さく、そして柔軟性が高まっています。仮想マシンだと起動時にメモリの容量などを決めないといけないですが、gVisorを用いると(普通のプロセスと同様で)そんなことはありません。

使い方

おなじみのDockerやKubernetesで簡単に使えます。公式のガイドも整っています。

gVisorが提供するコンテナのランタイムはOpen Container Initiativeの仕様に準拠していて、docker run --runtime=runsc ...のように指定すれば使えるようです。

現在はx64上のLinuxのみのサポートのようです。(詳しい数値は少しわかりませんが...)エンタープライズのクラウドの世界では大多数ですよね?

実用例

GCPのCloud Runが先月発表されて盛り上がっています。(自分も少し触ってみて感動しています。)

そのCloud Runですが、ドキュメントによるとgVisorが用いられているみたいです。

パーフェクトマッチな用途ですね。

また、gVisorの発表(2018年)以前からGoogleの内部では使われてきたようです。

参考

この記事では大枠のみになってしまいましたが、いろいろと参考になるリソースがありますので、興味のある人は覗いてみてください。

公式ページでは使い方のほか、アーキテクチャや開発のモチベーションなども触れられています。

GoogleでPMをされているYoshi Tamuraさんのインタビューも参考になりました。憧れます。

冒頭でも紹介しましたがSoftware Engineering Dailyのエピソードも参考になりました。実はこちらもYoshi Tamuraさんのインタビューです。

レポジトリはこちら。メモリ安全性や型安全性が評価され、Goを用いて実装されたようです。Dockerの実装もGoですしKubernetesの実装もGoですし大人気ですね。

おまけ: Kata Containers

コンテナとセキュリティに関連するプロジェクトとしてはKata Containersというのも有名なようです。こちらではKata Containers is an open source container runtime, building lightweight virtual machines that seamlessly plug into the containers ecosystem.と謳っていて、「軽量な仮想マシン」を用いることで安全なコンテナの実行環境を用意できるようです。gVisorとは少し違ったアプローチでとても興味深いので気が向いたときに調べてみようかと思います。

Bcryptを用いてパスワードをハッシュ化する (Node.js)

ログイン機能のあるアプリケーションを開発する場合、(大体の場合は)ユーザーにパスワードを設定してもらうことになります。当然ですがそれらのパスワードを平文でデータベースに保存したりするのはセキュリティ的にご法度で、ハッシュ化して保存をする必要があります。

この記事では、bcrypt というパッケージを用いて、Node.jsでパスワードをハッシュ化する方法・そしてそれを用いてパスワードをチェックする方法を紹介します。ちなみに、bcryptはハッシュ化アルゴリズムの名前でもありパッケージの名前でもあります。以下混同して使用しています。

準備

まずはbcryptをインストールします。TypeScriptの型定義ファイルももちろんあります。

$ npm install bcrypt --save
$ npm install @types/bcrypt --save-dev # TypeScriptを利用している場合

ちなみに執筆時では bcrypt@3.0.5 が入りました。

ハッシュ化

まずは平文のパスワードをハッシュ化します。会員登録時やパスワード変更時に行う処理ですね。

以下のように、パスワードを「ラウンド数」とともに bcrypt.hash 関数に渡します。

ラウンド数を大きくすればするほど安全なハッシュを生成することができますが、計算に要する時間が長くなります(ラウンド数が1増えると時間は2倍ほどになるそうです)。こちらによると、ラウンド数10でのハッシュ化には2.0GHzのCPUで0.1秒ほどかかるようです。

ここではラウンド数を10に設定しています。通常はこれくらいで(もう少し小さくても?)大丈夫そうです。

const bcrypt = require('bcrypt');

const saltRounds = 10;

bcrypt.hash(password, rounds)
  .then((hashedPassword) => {
    // ...
  });

チェック

平文のパスワード(password)とハッシュ化されたパスワード(hashedPassword)を比較し、その平文のパスワードが正しいかどうかをチェックします。ログイン時の処理ですね。正しければisCorrectPasswordtrueに、そうでなければfalseになります。

bcrypt.compare(password, hashedPassword)
  .then((isCorrectPassword) => {
    // ...
  });

おまけ

  • bcryptの計算の概要について大雑把に説明します。まずランダムでソルトを作成しています。そして、平文パスワードとソルトを組み合わせてハッシュ化し、そのハッシュとソルトを組み合わせてハッシュ化し、そのハッシュとソルトを組み合わせてハッシュ化し...というのを何回も繰り返しているようです。その回数を調整しているのがラウンド数というわけです。
  • 上の例でのhashedPasswordには、ラウンド数やソルトの情報も含まれています。compare関数は「ラウンド数やソルトの情報を抜き出し、それをもとに平文パスワードをソルトともに指定回数ハッシュ化し、比較する」ということをやってます。
  • 上の例の通り、bcryptは、コスト(ラウンド数)を設定できるようになっています。これにより、コンピューターの計算能力が伸びて攻撃側の能力が上がったとしても(ラウンド数を上げることで)同じアルゴリズムを利用し続けることができるというメリットがあります。
  • bcryptには、hashSync 関数や compareSync 関数などの同期的な関数も存在します。しかし、簡単なスクリプト等以外には使用はするべきではありません。上にも書きましたが、これらの関数は計算量の大きい処理をするので、ある程度時間がかかります。その間イベントループがブロックされてしまい、他の処理が(ほとんど)できなくなります。サーバーアプリケーションの場合はリクエストに対する処理ができなくなってしまいます。ちなみに、hash 関数や compare 関数を呼び出した際はスレッドプールを利用して(メインスレッド外で)処理をするので、イベントループのブロックはおきません。そして、複数のCPUコアを有効活用できます。

Cのプログラムをx86-64のマシン上でPowerPC向けにコンパイルする

x86-64のマシン + Ubuntu 16.04で、PowerPC 64bit向けにC言語のプログラムをコンパイルする方法を紹介します。俗に言うクロスコンパイルっていうやつです。

以下のように、必要なものをaptで入れます。binutilsにはアセンブラやローダが入っています。

$ sudo apt install gcc-powerpc-linux-gnu binutils-powerpc-linux-gnu

これで環境は整ったので、実際に動かしてみます。まず、以下のファイルをa.cとして保存します。

int fact(int n) {
  if (n == 1) return 1;
  return n * fact(n - 1);
}

以下のようなコマンドでコンパイルします。わかりやすさのために最適化オプションを無効にし、アセンブリを出力しています。

$ powerpc64-linux-gnu-gcc -S a.c -O0

以下のような(見慣れた?)PowerPCのアセンブリを得ることができました。

 .file   "a.c"
    .machine power7
    .section    ".toc","aw"
    .section    ".text"
    .align 2
    .globl fact
    .section    ".opd","aw"
    .align 3
fact:
    .quad   .L.fact,.TOC.@tocbase,0
    .previous
    .type   fact, @function
.L.fact:
    mflr 0
    std 0,16(1)
    std 31,-8(1)
    stdu 1,-128(1)
    mr 31,1
    mr 9,3
    stw 9,176(31)
    lwz 9,176(31)
    cmpwi 7,9,1
    bne 7,.L2
    li 9,1
    b .L3
.L2:
    lwz 9,176(31)
    addi 9,9,-1
    extsw 9,9
    mr 3,9
    bl fact
    mr 9,3
    mr 10,9
    lwz 9,176(31)
    mullw 9,9,10
    extsw 9,9
.L3:
    mr 3,9
    addi 1,31,128
    ld 0,16(1)
    mtlr 0
    ld 31,-8(1)
    blr
    .long 0
    .byte 0,0,0,1,128,1,0,1
    .size   fact,.-.L.fact
    .ident  "GCC: (Ubuntu/IBM 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609"

とても簡単で最高ですね。

ちなみに、今回入ったアプリケーションたちのバージョンはこのような感じでした。

$ powerpc64-linux-gnu-gcc --version
powerpc64-linux-gnu-gcc (Ubuntu/IBM 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609
...
$ powerpc64-linux-gnu-as --version
GNU assembler (GNU Binutils for Ubuntu) 2.26.1
...
$ powerpc64-linux-gnu-ld --version
GNU ld (GNU Binutils for Ubuntu) 2.26.1
...

URLから画像のサイズを取得する(Node.js)

サーバーサイドアプリケーションを書いていると、「あるURLでアクセスできる画像の(縦横の)サイズを知りたい」という場面がまれにあると思います。Nodejsにおいて、そういった場合にどうしたらよいかを紹介します。

準備

image-size を利用します。また、ここでは axios を用いますが、node-fetch など他のライブラリでも同様にできると思います。標準ライブラリの https.requesthttp.request を用いることもできますが、いろいろとめんどくさいと思います(そもそもhttpかhttpsかで使うライブラリを分けなくてはいけない?)。

ちなみに執筆時点でのバージョンは axios@0.18.0, image-size@0.7.3 です。

$ npm i image-size axios

実装

以下のような関数を用意します。axios.get のオプションにおいて responseType: 'arraybuffer' と指定してあげないと、 res.data が文字列になったりしてうまくいきません(ContentTypeなどをもとにうまくやってほしいとも思ってしまいますが...)。

この関数に画像のURLを投げれば、width プロパティ(number)と height プロパティ(number)をもったオブジェクト(のプロミス)を返してくれます。大体のメジャーなフォーマットに対応してくれています。

const imageSize = require('image-size');
const axios = require('axios');

function fetchSize(imgUrl) {
  return axios.get(imgUrl, {
    responseType: 'arraybuffer',
  })
    .then(res => imageSize(res.data))
    .then(i => ({
      width: i.width,
      height: i.height,
    }));
}

TypeScriptの場合

簡単ですが、TypeScriptだと以下のようになります。

import imageSize from 'image-size';
import axios from 'axios';

function fetchSize(imgUrl: string): Promise<{ height: number; width: number; }> {
  return axios.get(imgUrl, {
    responseType: 'arraybuffer',
  })
    .then(res => imageSize(res.data))
    .then(i => ({
      width: i.width,
      height: i.height,
    }));
}