読者です 読者をやめる 読者になる 読者になる

LISP on TeXを作る(評価器編2)

前回の続き.evalの本丸である関数適用の説明に入ろう.

consセルの評価

関数適用が起こるタイミングとはすなわち,consセルが評価されるタイミングである.まずは,consセルのデータ構造を確認しておこう.consセルは,次の形をもつトークン列である.

\@tlabel@cons{\carXX\cdrXX}

\carXXがCAR,\cdrXXがCDRを表す制御綴りであり,展開するとLISP on TeXにおけるオブジェクトの形式をしたトークン列を得ることができる.

consセルの評価規則は簡単で,

  1. CARを評価して,適用可能なオブジェクトを得る
  2. CDRを引数として,さきほど得られたオブジェクトに適用する
    • 関数やクロージャの場合は各引数が評価される.マクロの場合はそのまま引き渡す

だけである.consセルの評価規則の実装,\@eval@consを確認しよう.

\def\@eval@cons#1#2#3{\@@eval@cons#1{#2}#3}
\def\@@eval@cons#1#2#3#4{%
  \expandafter\@eval#1{#3}\@temp@i
  \def\@temp@ii{}% init
  \expandafter\@flatten@args#2\@temp@ii
  \expandafter\expandafter\expandafter\@@select@apply@pre\expandafter\@temp@i\@temp@ii\@{#3}#4}
\def\@@select@apply@pre{\expandafter\@@select@apply}

\@eval@consの引数は,順に「CAR」,「CDR」,「現在の環境(大域環境との差分)」,「制御綴り」である.第4引数の制御綴りに評価結果が格納される.

まず,\@eval@consでは,現在の環境のもとでCARを評価する.\expandafter便利.評価結果は,\@temp@iに格納される.次に,\@flatten@argsで引数をTeXで扱いやすい形に整形する.現時点での引数部分,すなわちCDRは単一の制御綴りであり,すべての引数を得るには順次それを展開していかないといけない構造になっている.正直言って,TeX側で扱うには不便である.\@flatten@argsでは,評価前の引数を列を次の形(整形形式)に整形する.

\csI{valI}\csII{valII}...\csN{valN}

ここで,\csI, \csII, …, \csNは引数1, 引数2, …, 引数Nの型ラベル,valI, valII, …, valNがデータである.\flatten@argsのコードを示す.

\def\@flatten@args#1#2#3{%
  \ifx#1\@tlabel@cons
    \let\@flatten@next\@@flatten@next
  \else\ifx#1\@tlabel@nil
    \let\@flatten@next\@@flatten@fin
  \else
    \errmessage{LISP on TeX [internal apply]: Invalid args}%
  \fi\fi
  \@flatten@next#2#3}

\def\@@flatten@next#1#2#3{%
  \expandafter\expandafter\expandafter\def
  \expandafter\expandafter\expandafter#3%
  \expandafter\expandafter\expandafter{\expandafter#3#1}%
  \expandafter\@flatten@args#2#3}

\def\@@flatten@fin#1{}


要は,consセルを順次たどっていっているだけである.ここで,\@flatten@argsはconsセル全体が行儀の良いリストか否かの判定も行っている.整形した結果は.\@flatten@argsの第3引数に与えられた制御綴り,\@eval@consでは\@temp@iiに格納される.ここで,引数はまだ評価されていないことに注意する.

最後に,\@eval@consはCARの評価結果(\@temp@i)を引数(\@temp@ii)に適用する.すなわち,次のトークン列になるように展開される.

\@apply@XXX{valCAR}\csI{valI}\csII{valII}...\csN{valN}\@{env}\targetReg

\@apply@XXXはCARを評価結果が持つ適用のためのマクロ,valCARはCARを評価した結果のデータ,\csI{valI}\csII{valII}...\csN{valN}が引数,\@は引数の終端,envは環境,\targetRegは適用結果を格納するための制御綴りである.

組み込み関数の適用

残りは,組み込み関数,クロージャ,マクロ,およびスペシャルフォームの適用がどのように実装されているのかを確認するだけである.まずは,組み込み関数から見ていく.

適用規則に入る前に,次のコードから,組み込み関数のデータ構造を確認しておこう.

\@tlabel@func{\cs}

\csが組み込み関数のTeX実装で,次のように呼び出されることを前提として実装されていなければならない.

\cs\targetReg\csI{valI}\csII{valII}...\csN{valN}\relax\relax

\targetRegが適用結果格納を格納する制御綴り,\csI{valI}\csII{valII}...\csN{valN}が評価済みの引数である.可変長引数に対応するため,引数列のラストは\relax\relaxが付加されている.当然,\relaxは展開されても何の効果もないため,実装側はこれを無視してもよい.例えば,LISP on TeXの等価判定である\=は次のように実装されている.

%equality
\addassoc\@globalenv\={\@tlabel@func{\@lisp@equal}}
\def\@lisp@equal#1#2#3#4#5{%
  \gdef#1{\@tlabel@bool{f}}%
  \ifx#2#4%
    \def\@@temp@eqchecki{#3}%
    \def\@@temp@eqcheckii{#5}%
    \ifx\@@temp@eqchecki\@@temp@eqcheckii\gdef#1{\@tlabel@bool{t}}\fi
  \fi}

\@lisp@equalがその実体で,LISP on TeX側での第1引数(#2#3)と,第2引数(#4#5)を\ifxで等価判定し,その結果に応じて#1に偽(\@tlabel@bool{f})もしくは真(\@tlabel@bool{t})のいずれかが格納されるようになっている*1

組み込み関数の適用規則,\@apply@funcは次のように実装されている.

\def\@apply@func#1#2\@#3#4{%
  \def\@temp@i{}%
  \@apply@eval@args\@temp@i{#3}#2\relax\relax
  \expandafter\@apply@func@next\expandafter{\@temp@i}{#1}{#3}#4}
\def\@apply@func@next#1#2#3#4{\@@apply@func{#2}#1\@{#3}#4}

まず,\@apply@funcは,\@apply@eval@argsを用いて,LISP on TeXの意味での引数(#2)を評価し,整形形式にする.その結果は\@temp@iに格納される.\@apply@funcは最終的に次のトークン列に展開される.

\@@apply@func{\cs}\csI{valI}\csII{valII}...\csN{valN}\@{env}\targetReg

\csは組み込み関数の本体,\csI{valI}\csII{valII}...\csN{valN}が評価済みの引数,\@は引数の終端,envは環境,\targetRegは適用結果を格納するための制御綴りである.形式はほぼ\@apply@funcと同じだが,引数列が評価されている点で異なる.このように適用規則を分解したのは,\apply関数の実装のためである.\applyでは引数を評価しないで関数適用する必要がある,そのため,\applyでは\@@apply@XXXを直接呼ぶようになっている.

\@@apply@funcの実装を見てみよう.

\def\@@apply@func#1#2\@#3#4{\gdef\@@tco{#1#4#2\relax\relax}\aftergroup\@@tco}

要は,先に示した

\cs\targetReg\csI{valI}\csII{valII}...\csN{valN}\relax\relax

と言う形に展開されるのだが,ここではそれを\@@tcoというマクロに定義して,それを\aftergroupの引数にしている.これは,末尾呼び出しの最適化のためである.\aftergroupは現在のグループの終了時に,指定されたトークンを指定した順で出力するためのプリミティブである.評価器編1で,LISP on TeXのコールスタックはグループで表現されていることを説明した.すなわち,展開中のトークン列は

\gdef\@@tco{#1#4#2\relax\relax}\aftergroup\@@tco\endgroup

となっている.\aftergroupにより,関数適用はグループの終了直後,すなわち\endgroupの終了後に実行されることになる.これにより,無駄に\endgroupが末尾に溜まっていくことを防いでいる.

これらにより,目標としていたトークン列が展開され,組み込み関数の適用が行われる.

クロージャの適用

クロージャの場合も,組み込み関数とほぼ変わらない.まず,次のコードでクロージャのデータ構造を確認しておこう.

\@tlabel@closure{{bind}{env}\bodyLabel{bodyValue}}

bindは仮引数を表すトークン列,\bodyLabel{bodyValue}がクロージャの本体,envがクロージャ作成時の環境(大域環境との差分のみ)である.bindは次の形式を持つ.

\csI\csII...\csN:\csRem

ここで,\csI, \csII, …, \csN, \csRemが仮引数に使われているシンボルである.\csRemはリストにバインドされる特別なシンボルであり,仮引数の形式が単一のシンボルもしくは行儀の悪いリストの時に使用される.使用されない場合,すなわち仮引数リストが行儀の良いリストだった場合,\@@unusedという特別なシンボルが与えられる*2

さて,クロージャの適用規則である\@apply@closureを見てみよう.

\def\@apply@closure#1#2\@#3#4{%
  \def\@temp@i{}%
  \@apply@eval@args\@temp@i{#3}#2\relax\relax
  \expandafter\@apply@closure@next\expandafter{\@temp@i}{#1}{#3}#4}
\def\@apply@closure@next#1#2#3#4{\@@apply@closure{#2}#1\@{#3}#4}

\@apply@funcと同様に,\@apply@eval@argsで引数を評価し.\@@apply@closureを展開する.

\@@apply@closureの実装は次のようになっている.

\def\@@apply@closure#1#2\@#3#4{\@@apply@closure@next#1#2\@#4}
\def\@@apply@closure@next#1#2#3#4#5\@#6{%
  \def\@temp@env{}%
  \@@apply@create@env\@temp@env#1#5\relax\relax
  \expandafter\gdef\expandafter\@@tco\expandafter{%
    \expandafter\@@eval@envcs\expandafter{\@temp@env#2}#3{#4}#6}%
  \aftergroup\@@tco}

まず,\@@apply@create@envを使って実引数割り当てを行っている.すなわち,仮引数を表すトークン列と実引数から,整形形式のトークン列を得る*3.\@@apply@funcと同様,\aftergroupを利用して末尾呼び出しの最適化を行いつつ,これは次のトークン列に展開される.

\@@eval@envcs{env1env}\bodyLabel{bodyValue}\targetReg}

env1は仮引数を実引数に束縛した環境,envがクロージャ作成時の環境(大域環境との差分のみ),\bodyLabel{bodyValue}がクロージャの本体,\targetRegが評価結果を格納するための制御綴りである.これは更に,次のように展開される.

\@eval\bodyLabel{bodyValue}{env1env}\targetReg

これにより,クロージャの本体が適切な環境で評価される.

マクロの適用

次に,マクロの適用規則を見ていこう.その前に,マクロのデータ構造を確認する.

\@tlabel@closure{{bind}\bodyLabel{bodyValue}{env}}

実はクロージャと全く同一の構造を持っている.なお,envが入っているが,\defmacro自体の実行タイミングが大域環境の直下しかないので,空になっていることに注意する*4

これまでで,\apply@XXXの目的が「引数を評価する」ことに,察しのいい読者なら気づいただろう.引数を評価する必要のないマクロでは,\@apply@macroと\@@apply@macroは同一になっている.

\let\@apply@macro\@@apply@macro

\@@apply@macroは,\@@apply@closureと同様の動きをする.コードを示す.

\def\@@apply@macro#1#2\@#3#4{\@@apply@macro@next#1#2\@{#3}#4}
\def\@@apply@macro@next#1#2#3#4#5\@#6#7{%
  \def\@temp@env{}%
  \@@apply@create@env\@temp@env#1#5\relax\relax
  \expandafter\gdef\expandafter\@@tco\expandafter{%
    \expandafter\@@eval@envcs\expandafter{\@temp@env#2}#3{#4}#7%
    \expandafter\@eval#7{#6}#7}%
  \aftergroup\@@tco}

まず,\@@apply@create@envで仮引数を束縛する.その後,その環境でマクロの本体を評価して,マクロの仮引数をすべて実引数に置き換える.更にその結果を評価して,マクロの展開が修了する.なお,ここでも末尾呼び出しの最適化がかかる.

スペシャルフォームの評価

最後はスペシャルフォームの評価である.LISP on TeXでは,各スペシャルフォームに別々の型ラベルを与えている.すなわち,スペシャルフォームSに対し\@tlabel@Sが定義されている.すべてのスペシャルフォームについて説明するのは冗長なので,ここでは\if,\define,\quoteの実装を示す*5

\if

\ifの評価規則\@apply@ifは次のように実装されている.

\def\@apply@if#1#2#3#4#5#6#7\@#8#9{%
  \@eval#2{#3}{#8}#9%
  \expandafter\@apply@if@next#9#4{#5}#6{#7}{#8}#9%
  \aftergroup\@@tco
  }
\def\@apply@if@next\@tlabel@bool#1#2#3#4#5#6#7{%
  \let\@@next\relax
  \ifx#1t%
    \let\@@next\@apply@if@next@t
  \else\ifx#1f%
    \let\@@next\@apply@if@next@f
  \else
    \errmessage{LISP on TeX [if]: Invalid boolean. It's BUG. Please report.}%
  \fi\fi\@@next{#1}{#2}{#3}{#4}{#5}{#6}{#7}}
\def\@apply@if@next@t#1#2#3#4#5#6#7{\gdef\@@tco{\@eval#2{#3}{#6}#7}}
\def\@apply@if@next@f#1#2#3#4#5#6#7{\gdef\@@tco{\@eval#4{#5}{#6}#7}}

まず,第1引数が評価されて\@apply@if@nextが展開される.\@apply@if@nextでは,第1引数の評価結果であるbool型オブジェクトの中身を見て,真なら第2引数を,偽なら第3引数を評価する.なお,第1引数の評価結果であるオブジェクトがbool型でない場合,TeX側でエラーになる.

\define

\defineは,第2引数を評価して,大域環境に{第1引数→第2引数の評価結果}を追加するだけである.コードを示す.

\def\@apply@define#1\@tlabel@symbol#2#3#4\@#5#6{%
  \@eval#3{#4}{#5}#6% define does NOT use local environment
  \expandafter\addassoc\expandafter\@globalenv\expandafter#2\expandafter{#6}%
  \gdef#6{\@tlabel@nil{}}}

まず,第2引数(#3#4)を評価する.このとき,大域環境との差分(#5)は空であるはずだが,LISP on TeXではそれを確認していない.その後,{第1引数→第2引数の評価結果}を\@globalenvを用いて大域環境(\@globalenv)に追加する.\define全体の評価結果はnilになることが,この実装からわかる.

\quote

\quoteは第1引数をそのまま返すだけである.コードも簡単で,次のようになっている.

\def\@apply@quote#1#2#3\@#4#5{\gdef#5{#2{#3}}}

終わりに

これをもって,LISP on TeXの実装のほとんどが説明された.誰でもLISP on TeXが実装できるようになったわけである.

現在,LISP on TeXではqstestパッケージを使ったテストコードの整備を進めている.諸事情により,これが終了し次第,one-shot continuationの実装に入る予定である.また,GCも実装可能な目処が立ってしまったので,実装するかもしれない.

2014/05/18 クロージャオブジェクトの表現が間違っていたので修正

*1:この実装,実は引数が規定よりも多かった時に何の処理もしていない.おそらく,型ラベルが展開されて予期しない結果を得ることになる.現状の改善点のひとつだが,どうせエラーなので私の中での優先度は低い.

*2:すなわち,LISP on TeXでは仮引数かつそれにリストが割り当てられる場合,\@@unusedというシンボルを使用することができない.これも修正対象ではあるが,割りと面倒なので放置していた.

*3:割りと複雑なマクロにしてしまったので詳細は省略する

*4:実際は,大域環境直下以外の実行を禁止しているわけではない.やったら謎の環境で展開されるマクロが完成する.

*5:実装が複雑なスペシャルフォームは\lambdaなどだが,それらの解読は読者への課題とする(マテ