WLoop

WLoop (pronounced "double loop") is a Turing-complete language based on LOOP and Kleene's T predicate. It was created on December 12th, 2017 by User:Sacchan.

Structure

Each WLoop-program consists of two LOOP-programs: One that describes a T predicate and one that describes a U function. The T predicate is executed repeatedly on the program input with an increasing value in the special register X. Once the T predicate returns True, the current X value is fed as the sole parameter into the U function which handles program output.

Syntax and Semantics

A statement (for both T and U) is one of the following (R is any natural number including zero, S is any statement):

• R+
• R-
• SS
• R[S]
• X[S]

Additionally, T has the following two special statements:

• T
• F

while U has the following special statement:

• P[R]

Finally, a program is written as

• S|S

where the first statement is a T-statement and the second statement is a U-statement

The machine model for WLoop is a register machine with infinitely many registers, each storing arbitrarily large natural numbers including zero, numbered with natural numbers including zero, plus the special register X. All registers are initialized with zero and the program parameters are written to the first n special registers for the T-predicate. For the U-function, the first 256 registers are initialized with their index (so r0 := 0, r1 := 1...) for convenience, while all registers from r256 up are initialized with zero. The special register X contains the least value that satisfies T. The statements described above have the following semantics:

• R+ : Increment the value of register R
• R- : Decrement the value of register R. If the value is already zero, nothing happens
• SS : Execute the two statements in order
• R[S] : Execute statement S as many times as the current value of register R
• X[S] : Execute statement S as many times as the current value of special register X
• T : Return True
• F : Return False
• P[R] : Write a char with the ASCII-code of the current value of register R to the output

Note that if the T predicate finishes execution without any explicit return, the implicitly returned value is False.

The program execution, in pseudocode, is as follows:

x := 0
while not T(x,in) do
  x++
U(x)

While the two loop programs are guaranteed to terminate (as they are primitive recursive), the whole program will not terminate if T is always false.

Examples for T-Predicates

Sign Function

   0[X[T]F]X[F]T

As soon as X and r0 are both zero or not zero, return true.

Boolean NOT

   0[X[F]T]X[T]

Inversion of the program above

Boolean OR

   X[0[T]1[T]F]0[F]1[F]

If X > 0 then either r0 or r1 have to be > 0. If x == 0, both r0 and r1 have to be == 0

Boolean AND

   0[1[X[T]F]]X[F]T

If r0 > 0 and r1 > 0, X has to be > 0. Otherwise, X has to be == 0

Addition

A simple T-predicate that is true as soon as X is r0+r1

   2+X[2+]0[2-]1[2-]2[T]

Idea: r2 is initialized with x+1. Then, r2 := r2 - r0 - r1 is calculated. The first time r2 is positive (for increasing x) is exactly when x == r0+r1. In this case, the final loop 2[T] is executed and True is returned.

Example U-Functions

Print as char

The simplest possible output is outputting X as a char:

   X[0+]P[0]

Print numeric char

We can also print a value between 0 and 9 as correct char for that number:

   X[48+]P[48]P[10]

External resources

• A reference implementation of the interpreter, written in Haskell.