mimium
ツリー形式からBasicBlockのインストラクション形式に変える
Stateのこととupvalueを両方処理しなくてはならない。ワンパスで処理できるのか？
StateSize計算とUpvalue計算の両方をtraitとして切り出す方がいいのかな
値
\begin{align}<!-- line:16 -->
v \; ::= & \quad R \\<!-- line:17 -->
| & (\lambda x:\tau.e, [\Gamma, x:e],StateStorage(p,Vec)) \quad & [Closure]\\<!-- line:18 -->
\end{align}<!-- line:19 -->
$$<!-- line:20 -->
<!-- line:21 -->
$$<!-- line:22 -->
\begin{align}<!-- line:23 -->
e \; ::=& \quad x \quad x \in \mathbb{V} \quad & [value]\\<!-- line:24 -->
|& \quad \lambda x.e \quad & [lambda]\\<!-- line:25 -->
|& \quad e \; e \quad & [app（global,stateful)]\\<!-- line:26 -->
|& \quad appcls \; e \; e \quad & [appclosure]\\<!-- line:27 -->
|& \quad fix \; x.e \quad & [fixpoint]\\<!-- line:28 -->
|& \quad getstate \; e \; I_n \; I_s \quad & [feed] \\<!-- line:29 -->
|& \quad delay \; e \; e & [delay]\\<!-- line:30 -->
\end{align}<!-- line:31 -->
$$<!-- line:32 -->
<!-- line:33 -->
結局[[The w-calculus a synchronous framework for the verified modelling of digital signal processing algorithms|W計算]]のStaged Interpreterと変わらんかもな<!-- line:34 -->
<!-- line:35 -->
そうすると型付けの時点でクロージャ相当の項とグローバル関数適用の項は分かれることになる?エフェクトとして考えるのが妥当なのかな<!-- line:36 -->
<!-- line:37 -->
## 型<!-- line:38 -->
<!-- line:39 -->
$$<!-- line:40 -->
\begin{align}<!-- line:41 -->
\tau ::=&\quad R_a \quad & a \in \mathbb{N}\\<!-- line:42 -->
|&\quad I_n \quad &n \in \mathbb{N} \\\<!-- line:43 -->
|&\quad \tau → \tau \quad \\<!-- line:44 -->
% |&\quad \langle \tau \rangle<!-- line:45 -->
\end{align}<!-- line:46 -->
$$<!-- line:47 -->
<!-- line:48 -->
## コンパイル<!-- line:49 -->
<!-- line:50 -->
Valueとして、次のようなものがあり得る<!-- line:51 -->
<!-- line:52 -->
```rust
struct VRegister(usize);//Vregisterは無限に使用できてサイズ可変<!-- line:54 -->
struct StackSlot(usize);<!-- line:55 -->
enum Value{<!-- line:56 -->
Static(usize),<!-- line:57 -->
Global(usize),<!-- line:58 -->
Function(usize),<!-- line:59 -->
ExternalItem(usize),<!-- line:60 -->
Register(VRegister),<!-- line:61 -->
StackSlot(StackSlot),//引数とかはこれで処理して良い<!-- line:62 -->
}<!-- line:63 -->
```
<!-- line:65 -->
原則、Letが出てくればStackSlotに確保、そうでない一次変数はRegisterに確保でよい<!-- line:66 -->
LetだけどRegisterに逃がせるとか、RegisterからStackへスピルするとかはオプティマイザの範疇<!-- line:67 -->
基本的にはFuncProtoはValueに依存しない構造にしたい<!-- line:68 -->
<!-- line:69 -->
今はmir::ValueにmirgenとBytecodeGen両方が依存しているが、Valueは本来Expr→MIR生成時に使われるだけの中間的な値であるべき<!-- line:70 -->
<!-- line:71 -->
```rust
struct MIR{<!-- line:73 -->
name:Symbol,<!-- line:74 -->
static_data:Vec<StaticData><!-- line:75 -->
externals:<ExternalItems><!-- line:76 -->
functions:Vec<FuncProto><!-- line:77 -->
}<!-- line:78 -->
<!-- line:79 -->
struct Operation{<!-- line:80 -->
dest:Option<VRegister>,<!-- line:81 -->
inst:Instruction<!-- line:82 -->
}<!-- line:83 -->
struct UpIndex(FnId,usize)<!-- line:84 -->
struct UpIndexStorage(Vec<StackSlot>)<!-- line:85 -->
<!-- line:86 -->
impl UpIndexStorage{<!-- line:87 -->
fn get_upv_index(&self,i:UpIndex)->Option<StackSlot>{<!-- line:88 -->
self.0.get(i.0)<!-- line:89 -->
}<!-- line:90 -->
}<!-- line:91 -->
struct BlockId(usize)<!-- line:92 -->
struct BasicBlock{<!-- line:93 -->
label:Symbol,<!-- line:94 -->
entry_v:Vec<BlockId><!-- line:95 -->
op:Vec<Operation><!-- line:96 -->
}<!-- line:97 -->
struct BlockChunk(Vec<Block>)<!-- line:98 -->
impl BlockChunk{ /*newtype pattern*/ }<!-- line:99 -->
struct FuncProto{<!-- line:100 -->
name: Symbol,<!-- line:101 -->
upindexes: UpIndexStorage,<!-- line:102 -->
blocks: BlockChunk,<!-- line:103 -->
state_tree: Vec<StateLeaf> //StateTreeは実際のデータを保持しない<!-- line:104 -->
meta_labels:BTreeMap<StackSlot,Symbol> //print用メタデータ<!-- line:105 -->
}<!-- line:106 -->
<!-- line:107 -->
enum Instruction{<!-- line:108 -->
Load(StackSlot,Type)<!-- line:109 -->
Store{dest:StackSlot,src:Register,Type},<!-- line:110 -->
GetUpValue(UpIndex,Type),<!-- line:111 -->
JmpIf{cond:Register,then:BlockId,else_:BlockId,merge:BlockId},<!-- line:112 -->
ShiftStatePos(isize)//ツリーの子インデックスに対するカーソル移動オフセット<!-- line:113 -->
GetState(Type)<!-- line:114 -->
//その他、プリミティブな命令はfrom Register to Register<!-- line:115 -->
}<!-- line:116 -->
<!-- line:117 -->
```
<!-- line:119 -->
評価をしながら副作用としてMIRを書き込んでいくような感じ<!-- line:120 -->
<!-- line:121 -->
```rust
fn eval(e:ExprNodeId,env:Env<(Value,Type)>)->(Value,Type){<!-- line:123 -->
match e.to_expr() {<!-- line:124 -->
Expr::Id(name)=>{<!-- line:125 -->
match env.lookup(name){<!-- line:126 -->
(Value::Register(r),t)=>(r,t)<!-- line:127 -->
(Value::StackSlot(s),t)=>push_inst(Instruction::Load(s,t))<!-- line:128 -->
}<!-- line:129 -->
<!-- line:130 -->
},<!-- line:131 -->
Expr::Let(name,e,body)=>{<!-- line:132 -->
let env = env.extend((name,eval(e,env).0));<!-- line:133 -->
eval(e,env)<!-- line:134 -->
},<!-- line:135 -->
Expr::App(e,args)=>{<!-- line:136 -->
let (f,ft) = eval(e,env);<!-- line:137 -->
let argvs = args.iter().map(|e| eval(e,env));<!-- line:138 -->
match f{<!-- line:139 -->
Value::Closure(fproto,names,body,env)=>{<!-- line:140 -->
let kvs = names.iter().zip(argvs.zip()).collect()<!-- line:141 -->
let env = env.extend(kvs);<!-- line:142 -->
eval(body,env)<!-- line:143 -->
}<!-- line:144 -->
_=>panic!()<!-- line:145 -->
}<!-- line:146 -->
}<!-- line:147 -->
Expr::Feed(id,body)=>{<!-- line:148 -->
<!-- line:149 -->
}<!-- line:150 -->
}<!-- line:151 -->
<!-- line:152 -->
}<!-- line:153 -->
<!-- line:154 -->
```