Translating match ================= [ e match { cases } ] out = [e] after after: [ cases ] out The execution of [cases]out should consume one element from the stack (the value of e) and leave one element of the stack (the result of match). If c is one case and cs the remaining ones ========================================== Recursive case: [ c; cs ] out = [c] nextCase out nextCase: [cs] The above translation assumes that matching of one case will leave the stack as it is if the match fails, or consume a value and leave the result on the stack, if the case succeeds. Base case - empty list of patterns: [ ] out = goto out Translating one case - base case of a variable pattern ====================================================== In this case we just match the variable; it always succeeds. We consume the value to match by storing it that variable. Allocate a slot for a new variable, x, and give it a previously unused slot while translating this statement. Denote that slot by #x. [ case x => f ] next out = // stack: e istore #x // stack: [f] out // stack: f Here we assume that the translation of an expression, [f], takes one parameter, the place to go to after the evaluation of an expression. Translating recursive case - linear pattern match ================================================= Here p is a pattern itself. We need to test that the value is non-negative and then if subtracting b gives a result divisible by a. We keep in mind that if match succeeds the code should consume e and leave f on stack. If the match fails, the code should leave only e on the stack. [ case (a*p + b) => f ] next out = // stack: e dup // after this, stack: e,e iflt out // e dup // e,e bipush b // e,e,b isub // e,e-b dup // e,e-b,e-b bipush a // e,e-b,e-b,a irem // e,e-b,r ifneq next1 // e,e-b bipush a // e,e-b,a idiv // e,q [case p => f] next1 out1 // translate recursively out1: // e,f swap // f,e pop // f next1: // e,q pop // e goto next // e