"""
This script implements a bounded version of the Turing Halting Test using a finite state machine (FSM) interpreter.
It defines a minimal programming language with basic control flow constructs (`set`, `if`, `goto`, `print`, `end`)
and introduces an API extension that allows programs to introspect their own halting behavior.

The core class `BasicInterpreterWithAPI` executes programs line by line, tracking visited states to detect loops.
If the same program counter and variable configuration are encountered twice, the interpreter concludes that the
program does not halt. Otherwise, it halts successfully. The interpreter also supports an internal API call
`api_check_halting(self)` which allows a program to simulate its own execution and determine whether it halts.

A self-referential "paradox program" is included to demonstrate the halting test. This program uses the API to
check if it halts, and then deliberately does the opposite: if the API says it halts, it loops; if the API says
it loops, it halts. This creates a bounded logical contradiction, echoing the structure of the Halting Problem
without violating Turing's theorem, since the system operates within a finite and constrained state space.

This implementation showcases how simple FSM logic can be used to explore deep computability concepts like
self-reference, halting analysis, and bounded paradoxes — all within a sandboxed interpreter.
"""

import re
from collections import defaultdict

# Basic interpreter with halting check API
class BasicInterpreterWithAPI:
    def __init__(self, program_lines, api=None):
        self.program = self.parse_program(program_lines)
        self.variables = {}
        self.visited_states = defaultdict(set)
        self.execution_trace = []
        self.pc = list(self.program.keys())[0]
        self.loop_detected = False
        self.api = api or {}

    def parse_program(self, lines):
        program = {}
        for line in lines:
            match = re.match(r'^(\d+)\s+(.*)$', line.strip())
            if match:
                line_num = int(match.group(1))
                command = match.group(2)
                program[line_num] = command
        return dict(sorted(program.items()))

    def eval_expr(self, expr):
        expr = expr.replace("true", "True").replace("false", "False")
        for var in self.variables:
            expr = expr.replace(var, str(self.variables[var]))
        try:
            return eval(expr)
        except:
            return False

    def run(self):
        line_nums = list(self.program.keys())
        while True:
            state_key = (self.pc, tuple(sorted(self.variables.items())))
            if state_key in self.visited_states[self.pc]:
                self.loop_detected = True
                print("\n🔁 Non-halting loop detected:")
                for trace in self.execution_trace:
                    print(trace)
                print("⛔ Program does not halt.")
                return False
            self.visited_states[self.pc].add(state_key)

            command = self.program[self.pc]
            self.execution_trace.append(f"{self.pc}: {command} | vars: {self.variables}")

            if command.startswith("set"):
                var, expr = command[4:].split("=", 1)
                self.variables[var.strip()] = self.eval_expr(expr.strip())
            elif command.startswith("print"):
                expr = command[6:].strip()
                print(f"{self.pc}: PRINT {self.eval_expr(expr)}")
            elif command.startswith("goto"):
                self.pc = int(command[5:].strip())
                continue
            elif command.startswith("if"):
                cond, goto_part = command[3:].split("goto")
                if self.eval_expr(cond.strip()):
                    self.pc = int(goto_part.strip())
                    continue
            elif command.startswith("api_check_halting"):
                target = command.split("(", 1)[1].split(")")[0].strip()
                result = self.api.get("check_halting", lambda x: False)(target)
                self.variables["halting_result"] = result
            elif command == "end":
                print("✅ Program halts.")
                return True

            # Move to next line
            line_nums_sorted = sorted(self.program.keys())
            idx = line_nums_sorted.index(self.pc)
            if idx + 1 < len(line_nums_sorted):
                self.pc = line_nums_sorted[idx + 1]
            else:
                print("✅ Program halts.")
                return True

# Self-referential paradox program
paradox_program = [
    "10 api_check_halting(self)",               # Check if this program halts
    "20 if halting_result == true goto 40",     # If it halts, go loop
    "30 end",                                   # Otherwise, halt
    "40 goto 20"                                # Loop forever
]

# API function to simulate halting check
def halting_api(program_name):
    if program_name == "self":
        test = BasicInterpreterWithAPI(paradox_program)
        return test.run()

# Run the paradox program
interpreter = BasicInterpreterWithAPI(paradox_program, api={"check_halting": halting_api})
interpreter.run()