Progline

An esoteric programming language, and by esoteric, I mean as esoteric as Fractran.

A program consists of several directed lines on the Euclidean plane. A line has four properties: the direction it is going to, whether it is bounded to the “back” (negative, opposite of the line’s direction) (and if so, the endpoint), whether it is bounded to the “front” (positive, along the line’s direction) (and if so, the endpoint), and an attribute. All lines are open (doesn’t include the endpoints).

The program must consist of the line y = 0 directed to the “right” (positive; “left” is negative) that is not bounded to the back; this is the “main line” equivalent to the main procedure in other languages.

The lines may intersect, but no intersection may be passed by more than two non-vertical lines; this results on a compile error. No two non-vertical lines may coincide at more than one point either; this also results a compile error.

The program begins with a “program counter” (PC) at (-\infty, 0). PC always moves along the direction of the line it’s on. When it reaches an intersection (thus meeting another line, which we will call L), some action happened which cause the PC to choose between the two lines, according to the attribute of L.

Vertical lines (infinite/undefined slope) behave very differently though. A vertical line has no direction, and the PC never goes along a vertical line. There is a completely different set of attributes for vertical lines. Generally non-vertical lines and intersections are for various conditionals, and vertical lines are about programs.

The program ends successfully if the PC can be proven not to meet any other intersection. The program returns a runtime error if the PC reaches an endpoint of a line.

The program has an “input stack”. True to its name, when the program is executed, all input is moved to the input stack so that the first bit in input is the top bit in the stack. The program modifies this stack (as the sole movable data storage). The program also has a standard output.

Attributes for non-vertical lines:
– Is 1: Pops a bit from the input stack. If it’s 1, PC moves to the line met; if it’s 0, PC stays on the same line. If there is no bit to read, the program returns a runtime error.
– Is 1 Seen: Similar to “Is 1”, but pushes back the bit to the input stack afterwards.
– Is Empty: Checks whether the input stack is empty. If it is empty, PC moves to the line met. If it is not empty, PC stays on the same line.

The three attributes above also come with the negated variants: PC stays on the same line if the condition is met and moves to the line met otherwise.

– Move: PC is forced to move along this line. (Note that as only the attribute of the line met that is checked, PC can move out from this line on the next intersection.)

Vertical lines:
– Output: Prints a 1 if the PC has a positive ordinate (y-coordinate), 0 if the PC has a negative ordinate, and doesn’t print anything otherwise.
– Push: Pushes a 1 to the input stack if the PC has a positive ordinate, 0 if the PC has a negative ordinate, and doesn’t push anything otherwise.

So far that’s all attributes I can think of.

Progline can be specified in natural English, but since I want a more compact definition:

Every line I write is of this format:
(equation) (direction) (back-boundedness) (front-bounded-ness) (attribute)

Equation is always in the form y = slope * x + constant for non-vertical lines and x = constant for vertical lines.

Direction is Left or Right for non-vertical lines and Up for vertical lines. (The latter makes sure a back endpoint is lower than a front endpoint, which is usually natural to humans (smaller numbers to the left of larger numbers when written).)

Each boundedness is either None or a point that the line is guaranteed to pass.

Attribute is one of the above.

A line that is preceded by * is a comment. A blank line is also allowed to clarify procedures better.

Sample program:

Copy input bit
Outputs the first bit in input, or leave the output empty if there is no input.

* Main line
y = 0 Right None None Move

* Check whether input stack is empty. If it’s empty, go to the left. We’ll make sure no line afterwards interferes with this line, so this successfully exits the program.
y = x Left (1,1) None Is Empty

* Otherwise, read the first bit in the input (that is proven to exist). If it’s 1, go up with the first line; if it’s 0, go down after passing the first line unchanged. Note that as endpoints are open, these two lines don’t intersect.
y = x-10 Right (-10, 0) None Is 1
y = -x+12 Right (11, 1) None Move

* Now PC is above the x-axis if the input is 1 and below otherwise. Also, PC won’t meet any other line, so the program exits successfully.
x = 14 Vertical None None Output

Infinite loop
This utilizes the push vertical attribute to generate numbers endlessly, while keeping the input stack near empty.

* Begin by pushing a 0 to the stack. The first line is the obligatory main line, the second line moves PC down, the third line pushes 0, the fourth line moves PC up (passing the ended main line to above x-axis), and the fifth line keeps the PC on a horizontal line just for the sake of ease.
y = 0 Right None (-9, 0) Move
y = -x-10 Right None None Move
x = -9 Up None None Push
y = x+8 Right None None Move
y = 2 Right None None Move

* Begin the fun. The loop utilizes the triangle (-2, 2)—(2, 2)—(0, 4).

* First, the PC will pass an Is 1 line. This line will be skipped in the first iteration, but will be followed in later iterations; keep reading. This also has the side effect of consuming the 0, which helps keeping the stack empty (although it’s not necessary).
y = x+4 Left None None Is 1

* Now, the PC will pass a Push line. Because it has ordinate 2, it will push 1 to the stack.
x = 0 Up (0, 1) (0, 3) Push

* We move back to our Is 1 line.
y = -x+4 Left None None Move

* Now, it will meet our Is 1 line before, and will move along that line because our bit is 1. The PC then meets the y=2 line again with empty stack, repeating the state and hence proving an infinite loop.

Progline programming problems! (some are open)
– Can you find a Copy input bit program that has no endpoints of lines anywhere? (I found one.)
– Can you find an Infinite loop program that doesn’t push values into the stack, even if it means an infinite input is required? (I found one.)
– Can you find an Infinite loop program that doesn’t push values into the stack but has only a finite input? (I haven’t found one 😦 ) Or otherwise prove that this is impossible.
– Can you make the Hello, world! program? (Assume that every 8 bits output is bundled into one ASCII character, with earlier bit being more significant and printed characters are from left to right. So “123” can be output by 001100010011001000110011, as “00110001” is “1”, “00110010” is “2”, and “00110011” is “3”, concatenated together.) (I found one.)
– Can you make a program that generates the Thue-Morse sequence? (I haven’t found one 😦 )

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s