Documentation

This documentation provides an in-depth guide to the Ulto programming language. Use the navigation links below to explore detailed sections on Variables and Data, Control Structures, and Reversibility in Ulto. Each section includes grammar rules, code examples, and comprehensive descriptions to help you understand the key features of the language.

For detailed docstring for the codebase you can visit on the link below

Ulto Docstrings

Reversibility

One of the defining features of the Ulto programming language is its support for reversible computing. Reversibility allows the program's state to be traced back to previous states, providing a powerful mechanism for debugging, rollback, and state management. This is achieved primarily through the rev and revtrace tokens.

The rev token has two forms. Named with a variable, it steps that one variable back. Written on its own, it steps back the whole previous statement, which is how an if or a loop is reversed.

1. The `rev` Token

The rev token enables the reversal of a variable's state to its immediately previous value. This operation is sequential, ensuring that the program can only be reversed in the exact order the operations were performed, preserving the integrity of the execution flow.

Example: Using `rev`

x = 10
x += 5
print(x)  # Outputs: 15
rev x
print(x)  # Outputs: 10

In this example, the variable x is incremented by 5, and then the rev operation reverts x to its original value of 10.

Grammar Rule: Reverse Statement

reverse
    : REV ID?
    ;

This grammar rule defines the structure of a rev statement in Ulto. The identifier is optional: given one, rev reverses that variable, and given none it reverses the previous statement.

2. Reversing Control Flow with a bare `rev`

Written without a variable name, rev steps back one whole statement rather than one value. An if reverses whichever branch actually ran, and a loop reverses every iteration it actually performed, the loop variable included. Repeating rev walks back through the block a statement at a time.

Example: Reversing an `if` Statement

x = 10
if x > 5:
    x = x - 6
else:
    x = x + 100
print(x)  # Outputs: 4
rev
print(x)  # Outputs: 10

This is the case that shows why reversal is recorded rather than recomputed. After the branch runs, x is 4, so re-testing x > 5 would answer false and point at the wrong branch. The branch body destroyed the very value its own condition was testing. Ulto does not re-test it: the changes the branch made were recorded as they happened, so reversing the statement undoes exactly those.

Example: Reversing a Loop

k = 0
total = 0
for k in range(1, 6):
    total += k
    if total > 6:
        total += 100
print(total)  # Outputs: 215
rev
print(total)  # Outputs: 0, and k is back to 0

The nested if fires on some iterations and not others, and nothing needs to record how many times the loop went round. A single rev unwinds the whole statement.

Example: Walking Backwards Statement by Statement

p = 0
p += 3
p += 10
p += 100
print(p)  # Outputs: 113
rev
print(p)  # Outputs: 13
rev
print(p)  # Outputs: 3

Statements that changed no state are stepped over rather than counted, so a print between them does not consume a rev. Output already written cannot be unwritten.

3. The `revtrace` Token

The revtrace token allows you to view the history of a variable's state over multiple operations. However, unlike rev, revtrace does not revert the variable to a previous state; it only prints the past states for inspection. The actual reversal still requires the use of rev.

Example: Using `revtrace`

x = 5
x += 10
x *= 2
print(x)  # Outputs: 30
revtrace x 2
# Outputs the state 2 steps back: 5
rev x
print(x)  # Outputs: 20 (Reverts one step back to x *= 2)

Here, revtrace x 2 prints the value of x from two operations ago, but rev x only reverts the variable to its previous one at a time. This is done to ensure no variables are destroyed during the process and all reversal are sequential without missing a step to ensuring intergrity for reversibility.

Grammar Rule: Revtrace Statement

revtrace
    : REVTRACE ID NUMBER
    ;

This grammar rule defines the structure of a revtrace statement. It includes the revtrace keyword followed by an identifier and a number, indicating how far back in the history to trace.

4. Preserving State with LogStack

Unlike traditional programming languages, where variable assignment is often destructive (overwriting the previous value), Ulto uses a log stack to preserve every state change. This allows the program to safely reverse operations without losing any information.

Example: Non-destructive Assignment

y = 50
y /= 2
rev y
print(y)  # Outputs: 50

Even though y was divided by 2, the original value is preserved in the log stack. The rev operation restores y to 50.

5. Pruning Operations

To manage memory, Ulto prunes the record of what has happened. Only changes that have already been reversed are released. A change still outstanding is the sole record of how to return to an earlier state, so discarding it would destroy the reversibility the language exists to provide, and under Landauer's principle that discarding is precisely the erasure the language is built to avoid. Having already been reversed, a change carries no such duty, and its stored value can be let go.

Example: Pruning in Action

z = 100
z += 25
z -= 10
rev z
print(z)  # Outputs: 115 (reverts the last operation)

Reversing z -= 10 makes that step eligible for pruning, because it has served its purpose. The steps still ahead of it stay, so z can be walked all the way back to 100.

6. What Reversal Costs

Keeping history is not free, and Ulto works to make it cheaper wherever the shape of a program allows.

A change of the form x += e, where e does not read x, is its own inverse: undoing it is a subtraction rather than a stored value. Nothing has to be kept but the operand, which matters when the replaced value is large and the operand is small.

Such changes also compose, so a loop that only adds and subtracts is recorded once for the entire run rather than once per iteration. A thousand i += 1 steps undo as a single i -= 1000, and reversing that loop costs the same whether it went round ten times or ten thousand.

A variable is left out of that summing wherever it would lose something asked for: if the loop also assigns it outright, if the body contains a reversal, or if rev x or revtrace x n names it anywhere in the program, since both of those walk a variable back one change at a time.