Examples

The best way to internalize Varphi's syntax and semantics is by reading and writing code. This section presents three fundamental programs that progress from simple state machines to multi-tape algorithms.

---

1. The Binary Incrementer (Single Tape)

This machine takes a binary number (e.g., 1011) on the tape and adds 1 to it (resulting in 1100).

The Logic

1. Scan Right: We start at the beginning (left) of the number. We must traverse to the far right end to find the Least Significant Bit (LSB).

2. Scan Left (Carry): Once we hit a BLANK at the end, we move one step left and enter the "carry" state.

   • If we see a 1, change it to 0 and keep moving left (carry over).

   • If we see a 0, change it to 1 and stop (carry consumed).

   • If we see a BLANK (overflow), write 1 and stop.

The Code

// Step 1: Move to the far right of the string
// If we see 0 or 1, keep moving RIGHT.
start   (0)      start    (0)     (RIGHT)
start   (1)      start    (1)     (RIGHT)

// When we hit a BLANK, we've passed the number. 
// Move LEFT back onto the last digit and switch to 'carry' mode.
start   (BLANK)  carry    (BLANK) (LEFT)


// Step 2: Perform the addition
// Case A: Found a '1'. Flip to '0' and keep carrying left.
carry   (1)      carry    (0)     (LEFT)

// Case B: Found a '0'. Flip to '1'. No more carry needed. Halt.
carry   (0)      halt     (1)     (STAY)

// Case C: Found a BLANK. This means we overflowed (e.g. 11 + 1 = 100).
// Write the final '1' and Halt.
carry   (BLANK)  halt     (1)     (STAY)

---

2. The Equality Tester (Multi-Tape)

This program compares two strings on two separate tapes to see if they are identical. It demonstrates the power of Varphi's variable support. We define a specific rule for "match" and a generic rule for "mismatch," relying on the compiler to pick the right one.

The Logic

1. Match: If Tape 1 has $x and Tape 2 has $x (the same symbol), move both heads right.

2. Mismatch: If Tape 1 has $x and Tape 2 has $y (implicitly different), the strings are not equal. Reject.

3. End: If both tapes hit BLANK at the same time, the strings were equal. Accept.

The Code

// Case 1: Both characters match
// In this case, just move both heads right
// Specificity: ($x, $x) uses 1 unique variable. 
// This is MORE specific than the ($x, $y) rule below.
// If both heads see the same symbol, this rule WILL be hit.
compare  ($x, $x)        compare  ($x, $x)        (RIGHT, RIGHT)

// Case 2: Both characters are BLANK
// In this case, the strings are equal (or we would've failed already)
compare  (BLANK, BLANK)  accept   (BLANK, BLANK)  (STAY, STAY)

// 3. Case 3: The two characters mismatch
// Specificity: ($x, $y) uses 2 unique variables.
// This rule runs only if the ($x, $x) rule above fails to match.
compare  ($x, $y)        reject   ($x, $y)        (STAY, STAY)

We did not need to explicitly write transitions for length mismatches (e.g., ($x, BLANK)). Because ($x, $y) matches any two symbols (including a symbol and a blank), it automatically catches cases where one tape ends before the other.

---

3. The Palindrome Detector (Multi-Tape)

This machine determines if a string is a palindrome (reads the same forwards and backwards). We use a two-tape approach: copy the input to the second tape, then compare them in opposite directions to make sure the string reads the same in reverse order.

The Logic

1. Copy: Copy the input from Tape 1 to Tape 2. Both heads end up at the far right.

2. Rewind Head 1: Move the head on Tape 1 back to the start of the string. Keep the head on Tape 2 at the end of the string.

3. Converge: Move Head 1 RIGHT (forward) and Head 2 LEFT (backward). If the symbols match at every step, it is a palindrome.

The Code

// Step 1: Copy
// Copy Tape 1 to Tape 2.
// While there is input on Tape 1, write it to Tape 2.
start   ($x, BLANK)     start    ($x, $x)       (RIGHT, RIGHT)

// When we hit the end (BLANK), step back one cell to the last char.
// Switch to 'rewind' mode.
start   (BLANK, BLANK)  rewind   (BLANK, BLANK) (LEFT, LEFT)


// Step 2: Rewind Head 1
// We want Head 1 at the start of Tape 1, but Head 2 must stay at 
// the end of Tape 2.
// As long as Head 1 reads a symbol, move it LEFT.
// Keep Tape 2 where it is (STAY).
rewind  ($x, $y)        rewind   ($x, $y)       (LEFT, STAY)

// When Tape 1 hits the BLANK at the start, move it RIGHT once
// to land on the first character. Switch to 'compare'.
rewind  (BLANK, $y)     compare  (BLANK, $y)    (RIGHT, STAY)


// Step 3: Compare
// Tape 1 scans forward (RIGHT), Tape 2 scans backward (LEFT).
// ---------------------------------------------------------

// Case A: Match ($x, $x). 
// The symbols are the same. Continue checking.
compare ($x, $x)        compare  ($x, $x)       (RIGHT, LEFT)

// Case B: Success.
// If both hit BLANK, we finished the whole string successfully.
compare (BLANK, BLANK)  accept   (BLANK, BLANK) (STAY, STAY)

// Case C: Mismatch ($x, $y).
// Because ($x, $x) is more specific, this rule only runs if 
// symbols differ.
compare ($x, $y)        reject   ($x, $y)       (STAY, STAY)