Turing Complete Programming On ARM With Two Instructions

September 29, 2023 by Maya Posch 14 Comments

There are many questions that can be asked for software projects, with most of these questions starting with ‘Why…?’. This is true for the challenge of proving that cascading stylesheets are Turing-complete, or that you don’t need all those fancy ISA bits of an ARM processors when you already got the LDM and STM commands in the 32-bit ISA. What originally started off as a bit of a running gag in a group of developers led to [Kellan Clark] implementing a Turing-complete computer and a functioning interpreter using nothing but these two opcodes.

Adding some Brainfsck to your ARM, inside your GBA. — Adding some Brainf**k to your ARM, inside your GBA.

These two opcodes essentially allow the storing or reading of data into memory from any combination of the 16 general-purpose registers (GPRs). This makes them both extremely versatile and also extremely open to ‘abuse’ like in this example. For a straightforward implementation that could prove the concept, [Kellan] decided to pick one of everyone’s favorite esoteric programming languages: Brainf**k, creating the charmingly titled Armf**k that allows anyone to write BF programs for any suitable ARM processor, like the ARM7TDMI in the Game Boy Advance that [Kellan] targeted.

As a proof of concept it’s unquestioningly intriguing, and a great example of how the most powerful parts of any ISA are those that move data around. After all, as anyone who writes ASM and C knows, computers are just machines that can copy bytes around really fast to make stuff happen. Mind-blowing examples like these serve to illustrate that point quite well.

Tip kindly provided by [eeucalyptus].

Two Esoteric Programming Languages, One Interpreter

November 19, 2022 by Elliot Williams 9 Comments

Many of you will have heard of the esoteric programming language Brainf**k_. It’s an example language that’s nearly impossible to use because it’s too simple. It’s basically a Turing computer in code – you can essentially put characters into an array, read them out, increment, decrement, and branch. The rest is up to you. Good luck!

What could be worse? Befunge, a language that parses code not just left-to-right or top-to-bottom, but in any direction depending on the use of ^, v, >, and <. (We love the way that GOTO 10 looks like a garden path in the example.)

Uniting the two, [rsheldiii] brings us BrainFunge, a Brainf**k_ interpreter written in Befunge. And surprisingly, the resulting write-up sheds enough light on both of the esoteric programming languages that they make a little bit of sense. If you try to read along, you’ll definitely be helped out by Esolang Park, which was new to us, and accommodates the non-traditional parsing while displaying the contents of the stack.

If you get a taste of the esoteric, and you find that you’d like a little more, we have a great survey of some of the oddest for you. After cutting your teeth on Befunge, for example, we bet you’ll be ready for Piet.

Code Wrong: Expand Your Mind

January 29, 2022 by Elliot Williams 24 Comments

The really nice thing about doing something the “wrong” way is that there’s just so much variety! If you’re doing something the right way, the fastest way, or the optimal way, well, there’s just one way. But if you’re going to do it wrong, you’ve got a lot more design room.

Case in point: esoteric programming languages. The variety is stunning. There are languages intended to be unreadable, or to sound like Shakespearean sonnets, or cooking recipes, or hair-rock ballads. Some of the earliest esoteric languages were just jokes: compilations of all of the hassles of “real” programming languages of the time, but yet made to function. Some represent instructions as a grid of colored pixels. Some represent the code in a fashion that’s tantamount to encryption, and the only way to program them is by brute forcing the code space. Others, including the notorious Brainf*ck are actually not half as bad as their rap — it’s a very direct implementation of a Turing machine.

So you have a set of languages that are designed to be maximally unlike each other, or traditional programming languages, and yet still be able to do the work of instructing a computer to do what you want. And if you squint your eyes just right, and look at as many of them all together as you can, what emerges out of this blobby intersection of oddball languages is the essence of computing. Each language tries to be as wrong as possible, so what they have in common can only be the unavoidable core of coding.

While it might be interesting to compare an contrast Java and C++, or Python, nearly every serious programming language has so much in common that it’s just not as instructive. They are all doing it mostly right, and that means that they’re mostly about the human factors. Yawn. To really figure out what’s fundamental to computing, you have to get it wrong.

Character Generation In 144 Bytes

December 15, 2016 by Adam Fabio 34 Comments

[Jaromir Sukuba] has an awesome BrainF*ck interpreter project going. He’s handling the entire language in less than 1 kB of code. Sounds like a great entry in the 1 kB Challenge. The only problem is the user interface. The original design used a 4 line character based LCD. The HD44780 controller in these LCDs have their own character table ROM, which takes up more than 1 kB of space alone.

[Jaromir] could have submitted the BrainF*ck interpreter without the LCD, and probably would have done well in the contest. That wasn’t quite enough for him though. He knew he could get character based output going within the rules of the contest. The solution was a bit of creative compression.

Rather than a pixel-by-pixel representation of the characters, [Jaromir] created a palette of 16 single byte vectors of commonly used patterns. Characters are created by combining these vectors. Each character is 4 x 8 pixels, so 4 vectors are used per character. The hard part was picking commonly used bit patterns for the vectors.

The first iteration was quite promising – the text was generally readable, but a few characters were pretty bad. [Jaromir] kept at it, reducing and optimizing his vector pallet twice more. The final design is pretty darn good. Each character uses 16 bits of storage (four 4-bit vector lookup values). The vector pallet itself uses 16 bytes. That means 64 characters only eat up 144 Bytes of flash.
This is exactly the kind of hack we were hoping to see in the 1 kB challenge. A bit of creative thinking finds a way around a seemingly impossible barrier. The best part of all is that [Jaromir] has documented his work, so now anyone can use it in the 1 kB challenge and beyond.

If you have a cool project in mind, there is still plenty of time to enter the 1 kB Challenge! Deadline is January 5, so check it out and fire up your assemblers!