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: be smart (5)

Context

We now have conversion operators to handle 16-bit integers. We also created a piece of code to display 16-bit integers as decimal numbers.
The code was quite verbose however. Using those operators, one should really be careful regarding the "type" used. Do not use 16-bit integers when it's not needed.

Here, for example, we have

• One integer N (16-bit)
• divided by ten
• divisor is always 10: 8-bit
• remainder is always less than ten: 8-bit
• quotient may be more than 256: 16-bit
• else flag used by division: 8-bit
• Take remainder and add 48 to have a char
• 48 can be added using 6x8, all of them (including remainder) are always less than 256: 8-bit
• Clear remaining part of divisor: 8-bit
• Move quotient and start again: 16-bit

There is a huge place to improve code here.

The best way is probably to write BF instructions for 8-bit and plain text instructions for 16-bit, and finally replace plain text, to avoid mistakes.

Example:

WHILE

    RIGHT

    >>>++++++++++<<<

    LEFT

    WHILE

        MINUS

        RIGHT

        +>>+>-[-<]<[> RIGHT PLUS LEFT <-<<[->>>+<<<]>]<

        LEFT

    LOOP

    RIGHT

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

......

LOOP

[.[-] <<< LEFT]

Then, replace WHILE, RIGHT, ... (and you can also remove all '< >' or '> <')

Minified code to print 2056 - 75% smaller - try it

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

16-bit values: summary and application (4)

Context

Here is a summary of our structures, and operations implemented to handle the basic 8 ones

Structure 1 - "4 cells"

A, B, C, D to represent integer N; with

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

Cursor on C

Structure 2 - "3 cells"

A, B, C to represent integer N; with

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

Cursor on A

Operation	"4 cells"	"3 cells"
,(read)	,>[-]<	,>[-]<
.(print)	.	.
<(move left)	<<<<	<<<
>(move right)	>>>>	>>>
+(inc)	+<+>[<-]<[->>+<<<]>>	+[-<+>>>+<<]<[->+<]+>>>[[-]<<<->>>]<<<[->>+<<]>
-(dec)	<+>[<-]<[->>-<<<]>>-	[-<+>>>+<<]<[->+<]+>>>[[-]<<<->>>]<<<[->>-<<]>-
[(while)	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>
](loop)	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>

Application

Let's reuse our previous "decimal printing" algorithm, and replace each instruction by its new implementation, to print a large number (let's say 2056)

Code - 4 cells structure - try it

generate 2056 using 4 cells structure
>>>>>>++++++++>++++++++<
decimal print algorithm rewritten using instruction replacements
>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>>>>>>>>>>>>>>>>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>><<<<<<<<<<<<<<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>->>>>+<+>[<-]<[->>+<<<]>>>>>>>>>>+<+>[<-]<[->>+<<<]>>>>>><+>[<-]<[->>-<<<]>>->[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><<<<<+>[<-]<[->>-<<<]>>->[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>->>>>>>>>+<+>[<-]<[->>+<<<]>><<<<<<<<<<<<<<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>->>>>>>>>>>>>+<+>[<-]<[->>+<<<]>><<<<<<<<<<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<<<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>>>>>+<+>[<-]<[->>+<<<]>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>-<<<<+<+>[<-]<[->>+<<<]>>>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>>>>>>>>>>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>->[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>-<<<<<<<<<<<<<<<<+<+>[<-]<[->>+<<<]>>>>>>>>>>>>>>>>>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<<<<<<<<<<<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>>>>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><<<<+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>+<+>[<-]<[->>+<<<]>>>>>><+>[<-]<[->>-<<<]>>->[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<<+>[<-]<[->>-<<<]>>-.>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]><+>[<-]<[->>-<<<]>>->[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]><<<<>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>

Note: 3 cells version's code is about 50% longer, but it's also 3 times longer to execute...

16-bit values: jumps (3)

Context

Note: read first and second part .
As a reminder, we have 2 different structures, named "4 cells" and "3 cells" to represent 16-bit integers.
Let's now redefine instructions + and - on those 2 structures.

Structure 1 - "4 cells"

A, B, C, D to represent integer N; with

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

Cursor on C

Structure 2 - "3 cells"

A, B, C to represent integer N; with

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

Cursor on A

We can see that these structures mean that we divided N by 256 and stored both quotient and remainder.

While [

What we need to do is to start execution of a piece of code if and only if at least one of {quotient, remainder} is not null.

Using 4 cells structure (reminder: like the 3 cells structure, we can leverage the next cell X, after D...)

• If D is not null, move it to X and increase B
• If C is not null, move it to D and increase B
• Move D back to C and X back to D
• Go to B. If not null, enter while (and reset B, and back to C to keep system consistent)
• Note: if B is null, or after while, we'll have to move back to C as well

Using 3 cells structure (reminder: cell X before A is null as well, as it's the C from previous block, and same applies to Y cell in the next block):

• If B is not null, move it to C and increase X
• If A is not null, move it to B and increase X
• Move B back to A and C back to B
• Go to X. If not null, enter while (and reset X, and back to A to keep system consistent)
• Note: if X is null, or after while, we'll have to move back to A as well

Note: actually, code is the same for both structures.

Loop ]

To loop (note: we are on the remainder, but loop started one cell before). We need to evaluate if both quotient and remainder are null or not as before, store the result at the exact same place than before, and loop if not null. Then

• If not null, the current cell will be reset after looping, thanks to our previous reset at the beginning. And it can't be done before looping. Otherwise, there won't be any loop
• If null, then there is nothing to reset, but let's just go back on remainder

Using 4 cells structure:

• If D is not null, move it to X and increase B
• If C is not null, move it to D and increase B
• Move D back to C and X back to D
• Go to B. If not null, loop (no reset needed, nor back to C, as it's done by while)

Using 3 cells structure:

• If B is not null, move it to C and increase X
• If A is not null, move it to B and increase X
• Move B back to A and C back to B
• Go to X. If not null, enter while (and reset X, and back to A to keep system consistent)
• Note: if X is null, or after while, we'll have to move back to A as well

Note: again, code is the same for both structures.

Operation	"4 cells"	"3 cells"
[(while)	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<[[-]>
](loop)	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>	>[[->+<]<<+>>]<[[->+<]<+>]>[-<+>]>[-<+>]<<<]>

Self-interpreter: inactive and direction flags (8)

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 see how to handle inactive_flag and direction_flag

• Inactive_flag: when not null, execution of instructions should be suspended, only '[' and ']' will taken into account.
• While will increase the inactive_flag and if null update direction_flag.
• Loop will decrease the inactive_flag

Initial state

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

Process

• Set else bit
• If inactive flag is not null
• Reset else bit  
• Check if instruction is ]
• Decrease inactive flag
• If not, check if it is [
• Increase inactive flag
• If inactive flag is null, reset direction flag
• If not, ignore instruction
• If not null: process instruction normally 

Update instruction pointer: instead of  moving to next instruction, we need to check if direction_flag is not null (go back) or not (go forward). An easier way to do that is to go back to steps back if direction flag is not null, and then go one step forward in all cases.

Code snippet for inactive case

parse current instruction
>+<[>->+>
[
  check if instruction is while (increase flag) or loop (decrease flag)
  <<++++++++[-<------->]+<
  [
    --
    [>-<
      clear instruction read
      [-]
    ]>[-
      instruction: loop
      decrease inactive_flag
      >>-<<
    ]<
  ]>[-
    instruction: while
    increase inactive_flag
    >>+
  
    if inactive_flag = 0 then reset direction_flag
    [<-]<[>>[-]<<-<]>+
    <
  ]<
  set instruction read to 1 to consider it as a non instruction
  +>>-
]
<[-<]
+<
[
 and continue

Code snippet for instruction pointer update

increase or decrease instruction counter based on direction_flag
>>>>[-<<+<<<-->>>>>]<<[->>+<<]<<<++>

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: while and loop (7)

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 see how to implement '[' and ']'

Initial state

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

Process

• Common part 
• Access memory value - see previous post
• Copy memory value
• Move array back to initial position
•  While '['
• If copy is null
• increase inactive_flag
• If not: do nothing
• Loop ']'
• If copy is null: do nothing
• If not:
• decrease inactive_flag
• Set direction_flag to 1

Code for while

Access memory cell
>>>>[->+>+<<]>>[-<<+>>]<+[->>>>[>>]+>>[-]>[-<<+>>]<<<[<<]<<
]>>>>[>>]<
copy value
[->>+<<]>>[-<<+<[<<]<<+>>>>[>>]>]<<

move array back to initial position
<[[->>+<<]>[->>+<<]<<<]

check current memory value: do nothing if not null and move to corresponding loop otherwise
<+<[>-<[-]]>[-<
  if null (current position: next to memory_pointer)
  increase inactive_flag
  <<<+>>>
>]<
<<<<<

Code for loop

duplicate memory pointer and move to copy
>>>>[->+>+<<]>>[-<<+>>]<+
[
  -
  go to next memory cell
  >>>>[>>]+>>
  (re)init/copy memory indicator
  [-]>[-<<+>>]<<<[<<]<<
]
go to current memory cell
>>>>[>>]<
copy value
[->>+<<]>>[-<<+<[<<]<<+>>>>[>>]>]<<
move array back to initial position
<[[->>+<<]>[->>+<<]<<<]
check current memory value: do nothing if null and move to corresponding while otherwise
<<
[
  if not null (current position: next to memory_pointer)
  reset value
  [-]
  decrease inactive_flag and change direction_flag
  <<<->[-]+>>
]
<<<<<

Final state

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

Back to previous step

Go to next step