Home | History | Annotate | Line # | Download | only in tut04-toyvm
fibonacci.toy revision 1.3 
      1 # Simple recursive fibonacci implementation, roughly equivalent to:
      2 #
      3 #  int fibonacci (int arg)
      4 #  {
      5 #     if (arg < 2)
      6 #       return arg
      7 #     return fibonacci (arg-1) + fibonacci (arg-2)
      8 #  }
      9 
     10 # Initial state:
     11 # stack: [arg]
     12 
     13 # 0:
     14 DUP
     15 # stack: [arg, arg]
     16 
     17 # 1:
     18 PUSH_CONST 2
     19 # stack: [arg, arg, 2]
     20 
     21 # 2:
     22 BINARY_COMPARE_LT
     23 # stack: [arg, (arg < 2)]
     24 
     25 # 3:
     26 JUMP_ABS_IF_TRUE 13
     27 # stack: [arg]
     28 
     29 # 4:
     30 DUP
     31 # stack: [arg, arg]
     32 
     33 # 5:
     34 PUSH_CONST  1
     35 # stack: [arg, arg, 1]
     36 
     37 # 6:
     38 BINARY_SUBTRACT
     39 # stack: [arg,  (arg - 1)
     40 
     41 # 7:
     42 RECURSE
     43 # stack: [arg, fib(arg - 1)]
     44 
     45 # 8:
     46 ROT
     47 # stack: [fib(arg - 1), arg]
     48 
     49 # 9:
     50 PUSH_CONST  2
     51 # stack: [fib(arg - 1), arg, 2]
     52 
     53 # 10:
     54 BINARY_SUBTRACT
     55 # stack: [fib(arg - 1), arg,  (arg - 2)
     56 
     57 # 11:
     58 RECURSE
     59 # stack: [fib(arg - 1), fib(arg - 1)]
     60 
     61 # 12:
     62 BINARY_ADD
     63 # stack: [fib(arg - 1) + fib(arg - 1)]
     64 
     65 # 13:
     66 RETURN
     67