Yes - 4 (or 5) opcodes can implement Fibonacci

I've managed to implement fibonacci in my own dynamic VM, using 5 opcodes (could do it in 4). It was a real discipline to have to keep those codes down, and I tried very hard to only do enough for the fibonacci function itself.

I am quite happy with the results. I've learnt quite a bit about what is needed, and what isn't. I've tried to make sure that things stay relatively neat, and what that costs at even this early stage.

It relies heavily upon closures to get stuff done, since there is no such thing as 'if'. At this stage everything that is needed is prebuilt - even the object representing the value 1.

So here is the code, as such. Firstly, a 'smalltalk' like description of how it works

   function fibonacci: index
    (index isLessThan: 2)
      ifTrue:
        [ ^ index ]
      ifFalse:
        [ ^ (fibonacci: (index minus: 1)) plus: (fibonacci: (index minus: 2)) ]

Next, the opcode translations. The actual fibonacci function first

   Push(two), // result = index isLessThan: two
   SetObject(index),
   MethodCall(isLessThan$),

   Push(anon1), // result = result ifTrue: anon1 ifFalse: anon2
   Push(anon2),
   SetObject(Symbol.RESULT),
   MethodCall(ifTrue$IfFalse$),
        
   Push(Symbol.RESULT),  // contextualize anon function
   Push(Symbol.CURRENT_CONTEXT),
   ContextCall(Symbol.CONTEXTUALIZE_FUNCTION),
        
   CallFunctionInSlot(Symbol.RESULT) // call anon function

The two anonymous functions are implemented as follows. The first simply returns 1

   Push(one),
   ContextCall(Symbol.SET_RESULT)

While the second does the more complex recursive calling of fibonacci to calculate the new number

   Push(one),  // result = index - 1
   SetObject(index),
   MethodCall(minus$),

   Push(Symbol.RESULT), // result = fibonacci( result )
   ContextCall(fibonacci$),

   Push(Symbol.RESULT),  // temp1 = result
   ContextCall(temp1Setter),

   Push(two),  // result = index - 2
   SetObject(index),
   MethodCall(minus$),

   Push(Symbol.RESULT), // result = fibonacci( result )
   ContextCall(fibonacci$),

   Push(Symbol.RESULT), // result = temp1 + result
   SetObject(temp1),
   MethodCall(plus$)

Note the extensive use of result. There are lots of globals in this example (one, two, fibonacci$) and lots of symbols. This approach sure burns through the symbols.

Everything is a function call - you can only use a slot by calling it's accessor. So when slots are added to an object they usually have accessors created for them.

The native functions at the moment are; plus:, minus:, isLessThan: (and behind the scenes; getters and setters)

Also note CallFunctionInSlot, which is nasty. This is because I need to invoke a function that is stored in a slot (doesn't have to be a slot...), but by calling the slot accessor the function is returned, not executed. I believe there is no way around this.

From this point I have identified a few things to do next. I really need to neaten things up; move all the 'native' functions into the VM object, implement Number properly as a prototype and factory. But more fundamentally I need to

• introduce a PushValue opcode so I can create numbers (so the values of one and two above can be created within the fibonacci program)
• find some way to define a function within an existing function (so the above anon functions can be created within the definition of the fibonacci program, rather than externally to it)
• think about exceptions

Patently there's a lot more than just that, but it's a good start

Update: I've just eliminated one of those opcodes (the one I didn't like called 'CallFunctionInSlot') with the oh so obvious function 'execute' on Function. So now you can execute a function that is sitting in a slot.

Down to 3(or 4) opcodes!