Programming Like It's 1981

tl;dr: calculator code, registers, goto.

You know how you should learn a new programming language every year? I decided to cheat and learn one that is tedious to use but very quick to learn: HP 11C calculator code! This language feels like interpreted assembly language so get ready for something unusual.

If you want to play along you should get a free emulator app and maybe read the basic intro in the original manual (PDF).

RPN Calculators, How Do They Work?

If you want to calculate 1 + 2 you type it as 1 ENTER 2 +. The calculator has a stack with room for 4 numbers, so after typing 1 ENTER 2 both 1 and 2 will be on the stack; when you then type + it will take the two numbers from the stack and put back 3.

This is useful because you won't need parenthesis any more, e.g. 2 * (3 + 4) is just 2 ENTER 3 ENTER 4 + * which also simplifies programming.

Coming Up With A Readable Notation

Calculator code is awful to read so the first step is to come up with a useful notation (the original manual uses button presses, which just doesn't cut it for me). Let's say we want to write a program that calculates the logarithm of a number for a given base, e.g. log_2(8). The tricky part is that the calculator does not have a log_x(y) key so you have to build one yourself out of the log(x) key (base 10 logarithm):

log_2(8) = log_10(8) / log_10(2) = 3

Converted to calculator code it looks like this:

001-42.21.13
002-34
003-43.13
004-34
005-43.13
006-10
007-43.32

Charming, isn't it? It looks like this because the calculator only has a 7-segment display i.e. it cannot display letters. Luckily, the manufacturer came of with the neat idea of having the numbers refer to button coordinates on the key pad so the first 42 means "fourth row, second column", which happens to be the f-shift key. If we replace every number by the key located at the position by said number and remove the line numbers it suddenly starts to make a bit more sense:

f LBL C
x><y
g LOG
x><y
g LOG
/
g RTN

The shift keys are needed because things like LOG or RTN don't have their own keys, they are secondary or ternary functions of other keys. When writing down code they are just noise so we can skip them as well:

LBL C
x><y
LOG
x><y
LOG
/
RTN

So what's up with all these abbreviations? Everything is abbreviated to fit on the tiny calculator keys. Luckily, we don't have that limitation so we can spell them fully and even add indentation after the label in the LBL C command:

C:
  x><y
  log
  x><y
  log
  /
  return

Much better!

Notice that all functions only operate on the number on top of the stack so we need the x><y command to switch the two numbers on the top (top number is called x, second one is y). Let's comment the code:

; calculates log_x(y) as log_10(y) / log_10(x)
C:
  x><y        ; swap previous number to the top
  log         ; replace it with its base 10 logarithm
  x><y        ; swap it back
  log         ; replace the second number with base 10 log
  /           ; divide them (replace both with the result)
  return      ; stop program

Registers

The calculator lacks a modulo function (remainder of division), so let's implement one. One possible algorithm looks like this:

y mod x = y - round_down(y / x) * x

For example the remainder of 5 mod 2 would be 5 - round_down(2.5) * 2 or 5 - 2 * 2 or 5 - 4 which is 1.

The problem is that we are using the same values in multiple places in the calculation, which won't work because y / x destroys both x and y and replaces it with the result of the division. To work around this problem we have to use registers (think variables):

; y `mod` x
D:
  store 0
  x >< y
  store 1
  x >< y
  /
  int         ; round towards zero
  recall 0
  *
  recall 1
  x >< y
  -
  return

The calculator has 20 regular registers which are numbered from 0 to 19. The code above uses registers 0 and 1 to first store the two numbers before destroying them with / to recall them later.

Also note that the label at the top is different. There is only one program memory, but by using different labels we can jump to different positions in program memory to effectively have multiple small programs simultaneously (just remember to end them with return, otherwise program execution will fall through the next label and continue in the next program).

Loops, Goto and Subroutines

Let's write a program to convert decimal numbers to binary. Since the calculator will always display numbers in decimal format, we'll cheat by converting to numbers that look binary when written as decimal, e.g. we'll convert 5 to what looks like 101 but is actually one hundred one.

When converting to binary, calculating modulo 2 comes in handy. Luckily we already implemented that so we can now call it as a subroutine by first putting 2 on the stack and then doing gosub D. Note that the meaning of return changes when encountered after a gosub: Instead of stopping the program it will jump back to after the gosub command.

The call stack is only 4 deep so recursion is out of the question. Instead of using gosub you can also use goto to construct loops.

Let's have a look at the binary converter:

; toBinary(x)
B:
  0                ; put 0 on the stack as the result "variable"
  store 3          ; initialize exponent to 0
  x >< y

  0:               ; begin while loop
    if(x == 0)     ; while(x != 0)
      goto 1
    store 2
    2
    gosub D        ; (`mod` 2)
    recall 3
    10^x
    *
    +
    1
    store + 3
    pop
    recall 2

    2              ;
    /              ; right shift
    int            ;

    goto 0         ; end while loop

  1:
  pop
  return

Conditionals like if(x == 0) all follow the same pattern: It skips the next command if the condition is false. The rest is just some math to construct a decimal number that looks binary and add it to the result (store + 3 is a trick that only works with registers 0 to 9: It adds what is on the stack to the register instead of replacing it). pop rotates the stack by one position i.e. it removes the top value and appends it at the other end of the stack.

It's Too Slow!

This algorithm is technically fast because it runs in O(log_2(n)), but it is practically slow because the calculator itself is so very slow. We can however speed it up by a constant factor by converting 4 bits at once using a lookup table. To do this, we need the special index register.

The Index Register

This special register has two functions:

• indirect register addressing
• iterating (like a for loop)

Indirect Addressing

Indirect addressing is done with I and (i), e.g. STO I stores in register I but STO (i) stores in the regular register with the number that is in the integer part of I. My first intuition was to write this as pointer dereferencing like store *i, but pointers are error prone and difficult so let's change our mental model of how registers work to come up with something simpler.

Imagine the index register as variable i and imagine the regular registers as an array called register. We can now think of indirect addressing as a simple array lookup.

buttons	notation
RCL I	i
STO I	i=
RCL 4	register[4]
STO (i)	register[i]=

Here is an example program that indirectly stores 5 in register 3:

; button notation
3
STO I
5
STO (i)

or

; custom notation
3
i=
5
register[i]=

Iterating

The index register can store any number, but there are two commands, ISG and DSE that interpret the fractional part of it in a special way: The first three digits are a loop limit number and the next two are a step size. If we set the index register to 0.01501 it means that we want to increment from 0 to 015 with a step size of 01. To save memory, this can be written as .015, because a step size of 0 will be interpreted as 1 (When writing numbers in programming mode, each digit counts as one line of program memory).

The commands ISG and DSE stand for "Increment, skip greater" and "Decrement, skip equal". They first change the integer part of the index register by the step amount, then compare the integer part to the loop limit and then they skip or don't skip the next line.

With indirect addressing and iterating we can now write a program that initializes registers 0 to 15 with a lookup table:

; create lookup table
A:
  .015
  i=
  5:               ; for(i = 0, i <= 15, i++)
    i
    int
    gosub B        ; toBinary((int) i)
    register[i]=
    incrementSkipGreater
      goto 5
  return

Using this lookup table, we can rewrite the toBinary program to convert 4 bits at once (Notice that we also have to change which registers we used everywhere, because 0-15 are now occupied. This also means that we can no longer use += to store in a register because that only works for registers 0 to 9):

; toBinary with lookup table
B:
  0
  register[16]=
  x >< y

  0:                ; begin loop
    if(x == 0)
      goto 3
    register[17]=   ; store input

    ; fetch 4 bits from input
    16
    gosub D         ; (`mod` 16)

    ; lookup binary
    i=
    pop
    register[i]

    ; shift result bits to the left and add to result
    register[16]
    10^x
    *
    +

    ; increment left shift amount for next iteration
    4
    register[16]
    +
    register[16]=
    pop

    ; input `shr` 4
    register[17]
    16
    /
    int

    goto 0 ; end loop

  pop
  return

But wait! How is this supposed to work if the table generating program uses the toBinary program and the toBinary program uses the table? We need to keep both versions of the algorithm to create the table with the slow one and then use the fast one, but we don't have the memory to keep both versions around.

If you look closely you'll notice that those two implementations only differ in the algorithm that is used to pull out bits from the input number. If we were using a high level language we would pass the algorithm we want to use as a second parameter (Think algebraic data type of functions or enum with instance methods):

toBinary(42, Algorithm.FAST)

What we would NOT do is add a boolean parameter and use an if statement to pick the algorithm. Yet that is exactly what we will have to do on the calculator.

Flags

The calculator has two flags, 0 and 1, which can be set, cleared and checked with the SF, CF and F? commands. I like to think of them as booleans so my notation for them looks like this:

button	notation
SF 0	flag0 = true
CF 1	flag1 = false
F? 0	if(flag0)

We can now use flag0 to choose the algorithm. We will use the fast algorithm only if the flag is set:

; toBinary with different algorithms
B:
  ...
  0:         ; begin loop
    ...
    if(flag0)
      goto 1       ; fast algorithm
    ;else
      goto 2       ; slow algorithm

    ; fast (fetch 4 bits using the lookup table)
    1:
      ...
      goto 0 ; end loop

    ; slow (fetch 1 bit)
    2:
      ...
      goto 0 ; also end loop
  ...

The user can now choose the algorithm by changing the flag. However, to improve the user experience even more we should add flag handling to the table generator itself:

; create lookup table
A:
  flag0 = false    ; use slow algorithm
  .015
  i=
  5:         ; for(i = 0, i <= 15, i++)
    i
    int
    gosub B        ; to binary
    register[i] =
    incrementSkipGreater
      goto 5
  flag0 = true     ; use fast from now on
  return

Generating the table takes about 3 minutes, but it only has to be done once.

Now everything is fast, but we ran out of memory because we use 50% than we have. Let's fix that.

Memory reallocation

Initially, the calculator has 63 lines for programs and 20 regular registers. Programs and registers share the same memory so when you enter the 64th line, the last register will be converted to 7 more program lines, which means that you can have up to 203 lines for programs. Since we are using all 20 registers and 82 lines of code we have to optimize 19 lines away, or 3 registers, or a combination of both.

We can do this by replacing the modulo calculation with a faster and shorter one that only uses one register, adding 4 lines of code to make converting 0 a special case so we no longer need to use register 0 as a lookup, which frees up 7 lines, giving us a net gain of 3 and some other optimizations here and there.

One interesting optimization is that by creating the lookup table backwards we can initialize the index register with 15 instead of .015, which saves 2 lines because .015 is 4 lines while 15 is only 2.

Final program

Custom notation:

; create lookup table
A:
  flag0 = false    ; slow algorithm
  15
  i=
  0:               ; for(i = 15, i > 0, i--)
    i
    gosub B        ; to binary
    register[i]=
    decrementSkipEqual
      goto 0
  flag0 = true
  return


; toBinary with lookup table
B:
  0                ; the result
  register[0]=     ; exponent
  x >< y

  1:               ; begin loop
    if(x == 0)
      goto 4
    register[16]=  ; store input

    if(flag0)
      goto 2       ; fast algorithm
    ;else
      ; slow algorithm
      2
      gosub D      ; (`mod` 2)
      register[0]
      10^x
      *
      +
      1
      register[0] +=
      pop
      register[16]

      2
      /
      int
      goto 1

    ; fast (fetch 4 bits using the lookup table)
    2:

      ; fetch 4 bits from input
      16
      gosub D      ; (`mod` 16)

      if(x == 0)
        goto 3
      ;else
        ; lookup binary
        i=
        pop
        register[i]
      3:

      ; shift result bits to the left and add to result
      register[0]
      10^x
      *
      +

      ; increment left shift amount for next iteration
      4
      register[0] +=
      pop

      ; input `shr` 4
      register[16]
      16
      /
      int

    goto 1 ; end loop

  4:
  pop
  return


; fast modulo
D:
  register[17]=
  /
  fractional
  register[17]
  *
  return

Here is the same thing in button notation which might be easier to enter on a real calculator because you won't have to "compile" each line in your head:

LBL A
CF 0
1
5
STO I
LBL 0
RCL I
GSB B
STO (i)
DSE
GTO 0
SF 0
RTN

LBL B
0
STO 0
x><y
LBL 1
x=0
GTO 4
STO . 6
F? 0
GTO 2
2
GSB D
RCL 0
10^x
*
+
1
STO + 0
R\/
RCL . 6
2
/
int
GTO 1
LBL 2
1
6
GSB D
x=0
GTO 3
STO I
R\/
RCL (i)
LBL 3
RCL 0
10^x
*
+
4
STO + 0
R\/
RCL . 6
1
6
/
int
GTO 1
LBL 4
R\/
RTN

LBL D
STO . 7
/
FRAC
RCL 17
*
RTN

Lessons Learned

Regarding Programming

Given how low level this programming language is I doubt that the language itself taught me anything new. If you want to improve yourself by learning a programming language you should probably pick one that is on a higher level than the ones you are used to, e.g. Idris, not a lower one.

The take-away is really the custom notation: I found the button notation cumbersome so I translated it into a more familiar syntax, which I had to refine along the way to accommodate concepts as I encountered them. Identifying commonalities between programming languages also reduces cognitive load and makes it easier to come to grips with new ideas because most "new" ideas are mostly recombinations of old ideas.

Regarding Mobile Programming

What surprised me was how natural programming on the calculators feels after you get used to it: Programming is just like performing regular calculations. You mostly use the same buttons you use all the time, just add some conditionals and goto and you are set. Instead of doing something silly like emulating a keyboard to spell commands you just use the dedicated GTO button. It really feels native to the platform.

Now, have you ever tried programming on a smartphone? Regular programming languages like Ruby or Clojure make you type in code with the keyboard, which doesn't feel native to the platform at all. Automation apps like IFTTT or Tasker get you a long way but I have yet to find a "real" programming environment that is also taylored to mobile.

Conclusion

Learning this low level language did not improve my programming skills significantly but it was great fun and gave me something to blog about :)