Garbage Collection Mechanism of Fuzuli Interpreter

Fuzuli, our programming language and interpreter, has a garbage collection utility since its early stages. Garbage collection is an old term in computer science.

A chunk of memory is allocated for each software program by operating systems. Programs also allocate memory at runtime. Those programs are responsable to free the memory they allocated. Operations for allocating and freeing memory areas are performed using single commands such like malloc, free, new and delete in C and C++.

But allocating and freeing the chunks of memory is not that easy. When a reference to a dynamically created object is broken, the object remains suspended in the memory. Look at code below:

(let a (list 5 6 10 "Text"))
(let a NULL)

In the code above, a list of 5, 6, 10 and Text is created and referenced by the variable 'a'. Then, a is set to NULL. After all, what happened to list and its objects? The answer is easy. They suspended in the memory and waiting to be cleaned.

Ok, what about the code given below?

(let b 11)
(let a (list 5 6 10 b))
(let a NULL)

In the code above, a is linked to a list which contains 5,6,10 and b. b is an other variable which has a value of 11. After setting the value of 'a' to NULL, there is some garbage but this is a little bit different. Cleaning the object referenced by 'a' also means cleaning the object referenced by b. But we don't 'b' to be cleaned, it should stay alive. Reference Counting now comes into account. Counting references given to an object gives more information about the aliveness status of an object. In this example, the integer object has only one references in (let b 11).

When the code (let a (list 5 6 10 b)) runs; references of objects 5, 6, 10 and b increased by 1. The old reference count of b was 1, so b has a reference counting of 2. When (let a NULL) runs; reference counts of all objects contained by 'a' are decreased by 1. After all, the object which have reference count of 0 are deleted from the memory. The object 'b' is still alive!. Fuzuli uses this mechanism.

Garbage collecting in Fuzuli is automatic by default. Calling

(gc false)

simply disables the automatic garbage collector. Calling

(gc true)

enables the garbage collector. Whenever the garbage collector is enabled or disabled, it can be called manually. Simply calling (gc) triggers the garbage collector:

(let total (gc))
(print "Number of gargabe collected: " total "\n")

In the example below, a list of 1,2,...,1000000 created and referenced by a variable 'a'. Then a is set to NULL and generated garbage is collected manually.

(gc off)
(let limit 1000000)
(print "Creating array of 0..." limit "\n")
(let a (: 0 limit))
(print "Array created with length " (length a) "\n")
(dump)
(let a NULL)
(print "Gargabe Collecting manually:\n")
(gc)
(dump)

The output is

Creating array of 0...1000000
Array created with length 1000001
Environment Deep: 0
# Sub Environments: 0
# Tokens 1000054
Gargabe Collecting manually:
Environment Deep: 0
# Sub Environments: 0
# Tokens 67

 In the example above, there are 1000054 garbage objects before manual garbage collection. After garbage collecting, there are 67 objects which includes the source code itself. It was a nice experiment to implement a garbage collector in Fuzuli. Hope you have fun with it!