On the Subtleties of Implicit Assumptions

Hi!

In this post, I just want to throw a reflection on the difficulties that you may encounter in changing your mindset when you have some implicit assumptions deep in your mind. This post is more about programming than it is about game development but anyway, the former is closely related to the latter.

From time to time, I like to read about Lua, a scripting language that is gaining traction among game developers for its multiple benefits, which include its easy integration with C/C++ and its reduced footprint, which makes it efficient for real-time applications. 

In order to practice, I decided to implement the well-known mergesort algorithm. Just as a short explanation/reminder, mergesort is used to sort a collection of elements (i.e. an array), being the main representative of the divide-and-conquer paradigm. The idea is simple: you split the collection in two halves, you sort each half and you merge it, as you would do with a deck of cards. You repeat this process recursively until you have a straightforward problem (e.g. one card), which constitutes the base case.

Without further ado, this is the algorithm implemented in Lua:

 function merge( a1, a2 )  
   local j = 1  
   local i = 1  
   local k = 1  
   local  b = {}  
   while i <= #a1 and j <= #a2 do  
     if a1[i] < a2[j] then  
       b[k] = a1[i]  
       i = i + 1    
     else  
       b[k] = a2[j]  
      j = j + 1    
     end  
     k = k + 1  
   end  
   if i <= #a1 then  
     for t = i, #a1 do  
       b[k] = a1[t]  
       k = k + 1   
     end  
   else  
     for t = j, #a2 do  
       b[k] = a2[t]  
       k = k + 1  
     end  
   end  
   return b  
 end   
 function mergeSort( a )  
   if #a <= 1 then  
     return a    
   else  
     local b = {}  
     for i = 1, math.floor(#a/2) do  
       b[i] = a[i]  
     end  
     local c = {}  
     for i = math.floor(#a/2) + 1, #a do  
       c[i - math.floor(#a/2)] = a[i]  
     end    
     array1 = mergeSort(b)  
     array2 = mergeSort(c)  
     return merge( array1, array2 )  
   end  
 end  

The thing is that, even when I was pretty sure that the algorithm was well implemented, it was not working as expected. And it took me a while to understand why, because the reason is hidden as an implicit assumption that I was making as a result of being used to programming in other languages, such as C++.

This assumption is that all variables are, by default, local to their scope. However, in Lua, unless you specify otherwise, all variables are global by default. Only if you add the modifier local before the name of the variable, the variable is actually local. Therefore, variables array1 and array2 are global variables, and upon recursion, they do not change their values by the values that correspond to the current stack, breaking the recursion mechanism. This problem is fixed by writing the local keyword before array1 and array2.

Anyway, what I wanted to discuss here is that when we are changing among different technologies/languages, we also need to update our implicit assumptions, which is what makes these changes challenging. Note that I didn't have a problem with the syntax: this kind of problems are pretty easy to detect and fix. My problem was more with the semantics and this is a much harder problem to detect.

So watch out! Your assumptions might be your worst enemies from time to time.

See you.