これはちゅらデータ Advent Calender 2021 19日目の記事です。

時を遡ること5年前⸺
平成28年8月、一斉を風靡した歴史的動画が発表されたことをお忘れではないだろうか。

＿人人人人人人人人人人人人人人人人＿
＞　ペンパイナッポーアッポーペン　＜
￣Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^￣

ペンとアッポーとパイナッポーという馴染み深いアイテムを巧みな手付きで融合し、ペンパイナッポーアッポーペンという聞いたこともない物体を錬成していく。
わずか1分ほどの動画だったが、その様子は見る者全てを驚かし、瞬く間に世界中を熱狂の渦へと巻き込んだ。

PPAPとは一体何なのか？　未だ謎多きPPAPについて分析を試みるものもいる。
例えば Wikipedia では、動画中で唱えられている呪文に対して品詞分析を行い、単語数や語彙数の統計を取ったものや、呪文のテンポや音程に関する分析結果が公表されている。他にも非常に有意義な情報があるため、ぜひ一読されたい。

あれから5年の節目を迎え、元号も令和に変わってしまった今こそ、もう一度あの動画を振り返って分析してみよう。

ピコ太郎は一体何をしているのか？

ピコ太郎はあの動画の中で一体何をしているのだろうか？
古坂大魔王を名乗る人物がピコ太郎をプロデュースしている¹ことからも、何らかの知られざる魔術が使われていることは間違いないだろう。
動画と呪文を見ながら、ピコ太郎が物体に対して行っている操作を追っていこう。

I have a pen
I have an apple
Uh!
Apple Pen

彼はおもむろにPenとAppleを取り出し、Uh!²という掛け声によってそれらは一瞬でApple Penへと変貌した。

I have a pen
I have a pineapple
Uh!
Pineapple Pen

次に彼が取り出したのはPenとPineappleだ。Uh!という掛け声によってそれらはPineapple Penへと変貌した。

規則性が見えてきただろうか。
彼は、1番目に取り出したものと2番目に取り出したものを、逆さに結合しているのだ。
ピコ太郎が「Uh!」という掛け声とともに実行しているこの結合のことを「PPAP結合」と呼ぶことにしよう。
図にするとこんな感じだ。

これを踏まえて最後の操作を見てみよう。

Apple Pen
Pineapple Pen
Uh!
Pen Pineapple Apple Pen

これまでにPPAP結合して生まれた2つの生成物を、さらに結合している。
ここでも先ほどと同じく、1番目と2番目を逆さに結合しているのだろうか？

実はそうではない。よく見ると分かるが、Pineapple Penの部分が結合後はPen Pineappleになっている。
2番目の要素Pineapple Penの中身を逆さにした上で、1番目の要素と2番目の要素を逆さに結合しているのだ。
ここで思い出してほしい。「逆さにする」というのは先ほどの操作でも行っていた。ならば、2番目の要素に対して行っている操作は、1番目の操作で行っていたことと同じではないだろうか？
図にするとこんな感じだ。

PPAP結合の操作の中で、さらに別のPPAP結合が行われている格好になっている。
このように、ある操作の中にその操作自身が含まれていることを再帰という。
ピコ太郎が動画の中で行っているPPAP結合は、逆さにしながら再帰的に結合する操作として説明ができそうだ。

PPAP結合を定義する

改めてPPAP結合というものを定義してみよう。
PPAP結合は、2つの要素について、次のような手続きで再帰的に結合する操作である。

2番目の要素が…
- …2つの要素からなるペアである場合、2番目の要素内の各要素についてPPAP結合を行う。
- …1つの要素である場合、そのままにしておく。
2番目の要素の後に1番目の要素を結合したペアを出力する。

こうして定義されるPPAP結合を arg1 arg2 uh という形式で書くことにしよう。
引数 arg1 arg2 の後にそれらを結合する演算子 uh を書くこの記法は、逆ポーランド記法と呼ばれている。
つまり、ピコ太郎は逆ポーランド記法の呪文を唱えているということになる。

ピコ太郎の動画の中で行われているPPAP結合は、次の式で表すことができる。

Pen Apple uh = Apple Pen
Pen Pineapple uh = Pineapple Pen
(Apple Pen) (Pineapple Pen) uh = Pen Pineapple Apple Pen

ちなみに入れ子構造で1行にまとめるとこうなる。

(Pen Apple uh) (Pen Pineapple uh) uh = Pen Pineapple Apple Pen

PPAP結合を実装する

環境

PPAP結合の手続きを明確に定義することができたので、今度はPPAP結合を実装してみよう。

先に書いたように、PPAP結合には魔術が使われている。ということは、その実装も魔術師に倣うべきだろう。
魔術師本の異名で知られる高名な教科書に「計算機プログラムの構造と解釈」がある（日本語版）。初版は昭和60年発行という古文書である。

いかにも禍々しい表紙だ。この教科書ならばPPAP結合も実現できそうな気がしてくる。

この教科書の中ではSchemeというLISPの一種が使われているため、それに倣ってここではPPAP結合をSchemeで実装してみることにしよう。
Schemeの実行環境は Racket のようなソフトウェアをインストールして用意しても構わないが、UC Berkeleyの 61A Code などブラウザ上から手軽に触れるSchemeインタプリタがあるので、そういうのもおすすめしたい。

ということでまず61A Codeを開き、[Create new file]しよう。

深淵まで覗けそうな漆黒の画面、魔術を実装するにはまさにうってつけだろう。
聡明な読者諸兄なら説明はいらないと思うが、ここに呪文（コード）を書いてから右上にある緑の▶️ボタンを押すと、書かれているものがすべて式として評価され、結果が下に表示されるようになっている。

実装

PPAP結合で最も重要なこと、それは何と言っても2つのものを結合することだろう。そして驚くべきことに、ほとんどのLISPには cons という2つのものを結合するための関数が存在する。これはまさにLISPがPPAP結合を実装するために生まれてきた言語であることを示唆していると言って差し支えない。

手始めにPenとAppleをcons関数に与えてみよう。

(cons "Pen" "Apple")
===
Output:
uh
("Pen" . "Apple")

PenとAppleが結合された！

しかしまだ入力した通りの順番でしか結合できていない。
今度は、2つの文字列 a b を受け取って逆順に結合して返す関数 (uh a b) を定義してみよう。
defineという関数に「関数の形」と「返り値の式」を与えることで新しい関数を定義することができる。

(define (uh a b) (cons b a))
(uh "Pen" "Apple")
===
Output:
uh
("Apple" . "Pen")

上出来だ！　ペンとアッポーからアッポーペンを錬成することができたではないか。
逆ポーランド記法になっていないことにさえ目をつぶれば、PPAP結合はもうほぼ完成したと言っていい。

ちなみにパイナポーペンも作れるかどうかを確かめておこう。

(define (uh a b) (cons b a))
(uh "Pen" "Apple")
(uh "Pen" "Pineapple")
===
Output:
uh
("Apple" . "Pen")
("Pineapple" . "Pen")

パイナポーペンも作ることができた！！いいぞ、その調子だ！！！

Apple PenとPineapple Penを結合すれば、ついにPen Pineapple Apple Penの完成……

(define (uh a b) (cons b a))
(uh "Pen" "Apple")
(uh "Pen" "Pineapple")
(uh (uh "Pen" "Apple") (uh "Pen" "Pineapple"))
===
Output:
uh
("Apple" . "Pen")
("Pineapple" . "Pen")
(("Pineapple" . "Pen") "Apple" . "Pen")

おや？？？？

どうやら「アッポーペン」と「パイナポーペン」を受け取って実行される最後の結合で、「パイナポーペン」を反転しなければいけないところが実装できていないようだ。

ここで (uh a b) に改変を加えよう。「2番目の引数が結合済みのペアだったら、その中身を取り出して逆順に結合し直す」という処理を加えるのだ。
b が結合済みのペアかどうかを判断するには (pair? b) という関数を利用でき、条件分岐には (if 条件式 Trueのときの式 Falseのときの式) という関数を利用できる。
結合済みのペア b の中身を取り出すための関数は2つあり、1番目の要素を取り出す関数が (car b) 、2番目の要素を取り出す関数が (cdr b) である。

いきなりややこしくなってきて恐縮だが、乗りかかった舟なので最後までお付き合い願いたい。サービスでインデントしてあげるから。

(define (uh a b)
    (cons
        (if (pair? b)
            (cons (cdr b) (car b)) ; bがペアのとき
            b) ; bがペアではなく単体のとき
        a))

b がペアのとき、 b の中身を逆順で結合しているところがおかわりいただけるだろうか。
親切心でインデントしてみたが、もちろん1行にまとめて書いてしまってもいい。1行にまとめて実行してみよう。

(define (uh a b) (cons (if (pair? b) (cons (cdr b) (car b)) b) a))
(uh "Pen" "Apple")
(uh "Pen" "Pineapple")
(uh (uh "Pen" "Apple") (uh "Pen" "Pineapple"))
===
Output:
uh
("Apple" . "Pen")
("Pineapple" . "Pen")
(("Pen" . "Pineapple") "Apple" . "Pen")

やった！！！ついにやったぞ！！！PPAP結合成功だ！！！！！

とはいえ、ドットやかっこが気持ち悪い感じなので、もうちょっときれいに表示できるようにしたい。
ググって出てきた秘伝のソースを入れた特製おまじない関数 say を追加する。

(define (say x) (if (pair? x) (append (say (car x)) (say (cdr x))) (list x))) ; おまじない
(define (uh a b) (cons (if (pair? b) (cons (cdr b) (car b)) b) a))
(say (uh "Pen" "Apple"))
(say (uh "Pen" "Pineapple"))
(say (uh (uh "Pen" "Apple") (uh "Pen" "Pineapple")))
===
Output:
say
uh
("Apple" "Pen")
("Pineapple" "Pen")
("Pen" "Pineapple" "Apple" "Pen")

きれいに表示されるようになった。

楽しいので他の文具や果物でもやってみよう。

(define (say x) (if (pair? x) (append (say (car x)) (say (cdr x))) (list x)))
(define (uh a b) (cons (if (pair? b) (cons (cdr b) (car b)) b) a))
(say (uh "Brush" "Grape"))
(say (uh "Brush" "Grapefruit"))
(say (uh (uh "Brush" "Grape") (uh "Brush" "Grapefruit")))
===
Output:
say
uh
("Grape" "Brush")
("Grapefruit" "Brush")
("Brush" "Grapefruit" "Grape" "Brush")

筆とブドウとグレープフルーツから「グレープブラッシュ」「グレープフルーツブラッシュ」「ブラッシュグレープフルーツグレープブラッシュ」という未知のアイテムを錬成することができた。

さて、ここで満足してお家に帰っても構わないのだが、せっかくなので先ほど書いた「PPAP結合の定義」にちゃんと従うことにしよう。こう定義したことを覚えているだろうか。

2番目の要素が…
- …2つの要素からなるペアである場合、2番目の要素内の各要素についてPPAP結合を行う。
- …1つの要素である場合、そのままにしておく。
2番目の要素の後に1番目の要素を結合したペアを出力する。

そうだ、PPAP結合を再帰を用いて定義したのだった。
太字の部分だけ書き換えればよいので、幸いにも加える変更は最小限で済みそうだ。

(define (uh a b)
    (cons
        (if (pair? b)
            (uh (car b) (cdr b)) ; bがペアのとき
            b) ; bがペアではなく単体のとき
        a))

uh の定義の中で uh を呼び出している。これぞ再帰である。
試しにこれで実行してみよう。

(define (say x) (if (pair? x) (append (say (car x)) (say (cdr x))) (list x)))
(define (uh a b) (cons (if (pair? b) (uh (car b) (cdr b)) b) a))
(say (uh "Pen" "Apple"))
(say (uh "Pen" "Pineapple"))
(say (uh (uh "Pen" "Apple") (uh "Pen" "Pineapple")))
===
Output:
say
uh
("Apple" "Pen")
("Pineapple" "Pen")
("Pen" "Pineapple" "Apple" "Pen")

一見するとさっきと同じ挙動だ。しかし再帰を用いて定義したことで、2回にとどまらず3回以上、理論上何重にもPPAP結合が可能になっているはずなのだ³。

つまり……どういうことだ？

「ペンパイナッポーアッポーペン」にさらに「ブラッシュグレープフルーツグレープブラッシュ」をPPAP結合できるってことなんだよッ！

な‥‥なんだって⸻!!

(define (say x) (if (pair? x) (append (say (car x)) (say (cdr x))) (list x)))
(define (uh a b) (cons (if (pair? b) (uh (car b) (cdr b)) b) a))
(say (uh (uh "Pen" "Apple") (uh "Pen" "Pineapple")))
(say (uh (uh "Brush" "Grape") (uh "Brush" "Grapefruit")))
(say (uh (uh (uh "Pen" "Apple") (uh "Pen" "Pineapple")) (uh (uh "Brush" "Grape") (uh "Brush" "Grapefruit"))))
===
Output:
say
uh
("Pen" "Pineapple" "Apple" "Pen")
("Brush" "Grapefruit" "Grape" "Brush")
("Brush" "Grape" "Brush" "Grapefruit" "Pen" "Pineapple" "Apple" "Pen")

＿人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人人＿
＞　ブラッシュグレープブラッシュグレープフルーツペンパイナッポーアッポーペン　＜
￣Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^￣

　
　　　　　　┼ヽ　-|r‐､.　ﾚ　|
　　　　　ｄ⌒)　./|　_ﾉ　 __ﾉ
　　　　――――――――――――
　　　　制作・著作　~~ちゅらデータ~~

最近仕事でSQLを触り始めたとき、非手続き型な発想が必要といえばLISPを思い出したりしていたので、この記事を書きました。

https://twitter.com/kosaka_daimaou/status/781341080419569664 ↩
Uum! など諸説あります ↩
何も考えずただそれっぽく書いているだけで、別に理由や根拠があるわけではない ↩