logo refleXio

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
- More readable 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)

I think, from 4th and 5th chapters of this article is obvious that 6.4th way could be fine for up-to-date languages rich with tradition as Rexx is.

 

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:

http://www2.hursley.ibm.com/nrl/nrslang.html#refsifw

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)

 

Code of Winograd's matrix multiplication

 

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


Cover Contents Index Main page

last modified 26 April 2002
Copyright 2000-2002 Vladimir Zabrodsky
Czech Republic