ちょーありがちなサンプル．
階乗 factorial を計算する等価変換ルール
(fact 0 *F) --> (= *F 1). // fact 0 = 1
(fact *N *F),
{(> *N 0)}
-->
(:= *N1 (- *N 1)), // n--;
(fact *N1 *F1),
(:= *F (x *F1 *N)). // fact n = n * fact n - 1
を末尾再帰で書くと，
(fact 0 *A *F) --> (= *F *A).
(fact *N *A *F)--> (:= *N1 (- *N 1)), (:= *A1 (x *A *N)), (fact *N1 *A1 *F).
こんな感じになる．
*A は途中結果を保持しておく accumulater．初期値は 1 だから，(fact 10 1 ?) みたいな呼び出し方になる．
# インタフェースがわかり難いから，Prolog とかでは普通 (fact *N *X) --> (fact *N 1 *X). みたいなラッパをかます．
んで，これが ETI に読み込まれると，内部的には S 式で保持されてる．
(as (fact 0 *A *B) : (= *B *A))
(as (fact *C *D *E) : (:= *F (- *C 1)) (:= *G (x *D *C)) (fact *F *G *E))
S 式 + パターンマッチ + 論理変数さえあれば，そうとういろんなことがやりたい放題．
そして，こいつをいろいろゴニョゴニョプログラム変換して (一応企業秘密)，部分評価 (まだ unfold 程度) して，出てきたプリミティブな D ルールは，こんな感じ．
(as (fact3 *Q *R *S) :
(fact31 *Q *R *S))
(as (fact31 *T *U *V)
(not (== (n 0) 1 *T *U *V)) :
(deref 2 *T *U *V (n *W))
(deref 1 *T *U *V (n *X))
(:= *Y (x *W *X))
(:= *A2 (+ 2 *T))
(getArrayElement *U *A2 *B2)
(setArrayElement *V *B2 (n *Y))
(deref 1 *T *U *V (n *B1))
(:= *D1 (- *B1 1))
(:= *C2 (+ 1 *T))
(getArrayElement *U *C2 *D2)
(setArrayElement *V *D2 (n *D1))
(fact31 *T *U *V))
(as (fact31 *F1 *G1 *H1) :
(:= *I1 (+ 2 *F1))
(getArrayElement *G1 *I1 *J1)
(:= *K1 (+ 3 *F1))
(getArrayElement *G1 *K1 *L1)
(setArrayElement *H1 *L1 (p *J1))
(getArrayElement *G1 *F1 *M1)
(:= *N1 (+ *M1 1))
(setArrayElement *G1 *N1 TRUE)
(setArrayElement *G1 0 *M1))
(as (fact32 *O1 *P1 *Q1) :
(deref 2 *O1 *P1 *Q1 (n *R1))
(deref 1 *O1 *P1 *Q1 (n *S1))
(:= *T1 (x *R1 *S1))
(:= *E2 (+ 2 *O1))
(getArrayElement *P1 *E2 *F2)
(setArrayElement *Q1 *F2 (n *T1))
(deref 1 *O1 *P1 *Q1 (n *V1))
(:= *X1 (- *V1 1))
(:= *G2 (+ 1 *O1))
(getArrayElement *P1 *G2 *H2)
(setArrayElement *Q1 *H2 (n *X1))
(fact31 *O1 *P1 *Q1))
ここまでくると，何もかも展開されて融合してるから，わけがわかりませんが… この何段階か前のレイヤーまでは，ランタイムルールが機能ごとに分割されていて，もう少し抽象度が高いです．
(全て私が手書きしたのですから，当たり前ですが．全部こんな素の，機械語レベル (見た目は S 式ですが，やってることはデータ参照と算術計算と配列操作のみ) のビルトインルール剥き出しで書かれていたら，保守拡張できるわけがありません．出ているのは，あくまでも最終結果のみです)
これをテキトーに fold して (ETI の上で動かしていろいろするために unfold していたのを，余計な中間変数を排除して，C コンパイラに最適化をがんばってもらうために再び fold) C にトランスレートすると，こんな感じになる．
#include "et.h"
void fact3(word base, word stack[], word heap[]) {
goto fact31;
fact31 :
if(ideref(1, base, stack, heap) == 0)
goto fact311;
heap[stack[2 + base]] = INT;
heap[stack[2 + base] + 1] = ideref(2, base, stack, heap) * ideref(1, base, stack, heap);
heap[stack[1 + base]] = INT;
heap[stack[1 + base] + 1] = ideref(1, base, stack, heap) - 1;
goto fact31;
fact311 :
heap[stack[3 + base]] = PTR;
heap[stack[3 + base] + 1] = stack[2 + base];
stack[stack[base] + 1] = INT;
stack[stack[base] + 1 + 1] = 1;
stack[0] = stack[base];
return;
fact32 :
heap[stack[2 + base]] = INT;
heap[stack[2 + base] + 1] = ideref(2, base, stack, heap) * ideref(1, base, stack, heap);
heap[stack[1 + base]] = INT;
heap[stack[1 + base] + 1] = ideref(1, base, stack, heap) - 1;
goto fact31;
}
C 言語って，本当に記述が簡潔な言語ですよね (笑)
ここでは末尾再帰になってるから，単なる goto しか出てこないけど，一般的には(再帰的)関数コールのためのスタックポインタ (base) のシフトとかいろいろやらないといけない．
んで，こいつをテキトーにファイルに出力して gcc -shared fact3.c -o fact3.dll とかコンパイルして共有 dl が生成されます．
そして，これをインタフェース etc から動的に呼び出すことができます．もちろん etc の再コンパイルは一切必要なし (とりあえｚ，同じディレクトリの中に lib ってディレクトリが切ってあって，その中にいろんなコンパイル済み dll が入っている)．
$ LD_LIBRARY_PATH=./lib ./etc
[D] > (fact 10 1 ?)
----------------------------------------------------------
Dynamic linking : fact3.dll
call : fact3
Remove : fact3.dll
// 結果の表示 (デバッグ用)
{ 4 2 13 18 23 } // スタック (全てヒープへ
のポインタ(配列 index)．先頭は使用長)
{4 fact 0 3628800 3628800} // スタックのプリティプリ
ント
// ヒープ (一つの要素には，ワードに乗るサイズのオブジェ
クトしか書き込めない．型タグとかも，単なる enum)
Array : {29, CONS, SYM, 6, PTR, 12, STR, 4, 'f', 'a',
'c', 't', CONS, INT, 0, PTR, 17, CONS, INT, 3628800,
PTR, 22, CONS, INT, 3628800, NIL, 0, STR, 1, '?'}
// ヒープのプリティプリント
Array : {
length : 29
1 cons
2 (sym (p 6))
4 (p 12)
6 str
7 length : 4
8 "fact"
12 cons
13 (i 0)
15 (p 17)
17 cons
18 (i 3628800)
20 (p 22)
22 cons
23 (i 3628800)
25 ()
27 str
28 length : 1
29 "?"
}
// 結果の S 式表現．面倒なので，引数として与えられたデー
タのコピーとかやってないので，副作用バリバリ．引数が書き
換わっちゃってる．
(fact 0 3628800 3628800)
----------------------------------------------------------
まだ型推論とかメモリイメージの静的解析みたいな，メタ計算 (一番肝心な部分 ！！ 論文になる部分 ！！) は全然やってなくて，変数に型すら再構築してないから deref とかやたら出てきて気持ち悪い．
(なら，もう少し真面目にやってください)
しかも，無駄なラッパルールがそのまま出力されてる．
(でも GCC は賢いから，こういうの人間がぱっと見てわかるレベルの無駄は全部潰してくれる… と良いなぁ)
まぁ，deref は
static inline int ideref(word x, word base, word stack[], word heap[]) {
word ptr = stack[x + base];
while(1) {
if(heap[ptr] == INT)
return heap[ptr + 1];
else if(stack[x + base] == PTR) {
ptr = heap[ptr + 1];
continue;
}
abort();
}
}
みたいな，単なる繰り返し文だから，そんなのコストは高くないとは思うけど (惰性で書いてるけど，たぶん inline 展開できる大きさの関数ではない．無視されるだけ)．
まぁ，今のところ，fact に特化したコードジェネレートとかをしているから，かなりいろんなところを書き直したり追加していかないといけない．
やることが腐るほどありすぎる．一応，ハリボテは出来たかな，というレベル．まだ何にも難しいことはしてない．誰でも手さえ動かせばできること．
というか，バックエンド部分は目的によって適した設計が全然変わってくると思います．
今のところは，どーんと生のメモリの塊 (heap) を reader に渡して，そのワードの配列に S 式を表す文字列を内部形式にエンコードしてそいつを操作するためのポインタを stack に格納して，動的に dll をリンクして関数コールしてあれこれする，というやり方を試してます．
C 言語で直接拡張ライブラリを書くことも可能で，しかも設計思想がシンプルなので，かなり簡単です．
ただし，C 言語で，いろんなライブラリの関数を直接呼び出すような形でプログラミングを行って dll を書くだけでは，柔軟性に乏しくなってしまいます．
できるだけ ET の D ルールでライブラリを書いておけば，部分評価とか融合変換みたいなことが簡単にできて，保守性や拡張性が格段にアップします．
人間ではとてもメンテナンスできないような，goto や switch case だらけの巨大な関数を難なく生成して，一つの dll としてまとめ，一回の関数呼び出しで一つの処理を終わらせることができるようになるので，オーバーヘッドがかなり減ります．
そしてこれらの技術は，将来的には，プログラムの仕様からの自動合成へとつながっていくことになるでしょう．
(わーお，バラ色の未来だね)
(ほんまかいな)
ワンランナーの処理をどれだけ速く処理できるか ? ということしか考えてないので，メモリのアロケートとかは一切行ってません．
最初にがばっと確保して，関数コールして例えば CGI で HTML を出力したら，後は全てまとめてメモリ領域を捨てると．
これにより，GC などのメモリ管理が一切不要になるので，極限までバックエンドがシンプルになります．
まぁ，今時の環境は，死ぬほどメモリあるんだから，ぶっちゃけ 8 割以上の状況では，GC なんて，実はいらなくね ? という逆転の発想です．
一つの処理ごとにメモリをまとめて確保 & 解放，万が一処理の途中で足りなくなったら，realloc みたいな，テキトーなノリでも，大部分は問題無いのではないかと．
このやり方には，メモリリークみたいな，深刻なバグが起こらないというメリットがあります．あと malloc とか new とかは，実は場合によっては GC よりも遅くなるから，なるべくしないのが望ましい．
そんなこんなで，今時の CPU の性能を最大限に生かすため，下手な小細工は行わず，なるべく計算資源を潤沢に使う，富豪さとシンプルさを重視した設計となっております．
(悪魔の辞典 : 作者ができるだけ実装を手抜きするため)
なんと，型タグに word (int32) 一個使うという，傍若無人ぶり．
たかが cons セル一個が，cons tag ･ car tag ･ car value ･ cdr tag ･ cdr value と，word 5 つ，20 byte も使います．
なんともやる気の無い実装．
文字列も，char じゃなくて，内部的には int32 の配列で持ってます．ascii コード前提で reader とか printer が書かれていて，printf とかがハードコードされてるから，全く意味は無いのに．
(なぜ管理人が執拗に UCS-4 にこだわるのか，これでバレちゃったなぁ，えへへ．最小限の修正で無駄を正当化するため ｗ)
ていうか，C 言語が，自由なようでいて全然自由じゃないんだよなぁ．いや，手段はいくらでもあるんですが，どれもこれも泥臭くて変態的なキャストとかビットシフトとかを駆使しないといけないから，私のようなへたれからすればイヤーンな感じ．
こういう変態的なプログラミングをずっとしていると，制約がきつくてきつくて，むしろ機械語を直接書くほうが，ポータビリティは無くなっちゃうけど，楽なんじゃね ? とかいう，どうしようもなく時代錯誤な思想が沸いてきて良くない．
C-- ってどうなんだろうなぁ．全然知らないけど．
まぁ，全部 Byte (char の typedef とか) の配列で持って，無理やり (int)(a + i) とかポインタをキャストして，自前でポインタ演算 (使用バイトぶんだけ Byte 配列 index を進める) して，ってやり方もありだけど…
細かいことばかりにこだわっていないで人間的になろう。 -- Jamie Zawinski
修正が面倒くさくてやる気が起きないintel 32 アーキテクチャでは，効率的にいろいろ疑問が残りますし．
というか，進捗状況をかせいでボスから破門されないためにテキトーにひたすらやっつけでコードを書いていくというのはよくないなぁ，とか思った．
まぁ，うだうだ考えているよりも，手を動かして初めてわかることも多いから，ボスの多少実装至上主義的な考えは正しいとも思う．
一番あたまが痛いのが，レイヤーの設計というか，どこで切り分けるか．
一つのレイヤーで，あんまり最適化をやり過ぎると，他のレイヤーでそれ以上の最適化が困難になったり，十分な最適化がかからなくて，全体的には非効率的になったりしてしまう．
なるべく全体の流れを重視して，いかにして体系的に，自然に滑らかにコードを変換するかを考慮しつつ，それぞれの部分の要素技術もいっぱい勉強しないといけないという．
んで，そういうのが大変だから，ついついトリビアルな実装技術に現実逃避してしまう… orz
| 
