50g System RPL list processing

[Jacob Wall]

In another thread a bit of discussion on code which indirectly involves list processing got me to thinking about how I had implemented my own custom System RPL operations for some specific tasks. NOTE: Used within a library so no type checking included.

1. Instead of ΣLIST, for a list of reals I have a very simple substitution:

Code:

::
  INNERCOMP
  ZERO
  #=casedrop
  %0
  DUP#1=
  caseDROP
  ONE_DO (DO)
  %+
  LOOP
;

2. Multiply corresponding elements of reals in two lists, instead of x*, for example
{ 1. 2. 3. } { 4. 5. 6. } x* = { 4. 10. 18. }

Code:

::
  INNERCOMP
  get1
  INNERCOMP
  get1
  2DUP#=
  NOT
  OVER#0=
  ORcase
  ::
    OVER#2+UNROL
    {}N
    OVER#2+UNROL
    {}N
  ;
  #1+_ONE_DO (DO)
  get1
  INDEX@
  #2+ROLL
  %*
  INDEX@
  #1+UNROLL
  LOOP
  {}N
;

Wondering if anyone had done similar implementations, and if so I'd be curious to compare.

Jacob

[ttw]

I've thought about doing something like this for list processing, but I never did. (I don't know enough about SYS RPL to matter and if the speed really needs to be fast, I just switch over to a computer.

What I wanted was a more useful definition of some of the list operations. For example, I spend too much programming space (if not time) checking for empty lists or lists with one element before doing processing. It makes it tedious to program variable dimension operations. It doesn't matter much except in inner loops where this sometimes takes up 30% of the execution time.

A list sum should return zero on an empty (or non-existent) list or the only element if a single element list (or a single variable is returned.) Similarly for the produce (but here the product of an empty list is one rather than zero.) A scalar should promote up to a list. For that matter, operations on conformable lists-of-lists should work (->Q works but addition doesn't.)

I got around some of the problem by preceding each sum by 0 1 ->List + or 1 1->List +for products. It's not perfect but helps.

I did in User RPL create min and max reduction operators for lists (trivial, for min just use xxxx <<min>> STREAM and similarly for max. To get the range of a list doing the above with max then min then subtracting was much faster than sorting and subtracting the first element from the last (or sorting, doing a delta list followed by a sum list).

[Jacob Wall]

(06-21-2014 02:13 AM)ttw Wrote:  ... I spend too much programming space (if not time) checking for empty lists or lists with one element before doing processing. It makes it tedious to program variable dimension operations. It doesn't matter much except in inner loops where this sometimes takes up 30% of the execution time.

True, the System RPL checks, which are required, do add execution time, however given the circumstances I think they are necessary, and also I admit I added some of those cases in my post to illustrate some of the possible situations that can arise. With System RPL you are left to ensure that what you provide as input for commands is valid, and that is what makes the language so appealing in a customizable sort of way. If you know precisely what the input will be, because you have done quality control prior, then you can really take advantage of avoiding the built-in checks that exist in User RPL.

With respect to list processing, there are no System RPL versions of commands like STREAM or ΣLIST, or even x* on two lists with the same number of elements. I think the reasons are fairly obvious when you think about it, I did however expect some of them when I first learned System RPL. I think it's fantastic that System RPL is included as an available option for programming the 50g and the documentation is also amazing considering the obscurity (IMHO) of the language, but it's definitely not for writing quick and dirty type of programs that take arguments from the stack, again IMHO.

Jacob

[Gilles]

(06-21-2014 02:13 AM)ttw Wrote:  (...)
What I wanted was a more useful definition of some of the list operations. For example, I spend too much programming space (if not time) checking for empty lists or lists with one element before doing processing. It makes it tedious to program variable dimension operations. It doesn't matter much except in inner loops where this sometimes takes up 30% of the execution time.
(...)

Hi TTW

Take a look at "gofer list library". Works perfectly and quickly on 49/50

http://www.musikwissenschaft.uni-mainz.d...GoferLists

http://www.musikwissenschaft.uni-mainz.d...9/hp49.php

Just perfect even if I don't like very much the names of the commands but it's just a matter of habit. I use this library often.

[Claudio L.]

(06-21-2014 02:13 AM)ttw Wrote:  A list sum should return zero on an empty (or non-existent) list or the only element if a single element list (or a single variable is returned.)

I agree with your view. This is one of the improvements that were implemented in newRPL, and it makes things much more consistent. And it doesn't break compatibility, because if you have old code that checks for empty or single-element lists, it will work fine, but if you don't, you'll get the expected result.

(06-21-2014 02:13 AM)ttw Wrote:  Similarly for the produce (but here the product of an empty list is one rather than zero.)

This I don't agree. The summation of an empty list should still give an error, because you don't know that the empty list would contain reals. What if it was a list of strings? The sum of that empty list should return an empty string then (""), but how do you distinguish between an empty list of reals and an empty list of strings?

(06-21-2014 02:13 AM)ttw Wrote:  A scalar should promote up to a list. For that matter, operations on conformable lists-of-lists should work (->Q works but addition doesn't.)

I think scalars need to remain scalars. What I figured for newRPL was like this:

• The four basic operations on lists are defined as element-by-element operations on lists that are of appropriate size. This includes the empty list ({ } { } * ==> { })
• The basic operations between a list and a scalar apply the object to each element of the list ({ 1 2 3 } 1 + ==> { 2 3 4 }, and also the empty list { } 2 * ==> { })
  

Always remember that objects are not necessarily numbers, so { 1 X 3 } 1 + ==> { 2 'X+1' 4 }. If elements are lists, then this case automatically expands to an element-by-element, since { { 1 2 3 } } 1 + ==> { [[{1 2 3} 1 +]] } ==> { { 2 3 4 } }
(I'm using the [[ ]] to mark intermediate evaluation steps that you wouldn't normally see).
If you were to promote numbers to a list, then the operation of:
{ 1 X 3 } 1 +
{ [[1 {1} +]] [[X {1} +]] [[3 {1} +]] }
{ [[{1} {1} +]] [[{2} {1} +]] [[{X}??? {1} +]] }
{ { 2 } { 'X+1' } { 4 } }

I promoted the 1 to a list, then I ended up with a number plus a list, so I had to promote the number too, and when I found the X then what do we do? We don't know that X is a scalar or not, so do we promote it? In this case I did, but I'm not sure I should.
I think it's more natural to get { 2 'X+1' 4 } than { {2} {'X+1'} {4} }
It looks like adding a number to a list ended up transposing it (if you think of a list as a matrix).

Claudio

[Gilles]

Hi Claudio, you must use 'ADD' and not '+' with the 48-50 series for arithmetic usages :

{ 1 2 3} 1 + gives {1 2 3 1}
{1 2 3} 1 ADD gives { 2 3 4}

It's not logical at all ( '+' and 'ADD' should be invert) but I think it was necessary for backward compatibility with the very earliest RPL calcs without parallel processing (28 and 48 SX?) and the bad choice of + for ADD at this time.

Invert '+' and 'ADD' would be logical but you break the backward compatibility.

With Gofer List :

{ } Sum gives 0
{ } Product gives 1

I dont understand your point of view about about "an empty list of reals or an empty list of strings"... From a User RPL point of view an empty list is ... an empty list. . An other choice could be to return NULL or NOVAL ?

[Han]

(10-28-2014 03:56 PM)Gilles Wrote:  I dont understand your point of view about about "an empty list of reals or an empty list of strings"... From a User RPL point of view an empty list is ... an empty list. . An other choice could be to return NULL or NOVAL ?

One can apply a "sum" operation to a list of strings to obtain a single string. If the empty list is a subset of a list of strings, then the "sum" of the list should be a null string and not, say, the number 0. Since there is no way of discerning an empty list as a subset of a set of strings or a subset of real numbers, returning an error should be the appropriate action.

At least that's what I interpreted Claudio to mean.

[Claudio L.]

(10-28-2014 03:56 PM)Gilles Wrote:  It's not logical at all ( '+' and 'ADD' should be invert) but I think it was necessary for backward compatibility with the very earliest RPL calcs without parallel processing (28 and 48 SX?) and the bad choice of + for ADD at this time.

Invert '+' and 'ADD' would be logical but you break the backward compatibility.

I already did for newRPL. In newRPL + behaves as I was showing above (as it should be?).

(10-28-2014 03:56 PM)Gilles Wrote:  With Gofer List :

{ } Sum gives 0
{ } Product gives 1

I dont understand your point of view about about "an empty list of reals or an empty list of strings"... From a User RPL point of view an empty list is ... an empty list. . An other choice could be to return NULL or NOVAL ?

My point exactly. An empty list is an empty list. What makes you think the sum should be a real number 0? why not an empty string? why not a zero vector with 2 components? or 3 components? or a NxN zero matrix?
There's no way of knowing what the list would've contained if it wasn't empty, so the result should be an error, you can't determine what the result should be (it has to be the null vector in the same vector space of a list full of items, be it matrices, vectors, scalars or any other object, but which one?).
returning NULL is about the same as an error (the user has to catch it or prevent this condition or their code will likely fail), except the concept of NULL is not defined in RPL (perhaps should be nil like in LISP?) so it would feel like a weird quirk of just one set of functions, rather than a feature of the language (like nil is in LISP).

[Gilles]

(10-29-2014 12:20 PM)Claudio L. Wrote:  (...)
My point exactly. An empty list is an empty list. What makes you think the sum should be a real number 0? why not an empty string? why not a zero vector with 2 components? or 3 components? or a NxN zero matrix?
There's no way of knowing what the list would've contained if it wasn't empty, so the result should be an error, you can't determine what the result should be (it has to be the null vector in the same vector space of a list full of items, be it matrices, vectors, scalars or any other object, but which one?).
returning NULL is about the same as an error (the user has to catch it or prevent this condition or their code will likely fail), except the concept of NULL is not defined in RPL (perhaps should be nil like in LISP?) so it would feel like a weird quirk of just one set of functions, rather than a feature of the language (like nil is in LISP).

OK Claudio, I agree with you. It's the best option.

I want to say that i was very happy when I discovered the new RPL project RPL still alive !

[Marcus von Cube]

(10-29-2014 12:20 PM)Claudio L. Wrote:  returning NULL is about the same as an error (the user has to catch it or prevent this condition or their code will likely fail), except the concept of NULL is not defined in RPL (perhaps should be nil like in LISP?) so it would feel like a weird quirk of just one set of functions, rather than a feature of the language (like nil is in LISP).

Why not define two generic objects nil and unit which behave properly when used in further calculations, i. e. like zero and one when combined with numbers, like an empty string and and error when combined with strings, and so forth?

[Claudio L.]

(10-31-2014 08:25 AM)Marcus von Cube Wrote:  Why not define two generic objects nil and unit which behave properly when used in further calculations, i. e. like zero and one when combined with numbers, like an empty string and and error when combined with strings, and so forth?

Interesting idea. There's a case where I don't quite understand how to proceed:
Let's say we have a program that does the sum of a list of 2x2 matrices, then multiplies that by a 2x4 matrix for a 2x4 result.
If the list happens to be empty, the result would be nil, and when multiplied by a 2x4 matrix, how do we know that nil was a scalar value, or a Nx2 matrix? We know it has to be Nx2 to be able to be multiplied, but we can't figure out N, so what should be the size of the result?

[Han]

(10-31-2014 12:23 PM)Claudio L. Wrote:  

(10-31-2014 08:25 AM)Marcus von Cube Wrote:  Why not define two generic objects nil and unit which behave properly when used in further calculations, i. e. like zero and one when combined with numbers, like an empty string and and error when combined with strings, and so forth?

Interesting idea. There's a case where I don't quite understand how to proceed:
Let's say we have a program that does the sum of a list of 2x2 matrices, then multiplies that by a 2x4 matrix for a 2x4 result.
If the list happens to be empty, the result would be nil, and when multiplied by a 2x4 matrix, how do we know that nil was a scalar value, or a Nx2 matrix? We know it has to be Nx2 to be able to be multiplied, but we can't figure out N, so what should be the size of the result?

Shouldn't the result be nil as well? Naively speaking, "addition" of \( X \) with nil should return \( X \) whereas "multiplication" of \( X \) with nil should return nil. I don't think it makes any sense to have any operation on ambiguous arguments return anything un-ambiguous.

[Claudio L.]

(10-31-2014 02:15 PM)Han Wrote:  Shouldn't the result be nil as well? Naively speaking, "addition" of \( X \) with nil should return \( X \) whereas "multiplication" of \( X \) with nil should return nil. I don't think it makes any sense to have any operation on ambiguous arguments return anything un-ambiguous.

I thought he meant restoring the zero value when nil is operated with another object (when we "know" what nil is supposed to mean). If we use "nil operated with anything = nil", then nil becomes a cancer that spreads through the stack eating all your results, and you don't notice anything until much later, making it difficult to debug your code. I'd rather get an error then, at least it tells me where the problem originated in the first place.

[Marcus von Cube]

The behavior of nil and one should be that of 0 and 1 for numbers:

nil + some object = some object
nil * some object = nil
one * some object = some object

This works only if + and * are defined for some object. If some object is a number, one is 1 and can also be used in addition.

[Claudio L.]

(10-31-2014 08:53 PM)Marcus von Cube Wrote:  The behavior of nil and one should be that of 0 and 1 for numbers:

nil + some object = some object
nil * some object = nil
one * some object = some object

This works only if + and * are defined for some object. If some object is a number, one is 1 and can also be used in addition.

That makes more sense. Still have a few extra cases to consider:
one + some object = ??? trivial for numbers, I'm not sure for other object types.
one + one = ??? (we need to define two??)
one + nil = one
one * nil = nil
one * one = one
nil * nil = nil
nil + nil = nil
Subtraction cases are trivial, division is not so trivial, though is not defined for most non-numeric objects:
nil / some object = nil
some object / nil = error: Divide by zero
one / some object = INV(some object) (assuming INV is defined for the object)
some object / one = some object

[Gilles]

Few thoughts after Claudio's explanations

1/

{6} ΣLIST --> 6
{"E"} ΣLIST --> "E"
{'a'} ΣLIST --> 'a'

idea is : 0+Value(s) -> Value (or ""+value(s) for string)

-----
{6} ΠLIST returns 6
{'a' } ΠLIST returns 'a'

idea is : 1*Value(s) -> value

------
{} ΣLIST returns "Error :invalid dimension"
{} ΠLIST returns "Error :invalid dimension" (or '?' ,see below, because applies only on number/algebraic)
{} ΔLIST returns "Error :invalid dimension" (or '?', because applies only on number/algebraic)

Idea is :Sum, product, delta of nothing is invalid / undetermined


2/

Note that the 50G use sometimes a '?' value (something like unknown or undetermined algebraic... For examplle lim (x->+oo,SIN(X)) -> ?
Could be interesting in some cases. A kind of NIL for algebraic

50 ? *
gives ?

? SIN
gives ?
etc.

"Résult=" '?' +
gives
"Résult='?'"

3/

You have also the NOVAL wich is a type 19 object. But any attemps to calculate with NOVAL result in an error. By the way "XX=" NOVAL + returns "XX=NOVAL"


4/

Another big problem in RPL list processing is that DOSUBS or DOLIST command can return ... nothing ! whereas an empty list would be far more logical... I think it will be a real progress to change this....

[Claudio L.]

(10-31-2014 10:06 PM)Gilles Wrote:  Another big problem in RPL list processing is that DOSUBS or DOLIST command can return ... nothing ! whereas an empty list would be far more logical... I think it will be a real progress to change this....

I took care of that for newRPL (I think, we need testers to make sure it behaves properly on all cases).
First of all, I don't like the "optional" arguments in these two commands. All arguments are mandatory in newRPL.
And also it always returns a list:

Code:


{ 1 2 3 4 } 1 << DROP >> DOLIST
{ 1 2 3 4 } 1 << DROP >> DOSUBS

returns an empty list.

Claudio

[Claudio L.]

(10-31-2014 10:06 PM)Gilles Wrote:  Note that the 50G use sometimes a '?' value (something like unknown or undetermined algebraic... For examplle lim (x->+oo,SIN(X)) -> ?
Could be interesting in some cases. A kind of NIL for algebraic

I like this idea better than the nil and one and then trying to operate on them. If the result is undetermined, it becomes symbolic, so any attempt to operate on it will return a symbolic with the unevaluated expression. Of course, we could call symbolic 'nil' (or '?' as it already exists) and symbolic 'one', and then we don't need to define any other operations. I think this is more generic, but still doesn't cover all cases, since it won't work for objects that are not accepted inside symbolics, like strings.
'?'+"HELLO" will give an error.
So '?' would have to be a hybrid that behaves like a symbolic when possible and like the nil/one solution proposed above for other objects. Or, we define nil/one and convert them to symbolic for the cases we don't know how to resolve like one+one => 'one+one'.
There doesn't seem to be one consistent solution that covers all cases, other than just issue the error on empty lists.

[Han]

(10-31-2014 07:01 PM)Claudio L. Wrote:  

(10-31-2014 02:15 PM)Han Wrote:  Shouldn't the result be nil as well? Naively speaking, "addition" of \( X \) with nil should return \( X \) whereas "multiplication" of \( X \) with nil should return nil. I don't think it makes any sense to have any operation on ambiguous arguments return anything un-ambiguous.

I thought he meant restoring the zero value when nil is operated with another object (when we "know" what nil is supposed to mean). If we use "nil operated with anything = nil", then nil becomes a cancer that spreads through the stack eating all your results, and you don't notice anything until much later, making it difficult to debug your code. I'd rather get an error then, at least it tells me where the problem originated in the first place.

I think you misread my post. In fact, I'm suggesting almost the same idea as Marcus von Cube -- excluding the notion of "one"

[Han]

(10-31-2014 08:53 PM)Marcus von Cube Wrote:  The behavior of nil and one should be that of 0 and 1 for numbers:

nil + some object = some object
nil * some object = nil
one * some object = some object

This works only if + and * are defined for some object. If some object is a number, one is 1 and can also be used in addition.

I don't understand the point of "one" -- "nil" actually makes sense with respect to empty sets. At what point will you ever use a regular operation and expect an ambiguous "one" ? The notion of "one" is a solution to a problem that does not seem to exist.