Easy as { 1 2 3 }?
Yesterday, 10:52 PM
Post: #1
 DavidM Senior Member Posts: 617 Joined: Dec 2013
Easy as { 1 2 3 }?
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.
Today, 12:52 AM
Post: #2
 Joe Horn Senior Member Posts: 1,277 Joined: Dec 2013
RE: Easy as { 1 2 3 }?
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.

X<> c
-Joe-
Today, 01:41 AM
Post: #3
 DavidM Senior Member Posts: 617 Joined: Dec 2013
RE: Easy as { 1 2 3 }?
(Today 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.
Today, 04:12 AM
Post: #4
 Joe Horn Senior Member Posts: 1,277 Joined: Dec 2013
RE: Easy as { 1 2 3 }?
(Today 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.

X<> c
-Joe-
Today, 04:52 AM
Post: #5
 DavidM Senior Member Posts: 617 Joined: Dec 2013
RE: Easy as { 1 2 3 }?
(Today 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.
Today, 01:01 PM
Post: #6
 John Keith Member Posts: 204 Joined: Dec 2013
RE: Easy as { 1 2 3 }?
Considering that the Saturn code is 115 times as fast as the next best option, I strongly concur with #3.
Today, 02:38 PM
Post: #7
 Dave Britten Senior Member Posts: 901 Joined: Dec 2013
RE: Easy as { 1 2 3 }?
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.
Today, 05:21 PM
Post: #8
 DavidM Senior Member Posts: 617 Joined: Dec 2013
RE: Easy as { 1 2 3 }?
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 »
Today, 05:54 PM
Post: #9
 Claudio L. Senior Member Posts: 1,295 Joined: Dec 2013
RE: Easy as { 1 2 3 }?
(Today 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.

Today, 06:07 PM
Post: #10
 DavidM Senior Member Posts: 617 Joined: Dec 2013
RE: Easy as { 1 2 3 }?