Collection of utilities for domain specific languages

main.py

"""Simple DSL"""

from utils import (
    evaluate_postfix,
    infix_to_postfix
)

SCOPE = dict()

FUNCTION_DEFINE = 'define'
FUNCTION_INPUT = 'input'
FUNCTION_OUTPUT = 'output'

# Our function mapping dictionary defines what each function does.
# This is the heart of our DSL as we would be storing all the custom
# syntax and functions for fetching, storing and execution operations.
FUNCTIONS = {
    FUNCTION_DEFINE: lambda key, value: SCOPE.update({key: value}),
    FUNCTION_OUTPUT: print,
    FUNCTION_INPUT: lambda key: SCOPE.update({key: input()}),
}


def repl():
    """Reads a line from STDIN. Splits it into tokens and executes the
    required function as defined in the syntax.

    REPL stands for Read-Evaluate-Print-Loop. This is what even Python
    console does. It reads input from the user, evaluates the
    expression, prints any output and repeats it until user closes the
    console.
    """

    try:
        expr = input('> ').strip()
        function, predicate = expr.split(maxsplit=1)

        if function == FUNCTION_DEFINE:
            variable, expression = predicate.split(maxsplit=1)

            FUNCTIONS[function](variable, evaluate_postfix(
                infix_to_postfix(expression), scope=SCOPE))
        elif function == FUNCTION_INPUT:
            variable = predicate

            FUNCTIONS[function](variable)
        elif function == FUNCTION_OUTPUT:
            FUNCTIONS[function](evaluate_postfix(
                infix_to_postfix(predicate), scope=SCOPE))
    except KeyboardInterrupt:
        exit()
    except Exception as ex:
        print(ex)


while True:
    repl()

utils.py

"""Collection of utilities for domain specific languages."""

import operator as op
from collections import deque

OPERATOR_DIVISION = '/'
OPERATOR_MULTIPLICATION = '*'
OPERATOR_SUBTRACTION = '-'
OPERATOR_ADDITION = '+'
OPERATOR_LEFT_PARENTHESIS = '('
OPERATOR_RIGHT_PARENTHESIS = ')'

# Higher the number, greater the precendence.
OPERATOR_PRECEDENCE = {
    OPERATOR_DIVISION: 3,
    OPERATOR_MULTIPLICATION: 3,
    OPERATOR_SUBTRACTION: 2,
    OPERATOR_ADDITION: 1,
    OPERATOR_LEFT_PARENTHESIS: 0,
    OPERATOR_RIGHT_PARENTHESIS: 0,
}

# Corresponding functions for the operators.
OPERATOR_FUNCTIONS = {
    OPERATOR_DIVISION: op.truediv,
    OPERATOR_MULTIPLICATION: op.mul,
    OPERATOR_SUBTRACTION: op.sub,
    OPERATOR_ADDITION: op.add,
}

# We will be doing a lot of "in" queries on the operator list. It's
# better to use set instead of list. Element searching in list is an
# O(n) operation whereas in set it's O(1) (almost).
OPERATORS = set(OPERATOR_PRECEDENCE.keys())


def infix_to_postfix(expr):
    """Converts an infix expression string to a list of postfix tokens.

    Args:
        expr (str): Expression string.

    Returns:
        deque: Postfix expression.
    """

    # We will be doing a lot of pops and appends in the algorithm. It
    # would be much much better to use double-ended queues which
    # perform significantly better when doing list operations at the
    # start or the end of the list.
    expr_tokens = deque(expr.split())

    def parse(tokens):
        """Converts a list of infix tokens to postfix tokens.

        Arguments:
            tokens (deque): List of infix tokens.

        Returns:
            deque: List of postfixed tokens.
        """
        output_stack = deque()
        operator_stack = deque()

        while tokens:
            # Pop one token at a time, top to bottom.
            token = tokens.popleft()

            # We don't know how to deal with anything apart from the
            # predefined operators. So, we'll just add it to the output
            # and move on.
            if token not in OPERATORS:
                output_stack.append(token)

            # When we encounter a left parenthesis, use the same parser
            # logic to parse whatever's inside the parenthesis. Hence,
            # the recursion.
            elif token == '(':
                output_stack.extend(parse(tokens))

            # Right parenthesis marks the end of the block. Don't parse
            # anything after this. Break out of the loop and let the
            # operator cleanup loop (see below) do the job.
            # TODO: This logic seems very shaky.
            elif token == ')':
                break

            # Whatever left are just pure operators.
            else:
                # As long as the current operator has a lower
                # precendence than the one at the top of the stack,
                # keep popping out one operator from the top of the
                # operator stack at a time and add it to the output
                # stack. Finally, add the current operator to the
                # operator stack.
                while operator_stack and (
                        OPERATOR_PRECEDENCE[operator_stack[-1]] >
                        OPERATOR_PRECEDENCE[token]):
                    output_stack.append(operator_stack.pop())
                operator_stack.append(token)

        # This is the operator cleanup loop. Empty all the operators
        # from the operator stack, top to bottom.
        while operator_stack:
            output_stack.append(operator_stack.pop())

        return output_stack

    return parse(expr_tokens)


def evaluate_postfix(expr, scope=None):
    """Evaluates the postfix expression and returns a result.
    Calculations happen only for numeric values. In case a non-numeric
    value is found, it is treated as a variable and the variable value
    should be present in the scope. Else, a ValueError is raised for
    invalid value.

    Args:
        expr (deque): Postfix expression.
        scope (dict): Variable mapping dictionary.

    Returns:
        float: Calulated value.

    Raises:
        ValueError: If an invalid value is specified which does not
            exist in the scope, ValueError is raised.
    """

    # Our temporary result and token holding stack.
    output_stack = deque()
    _scope = scope

    # If no scope is provided, assume it to be dictionary as default.
    if not _scope:
        _scope = dict()

    # Keep iterating unless all tokens are extracted from the expression.
    while expr:
        token = expr.popleft()

        if token in OPERATOR_FUNCTIONS:
            # It is assumed that every operator is always between two
            # values. During infix to postfix conversion, this order is
            # maintained. We are assuming here that the previous two
            # items in the expression are either two values or results
            # of the values calculated in the previous iterations.
            operand_1 = output_stack.pop()
            operand_2 = output_stack.pop()

            # Directly call the function corresponding to the operator
            # with the two operands. Since all our operators are anyway
            # binary, we need not perform any operand count check.

            # Result of the calculation is again stored in the output
            # stack as it can be used as an operand for some other
            # calculation.
            output_stack.append(OPERATOR_FUNCTIONS[token](operand_2,
                                                          operand_1))
        else:
            try:
                # Assume that the value is a number. If not...
                output_stack.append(float(token))
            except ValueError:
                try:
                    # Assume it as a variable. Fetch the corresponding
                    # value from the scope and use it here. If the
                    # token is not found in the scope, then we can
                    # safely call it as an invalid value and throw an
                    # error.
                    output_stack.append(float(_scope[token]))
                except KeyError:
                    raise ValueError('Value %r is invalid' % token)

    # The only thing that is left in the output stack is the final
    # value. Just return it.
    return output_stack.pop()