4
\$\begingroup\$

I'm currently in the process of writing my own programming language and the Virtual Machine for the language is responsible for handing all of the local variable scopes.

I need to support the following operations as fast as possible:

  • putLocal - puts an object into the stack
  • getLocal - retrieves an object from the stack
  • upScope - enters a new scope
  • downScope - leaves a single scope (in practice we can fall back multiple but I'll leave the operation elementary)

Originally I had a naive stack based system where the variables were stored in levels of a stack which had the following time complexities for the key operations, with \$n\$ the total levels in the stack:

  • putLocal - \$O(n)\$
  • getLocal - \$O(n)\$
  • upScope - \$O(1)\$
  • downScope - \$O(1)\$

I realised I could do better than this recently and devised a new lookup table method of storing the variables, which has the following time complexities as far as I can tell, where \$v\$ is the number of variables in existence and \$m\$ is the number of scope levels that do not inherit parents (i.e. function calls, it gets larger as your go into deep recursion):

  • putLocal - \$O(1)\$ or \$O(log(m))\$ (depending on Java TreeMap.lastKey() and whether we are overriding or not)
  • getLocal - \$O(1)\$ or \$O(log(m))\$ (depending on Java TreeMap.lastKey())
  • upScope - \$O(1)\$
  • downScope - \$O(v)\$ or \$O(vlog(m))\$ (depending on Java TreeMap.lastKey())

However, the downScope operation's runtime is much worse than the original scheme (due to hidden constants in complexity, the original stack implementation's downScope was literally just discarding the head of the stack) and I'd like to see hear any ways it could possibly be improved.

Here's the code that implements the new scheme:

class LocalScopeTable
{
    private int currentDepth;
    private Map<String, TreeMap<Integer, Object>> variableMap;
    // Stack<T> and LinkedStack<T> are efficient minimalistic stacks
    // They can be replaced by a Java Deque for any testing
    private Stack<Integer> scopeSearchLimit;

    LocalScopeTable()
    {
        currentDepth = 0;
        variableMap = new HashMap<>();
        scopeSearchLimit = new LinkedStack<>();
        scopeSearchLimit.push(0);
    }

    /** Puts a local variable into the table, overriding the deepest accessible definition in scope. */
    public void putLocal(String name, Object local)
    {
        if (!variableMap.containsKey(name))
        {
            TreeMap<Integer, Object> newEntry = new TreeMap<>();
            newEntry.put(currentDepth, local);
            variableMap.put(name, newEntry);
        }
        else
        {
            TreeMap<Integer, Object> depthMap = variableMap.get(name);
            int depth = depthMap.lastKey();
            if (depth >= scopeSearchLimit.peek()) depthMap.put(depth, local);
            else depthMap.put(currentDepth, local);
        }
    }

    /** Retrieves a local from the table, retrieving the variable in the most accessible scope level */
    public Object getLocal(String name)
    {
        if (!variableMap.containsKey(name))
        {
            System.err.println(String.format("Local %s not defined in scope", name));
            System.exit(1);
            return null;
        }
        Entry<Integer, Object> e = variableMap.get(name).lastEntry();
        if (e.getKey() < scopeSearchLimit.peek())
        {
            System.err.println(String.format("Local %s not defined in scope", name));
            System.exit(1);
            return null;
        }
        return e.getValue();
    }

    /** Enters a new scope, if inheritsParent is false then we entered a function's scope
        and we lose access to the previous levels of scope */
    public void upScope(boolean inheritsParent)
    {
        if (!inheritsParent) scopeSearchLimit.push(currentDepth);
        else scopeSearchLimit.push(scopeSearchLimit.peek());
        currentDepth++;    
    }

    /** Leaves "n" scopes. This needs to clear the entries for destroyed scopes from the table. */      
    public void downScope(int n)
    {
        for (int k = 0; k < n; k++)
        {
            List<String> removeKeys = new ArrayList<>();
            for (Entry<String, TreeMap<Integer, Object>> e: variableMap.entrySet())
            {
                if (e.getValue().lastKey() == currentDepth) e.getValue().pollLastEntry();
                if (e.getValue().isEmpty()) removeKeys.add(e.getKey());
            }
            removeKeys.parallelStream().forEach(key -> variableMap.remove(key));
            currentDepth--;
            scopeSearchLimit.pop();
        }
    }
}

For clarity, the scopeSearchLimit is a stack which keeps track of the maximum scope we can go into to find a variable (i.e. if there are no function calls this would be the root scope 0 otherwise it is the last time a function was called). If we aren't a function call then we just take the value currently on the top of the stack for ourselves.

Feel free to ask for any clarifications. I'm sure I've forgotten to explain something important somewhere along the line.

\$\endgroup\$
2
\$\begingroup\$

I think I have a quicker approach. It does however make the assumption that you don't have block scopes.

Some languages like JavaScript didn't use block scopes although I believe that's changing with the addition of the let keyword. If you wanted to implement block scope later I think you could copy the 'JS approach' and use a new keyword for it. Although checking for variables would then take longer as you would need to check the 'block scope' variables in each scope until the top parent.

import java.util.HashMap;
import java.util.Stack;

class LocalScopeTable {
    class Scope {
        protected Scope top_parent;
        HashMap<String, Object> locals = new HashMap<String, Object>();

        Scope(Scope parent){ top_parent = parent; }
        Scope(){ top_parent = this; }

        protected void putLocal(String name, Object local){
            locals.put(name, local);
        }

        protected Object getLocal(String name){
            return locals.get(name);
        }
    }

    Stack<Scope> scope_chain = new Stack<Scope>();
    int current_scope;

    LocalScopeTable(){
        scope_chain.push(new Scope()); //Declare initial scope
    }

    public void putLocal(String name, Object local){//O(1)
        scope_chain.peek().top_parent.putLocal(name, local);
    }

    public Object getLocal(String name){//O(1) unless the same hash gets used miraculously 
        return scope_chain.peek().top_parent.getLocal(name);
    }

    public void upScope(boolean inheritsParent){//O(1)
        if(inheritsParent){
            scope_chain.push(new Scope(scope_chain.peek().top_parent));
        }else{
            scope_chain.push(new Scope());
        }
    }

    public void downScope(int k){//O(1) amortized (I think)
        if(k > 0 && scope_chain.size() > 1){//prevent removal of initial scope
            scope_chain.pop();
            downScope(k-1);
        }
    }
}

This class stores each scope level as a 'Scope' Object in a Stack. Whenever upScope() is called a new scope is pushed onto the stack with top_parent parameter set to the top_parent of the current scope (if it inherits from parent). If it doesn't inherit then top_parent is set to be itself. In this way if there's a chain of inheritance, all variables are accessed from the top of the chain.

The downScope() method works by simply popping Scopes from the stack. The time complexity of this would be of the order of the number of pops, but I believe if it's amortized against upScope() we get O(1).

Calling getLocal() or putLocal() on a given scope simply calls the same method on the scope at the top of the chain where all of the variables are kept in a HashMap.

Hopefully this provides a solution, or at least is a step in the right direction. Please let me know if anything could have been explained better, this is my first SE response so I'm sure there's room to improve, or indeed if I made a mistake, I'm not too sure about the block scope stuff I mentioned above.

Edit: Possible method of allowing block scope.

Have 2 new HashMaps as parameters of Scope, one that maps the 'block scope variables' that were declared in that scope to their value, and another that is only defined in the parent scope that maps a 'block scope variable' to the scope under the parent in which it occurs (It can only occur once).

When declaring a 'block scope variable' you add a new entry to the HashMap in the top-parent of the current scope, mapping the name to the current scope, and also add the variable to the HashMap in the current scope.

putLocal() then needs to be modified to first check for the 'block scope variables'. It checks the top_parent to check first of all if the variable exists otherwise it can declare it. Note: in order to check if a variable exists, you have to check for both a mapping in the HashMap and that the variable exists in the scope referenced by the HashMap. This is because upScope() -> downScope() -> upScope() could add a variable to the HashMap that won't exist in the second upScope(). If the variable does exist, then you now know where to update. Approach getLocal() in a similar manner, just don't change any values.

This makes a bit of a trade-off in terms of space for speed here. In the worst case many variables could be declared below the parent of the scope chain, but as long as we don't downScope() past the parent_scope the HashMap is going to contain a lot of redundant mappings. But still O(1).

I haven't had a chance to check this approach yet but it seems sound to me. Let me know how it works out for you, or if anything could be improved.

\$\endgroup\$
  • \$\begingroup\$ Do you mean you need to edit putLocal not getLocal? \$\endgroup\$ – J_mie6 Mar 23 '16 at 14:42
  • \$\begingroup\$ So, on testing out this answer, it is around twice as slow for get and put and up. But is significantly faster for down. If you expect low levels of recursion and nested function calls and high numbers of accesses, my proposed scheme is faster. However if you expect the inverse, then Michaels scheme is faster. It is likely my Virtual Machine will do both schemes in the future! \$\endgroup\$ – J_mie6 Mar 23 '16 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.