 Reflections, from Late Latin reflexio, on the programming are inspired by work on the Album of Algorithms and Techniques for Standard Rexx.

14th September 2001

I sent the first version of following article to comp.lang.rexx on 13th September

SHORT CIRCUITING IN REXX?

1. Reason for my reflexion

Walter Pachl from Vienna found the error in the HEAPSORT implementation, which was included in my Album of algorithms and techniques:

 HEAPSORT: procedure expose A. parse arg N do I = N % 2 to 1 by -1   call SIFT I, N end do I = N to 2 by -1   W = A.1; A.1 = A.I; A.I = W   call SIFT 1, I - 1 end return SIFT: procedure expose A. parse arg L, R I = L; W = A.I; J = 2 * I Jp1 = J + 1 if J < R & A.J < A.Jp1 then J = Jp1 do while J <= R & W < A.J   A.I = A.J; I = J; J = 2 * I   Jp1 = J + 1   if J < R & A.J < A.Jp1 then J = Jp1 end A.I = W return

The code of the SIFT procedure is invalid. It will cause the NOVALUE condition in course evaluation of the J<R & A.J<A.Jp1 expression for R=N and J=N because variable A.Jp1, where Jp1=N+1, is uninitialized for the array A.1,...,A.N I returned to the original version of Niklaus Wirth's program in the book Algorithms and data structure, Prentice Hall, 1986. This is almost the same code but Wirth's program is written in Modula and there is the difference between Rexx and Modula in evaluation of expressions with logical operators AND and OR. In Rexx for A & B, A | B both operands are always evaluated. In Modula this expressions are evaluated in short circuit fashion, which means the second operand may not be evaluated if the first operand can determine the outcome.

2. Normal logical AND, OR and short circuit logical AND, OR

2.1: According ANSI X3J18-199X 7.4.8 the expression lhs & rhs ("&" is the normal logical AND operator) is evaluated

 if lhs \== '0' then   if lhs \== '1' then call #Syntax_error if rhs \== '0' then   if rhs \== '1' then call #Syntax_error Value='0' if lhs == '1' then   if rhs == '1' then Value='1'

2.2: Likewise lhs | rhs ("|" is the normal logical OR operator) is evaluated

 if lhs \== '0' then   if lhs \== '1' then call #Syntax_error if rhs \== '0' then   if rhs \== '1' then call #Syntax_error Value='1' if lhs == '0' then   if rhs == '0' then Value='0'

For evaluation of AND or OR we can use another, more effective algorithm. I propose to denote this short circuit AND, OR operators as "&*" and "|*". The asterisk means: "zero or one next operand will evaluated".

2.3: Then lhs &* rhs is evaluated

 if lhs \== '0' then   if lhs \== '1' then call #Syntax_error Value=lhs if Value then do   if rhs \== '0' then     if rhs \== '1' then call #Syntax_error   Value=rhs end

2.4: And likewise lhs |* rhs is evaluated

 if lhs \== '0' then   if lhs \== '1' then call #Syntax_error Value=lhs if \lhs then do   if rhs \== '0' then     if rhs \== '1' then call #Syntax_error   Value=rhs end

3. Short curcuit AND, OR operators in present-day classic Rexx

Suppose that {S} is a (long) sequence of statements then equivalent code to code with "&*" and "|*" follows (statements written on one row).

3.1: if A &* B then {S} (is equivalent to)
if A then if B then {S}

3.2: do while A &* B; {S}; end (is equivalent to)
do while A; if B then {S}; end

3.3: if A |* B then {S} (is equivalent to)
3.3.1:       do 1; if \A then if \B then leave; {S}; end
or 3.3.2:     do 1; if \A then if \B then iterate; {S}; end
or 3.3.3:     if A then {S}; else if B then {S}
or 3.3.4:     if A then call SUB; else if B then call SUB
where the SUB subroutine is
SUB: {S}; return

3.4: do while A |* B; {S}; end (is equivalent to)
do forever; if \A then if \B then leave; {S}; end

Review and notes
3.1 and 3.2 are readable; maybe also 3.4. Really problem is 3.3 case. 3.3.1 and 3.3.2 are almost not readable; 3.3.3 is not suitable for often changed {S}. And 3.3.4? - one subroutine into the bargain, it is not elegant ...

4. Good examples of using short circuit AND, OR

4.1: Now it is easy to translate from Modula to Rexx. In case HEAPSORT can be the result optimized, for example, thanks bypassing evaluation of A.J<A.Jp1 when J>=R.

 ... SIFT: procedure expose A. ... if J < R &* A.J < A.Jp1 then J = Jp1 do while J <= R &* W < A.J   ...   if J < R &* A.J < A.Jp1 then J = Jp1 end ...

Generalization:
- Facilitation of a translation of short circuiting from Ada, C, C++, GNU Pascal, Java, JavaScript, Lisp, Modula, Perl, VAX Pascal, VB.Net to Rexx and, of course, vice versa.
- More effective code.

4.2: It gives us a possibility to express short circuiting in clear form. Some typical examples follow

4.2.1 if N <> 0 &* M / N > 0 then ...

4.2.2 if (I = 0) |* (J = 1 / I) then ...

4.2.3

 IsPersonEligibleForThisJob: procedure parse arg Person if AGE(Person) > 18 &* IQTEST() > 138   then do; ...; return 1; end   else do; ...; return 0; end

Note: the IQTEST function is online interactive long-term computerized test.

4.2.4

 IsPersonEligibleForThisJob: procedure parse arg Person if RESULT_IQTEST(Person) > 138 |* IQTEST() > 138   then do; ...; return 1; end   else do; ...; return 0; end

Note: the RESULT_IQTEST function returns "" or a number, a number is result of the last IQ-test.

Generalization:
- More safe code.
- More simple code

5. Good reasons for using of normal logical AND, OR

5.0: Of course, there are enormous amount of perfect working programs with "&" and "|" around world.

5.1: Evaluation both operands can be useful in process debugging.

5.2: There are situations when both operands have to be evaluated. I.e. case when second operand contains side effect. See the following segment of program. This copies part of file Infile behind the line with value String to file Outfile. It may be useful. With "|*" operand it is only an ordinary never ending loop.

 ... do until LINES(Infile) = 0 | LINEIN(Infile) = String end do while LINES(Infile) <> 0   call LINEOUT Outfile, LINEIN(Infile) end ...

6. Conclusion

I found in literature 4 ways of using the logical operators AND, OR in programming languages

6.1 - only the normal logical AND, OR operators which always evaluate both arguments (Rexx, Pascal, Visual Basic, WEbScript)

6.2 - only the short circuit logical AND, OR (JavaScript, C, C++, Lisp, Modula, Perl)

6.3 - the logical AND, OR are either normal or short circuit. It is given by compiler directive (GNU Pascal).

6.4 - the logical normal and the logical short circuit AND, OR operators are used (Ada, VAX Pascal, Java, MATVEC, Octave, VB.Net)

7. Appendix

7.1 Thanks to Walter Pachl for inspiration.

7.2 The collection of articles "Comparing and Assessing Programming Languages Ada, C and Pascal" (editors A.R.Feuer, N.Gehani, Prentice-Hall, 1984) includes example 4.2.1, solution 3.1, the warning of "J<R & A.J<A.Jp1"-type (error in my old HEAPSORT) all in a critique of missing short circuiting in Pascal.

7.3 Martin Lafaix: "Proposals for NetRexx [2000-07-04]"; chapter 5 Short-circuit logical operators - brief suggestion of adding short-circuit logical operators "&&&" and "|||" to NetRexx. It includes solution 3.3.3. BTW why I use "&*" and "|*" instead "&&&" and "|||"? Because "&*", "|*" are mignon ...

7.4 There is very interesting opposite view by Tom Christiansen in

(i.e. arguments against normal logical OR to Perl where only short-circuit logical OR is used)

7.5 Following table shows symbols of logical operators in chosen programming languages:

 operation MATVEC Java VB.Net Ada normal AND .&& & And and normal OR .|| | Or or short circuit AND && && AndAlso and then short circuit OR || || OrElse or else

And there is Mike Cowlishaw's reply in comp.lang.rexx 25 September 2001

Nice analysis. See also the short circuiting approach which I used in NetRexx, at:

Mike Cowlishaw

Let me introduce this material here:

If and when enhancements

The if clause in the if instruction [NRL 80] and the when clause in the select instruction [NRL 108] both have the same form and serve the same purpose, which is to test a value either for being 1 or (for a when clause in a select case construct) being equal to the case expression.

In both if and when clauses multiple expressions may now be specified, separated by commas. These are evaluated in turn from left to right, and if the result of any evaluation is 1 (or equals the case expression) then the test has succeeded and the instruction following the associated then clause is executed.

Note that once an expression evaluation has resulted in a successful test, no further expressions in the clause are evaluated. So, for example, in:

-- assume 'name' is a string
if name=null, name='' then say 'Empty'

then if name does not refer to an object it will compare equal to null and the say instruction will be executed without evaluating the second expression in the if clause.

1st July 2001

P+n trick by Walter Pachl. He sent me mail: ... My versions of your algorithms (SIN) that I did a couple of years ago applied the trick to compute the function to a precision of P+2 when a precision of P was asked for and rounded the result to precision P. I did not do any error analysis --- the +2 was rather chosen heuristically. The following program by Walter Pachl proofs that his technique is useful for the calculation of SIN function (of course, also for COS, LN, SQRT, etc.)

 do P = 30 to 35   call Test P end exit TEST: procedure parse arg P numeric digits P say 'Yours ' SIN(0.6, P) say 'should be ' (SIN(0.6, P + 2) + 0) say ' ' return

More, the program gives different results in different implementations. Hence it follows: First - Pachl's trick is the intelligent technique for debugging and using numerical programs! Secondly - For the SIN function (COS, LN, SQRT, ...) the statements

 numeric digits P say SIN(X, P + N) + 0

give the result with P significant digits for a "sufficient" large N, where 0 <= N.

Examples:
for the SIN function and P = 9:
if X = 0.6 then N has to be 2
if X = 355 then N has to be even 7, because:

 SIN(355, 9) + 0 = -0.000029987 SIN(355,10) + 0 = -0.0000301545 SIN(355,11) + 0 = -0.0000301432200 SIN(355,12) + 0 = -0.0000301443310 SIN(355,13) + 0 = -0.0000301443963 SIN(355,14) + 0 = -0.0000301443526 SIN(355,15) + 0 = -0.0000301443532 SIN(355,16) + 0 = -0.0000301443534 ... SIN(355,99) + 0 = -0.0000301443534

4th March 2001

W. Kavan introduces in his Mathematics Written in Sand the following example:
729**33.5 = 729**(67/2) = (243*3)**(67/2) =
= (3*3*3*3*3*3)**(67/2) = 3**(3*67) = 3**201
But recent hand-held Hewlett-Packard calculators that accept and deliver data to 10 sig. dec. produce two results,
729**33.5 = 7.6841966E95

and

3**201 = 7.968419664E95

REPOWER(729,33.5,10) in version with row:

if P = "" then P = 9; numeric digits P

gives the result 7.96841935E+95. W. Kahan writes: ... here too would have required that intermediate calculations be carried to more than the 13 sig. dec. Hence I changed the code of the REPOWER function:

if P = "" then P = 9; numeric digits P

The following program

 do P = 3 to 10   numeric digits P   say P REPOWER(729, 33.5, P) + 0 end

displays results, which the following table describes:

 P result 3 7.97E+95 4 7.968E+95 5 7.9684E+95 6 7.96842E+95 7 7.968420E+95 8 7.9684197E+95 9 7.96841967E+95 10 7.968419666E+95

 30th January 2000 I read the algorithm of J. M. Borwein and P. B. Borwein for computation of Pi; I wrote and debugged program PI (about 20 minutes); I ran this program for computation of the number Pi to thousand decimal places (about 90 seconds). "Rexx code tends to run slowly.", hm ... we say speed of computation but we think speed of finding of answer, solution.

26th February 2000

It isn't a trivially job to translate algorithms from various pseudocodes or programming languages as Ada, ALGOL, BASIC, C, FORTRAN, Modula, Pascal, PL/1, into the useful code in the Rexx language.

I translated the Donald E. Knuth's code for Winograd's matrix multiplication (Chapter 4.6.4, The Art of Computer Programming, Volume 2) There is an old programmers rule: If some of the code does exactly the same thing, extract it from within loops. Coding of Winograd's algorithm was the hardest case of such extraction in my practice. This is the solution (schematic record).

 Odd = N // 2 do K = 1 to R; compute bk; end do I = 1 to M   compute A = ai   do K = 1 to R     zik = 0     if Odd then zik = ain * bnk     do J = 1 to N % 2       compute (xi,2j + y2j-1,k) * (xi,2j-1 + y2j,k)     end     zik = zik - A - bk   end K end I

I persuade of corectness of my solution by counting of multiplication operations. Their number has to be

FORMAT(N/2,,0)*M*R + (N%2)*(M+R).

27th February 2000

Does the RANDOM built-in function give the real good pseudorandom numbers? We can use the special tests as chi-square test or Kolmogorov-Smirnov test. But there are many more amusing ways.

E. Cesaro's theorem (1881) says: If A and B are integers chosen at random, the probability that GCD(A,B)=1 is 6/PI()**2.

Note 1: 6/PI()**2=0.607927099...
Note 2: For detailed description see GCD and PI

You can try the following program as a test your routine for generation of pseudorandom numbers.

 parse arg N P = 0 do i = 1 to N   A = RANDOM(0, 100000); B = RANDOM(0, 100000)   if GCD(A, B) = 1 then P = P + 1 end say P / N exit ...

Results are included in the table for N=10,100,1000,10000,100000

 N approach 0.607927099 10**1 0.6 10**2 0.62 10**3 0.615 10**4 0.6128 10**5 0.60887 10**6 0.607846

And additional example. The average number of swaps for MODIFIND is

 S(N, K) = 0.5((N + 1)HN - (N - K)HN - K + 1 - (K - 1)HK)

Where

 HN = 1 + 1/2 + ... + 1/N

For N = 1001; K = 500 and input array created by do J = 1 to N; A.J = RANDOM(1, 100000); end we will compute the average number of swaps after NR runs of the program.

 NR approach 353.311 10**1 370.2 10**2 354.23 10**3 352.171 10**4 353.234