---
[article]
uuid = "f4985d54-0907-4449-8101-0fcd382f9e02"
title = "PHPerKaigi 2022 トークン問題の解説"
description = "PHPerKaigi 2022 で私が作成した PHPer チャレンジ問題を解説する。"
tags = [
  "conference",
  "php",
  "phperkaigi",
]

[[article.revisions]]
date = "2022-04-09"
remark = "公開"

[[article.revisions]]
date = "2022-04-16"
remark = "2問目、3問目の解説を追加、1問目に加筆"
---
{#intro}
# はじめに

本日開始された [PHPerKaigi 2022](https://phperkaigi.jp/2022/) の PHPer
チャレンジにおいて、弊社
[デジタルサーカス株式会社](https://www.dgcircus.com/) の問題を
3問作成した。この記事では、これらの問題の解説をおこなう。

リポジトリはこちら: https://github.com/nsfisis/PHPerKaigi2022-tokens

{#q1-brainfuck}
# 第1問 brainf_ck.php

ソースコードはこちら。実行には PHP 8.1 以上が必要なので注意。

{filename="brainf_ck.php"}
```php
<?php

declare(strict_types=0O1);

namespace Dgcircus\PHPerKaigi\Y2022;

/**
 * @todo
 * Run this program to acquire a PHPer token.
 */

https://creativecommons.org/publicdomain/zero/1.0/

\error_reporting(~+!'We are hiring!');

$z = fn($f) => (fn($x) => $f(fn(...$xs) => $x($x)(...$xs)))(fn($x) => $f(fn(...$xs) => $x($x)(...$xs)));
$id = \spl_object_id(...);
$put = fn($c) => \printf('%c', $c);
$mm = fn($p, $n) => new \ArrayObject(\array_fill(+!![], $n, $p));

$👉 = fn($m, $p, $b, $e, $mp, $pc) => [++$mp, ++$pc];
$👈 = fn($m, $p, $b, $e, $mp, $pc) => [--$mp, ++$pc];
$👍 = fn($m, $p, $b, $e, $mp, $pc) => [$mp, ++$pc, ++$m[$mp]];
$👎 = fn($m, $p, $b, $e, $mp, $pc) => [$mp, ++$pc, --$m[$mp]];
$📝 = fn($m, $p, $b, $e, $mp, $pc) => [$mp, ++$pc, $put($m[$mp])];
$🤡 = fn($m, $p, $b, $e, $mp, $pc) => match ($m[$mp]) {
  +!![] => [$mp, $z(fn($loop) => fn($pc, $n) => match ($id($p[$pc])) {
    $b => $loop(++$pc, ++$n),
    $e => $n === +!![] ? ++$pc : $loop(++$pc, --$n),
    default => $loop(++$pc, $n),
  })($pc, -![])],
  default => [$mp, ++$pc],
};
$🎪 = fn($m, $p, $b, $e, $mp, $pc) => match ($m[$mp]) {
  +!![] => [$mp, ++$pc],
  default => [$mp, $z(fn($loop) => fn($pc, $n) => match ($id($p[$pc])) {
    $e => $loop(--$pc, ++$n),
    $b => $n === +!![] ? $pc+![] : $loop(--$pc, --$n),
    default => $loop(--$pc, $n),
  })($pc, -![])],
};
$🐘 = fn($p) => $z(fn($loop) => fn($m, $p, $b, $e, $mp, $pc) =>
  isset($p[$pc]) && $loop($m, $p, $b, $e, ...($p[$pc]($m, $p, $b, $e, $mp, $pc)))
)($mm(+!![], +(![].![])), $p, $id($🤡), $id($🎪), +!![], +!![]);

$🐘([
  $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍,
  $🤡,
  $👉, $👍, $👍, $👍,
  $👉, $👍, $👍, $👍, $👍, $👍,
  $👉, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍,
  $👉, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍,
  $👈, $👈, $👈, $👈, $👎,
  $🎪,
  $👉, $👍, $👍, $👍, $👍, $👍, $📝,
  $👎, $👎, $📝,
  $👉, $👎, $👎, $👎, $📝,
  $👉, $👎, $👎, $👎, $📝,
  $👎, $👎, $📝,
  $👎, $📝,
  $👈, $📝,
  $👉, $👉, $👎, $👎, $📝,
  $👍, $👍, $👍, $👍, $👍, $👍, $👍, $📝,
  $👈, $👎, $👎, $👎, $👎, $📝,
  $👈, $📝,
  $👉, $👍, $👍, $📝,
  $👉, $👎, $📝,
  $👈, $📝,
]);
```

この問題は、単に適切なバージョンの PHP で動かせばトークンが得られる。

{#commentary}
## 解説

{#emoji}
### 絵文字

まず目につくのは大量の絵文字だろう。 PHP
は識別子に使用できる文字の範囲が広く、絵文字も使うことができる。

{#brainfuck}
### プログラム全体

Brainf\*ck のインタプリタとプログラムになっている。 Brainf\*ck
とは、難解プログラミング言語のひとつであり、ここで説明するよりも
Wikipedia の該当ページを読んだ方がよい。

https://ja.wikipedia.org/wiki/Brainfuck

なお、brainf*ck プログラムを普通の書き方で書くと、次のようになる。

```
+ + + + + + + + + +
[
  > + + +
  > + + + + +
  > + + + + + + + + + + + +
  > + + + + + + + + + +
  < < < < -
]
> + + + + + .
- - .
> - - - .
> - - - .
- - .
- .
< .
> > - - .
+ + + + + + + .
< - - - - .
< .
> + + .
> - .
< .
```

実行結果はこちら: https://ideone.com/22VWmb

それぞれの絵文字で表された関数が、各命令に対応している。

* `$👉`: `&gt;`
* `$👈`: `&lt;`
* `$👍`: `+`
* `$👎`: `-`
* `$📝`: `.`
* `$🤡`: `[`
* `$🎪`: `]`

`,` (入力) に対応する関数はない
(このプログラムでは使わないので用意していない)。

なお、`$🐘` はいわゆる main 関数であり、プログラムの実行部分である。

{#emoji-selection}
### 絵文字の選択

おおよそ意味に合致するよう選んでいるが、`$🤡` と `$🎪`
は弊社デジタルサーカスにちなんでいる。 また、`$🐘` は PHP
のマスコットの象に由来する。

{#strict-types}
### strict_types

`declare` 文の `strict_types` に指定できるのは、`0` か `1`
の数値リテラルだが、 `0x0` や `0b1` のような値も受け付ける。 今回は、PHP
8.1 から追加された、`0O` または `0o` から始まる八進数リテラルを使った。

{#url}
### URL

ソースコードのライセンスを示したこの部分だが、

```php
https://creativecommons.org/publicdomain/zero/1.0/
```

完全に合法な PHP のコードである。 `https:` 部分はラベル、`//`
以降は行コメントになっている。

{#numbers}
### リテラルなしで数値を生成する

ソースコード中に、ほとんど数値リテラルが書かれていないことにお気づきだろうか。
PHP では、型変換を利用することで任意の整数を作り出すことができる。

```php
assert(0 === +!![]);
assert(1 === +![]);
assert(2 === ![]+![]);
assert(3 === ![]+![]+![]);
assert(10 === +(![].+!![]));
```

`[]` に `!` を適用すると `true` が返ってくる。それに `+`
を適用すると、`bool` から `int` ヘの型変換が走り、`1` が生成される。`10`
はさらにトリッキーだ。まず `1` と `0` を作り、`.` で文字列として結合する
(`'10'`)。これに `+` を適用すると、`string` から `int`
への型変換が走り、`10` が生まれる (コード量に頓着しないなら、`1` を 10
個足し合わせてももちろん 10 が作れる)。

また、`error_reporting` に指定しているのは `-1` である。 これは、`!`
によって文字列を `false` にし、`+` によって `false` を `0`
にし、さらにビット反転して `-1` にしている。

{#conditionals}
### `if` 文なしで条件分岐

三項演算子ないし `match` 式を使うことで、`if`
を一切書かずに条件分岐ができる。 また、`&amp;&amp;` / `||` も使えることがある。
遅延評価が不要なケースでは、`[$t, $f][$cond]`
のような形で分岐することもできる。

{#loops}
### `while`、`for` 文なしでループ

不動点コンビネータを使って無名再帰する
(詳しい説明は省略する。これらの単語で検索してほしい)。 ここでは、一般に
Z コンビネータとして知られるものを使った (`$z`)。

実際のところ、`$🤡` や `$🎪`、`$🐘` は、一度 Scheme (Lisp の一種)
で書いてから PHP に翻訳する形で記述した。

なお、PHP は末尾再帰の最適化をおこなわない (少なくとも今のところは)
ので、 あまりに長い brainf*ck
プログラムを書くとスタックオーバーフローする。

{#q2-riddle}
# 第2問 riddle.php

ソースコードはこちら。実行には PHP 8.0 以上が必要なので注意。

{filename="riddle.php"}
```php
<?php

/*********************************************************
 * This program displays a PHPer token.                  *
 * Guess 'N'.                                            *
 *                                                       *
 * Hints:                                                *
 * - N itself has no special meaning, e.g., 42, 8128,    *
 *   it is selected at random.                           *
 * - Each element of $token represents a single letter.  *
 * - One letter consists of 5x5 cells.                   *
 * - Remember, the output is a complete PHPer token.     *
 *                                                       *
 * License:                                              *
 *   https://creativecommons.org/publicdomain/zero/1.0/  *
 *********************************************************/
const N = 0 /* Change it to your answer. */;
assert(0 <= N && N <= 0b11111_11111_11111_11111_11111);

$token = [
  0x14B499C,
  0x0BE34CC, 0x01C9C69,
  0x0ECA069, 0x01C2449, 0x0FDB166, 0x01C9C69,
  0x01C1C66, 0x0FC1C47, 0x01C1C66,
  0x10C5858, 0x1E4E3B8, 0x1A2F2F8,
];
foreach ($token as $x) {
  $x = $x ^ N;

  $x = sprintf('%025b', $x);
  $x = str_replace(search: ['0', '1'], replace: [' ', '#'], subject: $x);
  $x = implode("\n", str_split($x, length: 5));
  echo "{$x}\n\n";
}
```

さて、この問題はさきほどのように単純に実行しただけでは、謎のブロックが表示されるだけでトークンは得られない。
トークンを得るためには、ソースコードを読み、定数 `N`
を特定する必要がある。

ここでは、私の想定解を解説する。

{#code-reading}
## 読解

まずはソースコードを読んでいく。

```php
$token = [
  // 略
];
```

数値からなる `$token` があり、各要素をループしている。

```php
$x = $x ^ N;
```

まずは排他的論理和 (xor) を取り、

```php
$x = sprintf('%025b', $x);
```

二進数に変換して、

```php
$x = str_replace(search: ['0', '1'], replace: [' ', '#'], subject: $x);
```

0 を空白に、1 を `#` にし、

```php
$x = implode("\n", str_split($x, length: 5));
```

5文字ごとに区切ったあと、改行で結合している。

{#hint}
## ヒント

次に、ソースコードに書いてあるヒントを読んでいく。

* `N` それ自体は、42 や 8128 といったような特別な意味を持たず、ランダムに決められている
* `$token` の各要素は、1文字を表す
* 1文字は 5x5 のセルからなる
* 出力されるのは、完全な PHPer トークンである

ここで、PHPer トークンは必ず `#` 記号から始まることを思いだすと、
`$token` の最初の数字 `0x14B499C` は、変換の結果 `#`
になるのではないかと予想される (なお、このことは、リポジトリの README
ファイルに追加ヒントとして書かれている)。

{#solve}
## 解く

ここまでわかれば、あと一歩で解ける。すなわち、`0x14B499C` が `#`
に変換されるような `N` を見つければよい。

`N` は高々

```php
assert(0 <= N && N <= 0b11111_11111_11111_11111_11111);
```

なのでブルートフォースしてもよいが、ここではブルートフォースしない方法を紹介する。

```php
<?php

$x = 0x14B499C;

$x = $x ^ N;

$x = sprintf('%025b', $x);
$x = str_replace(search: ['0', '1'], replace: [' ', '#'], subject: $x);
$x = implode("\n", str_split($x, length: 5));

assert($x ===
" # # \n" .
"#####\n" .
" # # \n" .
"#####\n" .
" # # ");
```

この一連の変換に対する逆変換を考えると、次のようになる。

```php
<?php

$x =
" # # \n" .
"#####\n" .
" # # \n" .
"#####\n" .
" # # ";

$x = implode('', explode("\n", $x));
$x = str_replace(search: [' ', '#'], replace: ['0', '1'], subject: $x);
$x = bindec($x);

$n = $x ^ 0x14B499C;

echo "N = $n\n";
```

これを実行すると、`N` が得られる。

{#q3-toquine}
# 第3問 toquine.php

ソースコードはこちら。

{filename="toquine.php"}
```php
<?php

// License: https://creativecommons.org/publicdomain/zero/1.0/
// This is a quine-like program to generate a PHPer token.
// Execute it like this: php toquine.php | php | php | php | ...

$s = <<<'Q'
<?cuc
// Yvprafr: uggcf://perngvirpbzzbaf.bet/choyvpqbznva/mreb/1.0/
// Guvf vf n dhvar-yvxr cebtenz gb trarengr n CUCre gbxra.
// Rkrphgr vg yvxr guvf: cuc gbdhvar.cuc | cuc | cuc | cuc | ...
%f$f = %f;
$f = fge_ebg13($f); $kf = [
%f,
];
$g = ahyy.snyfr; sbe ($v = 0; $v <= vagqvi(__YVAR__-035,6); ++$v) vs (!vffrg($kf[$v])) oernx; ryfr
$g .= vzcybqr("\a", fge_fcyvg(fge_ercynpr(['0','1'], ['  ','##'], fcevags(pue(37) . '025o', $kf[$v])), 012)) . "\a\a";
$jf = neenl_znc(sa($j) => vzcybqr(', ', $j), neenl_puhax(neenl_znc(sa($k) => fcevags('0k' . pue(37) . '07K', $k), $kf), 10));
cevags($f, $g, fge_ebg13("<<<'Q'\a{$f}\aQ"), vzcybqr(",\a", $jf));
Q;
$s = str_rot13($s); $xs = [
0x0AFABEA, 0x1F294A7, 0x1F2109F, 0x1F294A7, 0x0002800, 0x1F2109F, 0x0117041, 0x1F294A7, 0x1FAD6B5, 0x1F295B7,
0x010FC21, 0x1FAD6B5, 0x1151151, 0x010FC21, 0x1F294A7, 0x1F295B7, 0x1FAD6B5, 0x1F294A7, 0x1F295B7, 0x1F8C63F,
0x1F8C631, 0x1FAD6B5, 0x17AD6BD, 0x17AD6BD, 0x1F8C63F, 0x1F295B7,
];
$t = null.false; for ($i = 0; $i <= intdiv(__LINE__-035,6); ++$i) if (!isset($xs[$i])) break; else
$t .= implode("\n", str_split(str_replace(['0','1'], ['  ','##'], sprintf(chr(37) . '025b', $xs[$i])), 012)) . "\n\n";
$ws = array_map(fn($w) => implode(', ', $w), array_chunk(array_map(fn($x) => sprintf('0x' . chr(37) . '07X', $x), $xs), 10));
printf($s, $t, str_rot13("<<<'D'\n{$s}\nD"), implode(",\n", $ws));
```

コメントにもあるとおり、次のようにして実行すれば答えがでてくる。

```shell-session
$ php toquine.php | php | php | php | ...
```

実際にはもう少しパイプで繋げなければならない。

{#commentary}
## 解説

{#quine}
### プログラム全体

コメントにもあるとおり、これは quine (風) のプログラムになっている。
Quine
とは、自分のソースコードをそっくりそのまま出力するようなプログラムのことである。

このプログラムは、実行すると自身とほとんど同じプログラムを出力する。
異なるのはトークンになっている部分のみである。

{#tokens}
### トークン

`$xs` がトークンに対応している。変換のロジックは `riddle.php`
とほぼ同じなので省略する。

{#states}
### 状態保持

トークンの何文字目まで出力したかを、ソースコードを変えずに (quine
なので) 覚えておく必要がある。
このプログラムでは、トークンが出力されるとソースコードがだんだんと長くなっていくのを利用して、`__LINE__`
から情報を取得している。

{#rot-13}
### ROT 13

Quine は、素朴に書くとプログラムの一部が 2回記述されてしまう。
これがあまり美しくないので、`toquine.php` では、ROT 13
変換を使って難読化した。

それにしてもなぜこんなものが標準ライブラリに……。

{#outro}
# おわりに

解いていただいたみなさん、また、難易度調整につきあっていただいた社内のみなさん、ありがとうございました。

今回は直前に作りはじめたのもあり、3問だけかつ使い古されたネタばかりになってしまいましたが、
来年は 5問、より面白い問題を持っていきます。

実はもう作りはじめているので、どうか来年もありますように……。