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.

Strange Computer Languages: A Hacker’s Field Guide

January 26, 2022 by Al Williams 47 Comments

Why do we build radios or clocks when you can buy them? Why do we make LEDs blink for no apparent purpose? Why do we try to squeeze one extra frame out of our video cards? We don’t know why, but we do. That might be the same attitude most people would have when learning about esolangs — esoteric programming languages — we don’t know why people create them or use them, but they do.

We aren’t talking about mainstream languages that annoy people like Lisp, Forth, or VBA. We aren’t talking about older languages that seem cryptic today like APL or Prolog. We are talking about languages that are made to be… well… strange.

INTERCAL

We have to start at the beginning. INTERCAL. This was started as a joke in 1972 and the acronym is purportedly for Compiler Language With No Pronounceable Acronym. There was no actual implementation, though, until around 1990. Now there are two: C-INTERCAL and CLC-INTERCAL.

Since INTERCAL is a parody, it makes some very odd choices. For example, bitwise operators like AND operate with two arguments, but one of the arguments is reversed. That is, the top bit of one operand matches the bottom bit of the second operand. In a nod to social convention, there is a modifier known as PLEASE that you should sometimes use when, for example, reading data as in “PLEASE READ IN.” If you don’t use it often enough, the compile will fail warning you that the program is insufficiently polite. However, if you use it too often, you’ll also get an error that your program is excessively polite.

Originally, the implementation used EBCDIC, so it uses some characters that don’t appear on conventional 7-bit ASCII systems. This forced some character substitutions and now, with Unicode, some versions will allow the old-style characters if you prefer them. The INTERCAL manual renames nearly all the special characters for further confusion. A single quote is a “spark” and the equal sign is a “half-mesh”. Only the ampersand remains unscathed.

Want to know more? Be careful what you wish for.

Continue reading “Strange Computer Languages: A Hacker’s Field Guide” →