List Commands Library for 50g

[DavidM]

An Illustrative Example

Consider how you might implement the following problem:

Create an RPL program to convert a non-negative integer into a string representing that number in a base ranging from 2 to 36.

In order to stay focused on the general solution, I'm going to skip range checks and any consideration of exact-vs-approximate numbers here. One such implementation of the above, then, might be as follows:

Code:

Program: n2b
\<<
  "" ROT                   @ move result string into position
  DO                       @ main loop
    PICK3                    @ make a copy of given base
    IDIV2                    @ determine quotient, remainder
    DUP 9 > 55 48 IFTE       @ convert remainder to corresponding base character
    + CHR
    ROT + SWAP               @ add new character to front of result
  UNTIL                    @ do main loop until number is fully processed
    DUP NOT
  END
  DROP NIP                 @ drop supplemental stack variables
\>>

I believe this to be a good example of the type of problem that translates fairly well to a list-focused approach. It also happens to utilize functionality which has good representation in the ListExt library. So how might this be done using ListExt features? There's 3 commands in particular that will work nicely here. They are:

I→BL (Integer to Base List): converts an integer into a list of remainders after repeated division by a constant
NL→S (Number List to String): converts a list of character numbers into a string
CHR+ (Character Offset): adds an offset to the CHR value of each character of a string

Using the above commands, the n2b program could be re-written very simply as

Code:

Program: n2bLE
\<<
  I\->BL                   @ convert number and base into a list of remainders
  NL\->S                   @ convert the remainder list into a string
  { 0 9 48 } CHR+          @ replace characters in range 0..9 with 48..57
  { 10 35 55 } CHR+        @ replace characters in range 10..35 with 65..90
\>>

If we run either of the above programs with the following on the stack

Code:

2: 123456789012
1: 36

...the result is the same: "1KPQZG2C".

Looking at the ListExt version more closely, we see the following occur at each step (note that there are no loops in the UserRPL code):

Code:

STEP                       STACK
-------------------------  ----------------------------
(pre-launch)               2: 123456789012
                           1: 36
                                        
I→BL                       1: { 1 20 25 26 35 16 2 12 }

NL→S                       1: "▪▪▪▪#▪▪▪"

{ 0 9 48 } CHR+            1: "1▪▪▪#▪2▪"

{ 10 35 55 } CHR+          1: "1KPQZG2C"

Code Size

The size of the compiled code is a frequent concern of programmers, so let's consider that aspect for the above two programs. The following assumes that both programs were entered with the calculator in Exact mode. Changes to the mode before editing may alter the compiled size of the code objects.

Size
n2b: 78.5 bytes
n2bLE: 73 bytes

The similarity in size may come as a surprise when looking at the actual source code. Despite its relatively smaller footprint in text form, the ListExt version is encumbered by the following when compared to the first program:
- library calls consume 5.5 bytes of storage when compiled, compared with 2.5 bytes for most built-in commands
- the lists consume 16.5 and 24.5 bytes of storage for a combined total of 41 bytes (a little over half of the total byte count in that version)

The lesson here: delineated lists in source code can take up a lot of space, so it's best to encode them as functions of other commands (when possible) if space is a concern. There's several commands in the CREAT submenu that can help with this, mostly for sequences and repetitive sets.


Performance

This is a good example to discuss some performance considerations, as it shows what I consider to be a typical set of characteristics for programs that make use of ListExt functions.

Speed of Execution
n2b: 0.723s
n2bLE: 0.114s

While this shows a decent advantage for the ListExt version, the results in practice can vary depending on many factors. For one thing, someone concerned about performance should never use the IDIV2 command. Replacing that single command with the much longer sequence "DUP2 MOD ROT OVER - ROT / SWAP" will actually speed up the program (0.668s). That may seem counterintuitive, but IDIV2 really is that slow. Additionally, Exact and Approximate mode results will differ. These timings were observed in Exact mode.

Another consideration is that anything that can reduce the quantity and size of loops in the UserRPL code will have a noticeable impact on performance. In this particular example, converting a number to a base that results in only a single character will actually run faster than the ListExt version. In that situation, the main loop code is executed only once. As soon as the result string needs more than one character, though, the ListExt version is faster.

This helps to illustrate a fundamental concept of list processing on RPL calculators: performance gains are more pronounced as the size of the input and output grows. There is an overhead required to deal with lists for all commands (whether built-in or ListExt), and if the data sets are small, this overhead may actually negate any potential performance gain over processing the data without lists. As the data sets grow in size, that overhead is surpassed by the gains made from using faster internal looping structures and optimized code in the list commands.

So if you know in advance that data sets will be small, it may be best to avoid the use of lists. Conversely, knowing that there will be larger data sets makes it highly likely that coding with lists will improve performance (sometimes substantially). Many of the ListExt commands have critical sections implemented in Saturn assembly code, which gives them a sizable speed advantage over similar UserRPL implementations.


Summary

Like any programming paradigm, list processing has its advantages and disadvantages. In situations where it is a good fit, the programmer has the opportunity to focus on simpler steps to achieve the desired goal. Creating and maintaining lists carries with it some overhead which may negatively offset performance when lists are small. These offsets are mitigated, however, as list sizes grow. Depending on the needed functionality and data set sizes, list processing may actually grant significant performance gains.