User:PkmnQ/Hypercomputable implementations

From Esolang
Jump to navigation Jump to search

These are implementations for hypercomputable esolangs in "Banana pseudoPython". I hope to rewrite these in Banana Scheme at some later point, but I'll have to learn Scheme first.

Brainhype, Hyperon, and Loop preventing brainfuck

These implementations use pseudoPython-omega.

import collections, sys
def find_degree(code, open, close):
    max_nesting, nesting = 0, 0
    for instruction in code:
        if instruction in open:
            nesting += 1
        if instruction in close:
            nesting -= 1
        max_nesting = max(max_nesting, nesting)
    return max_nesting
def find_matches(code, open, close):
    matches, stack = {}, []
    for i, instruction in code:
        if instruction in open:
            stack.append(i)
        if instruction in close:
            match = stack.pop(i)
            matches[i], matches[match] = match, i
# mostly adapted from brainfuck Python interpreter
def brainhype(code, tape=None, p=0):
    matches = find_matches(code, "[{", "]}")
    if tape is None:
        tape = collections.defaultdict(int)
    cp=0
    while cp<len(code):
        if code[cp]=='+':
            tape[p]=(tape[p]+1)%256
        if code[cp]=='-':
            tape[p]=(tape[p]-1)%256
        if code[cp]==',':
            c=sys.stdin.read(1)
            tape[p]=(ord(c) if c else 0)%256
        if code[cp]=='.':
            print(chr(tape[p]),end=)
        if code[cp]=='<':
            p-=1
        if code[cp]=='>':
            p+=1
        if code[cp]=='[':
            if not tape[p]:
                cp=matches[cp]
        if code[cp]==']':
            if tape[p]:
                cp=matches[cp]
        if code[cp]=='{':
            subprogram = code[cp+1:matches[cp]]
            if halts(find_degree(subprogram, "{", "}"), lambda: brainhype(subprogram, tape, p)):
                tape[p] = 0
            cp = matches[cp]
        cp+=1
def hyperon(code, tape=None, p=0):
    matches = find_matches(code, "[{", "]}")
    if tape is None:
        tape = collections.defaultdict(int)
    cp=0
    while cp<len(code):
        if code[cp]=='+':
            tape[p]=(tape[p]+1)%256
        if code[cp]=='-':
            tape[p]=(tape[p]-1)%256
        if code[cp]==',':
            c=sys.stdin.read(1)
            tape[p]=(ord(c) if c else 0)%256
        if code[cp]=='.':
            print(chr(tape[p]),end=)
        if code[cp]=='<':
            p-=1
        if code[cp]=='>':
            p+=1
        if code[cp]=='[':
            if not tape[p]:
                cp=matches[cp]
        if code[cp]==']':
            if tape[p]:
                cp=matches[cp]
        if code[cp]=='{':
            subprogram = code[cp+1:matches[cp]]
            if halts(find_degree(subprogram, "{", "}"), lambda: hyperon(subprogram, tape, p)):
                tape[p] += 1
            cp = matches[cp]
        cp+=1
def loop_preventing_brainfuck(code, tape=None, p=0):
    matches = find_matches(code, "([", "|")
    if tape is None:
        tape = collections.defaultdict(int)
    cp=0
    while cp<len(code):
        if code[cp]=='+':
            tape[p]=tape[p]+1
        if code[cp]=='-':
            tape[p]=tape[p]-1
        if code[cp]==',':
            c=sys.stdin.read(1)
            tape[p]=ord(c) if c else 0
        if code[cp]=='.':
            print(chr(tape[p]),end=)
        if code[cp]=='<':
            p-=1
        if code[cp]=='>':
            p+=1
        if code[cp]=='[':
            if not tape[p]:
                cp=matches[cp]
        if code[cp]=='|':
            if tape[p]:
                cp=matches[cp]
        if code[cp]=='(':
            subprogram = code[cp+1:matches[cp]]
            if halts(find_degree(subprogram, "([", "|"), lambda: loop_preventing_brainfuck(subprogram, tape, p)):
                loop_preventing_brainfuck(subprogram, tape, p)
            cp = matches[cp]
        cp+=1

Beeping cyclic tag

This implementation uses pseudoPython-2. If looping infinitely instead of erroring out is acceptable, pseudoPython-1 can be used instead.

import itertools

q1, q2, q = [], [], False

def run_until_beep(commands):
    global q1, q2, q
    while True:
        current_queue = q2 if q else q1
        if next(commands):
            if q1[0] == True:
                current_queue.append(next(commands))
                if q:
                    return
        elif next(commands):
            q = not q
        else:
            current_queue.pop(0)
            if q:
                return

def almost_beeping_cyclic_tag(commands):
    global q1, q2, q
    while halts(0, lambda: run_until_beep(commands)):
        run_until_beep(commands)
    return q2

def beeping_cyclic_tag(code, inputs=None):
    global q1, q2, q
    if inputs:
        q1 = inputs
    else:
        q1 = [True]
    commands = itertools.cycle(code)
    if halts(1, lambda: almost_beeping_cyclic_tag(commands)):
        return almost_beeping_cyclic_tag(commands)
    raise Exception("Q2 is updated infinitely")