Programming in 1L a/Printable version

Programming in 1L a

The current, editable version of this book is available in Wikibooks, the open-content textbooks collection, at
https://en.wikibooks.org/wiki/Programming_in_1L_a

Permission is granted to copy, distribute, and/or modify this document under the terms of the Creative Commons Attribution-ShareAlike 3.0 License.

The language

How it works

1L_a is a two-dimensional programming language, which means the code is not necessarily executed linearly. So when the program starts, an instruction pointer, or IP for short, spawns on the first character of the first row, heading down. It will go forward every step and execute the command it reaches unless something changed its direction.

There are two instructions: GO and STOP. The GO instruction performs different operations depending on the IP's direction. (We will talk about the instructions later after we've introduced the array.) The interpreter will remember the first character of your program, and every time it reaches that character, the GO instruction is executed. Everything else executes STOP. I prefer using the whitespace for the GO-triggering character because you could trace how the IP moves by just looking at the program easily.

The Array

1L_a is array-based, which means you can manipulate a built-in array. (Here, the array is bool-typed.) The first three elements in the array, namely TL0, TL1, and TL2, are for I/O which we will discuss later.

Data Pointer

There's a data pointer (not to be confused with IP), or DP for short, initially pointing at TL2. All your operations are based on the data pointer. You can move the data pointer, or read and toggle the bit it is pointing.

You may notice the fact that I said read and toggle, instead of reading and write. That's because 1L_a doesn't have a direct way to set one bit. To set a bit to 0, you may write something like:

• Read the bit.
• If the bit is 1, toggle it.

TL0

TL0 is the first element in the array. If it is toggled, the program will read input from STDIN or write output to STDOUT, depending on the value of TL1 and TL2. That's the only way to do I/O in this language.

TL1

TL1 is the I/O switch. When you toggle TL0, the interpreter will check TL1, if TL0 is 0, the program will read a bit for input, and store its value in TL2; If TL1 is 1, the program will output a bit.

TL2

TL2 is registered for the bit to be outputted or the newly-inputted bit. It is closer to the normal-bits, so when you want to output a bit, you can move it from the normal bits to TL2 without passing other special registers(in 1L_a, moving your DP is very tricky), and when you inputted a bit, you can read that bit on the way back "home".

Instructions

As mentioned earlier, there are two instructions in 1L_a: GO and STOP. Here's a table showing the operation they do:

Instruction	IP direction	Operation
GO	Up	The DP is moved one bit to the right.
GO	Left	The DP is moved one bit to the left, AND THEN the bit pointed by the DP is toggled. (Note: The toggled bit is on the new position, not the old position.)
GO	Down	Do nothing.
GO	Right	Do nothing
STOP	Any	Move one cell back(here, "back" means the direction opposite to the IP direction), and read the pointed bit. If 0 is read, the IP will turn counterclockwise, if 1 is read, the IP will turn clockwise.

Unlike what you might think, the "Do nothing" operation is very useful in such a language, since it transfers the IP without any "side effects", like modifying the array.

A side note: The I/O Buffers

This language is bit-based, so it outputs by bits, not characters. Yet, in many implementations, those bits are stored inside a "buffer", when there are already 8 bits in the buffer, those bits are outputted as ASCII code, and they are cleared. For the input, similar things happen. When you enter a character, the program automatically decomposes it into 8 bits, and then stores it into an "input buffer". When the program wants to read a bit, it reads one bit in the buffer, and that bit was removed.

Flattened 1L a

A way to create 1L_a programs is to write the corresponding Brainf*** program first, and then convert it into 1L_a. So it's time for a new language, Flattened 1L_a, which took place between 1L_a and Brainf***.

Brainf*** and its minimalizations

As you might know, Brainf*** is a well-known and one-dimensional programming language. Like 1L_a, there's DP and IP too, yet the DP only moves in a line, and the DP moves on a character array instead of a bit array. It is Turing complete and has 8 instructions. Here are them:

Instruction	Operation
>	Move the DP to the right
<	Move the DP to the left
+	Increment the memory cell the DP is pointing at
-	Decrement the memory cell the DP is pointing at
.	Output the character pointed by DP
,	Input a character and store it in the cell at the DP
[	Jump past the matching ] if the cell at the DP is 0
]	Jump back to the matching [ if the cell at the DP is 0

Yet, as a Turing-Tarpit(languages that are designed to be both have only a few instructions and is Turing-Complete), 8 instructions are a bit too much. So we may create Brainf*** equivalents that have less instructions.

We call a language Brainf*** equivalent if you can implement every instructions in the language in Brainf*** and implement every instructions in Brainf*** in the language.

Boolf***

It's pretty much obvious that we can reduce Brainf*** to 7 instructions by operating on an array of bits(like 1L_a!) instead of an array of characters, so that the instruction + and - become one: the toggle operation, notated as @. It is possible to use our powerful flow control to simulate a character array, but it would be bulky and I'm too lazy to do that. Luckily, someone have already done it for us:

Brainf*** The new language
--------- ----------------
>         >>>>>>>>>
<         <<<<<<<<<
+         >>>>>>>>[<]@>[@>]<<<<<<<<<[@]
-         @>>>>>>>>@[<@]>[>]<<<<<<<<<[@]
[         @[>>>>>>>>@[<@]>[>]<<<<<<<<<[@]>>>>>>>>[<]@>[@>]<<<<<<<<<@[@
]         >>>>>>>>>@<<<<<<<<<]>>>>>>>>>[<<<<<<<<<@>>>>>>>>>@]<<<<<<<<<]
.         >.<
,         >,<

We call this language Boolf***. Since Brainf*** is Turing-Complete, and you can translate any Brainf*** program into Boolf*** program, Boolf*** is Turing-Complete too.