Running Varphi Programs

Once you have the Varphi Interpreter (vpi) installed, you can execute, debug, and analyze your Turing Machine programs directly from the command line.

Basic Usage

The general syntax for the interpreter is:

vpi [OPTIONS] INPUT_FILE

• INPUT_FILE: The path to your .vp source code.

Running a Program

To run a program, simply pass the filename. The interpreter will compile the code and then prompt you to enter the initial content for each tape defined in your program via standard input (stdin).

vpi example.vp

Example Session:

$ vpi example.vp
Number of input tapes: 1
Tape 1: hello

————————————————————————————————————————————————————————————
HALTED at state 'accept'
Time taken: 25 steps
Space used: 11 cells
Number of tapes: 1
Tape 1: hello

Input Formatting & Tape Behavior

Since Varphi allows alphanumeric characters on tapes, there are specific rules for how to represent blank cells and how the machine initializes head positions.

1. Representing Blanks (_)

The standard BLANK keyword used in Varphi source code programs cannot be typed easily in a terminal without confusing it for the characters "B", "L", "A", "N", and "K". When providing input, use the underscore _ to represent a blank cell.

• Example Input: abc_123

  • Varphi will interpret this as: ['a', 'b', 'c', BLANK, '1', '2', '3']

In any output of the Varphi Interpreter, a blank tape cell will also be represented with _.

2. Head Positioning

When a program starts, the tape head, for any tape of the machine, is always stationed at the first non-blank character of your input string. Leading blanks are essentially skipped for the purpose of initialization. If there is no non-blank character on the input tape, an arbitrary blank tape cell will be chosen.

Example: If you input _____123, the tape will contain those leading blanks (obviously, because there are infinite blanks in either direction anyways), but the head will start off pointing at 1, as shown below:

$ vpi --debug example.vp
Number of input tapes: 1
Tape 1: _____123

————————————————————————————————————————————————————————————
STEP 1 [State: start]
————————————————————————————————————————————————————————————
State: start (Line 4)
Tape 1: __[1]23
...

3. Tape Count & Composition

The input system allows you to input more or less tapes than the machine actually needs ($k$), according to two rules:

• Fewer Tapes: If you provide less tapes than required, the remaining tapes are automatically initialized to be blank.
• More Tapes: If you provide more tapes than required, only the first $k$ are used.

This allows convenient composition of Turing machines by piping the output of one to another, even if the two machines do not use the same number of tapes.

Note: Piping will not work well with debug mode enabled, so avoid composition/piping when --debug is used.

Execution Modes

vpi supports several flags to alter how the program is run.

1. Standard Run

By default, vpi runs silently until the machine halts. Upon completion, it prints the final state of all tapes and performance metrics (see below).

2. Debug Mode (--debug)

The --debug flag activates an interactive, step-by-step debugger. This is essential for visualizing state transitions and head movements.

• Visual Head: The character currently under the tape head is enclosed in brackets (e.g., [1]).
• Stepping: Press ENTER to advance the machine by one step.
• Interruption: You can stop execution at any time using Ctrl+C.

vpi --debug example.vp

Output Preview:

...
————————————————————————————————————————————————————————————
STEP 7 [State: compare]
————————————————————————————————————————————————————————————
State: compare (Line 29)
Tape 1: __[1]1_
Tape 2: _1[1]__

>> Press ENTER to step forward...
...

As the command line debugger requires you to input ENTER over standard input, you must not use this mode if you are redirecting the input tapes from a file, since redirection closes standard input.

3. Syntax Check (--check)

If you only want to verify that your code is valid without running it, use --check. This is useful for catching syntax errors quickly.

vpi --check example.vp

If the code is valid, it prints OK. If there are errors, the compiler driver will point to the exact line and column of the issue. An example of a compilation error is shown below:

Compilation Error: 
error: extraneous input '\n' expecting {')', ','}
   --> line 33:60
     |
  33 | compare (BLANK, BLANK)  accept   (BLANK, BLANK) (STAY, STAY
     |                                                             ^

Understanding Performance Metrics

When a Varphi program halts, the interpreter reports Time taken and Space used. It is important to understand how these are calculated.

Time Complexity

Time taken is simply the total number of transitions (steps) the machine executed from the start state until it reached a halting configuration. You can see the exact steps by using the --debug flag.

Space Complexity (Auxiliary Space)

Space used calculates the Auxiliary Space complexity, not the total tape lengths.

• The cells occupied by your initial input do not count toward space complexity.
• Space is only counted when the machine writes to or visits a cell outside the range of the original input.

For example, if you input a string of length 5, and the machine only moves back and forth within those 5 cells, the Space used will be 0 cells. If it moves one step to the right of the input and reads that tape cell, the space used becomes 1 cell.

CLI Reference

                                                                                                 
 Usage: vpi [OPTIONS] INPUT_FILE                                                                 

 Compile and execute a Varphi program.

╭─ Arguments ───────────────────────────────────────────────────────────────────────────────────╮
│ *    input_file      FILE  Path to the Varphi source file [required]                          │
╰───────────────────────────────────────────────────────────────────────────────────────────────╯
╭─ Options ─────────────────────────────────────────────────────────────────────────────────────╮
│ --dap                Run in Debug Adapter Protocol mode (for IDEs).                           │
│ --debug              Enable verbose step-by-step logging (Standard mode only).                │
│ --check              Compile only to verify syntax (does not execute).                        │
│ --version  -V        Show the version and exit.                                               │
│ --help               Show this message and exit.                                              │
╰───────────────────────────────────────────────────────────────────────────────────────────────╯