Punctree interpreter [prototype; untested] <https://esolangs.org/wiki/Punctree>

Punctree.py

#!/usr/bin/env python
# coding: utf-8
from __future__ import annotations
from typing import Dict, List, Set, Tuple, NamedTuple, Callable, Optional, Union, Iterable, Iterator, Sequence, Mapping, Any, NoReturn, ClassVar, AbstractSet, NewType, Type, TypeVar
from dataclasses import dataclass, field
from itertools import islice, repeat
from functools import reduce, lru_cache
from enum import Enum
import enum
import inspect
from sys import stdin, stdout

class OpCode(Enum):
    HOLE = '_'
    SWAP = '~'
    FILL = '.'
    PLUS = '+'
    Z_UP = '^'
    Z_DL = '/'
    Z_DR = '\\'
    TAU = '%'
    PROJ = '#'
    PTAU = '@'
    EQ = '='
    LEFT = '<'
    IN = ':'
    OUT = ';'
    LOOP = '?'
    POPBAR = '|'
    QUOTE = '[{}]'
    PUSHBAR = '{}|'
    DUP = '{}+'
    SET = '{}='
    DBG_CLRSTACK = '`c'
    DBG_EXIT = '`q'
    DBG_BREAK = '`b'
    DBG_SHOWSTACK = '`s'
    DBG_SHOWCONT = '`r'

    @staticmethod
    @lru_cache
    def greeks() -> AbstractSet[OpCode]:
        return frozenset((OpCode.PUSHBAR, OpCode.DUP, OpCode.SET))

    @staticmethod
    @lru_cache
    def inverse() -> Mapping[str, OpCode]:
        return {i.value: i for i in list(OpCode)}

opcode_impls: Dict[OpCode, Tuple[Callable, int]]
opcode_impls = dict()

def opcode(opcode_: OpCode):
    def decorator(f: Callable) -> Callable:
        arity: int = len(inspect.signature(f).parameters)
        opcode_impls[opcode_] = (f, arity)
        return f
    return decorator

class Branch(Enum):
    L = enum.auto()
    R = enum.auto()
    
    def unbranch(self, left: Callable, right: Callable):
        return left() if self is Branch.L else right()

    @property
    def mirror(self) -> Branch:
        return self.unbranch(lambda: Branch.R, lambda: Branch.L)

    @property
    def digit(self) -> int:
        return self.unbranch(lambda: 1, lambda: 0)

    @staticmethod
    def from_digit(x: int) -> Branch:
        return Branch.L if x == 1 else Branch.R

    def cons(self, ex_t1: Tree0, t0: Tree0) -> Tree0:
        return Tree0.cons(ex_t1, t0) if self is Branch.L else Tree0.cons(t0, ex_t1)

    def parts(self, left, right) -> Tuple[Any, Any]:
        return self.unbranch(lambda: (left, right), lambda: (right, left))

# commented until mypy supports recursive types :)
# InnerTree = Union[Tuple[()], Tuple['InnerTree', 'InnerTree']]
InnerTree = Any

@dataclass
class Tree0:
    _val: InnerTree

    def __str__(self) -> str:
        maybe_cons = self.from_cons
        if maybe_cons is None:
            return "0"
        t, u = maybe_cons
        return f"({t}{u})"

    @staticmethod
    @lru_cache
    def nil() -> Tree0:
        return Tree0(())

    @classmethod
    def cons(cls, car: Tree0, cdr: Tree0) -> Tree0:
        return cls((car._val, cdr._val))

    @property
    def from_cons(self) -> Optional[Tuple[Tree0, Tree0]]:
        if not self._val:
            return None
        return tuple(Tree0(x) for x in self._val) # type: ignore # I’m lazy

class StackValue:
    pass

@dataclass
class Tree1(StackValue):
    _trail: Tuple[Tuple[Branch, Tree0], ...]

    def __post_init__(self):
        assert isinstance(self._trail, tuple), "_trail should be a tuple."

    def __str__(self) -> str:
        strs = ["_"]
        for branch, t0 in reversed(self._trail):
            t0_str = str(t0)
            prefixes, suffixes = branch.unbranch(
                lambda: (["("], [t0_str, ")"]),
                lambda: (["(", t0_str], [")"]))
            strs[0:0] = prefixes
            strs += suffixes
        return ''.join(strs)

    @staticmethod
    @opcode(OpCode.HOLE)
    @lru_cache
    def hole() -> Tree1:
        return Tree1(())

    @staticmethod
    @lru_cache
    def true() -> Tree1:
        return Tree1(((Branch.L, Tree0.nil()),))

    @staticmethod
    def zipper(t1: Tree1, t0: Tree0) -> Tree1:
        return Tree1(((Branch.L, t0), *t1._trail))

    @property
    def from_cons(self) -> Optional[Tuple[Branch, Tree1, Tree0]]:
        trail = self._trail
        if not trail:
            return None
        (branch, t0), *levels = trail
        return (branch, Tree1(tuple(levels)), t0)

    @opcode(OpCode.SWAP)
    def swap(self) -> Tree1:
        trail = self._trail
        if not trail:
            return Tree1.hole()
        (branch, t0), *levels = trail
        return Tree1(((branch.mirror, t0), *levels))

    @opcode(OpCode.FILL)
    def fill(self, other: Tree1) -> Tree1:
        trail = self._trail + other._trail
        return Tree1(trail)

    def close(self) -> Tree0:
        maybe_cons = self.from_cons
        if maybe_cons is None:
            return Tree0.nil()
        branch, t1, t0 = maybe_cons
        return branch.cons(t1.close(), t0)

    @opcode(OpCode.PLUS)
    def plus(self, other: Tree1) -> Tree1:
        return Tree1(((Branch.L, other.close()), *self._trail))

    @property
    def from_zipper(self) -> Optional[Tuple[Tree1, Tree0]]:
        maybe_cons = self.from_cons
        if maybe_cons is None or maybe_cons[0] is Branch.R:
            return None
        return maybe_cons[1::]

    @opcode(OpCode.Z_UP)
    def zipper_up(self) -> Tree1:
        maybe_zipper = self.from_zipper
        if maybe_zipper is None:
            return Tree1.hole()
        t1, t0 = maybe_zipper
        levels = list(t1._trail)
        if not levels:
            return Tree1.hole()
        *levels, (branch, u0) = levels
        new_t0 = branch.cons(t0, u0)
        return Tree1.zipper(Tree1(tuple(levels)), new_t0)

    def zipper_down(self, branch: Branch) -> Tree1:
        maybe_zipper = self.from_zipper
        if maybe_zipper is None:
            return Tree1.hole()
        t1, t0 = maybe_zipper
        maybe_cons = t0.from_cons
        if maybe_cons is None:
            return Tree1.hole()
        new_t0, u0 = branch.parts(*maybe_cons)
        return Tree1.zipper(Tree1((*t1._trail, (branch, u0))), new_t0)

    @opcode(OpCode.Z_DL)
    def zipper_downleft(self) -> Tree1:
        return self.zipper_down(Branch.L)

    @opcode(OpCode.Z_DR)
    def zipper_downright(self) -> Tree1:
        return self.zipper_down(Branch.R)

    @opcode(OpCode.TAU)
    def tau_copy(self, other: Tree1) -> Tree1:
        trail = self._trail
        otrail = other._trail
        if not trail or not otrail:
            return Tree1.hole()
        *_,       (_,       t0) = trail
        *olevels, (obranch, _) = otrail
        return Tree1((*olevels, (obranch, t0)))

    @opcode(OpCode.PROJ)
    def proj_tree1(self) -> Tree1:
        maybe_cons = self.from_cons
        if maybe_cons is None:
            return Tree1.hole()
        return maybe_cons[1]

    @opcode(OpCode.PTAU)
    def proj_tree0_tau_copy(self, other: Tree1) -> Tree1:
        maybe_cons = self.from_cons
        otrail = other._trail
        if maybe_cons is None or not otrail:
            return Tree1.hole()
        *olevels, (obranch, _) = otrail
        return Tree1((*olevels, (obranch, maybe_cons[2])))

    @opcode(OpCode.EQ)
    def equals(self, other: Tree1) -> Tree1:
        return Tree1.true() if self == other else Tree1.hole()

    @opcode(OpCode.LEFT)
    def filter_left(self) -> Tree1:
        maybe_cons = self.from_cons
        if maybe_cons is None or maybe_cons[0] is Branch.R:
            return Tree1.hole()
        return self

def byte_from_tree(x: Tree1, *, little_endian: bool = True) -> Optional[int]:
    # we’ll use UB in the specification to allow simpler impl
    digits = [branch.digit for branch, _ in x._trail]
    if little_endian:
        digits.reverse()
    value = reduce(lambda acc, digit: 2 * acc + digit, digits, 0)
    if 0 <= value < 256:
        return value
    return None

def byte_to_tree(x: int, *, little_endian: bool = True) -> Tree1:
    assert 0 <= x < 256, "The argument should fit into a single unsigned byte."
    digits = [int(ch) for ch in format(x, '08b')]
    if little_endian:
        digits.reverse()
    trail = tuple((Branch.from_digit(d), Tree0.nil()) for d in digits)
    return Tree1(trail)

class Error(Exception):
    message: str
    
    def __init__(self, message):
        self.message = message

class PRuntimeError(Error): pass

class PSyntaxError(Error): pass

io_little_endian = True

@opcode(OpCode.IN)
def input_tree() -> Tree1:
    read = stdin.buffer.read(1)
    if not read:
        #hopefully it’s an EOF and not a shortage of data
        return Tree1.hole()
    return byte_to_tree(read[0], little_endian=io_little_endian)

@opcode(OpCode.OUT)
def output_tree(x: Tree1) -> None:
    maybe_byte = byte_from_tree(x, little_endian=io_little_endian)
    if maybe_byte is None:
        raise PRuntimeError("Can’t output this value.")
    stdout.buffer.write(bytes((maybe_byte,)))

def convert_value(e: StackValue, to: Type[TStackValue]) -> TStackValue:
    if isinstance(e, to): # treats to = object as well
        return e
    if isinstance(e, CodeChunk) and to is Tree1:
        return e.to_tree() # type: ignore # I’m lazy
    elif isinstance(e, Tree1) and to is CodeChunk:
        new_e = CodeChunk.from_tree(e)
        if new_e is None:
            raise PRuntimeError("This value doesn’t represent a valid code.")
        return new_e # type: ignore # I’m lazy
    else:
        raise NotImplementedError("No conversion for these types.")

class Stack:
    _frames: List[List[StackValue]]
    
    def __init__(self):
        self._frames = [[]]
    
    def flat(self) -> Iterator[StackValueBar]:
        needs_bar = False
        for frame in self._frames:
            if needs_bar:
                yield None
            else:
                needs_bar = True
            yield from frame
    
    def __str__(self) -> str:
        def stringify(x: StackValueBar) -> str:
            if x is None:
                return '|'
            elif isinstance(x, Tree1):
                return str(x)
            elif isinstance(x, CodeChunk):
                return str(x.to_tree())
            else:
                raise NotImplementedError("Unknown stack value type.")
        return ' '.join(map(stringify, self.flat()))
    
    def pop(self, types: Sequence[Type[TStackValue]]) -> List[TStackValue]:
    #def pop(self, types: Sequence[type]) -> List[StackValue]:
        last_frame = self._frames[-1]
        usable = len(last_frame)
        expected = len(types)
        if usable < expected:
            raise PRuntimeError(f"Not enough values: {expected} expected, {usable} usable.")
        from_ = usable - expected
        popped = last_frame[from_:]
        del last_frame[from_:]
        return [convert_value(e, to) for e, to in zip(popped, types)]
    
    def push(self, *values: StackValue) -> None:
        self._frames[-1] += values
    
    def clear(self) -> None:
        self._frames.clear()
        self._frames.append([])
    
    def push_bar(self, index: int) -> None:
        last_frame = self._frames[-1]
        index = len(last_frame) - index
        if index < 0:
            raise PRuntimeError("Can’t push bar behind another one: {-index} too deep.")
        self._frames.append(last_frame[index:])
        del last_frame[index:]
    
    def pop_penultimate_section(self) -> None:
        del self._frames[-2:-1]
    
    def checked_section_index(self, index: int) -> int:
        if 0 <= index < len(self._frames[-1]):
            return index
        raise PRuntimeError("The index is out of bounds.")
    
    def dup(self, index: int) -> None:
        index = self.checked_section_index(index)
        self.push(self._frames[-1][index])
    
    def set_(self, index: int) -> None:
        new_value = self.pop([StackValue])[0]
        index = self.checked_section_index(index)
        self._frames[-1][index] = new_value

_inv_greeks: str
_inv_greeks = "αβγδεζηθικλμνοπρστυφχψω"

_greeks: Mapping[str, int]
_greeks = {s: i for i, s in enumerate(_inv_greeks)}

@dataclass(eq=False)
class CodeChunk(StackValue):
    _code: Tuple[Op]
    _index: int = field(init=False)
    _len: int = field(init=False)
    
    def __post_init__(self):
        self._len = len(self._code)
        self.reset_iter()
    
    @staticmethod
    def compile(source: str) -> CodeChunk:
        it: Iterator[Tuple[int, str]] = enumerate(source)
        eof: Tuple[int, str] = (len(source), '\0')
        ops: List[Op] = []
        quote_starts: List[int] = []

        def it_next() -> Tuple[int, str]:
            return next(it, eof)

        def skip_comments():
            nesting = 1
            while True:
                i, ch = it_next()
                if ch == '{':
                    nesting += 1
                    continue
                if ch == '}':
                    nesting -= 1
                elif ch == '\0':
                    if not nesting:
                        return
                    raise PSyntaxError(f"Unclosed comment at {i}.")
                if not nesting:
                    return
                if nesting < 0:
                    raise PSyntaxError(f"Extraneous comment end at {i}.")

        def greek(prev: str) -> Op:
            value = _greeks[prev]
            i, ch = it_next()
            if ch == '|':
                return OpCode.PUSHBAR, value
            elif ch == '+':
                return OpCode.DUP, value
            elif ch == '=':
                return OpCode.SET, value
            else:
                raise PSyntaxError(f"Unfinished ‘{prev}’, expecting one of ‘|+=’ at {i}.")

        def debug(prev: str) -> Op:
            i, ch = it_next()
            maybe_opcode = OpCode.inverse().get(prev + ch, None)
            if maybe_opcode is None:
                raise PSyntaxError(f"Unfinished ‘{prev}’, expecting one of ‘cqbsr’ at {i}.")
            return (maybe_opcode,)

        while True:
            i, ch = it_next()
            maybe_opcode = OpCode.inverse().get(ch, None)
            if maybe_opcode is not None:
                ops.append((maybe_opcode,))
            elif ch == '{':
                skip_comments()
            elif ch == '[':
                quote_starts.append(len(ops))
            elif ch == ']':
                if not quote_starts:
                    raise PSyntaxError(f"Extraneous quote end at {i}.")
                start = quote_starts.pop()
                quoted_ops = ops[start:]
                ops[start:] = [(OpCode.QUOTE, CodeChunk(tuple(quoted_ops)))] # type: ignore # I’m lazy
            elif 'α' <= ch <= 'ω':
                ops.append(greek(ch))
            elif ch == '`':
                ops.append(debug(ch))
            elif ch.isspace():
                pass
            elif ch == '\0':
                if quote_starts:
                    raise PSyntaxError(f"Unclosed quotes ({len(quote_starts)}) at {i}.")
                break
            else:
                raise PSyntaxError(f"Unknown character ‘{ch}’ at {i}.")
        return CodeChunk(tuple(ops)) # type: ignore # I’m lazy
    
    def code_str(self) -> str:
        def op_str(opcode: OpCode, *args: OpArg) -> str:
            value: str = opcode.value
            if opcode in OpCode.greeks():
                assert isinstance(arg := args[0], int)
                return value.format(_inv_greeks[arg])
            elif opcode is OpCode.QUOTE:
                assert isinstance(arg := args[0], CodeChunk)
                return value.format(arg.code_str())
            else:
                return value
        return ''.join((op_str(*op) for op in self._code))
    
    def __str__(self) -> str:
        return f"[{self.code_str()}]::{self._index}"
    
    @staticmethod
    def from_tree(x: Tree1) -> Optional[CodeChunk]:
        trail = x._trail
        subtrails = (trail[index:index + 8] for index in range(0, len(trail) - 7, 8))
        maybe_bytes = tuple(byte_from_tree(Tree1(tr)) for tr in subtrails)
        if None in maybe_bytes:
            return None
        decoded = bytes(maybe_bytes).decode() # type: ignore # I’m lazy
        return CodeChunk.compile(decoded)
    
    def to_tree(self) -> Tree1:
        encoded = self.code_str().encode()
        trail: List[Tuple[Branch, Tree0]] = []
        for b in encoded:
            trail += byte_to_tree(b)._trail
        return Tree1(tuple(trail))
    
    def reset_iter(self) -> None:
        self._index = 0
    
    def next_op(self) -> Optional[Op]:
        if self._index < self._len:
            op = self._code[self._index]
            self._index += 1
            return op
        return None

OpArg = Union[int, CodeChunk]
Op = Union[Tuple[OpCode], Tuple[OpCode, OpArg]]
TStackValue = TypeVar('TStackValue', bound=StackValue)
StackValueBar = Union[StackValue, None]

class WhileState(Enum):
    BEFORE = enum.auto()
    FIRST_TESTED = enum.auto()
    CONTINUE = enum.auto()
    TESTED = enum.auto()

@dataclass
class While:
    _state: WhileState
    _cond: CodeChunk
    _body: CodeChunk
    _else: CodeChunk
    
    def __str__(self) -> str:
        return (f"[{self._cond.code_str()}][{self._body.code_str()}]"
                f"[{self._else.code_str()}]{self._state}")

class Breakpoint:
    def __str__(self) -> str:
        return type(self).__name__

RunState = Union[While, CodeChunk, Breakpoint]

class Runtime:
    stack: Stack
    _continue: List[RunState]
    
    def __init__(self):
        self.stack = Stack()
        self._continue = []
    
    def add_code(self, source: str) -> None:
        self.schedule(CodeChunk.compile(source))
    
    def schedule(self, state: RunState) -> None:
        if isinstance(state, CodeChunk):
            state.reset_iter()
        self._continue.append(state)
    
    def run(self, limiter: Iterable = repeat(None)) -> bool:
        for _ in limiter:
            if self.run_step():
                return True
        return False
    
    def run_step(self) -> bool:
        if not self._continue:
            return True
        running = self._continue[-1]
        if isinstance(running, CodeChunk):
            self.run_step_chunk(running)
            return False
        elif isinstance(running, While):
            self.run_step_while(running)
            return False
        elif isinstance(running, Breakpoint):
            self._continue.pop()
            return True
        else:
            raise NotImplementedError("Unknown run state element.")

    def run_step_while(self, running: While) -> None:
        state = running._state
        if state is WhileState.CONTINUE:
            running._state = WhileState.TESTED
            self.schedule(running._cond)
        elif (state is WhileState.TESTED or
              state is WhileState.FIRST_TESTED):
            val, = self.stack.pop([Tree1])
            if val != Tree1.hole():
                running._state = WhileState.CONTINUE
                self.schedule(running._body)
                return
            self._continue.pop()
            if state is WhileState.FIRST_TESTED:
                self.schedule(running._else)
        elif state is WhileState.BEFORE:
            running._state = WhileState.FIRST_TESTED
            self.schedule(running._cond)
        else:
            raise NotImplementedError("Unknown while-loop state.")
    
    def run_step_chunk(self, running: CodeChunk) -> None:
        maybe_next = running.next_op()
        if maybe_next is None:
            self._continue.pop()
            return
        opcode, *args = maybe_next
        maybe_func = opcode_impls.get(opcode, None)
        if maybe_func is not None:
            self.eval_simple_function(*maybe_func)
        elif opcode is OpCode.LOOP:
            self.eval_while()
        elif opcode is OpCode.POPBAR:
            self.stack.pop_penultimate_section()
        elif opcode is OpCode.QUOTE:
            assert isinstance(arg := args[0], CodeChunk)
            self.stack.push(arg)
        elif opcode is OpCode.PUSHBAR:
            assert isinstance(arg := args[0], int)
            self.stack.push_bar(arg)
        elif opcode is OpCode.DUP:
            assert isinstance(arg := args[0], int)
            self.stack.dup(arg)
        elif opcode is OpCode.SET:
            assert isinstance(arg := args[0], int)
            self.stack.set_(arg)
        elif opcode is OpCode.DBG_CLRSTACK:
            self.stack.clear()
        elif opcode is OpCode.DBG_EXIT:
            self._continue.clear()
        elif opcode is OpCode.DBG_BREAK:
            self.schedule(Breakpoint())
        elif opcode is OpCode.DBG_SHOWSTACK:
            print(self.stack)
        elif opcode is OpCode.DBG_SHOWCONT:
            print(*self._continue, sep='\n')
        else:
            raise PRuntimeError(f"Unknown opcode ‘{opcode}’.")
    
    def eval_simple_function(self, f: Callable, arity: int) -> None:
        popped = self.stack.pop([Tree1] * arity)
        res = f(*popped)
        if isinstance(res, (Tree1, CodeChunk)):
            self.stack.push(res)
        elif isinstance(res, tuple):
            self.stack.push(*res)
        elif res is not None:
            raise NotImplementedError("Unknown return type.")
    
    def eval_while(self) -> None:
        chunks: List[CodeChunk]
        chunks = self.stack.pop([CodeChunk] * 3) # type: ignore # I’m lazy
        cond, body, else_ = chunks
        self.schedule(While(WhileState.BEFORE, cond, body, else_))

def test() -> None:
    import pytest
    assert False, "AAAAH!"

def main() -> None:
    print("Punctree REPL. Enter an empty line to exit.")
    print("Debug:  `b brkpnt  `c clrstack  `s prnstack  `q clrcont  `r prncont")
    runtime = Runtime()
    while True:
        response: str = input("°> ")
        if not response:
            break
        try:
            runtime.add_code(response)
        except PSyntaxError as err:
            print(f"[Syntax error] {err}")
        try:
            runtime.run()
        except PRuntimeError as err:
            runtime._continue.clear()
            print(f"[Runtime error] {err}")
    print("Bye!")

if __name__ == "__main__":
    from sys import argv
    if len(argv) == 1:
        main()
    elif len(argv) == 2 and argv[1] == 'test':
        test()