PHPでコードゴルフ - Brainf*ck

この記事は、以下の記事の続きです。

https://qiita.com/takaram/items/5ee3957a2303f2c3c559

第3問の自分の提出コードの解説をします。

## 第3問：Brainf*ck
https://t.nil.ninja/phperkaigi/2024/golf/q/brainf-ck/

プログラミング言語[Brainf*ck](https://ja.m.wikipedia.org/wiki/Brainfuck)のインタプリタを実装する問題でした。
私の提出コードがこちらです。

```php
$s=fread(STDIN,9999);$p=-1;function l($s,&$p,$r){for($d=1;$d+=["["=>$r,"]"=>-$r][$s[$p+=$r]]??0;);}for($m=[$t=0];$s[++$p]??0;){$a=&$m[$t];match(ord($s[$p])){62=>$t++,60=>$t--,43=>$a++,45=>$a--,46=>print chr($a),91=>$a||l($s,$p,1),93=>$a&&l($s,$p,-1),default=>0};}
```

整形するとこんな感じ。

```php
$s = fread(STDIN, 9999);
$p=-1;

function l($s, &$p, $r)
{
  for ($d = 1; $d += ["[" => $r, "]" => -$r][$s[$p += $r]] ?? 0;);
}

for ($m = [$t = 0]; $s[++$p] ?? 0;) {
  $a = &$m[$t];
  match (ord($s[$p])) {
    62 => $t++,
    60 => $t--,
    43 => $a++,
    45 => $a--,
    46 => print chr($a),
    91 => $a || l($s, $p, 1),
    93 => $a && l($s, $p, -1),
    default => 0
  };
}
```

もとの実装例からどのように短くしていったか説明していきます。

### `$memory[$ptr]`の初期化
`isset($memory[$ptr])`というコードが4箇所出てきています。
これらを消すために、switchの前で初期化してやります。

```diff_php
+ $memory[$ptr] ??= 0;
  switch ($source[$pc]) {
  case '>':
    $ptr++;
    break;
  case '<':
    $ptr--;
    break;
  case '+':
-   if (!isset($memory[$ptr])) {
-     $memory[$ptr] = 0;
-   }
    $memory[$ptr]++;
    break;
  case '-':
-   if (!isset($memory[$ptr])) {
-     $memory[$ptr] = 0;
-   }
    $memory[$ptr]--;
    break;
  case '.':
    echo chr($memory[$ptr]);
    break;
  case '[':
-   if (!isset($memory[$ptr]) || $memory[$ptr] === 0) {
+   if ($memory[$ptr] === 0) {
      $depth = 1;
      while ($depth > 0) {
        $pc++;
        if ($source[$pc] === '[') {
          $depth++;
        } elseif ($source[$pc] === ']') {
          $depth--;
        }
      }
    }
    break;
  case ']':
-   if (isset($memory[$ptr]) && $memory[$ptr] !== 0) {
+   if ($memory[$ptr] !== 0) {
      $depth = 1;
      while ($depth > 0) {
        $pc--;
        if ($source[$pc] === ']') {
          $depth++;
        } elseif ($source[$pc] === '[') {
          $depth--;
        }
      }
    }
    break;
  }
```

### 共通部分の関数化
`case '['`と`case ']'`で同じような処理が重複しているので、これをDRYにします。

```php
function loop($source, &$pc, $direction)
{
  $depth = 1;
  while ($depth > 0) {
    $pc += $direction;
    if ($source[$pc] === '[') {
      $depth += $direction;
    } elseif ($source[$pc] === ']') {
      $depth -= $direction;
    }
  }
}

switch ($source[$pc]) {
// 省略
case '[':
  if ($memory[$ptr] === 0) {
    loop($source, $pc, 1);
  }
  break;
case ']':
  if ($memory[$ptr] !== 0) {
    loop($source, $pc, -1);
  }
  break;
}
```

引数の`$direction`の加算・減算でインクリメント・デクリメントを切り替えているのと、第2引数を[リファレンス渡し](https://www.php.net/manual/ja/language.references.pass.php)にすることで戻り値を受け取る必要をなくしているのがポイントです。

### switch→matchへ変更
記述量に関しては[まっちちゃんの勝利](https://fortee.jp/phperkaigi-2024/proposal/948ad912-f6b4-4564-ac7e-1d25ae8d2362)！ということで`match`に変更します。
```php
match ($source[$pc]) {
  '>' => $ptr++,
  '<' => $ptr--,
  '+' => $memory[$ptr]++,
  '-' => $memory[$ptr]--,
  '.' => print chr($memory[$ptr]),
  '[' => $memory[$ptr] || loop($source, $pc, 1),
  ']' => $memory[$ptr] && loop($source, $pc, -1),
  default => 0
}
```

matchの場合、`=>`の右側には式しか書けない、という制限があるため、`switch`版から少し変更を加えています。
- echoは式でないのでprintに変更
- ifは式でないので、`&&`, `||`に変更
  - 0はfalseyなので`=== 0` / `!== 0`を省略

また入力には改行などが含まれるようなので、それらを受け取ったときにエラーにならないよう`default`を追加しています（`=> 0`には特に意味ありません）。

### `$memory[$ptr]`を減らす
同じ配列アクセスが5箇所あるので、これを減らすためにリファレンスを使います。

```php
$a = &$memory[$ptr];
match ($source[$pc]) {
  '>' => $ptr++,
  '<' => $ptr--,
  '+' => $a++,
  '-' => $a--,
  '.' => print chr($a),
  '[' => $a || loop($source, $pc, 1),
  ']' => $a && loop($source, $pc, -1),
  default => 0
}
```

ちなみに、リファレンスのアクセスだとWarningが出ません（私も今回初めて知りました）。
なので最初に書いた`$memory[$ptr] ??= 0`は要らなくなります。

### `ord`の利用
冒頭の提出コードでは、`match`のカッコ内で[`ord`](https://www.php.net/manual/ja/function.ord)を使って、文字をASCIIコードに変換しています。こうすることで、関数呼び出しに5文字かかる代わりに`=>`の左側が1文字ずつ削れて、プラマイ2文字の節約に成功しました。

### ループ条件の変更
実装例の`while`ループの条件`$pc < strlen($source)`を`$source[$pc] ?? 0`に変更します。

### while→forへ変更
while文をfor文へ変更すると、キーワードが2文字短くなる代わりに`;`が2つ増えるので、単に変更するだけだと文字数が減りません。ただし、うまく利用すると全体では文字数がやや削れます。

#### メインのwhileループ
```diff_php
- $memory = [];
- $ptr = 0;
- while ($source[$pc] ?? 0) {
+ for ($memory = [$ptr = 0]; $source[$pc] ?? 0; $pc++) {
    // ...
-   $pc++;
  }
```

for文の`;`を無駄にしないよう、2つ目の条件式以外のところに他からコードを移動させています。
同時に、`$memory`の0番目の要素は0でもいいので、配列の初期化と`$ptr`への代入をまとめています。

また、`$pc`のインクリメントと参照をまとめることもできます。
```diff_php
- for ($memory = [$ptr = 0]; $source[$pc] ?? 0; $pc++) {
+ for ($memory = [$ptr = 0]; $source[++$pc] ?? 0;) {
```
ただ、前置インクリメントでないと上手くいかない関係上、`$pc`の初期値は0ではなく-1にする必要があります。

#### 関数内のwhileループ
```diff_php
  function loop($source, &$pc, $direction)
  {
-   $depth = 1;
-   while ($depth > 0) {
+   for ($depth = 1; $depth;) {
      $pc += $direction;
      if ($source[$pc] === '[') {
        $depth += $direction;
      } elseif ($source[$pc] === ']') {
        $depth -= $direction;
      }
    }
  }
```

### if文を配列アクセスに変更
ここからは`loop`関数の中を変えていきます。

```diff_php
  function loop($source, &$pc, $direction)
  {
    for ($depth = 1; $depth;) {
      $pc += $direction;
-     if ($source[$pc] === '[') {
-       $depth += $direction;
-     } elseif ($source[$pc] === ']') {
-       $depth -= $direction;
-     }
+     $depth += (['[' => $direction, ']' => -$direction][$source[$pc]] ?? 0);
    }
  }
```

### 代入と参照をまとめる
まず、`$pc`の代入 (`+=`) と参照を1つにまとめます。

```diff_php
  function loop($source, &$pc, $direction)
  {
    for ($depth = 1; $depth;) {
-     $pc += $direction;
-     $depth += (['[' => $direction, ']' => -$direction][$source[$pc]] ?? 0);
+     $depth += (['[' => $direction, ']' => -$direction][$source[$pc += $direction]] ?? 0);
    }
  }
```

さらに、`$depth`の代入と参照もまとめられます。
するとfor文の`{}`の中身がなくなりますが、その場合[公式マニュアル](https://www.php.net/manual/ja/control-structures.for.php)の例4のように、末尾はセミコロン1文字にできます。

```diff_php
  function loop($source, &$pc, $direction)
  {
-   for ($depth = 1; $depth;) {
-     $depth += (['[' => $direction, ']' => -$direction][$source[$pc += $direction]] ?? 0);
-   }
+   for ($depth = 1; $depth += (['[' => $direction, ']' => -$direction][$source[$pc += $direction]] ?? 0););
  }
```

### `stream_get_contents`→`fread`に変更
標準入力から読み込むのに`stream_get_contents`を使っていましたが、関数名が長いので`fread`を使います。`fread`は読み込むバイト数を指定しないといけませんが、今回のテストケースでは9999バイトにしておけば十分だったようです。

---
これで冒頭のコードと同じになるはずです。

## その後
PHPerKaigi終了後、[めもりー](https://twitter.com/m3m0r7)さんが私のコードを更に短縮してくださいました。

https://note.com/m3m0r7/n/n1783879bd825

> ```php
> for($s=fread(STDIN,9999),$p=-1,$m=[$t=0];$a=&$m[$t],$s[++$p]??0;)for($d=1,match($o=ord($s[$p])){62=>$t++,60=>$t--,43=>$a++,45=>$a--,46=>print chr($a),default=>0};($o==91&&!$a&&$r=1or$o==93&&$a&&$r=-1)&&$d+=["["=>$r,"]"=>-$r][$s[$p+=$r]]??0;);
> ```

これで242バイトで、当初の私のコードより21バイト短縮されています。
で、まだ削れそうなのでさらに削りました。

```php
for($s=fread(STDIN,9999),$p=-1,$m=[$t=0];$a=&$m[$t],@$s[++$p];)for($d=1,match($o=ord($s[$p])){62=>$t++,60=>$t--,43=>$a++,45=>$a--,46=>print chr($a),default=>0};($a?$o==93&&$r=-1:$o==91&&$r=1)&&$d+=@["["=>$r,"]"=>-$r][$s[$p+=$r]];);
```

これで231バイトです。

やってる間はもうこれ以上削れないだろう……と思っていても、思いの外短縮の余地があるものだなあというところです。

いやまだ減らせるぞ、という方はぜひコメントで教えてください！

---
**03/20 追記**
@rana_kualu さんに頂いたコメントと、プラスアルファでもう少し減らして220バイトになりました。

```php
for($s=0 .fread(STDIN,1e8),$m=[$t=0];$a=&$m[$t],$o=ord(@$s[++$p]);)for($d=1,match($o){60,62=>$t+=$o-61,43,45=>$a+=44-$o,46=>print chr($a),default=>0};$a?$o==93&&$r=-1:$o==91&&$r=1and$d+=@["["=>$r,"]"=>-$r][$s[$p+=$r]];);
```