309 lines
8.0 KiB
Python
309 lines
8.0 KiB
Python
#!/usr/bin/env python3
|
|
import enum
|
|
import sys
|
|
from collections import namedtuple
|
|
|
|
class actions(enum.Enum):
|
|
change, left, right, nothing = range(4)
|
|
|
|
State = namedtuple('State', ['action', 'transitions', 'reachable'])
|
|
|
|
class SFParseError(Exception): pass
|
|
|
|
def parse_smallfuck(s):
|
|
def parse(s, index = 0, in_loop = False):
|
|
parsed = []
|
|
while True:
|
|
assert index <= len(s)
|
|
if index == len(s):
|
|
if in_loop:
|
|
raise SFParseError('Unexpected end of text (expected "]")')
|
|
else:
|
|
break
|
|
|
|
c = s[index]
|
|
index += 1
|
|
|
|
if c == ']':
|
|
if in_loop:
|
|
break
|
|
else:
|
|
raise SFParseError('Unexpected "]"')
|
|
|
|
elif c == '[':
|
|
loop, index = parse(s, index, True)
|
|
parsed.append(loop)
|
|
|
|
elif c in ['<', '>', '*']:
|
|
parsed.append(c)
|
|
|
|
return parsed, index
|
|
|
|
parsed, index = parse(s)
|
|
return parsed
|
|
|
|
def turingify(parsed):
|
|
states = []
|
|
def add_state(action, transitions):
|
|
nonlocal states
|
|
assert action in actions
|
|
assert len(transitions) == 2
|
|
|
|
index = len(states)
|
|
states.append(State(action, transitions, [False, False]))
|
|
|
|
return index
|
|
|
|
def worker(parsed, end = None):
|
|
nonlocal states
|
|
|
|
while len(parsed) > 0:
|
|
c = parsed[-1]
|
|
parsed = parsed[:-1]
|
|
|
|
if type(c) == list:
|
|
loop_test = add_state(actions.nothing, [end, None])
|
|
loop_body = worker(c, loop_test)
|
|
# We want the loop to repeat if the cell is set
|
|
states[loop_test].transitions[1] = loop_body
|
|
end = loop_test
|
|
|
|
elif c == '*':
|
|
end = add_state(actions.change, [end, end])
|
|
|
|
elif c == '<':
|
|
end = add_state(actions.left, [end, end])
|
|
|
|
elif c == '>':
|
|
end = add_state(actions.right, [end, end])
|
|
|
|
else:
|
|
assert not "Unreachable"
|
|
|
|
return end
|
|
|
|
return worker(parsed), states
|
|
|
|
def prettyprint_states(states):
|
|
for i in range(len(states)):
|
|
state = states[i]
|
|
action = {actions.change: '* ', actions.left: '< ', actions.right: '> ', actions.nothing: ''}[state.action]
|
|
if state.reachable == [True, True]:
|
|
reachable = '(*)'
|
|
elif state.reachable == [True, False]:
|
|
reachable = '(0)'
|
|
elif state.reachable == [False, True]:
|
|
reachable = '(1)'
|
|
elif state.reachable == [False, False]:
|
|
reachable = '(!)'
|
|
else:
|
|
reachable = ''
|
|
print('%4i%s: %s%s' % (i, reachable, action, state.transitions))
|
|
|
|
def reachability(start, states):
|
|
def copy_state(index):
|
|
state = states[index]
|
|
action = state.action
|
|
transitions = state.transitions[:]
|
|
reachable = [False if i is None else i for i in state.reachable]
|
|
return State(action, transitions, reachable)
|
|
|
|
# Since we always end up with start at index 0, no need to create processed_start
|
|
processed = [copy_state(start)]
|
|
processed[0].reachable[0] = True
|
|
processed[0].reachable[1] = True
|
|
translations = {start: 0}
|
|
|
|
processed_sweep = 0
|
|
while processed_sweep < len(processed):
|
|
for i in range(len(processed[processed_sweep].transitions)):
|
|
index_states = processed[processed_sweep].transitions[i]
|
|
|
|
# Nothing to be done if we point to halt state
|
|
if index_states is None:
|
|
continue
|
|
|
|
# Copy the state to processed if it isn't already there
|
|
if index_states not in translations:
|
|
index_processed = len(processed)
|
|
processed.append(copy_state(index_states))
|
|
translations[index_states] = index_processed
|
|
|
|
# Fix transition to the state
|
|
processed[processed_sweep].transitions[i] = translations[index_states]
|
|
|
|
# Mark how we got to the state
|
|
processed[translations[index_states]].reachable[i] = True
|
|
|
|
processed_sweep += 1
|
|
|
|
return processed
|
|
|
|
def string_id(state, value, processed):
|
|
def intlog(num, base):
|
|
# This is floor(log_{base} num)
|
|
assert num > 0
|
|
result = 0
|
|
while num > base - 1:
|
|
num = num // base
|
|
result += 1
|
|
return result
|
|
|
|
assert value == 0 or value == 1
|
|
assert state is None or 0 <= state < len(processed)
|
|
|
|
# One for each (cell value, state) combination and one for the cell values without a state
|
|
max_num = 2 * len(processed) + 2 - 1
|
|
# Base 62 because we have 0-9A-Za-y, +1 because the intlog is one less than the digits needed
|
|
width = intlog(max_num, 61) + 1
|
|
|
|
if state is not None:
|
|
num = 2 * (state + 1) + value
|
|
else:
|
|
num = value
|
|
|
|
digits = []
|
|
|
|
while num > 0:
|
|
digit = num % 61
|
|
num = num // 61
|
|
|
|
if digit < 10:
|
|
digits.append(chr(ord('0') + digit))
|
|
elif digit < 36:
|
|
digits.append(chr(ord('A') + digit - 10))
|
|
else:
|
|
digits.append(chr(ord('a') + digit - 36))
|
|
|
|
string = ''.join(reversed(digits))
|
|
|
|
# Pad to width
|
|
string = '0' * (width - len(string)) + string
|
|
|
|
return string
|
|
|
|
def create_replacements(processed):
|
|
replacements = []
|
|
|
|
for index in range(len(processed)):
|
|
state = processed[index]
|
|
|
|
if state.action == actions.nothing:
|
|
for value in [0, 1]:
|
|
if state.reachable[value]:
|
|
start = string_id(index, value, processed)
|
|
end = string_id(state.transitions[value], value, processed)
|
|
replacements.append((start, end))
|
|
|
|
elif state.action == actions.change:
|
|
for original_value in [0, 1]:
|
|
if state.reachable[original_value]:
|
|
changed_value = original_value ^ 1
|
|
start = string_id(index, original_value, processed)
|
|
end = string_id(state.transitions[changed_value], changed_value, processed)
|
|
replacements.append((start, end))
|
|
|
|
elif state.action == actions.left:
|
|
for this_value in [0, 1]:
|
|
if state.reachable[this_value]:
|
|
for left_value in [0, 1]:
|
|
this_start = string_id(index, this_value, processed)
|
|
left_start = string_id(None, left_value, processed)
|
|
start = '%s %s' % (left_start, this_start)
|
|
|
|
this_end = string_id(None, this_value, processed)
|
|
left_end = string_id(state.transitions[left_value], left_value, processed)
|
|
end = '%s %s' % (left_end, this_end)
|
|
|
|
replacements.append((start, end))
|
|
|
|
elif state.action == actions.right:
|
|
for this_value in [0, 1]:
|
|
if state.reachable[this_value]:
|
|
for right_value in [0, 1, None]:
|
|
this_start = string_id(index, this_value, processed)
|
|
if right_value is not None:
|
|
right_start = string_id(None, right_value, processed)
|
|
else:
|
|
right_start = 'z'
|
|
start = '%s %s' % (this_start, right_start)
|
|
|
|
this_end = string_id(None, this_value, processed)
|
|
if right_value is not None:
|
|
right_end = string_id(state.transitions[right_value], right_value, processed)
|
|
else:
|
|
right_end = string_id(state.transitions[0], 0, processed) + ' z'
|
|
end = '%s %s' % (this_end, right_end)
|
|
|
|
replacements.append((start, end))
|
|
|
|
else:
|
|
assert not "Unreachable"
|
|
|
|
return replacements
|
|
|
|
def xedify(replacements):
|
|
replaced = '|'.join(start for start, end in replacements)
|
|
replacement = '|'.join(end for start, end in replacements)
|
|
|
|
return 'x/%s/%s/' % (replaced, replacement)
|
|
|
|
def process_tape(tape, processed):
|
|
assert all(i in ['0', '1', '^0', '^1'] for i in tape)
|
|
processed_tape = []
|
|
for i in tape:
|
|
if i == '0':
|
|
processed_tape.append(string_id(None, 0, processed))
|
|
elif i == '1':
|
|
processed_tape.append(string_id(None, 1, processed))
|
|
elif i == '^0':
|
|
processed_tape.append(string_id(0, 0, processed))
|
|
elif i == '^1':
|
|
processed_tape.append(string_id(0, 1, processed))
|
|
else:
|
|
assert not "Unreachable"
|
|
|
|
return ' '.join(processed_tape) + ' z'
|
|
|
|
def run_replacements(replacements, processed_tape):
|
|
while True:
|
|
made_replacement = False
|
|
for start, end in replacements:
|
|
if start in processed_tape:
|
|
processed_tape = processed_tape.replace(start, end)
|
|
made_replacement = True
|
|
break
|
|
|
|
if not made_replacement:
|
|
break
|
|
|
|
print(processed_tape)
|
|
|
|
def main():
|
|
if len(sys.argv) == 2 and sys.argv[1] == '-r':
|
|
run = True
|
|
else:
|
|
run = False
|
|
|
|
program = input('program: ')
|
|
|
|
start_noreachability, states_noreachability = turingify(parse_smallfuck(program))
|
|
processed = reachability(start_noreachability, states_noreachability)
|
|
|
|
replacements = create_replacements(processed)
|
|
print(xedify(replacements))
|
|
|
|
print('\nSend empty to exit. ^0/^1 for initial tape head position')
|
|
while True:
|
|
tape = input('tape: ')
|
|
if tape == '': break
|
|
tape = tape.split(' ')
|
|
processed_tape = process_tape(tape, processed)
|
|
print(processed_tape)
|
|
|
|
if run:
|
|
run_replacements(replacements, processed_tape)
|
|
|
|
if __name__ == '__main__':
|
|
main()
|