Symbol Resolution in Go

Symbol resolution is a fundamental aspect of compilers and interpreters, determining the meaning of identifiers (variables, functions, types) within a program. This challenge asks you to implement a simplified symbol resolution mechanism for a subset of Go-like code, focusing on variable lookup within a scope hierarchy. Successfully completing this challenge will demonstrate your understanding of scope, data structures for symbol storage, and recursive algorithms.

Problem Description

You are tasked with creating a symbol resolution system that can determine the value of a variable given its name and a list of scopes. A scope represents a block of code where a variable is defined. Scopes are nested, meaning variables defined in an inner scope can shadow variables with the same name in an outer scope. The system should support multiple scopes, each containing a map of variable names to their values.

What needs to be achieved:

• Implement a Scope struct that holds a map of variable names (strings) to their values (interface{} - allowing for different data types).
• Implement a SymbolTable struct that manages a list of scopes, representing the scope hierarchy.
• Implement a Resolve function that takes a variable name (string) and a SymbolTable as input. The function should traverse the scopes in reverse order (inner scopes first) to find the variable.
• If the variable is found in a scope, the function should return its value.
• If the variable is not found in any scope, the function should return nil.

Key Requirements:

• The SymbolTable should maintain the order of scopes.
• The Resolve function should prioritize variables defined in inner scopes over variables defined in outer scopes (shadowing).
• The interface{} type should be used to allow for variables of different types.
• Error handling is not required; return nil if the variable is not found.

Expected Behavior:

The Resolve function should return the value associated with the variable name if it exists in any of the scopes, starting with the innermost scope. If the variable is not found, it should return nil.

Edge Cases to Consider:

• Empty SymbolTable (no scopes).
• Variable name not found in any scope.
• Multiple scopes with the same variable name (inner scope should shadow outer scope).
• Empty scopes (scopes with no variables defined).

Examples

Example 1:

Input:
SymbolTable:
  Scope 1: {"x": 10, "y": "hello"}
  Scope 2: {"z": true}
Variable Name: "x"
Output: 10
Explanation: "x" is found in Scope 1. Scope 2 does not contain "x".

Example 2:

Input:
SymbolTable:
  Scope 1: {"x": 10}
  Scope 2: {"x": 20}
Variable Name: "x"
Output: 20
Explanation: "x" is found in both Scope 1 and Scope 2. Scope 2 (inner scope) shadows Scope 1, so the value from Scope 2 is returned.

Example 3:

Input:
SymbolTable:
  Scope 1: {"a": 1}
  Scope 2: {"b": 2}
Variable Name: "c"
Output: nil
Explanation: "c" is not found in any of the scopes.

Constraints

• Variable names will be strings.
• Values can be of any type (represented by interface{}).
• The number of scopes in a SymbolTable will be between 0 and 100.
• The number of variables in a scope will be between 0 and 50.
• Performance: The Resolve function should complete in O(n) time, where n is the number of scopes.

Notes

Consider using a slice of Scope structs to represent the scope hierarchy in the SymbolTable. The Resolve function will need to iterate through the scopes in reverse order. Think about how to efficiently traverse the scopes and check for the existence of a variable within each scope. The order of scopes in the SymbolTable is crucial for correct shadowing behavior.