Dogcows Code - chaz/p5-Acme-Test-LogicalEquivalence/blob - lib/Acme/Test/LogicalEquivalence.pm

   1 package Acme::Test::LogicalEquivalence;
   2 # ABSTRACT: Test if expressions are logically equivalent
   3 # KEYWORDS: test logic
   4
   5 use 5.008;
   6 use warnings;
   7 use strict;
   8
   9 our $VERSION = '999.999'; # VERSION
  10
  11 use Exporter qw(import);
  12 use Test::More;
  13 use namespace::clean -except => [qw(import)];
  14
  15 our @EXPORT_OK = qw(is_logically_equivalent);
  16
  17 =head1 SYNOPSIS
  18
  19     use Test::More;
  20     use Acme::Test::LogicalEquivalence qw(is_logically_equivalent);
  21
  22     # test two expressions with 2 variables using the special vars $a and $b
  23     is_logically_equivalent(2, sub { $a && $b }, sub { $b && $a });
  24
  25     # same as above
  26     is_logically_equivalent(2, sub { $_[0] && $_[1] }, sub { $_[1] && $_[0] });
  27
  28     # you can do as many vars as you like
  29     is_logically_equivalent(3, sub { $_[0] || ($_[1] && $_[2]) },
  30                                sub { ($_[0] || $_[1]) && ($_[0] || $_[2]) });
  31
  32     done_testing;
  33
  34 =head1 DESCRIPTION
  35
  36 Some expressions are "logically equivalent" to other expressions, but it may not be easy to tell if
  37 one or both of the expressions are reasonably complicated. Or maybe you're like many other people
  38 and are too lazy to go through the effort... Either way, why not let your computer prove logical
  39 equivalence for you?
  40
  41 =head1 SEE ALSO
  42
  43 =for :list
  44 * What is logical equivalence? Start here: L<https://en.wikipedia.org/wiki/Logical_equivalence>
  45
  46 =func is_logically_equivalent
  47
  48 Test logical equivalence of two subroutines.
  49
  50     my $is_equivalent = is_logically_equivalent($numvars, &sub1, &sub2);
  51
  52 This will execute both of the subroutines one or more times (depending on how many variables you
  53 specify) with different inputs. The subroutines shall be considered logically equivalent if, for all
  54 combinations of inputs, they both return the same thing.
  55
  56 Returns true if the subroutines are logically equivalent, false otherwise.
  57
  58 =cut
  59
  60 sub is_logically_equivalent {
  61     my $numvars = shift;
  62     my $sub1 = shift;
  63     my $sub2 = shift;
  64
  65     my $equivalence = 1;
  66
  67     for (my $i = 0; $i < 2 ** $numvars; ++$i) {
  68         my @vars = split(//, substr(unpack("B32", pack('N', $i)), -$numvars));
  69
  70         (local $a, local $b) = @vars;
  71         my $r1 = !!$sub1->(@vars);
  72
  73         (local $a, local $b) = @vars;
  74         my $r2 = !!$sub2->(@vars);
  75
  76         my $test = !($r1 xor $r2);
  77
  78         my $args = join(', ', map { $_ ? 'T' : 'F' } @vars);
  79         ok($test, "expr1($args) <=> expr2($args)");
  80
  81         $equivalence = '' if !$test;
  82     }
  83
  84     return $equivalence;
  85 }
  86
  87 1;