| 1 | #!/usr/bin/env perl | ||||||||||
| 2 | |||||||||||
| 3 | # Copyright (c) 2015-2020 Christian Jaeger, copying@christianjaeger.ch | ||||||||||
| 4 | # This is free software. See the file COPYING.md that came bundled | ||||||||||
| 5 | # with this file. | ||||||||||
| 6 | |||||||||||
| 7 | # This was written while working through the online course material | ||||||||||
| 8 | # "Introduction to Logic" at Stanford University | ||||||||||
| 9 | |||||||||||
| 10 | # http://logic.stanford.edu/intrologic/ | ||||||||||
| 11 | # http://logic.stanford.edu/intrologic/chapters/chapter_01.html | ||||||||||
| 12 | |||||||||||
| 13 | # It mostly uses functions (like array_any) over methods (like ->any), | ||||||||||
| 14 | # for demonstration purposes and since we can here since there's no | ||||||||||
| 15 | # need for this code to be generic, otherwise the latter would be the | ||||||||||
| 16 | # right choice. | ||||||||||
| 17 | |||||||||||
| 18 | 1 | ▶ | use strict; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 19 | 1 | ▶ | use warnings; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 20 | 1 | ▶ | use warnings FATAL => 'uninitialized'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 21 | 1 | ▶ | use experimental "signatures"; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 22 | |||||||||||
| 23 | # find modules from functional-perl working directory (not installed) | ||||||||||
| 24 | 1 | ▶ | use Cwd 'abs_path'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 25 | our ($mydir, $myname); | ||||||||||
| 26 | |||||||||||
| 27 | 1 | ▶ | BEGIN { | ||||||||
|
Subroutine
BEGIN: called CC=3 SCAR=11.7
| |||||||||||
| 28 | 1 | ▶ | my $location = (-l $0) ? abs_path($0) : $0; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 29 | 1 | ▶ | $location =~ /(.*?)([^\/]+?)_?\z/s or die "?"; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 30 | 1 | ($mydir, $myname) = ($1, $2); | |||||||||
| 31 | } | ||||||||||
| 32 | 1 | ▶ | use lib "$mydir/../lib"; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 33 | |||||||||||
| 34 | #use Sub::Call::Tail; | ||||||||||
| 35 | 1 | ▶ | use FP::Array ":all"; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 36 | 1 | ▶ | use FP::Predicates qw(complement); | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 37 | 1 | ▶ | use FP::Stream ":all"; # incl. F | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 38 | 1 | ▶ | use FP::Ops ":all"; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 39 | 0 | ▶ | use Chj::TEST ":all", use => 'FP::Repl::Dependencies'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.4
Subroutine
BEGIN: called CC=1 SCAR=0.4
| |||||||||||
| 40 | use FP::Equal; | ||||||||||
| 41 | use FP::Repl::Stack; | ||||||||||
| 42 | use FP::Repl::Trap; # or Chj::Backtrace | ||||||||||
| 43 | use FP::Repl; | ||||||||||
| 44 | use FP::Hash ":all"; | ||||||||||
| 45 | use FP::Show; | ||||||||||
| 46 | use FP::Array_sort ":all"; | ||||||||||
| 47 | use FP::Carp; | ||||||||||
| 48 | |||||||||||
| 49 | { | ||||||||||
| 50 | |||||||||||
| 51 | package examples_logic::Predicate; | ||||||||||
| 52 | use FP::Struct ["coderef", "stack"]; | ||||||||||
| 53 | use overload ('&{}' => "coderef", '""' => "FP_Show_show"); | ||||||||||
| 54 | |||||||||||
| 55 | sub FP_Show_show ($self, @args) { | ||||||||||
| 56 | "predicate from:\n" . $self->stack->backtrace(0) | ||||||||||
| 57 | } | ||||||||||
| 58 | _END_ | ||||||||||
| 59 | } | ||||||||||
| 60 | |||||||||||
| 61 | my @tests; | ||||||||||
| 62 | |||||||||||
| 63 | sub test($pred) { | ||||||||||
| 64 | push @tests, examples_logic::Predicate->new($pred, FP::Repl::Stack->get(1)); | ||||||||||
| 65 | } | ||||||||||
| 66 | |||||||||||
| 67 | sub matrix_likes ($matrix, $subj, $obj) { | ||||||||||
| 68 | $$matrix{$subj}{$obj} | ||||||||||
| 69 | } | ||||||||||
| 70 | |||||||||||
| 71 | sub likes ($subj, $obj) { | ||||||||||
| 72 | sub($matrix) { | ||||||||||
| 73 | matrix_likes $matrix, $subj, $obj | ||||||||||
| 74 | } | ||||||||||
| 75 | } | ||||||||||
| 76 | |||||||||||
| 77 | sub does_not_like ($subj, $obj) { | ||||||||||
| 78 | complement likes($subj, $obj) | ||||||||||
| 79 | } | ||||||||||
| 80 | |||||||||||
| 81 | sub likes_either ($subj, @objs) { | ||||||||||
| 82 | sub($matrix) { | ||||||||||
| 83 | array_any sub($obj) { | ||||||||||
| 84 | matrix_likes $matrix, $subj, $obj | ||||||||||
| 85 | }, \@objs | ||||||||||
| 86 | } | ||||||||||
| 87 | } | ||||||||||
| 88 | |||||||||||
| 89 | sub matrix_people($matrix) { | ||||||||||
| 90 | |||||||||||
| 91 | # XX only works if there are entries (at least in the first level) | ||||||||||
| 92 | # even for false relations! | ||||||||||
| 93 | [keys %$matrix] | ||||||||||
| 94 | } | ||||||||||
| 95 | |||||||||||
| 96 | sub matrix_likers ($matrix, $liked) { | ||||||||||
| 97 | |||||||||||
| 98 | # find who likes $liked | ||||||||||
| 99 | array_filter sub($person) { | ||||||||||
| 100 | matrix_likes $matrix, $person, $liked | ||||||||||
| 101 | }, matrix_people $matrix | ||||||||||
| 102 | } | ||||||||||
| 103 | |||||||||||
| 104 | sub matrix_liked ($matrix, $subj) { | ||||||||||
| 105 | |||||||||||
| 106 | # array of who $subj likes | ||||||||||
| 107 | my $l2 = $$matrix{$subj}; | ||||||||||
| 108 | [grep { $$l2{$_} } keys %$l2] | ||||||||||
| 109 | } | ||||||||||
| 110 | |||||||||||
| 111 | sub matrix_numrelations($matrix) { | ||||||||||
| 112 | my $n = 0; | ||||||||||
| 113 | for my $k0 (keys %$matrix) { | ||||||||||
| 114 | my $m = $$matrix{$k0}; | ||||||||||
| 115 | for my $k1 (keys %$m) { | ||||||||||
| 116 | $n++ if $$m{$k1} | ||||||||||
| 117 | } | ||||||||||
| 118 | } | ||||||||||
| 119 | $n | ||||||||||
| 120 | } | ||||||||||
| 121 | |||||||||||
| 122 | sub likes_everyone_that_x_likes ($subj, $othersubj) { | ||||||||||
| 123 | sub($matrix) { | ||||||||||
| 124 | array_every sub($obj) { | ||||||||||
| 125 | matrix_likes $matrix, $subj, $obj | ||||||||||
| 126 | }, matrix_liked($matrix, $othersubj) | ||||||||||
| 127 | } | ||||||||||
| 128 | } | ||||||||||
| 129 | |||||||||||
| 130 | sub likes_everyone_who_likes ($subj, $liked) { | ||||||||||
| 131 | |||||||||||
| 132 | # is this cheating, walking the matrix? Should it look at | ||||||||||
| 133 | # predicates? ehr no, ehr? | ||||||||||
| 134 | sub($matrix) { | ||||||||||
| 135 | array_every sub($liker) { | ||||||||||
| 136 | matrix_likes $matrix, $subj, $liker | ||||||||||
| 137 | }, matrix_likers($matrix, $liked) | ||||||||||
| 138 | } | ||||||||||
| 139 | } | ||||||||||
| 140 | |||||||||||
| 141 | sub Or ($t0, $t1) { | ||||||||||
| 142 | sub($matrix) { | ||||||||||
| 143 | &$t0($matrix) or &$t1($matrix) | ||||||||||
| 144 | } | ||||||||||
| 145 | } | ||||||||||
| 146 | |||||||||||
| 147 | sub contradictions_for($matrix) { | ||||||||||
| 148 | array_to_stream(\@tests)->filter(complement applying_to $matrix) | ||||||||||
| 149 | } | ||||||||||
| 150 | |||||||||||
| 151 | sub checks($matrix) { | ||||||||||
| 152 | is_null contradictions_for $matrix | ||||||||||
| 153 | } | ||||||||||
| 154 | |||||||||||
| 155 | # logic sentences | ||||||||||
| 156 | |||||||||||
| 157 | # Dana likes Cody. | ||||||||||
| 158 | test likes "Dana", "Cody"; | ||||||||||
| 159 | |||||||||||
| 160 | # Abby does not like Dana. | ||||||||||
| 161 | test does_not_like "Abby", "Dana"; | ||||||||||
| 162 | |||||||||||
| 163 | # Dana does not like Abby. | ||||||||||
| 164 | test does_not_like "Dana", "Abby"; | ||||||||||
| 165 | |||||||||||
| 166 | # Bess likes Cody or Dana. | ||||||||||
| 167 | test likes_either "Bess", "Cody", "Dana"; | ||||||||||
| 168 | |||||||||||
| 169 | # Abby likes everyone that Bess likes. | ||||||||||
| 170 | test likes_everyone_that_x_likes "Abby", "Bess"; | ||||||||||
| 171 | |||||||||||
| 172 | # Cody likes everyone who likes her. | ||||||||||
| 173 | test likes_everyone_who_likes "Cody", "Cody"; | ||||||||||
| 174 | |||||||||||
| 175 | # Nobody likes herself. | ||||||||||
| 176 | test does_not_like $_, $_ for qw(Dana Cody Abby Bess); | ||||||||||
| 177 | |||||||||||
| 178 | # Logical Entailment: | ||||||||||
| 179 | |||||||||||
| 180 | # is this compatible with the above world? Does it *change* the | ||||||||||
| 181 | # outcome? Then, *is* there still a successful match? | ||||||||||
| 182 | |||||||||||
| 183 | # Abby likes Bess or Bess likes Abby. | ||||||||||
| 184 | test Or(likes("Abby", "Bess"), likes "Bess", "Abby"); | ||||||||||
| 185 | |||||||||||
| 186 | my $onesolution = { | ||||||||||
| 187 | Abby => { Abby => '', Bess => 1, Cody => 1, Dana => '' }, | ||||||||||
| 188 | Bess => { Abby => '', Bess => '', Cody => 1, Dana => '' }, | ||||||||||
| 189 | Cody => { Abby => 1, Bess => 1, Cody => '', Dana => 1 }, | ||||||||||
| 190 | Dana => { Abby => '', Bess => '', Cody => 1, Dana => '' }, | ||||||||||
| 191 | }; | ||||||||||
| 192 | |||||||||||
| 193 | TEST { matrix_numrelations $onesolution } 7; | ||||||||||
| 194 | |||||||||||
| 195 | sub T($pred) { | ||||||||||
| 196 | &$pred($onesolution) | ||||||||||
| 197 | } | ||||||||||
| 198 | |||||||||||
| 199 | TEST { T likes "Dana", "Cody" } 1; | ||||||||||
| 200 | TEST { T likes "Abby", "Dana" } ''; | ||||||||||
| 201 | |||||||||||
| 202 | # test likes_everyone_who_likes "Abby", "Bess": | ||||||||||
| 203 | TEST { T likes "Cody", "Bess" } 1; | ||||||||||
| 204 | TEST { T likes "Abby", "Cody" } 1; # because Cody likes Bess | ||||||||||
| 205 | |||||||||||
| 206 | #^ ehr that was crap, 'odd' that it fits into the same world? | ||||||||||
| 207 | |||||||||||
| 208 | # test likes_everyone_that_x_likes "Abby", "Bess": | ||||||||||
| 209 | TEST { T likes "Bess", "Cody" } 1; | ||||||||||
| 210 | TEST { T likes "Abby", "Cody" } 1; | ||||||||||
| 211 | TEST { matrix_liked $onesolution, "Bess" } ["Cody"]; | ||||||||||
| 212 | TEST { T likes_everyone_that_x_likes "Abby", "Bess" } 1; | ||||||||||
| 213 | |||||||||||
| 214 | # test likes_everyone_who_likes "Cody", "Cody": | ||||||||||
| 215 | TEST { T likes "Dana", "Cody" } 1; | ||||||||||
| 216 | TEST { T likes "Bess", "Cody" } 1; | ||||||||||
| 217 | TEST { T likes "Abby", "Cody" } 1; | ||||||||||
| 218 | TEST { T likes "Cody", "Dana" } 1; # because Dana likes Cody | ||||||||||
| 219 | TEST { T likes "Cody", "Bess" } 1; | ||||||||||
| 220 | TEST { T likes "Cody", "Abby" } 1; | ||||||||||
| 221 | |||||||||||
| 222 | # does_not_like: | ||||||||||
| 223 | TEST { T does_not_like "Abby", "Dana" } 1; | ||||||||||
| 224 | |||||||||||
| 225 | # nobody likes herself: | ||||||||||
| 226 | TEST { T does_not_like "Cody", "Cody" } 1; | ||||||||||
| 227 | TEST { T does_not_like "Abby", "Abby" } 1; | ||||||||||
| 228 | |||||||||||
| 229 | TEST { checks $onesolution } 1; | ||||||||||
| 230 | |||||||||||
| 231 | #TEST { checks hash2_set $onesolution, "Bess", "Cody", 0 } 0; | ||||||||||
| 232 | #TEST { checks hash2_set $onesolution, "Bess", "Dana", 0 } 1; | ||||||||||
| 233 | #TEST { checks hash2_set $onesolution, "Bess", "Dana", 1 } 0; got 1 hm | ||||||||||
| 234 | |||||||||||
| 235 | our $people = matrix_people $onesolution; | ||||||||||
| 236 | our $people_i = [0 .. $#$people]; | ||||||||||
| 237 | |||||||||||
| 238 | sub buildmatrix($bits) { | ||||||||||
| 239 | array_to_hash_map sub ($subj, $subji) { | ||||||||||
| 240 | $subj => array_to_hash_map( | ||||||||||
| 241 | sub ($obj, $obji) { | ||||||||||
| 242 | my $i = $subji * 4 + $obji; | ||||||||||
| 243 | $obj => !!($bits & (1 << $i)) | ||||||||||
| 244 | }, | ||||||||||
| 245 | $people, | ||||||||||
| 246 | $people_i | ||||||||||
| 247 | ) | ||||||||||
| 248 | }, $people, $people_i | ||||||||||
| 249 | } | ||||||||||
| 250 | |||||||||||
| 251 | sub search () { | ||||||||||
| 252 | stream_iota->take(2**16)->map(\&buildmatrix)->filter(\&checks) | ||||||||||
| 253 | } | ||||||||||
| 254 | |||||||||||
| 255 | if ($ENV{RUN_SLOW_TESTS}) { | ||||||||||
| 256 | my $results; | ||||||||||
| 257 | TEST { | ||||||||||
| 258 | $results = search->array; | ||||||||||
| 259 | array_length $results | ||||||||||
| 260 | } | ||||||||||
| 261 | 2; | ||||||||||
| 262 | |||||||||||
| 263 | TEST { | ||||||||||
| 264 | array_length array_filter(sub($v) { equal $v, $onesolution }, $results) | ||||||||||
| 265 | } | ||||||||||
| 266 | 1; | ||||||||||
| 267 | |||||||||||
| 268 | my $sorted; | ||||||||||
| 269 | TEST { | ||||||||||
| 270 | $sorted = array_sort $results, on \&matrix_numrelations, \&real_cmp; | ||||||||||
| 271 | [matrix_numrelations($$sorted[0]), matrix_numrelations($$sorted[-1])] | ||||||||||
| 272 | } | ||||||||||
| 273 | [7, 8]; | ||||||||||
| 274 | |||||||||||
| 275 | } | ||||||||||
| 276 | |||||||||||
| 277 | perhaps_run_tests "main" or repl; | ||||||||||