Short-circuit evaluation: Difference between revisions
Line 123: | Line 123: | ||
* Since any result means an expression succeeded and is hence true, we can use any value. In this example our choice will be determined by how we deal with 'false'. |
* Since any result means an expression succeeded and is hence true, we can use any value. In this example our choice will be determined by how we deal with 'false'. |
||
* The inability to pass a 'false' value is a challenge. At first glance we might try &null, similar to Lisp, but there is no canonical true. Also &null produces a result, so strictly speaking it could be 'true' as well. |
* The inability to pass a 'false' value is a challenge. At first glance we might try &null, similar to Lisp, but there is no canonical true. Also &null produces a result, so strictly speaking it could be 'true' as well. |
||
* For this example we will define two procedures 'true' and 'false'. Because Icon treats procedures as a data type we can assign them and invoke them indirectly via the variable name they are assigned to. We can write " i := true " and later invoke 'true' |
* For this example we will define two procedures 'true' and 'false'. Because Icon treats procedures as a data type we can assign them and invoke them indirectly via the variable name they are assigned to. We can write " i := true " and later invoke 'true' via " i() ". |
||
* Rather than have the tasks print their own name, we will just utilize built-in tracing which will be more informative. |
* Rather than have the tasks print their own name, we will just utilize built-in tracing which will be more informative. |
||
This use of procedures as values is somewhat contrived but serves us well for demonstration. |
This use of procedures as values is somewhat contrived but serves us well for demonstration. |
Revision as of 13:46, 29 July 2010
You are encouraged to solve this task according to the task description, using any language you may know.
Assume functions a and b return boolean values, and further, the execution of function b takes considerable resources and is to be minimised.
If we needed to compute:
x = a() and b()
Then it would be best to not compute the value of b() if the value of a() is computed as False, as the value of x can then only ever be False.
Similarly, if we needed to compute:
y = a() or b()
Then it would be best to not compute the value of b() if the value of a() is computed as True, as the value of x can then only ever be True.
Some languages will stop further computation of boolean equations as soon as the result is known, so-called short-circuit evaluation of boolean expressions
Task Description
The task is to create two functions named a and b, that take and return the same boolean value. The functions should also print their name whenever they are called. Calculate and assign the values of the following equations to a variable in such a way that function b is only called when necessary:
x = a(i) and b(j) y = a(i) or b(j)
If the language does not have short-circuit evaluation, this might be achieved with nested if statements.
ALGOL 68
With Standard
Note: The "brief" conditional clause ( ~ | ~ | ~ ) is a the standard's shorthand for enforcing short-circuit evaluation. Moreover, the coder is able to define their own proc[edures] and op[erators] that implement short-circuit evaluation by using Algol68's proceduring. <lang algol68>PRIO ORELSE = 2, ANDTHEN = 3; # user defined operators # OP ORELSE = (BOOL a, PROC BOOL b)BOOL: ( a | a | b ),
ANDTHEN = (BOOL a, PROC BOOL b)BOOL: ( a | b | a );
- user defined Short-circuit_evaluation procedures #
PROC or else = (BOOL a, PROC BOOL b)BOOL: ( a | a | b ),
and then = (BOOL a, PROC BOOL b)BOOL: ( a | b | a );
test:(
PROC a = (BOOL a)BOOL: ( print(("a=",a,", ")); a), b = (BOOL b)BOOL: ( print(("b=",b,", ")); b);
CO
- Valid for Algol 68 Rev0: using "user defined" operators #
- Note: here BOOL is being automatically "procedured" to PROC BOOL #
print(("T ORELSE F = ", a(TRUE) ORELSE b(FALSE), new line)); print(("F ANDTHEN T = ", a(FALSE) ANDTHEN b(TRUE), new line));
print(("or else(T, F) = ", or else(a(TRUE), b(FALSE)), new line)); print(("and then(F, T) = ", and then(a(FALSE), b(TRUE)), new line));
END CO
- Valid for Algol68 Rev1: using "user defined" operators #
- Note: BOOL must be manually "procedured" to PROC BOOL #
print(("T ORELSE F = ", a(TRUE) ORELSE (BOOL:b(FALSE)), new line)); print(("T ORELSE T = ", a(TRUE) ORELSE (BOOL:b(TRUE)), new line));
print(("F ANDTHEN F = ", a(FALSE) ANDTHEN (BOOL:b(FALSE)), new line)); print(("F ANDTHEN T = ", a(FALSE) ANDTHEN (BOOL:b(TRUE)), new line));
print(("F ORELSE F = ", a(FALSE) ORELSE (BOOL:b(FALSE)), new line)); print(("F ORELSE T = ", a(FALSE) ORELSE (BOOL:b(TRUE)), new line));
print(("T ANDTHEN F = ", a(TRUE) ANDTHEN (BOOL:b(FALSE)), new line)); print(("T ANDTHEN T = ", a(TRUE) ANDTHEN (BOOL:b(TRUE)), new line))
)</lang> Output:
a=T, T ORELSE F = T a=T, T ORELSE T = T a=F, F ANDTHEN F = F a=F, F ANDTHEN T = F a=F, b=F, F ORELSE F = F a=F, b=T, F ORELSE T = T a=T, b=F, T ANDTHEN F = F a=T, b=T, T ANDTHEN T = T
With Extensions
<lang algol68>test:(
PROC a = (BOOL a)BOOL: ( print(("a=",a,", ")); a), b = (BOOL b)BOOL: ( print(("b=",b,", ")); b);
- Valid for Algol 68G and 68RS using non standard operators #
print(("T OREL F = ", a(TRUE) OREL b(FALSE), new line)); print(("T OREL T = ", a(TRUE) OREL b(TRUE), new line));
print(("F ANDTH F = ", a(FALSE) ANDTH b(FALSE), new line)); print(("F ANDTH T = ", a(FALSE) ANDTH b(TRUE), new line));
print(("F OREL F = ", a(FALSE) OREL b(FALSE), new line)); print(("F OREL T = ", a(FALSE) OREL b(TRUE), new line));
print(("T ANDTH F = ", a(TRUE) ANDTH b(FALSE), new line)); print(("T ANDTH T = ", a(TRUE) ANDTH b(TRUE), new line))
CO;
- Valid for Algol 68G and 68C using non standard operators #
print(("T ORF F = ", a(TRUE) ORF b(FALSE), new line)); print(("F ANDF T = ", a(FALSE) ANDF b(TRUE), new line))
END CO
)</lang> Output:
a=T, T OREL F = T a=T, T OREL T = T a=F, F ANDTH F = F a=F, F ANDTH T = F a=F, b=F, F OREL F = F a=F, b=T, F OREL T = T a=T, b=F, T ANDTH F = F a=T, b=T, T ANDTH T = T
Icon and Unicon
The entire concept of using 'boolean' values for logic control runs counter to the philosophy of Icon. Instead Icon has success (something that returns a result) and failure which is really a signal. The concept is similar to that used in SNOBOL4 and Lisp and far more potent than passing around and testing booleans. There is no way to pass around a 'false' value in that sense. Because failure is a signal control is always evaluated in a short-circuit manner. One consequence of this is that an expression "i < j" doesn't return a boolean value, instead it returns the value of j. While this may seem odd at first it allows for elegant expressions like "i < j < k".
While this task could be written literally, it would be more beneficial to show how an Icon programmer would approach the same problem. Icon extends the idea short circuit evaluation with the ability for expressions to generate alternate results only if needed. For more information see Failure is an option, Everything Returns a Value Except when it Doesn't, and Goal-Directed Evaluation and Generators. Consequently some small liberties will be taken with this task:
- Since any result means an expression succeeded and is hence true, we can use any value. In this example our choice will be determined by how we deal with 'false'.
- The inability to pass a 'false' value is a challenge. At first glance we might try &null, similar to Lisp, but there is no canonical true. Also &null produces a result, so strictly speaking it could be 'true' as well.
- For this example we will define two procedures 'true' and 'false'. Because Icon treats procedures as a data type we can assign them and invoke them indirectly via the variable name they are assigned to. We can write " i := true " and later invoke 'true' via " i() ".
- Rather than have the tasks print their own name, we will just utilize built-in tracing which will be more informative.
This use of procedures as values is somewhat contrived but serves us well for demonstration.
Icon
<lang Icon>procedure main()
&trace := -1 # ensures functions print their names
every (i := false | true ) & ( j := false | true) do {
write("i,j := ",image(i),", ",image(j)) write("i & j:") x := i() & j() write("i | j:") y := i() | j() }
end
procedure true() #: succeeds always (returning null) return end
procedure false() #: fails always fail # for clarity but not needed as running into end has the same effect end </lang>
Sample output for a single case:
i,j := procedure true, procedure false i & j: rtcircuit.icn: 8 | true() rtcircuit.icn: 16 | true returned &null rtcircuit.icn: 8 | false() rtcircuit.icn: 20 | false failed i | j: rtcircuit.icn: 10 | true() rtcircuit.icn: 16 | true returned &null i,j := procedure true, procedure true
Unicon
The Icon solution works in Unicon.
Java
In Java the boolean operators &&
and ||
are short circuit operators. The eager operator counterparts are &
and |
.
<lang java>public class ShortCirc {
public static void main(String[] args){ System.out.println("F and F = " + (a(false) && b(false)) + "\n"); System.out.println("F or F = " + (a(false) || b(false)) + "\n");
System.out.println("F and T = " + (a(false) && b(true)) + "\n"); System.out.println("F or T = " + (a(false) || b(true)) + "\n");
System.out.println("T and F = " + (a(true) && b(false)) + "\n"); System.out.println("T or F = " + (a(true) || b(false)) + "\n");
System.out.println("T and T = " + (a(true) && b(true)) + "\n"); System.out.println("T or T = " + (a(true) || b(true)) + "\n"); }
public static boolean a(boolean a){ System.out.println("a"); return a; }
public static boolean b(boolean b){ System.out.println("b"); return b; }
}</lang> Output:
a F and F = false a b F or F = false a F and T = false a b F or T = true a b T and F = false a T or F = true a b T and T = true a T or T = true
OCaml
<lang ocaml> let a r = print_endline " > function a called"; r let b r = print_endline " > function b called"; r
let test_and b1 b2 =
Printf.printf "# testing (%b && %b)\n" b1 b2; ignore (a b1 && b b2)
let test_or b1 b2 =
Printf.printf "# testing (%b || %b)\n" b1 b2; ignore (a b1 || b b2)
let test_this test =
test true true; test true false; test false true; test false false;
let () =
print_endline "==== Testing and ===="; test_this test_and; print_endline "==== Testing or ===="; test_this test_or;
- </lang>
output:
==== Testing and ==== # testing (true && true) > function a called > function b called # testing (true && false) > function a called > function b called # testing (false && true) > function a called # testing (false && false) > function a called ==== Testing or ==== # testing (true || true) > function a called # testing (true || false) > function a called # testing (false || true) > function a called > function b called # testing (false || false) > function a called > function b called
Logo
The AND and OR predicates may take either expressions which are all evaluated beforehand, or lists which are short-circuit evaluated from left to right only until the overall value of the expression can be determined. <lang logo> and [notequal? :x 0] [1/:x > 3] (or [:x < 0] [:y < 0] [sqrt :x + sqrt :y < 3]) </lang>
Oz
Oz' andthen
and orelse
operators are short-circuiting, as indicated by their name. The library functions Bool.and
and Bool.or
are not short-circuiting, on the other hand.
<lang oz>declare
fun {A Answer} AnswerS = {Value.toVirtualString Answer 1 1} in {System.showInfo " % Called function {A "#AnswerS#"} -> "#AnswerS} Answer end
fun {B Answer} AnswerS = {Value.toVirtualString Answer 1 1} in {System.showInfo " % Called function {B "#AnswerS#"} -> "#AnswerS} Answer end
in
for I in [false true] do for J in [false true] do X Y in {System.showInfo "\nCalculating: X = {A I} andthen {B J}"} X = {A I} andthen {B J} {System.showInfo "Calculating: Y = {A I} orelse {B J}"} Y = {A I} orelse {B J} end end</lang>
Output: <lang oz>Calculating: X = {A I} andthen {B J}
% Called function {A false} -> false
Calculating: Y = {A I} orelse {B J}
% Called function {A false} -> false % Called function {B false} -> false
Calculating: X = {A I} andthen {B J}
% Called function {A false} -> false
Calculating: Y = {A I} orelse {B J}
% Called function {A false} -> false % Called function {B true} -> true
Calculating: X = {A I} andthen {B J}
% Called function {A true} -> true % Called function {B false} -> false
Calculating: Y = {A I} orelse {B J}
% Called function {A true} -> true
Calculating: X = {A I} andthen {B J}
% Called function {A true} -> true % Called function {B true} -> true
Calculating: Y = {A I} orelse {B J}
% Called function {A true} -> true</lang>
Pascal
Standard Pascal
Standard Pascal doesn't have native short-circuit evaluation. <lang pascal> program shortcircuit(output);
function a(value: boolean): boolean;
begin writeln('a(', value, ')'); a := value end;
function b(value:boolean): boolean;
begin writeln('b(', value, ')'); b := value end;
procedure scandor(value1, value2: boolean);
var result: integer; begin {and} if a(value1) then result := b(value2) else result := false; writeln(value1, ' and ', value2, ' = ', result);
{or} if a(value1) then result := true else result := b(value2) writeln(value1, ' or ', value2, ' = ', result) end;
begin
scandor(false, false); scandor(false, true); scandor(true, false); scandor(true, true);
end. </lang>
Turbo Pascal
Turbo Pascal allows short circuit evaluation with a compiler switch: <lang pascal> program shortcircuit;
function a(value: boolean): boolean;
begin writeln('a(', value, ')'); a := value end;
function b(value:boolean): boolean;
begin writeln('b(', value, ')'); b := value end;
{$B-} {enable short circuit evaluation} procedure scandor(value1, value2: boolean);
var result: integer; begin result := a(value1) and b(value) writeln(value1, ' and ', value2, ' = ', result);
result := a(value1) or b(value2); writeln(value1, ' or ', value2, ' = ', result) end;
begin
scandor(false, false); scandor(false, true); scandor(true, false); scandor(true, true);
end. </lang>
Extended Pascal
The extended Pascal standard introduces the operators and_then
and or_else
for short-circuit evaluation.
<lang pascal>
program shortcircuit(output);
function a(value: boolean): boolean;
begin writeln('a(', value, ')'); a := value end;
function b(value:boolean): boolean;
begin writeln('b(', value, ')'); b := value end;
procedure scandor(value1, value2: boolean);
var result: integer; begin result := a(value1) and_then b(value) writeln(value1, ' and ', value2, ' = ', result);
result := a(value1) or_else b(value2); writeln(value1, ' or ', value2, ' = ', result) end;
begin
scandor(false, false); scandor(false, true); scandor(true, false); scandor(true, true);
end. </lang>
Note: GNU Pascal allows and then
and or else
as alternatives to and_then
and or_else
.
PureBasic
Logical And & Or operators will not evaluate their right-hand expression if the outcome can be determined from the value of the left-hand expression. <lang PureBasic>Procedure a(arg)
PrintN(" # Called function a("+Str(arg)+")") ProcedureReturn arg
EndProcedure
Procedure b(arg)
PrintN(" # Called function b("+Str(arg)+")") ProcedureReturn arg
EndProcedure
OpenConsole() For a=#False To #True
For b=#False To #True PrintN(#CRLF$+"Calculating: x = a("+Str(a)+") And b("+Str(b)+")") x= a(a) And b(b) PrintN("Calculating: x = a("+Str(a)+") Or b("+Str(b)+")") y= a(a) Or b(b) Next
Next Input()</lang>
Calculating: x = a(0) And b(0) # Called function a(0) Calculating: x = a(0) Or b(0) # Called function a(0) # Called function b(0) Calculating: x = a(0) And b(1) # Called function a(0) Calculating: x = a(0) Or b(1) # Called function a(0) # Called function b(1) Calculating: x = a(1) And b(0) # Called function a(1) # Called function b(0) Calculating: x = a(1) Or b(0) # Called function a(1) Calculating: x = a(1) And b(1) # Called function a(1) # Called function b(1) Calculating: x = a(1) Or b(1) # Called function a(1)
Python
Pythons and and or binary, infix, boolean operators will not evaluate their right-hand expression if the outcome can be determined from the value of the left-hand expression. <lang python>>>> def a(answer): print(" # Called function a(%r) -> %r" % (answer, answer)) return answer
>>> def b(answer): print(" # Called function b(%r) -> %r" % (answer, answer)) return answer
>>> for i in (False, True): for j in (False, True): print ("\nCalculating: x = a(i) and b(j)") x = a(i) and b(j) print ("Calculating: y = a(i) or b(j)") y = a(i) or b(j)
Calculating: x = a(i) and b(j)
# Called function a(False) -> False
Calculating: y = a(i) or b(j)
# Called function a(False) -> False # Called function b(False) -> False
Calculating: x = a(i) and b(j)
# Called function a(False) -> False
Calculating: y = a(i) or b(j)
# Called function a(False) -> False # Called function b(True) -> True
Calculating: x = a(i) and b(j)
# Called function a(True) -> True # Called function b(False) -> False
Calculating: y = a(i) or b(j)
# Called function a(True) -> True
Calculating: x = a(i) and b(j)
# Called function a(True) -> True # Called function b(True) -> True
Calculating: y = a(i) or b(j)
# Called function a(True) -> True</lang>
Pythons if expression can also be used to the same ends (but probably should not): <lang python>>>> for i in (False, True): for j in (False, True): print ("\nCalculating: x = a(i) and b(j) using x = b(j) if a(i) else False") x = b(j) if a(i) else False print ("Calculating: y = a(i) or b(j) using y = b(j) if not a(i) else True") y = b(j) if not a(i) else True
Calculating: x = a(i) and b(j) using x = b(j) if a(i) else False
# Called function a(False) -> False
Calculating: y = a(i) or b(j) using y = b(j) if not a(i) else True
# Called function a(False) -> False # Called function b(False) -> False
Calculating: x = a(i) and b(j) using x = b(j) if a(i) else False
# Called function a(False) -> False
Calculating: y = a(i) or b(j) using y = b(j) if not a(i) else True
# Called function a(False) -> False # Called function b(True) -> True
Calculating: x = a(i) and b(j) using x = b(j) if a(i) else False
# Called function a(True) -> True # Called function b(False) -> False
Calculating: y = a(i) or b(j) using y = b(j) if not a(i) else True
# Called function a(True) -> True
Calculating: x = a(i) and b(j) using x = b(j) if a(i) else False
# Called function a(True) -> True # Called function b(True) -> True
Calculating: y = a(i) or b(j) using y = b(j) if not a(i) else True
# Called function a(True) -> True</lang>
Scheme
<lang scheme>>(define (a x)
(display "a\n") x)
>(define (b x)
(display "b\n") x)
>(for-each (lambda (i)
(for-each (lambda (j) (display i) (display " and ") (display j) (newline) (and (a i) (b j)) (display i) (display " or ") (display j) (newline) (or (a i) (b j)) ) '(#t #f)) ) '(#t #f))
- t and #t
a b
- t or #t
a
- t and #f
a b
- t or #f
a
- f and #t
a
- f or #t
a b
- f and #f
a
- f or #f
a b </lang>
SNOBOL4
Because of its unique success/failure model of flow control, Snobol does not use standard boolean operators or assignment. However, in &fullscan mode Snobol exhibits short-circuit boolean behavior in pattern matches, with concatenation " " functioning as logical AND, and alternation " | " as logical OR.
The test statements below use a pattern constructed from the functions a( ) and b( ) and match it to the null string with deferred evaluation. This idiom allows the functions to self-report the expected short-circuit patterns.
<lang SNOBOL4> define('a(val)') :(a_end) a out = 'A '
eq(val,1) :s(return)f(freturn)
a_end
define('b(val)') :(b_end)
b out = 'B '
eq(val,1) :s(return)f(freturn)
b_end
- # Test and display
&fullscan = 1 output(.out,1,'-[-r1]') ;* Macro Spitbol
- output(.out,1,'B','-') ;* CSnobol
define('nl()'):(nlx);nl output = :(return);nlx out = 'T and T: '; null ? *a(1) *b(1); nl() out = 'T and F: '; null ? *a(1) *b(0); nl() out = 'F and T: '; null ? *a(0) *b(1); nl() out = 'F and F: '; null ? *a(0) *b(0); nl() output = out = 'T or T: '; null ? *a(1) | *b(1); nl() out = 'T or F: '; null ? *a(1) | *b(0); nl() out = 'F or T: '; null ? *a(0) | *b(1); nl() out = 'F or F: '; null ? *a(0) | *b(0); nl()
end</lang>
Output:
T and T: A B T and F: A B F and T: A F and F: A T or T: A T or F: A F or T: A B F or F: A B
Tcl
The &&
and ||
in the expr
command support short-circuit evaluation. It is recommended that you always put expressions in braces so that and command or variable substitutions are applied at the right time rather than before the expression is evaluated at all. (Indeed, it is recommended that you do that anyway as unbraced expressions cannot be efficiently compiled.)
<lang tcl>package require Tcl 8.5
proc tcl::mathfunc::a boolean {
puts "a($boolean) called" return $boolean
} proc tcl::mathfunc::b boolean {
puts "b($boolean) called" return $boolean
}
foreach i {false true} {
foreach j {false true} { set x [expr {a($i) && b($j)}] puts "x = a($i) && b($j) = $x" set y [expr {a($i) || b($j)}] puts "y = a($i) || b($j) = $y" puts ""; # Blank line for clarity }
}</lang> Output (note that booleans may be written out words or numeric):
a(false) called x = a(false) && b(false) = 0 a(false) called b(false) called y = a(false) || b(false) = 0 a(false) called x = a(false) && b(true) = 0 a(false) called b(true) called y = a(false) || b(true) = 1 a(true) called b(false) called x = a(true) && b(false) = 0 a(true) called y = a(true) || b(false) = 1 a(true) called b(true) called x = a(true) && b(true) = 1 a(true) called y = a(true) || b(true) = 1