Easy as { 1 2 3 }? (when { 1 2 3 } ≠ { 1 2 3 })

[DavidM]

While testing some RPL code recently, I was reminded of a problem that can occur on the 50g when attempting to test lists for equality. Here's an example of how the problem can show up:

1) Set your 50g to exact mode
2) Enter the list { 1 2 3 } on the stack
3) Press ENTER to make a duplicate, then 2 * to double each list element
4) Press 2 / to divide each element in the second list by 2

At this point, you should have what appears to be two identical lists in stack levels 1 and 2:
2: { 1 2 3 }
1: { 1 2 3 }

Execute SAME (or ==) to compare the two lists for equality. I'm of the opinion that most rational people would expect a result of 1, but unfortunately my rev 2.15 50g sees those lists as not being the same. The reason for this is a bit complicated, and even worse, it's not as predictable as you might imagine. Try the same test as above, but this time use { 10 20 30 } as the initial list. Surprise! Unlike before, those lists are the same. Likewise, try multiplying or dividing by 1 instead of 2. What result do you think that will give?

What's the difference, and why does this happen? The answer to that is a bit complicated, and has to do with the following:

1. How the built-in RPL compiler substitutes whole numbers in the range -9..9 with a reference to a ROM-based constant instead of a raw value when it is invoked
2. How SAME/== only looks at the binary data of the whole list (instead of individual elements) when comparing for equality
3. How mathematical operations involving exact integers sometimes result in raw values, and sometimes don't
   

The 50g is far more consistent with its handling of approximate numbers, so this isn't usually a problem with those values. I've yet to find a way to cause a similar problem with approximate numbers.

I'm curious as to whether others have run into this issue, and if so, how you dealt with it. The only UserRPL methods I can think of are very slow as list sizes increase (eg. applying →STR STR→ to the lists before comparing). What methods have you found to deal with this?

Note that this is really just an issue for the 48gII/49g+/50g, as earlier RPL models either don't use exact integers or treat them differently when performing math operations on lists of them. On my rev. 1.19-6 49G, { 1 2 3 } 2 * strangely yields a result of { 2. 4. 6. }, regardless of mode.

[Joe Horn]

The LIN, TLIN, and SIMPLIFY commands all "normalize" a list of numbers the way you want (turning integers between -9 and +9 into their 5-nibble forms), but they are even slower than →STR OBJ→. For example, →STR OBJ→ on a list of 1000 long-form integer 1's takes 15+ seconds, but LIN takes 77+ seconds, TLIN takes 52+ seconds, and SIMPLIFY takes 73+ seconds. Unfortunately, all three functions, like →STR OBJ→, turn the integers into reals if approx mode is turned on.

Maybe exploring LIN, TLIN, and SIMPLIFY using Nosy would reveal what *they* do to normalize integers. Maybe just that code can be extracted (or called) to avoid the overhead of everything else that LIN, TLIN and SIMPLIFY do.

[DavidM]

(07-15-2018 12:52 AM)Joe Horn Wrote:  Maybe exploring LIN, TLIN, and SIMPLIFY using Nosy would reveal what *they* do to normalize integers. Maybe just that code can be extracted (or called) to avoid the overhead of everything else that LIN, TLIN and SIMPLIFY do.

Thanks Joe, that's a good idea. I'll see if I can find references to ROM entries that perform needed translations in those commands. I think I'll start with SIMPLIFY.

FWIW, I've already put together a SysRPL/Saturn routine to do this, which is a fairly good performer (converts a list of 1000 long-form integers in about 0.13s). It converts long-form instances of both reals and zints in the -9..9 range, and leaves everything else as-is. It also converts embedded lists. The only problem with it is that it's a huge chunk of code: 471 bytes (almost entirely assembly). Seems like a serious waste of space for a somewhat esoteric issue that most likely already has a solution hiding in ROM somewhere.

[Joe Horn]

(07-15-2018 01:41 AM)DavidM Wrote:  Thanks Joe, that's a good idea. I'll see if I can find references to ROM entries that perform needed translations in those commands. I think I'll start with SIMPLIFY.

Uh oh... I just took a peek, and I wish you luck. None of those commands have a dispatch for the integer type, and for reals they do a NOP. So the "normalization" must be done by the dispatch code (not in the S Series but added in the G Series), specifically the code which handles integers when no integer dispatch exists. I've never delved that deeply into the ROM.

[DavidM]

(07-15-2018 04:12 AM)Joe Horn Wrote:  Uh oh... I just took a peek, and I wish you luck. None of those commands have a dispatch for the integer type, and for reals they do a NOP. So the "normalization" must be done by the dispatch code (not in the S Series but added in the G Series), specifically the code which handles integers when no integer dispatch exists. I've never delved that deeply into the ROM.

I've already started looking at SIMPLIFY. In that particular case, there's a dispatch for BINT10 (hex A), which is "Symbolic class". This is where the long-form ZINT ends up branching. Unfortunately, it looks like the way this ends up getting handled is to pass the zint to CASEVAL, which in turn passes it to CASCOMPEVAL, and from there I'm starting to get a headache trying to trace what happens. This is nothing new, it seems to happen every time I start trying to trace something that branches into a CAS handler.

I did some experiments with a short SysRPL routine that simply passed all zints to CASEVAL, and ended up with run times similar to the →STR STR→ methods. So at the moment it's looking like my choices are:

1) Drive myself crazy trying to trace through the various CAS handlers until I find something that will be highly-specific to a rev. 2.15 ROM (and perhaps still not be directly applicable to a separate routine like I need).

2) Use →STR STR→ and put up with the wait.

3) Spend a bit more time optimizing the existing code I already have and grudgingly accept the memory footprint in return for the performance.

I'm leaning toward #3 at present.

While I was at it, I looked a bit more closely at the handlers for reals and noticed why everything I've tried already does the substitutions for those: it conveniently occurs in the PUSH% code, which is ultimately what most everything calls when placing a real on the stack (either directly or indirectly). That's why this issue seems to be isolated to exact integers.

[John Keith]

Considering that the Saturn code is 115 times as fast as the next best option, I strongly concur with #3.

[Dave Britten]

Here's a fairly succinct 50g program that uses DOLIST and STREAM to compare elements (and has special cases to handle empty or single-element lists).

Code:


\<<
  DUP2 SIZE SWAP SIZE OVER ==
  \<<
    0. ==
    \<< DROP2 1. \>>
    \<< 2. \<< == \>> DOLIST
      DUP SIZE 1. ==
      \<< LIST\-> DROP \>>
      \<< \<< AND \>> STREAM \>>
      IFTE
    \>>
    IFTE
  \>>
  \<< DROP2 DROP 0. \>>
  IFTE
\>>

You could change the "\<< == \>>" DOLIST argument to do type checking and recursion if you want it to work on nested lists.

Corrections/improvements welcome, as always.

[DavidM]

That's nice, Dave!

In this particular case, I believe the "==" steps can all be safely replaced with SAME. SIZE always returns a real, so those comparisons are all ok. The comparison of similarly positioned integers where one is a ROM reference works fine with SAME as well (since at that point they're not being lumped in with the entire list), so the == passed to DOLIST can also be a SAME in this case. SAME is generally faster than ==, so that gives it a boost in speed. Of course, this doesn't apply if the intent is to allow reals and integers to be evaluated as equivalent (ie. 1. == 1). That wasn't my original goal, but it could certainly apply in other situations.

3 of the IFTE clauses can be encapsulated in {} instead of « », which saves a few bytes as well.

Those changes reduce the size of the program from 183.5 to 161 bytes. Checking two lists of 1000 integers takes 18.8 seconds with the original code, and that reduces to 5.1 seconds with the alternate version.

Code:

«
  DUP2 SIZE SWAP SIZE OVER SAME
  «
    0. SAME
    { DROP2 1. }
    «
      2. « SAME » DOLIST
      DUP SIZE 1. SAME
      { LIST\-> DROP }
      « « AND » STREAM »
      IFTE
    »
    IFTE
  »
  { DROP2 DROP 0. }
  IFTE
»

[Claudio L.]

(07-15-2018 04:52 AM)DavidM Wrote:  So at the moment it's looking like my choices are:

1) Drive myself crazy trying to trace through the various CAS handlers until I find something that will be highly-specific to a rev. 2.15 ROM (and perhaps still not be directly applicable to a separate routine like I need).

2) Use →STR STR→ and put up with the wait.

3) Spend a bit more time optimizing the existing code I already have and grudgingly accept the memory footprint in return for the performance.

4) Switch to newRPL, forget about this mess and relax....

[DavidM]

(07-15-2018 05:54 PM)Claudio L. Wrote:  4) Switch to newRPL, forget about this mess and relax....

I figured you'd have that reaction, Claudio.

[Claudio L.]

(07-15-2018 06:07 PM)DavidM Wrote:  

(07-15-2018 05:54 PM)Claudio L. Wrote:  4) Switch to newRPL, forget about this mess and relax....

I figured you'd have that reaction, Claudio.

I'm not joking, you are fighting to fix a system that is almost impossible to fix (I did succesfully modify the ROM back in the day to allow direct execution of C code, it was really hard so I know what you are facing). I feel your time and skills would be better spent on a system that CAN be fixed to your specs (that's the beauty of open source), hence I wanted to remind you you have a 4th option: come help with newRPL instead!
I like what you did with the List processing library, many of those commands should've been in the ROM to begin with, and probably should be in newRPL too.
You seem to have good ideas to either detect and fix "glitches" in the old system, or improve/expand the system, which is "by definition" the sole purpose of newRPL.

BTW, newRPL does your { 1 2 3 } problem this way (for the interested):
In my head, SAME refers to whether two things are identical or not, while == is more of a mathematical operator, between objects that have some definition of equality.
Both are overloadable operators, so each object type defines how to behave (including cross-type operations).
For most objects, SAME and == are equivalent, but for lists SAME always refers to the whole object, while == does list processing like most other operators, returning a list with the result of applying the operator to the elements.
SAME applies the operator SAME recursively on each object of the list (better than a binary comparison, though object handlers are free to implement SAME as a binary data comparison), it returns a single true/false if all elements in the list are the SAME.

{ 1 2 3 } DUP 2 * 2 / SAME ---> 1
{ 1 2 3 } { (1,0) 2 3 } SAME ---> 1 (because 1 (1,0) SAME is true in newRPL)

== works element by element, recursively if needed be. It returns a list (or list of lists) with true/false elements.

{ 1 2 3 } DUP 2 * 2 / == ---> { 1 1 1 }

Other composites behave different. For example a program defines SAME in a similar way to lists, but there's no equality between programs, the == operator is not defined so it throws an error.

It may be debatable, but at least this behavior is very consistent throughout newRPL.

[DavidM]

(07-16-2018 04:25 AM)Claudio L. Wrote:  ...

Thanks for the kind words, Claudio, and also for the explanation of newRPL's approach. As per your usual, it seems like a sensible and well thought-out way to handle things.

I'm actually a fan of what you're doing with the platform, and would definitely be inclined to help out if I could. Unfortunately C is not in my bag of tricks at present, though I've started going down that path on numerous occasions since the early eighties. Something has always seemed to derail those plans.

I hope you have some success with your investigations into a newRPL application for the Prime -- that could be an interesting endeavor. Likewise, some kind of newRPL implementation on a Swiss Micros platform would probably draw some interest as well. There's lots of possibilities, and so little time...

[rprosperi]

(07-17-2018 03:05 AM)DavidM Wrote:  Likewise, some kind of newRPL implementation on a Swiss Micros platform would probably draw some interest as well.

This tantalizing recent post from Michael may be of interest....

https://forum.swissmicros.com/viewtopic.php?f=2&t=1883&start=10#p8668

[DavidM]

(07-17-2018 03:26 AM)rprosperi Wrote:  

(07-17-2018 03:05 AM)DavidM Wrote:  Likewise, some kind of newRPL implementation on a Swiss Micros platform would probably draw some interest as well.

This tantalizing recent post from Michael may be of interest....

https://forum.swissmicros.com/viewtopic.php?f=2&t=1883&start=10#p8668

Yes, I noticed that one, and it definitely made me wonder what was behind it. There's several possibilities, all potentially interesting.

[Massimo Gnerucci]

(07-17-2018 03:26 AM)rprosperi Wrote:  

(07-17-2018 03:05 AM)DavidM Wrote:  Likewise, some kind of newRPL implementation on a Swiss Micros platform would probably draw some interest as well.

This tantalizing recent post from Michael may be of interest....

https://forum.swissmicros.com/viewtopic.php?f=2&t=1883&start=10#p8668

I wonder what will they use for their firmware.

[John Keith]

(07-17-2018 06:33 AM)Massimo Gnerucci Wrote:  I wonder what will they use for their firmware.

Hopefully NewRPL.

I am also looking forward to seeing NewRPL running on the Prime, but considering that the Primes CAS and Home use different floating-point formats I am worried about interoperability when adding in a third format.

[Eddie W. Shore]

Let me see if I understand this correctly:

SAME compares exact values while Equals (==) compares floating point numerical equivalents?

[rprosperi]

(07-17-2018 12:43 PM)Eddie W. Shore Wrote:  Let me see if I understand this correctly:

SAME compares exact values while Equals (==) compares floating point numerical equivalents?

No, SAME checks if the arguments are actually exactly the same (hence the name), while == tests if the arguments are equivalent.

(1/3) (2/6) SAME => 0. because they are not the same, while

(1/3) (2/6) == => 1. because they are equivalent.

[DavidM]

(07-17-2018 01:06 PM)rprosperi Wrote:  

(07-17-2018 12:43 PM)Eddie W. Shore Wrote:  Let me see if I understand this correctly:

SAME compares exact values while Equals (==) compares floating point numerical equivalents?

No, SAME checks if the arguments are actually exactly the same (hence the name), while == tests if the arguments are equivalent.

(1/3) (2/6) SAME => 0. because they are not the same, while

(1/3) (2/6) == => 1. because they are equivalent.

== also ignores tags, which can be useful at times. But the increased flexibility of == comes with a price: it is noticeably slower. So in cases where performance is an issue, it's better to use SAME if you know that the objects in question are compatible with its strictness. In my experience, the most common issue that comes up for compatibility is exact vs. approximate numbers.

[Massimo Gnerucci]

(07-17-2018 12:32 PM)John Keith Wrote:  

(07-17-2018 06:33 AM)Massimo Gnerucci Wrote:  I wonder what will they use for their firmware.

Hopefully NewRPL.

I am also looking forward to seeing NewRPL running on the Prime, but considering that the Primes CAS and Home use different floating-point formats I am worried about interoperability when adding in a third format.

OK, so DM 48 <> "48GX clone".
Now the post makes sense.