BrainDeque

BrainDeque is designed by PSTF.

It is based on Deque, instead of Tape.

Command Table

>  - Push 0 to right end
<  - Push 0 to left end
+  - Increment front element
-  - Decrement front element
.  - Output front element as ASCII
,  - Input character to front element
[  - Jump past matching ] if front == 0
]  - Jump back to matching [ if front != 0
{  - Rotate deque left (move front to back)
}  - Rotate deque right (move back to front)
:  - Duplicate front element
;  - Swap front two elements
!  - Negate front element (0→1, non-zero→0)
@  - Set front to length of deque
#  - Output front element as integer
$  - Input integer to front element

Python Implementation

#!/usr/bin/env python3
"""
DequeLang - A Turing-complete deque-based programming language interpreter
Author: AI Assistant
"""

import sys
import collections
import readline  # For better input handling

class DequeLangInterpreter:
    def __init__(self, code, input_data=""):
        self.code = code
        self.input_data = input_data
        self.input_ptr = 0
        
        # Memory: infinite deque initialized with [0]
        self.deque = collections.deque([0])
        
        # Instruction pointer
        self.ip = 0
        
        # Stack for loop matching
        self.loop_stack = []
        
        # Precompute matching brackets for O(1) lookups
        self.match_brackets = self._match_brackets()
        
        # Output buffer
        self.output = []
    
    def _match_brackets(self):
        """Precompute matching bracket positions."""
        match = {}
        stack = []
        
        for i, char in enumerate(self.code):
            if char == '[':
                stack.append(i)
            elif char == ']':
                if not stack:
                    raise SyntaxError(f"Unmatched ']' at position {i}")
                start = stack.pop()
                match[start] = i
                match[i] = start
        
        if stack:
            raise SyntaxError(f"Unmatched '[' at position {stack[-1]}")
        
        return match
    
    def get_front(self):
        """Get value at front of deque."""
        if not self.deque:
            self.deque.append(0)
        return self.deque[0]
    
    def set_front(self, value):
        """Set value at front of deque."""
        if not self.deque:
            self.deque.append(0)
        self.deque[0] = value
    
    def rotate_left(self):
        """Rotate deque left (front moves to back)."""
        if self.deque:
            self.deque.rotate(-1)
    
    def rotate_right(self):
        """Rotate deque right (back moves to front)."""
        if self.deque:
            self.deque.rotate(1)
    
    def get_input_char(self):
        """Get next character from input."""
        if self.input_ptr < len(self.input_data):
            char = self.input_data[self.input_ptr]
            self.input_ptr += 1
            return ord(char)
        else:
            # Try to get input from user if data exhausted
            try:
                char = sys.stdin.read(1)
                return ord(char) if char else 0
            except:
                return 0
    
    def get_input_int(self):
        """Get next integer from input."""
        if self.input_ptr < len(self.input_data):
            # Try to read integer from input string
            import re
            match = re.search(r'-?\d+', self.input_data[self.input_ptr:])
            if match:
                self.input_ptr += match.end()
                return int(match.group())
        
        # Fallback to user input
        try:
            return int(input("Enter integer: "))
        except:
            return 0
    
    def step(self):
        """Execute one instruction."""
        if self.ip >= len(self.code):
            return False
        
        instruction = self.code[self.ip]
        
        try:
            if instruction == '>':
                # Push 0 to right end
                self.deque.append(0)
                self.rotate_right()  # Move new element to front
                
            elif instruction == '<':
                # Push 0 to left end
                self.deque.appendleft(0)
                
            elif instruction == '+':
                # Increment front
                self.set_front((self.get_front() + 1) % 256)
                
            elif instruction == '-':
                # Decrement front
                self.set_front((self.get_front() - 1) % 256)
                
            elif instruction == '.':
                # Output as ASCII
                value = self.get_front()
                if 0 <= value <= 255:
                    self.output.append(chr(value))
                    print(chr(value), end='', flush=True)
                else:
                    self.output.append(str(value))
                    
            elif instruction == ',':
                # Input character
                value = self.get_input_char()
                self.set_front(value)
                
            elif instruction == '[':
                # Start loop
                if self.get_front() == 0:
                    self.ip = self.match_brackets[self.ip]
                    
            elif instruction == ']':
                # End loop
                if self.get_front() != 0:
                    self.ip = self.match_brackets[self.ip]
                    
            elif instruction == '{':
                # Rotate left
                self.rotate_left()
                
            elif instruction == '}':
                # Rotate right
                self.rotate_right()
                
            elif instruction == ':':
                # Duplicate front
                front = self.get_front()
                self.deque.appendleft(front)
                
            elif instruction == ';':
                # Swap front two elements
                if len(self.deque) >= 2:
                    a = self.deque.popleft()
                    b = self.deque.popleft()
                    self.deque.appendleft(a)
                    self.deque.appendleft(b)
                    
            elif instruction == '!':
                # Logical NOT (0→1, non-zero→0)
                self.set_front(1 if self.get_front() == 0 else 0)
                
            elif instruction == '@':
                # Set front to deque length
                self.set_front(len(self.deque))
                
            elif instruction == '#':
                # Output as integer
                value = self.get_front()
                self.output.append(str(value))
                print(value, end=' ', flush=True)
                
            elif instruction == '$':
                # Input integer
                value = self.get_input_int()
                self.set_front(value)
                
            # Ignore whitespace and comments
            elif instruction in ' \t\n':
                pass
            else:
                pass
                
        except Exception as e:
            raise RuntimeError(f"Error executing instruction at position {self.ip}: {e}")
        
        self.ip += 1
        return True
    
    def run(self, max_steps=1000000):
        """Execute the entire program."""
        step_count = 0
        
        while self.ip < len(self.code) and step_count < max_steps:
            self.step()
            step_count += 1
            
            # Safety check
            if len(self.deque) > 10000:
                raise MemoryError("Deque grew too large (possible infinite loop)")
        
        if step_count >= max_steps:
            print(f"\nWarning: Execution stopped after {max_steps} steps")
        
        return ''.join(self.output)


# Example programs
EXAMPLE_PROGRAMS = {
    'hello': """+++{+++}++++++[>+<-]>.>+[+>+<]>.>+++.+++..+++.>[-]<[-]<[-]<""",
    
    'cat': """[,.+]""",
    
    'add': """$,$$:>[-<+>]<#""",
    
    'multiply': """$$:>[<[->+<]>[-<+>]<-]<>#""",
    
    'fibonacci': """# Generate first 10 Fibonacci numbers
>+>+<<
[#>.>:<<
  [->+>+<<]
  >[-<+>]
  <
  >.>#
  <<+>>
]""",
    
    'reverse': """Reverse input string
[,.>]<[.<]"""
}


def run_program(program_name=None, code=None, input_data=""):
    """Run a DequeLang program."""
    if program_name and program_name in EXAMPLE_PROGRAMS:
        code = EXAMPLE_PROGRAMS[program_name]
        print(f"Running example: {program_name}")
        print(f"Code:\n{code}\n")
    
    if not code:
        print("No code provided")
        return
    
    try:
        interpreter = DequeLangInterpreter(code, input_data)
        output = interpreter.run()
        
        print(f"\n\nFinal deque: {list(interpreter.deque)}")
        print(f"Output: {output}")
        
    except Exception as e:
        print(f"Error: {e}")
        import traceback
        traceback.print_exc()


def interactive_mode():
    """Run DequeLang in interactive mode."""
    print("DequeLang Interactive Mode")
    print("Enter DequeLang code line by line. Type 'RUN' on a new line to execute.")
    print("Type 'QUIT' to exit.")
    
    code_lines = []
    
    while True:
        try:
            line = input(">>> ").strip()
            
            if line.upper() == 'QUIT':
                break
            elif line.upper() == 'RUN':
                if code_lines:
                    code = '\n'.join(code_lines)
                    print(f"\nExecuting:\n{code}\n")
                    run_program(code=code)
                    code_lines = []
                else:
                    print("No code to run")
            elif line.upper() == 'EXAMPLES':
                print("\nAvailable examples:")
                for name in EXAMPLE_PROGRAMS:
                    print(f"  {name}")
                print("Use: run_program('example_name')")
            elif line.upper().startswith('RUN '):
                # Run example
                example_name = line[4:].strip()
                if example_name in EXAMPLE_PROGRAMS:
                    run_program(example_name)
                else:
                    print(f"Unknown example: {example_name}")
            else:
                code_lines.append(line)
                
        except EOFError:
            break
        except KeyboardInterrupt:
            print("\nInterrupted")
            break


def main():
    """Main entry point."""
    if len(sys.argv) > 1:
        # Run from command line
        if sys.argv[1] == '-i':
            interactive_mode()
        elif sys.argv[1] in EXAMPLE_PROGRAMS:
            input_data = sys.argv[2] if len(sys.argv) > 2 else ""
            run_program(sys.argv[1], input_data=input_data)
        else:
            # Assume it's a filename
            try:
                with open(sys.argv[1], 'r') as f:
                    code = f.read()
                input_data = sys.argv[2] if len(sys.argv) > 2 else ""
                run_program(code=code, input_data=input_data)
            except FileNotFoundError:
                print(f"File not found: {sys.argv[1]}")
    else:
        # Show usage
        print("DequeLang - Deque-based Turing-complete Language")
        print("=" * 50)
        print("\nUsage:")
        print("  python deque_lang.py [filename] [input]")
        print("  python deque_lang.py -i  (interactive mode)")
        print("  python deque_lang.py [example_name] [input]")
        print("\nExamples:")
        for name, code in list(EXAMPLE_PROGRAMS.items())[:3]:
            print(f"  {name}: {code[:50]}...")
        
        print("\nTry: python deque_lang.py hello")
        print("Or: python deque_lang.py -i")


if __name__ == "__main__":
    main()

Examples

Hello, World!

+++{+++}++++++[>+<-]>.>+[+>+<]>.>+++.+++..+++.>[-]<[-]<[-]<

Cat Program

>+[,.+]

More Examples

Coming Soon.