Walkthrough of an RPL program for an RPN programmer

[Thomas Klemm]

(04-06-2018 11:59 AM)Maximilian Hohmann Wrote:  I would consider myself a random person in that respect (*), but I have so far failed to understand even a single program written in RPL. I don't know if I really can't understand it or if it is because I don't want to... because whenever I see anything like <<DUP ROT ... I instantly feel the urge to zap it away, just the way I would do with commercial breaks on TV or whenever a hip hop song is played on the radio.

I can give you a walkthrough of the following program for the HP-48G:

(08-18-2018 04:41 PM)Thomas Klemm Wrote:  ( mm dd yyyy -- dow )

Code:

« ROT
  IF DUP 3 <
  THEN 12 + SWAP 1 -
  ELSE SWAP
  END
  DUP 100 MOD
  SWAP 100 / IP
  → q m K J
  « { "Saturday"
      "Sunday"
      "Monday"
      "Tuesday"
      "Wednesday"
      "Thursday"
      "Friday" } 
    q
    m 1 + 2.6 * IP +
    K + K 4 / IP +
    J 4 / IP + J 2 * -
    7 MOD
    1 + GET
  »
»

To make you familiar with the context please read my original post.

Stack Commands

The aforementioned commands DUP, ROT, SWAP are well know among RPN programmers but we use different names:

DUP is ENTER but without disabling stack lift.
ROT is R↑ but for a 3-level stack.
SWAP is X<>Y.
OVER is RCL Y if you know the HP-41.
DROP is something like CLX followed by R↓.

All these commands stem from Forth so it's not something specific to RPL.

Stack Diagrams

There's an infinite stack (well not really) with RPL. This is nice: we can push stuff on it and don't have to care until later. However we don't have automatic copy of T. The stack may be empty. This is what we get with the DEL command.

You may be familiar with stack diagrams that show the state of the stack with each command.
For instance to calculate: \(3\times(4 + 5)\)

Key    X       Y       Z       T
3      3
ENTER  3       3
4      4       3
ENTER  4       4       3
5      5       4       3
+      9       3
×      27


But with Forth the order of the stack is reversed in diagrams. The top of stack is the rightmost element. But that's exactly the order you enter the data.

So on a HP-48G you can use the ENTER key to separate numbers:

3
ENTER  : 3
4
ENTER  : 3 4
5
ENTER  : 3 4 5
+      : 3 9
×      : 27


Or then you can use a space to separate numbers:

3 4 5
+      : 3 9
×      : 27


Input

( mm dd yyyy -- dow )

This is just the order we fill the stack before calling the function that returns dow, the day of week.

For today (i.e. August, 18th 2018) we would use:

8
ENTER
18
ENTER
2018


Or then:

8 18 2018


In both cases we end up with the following stack diagram:

8 18 2018


Initialisation

We have to modify the month and year in case of January and February and then calculate both the year of the century and the zero-based century.

First we bring the month mm to the top of the stack:

Code:

ROT     @ dd yyyy mm

Now we check if that value is smaller than 3.
Contrary to RPN the commands always consume the parameters even in case of comparisons.
Since we need the value later we have to duplicate it first:

Code:

IF DUP 3 <

Here are the steps in slow motion:

Code:

IF      @ dd yyyy mm
DUP     @ dd yyyy mm mm
3       @ dd yyyy mm mm 3
<       @ dd yyyy mm 0|1

The result (either 0 or 1) is then consumed by the IF statement and we branch to the correct case:

Code:

THEN 12 + SWAP 1 -

Let's split that up into multiple lines:

Code:

THEN    @ dd yyyy mm
12 +    @ dd yyyy mm+12
SWAP    @ dd mm+12 yyyy
1 -     @ dd mm+12 yyyy-1

The other case is much simpler:

Code:

ELSE    @ dd yyyy mm
SWAP    @ dd mm yyyy

And then we finish the IF statement with:

Code:

END

We just have to make sure that at the end of both branches the order of the elements is the same.

year of the century

For this we just have to calculate: yyyy MOD 100.
But since we need that value again later we better make a copy beforehand:

Code:

DUP     @ dd mm YYyy YYyy
100     @ dd mm YYyy YYyy 100
MOD     @ dd mm YYyy yy

zero-based century

We take the integer part of yyyy after dividing it by 100:

Code:

SWAP    @ dd mm yy YYyy
100     @ dd mm yy YYyy 100
/       @ dd mm yy YY.yy
IP      @ dd mm yy YY

Local Variables

The next line creates a new context for local variables.
They are assigned in the same order that they appear on the stack.

Code:

  → q m K J

Thus we end up with:

q = dd
m = mm
K = yy
J = YY

The context is marked with these guillemets:

Code:

«
…
»

This step consumed the stack completely so it's now empty.

List of Weekdays

We push that list now but we need it only later:

Code:

{ "Saturday"
"Sunday"
"Monday"
"Tuesday"
"Wednesday"
"Thursday"
"Friday" }

Calculating the Zeller's congruence

The next steps should be easy to understand since it's exactly how you'd calculate the expression on any RPN calculator:

\(h=\left(q+\left\lfloor {\frac {13(m+1)}{5}}\right\rfloor +K+\left\lfloor {\frac {K}{4}}\right\rfloor +\left\lfloor {\frac {J}{4}}\right\rfloor -2J\right){\bmod {7}}\)

Code:

q
m 1 + 2.6 * IP +
K + 
K 4 / IP +
J 4 / IP + 
J 2 * -
7 MOD

This leaves us with the following stack diagram:

weekdays h

Mapping to Day of Week

Since the index of lists start with 1 we have to adjust that:

Code:

1 + GET

I assume that you can figure out by yourself what GET does.

Next Steps

Debugger

I highly recommend to run the program in the debugger and single step through it. So you can follow the changes of the stack with each step.

Control Structures

There are other control structures that you could explore: CASE, START, FOR, DO, WHILE

List Operations

There's a good reason this language has Lisp in it's acronym. It's worth to make you familiar with lists and their powerful operations.

It allows to calculate Gauss's shoelace formula with just a few lines:

Code:

«
  DUP HEAD +
  2 « CROSS » DOSUBS
  ∑LIST ABS 2 /
»

Kind regards
Thomas

[Albert Chan]

Thank you Thomas, great post.

Just when I thought I can read RPL code, you showed the shoelace formula.

Code:

«
  DUP HEAD +
  2 « CROSS » DOSUBS
  ∑LIST ABS 2 /
»

Perhaps an explanation of how that work ?

For example, why CROSS need the << ... >> ?

[rprosperi]

(08-19-2018 12:17 AM)Albert Chan Wrote:  For example, why CROSS need the << ... >> ?

DOSUBS requires a program as an argument.

DOSUBS applies the immediately preceding program (here, it is << CROSS >>) to the list and parameter 2 just in front.

See p. 3-66 in the 50g AUR for an explanation of DOSUBS, a remarkably powerful command, though not always intuitive, even if you can think in RPL.

A bit advanced for teaching RPL, but the brevity of the program indeed shows the power of RPL and lists.

BTW - Bravo Thomas on an epic and well-done post. Alas, it's probably wasted for Max, as he averts his eyes when he sees RPL, but obviously useful for other folks (me included).

[Thomas Klemm]

(08-19-2018 12:17 AM)Albert Chan Wrote:  Perhaps an explanation of how that work ?

Here's a video by Mathologer Burkard Polster:
Gauss's magic shoelace area formula and its calculus companion

Commands
This is a short description of the commands from the user's guide.

DUP
Duplicates object (x).

HEAD
Gets the first element from a list (x).

CROSS
Cross product of two vectors (y ⨯ x).

DOSUBS
Executes a program or command (x) on a specified number of elements at a time (y) within a list (z).

ΣLIST
Adds together all of the elements in a list (x).

ABS
Absolute value of an object (x).

« and »
These mark the begin and end of a code object.


Example
These are the vertices of the cat from the video:

List of Vertices

Code:

{
[ 4 4 ]
[ 0 1 ]
[ -2 5 ]
[ -6 0 ]
[ -1 -4 ]
[ 5 -2 ]
}

They can be entered as a single line:

Enter the List

Code:

{[4 4][0 1][-2 5][-6 0][-1 -4][5 -2]}

Step by Step
Let's go through the program step by step and list the content of the stack.

List of Vertices

Code:

1: {[4 4][0 1][-2 5][-6 0][-1 -4][5 -2]}

DUP

Code:

2: {[4 4][0 1][-2 5][-6 0][-1 -4][5 -2]}
1: {[4 4][0 1][-2 5][-6 0][-1 -4][5 -2]}

HEAD

Code:

2: {[4 4][0 1][-2 5][-6 0][-1 -4][5 -2]}
1: [4 4]

+

Code:

1: {[4 4][0 1][-2 5][-6 0][-1 -4][5 -2][4 4]}

2

Code:

2: {[4 4][0 1][-2 5][-6 0][-1 -4][5 -2][4 4]}
1: 2

« CROSS »

Code:

3: {[4 4][0 1][-2 5][-6 0][-1 -4][5 -2][4 4]}
2: 2
1: « CROSS »

DOSUBS

Code:

1: {[0 0 4][0 0 2][0 0 30][0 0 24][0 0 22][0 0 28]}

ΣLIST

Code:

1: [0 0 110]

ABS

Code:

1: 110

2

Code:

2: 110
1: 2

/

Code:

1: 55

Python

I'm not aware of a way to partition a list in Python. However we can use map with an additional copy of the list that is rotated by one place:

Code:

def cross(A, B):
    return A[0] * B[1] - A[1] * B[0]

def area(P):
    s = map(cross, P, P[1:]+P[0:1])
    return abs(sum(s)) / 2

Example:

Code:

>>> cat = [(4,4), (0,1), (-2,5), (-6,0), (-1,-4), (5,-2)]
>>> area(cat)
55.0

Clojure

Code:

(defn cross [[[a b] [c d]]]
    (- (* a d) (* b c)))

(defn area [polygon]
    (/ (reduce + (map cross (partition 2 1 [(first polygon)] polygon))) 2))

We can make that area function a bit more readable using threading macros -> and ->>:

Code:

(defn area [polygon]
    (->
    (->> polygon
    (partition 2 1 [(first polygon)])
    (map cross)
    (reduce +))
    (/ 2)))

Example:

Code:

user=> (def polygon [[4 4][0 1][-2 5][-6 0][-1 -4][5 -2]])
#'user/polygon
user=> (area polygon)
55

SQL

I haven't tried but DOSUB and partition remind me of window functions in SQL.

Kind regards
Thomas

[Albert Chan]

(08-19-2018 10:15 AM)Thomas Klemm Wrote:  I'm not aware of a way to partition a list in Python.
However we can use map with an additional copy of the list that is rotated by one place:

You mean like this ?

Code:

def partition(lst, n, step=0):    # no step = no overlap
    return [ lst[i-n:i] for i in range(n, len(lst) + 1, step or n) ]

Perhaps we do not need partitioned list, map, and sum. Just do it all at once.

Code:

def cross_and_sum(((x, y), sum), v):
    return v, sum + (x * v[1] - y * v[0])

def area(v):
    'Area of polygon using shoelace formula'
    _, s = reduce(cross_and_sum, v, (v[-1], 0))
    return 0.5 * abs(s)

[Thomas Klemm]

(08-19-2018 01:13 PM)Albert Chan Wrote:  You mean like this ?

Except that the Clojure implementation provides more:

Quote:(partition n coll) (partition n step coll) (partition n step pad coll)

Returns a lazy sequence of lists of n items each, at offsets step
apart. If step is not supplied, defaults to n, i.e. the partitions
do not overlap. If a pad collection is supplied, use its elements as
necessary to complete last partition upto n items. In case there are
not enough padding elements, return a partition with less than n items.

What I meant is that I wasn't aware of a built-in function similar to that in Python.
Of course we can always craft something by ourselves if in need as you demonstrated.

Quote:Perhaps we do not need partitioned list, map, and sum.

The point of using examples in Python or Clojure was to show code similar to the RPL program.
That might help someone to understand how DOSUBS works if they are familiar with either language.

Cheers
Thomas

[Albert Chan]

(08-19-2018 10:15 AM)Thomas Klemm Wrote:  « and »
These mark the begin and end of a code object.

I am a bit unclear about code object << ... >>

A program is an object, so it need a set of << ... >>
CROSS need to be an object for DOSUBS to work.

But, going back to day-of-the-week code, after -> q m K J, why create a code object ?

How to decide where to add << ... >> ?

[rprosperi]

(08-19-2018 03:13 PM)Albert Chan Wrote:  But, going back to day-of-the-week code, after -> q m K J, why create a code object ?

The scope of local variables (here, declared by "-> q m K J") is limited to the program which immediately follows their declaration.

As it seems you'd like to learn RPL, you should definitely read Bill Wickes's book "HP-48 Insights Part I (48G/GX Edition)", which is available as part of the MoHPC Document Set, available here. An incredible value that includes hundreds of manuals, books, brochures, HP publications, etc., the small price also helps to pay for this great website.

[Thomas Klemm]

(08-19-2018 03:13 PM)Albert Chan Wrote:  But, going back to day-of-the-week code, after -> q m K J, why create a code object ?

That's just the syntax used to create a context for local variables.

All of these variants aren't valid syntax and won't compile:

Code:

« →
»

Code:

« → a
»

Code:

« → «
  »
»

You actually need all of this:

Code:

« → a «
  »
»

This doesn't create a code object on the stack as « CROSS » did.
It just indicates the scope of the local variables using the same guillemets « and ».

HTH
Thomas

[Thomas Klemm]

(08-19-2018 03:13 PM)Albert Chan Wrote:  How to decide where to add << ... >> ?

The guillemets « … » around the code postpone its execution.
That's similar to quote (or ') in Lisp.

We have to that or then the CROSS command would be executed immediately.
But we want DOSUBS to execute it.

In Javascript parlance we pass it as a callback.
Or simply as a function.

So yes, RPL is a functional programming language.

Cheers
Thomas

[Albert Chan]

Hi, rprosperi and Thomas Klemm:

Thank you both. I think I get the gist of it.

RPL scoping rule have to think in reverse too.

For Lua, we open the scope *before* local variables: do local x, y, z = 1, 2, 3; ... ; end

For RPL, above is done in reverse: -> x y z << ... >>

Also, << ... >> have double meaning.
If preceded by locals setup, it open the scope.
If not, it turn whatever inside, as code object.

Double meaning also apply with +
If 2 items on stack is number, it replace them with their sum
If 2 items on stack is list, it replace them with concatenated list (just like Python)

Possibly even more than double meaning for +, say for string arguments ...

[John Keith]

(08-19-2018 03:29 PM)rprosperi Wrote:  The scope of local variables (here, declared by "-> q m K J") is limited to the program which immediately follows their declaration.

As it seems you'd like to learn RPL, you should definitely read Bill Wickes's book "HP-48 Insights Part I (48G/GX Edition)", which is available as part of the MoHPC Document Set, available here. An incredible value that includes hundreds of manuals, books, brochures, HP publications, etc., the small price also helps to pay for this great website.

I strongly second Bob's recommendations, the Wickes book and of course the Museum USB stick.

Also in reference to the above discussions, this bit of code

Code:


 → a «
  »

is referred to in the HP manuals as a "local variable structure". The description of -> (the right arrow character) in the AUR is worth reading as well.

John

[Vtile]

There is so many exceptions in RPL when you go above the basics, partly because in 50G there is 2700+ in build commands you can play with.

Code:

« → a 'a+a' »

Will also work, but here the local variable is used in algebraic object.

[DavidM]

(08-19-2018 05:15 PM)Vtile Wrote:  

Code:

« → a 'a+a' »

Will also work, but here the local variable is used in algebraic object.

I don't actually think of this as an exception, but rather as overloaded functionality. As Albert has (correctly) noted, a single RPL operator (such as "+") can have multiple overloaded uses as defined by the types of arguments it is given. "→" also has overloaded functionality. In particular, it will execute either a program object («...») or an algebraic object ('...') with the provided locals. The action is essentially the same in both cases:

1) Assign as many stack items to local variable IDs as are indicated
2) Execute the final object
3) Release the most recently assigned local variables

The "→" operator is special (though not unique) in that it not only requires arguments on the stack, but it also requires objects following it in the program stream to be executed properly. The true "arguments" are already on the stack before it executes, and they end up being the values assigned to the local variables which follow the "→" operator in the program stream. The final object needed for the operator, though, is the single object which will be executed while those local variables are defined. So the «...» structure following the "→" operator is in reality still a single (encapsulated) object, not some exceptional version of the «» brackets.

Thinking of the "→" structure in this way makes it easier to understand what happens when local variable constructs are nested.

[Albert Chan]

(08-19-2018 06:31 PM)DavidM Wrote:  "→" also has overloaded functionality.
In particular, it will execute either a program object («...») or an algebraic object ('...') with the provided locals.

Wait a second.

Expression -> x y z << ... >>, the overloaded symbol were ->, not << ... >> ?

<< ... >> still means code object, execution delayed until the locals are setup.

Now it make sense.

Otherwise, we created the locals before opening the scope, which make no sense.

[DavidM]

(08-19-2018 07:02 PM)Albert Chan Wrote:  Expression -> x y z << ... >>, the overloaded symbol were ->, not << ... >> ?

I would show the syntax a different way:

Code:

on the stack prior to execution:
n: <arg1>
n-1: <arg2>
...
1: <argn>

syntax of "→":
→    <local_ID_1>...<local_ID_n>    «...» | '...'

The → operator requires the same quantity of arguments already present on the stack as there are local IDs between it and the object to execute. "→" is overloaded to accept either a code object or an algebraic object as the final element in its syntactical structure. By definition, "→" executes that final object within the context of the locals that it "owns". After that final object is executed, the supplied locals are released by "→", and execution continues with the next item in the program stream after the executable object (which could be anything, including a '»' that would signal the end of the current program stream).

[Claudio L.]

(08-19-2018 07:02 PM)Albert Chan Wrote:  Wait a second.

Expression -> x y z << ... >>, the overloaded symbol were ->, not << ... >> ?

<< ... >> still means code object, execution delayed until the locals are setup.

Now it make sense.

Otherwise, we created the locals before opening the scope, which make no sense.

I think the easiest way to understand it (at least for me) is as an unnamed (lambda) function arguments declaration.

-> x y z << ... >>

is equivalent to:

function(x,y,z) { ... }

and it does the same thing, takes "external" values (from the stack), assigns them local names then executes what's in scope. Defining locals out of the scope wouldn't make sense, but arguments on the other hand, are usually declared out of the scope.
And this is actually consistent with using an algebraic object as the scope, more like a mathematical function declaration:
f(x,y,z) '...'

In my RPL head this is how I "see" it.

[pier4r]

Thanks for the contributions you all

[Maximilian Hohmann]

Hello!

As I am quoted in the original and really excellent (!) post of this thread I need to comment quickly... (have been away for work last week and couldn't do it earlier).

Having read the posting and the replies shows me several things:

1. RPL is not RPL, not even within HP. While I was away last week the postman brought me yet another HP-19BII (with an uncracked battery door) which supposedly is RPL based. The examples from above which I tried on that calculator did not work. Especially not replacing the "Enter" key with blank spaces between the numbers which I had never heard about before. But then that calculator is only RPL internally with an RPN user interface. Following the thread however I read that there are really siginificant differences between RPL on various HP calculators.
2. RPL experts are not RPL experts, at least every one seems to use it in his own special way. Which makes RPL a very versatile tool but even harder to understand for laypersons. Because not only does one need a good understanding of the underlying principle/paradigm but one must be able to follow the thought patterns of the programmer. And all based on some extremely abbreviated and cryptic syntax. The best example for that is the expression « → a 'a+a' » of which, even after having read the whole thread, I still don't have the faintest idea what it might do.
3. RPL is definitely not for the occasional user.
4. Some RPL implementations are exrtemely powerful. 2500 built in functions. Impressive! But who remembers all those when he needs them? I certainly couldn't and the manuals don't make it very easy to find them either. There must be a reason why RISC has become the standard with microprocessors now: Keep it simple and keep the users in the loop.

Thanks for that great thread!
Max (still not convinced that RPL will ever be my thing)

[Claudio L.]

(08-25-2018 01:35 PM)Maximilian Hohmann Wrote:  Hello!

As I am quoted in the original and really excellent (!) post of this thread I need to comment quickly... (have been away for work last week and couldn't do it earlier).

Having read the posting and the replies shows me several things:

1. RPL is not RPL, not even within HP. While I was away last week the postman brought me yet another HP-19BII (with an uncracked battery door) which supposedly is RPL based. The examples from above which I tried on that calculator did not work. Especially not replacing the "Enter" key with blank spaces between the numbers which I had never heard about before. But then that calculator is only RPL internally with an RPN user interface. Following the thread however I read that there are really siginificant differences between RPL on various HP calculators.

The RPL engine and basic language is the same on those various HP calculators. The libraries surrounding the RPL core are not: some models have a more complete set of commands than others. The UI can be anything you want, much like Ubuntu can have Gnome, KDE, XFCE, etc. running on top. It's still the same, just different UI, and different libraries.

(08-25-2018 01:35 PM)Maximilian Hohmann Wrote:  2. RPL experts are not RPL experts, at least every one seems to use it in his own special way. Which makes RPL a very versatile tool but even harder to understand for laypersons. Because not only does one need a good understanding of the underlying principle/paradigm but one must be able to follow the thought patterns of the programmer. And all based on some extremely abbreviated and cryptic syntax. The best example for that is the expression « → a 'a+a' » of which, even after having read the whole thread, I still don't have the faintest idea what it might do.

This is true for many languages! I consider myself seasoned in C++, and I still have no clue how those templates and meta-templates could possibly work. But I don't blame the language, and keep coding in C++ "in my own way".

(08-25-2018 01:35 PM)Maximilian Hohmann Wrote:  3. RPL is definitely not for the occasional user.
4. Some RPL implementations are exrtemely powerful. 2500 built in functions. Impressive! But who remembers all those when he needs them? I certainly couldn't and the manuals don't make it very easy to find them either. There must be a reason why RISC has become the standard with microprocessors now: Keep it simple and keep the users in the loop.

And this is also true for many other languages! Knowing C or C++ doesn't mean you can code a simple hello world with Qt, or MFC, or GTK, or ...[name your tookit here]...
All those toolkits are massive and impressive, and equally difficult to master. I agree manuals don't help much, but that's also true for the aforementioned toolkits. There's more tutorials just because there's more people using them, but that's it.

I love that to learn Lua you need to read only 36 pages of the manual to fully understand and master the language. It's that simple. But then when you want to code anything serious, you use libraries with hundreds of API functions you need to learn on your own, so it ends up being the same as all other languages.