However, there is no useful series: how about writing a Brainfuck interpreter

Lisp is a write-only language? You forgot the famous turing-complete “garbled code”.

A recent Codewars exercise involved implementing a brainFuck (or BF) interpreter. The process of hands-on practice is very interesting, and various problems are encountered in the process. Finally, through the test, the code is relatively close to the current JS high score solution. This article will cover some knowledge and implementation details.

“Imaginative” language – BF introduction

BrainFuck (later abbreviated as BF), the name alone is easily imaginative and has an indefinable “philosophical” appeal. So if you can’t resist googling, you might find something like this:

Is the picture already vivid?

The literal meaning of BF already implies that it is a language that is not very intuitive and easy to read, and certainly not a universal language at the moment. She belongs to the category of Esolang (which stands for Esoteric programming language).

BF was created in the 1930s and was used in the early PC (Amiga). If you want to learn more about BF, you can browse Wikipedia.

What are the current application scenarios of BF?

I think, to a melon eating masses, to understand it, writing force and mental improvement is very useful. BF has minimalism (make the design of children’s shoes as well as to understand the next) and functional (Turing complete) characteristics, aimed at users to bring confusion and challenges, rich working people’s amateur life.

Eight operators and their operations

BF, as a minimalist computer language, has only 8 operators, respectively: < > + -,. []. Its functions are shown in the following table:

BF is based on a simple machine model that includes, in addition to eight instructions, an array initialized to zero in bytes, a pointer to that array (initially pointing to the first byte of the array), and two byte streams for input and output.

An interesting analogy to BF is this:

1. If you think of machine memory as an infinitely long “train” (similar toArrayorListData structure), the cargo in each compartment (storage unit) is digital by default0, the train has only one conductor (data pointer);
2. <>It is equivalent to the conductor moving between carriages. Only when the conductor is in a certain carriage can the goods of the carriage be operated.
3. +-Equivalent to the conductor on the current carriage of goods to increase or decrease;
4. .Equivalent to the loading of the train, the conductor will replace the current carriage of goods with a single batch of goods entered by the freight station (ASCII code of one character);
5. .The name of the goods in the current carriage (single character) will come out;
6. []It is equivalent to the conductor moving back and forth between two carriages that meet the conditions;

Note here that each element of the array is one byte in size; – Commands allow overflow, which can be replaced by 255 + commands. For example, when the value of a storage unit is 255, the result of executing the instruction + is 0. Similarly, 0 executes the instruction – and the result is 255.

Analogies with common language

Thus, the BF operator is analogous to a general-purpose language (C as an example) :

BF interpreter JS function implementation

Code attached:

function brainLuck(code, input) {             / / @ 1
  const inputChars = input.split(' ');         / / @ 2

  const codes = code.split(' ');               / / @ 3
  let codeIdx = 0;

  const arr = [];                             / / @ 4
  let arrIdx = 0;
  let outputStr = ' ';                         / / @ 5

  while (codeIdx < code.length) {             / / @ 6
    const ops = codes[codeIdx];

    const handleLeftBracket = (a)= > {         / / @ 7
      if (~~arr[arrIdx] === 0) {
        let cnt = 1;

        while (cnt) {
          codeIdx++;
          if (codes[codeIdx] === '[') {
            cnt += 1;
          }
          if (codes[codeIdx] === '] ') {
            cnt -= 1; }}}};const handleRightBracket = (a)= > {        / / @ 8
      if(~~arr[arrIdx] ! = =0) {
        let cnt = 1;

        while (cnt) {
          codeIdx--;
          if (codes[codeIdx] === '] ') {
            cnt += 1;
          }
          if (codes[codeIdx] === '[') {
            cnt -= 1; }}}};switch (ops) {                            / / @ 9
      case '>':
        arrIdx += 1;
        break;
      case '<':
        arrIdx -= 1;
        break;
      case '+':
        arr[arrIdx] = (~~arr[arrIdx] + 1) % 256;
        break;
      case The '-':
        arr[arrIdx] = (~~arr[arrIdx] || 256) - 1;
        break;
      case ', ':
        const iptChar = inputChars.shift();
        arr[arrIdx] = iptChar ? iptChar.charCodeAt(0) : arr[arrIdx];
        break;
      case '. ':
        outputStr += String.fromCharCode(arr[arrIdx]);
        break;
      case '[':
        handleLeftBracket();
        break;
      case '] ':
        handleRightBracket();
        break;
    }

    codeIdx++;                               / / @ 10
  }

  return outputStr;                          / / @ 11
}

Copy the code

Description of the implementation idea (corresponding to the number of comments in the code) :

(1) We implemented a function brainLuck to simulate the interpretation execution of BF language. The use of function brainLuck is as follows:

const code = ', + / -. + ';
const input = 'Parksben' + String.fromCharCode(255);

const output = brainLuck(code, input);
console.log(output); // -> 'Parksben'
Copy the code

(2) Cut the input string into a single character and temporarily store it in the array inputChars;

(3) BF program is cut into a single operator to facilitate traversal of each instruction, and codeIdx is used as the subscript for traversal;

(4) Declare an array ARR to simulate machine memory, and store the values generated by the procedure in this array;

(5) Use the string outputStr to store the program output;

(6) Traverse the BF operator and perform corresponding operations on different instructions;

(7) Method handleLeftBracket is used to match the current bracket (subscript codeIdx).

(8) Method handleRightBracket is used to match the current bracket [(subscript codeIdx);

(9) Switch statements used to process different instructions;

(10) codeIdx increments one to traverse codes forward;

(11) Program output;

read

Brainfuck: a Programming Language or a Joke?

Some BF examples of Daniel Cristofani

Esoteric programming language – Wikipedia

The text/Parksben

Focus on 2/3D visualization and front-end development

Sound/fluorspar

This article has been authorized by the author, the copyright belongs to chuangyu front. Welcome to indicate the source of this article. Link to this article: knownsec-fed.com/2018-08-13-…

To see more sharing from the front line of KnownsecFED development, please search our wechat official account KnownsecFED.

Welcome to leave a comment to discuss, we will reply as far as possible.

Thank you for reading.