Share
Lambda-mmm: the Intermediate Representation for Synchronous Signal Processing Language Based on Lambda Calculus
This paper proposes Lambda-mmm, a call-by-value, simply typed lambda calculus-based intermediate representation for a music programming language that handles synchronous signal processing and introduces a virtual machine and instruction set to execute Lambda-mmm. Digital signal processing is represented by a syntax that incorporates the internal states of delay and feedback into the lambda calculus.
Lambda-mmm extends the lambda calculus, allowing users to construct generative signal processing graphs and execute them with consistent semantics. However, a challenge arises when handling higher-order functions because users must determine whether execution occurs within the global environment or during DSP execution. This issue can potentially be resolved through multi-stage computation.
Tomoya Matsuura
Transcript
64 slides
-
2024-11-21 International Faust Conference 2024 MATSUURA Tomoya / Tokyo University
of the Arts, Art Media Center([email protected]) λmmm -the Intermediate Representation for Synchronous Signal Processing Language Based on Lambda Calculus -
back in 2017. A fi rst (and perhaps the last
since today) Faust learning meeting in Japan -
Sorry, there were some errors in the typing rules and
example codes on the paper! Corrected version is currently uploaded on Zenodo. https://doi.org/10.5281/zenodo.13855342 -
Agenda 1. Background 2. Syntax of mimium and Lambda-mmm 3.
Naive Operational Semantics of Lambda-mmm 4. VM and bytecode format for Lambda-mmm 5. Discussion -
#BDLHSPVOE • Need of formalization for mimium, lambda-calculus based DSP
language • Formalization of synchronous signal processing languages -
Background 1: Languages for Signal Processing Faust • Block Diagram
Algebra: combining block with in/outs by 5 composition operators • parallel(,) sequential(:) split(<:) merge(:>) recursion(~) • Primitive blocks: constant / arithmetics / delay / conditional* *Faust's conditional evaluate both branch and take either of the results -
Pros and Cons in Faust • + One algorithm can
be translated into multiple platforms: C++/Rust/LLVM IR... • Lacks theoretical compatibility between other general systems like lambda-calculus • - External function call from Faust must be pure • +- Easy to embed Faust to the host, Uneasy to call host's functions • Term-Rewriting Macro is an independent system from BDA • +Can represent complex signal graph with pattern-matching • - Bad macro may causes an error because of in/out mismatch in BDA, but hard to understand the reason for the programmer • - Implicit distinction between signal(number) and compile-time constant integer -
Idea: lambda calculus + minimum primitives for the time operation
Delay and Feedback -
mimium's syntax for feedback fn onepole(x,g){ x*(1.0-g) + self*g }
onepole(x,g) = (1.0 - g) * x + g * _ ~ _; onepole(x,g) = self ~ _ with { self(y) = (1.0 - g) * x + g * y; }; mimium Faust or (Simpli fi ed si.smooth) can refer to the return value of 1 sample before -
Problems in the previous version of mimium • No formal
semantics • Could not compile codes when the higher-order function is used with the stateful function: refers to self or delay somewhere in the call tree • = the allocation size of internal state for the feedback & delay cannot be determined at the compile time • = Impossible to generate a signal graph parametrically • →Re-design & implement the compiler from zero again (Also, I was exhausted to write compiler in C++ and wanted to switch to Rust) -
Prior works on lambda-based DSP language • Kronos[Norilo 2015] •
Based on System-Fω, Type-level computation corresponds to the signal graph generation • No formal semantics(compiler code is the reference) • W-Calculus[Arias et al. 2021], strongly formalized with Coq • No higher-order function / only for linear-time invariant systems W-calculus with loosening these restriction => λmmm -
Prior works on lambda-based DSP language • Kronos[Norilo 2015] •
Based on System-Fω (Type-level lambda abstraction can be used) • Type-level computation corresponds to the signal graph generation • Feedback is represented as a type-level recursive function application • No formal semantics(compiler code is the reference) -
Prior works on lambda-based DSP language • W-Calculus[Arias et al.
2021], strongly formalized with Coq • Introduces "feed" to the lambda calculus that represents feedback with 1 sample delay • "onepole" example can be expressed like • No higher-order function • Lambda abstraction can map from tuple of number, to tuple of number in the type system. • Only Expr + Expr and Constant * Expr are allowed primitive operations for expressing linear time-invariant system (like basic fi lter and reverb) -
Prior works on lambda-based DSP language • W-Calculus[Arias et al.
2021], strongly formalized with Coq • Introduces "feed" to the lambda calculus that represents feedback with 1 sample delay • "onepole" example can be expressed like • No higher-order function • Lambda abstraction can map from tuple of number, to tuple of number in the type system. • Only Expr + Expr and Constant * Expr are allowed primitive operations for expressing linear time-invariant system (like basic fi lter and reverb) W-calculus with loosening these restriction => λmmm -
Scope of This Paper & Compiler Pipeline fn onepole(x,g){ x*(1.0-g)
+ self*g } Source Code Syntax Tree(≒λmmm) Type Inference & MIR Generator LLVM-like SSA MIR CONSTANTS:[1.0] state_size:1 fn onepole(x,g) MOVECONST 2 0 MOVE 3 1 SUBF 2 2 3 MOVE 3 0 MULF 2 2 3 GETSTATE 3 MOVE 4 1 MULF 3 3 4 ADDF 2 2 3 GETSTATE 3 SETSTATE 2 RETURN 3 1 Bytecode Generator Virtual Machine Bytecode Naive Interpreter (Inef fi cient) 2.Syntax 3. Semantics 4. VM & Bytecode Formalization of this part is a future work -
Scope of This Paper & Compiler Pipeline fn onepole(x,g){ x*(1.0-g)
+ self*g } Source Code Syntax Tree(≒λmmm) Type Inference & MIR Generator LLVM-like SSA MIR CONSTANTS:[1.0] state_size:1 fn onepole(x,g) MOVECONST 2 0 MOVE 3 1 SUBF 2 2 3 MOVE 3 0 MULF 2 2 3 GETSTATE 3 MOVE 4 1 MULF 3 3 4 ADDF 2 2 3 GETSTATE 3 SETSTATE 2 RETURN 3 1 Bytecode Generator Virtual Machine Bytecode Naive Interpreter (Inef fi cient) 2.Syntax 3. Semantics 4. VM & Bytecode Formalization of this part is a future work SKIP TODAY -
Syntax of λmmm base on a simply typed, call by
value lambda calculus (Aggregate types like tuple are omitted in this paper.) e ::= x x ∈ vp [value] | λx.e [lambda] | let x = e1 in e2 [let] | fix x.e [fixpoint] | e1 e2 [app] | if (ec ) et else ee [if ] | delay n e1 e2 n ∈ ℕ [delay] | feed x.e [feed] | ... τp ::= R [real] | N [nat] τ ::= τp | τ → τ [function] 7BMVFT 5FSNT vp ::= r r ∈ ℝ | n n ∈ ℕ v ::= vp | cls(λx.e, E) 5ZQFT -
Typing Rule(Excerpt) Γ, x : τa ⊢ e : τb
Γ ⊢ λx.e : τa → τb [T-LAM] Γ ⊢ n : N Γ ⊢ e1 : τ Γ ⊢ e2 : R Γ ⊢ delay n e1 e2 : τ [T-DELAY] Γ, x : τp ⊢ e : τp Γ ⊢ feedx.e : τp [T-FEED] Γ ⊢ ec : R Γ ⊢ et : τ Γ ⊢ ee : τ Γ ⊢ if (ec ) et ee : τ [T-IF] "Allows maps from any type to any type" "Time index must be real number" "Use number instead of boolean for condition" "Feed must not return functional type" -
Typing Rule(Excerpt) Γ, x : τa ⊢ e : τb
Γ ⊢ λx.e : τa → τb [T-LAM] Γ ⊢ n : N Γ ⊢ e1 : τ Γ ⊢ e2 : R Γ ⊢ delay n e1 e2 : τ [T-DELAY] Γ, x : τp ⊢ e : τp Γ ⊢ feedx.e : τp [T-FEED] Γ ⊢ ec : R Γ ⊢ et : τ Γ ⊢ ee : τ Γ ⊢ if (ec ) et ee : τ [T-IF] Only primitive types are allowed for feed to simplify implementation. However, returning function in feed could be theoretically possible. (The function whose behavior changes sample-by-sample?) -
Operational Semantics of λmmm (Big-step style, Excerpt) En ⊢ e1
⇓ v1 n > v1 En−v1 ⊢ e2 ⇓ v2 En ⊢ delay n e1 e2 ⇓ v2 [E-DELAY] En ⊢ λx.e ⇓ cls(λx.e, En) [E-LAM] En−1 ⊢ e ⇓ v1 En, x ↦ v1 ⊢ e ⇓ v2 En, x ↦ v2 ⊢ feed x e ⇓ v1 [E-FEED] En ⊢ ec ⇓ n n > 0 En ⊢ et ⇓ v En ⊢ if(ec ) et else et ⇓ v [E-IFTRUE] En ⊢ ec ⇓ n n ≦ 0 En ⊢ ee ⇓ v En ⊢ if(ec ) et else et ⇓ v [E-IFFALSE] En ⊢ e1 ⇓ cls(λxc .ec , En c )En ⊢ e2 ⇓ v2 En c , xc ↦ v2 ⊢ ec ⇓ v En ⊢ e1 e2 ⇓ v [E-APP] This semantics stores evaluation context in each sample as En. If referred to the environment of n<0, it returns 0. In this semantics, the value from 0 to the present is recalculated every sample, and the variable environments are recreated and discarded each time. -
VM and Bytecodes for λmmm • Based on Lua VM
5.0 (Register-machine but the register is represented as just the relative position on a call stack from a base pointer) • Resolves captured values of the closure by special instruction `getupvalue` • Tuned for static typed language • e.g. Call to the global function and Call to the closure are di ff erent operation • Only closures are heap-allocated (currently managed by reference-counted GC) • Operations for getting/setting internal state variable for self and delay -
MOVE A B R(A) := R(B) MOVECONST A B R(A)
:= K(B) GETUPVALUE A B R(A) := U(B) (SETUPVALUE does not exist) GETSTATE* A R(A) := SPtr[SPos] SETSTATE* A SPtr[SPos] := R(A) SHIFTSTATE* sAx SPos += sAx DELAY* A B C R(A) := update_ringbuffer(SPtr[SPos],R(B),R(C)) *(SPos,SPtr)= vm.closures[vm.statepos_stack.top()].state (if vm.statepos_stack is empty, use global state storage.) JMP sAx PC +=sAx JMPIFNEG A sBx if (R(A)<0) then PC += sBx CALL A B C R(A),...,R(A+C-2) := program.functions[R(A)](R(A+1),...,R(A+B-1)) CALLCLS A B C vm.statepos_stack.push(R(A)) R(A),...,R(A+C-2) := vm.closures[R(A)].fnproto(R(A+1),...,R(A+B-1)) vm.statepos_stack.pop() CLOSURE A Bx vm.closures.push(closure(program.functions[R(Bx)])) R(A) := vm.closures.length - 1 CLOSE A close stack variables up to R(A) RETURN A B return R(A), R(A+1)...,R(A+B-2) ADDF A B C R(A) := R(B) as float + R(C) as float SUBF A B C R(A) := R(B) as float - R(C) as float MULF A B C R(A) := R(B) as float * R(C) as float DIVF A B C R(A) := R(B) as float / R(C) as float ADDI A B C R(A) := R(B) as int + R(C) as int ...Other basic arithmetic continues for each primitive types... (In the actual compiler, most of the operation have an additional operand to indicate word-size of the value to handle aggregate-type value) -
Overview of the VM and Program Virtual Machine Program Counter
State_Ptr Stack Audio Driver Call Stack ... State Storage Closure Storage Base Pointer State Position State for self 1 Ring Buffer for delay 1 State for self 2 Ring Buffer for delay 2 ... Program Function Prototype0 Static Variables ... ... Function Prototype1 OP A B C OP A B C OP A B C OP A B C OP A B C Upvalue List Program State Size Local(N1) Upvalue(N2) Open Closure Function Prototype State Storage Upvalues Open(Local(N1)) Open(Upvalue(N2)) State Position Escaped Closure Function Prototype State Storage Upvalues State Position Closed Upvalue 1 Closed Upvalue 2 Somewhere on the Heap Memory (Maybe Shared with other closures) -
Simplified version when no stateful functions are used Virtual Machine
Program Counter Audio Driver Call Stack ... Closure Storage Base Pointer Program Function Prototype0 Static Variables ... ... Function Prototype1 OP A B C OP A B C OP A B C OP A B C OP A B C Upvalue List Program Local(N1) Upvalue(N2) Open Closure Function Prototype Upvalues Open(Local(N1)) Open(Upvalue(N2)) Escaped Closure Function Prototype Upvalues Closed Upvalue 1 Closed Upvalue 2 Somewhere on the Heap Memory (Maybe Shared with other closures) -
Case: combining multiple delay with feedback fn fbdelay(x,fb,dtime){ x +
delay(1000,self,dtime)*fb } fn twodelay(x,dtime){ fbdelay(x,dtime,0.7) +fbdelay(x,dtime*2,0.8) } fn dsp(x){ twodelay(x,400)+twodelay(x,800) } "fbdelay" uses delay with 1000 as a maximum samples , and self "twodelay" uses "fbdelay" twice "dsp" uses "twodelay" twice -
CONSTANTS:[0.7,2,0.8,400,800,0,1] fn fbdelay(x,fb,dtime) state_size:1004 MOVE 3 0 //load x GETSTATE
4 SHIFTSTATE 1 DELAY 4 4 2 MOVE 5 1 MULF 4 4 5 ADDF 3 3 4 SHIFTSTATE -1 GETSTATE 4 SETSTATE 3 RETURN 4 1 fn twodelay(x,dtime) state_size:2008 MOVECONST 2 5 MOVE 3 0 MOVE 4 1 MOVECONST 5 0 CALL 2 3 1 SHIFTSTATE 1004 MOVECONST 3 5 MOVE 4 0 MOVECONST 5 1 //load 2 MULF 4 4 5 MOVECONST 5 0 //load 0.7 CALL 3 3 1 ADDF 3 3 4 SHIFTSTATE -1004 RETURN 3 1 fn dsp (x) state_size:4016 MOVECONST 1 6 //load twodelay MOVE 2 0 MOVECONST 3 3 //load 400 CALL 1 2 1 SHIFTSTATE 2008 MOVECONST 2 6 //load twodelay MOVE 2 3 MOVE 3 0 MOVECONST 3 4 //load 400 CALL 2 2 1 ADD 1 1 2 SHIFTSTATE -2008 RETURN 1 1 Bytecode Representation of the "twodelay" Example -
fn fbdelay(x,fb,dtime) state_size:1004 MOVE 3 0 //load x GETSTATE 4
SHIFTSTATE 1 DELAY 4 4 2 MOVE 5 1 MULF 4 4 5 ADDF 3 3 4 SHIFTSTATE -1 GETSTATE 4 SETSTATE 3 RETURN 4 1 State for Self Ring Buffer for Delay SPos ... ... -
fn fbdelay(x,fb,dtime) state_size:1004 MOVE 3 0 //load x GETSTATE 4
SHIFTSTATE 1 DELAY 4 4 2 MOVE 5 1 MULF 4 4 5 ADDF 3 3 4 SHIFTSTATE -1 GETSTATE 4 SETSTATE 3 RETURN 4 1 State for Self Ring Buffer for Delay SPos Refer to the "self" Take one word at SPos, and load to register 4 ... ... -
fn fbdelay(x,fb,dtime) state_size:1004 MOVE 3 0 //load x GETSTATE 4
SHIFTSTATE 1 DELAY 4 4 2 MOVE 5 1 MULF 4 4 5 ADDF 3 3 4 SHIFTSTATE -1 GETSTATE 4 SETSTATE 3 RETURN 4 1 State for Self Ring Buffer for Delay SPos ... ... -
fn fbdelay(x,fb,dtime) state_size:1004 MOVE 3 0 //load x GETSTATE 4
SHIFTSTATE 1 DELAY 4 4 2 MOVE 5 1 MULF 4 4 5 ADDF 3 3 4 SHIFTSTATE -1 GETSTATE 4 SETSTATE 3 RETURN 4 1 State for Self Ring Buffer for Delay SPos ... ... Update a ring bu ff er at a SPos -
fn fbdelay(x,fb,dtime) state_size:1004 MOVE 3 0 //load x GETSTATE 4
SHIFTSTATE 1 DELAY 4 4 2 MOVE 5 1 MULF 4 4 5 ADDF 3 3 4 SHIFTSTATE -1 GETSTATE 4 SETSTATE 3 RETURN 4 1 State for Self Ring Buffer for Delay SPos ... ... Move back Spos so that the sum of the Spos movement within the function should be 0 -
fn fbdelay(x,fb,dtime) state_size:1004 MOVE 3 0 //load x GETSTATE 4
SHIFTSTATE 1 DELAY 4 4 2 MOVE 5 1 MULF 4 4 5 ADDF 3 3 4 SHIFTSTATE -1 GETSTATE 4 SETSTATE 3 RETURN 4 1 State for Self Ring Buffer for Delay SPos ... ... If "self" is used, take the previous return value from Spos, write return value at this time to Spos, and return the previous value from function -
fn twodelay(x,dtime) state_size:2008 MOVECONST 2 5 MOVE 3 0 MOVE
4 1 MOVECONST 5 0 CALL 2 3 1 SHIFTSTATE 1004 MOVECONST 3 5 MOVE 4 0 MOVECONST 5 1 //load 2 MULF 4 4 5 MOVECONST 5 0 //load 0.7 CALL 3 3 1 ADDF 3 3 4 SHIFTSTATE -1004 RETURN 3 1 State for Self Ring Buffer for Delay SPos ... ... State for Self Ring Buffer for Delay 0 1 2 Call to the fi rst "fbdelay" -
fn twodelay(x,dtime) state_size:2008 MOVECONST 2 5 MOVE 3 0 MOVE
4 1 MOVECONST 5 0 CALL 2 3 1 SHIFTSTATE 1004 MOVECONST 3 5 MOVE 4 0 MOVECONST 5 1 //load 2 MULF 4 4 5 MOVECONST 5 0 //load 0.7 CALL 3 3 1 ADDF 3 3 4 SHIFTSTATE -1004 RETURN 3 1 State for Self Ring Buffer for Delay ... ... State for Self Ring Buffer for Delay 0 1 2 SPos 3 1 for self, 1003 for delay(3 for read index, write index, bu ff er size) => 1004 -
fn twodelay(x,dtime) state_size:2008 MOVECONST 2 5 MOVE 3 0 MOVE
4 1 MOVECONST 5 0 CALL 2 3 1 SHIFTSTATE 1004 MOVECONST 3 5 MOVE 4 0 MOVECONST 5 1 //load 2 MULF 4 4 5 MOVECONST 5 0 //load 0.7 CALL 3 3 1 ADDF 3 3 4 SHIFTSTATE -1004 RETURN 3 1 State for Self Ring Buffer for Delay ... ... State for Self Ring Buffer for Delay 0 1 2 SPos 3 4 5 Call to the second "fbdelay" -
fn twodelay(x,dtime) state_size:2008 MOVECONST 2 5 MOVE 3 0 MOVE
4 1 MOVECONST 5 0 CALL 2 3 1 SHIFTSTATE 1004 MOVECONST 3 5 MOVE 4 0 MOVECONST 5 1 //load 2 MULF 4 4 5 MOVECONST 5 0 //load 0.7 CALL 3 3 1 ADDF 3 3 4 SHIFTSTATE -1004 RETURN 3 1 State for Self Ring Buffer for Delay ... ... State for Self Ring Buffer for Delay 0 1 2 SPos 3 4 5 6 -
fn dsp (x) state_size:4016 MOVECONST 1 6 //load twodelay MOVE
2 0 MOVECONST 3 3 //load 400 CALL 1 2 1 SHIFTSTATE 2008 MOVECONST 2 6 //load twodelay MOVE 2 3 MOVE 3 0 MOVECONST 3 4 //load 400 CALL 2 2 1 ADD 1 1 2 SHIFTSTATE -2008 RETURN 1 1 State for Self Ring Buffer for Delay State for Self Ring Buffer for Delay 0 1 2 SPos 3 4 5 6 State for Self Ring Buffer for Delay State for Self Call to the fi rst "twodelay" -
fn dsp (x) state_size:4016 MOVECONST 1 6 //load twodelay MOVE
2 0 MOVECONST 3 3 //load 400 CALL 1 2 1 SHIFTSTATE 2008 MOVECONST 2 6 //load twodelay MOVE 2 3 MOVE 3 0 MOVECONST 3 4 //load 400 CALL 2 2 1 ADD 1 1 2 SHIFTSTATE -2008 RETURN 1 1 State for Self Ring Buffer for Delay State for Self Ring Buffer for Delay 0 1 2 SPos 3 4 5 6 State for Self Ring Buffer for Delay State for Self 7 -
fn dsp (x) state_size:4016 MOVECONST 1 6 //load twodelay MOVE
2 0 MOVECONST 3 3 //load 400 CALL 1 2 1 SHIFTSTATE 2008 MOVECONST 2 6 //load twodelay MOVE 2 3 MOVE 3 0 MOVECONST 3 4 //load 400 CALL 2 2 1 ADD 1 1 2 SHIFTSTATE -2008 RETURN 1 1 State for Self Ring Buffer for Delay State for Self Ring Buffer for Delay 0 1 2 SPos 3 4 5 6 State for Self Ring Buffer for Delay State for Self 7 8 9 10 11 12 13 Call to the second "twodelay" -
fn dsp (x) state_size:4016 MOVECONST 1 6 //load twodelay MOVE
2 0 MOVECONST 3 3 //load 400 CALL 1 2 1 SHIFTSTATE 2008 MOVECONST 2 6 //load twodelay MOVE 2 3 MOVE 3 0 MOVECONST 3 4 //load 400 CALL 2 2 1 ADD 1 1 2 SHIFTSTATE -2008 RETURN 1 1 State for Self Ring Buffer for Delay State for Self Ring Buffer for Delay 0 1 2 SPos 3 4 5 6 State for Self Ring Buffer for Delay State for Self 7 8 9 10 11 12 13 14 -
fn dsp (x) state_size:4016 MOVECONST 1 6 //load twodelay MOVE
2 0 MOVECONST 3 3 //load 400 CALL 1 2 1 SHIFTSTATE 2008 MOVECONST 2 6 //load twodelay MOVE 2 3 MOVE 3 0 MOVECONST 3 4 //load 400 CALL 2 2 1 ADD 1 1 2 SHIFTSTATE -2008 RETURN 1 1 State for Self Ring Buffer for Delay State for Self Ring Buffer for Delay 0 1 2 SPos 3 4 5 6 State for Self Ring Buffer for Delay State for Self 7 8 9 10 11 12 13 14 By having relative offsets, each functions do not need to care where they are called from -
Combination with Higher-Order Function fn bandpass(x,freq){ //... } fn filterbank(n,filter_factory:()->(float,float)->float){
if (n>0){ let filter = filter_factory() let next = filterbank(n-1,filter_factory) |x,freq| filter(x,freq+n*100) + next(x,freq) }else{ |x,freq| 0 } } let myfilter = filterbank(3,| | bandpass) fn dsp(){ myfilter(x,1000) } -
Combination with Higher-Order Function fn bandpass(x,freq){ //... } fn filterbank(n,filter_factory:()->(float,float)->float){
if (n>0){ let filter = filter_factory() let next = filterbank(n-1,filter_factory) |x,freq| filter(x,freq+n*100) + next(x,freq) }else{ |x,freq| 0 } } let myfilter = filterbank(3,| | bandpass) fn dsp(){ myfilter(x,1000) } The size of the internal state variable for " fi lter_factory" is not determined at a compile time. -
Virtual Machine Program Counter State_Ptr Stack Audio Driver Call Stack
... State Storage Closure Storage Base Pointer State Position State for self 1 Ring Buffer for delay 1 State for self 2 Ring Buffer for delay 2 ... Program Function Prototype0 Static Variables ... ... Function Prototype1 OP A B C OP A B C OP A B C OP A B C OP A B C Upvalue List Program State Size Local(N1) Upvalue(N2) Open Closure Function Prototype State Storage Upvalues Open(Local(N1)) Open(Upvalue(N2)) State Position Escaped Closure Function Prototype State Storage Upvalues State Position Closed Upvalue 1 Closed Upvalue 2 Somewhere on the Heap Memory (Maybe Shared with other closures) When the closure is made with CLOSURE instruction, it allocates storage for internal state variables individually -
Virtual Machine Program Counter State_Ptr Stack Audio Driver Call Stack
... State Storage Closure Storage Base Pointer State Position State for self 1 Ring Buffer for delay 1 State for self 2 Ring Buffer for delay 2 ... Program Function Prototype0 Static Variables ... ... Function Prototype1 OP A B C OP A B C OP A B C OP A B C OP A B C Upvalue List Program State Size Local(N1) Upvalue(N2) Open Closure Function Prototype State Storage Upvalues Open(Local(N1)) Open(Upvalue(N2)) State Position Escaped Closure Function Prototype State Storage Upvalues State Position Closed Upvalue 1 Closed Upvalue 2 Somewhere on the Heap Memory (Maybe Shared with other closures) When CALLCLS is used, VM pushes the pointer to closure's state storage to the stack, to switch which storage are used in GET/SET/SHIFTSTATE operations -
CONSTANTS[100,1,0,2] fn inner_then(x,freq) //upvalue: [local(4),local(3),local(2),local(1)] GETUPVALUE 3 2 //load filter
MOVE 4 0 MOVE 5 1 GETUPVALUE 6 1 //load n ADDD 5 5 6 MOVECONST 6 0 MULF 5 5 6 CALLCLS 3 2 1 //call filter GETUPVALUE 4 4 //load next MOVE 5 0 MOVE 6 1 CALLCLS 4 2 1 //call next ADDF 3 3 4 RETURN 3 1 fn inner_else(x,freq) MOVECONST 2 2 RETURN 2 1 fn filterbank(n,filter_factory) MOVE 2 0 //load n MOVECONST 3 2 //load 0 SUBF 2 2 3 JMPIFNEG 2 12 MOVE 2 1 //load filter_factory CALL 2 2 0 //get filter MOVECONST 3 1 //load itself MOVE 4 0 //load n MOVECONST 5 1 //load 1 SUBF 4 4 5 MOVECONST 5 2 //load inner_then CALLCLS 3 2 1 //recursive call MOVECONST 4 2 //load inner_then CLOSURE 4 4 //load inner_lambda JMP 2 MOVECONST 4 3 //load inner_else CLOSURE 4 4 CLOSE 4 RETURN 4 1 There are no "GET/SET/SHIFTSTATE" operation here! -
Combination with Higher-Order Function fn bandpass(x,freq){ //... } fn filterbank(n,filter_factory:()->(float,float)->float){
if (n>0){ let filter = filter_factory() let next = filterbank(n-1,filter_factory) |x,freq| filter(x,freq+n*100) + next(x,freq) }else{ |x,freq| 0 } } let myfilter = filterbank(3,| | bandpass) fn dsp(){ myfilter(x,1000) } This works like a constructor of Unit Generator, in the object-oriented programming world -
%JTDVTTJPO • Counterintuitive behavior of higher order functions • Foreign
stateful function call • Comparison to the other languages -
Comparison to the other languages Parametric Signal Graph Actual DSP
Faust Term Rewriting Macro BDA Kronos Type-level Computation Value Evaluation mimium Global Context Execution dsp Function Execution Both are same semantics in the value level. This will make it easier to understand for novice users but... -
This code does not work: fn filterbank(n,filter){ if (n>0){ |x,freq|
filter(x,freq+n*100) + filterbank(n-1,filter)(x,freq) }else{ |x,freq| 0 } } fn dsp(){ filterbank(3,bandpass)(x,1000) } -
This code does not work: fn filterbank(n,filter){ if (n>0){ |x,freq|
filter(x,freq+n*100) + filterbank(n-1,filter)(x,freq) }else{ |x,freq| 0 } } fn dsp(){ filterbank(3,bandpass)(x,1000) } These part re-instantiates the closure with zero- initiallized state variables every samples -
This code still does not work: fn filterbank(n,filter){ let next
= filterbank(n-1,filter) if (n>0){ |x,freq| filter(x,freq+n*100) + next(x,freq) }else{ |x,freq| 0 } } let myfilter = filterbank(3,bandpass) fn dsp(){ myfilter(x,1000) } -
This code still does not work: fn filterbank(n,filter){ let next
= filterbank(n-1,filter) if (n>0){ |x,freq| filter(x,freq+n*100) + next(x,freq) }else{ |x,freq| 0 } } let myfilter = filterbank(3,bandpass) fn dsp(){ myfilter(x,1000) } This code shares the same instance of the closure and updated multiple times at a sample *This behavior could be fi xed by changing the closure to be “deep-copied” when passed as an argument to HOF. -
If the Multi-Stage Programming can be used: fn filterbank(n,filter:&(float,float)->float)->&(float,float)->float{ .<
if (n>0){ |x,freq| ~filter(x,freq+n*100) + ~filterbank(n-1,filter)(x,freq) }else{ |x,freq| 0 } >. } fn dsp(){ ~filterbank(3,.<bandpass>.)(x,1000) } *This is a pseudo-code, based on the syntax of BER MetaOCaml -
Considering on a multi-stage computation • Question: When should we
evaluate stage-0. At AST or Bytecode? • If the former, we have to implement two di ff erent evaluators. • If the latter, we have to translate multi-stage computation semantics into imperative world somehow. • Is the syntax of multi-stage computation really easy to understand for novices, than the type-level computation in Kronos or the term rewriting macro in Faust? *I'm going to this choice currently -
Foreign stateful function calls • Because the closure works like
Unit Generator in the OOP world, mimium can call UGen de fi ned in the native code with small wrapper naturally. • though it will not work for vector-by-vector processing correctly. -
In fact, some external modules like MIDI and Instant oscilloscope
(written in Rust) are used with higher-order function pattern -
Wrap-up • λmmm: an extended call-by value lambda calculus, that
adds "delay" and "feed" • Proposed VM and Instruction set for it • GET/SET/SHIFTSTATE to handle "delay" and "feed" • A closure instance holds a memory for state variables for "delay" and "feed" to handle a higher-order function with stateful functions. • Resulted in uni fi ed semantics for both parametric signal graph generation and actual execution of the graph • This makes it easier to understand semantics but the users have to be responsible to distinct whether the function is evaluated in global context once or in "dsp" function iteratively • Domain-Speci fi c, but not loosing generality, self-extensibility and interoperability -
Thank you for listening. email: [email protected] mastodon: social.matsuuratomoya.com/@tomoya https://github.com/tomoyanonymous/mimium-rs Development
repository of mimium v2 (written in Rust)