# Code test

Given the following tree definition (in Python 3+)

class Expr:
    pass

@dataclass
class BinOp(Expr):
    l  : Expr
    op : str
    r  : Expr

@dataclass
class Literal(Expr):
    lit : int

@dataclass
class IfExpr(Expr):
    cond      : Expr
    then_expr : Expr
    else_expr : Expr

Implement the evaluation function with the following prototype:

def eval(expr: Expr) -> int:
    pass

For if-expression conditions, you can assume that booleans are encoded as in C: 0 is `false` and anything else is `true`.

Here is the complete code template with tests

from dataclasses import dataclass

class Expr:
    pass

@dataclass
class BinOp(Expr):
    l  : Expr
    op : str
    r  : Expr

@dataclass
class Literal(Expr):
    lit : int

@dataclass
class IfExpr(Expr):
    cond      : Expr
    then_expr : Expr
    else_expr : Expr

def eval(expr: Expr) -> int:
    ...


for expr, expected_res in [
    (BinOp(Literal(1), "+", Literal(2)), 3),
    (BinOp(Literal(3), "-", Literal(1)), 2),
    (IfExpr(BinOp(Literal(1), "+", Literal(2)), Literal(1), Literal(2)), 1),
    (IfExpr(Literal(0), Literal(1), Literal(2)), 2),
]:
    res = eval(expr)
    if res != expected_res:
        print(f"Unexpected result from evaluating {expr}: {res}")
    else:
        print(f"Eval {expr} = {res}")

## Advanced question 1: type_check function

Add boolean literals, and the `and` and `or` short circuit operators. Add a type_check function to check the correctness node types.

One example of an error that the type_check function should be able to catch, is that operands of an operator should be of the same type.

**The type_check function is expected to compute the type of an expression. In case of error (type checking failure), it must print the error and raise an exception.**

from dataclasses import dataclass
from typing import Union

class Expr:
    pass

@dataclass
class BinOp(Expr):
    l  : Expr
    op : str
    r  : Expr

@dataclass
class Literal(Expr):
    lit : Union[int, bool]

@dataclass
class IfExpr(Expr):
    cond      : Expr
    then_expr : Expr
    else_expr : Expr

def eval(expr: Expr) -> Union[int, bool]:
    ...

def type_check(expr: Expr) -> type:
    ...


for expr, expected_res in [
    (IfExpr(Literal(False), Literal(1), Literal(2)), 2),
    (IfExpr(Literal(True), Literal(1), Literal(2)), 1),
    (IfExpr(Literal(1), Literal(2), Literal(True)), None),
    (IfExpr(Literal(True), Literal(False), Literal(False)), False),
    (IfExpr(Literal(True), Literal(True), Literal(2)), None),
    (BinOp(Literal(True), "+", Literal(False)), None),
    (BinOp(Literal(True), "or", Literal(False)), True),
    (BinOp(Literal(1), "or", Literal(2)), None),
    (BinOp(BinOp(Literal(1), "+", Literal(3)), "/", IfExpr(Literal(True), Literal(1), Literal(2))), 4)
]:
    try:
        type_check(expr)
        res = eval(expr)
        if res != expected_res:
            print(f"Unexpected result from evaluating {expr}: {res}")
        else:
            print(f"Eval {expr} = {res}")
    except Exception as exc:
        print(
            f"{'Expected'if expected_res is None else 'Unexpected'} "
            f"type checking failure for {expr}:\n  {exc}"
        )

## Advanced question 2: Let expressions

Add an expression to the evaluator: this expression is called a `Let` expression, and allows the user to introduce a temporary name for an intermediate expression.

from __future__ import annotations

from dataclasses import dataclass
from typing import Any, Dict, Optional, Union

class Expr:
    pass

@dataclass
class BinOp(Expr):
    l  : Expr
    op : str
    r  : Expr

@dataclass
class Literal(Expr):
    lit : Union[int, bool]

@dataclass
class IfExpr(Expr):
    cond      : Expr
    then_expr : Expr
    else_expr : Expr

@dataclass
class Let(Expr):
    name : str
    val  : Expr
    into : Expr

@dataclass
class Ref(Expr):
    name: str

class Scope:
    def __init__(self, parent: Optional[Scope]):
        self.data: Dict[str, Any] = {}
        self.parent = parent

    def get(self, key: str) -> Any:
        if key in self.data:
            return self.data[key]
        elif self.parent is None:
            raise KeyError
        else:
            return self.parent.get(key)

    def set(self, key: str, val: Any) -> None:
        self.data[key] = val

    def new_scope(self) -> Scope:
        return Scope(self)


def eval(expr: Expr, scope: Optional[Scope] = None) -> Union[int, bool]:
    ...

def type_check(expr: Expr, scope: Optional[Scope] = None) -> type:
    ...

for expr in [
    Let("a", Literal(1), BinOp(Ref("a"), "+", Literal(2))),
    Let("a", Literal(True), BinOp(Ref("a"), "+", Literal(2)))
]:
    try:
        type_check(expr)
        print(f"Eval {expr} = {eval(expr)}")
    except Exception as exc:
        print(f"Type checking {expr} failed:\n  {exc}")

# General questions

* What is a hash table?
* How is it implemented?
* What is the complexity of basic operations?

* What is the asymptotic complexity of fib? Modify it to make it linear any way you want.

  function fib(n) 
       if n <= 1 return n
       return fib(n − 1) + fib(n − 2)

* What is dynamic programming? What is memoization?