After grasping the power of Memoize in VB.NET and C#, I tried my luck at making a memoizing Fibonacci generator in Second Life’s scripting language LSL. Second Life is a 3D virtual world where end users can create their own world using basic building blocks. They can script their creation with a scripting language called LSL. This language gets compiled to Mono’s runtime.
LSL is somewhat limited. It does not allow for closures or lambda functions. It also has a very limited set of datatypes. It does not have arrays. It has immutable lists. A list in LSL can contain elements of string, integer and other types but not lists themselves. For Fibonacci a list with only integers will do.
I defined fib(n) first using its recursive definition to get the LSL right. Of course this doesn’t perform at all. After that I looked into memoizing. I noticed that inserting integers in a list is an expensive operation in LSL. However the nature of the Fibonacci algorithm makes this not necessary. The cache will always be filled in order from n=0 up to the requested number. I pre-seeded the list with [0,1,1] which eliminates one if clause. After that the fib function is recursively called and the results are added to the cache. Below is the final code
list cache=[0,1,1];
integer fib(integer n)
{
integer result;
if (n<llGetListLength(cache))
{
result= llList2Integer(cache, n);
}
else
{
result=fib(n-1)+fib(n-2);
cache=(cache=[])+cache+result;
}
return result;
}
default
{
state_entry()
{
llSay(0, "Hello, Avatar!");
}
touch_start(integer total_number)
{
integer i;
for(i=0;i<