Implement a Simple Lisp Interpreter in Go

This challenge asks you to build a basic interpreter for a simplified Lisp-like language in Go. Interpreters are fundamental tools in computer science, enabling the execution of code written in various programming languages. This exercise will deepen your understanding of parsing, abstract syntax trees, and recursive evaluation.

Problem Description

You need to implement an interpreter for a small, Lisp-inspired language. The language will support basic arithmetic operations, variable definition, and conditional logic.

Key Requirements:

1. Lexing/Tokenization: The interpreter must first break down the input program string into a sequence of meaningful tokens (e.g., numbers, symbols, parentheses, operators).
2. Parsing: Convert the token stream into an Abstract Syntax Tree (AST). The AST will represent the structure of the program.
3. Evaluation/Interpretation: Traverse the AST and execute the program logic. This involves:
   • Arithmetic Operations: Support +, -, *, / for integers.
   • Variable Definition: Support (define var value) to bind a symbol to a value.
   • Variable Lookup: Retrieve the value of a defined variable.
   • Conditional Logic: Support (if condition then else) where condition evaluates to a boolean (we'll simplify this: any non-zero number is true, zero is false).
   • Basic Data Types: Support integers and symbols.

Expected Behavior:

The interpreter should take a string representing a program in the custom language and return the evaluated result of the program. For expressions that don't have a single explicit return value (like a sequence of definitions), the result should be the value of the last expression evaluated.

Important Edge Cases:

• Handling of unbalanced parentheses.
• Division by zero.
• Undefined variables.
• Order of operations (implicitly handled by the AST structure for arithmetic).

Examples

Example 1:

Input: "(+ 1 2)"
Output: 3
Explanation: The input is a simple addition expression. The interpreter parses it, builds an AST representing `1 + 2`, and evaluates it to `3`.

Example 2:

Input: "(define x 10)(* x 5)"
Output: 50
Explanation: First, the variable `x` is defined with the value `10`. Then, `x` is multiplied by `5`. The interpreter looks up `x`'s value and computes `10 * 5`, returning `50`.

Example 3:

Input: "(if (> 5 3) 10 20)"
Output: 10
Explanation: The condition `(> 5 3)` evaluates to true (since 5 is indeed greater than 3). Therefore, the `then` part (`10`) is evaluated and returned.

Example 4:

Input: "(if 0 100 200)"
Output: 200
Explanation: In our simplified language, `0` is considered false. Therefore, the `else` part (`200`) is evaluated and returned.

Example 5:

Input: "(define y (+ 2 3))(- y 1)"
Output: 4
Explanation: `y` is defined as the result of `2 + 3` (which is 5). Then, `y - 1` is evaluated, resulting in `5 - 1 = 4`.

Constraints

• Input programs will be strings.
• Supported data types are integers and symbols.
• Arithmetic operations (+, -, *, /) will only operate on integers.
• Division by zero will result in an error (e.g., panic or return an error value).
• The number of nested parentheses will not exceed 100.
• The length of any single expression or definition will not exceed 256 characters.
• The interpreter should be able to handle a reasonable number of variable definitions (e.g., up to 100 distinct variables within a single program execution).

Notes

• You will need to define structures to represent your tokens and AST nodes.
• Consider using recursion extensively for parsing and evaluation.
• A map is a suitable data structure for storing variable bindings.
• Error handling for invalid syntax, division by zero, and undefined variables is crucial.
• For simplicity, you can assume that inputs are well-formed in terms of basic syntax, focusing on the core interpretation logic. However, robust error handling for malformed inputs is a good practice.
• You might want to start by implementing a simple calculator that only handles arithmetic, then gradually add features like define and if.