Simple functional programming language interpreter

.gitignore

__pycache__/

README.md

README

A demonstration of a simple functional programming language implementation.

To run REPL, run python main.py.

binding_power.py

class BindingPower:
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __repr__(self):
        return f"[BindingPower: {self.left}, {self.right}]"

class BindingPowers:
    def __init__(self):
        self.lowest = BindingPower(0, 1)
        self.assignment = BindingPower(11, 10)
        self.arrow = BindingPower(21, 20)
        self.summative = BindingPower(30, 31)
        self.productive = BindingPower(40, 41)
        self.call = BindingPower(50, 51)

    def get(self, operator: str) -> BindingPower:
        if operator == "=":
            return self.assignment
        if operator == "->":
            return self.arrow
        if operator in "+-":
            return self.summative
        if operator in "*/":
            return self.productive
        if operator == "(":
            return self.call

        return self.lowest

if __name__ == "__main__":
    bindingPowers = BindingPowers()
    plus = bindingPowers.get("+")
    print(plus)
    # [BindingPower: 30, 31]

char_reader.py

class CharReader:
    def __init__(self, source: str):
        self.source = source
        self.pos = 0 # index to read next

    def read(self) -> str:
        if self.pos == len(self.source):
            return "\0"

        return self.source[self.pos]

    def advance(self) -> None:
        if self.pos == len(self.source):
            return

        self.pos += 1

# test code
if __name__ == "__main__":
    reader = CharReader("12")
    assert reader.read() == "1"
    assert reader.read() == "1" # same character if not advanced
    reader.advance()
    assert reader.read() == "2"
    reader.advance()
    assert reader.read() == "\0" # null character if end

evaluator.py

from typing import Any
from parser import Node

class Value:
    def __init__(self, kind: str, value: Any):
        self.kind = kind
        self.value = value

    def __repr__(self):
        return f"[Value: {self.kind}, {self.value}]"

class Environment:
    def __init__(self, super = None):
        self.super = super
        self.bindings = dict()

    def getVar(self, name: str) -> Value | None:
        if name in self.bindings:
            return self.bindings[name]

        if self.super is not None:
            return self.super.getVar(name)

        return None

    def setVar(self, name: str, value: Any) -> None:
        self.bindings[name] = value

class FunctionValue:
    def __init__(self, param: Any, body: Node, env: Environment):
        self.param = param
        self.body = body
        self.env = env

    def __repr__(self):
        return f"[Function: {self.param} -> ...]"

class Evaluator:
    def __init__(self, nodes: list[Node]):
        self.nodes = nodes

    def evaluate(self, env: Environment) -> Value:
        lastEvaluated = Value("null", None)
        for node in self.nodes:
            lastEvaluated = self.evaluateNode(node, env)

        return lastEvaluated

    def evaluateNode(self, node: Node, env: Environment) -> Value:
        if node.kind == "number":
            return Value("number", node.children[0])
        if node.kind == "identifier":
            return self.evaluateIdentifier(node, env)
        if node.kind == "infix":
            return self.evaluateInfix(node, env)
        if node.kind == "call":
            return self.evaluateCall(node, env)

        raise Exception(f"bad node '{node.kind}'")

    def evaluateIdentifier(self, node: Node, env: Environment) -> Value:
        name = node.children[0]
        value = env.getVar(name)

        if value is None:
            raise Exception(f"variable '{name}' not found")

        return value

    def evaluateInfix(self, node: Node, env: Environment) -> Value:
        infix = node.children[0]
        left = node.children[1]
        right = node.children[2]

        if infix == "=":
            return self.evaluateAssignment(left, right, env)
        if infix in "+-*/":
            return self.evaluateArithmetic(infix, left, right, env)
        if infix == "->":
            return self.evaluateFunction(left, right, env)

        raise Exception(f"bad infix '{infix}'")

    def evaluateAssignment(self, left: Node, right: Node, env: Environment) -> Value:
        value = self.evaluateNode(right, env)

        name = left.children[0]
        env.setVar(name, value)

        return value

    def evaluateArithmetic(self, infix: str, left: Node, right: Node, env: Environment) -> Value:
        evalLeft = self.evaluateNode(left, env)
        evalRight = self.evaluateNode(right, env)

        if evalLeft.kind != "number":
            raise Exception(f"bad left value '{evalLeft.kind}")
        if evalRight.kind != "number":
            raise Exception(f"bad right value '{evalRight.kind}")

        if infix == "+":
            return Value("number", evalLeft.value + evalRight.value)
        if infix == "-":
            return Value("number", evalLeft.value - evalRight.value)
        if infix == "*":
            return Value("number", evalLeft.value * evalRight.value)
        if infix == "/":
            return Value("number", evalLeft.value / evalRight.value)

        raise Exception(f"bad infix '{infix}'")

    def evaluateFunction(self, left: Node, right: Node, env: Environment) -> Value:
        param = left.children[0]
        body = right

        return Value("function", FunctionValue(param, body, env))

    def evaluateCall(self, node: Node, env: Environment) -> Value:
        func = self.evaluateNode(node.children[0], env)
        arg = self.evaluateNode(node.children[1], env)

        funcEnv = func.value.env
        funcParam = func.value.param
        funcBody = func.value.body

        extendedEnv = Environment(funcEnv)
        extendedEnv.setVar(funcParam, arg)

        value = self.evaluateNode(funcBody, extendedEnv)
        return value

# test code
if __name__ == "__main__":
    pass

main.py

from repl import Repl

if __name__ == "__main__":
    repl = Repl()
    repl.run()

parser.py

from typing import Any
from tokenizer import Token
from token_reader import TokenReader
from binding_power import BindingPower, BindingPowers

class Node:
    def __init__(self, kind: str, children: list[Any]):
        self.kind = kind
        self.children = children

    def __repr__(self) -> str:
        return f"[Node: {self.kind}, {self.children}]"

class Parser:
    def __init__(self, tokens: list[Token]):
        self.reader = TokenReader(tokens)
        self.bindingPowers = BindingPowers()

    def parse(self) -> list[Node]:
        nodes: list[Node] = []
        while self.reader.read().kind != "END":
            nodes.append(self.parseExpression(self.bindingPowers.lowest))
        return nodes

    def parseExpression(self, leftBindingPower: BindingPower) -> Node:
        top = self.parseExpressionFirst()

        while True:
            token = self.reader.read()

            rightBindingPower = self.bindingPowers.get(token.kind)
            if leftBindingPower.right >= rightBindingPower.left:
                break

            parsedRest = self.parseExpressionRest(top)
            top = parsedRest

        return top

    def parseExpressionFirst(self) -> Node:
        token = self.reader.read()
        self.reader.advance()

        if token.kind == "number":
            return Node("number", [int(token.value)])
        if token.kind == "identifier":
            return Node("identifier", [token.value])

        raise Exception(f"bad token '{token.kind}' for the first part of expression")

    def parseExpressionRest(self, left: Node) -> Node:
        token = self.reader.read()
        self.reader.advance()

        if token.kind == "->" or token.kind in "+-*/=":
            infix = token.kind
            right = self.parseExpression(self.bindingPowers.get(infix))

            return Node("infix", [infix, left, right])

        if token.kind == "(":
            arg = self.parseExpression(self.bindingPowers.lowest)

            token = self.reader.read()
            if token.kind != ")":
                raise Exception(f"expected ')' but received '{token.kind}'")
            self.reader.advance()

            return Node("call", [left, arg])

        raise Exception(f"bad token '{token.kind}' for the first part of expression")

# test code
if __name__ == "__main__":
    def parseAddition() -> None:
        tokens = [
            Token("number", "1"),
            Token("+"),
            Token("number", "2"),
            Token("+"),
            Token("number", "3"),
            Token("END"),
        ]
        node = Parser(tokens).parse()

        assert node[0].kind == "infix"
        assert node[0].children[0] == "+"
        assert node[0].children[1].kind == "infix"
        assert node[0].children[1].children[0] == "+"
        assert node[0].children[1].children[1].kind == "number"
        assert node[0].children[1].children[1].children[0] == 1
        assert node[0].children[1].children[2].kind == "number"
        assert node[0].children[1].children[2].children[0] == 2
        assert node[0].children[2].kind == "number"
        assert node[0].children[2].children[0] == 3

    parseAddition()

    def parseArithmetic() -> None:
        tokens = [
            Token("number", "1"),
            Token("+"),
            Token("number", "2"),
            Token("*"),
            Token("number", "3"),
            Token("END")
        ]
        node = Parser(tokens).parse()

        assert node[0].kind == "infix"
        assert node[0].children[0] == "+"
        assert node[0].children[1].kind == "number"
        assert node[0].children[1].children[0] == 1
        assert node[0].children[2].kind == "infix"
        assert node[0].children[2].children[0] == "*"
        assert node[0].children[2].children[1].kind == "number"
        assert node[0].children[2].children[1].children[0] == 2
        assert node[0].children[2].children[2].kind == "number"
        assert node[0].children[2].children[2].children[0] == 3

    parseArithmetic()

    def parseExpressions() -> None:
        tokens = [
            Token("number", "1"),
            Token("number", "2"),
            Token("number", "3"),
            Token("END")
        ]
        node = Parser(tokens).parse()

        assert node[0].kind == "number"
        assert node[0].children[0] == 1
        assert node[1].kind == "number"
        assert node[1].children[0] == 2
        assert node[2].kind == "number"
        assert node[2].children[0] == 3

    parseExpressions()

repl.py

from sys import stdin
from typing import Any
from tokenizer import Tokenizer
from parser import Parser
from evaluator import Evaluator, Environment

class Repl:
    def __init__(self):
        self.env = Environment()

    def run(self) -> None:
        print("to quit, type 'quit'")

        repl = Repl()

        while True:
            try:
                print("> ", end="", flush=True)

                line = stdin.readline().strip()
                if line == "quit":
                    print("bye")
                    break

                print(self.execute(line))
            except Exception as e:
                print(e)

    def execute(self, input: str) -> Any:
        tokens = Tokenizer(input).getTokens()
        nodes = Parser(tokens).parse()
        evaluated = Evaluator(nodes).evaluate(self.env)
        return evaluated.value

token_reader.py

from tokenizer import Token

class TokenReader:
    def __init__(self, tokens: list[Token]):
        self.tokens = tokens
        self.pos = 0 # index to read next

    def read(self) -> Token:
        if self.pos == len(self.tokens):
            return self.tokens[-1]

        return self.tokens[self.pos]

    def advance(self) -> None:
        if self.pos == len(self.tokens):
            return

        self.pos += 1

# test code
if __name__ == "__main__":
    tokens = [Token("+"), Token("-"), Token("END")]

    reader = TokenReader(tokens)

    assert reader.read().kind == "+"
    assert reader.read().kind == "+" # same character if not advanced
    reader.advance()
    assert reader.read().kind == "-"
    reader.advance()
    assert reader.read().kind == "END"

tokenizer.py

from char_reader import CharReader

class Token:
    def __init__(self, kind: str, value: str = ""):
        self.kind = kind
        self.value = value

class Tokenizer:
    def __init__(self, source: str):
        self.reader = CharReader(source)

    def getTokens(self) -> list[Token]:
        tokens: list[Token] = []
        while self.reader.read() != "\0":
            tokens.append(self.tokenize())
        tokens.append(Token("END"))

        return tokens

    def tokenize(self) -> Token:
        self.skipWhitespace()

        char = self.reader.read()
        self.reader.advance()

        if char in "()+*/=":
            return Token(char)

        if char == "-":
            nextChar = self.reader.read()
            if nextChar == ">":
                self.reader.advance()
                return Token("->")

            return Token("-")

        if char.isdigit():
            chars = [char]
            while True:
                nextChar = self.reader.read()
                if nextChar.isdigit():
                    self.reader.advance()
                    chars.append(nextChar)
                    continue

                value = "".join(chars)
                return Token("number", value)

        if char.isalpha():
            chars = [char]
            while True:
                nextChar = self.reader.read()
                if nextChar.isalpha() or nextChar.isdigit():
                    self.reader.advance()
                    chars.append(nextChar)
                    continue

                value = "".join(chars)
                return Token("identifier", value)

        raise Exception(f"bad character '{char}'")

    def skipWhitespace(self) -> None:
        while self.reader.read() == " ":
            self.reader.advance()

# test code
if __name__ == "__main__":
    tokens = Tokenizer("abc = de -> fgh(12+34) - 5*6/7").getTokens()

    assert tokens[0].kind == "identifier"
    assert tokens[0].value == "abc"

    assert tokens[1].kind == "="

    assert tokens[2].kind == "identifier"
    assert tokens[2].value == "de"

    assert tokens[3].kind == "->"

    assert tokens[4].kind == "identifier"
    assert tokens[4].value == "fgh"

    assert tokens[5].kind == "("

    assert tokens[6].kind == "number"
    assert tokens[6].value == "12"

    assert tokens[7].kind == "+"

    assert tokens[8].kind == "number"
    assert tokens[8].value == "34"

    assert tokens[9].kind == ")"

    assert tokens[10].kind == "-"

    assert tokens[11].kind == "number"
    assert tokens[11].value == "5"

    assert tokens[12].kind == "*"

    assert tokens[13].kind == "number"
    assert tokens[13].value == "6"

    assert tokens[14].kind == "/"

    assert tokens[15].kind == "number"
    assert tokens[15].value == "7"