Threaded Mode | Linear Mode

Thomas Okken · 06-29-2018, 07:14 PM

(06-29-2018 04:59 PM)BartDB Wrote:
(06-29-2018 02:49 PM)Thomas Okken Wrote: This is a perfect example of what some people dislike about RPL: in order to write efficient programs, you have to avoid expressions and use stack manipulation instead..

? that's what trditional RPN does too??

Besides, that's exactly what I like about RPL compared to e.g. Prime (and Casio/TI/Sharp)

And for RPL calculators, the stack is an "infinite" set of storage registers

"Traditional" RPN has only four stack levels, which forces you to use numbered registers, or named variables on the later calculators that have them. That makes the flow of data a lot easier to follow.

When I see STO 00 and later on I see RCL 00, I know where that bit of data came from. I can't make such easy inferences when I'm looking at a bunch of DUP ROT SWAP etc.

(06-29-2018 05:13 PM)Thomas Klemm Wrote:
(06-29-2018 01:08 PM)Gerson W. Barbosa Wrote: That's one of my first RPL programs (HP-28S, back in 1987), so it can surely be optimized a bit.

Using local variables avoids stack juggling. Otherwise the changes were only minor.

Code:

« IF DUP 2 MOD THEN DUP √ → n r « 1 DO 2 + UNTIL r OVER < OVER n SWAP MOD NOT OR END n SWAP MOD NOT » END NOT »

(06-29-2018 02:49 PM)Thomas Okken Wrote: The resulting programs are hard to write and even harder to read.

Is that easy enough to understand?

Better, but no.

You still have to expend way too much mental energy to keep track of what is where in the stack. "r OVER < OVER n SWAP MOD NOT OR" is only "easy to read" for very specific values of "easy." Smile

Gerson W. Barbosa · 06-29-2018, 07:35 PM

(06-29-2018 05:13 PM)Thomas Klemm Wrote:
(06-29-2018 01:08 PM)Gerson W. Barbosa Wrote: That's one of my first RPL programs (HP-28S, back in 1987), so it can surely be optimized a bit.

Using local variables avoids stack juggling. Otherwise the changes were only minor.

Code:

« IF DUP 2 MOD THEN DUP √ → n r « 1 DO 2 + UNTIL r OVER < OVER n SWAP MOD NOT OR END n SWAP MOD NOT » END NOT »

Also, your version is faster: 201 seconds for testing 177777773 instead of 214 seconds (on the real 28S). This means my stack handling is not efficient. When properly done it should be faster than using local variables.

Gerson.

Valentin Albillo · 06-29-2018, 11:32 PM

.
Hi, Thomas:

(06-29-2018 02:49 PM)Thomas Okken Wrote:
(06-29-2018 01:08 PM)Gerson W. Barbosa Wrote: « DUP 2 / FP IF NOT NOT THEN DUP √ 1 DO 2 + 3 DUPN SWAP OVER [...] END SWAP DROP MOD NOT END NOT »

This is a perfect example of what some people dislike about RPL:
in order to write efficient programs, you have to avoid expressions and use stack manipulation instead. The resulting programs are hard to write and even harder to read.

Couldn't agree more. Most every RPL (probably an acronym of 'RePeLent') program of non-trivial size totally seems an entry for an "Obfuscated C" contest. Matter of fact I've seen actual OC entries much easier to understand than the usual RPL garbage-like "... R\->I 1 + OBJ\-> 1 SWAP 2 PICK3 ROT 1 + ^ 1 - OVER ...". Even Saturn assembler is much clearer in comparison.

And not only are RPL programs of non-trivial size hard to write and hard to read, they're almost impossible to understand and edit unless:

you

and

named

EVAL

algebraic

and

excruciatingly extensive docs

And let's not begin with so-called "System RPL", which makes "User RPL" seem like Tiny BASIC in comparison. XD

Regards.
V.
.

Thomas Klemm · 06-30-2018, 01:20 AM

(06-29-2018 07:14 PM)Thomas Okken Wrote: You still have to expend way too much mental energy to keep track of what is where in the stack.

Instead of 3 values only one is permanently on the stack. It's the divisor that is incremented by 2 with each step in the DO-loop:

Code:

        2 +

You may call it d or if you prefer OVER.

Quote:"r OVER < OVER n SWAP MOD NOT OR" is only "easy to read" for very specific values of "easy."

There's a reason I wrote this as:

Code:

        r OVER <

        OVER n SWAP MOD NOT

        OR

Using the variable d instead that would be:

Code:

        r d <

        d n SWAP MOD NOT

        OR

That's the combination of two predicates using or.
In Python that would be:

Code:

r < d or n % d == 0

So there's left only one relevant stack operation: SWAP.

In Forth we would probably factor this as:

Code:

: DIVIDES SWAP MOD NOT ;

This would lead to:

Code:

        r d <

        d n DIVIDES

        OR

While we could extract that in UserRPL as code object in a local variable we'd still have to EVAL it. That's the reason I would avoid that. And then I assume it would be slow.

Hopefully I reduced the mental energy needed to read that piece of code once more.

Thomas Klemm · 06-30-2018, 02:14 AM

(06-29-2018 07:35 PM)Gerson W. Barbosa Wrote: This means my stack handling is not efficient. When properly done it should be faster than using local variables.

Don't consider me an expert so I could be totally wrong, but I would recommend:

Avoid global variables in a program.
Use local variables for immutable values to reduce the amount of objects on the stack.
Use only the simplest stack-manipulating commands as DUP, SWAP, OVER or ROT.

I could imagine that creating a context for local variables is somewhat expensive. So don't do that within a tight loop. But accessing local variables should be fast. Similar to something like DUP or +.

In UserRPL the overhead for each command is big compared to actually doing it.
Thus reducing the amount of commands within a loop helps.
Just by counting the commands in the DO-loop we can see that their ratio 11 ÷ 12 is close to the ratio of durations: 201 ÷ 214.

Use SysRPL if time really matters.

Cheers
Thomas

Thomas Klemm · (This post was last modified: 06-30-2018 07:38 AM by Thomas Klemm.)

(06-29-2018 11:32 PM)Valentin Albillo Wrote: And not only are RPL programs of non-trivial size hard to write and hard to read, they're almost impossible to understand and edit unless:
(1) you wrote the program and no more than a few days have elapsed since you did, and
(2) you used lots of named variables and EVALs of algebraic expressions, and
(3) you wrote down excruciatingly extensive docs and commented most every line

In this post about Farey Sequences in the old forum I wrote:

Quote:Looking at the different solutions I wondered whether I can still understand what I've done in a few weeks or months from now.

Looking at the different solutions I wrote more than 9 years ago I didn't have much trouble to understand the UserRPL program. The SysRPL program is similar. You just have to sprinkle a percent sign here and there. But I never would have recognised the code to add an algebraic expression to a list.

Even the horrible ALG for HP-35s solution I understood after a couple of WUTs. Who would ever use that?

Quote:The BASIC version for HP-71B is missing I know and it might be quiet similar to Python: a short one- or three-liner. Take it as a mini-challenge.

Cheers and have fun!
Thomas

PS: Years later I even provided a UserRPL program that avoids the STO command.

Thomas Klemm · (This post was last modified: 06-30-2018 08:46 AM by Thomas Klemm.)

(06-29-2018 07:35 PM)Gerson W. Barbosa Wrote: Also, your version is faster: 201 seconds for testing 177777773 instead of 214 seconds (on the real 28S).

This variant raises an error when a divisor is found:

Code:

«

  IF DUP 2 MOD

  THEN → n

    «

      IFERR 3 n √

        FOR d

          IF n d MOD NOT

          THEN 0 DOERR

          END

          2

        STEP

      THEN 0

      ELSE 1

      END

    »

  ELSE NOT

  END

»

My hope is that using a FOR-loop is both faster and easier to understand.

RMollov · 06-30-2018, 10:20 AM

I like RPL better than RPN. It took me about a week or so to transform all my surveying programs written originally for the HP41 to the HP28S back then, having only German manual and I don't understand German language. Printed examples turned out to be enough.
Later I wrote many more, still used today by colleagues. I followed advice I found somewhere to create little routines with known input and output, test them and latter combine them to make complex program. The resulting directory was used as a source for a library with only selected programs (or macros) left "visible". Debugging was easy for obvious reasons.
I agree RPL is hardly perfect as a language for other than calculator purposes, but wasn't it created exactly for that?
I strongly disagree with the criticism of the manuals, especially the original, thick one, the HP-48 Owner's Manual, for the HP-48 S/X. IMHO it's brilliant. And that without list processing functions that came with the HP-48G/X.

Cheers,

pier4r · 06-30-2018, 11:16 AM

(06-29-2018 11:32 PM)Valentin Albillo Wrote: And not only are RPL programs of non-trivial size hard to write and hard to read, they're almost impossible to understand and edit unless:
(1) you wrote the program and no more than a few days have elapsed since you did, and
(2) you used lots of named variables and EVALs of algebraic expressions, and
(3) you wrote down excruciatingly extensive docs and commented most every line
And let's not begin with so-called "System RPL", which makes "User RPL" seem like Tiny BASIC in comparison. XD

This discussion is cyclic but every time new bits pops out.

While I like RPL , I like it so much that I don't mind waiting 5-6 days for a result using the 50g, instead of writing the program in any language that can run on different hw (n1), I completely agree.

I mean, garbage can be written in whatever language if one wants to be cryptic. Even basic without named variables, long routines and no comments can be hard to follow.
Therefore whatever the language, I try to do what is written in the Valentin's points 2 and 3 (in comments I expose the algebraic expressions).

As I realized, also thanks to the 50g, one should see the solution time of a problem as a whole. One should not focus only on the execution time (unless the challenge is to bring down the execution time).

Considering development time (did someone mention debugging?), execution time and once again development time (if the program has to be changed over time to accommodate small variations ), I find it way better to have a program that is slower but that can be extended and combined with other programs written in a similar way. This rather than a program that I have no will to touch because it is complicated to read and understand.
The "no will to touch it" can be counted as infinite development time, and that beats the slowest finite execution time that one can imagine.

For example in the last months I am happily using the 50g crunching for days using a program that maybe is not optimized, but it is relatively easy to read/modify. This also because I couldn't and can't process faster outputs, since life happens, so waiting a week for a result is still ok (newRPL may bring this down to hours maybe).

If I need faster results then I would use prime+android or maybe languages available on termux+android. Since android devices are powerful, silent and relatively power efficient (someday I may use scaleway arm systems).
I may even start to consider python, that I know it is great but I cannot really digest the absence of curly braces (or similar symbols) for blocks of code, if I have no other good alternative.

n1: actually I should use the prime app more, that's a monster on android! Only I am lazy and I don't often open my win10 system that has the connectivity kit to transfer programs with ease.

John Keith · 06-30-2018, 02:16 PM

(06-30-2018 02:14 AM)Thomas Klemm Wrote: Use only the simplest stack-manipulating commands as DUP, SWAP, OVER or ROT.

I could imagine that creating a context for local variables is somewhat expensive. So don't do that within a tight loop. But accessing local variables should be fast. Similar to something like DUP or +.

I would amend that slightly by saying that one should avoid stack commands that take a numerical argument (such as PICK and ROLL) whenever possible. They take several times as long to execute as simple stack commands. The newer commands such as PICK3, DUPDUP and NIP are just as fast as the basic ones you listed, and they save time and memory.

Local variables are faster than globals in programs but not as fast as stack operations.

When I am writing a program or translating one from another language, I tend to use lots of local variables and avoid complex stack gymnastics. This speeds development time and (slightly) increases readability. If the program is one I plan to keep and use often, I will further optimize it by eliminating variables as much as possible and using the stack more.

John

Gerson W. Barbosa · 06-30-2018, 02:37 PM

(06-30-2018 07:27 AM)Thomas Klemm Wrote:
(06-29-2018 07:35 PM)Gerson W. Barbosa Wrote: Also, your version is faster: 201 seconds for testing 177777773 instead of 214 seconds (on the real 28S).

This variant raises an error when a divisor is found:

Code:

« IF DUP 2 MOD THEN → n « IFERR 3 n √ FOR d IF n d MOD NOT THEN 0 DOERR END 2 STEP THEN 0 ELSE 1 END » ELSE NOT END »
My hope is that using a FOR-loop is both faster and easier to understand.

Really faster and easier to read: 86 seconds instead of 108 seconds on the 48GX (DOERR doesn’t belong in the 28S catalog).

Thomas Klemm · 06-30-2018, 03:04 PM

(06-30-2018 02:37 PM)Gerson W. Barbosa Wrote: DOERR doesn’t belong in the 28S catalog.

Would the following work then?

Code:

«

  IF DUP 2 MOD

  THEN → n

    «

      IFERR 3 n √

        FOR d

          n d MOD INV

          DROP

          2

        STEP

      THEN

      ELSE 1

      END

    »

  ELSE NOT

  END

»

Gerson W. Barbosa · (This post was last modified: 06-30-2018 06:14 PM by Gerson W. Barbosa.)

(06-30-2018 03:04 PM)Thomas Klemm Wrote:
(06-30-2018 02:37 PM)Gerson W. Barbosa Wrote: DOERR doesn’t belong in the 28S catalog.

Would the following work then?

Code:

« IF DUP 2 MOD THEN → n « IFERR 3 n √ FOR d n d MOD INV DROP 2 STEP THEN ELSE 1 END » ELSE NOT END »

Yes, for n>3 (if I’ve entered it right). Anyway, 172 seconds (down from 201 seconds).

PS: My bad. All previous ones don’t work either when n<4. This was used together with a prime factorizer for which this behavior didn’t matter. Will see to that later. Sorry!

Valentin Albillo · 06-30-2018, 11:35 PM

.
Hi, Pier:

(06-30-2018 11:16 AM)pier4r Wrote: While I like RPL , I like it so much that I don't mind waiting 5-6 days for a result [...]

Good for you. Just out of curiosity: what's the result you're eagerly waiting 5-6 days for ? Would you indulge me and describe either the problem or the computation ? Thanks.

Quote:I mean, garbage can be written in whatever language if one wants to be cryptic.

The problem with RePeLent is that it's almost impossible to not write unfathomable "garbage" even if you're trying hard not to be cryptic, and in any case the moment you resort to stack juggling and stack acrobatics for the sake of efficiency you'll immediately plunge head on on cryptography.

Quote:Even basic without named variables, long routines and no comments can be hard to follow.

See ? you must picture a worst-case scenario (no named variables, long routines, no comments ...) to try and get "basic" to be "hard to follow" (nope!) while in even the best-case scenario RePeLent is nothing but impossibly hard to follow, to the point of needing to write down the stack after every step to understand what's where. Comparing both languages in this respect is utterly ridiculous.

Quote:[...] I find it way better to have a program that is slower but that can be extended and combined with other programs written in a similar way. This rather than a program that I have no will to touch because it is complicated to read and understand.

So you're advocating sacrificing speed for readability, i.e., completely going against what the RPL paradigm posits. Stack juggling is virtually incompatible with "readability".

You know what ? The RPL case reminds me a lot of a hobbyist personal computer of the 80's (I think), the Jupiter Ace, which had a native FORTH implementation out of the box and was being advertised as a fully structured, higher level, much faster language than Sinclair's Spectrum, so supposedly superior and/or more desirable.

You know how it all ended: almost nobody bought the FORTH computer, they only sold a few thousand units as nobody was writing commercial software for it and the BASIC listings in the popular hobbyist magazines of the time could'nt be used in FORTH. The makers were losing money big time and it ended in sheer failure despite its supposed strong points vs Spectrum's BASIC, which sold untold millions of units.

The Jupiter ACE's FORTH programming paradigm proved to be just too cryptic, it forced would-be programmers to take care of the low-level details (stacks, RPN evaluations, etc) which is precisely the kind of thing a decent language should take care of so that the programmer can concentrate on the algorithms and high-level details of the task to solve, not on "PICK3 ROT DUP SWAP ROT".

It's the programming language the one which should be working for me and releasing me of the low-level drudgery, not the other way around.

Best regards and have a nice weekend
V.
.

Thomas Klemm · (This post was last modified: 07-01-2018 08:24 PM by Thomas Klemm.)

(06-30-2018 03:32 PM)Gerson W. Barbosa Wrote: All previous ones don’t work either when n<4.

There's a problem with the FOR-loop in that it gets executed at least once even when the upper limit is smaller than the start value.

Try this line:

Quote:3 1 FOR i i END

This leaves the value 3 on the stack.
I'd prefer if the stack was left unchanged instead.

Now you can either handle that special case beforehand or then just call it a day.
How often will you use that program to check that 3 is a prime?

Cheers
Thomas

Gerson W. Barbosa · (This post was last modified: 07-01-2018 12:50 PM by Gerson W. Barbosa.)

(07-01-2018 03:49 AM)Thomas Klemm Wrote:
(06-28-2018 08:48 PM)mdunn Wrote: All previous ones don’t work either when n<4.

There's a problem with the FOR-loop in that it gets executed at least once even when the upper limit is smaller than the start value.

...

Now you can either handle that special case beforehand or then just call it a day.
How often will you use that program to check that 3 is a prime?

When I said "all previous ones" that included my original program. As I said, that limitation was irrelevant to my purpose, but if I want to use it as a primality test then I think it should handle all valid arguments, even if we know 1 is not prime and 2 and 3 are. An easy way to do it is by means of a patch (thus, an inelegant solution) to be added at the beginning of the program:

«
  IF 3 DUP2 ≤
  THEN SWAP -
  ELSE DROP
  END
  IF DUP 2 MOD
  THEN → n
    «
      IFERR 3 n √
        FOR d
          n d MOD INV DROP 2
        STEP
      THEN
      ELSE 1
      END
    »
  ELSE NOT
  END
»

I don't use the 28S anymore for prime factorization, as the built-in FACTOR on the 50g does it much faster, but if the 28S were my only calculator I would use your optimized version without my unnecessary patch.

FWIW, here is my full original HP-28S program:

Code:

%%HP: T(3)A(R)F(.);

DIR

  PRFAC

  \<< DUP

    IF NOT PRIME

    THEN 1 SF 2 "'" ROT ROT DCMP 1 + 1 CF

      WHILE OVER 1 \=/

      REPEAT DCMP 2 +

      END DROP2 DUP SIZE 1 - 1 SWAP SUB "'" + STR\->

    END

  \>>

  DCMP

  \<< DUP2 MOD

    IF NOT

    THEN DUP \->STR 0

      DO 1 + 4 ROLL 4 ROLL SWAP OVER / DUP2 6 ROLLD 5 ROLLD SWAP MOD

      UNTIL NOT NOT

      END DUP

      IF 1 \=/

      THEN SWAP "^" + SWAP \->STR +

      ELSE DROP

      END ROT DUP

      IF PRIME

      THEN DUP 2 - 1 FS? + ROT 4 ROLL DROP

      ELSE ROT ROT

      END "*" + 4 ROLL SWAP + ROT ROT

    END

  \>>

  PRIME

  \<< DUP 2 / FP

    IF NOT NOT

    THEN DUP \v/ 1

      DO 2 + 3 DUPN SWAP OVER

      UNTIL < ROT ROT MOD NOT OR

      END SWAP DROP MOD NOT

    END NOT

  \>>

END

Thank you very much for your advices and improvements.

Gerson.

PS:

Quote:All previous ones don’t work either when n<4.

That was written by myself, not by mdunn.

Claudio L. · 07-01-2018, 06:39 PM

(06-30-2018 11:35 PM)Valentin Albillo Wrote: So you're advocating sacrificing speed for readability, i.e., completely going against what the RPL paradigm posits. Stack juggling is virtually incompatible with "readability".

Most of the "bad" things mentioned here about RPL are a consequence of the particular implementation decisions, rather than the language itself. There's no real reason why using named variables should sacrifice speed, other than that's the way it was implemented, same thing with expressions.
As an example, newRPL implements named local variables in a way that using them is as fast (if not faster) than stack juggling. There's also no reason why comments can't be persistent (similar to REM in Basic).
I think RPL is not particularly difficult to read, unless you obfuscate the code on purpose for the sake of speed "in-this-particular-implementation".

(06-30-2018 11:35 PM)Valentin Albillo Wrote: You know what ? The RPL case reminds me a lot of a hobbyist personal computer of the 80's (I think), the Jupiter Ace, which had a native FORTH implementation out of the box and was being advertised as a fully structured, higher level, much faster language than Sinclair's Spectrum, so supposedly superior and/or more desirable.

You know how it all ended: almost nobody bought the FORTH computer, they only sold a few thousand units as nobody was writing commercial software for it and the BASIC listings in the popular hobbyist magazines of the time could'nt be used in FORTH. The makers were losing money big time and it ended in sheer failure despite its supposed strong points vs Spectrum's BASIC, which sold untold millions of units.

The Jupiter ACE's FORTH programming paradigm proved to be just too cryptic, it forced would-be programmers to take care of the low-level details (stacks, RPN evaluations, etc) which is precisely the kind of thing a decent language should take care of so that the programmer can concentrate on the algorithms and high-level details of the task to solve, not on "PICK3 ROT DUP SWAP ROT".

I loved the Spectrum when growing up, but I quickly abandoned BASIC in favor of raw Z80 assembler, not exactly easy reading material...

By the way, DUP SWAP is equivalent to DUP (in your example above). I get that you don't like RPL... cheers!

Thomas Klemm · 07-01-2018, 08:26 PM

(06-30-2018 03:32 PM)Gerson W. Barbosa Wrote: PS:

Quote:All previous ones don’t work either when n<4.

That was written by myself, not by mdunn.

Sorry for that. I have fixed it meanwhile.

Thomas Klemm · 07-01-2018, 08:51 PM

(06-30-2018 03:32 PM)Gerson W. Barbosa Wrote: Yes, for n>3 (if I’ve entered it right). Anyway, 172 seconds (down from 201 seconds).

I've written a new article: Miller-Rabin Primality Test for the HP-48

(06-30-2018 10:20 AM)RMollov Wrote: I followed advice I found somewhere to create little routines with known input and output, test them and latter combine them to make complex program.

This was used to create the programs:

PLUS
TIMES
POWER
COMPOSITE?
PRIME?

I recommend to create them in a separate directory.
They aren't optimised for speed but I still assume that it's much faster than the naïve approach.

I'd be interested to know how long it takes on a real HP-28 to verify that 177777773 or 999999999989 are primes.

Cheers
Thomas

PS: For this program n must be bigger than 2. Sad

Valentin Albillo · 07-01-2018, 09:04 PM

.
Hi, Thomas:

(06-30-2018 03:32 AM)Thomas Klemm Wrote:
(06-29-2018 11:32 PM)Valentin Albillo Wrote: And not only are RPL programs of non-trivial size hard to write and hard to read, they're almost impossible to understand and edit unless:
(1) you wrote the program and no more than a few days have elapsed since you did,[...]

Looking at the different solutions I wrote more than 9 years ago I didn't have much trouble to understand the UserRPL program.

Computing Farey series is a program of trivial size on most any decent programming language (and more than a few indecent ones) so it's no wonder you still understand your RPL code. Try that with an RPL program of non-trivial size as I stated.

Quote:The BASIC version for HP-71B is missing I know and it might be quiet similar to Python: a short one- or three-liner. Take it as a mini-challenge.

I'll take it you're subtly addressing me to produce an HP-71B program to compute Farey series. I created one eons ago as part of my Euler Project's solutions but you missed the correct length: it's a two-liner (i.e.: trivial size) some 109 bytes long with nothing special about it so I'll omit it here.

Best regards.
V.
.