use Collection.Generic;

class MiniLisp {
    function : Main(args : String[]) ~ Nil {
        if(args->Size() = 1) {
            root := Parser->New(args[0])->Parse();
            if(root <> Nil) {
                Evaluator->New(root)->Evaluate();
            };
        };
    }
}

#--- Evaluator ---

class Evaluator {
    @root : Node;
    @stack : Stack<Value>;
    @symbol_tables : List<Hash<String, Value>>;
    @is_debug : Bool;

    New(root : Node) {
        @root := root;
        @stack := Stack->New()<Value>;
        @symbol_tables := List->New()<Hash<String, Value>>;
        @is_debug := true;

        Value->Init();
    }

    method : public : Evaluate() ~ Nil {
        if(@is_debug) {
            "\n--- Evaluate ---"->PrintLine();
        };

        Evaluate(@root);
    }

    method : Evaluate(node : Node) ~ Nil {
        select(node->GetType()) {
            label Node->Type->STR_LIT {
                found := false;
                name := node->GetStringValue();

                @symbol_tables->Rewind();
                while(@symbol_tables->More() & <>found) {
                    symbol_table := @symbol_tables->Get();

                    value := symbol_table->Find(name);
                    if(value <> Nil) {
                        @stack->Push(value);
                        found := true;
                    };

                    @symbol_tables->Next();
                };

                if(<>found) {
                    "Unable to find variable '{$name}'"->ErrorLine();
                    Runtime->Exit(1);
                };
            }

            label Node->Type->LET {
                table := Hash->New()<String, Value>;
                @symbol_tables->AddFront(table);

                children := node->GetChildren()<Node>;
                each(i : children) {
                    child := children->Get(i);
                    if(child->GetType() = Node->Type->LET_DEC) {
                        name := child->GetStringValue();
                        sub_child := child->GetChildren();
                        Evaluate(sub_child->Get(0));
                        table->Insert(name, @stack->Pop());
                    }
                    else {
                        Evaluate(child);
                    };
                };

                @symbol_tables->RemoveFront();
            }

            label Node->Type->LIST {
                children := node->GetChildren();
                each(i : children) {
                    Evaluate(children->Get(i));
                };

                list := Value->New(Value->Type->LIST);
                each(i : children) {
                    child := @stack->Pop();
                    if(child->GetType() = Value->Type->LIST) {
                        list->AddList(child);
                    }
                    else {
                        list->AddElement(child);
                    };
                };
                @stack->Push(list);
            }

            label Node->Type->CONS {
                children := node->GetChildren();
                each(i : children) {
                    Evaluate(children->Get(i));
                };

                list := Value->New(Value->Type->LIST);
                each(i : children) {
                    list->AddElement(@stack->Pop());
                };
                @stack->Push(list);
            }

            label Node->Type->WRITE {
                children := node->GetChildren();
                each(i : children) {
                    Evaluate(children->Get(i));
                };

                @stack->Pop()->ToString()->PrintLine();
            }

            label Node->Type->LENGTH {
                children := node->GetChildren();
                each(i : children) {
                    Evaluate(children->Get(i));
                };

                list := @stack->Pop();
                @stack->Push(Value->New(list->GetListSize()));
            }

            label Node->Type->EMPTY_LIST {
                @stack->Push(Value->EmptyList());
            }

            label Node->Type->INT_LIT {
                @stack->Push(Value->New(node->GetIntValue()));
            }

            label Node->Type->ADD {
                children := node->GetChildren();
                reverse(i : children) {
                    Evaluate(children->Get(i));
                };

                left := @stack->Pop();
                for(i := 1;  i < children->Size(); i += 1;) {
                    right := @stack->Pop();
                    left->SetIntValue(left->GetIntValue() + right->GetIntValue());
                };
                @stack->Push(left);
            }

            label Node->Type->MUL {
                children := node->GetChildren();
                reverse(i : children) {
                    Evaluate(children->Get(i));
                };

                left := @stack->Pop();
                reverse(i : children) {
                    right := @stack->Pop();
                    left->SetIntValue(left->GetIntValue() * right->GetIntValue());
                };
                @stack->Push(left);
            }

            label Node->Type->SUB {
                children := node->GetChildren();
                reverse(i : children) {
                    Evaluate(children->Get(i));
                };

                left := @stack->Pop();
                if(children->Size() = 1) {
                    left->SetIntValue(left->GetIntValue() * -1);
                }
                else {
                    for(i := 1;  i < children->Size(); i += 1;) {
                        right := @stack->Pop();
                        left->SetIntValue(left->GetIntValue() - right->GetIntValue());
                    };
                };
                @stack->Push(left);
            }

            label Node->Type->DIV {
                children := node->GetChildren();
                for(i := children->Size() - 1; i >= 0; i -= 1;) {
                    Evaluate(children->Get(i));
                };

                left := @stack->Pop();
                if(children->Size() = 1) {
                    left->SetRealValue(1.0 / left->GetIntValue()->ToFloat());
                }
                else {
                    for(i := 1;  i < children->Size(); i += 1;) {
                        right := @stack->Pop();
                        left->SetIntValue(left->GetIntValue() - right->GetIntValue());
                    };
                };
                @stack->Push(left);
            }
        };
    }
}

class Value {
    @type : Type;
    @nil_value : static : Value;
    @empty_list_value : static : Value;
    @next_elem : Value;
    @next_list : Value;
    @int_value : Int;
    @real_value : Float;
    @str_value : String;

    enum Type := -300 {
        LIST,
        NIL_TYPE,
        INT_TYPE,
        REAL_TYPE,
        STRING_TYPE
    }

    function : Init() ~ Nil {
        @nil_value := Value->New(Value->Type->NIL_TYPE);
        @empty_list_value := Value->New(Value->Type->LIST);
    }

    New(int_value : Int) {
        @type := Value->Type->INT_TYPE;
        @int_value := int_value;
    }

    New(real_value : Float) {
        @type := Value->Type->REAL_TYPE;
        @real_value := real_value;
    }

    New(type : Value->Type) {
        @type := type;
    }

    function : EmptyList() ~ Value {
        return @empty_list_value;
    }

    method : public : GetType() ~ Value->Type {
        return @type;
    }

    # list operations
    method : public : GetNextElement() ~ Value {
        return @next_elem;
    }

    method : SetNextElement(next_elem : Value) ~ Nil {
        @next_elem := next_elem;
    }

    method : public : GetNextList() ~ Value {
        return @next_list;
    }

    method : SetNextList(next_list : Value) ~ Nil {
        @next_list := next_list;
    }

    method : public : AddElement(elem : Value) ~ Nil {
        temp := @next_elem;

        if(elem->GetType() = Value->Type->LIST) {
            @next_elem := elem->GetNextElement();
        }
        else {
            @next_elem := elem;
        };

        elem->SetNextElement(temp);
    }

    method : public : AddList(list : Value) ~ Nil {
        if(list->GetType() = Value->Type->LIST) {
            if(@next_list = Nil) {
                @next_list := list;
            }
            else {
                temp := @next_list;
                while(temp->GetNextList() <> Nil) {
                    temp := temp->GetNextList();
                };
                temp->SetNextList(list);
            };
        };
    }

    method : public : GetListSize() ~ Int {
        if(@type = Value->Type->LIST) {
            if(@next_elem = Nil & @next_list = Nil) {
                return 0;
            }
            else {
                count := 0;

                elem := @next_elem;
                list := @next_list;
                if(elem <> Nil) {
                    while(elem <> Nil) {
                        count += 1;
                        elem := elem->GetNextElement();
                    };
                };

                if(list <> Nil) {
                    while(list <> Nil) {
                        count += 1;
                        list := list->GetNextList();
                    };
                };

                return count;
            };
        };

        return -1;
    }

    # atom operations
    method : public : GetIntValue() ~ Int {
        return @int_value;
    }

    method : public : SetIntValue(int_value : Int) ~ Nil {
        @type := Value->Type->INT_TYPE;
        @int_value := int_value;
    }

    method : public : GetRealValue() ~ Float {
        return @real_value;
    }

    method : public : SetRealValue(real_value : Float) ~ Nil {
        @type := Value->Type->REAL_TYPE;
        @real_value := real_value;
    }

    # other
    method : public : ToString() ~ String {
        buffer := "";

        select(@type) {
            label Value->Type->INT_TYPE {
                buffer += @int_value->ToString();
            }

            label Value->Type->REAL_TYPE {
                buffer += @real_value->ToString();
            }

            label Value->Type->STRING_TYPE {
                buffer += @str_value;
            }

            label Value->Type->LIST {
                if(@next_elem = Nil & @next_list = Nil) {
                    buffer += "NIL";
                }
                else {
                    buffer += "(";

                    elem := @next_elem;
                    list := @next_list;
                    if(elem <> Nil) {
                        while(elem <> Nil) {
                            buffer += elem->ToString();
                            elem := elem->GetNextElement();
                            if(elem <> Nil | list <> Nil) {
                                buffer += ", ";
                            };
                        };
                    };

                    if(list <> Nil) {
                        while(list <> Nil) {
                            buffer += list->ToString();
                            list := list->GetNextList();
                            if(list <> Nil) {
                                buffer += ", ";
                            };
                        };
                    };

                    buffer += ")";
                };
            }

            label Value->Type->NIL_TYPE {
                buffer += "NIL";
            }
        };

        return buffer;
    }
}

#--- Parser ---

class Parser {
    @input : String;
    @tokens : Vector<Token>;
    @token_pos : Int;
    @level : Int;
    @error : Bool;
    @is_debug : Bool;

    New(input : String) {
        @input := input;
        @is_debug := true;
    }

    method : public : Parse() ~ Node {
        @tokens := Scanner->New()->Scan(@input);

        if(@is_debug) {
            "--- Input ---\n\"{$@input}\""->PrintLine();

            "\n--- Tokens ---"->PrintLine();
            each(i : @tokens) {
                value := @tokens->Get(i);
                "{$i}: '{$value}'"->PrintLine();
            };
            "\n--- Expressions ---"->PrintLine();
        };

        root := Expression(0);
        if(@token_pos <> @tokens->Size()) {
            @error := true;
            "*** unexpected tokens ***"->ErrorLine();
            return Nil;
        };

        if(@is_debug) {
            if(root <> Nil) {
                "\n--- Tree ---"->PrintLine();
                root->ToString()->PrintLine();
            };
        };

        return root;
    }

    method : public : NextToken() ~ Nil {
        @token_pos += 1;
    }

    method : GetTokenType() ~ Token->Type {
        if(@token_pos < @tokens->Size()) {
            return @tokens->Get(@token_pos)->GetType();
        };

        return Token->Type->OTHER;
    }

    method : Match(type : Token->Type) ~ Bool {
        return GetTokenType() = type;
    }

    method : public : Expression(depth : Int) ~ Node {
        node : Node;

        if(@is_debug) {
            length := @tokens->Size();
            "Expression: pos=({$@token_pos},{$length}); depth={$depth}"->PrintLine();
        };

        is_eval := true;
        if(Match(Token->Type->QUOTE)) {
            is_eval := false;
            NextToken();
        };

        if(Match(Token->Type->OPRN)) {
            NextToken();
            @level += 1;

            if(@token_pos + 2 < @tokens->Size()) {
                select(@tokens->Get(@token_pos)->GetType()) {
                    label Token->Type->ADD:
                    label Token->Type->SUB:
                    label Token->Type->MUL:
                    label Token->Type->DIV: {
                        if(@is_debug) {
                            "\t[+,-,*,/]"->PrintLine();
                        };

                        node := Node->New(GetTokenType());
                        if(<>Operands(node, depth)) {
                            return Nil;
                        };
                    }

                    label Token->Type->LIST_KEYWORD: {
                        if(@is_debug) {
                            "\tList"->PrintLine();
                        };

                        node := Node->New(Node->Type->LIST);
                        if(<>Operands(node, depth)) {
                            return Nil;
                        };
                    }

                    label Token->Type->WRITE_KEYWORD: {
                        if(@is_debug) {
                            "\tWrite"->PrintLine();
                        };

                        node := Node->New(Node->Type->WRITE);
                        if(<>Operands(node, depth)) {
                            return Nil;
                        };

                        if(node->GetChildren()->Size() <> 1) {
                            @error := true;
                            "*** 'write' operation takes 1 operand ***"->ErrorLine();
                            return Nil;
                        };
                    }

                    label Token->Type->CONS_KEYWORD: {
                        if(@is_debug) {
                            "\tCons"->PrintLine();
                        };

                        node := Node->New(Node->Type->CONS);
                        if(<>Operands(node, depth)) {
                            return Nil;
                        };

                        if(node->GetChildren()->Size() <> 2) {
                            @error := true;
                            "*** 'cons' operation takes 2 operands ***"->ErrorLine();
                            return Nil;
                        };
                    }

                    label Token->Type->LET_KEYWORD: {
                        if(@is_debug) {
                            "\tLet"->PrintLine();
                        };

                        NextToken();
                        if(GetTokenType() <> Token->Type->OPRN) {
                            @error := true;
                            "*** expected '(' ***"->ErrorLine();
                            return Nil;
                        };

                        node := Node->New(Node->Type->LET);
                        if(<>Operands(node, depth)) {
                            return Nil;
                        };

                        if(GetTokenType() <> Token->Type->CPRN) {
                            expr := Expression(depth);
                            if(expr <> Nil) {
                                node->AddChild(expr);
                            };

                            if(GetTokenType() <> Token->Type->CPRN) {
                                @error := true;
                                "*** expected ')' ***"->ErrorLine();
                                return Nil;
                            };
                        };

                        NextToken();
                    }

                    label Token->Type->STR_LIT: {
                        value := @tokens->Get(@token_pos)->GetStringValue();
                        if(@is_debug) {
                            "\tStr_Lit; value={$value}"->PrintLine();
                        };

                        node := Node->New(Node->Type->LET_DEC, value);
                        if(<>Operands(node, depth)) {
                            return Nil;
                        };
                    }

                    label Token->Type->LENGTH_KEYWORD: {
                        if(@is_debug) {
                            "\tLength"->PrintLine();
                        };

                        node := Node->New(Node->Type->LENGTH);
                        if(<>Operands(node, depth)) {
                            return Nil;
                        };

                        if(node->GetChildren()->Size() <> 1) {
                            @error := true;
                            "*** 'length' operation takes 1 operand ***"->ErrorLine();
                            return Nil;
                        };
                    }

                    label Token->Type->CPRN: {
                        if(@is_debug) {
                            "\tEmpty_List"->PrintLine();
                        };

                        node := Node->New(Node->Type->EMPTY_LIST);
                    }

                    other: {
                        token_id := GetTokenType()->As(Int);
                        @error := true;
                        "*** Error: unknown operation: id={$token_id} ***"->ErrorLine();
                        return Nil;
                    }
                };
            }
            else if(Match(Token->Type->CPRN)) {
                if(@is_debug) {
                    "\tEmpty_List"->PrintLine();
                };

                node := Node->New(Node->Type->EMPTY_LIST);
            }
            else {
                @error := true;
                "*** Error: operation requires at least 1 operand ***"->ErrorLine();
                return Nil;
            };
        }
        else if(Match(Token->Type->CPRN)) {
            NextToken();
            @level -= 1;
        }
        else if(Match(Token->Type->INT_LIT)) {
            value := @tokens->Get(@token_pos)->GetIntValue();
            if(@is_debug) {
                "\tInt_Lit; value={$value}"->PrintLine();
            };
            node := Node->New(value);
            NextToken();
        }
        else if(Match(Token->Type->STR_LIT)) {
            value := @tokens->Get(@token_pos)->GetStringValue();
            if(@is_debug) {
                "\tStr_Lit; value={$value}"->PrintLine();
            };
            node := Node->New(Node->Type->STR_LIT, value);
            NextToken();
        }
        else {
            token_id := GetTokenType()->As(Int);
            @error := true;
            "*** Error: unknown token: id={$token_id} ***"->ErrorLine();
            NextToken();
            return Nil;
        };

        if(node <> Nil) {
            node->SetEval(is_eval);
        };

        return node;
    }

    method : Operands(node : Node, depth : Int) ~ Bool {
        NextToken();

        cur_level := @level;
        do {
            child := Expression(depth + 1);
            if(@error) {
                return false;
            };

            if(child <> Nil) {
                node->AddChild(child);
            };
        }
        while(cur_level <= @level);

        return true;
    }
}

class Node {
    @type : Node->Type;
    @is_eval : Bool;
    @int_value : Int;
    @real_value : Float;
    @str_value : String;
    @children : Vector<Node>;

    enum Type := -200 {
        ADD,
        SUB,
        MUL,
        DIV,
        LIST,
        LET,
        LET_DEC,
        CONS,
        WRITE,
        LENGTH,
        EMPTY_LIST,
        INT_LIT,
        REAL_LIT,
        STR_LIT
    }

    New(int_value : Int) {
        @type := Node->Type->INT_LIT;
        @int_value := int_value;
    }

    New(real_value : Float) {
        @type := Node->Type->REAL_LIT;
        @real_value := real_value;
    }

    New(type : Node->Type, str_value : String) {
        @type := type;
        @str_value := str_value;
    }

    New(type : Node->Type) {
        @type := type;
    }

    New(type : Token->Type) {
        select(type) {
            label Token->Type->ADD {
                @type := Node->Type->ADD;
            }

            label Token->Type->SUB {
                @type := Node->Type->SUB;
            }

            label Token->Type->MUL {
                @type := Node->Type->MUL;
            }

            label Token->Type->DIV {
                @type := Node->Type->DIV;
            }
        };
    }

    method : public : SetEval(is_eval : Bool) ~ Nil {
        @is_eval := is_eval;
    }

    method : public : GetEval() ~ Bool {
        return @is_eval;
    }

    method : public : GetType() ~ Node->Type {
        return @type;
    }

    method : public : GetIntValue() ~ Int {
        return @int_value;
    }

    method : public : GetRealValue() ~ Float {
        return @real_value;
    }

    method : public : GetStringValue() ~ String {
        return @str_value;
    }

    method : public : AddChild(node : Node) ~ Nil {
        if(@children = Nil) {
            @children := Vector->New()<Node>;
        };

        @children->AddBack(node);
    }

    method : public : GetChildren() ~ Vector<Node> {
        return @children;
    }

    method : public : ToString() ~ String {
        return ToString(0);
    }

    method : public : ToString(level : Int) ~ String {
        buffer := "";

        each(l : level) {
            buffer += "  ";
        };
        buffer += "[";

        select(@type) {
            label Node->Type->ADD {
                buffer += "+";
            }

            label Node->Type->LIST {
                buffer += "list";
            }

            label Node->Type->WRITE {
                buffer += "write";
            }

            label Node->Type->LENGTH {
                buffer += "length";
            }

            label Node->Type->LET {
                buffer += "let";
            }

            label Node->Type->LET_DEC {
                buffer += "let_dec '{$@str_value}'";
            }

            label Node->Type->EMPTY_LIST {
                buffer += "empty_list";
            }

            label Node->Type->SUB {
                buffer += "-";
            }

            label Node->Type->MUL {
                buffer += "*";
            }

            label Node->Type->DIV {
                buffer += "/";
            }

            label Node->Type->INT_LIT {
                buffer += @int_value->ToString();
            }

            label Node->Type->REAL_LIT {
                buffer += @real_value->ToString();
            }

            label Node->Type->STR_LIT {
                buffer += @str_value;
            }
        };

        if(@children <> Nil) {
            each(i : @children) {
                buffer += '\n';
                buffer += @children->Get(i)->ToString(level + 1);
            };

        };
        buffer += "]";

        return buffer;
    }
}

#--- Scanner ---

class Scanner {
    @keywords : Hash<String, Token->Type>;

    New() {
        @keywords := Hash->New()<String, Token->Type>;
        @keywords->Insert("let", Token->Type->LET_KEYWORD);
        @keywords->Insert("write", Token->Type->WRITE_KEYWORD);
        @keywords->Insert("list", Token->Type->LIST_KEYWORD);
        @keywords->Insert("cons", Token->Type->CONS_KEYWORD);
        @keywords->Insert("length", Token->Type->LENGTH_KEYWORD);
    }

    method : public : Scan(input : String) ~ Vector<Token> {
        tokens := Vector->New()<Token>;

        each(i : input) {
            while(input->Get(i) = ' ' | input->Get(i) = '\r' | input->Get(i) = '\n' | input->Get(i) = '\t') {
                i += 1;
            };

            if(input->Get(i)->IsChar()) {
                start := i;
                while(input->Get(i)->IsChar() | input->Get(i) = '_') {
                    i += 1;
                };
                ident := input->SubString(start, i - start);

                found := @keywords->Find(ident);
                if(found <> 0) {
                    tokens->AddBack(Token->New(found));
                }
                else {
                    tokens->AddBack(Token->New(Token->Type->STR_LIT, ident));
                };

                i -= 1;
            }
            else if(input->Get(i)->IsDigit()) {
                is_real := false;

                start := i;
                while(input->Get(i)->IsDigit() | input->Get(i) = '.') {
                    if(input->Get(i) = '.') {
                        is_real := true;
                    };
                    i += 1;
                };

                value := input->SubString(start, i - start);
                if(is_real) {
                    tokens->AddBack(Token->New(value->ToFloat()));
                }
                else {
                    tokens->AddBack(Token->New(value->ToInt()));
                };
                i -= 1;
            }
            else {
                select(input->Get(i)) {
                    label '(' {
                        tokens->AddBack(Token->New(Token->Type->OPRN));
                    }

                    label ')' {
                        tokens->AddBack(Token->New(Token->Type->CPRN));
                    }

                    label '+' {
                        tokens->AddBack(Token->New(Token->Type->ADD));
                    }

                    label '-' {
                        tokens->AddBack(Token->New(Token->Type->SUB));
                    }

                    label '*' {
                        tokens->AddBack(Token->New(Token->Type->MUL));
                    }

                    label '/' {
                        tokens->AddBack(Token->New(Token->Type->DIV));
                    }

                    label '\'' {
                        tokens->AddBack(Token->New(Token->Type->QUOTE));
                    }

                    other {
                        tokens->AddBack(Token->New(Token->Type->OTHER));
                    }
                };
            };
        };

        return tokens;
    }
}

class Token {
    @type : Token->Type;
    @str_value : String;
    @int_value : Int;
    @real_value : Float;

    enum Type := -100 {
        WRITE_KEYWORD,
        LET_KEYWORD,
        LIST_KEYWORD,
        CONS_KEYWORD,
        LENGTH_KEYWORD,
        INT_LIT, # -95
        REAL_LIT,
        STR_LIT,
        OPRN,
        CPRN,
        ADD, # -90
        SUB,
        MUL,
        DIV,
        QUOTE,
        OTHER # -85
    }

    New(type : Token->Type) {
        @type := type;
    }

    New(type : Token->Type, str_value : String) {
        @type := type;
        @str_value := str_value;
    }

    New(int_value : Int) {
        @type := Type->INT_LIT;
        @int_value := int_value;
    }

    New(real_value : Float) {
        @type := Type->REAL_LIT;
        @real_value := real_value;
    }

    method : public : GetType() ~ Token->Type {
        return @type;
    }

    method : public : GetStringValue() ~ String {
        return @str_value;
    }

    method : public : GetIntValue() ~ Int {
        return @int_value;
    }

    method : public : GetRealValue() ~ Float {
        return @real_value;
    }

    method : public : ToString() ~ String {
        select(@type) {
            label Type->OPRN {
                return "(";
            }

            label Type->CPRN {
                return ")";
            }

            label Type->ADD {
                return "+";
            }

            label Type->SUB {
                return "-";
            }

            label Type->MUL {
                return "*";
            }

            label Type->DIV {
                return "/";
            }

            label Type->WRITE_KEYWORD {
                return "write";
            }

            label Type->LENGTH_KEYWORD {
                return "length";
            }

            label Type->LIST_KEYWORD {
                return "list";
            }

            label Type->CONS_KEYWORD {
                return "cons";
            }

            label Type->LET_KEYWORD {
                return "let";
            }

            label Type->STR_LIT {
                return @str_value;
            }

            label Type->INT_LIT {
                return @int_value->ToString();
            }

            label Type->REAL_LIT {
                return @real_value->ToString();
            }

            other {
                return "?";
            }
        };
    }
}