memo mimium programming-language
多段階計算を取り入れたい → 多段階計算を命令型VMインストラクションで表現したい
とりあえずW Calculusを自然に拡張してみる。 Calculusとmimiumの形式は似ているが、主に2つの違いがある。
- Calculus はLinear-Time Invariant なシステムを想定しているため、基本演算は項の加算と、項と定数の乗算しか使えない。
- Calculusでは関数が数をとって数を返すものしかない。つまり、関数やfeedの項を取ったり返すような高階関数は想定されていない。
問題になるのは後者の方だ。
型
n以下の自然数 (ディレイのbounded access用)
\begin{align}<!-- line:25 --> \tau ::=&\quad R_a \quad & a \in \mathbb{N}\\<!-- line:26 --> |&\quad I_n \quad &n \in \mathbb{N} \\\<!-- line:27 --> |&\quad \tau → \tau \quad &a,b \in \mathbb{N}\\<!-- line:28 --> % |&\quad \langle \tau \rangle<!-- line:29 --> \end{align}<!-- line:30 --> $$<!-- line:31 --> とりあえず1要素のタプルと普通のRは区別しないことにする<!-- line:32 --> (そしてよく見るとこれは関数→関数のような高階関数を許してないんだな)<!-- line:33 --> そうか高階関数を考えなければクロージャを考慮する必要もないものな<!-- line:34 --> <!-- line:35 --> <!-- line:36 --> [[ブロックとサンプルの互換性]]をどうするかが問題？<!-- line:37 --> <!-- line:38 --> ## 値<!-- line:39 --> <!-- line:40 --> 一旦タプルについては考えないことにしよう<!-- line:41 --> <!-- line:42 --> <!-- line:43 --> <!-- line:44 --> $$<!-- line:45 --> \begin{align}<!-- line:46 --> v \; ::= & \quad R \\<!-- line:47 --> | & \quad \lambda x:\tau.e \quad & [lambda]\\<!-- line:48 --> |& \quad feed \; x.e \quad & [feed] \\<!-- line:49 --> \end{align}<!-- line:50 --> $$<!-- line:51 --> ## 項<!-- line:52 --> <!-- line:53 --> <!-- line:54 --> $$<!-- line:55 --> \begin{align}<!-- line:56 --> e \; ::=& \quad x \quad x \in \mathbb{V} \quad & [value]\\<!-- line:57 --> |& \quad \lambda x.e \quad & [lambda]\\<!-- line:58 --> |& \quad e \; e \quad & [app]\\<!-- line:59 --> |& \quad fix \; x.e \quad & [fixpoint]\\<!-- line:60 --> |& \quad feed \; x.e \quad & [feed] \\<!-- line:61 --> |& \quad delay \; e \; e & [delay]\\<!-- line:62 --> \end{align}<!-- line:63 --> $$<!-- line:64 --> <!-- line:65 --> 基本演算（Intrinsic）は直感に任せる<!-- line:66 --> <!-- line:67 --> 本来はfixの中でfeedを使ったり、feedの中でfixを使うとエラーだが、結局シンタックスレベルでは排除できないので型でエラーとして弾くことにする…？<!-- line:68 --> いや値レベルでの切り分けは不可能なので、こうする<!-- line:69 --> <!-- line:70 --> <!-- line:71 --> <!-- line:72 --> ## 実例<!-- line:73 --> <!-- line:74 --> <!-- line:75 --> ```rust fn cascade(order:int,fb)->(float->float){<!-- line:77 --> if(order>0){<!-- line:78 --> |x|{<!-- line:79 --> cascade(order-1)(x) *(1-fb) + self*fb <!-- line:80 --> }<!-- line:81 --> }else{<!-- line:82 --> |x| x<!-- line:83 --> }<!-- line:84 --> }<!-- line:85 --> ``` <!-- line:87 --> <!-- line:88 --> ちょっとわかりやすさのために`self`を使わずfeedにしてみる<!-- line:89 --> <!-- line:90 --> ```rust fn cascade(order:int,fb)->(float->float){<!-- line:92 --> if(order>0){<!-- line:93 --> |x|{<!-- line:94 --> feed(y) { cascade(order-1)(x) *(1-fb) + y*fb }<!-- line:95 --> }<!-- line:96 --> }else{<!-- line:97 --> |x| x<!-- line:98 --> }<!-- line:99 --> }<!-- line:100 --> ``` <!-- line:102 --> あー、今までは`fn(x)`でself使うものを`feed(self).lambda(x).e,`って感じに自動的に変換してたけど、変換するとしたら`lambda(x).feed(x).e`の方が良かったってことなんだな<!-- line:103 --> <!-- line:104 --> これを`cascade(3,0.9)`とかで簡約してみるか<!-- line:105 --> <!-- line:106 --> ```rust cascade(3,0.9)<!-- line:108 --> <!-- line:109 --> |x|{<!-- line:110 --> let res = cascade(2)(x);<!-- line:111 --> feed(y) { res*0.1 + y*0.9 }<!-- line:112 --> }<!-- line:113 --> |x1|{<!-- line:114 --> let res1 =|x2|{<!-- line:115 --> let res2 = cascade(1)(x2);<!-- line:116 --> feed(y2) { res2*0.1 + y2*0.9 }<!-- line:117 --> }(x1);<!-- line:118 --> feed(y1) { res1*0.1 + y1*0.9 }<!-- line:119 --> }<!-- line:120 --> |x1|{<!-- line:121 --> let res1 =|x2|{<!-- line:122 --> let res2 = |x3|{<!-- line:123 --> let res3 = cascade(0)(x3);<!-- line:124 --> feed(y3) { res3*0.1 + y3*0.9 }<!-- line:125 --> }(x2);<!-- line:126 --> feed(y2) { res2*0.1 + y2*0.9 }<!-- line:127 --> }(x1);<!-- line:128 --> feed(y1) { res1*0.1 + y1*0.9 }<!-- line:129 --> }<!-- line:130 --> |x1|{<!-- line:131 --> let res1 =|x2|{<!-- line:132 --> let res2 = |x3|{<!-- line:133 --> let res3 = |x|{x}(x3);<!-- line:134 --> feed(y3) { res3*0.1 + y3*0.9 }<!-- line:135 --> }(x2);<!-- line:136 --> feed(y2) { res2*0.1 + y2*0.9 }<!-- line:137 --> }(x1);<!-- line:138 --> feed(y1) { res1*0.1 + y1*0.9 }<!-- line:139 --> }<!-- line:140 --> |x1|{<!-- line:141 --> let res1 =|x2|{<!-- line:142 --> let res2 = |x3|{<!-- line:143 --> let res3 = x3;<!-- line:144 --> feed(y3) { res3*0.1 + y3*0.9 }<!-- line:145 --> }(x2);<!-- line:146 --> feed(y2) { res2*0.1 + y2*0.9 }<!-- line:147 --> }(x1);<!-- line:148 --> feed(y1) { res1*0.1 + y1*0.9 }<!-- line:149 --> }<!-- line:150 --> |x1|{<!-- line:151 --> let res1 =|x2|{<!-- line:152 --> let res2 = |x3|{<!-- line:153 --> feed(y3) { x3*0.1 + y3*0.9 }<!-- line:154 --> }(x2);<!-- line:155 --> feed(y2) { res2*0.1 + y2*0.9 }<!-- line:156 --> }(x1);<!-- line:157 --> feed(y1) { res1*0.1 + y1*0.9 }<!-- line:158 --> }<!-- line:159 --> |x1|{<!-- line:160 --> let res1 =|x2|{<!-- line:161 --> let res2 = feed(y3) { x2*0.1 + y3*0.9 };<!-- line:162 --> feed(y2) { res2*0.1 + y2*0.9 }<!-- line:163 --> }(x1);<!-- line:164 --> feed(y1) { res1*0.1 + y1*0.9 }<!-- line:165 --> }<!-- line:166 --> |x1|{<!-- line:167 --> let res1 =|x2|{<!-- line:168 --> feed(y2) { feed(y3) { x2*0.1 + y3*0.9 } *0.1 + y2*0.9 }<!-- line:169 --> }(x1);<!-- line:170 --> feed(y1) { res1 *0.1 + y1*0.9 }<!-- line:171 --> }<!-- line:172 --> |x1|{<!-- line:173 --> let res1 = feed(y2) { feed(y3) { x1 *0.1 + y3*0.9 } *0.1 + y2*0.9 };<!-- line:174 --> feed(y1) { res1 *0.1 + y1*0.9 }<!-- line:175 --> }<!-- line:176 --> |x1|{<!-- line:177 --> feed(y1) { <!-- line:178 --> feed(y2) { <!-- line:179 --> feed(y3) { x1*0.1 + y3*0.9} *0.1 + y2*0.9 }*0.1 + y1*0.9 }<!-- line:180 --> }<!-- line:181 --> ``` <!-- line:183 --> feedの項に対する加算とか乗算の計算は簡約がしづらいなあ<!-- line:184 --> <!-- line:185 --> 時間0の時のyは全て0として、<!-- line:186 --> <!-- line:187 --> ```rust |x1,y1_ref,y2_ref,y3_ref| {<!-- line:189 --> let y1 = *y1_ref;<!-- line:190 --> let y1_next= {<!-- line:191 --> let y2 = *y2_ref;<!-- line:192 --> let y2_next = {<!-- line:193 --> let y3 = *y3_ref;<!-- line:194 --> let y3_next = x1*0.1 + y3*0.9;<!-- line:195 --> *y3_ref = y3_next;<!-- line:196 --> y3_next<!-- line:197 --> }*0.1 + y2*0.9;<!-- line:198 --> *y2_ref = y2_next;<!-- line:199 --> y2_next }*0.1 + y1*0.9;<!-- line:200 --> *y1_ref = y1_next;<!-- line:201 --> y1_next<!-- line:202 --> }<!-- line:203 --> ``` <!-- line:205 --> やっぱdenotationalの方が定義しやすいかもなあ<!-- line:206 --> <!-- line:207 --> ああでもfeedを無事に展開できるということは、feedの項に対して`Cell`を割り当てることそのものには間違いはないのか<!-- line:208 --> <!-- line:209 --> ただ、例えばFeedの項の中に関数が残っちゃうような可能性もあるため、Feedのhistoryの中にLambdaの項が保存されるような状況が回避できない。<!-- line:210 --> <!-- line:211 --> 型付規則の中でfeed x.eのeがプリミティブというか、Boxedにならないものしか取れないようにすればいいのかね。そうするとValueはCopyトレイトを実装できて、feedの中に実際にはラムダが入ってたとしても、簡約後は必ずValueになっていると<!-- line:212 --> <!-- line:213 --> ## 型（改正版）<!-- line:214 --> <!-- line:215 --> というわけで型の定義再訪<!-- line:216 --> <!-- line:217 --> $$<!-- line:218 --> \begin{align}<!-- line:219 --> \tau_p ::=&\quad R_a \quad & a \in \mathbb{N}\\<!-- line:220 --> |&\quad I_n \quad &n \in \mathbb{N} \\<!-- line:221 --> \tau :: = &\quad \tau_p\\<!-- line:222 --> |&\quad \tau → \tau \quad &a,b \in \mathbb{N}\\<!-- line:223 --> % |&\quad \langle \tau \rangle<!-- line:224 --> \end{align}<!-- line:225 --> $$<!-- line:226 --> <!-- line:227 --> でラムダ抽象とFeedの型付け規則こういう感じになると<!-- line:228 --> <!-- line:229 --> $$<!-- line:230 --> \frac{\Gamma, x:\tau^a \vdash e:\tau^b}{\Gamma \vdash \lambda x.e:\tau^a \to \tau^b }<!-- line:231 --> $$<!-- line:232 --> $$<!-- line:233 --> \frac{\Gamma, x : \tau_p^a \vdash e: \tau_p^a }{\Gamma \vdash feed\ x.e:\tau_p^a}<!-- line:234 --> $$<!-- line:235 --> <!-- line:236 --> タプルとかレコードもできるけど、関数をタプルの要素にしたりはできない（できないでもないけど、「そういう型をとれるタプル」と「そういうのできないタプル」を分けて考える必要がある）、って感じでユーザーにはややこしいですねえ<!-- line:237 --> <!-- line:238 --> ## Feedのスコープと簡約の順番について<!-- line:239 --> <!-- line:240 --> ところでさっきの`cascade`関数ってさ、わざわざ高階関数にせず一括でやれるんですかね、<!-- line:241 --> <!-- line:242 --> ```rust fn cascade_f(order:int,fb,x)->float{<!-- line:244 --> letrec cascade = if(order>0){<!-- line:245 --> |x|{<!-- line:246 --> cascade(N-1)(x) *(1-fb) + self*fb <!-- line:247 --> }<!-- line:248 --> }else{<!-- line:249 --> |x| x<!-- line:250 --> }<!-- line:251 --> cascade(x)<!-- line:252 --> }<!-- line:253 --> <!-- line:254 --> let res = cascade_f(3,0.9,input)<!-- line:255 --> ``` <!-- line:257 --> ともあれコピーキャプチャのクロージャでも問題はなさそうだけども、この状態だと`cascade`のfeedのコンテキストは毎サンプル終了しちゃうって感じなんだよね<!-- line:258 --> <!-- line:259 --> <!-- line:260 --> ## VMのインストラクションとデータ構造<!-- line:261 --> <!-- line:262 --> ```rust type Ref = u8;<!-- line:264 --> enum UpIndex{<!-- line:265 --> Local(Reg),<!-- line:266 --> UpValue(u64)<!-- line:267 --> }<!-- line:268 --> struct FuncProto{<!-- line:269 --> instructons: Vec<Instruction>,<!-- line:270 --> constants: Vec<RawVal>,<!-- line:271 --> upvalue_idxs: Vec<UpIndex>,<!-- line:272 --> feed_idx: Vec<u64><!-- line:273 --> }<!-- line:274 --> ``` <!-- line:276 --> この関数だけだとfeedidをどうつければいいかなあ<!-- line:277 --> <!-- line:278 --> ```rust fn filterbank(N,input,lowestfreq, margin,filter){<!-- line:280 --> if(N>0){<!-- line:281 --> let freq = lowestfreq+N*margin;<!-- line:282 --> return filter(input,freq)<!-- line:283 --> + filterbank(N-1,input,lowestfreq,margin,filter)<!-- line:284 --> }else{<!-- line:285 --> return 0<!-- line:286 --> }<!-- line:287 --> }<!-- line:288 --> fn lowpass(input,fb){<!-- line:289 --> input* (1-fb) + self * fb<!-- line:290 --> }<!-- line:291 --> let lowpass = |input,fb|{feed(y) { <!-- line:292 --> input* (1-fb) + y * fb<!-- line:293 --> }} }<!-- line:294 --> let lowpass = |input,fb,ref_y|{<!-- line:295 --> let res = input* (1-fb)+ deref(ref_y)*fb<!-- line:296 --> ref_y := res<!-- line:297 --> res<!-- line:298 --> }<!-- line:299 --> res = filterbank(3,input,100,2000,2.0,lowpass)<!-- line:300 --> ``` <!-- line:302 --> lowpassは最終的にlambda{feed{self}}的な感じになるが、それはfilterbankの中で呼ばれるまではわからない<!-- line:303 --> lowpassのバイトコードはこんな感じか<!-- line:304 --> ``` lowpass: //stack 0:input, 1: fb<!-- line:306 --> moveconst 2 0<!-- line:307 --> sub 3 1 2<!-- line:308 --> getfeed 4<!-- line:309 --> mult 5 2 4<!-- line:310 --> add 6 3 5<!-- line:311 --> retfeed 6 1<!-- line:312 --> const:<!-- line:313 --> 1_i64<!-- line:314 --> upindexes:<!-- line:315 --> //nothing<!-- line:316 --> ``` <!-- line:318 --> ``` global_ftable:<!-- line:320 --> lowpass<!-- line:321 --> filterbank<!-- line:322 --> <!-- line:323 --> filterbank: //stack 0:N,1:input,2:lfreq,3:margin,4:filter<!-- line:324 --> moveconst 5 0<!-- line:325 --> gt 6 0 5<!-- line:326 --> jmpifneg 6 16<!-- line:327 --> mult 6 0 3<!-- line:328 --> add 7 2 0<!-- line:329 --> move 6 6 7<!-- line:330 --> move 7 4 // get filter <!-- line:331 --> move 8 1<!-- line:332 --> move 9 6<!-- line:333 --> callcls 7 2 1 //result on stack 7<!-- line:334 --> moveconst 8 1<!-- line:335 --> sub 9 0 8<!-- line:336 --> move 10 -1 // get recursive call<!-- line:337 --> move 11 9 // prepare arguments...<!-- line:338 --> move 12 1<!-- line:339 --> move 13 2<!-- line:340 --> move 14 3<!-- line:341 --> closure 15 4 // hof requires all function should be closure<!-- line:342 --> call 10 5 1 //recursive call, result on stack 10<!-- line:343 --> add 0 7 10<!-- line:344 --> jmp 1<!-- line:345 --> moveconst 0 0<!-- line:346 --> ret 0 1<!-- line:347 --> const:<!-- line:348 --> 0_i64 <!-- line:349 --> -1_u64<!-- line:350 --> ``` <!-- line:352 --> feedが呼ばれた時にどのfeedidかを判別するのはランタイム側の役目<!-- line:353 --> <!-- line:354 --> --- <!-- line:356 --> ```rust fn cascade_f(order:int,fb,x)->float{<!-- line:358 --> letrec cascade = if(order>0){<!-- line:359 --> |x|{<!-- line:360 --> cascade(N-1)(x) *(1-fb) + self*fb <!-- line:361 --> }<!-- line:362 --> }else{<!-- line:363 --> |x| x<!-- line:364 --> }<!-- line:365 --> cascade(x)<!-- line:366 --> }<!-- line:367 --> fn phasor(freq)->float{<!-- line:368 --> 1+self<!-- line:369 --> }<!-- line:370 --> fn doubleosc(freq)->freq{<!-- line:371 --> phasor(freq)+phasor(freq+10)<!-- line:372 --> }<!-- line:373 --> let res = cascade_f(3,0.9,input)+doubleosc(440)<!-- line:374 --> ``` <!-- line:376 --> なんかこんな感じだとして、レキシカルに何番目の関数呼び出しか、<!-- line:377 --> <!-- line:378 --> [[mimiumの中間表現を考える]]<!-- line:379 -->