-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
875 lines (838 loc) · 31.3 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<!-- 2017-03-07 Tue 21:02 -->
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>General Problem Solver in Python</title>
<meta name="generator" content="Org mode" />
<meta name="author" content="benrudgers" />
<style type="text/css">
<!--/*--><![CDATA[/*><!--*/
.title { text-align: center;
margin-bottom: .2em; }
.subtitle { text-align: center;
font-size: medium;
font-weight: bold;
margin-top:0; }
.todo { font-family: monospace; color: red; }
.done { font-family: monospace; color: green; }
.priority { font-family: monospace; color: orange; }
.tag { background-color: #eee; font-family: monospace;
padding: 2px; font-size: 80%; font-weight: normal; }
.timestamp { color: #bebebe; }
.timestamp-kwd { color: #5f9ea0; }
.org-right { margin-left: auto; margin-right: 0px; text-align: right; }
.org-left { margin-left: 0px; margin-right: auto; text-align: left; }
.org-center { margin-left: auto; margin-right: auto; text-align: center; }
.underline { text-decoration: underline; }
#postamble p, #preamble p { font-size: 90%; margin: .2em; }
p.verse { margin-left: 3%; }
pre {
border: 1px solid #ccc;
box-shadow: 3px 3px 3px #eee;
padding: 8pt;
font-family: monospace;
overflow: auto;
margin: 1.2em;
}
pre.src {
position: relative;
overflow: visible;
padding-top: 1.2em;
}
pre.src:before {
display: none;
position: absolute;
background-color: white;
top: -10px;
right: 10px;
padding: 3px;
border: 1px solid black;
}
pre.src:hover:before { display: inline;}
/* Languages per Org manual */
pre.src-asymptote:before { content: 'Asymptote'; }
pre.src-awk:before { content: 'Awk'; }
pre.src-C:before { content: 'C'; }
/* pre.src-C++ doesn't work in CSS */
pre.src-clojure:before { content: 'Clojure'; }
pre.src-css:before { content: 'CSS'; }
pre.src-D:before { content: 'D'; }
pre.src-ditaa:before { content: 'ditaa'; }
pre.src-dot:before { content: 'Graphviz'; }
pre.src-calc:before { content: 'Emacs Calc'; }
pre.src-emacs-lisp:before { content: 'Emacs Lisp'; }
pre.src-fortran:before { content: 'Fortran'; }
pre.src-gnuplot:before { content: 'gnuplot'; }
pre.src-haskell:before { content: 'Haskell'; }
pre.src-java:before { content: 'Java'; }
pre.src-js:before { content: 'Javascript'; }
pre.src-latex:before { content: 'LaTeX'; }
pre.src-ledger:before { content: 'Ledger'; }
pre.src-lisp:before { content: 'Lisp'; }
pre.src-lilypond:before { content: 'Lilypond'; }
pre.src-lua:before { content: 'Lua'; }
pre.src-matlab:before { content: 'MATLAB'; }
pre.src-mscgen:before { content: 'Mscgen'; }
pre.src-ocaml:before { content: 'Objective Caml'; }
pre.src-octave:before { content: 'Octave'; }
pre.src-org:before { content: 'Org mode'; }
pre.src-oz:before { content: 'OZ'; }
pre.src-plantuml:before { content: 'Plantuml'; }
pre.src-processing:before { content: 'Processing.js'; }
pre.src-python:before { content: 'Python'; }
pre.src-R:before { content: 'R'; }
pre.src-ruby:before { content: 'Ruby'; }
pre.src-sass:before { content: 'Sass'; }
pre.src-scheme:before { content: 'Scheme'; }
pre.src-screen:before { content: 'Gnu Screen'; }
pre.src-sed:before { content: 'Sed'; }
pre.src-sh:before { content: 'shell'; }
pre.src-sql:before { content: 'SQL'; }
pre.src-sqlite:before { content: 'SQLite'; }
/* additional languages in org.el's org-babel-load-languages alist */
pre.src-forth:before { content: 'Forth'; }
pre.src-io:before { content: 'IO'; }
pre.src-J:before { content: 'J'; }
pre.src-makefile:before { content: 'Makefile'; }
pre.src-maxima:before { content: 'Maxima'; }
pre.src-perl:before { content: 'Perl'; }
pre.src-picolisp:before { content: 'Pico Lisp'; }
pre.src-scala:before { content: 'Scala'; }
pre.src-shell:before { content: 'Shell Script'; }
pre.src-ebnf2ps:before { content: 'ebfn2ps'; }
/* additional language identifiers per "defun org-babel-execute"
in ob-*.el */
pre.src-cpp:before { content: 'C++'; }
pre.src-abc:before { content: 'ABC'; }
pre.src-coq:before { content: 'Coq'; }
pre.src-groovy:before { content: 'Groovy'; }
/* additional language identifiers from org-babel-shell-names in
ob-shell.el: ob-shell is the only babel language using a lambda to put
the execution function name together. */
pre.src-bash:before { content: 'bash'; }
pre.src-csh:before { content: 'csh'; }
pre.src-ash:before { content: 'ash'; }
pre.src-dash:before { content: 'dash'; }
pre.src-ksh:before { content: 'ksh'; }
pre.src-mksh:before { content: 'mksh'; }
pre.src-posh:before { content: 'posh'; }
/* Additional Emacs modes also supported by the LaTeX listings package */
pre.src-ada:before { content: 'Ada'; }
pre.src-asm:before { content: 'Assembler'; }
pre.src-caml:before { content: 'Caml'; }
pre.src-delphi:before { content: 'Delphi'; }
pre.src-html:before { content: 'HTML'; }
pre.src-idl:before { content: 'IDL'; }
pre.src-mercury:before { content: 'Mercury'; }
pre.src-metapost:before { content: 'MetaPost'; }
pre.src-modula-2:before { content: 'Modula-2'; }
pre.src-pascal:before { content: 'Pascal'; }
pre.src-ps:before { content: 'PostScript'; }
pre.src-prolog:before { content: 'Prolog'; }
pre.src-simula:before { content: 'Simula'; }
pre.src-tcl:before { content: 'tcl'; }
pre.src-tex:before { content: 'TeX'; }
pre.src-plain-tex:before { content: 'Plain TeX'; }
pre.src-verilog:before { content: 'Verilog'; }
pre.src-vhdl:before { content: 'VHDL'; }
pre.src-xml:before { content: 'XML'; }
pre.src-nxml:before { content: 'XML'; }
/* add a generic configuration mode; LaTeX export needs an additional
(add-to-list 'org-latex-listings-langs '(conf " ")) in .emacs */
pre.src-conf:before { content: 'Configuration File'; }
table { border-collapse:collapse; }
caption.t-above { caption-side: top; }
caption.t-bottom { caption-side: bottom; }
td, th { vertical-align:top; }
th.org-right { text-align: center; }
th.org-left { text-align: center; }
th.org-center { text-align: center; }
td.org-right { text-align: right; }
td.org-left { text-align: left; }
td.org-center { text-align: center; }
dt { font-weight: bold; }
.footpara { display: inline; }
.footdef { margin-bottom: 1em; }
.figure { padding: 1em; }
.figure p { text-align: center; }
.inlinetask {
padding: 10px;
border: 2px solid gray;
margin: 10px;
background: #ffffcc;
}
#org-div-home-and-up
{ text-align: right; font-size: 70%; white-space: nowrap; }
textarea { overflow-x: auto; }
.linenr { font-size: smaller }
.code-highlighted { background-color: #ffff00; }
.org-info-js_info-navigation { border-style: none; }
#org-info-js_console-label
{ font-size: 10px; font-weight: bold; white-space: nowrap; }
.org-info-js_search-highlight
{ background-color: #ffff00; color: #000000; font-weight: bold; }
.org-svg { width: 90%; }
/*]]>*/-->
</style>
<script type="text/javascript">
/*
@licstart The following is the entire license notice for the
JavaScript code in this tag.
Copyright (C) 2012-2013 Free Software Foundation, Inc.
The JavaScript code in this tag is free software: you can
redistribute it and/or modify it under the terms of the GNU
General Public License (GNU GPL) as published by the Free Software
Foundation, either version 3 of the License, or (at your option)
any later version. The code is distributed WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU GPL for more details.
As additional permission under GNU GPL version 3 section 7, you
may distribute non-source (e.g., minimized or compacted) forms of
that code without the copy of the GNU GPL normally required by
section 4, provided you include this license notice and a URL
through which recipients can access the Corresponding Source.
@licend The above is the entire license notice
for the JavaScript code in this tag.
*/
<!--/*--><![CDATA[/*><!--*/
function CodeHighlightOn(elem, id)
{
var target = document.getElementById(id);
if(null != target) {
elem.cacheClassElem = elem.className;
elem.cacheClassTarget = target.className;
target.className = "code-highlighted";
elem.className = "code-highlighted";
}
}
function CodeHighlightOff(elem, id)
{
var target = document.getElementById(id);
if(elem.cacheClassElem)
elem.className = elem.cacheClassElem;
if(elem.cacheClassTarget)
target.className = elem.cacheClassTarget;
}
/*]]>*///-->
</script>
</head>
<body>
<div id="content">
<h1 class="title">General Problem Solver in Python</h1>
<div id="table-of-contents">
<h2>Table of Contents</h2>
<div id="text-table-of-contents">
<ul>
<li><a href="#org4e3a070">Introduction</a>
<ul>
<li><a href="#org3612d34">So why Python?</a></li>
<li><a href="#orge0162ff">General Approach</a></li>
</ul>
</li>
<li><a href="#orge668204">General Problem Solver</a>
<ul>
<li><a href="#org6c37e61">Special Variables</a></li>
<li><a href="#orgc2e3110">Data Structure</a></li>
<li><a href="#orga58342b">GPS</a>
<ul>
<li><a href="#org83fd798"><span class="todo TODO">TODO</span> verify find_all_if versus find_all</a></li>
</ul>
</li>
<li><a href="#orgfe9d5a0">Major Functions</a>
<ul>
<li><a href="#orgc148258">achieve_all</a></li>
<li><a href="#orgb167cf2">achieve_each</a></li>
<li><a href="#org01a3044">achieve</a></li>
<li><a href="#org3fb4dc9">appropriate_p</a></li>
<li><a href="#org77d5262">apply_op</a></li>
<li><a href="#org61975b0">appropriate_ops</a></li>
</ul>
</li>
<li><a href="#org0d0cdf9">Auxilary Functions</a>
<ul>
<li><a href="#org01cb97d">action_p</a></li>
<li><a href="#org873a77e">convert-op</a></li>
<li><a href="#org0b1c7b3">executing_p</a></li>
<li><a href="#org0536d27">find_all</a></li>
<li><a href="#org96c3ec2">mappend</a></li>
<li><a href="#org3cdef2f">member_equal</a></li>
<li><a href="#orgb377076">op</a></li>
<li><a href="#org5fc5f7f">remove_if_not</a></li>
<li><a href="#org1763f37">starts_with</a></li>
<li><a href="#org8a7788b">use</a></li>
</ul>
</li>
</ul>
</li>
<li><a href="#orgf9dae19">Knowledge Bases</a>
<ul>
<li><a href="#org5b0de6e">School Ops</a></li>
<li><a href="#org72b147a">Monkey Ops</a></li>
<li><a href="#orgb9b36af">Maze Ops</a></li>
</ul>
</li>
<li><a href="#org1e2b2cb">Applications</a>
<ul>
<li><a href="#org5fcb7da">School Ops</a></li>
<li><a href="#org3a2a18b">Monkey Ops</a></li>
<li><a href="#orgb2afa8c">Maze Ops</a></li>
</ul>
</li>
<li><a href="#org1b92059">Debugger</a>
<ul>
<li><a href="#org4de978f">dbg ids</a></li>
<li><a href="#org07bde85">dbg</a></li>
<li><a href="#orgfed795e">debug</a></li>
<li><a href="#org88d1083">undebug</a></li>
<li><a href="#org8f666a7">debug indent</a></li>
</ul>
</li>
<li><a href="#orgc533a21">Utilities</a>
<ul>
<li><a href="#org5cc0297">cons</a></li>
<li><a href="#org6090473">first</a></li>
<li><a href="#org4b7683d">rest</a></li>
<li><a href="#orgee5e9bc">list_append</a></li>
</ul>
</li>
</ul>
</div>
</div>
<div id="outline-container-org4e3a070" class="outline-2">
<h2 id="org4e3a070">Introduction</h2>
<div class="outline-text-2" id="text-org4e3a070">
<p>
This is a 'port' of Norvig's General Problem Solver from Norvig's Common Lisp code to my own Python. While my intent with the exercise includes learning a bit more Python, the big goal is to ensure a better understanding of the General Problem Solver. Just as typing in code from a book creates deeper understanding than mere reading, I suspect that rewriting a program in a second language increases the understanding even more so…yeah, it's a theory.
</p>
</div>
<div id="outline-container-org3612d34" class="outline-3">
<h3 id="org3612d34">So why Python?</h3>
<div class="outline-text-3" id="text-org3612d34">
<p>
Practically speaking, rewriting GPS in another Lisp (such as Clojure or Racket or Arc) smells a bit sour as an intellectual exercise. On the other hand, Norvig's handy <a href="http://norvig.com/python-lisp.html"><i>Python for Lisp Programmers</i></a> means there's an external basis for rewriting in Python and some signposts on how to proceed.
</p>
</div>
</div>
<div id="outline-container-orge0162ff" class="outline-3">
<h3 id="orge0162ff">General Approach</h3>
<div class="outline-text-3" id="text-orge0162ff">
<p>
The primary goal is working code by porting the Common Lisp to Python. Isomorphism between the code bases may wind up being a stronger condiseration than idiomatic Python. There's always time for refactoring later. However, the code base will reflect Norvig's completed version of GPS rather than following the iterative process in his book.
</p>
</div>
</div>
</div>
<div id="outline-container-orge668204" class="outline-2">
<h2 id="orge668204">General Problem Solver</h2>
<div class="outline-text-2" id="text-orge668204">
<p>
The outline for this Python implementation follows the structure of my Common Lisp implementation…for better or worse.
</p>
<div class="org-src-container">
<pre class="src src-python" id="org7107b0a"># gps.py
# This file autogenerated from gps_py.org
<<special-variables>>
<<op-data-structure>>
<<gps-function>>
# Utilities
<<cons>>
<<first>>
</pre>
</div>
</div>
<div id="outline-container-org6c37e61" class="outline-3">
<h3 id="org6c37e61">Special Variables</h3>
<div class="outline-text-3" id="text-org6c37e61">
<p>
The global variables follow the convention used by the debugger.
</p>
<div class="org-src-container">
<pre class="src src-python" id="orgc055c2e"># Special Variables
_ops_ = []
</pre>
</div>
</div>
</div>
<div id="outline-container-orgc2e3110" class="outline-3">
<h3 id="orgc2e3110">Data Structure</h3>
<div class="outline-text-3" id="text-orgc2e3110">
<p>
An <code>op</code> has four fields. The Common Lisp implementation uses <code>defstruct</code>. There is not a clear equivalent data structure in Python. So here are a number of alternatives for representing the data structure. Dictionaries seemed like a reasonable alternative. But would require writing constructor functions to initialize the fields of dictionary objects. Named tuples seemed like another alternative and have the advantage of immutability. The probelm there is that using <code>my_tuple.replace(action</code>[spam, eggs])= when <code>my_tuple</code> is in a list of <code>namedtuple</code> requires pointer maintenance because Python lists are place based. Again there's book keeping.
</p>
<p>
So objects it is.
</p>
<div class="org-src-container">
<pre class="src src-python" id="org3036520"># Data Structure
class Op:
"""
An action is the basis of an operation.
An action can only occur if all its preconditions exist in the execution environment.
An action changes the state of the world by:
1. adding the conditions in its add_list to the environment.
2. removing the conditions in its del_list from the enviroment.
"""
def __init__(self, action=[], preconds=[], add_list=[], del_list=[]):
self.action = action
self.preconds = preconds
self.add_list = add_list
self.del_list = del_list
def __repr__(self):
return str(vars(self))
</pre>
</div>
</div>
</div>
<div id="outline-container-orga58342b" class="outline-3">
<h3 id="orga58342b">GPS</h3>
<div class="outline-text-3" id="text-orga58342b">
<div class="org-src-container">
<pre class="src src-python" id="orgb9de017">def gps(state, goal, ops=_ops_):
"""
General Problem Solver: from state achieve goal using ops.
"""
return find_all_if(action_p, achieve_all(cons ('start', state)), goals, [])
</pre>
</div>
</div>
<div id="outline-container-org83fd798" class="outline-4">
<h4 id="org83fd798"><span class="todo TODO">TODO</span> verify find_all_if versus find_all</h4>
</div>
</div>
<div id="outline-container-orgfe9d5a0" class="outline-3">
<h3 id="orgfe9d5a0">Major Functions</h3>
<div class="outline-text-3" id="text-orgfe9d5a0">
</div><div id="outline-container-orgc148258" class="outline-4">
<h4 id="orgc148258">achieve_all</h4>
<div class="outline-text-4" id="text-orgc148258">
<div class="org-src-container">
<pre class="src src-python" id="org59449ab">def achieve_all(state, goals, goal_stack):
return [g for g in orderings(goals) if any achieve_each(state, g, goal_stack)]
</pre>
</div>
</div>
</div>
<div id="outline-container-orgb167cf2" class="outline-4">
<h4 id="orgb167cf2">achieve_each</h4>
<div class="outline-text-4" id="text-orgb167cf2">
<p>
The critical bit of code in <code>achieve_each</code> is to create a mutable copy of the global state. There are several ways to do this in Python, one way is to create a mutable object such as a <code>list</code>. Here a <code>class</code> is used instead.
</p>
<div class="org-src-container">
<pre class="src src-python" id="org7581285">def achieve_each(state, goals, goal_stack):
"""Achieve each goal and make sure that they all hold at the end"""
# the function will mutate state
# but don't mutate the current state
class Obj:
Obj.current_state = state
# achieve a goal using the local version of the state
# and update the local copy of state
def f(goal):
Obj.current_state = achieve(Obj.current_state, goal, goal_stack)
# make sure each goal is achievable on its own
# and that no goal clobbers another goal
if all(map(f, goals)) and set(goals) < set(Obj.current_state):
return Obj.current_state
</pre>
</div>
</div>
</div>
<div id="outline-container-org01a3044" class="outline-4">
<h4 id="org01a3044">achieve</h4>
<div class="outline-text-4" id="text-org01a3044">
<div class="org-src-container">
<pre class="src src-python" id="org803bf85">def achieve(state, goal, goal_stack):
"""
A goal is achieved when it already holds
or if there is an appropriate op that
is applicable.
"""
# make debugger available
debug_indent('gps', len(goal_stack), 'Goal: {}'.format(goal))
# local function keep line length down
def a_lambda(op):
return apply_op(state, goal, op, goal_stack)
# main logic
if goal in state:
return state
elif goal in goal_stack:
return False
else return any(op for op in map(a_lambda, appropriate_ops(goal, state)))
</pre>
</div>
</div>
</div>
<div id="outline-container-org3fb4dc9" class="outline-4">
<h4 id="org3fb4dc9">appropriate_p</h4>
</div>
<div id="outline-container-org77d5262" class="outline-4">
<h4 id="org77d5262">apply_op</h4>
</div>
<div id="outline-container-org61975b0" class="outline-4">
<h4 id="org61975b0">appropriate_ops</h4>
<div class="outline-text-4" id="text-org61975b0">
<p>
The Common Lisp version of this function uses quite a bit of the language's built in list handling to do a lot in a little space.
</p>
<div class="org-src-container">
<pre class="src src-python" id="orgcee1763">def appropriate_ops(goal, state):
"""
Return a list of appropriate operators
sorted by the number of unfilled preconditions.
"""
<<appropriate-ops-key>>
</pre>
</div>
<p>
One of the features the Lisp version uses is a <code>:key</code> for the sort command. It takes an op and counts how many of its preconditions are not met in the current state.
</p>
<div class="org-src-container">
<pre class="src src-python" id="org89c1ebc">def appropriate_ops_sort_key(op):
"""A closure over the external value state"""
return len([p for p in op.preconds if p not in state])
</pre>
</div>
</div>
</div>
</div>
<div id="outline-container-org0d0cdf9" class="outline-3">
<h3 id="org0d0cdf9">Auxilary Functions</h3>
<div class="outline-text-3" id="text-org0d0cdf9">
</div><div id="outline-container-org01cb97d" class="outline-4">
<h4 id="org01cb97d">action_p</h4>
<div class="outline-text-4" id="text-org01cb97d">
<div class="org-src-container">
<pre class="src src-python" id="orgbd6086d">def action_p(x):
"""
Is x the start start state or an executing form.
"""
return x == ['start'] or executing_p(x)
</pre>
</div>
</div>
</div>
<div id="outline-container-org873a77e" class="outline-4">
<h4 id="org873a77e">convert-op</h4>
<div class="outline-text-4" id="text-org873a77e">
<p>
The executing convention adds a sense of time transition to the world by handling actions such as <code>run_around_block</code> as a change to the world state. To implement the convention, every <code>op</code> has at least one executing form in <code>op.add_list</code>. The default executing form when no other executing form is present is <code>['executing', op.action]</code>. <code>convert-op</code> adds the default to an <code>op</code> if none is present.
</p>
<div class="org-src-container">
<pre class="src src-python" id="org9dcbe4a">def convert_op(op):
"""
op -> NONE
Make op conform to the ['executing', op] convention.
"""
add_list = op.add_list
some_executing = any(executing_p(item) for item in add_list)
if not some_executing: # aka unless
op.add_list = cons(['executing', op.action], add_list)
</pre>
</div>
</div>
</div>
<div id="outline-container-org0b1c7b3" class="outline-4">
<h4 id="org0b1c7b3">executing_p</h4>
<div class="outline-text-4" id="text-org0b1c7b3">
<div class="org-src-container">
<pre class="src src-python" id="orgbe3a64a">def executing_p(x):
"""
Is the form ['executing' ...]?
"""
return starts_with(x, 'executing')
</pre>
</div>
</div>
</div>
<div id="outline-container-org0536d27" class="outline-4">
<h4 id="org0536d27">find_all</h4>
<div class="outline-text-4" id="text-org0536d27">
<p>
The version here is simpler than the version Norvig provides in that it does not have a wide range of options as is typical for Common Lisp functions.
</p>
<div class="org-src-container">
<pre class="src src-python" id="org5fbddbb">def find_all(a_list, test, not_test=False):
"""
List -> List
Non-mutating.
Finds all the elements of a list that pass the test if not_test is False.
If not_test evaluates to True, returns all elements that do not pass the test.
"""
if not_test:
return [element for element in a_list if not test(element)]
else:
return [element for element in a_list if test(element)]
</pre>
</div>
</div>
</div>
<div id="outline-container-org96c3ec2" class="outline-4">
<h4 id="org96c3ec2">mappend</h4>
</div>
<div id="outline-container-org3cdef2f" class="outline-4">
<h4 id="org3cdef2f">member_equal</h4>
</div>
<div id="outline-container-orgb377076" class="outline-4">
<h4 id="orgb377076">op</h4>
</div>
<div id="outline-container-org5fc5f7f" class="outline-4">
<h4 id="org5fc5f7f">remove_if_not</h4>
</div>
<div id="outline-container-org1763f37" class="outline-4">
<h4 id="org1763f37">starts_with</h4>
<div class="outline-text-4" id="text-org1763f37">
<div class="org-src-container">
<pre class="src src-python" id="org0d88b79">def starts_with (a_list x):
"""
Is this a list that starts with x?
"""
return type(a_list) is list and first(a_list) == x
</pre>
</div>
</div>
</div>
<div id="outline-container-org8a7788b" class="outline-4">
<h4 id="org8a7788b">use</h4>
</div>
</div>
</div>
<div id="outline-container-orgf9dae19" class="outline-2">
<h2 id="orgf9dae19">Knowledge Bases</h2>
<div class="outline-text-2" id="text-orgf9dae19">
</div><div id="outline-container-org5b0de6e" class="outline-3">
<h3 id="org5b0de6e">School Ops</h3>
</div>
<div id="outline-container-org72b147a" class="outline-3">
<h3 id="org72b147a">Monkey Ops</h3>
</div>
<div id="outline-container-orgb9b36af" class="outline-3">
<h3 id="orgb9b36af">Maze Ops</h3>
</div>
</div>
<div id="outline-container-org1e2b2cb" class="outline-2">
<h2 id="org1e2b2cb">Applications</h2>
<div class="outline-text-2" id="text-org1e2b2cb">
</div><div id="outline-container-org5fcb7da" class="outline-3">
<h3 id="org5fcb7da">School Ops</h3>
</div>
<div id="outline-container-org3a2a18b" class="outline-3">
<h3 id="org3a2a18b">Monkey Ops</h3>
</div>
<div id="outline-container-orgb2afa8c" class="outline-3">
<h3 id="orgb2afa8c">Maze Ops</h3>
</div>
</div>
<div id="outline-container-org1b92059" class="outline-2">
<h2 id="org1b92059">Debugger</h2>
<div class="outline-text-2" id="text-org1b92059">
<p>
One of the fun parts of Norvig's approach is building something rather than searching for someone else's tool. The simple debugger he implements for GPS seems like a good place to start.
</p>
<div class="org-src-container">
<pre class="src src-python" id="orge7b9fbd"># debugger.py
# This file autogenerated from gps_py.org
<<dbg_ids>>
<<dbg>>
<<debug>>
<<undebug>>
<<dbg_indent>>
</pre>
</div>
</div>
<div id="outline-container-org4de978f" class="outline-3">
<h3 id="org4de978f">dbg ids</h3>
<div class="outline-text-3" id="text-org4de978f">
<p>
I used leading underscores to indicate there is something a bit special about the variable as an isomorphism to the asterisks in <code>*dbg-ids*</code> from Common Lisp.
</p>
<div class="org-src-container">
<pre class="src src-python" id="org553ef47"># Identifiers used by dbg.
_dbg_ids_ = []
</pre>
</div>
</div>
</div>
<div id="outline-container-org07bde85" class="outline-3">
<h3 id="org07bde85">dbg</h3>
<div class="outline-text-3" id="text-org07bde85">
<p>
Uses <code>target</code> instead of 'id'. May need to import <code>sys</code> and <code>write</code> to a different stream.
</p>
<div class="org-src-container">
<pre class="src src-python" id="org2a34005">def dbg (target, format_string, *args):
"""Print debugging information if target has been specified"""
if target in _dbg_ids_:
print(format_string.format(args))
</pre>
</div>
</div>
</div>
<div id="outline-container-orgfed795e" class="outline-3">
<h3 id="orgfed795e">debug</h3>
<div class="outline-text-3" id="text-orgfed795e">
<div class="org-src-container">
<pre class="src src-python" id="org9d0123f">def debug(*ids):
"""Start dbg output the given ids."""
global _dbg_ids_
_dbg_ids_ = _dbg_ids_ + list(ids)
</pre>
</div>
</div>
</div>
<div id="outline-container-org88d1083" class="outline-3">
<h3 id="org88d1083">undebug</h3>
<div class="outline-text-3" id="text-org88d1083">
<p>
Python does not have set semantics for lists so I had to make <code>list_diff</code>, or rather I made <code>list_diff</code> so that <code>undebug</code> would have the appropriate level of abstraction. It seems to me that incorporating a list comprehension within <code>undebug</code> sort of gets in the way of readability…particularly because the list comprehension contains a negative statement.
</p>
<p>
I used <code>minuend</code> and <code>subtrahend</code> per <a href="https://en.wikipedia.org/wiki/Subtraction">Wikipedia</a>.
</p>
<p>
Python requires the <code>global</code> keyword to perform the assignment to <code>_dbg_ids_</code> because the <code>=</code> operator makes the variable locally scoped.
</p>
<div class="org-src-container">
<pre class="src src-python" id="org7a53908">def list_diff(minuend, subtrahend):
"""Remove the elements of the subtrahend from the minuend."""
return [val for val in minuend if val not in subtrahend]
def undebug(*ids):
"""Stop dbg on the ids. If no ids, stop all debugging"""
global _dbg_ids_
if ids:
_dbg_ids_ = list_diff(_dbg_ids_, list(ids))
else:
_dbg_ids_ = []
</pre>
</div>
</div>
</div>
<div id="outline-container-org8f666a7" class="outline-3">
<h3 id="org8f666a7">debug indent</h3>
<div class="outline-text-3" id="text-org8f666a7">
<div class="org-src-container">
<pre class="src src-python" id="org41f4a81">def dbg_indent (target, indent, format_string, *args):
"""Print indented debugging info if target has been specified"""
if target in _dbg_ids_:
s = ""
for i in range(indent):
s += " "
s = s + format_string
print(s.format(args))
</pre>
</div>
</div>
</div>
</div>
<div id="outline-container-orgc533a21" class="outline-2">
<h2 id="orgc533a21">Utilities</h2>
<div class="outline-text-2" id="text-orgc533a21">
<p>
Since the first goal is to port code from Common Lisp it probably makes sense to have a some tools for handling lists in a familiar way. All of this can be refactored later.
</p>
</div>
<div id="outline-container-org5cc0297" class="outline-3">
<h3 id="org5cc0297">cons</h3>
<div class="outline-text-3" id="text-org5cc0297">
<p>
Where to start but with <code>cons</code>. It's not that Python doesn't have the ability to add to lists, it's just that trying to translate from front to rear addition is probably not the best place to start.
</p>
<div class="org-src-container">
<pre class="src src-python" id="orgd965cb9">def cons (element, a_list):
"""
Adds an elment to the *front* of a_list.
If a_list is not a list, cons creates a list of one element holding a_list.
"""
if not type(a_list) == list:
a_list = [a_list]
a = [element]
a.extend(a_list)
return a
</pre>
</div>
</div>
</div>
<div id="outline-container-org6090473" class="outline-3">
<h3 id="org6090473">first</h3>
<div class="outline-text-3" id="text-org6090473">
<div class="org-src-container">
<pre class="src src-python" id="org5b9770b">def first(a_list):
"""
Returns the first elment of a list.
Returns False if the list is empty.
"""
if len(a_list)==0:
return False
else:
return a_list[0]
</pre>
</div>
</div>
</div>
<div id="outline-container-org4b7683d" class="outline-3">
<h3 id="org4b7683d">rest</h3>
<div class="outline-text-3" id="text-org4b7683d">
<div class="org-src-container">
<pre class="src src-python" id="orgfbe1cd1">def rest(a_list):
"""
Returns a list minus its first elment.
Returns false if list is empty.
Returns the empty list if list has one element.
"""
if len(a_list)==0:
return False
elif len(a_list)==1:
return []
else:
return a_list[1:]
</pre>
</div>
</div>
</div>
<div id="outline-container-orgee5e9bc" class="outline-3">
<h3 id="orgee5e9bc">list_append</h3>
<div class="outline-text-3" id="text-orgee5e9bc">
<p>
Python has an <code>append</code> function that adds an element onto the end of a list. While the <code>+</code> operator will concatenate two lists, my quick and dirty testing indicates it cannot be passed directly to <code>reduce</code>.
</p>
<pre class="example">
# Example
>>> reduce(+, [[1],[2],[3]])
File "<stdin>", line 1
reduce(+, [[1],[2],[3]])
^
SyntaxError: invalid syntax
</pre>
<p>
The call to <code>+</code> must be wrapped in a <code>lambda</code>. It works and it's not terrible
</p>
<pre class="example">
# Example
reduce(lambda x,y: x + y, [[1],[2],[3]])
# => [1, 2, 3]
</pre>
<p>
This means that mapping an append operation starts to look like lambdas inside of lambdas and that smells to me like a breakdown of abstraction layers.
</p>
<p>
In the end, a function that works with lists just feels right to me. It can be fed to <code>reduce</code> or its equivalent list comprehension. Having a meaningful name is useful.
</p>
<div class="org-src-container">
<pre class="src src-python" id="orgc7fc474">def list_append(list_1, list_2):
return list_1 + list_2
</pre>
</div>
</div>
</div>
</div>
</div>
<div id="postamble" class="status">
<p class="author">Author: benrudgers</p>
<p class="date">Created: 2017-03-07 Tue 21:02</p>
<p class="validation"><a href="http://validator.w3.org/check?uri=referer">Validate</a></p>
</div>
</body>
</html>