# Welcome The official website for the Varphi programming language. Welcome to the Varphi user documentation! Here you'll get an overview of all the amazing features Varphi offers to help you build, simulate, and debug Turing machines and finite automata. ### What is Varphi? Varphi is a modern, domain-specific language designed for defining, simulating, and studying Turing machines and finite automata. While Turing machines are the fundamental model of computation, defining them has historically been tedious, relying on verbose state tables or fragile graphical simulators. Varphi bridges the gap between theoretical computer science and modern software engineering, providing a concise syntax, a robust compiler, and high-quality developer tooling. ### Why Varphi? Varphi treats Turing Machines as code, not diagrams. It introduces modern language features to the theoretical domain: * **Concise Syntax:** Define complex state transitions using pattern matching and variables instead of listing every single symbol combination. * **Native Multi-Tape Support:** Write algorithms for $$k$$-tape machines as easily as single-tape ones. The compiler handles the complexity. * **First-Class Tooling:** Debug your machines with a dedicated [VS Code Extension](/vs-code-extension), complete with syntax highlighting, live error reporting, and a step-by-step debugger (DAP). ### Jump right in


Installation	Install Varphi on your machine	/pages/7FvWQMF0kTK7HGhlQfmo
The Varphi Language Reference	Learn about Varphi's syntax	/pages/hRtMutGeePNkdlerpdMV
Examples	See some of what you can do with Varphi	/pages/zcs2H5y0A2RAgLAvckMp

# Installation Although Varphi is fundamentally a compiled language, we have created a *compiler driver* which handles both compiling your Varphi code and running the compiled code. We call this tool *the Varphi Interpreter*, or *vpi* for short. The Varphi Interpreter is installable via two methods, which we cover below. ### Installation via pip (Recommended) If you already have pip installed, you can easily install the Varphi Interpreter via ```bash pip install varphi-interpreter ``` {% hint style="warning" %} To avoid future issues, please create a Virtual Environment before installing. Simple instructions can be found below, but please refer to the [official guide](https://docs.python.org/3/library/venv.html) in case of any issues. \ \ On Windows: ``` python -m venv venv venv\Scripts\activate ``` On Linux/macOS: ``` python -m venv venv source venv/bin/activate ``` {% endhint %} The Varphi Interpreter should then be accessible through the `vpi` command. For example, you can confirm the installation succeeded using ```bash vpi --version ``` ### Installation via GitHub Releases We have pre-compiled some versions of the Varphi Interpreter for popular operating systems, namely the latest Windows, macOS, and Linux (Ubuntu) versions. The binaries are available on [GitHub Releases](https://github.com/varphi-lang/varphi/releases). These executables work right out of the box; just download the executable for your OS and invoke it over the command line. For example, to confirm the executable works, you can use ```bash /path/to/the/downloaded/executable --version ``` # 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: ```bash 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). ```bash 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. {% hint style="warning" %} Note: Piping will not work well with debug mode enabled, so avoid composition/piping when `--debug` is used. {% endhint %} ### 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](#understanding-performance-metrics)). #### 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`. ```bash 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... ... ``` {% hint style="danger" %} 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. {% endhint %} #### 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. ```bash 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. │ ╰───────────────────────────────────────────────────────────────────────────────────────────────╯ ``` # The Varphi Language Reference A comprehensive guide to the syntax and semantics of the Varphi programming language. Varphi is a domain-specific language (DSL) designed for defining, simulating, and studying Turing Machines. Unlike traditional formal definitions found in textbooks, Varphi employs a concise yet fully expressive syntax that scales from simple single-tape machines to complex multi-tape algorithms. This document serves as the formal specification for Varphi programs. *** ### 1. Program Structure A Varphi program describes the state transition diagram of a Turing Machine. The file structure is flat and line-oriented. * **Transitions:** The program is a sequence of **transition lines**. Each line represents a directed edge in the Turing Machine's state graph. * **Entry Point:** The machine represented by a Varphi program initializes execution at the **current state of the first transition line in the file**. * **Newlines:** Newlines act as the statement terminator. * **Whitespace:** All non-newline whitespace is completely ignored. You may indent code as you please. #### Comments Varphi supports C-style comments for documentation. ``` // This is a single-line comment. /* This is a multi-line comment. */ ``` *** ### 2. Transition Lines Every valid transition line (i.e., line of code) in Varphi must contain exactly **five components** in a specific order. This strict structure ensures readability and parsing consistency. #### Syntax ``` ``` {% hint style="info" %} The above transition line template (although not syntactically valid) is read as follows: > If the machine's current state is ``, and the heads of the machine read ``, then switch the machine's state to ``, make the heads of the machine write ``, and shift the heads of the machine in the directions given in ``. > {% endhint %} #### Component Breakdown | Component | Description | Example | | ----------------- | ------------------------------------------------------ | ------------------------- | | **Current State** | The state the machine must be in to trigger this line. | `q0`, `start` | | **Read Tuple** | The pattern of symbols to match on the tape(s). | `(0)`, `($x, BLANK)` | | **Next State** | The state the machine transitions to. | `q1`, `halt` | | **Write Tuple** | The symbols to overwrite on the tape(s). | `(1)`, `($x, 1)` | | **Shift Tuple** | The direction to move the tape head(s). | `(RIGHT)`, `(STAY, LEFT)` | {% hint style="warning" %} The elements of the Read, Write, and Shift tuples of all transition lines must be enclosed in parenthesis, even if only one element is present. {% endhint %} #### Example A simple incrementer state: ``` /* - If the machine is on state q0, and "0" is seen on the current tape, then stay on q0, write back the "0", and move the head right - If the machine is on state q0, and "1" is seen on the current tape, then stay on q0, write back the "1", and move the head right - If the machine is on state q0, and the current tape cell is blank, then switch to q1, write a "1", and keep the head stationary. - That is, traverse the tape until a blank cell is found, then write a "1" to the cell. */ q0 (0) q0 (0) (RIGHT) q0 (1) q0 (1) (RIGHT) q0 (BLANK) q1 (1) (STAY) ``` {% hint style="info" %} In the above program, when a blank cell is observed, the program writes "1" to the cell and switches to state `q1`, leaving the head stationary. Since no transition applies for when the machine is on state `q1` and "1" is observed, the machine *halts*. A state that always results in the machine halting is called a *halting* (or *final*) *state*. {% endhint %} *** ### 3. The Tape Model & Symbols Varphi abstracts the machine's tape as an infinite strip of cells. Inside the Read and Write tuples, three types of symbols function as the alphabet. #### A. Literals *Alphanumeric* characters represent exact values on the tape. They are used for exact matching (so `0` will match only "0" on the tape) * **Examples:** `0`, `1`, `a`, `B`, `x`. #### B. The `BLANK` Keyword The keyword `BLANK` represents an empty tape cell (often denoted as $$\sqcup$$ in textbooks). This is often used when detecting end-of-input or clearing tape cells. #### C. Variables (Pattern Matching) {% hint style="info" %} Variables in Varphi are purely syntactic sugar, and thus any Varphi program that uses variables can technically be converted to one that does not use them. {% endhint %} Variables allow a single transition to handle multiple symbols, significantly reducing code size. * **Syntax:** A `$` followed by alphanumerical characters (e.g., `$x`, `$val`, `$1`). * **Semantics:** * **On Read:** The variable *binds* to the symbol currently under the corresponding tape head. * **On Write:** The variable evaluates to the symbol it bound during the read phase. **Variable Binding Examples** The following transition reads *any* symbol, remembers it as `$x`, transitions to `q1`, writes `$x` back (no change), and moves right. ``` // Identity operation; leaves input untouched q0 ($x) q1 ($x) (RIGHT) ``` **Constraint:** Variables are local to the transition line they appear in. You cannot use a variable in the `write_tuple` unless it was defined (bound) in the `read_tuple` on that same line. Further, variables with the same name that are used across different lines are totally independent. *** ### 4. Multi-Tape Support Varphi supports $$k$$-tape Turing Machines. The dimension $$k$$ is inferred from the first line of the program (based on the lengths of the Read, Write, and Direction tuples). #### Consistency Rule Every transition in the file must have a tuple length exactly equal to $$k$$. * If line 1 uses a tuple of length $$i$$ for its Read tuple, then $$k=i$$. * If any other tuple in the program has a length that is not $$k$$, a compilation error will be thrown. #### Example: 2-Tape Swap Machine This machine swaps the symbols on two tapes until it reaches a blank tape cell on either one, demonstrating the concepts of variables and multi-tape support. ``` // Swap the contents of two tapes copy ($x, $y) copy ($y, $x) (RIGHT, RIGHT) copy (BLANK, $ignore) all_done (BLANK, $ignore) (STAY, STAY) copy ($ignore, BLANK) all_done ($ignore, BLANK) (STAY, STAY) ``` {% hint style="warning" %} Notice that the second and third rules will always take precedence over the first one, since they are more specific. We discuss this more [below](#specificity-and-execution-priority). {% endhint %} {% hint style="info" %} By now, you should be able to recognize that `all_done` is a halting state in the above program. {% endhint %} *** ### 5. Control Flow & Nondeterminism #### Specificity & Execution Priority In Varphi, if multiple transitions match the current configuration (state and read symbols), the machine selects the "best" match based on **Specificity**. The compiler calculates a **Specificity Score** based on `(Unique Variables, Total Variables)`. Lower scores are prioritized. 1. **Priority 1: Fewest Unique Variables.** * Literals are more specific than variables. * Reusing a variable (constraints) is more specific than using distinct variables. 2. **Priority 2: Fewest Total Variables.** * If unique counts are equal, the rule with fewer variable slots (more literals) wins. **Resolution Table for the 2-Tape Case**

Rule Pattern	Unique Vars	Total Vars	Priority	Interpretation
`(0, 0)`	0	0	Highest	Exact literal match.
`($x, 0)`	1	1	High	One variable, one literal.
`($x, $x)`	1	2	Medium	Constraint: Both heads must read the same symbol.
`($x, $y)`	2	2	Lowest	Catch-all: Matches any two symbols.

#### Nondeterminism If two rules have the exact same Specificity Score and both match the tape state, the machine exhibits **Nondeterministic behavior**. The runtime will randomly select one of the valid transitions. Below is an example of a machine where the machine stochastically picks a branch at runtime. ``` // Nondeterministic Branching q0 (0) state_A (0) (LEFT) q0 (0) state_B (0) (RIGHT) ``` *** ### 6. Directions The Shift Tuple of a transition line dictates head movement. There are exactly three valid keywords that can be used in a Shift Tuple: * `LEFT`: Move head one cell to the left. * `RIGHT`: Move head one cell to the right. * `STAY`: Do not move the head. *** ### 7. Safety & Constraints #### Write Safety A variable cannot appear in the Write Tuple of a transition line unless it was defined (i.e., appears) in the Read Tuple of the same transition line. ``` // VALID q0 ($x) q1 ($x) (RIGHT) // INVALID: $y is undefined q0 ($x) q1 ($y) (RIGHT) ``` #### Keyword Safety While the parser allows keywords like `LEFT` or `BLANK` to be used as state names and variable names, this is strongly discouraged as it creates hard-to-read code. {% hint style="info" %} Pedantically speaking, `LEFT`, `RIGHT`, `STAY`, and `BLANK` are not keywords in Varphi, since they only function differently in certain contexts (i.e., certain tuples). As such, we can call them *context-specific keywords*. {% endhint %} # 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) ``` {% hint style="info" %} 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. {% endhint %} *** ### 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) ``` # VS Code Extension To make developing Turing Machines easier, we have developed a Varphi language extension for Visual Studio Code. This extension integrates the Varphi interpreter directly into your editor, providing features like syntax highlighting, error checking, and a fully interactive debugger. ### Installation You can install the language extension via the [Visual Studio Code marketplace](https://marketplace.visualstudio.com/items?itemName=varphi-lang.varphi). ### Features #### 1. Syntax Highlighting The extension provides full syntax highlighting for `.vp` files (the recommended file extension for Varphi). Keywords, states, and tuples are color-coded to improve readability and help you visually structure your transition rules. #### 2. Live Error Reporting The extension works in the background to validate your code as you type. It reports errors instantly via the **Problems** panel. Errors are underlined with red squiggles, and hovering over them reveals the specific error message from the compiler. #### 3. One-Click Execution You don't need to leave the editor to run your code. The extension adds dedicated **Run** and **Debug** buttons to the editor title bar (top right). * **Run (Play Icon):** Compiles and executes the current file in a dedicated terminal. * **Debug (Bug Icon):** Starts an interactive debugging session. When you click **Run**, the extension opens a dedicated "Varphi" terminal and executes your program, keeping your output separate from other terminal processes. #### 4. Interactive Debugging (DAP) The extension communicates with the Varphi Interpreter using the **Debug Adapter Protocol (DAP)**, allowing you to debug Varphi programs just like you would debug other languages. **Providing Tape Inputs** When you start a debug session, the extension will prompt you to provide initial values for your tapes via an input box at the top of the screen. You can press `Enter` to leave a tape blank, or `Esc` to finish providing inputs. **Stepping Through Code** Once the session starts, you can step through your Turing Machine line-by-line. The editor highlights the active transition rule in yellow, letting you trace exactly which logic is currently being executed. **Breakpoints** As with other language extensions, the Varphi extension fully supports breakpoints. ### Configuration By default, the extension assumes the Varphi Interpreter (`vpi`) is available in your system's `PATH`. If you have installed the interpreter in a custom location, you can configure the path in your VS Code settings: 1. Open Settings (`Ctrl+,`). 2. Search for `Varphi`. 3. Set **Varphi: Interpreter Path** to the location of your executable. If you prefer editing the setting in JSON, the setting is: ```json "varphi.interpreterPath": "/path/to/your/vpi" ``` {% hint style="danger" %} The path to the Varphi Interpreter must not include spaces or quotations. {% endhint %} # Ampliphi Ampliphi is a high-level, imperative programming language designed to compile down to the Varphi architecture. Ampliphi was originally developed by [Hassan El-Sheikha](https://www.linkedin.com/in/hassan-el-sheikha/), [Kevin Thevara](https://www.linkedin.com/in/kevin-thevara/), and [Youssef Abouzied](https://www.linkedin.com/in/youssef-abouzied/) as part of a compilers course at the University of Toronto. It provides a familiar C-like syntax with strong static typing, arrays, and procedures. It attempts to abstract away the complexities of writing raw Varphi assembly while utilizing an advanced compiler optimization pipeline to produce more efficient Varphi code. *** ### Quick Look Ampliphi programs consist of global variable declarations followed by procedures. The entry point of every program is the `main` procedure. Because Ampliphi compiles directly to Varphi, each declared variable maps directly to a tape in the generated Varphi code. When running your program via the Ampliphi CLI, you will be automatically prompted to initialize the values of these variables/tapes before the program executes. Here is a simple program that calculates the sum of an array: ```c // Global declarations int[5] arr; int sum; int i; bool cond; // Entry point procedure main { sum = 0; i = 0; // Note: Control flow conditions must be evaluated into a boolean variable first! cond = i < 5; while (cond) { sum = sum + arr[i]; i = i + 1; // Re-evaluate condition for the next iteration cond = i < 5; } } ``` *** ### Getting Started #### Installation You can install the Ampliphi toolchain directly via PyPI using `uv` or `pip`: ```bash uv pip install ampliphi ``` Alternatively, you can download the standalone executable for your operating system (Windows, macOS, or Linux) from our [GitHub Releases](https://github.com/varphi-lang/ampliphi/releases/latest). #### Usage To compile and run an Ampliphi source file, simply use the CLI: ```bash ampliphi my_program.aphi --run ``` If you use the `--run` flag, the CLI will interactively ask you to provide initial values for your global variables (tapes) before executing the compiled Varphi. You can also inspect the compilation pipeline by emitting the AST, IR, or Tokens: ``` Usage: ampliphi [OPTIONS] INPUT_FILE Options: -t, --tokens Print the token stream from the lexer. -a, --ast Print the abstract syntax tree. -c, --check Check syntax and types only (do not compile). -x, --xml Print the AST in XML format. -i, --ir Print the intermediate representation. -r, --run Run the compiled program immediately. --no-opt Disable optimizations. --help Show this message and exit. ``` *** ### Language Guide #### Variables and Types All variables in Ampliphi are **global** and must be declared at the top of the file before any procedures. Ampliphi supports two primitive types: `int` and `bool`, as well as fixed-size arrays. ```c int x; bool flag; int[10] arr; ``` {% hint style="info" %} In the compiled Varphi output for the snippet above, `x` and `flag` will each become a standard tape, while `arr` will consist of 10 array tapes. {% endhint %} #### Procedures Code is organized into procedures. A program must contain at least one procedure named `main`. Procedures can invoke other procedures using the `invoke` keyword. ```c procedure do_work { x = x + 1; } procedure main { x = 0; invoke do_work; } ``` #### Control Flow Ampliphi supports `if/else` and `while` statements. {% hint style="info" %} The condition for an `if` or `while` statement *cannot* be an inline expression (like `x < 5`). It **must** be a boolean identifier. You must evaluate your condition into a boolean variable first. {% endhint %} ```c bool greater; int x; procedure main { greater = x > 10; if (greater) { x = 10; } else { x = 0; } } ``` *** ### Formal Grammar Ampliphi follows a strict, easy-to-parse grammar. Below is the formal EBNF specification: ```ebnf program = {declaration} {procedure} declaration = type identifier ";" | type "[" int_literal "]" identifier ";" type = "int" | "bool" procedure = "procedure" identifier "{" {statement} "}" statement = assignment | if_statement | while_statement | invoke_statement assignment = identifier "=" rhs ";" | array_access "=" rhs ";" rhs = operand | unary_op operand | operand binary_op operand if_statement = "if" "(" identifier ")" "{" {statement} "}" "else" "{" {statement} "}" while_statement = "while" "(" identifier ")" "{" {statement} "}" invoke_statement = "invoke" identifier ";" operand = identifier | literal | array_access array_access = identifier "[" operand "]" binary_op = "+" | "-" | ">" | "<" | "==" | "&&" | "||" unary_op = "!" literal = int_literal | bool_literal bool_literal = "true" | "false" int_literal = digit {digit} identifier = letter { letter | digit } letter = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" | "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ``` # About Learn about Varphi's journey. ## The Story Behind Varphi My name is [Hassan El-Sheikha](https://hassanelsheikha.com/), and I am a Computer Science student at the University of Toronto. The story of Varphi begins not in a lab, but in a classroom during my time in CSC363: Computational Complexity and Computability. #### Motivation Like many computer science students, I was fascinated by the theory of computation. However, I quickly ran into a frustration shared by many of my classmates: Turing machines lacked a true "standard" representation. In the classroom, we alternated between drawing diagrams, writing pseudocode, or using verbose mathematical definitions to communicate our ideas. As noted in my research, these conventional representations (i.e., diagrams and transition tables) can often overwhelm students and obscure the fundamental computational ideas at play. The formal definitions were often fragile, and different textbooks utilized different symbols, which was sometimes confusing. I wanted to make a change in this domain. #### Research Opportunity My interest in the field deepened when my professor, [Dr. Mohammad Mahmoud](https://www.mmsquared.ca/), invited a cohort of students to join a reading course. The goal was to assist in developing a computability theory textbook and research advanced complexity classes. I had the honor of being part of this cohort. While working on the textbook, the frustration regarding inconsistent Turing machine definitions lingered. I pitched an idea to Dr. Mahmoud: a project to create a new standard language for representing Turing machines and finite automata; one that was readable, writable, and executable. He loved the idea and agreed to supervise the project. #### Development and Publication Over the course of four months, I developed the syntax and the language architecture. In January 2025, we launched Varphi v1.0.0. This initial version was minimalist by design. It focused on describing standard unary Turing machines with a single two-way infinite tape. While this made the language Turing-complete, it was admittedly tedious for writing complex algorithms. However, its simplicity was its strength for educational purposes. To validate the project, we integrated Varphi into the CSC363 curriculum. The results were exciting: * **Widespread Adoption:** We tested the tool in classroom trials involving 184 participants. * **Student Success:** Despite being given deliberately challenging tasks, 88% of students successfully completed them using Varphi. * **Positive Reception:** Students rated the tool highly (averaging 4.28 out of 5), noting that it helped simplify the representation of these abstract machines. This work culminated in the publication of our paper, *"Varphi: A Description Language for Turing Machines"* , which I [presented](https://www.utm.utoronto.ca/math-cs-stats/news/mcs-faculty-and-student-present-novel-programming-language-varphi-wccce-2025) at the Western Canada Conference on Computing Education (WCCCE 2025) in Calgary. [Read the full WCCCE 2025 Paper Here](https://mru.arcabc.ca/_flysystem/repo-bin/2025-09/El-Sheikha%26Mahmoud_WCCCE_2025_0.pdf)

Dr. Mohammad Mahmoud (left) and Hassan El-Sheikha (right) at WCCCE 2025

In 2026, I presented the next iteration of Varphi at WCCCE 2026 in Vancouver.

Hassan El-Sheikha presenting at WCCCE 2026

#### The Future of Varphi Today, Varphi has evolved far beyond its prototype roots. While v1.0.0 was restricted to unary, single-tape machines, the current version supports multi-tape, deterministic and non-deterministic machines with arbitrary alphabets, as well as finite automata. My vision is for Varphi to become the academic standard for representing and sharing these machines, bridging the gap between abstract theory and practical implementation for students and researchers alike.

:arrow-down-to-line:

:code:

:lightbulb: