Tiny scheme-like language to try out the structural pattern matching features in Python 3.10 onwards

main.py

"""
A very small scheme-like language to try out the structural pattern matching
features of python 3.11

Features:
    * Mathematical expressions +,-,*,/ involving integers, variables and functions
    * Functions are defined via lambda.
    * Values (including functions) are assigned to variables via let

For more information regarding the concepts this language depends on, see:
    * https://docs.racket-lang.org/reference/let.html
    * https://docs.racket-lang.org/guide/lambda.html
    * https://en.wikipedia.org/wiki/Polish_notation
    * https://en.wikipedia.org/wiki/S-expression

Improvements:
    * There is some error handling but the validity of s-expressions is not tested.
    * Some syntactical conveniences have been ommitted.
    * Maybe it would be worth adding a parser that reads "normal" s-expressions 
      and produces a Python list (akin to prgm) which is then sent for evaluation.
      But then again https://github.com/hylang/hy


:author: Athanasios Anastasiou
:date: Nov 2022
"""
import copy

# Call stack
context = []

class SpecialCallable:
    """
    Represents a function that executes within the most recent call stack
    
    :param params: Function parameters
    :type params: list[str]
    :param body: The body of the function
    :type body: list
    """
    def __init__(self, params, body):
        self._params = params
        self._params_len = len(params)
        self._body = body

    @property
    def parameters(self):
        """
        Returns the parameters that this function takes
        """
        return self._params

    @property
    def n_params(self):
        """
        Returns the number of parameters
        """
        return self._params_len

    def __call__(self,):
        """
        Evaluates the body of the function
        """
        return evalexp(self._body)

def resolve_operand(an_op):
    """
    Resolves the operand to its "meaning". This is either an integer or a SpecialCallable
    """
    if type(an_op) is int:
        return an_op
    if type(an_op) is str:
        if an_op in context[-1]:
            return context[-1][an_op]
        else:
            raise Exception(f"Variable {an_op} not defined")
    if type(an_op) is list:
        return evalexp(an_op)
    return an_op

def evalexp(exp):
    """
    Resolves a program expressed as a set of nested lists to its meaning (an integer)
    """
    if len(context) == 0:
        context.append({})
    # In the following match block, the case statements are !ordered! in order of 
    # priority.
    # For example, if the "function application" was brought further up, before "addition", 
    # then the interpreter would stop functioning completely. This is because, the "addition" 
    # would be interpreted as a function application and "+" would be looked up in the context 
    # for a user-defined function with the same name. "+" however is not a user-defined function 
    # and this would create an error.
    # Yes, it is possible to define everything in one style (e.g. pre-populate the context) but
    # there would still be need for a distinction in reserved-words in the language.
    match exp:
        case ["lambda", list(arguments), list(function_body)]:
            # Function definition
            return SpecialCallable(arguments, function_body)
        case ["let", list(pair_defs), list(let_body)]:
            # Bind symbols to values
            for a_symbol, an_expression in pair_defs:
                if a_symbol not in context[-1]:
                    context[-1][a_symbol] = resolve_operand(an_expression)
                else:
                    raise Exception(f"Symbol {a_symbol} already defined")
            return evalexp(let_body)
        case ["+", int(op1)|str(op1)|list(op1), int(op2)|str(op2)|list(op2)]:
            # Addition
            op_a = resolve_operand(op1)
            op_b = resolve_operand(op2)
            return op_a + op_b
        case ["-", int(op1)|str(op1)|list(op1), int(op2)|str(op2)|list(op2)]:
            # Subtraction
            op_a = resolve_operand(op1)
            op_b = resolve_operand(op2)
            return op_a - op_b
        case ["*", int(op1)|str(op1)|list(op1), int(op2)|str(op2)|list(op2)]:
            # Multiplication
            op_a = resolve_operand(op1)
            op_b = resolve_operand(op2)
            return op_a * op_b
        case ["/", int(op1)|str(op1)|list(op1), int(op2)|str(op2)|list(op2)]:
            # Division
            op_a = resolve_operand(op1)
            op_b = resolve_operand(op2)
            return op_a / op_b
        case [str(symbol), *arguments]:
            # Function application
            if symbol not in context[-1]:
                raise Exception(f"Symbol {symbol} undefined")
            called_function = context[-1][symbol]
            eval_args = dict([(an_arg, resolve_operand(arguments[an_arg_idx])) for an_arg_idx, an_arg in enumerate(called_function.parameters)])
            # Create a new frame
            context.append(copy.deepcopy(context[-1]))
            # Update it
            context[-1].update(eval_args)
            # Evaluate the function in the latest, updated context
            exp_result = called_function()
            # Pop the context
            context.pop()
            # Return the result of the function
            return exp_result

                 
if __name__ == "__main__":
    # Uncomment each of the following prgm=... lines to test each
    # program.
    #
    # Simple mathematical expression
    # (6 + 1*3) * (5 - (1+1)) = 27
    # prgm = ["*", ["+", 6,["*",1, 3]], ["-", 5, ["+",1 ,1]]]
    #
    # Expressions involving variables
    # a = 1
    # b = 1
    # a+b = 2
    # prgm = ["let", [["a",1],["b",1]], ["+", "a","b"]]
    #
    # Expressions involving functions
    # a = 1
    # b = lambda:0+1 (a function that returns 1 always)
    # a + b()
    prgm = ["let", [["a", 1],["b", ["lambda", [], ["+", 0, 1]]]], ["+", "a",["b",]]]
    
    print(f"Program:\n {prgm}")
    print("Evaluates to:")
    print(evalexp(prgm))