List Commands Library for 50g

[3298]

Don't mind me, I'm just dropping some semi-relevant SysRPL code including a wall of text, just as I usually do.

Using some SysRPL tools there is another trick to accelerate list processing. In a nutshell, it's an alternative to exploding a list, then operating on the elements, and reassembling the list. The basic operation is:
- push the list to the return stack using >R
- try to pop one element off the list onto the normal data stack using ticR
- if successful (returned element and TRUE), perform your operation and repeat from the previous step.
- if not successful (returned FALSE), just continue. The end of the list has been reached, and ticR already dropped the empty remnant of the list from the return stack.
- reassemble the list in some way, if you want.

It's not suitable for all list operations, but many go well with it. Mapping and filtering is straightforward (just remember to wrap the results of the mapping operations into a list afterwards), folding is easy by either popping one additional element off the list before entering the loop, or using a neutral element to start with (0 for addition, 1 for multiplication, ...). If you don't know what folding means, it's basically (((elem1 `op` elem2) `op` elem3) `op` elem4) ... for any user-defined `op`; if you use * as `op` the result will be a product of all elements; MAX as `op` returns the greatest element, etc.

The benefit of this approach is that depending on the operation there may be only a few elements of the list on the stack at any time, so when the garbage collection kicks in, it won't waste much time trying to find out that the elements are part of that huge list. Folding keeps the stack very clean; most mapping operations create new elements which are not pointers into the list; filtering is the black sheep in that it still accumulates a lot of unmodified elements from the original list on the stack, though I believe this is still a small speed improvement over keeping the entire exploded list on the stack and rolling it until the entire list is processed. The store-to-global-var trick mentioned by Joe can be combined with this to reap the benefits of both.

I can't take credit for this trick, I found it ... somewhere a long time ago. Probably in ROM, because ticR is just made for this, and it's a command from ROM. Perhaps I was reading POSCOMP, which is one of the routines using it. (Nosy is a wonderful tool, it's so easy to quickly browse the ROM for anything!) Maybe some of the experienced SysRPL programmers already knew this trick because they did the same.

The only difficult part in using this is constructing the loop, because SysRPL's indefinite loops use one item on the return stack as well, so the programmer must keep track of what's where on the return stack. In ROM there is an easy workaround involving GOTO which doesn't care about the return stack, but that only works with fixed addresses, so we can't use it (a relative GOTO is possible, but it has to be supplied by the programmer). This loop should work:

Code:

::
  >R
  BEGIN
    RSWAP ticR
  WHILE
    ::
      RSWAP
      ... your operation ...
    ;
  REPEAT
;

This is the bare minimum for mapping purposes - you'll need to add code to wrap the results into a list, and for that you'll also need to keep track of the list size.
An alternative approach to looping would be to use recursive calls and COLA (to keep the recursion from leaving stuff on the return stack), but that's slower because recursion needs some kind of variable or ROMPTR lookup. Even NULLLAMs have a hard time beating the easy pointer storage on the return stack, as employed by the existing indefinite loop commands.

The upside of the >R and ticR loop compared to UserRPL's MAP is that you can access and modify all elements of the stack (except for the original list, but that's fixable by DUPing it beforehand) as you please; including the ones left behind by previous iterations of the loop, which is why folding is so easy. Filtering is enabled by mapping an element to itself or to nothing - MAP will fill in NOVAL if you try that, but this loop allows you to truly remove elements. (Similarly, when returning multiple results from an operation, MAP will wrap them into a list to place at the mapped element's spot, the ticR loop allows growing the list.)
The downside is that you need to dive into SysRPL, obviously.