tl;dr: The simplicity of this 1982 programmable calculator makes it possible to become a "guru" just by reading the manual: Since there are no abstraction layers that can fail you can just write whatever you want without wasting your time with demotivating nonsense like googling error messages or seeking through stackoverflow answers. Just code and it works!

Brainfuck Difference Engine on HP 15C Calculator Hardware Clone

I was just sitting in a park, listening to some podcast and wondered "Hey, why not write a Brainfuck interpreter for my calculator?". So I grabbed my notebook and started scribbling.

Notebook

Brainfuck?

It's a programming language that only has eight instructions. The instructions operate on a tape of numbers.

Instruction	Meaning
>	Move tape head to the right
<	Move tape head to the left
+	Increment value at tape head position
-	Decrement value at tape head position
.	Print value at tape head position
,	Read value from input to tape head position
[	Loop: Jump to after the corresponding ] if the value at the tape head position is 0
]	Loop: Jump to after the corresponding [ if the value at the tape head position is not 0

For example, this program prompts the user for two numbers and then adds them together:

,>,[-<+>]<.

For more details, you can read the Wikipedia article on Brainfuck.

HP 15C

It's a programmable calculator from 1982 that has 20 registers of storage and the ability to do indirect register addressing and indirect jumping to labels based on register content, which comes in really handy when interpreting numbers as instructions. See My previous blog post "Programming like it's 1981" about this thing for more details.

Implementing the Interpreter

An interpreter is a program that looks at data and interprets it as a program i.e. executing the instructions encoded in the data. In the case of the 15C calculator this means that there is an interpreter program written in the calculator's unnamed programming language that reads the numbers that are stored in the registers and behaves as if those numbers were Brainfuck instructions. So the first thing we need is a mapping from instructions to numbers:

Instruction	Number
>	1
<	2
+	3
-	4
.	5
,	6
[	7
]	8

For example, the program "+[.+]", which prints all natural numbers, would be [3, 7, 5, 3, 8].

Instruction Pointer

If we put the instructions into the registers we need to keep track of which instruction to execute next: One register is used as the instruction pointer and contains the number of the register holding the next instruction to be executed; So we fetch the number from that register, execute the instruction, then add 1 to the instruction pointer and repeat.

Tape Pointer

Since Brainfuck uses a tape head that moves across a tape of numbers, we need to store the tape head position in another register. The ">" command moves the tape head to the right, "<" to the left.

However, since we only have 20 registers in total, we should place code and tape on opposite ends of the register space, which means that the first tape cell is the last register, the second tape cell is the second to last register etc. and the ">" command decreases the tape pointer register by 1 to move "right".

Loops

Brainfuck loops can be nested to an arbitrary depth. A fast implementation would probably use some sort of look-up table for matching the loop brackets, but this would take too many registers so instead I opted for just one register that contains a "loop nesting number".

Consider this program:

[+++++[++++++]++++++]++

The first "[" skips the block if the cell at the tape head position is zero. One solution for finding the matching "]" is to set the loop nesting number to 1, then read the program in the right direction and count each "[" as +1 and each "]" as -1. So when encountering the second "[" in the program, the loop nesting number becomes 2, on the next "]" it becomes 1 again and on the final "]" it becomes 0, which means we found the end of the current block and the program can now resume normal execution.

Jumping from the end of a block to the start works similarly: set the loop nesting number to -1 and seek backwards.

Memory Layout

So we need three special purpose registers, followed by Brainfuck code, followed by the tape. We can allocate the registers like this:

Register	Content
0	Instruction pointer
1	Tape pointer
2	Loop nesting number
3	Begin of program code
...	More program code
...	0 (Signals end of program code)
...	More tape
19	Begin of tape

Note that the tape grows backwards from the end of register space. Note that programs can corrupt themselves since there is no bounds checking.

Compacting code

Since 20 registers are not enough to write any interesting programs at one instruction per register, we need a way to put more than one instruction in each register.

The HP 15C uses decimal numbers with a 10 digit mantissa, a 2 digit exponent and a sign, which means we can fit one instruction per digit. Consider this program that calculates fibonacci numbers:

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

At one digit per instruction, this fits into just 3 registers:

3137741313
2282741113
2228111580

(Notice that the last number is padded with a 0 on the right side since the code is stored as big endian)

If we want to keep both the fast "one instruction per register"- and the compact "ten instructions per register"-mode we could use flag 0 to distinguish which mode to use.

Compiling code

The mapping of one instruction per register or digit is simple enough to write code directly on the calculator. However, it would be more convenient if we had a compiler that turns Brainfuck code into numbers.

Here's a ruby script that does exactly that:

instruction_table = {
  ">" => 1,
  "<" => 2,
  "+" => 3,
  "-" => 4,
  "." => 5,
  "," => 6,
  "[" => 7,
  "]" => 8
}

program = ARGV[0]
instructions = program.chars
codes = instructions.map { |i| instruction_table[i] }

# Fast program (for programs up to 15 commands long)
if(codes.size <= 15) then
  registers = codes.map.with_index { |instruction, index|  "#{instruction} STO #{index + 3}" }

  puts 
  puts "Fast"
  puts "===="
  puts "CF 0"
  puts registers
end

# Compact program
chunks = codes.each_slice(10).to_a.map { |a| a.fill(0, a.size...10) }
registers = chunks.map.with_index { |line, index| "#{line.join} STO #{index + 3}"}

puts
puts "Compact"
puts "======="
puts "SF 0"
puts registers
puts

Just save this as bf.rb and start it like ruby bf.rb "+[.+]" to get an output like this:

Fast
====
CF 0
3 STO 3
7 STO 4
5 STO 5
3 STO 6
8 STO 7

Compact
=======
SF 0
3753800000 STO 3

For programs that won't fit in Fast mode, only the Compact version will be shown:

ruby ../utils/bf_compile.rb "+>+[[->+>+<<]<[->>>+<<<]>>>.]"

Compact
=======
SF 0
3137741313 STO 3
2282741113 STO 4
2228111580 STO 5

Charles Babbage's Difference Engine

The Difference Engine was a machine to tabulate polynomials using divided differences. It wasn't programmable, but it ran a program that was parameterizable so you could use it to calculate different functions, e.g. logarithmic tables or sine tables.

Here is a simple implementation in Brainfuck: ,>>,>>,>+[<[-<+<+>>]<[->+<]<[-<+<+>>]<<.>[->+<]>>>>]

You can enter it into the calculator like this:

SF 0
6116116137 STO 3
2742323118 STO 4
2741328274 STO 5
2323118225 STO 6
1741328111 STO 7
1800000000 STO 8

When you run this program, it will ask you for three numbers corresponding to the initial number column setting of the Difference Engine. Examples:

Input	Output
0, 1, 0	Natural numbers (1, 2, 3 ...)
1, 1, 2	Square numbers (1, 4, 9 ...)

So there you have it: A running Difference Engine, implemented in Brainfuck, running on a HP 15C calculator from the eighties :)

Program

Now all you have to do is enter the following code into your calculator. After you entered your program, run B to start the interpreter.

Output will be displayed for one second.
When input is required, the display will flash. Simply enter a number and hit R/S to continue.
When the program terminates it will try to display the last output.

Registers

Register	Content
0	Instruction Pointer
1	Tape Pointer
2	Loop nesting number
3	Begin of program code
...	More program code
...	0 (Signals end of program code)
...	More tape
19	Begin of tape

Flags

Flag 0 is meant to be set/cleared by the user.

Flag	Status	Meaning
0	clear	Fast mode (1 instruction per register)
0	set	Compact mode (10 instructions per register)
1	clear	Seek forward to matching bracket
1	set	Seek backward to matching bracket

Labels

Label	Content
B	Run Brainfuck program
C	Clear tape
E	vRCL digit
0	End program
1-8	Run corresponding Brainfuck instruction
9	Seek to matching bracket
10	Fetch current instruction
11	Execution loop
12	Clear tape loop

Code Listing

; init registers
001 - LBL B
  FIX 0
  GSB C
  10
  ENTER
  3
  F? 0
    *
  STO 0
  1
  9
  STO 1
  0
  STO 2

; run program
012 - LBL 11

  ; fetch instruction
  GSB 10

  ; execute instruction
  STO I
  GSB I

  ; increment instruction pointer
  1
  STO + 0

  ; execute next instruction
  GTO 11

; clear tape
019 - LBL C
  CF 1
  3.019
  STO I
  LBL 12
    RCL (i)
    x = 0 ?
      SF 1
    F? 1
      CLx
    STO (i)
    ISG I
      GTO 12
  RTN

; special "stop program" instruction
037 - LBL 0
  ; display last output for convenience
  R/\
  R/S

; ">" (Move tape head to the right)
044 - LBL 1
  1
  STO - 1
  RTN

; "<" (Move tape head to the left)
048 - LBL 2
  1
  STO + 1
  RTN

; "+" (Increment value at tape head position)
052 - LBL 3
  RCL 1
  STO I
  1
  STO + (i)
  RTN

; "-" (Decrement value at tape head position)
058 - LBL 4
  RCL 1
  STO I
  1
  STO - (i)
  RTN

; "." (Output value at tape head position)
064 - LBL 5
  RCL 1
  STO I
  RCL (i)
  PSE
  RTN

; "," (Input value to tape head position)
070 - LBL 6
  RCL 1
  STO I
  CLx
  SF 9 ; blink
  R/S
  CF 9
  STO (i)
  RTN

; "[" (begin loop)
079 - LBL 7
  RCL 1
  STO I
  RCL (i)
  x != 0 ?
    RTN
  0
  STO 2
  CF 1 ; seek forward
  GTO 9

; "]" (end loop)
089 - LBL 8
  RCL 1
  STO I
  RCL (i)
  x = 0 ?
    RTN
  0
  STO 2
  SF 1

098 - LBL 9 ; seek to matching bracket
    GSB 10
    6
    -
    1
    x = y ?
      STO + 2
    GSB 10
    7
    -
    1  ; needed because GSB 10 modifies the stack
    x = y ?
      STO - 2
    RCL 2
    x = 0 ?
      RTN
    1
    F? 1
      CHS
    STO + 0
    GTO 9

; fetch current instruction
119 - LBL 10
  RCL 0
  F? 0
    GTO E
  STO I
  RCL (i)
  RTN

; vRCL digit
126 - LBL E
  ; find correct register
  1
  0
  /
  STO I

  ; find digit index (reversed)
  FRAC
  1
  0
  *
  LSTx
  x><y
  -
  10^x
  RCL (i)
  x><y
  /
  FRAC
  1
  0
  *
  INT
147 - RTN

Example Programs

Add two numbers

,>,[-<+>]<.

 Fast
====
CF 0
6 STO 3
1 STO 4
6 STO 5
7 STO 6
4 STO 7
2 STO 8
3 STO 9
1 STO 10
8 STO 11
2 STO 12
5 STO 13

Compact
=======
SF 0
6167423182 STO 3
5000000000 STO 4

Multiply two numbers

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

SF 0
6162717413 STO 3
1322817423 STO 4
1822481115 STO 5

Fibonacci Numbers

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

SF 0
3137741313 STO 3
2282741113 STO 4
2228111580 STO 5

Difference Engine

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

SF 0
6116116137 STO 3
2742323118 STO 4
2741328227 STO 5
4232311822 STO 6
5174132811 STO 7
1180000000 STO 8

Learnings

It's insane how simple and productive it is to write something for the calculator: There is absolutely zero nonsense involved, all you need to know is in the manual, you will never have to look something up on stack overflow, there are no nonsensical errors, you won't have to clear the cache of the IDE etc. Surely there must be a middleground between working on a high tower of faulty abstraction layers and writing in this oldschool machine language.

Software development should be a lot simpler, it's insane how much time is spent on irrelevant nonsense.