List Commands Library for 50g

[pier4r]

Nice! Hopefully this weekend I will have some time. After a month of scarcity.

[pier4r]

Today I had a problem to solve and I said "oh noes, I need to find/write the MIN/MAX utilities for list again" (therefore I started project like this: http://www.wiki4hp.com/doku.php?id=rpl:start , to save time for everyone. I wonder why such collections were not done before. I started quite late too out of frustration.)

Then I remembered "wait a second, the glorious listExt has it! LMIN and LMAX". By curiosity I checked hpcalc this time, if it is also there (it is there, thanks David and Eric !), and I updated the 1.1.3b5 to 1.1.3 .

The value of ready made reliable commands, no matter how short!

[DavidM]

Although I was initially skeptical about adding stack manipulation commands to the library, I've considered that it can be rationalized somewhat by recognizing that it's often necessary to construct list contents on the stack during the building and editing process. As such, I've revisited some commands that I worked on in the early stages of the library, but subsequently decided to remove as "non-list-centric" commands.

I've got the following in a "test build" version of the library, and would greatly appreciate feedback concerning their potential inclusion into another release sometime in the future. I should add that these are generally good performers -- NMDUP can create 174 replications of 174 stack items (30276 total items) on a 50g in 0.26 second. Are the below commands worth including in the library? Here's their descriptions:

______________________________________________________________________________

NMDUP (Duplicate a Group of Stack Items Multiple Times)

Input:
N+2: <object 1>
...
3: <object N>
2: N (the size of the group of objects to replicate)
1: M (the number of replications after execution)

Output:
<NxM objects on the stack>

Using the first N objects at the bottom of the stack as the basis, creates a total of M copies of the entire group. Any objects above the identified group when the command is executed are left intact above the replicated output of the command. If M is 0, the identified group is deleted (similar to DROPN). If M is 1, the original group is left in place.

Examples:
1 2 3 4 5 3 0 NMDUP => 1 2
1 2 3 4 5 3 1 NMDUP => 1 2 3 4 5
1 2 3 4 5 3 2 NMDUP => 1 2 3 4 5 3 4 5
5 6 7 8 4 4 NMDUP => 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8


______________________________________________________________________________

NMROT (Rotate a Group of Stack Items)

Input:
N+2: <object 1>
...
3: <object N>
2: N (the size of the group of objects to rotate)
1: M (the number of positions to shift)

Output:
<the same N objects, rotated as indicated>

Rotates the lowest N objects on the stack through M positions. Positive M shifts stack levels up, negative M shifts down. A value of 0 for N makes no changes to object positions. Likewise, a value of 0 for M leaves all stack levels intact. Using 1 or -1 for M is the equivalent of ROLL or ROLLD, which are more efficient in that situation. NMROT is best used when the rotation count is 2 or greater.

The standard UserRPL ROT command is equivalent to 3 1 NMROT.

Examples:
1 2 3 4 5 0 0 NMROT => 1 2 3 4 5
1 2 3 4 5 3 0 NMROT => 1 2 3 4 5
1 2 3 4 5 3 1 NMROT => 1 2 4 5 3 (Note: same as ROT)
1 2 3 4 5 3 -1 NMROT => 1 2 5 3 4 (Note: same as UNROT)
1 2 3 4 5 6 7 8 9 5 2 NMROT => 1 2 3 4 7 8 9 5 6


______________________________________________________________________________

SWPXY (Swap Two Individual Stack Levels)

Input:
<objects on stack>
2: Y (second stack level to swap)
1: X (first stack level to swap)

Output:
<same objects that were previously above SL2, with the indicated levels swapped>

Swaps two arbitrary stack levels as indicated by the stack level numbers given in SL1 and SL2. The X and Y values are the level numbers before adding X and Y to the stack. Both stack levels given as input must have something in them or an error will be generated. If X and Y are equal, no changes to stack items are made.

Examples:
5 4 3 2 1 5 5 SWPXY => 5 4 3 2 1
5 4 3 2 1 1 3 SWPXY => 5 4 1 2 3
5 4 3 2 1 3 4 SWPXY => 5 3 4 2 1
5 4 3 2 1 4 2 SWPXY => 5 2 3 4 1


______________________________________________________________________________

DRPXY (Drop a Range of Stack Levels)

Input:
2: Y (last stack level to drop)
1: X (first stack level to drop)

Output:
<the same stack data with the indicated levels dropped>

Drops the range of stack levels indicated, leaving all others intact. The indicated stack levels are inclusive; they and all levels in between will be dropped upon executing the command. The X and Y values are the level numbers before adding X and Y to the stack.

Examples:

5 4 3 2 1 1 1 DRPXY => 5 4 3 2
5 4 3 2 1 5 5 DRPXY => 4 3 2 1
5 4 3 2 1 1 5 DRPXY => <empty stack>
5 4 3 2 1 4 2 DRPXY => 5 1


______________________________________________________________________________

REVN (Reverse Stack Entries)

Input:
N+1: <object 1>
...
2: <object N>
1: N (the size of the group of objects to reverse)

Output:
<the same objects 1-N as above, reversed>

Reverses the order of the lowest N objects on the stack. N of 0 or 1 has no effect on the stack objects.

Examples:
1 2 3 4 5 0 REVN => 1 2 3 4 5
1 2 3 4 5 1 REVN => 1 2 3 4 5
1 2 3 4 5 4 REVN => 1 5 4 3 2
1 2 3 4 5 5 REVN => 5 4 3 2 1


______________________________________________________________________________

...and finally, there's another one that is list-specific. I've used this during my testing of many of the commands in the library, and thought that it might be useful to others as well.

______________________________________________________________________________

SLST→ (Safe LIST→)

Input:
1: { list of 0 or more objects }

Output:
<list objects, 1 per stack level>
1: count of objects in the list

SLST→ essentially does the same thing as LIST→, with one difference: the exploded list objects are no longer embedded in the original list object in the TEMPOB area of the calculator's memory, and are thus no longer subject to causing extended pauses when the calculator processes a Garbage Collection event. SLST→ is less efficient with memory than LIST→, so it is slightly slower to process. But with large lists, the extra time required to complete SLST→ is minor when compared to the delay caused by any subsequent Garbage Collection event after the list has been exploded.

The Garbage Collection issue can be avoided by saving the list to a global variable first (ie. put it in a saved variable somewhere in HOME), but you don't always want to do that. SLST→ can be useful when you don't want to save/delete a list just to process its contents.

Examples:
12345 1000 NDUPN →LIST LIST→ « MEM » TEVAL => 33.3s on a 50g
12345 1000 NDUPN →LIST SLST→ « MEM » TEVAL => 0.3s on a 50g

Note: the above times are only for the MEM command. MEM always triggers a Garbage Collection event, and that's what I was looking to isolate above. Similar timings just for LIST→ and SLST→ in the above sequences show results of 0.05s and 0.31s, respectively. So while SLST→ is definitely slower than LIST→, the difference is minor when compared to the delay caused by the GC event.

[pier4r]

Cool! How many!

If they don't fit the listext library I would either rename the library, like libUtil or the like (so everything can fit), or create a sister library like stackext.

[John Keith]

Interesting. The first five are reminiscent of Jim Donnely's Programmer's Toolkit for the 48SX. I can see them being in a separate STACK menu in the Library.

While SLST→ sounds very useful, the most common list-related slowdown that I face is with appending items to existing lists. Accumulating items on the stack and then creating a list from them is always faster but often difficult to accomplish. For example, numeric sequences where the next element is a function of two or more previous elements. If there was a way of fixing that problem it would speed up a lot of programs.

John

[DavidM]

(05-22-2018 01:22 PM)John Keith Wrote:  Interesting. The first five are reminiscent of Jim Donnely's Programmer's Toolkit for the 48SX. I can see them being in a separate STACK menu in the Library.

I should take a look at the Programmer's Toolkit; I hadn't realized there were some similarities and thus might be reinventing the wheel here. FWIW, I did create a STACK menu in the test build to contain all but SLST→ (the latter went into the GROUP menu).

(05-22-2018 01:22 PM)John Keith Wrote:  While SLST→ sounds very useful, the most common list-related slowdown that I face is with appending items to existing lists. Accumulating items on the stack and then creating a list from them is always faster but often difficult to accomplish. For example, numeric sequences where the next element is a function of two or more previous elements. If there was a way of fixing that problem it would speed up a lot of programs.

John

It was while I was testing NMDUP that I decided to include SLST→ as a "regular" command. One of my favorite ways to test list commands is to use LSEQ to create large lists of unique elements so that I can quickly see what happens to them. When testing NMDUP, I created large lists with LSEQ and then exploded them with EVAL (1 keypress). This was a fast way to create a large quantity of unique stack objects, but I quickly found that GCs were making things difficult. Using SLST→ instead of EVAL gave me the true picture of what was happening.

Would you be able to elaborate on what you mean by "numeric sequences where the next element is a function of two or more previous elements"? Applying functions to list elements is a central theme to many GoferLists commands, so I've mostly stayed away from that sort of thing with ListExt. What's an example of what you have in mind for this?

[John Keith]

(05-22-2018 02:01 PM)DavidM Wrote:  Would you be able to elaborate on what you mean by "numeric sequences where the next element is a function of two or more previous elements"? Applying functions to list elements is a central theme to many GoferLists commands, so I've mostly stayed away from that sort of thing with ListExt. What's an example of what you have in mind for this?

I think "function" was an ambiguous word here. I was referring to Fibonacci-like sequences with additional levels of abstraction. In these sequences, the next element in the series can be the sum of two or more elements arbitrarily far back in the sequence, not just the last two. The expressions involved are simple one-liners in e.g. the Prime Sequence app but simple RPL programs for them would be very slow once the list size grew to 50 or so. To make a reasonably fast RPL program requires a lot of stack gymnastics that make the program hard to write and impossible to read.

I'm sure the preceding paragraph is clear as mud but I'm not at home now and I don't have my notes with me. Basically it amounts to the well-known problem with RPL that building lists by appending one element at a time is much slower than doing the work on the stack and collecting everything into a list at the end. I'm guessing that if there was a simple fix for this it would have been found by now but hope springs eternal...

John

[DavidM]

(05-22-2018 05:35 PM)John Keith Wrote:  To make a reasonably fast RPL program requires a lot of stack gymnastics that make the program hard to write and impossible to read.

Are there some particular types of stack-based operations that would be helpful for this?

One of the concepts I've toyed with from time to time is creating some "generic" RPL commands to do stack-targeted arithmetic, similar to traditional RPN commands such as ST+Z, ST*Y, etc. In the RPL context, perhaps those commands might look more like ST+3, ST*3, etc. (3=stack level 3). Or possibly the stack level indicator could be an indirect reference. I'm not sure if this would be helpful, but it's something that I've thought about in the past that might apply to this kind of concept.

(05-22-2018 05:35 PM)John Keith Wrote:  Basically it amounts to the well-known problem with RPL that building lists by appending one element at a time is much slower than doing the work on the stack and collecting everything into a list at the end.

Yes, if the data is to be stored in a list, there's no way to avoid a basic truth here: RPL objects are essentially COW (Copy On Write) data structures. There's no way to simply add one element to a list -- the entire list is copied to a new memory location with the change, and a pointer to that new list is pushed onto the stack where appropriate. Furthermore, any attempt to access a specific element in a list requires the command in question to play hopscotch with every preceeding element leading up to it. Those "skips" are relatively fast on the ARM-based RPL machines, but they still take time.

The RPL stack is simply an array of pointers, with each pointer being the address of some RPL object floating around in memory somewhere (usually in TEMPOB, but not always). Pointers are all the same size, so it's easy to access indexed stack levels by knowing where SL1 is and figuring out the offset to the stack level you need (and multiplying a 5-nibble number by 5 is fast and easy in Saturn code). So working with arbitrary stack levels is much faster than having to skip through each list element every time you need to access a specific item. If random access is needed (in the traditional programming sense, not "unpredictable" ), you'll almost always be better off exploding a list onto the stack. Unless the list is very large, in which case the possible GC issues that result from doing that may backfire on you.

Oh, the joys of working with lists!

[John Keith]

(05-22-2018 09:40 PM)DavidM Wrote:  Are there some particular types of stack-based operations that would be helpful for this?

None that come to mind, the solution seems to be different for every problem, but I'll think about it.

Quote:Yes, if the data is to be stored in a list, there's no way to avoid a basic truth here: RPL objects are essentially COW (Copy On Write) data structures. There's no way to simply add one element to a list -- the entire list is copied to a new memory location with the change, and a pointer to that new list is pushed onto the stack where appropriate. Furthermore, any attempt to access a specific element in a list requires the command in question to play hopscotch with every preceeding element leading up to it. Those "skips" are relatively fast on the ARM-based RPL machines, but they still take time.

The RPL stack is simply an array of pointers, with each pointer being the address of some RPL object floating around in memory somewhere (usually in TEMPOB, but not always). Pointers are all the same size, so it's easy to access indexed stack levels by knowing where SL1 is and figuring out the offset to the stack level you need (and multiplying a 5-nibble number by 5 is fast and easy in Saturn code). So working with arbitrary stack levels is much faster than having to skip through each list element every time you need to access a specific item. If random access is needed (in the traditional programming sense, not "unpredictable" ), you'll almost always be better off exploding a list onto the stack. Unless the list is very large, in which case the possible GC issues that result from doing that may backfire on you.

Oh, the joys of working with lists!

That's pretty much what I feared. As I understand, this is true to some degree for all LISP-derived languages.

[pier4r]

David, any news?

[DavidM]

I've added several new commands and made some minor performance improvements. All but one of the new commands are in a new category: stack manipulation. While not directly list-related, these new commands can still be a useful part of preparing data from (or to be added to) a list.

Here's a brief description of what's been added:

Stack Operations (STACK menu)
NMDUP - replicates a group of stack levels as indicated
NMROT - rotates stack items as indicated
SWPXY - swaps the indicated stack levels
DRPXY - drops the stack levels indicated in the range from X to Y
REVN - reverses the order of N stack levels

Element Grouping (GROUP menu)
SLST→ - LIST→ that avoids Garbage Collection issues for large lists

If anyone would be willing to try out the new commands, please send me a PM with an email address and I'll send you a preliminary "test" version of the library. It comes with a special testing function that exercises every command with a variety of different system configurations.

I've also been creating UserRPL versions of all the library commands in preparation for doing some performance comparisons. This is taking some time. To simplify the code, I've opted to ignore some of the edge cases for certain functions. My interest is more in comparing the general performance than in handling every possible edge case that the library code anticipates. I'm only about halfway through the command list so far, so there's still lots of work to do in this area.

[pier4r]

Any news? (this thread has finally more views than the other one http://www.hpmuseum.org/forum/thread-8209.html (list challenges) )

[DavidM]

(07-20-2018 08:58 PM)pier4r Wrote:  Any news? (this thread has finally more views than the other one http://www.hpmuseum.org/forum/thread-8209.html (list challenges) )

I've had a couple of detours, but some good progress has been made. I've managed to make some refinements to a couple of the stack commands as well as incorporating some enhancements to the operations of a few others. I also added a list-normalization command to address the issue identified in this thread.

Everything has tested well so far, and all of the new commands appear to be stable. The benefit of the stack commands is noticeable when there's a lot of stack items to be created/moved/dropped, but these commands may actually be slower than using built-ins in cases where there's not much data to be changed. Something like "NIP NIP" will always be faster than "2 3 DRPXY", for a variety of reasons. While I can include hints in the documentation about these kinds of considerations, I'm on the fence about whether the optimal use case would come up enough to warrant including them.

The offer still stands for anyone who'd like to get a sneak peek at the new features: send me a PM with an email address and I'll send you the latest build that includes an automated comprehensive test suite.

[pier4r]

(07-20-2018 11:36 PM)DavidM Wrote:  I've had a couple of detours, but some good progress has been made. I've managed to make some refinements to a couple of the stack commands as well as incorporating some enhancements to the operations of a few others. I also added a list-normalization command to address the issue identified in this thread.

I missed that one, nice exchange between you and Claudio. I understand what Claudio means but actually there is a lot of (niche) interest in the uRPL world still, plus if something is fun then that's it. As how my memory (that failed, see below n1) remembers Valentin saying in one of his recent posts "people spend a lot of time to produce libraries that may be used by 10 other people or less" (wrong, see n1) and I replied like "yes but if it is a fun/learning process, so be it". Also it depends how heavily those 10 people will use the library.

n1: what Valentin said was different. This was pointed out in subsequent messages in this thread. Lesson learned (again): my memory/understanding is not that accurate at times.

Quote:That's the decades-long problem I've always resented: people will constantly produce this or that library, or this or that utilities ROM, or this or that utilities LEX files and so on and so forth, which are then published and/or made available for free or nearly so, intended to be used in people's own programs and such. So far so good.

Regrettably, most people either don't use them in actual, non-trivial programs or, if they do, they don't make them publicly available so in the end the community rarely gets full-fledged, useful programs but tons upon tons of routines, libraries, utilities, etc., apparently because people love to write libraries and utilities (it's like solving a puzzle or a challenge) but complex, useful programs not so much.

http://www.hpmuseum.org/forum/thread-109...l#pid99989

[DavidM]

(07-21-2018 11:13 AM)pier4r Wrote:  ... there is a lot of (niche) interest in the uRPL world still, plus if something is fun then that's it.

"a lot" may be an over-statement. When you consider all the niches here*, I'd be surprised if there were more than 3-4 regular users of the ListExt library. I think the viewings of this thread are more from curious onlookers than anything else, something akin to the way traffic backs up near the site of a car accident.

I'd have worked on this even if I was the only user of the library. The end result would not have been anywhere near as versatile and useful, though, were it not for the suggestions and discussion of the participants in this thread. I continue to learn much from seeing what other people do/need/want and how they approach problems to be solved. Example: John Keith recently noted that the output of repeated calls to LSHUF with a common input argument generated the expected percentage of single cycles in the results. That's not only a nice anecdote to support the efficacy of LSHUF, but it also caused me to start looking into yet another branch of math that I've had no reason to dive into before now.

Yet another example of "the journey is the reward."





* Niches:

• People who like to use calculators
  • People who like to use HP calculators
    • People who use RPL calculators
      • People who use 49G-50g calculators
        • People who program their calculators
          • People who make use of lists in their programs
            • People who don't mind using 3rd-party software on their calculators
              • People who know about the HP Museum or follow hpcalc.org submissions
                

[pier4r]

(07-21-2018 06:36 PM)DavidM Wrote:  Yet another example of "the journey is the reward."

Exactly. Where did John K. noted that part about LSHUF? I skipped it.

Quote:* Niches:

• People who like to use calculators
  • People who like to use HP calculators
    • People who use RPL calculators
      • People who use 49G-50g calculators
        • People who program their calculators
          • People who make use of lists in their programs
            • People who don't mind using 3rd-party software on their calculators
              • People who know about the HP Museum or follow hpcalc.org submissions
                

I can easily mention that listExt involved more machine operations that inhabitants on the planet, therefore your argument is clearly moot! Ha!

No really, it is since May 25 that two of my 50g are simulating little tournaments (of course producing intermediate results but I have to wait more and more as the iterations scale).

I have to buy 2 more usb mini B so I can use the two remaining 50g, but I need to convert a 50g back to uRPL as one has newRPL on it. I have a bit of a dilemma between using a user friendly but relatively slow environment of user RPL or the not-as-complete-or-stable-but-surely-faster newRPL. For relatively(n1) fast results uRPL is ok, after that part of my brain pushes for other solutions.

n1: a result within a week is fast enough in this period.

[DavidM]

(07-21-2018 08:14 PM)pier4r Wrote:  Where did John K. noted that part about LSHUF? I skipped it.

It was in a private exchange of communications as we were both exploring ideas, most of which would qualify as learning exercises as opposed to meaningful problem solving. The cycle output ratio wasn't the goal of the experiment, but it was nice to see it fall in line with expectations.

It grew out of an idea John had about an alternative form of the Fisher-Yates shuffle known as Sattolo's algorithm, which intentionally creates a biased permutation with certain specific qualities. I'm quite ignorant of potential uses for the algorithm, though it did seem to work as described when we both played around with it.

[rprosperi]

(07-21-2018 06:36 PM)DavidM Wrote:  When you consider all the niches here*, I'd be surprised if there were more than 3-4 regular users of the ListExt library. I think the viewings of this thread are more from curious onlookers than anything else, something akin to the way traffic backs up near the site of a car accident.

David - Although I can't foresee any real requirement for me to ever need to install this library, I have followed it's birth and growth closely as it has evolved, as the discussions about implementation choices, test cases used and proposed by readers and even your own reassessing and changing things is very educational for even basic RPL programmers, like me.

Also, the ensuing discussions about using lists for various things has led to additional interest in exploring some of those areas as well.

So you can't really judge such a tool's contribution solely by the number of users that have installed it, it has other positive influences just from being discussed.

Which is to say thank you, not only for creating and sharing this library, but also for doing it in an open and collaborative manner; doing so continues to be interesting and helpful to me, and surely many other folks too.

[Valentin Albillo]

.
Hi, Pier:

(07-21-2018 11:13 AM)pier4r Wrote:  As Valentin said in one of his recent posts "people spend a lot of time to produce libraries that may be used by 10 other people or less" ... Also it depends how heavily those 10 people will use the library.

I never said that. Else please post a link to the exact post of mine where I explicitly said the above text which you are quoting (between quotation marks) as said by me.

If you can't, please remove that fake quotation from your post.

Among educated people, it's customary and to be expected that if you are quoting (not paraphrasing or whatever) what someone said, including the text between quotation marks, then you must include that text verbatim, i.e.: exactly what the quoted person said, not your very own personal interpretation of what you think the person said.

This is not the first time this happens to one of my posts lately but I sure expect it will be the last on your part.

V.
.

[Thomas Klemm]

Here's another quote by Valentin:

Quote:Man soll die Dinge nicht so tragisch nehmen, wie sie sind.