Unbounded integers

Context

After 16-bit integers, we can try to implement 32-bit, 64-bit, ... but the principles are the same.
Instead, let's define unbounded integer, in  other word one single integer that has no limit (in other words, an integer that can execute +[+] without never ending).
We will focus on one single integer, because it is far more simple. Actually, any implementation we can imagine will rely on arrays with dynamic sizes. The array can be resized, meaning that the data before and / or after will have to be moved. This is not impossible, but extending one array then means extend one array + move next integer + move integer after this one + move integer after this one + ...
This will be definitely too long (not impossible anyway), so let's just implement one single number like this.

The data structure:

• A number N will be encoded in an array of cells
• Encoding will be in base 255
• Note: not 256. This allows to have values from 1 to 255. Therefore, there won't be any null cell, so no need to have a 2-cells array to browse it. This divides the memory used by 2.
• Operator overrides will be defined below. However, we will need 2 different overrides for LEFT and RIGHT: one from the number N and one to number N.
• Data representation:

memory_before [0 0 0 0 D1 D2 D3 .... Dx 0] memory_after

• By default, cursor will be on first base-255 digit D1.

Process

• Print: simply print D1. However, the values are between 1 and 255. So
• Decrease D1
• Print D1
• Increase D1
• Read: idem
• Reset all digits (set to 1)
• Read to D1
• Increase D1
• Inc:
• Set loop flag.
• Start with digit D1 and loop
• if current digit is null, set to 1
• increase current digit
• move before loop flag
• if not null, reset loop flag
• otherwise, set to 1 (equivalent to null in our representation)
• process next digit if loop flag is on
• Move back values to their position
• Dec: idem
• Set loop flag
• Start with digit D1 and loop
• if current digit is null, set to 1
• decrease current digit
• move before loop flag
• if not null, reset loop flag
• otherwise, set to 255
• process next digit if loop flag is on
• Move back values to their position
• While:
• Our structure is [R 0 0 0 D1 D2 D3 .... Dx 0]
• We want to check if at least one of the digits is not 1 and store into R
• Set loop flag
• Start with D1 and loop
• Reset loop flag
• if current digit is not null
• Set loop flag
• if digit is not 1 (decrease then while)
• Set R to 1
• Reset loop flag
• Move digit before loop flag
• increase moved digit to recover initial value (see 4 lines above)
• process with next digit if loop flag is on
• Move back values to their position
• Move to result
• If not null: enter while, reset result, go to D1
• Loop
• Same as while to compute result
• Move to result
• If not null: loop
• Go back to D1
• Left (from N)
• 5 cells on the left
• Left (to N). Note: with unbounded array, it is not recommended to have things after the array
• 2 cells on left for last digit then go to D1
• Right (to N)
• 5 cells on the right
• Right (from N). Note: again, with unbounded array, going after array in memory is not recommended
• Go to last digit then 2 cells on the right

Code - print

-.+

Code - read

Go to last integer
[>]<
Set all digits to 1 up to first
[[-]+<]
Read value and increase
>,+

Code - inc

Set loop flag
<+
Loop
[
  Go to current digit
  >
  If current digit is null then initialize to 1
    reset loop flag as else bit
    [<-]
    go to else bit or 0 and if else bit then set digit to 1 and go to 0
    <[->+<<]
    go back to digit and reset loop flag
    >+>
  Increase current digit and move before loop flag
  +[-<<+>>]
  Go to current digit
  <<
  If not null reset loop flag and set to 1 otherwise
  [>-]>[<+>>]
  Move loop flag to left and go to loop flag then loop
  <[->+<]>
]
Go to last moved digit
<<
Move back all digits
[[->>+<<]<]>>>

Code - dec

Set loop flag
<+
Loop
[
  Go to current digit
  >
  If current is null then initialize to 1
    reset loop flag as else bit
    [<-]
    go to else bit or 0 and if else bit then set digit to 1 and go to 0
    <[->+<<]
    go back to digit and reset loop flag
    >+>
  Decrease current digit and move before loop flag
  -[-<<+>>]
  Go to current digit
  <<
  If not null reset loop flag and set to 255 otherwise
  [>-]>[<->>]
  Move loop flag to left and go to loop flag then loop
  <[->+<]>
]
Go to last moved digit
<<
Move back all digits
[[->>+<<]<]>>>

Code - while

Set loop flag
<+
Loop
[
  Reset loop flag and go to current digit
  ->
  If not null: still in the number
  [
    Set loop flat to 1
    <+
    If current digit is not 1
    >-[
      set result to 1
      <<<[<]<+
      reset loop flag
      >>[>]>-
      move digit before flag
      >[-<<+>>]
    ]
    Add 1 to digit copy and go back to location
    <<+>>
  ]
  Move loop flag
  <[->+<]
  Go to loop flag and loop
  >
]
Go to last moved digit (can be 2 or 3 cells on the left)
<<[>]<
Move back all digits
[[->>+<<]<]
Go to result and start while
<[
  Reset result and move back to first digit
  ->>>>

Code - loop

Set loop flag
<+
Loop
[
  Reset loop flag and go to current digit
  ->
  If not null: still in the number
  [
    Set loop flat to 1
    <+
    If current digit is not 1
    >-[
      set result to 1
      <<<[<]<+
      reset loop flag
      >>[>]>-
      move digit before flag
      >[-<<+>>]
    ]
    Add 1 to digit copy and go back to location
    <<+>>
  ]
  Move loop flag
  <[->+<]
  Go to loop flag and loop
  >
]
Go to last moved digit (can be 2 or 3 cells on the left)
<<[>]<
Move back all digits
[[->>+<<]<]
Go to result and loop if needed
<]
Move back to initial position
>>>>

Code - left from N

<<<<<

Code - left to N

<<[<]>

Code - right to N

>>>>>

Code - right from N

[>]>

Example - try it

This code is equivalent to +[.+] with unbounded integers

>>>>++<+[->[<+>-[<<<[<]<+>>[>]>->[-<<+>>]]<<+>>]<[->+<]>]<<[>]<[[->>+<<]<]<[->>>>-.+<+[>[<-]<[->+<<]>+>+[-<<+>>]<<[>-]>[<+>>]<[->+<]>]<<[[->>+<<]<]>>><+[->[<+>-[<<<[<]<+>>[>]>->[-<<+>>]]<<+>>]<[->+<]>]<<[>]<[[->>+<<]<]<]>>>>

16-bit values: concept, structures, IO and moves (1)

Context

What may be annoying using Brainfuck is the size of the cell. You can't (in theory) have integers greater than 255. Of course, this is the case for most of the programming languages, where integers are encoded using either 32 or 64 bits, but the limit is far higher in those cases.
Obviously, the 'cheating' solution would be to use another BF interpreter implementation that supports 16-, 32- or 64-bit integers. But how to use, let's say, 16-bit integers (up to 65,535) using regular Brainfuck?
Our only option would be to

1. Define a new data structure
2. Re-define all the 8 operators using this new data structure
   What does '+' means ? Add 1. So, how to modify our data that represents an integer N to represents integer 'N+1' instead, and same for - , . < > [ ]

Structure(s)

Actually, I found 2 different data structures, one that uses more memory cells but with faster overrides of operators, and one using less cells but with longer processes.

Actually, both needs 4 cells, but when you have multiple integers in memory, first one uses 4 cells per integer, while second one can use only 3 cells (reusing a cell from previous integer)

In this post and all the coming ones, we'll define the 2 structures and all their operators.

Structure 1 - "4 cells"

Let's have 4 cells A, B, C, D to represent integer N; with

• A = 0
• B = 0
• C and D so that N = D * 256 + C

A and B are used for logical branching that will occur in our future code.
Using this structure, "having on a value" means having cursor on C

Structure 2 - "3 cells"

Let's have 4 cells A, B, C to represent integer N; with

• A and B so that N = B * 256 + A
• C = 0

Again, C is used for logical branching, but also "D", which is the "C" from the previous integer.
Using this structure, "having on a value" means having cursor on A

IO

Using those 2 structures, let's define how to read or print a value. Read means reinitialize the "quotient" (D, or B, according to the structure) and read value in "remainder" (C, or A)

Operation	"4 cells"	"3 cells"
,(read)	,>[-]<	,>[-]<
.(print)	.	.

Moves

Now, let's do the same wit

Operation	"4 cells"	"3 cells"
<(move left)	<<<<	<<<
>(move right)	>>>>	>>>

Calc tool

Context

Let's implement a calculation tool. Inputs will be operations as [operand 1][operator][operand 2] and output will be the operation with its result

Initial state

• Memory: empty
• Cursor: first cell
• Input: an operation [operand][operator][operand] where operatands are numbers in base 10, and operator one of + - * /

Process

• Read input - memory after reading should be operand operator_flag operand 0 0 0 0 ....
• Print char (faster than rebuilding it afterwards)
• Use a switch/case
• If it's a *, set operator flag to 0 (do nothing) and start reading a new integer
• Same for +, - and * but set operator flag to 1, 2 or 3
• Otherwise, it's a digit: build integer
• multiply previously read integer by 10
• add the new digit
• Move operator to have operand 0 operand operator flag switch_flag
• Set switch_flag to 1 and use another switch/case
• Flag is 0: multiply numbers and store result in second cell
• Flag is 1 or 2: same, but sums up or subtract numbers
• Flag is 3: move operand 2, then perform division
• Display = symbol
• Display result
• If it's 0, then display '0'
• Otherwise, display the computed integer

Code - try it

Codes:
Multpily 42
Add 43
Subtract 45
Divide 47

>,[
  print char
  .
  subtract 42
  >++++++[-<------->]+<
  [
    not a multiplication
    -
    [
      not an addition
      --
      [
        not a subtraction
        --
        [
          not a division
          this is a digit
          build number
          ->++++++++[-<<[->+>>+<<<]>>>[-<<<+>>>]<]<[-<+>]
        ]>[-
          this is a division
          set operation flag to 3 and start new number
          <+++>>>
        ]<
      ]>[-
        this is a subtraction
        set operation flag to 2 and start new number
        <++>>>
      ]<
    ]>[-
      this is an addition
      set operation flag to 2 and start new number
      <+>>>
    ]<
  ]>[-
    this is a multiplication
    start new number
    >>
  ]
  read next char
  <,
]
move operator
<<[->>+<<]>>
>+<[
  not a multiplication
  -
  [
    not an addition
    -
    [->-<
      division
      move operand 2
      <[->>+<<]
      divide
      <<[->+>>+>-[<-]<[->>+<<<<[->>>+<<<]>]<<]
      clear and move result
      >[-]>>>[-]>[-<<<<+>>>>]<<
    ]>[-
      subtraction
      <<<<[->+<]>>[-<->]>>
    ]<
  ]>[-
    addition
    <<[-<+>]<<[->+<]>>>>
  ]<
]>[-
  multiplication
  <<<<[->>[-<+>>+<]>[-<+>]<<<]
  clean operands
  >>[-]>>
]

print =
+++++++++[-<+++++++>]<--.[-]

<+<[>-<
  print result if not 0
  [>>>>++++++++++<<<<[->+>>+>-[<-]<[->>+<<<<[->>>+<<<]>]<<]>+[-<+>]>>>[-]>[-<<<<+>>>>]<<<<]<[>++++++[<++++++++>-]<-.[-]<]
]>[
  or print 0
  +++++++[-<++++++>]<.[-]
]

Final state

• Memory: empty
• Cursor: second cell
• Input: empty
• Output: the operation followed by equal sign and its result

Note: of course, this is a calc tool valid in the Z/256Z group, meaning that all inputs and results are taken modulo 256. Moreover, the division is actually an euclidean division, so result is not displayed completely (only the quotient is)

Self-interpreter: memory access, inc, dec, print and read (6)

Context

As a reminder, here is the final memory map

0 0 0 {instrs} 0 inst_ptr 0 0 0 inactive_flag direction_flag memory_ptr  0 0 0 0 0 {mem}

Let's now how to access a value in memory and implement '+', '-', '.' and ',' operations.

Initial state

• Memory: see above
• Cursor: on instruction, next to inst_ptr
• Input: any

Process

• Access memory value
• Copy memory pointer, and add one to copy
• While copy is not null
• Move through the first memory array (initially: none)
• Move second memory array (initially: whole memory) first element to end of first array. Init / reinit first cell of the block to 1.
• Decrease copy
• Loop invariant: target item is Nth of second memory array, where N is the actual copy value (1-based index)
• When copy is null: N is the last element of first memory array
• Go to last element of first memory array
• Execute instruction
• Move array back to initial position

Code - generic

duplicate memory pointer and move to copy
>>>>[->+>+<<]>>[-<<+>>]<+
[
  -
  go to next memory cell
  >>>>[>>]+>>
  (re)init/copy memory indicator
  [-]>[-<<+>>]<<<[<<]<<
]go to current memory cell
>>>>[>>]<do somethingmove array back to initial position
<[[->>+<<]>[->>+<<]<<<]
<<<<<<<

Code (minified) for inc

>>>>[->+>+<<]>>[-<<+>>]<+[->>>>[>>]+>>[-]>[-<<+>>]<<<[<<]<<]>>>>[>>]<+<[[->>+<<]>[->>+<<]<<<]<<<<<<<

Code (minified) for dec

>>>>[->+>+<<]>>[-<<+>>]<+[->>>>[>>]+>>[-]>[-<<+>>]<<<[<<]<<]>>>>[>>]<-<[[->>+<<]>[->>+<<]<<<]<<<<<<<

Code (minified) for print

>>>>[->+>+<<]>>[-<<+>>]<+[->>>>[>>]+>>[-]>[-<<+>>]<<<[<<]<<]>>>>[>>]<.<[[->>+<<]>[->>+<<]<<<]<<<<<<<

Code (minified) for read 

>>>>[->+>+<<]>>[-<<+>>]<+[->>>>[>>]+>>[-]>[-<<+>>]<<<[<<]<<]>>>>[>>]<.<[[->>+<<]>[->>+<<]<<<]<<<<<<<

Final state

• Memory: see above
• Cursor: on instruction, next to inst_ptr
• Input: unchanged
• Output: unchanged

Back to previous step

Go to next step

Self-interpreter: load code (2)

Context

Let's now implement the first part of our interpreter: read code to execute - and code only. The part dedicated to execution's input should remain unread for now.
Here are the characters we want to read. First value is the corresponding ASCII code, second is 35 below those values (35 is ASCII code of #, our separator.

• # separator 35/0
• + inc 43/8
• , read 44/9
• - dec 45/10
• . print 46/11
• > left 60/25
• < right 62/27
• [ while 91/56
• ] loop 93/58

Our goal here will be to

1. Read character
2. Subtract 35 to check if character is the separator, or not
1. If separator: stop reading
2. If not: store instruction value (even the -35 one, it doesn't matter as long as '+' is now defined by 8, ', ' by 9, ...)

Initial state

• Memory: empty
• Cursor: first cell
• Input: any

Process

• Read char
• While current char is not null
• Decrease by 35, set else bit
• If value is not null, read next char
• Otherwise, stop reading

Code

>>>,
leave some cells for future use and read char
[
  >+++++[-<------->]+
  subtract by 35 and set else bit
  <[>,>]
  if not # then read next char
  >[[-]>]
  otherwise do not read and back to same position in both cases
  <<
]>

Code (minified)

>>>,[>+++++[-<------->]+<[>,>]>[[-]>]<<]>

Final state

• Memory: 0, 0, 0, instructions, 0, IP (=0)
• Cursor: on IP (instruction pointer, currently 0)
• Input: remaining is interpreted code's input only
• Output: unchanged

Example

Live 'Instruction reader' example, that reads code to execute until it reaches separator, then display the code (add 35 to each char and print).

Back to previous step
Go to next step

Read comma-separated numbers

Context

Let's have an input like '12,34,56,78,9,100'. The goal is to have an array of numbers [12], [34], ... in memory, reading comma-separated decimal numbers. To achieve it, we'll have to

• Read a char
• If it's a comma (ASCII code 44), then start a new number
• Otherwise it's a digit, add it to ten times the current number

Note: this post is strongly related to array definition and read decimal number ones

Initial state

• Memory: 0, 0, 0, 0...
• Cursor: first cell
• Input: comma-separated decimal numbers (A,B,C,...)

Process

• Leave one cell to delimit array, plus one cell for current first integer read
• While a character is read
• Remove 44 (',' ASCII code)
• Set else bit
• If result is not null
• It's a digit. Remove 4 to get the decimal digit value
• Update current integer
• Otherwise
• Start a new integer 

Code 

>>
array delimiter and first integer (currently 0)
,[
  >++++[-<----------->]+<
  remove 44 (comma ASCII code) and set bit else
  [>-<
    if read value is not 44 => it is a digit
    ----
    remove 4 again (to remove 48 which is 0's ASCII code)
    >+++++++++[-<<[->+>>+<<<]>>>[-<<<+>>>]<]<[-<+>]
    multiply current integer by ten and add new digit
  ]
  >[-
    else
    >
    move to next integer
  ]<
,]

Code (minified)

>>,[>++++[-<----------->]+<[>-<---->+++++++++[-<<[->+>>+<<<]>>>[-<<<+>>>]<]<[-<+>]]>[->]<,]

Final state

• Memory: 0,A,B,C,...,0
• Cursor: on final 0 (end of array)
• Input: empty
• Output: unchanged

Example

Live 'Comma-separated decimal to ASCII' converter: type comma-separated ASCII code to display the corresponding string (e.g. input 50,48,49,55 produces 2017)

Read decimal number

Context

Given an input '123', reading input will populate cells with values [49], [50] and [51] (ASCII codes of 1, 2 and 3). Here, we want to read 123 as a number, and have one unique value [123].
Therefore, we'll have to:

• Read a char
• Convert it to a digit (-48)
• Multiply the previous result by 10, and add the new digit

Initial state

• Memory: 0, 0, 0, 0
• Cursor: first cell
• Input: a decimal number

Process

• Move to second cell (first is for result)
• While a digit is read
• Convert to decimal digit (-48)
• Multiply first cell by 10 and add current digit
• Loop invariant: first cell = current read number (decimal)
• When all chars are read, first cell equals number to read

Code 

>,[
  >++++++[-<-------->]
  remove 48
  +++++++++[-<<[->+>>+<<<]>>>[-<<<+>>>]<]
  add first cell 9 times to second
  <[-<+>]
  add second cell to first (result: first cell * 10 plus second cell)
  ,
  read next char
]<

Code (minified)

>,[>++++++[-<-------->]+++++++++[-<<[->+>>+<<<]>>>[-<<<+>>>]<]<[-<+>],]<

Final state

• Memory: number value (decimal)
• Cursor: first cell
• Input: empty
• Output: unchanged

Example

Live 'Decimal to ASCII' converter: type a number (e.g. 122) to see the corresponding ASCII char in output (e.g. 'z')