-
Notifications
You must be signed in to change notification settings - Fork 0
/
cmplutil1.dtx
4179 lines (4163 loc) · 140 KB
/
cmplutil1.dtx
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
%
% \iffalse (driver)
%<*driver>
\documentclass[a4paper]{tclldoc}[2007/04/01]
\usepackage{longtable}
\usepackage{amsmath,amssymb,amsfonts,amsthm}
\newtheorem{lemma}{Lemma}[section]
\theoremstyle{definition}
\newtheorem{definition}[lemma]{Definition}
\newtheorem{example}[lemma]{Example}
\theoremstyle{remark}
\newtheorem*{remark}{Remark}
\newtheorem*{algsketch}{Algorithm sketch}
\PageIndex
\CodelineNumbered
\setcounter{IndexColumns}{2}
\newenvironment{ttdescription}{%
\description
\def\makelabel##1{\hspace\labelsep\normalfont\ttfamily ##1}%
}{\enddescription}
\makeatletter
\DeclareRobustCommand\SMC{%
\ifx\@currsize\normalsize\small\else
\ifx\@currsize\small\footnotesize\else
\ifx\@currsize\footnotesize\scriptsize\else
\ifx\@currsize\large\normalsize\else
\ifx\@currsize\Large\large\else
\ifx\@currsize\LARGE\Large\else
\ifx\@currsize\scriptsize\tiny\else
\ifx\@currsize\tiny\tiny\else
\ifx\@currsize\huge\LARGE\else
\ifx\@currsize\Huge\huge\else
\small\SMC@unknown@warning
\fi\fi\fi\fi\fi\fi\fi\fi\fi\fi
}
\newcommand{\SMC@unknown@warning}{\TBWarning{\string\SMC: unrecognised
text font size command -- using \string\small}}
\makeatother
\newcommand{\PROP}{{\SMC PROP}}
\newcommand{\PROPs}{{\SMC PROP}s}
\newcommand{\PRO}{{\SMC PRO}}
\newcommand{\ISBN}{{\SMC ISBN}}
\newcommand{\ISBNX}{{\SMC X}}
\providecommand*{\Dash}{%
\hspace*{0.166667em}\textemdash\hspace{0.166667em}%
}
\providecommand*{\Ldash}{%
\hspace{0.166667em}\textemdash\hspace*{0.166667em}%
}
\providecommand*{\dash}{\textendash\hspace{0pt}}
\newcommand{\package}[1]{\textsf{#1}}
\newcommand{\Tcl}{\Tcllogo}
\newcommand*{\DefOrd}[2][]{\textbf{#2}}
\newcommand*{\emDefOrd}[2][]{\emph{#2}}
\newcommand{\mc}{\mathcal}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Zp}{\mathbb{Z}_{>0}}
\newcommand{\Fpil}{\longrightarrow}
\newcommand{\cross}[2]{{}^{#1}\mathsf{X}^{#2}}
\newcommand{\same}[1]{\mathsf{I}^{#1}}
\newcommand{\arity}{\mathrm{ar}}
\newcommand{\coarity}{\mathrm{ca}}
\newcommand{\id}{\mathrm{id}}
\newcommand{\GV}{\mathrm{V}}
\newcommand{\GE}{\mathrm{E}}
\makeatletter
\newcommand*{\setOf}[3][\@gobble]{%
\left\{ \, #2 \,\,\vrule\relax#1.\,\, #3 \, \right\}%
}
\newcommand*{\card}[2][\@gobble]{\left|#1. #2 \right|}
\makeatother
\newcommand*{\pin}[1]{%
\mathchoice{%
\mathrel{\mathrm{in}}%
}{%
\mathrel{\mathrm{in}}%
}{%
\mathop{\mathrm{in}}%
}{%
\mathop{\mathrm{in}}%
}#1%
}
\newcommand{\restr}[2]{#1_{\lvert #2}}
\begin{document}
\DocInput{cmplutil1.dtx}
\end{document}
%</driver>
% \fi
%
% \title{Completing a set of \PROP py identities}
% \author{Lars Hellstr\"om}
% \maketitle
%
% \begin{abstract}
% This is a simple utility for completing sets of \PROP\
% identities, utilising the \textsf{network} package version 2.
% Hopf algebra identities are provided as examples.
% \end{abstract}
%
% \tableofcontents
%
%
% \section{A completion utility}
% \label{Sec:Tillslutning}
%
% This section contains the implementation of a small utility for
% computing the completion of a system of substitution rules. In
% preparation for expected developments, the rules are lists
% \begin{quote}
% \word{left hand side (wfb)} \word{left hand side (rich)}\
% \word{right hand side} \word{derivation}\regopt
% \end{quote}
% where the first left hand side is in the form of a network with
% feedback\Ldash that determines the sort of the entire rule\Dash and
% the second left hand side is the same as a rich network. The
% \word{right hand side} is going to be a linear combination of
% networks, but currently it defaults to being a pair
% \begin{quote}
% \word{canonical} \word{rich}
% \end{quote}
% where \word{canonical} is the canonical form of the right hand
% side network and \word{rich} is a corresponding rich network. The
% utility can thus only handle the special case that every element
% considered has one coefficient equal to $1$ and all other
% coefficients equal to $0$.
%
% If included, the \word{derivation} is a recording of the steps in
% which this rule was derived (rules given as axioms don't have
% derivations). The format of a derivation is as a list
% \begin{quote}
% \begin{regblock}[\regstar]\word{rule spec}
% \word{rich network}\end{regblock}
% \end{quote}
% where each \word{rich network} is a step in the derivation; the
% last one is the \word{right hand side (rich)} whereas the
% \word{left hand side (rich)} is omitted since it is readily
% available elsewhere.\footnote{For more serious work, it might
% actually be better to record only the pure networks, but right now
% rich networks are easier.} A \word{rule spec} is one of
% \begin{quote}
% |backward| \word{rule no.}\\
% |forward| \word{rule no.}
% \end{quote}
% where |backward| items mean that the right hand side of the rule
% is being replaced by the left hand side, and |forward| items is the
% normal way around. It is all |backward| until one reaches the site
% of the ambiguity, and after that it is all |forward|.
%
% \setnamespace{}
% \begin{tcl}
%<*util1>
package require Tk
package require network 2
% \end{tcl}
%
% The following deals with a problem in the Aqua versions of Tk:
% short curves drawn as many small line segments become horribly
% jagged.
% \begin{tcl}
namespace eval tk::mac {variable CGAntialiasLimit 1}
% \end{tcl}
%
%
% \subsection{User interface}
%
% The previous incarnation of this completion procedure was only meant
% to be semi-automatic, so user interaction was an important part of
% the program. This incarnation should do much better, but it still
% retains all the GUI elements of the predecessor.
%
%
% \begin{proc}{new_ambiguity_window}
% The |new_ambiguity_window| procedure creates a new window in which
% one can show an ambiguity and its resolution. There syntax is
% \begin{quote}
% |new_ambiguity_window| \word{title}\regopt
% \end{quote}
% where \word{title} is a title for the window. The return value is
% the name of the |toplevel| created.
%
% \begin{variable}{last_ambiguity_window}
% The |last_ambiguity_window| variable is a number that was used in
% the name of the last ambiguity window. It is incremented with
% every creation of an ambiguity resolution window.
% \begin{tcl}
set last_ambiguity_window 0
% \end{tcl}
% \end{variable}
% The layout of the window created is roughly
% \begin{center}
% \begin{tabular}{ccc}
% \textbf{Left}& \textbf{Top}& \textbf{Right}\\
% \framebox[0.25\linewidth]{Network $1$\vrule width 0pt
% height 10ex depth 9ex}&
% \framebox[0.25\linewidth]{Network $0$\vrule width 0pt
% height 10ex depth 9ex}&
% \framebox[0.25\linewidth]{Network $2$\vrule width 0pt
% height 10ex depth 9ex}\\
% \meta{button}& \meta{message}&\meta{button}
% \end{tabular}
% \end{center}
% where the middle network $0$ is the ambiguity and the flank networks
% $1$ and $2$ are things to which it can be reduced. The buttons are
% for choosing which of the two that will be made the left hand side
% of a new rule.
%
% This procedure also creates a ``middle button'' |bm| which is
% used for cases where neither the left nor the right button would
% do the right thing. This button is initially unmapped, but so
% anyone wanting to make it visible should supply the relevant
% |grid| command.
% \begin{tcl}
proc new_ambiguity_window {{title {}}} {
variable last_ambiguity_window
incr last_ambiguity_window
set t [toplevel .ambiguity$last_ambiguity_window]
if {![string length $title]} then {
set title "Ambiguity $last_ambiguity_window"
}
wm title $t $title
bindtags $t [linsert [bindtags $t] 1 Ambiguity]
label $t.hl -text "Left"
label $t.hm -text "Top"
label $t.hr -text "Right"
grid $t.hl -row 0 -column 0 -sticky s
grid $t.hm -row 0 -column 1 -sticky s
grid $t.hr -row 0 -column 2 -sticky s
foreach c [list $t.cl $t.cm $t.cr] {
canvas $c -width 200 -height 400 -relief solid -borderwidth 1\
-xscrollincrement 1 -yscrollincrement 1
}
grid $t.cl -row 1 -column 0 -sticky nswe
grid $t.cm -row 1 -column 1 -sticky nswe
grid $t.cr -row 1 -column 2 -sticky nswe
button $t.bl -text "Reduce" -state disabled
button $t.bm -text "Change this text"
button $t.br -text "Reduce" -state disabled
grid $t.bl -row 2 -column 0 -sticky n
grid $t.br -row 2 -column 2 -sticky n
label $t.lm -justify center -text {}
grid $t.lm -row 2 -column 1 -sticky nwe
grid rowconfigure $t 1 -weight 1
grid columnconfigure $t 0 -weight 1
grid columnconfigure $t 1 -weight 1
grid columnconfigure $t 2 -weight 1
foreach c [list $t.cl $t.cm $t.cr] {
bindtags $c [linsert [bindtags $c] 1 Network]
}
%<*test3>
bind $t <FocusIn> [list puts stdout "$t got focus."]
bind $t <FocusOut> [list puts stdout "$t lost focus."]
%</test3>
return $t
}
% \end{tcl}
% \end{proc}
%
% The \describestring[bindtag]{Network}|Network| bindtag is used for
% all canvases displaying networks. It offers bindings for grabbing the
% network with the mouse and moving it around. The |-cursor|
% man\oe uvres are meant to isolate this use of the mouse from that
% of clicking hyperlinks, which is supported by the rule browser.
% \begin{tcl}
bind Network <ButtonPress-1> {
if {[%W cget -cursor] eq ""} then {
%W configure -cursor fleur
%W scan mark %x %y
}
}
bind Network <B1-Motion> {
if {[%W cget -cursor] eq "fleur"} then {%W scan dragto %x %y 1}
}
bind Network <ButtonRelease-1> {
if {[%W cget -cursor] eq "fleur"} then {
%W configure -cursor ""
}
}
bind Network <B1-Leave> {%W configure -cursor ""}
% \end{tcl}
%
% \begin{proc}{center_network}
% This procedure scrolls a canvas so that the contents appear in
% the center of the visible region. The call syntax is
% \begin{quote}
% |center_network| \word{canvas} \word{itemOrId}\regopt
% \end{quote}
% where \word{itemOrId} selects the items to center. If not
% specified, then this defaults to |all|.
% \begin{tcl}
proc center_network {c {id all}} {
foreach {left top right bottom} {0 0 0 0} break
foreach {left top right bottom} [$c bbox $id] break
%<debug> puts "In $c center $id:($left,$top,$right,$bottom)"
$c scan mark [expr {($right+$left)/2}] [expr {($bottom+$top)/2}]
set w [winfo width $c]
if {$w < 10} then {set w [winfo reqwidth $c]}
set h [winfo height $c]
if {$h < 10} then {set h [winfo reqheight $c]}
$c scan dragto [
expr {round([$c canvasx [expr {$w/2}]])}
] [
expr {round([$c canvasy [expr {$h/2}]])}
] 1
%<debug> puts "TopLeft is ([$c canvasx 0],[$c canvasy 0])."
}
% \end{tcl}
% \end{proc}
%
% \begin{arrayvar}{after_id}
% The |after_id| array is used for storing |after| identifiers which
% are related to a particular ambiguity. Every index should have the
% name of the toplevel window to which they belong as prefix. It is
% recommended that further qualifications use widget names as far as
% these are able to distinguish matters, and then use |'| as
% delimiter for further separation.
%
% See |idle_reschedule| for an example of a procedure that uses
% this array.
% \end{arrayvar}
%
% \begin{proc}{ambiguity_cancel}
% The |ambiguity_cancel| procedure cancels the |after| script(s) for a
% toplevel, if there are any. The syntax is
% \begin{quote}
% |ambiguity_cancel| \word{toplevel}
% \end{quote}
% It is meant to be called from an envent binding, e.g.~|FocusOut|.
% \changes{2}{2007/02/14}{Modified to handle the case that a
% toplevel name is a prefix of another toplevel name. (LH)}
% \begin{tcl}
proc ambiguity_cancel {t} {
global after_id
foreach i [
concat [list $t] [array names after_id "${t}.*"]\
[array names after_id "${t}'*"]
] {
after cancel $after_id($i)
unset after_id($i)
}
}
% \end{tcl}
% \end{proc}
%
% The \describestring[bindtag]{Ambiguity}|Ambiguity| bindtag is used for
% toplevels displaying ambiguities. It is used for controlling which
% ambiguity is being processed. An ambiguity whose window loses focus
% should seize all processing.
% \begin{tcl}
bind Ambiguity <FocusOut> {ambiguity_cancel %W}
% \end{tcl}
% It seems toplevels have a tendency to wander off the screen, so the
% ambiguity windows can do with a |<Configure>| binding to correct that.
% \begin{tcl}
bind Ambiguity <Configure> {ensure_on_screen %W}
% \end{tcl}
%
% \begin{proc}{ensure_on_screen}
% This procedure moves a toplevel to ensure that it is completely on
% its screen. The argument is the name of the toplevel.
% \begin{tcl}
proc ensure_on_screen {w} {
if {$w ne [winfo toplevel $w]} then {return}
set extra_width\
[expr {[winfo vrootwidth $w] - [winfo reqwidth $w]}]
set extra_height\
[expr {[winfo vrootheight $w] - [winfo reqheight $w]}]
set x [winfo rootx $w]
set y [winfo rooty $w]
set moved 0
if {$extra_width > 0 && $x > $extra_width} then {
set x [expr {$x - $extra_width}]
set moved 1
}
if {$extra_height > 0 && $y > $extra_height} then {
set y [expr {$y - $extra_height}]
set moved 1
}
if {$moved} then {
wm geometry $w +${x}+${y}
}
}
% \end{tcl}
% \end{proc}
%
% \begin{proc}{create_controller}
% The |create_controller| procedure creates a controller window, for
% controlling how the processing of ambiguities are run. The syntax is
% \begin{quote}
% |create_controller| \word{major-var} \word{minor-var}
% \end{quote}
% where \word{major-var} and \word{minor-var} are names of two global
% variables which are linked to |entry| widgets.
% \begin{tcl}
proc create_controller {major_var minor_var} {
set t [toplevel .controller]
label $t.ll -text "Left rule:"
label $t.lr -text "Right rule:"
entry $t.el -textvariable $minor_var
entry $t.er -textvariable $major_var
foreach c [list $t.cl $t.cr] {
canvas $c -width 200 -height 400 -relief solid -borderwidth 1
bindtags $c [linsert [bindtags $c] 1 Network]
}
grid $t.cl - -row 0 -column 0 -sticky nsew
grid $t.cr - -row 0 -column 2 -sticky nsew
grid rowconfigure $t 0 -weight 1
grid $t.ll -row 1 -column 0 -sticky e
grid $t.el -row 1 -column 1 -sticky w
grid $t.lr -row 1 -column 2 -sticky e
grid $t.er -row 1 -column 3 -sticky w
foreach i {0 1 2 3} {grid columnconfigure $t $i -weight 1}
button $t.b_go -text Go
grid $t.b_go -row 2 -column 3
button $t.b_next -text Next
grid $t.b_next -row 2 -column 0
checkbutton $t.check_auto -text "Auto Next Go"\
-variable $t.check_auto
grid $t.check_auto - -row 2 -column 1 -sticky e
}
% \end{tcl}
% \end{proc}
%
% \begin{variable}{.controller.check_auto}
% This is the value variable of the \textsf{Auto Next Go}
% checkbutton.
% \end{variable}
%
% \begin{arrayvar}{Network}
% The |Network| array is used for storing networks directly associated
% with some widget. The indices are widget names (paths). The entries
% are rich networks.
% \end{arrayvar}
%
% \begin{variable}{vertex_appearances}
% \begin{variable}{vertex_sizes}
% The |vertex_appearances| variable holds the dictionary of
% appearances for the vertex types currently occuring in the rule
% networks. It is used by those procedures that draw or
% redraw networks. The |vertex_sizes| variable is a list patterns
% and vertex sizes for use with |make_level-layout-Tk|.
% \begin{tcl}
set vertex_sizes {* {20 20}}
% \end{tcl}
% \end{variable}\end{variable}
%
%
% \begin{proc}{show_sparsest_cut}
% This procedure exists to examine the capabilities of the
% |network::pure::sparsest_cut| procedure. The call syntax is
% \begin{quote}
% |show_sparsest_cut| \word{canvas}
% \end{quote}
% and this does the following: (i)~look up the network shown in the
% \word{canvas}, (ii)~compute its sparsest cut region, (iii)~update
% the display of the network with this region, and (iv)~report the
% time taken to |stdout|. Nothing is done if the \word{canvas} does
% not have a |Network| entry.
% \begin{tcl}
proc show_sparsest_cut {c} {
global Network vertex_appearances
if {![info exists Network($c)]} then {return}
array set NW $Network($c)
set time [time {set region [
network::pure::sparsest_cut $NW(pure)
]}]
if {[llength $region]} then {
network::rich::drawit $c $vertex_appearances {} -update 1\
-var NW -region $region
}
puts [format {Vertices: %d/%d. Boundary: %d. %s}\
[llength [lindex $region 0]] [llength [lindex $NW(pure) 0]]\
[llength [concat [lindex $region 1] [lindex $region 2]]] $time]
}
%<showcut>bind Network <Command-ButtonPress-1> {show_sparsest_cut %W}
% \end{tcl}
% \end{proc}
%
%
%
% \subsection{Reduction}
%
% \begin{variable}{rulesL}
% The |rulesL| variable contains the current list of reduction rules.
% New rules are appended at the end. Rules are never removed.
% \end{variable}
%
% \begin{variable}{reduce_stats}
% For the purpose of speeding up the reduction process, the normal
% reduction procedure requires an auxilliary table of how often the
% various rules have been used just after another rule. This table is
% implemented as a list with one elment per rule, where each list
% element is a list with the structure
% \begin{quote}
% \word{rule no.} \word{after $0$} \word{after $1$} \word{after $2$}
% \dots
% \end{quote}
% where each \word{after $i$} is the number of times this rule could be
% applied following an application of rule $i$. These numbers would be
% updated whenever a reduction was made.
%
% The table is stored in the variable |reduce_stats|.
% \end{variable}
%
% \begin{proc}{repair_reduce_stats}
% When importing a dumped set of rules, the |reduce_stats| and
% |rulesL| variables can get out of sync. This procedure extends
% |reduce_stats| to be consistent with |rulesL|. There are no
% variables, nor any particular return value.
% \changes{2.1}{2007/12/19}{Procedure added. (LH)}
% \begin{tcl}
proc repair_reduce_stats {} {
global reduce_stats rulesL
set newL {}
foreach line $reduce_stats {
set Seen([lindex $line 0]) ""
while {[llength $line] <= [llength $rulesL]} {lappend line 0}
lappend newL $line
}
for {set n 0} {$n < [llength $rulesL]} {incr n} {
if {[info exists Seen($n)]} then {continue}
set line [list $n]
while {[llength $line] <= [llength $rulesL]} {lappend line 0}
lappend newL $line
}
set reduce_stats $newL
return
}
% \end{tcl}
% \end{proc}
%
% \begin{proc}{add_rule}
% The |add_rule| procedure adds a rule to the list of rules and
% extends the table of reduction statistics accordingly. The syntax
% is
% \begin{displaysyntax}
% |add_rule| \word{feedbacks}
% \begin{regblock}|pure|\regalt|rich|\end{regblock}
% \word{left hand side}
% \begin{regblock}|pure|\regalt|rich|\end{regblock}
% \word{right hand side}
% \word{target-var}\regopt
% \end{displaysyntax}
% where the \word{left hand side} and \word{right hand side} are
% pure or rich networks, according to the indication in the
% preceeding argument. \word{feedbacks} is the list of feedbacks
% for this rule. The return value is the number of the new rule.
%
% If a \word{target-var} is given, then it is the name in the
% calling context of a variable to which the rule will be
% |lappend|ed instead of |rulesL|. In this case, the reduction
% statistics tables are left alone.
% \begin{tcl}
proc add_rule {feedbackL type_left left type_right right {tovar ""}} {
global rulesL rule_queue reduce_stats vertex_appearances\
vertex_sizes
switch -- $type_left "pure" {
set NW1(pure) $left
} "rich" {
array set NW1 $left
} default {
error "type must be 'pure' or 'rich'"
}
if {![info exists NW1(vpos-Tk)] || ![info exists NW1(ecurve-Tk-tt)]}\
then {
if {![info exists NW1(level-layout-Tk)]} then {
network::rich::make_level-layout-Tk $vertex_sizes -var NW1
}
if {![info exists NW1(vpos-Tk)]} then {
network::rich::vpos-Tk_by_level -var NW1
}
if {![info exists NW1(ecurve-Tk-tt)]} then {
network::rich::ecurve-Tk-tt_by_level $vertex_appearances\
-var NW1
}
}
if {![info exists NW1(canonical)]} then {
set NW1(canonical) [network::pure::canonise $NW1(pure)]
}
switch -- $type_right "pure" {
set NW2(pure) $right
} "rich" {
array set NW2 $right
} default {
error "type must be 'pure' or 'rich'"
}
if {![info exists NW2(vpos-Tk)] || ![info exists NW2(ecurve-Tk-tt)]}\
then {
if {![info exists NW2(level-layout-Tk)]} then {
network::rich::make_level-layout-Tk $vertex_sizes -var NW2
}
if {![info exists NW2(vpos-Tk)]} then {
network::rich::vpos-Tk_by_level -var NW2
}
if {![info exists NW2(ecurve-Tk-tt)]} then {
network::rich::ecurve-Tk-tt_by_level $vertex_appearances\
-var NW2
}
}
if {![info exists NW2(canonical)]} then {
set NW2(canonical) [network::pure::canonise $NW2(pure)]
}
set rule [list [
list $NW1(pure) $feedbackL
] [
array get NW1
] [
list $NW2(canonical) [array get NW2]
]]
if {$tovar ne ""} then {
upvar 1 $tovar toL
set index [llength $toL]
lappend toL $rule
return $index
}
cull_rules [list $NW1(pure) $feedbackL]
set index [llength $rulesL]
lappend rulesL $rule
set new_stats {}
foreach row $reduce_stats {
lappend row 0
lappend new_stats $row
}
lappend new_stats\
[linsert [string repeat " 0" [llength $rulesL]] 0 $index]
set reduce_stats $new_stats
lappend rule_queue [list $index\
[score_network $NW1(pure) $feedbackL]]
return $index
}
% \end{tcl}
% \end{proc}
%
% \begin{proc}{score_network}
% This procedure computes the sort key used in the |rule_queue|.
% The call syntax is
% \begin{displaysyntax}
% |score_network| \word{network} \word{feedbacks}
% \end{displaysyntax}
% The default definition just returns the number of vertices, but
% it can be overridden for specific problems.
% \begin{tcl}
proc score_network {NW fbL} {llength [lindex $NW 0]}
% \end{tcl}
% \end{proc}
%
%
% \begin{proc}{make_rule_derivation}
% This procedure constructs a \word{derivation} section to for a
% rule, but doesn't modify the |rulesL|. The call syntax is
% \begin{quote}
% |make_rule_derivation| \word{backwards} \word{top}
% \word{forwards}
% \end{quote}
% where the \word{backwards} argument are the steps in the
% derivation which will be |backward|s, the \word{top} is the rich
% network that serves as turning point, and the \word{forwards}
% is the list of |forward| steps in the derivation.
% \begin{tcl}
proc make_rule_derivation {bwL top fwL} {
set res {}
for {set n [llength $bwL]} {$n>0} {} {
set step [lindex $bwL [incr n -1]]
set rule [lindex $bwL [incr n -1]]
lappend res $step [list backward $rule]
}
lappend res $top
foreach {rule step} $fwL {
lappend res [list forward $rule] $step
}
return [lrange $res 1 end]
}
% \end{tcl}
% \end{proc}
%
% \begin{proc}{add_rule_derivation}
% This procedure adds a \word{derivation} section to an existing
% rule. The call syntax is
% \begin{quote}
% |add_rule_derivation| \word{to-no.} \word{backwards} \word{top}
% \word{forwards}
% \end{quote}
% where \word{to-no.} is the number of the rule to modify. This
% number is also the return value. The \word{backwards} argument
% are the steps in the derivation which will be |backward|s, the
% \word{top} is the rich network that serves as turning point, and
% the \word{forwards} is the list of |forward| steps in the
% derivation.
% \begin{tcl}
proc add_rule_derivation {target bwL top fwL} {
global rulesL
set L [lrange [lindex $rulesL $target] 0 2]
lappend L [make_rule_derivation $bwL $top $fwL]
lset rulesL $target $L
return $target
}
% \end{tcl}
% \end{proc}
%
% \begin{proc}{unmake_rule_derivation}
% This procedure does the opposite of |make_rule_derivation|, i.e.,
% it reconstructs the
% \begin{quote}
% \word{backwards} \word{top} \word{forwards}
% \end{quote}
% from a rule with derivation. The call syntax is
% \begin{quote}
% |unmake_rule_derivation| \word{rule}
% \end{quote}
% and the return value is the three element list shown above.
% \begin{tcl}
proc unmake_rule_derivation {rule} {
set res {}
set fwL {}
set n -1
foreach {rel step} [lindex $rule 3] {
if {[lindex $rel 0] eq "backward"} then {incr n 2} else {
lappend fwL [lindex $rel 1] $step
}
}
set bwL {}
for {} {$n>0} {incr n -2} {
lappend bwL [lindex $rule 3 $n] [lindex $rule 3 [expr {$n-1}] 1]
}
lappend bwL [lindex $rule 1]
return [list [lrange $bwL 1 end] [lindex $bwL 0] $fwL]
}
% \end{tcl}
% \end{proc}
%
%
% \begin{variable}{equalitiesL}
% This variable has the same structure as |rulesL|, although it is
% for equalities that could not be turned into rules. The choice of
% what to label as the ``left'' or ``right'' hand side is arbitrary.
% \end{variable}
%
% \begin{arrayvar}{equality_side}
% A problem with the equalities is that there are usually several
% ways to derive them, so if one simply adds everything derived
% that cannot be turned into a rule to |equalitiesL| then there
% will be duplicate entries. The |equality_side| array maps sides
% of an equality to the location in |equalitiesL| where they occur,
% so that such rederivation can be detected. The indices are lists
% with the structure
% \begin{quote}
% \word{canonical pure network} \word{feedback-list}
% \end{quote}
% where the \word{canonical pure network} is what it says it is,
% and the \word{feedback-list} is the |lsort -dictionary| sorted
% list of feedbacks. The entries are lists, where each element is a
% pair
% \begin{quote}
% \word{equality number} \word{side}
% \end{quote}
% where the \word{side} is |0| for the left hand side and |1| for
% the right hand side. The reason the entries are lists is the
% chance that more than two networks can be found equal.
% \end{arrayvar}
%
% \begin{variable}{remaining_equalities}
% Since |equality_side| maps networks to equality numbers, the
% equality numbers should be fixed, and hence it is not possible to
% remove elements from |equalitiesL|. Since equalities may still be
% dropped if a new rule applies to them, the |remaining_equalities|
% list stores the numbers of those equalities which remain to
% resolve.
% \end{variable}
%
% \begin{proc}{add_equality}
% This procedure adds an entry to |equalitiesL|. The call syntax is
% \begin{quote}
% |add_equality| \word{feedbacks} \word{backwards} \word{top}
% \word{forwards} \word{reason}
% \end{quote}
% The \word{feedbacks} is the feedback type for this equality.
% The \word{backwards} argument are the steps in the derivation
% which will be |backward|s, the \word{top} is the rich network that
% serves as turning point, and the \word{forwards} is the list of
% |forward| steps in the derivation. The \word{reason} is the
% reason this was turned into an equality, typically the result of
% comparing the two sides of it.
% \changes{2.2}{2009/02/10}{Modified to notice duplicate
% equalities. Moved \texttt{stdout} messages here. (LH)}
% \begin{tcl}
proc add_equality {feedbackL bwL top fwL reason} {
global equalitiesL equality_side remaining_equalities
array set NW1 [lindex $bwL end]
array set NW2 [lindex $fwL end]
set NW1c [network::pure::canonise $NW1(pure)]
set NW2c [network::pure::canonise $NW2(pure)]
set feedbackLc [lsort -dictionary $feedbackL]
set idx1 [list $NW1c $feedbackLc]
set idx2 [list $NW2c $feedbackLc]
if {[info exists equality_side($idx1)] &&\
[info exists equality_side($idx2)]} then {
foreach pair $equality_side($idx1) {
set S([lindex $pair 0]) [lindex $pair 1]
}
foreach pair $equality_side($idx2) {
if {[info exists S([lindex $pair 0])]} then {
%<*stdout>
puts stdout "Rediscovered equality [lindex $pair 0]."
%</stdout>
return
}
}
}
set num [llength $equalitiesL]
lappend equality_side($idx1) [list $num 0]
lappend equality_side($idx2) [list $num 1]
set eq [list [list $NW1(pure) $feedbackL] [lindex $bwL end]]
lappend eq [list $NW2c [lindex $fwL end]]
lappend eq [make_rule_derivation $bwL $top $fwL]
lappend equalitiesL $eq
lappend remaining_equalities $num
%<*stdout>
puts stdout "Added equality $num ($reason)."
%</stdout>
return $num
}
% \end{tcl}
% \end{proc}
%
% \begin{proc}{rule_children}
% This procedure lists the numbers and equalities that are direct
% children of a specified rule, i.e., the given rule was one of
% those that gave rise to the underlying ambiguity. The call syntax
% is
% \begin{displaysyntax}
% |rule_children| \word{rule number}
% \end{displaysyntax}
% and the result is a string, with one line per child.
% \begin{tcl}
proc rule_children {parent} {
global rulesL equalitiesL
set res {}
foreach list [list $rulesL $equalitiesL] prefix {"" e} {
set n -1; foreach rule $list {incr n
set line $prefix$n
set bwL {}; set fwL {}
foreach {spec NW} [lindex $rule 3] {
switch -- [lindex $spec 0] "forward" {
lappend fwL [lindex $spec 1]
} "backward" {
lappend bwL [lindex $spec 1]
}
}
if {[lindex $fwL 0] == $parent} then {
append line " with [lindex $bwL end]"
lappend res $line
} elseif {[lindex $bwL end] == $parent} then {
append line " with [lindex $fwL 0]"
lappend res $line
}
}
}
return [join $res \n]
}
% \end{tcl}
% \end{proc}
%
% \begin{proc}{clear_rules}
% The |clear_rules| procedure clears the lists of rules and statistics
% of rules. It takes no arguments.
% \begin{tcl}
proc clear_rules {} {
global rulesL reduce_stats rule_base rule_queue equalitiesL\
remaining_equalities browser_fwL browser_bwL
set rulesL [list]
set reduce_stats [list]
set rule_base [list]
set rule_queue [list]
set equalitiesL {}
set remaining_equalities {}
set browser_fwL {}
set browser_bwL {}
}
% \end{tcl}
% \end{proc}
%
% \begin{proc}{cull_rules}
% The |cull_rules| procedure searches through |reduce_stats| for rules
% that are should be removed from active use because their principal
% parts can be reduced by another rule. The syntax is
% \begin{quote}
% |cull_rules| \word{network with feedback}
% \end{quote}
% \begin{tcl}
proc cull_rules {NW} {
global reduce_stats rulesL
set new_statsL [list]
foreach row $reduce_stats {
if {[llength [
network::wfb::instances [lindex $rulesL [lindex $row 0] 0] $NW
]]} then {
%<stdout> puts stdout "Dropped rule [lindex $row 0]."
} else {
lappend new_statsL $row
}
}
set reduce_stats $new_statsL
}
% \end{tcl}
% \end{proc}
%
% \begin{arrayvar}{Steps}
% This array records the reduction steps that have been carried out
% in a |Network| canvas. The index is the name of the canvas,
% whereas an entry is a list
% \begin{quote}
% \begin{regblock}[\regstar]\word{rule no.}
% \word{rich network}\end{regblock}
% \end{quote}
% where the \word{rich network} is what appeared in the canvas
% after applying the corresponding rule. Later results are appended
% to the end of this list.
% \end{arrayvar}
%
%
% \begin{proc}{graphic_reduce}
% The |graphic_reduce| procedure reduces a network one step, if
% possible, while updating its graphical appearance on a canvas. The
% syntax is
% \begin{quote}
% |graphic_reduce| \word{network-var} \word{feedbacks}
% \word{canvas} \word{last rule}
% \end{quote}
% where \word{network-var} is the name of a variable in the local
% context of the caller. The \word{network-var} is assumed to contain
% a rich network (as a dict, not unrolled into an array) whose
% feedbacks are \word{feedbacks}, which is currently drawn on the
% specified \word{canvas}. The procedure will try to reduce the
% network, starting with the assumption that \word{last rule} is the
% number of the most recently applied rule, and if it succeeds update
% the |reduce_stats| variable. In the case of success it will also
% replace the network on the canvas by the reduced form.
%
% The return value is the number of the rule that was applied, or |-1|
% if no rule could be applied. The \word{last rule} upon calling may
% be |-1|.
%
% \begin{tcl}
proc graphic_reduce {NWvar fbL canvas last} {
global rulesL reduce_stats vertex_appearances vertex_sizes Steps
array set NW [uplevel 1 [list ::set $NWvar]]
set reduce_stats\
[lsort -index [expr {$last+1}] -decreasing -integer $reduce_stats]
set sites {}
set i -1; foreach t $reduce_stats {incr i
set n [lindex $t 0]
set sites [
network::wfb::instances [list $NW(pure) $fbL]\
[lindex $rulesL $n 0] 1
]
if {[llength $sites]} then {break}
}
if {![llength $sites]} then {return -1}
if {$last>=0} then {
lset reduce_stats $i [expr {$last+1}]\
[expr {[lindex $reduce_stats $i [expr {$last+1}]] +1}]
}
set NW(pure) [network::pure::replace $NW(pure) [lindex $sites 0]\
[lindex $rulesL $n 2 0]]
network::rich::make_level-layout-Tk $vertex_sizes -var NW
network::rich::vpos-Tk_by_level -var NW
network::rich::ecurve-Tk-tt_by_level $vertex_appearances -var NW
$canvas delete all
network::rich::drawit $canvas $vertex_appearances {} -var NW
center_network $canvas
lappend Steps($canvas) $n [array get NW]
uplevel 1 [list ::set $NWvar [lindex $Steps($canvas) end]]
return $n
}
% \end{tcl}
% \end{proc}
%
% \begin{arrayvar}{lastrule}
% The |lastrule| array stores the number of the last reduction rule
% that was applied to the network in a particular canvas. The index
% is the canvas name (widget path).
% \end{arrayvar}
%
% \begin{arrayvar}{feedbacks}
% The |feedbacks| array stores the sorts (feedbacks-lists) of
% networks that appear in windows. The index is the name of a