lua.cs

using System;
using System.IO;
using System.Collections.Generic;

namespace Lua
{
    class Program
    {
        /// <summary>
        /// Program entry point.
        /// </summary>
        /// <param name="args"></param>
        static void Main(string[] args)
        {
            if (args.Length != 1)
            {
                Console.WriteLine("Usage: Lua [script]");
                Environment.Exit(1);
            }
            else
            {
                try
                {
                    runFile(args[0]);
                } catch (Exception e)
                {
                    Console.WriteLine("Aww, we encountered an error running the program: " + e.Message);
                }
            }
        }

        /// <summary>
        /// Loads a source file and runs it.
        /// </summary>
        /// <param name="path"></param>
        static void runFile(string path)
        {
            string source = File.ReadAllText(path);
            run(source);
        }

        /// <summary>
        /// Parses a source string and executes it.
        /// </summary>
        /// <param name="source"></param>
        static void run(string source)
        {
            var scanner = new Scanner(source);
            var tokens = scanner.ScanTokens();
            foreach (var token in tokens)
            {
                Console.WriteLine("Token: " + token.type + " " +token.lexeme);
            }
            var parser = new Parser(tokens);
            AstNode root = parser.Root();
            var state = new ExecutionState();
            state.scope.declare("print", (Func<dynamic, dynamic>)(args =>
            {
                Console.WriteLine(args[0].ToString());
                return null;
            }));
            root.visit(state);
        }
    }

    /// <summary>
    /// TokenType represents all distinct syntactical tokens in the grammar.
    /// </summary>
    enum TokenType
    {
        LEFT_PAREN, RIGHT_PAREN,
        COMMA, DOT, MINUS, PLUS, SEMICOLON, SLASH, STAR,
        LEFT_BRACKET, RIGHT_BRACKET,

        NOT, TILDE_EQUAL,
        EQUAL, EQUAL_EQUAL,
        GREATER, GREATER_EQUAL,
        LESS, LESS_EQUAL,

        IDENTIFIER, STRING, NUMBER, TABLE,

        AND, ELSE, FALSE, IF, NIL, OR, THEN,
        DO, END, TRUE, LOCAL, WHILE, BREAK,

        EOF
    }

    /// <summary>
    /// A Token represents one token in the source code using a type,
    /// the source text and optionally an attached literal for tokens like numbers.
    /// </summary>
    class Token
    {
        public TokenType type;

        /// <summary>
        /// The source string of the token.
        /// </summary>
        public String lexeme;

        /// <summary>
        /// An optional value used by the interpreter in certain contexts.
        /// </summary>
        public dynamic literal;

        public Token(TokenType type, String lexeme, Object literal)
        {
            this.type = type;
            this.lexeme = lexeme;
            this.literal = literal;
        }   

        /// <summary>
        /// How tight infix operators bind. Infix operators are operators that go between two expressions.
        /// </summary>
        /// <param name="type"></param>
        /// <returns></returns>
        public static object InfixPower(TokenType type)
        {
            return type switch
            {
                TokenType.OR => (1, 2),
                TokenType.AND => (3, 4),
                TokenType.LESS or TokenType.LESS_EQUAL or TokenType.GREATER or TokenType.GREATER_EQUAL or TokenType.TILDE_EQUAL or TokenType.EQUAL_EQUAL => (5, 6),
                TokenType.PLUS or TokenType.MINUS => (17, 18),
                TokenType.STAR or TokenType.SLASH => (19, 20),
                TokenType.DOT => (24, 23),
                _ => null,
            };
        }

        /// <summary>
        /// How tight prefix operators bind. Prefix operators are operators that go before an expression.
        /// </summary>
        /// <param name="type"></param>
        /// <returns></returns>
        public static object PrefixPower(TokenType type)
        {
            return type switch
            {
                TokenType.LEFT_BRACKET or TokenType.LEFT_PAREN => 21,
                _ => null,
            };
        }

        /// <summary>
        /// How tight post operators bind. Post operators are operators that go after an expression.
        /// </summary>
        /// <param name="type"></param>
        /// <returns></returns>
        /// <exception cref="Exception"></exception>
        public static int PostPower(TokenType type)
        {
            switch (type)
            {
                case TokenType.LEFT_BRACKET:
                case TokenType.LEFT_PAREN:
                    return 22;
                default: throw new Exception("invalid postfix operator");
            }
        }
    }

    /// <summary>
    /// The scanner takes a source string and breaks it up into a list of syntactical tokens.
    /// This helps simplify parsing algorithms used later on.
    /// </summary>
    class Scanner
    {
        private string source;
        private List<Token> tokens = new List<Token>();
        private int start;
        private int current;
        private Dictionary<string, Token> keywords = new Dictionary<string, Token> {
            {"and", new Token(TokenType.AND, "and", null)},
            {"else", new Token(TokenType.ELSE, "else", null)},
            {"false", new Token(TokenType.FALSE, "false", false)},
            {"if", new Token(TokenType.IF, "if", null)},
            {"nil", new Token(TokenType.NIL, "nil", null)},
            {"or", new Token(TokenType.OR, "or", null)},
            {"true", new Token(TokenType.TRUE, "true", true)},
            {"local", new Token(TokenType.LOCAL, "local", null)},
            {"while", new Token(TokenType.WHILE, "while", null)},
            {"not", new Token(TokenType.NOT, "not", null)},
            {"do", new Token(TokenType.DO, "do", null)},
            {"end", new Token(TokenType.END, "end", null)},
            {"break", new Token(TokenType.BREAK, "break", null)},
            {"then", new Token(TokenType.THEN, "then", null)},
        };

        public Scanner(string source)
        {
            this.source = source;
        }

        public List<Token> ScanTokens()
        {
            while (!isAtEnd())
            {
                start = current;
                scanToken();
            }

            tokens.Add(new Token(TokenType.EOF, "", null));
            return tokens;
        }

        private bool isAtEnd()
        {
            return current >= source.Length;
        }

        private void addToken(TokenType type)
        {
            addToken(type, null);
        }

        private void addToken(TokenType type, dynamic literal)
        {
            String text = source.Substring(start, current - start);
            tokens.Add(new Token(type, text, literal));
        }

        private char advance()
        {
            return source[current++];
        }

        private bool match(char expected)
        {
            if (isAtEnd()) return false;
            if (source[current] != expected)
            {
                return false;
            }

            current++;
            return true;
        }

        private char peek()
        {
            if (isAtEnd()) return '\0';
            return source[current];
        }

        private char peekNext()
        {
            if (current + 1 >= source.Length) return '\0';
            return source[current + 1];
        }

        private bool isDigit(char c)
        {
            return Char.IsDigit(c);
        }

        private bool isAlpha(char c)
        {
            return Char.IsLetter(c);
        }

        private bool isAlphaNumeric(char c)
        {
            return isAlpha(c) || isDigit(c);
        }

        private void scanToken()
        {
            char c = advance();
            switch (c)
            {
                case '(': addToken(TokenType.LEFT_PAREN); break;
                case ')': addToken(TokenType.RIGHT_PAREN); break;
                case '[': addToken(TokenType.LEFT_BRACKET); break;
                case ']': addToken(TokenType.RIGHT_BRACKET); break;
                case ',': addToken(TokenType.COMMA); break;
                case '.': addToken(TokenType.DOT); break;
                case '-': addToken(TokenType.MINUS); break;
                case '+': addToken(TokenType.PLUS); break;
                case ';': addToken(TokenType.SEMICOLON); break;
                case '*': addToken(TokenType.STAR); break;
                case '{':
                    addToken(match('}') ? TokenType.TABLE : throw new Exception("fucky wucky uwu"), new Dictionary<dynamic, dynamic>());
                    break;
                case '~':
                    addToken(match('=') ? TokenType.TILDE_EQUAL : throw new Exception("fucky wucky uwu"));
                    break;
                case '=':
                    addToken(match('=') ? TokenType.EQUAL_EQUAL : TokenType.EQUAL);
                    break;
                case '<':
                    addToken(match('=') ? TokenType.LESS_EQUAL : TokenType.LESS);
                    break;
                case '>':
                    addToken(match('=') ? TokenType.GREATER_EQUAL : TokenType.GREATER);
                    break;
                case '/':
                    if (match('/'))
                    {
                        while (peek() != '\n' && !isAtEnd()) advance();
                    }
                    else
                    {
                        addToken(TokenType.SLASH);
                    }
                    break;
                case ' ':
                case '\r':
                case '\t':
                case '\n':
                    break;
                case '"': scanString(); break;
                default:
                    if (isDigit(c))
                    {
                        scanNumber();
                        return;
                    }
                    else if (isAlpha(c))
                    {
                        scanIdentifier();
                        return;
                    }

                    throw new Exception("unrecognized character: " + c);
            }
        }

        private void scanString()
        {
            while (peek() != '"' && !isAtEnd())
            {
                advance();
            }

            if (isAtEnd())
            {
                throw new Exception("unterminated string");
            }

            advance();
            String value = source.Substring(start + 1, current - start - 2);
            addToken(TokenType.STRING, value);
        }

        private void scanNumber()
        {
            while (isDigit(peek())) advance();

            if (peek() == '.' && isDigit(peekNext()))
            {
                advance();
                while (isDigit(peek())) advance();
            }

            var raw = float.Parse(source.Substring(start, current - start));
            addToken(TokenType.NUMBER, raw);
        }

        private void scanIdentifier()
        {
            while (isAlphaNumeric(peek())) advance();
            var type = TokenType.IDENTIFIER;
            var text = source.Substring(start, current - start);
            if (keywords.ContainsKey(text))
            {
                tokens.Add(keywords[text]);
                return;
            }

            addToken(type, text);
        }
    }

    /// <summary>
    /// The parser takes a list of tokens from the scanner and assembles an abstract syntax tree.
    /// The syntax tree is used to determine in which order to evaluate the program
    /// and what belongs to what. For example, multiplications bind tighter than additions and thus multiplications
    /// will in most cases contain child addition nodes instead of the other way around.
    /// </summary>
    class Parser
    {
        List<Token> tokens;
        int cursor = 0;

        public Parser(List<Token> tokens) {
            this.tokens = tokens;
        }

        private Token At() {
            return tokens[cursor];
        }

        private Token Peek()
        {
            return tokens[cursor + 1];
        }

        /// <summary>
        /// Increments the cursor if the token we expect is present, otherwise errors.
        /// </summary>
        /// <param name="type"></param>
        /// <returns></returns>
        /// <exception cref="Exception"></exception>
        private Token Expect(TokenType type)
        {
            var token = tokens[cursor];
            if (token.type == type)
            {
                cursor++;
                return token;
            } else
            {
                throw new Exception("unexpected token: " +token.type+" wanted: " + type);
            }
        }

        /// <summary>
        /// Creates a root node for the program containing all other nodes as a list of statements.
        /// </summary>
        /// <returns></returns>
        public AstNode Root()
        {
            var stmts = new List<AstNode>();
            while (At().type != TokenType.EOF)
            {
                stmts.Add(Stmt());
            }

            return new AstNode.Do(stmts.ToArray());
        }

        /// <summary>
        /// Parses a statement, i.e a simple expression or a block like DO or WHILE.
        /// </summary>
        /// <returns></returns>
        /// <exception cref="Exception"></exception>
        private AstNode Stmt()
        {
            return At().type switch
            {
                TokenType.DO => Do(),
                TokenType.WHILE => While(),
                TokenType.BREAK => Break(),
                TokenType.IF => If(),
                TokenType.LOCAL => Local(),
                TokenType.IDENTIFIER => MaybeAssign(),
                TokenType.SEMICOLON => Stmt(),
                TokenType.LEFT_PAREN => Expr(),
                _ => throw new Exception("unexpected token"),
            };
        }
            
        /// <summary>
        /// Parses a DO block.
        /// </summary>
        /// <returns></returns>
        private AstNode Do()
        {
            Expect(TokenType.DO);
            var stmts = new List<AstNode>();
            while (At().type != TokenType.END)
            {
                stmts.Add(Stmt());
            }

            Expect(TokenType.END);
            return new AstNode.Do(stmts.ToArray());
        }

        /// <summary>
        /// Parses a WHILE loop.
        /// </summary>
        /// <returns></returns>
        private AstNode While()
        {
            Expect(TokenType.WHILE);
            var condition = Expr();
            Expect(TokenType.DO);
            var stmts = new List<AstNode>();
            while (At().type != TokenType.END)
            {
                stmts.Add(Stmt());
            }

            Expect(TokenType.END);
            return new AstNode.While(condition, stmts.ToArray());
        }

        /// <summary>
        /// Parses a break statement.
        /// </summary>
        /// <returns></returns>
        private AstNode Break()
        {
            Expect(TokenType.BREAK);
            return new AstNode.Break();
        }

        /// <summary>
        /// Parses a conditional if.
        /// </summary>
        /// <returns></returns>
        private AstNode If()
        {
            Expect(TokenType.IF);
            var condition = Expr();
            Expect(TokenType.THEN);
            var stmts = new List<AstNode>();
            var el = new List<AstNode>();
            while (At().type != TokenType.END && At().type != TokenType.ELSE)
            {
                stmts.Add(Stmt());
            }

            if (At().type == TokenType.ELSE)
            {
                Expect(TokenType.ELSE);
                while (At().type != TokenType.END)
                {
                    el.Add(Stmt());
                }
            }

            Expect(TokenType.END);
            return new AstNode.If(condition, stmts.ToArray(), el.ToArray());
        }

        /// <summary>
        /// Parses a local variable declaration.
        /// </summary>
        /// <returns></returns>
        private AstNode Local()
        {
            Expect(TokenType.LOCAL);
            var literal = Expect(TokenType.IDENTIFIER);
            AstNode left = new AstNode.Ident(literal.literal);
            Expect(TokenType.EQUAL);
            var expr = Expr();
            return new AstNode.Assign(true, left, expr);
        }

        /// <summary>
        /// Parses an assignment or a simple expression.
        /// </summary>
        /// <returns></returns>
        private AstNode MaybeAssign()
        {
            var left = SimpleExpr();
            if (At().type == TokenType.EQUAL) {
                Expect(TokenType.EQUAL);
                var right = Expr();
                return new AstNode.Assign(false, left, right);
            }

            return left;
        }

        /// <summary>
        /// Parses a function call.
        /// </summary>
        /// <param name="target"></param>
        /// <returns></returns>
        private AstNode FunctionCall(AstNode target)
        {
            Expect(TokenType.LEFT_PAREN);
            var args = new List<AstNode>();
            while (At().type != TokenType.RIGHT_PAREN)
            {
                args.Add(Expr());
            }

            Expect(TokenType.RIGHT_PAREN);
            return new AstNode.FunctionCall(target, args.ToArray());
        }

        /// <summary>
        /// Parses a simple expression, i.e one that may appear by itself or to the left of an assignment.
        /// </summary>
        /// <returns></returns>
        private AstNode SimpleExpr()
        {
            var literal = Expect(TokenType.IDENTIFIER);
            AstNode left = new AstNode.Ident(literal.literal);

            while (true) {
                switch (At().type)
                {
                    case TokenType.LEFT_PAREN:
                        left = FunctionCall(left);
                        continue;
                    case TokenType.DOT:
                        Expect(TokenType.DOT);
                        var index = Literal(TokenType.IDENTIFIER);
                        left = new AstNode.Index(left, index);
                        continue;
                    case TokenType.LEFT_BRACKET:
                        Expect(TokenType.LEFT_BRACKET);
                        index = Expr();
                        Expect(TokenType.RIGHT_BRACKET);
                        left = new AstNode.Index(left, index);
                        continue;
                    default: goto loopEnd;
                }
            }

        loopEnd:
            return left;
        }

        /// <summary>
        /// Parses any expression.
        /// </summary>
        /// <returns></returns>
        private AstNode Expr()
        {
            return ExprInner(0);
        }

        /// <summary>
        /// Parses expressions using the Pratt parsing algorithm. This can be quite tricky to get your head around.
        /// The gist of it is that we assign each operator a binding power, the higher the number, the higher its associativity.
        ///
        /// We then keep parsing to the right until we encounter an operator with lower binding power than we currently have,
        /// at that point we break and return an expression. Explanation: https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html
        /// </summary>
        /// <param name="minPower"></param>
        /// <returns></returns>
        private AstNode ExprInner(int minPower)
        {
            var left = ExprLeft();

            while (true)
            {
                var token = At();

                if (token.type == TokenType.LEFT_PAREN && Token.PostPower(TokenType.LEFT_PAREN) >= minPower)
                {
                    left = FunctionCall(left);
                    continue;
                }

                if (token.type == TokenType.LEFT_BRACKET && Token.PostPower(TokenType.LEFT_BRACKET) >= minPower)
                {
                    Expect(TokenType.LEFT_BRACKET);
                    var index = Expr();
                    Expect(TokenType.RIGHT_BRACKET);
                    left = new AstNode.Index(left, index);
                    continue;
                }

                var bp = Token.InfixPower(token.type);
                if (bp is not null)
                {
                    var (lBp, rBp) = ((int, int))bp;
                    if (lBp < minPower)
                    {
                        break;
                    }

                    Expect(token.type);
                    AstNode right;

                    if (token.type == TokenType.DOT)
                    {
                        right = Literal(TokenType.IDENTIFIER);
                    } else
                    {
                        right = ExprInner(rBp);
                    }
                    
                    left = new AstNode.Binary(left, token.type, right);
                    continue;
                }

                break;
            }

            return left;
        }

        /// <summary>
        /// Parses any valid left-expression. Left expressions are any expression that does not involve any other operator.
        /// </summary>
        /// <returns></returns>
        /// <exception cref="Exception"></exception>
        private AstNode ExprLeft()
        {
             switch(At().type)
            {
                case TokenType.IDENTIFIER:
                    return new AstNode.Ident(Expect(TokenType.IDENTIFIER).literal);
                case TokenType.TABLE:
                case TokenType.STRING:
                case TokenType.NIL:
                case TokenType.TRUE:
                case TokenType.FALSE:
                case TokenType.NUMBER: return Literal(At().type);
                case TokenType.LEFT_PAREN:
                    Expect(TokenType.LEFT_PAREN);
                    var expr = Expr();
                    Expect(TokenType.RIGHT_PAREN);
                    return expr;
                default:
                    if (Token.PrefixPower(At().type) is not null)
                    {
                        return ExprUnary();
                    }

                    throw new Exception("invalid expresssion form: " + At().type);
            }
        }

        /// <summary>
        /// Parses an unary expression. That's any expression that consists of a prefix operator followed by another expression.
        /// </summary>
        /// <returns></returns>
        private AstNode ExprUnary()
        {
            var op = At().type;
            Expect(op);
            var rBp = Token.PrefixPower(op);
            var right = ExprInner((int)rBp);
            return new AstNode.Unary(op, right);
        }

        /// <summary>
        /// Parse a literal token with an attached value.
        /// </summary>
        /// <param name="type"></param>
        /// <returns></returns>
        private AstNode Literal(TokenType type)
        {
            var token = Expect(type);
            return new AstNode.Literal(token.literal);
        }
    }

    /// <summary>
    /// Our base AST node type, all other types inherit from this and override the visit method in order to implement
    /// their own execution behaviour.
    /// </summary>
    abstract class AstNode
    {
        /// <summary>
        /// Executes the node, modifying program state.
        /// </summary>
        /// <param name="state"></param>
        /// <returns></returns>
        public abstract dynamic visit(ExecutionState state);

        /// <summary>
        /// Represents an indexing operator like a[5] or a.x = 4.
        /// </summary>
        public class Index : AstNode
        {
            public AstNode left;
            public AstNode index;

            public Index(AstNode left, AstNode index)
            {
                this.left = left;
                this.index = index;
            }

            public override dynamic visit(ExecutionState state)
            {
                var lhs = left.visit(state);
                var idx = index.visit(state);
                return lhs[idx];
            }
        }

        /// <summary>
        /// Thrown when we encounter a break statement, used to bring us up the callstack to the first catchpoint.
        /// </summary>
        public class BreakException : Exception { }

        /// <summary>
        /// Represents a break statement.
        /// </summary>
        public class Break : AstNode
        {
            public override dynamic visit(ExecutionState state)
            {
                throw new BreakException();
            }
        }

        /// <summary>
        /// Represents a while loop with a condition and a list of statements within.
        /// </summary>
        public class While : AstNode
        {
            AstNode condition;
            AstNode[] block;

            public While(AstNode condition, AstNode[] block)
            {
                this.condition = condition;
                this.block = block;
            }

            public override dynamic visit(ExecutionState state)
            {
                state.pushScope();
                try
                {
                    while (state.isTruthy(condition.visit(state)))
                    {
                        foreach (AstNode node in block)
                        {
                            node.visit(state);
                        }
                    }
                }
                catch (BreakException) { }

                state.popScope();
                return null;
            }
        }

        /// <summary>
        /// Represents a do block, provides syntactical scoping and not much else.
        /// </summary>
        public class Do : AstNode
        {
            AstNode[] block;

            public Do(AstNode[] block)
            {
                this.block = block;
            }

            public override dynamic visit(ExecutionState state)
            {
                state.pushScope();
                foreach (AstNode node in block)
                {
                    node.visit(state);
                }

                state.popScope();
                return null;
            }
        }

        /// <summary>
        /// Represents a conditional if using a condition expression and a list of statements to possibly execute.
        /// </summary>
        public class If : AstNode
        {
            AstNode condition;
            AstNode[] block;
            AstNode[] el;

            public If(AstNode condition, AstNode[] block, AstNode[] el)
            {
                this.condition = condition;
                this.block = block;
                this.el = el;
            }

            public override dynamic visit(ExecutionState state)
            {
                state.pushScope();
                if (state.isTruthy(condition.visit(state)))
                {
                    foreach (AstNode node in block)
                    {
                        node.visit(state);
                    }
                }
                else if (el != null)
                {
                    foreach (AstNode node in el)
                    {
                        node.visit(state);
                    }
                }

                state.popScope();
                return null;
            }
        }

        /// <summary>
        /// Represents an assign action like a = 5 using a target left expression and a value right hand expression.
        /// </summary>
        public class Assign : AstNode
        {
            bool declaration;
            AstNode target;
            AstNode right;

            public Assign(bool declaration, AstNode target, AstNode right)
            {
                this.declaration = declaration;
                this.target = target;
                this.right = right;
            }

            public override dynamic visit(ExecutionState state)
            {
                var rhs = right.visit(state);
                if (declaration)
                {
                    // Declarate a variable, allowing it to be used later.
                    var name = ((Ident)target).name;
                    state.scope.declare(name, rhs);
                }
                else
                {
                    if (target is Ident)
                    {
                        // It's a local variable, assign in the scope map.
                        var name = ((Ident)target).name;
                        var found = state.scope.assign(name, rhs);
                        if (!found)
                        {
                            throw new Exception("Cannot assign to undeclared variable: " + name);
                        }
                    } else if (target is Index)
                    {
                        // The parent is a table, we need to write to the table instead.
                        var index = (Index)target;
                        var lhs = index.left.visit(state);
                        var idx = index.index.visit(state);
                        lhs[idx] = rhs;
                    } else
                    {
                        throw new Exception("invalid assign target");
                    }
                }

                return null;
            }
        }

        /// <summary>
        /// Represents a unary expression like -8 or not true.
        /// </summary>
        public class Unary : AstNode
        {
            TokenType op;
            AstNode right;

            public Unary(TokenType op, AstNode right)
            {
                this.op = op;
                this.right = right;
            }

            public override dynamic visit(ExecutionState state)
            {
                var rhs = right.visit(state);

                return op switch
                {
                    TokenType.NOT => !rhs,
                    TokenType.MINUS => -rhs,
                    _ => null,
                };
            }
        }

        /// <summary>
        /// Represents a binary expression like 5+3.
        /// </summary>
        public class Binary : AstNode
        {
            AstNode left;
            TokenType op;
            AstNode right;

            public Binary(AstNode left, TokenType op, AstNode right)
            {
                this.left = left;
                this.op = op;
                this.right = right;
            }

            public override dynamic visit(ExecutionState state)
            {
                var lhs = left.visit(state);
                var rhs = right.visit(state);

                return op switch
                {
                    TokenType.PLUS => lhs + rhs,
                    TokenType.MINUS => lhs - rhs,
                    TokenType.STAR => lhs * rhs,
                    TokenType.SLASH => lhs / rhs,
                    TokenType.AND => lhs && rhs,
                    TokenType.OR => lhs || rhs,
                    TokenType.EQUAL_EQUAL => lhs == rhs,
                    TokenType.TILDE_EQUAL => lhs != rhs,
                    TokenType.DOT => lhs[rhs],
                    TokenType.LESS => lhs < rhs,
                    TokenType.LESS_EQUAL => lhs <= rhs,
                    TokenType.GREATER => lhs > rhs,
                    TokenType.GREATER_EQUAL => lhs >= rhs,
                    _ => null,
                };
            }
        }

        /// <summary>
        /// Represents a literal expression like 9 or "hello world".
        /// </summary>
        public class Literal : AstNode
        {
            dynamic value;

            public Literal(dynamic value)
            {
                this.value = value;
            }

            public override dynamic visit(ExecutionState state)
            {
                return value;
            }
        }

        /// <summary>
        /// Represents an identifier expression like x, evaluated by looking into the scope map of declared variables.
        /// </summary>
        public class Ident : AstNode
        {
            public string name;

            public Ident(string name)
            {
                this.name = name;
            }

            public override dynamic visit(ExecutionState state)
            {
                return state.scope.resolve(name);
            }
        }

        /// <summary>
        /// Represents a function call expression like print(4).
        /// </summary>
        public class FunctionCall : AstNode
        {
            AstNode left;
            AstNode[] args;

            public FunctionCall(AstNode left, AstNode[] args)
            {
                this.left = left;
                this.args = args;
            }

            public override dynamic visit(ExecutionState state)
            {
                var target = left.visit(state);
                var args2 = new dynamic[args.Length];
                for (int i = 0; i < args.Length; i++)
                {
                    args2[i] = args[i].visit(state);
                }

                return target(args2);
            }
        }
    }

    /// <summary>
    /// Scope represents all of the current variables in the scope and their hierarchy.
    /// Scopes are essentially a linked list of sets of variables, at each point where a new lexical scope is created
    /// we create a new scope structure. Then when we exit a scope, we simply remove the top scope, deleting all its variables in one go.
    /// </summary>
    class Scope
    {
        Dictionary<string, dynamic> vals = new Dictionary<string, dynamic>();
        public Scope parent;

        public Scope(Scope parent)
        {
            this.parent = parent;
        }

        /// <summary>
        /// Look in the current and parent scopes for a variable with a given name.
        /// </summary>
        /// <param name="name"></param>
        /// <returns></returns>
        public dynamic resolve(string name)
        {
            if (!vals.ContainsKey(name))
            {
                if (parent == null)
                {
                    return null;
                }

                return parent.resolve(name);
            }

            return vals[name];
        }

        /// <summary>
        /// Declare a new variable in the current scope.
        /// </summary>
        /// <param name="name"></param>
        /// <param name="value"></param>
        public void declare(string name, dynamic value)
        {
            vals[name] = value;
        }

        /// <summary>
        /// Assign to an already existing variable in the current or a parent scope.
        /// </summary>
        /// <param name="name"></param>
        /// <param name="value"></param>
        /// <returns></returns>
        public bool assign(string name, dynamic value)
        {
            if (vals.ContainsKey(name))
            {
                vals[name] = value;
                return true;
            }

            if (parent != null)
            {
                return parent.assign(name, value);
            }

            return false;
        }
    }

    class ExecutionState
    {

        public Scope scope = new Scope(null);

        /// <summary>
        /// Create a new top-level lexical scope.
        /// </summary>
        public void pushScope()
        {
            scope = new Scope(scope);
        }

        /// <summary>
        /// Pop the top scope in the stack, removing all contained variables.
        /// </summary>
        public void popScope()
        {
            scope = scope.parent;
        }

        /// <summary>
        /// Check if a given variable evaluates to true.
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        public bool isTruthy(dynamic value)
        {
            return value != null && value != false;
        }
    }
}