計算機科学のクリスマス

【IIJ 2023 TECHアドベントカレンダー 12/10の記事です】

今年も楽しかるべきクリスマスがやってくる. しかしどうも華やいだ気分になれないのは, 連日報道されるイスラエルとパレスチナの紛争のせいである. そもそもこれは, 第2次大戦後, パレスチナ人を追い出してイスラエル国を建国し, さらにイスラエルがパレスチナの土地を侵食し続けた結果だ.
ガザ地区の南, ラファの検問所に集結するパレスチナの人々の姿から, 2000年もの昔, ヨセフが「幼児とその母とを携へエジプトへ逃れ」たのはこの辺りからかと想像する. その時は一家族だけであったが.
堀辰雄の「木の十字架」を読むと, ドビュッシーの晩年の歌曲に「もう家もない子のクリスマス」があるらしい.

クリスマスよ, クリスマスよ, どうぞ彼等のところへは行かないで.
もう決して行かないで. さうして彼等を懲らしめてやつておくれ.

今はイスラエルにもウクライナにもそういう子等が増えているのは痛ましいが, それでも年末にはキリスト教徒以外にもクリスマスは訪れる. そしてこれは一年中で最も神聖な季節と信じられている.

救い主キリストの生誕を祝う季節が近づくと
暁を告げるあの鳥が夜を徹して鳴きつづけ,
そのためにもののけもさまよい歩かぬと言う.
夜は浄められ, 星は人を害する力を失い,
妖精は影をひそめ, 魔女は通力をなくし,
神聖至福の気があふれる季節になると言う.
　　　　　　　　　　　　　　　Hamlet(I,i 小田島訳)

こちらは楽しいクリスマス前夜. こういう詩がある.

Twas the night before Christmas, when all through the house
Not a creature was stirring, not even a mouse;
The stockings were hung by the chimney with care,
In hopes that St. Nicholas soon would be there;

クリスマスの前夜のことだ. 家の中では
ねずみどころか, 何も動かぬ.
靴下を煙突の脇に丁寧に吊り,
サンタクロースが来るのを待つ.

似たような書き出しで, 期待を込めたこの詩はどうだろう.

Twas the night before start-up and all through the net,
    not a packet was moving; no bit nor octet.
The engineers rattled their cards in despair,
    hoping a bad chip would blow with a flare.
The salesmen were nestled all snug in their beds,
    while visions of data nets danced in their heads.
And I with my datascope tracings and dumps
    prepared for some pretty bad bruises and lumps.
When out in the hall there arose such a clatter,
    I sprang from my desk to see what was the matter.

立上げの前夜のことだ. ネットの中では
    1ビット1オクテットどころか, 1パケットも動かぬ.
エンジニアたちは絶望してカードをガタガタさせ
    悪いチップを吹き飛ばそうとする.
セールスマンたちは寝床に心地良く横たわり
    頭の中ではデータネットの夢が踊る.
私はデータスコープのトレースやダンプを持って
    ひどい痛みや腫れに対応しようとしていた.
突然ホールで騒ぎが起き
    何かと思って私は机から飛び上がった.

インターネットが動き出した時のバグ取りの様子だ. これはあのVint Cerfが1985年12月にRFC 968として書いた. (net, octet), (despair, flare) (beds, heads), (dumps, lumps), (clatter, matter)と脚韻を踏むところにも注意. クリスマス前夜もRFCもそれほど難しくはないので, 後は自分で見て欲しい. クリスマス前夜は, 例えば:
https://www.teachervision.com/christmas/twas-the-night-before-christmas-full-text-of-the-classic-poem,
RFCは: https://datatracker.ietf.org/doc/html/rfc968 にある.

私が昨年のAdvent Calendarに書いた, KnuthのThe Art of Computer Programming 第4A巻にChristmas Tree Pattern (次数(order) = 8)という図がある.

= 8のクリスマス木

Knuthがスタンフォード大学で毎年末に行なうクリスマス講義の2002年の話題がこれであったので, こう命名した.
この次数 = 8の図は上下は最上段の10101010から, 最下段の00000000 . . . 11111111まで  = 70行あり, 左右は最下段の左端の00000000から右端の11111111まで + 1 = 9列ある.
まずこの作り方を説明する. 始めに次数 = 1のクリスマス木0と1がある. 創世記風にいうと「元始はじめに神0と1を創造つくりたまへり(In the beginning, God created 0 and 1.)」である.
次数のクリスマス木から次数 + 1のクリスマス木を作るには, 次数の各々の行の二進数(文字列)の並び:

　　σ₁  σ₂ . . . σ_s

を

　　 σ₂0 . . . σ_s0
σ₁0 σ₁1 . . . σ_s−11 σ_s1

の上下2行にする. 但し = 1なら上の行は作らない. つまりある行の二進数のそれぞれの後に0を付けた上の行と, 1を付けた下の行を作り, 上の行の左端のσ₁0 を下の行の左端に移動する. = 1, 2でやってみよう.

0 ≤ ≤ ⌊/2⌋について, 列から始まる行の1の数は, , +1, . . . , −なので, 1の数は0を追加した行はそのまま, 1を追加した行は1ずつ増え, 左端の1が1個増えたその左に, 1個少ないのを上の行から貰って来るわけだ.
こうして次数を増やすと, クリスマス木は指数関数的に増大し, 「神彼等を祝し神彼等に言たまひけるは生うめよ繁殖ふえよ地に滿盈みてよ（創世記1-28)」状態になった.

= 1, 2, . . . , 6のクリスマス木

= 8のクリスマス木の図で, 各列にある二進数は左から順に, 1,8,28,56,70,56,28,8,1個あり, パスカル三角形の8段目だということが判明する. 列目には1がちょうど個, 0がちょうど(8 − )個あるからそうなり, そういう行は行ある. 従って, + + · · · +  = 2⁸ = 256の二進数が揃う.
+ + · · · + の和が2になるのは, ( + )の展開が ⁻で, そのとを1と思うと理解出来る.

また各行の二進数を左から右に見ていくと, どれもすぐ左の二進数のいずれかの0を1に変えたものである.
こうして作った次のクリスマス木は,

a 0から2 − 1までの二進数をすべて含む.
b 0 ≤ ≤ について, 左から列目はi個の1と( − )個の0を含む.
c 各行の隣同士のハミング距離は1である.
d 各行の右端の二進数は下へ向って順次増える.
e 偶数次数2のクリスマス木で, 行に1個だけの二進数は, 釣り合うかっこ対が出来る.
f 各行の隣合う3個の二進数の排他的論理和の二進数はその行より上の行にある.

これらの性質のうち, aからdまでは作り方からほぼ自明である. eとfは難しい. 10101100は, 1を(, 0を)とすると, ()()(())の釣り合うかっこ対が出来る. 個の(と, 個の)で出来る釣り合うかっこ対の数はカタラン数といい, = (0, 1, 2, 3, 4, 5, . . .)について, = (0, 1, 2, 5, 14, 42, . . .)である.

ある年末に = 6のクリスマス木を, 0と1の代わりに易の陽爻ようこう(⚊)と陰爻いんこう(⚋)を縦にしたもので描き, Knuthに送ったところ, 彼はクリスマス講義でそれを見せ, 「和田からの贈り物」と紹介したそうだ.

話は変って, = 1+2+· · ·+とする時, 1³ +2³ +· · ·+³ = ²は常識だ. 例えば = 3なら1³ +2³ +3³ = 1+8+27 = 36 = 6² = (1 + 2 + 3)²だ. これを幾何学的に証明しようとした人がいる. つまり1 × 1の正方形1個, 2 × 2の正方形2個, . . .,
× の正方形個で, × の正方形をぴったり埋めることが出来るかという問題である.
当然の小さい方から調べる. 1 × 1の正方形1個は1 × 1の正方形をぴったり埋めるか. ブラボー! 出来る. しかしこれは糠喜び, = 2でもう破綻する. でも, > 2に出来るものがあるかもしれない.
このテストは, 1 × 1のピース1個, 2 × 2のピース2個, . . ., × のピース個が × の箱に入るかという, ペントミノパズルの要領でプログラムを書く. 冗長な解を出力しないよう, 回転, 反転の除去がプログラムに要請される.
これを実験すると, = 8には解があった. それが下の図の左である. この図には正方形のサイズが, 1を除いて記入してある.

山うずらパズル(左)と「正当な」山うずらパズル(右)

= 12の時にも解があったので, このパズルを考えた人は, 「クリスマスの12日(The twelve days of Christmas)」という歌詞の第1日の連想から, 「山うずらパズル(partridge puzzle)」と命名した.
「クリスマスの12日」はこういう詩だ. クリスマスキャロルなどで歌われる. 数え歌というと少し違うかもしれない.

On the first day of Christmas my true love sent to me,
A partridge in a pear tree.

On the second day of Christmas my true love sent to me,
Two turtle doves,
And a partridge in a pear tree.

On the third day of Christmas my true love sent to me,
Three French hens,
Two turtle doves,
And a partridge in a pear tree.

4日目以降も贈り物は続々増え, 12日目は

On the twelfth day of Christmas, my true love sent to me,
Twelve drummers drumming,
Eleven pipers piping,
Ten lords a-leaping,
Nine ladies dancing,
Eight maids a-milking,
Seven swans a-swimming,
Six geese a-laying,
Five golden rings,
Four calling birds,
Three French hens,
Two turtle doves,
And a partridge in a pear tree.

贈り物は日本語では

12人の太鼓を叩く鼓手  11人の笛を吹く笛吹き
10人の飛び跳ねる貴族  9人の踊る貴婦人
8人の乳搾りの下女     7羽の泳ぐ白鳥
6羽の卵を生む鵞鳥     5個の金の指輪
4羽の鳴く鳥           3羽のフランス雌鳥
2羽の雉鳩             そして梨の木に止る1羽の山うずら

一体贈り物の総数はいくつか. 鳥や人や指輪があるが, ここでは「個」で統一する. 1日目に初めて1個貰ったものは, 12日間貰う; 2日目に初めて2個貰ったのもは, 11日間貰う; 1 ≤ ≤ 12について, 日目に初めて個貰ったものは, (13 − )日間貰う.
従って, 贈り物の総数は

そうして見ると3乗の和の証明の「山うずらパズル」は違うのではないかということになる. 正当な(authentic)パズルの日目までの贈り物は, 1 × 1の正方形がn個, 2 × 2の正方形が( − 1)個, … , 1 ≤ ≤ について, × の正方形が( + 1 − )個, … , × の正方形が1個. 従って, 日までの面積の和は

この値は = (1, 2, 3, 4, 5, 6, . . .)について(1, 6, 20, 50, 105, 196, . . .) となり, = 6で初めて平方数になる. それが上の右の図である. 小さい正方形が多いので, 箱詰めは簡単らしい.
この繰返しパターンを見ると, プログラムを書いてみたくなるのは人情だ. SNOBOL, TECO, Pythonで書いたプログラムは見たことがある. C言語による超難解なプログラムxmas.cとその詳しい解説はhttps://udel.edu/~mm/xmas/にある. 私はまだ理解しようとは思わない.
これらとは違った趣向だが, この詩自体をプログラムにする話が, Algol Bulletin 42にある. Bristol大学のJohn P. Bakerは, 単語を演算子として定義し, その後の詩が1から12までの階乗を計算するプログラムをAlgol 68で書いた.
(https://archive.computerhistory.org/resources/text/algol/algol bulletin/A42/P46.HTM. 「Algol Bulletin」で検索, そのVol.42のpp.50-52にある. bit 1982年3月号(Vol.14,No.4), pp.578-587に転載されている.)
さて, 例えば私がPythonでちらっと書いたプログラムがこれだ. (andの位置が多少違うが… orz)

nth=["first","second","third","fourth","fifth","sixth",
     "seventh","eighth","nineth","tenth","eleventh","twelfth"]
gifts=["Twelve drummers drumming,","Eleven pipers piping,",
       "Ten lords a-leaping,","Nine ladies dancing,","Eight maids a-milking,",
       "Seven swans a-swimming,","Six geese a-laying,","Five gold rings,",
       "Four calling birds,","Three French hens,","Two turtle doves, and",
       "A partridge in a pear tree.\n"]
for i in range(0,12):
    print("On the "+nth[i]+" day of Christmas, my true love sent to me,")
    for j in range(11-i,12):
          print(gifts[j])

ついでにもう1つ. で書いたのはこんな具合だ.

\documentclass{jsarticle}
\parindent=0mm
\begin{document}
\def\xmas#1{On the #1 day of Christmas, my true love sent to me,\\}
\def\partridge{partridge in a pear tree.\\}
\def\doves{Two turtle doves,\\ And a \partridge}
\def\hens{Three French hens,\\ \doves}
\def\birds{Four calling birds,\\ \hens}
\def\rings{Five golden rings,\\ \birds}
\def\geese{Six geese a-laying,\\ \rings}
\def\swans{Seven swans a-swimming,\\ \geese}
\def\maids{Eight maids milking,\\ \swans}
\def\ladies{Nine ladies dancing,\\ \maids}
\def\lords{Ten lords a-leaping,\\ \ladies}
\def\pipers{Eleven pipers piping,\\ \lords}
\def\drummers{Twelve drummers drumming,\\ \pipers}
\xmas{first}A \partridge\\ \xmas{second}\doves\\
\xmas{third}\hens\\        \xmas{fourth}\birds\\
\xmas{fifth}\rings\\       \xmas{sixth}\geese\\
\xmas{seventh}\swans\\     \xmas{eighth}\maids\\
\xmas{nineth}\ladies\\     \xmas{tenth}\lords\\
\xmas{eleventh}\pipers\\   \xmas{twelfth}\drummers\\
\end{document}

出力を示すまでもないであろう.

IEEE Spectrumに, プログラミング言語Pythonが出来るまでの話題があった. How Python Swallowed the World(https://spectrum.ieee.org/python)で, 終りの方にプログラミング言語の系譜, 「BCPL begat B. And B begat C.」つまり「BCPLがBを生み, BがCを生んだ.」という文がある. (その前にCPL begat BCPLがあるのだが, それはさて置き,) このbegatはマタイによる福音書1-1のイエス・キリストの系図で, 「アブラハム, イサクを生み, イサク, ヤコブを生み, ヤコブ, ユダとその兄弟らとを生み, …」の転用である. 英語では, 「Abraham begat Isaac; and Isaac begat Jacob; and Jacob begat Judas and his brethren; …」だ(begatはbegetの古い過去形で, begetは父親について子を儲けるの意). その少し先まで読むと「イエスはヘロデ王の時, ユダヤの(現在はヨルダン川西岸のパレスチナ自治区にある)ベツレヘムで生れ給ひしが,…(マタイ伝2-1)」とあり, これが最初のクリスマスである.

Hallelujah, Hallelujah, Merry Christmas and Happy Hacking!