Repository navigation
Expand file tree
/
Copy path9_trees_and_directed_acyclic_graphs.html
More file actions
1179 lines (1121 loc) · 118 KB
/
Copy path9_trees_and_directed_acyclic_graphs.html
File metadata and controls
1179 lines (1121 loc) · 118 KB
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
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="en" data-content_root="./">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="viewport" content="width=device-width, initial-scale=1" />
<title>9. Trees and directed acyclic graphs — Object-oriented Programming documentation</title>
<link rel="stylesheet" type="text/css" href="_static/pygments.css?v=03e43079" />
<link rel="stylesheet" type="text/css" href="_static/fenics.css?v=8c7d05f9" />
<link rel="stylesheet" type="text/css" href="_static/proof.css" />
<link rel="stylesheet" type="text/css" href="_static/graphviz.css?v=fd3f3429" />
<script src="_static/documentation_options.js?v=5929fcd5"></script>
<script src="_static/doctools.js?v=9a2dae69"></script>
<script src="_static/sphinx_highlight.js?v=dc90522c"></script>
<script src="_static/proof.js"></script>
<script async="async" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<link rel="index" title="Index" href="genindex.html" />
<link rel="search" title="Search" href="search.html" />
<link rel="next" title="10. Further object-oriented features" href="10_further_object-oriented_features.html" />
<link rel="prev" title="8. Debugging and testing" href="8_debugging.html" />
<!--[if lte IE 6]>
<link rel="stylesheet" href="_static/ie6.css" type="text/css" media="screen" charset="utf-8" />
<![endif]-->
<!-- Global site tag (gtag.js) - Google Analytics -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-0EFVH5C4DC"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'G-0EFVH5C4DC');
</script>
<link rel="stylesheet" href="_static/featured.css">
<link rel="shortcut icon" href="_static/icon.ico" />
</head><body>
<div class="wrapper">
<a href="index.html"><img src="_static/banner.png" width="900px" alt="FInAT Project Banner" /></a>
<div id="access">
<div class="menu">
<ul>
<li class="page_item"><a href="index.html" title="Book">Book</a></li>
<li class="page_item"><a href="videos.html" title="Videos">Videos</a></li>
<li class="page_item"><a href="exercises.html"
title="Exercises">Exercises</a></li>
<li class="page_item"><a href="installation.html" title="Installation">Installation</a></li>
</ul>
</div><!-- .menu -->
</div><!-- #access -->
</div><!-- #wrapper -->
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<section id="trees-and-directed-acyclic-graphs">
<span id="trees"></span><h1><span class="section-number">9. </span>Trees and directed acyclic graphs<a class="headerlink" href="#trees-and-directed-acyclic-graphs" title="Link to this heading">¶</a></h1>
<p>The <a class="reference internal" href="5_abstract_data_types.html#term-abstract-data-type"><span class="xref std std-term">abstract data types</span></a> that we met in
<a class="reference internal" href="5_abstract_data_types.html#abstract-data-types"><span class="std std-numref">Chapter 5</span></a> were all fairly simple sequences of
objects that were extensible in different ways. If that were all the sum total
of abstract data types then the reader might reasonably wonder what all the
fuss is about. In this chapter we’ll look at <a class="reference internal" href="#term-tree"><span class="xref std std-term">trees</span></a> and
<a class="reference internal" href="#term-directed-acyclic-graph"><span class="xref std std-term">directed acyclic graphs (DAGs)</span></a>, which are
abstract data types which look very different from the ones we’ve met so far.</p>
<p>Trees and DAGs provide some great examples of <a class="reference internal" href="7_inheritance.html#term-inheritance"><span class="xref std std-term">inheritance</span></a> and give us
the chance to look at some new algorithm types. They are also the core data
types underpinning computer algebra systems, so studying trees and DAGs will
enable us to gain a little insight into how systems such as <a class="reference external" href="https://www.sympy.org">SymPy</a>, <a class="reference external" href="https://www.maplesoft.com">Maple</a> and
<a class="reference external" href="https://www.wolfram.com/mathematica/">Mathematica</a> actually work. As we come
to the latter parts of the course, we’ll also step back a little from laying out
a lot of code, and instead focus on the mathematical structure of the objects in
question. When we come to the exercises, you will then take a little more
responsibility for translating the maths into code.</p>
<section id="the-splat-and-double-splat-operators">
<h2><span class="section-number">9.1. </span>The splat and double splat operators<a class="headerlink" href="#the-splat-and-double-splat-operators" title="Link to this heading">¶</a></h2>
<details>
<summary>
Video: splat and double splat.</summary><div class="video_wrapper" style="">
<iframe allowfullscreen="true" src="https://player.vimeo.com/video/523477744" style="border: 0; height: 345px; width: 560px">
</iframe></div><p>Imperial students can also <a class="reference external" href="https://imperial.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=a481be22-0df9-4aa1-bbed-ae1c00dba7a6">watch this video on Panopto</a>.</p>
</details><p>Before we go on to write code for trees and their traversal, we need to
digress ever so slightly in order to explain a new piece of syntax. We’re going
to want to write functions that can take a variable number of arguments. For
example, we’re going to want the <a class="reference internal" href="3_objects.html#term-constructor"><span class="xref std std-term">constructor</span></a> of a tree node object to
be able to take a variable number of children. We can do this by writing the
relevant parameter as <code class="xref py py-obj docutils literal notranslate"><span class="pre">*children</span></code>. The character <code class="xref py py-obj docutils literal notranslate"><span class="pre">*</span></code> in this case is the
argument packing operator, also known as the <em>splat</em> operator <a class="footnote-reference brackets" href="#splat" id="id1" role="doc-noteref"><span class="fn-bracket">[</span>2<span class="fn-bracket">]</span></a>. When
used in the parameter list of a function, splat takes all of the remaining
<a class="reference external" href="https://docs.python.org/3/glossary.html#term-argument" title="(in Python v3.15)"><span class="xref std std-term">positional arguments</span></a> provided by the caller and packs them
up in a tuple. In this case, this enables any number of child nodes to be
specified for each node.</p>
<p>The splat operator can also be used when calling a function. In that case it
acts as a sequence unpacking operator, turning a sequence into separate
arguments. For example:</p>
<div class="highlight-ipython3 notranslate"><div class="highlight"><pre><span></span><span class="gp">In [1]: </span><span class="n">a</span> <span class="o">=</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">)</span>
<span class="gp">In [2]: </span><span class="nb">print</span><span class="p">(</span><span class="o">*</span><span class="n">a</span><span class="p">)</span>
<span class="go">1 2 3</span>
</pre></div>
</div>
<p>which is identical to:</p>
<div class="highlight-ipython3 notranslate"><div class="highlight"><pre><span></span><span class="gp">In [3]: </span><span class="nb">print</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">)</span>
<span class="go">1 2 3</span>
</pre></div>
</div>
<p>but different from:</p>
<div class="highlight-ipython3 notranslate"><div class="highlight"><pre><span></span><span class="gp">In [4]: </span><span class="nb">print</span><span class="p">(</span><span class="n">a</span><span class="p">)</span>
<span class="go">(1, 2, 3)</span>
</pre></div>
</div>
<p>The double splat operator, <code class="xref py py-obj docutils literal notranslate"><span class="pre">**</span></code> plays a similar role to the single splat
operator, but packs and unpacks <a class="reference external" href="https://docs.python.org/3/glossary.html#term-argument" title="(in Python v3.15)"><span class="xref std std-term">keyword arguments</span></a> instead of
positional arguments. When used in the <a class="reference external" href="https://docs.python.org/3/glossary.html#term-parameter" title="(in Python v3.15)"><span class="xref std std-term">parameter</span></a> list of a function,
<code class="xref py py-obj docutils literal notranslate"><span class="pre">**</span></code> gathers all of the keyword arguments that the caller passes, other than any
which are explicitly named in the interface. The result is a <a class="reference external" href="https://docs.python.org/3/builtins/stdtypes.html#dict" title="(in Python v3.15)"><code class="xref py py-class docutils literal notranslate"><span class="pre">dict</span></code></a> whose
keys are the argument names, and whose values are the arguments.
<a class="reference internal" href="#kwarg-packing"><span class="std std-numref">Listing 9.1</span></a> demonstrates the argument packing function of <code class="xref py py-obj docutils literal notranslate"><span class="pre">**</span></code>,
while <a class="reference internal" href="#kwarg-unpacking"><span class="std std-numref">Listing 9.2</span></a> shows the unpacking function.</p>
<div class="literal-block-wrapper docutils container" id="id5">
<span id="kwarg-packing"></span><div class="code-block-caption"><span class="caption-number">Listing 9.1 </span><span class="caption-text">An illustration of keyword argument packing. All of the keyword
arguments are packed into the dictionary <code class="xref py py-data docutils literal notranslate"><span class="pre">kwargs</span></code>, except for <code class="xref py py-obj docutils literal notranslate"><span class="pre">b</span></code>,
because that explicitly appears in the parameter list of <code class="xref py py-func docutils literal notranslate"><span class="pre">fn()</span></code>.</span><a class="headerlink" href="#id5" title="Link to this code">¶</a></div>
<div class="highlight-ipython3 notranslate"><div class="highlight"><pre><span></span><span class="gp">In [1]: </span><span class="k">def</span><span class="w"> </span><span class="nf">fn</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">b</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
<span class="gp"> ...: </span> <span class="nb">print</span><span class="p">(</span><span class="s2">"a:"</span><span class="p">,</span> <span class="n">a</span><span class="p">)</span>
<span class="gp"> ...: </span> <span class="nb">print</span><span class="p">(</span><span class="s2">"b:"</span><span class="p">,</span> <span class="n">b</span><span class="p">)</span>
<span class="gp"> ...: </span> <span class="nb">print</span><span class="p">(</span><span class="s2">"kwargs:"</span><span class="p">,</span> <span class="n">kwargs</span><span class="p">)</span>
<span class="gp"> ...:</span>
<span class="gp">In [2]: </span><span class="n">fn</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="n">f</span><span class="o">=</span><span class="mi">3</span><span class="p">,</span> <span class="n">b</span><span class="o">=</span><span class="mi">2</span><span class="p">,</span> <span class="n">g</span><span class="o">=</span><span class="s2">"hello"</span><span class="p">)</span>
<span class="go">a: 1</span>
<span class="go">b: 2</span>
<span class="go">kwargs: {'f': 3, 'g': 'hello'}</span>
</pre></div>
</div>
</div>
<div class="literal-block-wrapper docutils container" id="id6">
<span id="kwarg-unpacking"></span><div class="code-block-caption"><span class="caption-number">Listing 9.2 </span><span class="caption-text">Keyword argument unpacking. Notice that the arguments matching the
explicitly named keywords are unpacked, while the remainder are repacked
into the <code class="xref py py-obj docutils literal notranslate"><span class="pre">**kwargs</span></code> parameter.</span><a class="headerlink" href="#id6" title="Link to this code">¶</a></div>
<div class="highlight-ipython3 notranslate"><div class="highlight"><pre><span></span><span class="gp">In [3]: </span><span class="n">kw</span> <span class="o">=</span> <span class="p">{</span><span class="s2">"a"</span><span class="p">:</span> <span class="s2">"mary"</span><span class="p">,</span> <span class="s2">"b"</span><span class="p">:</span> <span class="s2">"had"</span><span class="p">,</span> <span class="s2">"c"</span><span class="p">:</span> <span class="s2">"a"</span><span class="p">,</span> <span class="s2">"d"</span><span class="p">:</span> <span class="s2">"little"</span><span class="p">,</span>
<span class="go"> "e": "lamb"}</span>
<span class="gp">In [4]: </span><span class="n">fn</span><span class="p">(</span><span class="o">**</span><span class="n">kw</span><span class="p">)</span>
<span class="go">a: mary</span>
<span class="go">b: had</span>
<span class="go">kwargs: {'c': 'a', 'd': 'little', 'e': 'lamb'}</span>
</pre></div>
</div>
</div>
<p>Combining the splat and double splat operators, it is possible to write a
function that will accept any combination of positional and keyword arguments.
This is often useful if the function is intended to pass these arguments through
to another function, without knowing anything about that inner function. For
example:</p>
<div class="highlight-python3 notranslate"><div class="highlight"><pre><span></span><span class="k">def</span><span class="w"> </span><span class="nf">fn</span><span class="p">(</span><span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
<span class="o">...</span>
<span class="n">a</span> <span class="o">=</span> <span class="n">inner_fn</span><span class="p">(</span><span class="o">*</span><span class="n">args</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">)</span>
<span class="o">...</span>
</pre></div>
</div>
<p>The names <code class="xref py py-obj docutils literal notranslate"><span class="pre">*args</span></code> and <code class="xref py py-obj docutils literal notranslate"><span class="pre">**kwargs</span></code> are the conventional names in
cases where nothing more specific is known about the parameters in question.</p>
</section>
<section id="graph-and-tree-definitions">
<h2><span class="section-number">9.2. </span>Graph and tree definitions<a class="headerlink" href="#graph-and-tree-definitions" title="Link to this heading">¶</a></h2>
<p>Trees and DAGs are examples of graphs, a type of mathematical object that you
may have met in previous courses. Before moving on to define data structures
and algorithms that work with them, it’s helpful to state the relevant
definitions.</p>
<div class="proof proof-type-definition" id="id7">
<div class="proof-title">
<span class="proof-type">Definition 9.1</span>
<span class="proof-title-name">(Graph)</span>
</div><div class="proof-content">
<p>A <em>graph</em> <span class="math notranslate nohighlight">\((V, E)\)</span> is a set <span class="math notranslate nohighlight">\(V\)</span> known as the vertices or nodes,
and a set of pairs of vertices, <span class="math notranslate nohighlight">\(E\)</span>, known as the edges.</p>
</div></div><p>A graph describes connections between its vertices, and can be used to model a
huge range of interconnected networks. <a class="reference internal" href="#graph"><span class="std std-numref">Fig. 9.1</span></a> illustrates a simple example.</p>
<figure class="align-center" id="id8">
<span id="graph"></span><div class="graphviz"><object data="_images/graphviz-19785a8c31b0abdce6f7a6d4ea5bf08ec31097e7.svg" type="image/svg+xml" class="graphviz">
<p class="warning">strict graph{
a -- b
b -- c
b -- d
c -- f
f -- b
d -- a
f -- a
e -- c
e -- d
}</p></object></div>
<figcaption>
<p><span class="caption-number">Fig. 9.1 </span><span class="caption-text">A graphical representation of the graph <span class="math notranslate nohighlight">\((\{a, b, c, d, e,
f\},\)</span> <span class="math notranslate nohighlight">\(\{(a, b), (a, d), (a, f), (b, c), (b, d), (b, f), (c, e), (c, f), (d, e) \})\)</span></span><a class="headerlink" href="#id8" title="Link to this image">¶</a></p>
</figcaption>
</figure>
<figure class="align-center" id="id9">
<span id="digraph"></span><div class="graphviz"><object data="_images/graphviz-e2b7d1ccc0c7da231b3e144e5a28b96a831ca8f5.svg" type="image/svg+xml" class="graphviz">
<p class="warning">strict digraph{
a -> b [color=red]
b -> c
b -> d [color=red]
c -> f
f -> b
d -> a [color=red]
f -> a
e -> c
e -> d
}</p></object></div>
<figcaption>
<p><span class="caption-number">Fig. 9.2 </span><span class="caption-text">A directed graph. The edges in red depict a cycle.</span><a class="headerlink" href="#id9" title="Link to this image">¶</a></p>
</figcaption>
</figure>
<div class="proof proof-type-definition" id="id10">
<div class="proof-title">
<span class="proof-type">Definition 9.2</span>
<span class="proof-title-name">(Directed graph)</span>
</div><div class="proof-content">
<p>A <em>directed graph</em> is a graph in which the pair of nodes forming each edge
is ordered. In other words each edge points <em>from</em> one node (the <em>source</em>)
and <em>to</em> another (the <em>target</em>).</p>
</div></div><p><a class="reference internal" href="#digraph"><span class="std std-numref">Fig. 9.2</span></a> shows a directed graph with similar topology to the previous example.</p>
<div class="proof proof-type-definition" id="id11">
<div class="proof-title">
<span class="proof-type">Definition 9.3</span>
<span class="proof-title-name">(Cycle)</span>
</div><div class="proof-content">
<p>A <em>cycle</em> in a graph is a sequence of edges such that the target of each
edge is the source of the next, and the target of the last edge is the
source of the first.</p>
</div></div><div class="proof proof-type-definition" id="id12">
<div class="proof-title">
<span class="proof-type">Definition 9.4</span>
<span class="proof-title-name">(Directed acyclic graph.)</span>
</div><div class="proof-content">
<p>A directed acyclic graph (DAG) is a directed graph in which there are no cycles.</p>
</div></div><p><a class="reference internal" href="#dag"><span class="std std-numref">Fig. 9.3</span></a> shows a directed acyclic graph, or DAG. The acyclic nature of the
graph imposes a certain form of hierarchy. For example the graph formed by the
<a class="reference internal" href="7_inheritance.html#term-inheritance"><span class="xref std std-term">inheritance</span></a> relationship of classes is a DAG. The hierarchy implied by a
DAG also lends itself to similar nomenclature to that which we use for class
hierarchies: the source node of an edge is also referred to as the <em>parent node</em>
and the target nodes of the edges emerging from a node are referred to as its
<em>child nodes</em> or <em>children</em>.</p>
<figure class="align-center" id="id13">
<span id="dag"></span><div class="graphviz"><object data="_images/graphviz-6cfbd5edf8d73e7c78e93483be046a0a9b638586.svg" type="image/svg+xml" class="graphviz">
<p class="warning">strict digraph{
a -> b
b -> c
b -> d
c -> f
b -> f
a -> f
e -> c
e -> d
}</p></object></div>
<figcaption>
<p><span class="caption-number">Fig. 9.3 </span><span class="caption-text">A directed acyclic graph, formed by reversing edges in
<a class="reference internal" href="#digraph"><span class="std std-numref">Fig. 9.2</span></a> so that no cycles remain.</span><a class="headerlink" href="#id13" title="Link to this image">¶</a></p>
</figcaption>
</figure>
<figure class="align-center" id="id14">
<span id="tree-image"></span><div class="graphviz"><object data="_images/graphviz-45aaf798a9c41baad331feeb9a8fc483501e07be.svg" type="image/svg+xml" class="graphviz">
<p class="warning">strict digraph{
a -> b
b -> d
b -> e
b -> f
a -> c
c -> g
}</p></object></div>
<figcaption>
<p><span class="caption-number">Fig. 9.4 </span><span class="caption-text">A tree.</span><a class="headerlink" href="#id14" title="Link to this image">¶</a></p>
</figcaption>
</figure>
<div class="proof proof-type-definition" id="id15">
<div class="proof-title">
<span class="proof-type">Definition 9.5</span>
<span class="proof-title-name">(Tree)</span>
</div><div class="proof-content">
<p>A <em>tree</em> is a directed acyclic graph in which each node is the target of
exactly one edge, except for one node (the <em>root node</em>) which is not the
target of any edges <a class="footnote-reference brackets" href="#tree-def" id="id2" role="doc-noteref"><span class="fn-bracket">[</span>1<span class="fn-bracket">]</span></a>.</p>
</div></div><p>Tree nodes with no children are called <em>leaf nodes</em>.</p>
</section>
<section id="data-structures-for-trees">
<h2><span class="section-number">9.3. </span>Data structures for trees<a class="headerlink" href="#data-structures-for-trees" title="Link to this heading">¶</a></h2>
<details>
<summary>
Video: Tree data structures.</summary><div class="video_wrapper" style="">
<iframe allowfullscreen="true" src="https://player.vimeo.com/video/523477713" style="border: 0; height: 345px; width: 560px">
</iframe></div><p>Imperial students can also <a class="reference external" href="https://imperial.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=be25b5ba-f361-4aa1-b2a8-ae1c00dbc5a6">watch this video on Panopto</a>.</p>
</details><p>Unlike the sequence types we have previously met, trees are not linear objects.
If we wish to iterate through every node in the tree then we have choices to
make about the order in which we do so. In particular, there are two obvious
classes of traversal order:</p>
<dl class="simple">
<dt>preorder traversal</dt><dd><p>A traversal in which each node is always visited <em>before</em> its children.</p>
</dd>
<dt>postorder traversal</dt><dd><p>A traversal order in which each node is always visited <em>after</em> its children.</p>
</dd>
</dl>
<p>Neither order is unique: a node can have any number of children and
the definitions are silent on the order in which these are visited. There is
furthermore no guarantee that the children of a node will be visited immediately
before or after their parent, and once we look at visitors for DAGs it will
become apparent that it is not always possible to do so.</p>
<div class="literal-block-wrapper docutils container" id="id16">
<span id="treenode"></span><div class="code-block-caption"><span class="caption-number">Listing 9.3 </span><span class="caption-text">A basic tree implementation. This code is available as the
<a class="reference internal" href="example_code.html#example_code.graphs.TreeNode" title="example_code.graphs.TreeNode"><code class="xref py py-class docutils literal notranslate"><span class="pre">example_code.graphs.TreeNode</span></code></a> class.</span><a class="headerlink" href="#id16" title="Link to this code">¶</a></div>
<div class="highlight-python3 notranslate"><div class="highlight"><pre><span></span><span class="linenos"> 1</span><span class="k">class</span><span class="w"> </span><span class="nc">TreeNode</span><span class="p">:</span>
<span class="linenos"> 2</span><span class="w"> </span><span class="sd">"""A basic tree implementation.</span>
<span class="linenos"> 3</span>
<span class="linenos"> 4</span><span class="sd"> Observe that a tree is simply a collection of connected TreeNodes.</span>
<span class="linenos"> 5</span>
<span class="linenos"> 6</span><span class="sd"> Parameters</span>
<span class="linenos"> 7</span><span class="sd"> ----------</span>
<span class="linenos"> 8</span><span class="sd"> value:</span>
<span class="linenos"> 9</span><span class="sd"> An arbitrary value associated with this node.</span>
<span class="linenos">10</span><span class="sd"> children:</span>
<span class="linenos">11</span><span class="sd"> The TreeNodes which are the children of this node.</span>
<span class="linenos">12</span><span class="sd"> """</span>
<span class="linenos">13</span>
<span class="linenos">14</span> <span class="k">def</span><span class="w"> </span><span class="fm">__init__</span><span class="p">(</span><span class="bp">self</span><span class="p">,</span> <span class="n">value</span><span class="p">,</span> <span class="o">*</span><span class="n">children</span><span class="p">):</span>
<span class="linenos">15</span> <span class="bp">self</span><span class="o">.</span><span class="n">value</span> <span class="o">=</span> <span class="n">value</span>
<span class="linenos">16</span> <span class="bp">self</span><span class="o">.</span><span class="n">children</span> <span class="o">=</span> <span class="n">children</span>
<span class="linenos">17</span>
<span class="linenos">18</span> <span class="k">def</span><span class="w"> </span><span class="fm">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="linenos">19</span><span class="w"> </span><span class="sd">"""Return the canonical string representation."""</span>
<span class="linenos">20</span> <span class="k">return</span> <span class="sa">f</span><span class="s2">"</span><span class="si">{</span><span class="nb">type</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="vm">__name__</span><span class="si">}{</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">value</span><span class="p">,)</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="bp">self</span><span class="o">.</span><span class="n">children</span><span class="si">}</span><span class="s2">"</span>
<span class="linenos">21</span>
<span class="linenos">22</span> <span class="k">def</span><span class="w"> </span><span class="fm">__str__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="linenos">23</span><span class="w"> </span><span class="sd">"""Serialise the tree recursively as parent -> (children)."""</span>
<span class="linenos">24</span> <span class="n">childstring</span> <span class="o">=</span> <span class="s2">", "</span><span class="o">.</span><span class="n">join</span><span class="p">(</span><span class="nb">map</span><span class="p">(</span><span class="nb">str</span><span class="p">,</span> <span class="bp">self</span><span class="o">.</span><span class="n">children</span><span class="p">))</span>
<span class="linenos">25</span> <span class="k">return</span> <span class="sa">f</span><span class="s2">"</span><span class="si">{</span><span class="bp">self</span><span class="o">.</span><span class="n">value</span><span class="si">!s}</span><span class="s2"> -> (</span><span class="si">{</span><span class="n">childstring</span><span class="si">}</span><span class="s2">)"</span>
</pre></div>
</div>
</div>
<p><a class="reference internal" href="#treenode"><span class="std std-numref">Listing 9.3</span></a> shows a very simple class which implements a tree. For
example, we can represent the tree in <a class="reference internal" href="#tree-image"><span class="std std-numref">Fig. 9.4</span></a> using:</p>
<div class="highlight-ipython3 notranslate"><div class="highlight"><pre><span></span><span class="gp">In [1]: </span><span class="kn">from</span><span class="w"> </span><span class="nn">example_code.graphs</span><span class="w"> </span><span class="kn">import</span> <span class="n">TreeNode</span>
<span class="gp">In [2]: </span><span class="n">tree</span> <span class="o">=</span> <span class="n">TreeNode</span><span class="p">(</span>
<span class="gp"> ...: </span> <span class="s2">"a"</span><span class="p">,</span>
<span class="gp"> ...: </span> <span class="n">TreeNode</span><span class="p">(</span><span class="s2">"b"</span><span class="p">,</span> <span class="n">TreeNode</span><span class="p">(</span><span class="s2">"d"</span><span class="p">),</span> <span class="n">TreeNode</span><span class="p">(</span><span class="s2">"e"</span><span class="p">),</span> <span class="n">TreeNode</span><span class="p">(</span><span class="s2">"f"</span><span class="p">)),</span>
<span class="gp"> ...: </span> <span class="n">TreeNode</span><span class="p">(</span><span class="s2">"c"</span><span class="p">,</span> <span class="n">TreeNode</span><span class="p">(</span><span class="s2">"g"</span><span class="p">))</span>
<span class="gp"> ...: </span><span class="p">)</span>
<span class="gp">In [3]: </span><span class="nb">print</span><span class="p">(</span><span class="n">tree</span><span class="p">)</span>
<span class="go">a -> (b -> (d -> (), e -> (), f -> ()), c -> (g -> ()))</span>
</pre></div>
</div>
<p>The reader might immediately observe that serialised trees can be a little hard
to read! This is the reason that trees are often represented by diagrams.</p>
<section id="traversing-treenode">
<h3><span class="section-number">9.3.1. </span>Traversing <a class="reference internal" href="example_code.html#example_code.graphs.TreeNode" title="example_code.graphs.TreeNode"><code class="xref py py-class docutils literal notranslate"><span class="pre">TreeNode</span></code></a><a class="headerlink" href="#traversing-treenode" title="Link to this heading">¶</a></h3>
<details>
<summary>
Video: tree traversal.</summary><div class="video_wrapper" style="">
<iframe allowfullscreen="true" src="https://player.vimeo.com/video/523477719" style="border: 0; height: 345px; width: 560px">
</iframe></div><p>Imperial students can also <a class="reference external" href="https://imperial.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=3da6b798-c795-44a2-bf91-ae1c00dbd0f6">watch this video on Panopto</a>.</p>
</details><p>A function which traverses a tree is often called a tree visitor, because it
visits every node in the tree. What does it do when it visits? Well it could do
just about anything that one can do on the basis of the data available at that
node, and the results of visiting whichever nodes have already been visited. The
way that such a wide range of options can be accommodated is by the tree
traversal function taking another function as an argument. This enables the
caller to specify what should happen when each node is visited. An approach like
this is a good example of a <a class="reference internal" href="5_abstract_data_types.html#term-separation-of-concerns"><span class="xref std std-term">separation of concerns</span></a>: the process of
visiting a tree in the correct order is separated from the question of what to
do when we get there.</p>
<p>We’ll consider postorder traversal first, as it’s the easier to implement.</p>
<div class="literal-block-wrapper docutils container" id="id17">
<span id="postorder-recursive"></span><div class="code-block-caption"><span class="caption-number">Listing 9.4 </span><span class="caption-text">A basic postorder tree visitor. This code is also available as
<a class="reference internal" href="example_code.html#example_code.graphs.postvisitor" title="example_code.graphs.postvisitor"><code class="xref py py-func docutils literal notranslate"><span class="pre">example_code.graphs.postvisitor()</span></code></a>.</span><a class="headerlink" href="#id17" title="Link to this code">¶</a></div>
<div class="highlight-python3 notranslate"><div class="highlight"><pre><span></span><span class="linenos"> 1</span><span class="k">def</span><span class="w"> </span><span class="nf">postvisitor</span><span class="p">(</span><span class="n">tree</span><span class="p">,</span> <span class="n">fn</span><span class="p">):</span>
<span class="linenos"> 2</span><span class="w"> </span><span class="sd">"""Traverse tree in postorder applying a function to every node.</span>
<span class="linenos"> 3</span>
<span class="linenos"> 4</span><span class="sd"> Parameters</span>
<span class="linenos"> 5</span><span class="sd"> ----------</span>
<span class="linenos"> 6</span><span class="sd"> tree: TreeNode</span>
<span class="linenos"> 7</span><span class="sd"> The tree to be visited.</span>
<span class="linenos"> 8</span><span class="sd"> fn: function(node, *fn_children)</span>
<span class="linenos"> 9</span><span class="sd"> A function to be applied at each node. The function should take</span>
<span class="linenos">10</span><span class="sd"> the node to be visited as its first argument, and the results of</span>
<span class="linenos">11</span><span class="sd"> visiting its children as any further arguments.</span>
<span class="linenos">12</span><span class="sd"> """</span>
<span class="linenos">13</span> <span class="k">return</span> <span class="n">fn</span><span class="p">(</span><span class="n">tree</span><span class="p">,</span> <span class="o">*</span><span class="p">(</span><span class="n">postvisitor</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">fn</span><span class="p">)</span> <span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="n">tree</span><span class="o">.</span><span class="n">children</span><span class="p">))</span>
</pre></div>
</div>
</div>
<p><a class="reference internal" href="#postorder-recursive"><span class="std std-numref">Listing 9.4</span></a> implements this visitor. Notice that there is
only one line of executable code, at line 13. This recursively calls
<a class="reference internal" href="example_code.html#example_code.graphs.postvisitor" title="example_code.graphs.postvisitor"><code class="xref py py-func docutils literal notranslate"><span class="pre">postvisitor()</span></code></a> on all of the children of the current
node, <em>before</em> calling <code class="xref py py-func docutils literal notranslate"><span class="pre">fn()</span></code> on the current node. As a trivial example,
<a class="reference internal" href="#linenos-postorder"><span class="std std-numref">Listing 9.5</span></a> prints out the nodes of the graph in
<a class="reference internal" href="#tree-image"><span class="std std-numref">Fig. 9.4</span></a> in postorder.</p>
<div class="literal-block-wrapper docutils container" id="id18">
<span id="linenos-postorder"></span><div class="code-block-caption"><span class="caption-number">Listing 9.5 </span><span class="caption-text">A trivial postorder tree traversal which simply prints the node
values in order. Observe that d, e, and f are printed before b; g is
printed before c; and both b and c are printed before a.</span><a class="headerlink" href="#id18" title="Link to this code">¶</a></div>
<div class="highlight-ipython3 notranslate"><div class="highlight"><pre><span></span><span class="linenos"> 1</span><span class="gp">In [1]: </span><span class="kn">from</span><span class="w"> </span><span class="nn">example_code.graphs</span><span class="w"> </span><span class="kn">import</span> <span class="n">TreeNode</span><span class="p">,</span> <span class="n">postvisitor</span>
<span class="linenos"> 2</span>
<span class="linenos"> 3</span><span class="gp">In [2]: </span><span class="n">tree</span> <span class="o">=</span> <span class="n">TreeNode</span><span class="p">(</span><span class="s2">"a"</span><span class="p">,</span> <span class="n">TreeNode</span><span class="p">(</span><span class="s2">"b"</span><span class="p">,</span> <span class="n">TreeNode</span><span class="p">(</span><span class="s2">"d"</span><span class="p">),</span> <span class="n">TreeNode</span><span class="p">(</span><span class="s2">"e"</span><span class="p">),</span>
<span class="linenos"> 4</span><span class="gp"> ...: </span> <span class="n">TreeNode</span><span class="p">(</span><span class="s2">"f"</span><span class="p">)),</span>
<span class="linenos"> 5</span><span class="gp"> ...: </span> <span class="n">TreeNode</span><span class="p">(</span><span class="s2">"c"</span><span class="p">,</span> <span class="n">TreeNode</span><span class="p">(</span><span class="s2">"g"</span><span class="p">)))</span>
<span class="linenos"> 6</span>
<span class="linenos"> 7</span><span class="gp">In [3]: </span><span class="n">fn</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">n</span><span class="p">,</span> <span class="o">*</span><span class="n">c</span><span class="p">:</span> <span class="nb">print</span><span class="p">(</span><span class="n">n</span><span class="o">.</span><span class="n">value</span><span class="p">)</span>
<span class="linenos"> 8</span>
<span class="linenos"> 9</span><span class="gp">In [4]: </span><span class="n">postvisitor</span><span class="p">(</span><span class="n">tree</span><span class="p">,</span> <span class="n">fn</span><span class="p">)</span>
<span class="linenos">10</span><span class="go">d</span>
<span class="linenos">11</span><span class="go">e</span>
<span class="linenos">12</span><span class="go">f</span>
<span class="linenos">13</span><span class="go">b</span>
<span class="linenos">14</span><span class="go">g</span>
<span class="linenos">15</span><span class="go">c</span>
<span class="linenos">16</span><span class="go">a</span>
</pre></div>
</div>
</div>
<p>The preceding example is possibly a little too trivial,
because we didn’t at all use the result of visiting the child nodes in visiting
the parent node. For a marginally less trivial case, let’s count the number of
nodes in the tree:</p>
<div class="highlight-ipython3 notranslate"><div class="highlight"><pre><span></span><span class="gp">In [5]: </span><span class="n">fn</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">n</span><span class="p">,</span> <span class="o">*</span><span class="n">c</span><span class="p">:</span> <span class="nb">sum</span><span class="p">(</span><span class="n">c</span><span class="p">)</span> <span class="o">+</span> <span class="mi">1</span>
<span class="gp">In [6]: </span><span class="n">postvisitor</span><span class="p">(</span><span class="n">tree</span><span class="p">,</span> <span class="n">fn</span><span class="p">)</span>
<span class="gh">Out[6]: </span><span class="go">7</span>
</pre></div>
</div>
<p>This time the visitor <a class="reference external" href="https://docs.python.org/3/builtins/functions.html#sum" title="(in Python v3.15)"><code class="xref py py-func docutils literal notranslate"><span class="pre">sums</span></code></a> the results from its children, and adds
one for itself.</p>
<p>What about preorder traversal? This time we need a little more code (not much)
as <a class="reference internal" href="#preorder-recursive"><span class="std std-numref">Listing 9.6</span></a> shows. This time, we call <code class="xref py py-func docutils literal notranslate"><span class="pre">fn()</span></code> on the
current tree node first, and then pass this result through as we recursively
call <code class="xref py py-func docutils literal notranslate"><span class="pre">previsitor()</span></code> on the child nodes.</p>
<div class="literal-block-wrapper docutils container" id="id19">
<span id="preorder-recursive"></span><div class="code-block-caption"><span class="caption-number">Listing 9.6 </span><span class="caption-text">The simple preorder visitor from
<a class="reference internal" href="example_code.html#example_code.graphs.previsitor" title="example_code.graphs.previsitor"><code class="xref py py-func docutils literal notranslate"><span class="pre">example_code.graphs.previsitor()</span></code></a>.</span><a class="headerlink" href="#id19" title="Link to this code">¶</a></div>
<div class="highlight-python3 notranslate"><div class="highlight"><pre><span></span><span class="linenos"> 1</span><span class="k">def</span><span class="w"> </span><span class="nf">previsitor</span><span class="p">(</span><span class="n">tree</span><span class="p">,</span> <span class="n">fn</span><span class="p">,</span> <span class="n">fn_parent</span><span class="o">=</span><span class="kc">None</span><span class="p">):</span>
<span class="linenos"> 2</span><span class="w"> </span><span class="sd">"""Traverse tree in preorder applying a function to every node.</span>
<span class="linenos"> 3</span>
<span class="linenos"> 4</span><span class="sd"> Parameters</span>
<span class="linenos"> 5</span><span class="sd"> ----------</span>
<span class="linenos"> 6</span><span class="sd"> tree: TreeNode</span>
<span class="linenos"> 7</span><span class="sd"> The tree to be visited.</span>
<span class="linenos"> 8</span><span class="sd"> fn: function(node, fn_parent)</span>
<span class="linenos"> 9</span><span class="sd"> A function to be applied at each node. The function should take</span>
<span class="linenos">10</span><span class="sd"> the node to be visited as its first argument, and the result of</span>
<span class="linenos">11</span><span class="sd"> visiting its parent as the second.</span>
<span class="linenos">12</span><span class="sd"> """</span>
<span class="linenos">13</span> <span class="n">fn_out</span> <span class="o">=</span> <span class="n">fn</span><span class="p">(</span><span class="n">tree</span><span class="p">,</span> <span class="n">fn_parent</span><span class="p">)</span>
<span class="linenos">14</span>
<span class="linenos">15</span> <span class="k">for</span> <span class="n">child</span> <span class="ow">in</span> <span class="n">tree</span><span class="o">.</span><span class="n">children</span><span class="p">:</span>
<span class="linenos">16</span> <span class="n">previsitor</span><span class="p">(</span><span class="n">child</span><span class="p">,</span> <span class="n">fn</span><span class="p">,</span> <span class="n">fn_out</span><span class="p">)</span>
</pre></div>
</div>
</div>
<p>What can we do with a preorder traversal? As an example, we can measure
the depth in the tree of every node:</p>
<div class="highlight-ipython3 notranslate"><div class="highlight"><pre><span></span><span class="gp">In [7]: </span><span class="kn">from</span><span class="w"> </span><span class="nn">example_code.graphs</span><span class="w"> </span><span class="kn">import</span> <span class="n">previsitor</span>
<span class="gp">In [8]: </span><span class="k">def</span><span class="w"> </span><span class="nf">fn</span><span class="p">(</span><span class="n">node</span><span class="p">,</span> <span class="n">p</span><span class="p">):</span>
<span class="gp"> ...: </span> <span class="n">depth</span> <span class="o">=</span> <span class="n">p</span> <span class="o">+</span> <span class="mi">1</span> <span class="k">if</span> <span class="n">p</span> <span class="k">else</span> <span class="mi">1</span>
<span class="gp"> ...: </span> <span class="nb">print</span><span class="p">(</span><span class="sa">f</span><span class="s2">"</span><span class="si">{</span><span class="n">node</span><span class="o">.</span><span class="n">value</span><span class="si">}</span><span class="s2">: </span><span class="si">{</span><span class="n">depth</span><span class="si">}</span><span class="s2">"</span><span class="p">)</span>
<span class="gp"> ...: </span> <span class="k">return</span> <span class="n">depth</span>
<span class="gp"> ...:</span>
<span class="gp">In [9]: </span><span class="n">previsitor</span><span class="p">(</span><span class="n">tree</span><span class="p">,</span> <span class="n">fn</span><span class="p">)</span>
<span class="go">a: 1</span>
<span class="go">b: 2</span>
<span class="go">d: 3</span>
<span class="go">e: 3</span>
<span class="go">f: 3</span>
<span class="go">c: 2</span>
<span class="go">g: 3</span>
</pre></div>
</div>
<p>Observe here that the node visitor order is different from the postvisitor, and
that we successfully diagnosed the depth of each node.</p>
</section>
</section>
<section id="expression-trees">
<span id="expr-trees"></span><h2><span class="section-number">9.4. </span>Expression trees<a class="headerlink" href="#expression-trees" title="Link to this heading">¶</a></h2>
<p>One important application of trees is in representing arithmetic expressions.
Consider the expression <span class="math notranslate nohighlight">\(2y + 4^{(5 + x)}\)</span>. Suppose, further, that
we want to represent this on a computer in such a way that we can perform
mathematical operations: evaluation, differentiation, expansion, and
simplification. How would we do this? Well, thanks to the rules for order of
operations, this expression forms a hierarchy from the operators to be evaluated
first, down to the last one. <a class="reference internal" href="#expr-tree"><span class="std std-numref">Fig. 9.5</span></a> shows a tree representation for
our mathematical expression. The evaluation rule for trees of this type is a
postorder traversal, first the leaf nodes are evaluated, then their parents and
so on up until finally the addition at the root node is evaluated.</p>
<figure class="align-default" id="id20">
<span id="expr-tree"></span><div class="graphviz"><object data="_images/graphviz-40c7ff52321f939db0b564bf24e78efc894b9d3d.svg" type="image/svg+xml" class="graphviz">
<p class="warning">strict digraph{
a [label="+"];
b [label="⨉"];
c [label="^"];
2;
y [font="italic"];
a->b
a->c
b->{2 y}
c->4
d[label="+"]
c->d
d->5
x [font="italic"]
d->x
}</p></object></div>
<figcaption>
<p><span class="caption-number">Fig. 9.5 </span><span class="caption-text">Expression tree for the expression <span class="math notranslate nohighlight">\(2y + 4^{(5 + x)}\)</span>.</span><a class="headerlink" href="#id20" title="Link to this image">¶</a></p>
</figcaption>
</figure>
<p>We will first consider how to construct trees like this, then consider the
question of the operations we could implement on them.</p>
<section id="an-expression-tree-class-hierarchy">
<span id="expr-hierarchy"></span><h3><span class="section-number">9.4.1. </span>An expression tree class hierarchy<a class="headerlink" href="#an-expression-tree-class-hierarchy" title="Link to this heading">¶</a></h3>
<p>The nodes of an expression tree don’t just have different values, they have
different <a class="reference internal" href="3_objects.html#term-type"><span class="xref std std-term">type</span></a>. That is to say, the meaning of operations changes
between, say <span class="math notranslate nohighlight">\(+\)</span> and <span class="math notranslate nohighlight">\(2\)</span>. For example the evaluation rule for these
nodes will be different, as will the differentiation rule. At the same time,
all the nodes are still expressions and will share many common features. This
is a textbook case of <a class="reference internal" href="7_inheritance.html#term-inheritance"><span class="xref std std-term">inheritance</span></a>. There should be a most general
class, covering all types of expression nodes, and then more specialised node
types should inherit from this. The most basic distinction is between
<em>operators</em>, which have at least one operand (represented by a child node), and
<em>terminals</em>, which have no children. In practice, it will result in simpler,
more elegant code if terminals actually have an empty tuple of operands rather
than none at all. This facilitates writing, for example, tree visitors which
loop over all of the children of a node.</p>
<figure class="align-default" id="id21">
<div class="graphviz"><object data="_images/graphviz-1b8623c6af5a7bb07913bec5340d894e765da9bf.svg" type="image/svg+xml" class="graphviz">
<p class="warning">strict digraph{
node [
shape = "record"
]
edge [
arrowtail = "empty";
dir = "back";
]
Expression -> Terminal
Terminal -> Number
Terminal -> Symbol
Expression -> Operator
Operator -> Add
Operator -> Mul
Operator -> Sub
Operator -> Div
Operator -> Pow
}</p></object></div>
<figcaption>
<p><span class="caption-number">Fig. 9.6 </span><span class="caption-text">Inheritance diagram for a very basic symbolic language. Each box
represents a class, with the arrows showing inheritance relationships. Note that
the edges in such diagrams conventionally point from the child class to the
parent class, because it’s the child class that refers to the parent. The
parent does not refer to the child.</span><a class="headerlink" href="#id21" title="Link to this image">¶</a></p>
</figcaption>
</figure>
<p>Let’s consider what would be needed at each layer of the hierarchy.
<code class="xref py py-class docutils literal notranslate"><span class="pre">Expression</span></code> should implement everything that is the same for all nodes. What
will that comprise?</p>
<dl>
<dt><code class="xref py py-meth docutils literal notranslate"><span class="pre">__init__()</span></code></dt><dd><p>The constructor will take a <a class="reference external" href="https://docs.python.org/3/builtins/stdtypes.html#tuple" title="(in Python v3.15)"><code class="xref py py-class docutils literal notranslate"><span class="pre">tuple</span></code></a> of operands, since every
expression has operands (even if terminals have zero operands).</p>
</dd>
<dt><a class="reference external" href="https://docs.python.org/3/reference/datamodel.html#object.__add__" title="(in Python v3.15)"><code class="xref py py-meth docutils literal notranslate"><span class="pre">__add__()</span></code></a>, <a class="reference external" href="https://docs.python.org/3/reference/datamodel.html#object.__sub__" title="(in Python v3.15)"><code class="xref py py-meth docutils literal notranslate"><span class="pre">__sub__()</span></code></a>, <a class="reference external" href="https://docs.python.org/3/reference/datamodel.html#object.__mul__" title="(in Python v3.15)"><code class="xref py py-meth docutils literal notranslate"><span class="pre">__mul__()</span></code></a>, <a class="reference external" href="https://docs.python.org/3/reference/datamodel.html#object.__truediv__" title="(in Python v3.15)"><code class="xref py py-meth docutils literal notranslate"><span class="pre">__truediv__()</span></code></a>, <a class="reference external" href="https://docs.python.org/3/reference/datamodel.html#object.__pow__" title="(in Python v3.15)"><code class="xref py py-meth docutils literal notranslate"><span class="pre">__pow__()</span></code></a></dt><dd><p>Implementing the <a class="reference internal" href="3_objects.html#term-special-method"><span class="xref std std-term">special methods</span></a> for arithmetic is
necessary for expressions to exhibit the correct symbolic mathematical
behaviour. We met this idea already in <a class="reference internal" href="3_objects.html#object-arithmetic"><span class="std std-numref">Section 3.3.6</span></a>.
Arithmetic operations involving symbolic expressions return other symbolic
expressions. For example if <code class="xref py py-obj docutils literal notranslate"><span class="pre">a</span></code> and <code class="xref py py-obj docutils literal notranslate"><span class="pre">b</span></code> are expressions then <code class="xref py py-obj docutils literal notranslate"><span class="pre">a</span> <span class="pre">+</span> <span class="pre">b</span></code> is
simply <code class="xref py py-obj docutils literal notranslate"><span class="pre">Add(a,</span> <span class="pre">b)</span></code>. The fact that these rules are the same for all
expressions indicates that they should be implemented on the base class
<code class="xref py py-class docutils literal notranslate"><span class="pre">Expression</span></code>.</p>
<p>Just as was the case when we implemented the
<a class="reference internal" href="example_code.html#example_code.polynomial.Polynomial" title="example_code.polynomial.Polynomial"><code class="xref py py-class docutils literal notranslate"><span class="pre">Polynomial</span></code></a> class, it will be necessary to
do something special when one of the operands is a number. In this case, the
right thing to do is to turn the number into an expression by instantiating a
<code class="xref py py-class docutils literal notranslate"><span class="pre">Number</span></code> with it as a value. Once this has been done, the number is
just another <code class="xref py py-class docutils literal notranslate"><span class="pre">Expression</span></code> obeying the same arithmetic rules as other
expressions. The need to accommodate operations between symbolic expressions
and numbers also implies that it will also be necessary to implement the
<a class="reference internal" href="3_objects.html#term-special-method"><span class="xref std std-term">special methods</span></a> for reversed arithmetic operations.</p>
</dd>
</dl>
<p>Let’s now consider <code class="xref py py-class docutils literal notranslate"><span class="pre">Operator</span></code>. The operations for creating string
representations can be implemented here, because they will be the same for all
operators but different for terminals.</p>
<dl>
<dt><a class="reference external" href="https://docs.python.org/3/reference/datamodel.html#object.__repr__" title="(in Python v3.15)"><code class="xref py py-meth docutils literal notranslate"><span class="pre">__repr__()</span></code></a></dt><dd><p>Remember that this is the canonical string representation, and is usually
the code that could be passed to the <a class="reference internal" href="2_programs_in_files.html#term-Python-interpreter"><span class="xref std std-term">Python interpreter</span></a> to construct
the object. Something like the following would work:</p>
<div class="highlight-python3 notranslate"><div class="highlight"><pre><span></span><span class="k">def</span><span class="w"> </span><span class="fm">__repr__</span><span class="p">(</span><span class="bp">self</span><span class="p">):</span>
<span class="k">return</span> <span class="nb">type</span><span class="p">(</span><span class="bp">self</span><span class="p">)</span><span class="o">.</span><span class="vm">__name__</span> <span class="o">+</span> <span class="nb">repr</span><span class="p">(</span><span class="bp">self</span><span class="o">.</span><span class="n">operands</span><span class="p">)</span>
</pre></div>
</div>
<p>This approach is valid because the string representation of a <a class="reference external" href="https://docs.python.org/3/builtins/stdtypes.html#tuple" title="(in Python v3.15)"><code class="xref py py-class docutils literal notranslate"><span class="pre">tuple</span></code></a>
is a pair of round brackets containing the string representation of each
item in the tuple.</p>
</dd>
<dt><a class="reference external" href="https://docs.python.org/3/reference/datamodel.html#object.__str__" title="(in Python v3.15)"><code class="xref py py-meth docutils literal notranslate"><span class="pre">__str__()</span></code></a></dt><dd><p>This is the human-readable string output, using <a class="reference internal" href="3_objects.html#term-infix-operator"><span class="xref std std-term">infix operators</span></a>, so in the example above we would expect to see
<code class="xref py py-obj docutils literal notranslate"><span class="pre">2</span> <span class="pre">*</span> <span class="pre">y</span> <span class="pre">+</span> <span class="pre">4</span> <span class="pre">^</span> <span class="pre">(5</span> <span class="pre">+</span> <span class="pre">x)</span></code> This looks sort of straightforward, simply associate the correct
symbol with each operator class as a <a class="reference internal" href="7_inheritance.html#term-class-attribute"><span class="xref std std-term">class attribute</span></a> and place the
string representation of the operands on either side.</p>
<p>The challenge is to correctly include the brackets. In order to do this, it
is necessary to associate with every expression class a <a class="reference internal" href="7_inheritance.html#term-class-attribute"><span class="xref std std-term">class
attribute</span></a> whose value is a number giving an operator precedence to that
class. For example, the precedence of <code class="xref py py-class docutils literal notranslate"><span class="pre">Mul</span></code> should be higher than
<code class="xref py py-class docutils literal notranslate"><span class="pre">Add</span></code>. A full list of operators in precedence order is available in
<a class="reference external" href="https://docs.python.org/3/reference/expressions.html#operator-summary" title="(in Python v3.15)"><span class="xref std std-ref">the official Python documentation</span></a>. An operand
<span class="math notranslate nohighlight">\(a\)</span> of an operator <span class="math notranslate nohighlight">\(o\)</span> needs to be placed in brackets if the
precedence of <span class="math notranslate nohighlight">\(a\)</span> is lower than the precedence of <span class="math notranslate nohighlight">\(o\)</span>.</p>
</dd>
</dl>
<p>Individual operator classes therefore need to define very little, just two
<a class="reference internal" href="7_inheritance.html#term-class-attribute"><span class="xref std std-term">class attributes</span></a>, one for the operator precedence, and
one to set the symbol when printing the operator.</p>
<p>Let’s now consider <code class="xref py py-class docutils literal notranslate"><span class="pre">Terminal</span></code>. What does it need to set?</p>
<dl class="simple">
<dt><a class="reference external" href="https://docs.python.org/3/reference/datamodel.html#object.__init__" title="(in Python v3.15)"><code class="xref py py-meth docutils literal notranslate"><span class="pre">__init__()</span></code></a></dt><dd><p>The <a class="reference internal" href="3_objects.html#term-constructor"><span class="xref std std-term">constructor</span></a> for <code class="xref py py-class docutils literal notranslate"><span class="pre">Expression</span></code> assumes that an expression is
defined by a series of operands. Terminals have an empty list of operands
but do have something that other expressions lack: a value. In the case of
<code class="xref py py-class docutils literal notranslate"><span class="pre">Number</span></code>, this is a number, while for <code class="xref py py-class docutils literal notranslate"><span class="pre">Symbol</span></code> the value is a
string (usually a single character). <code class="xref py py-class docutils literal notranslate"><span class="pre">Terminal</span></code> therefore needs its
own <code class="xref py py-meth docutils literal notranslate"><span class="pre">__init__()</span></code> which will take a value argument.
<code class="xref py py-class docutils literal notranslate"><span class="pre">Terminal.__init__</span></code> still has to call the <a class="reference internal" href="7_inheritance.html#term-superclass"><span class="xref std std-term">superclass</span></a>
constructor in order to ensure that the operands tuple is initialised.</p>
</dd>
<dt><a class="reference external" href="https://docs.python.org/3/reference/datamodel.html#object.__repr__" title="(in Python v3.15)"><code class="xref py py-meth docutils literal notranslate"><span class="pre">__repr__()</span></code></a> and <a class="reference external" href="https://docs.python.org/3/reference/datamodel.html#object.__str__" title="(in Python v3.15)"><code class="xref py py-meth docutils literal notranslate"><span class="pre">__str__()</span></code></a></dt><dd><p>The string representations of <code class="xref py py-class docutils literal notranslate"><span class="pre">Terminal</span></code> are straightforward, simply
return <code class="xref py py-obj docutils literal notranslate"><span class="pre">repr(self.value)</span></code> and <code class="xref py py-obj docutils literal notranslate"><span class="pre">str(self.value)</span></code> respectively. Note that in
order for <code class="xref py py-meth docutils literal notranslate"><span class="pre">Operator.__str__()</span></code> to function correctly, <code class="xref py py-class docutils literal notranslate"><span class="pre">Terminal</span></code>
will need to advertise its operator precedence. The reader should think
carefully about what the precedence of a <code class="xref py py-class docutils literal notranslate"><span class="pre">Terminal</span></code> should be.</p>
</dd>
</dl>
<p>The two <code class="xref py py-class docutils literal notranslate"><span class="pre">Terminal</span></code> subclasses need to do very little other than identify
themselves. The only functionality they might provide would be to override
<a class="reference external" href="https://docs.python.org/3/reference/datamodel.html#object.__init__" title="(in Python v3.15)"><code class="xref py py-meth docutils literal notranslate"><span class="pre">__init__()</span></code></a> to check that their value is a <a class="reference external" href="https://docs.python.org/3/library/numbers.html#numbers.Number" title="(in Python v3.15)"><code class="xref py py-class docutils literal notranslate"><span class="pre">numbers.Number</span></code></a>
in the case of <code class="xref py py-class docutils literal notranslate"><span class="pre">Number</span></code> and a <a class="reference external" href="https://docs.python.org/3/builtins/stdtypes.html#str" title="(in Python v3.15)"><code class="xref py py-class docutils literal notranslate"><span class="pre">str</span></code></a> in the case of <code class="xref py py-class docutils literal notranslate"><span class="pre">Symbol</span></code>.</p>
</section>
<section id="operations-on-expression-trees">
<h3><span class="section-number">9.4.2. </span>Operations on expression trees<a class="headerlink" href="#operations-on-expression-trees" title="Link to this heading">¶</a></h3>
<details>
<summary>
Video: evaluating expressions.</summary><div class="video_wrapper" style="">
<iframe allowfullscreen="true" src="https://player.vimeo.com/video/523478799" style="border: 0; height: 345px; width: 560px">
</iframe></div><p>Imperial students can also <a class="reference external" href="https://imperial.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=b9310ae7-0cf5-41f0-b0cc-ae1c00dbe39b">watch this video on Panopto</a>.</p>
</details><p>Many operations on expression trees can be implemented using tree visitors, most
frequently by visiting the tree in postorder. An example is
expression evaluation. The user provides a <a class="reference external" href="https://docs.python.org/3/builtins/stdtypes.html#dict" title="(in Python v3.15)"><code class="xref py py-class docutils literal notranslate"><span class="pre">dict</span></code></a> mapping symbol names to
numerical values, and we proceed from leaf nodes upwards. Every <code class="xref py py-class docutils literal notranslate"><span class="pre">Symbol</span></code>
is replaced by a numerical value from the dictionary, every <code class="xref py py-class docutils literal notranslate"><span class="pre">Number</span></code>
stands for itself, and every <code class="xref py py-class docutils literal notranslate"><span class="pre">Operator</span></code> performs the appropriate
computation on its operands (which are now guaranteed to be numbers).</p>
<p>The leaf-first order of execution makes this a postorder tree visitor, but what
is the visitor function? It seems we need a different function for every
<a class="reference external" href="https://docs.python.org/3/builtins/functions.html#type" title="(in Python v3.15)"><code class="xref py py-class docutils literal notranslate"><span class="pre">type</span></code></a> of expression node we encounter. It turns out that this is exactly
what is required, and Python provides this functionality in the form of the
single dispatch function.</p>
</section>
<section id="single-dispatch-functions">
<span id="single-dispatch"></span><h3><span class="section-number">9.4.3. </span>Single dispatch functions<a class="headerlink" href="#single-dispatch-functions" title="Link to this heading">¶</a></h3>
<p>In all of the cases we have encountered so far, there is a unique mapping from
the name of a function to the code implementing that function. That is, no
matter what arguments are passed to a function, the same code will execute (so
long as the right number of arguments are passed). A single dispatch function is
not like this. Instead, calling a single function name causes different function
code to execute, depending on the type of the first argument <a class="footnote-reference brackets" href="#single" id="id3" role="doc-noteref"><span class="fn-bracket">[</span>3<span class="fn-bracket">]</span></a>.</p>
<p><a class="reference internal" href="#tree-evaluate"><span class="std std-numref">Listing 9.7</span></a> shows a single dispatch function for a visitor function
which evaluates a <code class="xref py py-class docutils literal notranslate"><span class="pre">Expression</span></code>. Start with lines 6-24. These define a
function <a class="reference internal" href="example_code.html#example_code.expression_tools.evaluate" title="example_code.expression_tools.evaluate"><code class="xref py py-func docutils literal notranslate"><span class="pre">evaluate()</span></code></a> which will be used in
the default case, that is, in the case where the <a class="reference external" href="https://docs.python.org/3/builtins/functions.html#type" title="(in Python v3.15)"><code class="xref py py-class docutils literal notranslate"><span class="pre">type</span></code></a> of the first
argument doesn’t match any of the other implementations of
<a class="reference internal" href="example_code.html#example_code.expression_tools.evaluate" title="example_code.expression_tools.evaluate"><code class="xref py py-func docutils literal notranslate"><span class="pre">evaluate()</span></code></a>. In this case, the first
argument is the expression that we’re evaluating, so if the type doesn’t match
then this means that we don’t know how to evaluate this object, and the only
course of action available is to throw an <a class="reference internal" href="6_exceptions.html#term-exception"><span class="xref std std-term">exception</span></a>.</p>
<p>The new feature that we haven’t met before appears on line 5.
<a class="reference external" href="https://docs.python.org/3/library/functools.html#functools.singledispatch" title="(in Python v3.15)"><code class="xref py py-func docutils literal notranslate"><span class="pre">functools.singledispatch()</span></code></a> turns a function into
a single dispatch function. The <code class="xref py py-obj docutils literal notranslate"><span class="pre">@</span></code> symbol marks
<a class="reference external" href="https://docs.python.org/3/library/functools.html#functools.singledispatch" title="(in Python v3.15)"><code class="xref py py-func docutils literal notranslate"><span class="pre">singledispatch()</span></code></a> as a <a class="reference internal" href="10_further_object-oriented_features.html#term-decorator"><span class="xref std std-term">decorator</span></a>. We’ll return to them
in <a class="reference internal" href="10_further_object-oriented_features.html#decorators"><span class="std std-numref">Section 10.1</span></a>. For the moment, we just need to know that
<code class="xref py py-obj docutils literal notranslate"><span class="pre">@singledispatch</span></code> turns the function it precedes into a single dispatch
function.</p>
<div class="literal-block-wrapper docutils container" id="id22">
<span id="tree-evaluate"></span><div class="code-block-caption"><span class="caption-number">Listing 9.7 </span><span class="caption-text">A <a class="reference internal" href="#term-single-dispatch-function"><span class="xref std std-term">single dispatch function</span></a> implementing the evaluation of
a single <code class="xref py py-class docutils literal notranslate"><span class="pre">Expression</span></code> node. The implementation of the
expressions language itself, in the <code class="xref py py-mod docutils literal notranslate"><span class="pre">expressions</span></code> module, is
<a class="reference internal" href="#ex-expr"><span class="std std-ref">left as an exercise</span></a>.</span><a class="headerlink" href="#id22" title="Link to this code">¶</a></div>
<div class="highlight-python3 notranslate"><div class="highlight"><pre><span></span><span class="linenos"> 1</span><span class="kn">from</span><span class="w"> </span><span class="nn">functools</span><span class="w"> </span><span class="kn">import</span> <span class="n">singledispatch</span>
<span class="linenos"> 2</span><span class="kn">import</span><span class="w"> </span><span class="nn">expressions</span>
<span class="linenos"> 3</span>
<span class="linenos"> 4</span>
<span class="linenos"> 5</span><span class="nd">@singledispatch</span>
<span class="linenos"> 6</span><span class="k">def</span><span class="w"> </span><span class="nf">evaluate</span><span class="p">(</span><span class="n">expr</span><span class="p">,</span> <span class="o">*</span><span class="n">o</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
<span class="linenos"> 7</span><span class="w"> </span><span class="sd">"""Evaluate an expression node.</span>
<span class="linenos"> 8</span>
<span class="linenos"> 9</span><span class="sd"> Parameters</span>
<span class="linenos">10</span><span class="sd"> ----------</span>
<span class="linenos">11</span><span class="sd"> expr: Expression</span>
<span class="linenos">12</span><span class="sd"> The expression node to be evaluated.</span>
<span class="linenos">13</span><span class="sd"> *o: numbers.Number</span>
<span class="linenos">14</span><span class="sd"> The results of evaluating the operands of expr.</span>
<span class="linenos">15</span><span class="sd"> **kwargs:</span>
<span class="linenos">16</span><span class="sd"> Any keyword arguments required to evaluate specific types of</span>
<span class="linenos">17</span><span class="sd"> expression.</span>
<span class="linenos">18</span><span class="sd"> symbol_map: dict</span>
<span class="linenos">19</span><span class="sd"> A dictionary mapping Symbol names to numerical values, for</span>
<span class="linenos">20</span><span class="sd"> example:</span>
<span class="linenos">21</span>
<span class="linenos">22</span><span class="sd"> {'x': 1}</span>
<span class="linenos">23</span><span class="sd"> """</span>
<span class="linenos">24</span> <span class="k">raise</span> <span class="ne">NotImplementedError</span><span class="p">(</span>
<span class="linenos">25</span> <span class="sa">f</span><span class="s2">"Cannot evaluate a </span><span class="si">{</span><span class="nb">type</span><span class="p">(</span><span class="n">expr</span><span class="p">)</span><span class="o">.</span><span class="vm">__name__</span><span class="si">}</span><span class="s2">"</span><span class="p">)</span>
<span class="linenos">26</span>
<span class="linenos">27</span>
<span class="linenos">28</span><span class="nd">@evaluate</span><span class="o">.</span><span class="n">register</span><span class="p">(</span><span class="n">expressions</span><span class="o">.</span><span class="n">Number</span><span class="p">)</span>
<span class="linenos">29</span><span class="k">def</span><span class="w"> </span><span class="nf">_</span><span class="p">(</span><span class="n">expr</span><span class="p">,</span> <span class="o">*</span><span class="n">o</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
<span class="linenos">30</span> <span class="k">return</span> <span class="n">expr</span><span class="o">.</span><span class="n">value</span>
<span class="linenos">31</span>
<span class="linenos">32</span>
<span class="linenos">33</span><span class="nd">@evaluate</span><span class="o">.</span><span class="n">register</span><span class="p">(</span><span class="n">expressions</span><span class="o">.</span><span class="n">Symbol</span><span class="p">)</span>
<span class="linenos">34</span><span class="k">def</span><span class="w"> </span><span class="nf">_</span><span class="p">(</span><span class="n">expr</span><span class="p">,</span> <span class="o">*</span><span class="n">o</span><span class="p">,</span> <span class="n">symbol_map</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
<span class="linenos">35</span> <span class="k">return</span> <span class="n">symbol_map</span><span class="p">[</span><span class="n">expr</span><span class="o">.</span><span class="n">value</span><span class="p">]</span>
<span class="linenos">36</span>
<span class="linenos">37</span>
<span class="linenos">38</span><span class="nd">@evaluate</span><span class="o">.</span><span class="n">register</span><span class="p">(</span><span class="n">expressions</span><span class="o">.</span><span class="n">Add</span><span class="p">)</span>
<span class="linenos">39</span><span class="k">def</span><span class="w"> </span><span class="nf">_</span><span class="p">(</span><span class="n">expr</span><span class="p">,</span> <span class="o">*</span><span class="n">o</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
<span class="linenos">40</span> <span class="k">return</span> <span class="n">o</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">+</span> <span class="n">o</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span>
<span class="linenos">41</span>
<span class="linenos">42</span>
<span class="linenos">43</span><span class="nd">@evaluate</span><span class="o">.</span><span class="n">register</span><span class="p">(</span><span class="n">expressions</span><span class="o">.</span><span class="n">Sub</span><span class="p">)</span>
<span class="linenos">44</span><span class="k">def</span><span class="w"> </span><span class="nf">_</span><span class="p">(</span><span class="n">expr</span><span class="p">,</span> <span class="o">*</span><span class="n">o</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
<span class="linenos">45</span> <span class="k">return</span> <span class="n">o</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">-</span> <span class="n">o</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span>
<span class="linenos">46</span>
<span class="linenos">47</span>
<span class="linenos">48</span><span class="nd">@evaluate</span><span class="o">.</span><span class="n">register</span><span class="p">(</span><span class="n">expressions</span><span class="o">.</span><span class="n">Mul</span><span class="p">)</span>
<span class="linenos">49</span><span class="k">def</span><span class="w"> </span><span class="nf">_</span><span class="p">(</span><span class="n">expr</span><span class="p">,</span> <span class="o">*</span><span class="n">o</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
<span class="linenos">50</span> <span class="k">return</span> <span class="n">o</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">*</span> <span class="n">o</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span>
<span class="linenos">51</span>
<span class="linenos">52</span>
<span class="linenos">53</span><span class="nd">@evaluate</span><span class="o">.</span><span class="n">register</span><span class="p">(</span><span class="n">expressions</span><span class="o">.</span><span class="n">Div</span><span class="p">)</span>
<span class="linenos">54</span><span class="k">def</span><span class="w"> </span><span class="nf">_</span><span class="p">(</span><span class="n">expr</span><span class="p">,</span> <span class="o">*</span><span class="n">o</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
<span class="linenos">55</span> <span class="k">return</span> <span class="n">o</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">/</span> <span class="n">o</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span>
<span class="linenos">56</span>
<span class="linenos">57</span>
<span class="linenos">58</span><span class="nd">@evaluate</span><span class="o">.</span><span class="n">register</span><span class="p">(</span><span class="n">expressions</span><span class="o">.</span><span class="n">Pow</span><span class="p">)</span>
<span class="linenos">59</span><span class="k">def</span><span class="w"> </span><span class="nf">_</span><span class="p">(</span><span class="n">expr</span><span class="p">,</span> <span class="o">*</span><span class="n">o</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
<span class="linenos">60</span> <span class="k">return</span> <span class="n">o</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">**</span> <span class="n">o</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span>
</pre></div>
</div>
</div>
<p>Next we turn our attention to the implementation of evaluation for the different
expression types. Look first at lines 28-30, which provide the evaluation of
<code class="xref py py-class docutils literal notranslate"><span class="pre">Number</span></code> nodes. The function body is trivial: the evaluation of a
<code class="xref py py-class docutils literal notranslate"><span class="pre">Number</span></code> is simply its value. The function interface is more interesting.
Notice that the function name is given as <code class="xref py py-obj docutils literal notranslate"><span class="pre">_</span></code>. This is the Python convention for
a name which will never be used. This function will never be called by its
declared name. Instead, look at the decorator on line 28. The single dispatch
function <a class="reference internal" href="example_code.html#example_code.expression_tools.evaluate" title="example_code.expression_tools.evaluate"><code class="xref py py-func docutils literal notranslate"><span class="pre">evaluate()</span></code></a> has a <a class="reference internal" href="3_objects.html#term-method"><span class="xref std std-term">method</span></a>
<code class="xref py py-meth docutils literal notranslate"><span class="pre">register()</span></code>. When used as a decorator, the <code class="xref py py-meth docutils literal notranslate"><span class="pre">register()</span></code> method of a
single dispatch function registers the function that follows as implementation
for the <a class="reference external" href="https://docs.python.org/3/reference/compound_stmts.html#class" title="(in Python v3.15)"><code class="xref std std-keyword docutils literal notranslate"><span class="pre">class</span></code></a> given as an argument to <code class="xref py py-meth docutils literal notranslate"><span class="pre">register()</span></code>. On this
occasion, this is <code class="xref py py-class docutils literal notranslate"><span class="pre">expressions.Number</span></code>.</p>
<p>Now look at lines 33-35. These contain the implementation of
<a class="reference internal" href="example_code.html#example_code.expression_tools.evaluate" title="example_code.expression_tools.evaluate"><code class="xref py py-func docutils literal notranslate"><span class="pre">evaluate()</span></code></a> for <code class="xref py py-class docutils literal notranslate"><span class="pre">expressions.Symbol</span></code>.
In order to evaluate a symbol, we depend on the mapping from symbol names to
numerical values that has been passed in.</p>
<p>Finally, look at lines 38-40. These define the evaluation visitor for addition.
This works simply by adding the results of evaluating the two operands of
<code class="xref py py-class docutils literal notranslate"><span class="pre">expressions.Add</span></code>. The evaluation visitors for the other operators
follow in an analogous manner.</p>
</section>
<section id="an-expanded-tree-visitor">
<h3><span class="section-number">9.4.4. </span>An expanded tree visitor<a class="headerlink" href="#an-expanded-tree-visitor" title="Link to this heading">¶</a></h3>
<p>The need to provide the <code class="xref py py-obj docutils literal notranslate"><span class="pre">symbol_map</span></code> parameter to the
<code class="xref py py-class docutils literal notranslate"><span class="pre">expressions.Symbol</span></code> evaluation visitor means that the postorder visitor
in <a class="reference internal" href="#postorder-recursive"><span class="std std-numref">Listing 9.4</span></a> is not quite up to the task.
<a class="reference internal" href="#postorder-recursive-kwargs"><span class="std std-numref">Listing 9.8</span></a> extends the tree visitor using the double
splat operator to pass arbitrary keyword arguments through to the visitor
function.</p>
<div class="literal-block-wrapper docutils container" id="id23">
<span id="postorder-recursive-kwargs"></span><div class="code-block-caption"><span class="caption-number">Listing 9.8 </span><span class="caption-text">A recursive tree visitor that passes any keyword arguments
through to the visitor function. This is available as
<code class="xref py py-func docutils literal notranslate"><span class="pre">example_code.expression_tools.post_visitor()</span></code>. We also account
for the name changes between <a class="reference internal" href="example_code.html#example_code.graphs.TreeNode" title="example_code.graphs.TreeNode"><code class="xref py py-class docutils literal notranslate"><span class="pre">TreeNode</span></code></a>
and <code class="xref py py-class docutils literal notranslate"><span class="pre">Expression</span></code>.</span><a class="headerlink" href="#id23" title="Link to this code">¶</a></div>
<div class="highlight-python3 notranslate"><div class="highlight"><pre><span></span><span class="linenos"> 1</span><span class="k">def</span><span class="w"> </span><span class="nf">postvisitor</span><span class="p">(</span><span class="n">expr</span><span class="p">,</span> <span class="n">fn</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">):</span>
<span class="linenos"> 2</span><span class="w"> </span><span class="sd">'''Visit an Expression in postorder applying a function to every node.</span>
<span class="linenos"> 3</span>
<span class="linenos"> 4</span><span class="sd"> Parameters</span>
<span class="linenos"> 5</span><span class="sd"> ----------</span>
<span class="linenos"> 6</span><span class="sd"> expr: Expression</span>
<span class="linenos"> 7</span><span class="sd"> The expression to be visited.</span>
<span class="linenos"> 8</span><span class="sd"> fn: function(node, *o, **kwargs)</span>
<span class="linenos"> 9</span><span class="sd"> A function to be applied at each node. The function should take</span>
<span class="linenos">10</span><span class="sd"> the node to be visited as its first argument, and the results of</span>
<span class="linenos">11</span><span class="sd"> visiting its operands as any further positional arguments. Any</span>
<span class="linenos">12</span><span class="sd"> additional information that the visitor requires can be passed in</span>
<span class="linenos">13</span><span class="sd"> as keyword arguments.</span>
<span class="linenos">14</span><span class="sd"> **kwargs:</span>
<span class="linenos">15</span><span class="sd"> Any additional keyword arguments to be passed to fn.</span>
<span class="linenos">16</span><span class="sd"> '''</span>
<span class="linenos">17</span> <span class="k">return</span> <span class="n">fn</span><span class="p">(</span><span class="n">expr</span><span class="p">,</span>
<span class="linenos">18</span> <span class="o">*</span><span class="p">(</span><span class="n">postvisitor</span><span class="p">(</span><span class="n">c</span><span class="p">,</span> <span class="n">fn</span><span class="p">,</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">)</span> <span class="k">for</span> <span class="n">c</span> <span class="ow">in</span> <span class="n">expr</span><span class="o">.</span><span class="n">operands</span><span class="p">),</span>
<span class="linenos">19</span> <span class="o">**</span><span class="n">kwargs</span><span class="p">)</span>
</pre></div>
</div>
</div>
<p>Assuming we have an implementation of our simple expression language, we are now
in a position to try out our expression evaluator:</p>
<div class="highlight-ipython3 notranslate"><div class="highlight"><pre><span></span><span class="gp">In [1]: </span><span class="kn">from</span><span class="w"> </span><span class="nn">expressions</span><span class="w"> </span><span class="kn">import</span> <span class="n">Symbol</span>
<span class="gp">In [2]: </span><span class="kn">from</span><span class="w"> </span><span class="nn">example_code.expression_tools</span><span class="w"> </span><span class="kn">import</span> <span class="n">evaluate</span><span class="p">,</span> <span class="n">postvisitor</span>
<span class="gp">In [3]: </span><span class="n">x</span> <span class="o">=</span> <span class="n">Symbol</span><span class="p">(</span><span class="s1">'x'</span><span class="p">)</span>
<span class="gp">In [4]: </span><span class="n">y</span> <span class="o">=</span> <span class="n">Symbol</span><span class="p">(</span><span class="s1">'y'</span><span class="p">)</span>
<span class="gp">In [5]: </span><span class="n">expr</span> <span class="o">=</span> <span class="mi">3</span><span class="o">*</span><span class="n">x</span> <span class="o">+</span> <span class="mi">2</span><span class="o">**</span><span class="p">(</span><span class="n">y</span><span class="o">/</span><span class="mi">5</span><span class="p">)</span> <span class="o">-</span> <span class="mi">1</span>
<span class="gp">In [6]: </span><span class="nb">print</span><span class="p">(</span><span class="n">expr</span><span class="p">)</span>
<span class="go">3 * x + 2 ^ (y / 5) - 1</span>
<span class="gp">In [7]: </span><span class="n">postvisitor</span><span class="p">(</span><span class="n">expr</span><span class="p">,</span> <span class="n">evaluate</span><span class="p">,</span> <span class="n">symbol_map</span><span class="o">=</span><span class="p">{</span><span class="s1">'x'</span><span class="p">:</span> <span class="mf">1.5</span><span class="p">,</span> <span class="s1">'y'</span><span class="p">:</span> <span class="mi">10</span><span class="p">})</span>
<span class="gh">Out[7]: </span><span class="go">7.5</span>
</pre></div>
</div>
</section>
</section>
<section id="avoiding-recursion">
<h2><span class="section-number">9.5. </span>Avoiding recursion<a class="headerlink" href="#avoiding-recursion" title="Link to this heading">¶</a></h2>
<p>The recursive tree visitors we have written require very few lines of code, and
very succinctly express the algorithm they represent. However, in most
programming languages (including Python), recursion is a relatively inefficient
process. The reason for this is that it creates a deep <a class="reference internal" href="6_exceptions.html#term-call-stack"><span class="xref std std-term">call stack</span></a>
requiring a new <a class="reference internal" href="6_exceptions.html#term-stack-frame"><span class="xref std std-term">stack frame</span></a> for every level of recursion. In extreme
cases, this can exceed Python’s limit on recursion depth and result in a
<a class="reference external" href="https://docs.python.org/3/builtins/exceptions.html#RecursionError" title="(in Python v3.15)"><code class="xref py py-class docutils literal notranslate"><span class="pre">RecursionError</span></code></a>.</p>
<p>In order to avoid this, we can think a little more about what a recursive
function actually does. In fact, a recursive function is using the <a class="reference internal" href="6_exceptions.html#term-call-stack"><span class="xref std std-term">call
stack</span></a> to control the order in which operations are evaluated. We could do the
same using a <a class="reference internal" href="5_abstract_data_types.html#term-stack"><span class="xref std std-term">stack</span></a> to store which tree nodes still need processing.
There are a number of ways to do this, but one particular algorithm emerges if
we wish to be able to represent expressions not only as trees but as more
general <a class="reference internal" href="#term-DAG"><span class="xref std std-term">directed acyclic graphs</span></a>.</p>
</section>
<section id="representing-expressions-as-dags">
<h2><span class="section-number">9.6. </span>Representing expressions as <a class="reference internal" href="#term-DAG"><span class="xref std std-term">DAGs</span></a><a class="headerlink" href="#representing-expressions-as-dags" title="Link to this heading">¶</a></h2>
<p>If we treat an expression as a tree, then any repeated subexpressions will be
duplicated in the tree. Consider, for example, <span class="math notranslate nohighlight">\(x^2 + 3/x^2\)</span>. If we
create a tree of this expression, then <span class="math notranslate nohighlight">\(x^2\)</span> will occur twice, and any
operation that we perform on <span class="math notranslate nohighlight">\(x^2\)</span> will have to be done twice. If, on the
other hand, we treat the expression as a more general <a class="reference internal" href="#term-directed-acyclic-graph"><span class="xref std std-term">directed acyclic
graph</span></a>, then the single subexpression <span class="math notranslate nohighlight">\(x^2\)</span> can have multiple parents,
and so can appear as an operand more than once. <a class="reference internal" href="#tree-vs-dag"><span class="std std-numref">Fig. 9.7</span></a>
illustrates this distinction.</p>
<figure class="align-default" id="id24">
<span id="tree-vs-dag"></span><div class="graphviz"><object data="_images/graphviz-30b1f86e9c9fc23a27d1a6c916ab204294d55f23.svg" type="image/svg+xml" class="graphviz">
<p class="warning">strict digraph{
a1 [label="+"]
pow1 [label="^"]
x1 [label="x"]
n1 [label="2"]
a1 -> pow1
pow1 -> x1
pow1 -> n1
m1 [label="/"]
n0 [label=3]
pow2 [label="^"]
x2 [label="x"]
n2 [label="2"]
a1 -> m1
m1 -> n0
m1 -> pow2
pow2 -> x2
pow2 -> n2
a3 [label="+", ordering="out"]
pow3 [label="^"]
x3 [label="x"]
n3 [label="2"]
a3 -> pow3
pow3 -> x3
pow3 -> n3
m3 [label="/", ordering="out"]
n4 [label=3]
a3 -> m3
m3 -> n4
m3 -> pow3
}</p></object></div>
<figcaption>
<p><span class="caption-number">Fig. 9.7 </span><span class="caption-text"><a class="reference internal" href="#term-tree"><span class="xref std std-term">Tree</span></a> (left) and <a class="reference internal" href="#term-DAG"><span class="xref std std-term">DAG</span></a> (right) representations
of the expression <span class="math notranslate nohighlight">\(x^2 + 3/x^2\)</span>. Notice that the <a class="reference internal" href="#term-DAG"><span class="xref std std-term">DAG</span></a>
representation avoids the duplication of the <span class="math notranslate nohighlight">\(x^2\)</span> term.</span><a class="headerlink" href="#id24" title="Link to this image">¶</a></p>
</figcaption>
</figure>
<p>The difference between a tree and a DAG may seem small in the tiny examples we
can print on our page, but realistic applications of computer algebra can
easily create expressions with thousands or tens of thousands of terms, in
which larger common subexpressions themselves contain multiple instances of
smaller subexpressions. The repetition of common terms, and therefore data size
and computational cost, induced by the tree representation is exponential in
the depth of nesting. This can easily make the difference between a computation
that completes in a fraction of a second, and one which takes hours to complete
or which exhausts the computer’s memory and therefore fails to complete at all.</p>
<section id="building-expression-dags">
<h3><span class="section-number">9.6.1. </span>Building expression <a class="reference internal" href="#term-DAG"><span class="xref std std-term">DAGs</span></a><a class="headerlink" href="#building-expression-dags" title="Link to this heading">¶</a></h3>
<p>Using somewhat more complex data structures, it is possible to create
expressions that automatically result in <a class="reference internal" href="#term-DAG"><span class="xref std std-term">DAGs</span></a> rather than
<a class="reference internal" href="#term-tree"><span class="xref std std-term">trees</span></a>. That is beyond our scope, but we can
construct expression DAGs using our existing tools, at the expense of a little
extra code. Take as an example the expression we used above: <span class="math notranslate nohighlight">\(x^2 +
3/x^2\)</span>. If we write:</p>
<div class="highlight-ipython3 notranslate"><div class="highlight"><pre><span></span><span class="gp">In [1]: </span><span class="kn">from</span><span class="w"> </span><span class="nn">expressions</span><span class="w"> </span><span class="kn">import</span> <span class="n">Symbol</span>
<span class="gp">In [2]: </span><span class="n">x</span> <span class="o">=</span> <span class="n">Symbol</span><span class="p">(</span><span class="s1">'x'</span><span class="p">)</span>
<span class="gp">In [3]: </span><span class="n">expr</span> <span class="o">=</span> <span class="n">x</span><span class="o">**</span><span class="mi">2</span> <span class="o">+</span> <span class="mi">3</span><span class="o">/</span><span class="n">x</span><span class="o">**</span><span class="mi">2</span>
</pre></div>
</div>
<p>then each occurrence of <code class="xref py py-obj docutils literal notranslate"><span class="pre">x**2</span></code> creates a separate <code class="xref py py-class docutils literal notranslate"><span class="pre">Expression</span></code> object and
we have a tree. However, if we instead write:</p>
<div class="highlight-ipython3 notranslate"><div class="highlight"><pre><span></span><span class="gp">In [1]: </span><span class="kn">from</span><span class="w"> </span><span class="nn">expressions</span><span class="w"> </span><span class="kn">import</span> <span class="n">Symbol</span>
<span class="gp">In [2]: </span><span class="n">x</span> <span class="o">=</span> <span class="n">Symbol</span><span class="p">(</span><span class="s1">'x'</span><span class="p">)</span>
<span class="gp">In [3]: </span><span class="n">x2</span> <span class="o">=</span> <span class="n">x</span><span class="o">**</span><span class="mi">2</span>
<span class="gp">In [4]: </span><span class="n">expr</span> <span class="o">=</span> <span class="n">x2</span> <span class="o">+</span> <span class="mi">3</span><span class="o">/</span><span class="n">x2</span>
</pre></div>
</div>
<p>then we now have a DAG in which the two occurrences of the <span class="math notranslate nohighlight">\(x^2\)</span> term
refer to the same <code class="xref py py-obj docutils literal notranslate"><span class="pre">x**2</span></code> object.</p>
</section>
<section id="dag-visitors">
<h3><span class="section-number">9.6.2. </span><a class="reference internal" href="#term-DAG"><span class="xref std std-term">DAG</span></a> visitors<a class="headerlink" href="#dag-visitors" title="Link to this heading">¶</a></h3>
<p>Even if we represent an expression as a DAG rather than a tree, the simple
recursive tree visitors we have used thus far will undo all of our good work,
because common subexpressions will be visited via each parent expression, rather
than just once. This compounds the disadvantages of recursive visitors that we
discussed above. Instead, we can construct a postorder DAG visitor using a
<a class="reference internal" href="5_abstract_data_types.html#term-stack"><span class="xref std std-term">stack</span></a> to replace the recursion in keeping track of what to evaluate
next, and a <a class="reference external" href="https://docs.python.org/3/builtins/stdtypes.html#dict" title="(in Python v3.15)"><code class="xref py py-class docutils literal notranslate"><span class="pre">dict</span></code></a> to record the nodes we have already visited, and the
results of visiting them. <a class="reference internal" href="#nonrecursive-postvisit"><span class="std std-numref">Listing 9.9</span></a> illustrates one such
algorithm.</p>
<div class="literal-block-wrapper docutils container" id="id25">
<span id="nonrecursive-postvisit"></span><div class="code-block-caption"><span class="caption-number">Listing 9.9 </span><span class="caption-text">Pythonic <a class="reference internal" href="3_objects.html#term-pseudocode"><span class="xref std std-term">pseudocode</span></a> for a non-recursive postorder <a class="reference internal" href="#term-DAG"><span class="xref std std-term">DAG</span></a> visitor.</span><a class="headerlink" href="#id25" title="Link to this code">¶</a></div>
<div class="highlight-python3 notranslate"><div class="highlight"><pre><span></span><span class="linenos"> 1</span><span class="k">def</span><span class="w"> </span><span class="nf">visit</span><span class="p">(</span><span class="n">expr</span><span class="p">,</span> <span class="n">visitor</span><span class="p">):</span>
<span class="linenos"> 2</span> <span class="n">stack</span> <span class="o">=</span> <span class="p">[]</span>
<span class="linenos"> 3</span> <span class="n">visited</span> <span class="o">=</span> <span class="p">{}</span>
<span class="linenos"> 4</span> <span class="n">push</span> <span class="n">expr</span> <span class="n">onto</span> <span class="n">stack</span>
<span class="linenos"> 5</span> <span class="k">while</span> <span class="n">stack</span><span class="p">:</span>
<span class="linenos"> 6</span> <span class="n">e</span> <span class="o">=</span> <span class="n">pop</span> <span class="kn">from</span><span class="w"> </span><span class="nn">stack</span>
<span class="linenos"> 7</span> <span class="n">unvisited_children</span> <span class="o">=</span> <span class="p">[]</span>
<span class="linenos"> 8</span> <span class="k">for</span> <span class="n">o</span> <span class="ow">in</span> <span class="n">e</span><span class="o">.</span><span class="n">operands</span><span class="p">:</span>
<span class="linenos"> 9</span> <span class="k">if</span> <span class="n">o</span> <span class="ow">not</span> <span class="ow">in</span> <span class="n">visited</span><span class="p">:</span>
<span class="linenos">10</span> <span class="n">push</span> <span class="n">o</span> <span class="n">onto</span> <span class="n">unvisited_children</span>
<span class="linenos">11</span>
<span class="linenos">12</span> <span class="k">if</span> <span class="n">unvisited_children</span><span class="p">:</span>
<span class="linenos">13</span> <span class="n">push</span> <span class="n">e</span> <span class="n">onto</span> <span class="n">stack</span> <span class="c1"># Not ready to visit this node yet.</span>
<span class="linenos">14</span> <span class="c1"># Need to visit children before e.</span>
<span class="linenos">15</span> <span class="n">push</span> <span class="nb">all</span> <span class="n">unvisited_children</span> <span class="n">onto</span> <span class="n">stack</span>
<span class="linenos">16</span> <span class="k">else</span><span class="p">:</span>
<span class="linenos">17</span> <span class="c1"># Any children of e have been visited, so we can visit it.</span>
<span class="linenos">18</span> <span class="n">visited</span><span class="p">[</span><span class="n">e</span><span class="p">]</span> <span class="o">=</span> <span class="n">visitor</span><span class="p">(</span><span class="n">e</span><span class="p">,</span> <span class="o">*</span><span class="p">(</span><span class="n">visited</span><span class="p">(</span><span class="n">o</span><span class="p">)</span> <span class="k">for</span> <span class="n">o</span> <span class="ow">in</span> <span class="n">e</span><span class="o">.</span><span class="n">operands</span><span class="p">))</span>
<span class="linenos">19</span>
<span class="linenos">20</span> <span class="c1"># When the stack is empty, we have visited every subexpression,</span>
<span class="linenos">21</span> <span class="c1"># including expr itself.</span>
<span class="linenos">22</span> <span class="k">return</span> <span class="n">visited</span><span class="p">[</span><span class="n">expr</span><span class="p">]</span>
</pre></div>
</div>