Closure in RPL

[Thomas Klemm]

I can create the following program for the HP-48G:

Code:

\<< \-> a 
  \<<
    \<< \-> b
      \<< a b +
      \>>
    \>>
  \>>
\>>

Save it as e.g. MKADDR and run it with 5:

5 MKADDR

It returns:

Code:

\<< \-> b
  \<< a b +
  \>>
\>>

However when I try to use this with 8:

2: 8
1: \<< \-> b \<< a b + \>> \>>
EVAL

I get the following:

Error: Undefined Local Name

This comes at no surprise as apparently the code object hasn't been closed over the local variable a as I had hoped.
Otherwise the result would have been:

Code:

\<< \-> b
  \<< 5 b +
  \>>
\>>

Which then would lead to:

2: 8
1: \<< \-> b \<< 5 b + \>> \>>
EVAL

1: 13

For those familiar with JavaScript, I'm trying to do something similar to:

Code:

const mkaddr = (a) => (b) => a + b
const add5 = mkaddr(5)
add5(8)
13

I came up with a solution using the code of the closure in strings that are concatenated with the local variable a.
But I consider that an ugly hack.

Are there better ways to do that in UserRPL?
Or then maybe in SysRPL?

[DavidM]

This may be a situation where using an algebraic makes sense. Placing 5 on the stack, then running the following:

Code:

\<< \-> a
  \<<
    'a+b' EVAL
  \>>
\>>

...will leave '5+b' on the stack as a result. You can then use that algebraic as needed (with b in context as either a global or local variable) with another EVAL to get the final result.

There's other approaches, of course, that simply depend on your workflow. It's a bit unclear to me what the sequence of operations would be for your data entry with something like you've described. You could, for example, prompt for data entry using something like INPUT if you want it to be more interactive, or simply place the variables on the stack before running the program. If the latter is desired, simply place b and a (in that order) on the stack, then run your original program with an EVAL inserted strategically:

Code:

\<< \-> a
  \<<
    \<< \-> b
      \<< a b +
      \>>
      EVAL
    \>>
  \>>
\>>

The gist of it is that, in your original code, local 'a' becomes out-of-scope as soon as that penultimate \>> is encountered. This happens when you first run the program, so any subsequent reference to 'a' is invalid.

[Thomas Klemm]

I was goofing around with a filter I could use with DOSUBS to remove all multiples of a number n.
So I tried to write a program that creates it based on that number as input.

Since that didn't work, I moved this part into a program that does it:

Code:

\<< \-> p n
  \<< p
    \<< \-> k
      \<<
        IF k n == k n MOD OR
        THEN k
        END
      \>>
    \>> DOSUBS
  \>>
\>>

Let's say we call this program SIEVE.
Then we start with a list of numbers:

K ENTER
ENTER
2 887 1 SEQ

{ 2 3 4 5 6 7 8 9 10 … 887 }

Now we can remove all multiples of primes with:

2 SIEVE
{ 2 3 5 7 9 11 13 15 17 … 887 }

3 SIEVE
{ 2 3 5 7 11 13 17 19 23 … 887 }

5 SIEVE
{ 2 3 5 7 11 13 17 19 23 … 887 }

Just continue with the next prime in the list.
…
We can stop at \(31\) since \(31^2 > 887\).

31 SIEVE
{ 2 3 5 7 11 13 17 19 23 … 887 }

This list of primes can then be reversed and transformed into an array:

[ 887 883 881 877 … 7 5 3 2 ]

It is the input for the following program:

Code:

\<< PROOT OBJ\-> OBJ\-> DROP \->LIST
  ABS
  :: MIN DTAG STREAM
\>>

.806513599261

---

Thanks for your reply and your suggestions.
As you can see I could still solve the problem.
I was just wondering if maybe I missed an obvious solution.

[John Keith]

Maybe I'm missing something, but wouldn't something like this be simpler for SIEVE?

Code:


\<< \-> p
  \<< 1
    \<< DUP p MOD OVER p SAME OR NOT DROPN
    \>> DOLIST
  \>>
\>>

[John Keith]

Since the object of your program was to solve Valentin's ROOT challenge, here is a version of the complete program for the 50g with ListExt and LSORT.

Code:


\<< 2 :: NEXTPRIME
    { I\->R 887. \<= } LWHL
    :: I\->R LMAP REV OBJ\-> \->ARRY
    PROOT OBJ\-> OBJ\-> DROP \->LIST
    :: ABS LMAP LSORT HEAD
\>>

Takes 635 seconds on my 50g.

My apologies for hijacking your thread, your original question about closure is interesting to me as well.

[Thomas Klemm]

(11-19-2022 08:53 PM)John Keith Wrote:  Maybe I'm missing something, but wouldn't something like this be simpler for SIEVE?

What exactly do you consider simpler?

• stack vs. local variables
• DUP … NOT DROPN vs. IF … THEN k END
• SAME vs. ==
• DOLIST vs. DOSUBS
  

From my perspective both programs are on about the same level of complexity.
First I was a bit puzzled by your program as it uses p instead of n for the number while I used p for the list of primes.

(11-19-2022 09:50 PM)John Keith Wrote:  Takes 635 seconds on my 50g.

The 2nd part (i.e. after the list of prime numbers is created) takes maybe 2-3 seconds with an emulator on a slightly outdated smartphone.

We've come a long way …

(11-19-2022 09:50 PM)John Keith Wrote:  My apologies for hijacking your thread

No worries, I do this all the time.

---

(11-19-2022 09:50 PM)John Keith Wrote:  

Code:

OBJ\-> OBJ\-> DROP \->LIST

Couldn't we use AXL instead?

(11-19-2022 09:50 PM)John Keith Wrote:  

Code:

:: ABS LMAP

Doesn't ABS work on a list with an HP-50g?

(11-19-2022 09:50 PM)John Keith Wrote:  

Code:

LSORT HEAD

Using MAX on a list is \(\mathcal{O}(n)\) while LSORT is probably \(\mathcal{O}(n\log{}n)\).
But I don't think it matters in this case.

[John Keith]

A few explanatory notes for my programs:

Either DOLIST and DOSUBS will work in this case, and I probably should have used DOSUBS since it is usually a bit faster than DOLIST.

SAME is faster than ==.

AXL creates a symbolic array. I guessed that a symbolic array would be slower for PROOT but I did not actually test it.

All arithmetic functions are listable on the 50g but using the ListExt function LMAP is faster in almost all cases.

LSORT is incredibly fast, and LSORT HEAD is significantly faster than STREAM.

I am aware that emulators are much faster than physical calculators but I posted the timing for the physical calculator for comparison, since emulator speed is dependent on which emulator is used and what system it runs on.

[Thomas Klemm]

Thank you for your explanations.
I can always learn something from you all.

[Albert Chan]

(11-20-2022 02:29 AM)Thomas Klemm Wrote:  Using MAX on a list is \(\mathcal{O}(n)\) while LSORT is probably \(\mathcal{O}(n\log{}n)\).
But I don't think it matters in this case.

I think the bottleneck is PROOT. What is its time complexity?
For example, below trick will reduce primes needed. How much time will it save?

Primes grow slower than any geometric series. Asymptotically, p_n ≈ n*ln(n)

Let M = minimum absolute root function

M(2+3x+5x^2+...+887*x^153) ≈ M((2+3x+5x^2+...+683*x^123) + 683*x^124/(1-x))

Last term assumed primes stop growing after p₁₂₄ = 683, thus the factor 1/(1-x)
Multiply by (1-x), we have another polynomial that contains the same min abs root, but with less terms.

2 + (3-2)*x + (5-3)*x^2 + (7-5)*x^3 + ... + (683-677)*x^123

[Thomas Klemm]

I get the following:

.806513599262

And it takes about the same time: 2-3 seconds.

[Albert Chan]

My mistake. It take 125 primes to reach 12 digits accuracy.

XCas> M(n) := Mp(makelist(ithprime,n+1,1,-1));
XCas> Mp(p) := min(abs(proot(p-p[1:]))); // n-degree prime-gap polynomial min abs root

XCas> M(20)        → 0.809455733629
XCas> M(30)        → 0.807108146818
XCas> M(40)        → 0.806549211933
XCas> M(50)        → 0.806513445127
XCas> M(123)      → 0.806513599262
XCas> M(124)      → 0.806513599261
XCas> M(125)      → 0.806513599261
XCas> M(126)      → 0.806513599261