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
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
|
