List Commands Library for 50g

[3298]

(09-06-2017 02:22 PM)DavidM Wrote:  I'm actually using a variant of that technique quite a bit in the library -- instead of ticR (which returns the boolean), I've been using 'R (which only returns the object). I actually learned the technique when tracing through one of the built-in routines (probably DOLIST), and it is indeed a nice way to handle things in certain cases.

Told ya, there's always someone who knows the trick already. I used ticR because it tells the surrounding code when the list ends, but 'R is fine if you do that another way. DO ... LOOP doesn't use the return stack, so combining these may be a simple way to avoid that RSWAP hassle while keeping the benefits.

(09-06-2017 02:22 PM)DavidM Wrote:  For small lists, it's actually slightly slower than "explode/ROLL/ROLLD", but the difference isn't great enough to make up for the benefits it provides. In particular, it's very nice as a means to almost have a "spare stack" to draw objects from that doesn't cause you to have to juggle others. And as list sizes grow, its measurably faster than the ROLL/ROLLD sequence.

Yes, that's what I expected. I didn't throw the profiler at it, but ROLL/ROLLD needs to move a block of memory (part of the stack) which scales linearly with the list size, ticR and 'R are done in constant time (ignoring the possible garbage collection, because if that kicks in, it would have done the same in the explosion step). The "spare stack" argument applies to a major case I used ticR in too; it involved iterating over a list of variables and doing some complex operations on their contents with no return value (searching a project for INCLUDE directives, as part of my CRLIB replacement; the "return values" of the routine were appended to LAMs). Having to deal with changing offsets to the values I stored on the stack wouldn't have been pleasant, so having the option to stash the list somewhere else without slowing down the iteration process (like a CARCOMP/CDRCOMP combo would, which would also be a major memory hog) was a gift from heaven.

(09-06-2017 02:22 PM)DavidM Wrote:  Please continue to chime in with these suggestions! Although I already knew of this one (or its cousin), there's tons that I don't. I occasionally see things like this when tracing code with Nosy, and it can take a bit to figure out what it's for. This one caused me some head scratching until I actually copied some of the code and stepped through it to understand it better.

Will do whenever I find something useful. For now, I'll tell you some more details about my ticR use:
I guess you read the text file that comes with Nosy? It contains some programming tricks in its last section. In this context one of them could be interesting, filed under "Advanced looping". It consists of an optimized replacement for the indefinite loop structure, and I've combined that with ticR to write my own fast iteration program. In the process I found a workaround for the problem created by the presence of COLA_EVAL (namely evaluating the top of the stack). This is the code - as usual, if it works for you, don't hesitate to use and/or modify it, I'm sharing it for the greater good.

Code:

::
  >R IDUP RSWAP ticR
  NOTcase COLASKIP RSWAP
  3@REVAL AGAIN
;

It may not be immediately obvious, but it takes the list from the stack and the operation from the runstream, so assuming it's named iterate, this will calculate 0+10+11+12:

Code:

BINT0 { BINT10 BINT11 BINT12 } iterate #+

Taking the operation from the runstream makes it necessary to skip it afterwards, so I was able to replace COLA_EVAL by COLASKIP, avoiding the evaluation problem.
This might be just a little bit faster than other loops doing the same. Stupid me made this speed advantage mostly irrelevant by using a ROMPTR as the operation, though. In hindsight, I should have done this:

Code:

' iterate ' my_romptr ROMPTR@ DROP TWO ::NEVAL

instead of

Code:

iterate my_romptr

because using the ROMPTR directly as operation recalls its contents on every iteration.

(09-06-2017 02:44 PM)DavidM Wrote:  

(09-06-2017 01:52 PM)3298 Wrote:  The downside is that you need to dive into SysRPL, obviously.

Why is that a downside? That's been my preferred environment for 48-50 coding for some time now. The ListExt library is entirely a SysRPL project, except for 20 or so Saturn routines strategically placed to enhance performance.

Not a downside for us, of course. Just for those poor fellas who read this thread without having prior SysRPL experience.

[David Hayden]

(08-11-2017 02:15 PM)DavidM Wrote:  the conversion of vectors/matrices to lists is simple enough, and best handled at the user's discretion.

I suggest a S->CHRL command to convert a string to a list of its individual characters. E.g. { "ABC" } -> { "A" "B" "C" } A similar command could concatenate the values back into a single string. This would let you break a string into a list, operate on the characters, and put them back together. It would make things like converting to upper case, lower case, or adding/subtracting one easy to do in User RPL and could thus replace the new commands that do these.

[brickviking]

(09-06-2017 04:55 PM)3298 Wrote:  

(09-06-2017 02:44 PM)DavidM Wrote:  Why is that a downside? That's been my preferred environment for 48-50 coding for some time now. The ListExt library is entirely a SysRPL project, except for 20 or so Saturn routines strategically placed to enhance performance.

Not a downside for us, of course. Just for those poor fellas who read this thread without having prior SysRPL experience.

Like me! I don't think I've ever coded anything in SysRPL yet. I'm having enough trouble getting my head around UserRPL.

(Post 74)

[DavidM]

(09-06-2017 09:48 PM)brickviking Wrote:  Like me! I don't think I've ever coded anything in SysRPL yet. I'm having enough trouble getting my head around UserRPL.

Give it some time. RPL takes some getting used to, even if you're already familiar with RPN and stack-based programming. And one thing you'll find if you start browsing through code around here: there's probably 4 or 5 ways to do just about anything with RPL (User or Sys), and there's enough experienced users around here that someone will know a faster/simpler/more clever way to do just about anything you can come up with. Keep an open mind to this type of thing, and you'll learn more things than you could ever possibly remember.

[DavidM]

(09-06-2017 09:14 PM)David Hayden Wrote:  I suggest a S->CHRL command to convert a string to a list of its individual characters. E.g. { "ABC" } -> { "A" "B" "C" } A similar command could concatenate the values back into a single string. This would let you break a string into a list, operate on the characters, and put them back together. It would make things like converting to upper case, lower case, or adding/subtracting one easy to do in User RPL and could thus replace the new commands that do these.

Actually, I think that's a brilliant idea David! I guess I just had different names for the commands in mind . S→SL and SL→S have been in the library for a while now, and were the inspiration for some of the newer add-ons that occurred. I've actually had those 2 on a mental list more recently for possible recoding -- a performance boost wouldn't hurt them.

UCASE and LCASE were "convenient afterthoughts" after CHR+ was added, and CHR+ was born as a pseudo-S→SL (combined with some other commands and SL→S) that uses a Saturn routine to process its target more quickly than the others would complete it as a combined sequence.

Most of the previous comments I'd been receiving were encouraging the inclusion of "special case" commands such as these. Do you feel that their presence (and the space they take) is more of a liability?

[John Keith]

(09-07-2017 05:53 AM)DavidM Wrote:  Most of the previous comments I'd been receiving were encouraging the inclusion of "special case" commands such as these. Do you feel that their presence (and the space they take) is more of a liability?

In general, I prefer a small set of flexible, general-purpose commands that can be combined as the user sees fit. However, with interpreted languages like RPL, every command executed takes a significant amount of time. Therefore, I think in the case of User RPL, it is desirable to have a larger set of commands and functions than would be appropriate for a compiled language system.

This could obviously be taken to an absurd level where the user commands take huge amounts of memory and the menu system becomes excessively large and cumbersome. Where to draw the line is a matter for endless discussion... :-)

John

[DavidM]

(09-06-2017 04:55 PM)3298 Wrote:  DO ... LOOP doesn't use the return stack, so combining these may be a simple way to avoid that RSWAP hassle while keeping the benefits.

I'd love to avoid the RSWAPs if I could, but I thought they were still needed inside the DO...LOOP structure. I found where I originally saw the technique: STREAM. It was my first introduction to the concept. It's small enough to use as an example of this concept for any folks that wish to follow along here. I've included the code below, along with some comments to help others understand what we're talking about. Credit where due: this isn't my code, but rather the actual built-in code for STREAM. The comments were added to help understand what it is doing.

As a reminder, UserRPL STREAM puts the first two elements of a list on the stack, then executes the prog/function you give it, then does the same with the rest of the elements. Here's how it does this:

Code:

::
   CK2&Dispatch
   # 50  ( must be list in SL2, and any kind of object in SL1 )
   ::
      ( save the executable object into NULLLAM1 )
      1LAMBIND

      ( make a copy of the list, then... )
      DUP

      ( equivalent of HEAD SWAP TAIL )
      CARCOMP SWAP CDRCOMP

      ( get the list size of TAIL from above )
      DUP LENCOMP

      ( make a copy of the list size and place it above TAIL )
      DUPUNROT

      ( if TAIL is an empty list, raise "Invalid Dimension" error )
      #0=case DimError

      ( Here's where the "magic" happens... the TAIL portion of the list is pushed
        onto the RPL Return Stack. Note that the return stack normally contains the
        addresses of RPL objects that execution will jump to when the current stream
        of RPL objects ends -- in SysRPL parlance: when SEMI is encountered.

        In this case, it is being used in a non-standard [but very clever] way.
        The 'R command is used to POP the next list element, which then leaves
        the return stack pointing at the next list element [or SEMI if at the end].
        As you'll see below, the only "issue" to overcome is that once the loop
        has been initiated, the list is no longer on the top of the return stack,
        so the RSWAPs are needed to temporarily move it to the top and then put it
        back again )

      >R    ( places the list on the return stack )

      ( main loop -- the list size is already in place in SL1 )
      ZERO_DO (DO)

         ( has the user pressed the "ON" key to cancel the loop? exit if so )
         ?ATTNQUIT

         ( swap the list into place, pop the next element, swap it back into place )
         RSWAP 'R RSWAP

         ( execute the "user program or function" object )
         1GETLAM EVAL

      LOOP  ( bottom of DO loop )

      ( this is a necessary step to remove the final SEMI from the RPL return stack )
      RDROP

      ( abandon the NULLLAM containing the user program/function object )
      ABND
   ;
;

Stepping through the above code with the debugging tools shows that the RSWAPs are necessary.

Now, to follow my own advice from another post about learning from others, I'll attempt to convert the above code into an alternative form using 3298's ticR suggestion in place of 'R. I'll skip the loop structure optimization for now to avoid confusion, and this time without the comments to show how small this command really is:

Code:

::
   CK2&Dispatch
   # 50
   ::
      1LAMBIND
      DUP
      CARCOMP SWAP CDRCOMP
      DUPLENCOMP #0=case DimError
      >R
      BEGIN
         ?ATTNQUIT
         RSWAP ticR RSWAP
         ITE ::
            1GETLAM EVAL
            FALSE
         ;
            TRUE
      UNTIL
      ABND
   ;
;

(09-06-2017 04:55 PM)3298 Wrote:  I guess you read the text file that comes with Nosy? It contains some programming tricks in its last section. ...

Thanks for the reminder to go back and take a look at it. I did see that (a long time ago), but must confess that I didn't take the time to digest that section at the time. Your examples are good ones for the power of the optimizations you (and Werner) are using.

[David Hayden]

(09-07-2017 05:53 AM)DavidM Wrote:  Most of the previous comments I'd been receiving were encouraging the inclusion of "special case" commands such as these. Do you feel that their presence (and the space they take) is more of a liability?

There's always the need for another "special case." Where does it end? If it's something that's very small, or would be exceptionally large and/or slow in userRPL, or is a generally useful special case, then the library may be appropriate, but otherwise it's taking up space. One possibility would be to include userRPL for some special cases in the documentation. That way if a user wants something in particular, they can key it in themselves.

[David Hayden]

(09-07-2017 07:54 PM)DavidM Wrote:  Stepping through the above code with the debugging tools shows that the RSWAPs are necessary.

The reason they're necessary is because the DO (or in this case ZERO_DO) pushes the address of the next instruction on the return stack. That's how the LOOP instruction knows where to go to execute another iteration.

[David Hayden]

(08-13-2017 02:36 PM)DavidM Wrote:  

(08-13-2017 01:38 PM)BruceH Wrote:  LPICK command...

Nice one. Shouldn't be too difficult.

That could be generalized into something like DOLIST that applies a program to each element on the level 1 list and the entire level 2 list. Here it is in userRPL:

Code:

@ Input: List1 List2 Program
@ If List2 is {el1 el2 el3 ...} then
@ apply Program to List1 el1, then List1 el2
@ then List1 el3, etc. with DOLIST
«
ROT →  P L
  «
   1. « L SWAP P EVAL » DOLIST
  »
»

Here's an example that implements LPICK. I'm horrible with names so I'll just assume that the program above is called "Prog":
Get items 1, 1, 4, 3, and 2 from a list:
{ "A" "B" "C" "D" }
{ 1 1 4 3 2 }
« GET »
Prog
Output:
{"A" "A" "D" "C" "B"}

[DavidM]

David, your example program is actually a very good "test subject" for discussion, because it allows me to pinpoint some specific comparisons that I continue to question every time I start down the path of adding another command to this library.

Your straightforward (and well-written) program weighs in at 63.5 bytes of storage, and although it performs a more generic function than the defined LPICK, it certainly accommodates the same functionality very easily.

For comparison, the current version of LPICK weighs in at 243.5 bytes, and is "hard-wired" to only provide the << GET >> function without allowing other variants as your UserRPL program does.

While that may seem like a very poor result for LPICK, that's only part of the picture. Running equivalent "picks" of 650 elements from a source list containing 1300, your program completes in 27.4 seconds while the same data is processed by LPICK in 2.7 seconds. The reason for both the size and the speed difference is the same: two embedded Saturn routines in LPICK take up a lot of space but get the final result much faster.

So the question becomes: "what's the relative value of size (and additional menu items) vs. speed?" I know there's no easy answers here, but it's a legitimate concern. At this point I'm inclined to include the command, mainly because I think it's very versatile and the performance is good. Your point is good, though, that there needs to be a limit to the special-casing. It's really just another form of "feature creep", and that's a potential problem for all projects.

[pier4r]

My 2 eurocents:

User point of view: there can be tons of useful programs, for example scattered on this forum. The problem is that when they are scattered, the user has to search them, type them, evaluate them and that's a lot of overhead if the user wants to solve a problem in one session run. At the end he can end doing its own version of the solution.

This is a general problem about information. If the information that I need is somewhere but it is hard to reach given the time that I allocate to the problem I want to solve, often I end up trying to derive the information by myself with possible poor results.

Therefore I highly value libraries that centralize useful solutions. For example already someone (even me) that goes through this forum, comp.sys.hp48, hpcalc.org and other sources (which ones? I do know only MoHPC and comp.sys.hp48 as big sources for RPL programs) and assembles a library of useful programs because those either save programming time or execution time (size comes third), is doing a very useful work in my opinion. Like a "librarian" that offers the next person a selection of useful books.

Therefore for me what is important is the utility function first.

Take the LPICK example.

Does it save developing time for equivalent LPICK routine? Yes
Does it save time searching (and evaluating) for an equivalent LPICK routing written by someone else (ex: David Hayden) that may require hours (or days) due to absent centralized properly ordered repositories? (hpcalc is great, but still one needs to go through the entries) ? Yes
Does it perform well against the "locally" know alternatives? Yes
Does it take a lot of space? A mere 300 bytes for a library that can grow up to 128KB (as far as I know)
Can be often used? For someone that went through the effort to search a library for its needs, yes.

End decision: is it worth being in the library? Yes.

What about that program consisting of 3 cleverly arranged built in commands in userRPL, is it worth being in a library instead of being manually typed? If it satisfies the points above: yes.

[John Keith]

(09-09-2017 02:09 AM)DavidM Wrote:  So the question becomes: "what's the relative value of size (and additional menu items) vs. speed?" I know there's no easy answers here, but it's a legitimate concern. At this point I'm inclined to include the command, mainly because I think it's very versatile and the performance is good. Your point is good, though, that there needs to be a limit to the special-casing. It's really just another form of "feature creep", and that's a potential problem for all projects.

I am in favor of including it as long as the original LPICK command stays. LPICK is very useful as-is, and no matter how fast the new command is, needing to repeatedly execute a User RPL sequence will slow it down significantly.

John

[David Hayden]

(08-25-2017 09:07 PM)DavidM Wrote:  I just checked a couple of built-in list commands (SUB and GET), and it looks like they both perform a rounding function on the arguments instead of taking the integer part (likely due to COERCE being used to convert those reals into System Binary Integers). For example:

Code:

{ 1 2 3 4 5 } 1.1 GET

returns 1

whereas

Code:

{ 1 2 3 4 5 } 1.8 GET

returns 2

I think rounding is more appropriate. Consider the case where where some calculation is used to compute the index. If the calculation results in an index of 0.999999999 or 1.000000001, the result of GET should probably be the same.

On the other hand, I can't recall a single instance in decades of programming where I've needed complex calculations to compute an index that would result in needing rounding.

[DavidM]

(09-09-2017 01:28 PM)David Hayden Wrote:  I think rounding is more appropriate. Consider the case where where some calculation is used to compute the index. If the calculation results in an index of 0.999999999 or 1.000000001, the result of GET should probably be the same.

On the other hand, I can't recall a single instance in decades of programming where I've needed complex calculations to compute an index that would result in needing rounding.

I think the reason I've leaned toward using %IP># over COERCE in most of the commands is in consideration of situations where a given list's size is simply divided by some constant. Seems like IP is safer than rounding for that (to me). Regardless of that, though, my current thinking is that a precedent has already been set by the built-in commands, and following that precedent is more important. I just need to go through all the commands and find where I've IP'd an index (or count) to assess if the issue applies and what impact a change would make. It's on my task list, just haven't done it yet.

[pier4r]

David, I do not want to pressure you to publish your library (although I think it is already worth it many times) but to ease the ability to reach the file, would it be possible to update the first post with a link to the post with the last revision?

In any case, great work.

[DavidM]

(09-10-2017 09:42 AM)pier4r Wrote:  David, I do not want to pressure you to publish your library (although I think it is already worth it many times) but to ease the ability to reach the file, would it be possible to update the first post with a link to the post with the last revision?

In any case, great work.

Yes, I should have been doing that all along. I've now edited all of the previous posts with updates with a note to see the first post in the thread for the latest version. The first post now has the last released version (1.1.0d) from 2017-08-30. Hopefully this will reduce the confusion about where to get it. Future updates will all be placed in that same location, up until a final release is placed in the General Software section (and submitted to hpcalc.org).

[David Hayden]

(09-09-2017 02:09 AM)DavidM Wrote:  The reason for both the size and the speed difference is the same: two embedded Saturn routines in LPICK take up a lot of space but get the final result much faster.

I can't argue with that tradeoff, assuming that the Saturn code is related to the "get" functionality and not the rest. Otherwise, it might be worth considering if the more generic function would be a useful tradeoff.

While we're on the subject of size vs. speed tradeoffs, I'll mention HPGCC, which puts the tradeoff on steroids. In my experience C programs are about 100 times faster and about 100 times larger than userRPL. The size issue can be mitigated somewhat by storing the programs on the SD card and loading only when needed, but of course you have the load time (about 0.25s for most programs) and there still has to be room to load it, but at least you don't have to store in a port, flash, or userOb. I guess my point is that if you're avoiding some command because it's extremely CPU intensive, then this might be a viable alternative.

Great work by the way! I've really been enjoying reading the thread and using the library. Is the source code available?

[David Hayden]

(09-05-2017 09:33 PM)Joe Horn Wrote:  The problem of long garbage collections when there are a lot of exploded list items on the stack can be avoided by first storing the list into a global variable.

Brilliant!

By the way, I think that newRPL doesn't suffer from this "long garbage collection" problem. In "HP RPL," the temporary object area (tempOb) consists of contiguous blocks where each block contains

1. A 1-nibble flag used for garbage collection
2. The object itself
3. 5 nibbles to store the size of the object (or maybe the whole block, I can't remember)
   

When doing GC, the system has to set a bit in the flag nibble to indicate that the block is in use.

Given a pointer to an object in tempOb, it finds the corresponding flag nibble by starting at the object, and skipping forward until it finds the 5-nibble size field. I'm not sure how it distinguishes the size field from the start of another object, but it does. Once it find the size field, it just subtracts the size and that takes it to the flag nibble, where it can mark the block as being in use.

The important point here is the "skipping forward" part. If you have a pointer into a list, then you have to skip to the end of the list. And if you have pointers to every object in the list, then you have to skip forward from each one to the end of the list.

I'm pretty sure that newRPL handles this differently: Rather than storing the size (and the flag?) along with the object, it has a separate memory area that stores a table of pointers (or maybe offsets) to each object in tempOb. So finding the block that contains a particular object requires a binary search through the table of pointers, not a linear scan. Thus finding embedded objects is much faster.

[DavidM]

(09-11-2017 01:36 PM)David Hayden Wrote:  

(09-09-2017 02:09 AM)DavidM Wrote:  The reason for both the size and the speed difference is the same: two embedded Saturn routines in LPICK take up a lot of space but get the final result much faster.

I can't argue with that tradeoff, assuming that the Saturn code is related to the "get" functionality and not the rest. Otherwise, it might be worth considering if the more generic function would be a useful tradeoff.

LPICK starts out by exploding the contents of the source list onto the stack, then it performs the following steps to obtain the final results:
1) Make room on the stack above the exploded elements for the final "picked" element pointers.
2) Queue the pick list onto the RPL return stack, then loop through its contents. Pointers for each picked item are placed in the next available slot at the top of the stack.
3) Drop the original source elements from the stack, leaving only the "picked" elements.
4) Bundle result into final list

The Saturn parts are in steps 1&2. The first routine is essentially a "targeted MOVEDN" that moves the stack contents into position after the stack was expanded with NDUPN. The second one simply copies the given stack pointer into the identified position for the result.

(09-11-2017 01:36 PM)David Hayden Wrote:  While we're on the subject of size vs. speed tradeoffs, I'll mention HPGCC... then this might be a viable alternative.

It would be if I was anything more than "conversant" with C. I can usually read it and figure out what's going on, but I've never actually had to work on any C projects over the years, and thus never really got into the C mindset. I know that may seem odd to many, but C isn't really in my "toolbelt".

(09-11-2017 01:36 PM)David Hayden Wrote:  Great work by the way! I've really been enjoying reading the thread and using the library. Is the source code available?

Thanks, this has been an interesting exercise for me. I've had a long-standing desire to do more with list processing in RPL, and Pier's challenges were the perfect playground to do that. As is usually the case with me, though, I keep seeing opportunities for general solutions when I work on the specific problems. If others can make use of them, so much the better!

The source isn't published anywhere just yet, but I plan to make it available. I still need to clean it up some, as there are a handful of redundancies that I can eliminate and quite a few places where alternative approaches are "in the works" (notably storing lists as globals before exploding in a few key places). As is usually the case, I learn a few things as I go along and then want to go back and recode where appropriate, but that's never as fun as working on the newer things, is it?