Symbol Tables, Scala-ifying legacy code, and other design decisions

Symbol Tables

It's come time to write a symbol table for Magnificalc. It will allow user-defined functions, a function-registration mechanism, and multiple variables. It will also enable undefined variable solving (!) something useful for a CAS. There are many options with writing symbol tables:

• Binary Tree
• Binary Tree with Red-Black autobalancing algorithm
• Hash Table
• Linked List of name, value, and type sets

These all have their positives and negatives. Binary Trees must stay balanced to be fast, but if a binary tree is balanced, lookups are very fast (O(log n) time, O(n) space). The Red-Black tree algorithm keeps binary trees balanced with simple and quick algorithms to keep a set of stringent properties true. Those algorithms run in O(log n) time for insertions and deletions.

A Hash Table would have to have a bucket size large enough that there would not be any hash collisions, if not, the worst-case scenario is O(n) time. This is unacceptable if many variables and functions are present.

A Linked List would be a very poor choice, because a linked list's average lookup time is O(n). It would work for a small table, but not for many variables and functions.

Scala-ifying legacy code

This is the process of converting legacy Java code to Scala to take advantage of Scala features like traits and implicit type conversions. I have a significant amount of legacy code developed in a programming class in Java that I am reusing for this project, but I would like to be able to take advantage of Scala's features. Short of a full rewrite (which will happen eventually), I am starting with something like the following:

(Java) public class ExpressionTree implements ExpressionNode
{    
    ...    
    public ExpressionNode getRoot()
    {
        return root;
    }
    ...
}
(Scala) class SExpressionTree(tree:ExpressionTree)
{
    def root() = tree.getRoot()
}
implicit def exprTree2ScalaExprTree(tree:ExpressionTree) = new SExpressionTree(tree)

This will enable the ExpressionTrees to be used as if they were native Scala objects. This is a stopgap measure until the whole library is ported to Scala, and then the symbol table will be implemented.