resultsFixed.tex

\chapter{Evaluation} \label{cap:Resultados}

\begin{displayquote}
    \begin{center}
        \textit{``There is no pain as long as I keep my eyes on the balance scale.''}
    \end{center}
\end{displayquote}

\begin{flushright}
   \textit{-- NORIAKI KUBO}
\end{flushright}

% \section{Introduction}
This chapter is dedicated to present to the reader a series of different approaches that were taken in order to test the Bleach programming language and the Tree-Walk Interpreter implemented for it from different perspectives. Regarding these perspectives, the following approaches were taken:
\begin{itemize}
    \item \textbf{Test Suite:} A Test Suite is a carefully tailored collection of test cases and test scripts implemented in order to verify that a software program or a specific module of a program is behaving as expected.
    
    \item \textbf{Implementation of famous Algorithms and Data Structures:} As a way to better demonstrate Bleach's expressiveness and prowess, this section is dedicated to present to the reader implementation of famous Algorithms and Data Structures commonly taught in an undergraduate Computer Science degree.
    
    \item \textbf{Comparison of Bleach with ChocoPy, Cool and MiniJava:} Regarding comparison with its predecessors, this section is dedicated to compare Bleach with them in terms of language features.
\end{itemize}


\section{Bleach's Test Suite}
As mentioned above, one of the different ways to evaluate Bleach was through the creation of a test suite that verifies the correctness of the Tree-Walk Interpreter implementation. In this particular scenario, this test suite is composed of several test cases, the expected output for each of these test cases and a test script responsible for executing the test cases automatically.

The Test Suite is made of 44 test cases and a shell script that executes these tests in an automated manner. These test cases are divided into 3 groups (tests responsible for Expression nodes, tests responsible for Statement nodes and tests responsible for some of the Bleach Native Functions). All types of AST nodes previously presented in Table~\ref{tab:ASTNodes} are covered. Moreover, from these 44 test cases there are 2 of them that cover native functions from the following namespaces: \texttt{std::math} and \texttt{std::utils}.

Each test case is composed by a Bleach file (\texttt{.bch} extension) representing the Bleach program that will be executed by the interpreter, a file with the extension 
 \texttt{.bch.expected}, representing the expected output for that corresponding \texttt{.bch} file when it is executed and, finally, a corresponding \texttt{.bch.log} file that represents the actual output generated by the execution of such \texttt{.bch} file. In this context, it is important to highlight that each Bleach file (\texttt{.bch} extension) and its corresponding expected output (\texttt{.bch.expected} extension) were hand-crafted adopting an approach very similar to unit tests. Therefore, the focus of each test is on the runtime behavior of a single type of AST node. Finally, the difference between the \texttt{.bch.expected} and the \texttt{.bch.log} is computed. If there are no differences, then it means that the particular test case passed. Otherwise, it did not.

 This process is automated by a shell script called \texttt{bleach\_test\_pipeline.sh} that automatically executes each Bleach program and compares its expected output file with the produced output file. In the end, this script provides a simple metric displaying how many of the test cases have passed from the total number and it also shows which test cases did not pass.

 More detailed information about how to execute Bleach's test suite can be found at Bleach's official GitHub repository \cite{bleach_lang_git_repo}.


\section{Implementing Famous Algorithms and Data Structures in Bleach}
The main goal here is show the expressiveness and prowess of Bleach by demonstrating that it is possible to implement famous algorithms and data structures that are usually taught in an undergraduate "Introduction to Algorithms" course. These implementations, along with a few tests cases, can be found at \href{https://github.com/vmmc2/Bleach/tree/main/tests/algorithms_and_data_structures}{Famous A \& DS implementations in Bleach}. The implemented algorithms and data structures were:
\begin{itemize}
    \item Binary Heap
    \item Binary Search Tree
    \item Binary Search
    \item Breadth First Search
    \item Depth First Search
    \item Dijkstra's Shortest-Path Algorithm
    \item Insertion Sort
    \item Merge Sort
    \item Queue
    \item Quick Sort
    \item Stack
\end{itemize}

\begin{comment}

\begin{itemize}
    \item Stack
        \begin{lstlisting}
class Node{
  method init(value){
    self.value = value;
    self.next = nil;
  }

  method str(){
    return self.value;
  }
}

class Stack{
  method init(){
    self.root = nil;
    self.length = 0;
  }

  method empty(){
    return self.length == 0 ? true : false;
  }

  method size(){
    return self.length;
  }

  method push(value){
    let newNode = Node(value);
    if(self.root == nil){
      self.root = newNode;
    }else{
      newNode.next = self.root;
      self.root = newNode;
    }

    self.length = self.length + 1;

    return nil;
  }

  method pop(){
    if(self.root == nil){
      return "The stack is empty.";
    }else{
      let poppedValue = self.root;
      self.root = self.root.next;

      self.length = self.length - 1;

      return poppedValue;
    }
  }

  method str(){
    let stackAsString = "";
    let curr = self.root;
    while(curr != nil){
      stackAsString = stackAsString + (curr.value + " -> ");
      curr = curr.next;
    }
    stackAsString = stackAsString + " nil";

    return stackAsString;
  }

  method top(){
    if(self.root == nil){
      return "The stack is empty.";
    }else{
      return self.root;
    }
  }
}
        \end{lstlisting}


    \item Queue
        \begin{lstlisting}
class Node{
  method init(value){
    self.value = value;
    self.next = nil;
  }

  method str(){
    return self.value;
  }
}

class Queue{
  method init(){
    self.left = nil;
    self.right = nil;
    self.length = 0;
  }

  method empty(){
    return self.length == 0 ? true : false;
  }

  method size(){
    return self.length;
  }

  method front(){
    if(self.left == nil){
      return "The queue is empty.";
    }else{
      return self.left;
    }
  }

  method back(){
    if(self.right == nil){
      return "The queue is empty.";
    }else{
      return self.right;
    }
  }

  method push(value){
    if(self.length == 0){
      let newNode = Node(value);
      self.left = newNode;
      self.right = self.left;
    }else{
      let newNode = Node(value);
      self.right.next = newNode;
      self.right = newNode;
    }

    self.length = self.length + 1;

    return;
  }

  method pop(){
    if(self.length == 0){ // Queue is empty.
      return "The queue is empty.";
    }elif(self.length == 1){ // Queue is not empty and has only one element.
      let poppedValue = self.left.value;

      self.left = nil;
      self.right = nil;

      self.length = self.length - 1;

      return poppedValue;
    }else{ // Queue is not empty and has more than one element.
      let poppedValue = self.left.value;

      self.left = self.left.next;
      self.length = self.length - 1;

      return poppedValue;
    }
  }

  method str(){
    let queueAsString = "front -> ";
    let curr = self.left;
    while(curr != nil){
      if(curr != nil and curr.next != nil){
        queueAsString = queueAsString + (curr.value + " -> ");
      }else{
        queueAsString = queueAsString + curr.value;
      }
      curr = curr.next;
    }
    queueAsString = queueAsString + " <- back";

    return queueAsString;
  }
}
        \end{lstlisting}


    \item Insertion Sort
        \begin{lstlisting}
/*
Code that implements the Insertion Sort algorithm.
Assumes it is a list where every value is of type 'num'.
*/

function insertionSort(l){
  let n = l.size();

  for(let i = 0; i < n; i = i + 1){
    let curr = i;
    while(curr > 0 and l.getAt(curr) < l.getAt(curr - 1)){
      let temp = l.getAt(curr);
      l.setAt(curr, l.getAt(curr - 1));
      l.setAt(curr - 1, temp);
      curr = curr - 1;
    }
  }

  return;
}
        \end{lstlisting}
    \item Merge Sort
        \begin{lstlisting}
/*
Code that implements the Merge Sort algorithm.
Assumes it is a list where every value is of type 'num'.
*/

function merge(a, b){
  let n = a.size();
  let m = b.size();

  let i = 0;
  let j = 0;
  let k = 0;
  
  let c = [];
  c.fill(nil, m + n);

  while(i < n or j < m){
    if(j == m or (i < n and a.getAt(i) < b.getAt(j))){
      c.setAt(k, a.getAt(i));
      k = k + 1;
      i = i + 1;  
    }else{
      c.setAt(k, b.getAt(j));
      k = k + 1;
      j = j + 1;
    }
  }

  return c;
}

function mergeSort(a){
  if(a.size() <= 1){
    return a;
  }else{
    let b = [];
    let c = [];
    let n = a.size();
    let mid = std::math::floor(n/2 - 1);

    for(let i = 0; i <= mid; i = i + 1){
      b.append(a.getAt(i));
    }

    for(let i = mid + 1; i <= n - 1; i = i + 1){
      c.append(a.getAt(i));
    }

    b = mergeSort(b);
    c = mergeSort(c);

    return merge(b, c);
  }
}
        \end{lstlisting}
    
    
    \item Quick Sort
        \begin{lstlisting}
/*
Code that implements the Quick Sort algorithm.
Assumes it is a list where every value is of type 'num'.
*/

function swap(list, a, b){
  let temp = list.getAt(a);
  list.setAt(a, list.getAt(b));
  list.setAt(b, temp);

  return;
}

function partition(list, low, high){
  let pivot = list.getAt(high);
  let i = low - 1;

  for(let j = low; j <= high - 1; j = j + 1){
    if(list.getAt(j) <= pivot){
      i = i + 1;
      swap(list, i, j);
    }
  }
  swap(list, i + 1, high);

  return i + 1;
}

function quickSort(list, low, high){
  if(low < high){
    let q = partition(list, low, high);
    quickSort(list, low, q - 1);
    quickSort(list, q + 1, high);
  }

  return;
}
        \end{lstlisting}
    
    
    
    \item Binary Search
        \begin{lstlisting}
function binarySearch(list, target){
  let left = 0;
  let right = list.size() - 1;

  while(left <= right){
    let mid = std::math::floor((left + right) / 2);
    if(list.getAt(mid) == target){
      return mid;
    }elif(list.getAt(mid) > target){
      right = mid - 1;
    }else{
      left = mid + 1;
    }
  }

  return -1; // Target value not present inside the list.
}
        \end{lstlisting}
    \item Binary Search Tree (BST)
        \begin{lstlisting}
/*
Code that implements the Binary Search Tree data-structure by using a pointers approach.
*/

class TreeNode{
  method init(key, value){
    self.key = key;
    self.value = value;
    self.left = nil;
    self.right = nil;
  }

  method str(){
    return "Node Key: " + self.key + " - Node Value: " + self.value;
  }
}

class BST{
  method init(){
    self.root = nil;
    self.length = 0;
  }

  method insert(key, value){
    if(self.root == nil){
      self.root = TreeNode(key, value);
    }else{
      let curr = self.root;
      while(true){
        if(key < curr.key and curr.left == nil){
          curr.left = TreeNode(key, value);
          break;
        }elif(key < curr.key and curr.left != nil){
          curr = curr.left;
        }elif(curr.key < key and curr.right == nil){
          curr.right = TreeNode(key, value);
          break;
        }else{
          curr = curr.right;
        }
      }
    }

    self.length = self.length + 1;

    return;
  }

  method aux_delete(root, key){
    if(root == nil){
      return root;
    }

    if(key < root.key){
      root.left = self.aux_delete(root.left, key);
    }elif(key > root.key){
      root.right = self.aux_delete(root.right, key);
    }else{
      // Scenario where the node to be deleted has one child or no child.
      if(root.left == nil){
        return root.right;
      }elif(root.right == nil){
        return root.left;
      }

      // Scenario where the node to be deleted has two children.
      // In this case, the inorder sucessor of the node to be deleted is retrieved:
      let temp = self.findMinimum(root.right);

      // Replacing the root's key and value with its inorder successor's key and value:
      root.key = temp.key;
      root.value = temp.value;

      // Deleting the inorder successor:
      root.right = self.aux_delete(root.right, temp.key);
    }

    return root;
  }

  method delete(key){
    self.root = self.aux_delete(self.root, key);
    self.length = self.length - 1;

    return;
  }

  method find(key){
    let curr = self.root;

    while(curr != nil and curr.key != key){
      if(key < curr.key){
        curr = curr.left;
      }else{
        curr = curr.right;
      }
    }

    return curr == nil ? "Could not find the key inside the BST" : curr;
  }

  method size(){
    return self.length;
  }

  method findMinimum(node){
    let curr = node;

    while(curr.left != nil){
      curr = curr.left;
    }

    return curr;
  }

  method inorderTraversal(curr){
    if(curr == nil){
      return;
    }
    self.inorderTraversal(curr.left);
    std::io::print(curr);
    self.inorderTraversal(curr.right);
  
    return;
  }
}
        \end{lstlisting}

    
    \item Binary Heap
        \begin{lstlisting}
/*
Code that implements the Binary Min Heap data-structure.
*/

class MinBinaryHeap{
  method init(){
    self.heap = [];
  }

  method empty(){
    return self.size() == 0 ? true : false;
  }

  method size(){
    return self.heap.size();
  }

  method top(){
    if(self.size() == 0){
      return "The Binary Heap is empty!";
    }else{
      return self.heap.getAt(0);
    }
  }

  method pop(){
    if(self.size() == 0){
      return "The Binary Heap is empty!";
    }else{
      self.swap(0, self.size() - 1);

      let minValue = self.heap.pop();
      self.bubbleDown(0);

      return minValue;
    }
  }

  method push(value){
    self.heap.append(value);
    self.bubbleUp(self.size() - 1);

    return;
  }

  method swap(i, j){
    let temp = self.heap.getAt(i);
    self.heap.setAt(i, self.heap.getAt(j));
    self.heap.setAt(j, temp);

    return;
  }

  method bubbleDown(index){
    let smallest = index;
    let leftChild = 2 * index + 1;
    let rightChild = 2 * index + 2;

    if(leftChild < self.heap.size() and self.heap.getAt(leftChild) < self.heap.getAt(smallest)){
      smallest = leftChild;
    }

    if(rightChild < self.heap.size() and self.heap.getAt(rightChild) < self.heap.getAt(smallest)){
      smallest = rightChild;
    }

    if(smallest != index){
      self.swap(index, smallest);
      self.bubbleDown(smallest);
    }

    return;
  }

  method bubbleUp(index){
    let parentIndex = std::math::floor((index - 1) / 2);
    if(index > 0 and self.heap.getAt(index) < self.heap.getAt(parentIndex)){
      self.swap(index, parentIndex);
      self.bubbleUp(parentIndex);
    }

    return;
  }
}
        \end{lstlisting}


    \item Depth First Search (DFS)
        \begin{lstlisting}
function dfs(source, adjacencyList, visitingOrder, visited){
  visited.setAt(source, true);
  visitingOrder.append(source);

  for(let i = 0; i < adjacencyList.getAt(source).size(); i = i + 1){
    let neighbor = adjacencyList.getAt(source).getAt(i);
    if(!visited.getAt(neighbor)){
      dfs(neighbor, adjacencyList, visitingOrder, visited);
    }
  }

  return;
}
        \end{lstlisting}

        
    \item Breadth First Search (BFS)
        \begin{lstlisting}
function bfs(source, adjacencyList, visited, distance){
  visited.setAt(source, true);
  distance.setAt(source, 0);

  let queue = Queue();
  queue.push(source);

  while(!queue.empty()){
    let currNode = queue.pop();

    for(let i = 0; i < adjacencyList.getAt(currNode).size(); i = i + 1){
      let neighbor = adjacencyList.getAt(currNode).getAt(i);

      if(!visited.getAt(neighbor)){
        visited.setAt(neighbor, true);
        distance.setAt(neighbor, 1 + distance.getAt(currNode));
        queue.push(neighbor);
      }
    }
  }

  return;
}
        \end{lstlisting}
    \item Dijkstra's Shortest Path Algorithm
        \begin{lstlisting}
function dijkstraAlgorithm(source, adjacencyList, distance){
  let minHeap = MinBinaryHeap(); // Modified to receive lists of 2 elements.
  distance.setAt(source, 0);

  minHeap.push([0, source]);

  while(!minHeap.empty()){
    let currNodeInfo = minHeap.pop();
    let minPath = currNodeInfo.getAt(0);
    let currNode = currNodeInfo.getAt(1);

    for(let i = 0; i < adjacencyList.getAt(currNode).size(); i = i + 1){
      let neighbour = adjacencyList.getAt(currNode).getAt(i).getAt(0);
      let edge = adjacencyList.getAt(currNode).getAt(i).getAt(1);
      if(distance.getAt(currNode) + edge < distance.getAt(neighbour)){
        distance.setAt(neighbour, distance.getAt(currNode) + edge);
        minHeap.push([distance.getAt(neighbour), neighbour]);
      }
    }
  }

  return;
}
        \end{lstlisting}
\end{itemize}

\newpage

\end{comment}

\newpage

\section{Comparing Bleach with ChocoPy, Cool and MiniJava}
In this section, a comparison between Bleach, ChocoPy, Cool and MiniJava is presented in Table 5.1 in terms of the features available in these programming languages.


\begin{table}[h!]
    \centering
    \begin{tabular}{|p{3.2cm}|p{3cm}|p{3cm}|p{3cm}|p{3cm}|p{3cm}|}
        \hline
        \textbf{Feature} & \textbf{Bleach} & \textbf{ChocoPy} & \textbf{Cool} & \textbf{MiniJava} \\  % First row: header
        \hline
        \textbf{Type System} & Dynamically-Typed & Statically-Typed & Statically-Typed & Statically-Typed \\  % Data rows
        \hline
        \textbf{Built-In Types} & \texttt{bool}, \texttt{nil}, \texttt{num}, \newline \texttt{list}, \texttt{str} & \texttt{int}, \texttt{bool}, \texttt{None}, \texttt{list}, \texttt{str} & \texttt{Int}, \texttt{Bool}, \texttt{String} & \texttt{int}, \texttt{int[ ]} \texttt{boolean}, \texttt{void} \\
        \hline
        \textbf{Arithmetical Operators} & \texttt{+}, \texttt{-}, \texttt{*}, \texttt{/}, \texttt{\%} & \texttt{+}, \texttt{-}, \texttt{*}, \texttt{//}, \texttt{\%} & \texttt{+}, \texttt{-}, \texttt{*}, \texttt{/} & \texttt{+}, \texttt{-}, \texttt{*} \\
        \hline
        \textbf{Comparison Operators} & \texttt{>}, \texttt{>=}, \texttt{<}, \texttt{<=} & \texttt{>}, \texttt{>=}, \texttt{<}, \texttt{<=} & \texttt{<}, \texttt{<=} & \texttt{<} \\
        \hline
        \textbf{Equality Operators} & \texttt{==}, \texttt{!=} & \texttt{==}, \texttt{!=}, \texttt{is} & \texttt{=} & No support \\
        \hline
        \textbf{Logical Operators} & \texttt{and}, \texttt{or}, \texttt{!} & \texttt{and}, \texttt{or}, \texttt{not} & \texttt{not} & \texttt{\&\&}, \texttt{!} \\
        \hline
        \textbf{Assignment Operator} & \texttt{=} & \texttt{=} & \texttt{<-} & \texttt{=} \\
        \hline
        \textbf{Ternary Operator Support} & Yes & Yes & No & No \\
        \hline
        \textbf{If Statement Support} & \texttt{if}, \texttt{elif}, \texttt{else} & \texttt{if}, \texttt{elif}, \texttt{else} & \texttt{if}, \texttt{else} & \texttt{if}, \texttt{else} \\
        \hline
        \textbf{Loops Support} & \texttt{for}, \texttt{do-while}, \texttt{while} & \texttt{while}, \texttt{for in} (only in lists and strings) & \texttt{while} & \texttt{while} \\
        \hline
        \textbf{Break/Continue Statements Support} & Yes, Yes & No, No & No, No & No, No \\
        \hline
        \textbf{Function Declaration Support} & Yes (with the \texttt{function} keyword) & Yes (with the \texttt{def} keyword) & Yes (only method declaration within classes) & Yes (only method declaration within classes) \\
        \hline
        \textbf{Anonymous Function Support} & Yes (with the \texttt{lambda} keyword) & No & No & No \\
        \hline
        \textbf{Comments} & Single-line (\texttt{//}) and Multi-line (\texttt{/**/}) & Single-Line (\texttt{\#}) & Single-line (\texttt{---}) and Multi-line (\texttt{**}) & Single-line (\texttt{//}) and Multi-line (\texttt{/**/}) \\
        \hline
        \textbf{Language Paradigm} & Object-Oriented and Interpreted & Object-Oriented and Compiled & Object-Oriented and Compiled & Object-Oriented and Compiled \\
        \hline
        \textbf{Inheritance} & Single & Single & Single & Single \\
        \hline
    \end{tabular}
    \caption{Comparison between Bleach, ChocoPy, Cool and MiniJava.}
    \label{tab:example5x5}
\end{table}