Programming in 1L a/Flattened 1L a

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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[edit]

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***[edit]

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. Luckly, 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.