Evaluate a Lisp-Style Prefix Expression Language With ADD, MULT and LET Variables

Implement `parse(expression)`, which evaluates an expression in a small Lisp-style language and returns its integer value. Despite its name, the function both parses and evaluates. The language uses prefix notation. An expression is either an integer literal or a parenthesized list whose first item is an operator and whose remaining items are operand expressions. Operands can themselves be nested expressions. The base language has two operators: `ADD` returns the sum of its operands, and `MULT` returns their product. ```text parse("( ADD 3 4 )") == 7 parse("( MULT 3 4 )") == 12 parse("( MULT 3 ( ADD 3 4 ) )") == 21 ``` After the base version works and passes some tests, the interviewer extends the language with variables, and then asks how the bindings should be stored when they can be nested. ### Constraints and Clarifications - In the examples, every token, including each parenthesis, is separated by a single space. - Operator names are uppercase. ### Clarifying Questions - Does every operator take exactly two operands, as in the examples, or any number of them? - Can integer literals be negative? - Can a parenthesis touch a neighboring token, as in `(ADD 3 4)`, or is the spacing always as in the examples? - How should malformed input be reported: unbalanced parentheses, an unknown operator, a wrong number of operands, or an empty string? ### Part 1 — Evaluate ADD and MULT Implement `parse` for the base language and test it, including the three examples above. State its time and space complexity. ```hint Let the grammar shape the code Write the grammar in one line. Notice that every operand has the same shape as the whole expression, and that each nested expression ends exactly where its matching parenthesis closes. ``` #### What This Part Should Cover - Turning the string into tokens, and consuming nested expressions so that each one hands its value back to its parent - Rejecting malformed input with clear errors - Tests that cover both operators, nesting, and invalid input - Complexity in terms of input length and nesting depth ### Part 2 — Add LET Extend the language with `LET`, which binds a variable name to a value so that later expressions can use the name as an operand. The input can now contain more than one top-level expression: ```text parse("( LET x 3 ) ( ADD 4 x )") == 7 ``` The example leaves several rules open. Settle them with the interviewer, then update your implementation and your tests. ```hint Where bindings live Evaluation now needs state that outlives a single expression. Decide what owns that state, when it is created, and what the value of the whole program is when there are several top-level expressions. ``` #### Clarifying Questions for this Part - May the same variable be assigned more than once? If so, which value do later expressions see? - What should a program consisting of a single `LET` expression return? - What should a program made only of several `LET` expressions, with no other expression, return? - Can the value in a `LET` be a nested expression or another variable, and what happens when an expression uses a variable that was never bound? #### What This Part Should Cover - An explicit answer to each open rule, reflected in both the code and the tests - How a sequence of top-level expressions is evaluated, and which value is returned - Variable lookup, rebinding, and the error for an unbound name ### Part 3 — Nested LET scopes Suppose `LET` can appear at several levels of nesting. What data structure would you use to hold the bindings? One proposal is a dictionary per nesting level, deep-copying the enclosing level's dictionary whenever a new level starts. The interviewer asked whether you would use a stack instead. An objection raised against the stack was that a variable bound once but used several times might no longer be on the stack when it is used the second time. Evaluate both options, settle that objection, and choose one. ```hint Name the events List the exact events that add or remove a binding, and check which structure makes each event cheap without changing what a later read returns. ``` #### Clarifying Questions for this Part - Is a binding made inside a nested expression still visible after that expression closes? For example, in `( ADD ( LET x 2 ) x ) ( MULT x 10 )`, is `x` bound in the second top-level expression? - If an inner level binds a name that an outer level already bound, should the inner binding shadow the outer one, and should the outer value come back afterwards? #### What This Part Should Cover - Scope rules: when a binding becomes visible and when it disappears - The time and memory cost of copying per level versus a shared structure - Whether the stack objection holds, shown with a concrete trace ### What a Strong Answer Covers - A correct, tested base evaluator finished quickly enough to leave time for the extension - Open language rules raised and resolved before the code changes, not discovered through failing tests - Tokenizing, parsing, and evaluation kept separate enough that new operators are cheap to add - A scope structure justified by its complexity and by the chosen semantics - Clear errors for malformed input and unbound variables ### Follow-up Questions - How would you support a `LET` with a body, such as `( LET x 3 ( ADD x 1 ) )`, where the binding is visible only inside the body? - How would you evaluate very deeply nested input without hitting the language's recursion limit? - What would user-defined functions with closures require from your binding structure?