Short-circuit evaluation: Difference between revisions

From Rosetta Code
Content added Content deleted
m (Fixed typo)
(Added Snobol4)
Line 544: Line 544:
b
b
</lang>
</lang>

=={{header|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 accept 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:
<pre>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</pre>

Revision as of 09:40, 25 July 2010

Task
Short-circuit evaluation
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

Works with: ALGOL 68 version Revision 1 - no extensions to language used
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d

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 );
  1. 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

  1. Valid for Algol 68 Rev0: using "user defined" operators #
  2. 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

  1. Valid for Algol68 Rev1: using "user defined" operators #
  2. 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

Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8-8d

<lang algol68>test:( 

 PROC a = (BOOL a)BOOL: ( print(("a=",a,", ")); a),
      b = (BOOL b)BOOL: ( print(("b=",b,", ")); b);
  1. 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;

  1. 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. While this task could be written literally, it would be more beneficial to show how an Icon programmer would approach the same problem. Icon already embraces the idea of short circuit evaluation and goes further with the ability of 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:

  • For false we will use the null value &null and true we will use anything else (a 1 will do).
  • Short-circuit evaluation uses success (a result) and failure (a signal that cannot be ignored and no result) so strictly speaking the boolean false will not be returned (only the failure signal).
  • Rather than have the tasks print their own name, we will just utilize built-in tracing which will be more informative.

Icon

<lang Icon>procedure main() &trace := -1 # ensures a and b print their names

every (i := &null | 1 ) & ( j := &null | 1) do { 

 write("i,j := ",image(i),", ",image(j))
 write("a & b:")
 x := a(i) & b(j)
 write("a | b:")
 y := a(i) | b(j)
 }

end

procedure a(x) #: returns x if x is non-null or fails otherwise return \x end

procedure b(x) return \x end</lang>

Sample output for a single case:

i,j := &null, 1
a & b:
shortcicuit.icn:   10  | a(&null)
shortcicuit.icn:   19  | a failed
a | b:
shortcicuit.icn:   12  | a(&null)
shortcicuit.icn:   19  | a failed
shortcicuit.icn:   12  | b(1)
shortcicuit.icn:   23  | b returned 1

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

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))
  1. t and #t

a b

  1. t or #t

a

  1. t and #f

a b

  1. t or #f

a

  1. f and #t

a

  1. f or #t

a b

  1. f and #f

a

  1. 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 accept 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
Retrieved from "https://rosettacode.org/wiki/Short-circuit_evaluation?oldid=153491"