この記事について

SATySFi には多段階計算という機構があり，文書のプリプロセスに利用することができる．

ただ，現状まとまった資料がないので使ってみようと思っても敷居が少し敷居が高い．この記事は多段階計算について，

何のためにあるのか
どうやって書くのか

といった部分の基本を入門向けにまとめる試みである．

SATySFiのバージョンは0.0.7に基づいている．推測に基づいて書いている部分もあるので，間違っている箇所があったら遠慮なく指摘してほしい．

なお，前提としてSATySFiの通常のコマンド定義等は知っているものとしている．

多段階計算とは

多段階計算は，プログラムの評価を多段階に分けて処理する機構である．

それぞれの段階をステージと呼び，stage 0 -> stage 1 -> ... -> stage (n-1)の順で評価を行う． stage 0を評価するとstage 1のプログラムが出力され，stage 1を評価するとstage 2のプログラムが出力され，... といった具合で処理が進む．つまり，あるステージは次のステージのためのプリプロセス的な役割を行うことができる．

SATySFi の多段階計算の動機

SATySFi は組版処理に特化した言語であり，型検査による組版処理開始前のエラー報告が大きな強みである．

一方，組版処理においては文書を生成するという役割上，比較的複雑な処理でも簡潔に記述できることが望まれる．このような要求に対処する方法として，文字列を解釈するような言語内DSL(domain specific language)を設計して使うという方法がある．

ここで，通常DSLが解釈されるのは文書の組版処理と同じタイミングであるため，DSLの入力にエラーがあった場合にこのエラーが発見されるのは組版処理中である．したがって，例えば500ページの文書を組版するのにエラー箇所が490ページ目であればそこまでの490ページ分の組版処理が終わってから初めてエラーが発見されて処理が中止され，そこまでの組版結果は無駄になってしまう．

そこで，多段階計算を導入してプリプロセスの段階でDSLの解釈を行うことで全体の文書の組版を開始する前にエラー報告を行うことができるようにしたいという動機がある．

SATySFi では2段階の計算をサポートしており，stage 0とstage 1が存在する． stage 0でstage 1のプリプロセスを行う間にエラーを発見することで，迅速なエラー報告を行うことができるようになる．

文法と評価規則

肝となる文法は次の2つである．

stage 1のプログラム中に，~(...)という記法によってstage 0のコードを埋め込むことができる．
stage 0のプログラム中に，&(...)という記法によってstage 1のコードを埋め込むことができる．

SATySFiの文書ファイルはstage 1のプログラムとして解釈する．

stage 1のプログラム中に~(...)という式が現れたら，stage 1の評価を行う前に~(...)の中身をstage 0のプログラムとして評価する． stage 0の評価の結果が&(exp)(expはstage 1の式)という形になればstage 0の評価は終了し，~(&(exp))全体をexpで置き換える．

非常に単純な例として，1 + ~(&2)というstage 1のコードを考える． stage 1の評価を始める前に，~(&2)の中身&2をstage 0のプログラムとして評価する． 2は整数を表すstage 1の式なので，&2はすでに&(stage 1 の式)という形になっている．したがってstage 0の評価は直ちに終了して~(&2) -> 2という置き換えが行われ，元のプログラムは1 + 2というstage 1のコードになる．

上の例は実質的にstage 0で何もしていないのであまり意味がないが，もちろんstage 0の上でいろいろな計算を行うことができる．後から，もう少し複雑な例についても考えていく．

stage の指定

SATySFi では，ファイル冒頭にステージの指定@stage: ...を書くことでそのファイルがどのステージに関するコードかを記述する．指定できるのは，次の3つである．

@stage: 0: stage 0のコード
@stage: 1: stage 1のコード
@stage: persistent: stage 0, stage 1どちらでも使えるコード(後述)

プリプロセス用の関数を定義したいなら，基本的に@stage: 0のファイル内で書くことになる．

指定を省略した場合，デフォルトで@stage: 1と等価になる．文書ファイルに対するステージの指定は@stage: 1でなければならない．

@stage: persistentは少し特殊で，stage 0とstage 1両方で使えるコードを記述する．ただし，~(...)や&(...)のステージをまたぐ文法を使うことはできない．例えば，標準ライブラリのlist.satygなどはpersistentである．

ファイル間の依存関係において，次の制約を満たす必要がある．

@stage: 0のファイルは@stage: 1のファイルに依存してはいけない．
@stage: persistentのファイルは@stage: 0,@stage: 1のファイルに依存してはいけない．

型システム

SATySFi の多段階計算では，int,string,int -> intといった普通の基本型や関数型に加えて，&(...)で表される "1つ上のステージのコードを表す型" を導入している．例えば，stage 0 での &int型というのは，"stage 1 でintとして評価されるコードの型" である．

ステージ間に関する型の規則として次の2つが要求される．

stage 1でτ型の値が要求される部分にstage 0のコードの埋め込み~(exp)がある場合，expはstage 0で&τ型が付かなければならない．
stage 0で&τ型の値が要求される部分にstage 1のコードの埋め込み&(exp)がある場合，expはstage 1でτ型が付かなければならない．

このような型システムによって，stage 0のプリプロセスによって生成されたstage 1のコードが正しく型付けされたコードになっていることが保証される．

少し複雑な例

次のようなプログラムを考える．

% stage 1
let n = 100 in
  ~( let double x = &(~x + ~x) in double &n )

それぞれの変数のステージと型をまとめると，次のようになっている．

n: stage 1のint
x: stage 0のint&
double: stage 0の&int -> &int

基本として，stage 0の変数はstage 0のコード中でしか使えないし，stage 1の変数はstage 1のコード中でしか使えない．特に，stage 0中の&τ型の変数と，stage 1中のτ型の変数は別物であるという点に注意しておくべきだろう．

中身について少し詳しく見てみる．まずは関数定義を見てみる．

% stage 0
let double x = &(~x + ~x)

&(...)に囲まれた部分はstage 1のコードであるから，~x + ~xをstage 1の式として解釈する． +は左右にintをとり，int型の値を返す二項演算子であるから，~xや~x + ~xはstage 1でint型が付かなければならない．従って上に述べた型付け規則から，xはstage 0で&int型が付かなければならない． &(~x + ~x)はstage 0で&int型の値であるから，doubleの型は&int -> &intである．

次に関数適用に注目する．

% stage 0
double &n

nはstage 1でint型の変数として宣言されているので，&nはstage 0で&int型の値である．

doubleの定義を思い出すと，stage 0は次のように評価される．

~(double &n)
-> ~(&(~(&n) + ~(&n)))
-> ~(&(n + n))
-> (n + n)

つまり，元のプログラムはstage 0のプリプロセスが終わると，全体let n = 100 in (n + n)というstage 1のプラグラムになっていることがわかる．

もう少し実用的な例: 累乗関数の生成

プリプロセスの目的として，エラー報告の迅速化以外だけでなく，事前計算による高速化がある．下の関数はpower 3のように書くことで(fun x -> x * x * x * 1)のようなコードを生成し，実行時の再帰をなくすことで処理が高速化できることが期待される．

@stage: 0

let power n =
  let-rec aux n x =
    if n <= 0 then &1 else &(~x * ~(aux (n - 1) x))
  in
  &(fun x -> ~(aux n &x))

power 3の評価の様子を下に示す．

power 3
-> &(fun x -> ~(aux 3 &x))
-> &(fun x -> ~(if 3 <= 0 then &1 else &(~(&x) * ~(aux (3 - 1) &x))))
-> &(fun x -> ~(&(x * ~(aux 2 &x))))
-> &(fun x -> ~(&(x * ~(if 2 <= 0 then &1 else &(~(&x) * ~(aux (2 - 1) &x))))))
-> &(fun x -> ~(&(x * ~(&(x * ~(aux 1 &x))))))
-> &(fun x -> ~(&(x * ~(&(x * ~(if 1 <= 0 then &1 else &(~(&x) * ~(aux (1 - 1) &x))))))))
-> &(fun x -> ~(&(x * ~(&(x * ~(&(x * ~(aux 0 &x))))))))
-> &(fun x -> ~(&(x * ~(&(x * ~(&(x * ~(if 0 <= 0 then &1 else ~(aux (0 - 1) &x)))))))))
-> &(fun x -> ~(&(x * ~(&(x * ~(&(x * ~(&1))))))))
-> &(fun x -> ~(&(x * ~(&(x * ~(&(x * 1)))))))
-> &(fun x -> ~(&(x * ~(&(x * (x * 1))))))
-> &(fun x -> ~(&(x * (x * (x * 1)))))
-> &(fun x -> (x * (x * (x * 1))))
~(power 3)
-> ~(&(fun x -> (x * (x * (x * 1)))))
-> (fun x -> (x * (x * (x * 1))))

stage 0 から stage 1 への値の移動

stage 0で何らかの計算を行ってその結果をstage 1のコード中で使いたいとする．例えば，stage 0で足し算を行うなら~(1 + 2)のように記述すれば良いが，結果として出てくる3はstage 0のintであってstage 1のintではないのでそのままではstage 1のコード中に埋め込めない．

このようなとき，lift-string : int -> &intというプリミティブを使うと，stage 0における計算結果をstage 1に埋め込めるようにすることができる．上の例であれば ~(lift-int (1 + 2))とすればlift-int (1 + 2) = lift-int 3が評価され，"3を表すstage 1のコード" を埋め込むことができる．

現状は，lift-int,lift-float,lift-string,lift-lengthの4つのプリミティブが提供されているが，将来的には任意の型に使えるlift : 'a -> &'aに置き換わる可能性がある．

汎用のliftが無い場合でも，たとえばlist型のlift関数は次のようにして実装できる．

@stage: 0
@require: list

let lift-list liftf lst =
  let codeacc =
    lst |> List.fold-left (fun codeacc x ->
             &(~(liftf x) :: ~codeacc))
             &[]
  in
  &(List.reverse ~codeacc)