Categories
Arduino software

Minimalist Programming

Sometimes it’s fun to do things just because they are interesting. This idea seems to be behind minimalist programming languages (languages with barely enough keywords to be viable). These languages have no useful purpose except to pose a challenge to programmers using them. Here’s one I played with on the Arduino.

Turing Machines

The Turing Machine is, arguably, the original idea behind most of these tiny languages. A Turing machine is a mathematical model of computation that defines an abstract machine that manipulates symbols on a strip of tape according to a table of rules.

Despite the model’s simplicity a Turing machine is capable of simulating any computer algorithm’s logic. This leads to the term Turing Complete – a machine that, given enough time and memory along with the necessary instructions, can solve any computational problem, no matter how complex.

Most computer languages today, including minimalist languages, are Turing-complete. Conditions for a language to be Turing-complete include conditional branching (e.g., “if” and “goto” statements, “branch if zero” instruction) and the ability to change an arbitrary amount of memory.

Minimalist Programming

Brainfuck (BF from now on) is an extreme minimalist programming language created in 1993 by Urban Müller. It is named, apparently, after the effect on your brain when you program using it. The language is Turing-complete and has no practical applications.

It comprises eight simple commands, a memory pointer and an instruction pointer. BF ignores all characters except the eight commands so no special syntax for comments is needed as long as the comments do not contain the command characters.

The language commands each consist of a single character:

>increment the data pointer (point to the next cell on the right).
<decrement the data pointer (point to the next cell on the left).
+increment (increase by one) the byte at the data pointer.
decrement (decrease by one) the byte at the data pointer.
.output the byte at the data pointer.
,accept one byte of input, storing its value in the byte at the data pointer.
[if the byte at the data pointer is zero, then instead of moving the instruction pointer forward to the next command, jump it forward to the command after the matching ] command (nesting allowed).
]if the byte at the data pointer is nonzero, then instead of moving the instruction pointer forward to the next command, jump it back to the command after the matching [ command (nesting allowed).

A simple BF program to add a cell to its neighbor is ‘[->+<]’ – yes it does mess with your brain!

A couple of additional ‘rules’ are specified for implemetors of the language:

  • The memory array should have at least 30,000 cells, if possible.
  • The memory pointer should start at the left end (RAM address 0).

Implementing on Arduino

In the spirit of doing something for no useful reason, I decided to implement a BF interpreter on an Arduino Uno.

This site has a bunch of ‘interpreter’ code examples in many languages and I used the ‘C’ version to implement my Arduino variant.

With respect to the a 30,000 byte ‘memory’, as the Uno has maximum of 2kb RAM, I compromised (!) with only a few hundred bytes available for BF code to use. The BF source code to be interpreted is stored as ASCII text in PROGMEM so it can be reasonably large, although it is fixed for each instance of the sketch.

Here’s the result (BF-run.ino)

const char PROGMEM program[] = // print "hello world"
"++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.";
const uint16_t MEM_SIZE = 400;

uint8_t getChar(void)
// blocking read one character from the serial input
{
  uint8_t n;
  while (!Serial.available()) {}
  n = Serial.read();
  return(n);
}

void setup(void)
{
  Serial.begin(9600);
  Serial.print(F("\n[BF run]\n\n"));
}

void loop(void)
{
  static uint16_t ip = 0; // instruction offset
  static uint8_t memory[MEM_SIZE] = { 0 };
  static uint8_t *mp = memory; // memory pointer
  char opcode = pgm_read_byte(program + ip);
  switch (opcode)
  {
    case '>': ++mp; break;
    case '<': --mp; break;
    case '+': ++(*mp); break; case '-': --(*mp); break;
    case '.': Serial.print((char)(*mp)); break;
    case ',': *mp = getChar(); break;
    case '[':
      if (!*mp)
      {
        uint16_t count = 1;
        while (count) 
        { 
          ++ip;
          if (pgm_read_byte(program + ip) == '[') ++count; 
          if (pgm_read_byte(program + ip) == ']') --count; 
        } 
      }
      break;
    case ']':
      if (*mp)
        {
          uint16_t count = 1;
          while (count) 
          { 
            --ip;
            if (pgm_read_byte(program + ip) == ']') ++count; 
            if (pgm_read_byte(program + ip) == '[') --count; 
          }
        }
        break;
  }
  if (opcode != '\0') // end of program string
  ++ip;
}

After playing with this for a while, I decided that it would be good to trace the program running and be able to load programs dynamically, so I implemented a version that uses a SD card to store both the program and the RAM. This version allows you to load the program from the SD card, run and step through the code and dump a block of memory.

All of this extra overhead made the interpreted BF code run much slower so I had to implement a paging system to load manage blocks of RAM on and off the SD card so that it remained responsive. That change delivered a huge performance lift. The sketch (BF-Explorer.ino) can be found in the code repository for this project, as it is too long to include here.

Sometimes it is just interesting to do stuff, and there’s a lot more BF related stuff to explore when I feel the urge.

More to read

References below are a starting point as they many more links in them.

http://www.hevanet.com/cristofd/brainfuck/

https://curlie.org/Computers/Programming/Languages/Brainfuck

https://en.wikipedia.org/wiki/Brainfuck

https://github.com/pablojorge/brainfuck

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s