Excel数式で作るBrainf*ckインタプリタ

:::note warn
以下は訳あって削除済みの過去記事の転載です（published at 2023-03-24 19:57）。
:::

---

# はじめに

Excelなど表計算ソフトウェアでは、数式を用いて他のセルの値を参照したり、値を利用して計算したりできます。`=SUM(A1:A5)` のように入力するアレのことです。

今回はとりわけ特徴的なLET関数とLAMBDA関数を活用して、指定したセルにBrainf\*ckプログラムを入力すると実行結果を表示する数式を作成します。

遊んでみたい方は[こちら](https://docs.google.com/spreadsheets/d/1XFHzKRiytyjLT7nAq8xEDqdVjBUVlPkoSPIeihb3l1Y/edit?usp=sharing)からどうぞ。とりあえず動いたことしか確認していないので、もっといい書き方があるとか、バグを見つけたりしたらこっそり教えてくださいね。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1550728/83eb525b-eaa5-961b-775b-8474a60b061a.png)

https://github.com/u1F992/excel-formula-bf

# LET関数

https://support.microsoft.com/ja-jp/office/let-%E9%96%A2%E6%95%B0-34842dd8-b92b-4d3f-b325-b8b8f9908999

値に名前を付けて、末尾の数式で利用する関数です。次の数式はA1に値が入っていれば`[`～`]`で囲んで表示し、値が入っていなければ`empty`と表示します。

```
=LET(
val,A1,
IF(val="",
  "empty",
  CONCAT(CONCAT("[",val),"]")
)
)
```

JavaScriptならこんなイメージでしょうか。constで表した通り、valは再代入できませんし、LETの外で使用することもできません。

```javascript
(() => {
    const val = A1;
    return (() => {
        if (val === "") {
            return "empty";
        } else {
            return "[" + val + "]";
        }
    })();
})();
```

名前と値のペアは複数並べることができます。

```
=LET(
v_1,1,
v_2,2,
v_3,3,
TEXTJOIN(",",TRUE,v_1,v_2,v_3)
)

> 1,2,3
```

入れ子にすると、見慣れたプログラミング言語っぽくなります。今後はこの記法を使います。

```
=
LET(v_1,1,
LET(v_2,2,
LET(v_3,3,
TEXTJOIN(",",TRUE,v_1,v_2,v_3)
)))

> 1,2,3
```

# LAMBDA関数

https://support.microsoft.com/ja-jp/office/lambda-%E9%96%A2%E6%95%B0-bd212d27-1cd1-4321-a34a-ccbf254b8b67

いろんな言語でおなじみの、匿名関数を作成する関数です。

```
=LAMBDA(x,y,x+y)(1,2)

> 3
```

JavaScriptならこんなイメージです。

```javascript
((x, y) => { return x + y; })(1, 2);
```

LET関数と組み合わせることで名前を付けることができます。

```
=
LET(ADD,LAMBDA(x,y,x+y),
ADD(1,2)
)

> 3
```

```javascript
(() => {
    const add = (x, y) => { return x + y; };
    return add(1, 2);
})();
```

LAMBDAは、ほかの関数に引数として与えられます。次の数式は行×列の多次元配列を作成するMAKEARRAY関数の使用例です。

https://support.microsoft.com/ja-jp/office/makearray-%E9%96%A2%E6%95%B0-b80da5ad-b338-4149-a523-5b221da09097

```
=MAKEARRAY(5,5,LAMBDA(r,c,r*c))

>
1,  2,  3,  4,  5
2,  4,  6,  8,  10
3,  6,  9,  12, 15
4,  8,  12, 16, 20
5,  10, 15, 20, 25
```

また、LAMBDAをLAMBDAの戻り値にすることもできます。`STRFINDER("[")`の戻り値は、「検索対象の文字列を引数にとり、`[`の位置を検索する関数」になります。

```
=
LET(STRFINDER,LAMBDA(search_for,
  LAMBDA(to_search,
    FIND(search_for,to_search)
  )
),
LET(FINDBRACKET,STRFINDER("["),
FINDBRACKET("hoge[]")
))

> 5
```

再帰を組めばループを表現することも可能です。ただし、自身の名前を参照することはできないため、ひと工夫必要になります。再帰時に用いる関数を引数で受け取るように変形して、自分自身を渡します。

```
=
LET(REPEAT,LAMBDA(str,count,
  LET(_,LAMBDA(F,left,out,
    IF(left=0,
      out,
      F(F,left-1,CONCAT(out,str))
    )
  ),
  _(_,count,"")
)),
REPEAT("hoge",2)
)

> hogehoge
```

# Brainf*ckインタプリタの実装

LET関数とLAMBDA関数を使いこなせば、Excelの数式をプログラミング言語とみなすことができます。[話によれば](https://twitter.com/satyanadella/status/1359289655565291520)、LAMBDAを備えたExcelの数式はチューリング完全なんだそうです。

Brainf\*ckインタプリタの数式は以下のようになりました。プログラムをセルB4から、標準入力に流す内容をセルB7から読み込んで、標準出力に書き込まれた内容をセルの値として表示します。

```
=
LET(UPDATEARRAY,LAMBDA(base,row,col,val,
  MAKEARRAY(ROWS(base),COLUMNS(base),LAMBDA(r,c,
    IF(AND(r=row,c=col),
      val,
      INDEX(base,r,c)
    )
  ))
),
LET(UPDATEARRAY_ADD,LAMBDA(base,row,col,val,
  UPDATEARRAY(base,row,col,INDEX(base,row,col)+val)
),
LET(UPDATEARRAY_INCR,LAMBDA(base,row,col,
  UPDATEARRAY_ADD(base,row,col,+1)
),
LET(UPDATEARRAY_DECR,LAMBDA(base,row,col,
  UPDATEARRAY_ADD(base,row,col,-1)
),

LET(CHARAT,LAMBDA(str,pos,
  MID(str,pos,1)
),
LET(CHARAT_HEAD,LAMBDA(str,
  CHARAT(str,1)
),

LET(REMOVE,LAMBDA(str,pos,cnt,
  LEFT(str,pos-1)&RIGHT(str,LEN(str)-(pos+cnt-1))
),
LET(REMOVE_HEAD,LAMBDA(str,cnt,
  REMOVE(str,1,cnt)
),

LET(CORRFINDER,LAMBDA(looking_for,corresponding,forward,
  LET(next,IF(forward,1,-1),

  LAMBDA(src,pos,
    LET(_,LAMBDA(F,pos,depth,
      LET(token,CHARAT(src,pos),

      SWITCH(token,          
        looking_for,
          IF(depth=1,
            pos,
            F(F,pos+next,depth-1)
          ),

        corresponding,
          F(F,pos+next,depth+1),

        F(F,pos+next,depth)
      )
    )),
    _(_,pos+next,1)
  ))
)),
LET(CORRRBRACKET,CORRFINDER("]", "[", TRUE),
LET(CORRLBRACKET,CORRFINDER("[", "]", FALSE),

LAMBDA(src,mem,in,out,
  LET(_,LAMBDA(F,pos,mem,ptr,in,out,
    LET(JUMP,LAMBDA(pos,mem,ptr,in,out,
      F(F,pos,mem,ptr,in,out)
    ),
    LET(JUMP_NEXT,LAMBDA(mem,ptr,in,out,
      JUMP(pos+1,mem,ptr,in,out)
    ),
    LET(JUMP_PASSTHRU,LAMBDA(
      JUMP_NEXT(mem,ptr,in,out)
    ),

    LET(PUTCHAR,LAMBDA(
      out&CHAR(INDEX(mem,ptr,1))
    ),
    LET(GETCHAR,LAMBDA(
      UPDATEARRAY(mem,ptr,1,CODE(CHARAT_HEAD(in)))
    ),

    IF(LEN(src)<pos,
      out,
      
      LET(token,CHARAT(src,pos),

      SWITCH(token,
        ">",
          JUMP_NEXT(mem,ptr+1,in,out),

        "<",
          JUMP_NEXT(mem,ptr-1,in,out),

        "+",
          JUMP_NEXT(UPDATEARRAY_INCR(mem,ptr,1),ptr,in,out),

        "-",
          JUMP_NEXT(UPDATEARRAY_DECR(mem,ptr,1),ptr,in,out),

        ".",
          JUMP_NEXT(mem,ptr,in,PUTCHAR()),

        ",",
          JUMP_NEXT(GETCHAR(),ptr,REMOVE_HEAD(in,1),out),
        
        "[",
          IF(INDEX(mem,ptr,1)=0,
            JUMP(CORRRBRACKET(src,pos),mem,ptr,in,out),
            JUMP_PASSTHRU()
          ),

        "]",
          IF(INDEX(mem,ptr,1)<>0,
            JUMP(CORRLBRACKET(src,pos),mem,ptr,in,out),
            JUMP_PASSTHRU()
          ),
        
        JUMP_PASSTHRU()
      )
    ))
  )))))),
  _(_,1,mem,1,in,out)
))
)))))))))))(B4,MAKEARRAY(64,1,LAMBDA(r,c,0)),B7,"")
```

LET関数で宣言した変数は再代入できないため、コードの実行位置／メモリ／ポインタ／標準入力／標準出力といったすべての状態を再帰のたびに引数で受け渡す形になります。

メモリは配列として用意していますが、その内容を変更することはできません。元の配列と位置と値を指定して新たな配列を作成するUPDATEARRAY関数を別途作成しています。

あとは素直に実行位置をぐりぐり動かしているだけです。

# おわりに

Excelの数式をプログラミング言語のように扱い、Brainf\*ckインタプリタを作成しました。詳しくないのですけど、関数型プログラミングというのでしょうか。とにかく、いつもの慣れたプログラミング言語とは頭の違う部分を使っているような感覚で面白かったです。