Excelのチューリング完全性を検証するためにPietインタプリタを実装しようとして挫折するまでの軌跡
はじめに
最近,Excelがチューリング完全になったという公式のお達しがあった.
Excel formulas, the world’s most popular programming language, is now Turing-complete. Go check it out! https://t.co/qkw3Bmt1gp
— Satya Nadella (@satyanadella) 2021年2月9日
チューリング完全になったということは,レイトレーシングや科学技術計算,言語処理系まで実装できるはずである.本記事では,Excelのチューリング完全性を悪用利用してそこそこ大きめのコード,具体的にはPiet処理系を実装しようとして挫折した流れを記録しようと思う.
Excelのチューリング完全性を支えるLAMBDAについて
詳しくは公式の説明を参照してほしい.簡単に言うと,
LAMBDA(n, n + 1)
のようにLAMBDA(引数1, 引数2, … , 引数n, 式)
の形でlambda抽象を導入できる.今回調べた限り,LAMBDAは次の性質を持つ.
- lambda抽象の状態でセルに配置できない(#CALC!エラーになる).
- lambda抽象自体はオブジェクトとして引き回せる.
- 要は
=LAMBDA(n, n(2))(LAMBDA(k, k+1))
のような記述が許容される.
- 要は
- なぜか計算によっては遅延評価される.
=LAMBDA(n, 3)(1/0)
はエラーにならずに3
と評価された.
Piet処理系を実装しようとして挫折した流れ
挫折した状態のコードは下記にある.
ここでは,これができるに至った経緯を示す.
対象の選定
今回,Excelのチューリング完全性を利用するにあたり,まずはExcelの性質をできる限り利用していこうと考えた.Excelの性質で特筆すべきなのはやはり二次元のデータ構造をナチュラルに扱えることであろう.つまり,実装するものもその性質があることが望ましい.そう,Piet処理系ならそれを満たせる.
Pietとは
Pietはプログラムが抽象画にみえるプログラミング言語である(公式を翻訳).画像上にあるプログラムポインタが,隣り合うふたつの画素の色差を元に計算を実行する.有名なのはこのHelloWorldだろう(DM's Esoteric Programming Languages - Piet Samples).
具体的な計算方法は公式を参照してほしい.ここでは,Pietが次の要素で構成されていることがわかっていればよい.
- プログラム
- 20色で構成された画像.上下左右につながった同色の画素はColour Blocksとよばれる一つの塊として扱われる.
- Program Pointer
- プログラムの実行位置.
- Direction PointerとCodel Chooser
- Program Pointerが次にどの方向へ移動するか.当然,計算中に書き換わる.
- 標準入力
- 数値,もしくは文字を読み取る対象.
- 標準出力
- 数値,もしくは文字を書き出す対象.
- スタック
- 計算の途中結果を書き出せる唯一の対象.
Pietを構成する各要素のExcel上での表現
プログラム
実はここが一番厄介.というのも,作る前からColour Blocks(と隣接)をExcelで直接計算するのは困難だと考えていた.そこで,画像を前処理して「自身が所属するColour Blocksへの参照」と「Colour Blocksの各情報」に分離することを考えた.具体的には,下記の画像のようにした.
上にある画像が「自身が所属するColour Blocksへの参照」である.各Colour Blocksの情報が載っているセルへの参照が文字列で記載されている.
下の表が「Colour Blocksの各情報」である.Colour Blocksの色,Direction PointerとCodel Chooserの値に対応した次のとび先(正確にはその計算に必要なセル参照を示す文字列),Colour Blocksの面積(命令によってこれを参照する場合がある)を事前に計算してある.ここにある情報を利用して,上にある画像に条件付き書式を設定して色付けしている.
Program Pointer
画像のどの位置にあればいいかが分かればいいので,セルへの参照で問題ない.
Direction PointerとCodel Chooser
取る値が決まっているので,とりあえず数値型とした.
標準入力
「標準入力として扱う行の先頭のセル参照」と「読み取るべき相対位置」で実現することにした.事前に文字と数値のパースが済んだ状態にできるのでうれしい.
標準出力
本当は標準入力と対になるように配列にしたかったが,あまりにも組み込み関数が足りないので文字列で妥協した.
スタック
Excelにまともなデータ構造を期待することはできない.しかし,配列で実装しようにも組み込み関数が足りないし,そもそも計算中に破壊的更新はできない.ここで役立つのがLAMBDAである.みんな学部のころに習ったであろうcons, car, cdrのlambdaによる表現がそのまま使えるのである.つまり,スタックの実装は下記で問題ない.
cons = LAMBDA(x,y, LAMBDA(m, m(x, y))) car = LAMBDA(z, z(LAMBDA(p,q, p))) cdr = LAMBDA(z, z(LAMBDA(p,q, q)))
PietインタプリタのLAMBDAによる構成
ここまで出来上がれば,インタプリタの構成は簡単である.メインループは下記の構成でよい.
mainloop = LAMBDA(pp,dp,cc,err,in,inp,out,stack, if(err >= 8, out, LET( ch, INDIRECT(pp), cl, OFFSET(INDIRECT(pp), 0, 1), nh, INDIRECT(OFFSET(INDIRECT(OFFSET(INDIRECT(pp), 0, 2 + dp * 2 + cc)), dy(dp), dx(dp))), nl, OFFSET(INDIRECT(OFFSET(INDIRECT(OFFSET(INDIRECT(pp), 0, 2 + dp * 2 + cc)), dy(dp), dx(dp))), 0, 1), IF(nh = -1, error, IF(OR(ch = 6, nh = 6), nop, switch(10 * hdiff(ch, nh) + ldiff(cl, nl), 1, push, 2, pop, 10, add, 11, subtract, 12, multiply, 20, divide, 21, modulo, 22, notpiet, 30, greater, 31, pointer, 32, switchpiet, 40, duplicate, 41, roll, 42, inn, 50, inc, 51, outn, 52, outc )))(pp,OFFSET(INDIRECT(OFFSET(INDIRECT(pp), 0, 2 + dp * 2 + cc)), dy(dp), dx(dp)),dp,cc,err,in,inp,out,stack) ) ))
要はProgram Pointerから実行すべき命令(error, nop, push, add, … , outc)を選択するだけである.各命令は次に実行すべき形のmainloopを呼び出す.例えば,足し算(add)は下記のようになる.
add = LAMBDA(pp,npp,dp,cc,err,in,inp,out,stack, IF(OR(car(stack) = "!!!error!!!", car(cdr(stack)) = "!!!error!!!"), mainloop(npp, dp, cc, 0, in, inp, out, stack), mainloop(npp, dp, cc, 0, in, inp, out, cons(car(stack) + car(cdr(stack)), cdr(cdr(stack)))) ) )
あとは,mainloopを適切な初期値で呼び出せば動くはずである.
ことの顛末
とりあえず,一番面倒なroll以外が実装できたところで動作確認してみた.結果,#NUM!エラーが返ってきた. Excelになぜかついているデバッガも雑にしか情報を返してこないので役に立たない. LETで適当に変数導入しているのが悪いのかと思い書き換えるも効果なし(正確には,ちょっと計算が進んでいたが最後までたどり着かない).
悶々として1日過ごしてMS公式ページを見ると,下記の注釈があることに気が付いた.
If you call a LAMBDA function from within itself and the call is circular, Excel returns a #NUM! error.
MSは停止性問題を肯定的に解決したどうやら関数呼び出しのネストが深すぎると#NUM!エラーにするらしい.ほとんど末尾呼び出しなんだから最適化してくれてもいいだろうとは思ったが,そうもいかないらしい.つまり,今回の実装方法ではリソースが足りないのでHello Worldすら実行できなかったのである.
私はここで諦めた.
まとめ
Excelは確かにチューリング完全になったかもしれませんが,現実の計算機では制限が強いので大きな計算はできません.いかがでしたか?
TeX言語でレイトレーシングを実装する話
この記事はTeX & LaTeX Advent Calendar 2019の14日目の記事です。 13日目はmattskalaさんでした。15日目はaminophenさんです。
TL; DR
TeX言語を使って,こんな画像を生成する話.
はじめに
周知のとおり,TeX言語はチューリング完全なプログラミング言語である.すなわち,世界にある任意のプログラムはTeX言語で記述可能である.あの文法と評価規則からは直観的ではないが,CGのレンダリングも科学技術計算もその気になればTeX言語で記述できる.
今回は,久しぶりのTeX芸人活動ということで,TeX言語でレイトレーシングしてみた.
レイトレーシングとは
レイトレーシングとは,画素ごとにカメラに入ってくる光線を逆方向に追跡してCGのレンダリングをする技法である.光線の追跡では,経路上の物体に対する反射・屈折を考慮する.本記事では,その詳細は省略する.
レイトレーシングのプログラムは比較的簡単*1である.下記の機能が実現しやすいプログラミング言語なら,その実装はそこまで難しくないと思っている.
- ラスタ画像の出力
- データ構造
- 浮動小数点数
これらの機能をTeX言語が有しているか検証してみよう,1に関しては過去の記事で実現可能であることを示した.2については,TeXほどアドホックにデータ構造を作成しやすい言語はないと思っている*2.3については,LaTeX3チームによりxfp.styが提供されている.なぜかすべて揃っていた.
xfp.styとは
xfp.styはThe LaTeX Teamが作成している浮動小数点数およびそれに対する演算の実装である.中身は,LaTeX3用のプログラミング言語であるexpl3のラッパーになっている.当然.expl3自体はTeX言語で実装されている.
xfp.styを導入すると,\fpeval{式}
の形で浮動小数点数演算ができる.四則演算はもちろん,なぜか乱数やベクトルの加算・減算とスカラ倍がサポートされている.The LaTeX TeamはこのTeX芸を見抜いていた.
できあがったもの
実際に作ったものがこちら.
https://github.com/hak7a3/raytracing-tex
読者が検証しやすいよう,最初に挙げた画像よりも解像度を落としている.というのも,あの画像は約2日ほど計算機を占有して描画した結果なので,手元で実行するにはあまりにも重い.といっても,公開版も数時間はかかる.
なお,xfp.styがエラーを出して処理が停止してしまう場合がある.おそらくxfp.styの不具合なのだが,乱数次第で回避できるので,検証する際は数回チャレンジしてほしい.
また,画像出力の関係上400x400だと計算終了後にTeX処理系が悲鳴を上げた.
☡ TeX言語的な話
ここから先は,TeX芸人らしくTeX言語実装のテクニックに言及する.
マクロ定義よりトークンリストレジスタが高速だった話
The TeXbookには,マクロ定義を上書きしていくよりもトークンリストレジスタでそれを実施したほうが高速であると記されている.今回のプログラム,初期は計算結果をマクロで貯めていったのだが,途中で速度が気になりトークンリストレジスタに変更した.体感でかなり早くなったので,TeX芸人は少なくともThe TeXbook Appendix Dは読むべきだと思う.
\loopすら使えなかった話
LaTeXには\loop ... \repeat
で繰り返しを記述できる.通常のTeX言語プログラミングでは問題にならないのだが,今回のプログラムでは,その内部構造に起因してTeXのmain memoryを食いつぶした.ループ本体部分をマクロ定義していることが悪い可能性を鑑み,自前でCPS変換したところ処理が通った.詳しい検証はしていないが,main memory不足に悩まされたら思い出してほしい.
まとめ
TeX言語はチューリング完全なので,任意のプログラムを記述できる. その一芸として,レイトレーシングを実装した.
Merry TeX'mas(ちょっと粗すぎた……).
PDFの注釈機能で遊ぶ
この記事はTeX & LaTeX Advent Calendar 2017の9日目の記事です. 8日目はmunepiさんでした.10日目はaminophenさんです.
はじめに
PDFには,注釈という文書に様々な情報を付加するための機能がある.今回は,PDFTeXから注釈機能を叩くことにより,その面白さの一端を見てみようと思う.
注釈とは
概要
PDFの注釈とは,
- メモや音,動画といった要素をページに付与する,もしくは
- インタラクティブな要素を提供する
機能である.具体的には,次のような要素をPDF文書に付与することができる.
型 | 機能 |
---|---|
Text | 付箋のように表示されるテキストを付与する |
Line | 直線を引く |
Link | ハイパーリンク機能を提供する |
Stamp | ゴム印を押したような効果を与える |
FileAttachment | ファイルを添付する |
Sound | 音声ファイルを付与し,再生機能を与える |
これらの注釈の中には,ページが開かれた際やマウスオーバーした際などのイベントに対して,独自のアクションを設定できるものもある.
PDFTeXによる注釈の利用
TeXでPDFの注釈を使用するには,PDFの注釈オブジェクトを生成し書き込む必要がある.また,注釈を含むページにも細工をする必要がある*1.
この文面だけ見ると面倒なように見えるが,PDFTeXにはこれらを簡単に扱うためのプリミティブ\pdfannot
が既に準備されている.\pdfannot
は次のように用いる.
\pdfannot <<サイズ指定やオブジェクト番号に関する記述>> {<<注釈オブジェクトの記述>>}
これだけではイメージは沸かないと思われるので,ファイル添付注釈を例に,具体的な使用法を示す.まず,次のコードを考える.
\documentclass{article} \begin{document} The source code of this PDF document is attached on this page. %% read a file to pdf object \immediate \pdfobj stream file {\jobname.tex}% %% add file attachment annotation \pdfannot width 1em height 1.7ex depth 0.3ex { /Subtype /FileAttachment /FS << /EF << /F \the\pdflastobj\space 0 R >> /F (\jobname.tex) /Type /Filespec >> }% Oops, this text is wrapped.... \end{document}
これは,このソースコード自身を結果のPDFに添付するサンプルになっている.私の手元のAdobe Acrobat Reader DC(Windows)では次のような表示を得ることができた.
「Oops, ...」の上にピンのアイコンがあるのがわかるだろう.これをダブルクリックすると,上のコードを開くことができる.
では,\pdfannot
を実際にどう使っているか見ていこう.
まず,\pdfannot
と{
の間にアイコンの大きさ指定がある.この大きさ指定が実際に意味を持つかどうかはViewer依存だが,書いておいたほうが無難である.なお,結果を見ればわかる通り,大きさを指定しても組版には影響を与えない.
{
と}
の間には注釈オブジェクトの内容をPDFの文法で記載する.今回はファイル添付注釈なので,/Subtype
を/FileAttachment
にし,/FS
でファイルの詳細を与えている.ファイルそのものは\pdfannot
の前に\pdfobj
を使ってPDFファイル自体に取り込んでいる.
TeX芸での利用例
これだけではあまり面白くない.もう少しTeX芸っぽいことをしよう.上の例では,ファイルを外部から読み込んだが,これをソースに直接記述しよう.また,テキストファイルだと面白くないので,バイナリファイルにしよう.
結果がこれだ.
なお,ChomeのPDF ViewerやGithubのViewerでは注釈の表示がされないようなので,手元にダウンロードしてみてほしい(音量注意).
まとめ
PDFの機能,もっと活用すればいいと思うよ*2.
LaTeXはExcel方眼紙の夢を見るか
はじめに
近年,Excel方眼紙が注目されている(要出典).Excel方眼紙とは,自由に罫線を引くためにあらかじめセルを正方形状に設定しておいたExcelファイル,およびそれによって作成された帳票を指す.そのサンプルや問題点については,参考文献を読むとよい.
Excel方眼紙は,書類としてのデザインに重きを置かれて作成されているため,データ入力や抽出・再利用に余計な労力が必要になる.しかし,これを捨てるのは容易ではない.参考文献の言葉を借りれば『「紙」文化圏の大人にとって,「データ」文化への切り替えは容易ではない』*1.
この状況を改善するには,「データ」文化側が,
- Excel方眼紙の存在を許容し,データ入力や抽出・再利用の方法を工夫する
- 「紙」文化側でもそれなりに扱えるような軽量かつグラフィカルにできる文書作成方法を提供する
といった対策が考えられる.
1については,OOXMLを直に操作したりPowerShellからExcelのCOMを叩く*2といった方法が考えられる.しかし,手動でExcel方眼紙を扱う際に発生する余計な労力と,これらの学習コストが釣り合うかどうかという問題がある.
2について考える.現状でも,LaTeXなどは表形式に対するマークアップ記法を用意している.しかし,これらの形式は単純な表に対して最適化されており,Excel方眼紙のターゲットとなる自由に罫線を引いた文書には向いていない*3.しかし,マークアップ記法さえ確立してしまえば問題は解決できる.
本記事では,2の手法について自由に罫線を引いた文書に対するマークアップ記法を提案し,そのLaTeXでの実装を示す.
マークアップ記法
今回作成した試作品は,Githubで公開している.
サンプルは,Excel方眼紙公開討論会を参考にして作成した*4.
作成したスタイルファイル,hogan.styでは,次の形式で自由に罫線を引いた文書に対するマークアップ記法を提供する.
% <<x>>は横方向のセル数,<<y>>は縦方向のセル数 % <<w>>は1セルの幅,<<h>>は1セルの高さ \begin{hogan}[cells=<<x>>*<<y>>, size=<<w>>*<<h>>] \begin{lines} <<罫線部分へのマークアップ>> \end{lines} <<各セルへのテキストの配置>> \end{hogan}
いくつか例を示そう.まずは,3行3列の各セルに実線の罫線を引き,それぞれにテキストを入れる場合,次のようにする.
\begin{hogan}[cells=3*3, size=2.5cm*1cm] \begin{lines} +-----+-----+-----+ | | | | +-----+-----+-----+ | | | | +-----+-----+-----+ | | | | +-----+-----+-----+ \end{lines} \ctextbox[at={(0,0)}]{\textbf{左上}} \ctextbox[at={(1,0)}]{上} \ctextbox[at={(2,0)}]{\hbox{\tate 右上}} \ctextbox[at={(0,1)}, align=left]{左側\\左寄せ} \ctextbox[at={(1,1)}]{☃} \ctextbox[at={(2,1)}, align=right]{右側\\右寄せ} \ltextbox[at={(0,2)}, align=left]{左側\\セルも左寄せ} \ctextbox[at={(1,2)}, align=center]{中央\\中央寄せ} \rtextbox[at={(2,2)}, align=right]{右側\\セルも右寄せ} \end{hogan}
この記述により,次の出力を得る.
上記のように,hogan.styでは罫線をlines
環境配下にアスキーアートで与える.各行の高さは1行であることを求めるが,各列の幅は何文字あってもよい.実線の罫線を引く場合,横方向なら-
,縦方向なら|
を用いる.
描画時の幅および高さはhogan
環境のオプションのみで決定される.Excelと違い,ある行の高さもしくは列の幅のみを操作はできない*5.
セルへ文字列を印字するには,\ltextbox
,\ctextbox
,もしくは\rtextbox
のいずれかの命令を用いる.at
オプションでセルの座標を与える.命令はそれぞれ,セル内の配置が左寄せ,中央寄せ,右寄せのテキストを生成する.これらの命令にはalign
オプションを与えることができる.このオプションは引数のテキストが複数行のときに,そのテキストの整列法を指定する.なお,現状の実装ではセル内の折り返しを実装していないので,改行は手動で与える必要がある*6.
hogan.sty
では,実線以外にもいくつかの罫線を提供している.横・縦方向ともに*
で太線が引かれる.また,横方向で"
,縦方向で:
を用いると点線が引かれる.サンプルを示しておこう.
\begin{hogan}[cells=3*2, size=2.5cm*1cm] \begin{lines} +-----+-----+-----+ | : * | +"""""+-----+*****+ | : * | +-----+-----+-----+ \end{lines} \ctextbox[at={(0,0)}]{↓→点線} \ctextbox[at={(2,1)}]{↑←太線} \end{hogan}
セル結合は,セル間の罫線を引かない機能と,テキストを複数セル間にまたがって配置する機能を組み合わせて実現する.サンプルを以って示しておこう.
\begin{hogan}[cells=3*2, size=2.5cm*1cm] \begin{lines} +-----+-----+-----+ | . | | + + +-----+ | . | | +-----+-----+-----+ \end{lines} \ctextbox[at={(0,0)}, box=2*2]{セル結合} \end{hogan}
実装
hogan.sty
の描画は,単純にTikZを利用して実装している.工夫したことといえば座標の計算のみである.hogan
環境内部はtikzpicture
環境となっているので,TikZの力を借りて吹き出しを入れるといったことも可能である*7.
lines
環境のパースも特筆すべきことはない*8.現状はカテゴリーコードの変更をかけていないが,変更すれば縦方向の罫線なしの記法をにすることも可能な見込みなので,この辺りは再考の余地がある.
考察
hogan.sty
によって,アスキーアートを利用したある程度グラフィカルな文書作成環境を提供できる.しかし,現状のhogan.sty
だけでは大規模な文書の作成が難しい.Githubに載せているサンプルを作成してわかったのだが,セル数が増えれば増えるほど,lines
環境に与えるアスキーアートを描くコストが増大する.その点を考えると,Excelは罫線を引くUIとして使いやすい*9.データだけではなく,罫線も入力しやすくする方法を模索していきたい.
まとめ
Excel方眼紙は悪い文明だが,駆逐するのは難しい.
もうひとつのTeXがチューリング完全であることの証明
この記事はTeX & LaTeX Advent Calendar 2016の17日目の記事です. 2日目はYasuhide Minodaさんでした.18日目はVoDさんです.
はじめに
これまで,TeXがチューリング完全であるかを証明する様々な試みがあった.ここにいくつか挙げておこう.
私の知る限り,そのすべてがTeXの胃,すなわちプリミティブの実行までを使用している.しかし,TeXには胃の前に口,すなわちマクロの展開がある.ここで,気になるのは次の問題である.
この問いに答えるため,簡単なBrainf*ck処理系を作成してみた.それが,次である.
実用するためのプログラムでないため,使い方の説明は省略するが,sample.tex
の\edef
の中にBrainf*ckコードがあり,それが\show
によって正しく処理されていることがわかる.\edef
の中ではTeXの胃が動かないことがわかっているので,TeXはマクロ展開のみでチューリング完全であることが示された.
この処理系実装には,いくつかの面白い点がある.今回の記事では,そのTeX言語テクニックを紹介していこう.
マクロ展開のみにすることによるメリット・デメリット
テクニックそのものの前に,TeX言語をマクロ展開のみに制限して使用することのメリットとデメリットをまとめておこう.
マクロ展開のみで望んだ結果が得られるマクロのことを,界隈では「完全展開可能な」マクロと呼ぶ.TeX内において,完全展開可能なマクロは制限なく使用することができる.というのも,TeXは文脈によって,完全展開可能であることを要求されるのだ.先のsample.tex
における\edef
の中などがそれである.そのような状況でも使用可能なマクロは,他のマクロと組み合わせて使用することが容易である.
デメリットは,完全展開可能であるために,ほとんどの副作用が禁じられる*1点だ.これにより,次のことができなくなる.
- マクロ展開中のマクロ定義
- ラムダ計算のように,その場でマクロを定義できない
- 値の書き換えといった動作も禁止される
- 算術演算
これらの制限により,展開可能なマクロを実装することは困難である.
完全展開可能Brainf*ck処理系実装のためのテクニック
では,完全展開可能Brainf*ck処理系を実装するためのテクニックを見てみよう.
入出力・環境
まずはBrainf*ck処理系を実行していった時のテープなどの状態,すなわち環境をどう表現するかを見ていこう.まず,完全展開可能にする時点で,副作用が一切使えない.よって,直接テープを書き換えるといった実装はできない.ここでは,Brainf*ck処理系を環境を受け取り,環境を返すマクロとして作成することとした.もう少し詳しく説明すると,次のようになる.
Brainf*ck処理系における 環境 とは,(テープ, 入力, 出力, コード) である.テープとは,次節で示す数値を{
と}
で囲んだものの列である.テープには,読み取り位置という,特別な要素がひとつ存在する.入力と出力はともに文字列である.コードとは<
,>
,+
,-
,.
,,
,[
,]
から構成される列*2である.
Brainf*ck処理系における評価(→)とは,環境から環境への関数である.評価を複数回適用することを→*で表現する.
初期環境Iを(初期テープ, s, ε, c)とする.ここで初期テープとは,列のすべての要素が0の読み取り位置が左端のテープで,sは任意の文字列,cは任意のコードである.Eをコードが空列の環境とし,I→*Eであるとき,Eの出力を実行結果と呼ぶ.
ここで,本来は→の中身,すなわち評価規則を定義するべきだが,長くなるので省略する*3.評価規則は普通のBrainf*ckなので,定義自体は簡単なはずだ.
今回作成したBrainf*ck処理系とは,この関数→を完全展開可能なマクロとして実装したものにあたる.
数値の表現
ここで,前節で述べなかった数値の定義を示しておこう.当然,TeXの数値は完全展開可能な状況では使いづらいので,使いやすいように定義している.
- 空列εは数値である.
- 任意の数値nに対し,
o
nは数値である.
よくある自然数の定義法である.ここでは,succを「o
を前置する」関数としている*4.
テープの表現
さて,ここで具体的にテープをどう実装したかを述べよう.テープに必要な要件は次である.
- 副作用なしで,読み取り位置を前後させた状態を構築できる
- 副作用なしで,読み取り位置の値を書き換えた状態を構築できる
あ,これ研究室ゼミでみたことある*5.Zipperだ!
Zipperとは,副作用なしで要素をたどり,書き換えるなどの操作ができることができる木やリストなどを実装するためのプログラミング技法である.先の要件を満たすリストはその典型である.例を挙げておこう.
リスト[1,2,3,4]
に対し,読み取り位置が要素3
の位置にあるとする場合,これを([2,1],[3,4])
の組で表現する.読み取り位置を右にずらすときは,右側のリストの先頭を左側のリストの先頭に送る.すなわち([3,2,1],[4])
のようになる.現在の読み取り位置の値を書き換えるには,右側のリストの先頭を置換えればよい.([3,2,1],[4])
の先頭を42
に書き換えると([3,2,1],[42])
になる.
さて,これをTeXでどう実装するかである.左側のリストをl1,右側のリストをl2とする.これらは,単純に数値を{
と}
で囲んだものの列である.これに対し,リストZipperは\@febf@mem@start
l1{}{}\cur
l2で表現される.リストZipperへの操作は,マクロとパターンマッチで実装される.なお,l1の後に不要な{}{}
があるように思えるが,これには意味がある.パターンマッチの都合上,左側に最低でも2要素必要だったのだ.
入出力
ここまでで,テープに数値がどのように書き込まれるのかを確認した.ここで問題になるのが入出力である.入出力は文字列なので,文字から自然数への相互変換が必要になってくる.これは,事前に相互変換を行うためのテーブルのようなマクロを用意することとした.ソースコードも分離してあり,in.tex
が文字から自然数への,out.tex
が自然数から文字への変換を行うマクロになっている.それぞれの中身を一部見てみよう.
% in.texの一部 \expandafter\def\csname @febf@in@'\endcsname{ooooooooooooooooooooooooooooooooooooooo} \expandafter\def\csname @febf@in@(\endcsname{oooooooooooooooooooooooooooooooooooooooo} \expandafter\def\csname @febf@in@)\endcsname{ooooooooooooooooooooooooooooooooooooooooo} \expandafter\def\csname @febf@in@*\endcsname{oooooooooooooooooooooooooooooooooooooooooo} \expandafter\def\csname @febf@in@+\endcsname{ooooooooooooooooooooooooooooooooooooooooooo}
% out.texの一部 \expandafter\def\csname @febf@out@ooooooooooooooooooooooooooooooooooooooo\endcsname{'} \expandafter\def\csname @febf@out@oooooooooooooooooooooooooooooooooooooooo\endcsname{(} \expandafter\def\csname @febf@out@ooooooooooooooooooooooooooooooooooooooooo\endcsname{)} \expandafter\def\csname @febf@out@oooooooooooooooooooooooooooooooooooooooooo\endcsname{*} \expandafter\def\csname @febf@out@ooooooooooooooooooooooooooooooooooooooooooo\endcsname{+}
文字aから対応する自然数への変換は,\@febf@in@
aというマクロで,自然数nから対応する文字への変換は\@febf@out@
nというマクロで表現される.これらの変換は\csname
を用いて動的にマクロを呼び出すことによって解決される.
当然,%
など,TeXの中で特別な役割を持つ文字を,この方法で変換することは難しい.今回のBrainf*ck処理系の目的は,あくまでチューリング完全性の確認であるから,使用できる文字の集合が小さくなることは許容できるとしている.許容できないという読者は,ぜひ改善してみてほしい.
評価
準備が終わり,あとはコードを評価する部分だけである.この部分は先にコードを示しておこう.
\def\@febf\@febf@mem@start#1\cur#2\inp#3\out#4\code#5{% \expandafter\ifx\csname @febf@#5\endcsname\relax \expandafter\@febf@mem \else \expandafter\@febf@normal \fi{#1}{#2}{#3}{#4}{#5}% }
評価→を表すマクロが,\@febf
である.このマクロは引数として\@febf@mem@start#1\cur#2
で示されるテープ,#3
で入力,#4
で出力,そして#5
でコードの先頭1文字を取る.このマクロは,基本的に#5
がどの文字かによって,どの評価規則を適用するかを決定しているだけである.
ただし,ここで[
と]
の対応を取る処理をさぼるため,TeXのカテゴリーコードを使った技法を使っている.実は今回の実装では,[
と{
,]
と}
を同等にしている.これは,[
と]
のカテゴリーコードという値を{
や}
と同一の値にすることで実現している.TeXにおいて,{
と}
は自動で対応が取られるのはよく知られているであろう.これが[
と]
にも適用されるのだ.
しかし,この方法を使う場合,TeXのパターンマッチ上,+
と[+]
など,「1文字」と「[
+1文字+]
」が区別できないという問題が生じる.幸い,Brainf*ckでは<>
が意味のない命令列として使用できるので,この問題はチューリング完全性を確認する目的に対しては障害とならない.
実行結果の取得
評価→が得られたら,最後はそれを可能な限り初期環境に対して適用し,実行結果を得るだけである.しかし,ここでも工夫が必要になる.残念なことに,TeXのマクロ展開はスモールステップなので,可能な限りマクロを展開し続けるという行為もテクニックが必要になるのだ.今回の実装では,\romannumeral
トリックと呼ばれる技法を使った.詳しい説明は,すでに公開された記事があるので,そちらを参照してほしい.
まとめ
ELVMにTeXバックエンドを足した話
この記事はTeX & LaTeX Advent Calendar 2016の3日目の記事です. 2日目はdoraTeXさんでした.4日目はtex-ut-texさんです.
はじめに
2017年に学ぶべき言語12位はLaTeXである.すなわち,TeX言語をホンキで語ることが求められている(Advent Calendarテーマ回収).
前回の記事では,ELVMバックエンド作成法を紹介した.本記事では,それをどうTeXに適用したか,すなわちELVMのTeXバックエンドで用いているTeXプログラミング技法を紹介する.これが理解できると,TeXで言語処理系を作るのがあまり困難ではないということがわかるはずだ.
TeXバックエンドで用いたプログラミング技法
メモリおよびレジスタの表現
メモリは\@mem@42
など,\@mem@
+ 番地で表現される*1.初期値に0以外の値が与えられるか,EIR実行中に書き込みが行われた場合に定義される.事前に全番地分定義しておけばよいと思うかもしれないが,24ビット空間すべてを定義してしまうとTeXで定義できるマクロの最大数に到達してしまい,TeX処理系が停止してしまう*2.この事象の回避のため,メモリを表すマクロの定義タイミングを必要最低限にしている*3.これをどうにかするのが今後の課題だろう*4.
レジスタは\@reg@pc
など,\@reg
+ レジスタ名で表現される.
命令列の表現および実行部
前回の記事でも述べたように,EIRの命令列のうち,同じpc
の値を持つものは,同じグループに属するので処理をまとめる必要がある.TeXでは,これを\@inst@23
のように\@inst@
+pc
の値というマクロを生成することとした.このマクロは引数がなく,展開・実行するとグループ内の命令が実行されるようになっている.
EIRの実行を司る部分は次のようになっている.
\def\@loop@main{% \let\@@next\@loop@main \csname @inst@\@reg@pc\endcsname \count0=\@reg@pc\relax \advance\count0by1\relax \edef\@reg@pc{\the\count0}% \@@next}\@loop@main
\@loop@main
がループの本体で,\@@next
に自身を\let
し,それを展開することによってループを末尾再帰で実現している(なぜ回りくどい方法を取ったかは後述).ループのメインは3行目の\csname @inst@\@reg@pc\endcsname
で,この部分で\@inst@
+pc
の値を作り出し,それを展開・実行している.その展開・実行の後,pc
の値をインクリメントしている*5.
各命令の表現法
ここまでで,大まかなEIRからTeXへの変換法がわかった.次に,EIRの各命令がTeXにどのように翻訳されるか,その詳細を見ていこう.
入出力(PUTC
,GETC
)
TeXは他のプログラミング言語と異なり,標準入出力を扱うのに苦労するという話はよく知られているであろう.入力に関してはTeXの目*6を気にしないとならない.バイナリ列として入力を扱いたくてもそう簡単にはいかない.出力に関しても同様で,ASCIIコードの印字可能でない範囲を出力することが原理的に困難である.さらに,バージョン情報などの自動出力も抑制できない.
TeXバックエンドを作るにあたり,入出力に関してはTeXの外の世界に頼るしかないと割り切った.そこで,ここでは次のような変換を行うことにした.
- EIRに与えられる入力を外部の力を借りて,そのASCIIコード値の改行区切り列に変換する
- 1で得られた結果を,TeXの標準入力に与える
- TeXは,別ファイルにEIRの実行結果としての標準出力をASCIIコード値の改行区切り列で出力する
- 3で得られたファイルを外部の力を借りて通常の文字列に戻す
図示すると,次のような形になる.赤色はASCIIコード値の改行区切り列,グレーは捨てるファイルや出力を指す.また,foo.tex
はTeXバックエンドより生成されたEIRのコンパイル結果である.
ここで,「入力をASCIIコード値の改行区切り列に変える」とは,
hoge fuga
という入力を
104 111 103 101 10 102 117 103 97
に変換することを指す.
この変換を挟む関係上,TeXバックエンドの出力結果は入出力をインタラクティブに扱えないという制限を持つ.これを改善するためには,TeXで標準入出力を普通のプログラミング言語のように取り扱えるようにする技法が求められる*7.
算術演算(ADD
,SUB
)
前回の記事で言及した通り,ELVMでは整数が24ビットである.そのため,多くの言語ではマスクしてやる必要がある.しかし,TeXはビット演算をプリミティブに持っていない.今回の加算の実装では,nビット整数とnビット整数の和はたかだかn+1ビット整数であるという性質を用いて,和が24ビットの範囲を超えているようなら,そこから224を引くという実装にしている.減算についても同様である.
EXIT
プログラムを終了するとき,メインループ\@loop@main
の末尾再帰を停止してやる必要がある.そこで,今回の実装では,EXIT
を\@@next
に\relax
を\let
するように翻訳した.これにより,\@loop@main
の末尾が\relax
と等価になり,末尾再帰が終了する.
その他
特筆すべきものはないだろう.
まとめ
やはり,TeX言語はそんなに難しくない.
参考
ELVMには現在,興味深い言語のバックエンドがどんどん追加され,その実装解説が出ている.ここにリストで挙げておこう.
- UnlambdaでVMを実装する(前編)
- UnlambdaでVMを実装する(後編)
- Unlambdaでの実装解説.一言でいうと凄まじい.ラムダ計算やコンビネータ論理を学ぶ予定があるなら目を通しておくべき.
- ELVM で C コンパイラをポーティングしてみよう(Vim script 編)
- Vim scriptでの実装解説.バックエンドの追加法に関してもよく解説されているので,これからバックエンドを足そうと考えている人は必読.
- コンパイル中にコンパイルする「コンパイル時Cコンパイラ」をつくった話
ELVM Compiler Infrastructureバックエンド作成のすゝめ
初編
「天はELVM Compiler Infrastructureの上にELVM Compiler Infrastructureを造れり」と言えり。されば天よりCコンパイラを生ずるには、……
というわけで,この記事では,(どこかに作者の資料があるかもしれないが)ELVM Compiler Infrastructureバックエンド作成法を解説する.
ELVM Compiler Infrastructureとは
ELVM Compiler Infrastructure(以下,本記事ではELVMと省略)とは
から構成されるCコンパイラ*1である.作者は@shinh氏.ELVMの詳細はここあたりを参照するとよいだろう.要は,Cプログラムを様々な他言語に変換できる.
何がうれしいのか
Turing完全性が云々……という話を置いておけば,純粋に変換でしかないので,普通のプログラミング言語ならあまりメリットはないだろう.しかし,これが難解プログラミング言語になると話が変わってくる.作者がLispインタプリタをPietで動かしたように,記述が困難な言語で大規模なプログラムを生成しやすくなるのだ.
さらに,ELVMの大きな特徴として,ELVMそのものがELVMでコンパイルできることが挙げられる.つまり,ELVMのバックエンドに追加されている言語でCコンパイラをお手軽に作ることができるようになるのだ.
話は変わり,近年,私のTLにおいて次の事象が観測された.
Vim の勉強会で空気読まずに TeX の話したら(Vim の話も申し訳程度にはしたけど)「TeX で C のコンパイラを作りなよ」って煽られた回.楽しかったです,お疲れ様でした.#yokohamavim
— ワトソン (@wtsnjp) 2016年10月16日
こんな話もあった.
Vim script で書かれた C コンパイラをリリースしました https://t.co/lStVsRU5gB
— ドッグ (@Linda_pp) 2016年10月20日
時代がTeXでCコンパイラを求めていることは自明であった.しかし,ELVMバックエンドにはTeXがない.というわけで,ELVMのTeXバックエンドを作成し,それを用いてCコンパイラ(8cc.tex)を作成した.
8cc.texの話は別の機会に行うものとして,さっそくELVMバックエンドの作成方法を記していこう.
ELVMバックエンド作成
準備
まずは,バックエンドに追加する言語を決めて本家をfork.
バックエンドの作成
実際,バックエンドを作成する際に作成するファイルは少ない.foo言語のバックエンドを作るなら,target
ディレクトリにfoo.c
を作成するだけである.正直,既存の多言語での実装を読めばどのように実装すべきかはすぐにわかるのだが,次の点に注意して読むとよりわかりやすくなるだろう.
- レジスタは全部で7つ.特に気にするべきなのは
pc
である.名前の通りプログラムカウンタで,実行のループのたびにインクリメントする必要がある - EIRは24bitマシンであることを想定している.普通の言語なら適宜マスクをかける必要があるだろう
- で,私はこの部分で
UINT_MAX + 1
を使用するという初心者レベルの失態を犯していた.後世のために,このミスを告白しておく
- で,私はこの部分で
- メモリの初期値は
Module
構造体のdata
に0番地から順に格納されている.ただし,data
に入っていない部分についても読み込んだ時に0
が返ってくるようにしておく必要がある - 命令は
data
とは別にModule
構造体のtext
で与えられる*2.これをバックエンドに追加する言語用に変換していく.text
の型はInst
で,単方向リストになっている.メンバpc
が同一のInst
同士は,ひとつのグループとして扱う必要がある*3.これをバックエンドに追加する言語用に変換していく.ジャンプもこのグループ単位で行われる点に注意
さらに,EIRは命令セットが小さい.大まかな特徴をあげておこう.
- 算術演算は加算(
ADD
)と減算(SUB
)しかない.なお,乗算,除算,およびビット演算はビルトイン関数で実装済みである - ファイルIOはない.libcの実装を見ればわかるが,
fopen
してもstdin
が返ってくる - 標準入出力の命令は1文字読み込み(
GETC
)と1文字書き込み(PUTC
)しかない
ビルドおよびテストの準備
ここまでで,foo.c
の作成が終了したとする.あとは,これを本体に組み込んでテストを実行するだけである.
まずは,バックエンドを使えるようにするため,target/elc.c
にfoo.c
のメインの関数のプロトタイプ宣言を記述しよう.次のようになるはずである.
/* ...(中略)... */ void target_bef(Module* module); void target_bf(Module* module); void target_unl(Module* module); void target_foo(Module* module); /* <- ここが追加 */ typedef void (*target_func_t)(Module*);
次に,target_foo
が呼べるように条件分岐を追加する.次のようになるはずだ.
static target_func_t get_target_func(const char* ext) { if (!strcmp(ext, "rb")) { return target_rb; } else if (!strcmp(ext, "py")) { return target_py; } else if (!strcmp(ext, "js")) { /* ...(中略)... */ } else if (!strcmp(ext, "unl")) { return target_unl; } else if(!strcmp(ext, "foo")) { /* <-ここが追加 */ return target_foo; /* <-ここが追加 */ } else { error("unknown flag: %s", ext); } }
なお.関数の追加位置については,(作者に本来は確認すべきだが)末尾のほうが良いだろう.最初に追加されたUnlambdaは末尾に,次に追加されたVim scriptはEmacs Lispとの対比の目的でその脇に配置されたが,私がTeXを追加するときに,誤ってVim scriptの脇に配置してしまった*4*5.
そして,追加したファイルをmake
できるようにする.Makefile
に次のように追加する.
# ...(中略)... # 末尾にfoo.cを追加 ELC_SRCS := elc.c util.c rb.c py.c ... unl.c foo.c # ...(さらに中略)... # 同じような記述が並んでいるところ(Targets)に次を追加 TARGET := foo RUNNER := <<foo-runner>> include target.mk
<<foo-runner>>
には,コンパイル結果を動かすためのコマンドを記載しておく.1コマンドで動かない場合は,tools/foo.sh
を追加し,1コマンドで動くようにしておく.TeXではこれを用いている.
これで,make
が行えるようになった.追加した言語のテストはmake foo
とmake elc-foo
で行う.これがすべて通過すれば追加した部分は問題ないだろう.その後,make test
することによって,全言語のテストを行うことができる.make test
は私の環境*6で時間がかかったので,お茶でも飲んで行く末を見守ると良いだろう.
テストまで通ったら,あとはREADME.md
のバックエンド一覧にfoo言語を追加し,言語数をインクリメントする.
終わりに
世界にELVMバックエンドが増えるといいな.