-
Notifications
You must be signed in to change notification settings - Fork 7
/
Consize.Prelude.tex
1650 lines (1238 loc) · 95.5 KB
/
Consize.Prelude.tex
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
\chapter{Die Prelude}
\label{Sec:Prelude}
Consize ist eine sehr primitive Sprache, die allein mit rund 50 atomaren Wörter auskommt. Damit kann man zwar programmieren -- aber das Programmieren mit Consize einzig mit den Wörtern der VM ist zu umständlich und macht wenig Spaß. Viel schlimmer noch: Consize ist anfänglich nicht einmal in der Lage, mit Ihnen zu interagieren. Wenn Sie Consize starten, möchte Consize eine Datei namens \verb|prelude.txt| verarbeiten, die sogenannte Prelude. Fehlt die Datei oder steht dort Unsinn drin, macht Consize entweder gar nichts -- oder eben eine Menge Unsinn. So oder so, wir können mit Consize im Urzustand kaum sinnvoll arbeiten.
Der Clou an Consize ist: Die Sprache lässt sich erweitern. Machen wir uns die Sprache komfortabel. Wir werden etliche neue Wörter einführen, die hilfreiche Abstraktionen bieten, wir werden die Syntax erweitern und Consize interaktiv machen. Die dazu nötigen Programme stehen in der Prelude.
% Dieser Vorgang nennt sich "`\href{http://de.wikipedia.org/wiki/Bootstrapping_(Informatik)}{Bootstrapping}"'.
In diesem Kapitel sind alle Programmzeilen der Prelude durch ein vorangestelltes "`\verb|>> |"' (inkl.\ Leerzeichen) ausgezeichnet. Diese Markierung soll Ihnen helfen, in dem gesamten Text dieses Kapitels mit all seinen Erläuterungen und Beispielen die entscheidenden Programmzeilen zu identifizieren. Übrigens helfen die Markierungen auch Consize, um den Quelltext aus der Dokumentation zu filtern.
% Consize sucht sich die markierten Zeilen ebenfalls zusammen -- mehr dazu später in Kap.~\ref{Sec:Dateien}.
%Abseits zum Zwecke der Markierung können Sie die Auszeichnung "`\verb|>> |"' gedanklich ignorieren.
Auch wenn der Einstieg in die Prelude gleich ein unvermittelter Einstieg in die Programmierung mit Consize ist: Sie werden sehen, Consize ist nicht wirklich schwer zu verstehen. In Consize zerlegt man Programme systematisch in kleine Miniprogramme, die zu schreiben vergleichbar ist mit der Herausforderung von Rätselaufgaben. Und Sie haben einen immensen Vorteil bei der Arbeit mit Consize: Ihnen stehen die Consize-Erweiterungen direkt zur Verfügung. Sie arbeiten mit einer geladenen Prelude, um die Prelude zu verstehen. Das ist einfacher und umkomplizierter als sich das anhört. Sie können ein paar Hilfsmittel, wie z.B.\ den Debugger nutzen, um sich die Arbeitsweise von Consize zu veranschaulichen.
\section{Vorbereitungen: Was sein muss und was nützlich ist}
\subsection{Consize-Lizenz}
Die Prelude beginnt mit einer \href{http://de.wikipedia.org/wiki/Pr%C3%A4ambel}{Präambel}.
Die Prelude ist \href{http://de.wikipedia.org/wiki/Open_source}{Open-Source-Software} (OSS). Consize soll als Bildungsgut allen Interessierten frei zur Verfügung stehen.
\begin{verbatim}
>> %%% A Prelude for Consize in Consize
>> %%% Copyright (c) 2017, Dominikus Herzberg, https://www.thm.de
>> %%% New BSD License: http://opensource.org/licenses/BSD-3-Clause
\end{verbatim}
%>> %%%
%>> %%% Consize is very much inspired by Factor, see http://factorcode.org.
%>> %%% Links to Factor's documentation help you compare the languages.
%>>
\subsection{Booting zur Verarbeitung der Prelude}
\label{Sec:LoadBootimage}
In Consize schreibt man Programme, indem man Wörter zum globalen Wörterbuch hinzufügt und das Wort mit einer Quotierung -- einem Mini-Programm, wenn man so möchte -- assoziiert. Das ist ein sehr einfacher, aber auch sehr leistungsfähiger Abstraktionsmechanismus. So abstrahiert das Wort \verb|-rot| die Quotierung \verb|[ rot rot ]|. Man spricht auch von einer benamten Abstraktion: \verb|-rot| ist der "`Name"' für die Abstraktion \verb|[ rot rot ]|.
% Sie erinnern sich an Kap.~\ref{Sec:AtomareWoerter}, S.~\pageref{rotsource}:
\begin{verbatim}
> \ -rot get-dict nil get
[ rot rot ]
\end{verbatim}
Mit dieser Abstraktionstechnik werden große und umfangreiche Programme überhaupt erst realisierbar. Wir Menschen müssen mehr oder minder große Programmeinheiten unter für uns sinngebenden Namen fassen können. Ansonsten stoßen unsere intellektuellen Fähigkeiten beim Programmieren rasch an ihre Grenzen.
Fortan wollen wir die Definition neuer Einträge im Wörterbuch wie folgt notieren: Ein Doppelpunkt \verb|:| leitet die Definition ein. Nach dem Doppelpunkt folgt das Wort, dann optional der Stapeleffekt und anschließend die das Wort definierende Wortfolge. Ein Semikolon schließt die Definition ab.
% Die definierende Wortfolge ist die mit dem Wort assoziierte Quotierung, allerdings ohne die eckigen Klammern.
In Anlehnung an die in Kap.~\ref{Sec:UrGrammatik} formulierte Grammatik hält die folgende Regel den Aufbau einer Wort-Definition fest.
\begin{grammar}
<definition> = ':' <separator> <word> [ <separator> <stackeffect> ] <separator> <program> <separator> ';'
\end{grammar}
Die Angabe von Stapeleffekten kennen Sie bereits aus Kap.~\ref{Sec:ConsizeVM}. Alle Wörter der Consize-VM sind dort mit ihren Stapeleffekten angegeben worden. Details zur Umsetzung von \synt{definition} finden sich in Kap.~\ref{Sec:DefWords}, S.~\pageref{Sec:DefWords}.
Die Syntax zur Definition neuer Wörter kann nicht direkt verwendet werden, da die Consize-VM sie nicht kennt. Es bedarf eines kleinen Consize-Programms, das diese komfortable Art der Definition neuer Wörter zur Verfügung stellt. Dieses Consize-Programm ist als sogenanntes "`Bootimage"' in der Datei \verb|bootimage.txt| abgelegt und muss zuvor geladen werden. Der Ladevorgang fährt die Consize-VM in einen programmiertauglichen Zustand hoch, was man als "`\href{http://de.wikipedia.org/wiki/Booten}{Booten}"' bezeichnen kann.
%>> % A TINY BOOTIMAGE
%>>
\begin{verbatim}
>> \ bootimage.txt run
\end{verbatim}
%>>
In Kap.~\ref{Sec:Bootstrapping} ist beschrieben, was in dem Bootimage steht und wie es erzeugt wird.
\subsection{Definition von \texttt{read-word} und \texttt{read-mapping}}
Der durch \verb|stepcc| beschriebene Ausführungsmechanismus der Consize-VM ist in engen Grenzen konfigurierbar. Das Verhalten der beiden Wörter \verb|read-word| und \verb|read-mapping| kann vom Anwender bzw. von der Anwenderin frei definiert werden.
Die Prelude assoziiert beide Wörter mit "`leeren"' Programmen. Das bedeutet: Unbekannte Wörter werden genauso wie Mappings auf dem Datastack belassen.
%>> % DEFINITION OF META-WORDS
%>>
\begin{verbatim}
>> : read-word ( wrd -- wrd ) ;
>> : read-mapping ( map -- map ) ;
\end{verbatim}
%>>
Durch Anpassung dieser Wörter sind beispielsweise Kodierungskonventionen für Wörter und Mappings einführbar, die eine Sonderbehandlung erfahren oder eine Vorverarbeitung erfordern sollen. Zu beachten ist, dass eine alternative Definition dieser Meta-Wörter das Risiko birgt, existierenden Code in größerem Umfang zu brechen. Man muss sehr sorgsam mit diesen Wörtern umgehen.
\subsection{Mehr davon: Stack Shuffler}
In praktisch allen höheren Programmiersprachen können Variablen in Form von Zuweisungen (bei imperativen Sprachen) oder Substitutionen (bei deklarativen\slash funktionalen Sprachen) verwendet werden. Variablen erfüllen dabei hauptsächlich zwei Aufgaben: sie helfen Werte zwischenzuspeichern und sie neu zu arrangieren für den Aufruf von Funktionen, Prozeduren oder Methoden. Darüber hinaus bieten Variablennamen semantische Brücken für den Programmierer bzw.\ die Programmiererin an, sich den Inhalt oder den Zweck eines Wertes zu merken.
Da es in Consize keine Variablen gibt, muss das Zwischenspeichern von Werten über die Erzeugung von Duplikaten auf dem Datastack möglich sein (deshalb gibt es \verb|dup| in der Consize-VM) und das Rearrangieren von Werten über Stack-Shuffling gelöst werden. Es ist daher sehr hilfreich, weitere Wörter als Abstraktionen zu den Stack-Shufflern der Consize-VM zur Verfügung zu haben.
Da Variablennamen als semantische Brücken beim Programmieren fehlen, gibt es nur eine Möglichkeit, um Consize-Programme übersichtlich zu halten: Man muss die Definition von neuen Wörtern kurz halten und gegebenenfalls weitere Wörter einführen, um über geeignete Abstraktionen die Programme lesbar zu halten. Das ist auch der Grund, warum sich Wortdefinitionen oft nur über ein, zwei oder drei Zeilen erstrecken und praktisch nie über ein Dutzend Codezeilen hinausgehen. Und es unterstreicht auch die Bedeutung der Angabe von Stapeleffekten. Stapeleffekte beschreiben oft hinreichend genau, was ein Wort tut, so dass man sich das \emph{Wie} der Manipulation der Werte auf dem Eingangsstapel nicht merken muss. Stapeleffekte erfüllen die Funktion einer Schnittstellenbeschreibung (\emph{interface description}).
%>> % STACK SHUFFLING
%>>
\begin{verbatim}
>> : 2drop ( x y -- ) drop drop ;
>> : 3drop ( x y z -- ) drop drop drop ;
>> : 2dup ( x y -- x y x y ) over over ;
>> : 3dup ( x y z -- x y z x y z ) pick pick pick ;
>> : dupd ( x y -- x x y ) swap dup rot ; % dup deep
>> : swapd ( x y z -- y x z ) swap rot rot ; % swap deep
>> : -rot ( x y z -- z x y ) rot rot ;
>> : rot4 ( x y z u -- y z u x ) [ rot ] dip swap ;
>> : -rot4 ( x y z u -- u x y z ) swap [ -rot ] dip ;
>> : pick ( x y z -- x y z x ) rot dup [ -rot ] dip ;
>> : over ( x y -- x y x ) swap dup -rot ;
>> : 2over ( x y z -- x y z x y ) pick pick ;
>> : nip ( x y -- y ) swap drop ;
>> : 2nip ( x y z -- z ) nip nip ;
\end{verbatim}
%>>
Es deutet sich bei den Definitionen einiger Stack-Shuffler wie z.B.\ \verb|rot4| und \verb|-rot4| an, dass es eine Alternative zum Stack-Shuffling gibt, die die Abwesenheit von Variablen elegant kompensiert: Kombinatoren, siehe Kap.~\ref{Sec:Kombinatoren}.
Zum Beispiel kann \verb|rot4| auch wie folgt definiert werden; das Stack-Shuffling ist im Kopf kaum mehr nachvollziehbar -- die Kommentare mögen bei den gedanklichen Schritten helfen.
\begin{verbatim}
: rot4 ( x y z u -- y z u x )
[ ] swap push swap push % x y [ z u ]
rot swap % y x [ z u ]
dup top swap pop top % y x z u
rot ; % y z u x
\end{verbatim}
Da die Stack-Shuffler der Consize-VM nicht über die ersten drei Elemente auf dem Datastack hinaus reichen, muss hier zu dem Trick gegriffen werden, Elemente vom Datastack in einen Stapel zu "`packen"', um auf das vierte Element von oben, hier \verb|x|, zugreifen zu können.
Mit Hilfe des \verb|dip|-Kombinators wird der Code radikal kürzer und gleichzeitig auch leicht nachvollziehbar. Es werden zunächst die unteren drei Werte, \verb|x| \verb|y| \verb|z|, auf dem Datastack per \verb|rot| rotiert, dann die obersten zwei Werte mit \verb|swap| getauscht.
Interessant ist auch, dass bei dem Einsatz von Kombinatoren die Reversibilität des Verhaltens von \verb|-rot4| zu \verb|rot4| klar zutage tritt: \verb|-rot4| tauscht erst die beiden obersten Elemente und rotiert dann die untersten drei. Die alternative Definition von \verb|-rot4| mittels
\begin{verbatim}
: -rot4 ( x y z u -- u x y z ) rot4 rot4 rot4 ;
\end{verbatim}
macht nicht nur deutlich schwerer nachvollziehbar, was die mehrfache Anwendung eines \verb|rot4| bewirkt, sondern sie hat auch die dreifachen Laufzeitkosten eines \verb|rot4|.
Mehr zu \verb|dip| und den anderen Kombinatoren steht in Kap.~\ref{Sec:Kombinatoren}.
\subsection{Freunde und Helferlein}
\label{Sec:Friends}
Bei der Arbeit mit Consize werden Sie feststellen, dass Sie einige Wortkombinationen sehr häufig benötigen. Es macht Sinn, eigene Wörter dafür einzuführen, um den Consize-Code lesbarer zu machen.
Die folgenden Wörter sind hilfreiche Begleiter bei der Arbeit mit Stapeln.
%>> % FRIENDS & HELPERS
%>>
\begin{verbatim}
>> : swapu ( itm stk -- stk' ) cons ; % deprecated
>> : cons ( itm stk -- [ itm & stk ] ) swap push ;
>> : uncons ( [ itm & stk ] -- itm stk ) dup top swap pop ;
>> : unpush ( [ itm & stk ] -- stk itm ) dup pop swap top ;
>> : empty? ( stk -- t/f ) ( ) equal? ;
>> : size ( seq -- n ) dup empty? [ drop 0 ] [ pop size 1 + ] if ;
>> : time ( quot -- ... msecs )
>> current-time-millis swap dip current-time-millis swap - ;
\end{verbatim}
%>>
Die Anzahl der Elemente in einer Sequenz liefert \verb|size| zurück.
\begin{verbatim}
> clear [ ] size [ x y z ] size
0 3
\end{verbatim}
Der Wert \verb|nil| zum Datentyp "`nil"' ist in Consize nur indirekt über ein \verb|top| eines leeren Stapels definiert. Um den Wert ohne Umwege zugreifbar zu haben, gibt es das Wort \verb|nil|.
Das Wort \verb|lookup| schlägt den mit einem Wort assoziierten Wert im Wörterbuch nach, \verb|delete| entfernt das Wort auf seinen Zielwert aus dem Wörterbuch. Das Wort \verb|values| gibt -- im Gegensatz zu \verb|keys| -- alle mit den Schlüsseln assoziierten Zielwerte als Sequenz zurück.
\begin{verbatim}
>> : nil ( -- nil ) ( ) top ;
>> : lookup ( word -- item ) get-dict nil get ;
>> : delete ( itm -- ) get-dict dissoc set-dict ;
>> : values ( dict -- seq ) dup keys swap [ nil get ] cons map ;
\end{verbatim}
%>>
\subsection{Kombinatoren: \texttt{call}, \texttt{fcall}}
Ein "`Kombinator"' ist ein Wort, das einen Stapel zur Ausführung bringt, d.h.\ das den Stapel als Programm interpretiert. Einen solchen Stapel nennen wir "`Quotierung"'. Der Stapel dient nur als Mittel zum Zweck, um die Ausführung des darin enthaltenen Programms zurückzustellen. Der Kombinator aktiviert die Quotierung.
% Ein Wort aus dem Wörterbuch heißt "`Kombinator"', wenn es eine oder mehr Quotierungen auf dem Datastack erwartet und die Quotierung(en) zur Abarbeitung bringt. Ganz offensichtlich ist \verb|call| ein Kombinator, das Wort \verb|conca| hingegen nicht.
% \subsection{Quotierungen aufrufen}
Wenn Consize ein Programm abarbeitet, ist es zu einem guten Teil mit der Auflösung benamter Abstraktionen beschäftigt: Das oberste Wort auf dem Callstack wird durch den Inhalt der mit ihm assoziierten Quotierung ersetzt. Technisch ausgedrückt: Das Wort wird vom Callstack entfernt und die assoziierte Quotierung mit dem Callstack konkateniert.
Für den Aufruf anonymer Abstraktionen, d.h. Quotierungen, die nicht im Wörterbuch mit einem Wort verknüpft sind, gilt im Grunde der gleiche Ablauf -- realisiert durch den Kombinator \verb|call|. Das Wort erwartet eine Quotierung auf dem Eingangsstapel, die es mit dem Callstack konkateniert. Implementiert werden kann dieses Verhalten mit Zugriff auf die aktuelle Continuation. Der Stapeleffekt soll die Umsetzung per \verb|call/cc| abbilden.
%>> % CALL A QUOTATION (ANONYMOUS ABSTRACTION)
%>> % http://docs.factorcode.org/content/article-combinators.html
%>> % http://docs.factorcode.org/content/article-call.html
%>>
\begin{verbatim}
>> : call ( [ quot & ds ] cs -- ds quot cs concat )
>> [ swap unpush rot concat continue ] call/cc ;
\end{verbatim}
%>>
Das mit \verb|call/cc| initiierte Programm tauscht Data- und Callstack der aktuellen Continuation (\verb|swap|), holt das oberste Element (die Quotierung) vom Datastack (\verb|unpush|), bringt den Callstack wieder nach oben (\verb|rot|) und konkateniert Quotierung und Callstack miteinander (\verb|concat|). Anschließend übernimmt die so veränderte Continuation wieder die Aus\-füh\-rung (\verb|continue|).\footnote{\texttt{call} ist bereits in der Consize-VM definiert, siehe Kap.~\ref{sec:core.start}. Da \texttt{call} nicht zwingend Teil der VM sein muss, wird die Definition in der Prelude wiederholt.}
Im Beispiel wird das per Quotierung zurückgestellte Programm, die Addition, erst durch den Aufruf von \verb|call| ausgeführt.
\begin{verbatim}
> clear 4 2 3 [ + ]
4 2 3 [ + ]
> call
4 5
\end{verbatim}
Die Technik, mit \verb|call/cc| und \verb|continue| ein Programm zu unterbrechen, es zu modifizieren und dann fortzusetzen, nennt man "`\href{http://de.wikipedia.org/wiki/Metaprogrammierung}{Metaprogrammierung}"'. Das mit \verb|call/cc| mitgegebene Programm modifiziert das aktuell in der Ausführung begriffene Programm. Diese zur Laufzeit des Programms stattfindende Änderung nennt man deshalb auch "`Laufzeit-Metaprogrammierung"'.
Mit Hilfe des \verb|call|-Kombinators können direkt oder indirekt alle anderen Kombinatoren abgeleitet werden. Einzig \verb|fcall| (für "`\emph{call via a function}") ist eine Ausnahme, aber nur deshalb, weil es eine andere Implementierungsstrategie über Funktionen verfolgt. Es erzeugt im Gegensatz zu \verb|call| über \verb|func| einen eigenen Ausführungs\-kon\-text, bekommt einen leeren Stapel als Eingangsstapel, wendet die Funktion darauf an (\verb|apply|) und liefert das Ausführungsergebnis als Stapel zurück und zwar mit dem "`umgekehrten"' Ergebnisstapel (\verb|reverse|).
\begin{verbatim}
>> : fcall ( quot -- seq ) get-dict func ( ) swap apply reverse ;
\end{verbatim}
%>>
\begin{verbatim}
> clear [ 4 2 3 + ] fcall
[ 4 5 ]
\end{verbatim}
Das Wort \verb|fcall| nimmt den Callstack der Implementierungssprache von Consize in Anspruch, \verb|call| nutzt den Callstack der aktuellen Continuation.
Die Namen der Kombinatoren in den folgenden Kapiteln orientieren sich in vielen Fällen an der konkatenativen Sprache Factor. Bisweilen sind auch die Definition der Kombinatoren von Factor übernommen.
\section{Entscheidungskombinatoren}
Ein grundlegendes Feature einer turingvollständigen Programmiersprache ist es, Entscheidungen treffen zu können: wähle -- abhängig von einem Entscheidungswert -- entweder dieses oder jenes. Im einfachstenfall ist der Entscheidungswert zweiwertig, binär. Zu Ehren des Logikers \href{http://de.wikipedia.org/wiki/George\_Boole}{{\sc George Boole}} heißen diese beiden Werte "`boolesche Werte"' und werden mit "`wahr"' (\emph{true}) und "`falsch"' (\emph{false}) bezeichnet. In Consize repräsentieren die Werte \verb|t| und \verb|f| diese beiden Optionen; in einem Programm schreibt es sich lesbarer mit \verb|true| und \verb|false|.
\subsection{Boolesche Werte und die binäre Wahl mit \texttt{choose}}
Die Consize-VM bietet von sich aus kein Wort an, das Entscheidungen realisiert; in vielen Programmiersprachen dient dazu das \emph{if}. Trotzdem -- und das ist das Spannende daran -- ist ein Wort für Entscheidungen nachrüstbar. Der \href{http://en.wikipedia.org/wiki/Lambda_calculus}{Lambda-Kalkül} macht es übrigens genauso.
Das Wort \verb|choose ( t/f this that -- this/that )| bildet die Grundlage für die binäre Auswahl. \verb|choose| erwartet auf dem Datastack einen booleschen Wert und zwei Wahlwerte, die wir im Stapeleffekt mit \verb|this| und \verb|that| bezeichnen. Abhängig vom booleschen Wert lässt \verb|choose| entweder \verb|this| oder \verb|that| auf dem Datastack zurück.
Die Bedeutung von \verb|t| und \verb|f| erschließt sich nur im Kontext des Wortes \verb|choose| -- und so bilden die mit den booleschen Werten assoziierten Programme exakt das beschriebene Verhalten nach: \verb|t| entfernt \verb|that| vom Datastack, um \verb|this| zu erhalten, \verb|f| macht es genau anders herum. Ohne den Kontext von \verb|choose| sind die booleschen Werte \verb|t| und \verb|f| bedeutungslos.
%>> % BOOLEAN VALUES, BOOLEAN CHOICE
%>> % http://docs.factorcode.org/content/article-booleans.html
%>>
\begin{verbatim}
: t ( this that -- this ) drop ;
: f ( this that -- that ) swap drop ;
\end{verbatim}
Die Wörter \verb|true| und \verb|false| dienen lediglich dem Lese- und Schreibkomfort beim Programmieren; es ist rasch vergessen, das Escape-Wort einem \verb|t| bzw. \verb|f| voranzustellen, denn schließlich sollen die Programme für \verb|t| und \verb|f| nicht sofort ausgeführt werden.
\begin{verbatim}
>> : true ( -- t ) \ t ;
>> : false ( -- f ) \ f ;
\end{verbatim}
%>>
Das Wort \verb|choose| muss per \verb|rot| den booleschen Wert lediglich oben auf den Datastack bringen, die Bedeutung (sprich: Semantik) von \verb|t| bzw. \verb|f| mit \verb|lookup| nachschlagen, und die ermittelte Quotierung mit \verb|call| aufrufen. Das Wort \verb|choose| macht nicht viel mehr als das mit \verb|t| bzw. \verb|f| assoziierte Verhalten zu aktivieren.
\begin{verbatim}
: choose ( t/f this that -- this/that ) rot lookup call ;
\end{verbatim}
Mit dieser Definition könnte man es bewenden lassen, doch es gibt einen guten Grund, die Auslegung boolescher Werte ein wenig zu erweitern.
Falls sich bei \verb|choose| weder ein \verb|t| noch ein \verb|f| an dritter Stelle, sondern ein beliebiger anderer Wert auf dem Datastack befindet, dann hat der Programmierer bzw.\ die Programmiererin den im Stapeleffekt dokumentierten "`Vertrag"' zum Gebrauch des Wortes \verb|choose| gebrochen. Die Folgen aus einem fälschlichen Gebrauch des Wortes hat der Programmierer bzw.\ die Programmiererin zu verantworten. Es spielt keine Rolle, ob der Fehlgebrauch unabsichtlich erfolgt oder nicht. Dieses Prinzip ist so wichtig, dass es nicht nur "`im richtigen Leben"' sondern auch in der Softwaretechnik zur Anwendung kommt: Wer einen Vertrag verletzt, darf die andere Partei (in dem Fall Consize) nicht für den entstehenden Schaden verantwortlich machen. Man muss beim Programmieren durchaus Vorsicht walten lassen.
Man könnte eine Vertragsverletzung durch eine Fehlermeldung abfangen, um auf das Problem aufmerksam zu machen und gegebenenfalls darauf zu reagieren. Allerdings verändert ein solches Vorgehen das Wort \verb|choose| von einer binären zu einer ternären Wahl: wähle \verb|this| im Fall von \verb|t|, \verb|that| im Fall von \verb|f| und mache etwas gänzlich anderes, wenn ein anderes Datum an dritter Position im Datastack steht. Das passt nicht zu unseren anfänglichen Intentionen, mit \verb|choose| lediglich eine binäre Auswahl treffen zu wollen.
Programmiersprachen mit \href{http://de.wikipedia.org/wiki/Dynamische\_Typisierung}{dynamischer Typisierung} -- Consize gehört dazu -- unterstützen zwar ein strikt binäres Verhalten, vermeiden aber Fehlermeldungen in der Regel durch eine simple Regelung: Jeder Wert, der sich von \verb|f| unterscheidet, wird so interpretiert als sei er ein logisches \emph{true}. Wenn der dritte Wert auf dem Datastack nicht \verb|f| ist, dann wählt \verb|choose| \verb|this|, ansonsten \verb|that| aus. Die Definition von \verb|choose| verändert sich entsprechend geringfügig. Der Stern \verb|*| im Stapeleffekt steht für einen beliebigen Wert außer \verb|f|.
\begin{verbatim}
: choose ( f/* this that -- that/this )
swap rot false equal? lookup call ;
\end{verbatim}
Sprachen mit \href{http://de.wikipedia.org/wiki/Statische\_Typisierung}{statischer Typisierung} schließen den Fehlerfall eines nicht booleschen Wertes durch eine Typüberprüfung vor Programmausführung aus. Wäre Consize eine statisch typisierte Sprache, könnte die Verwendung eines booleschen Wertes sicher gestellt werden, und es würde die eingangs angegebene Definition von \verb|choose| ausreichen.
Wenn die booleschen Werte nur im Kontext von \verb|choose| sinnvoll interpretiert werden können, stellt sich die Frage, ob die Bedeutung von \verb|t| und \verb|f| überhaupt außerhalb von \verb|choose| bekannt sein muss. Anders gefragt: Kommen wir ohne Einträge für \verb|t| und \verb|f| im Wörterbuch aus? In der Tat lässt sich ein "`lokales"' Wörterbuch im Rumpf der Definition von \verb|choose| verwenden. Und den Vergleich per \verb|equal?| bekommen wir bei einer Wörterbuchabfrage per \verb|get| gleichermaßen "`geschenkt"'.
\begin{verbatim}
>> SYMBOL: t
>> SYMBOL: f
>>
>> : choose ( f/* this that -- that/this )
>> rot { \ f [ swap drop ] } [ drop ] get call ;
\end{verbatim}
%>>
Das Verhalten von \verb|choose| demonstriert folgende Beispieleingabe an der Konsole.
\begin{verbatim}
> clear false this that
f this that
> choose
that
> clear [ 1 2 3 ] this that choose
this
\end{verbatim}
Die logischen Operationen der \href{http://de.wikipedia.org/wiki/Boolesche\_Algebra}{Booleschen Algebra} \verb|and| (Konjunktion), \verb|or| (Disjunktion), \verb|xor| (ausschließende Disjunktion) und \verb|not| (Negation) sind dieser erweiterten Interpretation logischer Werte ("`alles was nicht \verb|f| ist, ist logisch \verb|t|"') angepasst.
\begin{verbatim}
>> : and ( f/* f/* -- t/f ) over choose ; % Factor
>> : or ( f/* f/* -- t/f ) dupd choose ; % Factor
>> : xor ( f/* f/* -- t/f ) [ f swap choose ] when* ; % Factor
>> : not ( f/* -- t/f ) false true choose ;
\end{verbatim}
%>>
Ein kurzes Beispiel zeigt den Gebrauch von \verb|and|.
\begin{verbatim}
> clear true true and
t
> false true and
t f
\end{verbatim}
\subsection{Binäre Entscheidungen: \texttt{if}, \texttt{when}, \texttt{unless} \& Co.}
Das Wort \verb|choose| realisiert zwar eine binäre Wahl, doch werden damit noch keine unterschiedlichen Verhaltenskonsequenzen umgesetzt. Das ist erst dann der Fall, wenn \verb|this| und \verb|that| Quotierungen sind, die nach einem \verb|choose| per \verb|call| aufgerufen werden. Dafür gibt es das Wort \verb|if|; die Quotierungen werden im Stapeleffekt mit \verb|then| und \verb|else| bezeichnet. Dass die Auswirkungen auf den Datastack von den beiden Quotierungen abhängen und nicht vorhersehbar sind, deuten die Punkte auf der rechten Seite des Stapeleffekts an.
%>> % CONDITIONAL COMBINATORS
%>> % http://docs.factorcode.org/content/article-conditionals.html
%>>
\begin{verbatim}
>> : if ( f/* then else -- ... ) choose call ;
>> : if-not ( f/* then else -- ... ) swap if ;
>> : when ( f/* then -- ... ) [ ] if ;
>> : unless ( f/* else -- ... ) [ ] if-not ;
\end{verbatim}
%>>
Die Wörter \verb|if-not|, \verb|when| und \verb|unless| sind hilfreiche Abstraktionen, die alle Variationen des \verb|if|-Themas abdecken: \verb|if-not| vertauscht die Rolle der beiden Quotierungen \verb|then| und \verb|else| (dem gedanklich eine Negation des booleschen Wertes entspricht), \verb|when| führt die Quotierung nur aus, wenn der vorangehende Wert als logisch \emph{true} gilt, \verb|unless|, wenn er \emph{false} ist.
\begin{verbatim}
> clear 5 dup 3 < [ 1 + ] [ 1 - ] if
4
> clear 5 dup 3 < [ 1 + ] [ 1 - ] if-not
6
> clear 5 true [ 1 + ] when
6
> clear 5 false [ 1 - ] unless
4
\end{verbatim}
Jeder Wert außer \verb|f| gilt im Kontext eines \verb|if|, \verb|if-not|, \verb|when| oder \verb|unless| als logisch \emph{true}, selbst wenn der Bedingungswert nicht gleich \verb|t| ist. Da macht es bisweilen Sinn, den logisch wahren Bedingungswert auf dem Stapel durch ein implizites \verb|dup| zu erhalten, um mit ihm weiter rechnen zu können. Genau dafür gibt es die "`Stern-Varianten"' \verb|if*|, \verb|when*| und \verb|unless*|. Ist der Bedingungswert \verb|f|, so unterbleibt die Duplizierung und \verb|if*|, \verb|when*| bzw. \verb|unless*| arbeiten wie ihre "`sternlosen"' Vorbilder \verb|if|, \verb|when| und \verb|unless|.
\begin{verbatim}
>> : if* ( f/* then else -- ... )
>> pick [ drop call ] [ 2nip call ] if ; % Factor
>> : when* ( f/* then -- ... ) over [ call ] [ 2drop ] if ; % Factor
>> : unless* ( f/* else -- ... ) over [ drop ] [ nip call ] if ; % Factor
\end{verbatim}
%>>
\begin{verbatim}
> clear 6 [ 1 + ] [ 0 ] if*
7
> clear false [ 1 + ] [ 0 ] if*
0
> 6 [ 1 + ] when*
7
> clear 5 6 [ 1 - ] unless*
5 6
> clear 5 false [ 1 - ] unless*
4
\end{verbatim}
\subsection{$n$-äre Entscheidungen: \texttt{case} und \texttt{cond}}
Die mit dem Wort \verb|case| umgesetzte $n$-äre Entscheidung verallgemeinert das Konzept der binären \verb|if|-Entscheidung. Eine Handlungsalternative hängt bei \verb|case| nicht ab von zwei Alternativen (\verb|f| oder nicht \verb|f|), sondern von einem Wert aus einer Menge von Werten. Die Grundfunktionalität von \verb|case| ist bereits durch Mappings gegeben; nach einem \verb|get| muss im Grunde nur noch ein \verb|call| folgen. Mit dem Auswahlwert \verb|:else| besteht die Option, eine Reaktion zu initiieren, wenn kein sonstiger Auswahlwert in \verb|case| zutrifft.
Das Wort \verb|SYMBOL:| setzt mit dem nachfolgenden Wort, hier \verb|:else|, eine Definition auf, die das Wort mit sich selbst als Datenwert definiert (hier \verb|: :else \ :else ;|).
\begin{verbatim}
>> SYMBOL: :else
>> : case ( val { val' quot ... } -- ... )
>> :else over [ ] get get call ;
\end{verbatim}
%>>
Es ist zu beachten, dass die Zielwerte in einem "`\verb|case|-Mapping"' stets Quotierungen sind.
\begin{verbatim}
> clear 3 \ red
3 red
> { \ red [ 1 + ] \ blue [ 1 - ] :else [ ] } case
4
> blue { \ red [ 1 + ] \ blue [ 1 - ] :else [ ] } case
3
> black { \ red [ 1 + ] \ blue [ 1 - ] :else [ ] } case
3
\end{verbatim}
Die Verschachtlung von \verb|if|-Wörtern in den \verb|else|-Quotierungen eines \verb|if|-Worts erzeugt rasch unleserlichen Code. Als Alternative bietet sich das syntaktisch übersichtlichere \verb|cond| an, das die \verb|test|- und \verb|then|-Quo\-tie\-run\-gen verschachtlungsfrei zu notieren erlaubt. Einer \verb|test|-Quotierung folgt eine \verb|then|-Quotierung; im \verb|else|-Fall folgt die nächste \verb|test|-Quotierung usw.; die Terminologie orientiert sich an der Beschreibung des Stapeleffekts für \verb|if|. Eine optionale \verb|else|-Quotierung dient für den Fall, wenn alle \verb|test|-Quotierungen fehlschlagen.
\begin{verbatim}
>> : cond ( [ test1 then1 test2 then3 ... else ] -- ... )
>> dup empty? % anything left to test?
>> [ drop ] % no: quit
>> [ uncons dup empty? % only one quotation left?
>> [ drop call ] % yes: call 'else'
>> [ uncons % otherwise:
>> [ ] \ cond push cons % prepare 'cond' recursion
>> [ call ] 2dip if ] % call 'testN' and apply 'if'
>> if ]
>> if ;
\end{verbatim}
%>>
Per Konvention wird die Folge von Quotierungen vor einem \verb|cond| in runden Klammern notiert, nicht zuletzt, um eine visuell leichtere Abgrenzung zu haben. Beachten Sie, dass in den \verb|test|-Quotierungen in aller Regel ein \verb|dup| nötig ist, nicht zuletzt, um den Test-Wert für nachfolgende Bedingungen zu erhalten.
\begin{verbatim}
> clear
> 7 ( [ dup 0 > ] [ 1 + ] [ dup 0 < ] [ 1 - ] [ ] ) cond
8
> -7 ( [ dup 0 > ] [ 1 + ] [ dup 0 < ] [ 1 - ] [ ] ) cond
8 -8
> 0 ( [ dup 0 > ] [ 1 + ] [ dup 0 < ] [ 1 - ] [ ] ) cond
8 -8 0
\end{verbatim}
Ein \verb|case| lässt sich immer über ein \verb|cond| nachbilden, allerdings hat ein \verb|case| durch das Mapping ein besseres Laufzeitverhalten, während die Laufzeit von \verb|cond| mit jeder Verschachtlung linear anwächst. Umgekehrt kann nicht jedes \verb|cond| in ein äquivalentes \verb|case| umgewandelt werden.
\section{Aufruf-Kombinatoren}
\label{Sec:Kombinatoren}
Dieses Kapitel beschäftigt sich mit Kombinatoren, die Varianten von \verb|call| sind und unter dem Oberbegriff der "`Aufruf-Kombinatoren"' (\verb|call|-Kombinatoren) laufen. Die Abtauch-Kombinatoren (\verb|dip|-Kombinatoren) lassen die oberen Stapelwerte vor dem \verb|call| der Quotierung abtauchen, die Erhaltungskombinatoren (\verb|keep|-Kombinatoren) restaurieren die oberen Werte nach dem \verb|call| wieder. Wieder andere Kombinatoren rufen zwei oder mehr Quotierungen nach verschiedenen Mustern auf (Cleave-, Spread- und Apply-Kombinatoren).
Generell reduzieren diese Kombinatoren die Notwendigkeit des Stack-Shufflings und bringen deshalb lesbarere Programme mit sich.
\subsection{"`Abtauch"'-Kombinatoren: \texttt{dip}}\label{Sec:dip}
Die \verb|dip|-Kombinatoren rufen wie ein \verb|call| eine Quotierung auf dem Datastack auf. Im Gegensatz zu einem reinen \verb|call| gehen die unmittelbar "`vor"' der Quotierung stehenden Daten für die Dauer des Aufrufs gleichermaßen auf Tauchstation; das englische Wort \emph{dip} ist hier im Sinne von "`abtauchen"' zu verstehen. Nach dem Aufruf erscheinen die "`abgetauchten"' Daten wieder auf dem Datastack. Das Wort \verb|dip| verbirgt ein Element vor der aufzurufenden Quotierung, das Wort \verb|2dip| verbirgt zwei Elemente, \verb|3dip| drei und \verb|4dip| vier.
%>> % DATAFLOW COMBINATORS
%>> % http://docs.factorcode.org/content/article-dataflow-combinators.html
%>>
%>> % CALL A QUOTATION AND HIDE ITEMS UNDERNEATH
%>> % http://docs.factorcode.org/content/article-dip-keep-combinators.html
%>>
\begin{verbatim}
>> : dip ( x quot -- x ) [ ] rot push \ \ push concat call ;
>> : 2dip ( x y quot -- x y ) swap [ dip ] dip ;
>> : 3dip ( x y z quot -- x y z ) swap [ 2dip ] dip ;
>> : 4dip ( w x y z quot -- w x y z ) swap [ 3dip ] dip ;
\end{verbatim}
%>>
\begin{verbatim}
> clear [ ] 4 5 [ push ] dip
[ 4 ] 5
> clear [ ] 4 5 [ drop ] 2dip
4 5
\end{verbatim}
Die Definition $n$-facher \verb|dip|-Kombinatoren folgt einem einfachen Schema: Das einleitende \verb|swap| und das beendende \verb|dip| bleiben immer gleich; lediglich die Quotierung greift auf die vorhergehende \verb|dip|-Definition zurück. In der Rückverfolgung des Bildungsgesetzes kann man auch fragen: Wie müsste demnach die Definition von \verb|dip| lauten? In der Quotierung wäre ein \verb|0dip| zu verwenden. Ein \verb|dip|, das \verb|0| Werte auf dem Datastack "`abtauchen"' lässt, ist identisch mit \verb|call|.
\begin{verbatim}
: dip ( x quot -- x ) swap [ call ] dip ;
\end{verbatim}
Diese Definition nimmt auf sich selbst Bezug und liefert auch in ihrer Auflösung von \verb|dip| im Definitionsrumpf durch die Definition von \verb|dip| keine weitere Erkenntnisse. Einen Hinweis, wie \verb|dip| implementiert werden kann, liefert sie dennoch: Es ist der Versuch, das im Stapeleffekt mit \verb|x| bezeichnete Element nicht mehr vor der Quotierung, sondern es per \verb|swap| hinter die Quotierung zu bekommen, so dass der \verb|call| der Quotierung \verb|quot| das Element \verb|x| nicht mehr erfasst.
Man kann dieses Verhalten zum Beispiel durch die Manipulation der aktuellen Continuation nach einem \verb|swap| erreichen; der Stapeleffekt deutet an, was hier gemacht wird.
\begin{verbatim}
: dip ( itm quot -- quot | call \ itm )
swap [ swap unpush rot cons \ \ push \ call push continue ]
call/cc
\end{verbatim}
Grundsätzlich sollte man den Einsatz von Continuations vermeiden wann immer möglich; das hat formale Gründe, auf die in Kap.~\ref{Sec:DefSymbols} näher eingegangen wird.
Alternativ kann man den vor der Quotierung stehenden Wert ans Ende der Quotierung anhängen und mit einem Escape-Wort sicherstellen, dass der Wert nicht als zu interpretierendes Wort behandelt wird. Genau das tut die in der Prelude verwendete Definition, siehe oben. Alternative Definitionen sind:
\begin{verbatim}
: dip ( x quot -- x ) swap [ ] cons \ \ push concat call ;
\end{verbatim}
\begin{verbatim}
: dip ( x quot -- x ) reverse \ \ push cons reverse call ;
\end{verbatim}
Die alternativen Definitionen sind ebenso lesbar und einleuchtend wie die in der Prelude verwendete. Eine Messung der Laufzeiten könnte als Kriterium herangezogen werden, um die schnellste Lösung zu wählen. Da \verb|dip| durchaus laufzeitkritisch ist -- es spielt bei den nachfolgenden Kombinatoren eine entscheidende Rolle --, hat z.B.\ die konkatenative Sprache Factor \verb|dip| im Kern seiner VM aufgenommen. Angenommen, \verb|dip| sei als primitives Wort gegeben, dann sind \verb|call| und \verb|rot| definierbar als:
\begin{verbatim}
: call ( quot -- ... ) dup dip drop ;
: rot ( x y z -- y z x ) [ swap ] dip swap ;
\end{verbatim}
Es hängt sehr davon ab, welche Wörter als primitiv angesehen und in einer VM implementiert werden, und welche Wörter dann in Folge "`abgeleitete"' Wörter sind.
\subsection{Erhaltungskombinatoren: \texttt{keep}}
Die \verb|keep|-Kombinatoren rufen die Quotierung auf dem Datastack wie ein \verb|call| auf, sie bewahren (\emph{keep}) jedoch nach dem Aufruf eine Reihe von Daten, die sich "`vor"' der Quotierung und vor dem Aufruf auf dem Datastack befanden. Das Wort \verb|keep| erhält ein Datum, \verb|2keep| zwei Datenwerte und \verb|3keep| drei Datenwerte.
%>> % CALL A QUOTATION AND RESTORE ITEMS ON DATASTACK
%>> % http://docs.factorcode.org/content/article-dip-keep-combinators.html
%>>
\begin{verbatim}
>> : keep ( x quot -- x ) [ dup ] dip dip ;
>> : 2keep ( x y quot -- x y ) [ 2dup ] dip 2dip ;
>> : 3keep ( x y z quot -- x y z ) [ 3dup ] dip 3dip ;
\end{verbatim}
%>>
Die Ausdrucksmittel für die Beschreibung der Stapeleffekte reichen nicht aus, um die Unterschiede zu den \verb|dip|-Kombinatoren hervorzuheben. Die tatsächlichen Auswirkungen auf den Datastack hängen von dem Aufruf der Quotierung ab.
\begin{verbatim}
> clear 2 3 [ + ] 2keep
5 2 3
\end{verbatim}
Beachten Sie, dass die \verb|keep|-Kombinatoren wie die \verb|dip|-Kombinatoren einem regulären Aufbau folgen -- diesmal ohne jegliche Brüche.
Interessant sind in Consize die wechselseitigen Bezüge, die Wörter zueinander haben. Das offenbart innere Strukturen, die andere Programmiersprachen weniger deutlich erkennen lassen. Zum Beispiel könnten \verb|dup|, \verb|2dup| und \verb|3dup| auch über Erhaltungskombinatoren definiert sein.
\begin{verbatim}
: dup ( x -- x x ) [ ] keep ;
: 2dup ( x y -- x y x y ) [ ] 2keep ;
: 3dup ( x y z -- x y z x y z ) [ ] 3keep ;
\end{verbatim}
Andererseits ist \verb|keep| mit \verb|dup| definiert worden, \verb|2keep| mit \verb|2dup| etc. Es ist alles eine Frage, aus welchen Wörtern die Consize-VM besteht. Daraus sind die nicht atomaren Wörter abzuleiten.
Eine alternative Implementierung für die Erhaltungskombinatoren ist:
\begin{verbatim}
: keep ( x quot -- x ) over [ call ] dip ; % see Factor
: 2keep ( x y quot -- x y ) 2over [ call ] 2dip ;
: 3keep ( x y z quot -- x y z ) 3over [ call ] 3dip ;
\end{verbatim}
Beachten Sie, dass \verb|3over| in der Prelude nicht definiert ist.
\subsection{Cleave-Kombinatoren: \texttt{bi}, \texttt{tri}, \texttt{cleave}}
Das Wort \emph{cleave} heißt hier soviel wie "`bewahren"', "`festhalten"', "`teilen"'.
Die \verb|bi|- und \verb|tri|-Kombinatoren wenden zwei bzw.\ drei Quotierungen nacheinander auf den Datastack an und restaurieren ein, zwei oder drei Werte auf dem Datastack vor dem Aufruf der nächsten Quotierung. Im Stapeleffekt sind die Quotierungen mit \verb|p|, \verb|q| und \verb|r| bezeichnet, die restaurierten Werte mit \verb|x|, \verb|y| und \verb|z|.
%>> % CALL 2, 3 QUOTATIONS IN SEQUENCE, RESTORE ITEM(S) FOR NEXT CALL
%>> % http://docs.factorcode.org/content/article-cleave-combinators.html
%>> % "The cleave combinators apply multiple quotations to a single
%>> % value or set of values." [Factor]
%>>
\begin{verbatim}
>> : bi ( x p q -- ) [ keep ] dip call ;
>> : 2bi ( x y p q -- ) [ 2keep ] dip call ;
>> : 3bi ( x y z p q -- ) [ 3keep ] dip call ;
\end{verbatim}
%>>
\begin{verbatim}
>> : tri ( x p q r -- ) [ [ keep ] dip keep ] dip call ;
>> : 2tri ( x y p q r -- ) [ [ 2keep ] dip 2keep ] dip call ;
>> : 3tri ( x y z p q r -- ) [ [ 3keep ] dip 3keep ] dip call ;
\end{verbatim}
%>>
Ein paar wenige Beispiele mögen die Arbeitsweise von \verb|bi|- bzw. \verb|tri|-Kombinatoren veranschaulichen.
\begin{verbatim}
> clear 2 [ 1 + ] [ dup * ] bi
3 4
> [ + ] [ * ] 2bi
7 12
> clear 2 [ 1 + ] [ dup * ] [ 1 - ] tri
3 4 1
\end{verbatim}
Der \verb|cleave|-Kombinator verallgemeinert die \verb|bi|- bzw. \verb|tri|-Kombinatoren. Der \verb|cleave|-Kombinator nimmt beliebige viele Quotierungen als Sequenz entgegen und wendet die Quotierungen nacheinander auf einen (\verb|cleave|), auf zwei (\verb|2cleave|) bzw.\ drei (\verb|3cleave|) Werte auf dem Datastack an; vor jedem Aufruf werden die Werte restauriert. Das Wort \verb|each| ist in Kap.~\ref{Sec:SequenceCombinators} definiert.
\begin{verbatim}
>> : cleave ( x [ p q ... ] -- ) [ keep ] each drop ;
>> : 2cleave ( x y [ p q ... ] -- ) [ 2keep ] each 2drop ;
>> : 3cleave ( x y z [ p q ... ] -- ) [ 3keep ] each 3drop ;
\end{verbatim}
%>>
Das folgende Beispiel ist identisch mit dem vorstehenden \verb|tri|-Beispiel.
\begin{verbatim}
> clear 2 ( [ 1 + ] [ dup * ] [ 1 - ] ) cleave
3 4 1
\end{verbatim}
\subsection{Spread-Kombinatoren: \texttt{bi*}, \texttt{tri*}, \texttt{spread}}
Der \verb|bi*|-Kombinator erwartet zwei Quotierungen (\verb|p| und \verb|q|), der \verb|tri*|-Kombinator drei Quotierungen (\verb|p|, \verb|q| und \verb|r|). Die Quotierungen verarbeiten im Fall von \verb|bi*| und \verb|tri*| jeweils nur einen Wert, bei \verb|2bi*| und \verb|2tri*| jeweils zwei Werte. Die Quotierungen werden auf die Verarbeitung der Stapelwerte verteilt -- \emph{spread} bedeutet soviel wie "`verteilen"', "`spreizen"'.
Im Fall von \verb|bi*| arbeitet \verb|p| auf \verb|x| und \verb|q| auf \verb|y|. Und im Fall von \verb|2bi*| verarbeitet \verb|p| die Werte \verb|w| und \verb|x| und \verb|q| die Werte \verb|y| und \verb|z|.
%>> % CALL 1ST QUOTATION ON 1ST ITEM, 2ND QUOTATION ON 2ND ITEM
%>> % http://docs.factorcode.org/content/article-spread-combinators.html
%>> % "The spread combinators apply multiple quotations to multiple
%>> % values. The asterisk (*) suffixed to these words' names
%>> % signifies that they are spread combinators." [Factor]
%>>
%>> % : bi* ( #X #Y [ @P ] [ @Q ] ==> #X [ @P ] | call \ #Y [ @Q ] call )
%>> % : bi* ( #X #Y [ @P ] [ @Q ] ==> #X | @P \ #Y @Q )
\begin{verbatim}
>> : bi* ( x y p q -- ) [ dip ] dip call ;
>> : 2bi* ( w x y z p q -- ) [ 2dip ] dip call ;
\end{verbatim}
%>>
\begin{verbatim}
> clear 2 3 [ 1 + ] [ dup * ] bi*
3 9
> clear 1 2 3 4 [ + ] [ * ] 2bi*
3 12
\end{verbatim}
Die Kombinatoren \verb|tri*| und \verb|2tri*| arbeiten entsprechend.
%>> % : tri* ( x y z p q r -- ) [ [ 2dip ] dip dip ] dip call ; % Factor
\begin{verbatim}
>> : tri* ( x y z p q r -- ) [ 2dip ] 2dip bi* ;
>> : 2tri* ( u v w x y z p q r -- ) [ 4dip ] 2dip 2bi* ;
\end{verbatim}
%>>
\begin{verbatim}
> clear 4 3 2 [ 1 + ] [ dup * ] [ 1 - ] tri*
5 9 1
> clear 6 5 4 3 2 1 [ + ] [ * ] [ - ] 2tri*
11 12 1
\end{verbatim}
Die Verallgemeinerung der Spread-Kombinatoren \verb|bi*|- und \verb|tri*| bietet das Wort \verb|spread|; es erwartet $n$ Elemente und entsprechend $n$ Quotierungen in einem Stapel. Die $n$-te Quotierung wird auf das $n$-te Element angewendet.
Die Umsetzung des Wortes \verb|spread| geschieht via \verb|SPREAD|, das den notwendigen Code verschachtelter \verb|dip|-Aufrufe für das gewünschte "`Spreading"' erzeugt. Das Wort \verb|reduce| ist ein Sequenzkombinator, siehe Kap.~\ref{Sec:SequenceCombinators}.
\begin{verbatim}
>> : SPREAD ( [ quot1 ... quotn ] -- ... ) % def inspired by Factor
>> ( ) [ swap dup empty?
>> [ drop ]
>> [ [ dip ] rot concat cons ]
>> if ]
>> reduce ;
\end{verbatim}
%>>
Greifen wir das obige Beispiel für \verb|tri*| auf. \verb|SPREAD| erzeugt den benötigten Code, d.h.\ \verb|SPREAD| ist ein Code-Generator. Ein anschließendes \verb|call| bringt den generierten Code zur Ausführung. Das Ergebnis ist mit dem \verb|tri*|-Beispiel identisch.
\begin{verbatim}
> clear 4 3 2 ( [ 1 + ] [ dup * ] [ 1 - ] ) SPREAD
4 3 2 [ [ [ 1 + ] dip dup * ] dip 1 - ]
> call
5 9 1
\end{verbatim}
Damit erklärt sich auch die Umsetzung von \verb|spread|:
\begin{verbatim}
>> : spread ( itm1 ... itmn [ quot1 ... quotn ] -- ... ) SPREAD call ;
\end{verbatim}
%>>
\subsection{Apply-Kombinatoren: \texttt{bi@}, \texttt{tri@}, \texttt{both?}, \texttt{either?}}
\label{Sec:applyCombinators}
Die Apply-Kombinatoren sind "`Anwendungskombinatoren"' (\emph{apply} heißt "`anwenden"'), die wie Spread-Kombinatoren arbeiten, im Gegensatz dazu jedoch nur eine Quotierung erwartet, die entsprechend \verb|dup|liziert wird. Die Definitionen sind selbsterklärend.
%>> % CALL ONE QUOTATION ON MULTIPLE ITEMS
%>> % http://docs.factorcode.org/content/article-apply-combinators.html
%>> % "The apply combinators apply a single quotation to multiple values.
%>> % The at sign (@) suffixed to these words' names signifies that they
%>> % are apply combinators." [Factor]
%>>
\begin{verbatim}
>> : bi@ ( x y quot -- ) dup bi* ;
>> : 2bi@ ( w x y z quot -- ) dup 2bi* ;
>> : tri@ ( x y z quot -- ) dup dup tri* ;
>> : 2tri@ ( u v w x y z quot -- ) dup dup 2tri* ;
\end{verbatim}
%>>
\begin{verbatim}
> clear 3 4 [ dup * ] bi@
9 16
> clear 6 5 4 3 2 1 [ * ] 2tri@
30 12 2
\end{verbatim}
Zwei Beispiele für die Anwendung des \verb|bi@|-Kombinators sind \verb|both?| und \verb|either?|.
\begin{verbatim}
>> : both? ( x y pred -- t/f ) bi@ and ;
>> : either? ( x y pred -- t/f ) bi@ or ;
\end{verbatim}
%>>
\begin{verbatim}
> clear 2 -3 [ 0 > ] both?
f
> 2 -3 [ 0 > ] either?
f t
\end{verbatim}
\section{Sequenzkombinatoren}
\label{Sec:SequenceCombinators}
Sequenzkombinatoren wenden eine Quotierung auf jedes Element einer Sequenz an. Damit stehen Abstraktionen zur Verfügung, die dasselbe erreichen, wofür in anderen Programmiersprachen Schleifenkonstrukte wie "`\verb|for|"' und sogenannte Iteratoren zur Verfügung stehen. In einer funktionalen Sprache wie Consize geht man die Elemente einer Sequenz nicht per Index, sondern einfach der Reihe nach durch.
\subsection{Elemente bearbeiten: \texttt{each}, \texttt{map} und \texttt{reduce}}
Der \verb|each|-Kombinator ist der elementarste der Sequenzkombinatoren, er legt die Ergebnisse der Anwendung der Quotierung auf die einzelnen Elemente schlicht auf dem Datastack ab. Der rekursive Aufruf ist in \emph{tail position}, d.h.\ er ist das letzte Worte am Ende (\emph{tail}) der Quotierung, die für die Rekursion verantwortlich ist. Man spricht auch von \emph{tail recursion}, im Deutschen als "`Endrekursion"' bezeichnet. Sie zeichnet sich dadurch aus, dass die Rekursion nicht zum Anwachsen des Callstacks führt -- das Merkmal von Schleifenkonstrukten in imperativen Programmiersprachen.
%>> % SEQUENCE COMBINATORS
%>> % http://docs.factorcode.org/content/article-sequences-combinators.html
%>>
\begin{verbatim}
>> : each ( seq quot -- ... )
>> swap dup empty?
>> [ 2drop ]
>> [ unpush -rot over [ call ] 2dip each ]
>> if ;
\end{verbatim}
%>>
\begin{verbatim}
> clear ( 1 2 3 4 ) [ dup * ] each
1 4 9 16
\end{verbatim}
Ein einfaches Beispiel für die Verwendung von \verb|each| ist das Entpacken eines Stapel, hier definiert in Form des Wortes \verb|unstack|.
\begin{verbatim}
>> : unstack ( stk -- ... ) ( ) each ;
\end{verbatim}
%>>
\begin{verbatim}
> clear [ x [ y ] z ] unstack
x [ y ] z
\end{verbatim}
Die Varianten \verb|2each| und \verb|3each| erwarten zwei bzw. drei Stapel, greifen dort jeweils das oberste Element ab und rufen damit die Quotierung auf.
\begin{verbatim}
>> : 2each ( stk1 stk2 quot -- ... )
>> \ unstack push [ zip ] dip each ;
>> : 3each ( stk1 stk2 stk3 quot -- ... )
>> \ unstack push [ 3zip ] dip each ;
\end{verbatim}
%>>
Jeweils ein Beispiel illustriere den Gebrauch der Wörter.
\begin{verbatim}
> clear ( 1 2 3 ) ( 4 5 6 ) [ + ] 2each
5 7 9
> clear ( 1 2 ) ( 3 4 ) ( 5 6 ) [ + * ] 3each
8 20
\end{verbatim}
Das Wort \verb|map| fasst im Gegensatz zu \verb|each| die Ergebnisse in einer Sequenz zusammen.
\begin{verbatim}
>> : map ( seq quot -- seq' )
>> [ push ] concat ( ) -rot each reverse ;
\end{verbatim}
Die Definition von \verb|map| erweitert das durch die Quotierung dargestellte Programm um ein \verb|push|, das die einzelnen Ergebnis auf einen per \verb|( )| und \verb|-rot| bereit gestellten Stapel ablegt. Am Schluss stellt \verb|reverse| die korrekte Reihenfolge her.
\begin{verbatim}
> clear ( 1 2 3 4 ) [ dup * ] map
[ 1 4 9 16 ]
\end{verbatim}
Das Wort \verb|reduce| aggregiert die Werte einer Sequenz zu einem Einzelwert bezüglicher einer Operation, die durch eine Quotierung repräsentiert wird. Die Annahme ist zum einen, dass die Quotierung eine zweiwertige Operation ist, d.h. dass sie zwei Werte auf dem Datastack erwartet. Zum anderen ist \verb|identity| das neutrale Element dieser Operation.
\begin{verbatim}
>> : reduce ( seq identity quot -- res ) swapd each ;
\end{verbatim}
%>>
Ein paar Beispiele: Das neutrale Element der Addition ist \verb|0|, das der Multiplikation \verb|1| und das der Konkatenation \verb|( )|.
\begin{verbatim}
> clear ( 1 4 9 16 ) 0 [ + ] reduce
30
> clear ( ) 0 [ + ] reduce
0
> clear ( 2 3 4 ) 1 [ * ] reduce
24
> clear ( [ 1 ] [ 2 ] [ 3 4 ] ) ( ) [ concat ] reduce
[ 1 2 3 4 ]
\end{verbatim}
Die Beispiele motivieren drei nützlichen Abstraktionen: \verb|sum| zur Summenbildung, \verb|prod| zur Produktbildung und \verb|cat| zur Verschmelzung mehrerer Sequenzen.
\begin{verbatim}
>> : sum ( [ x ... z ] -- sum ) 0 [ + ] reduce ;
>> : prod ( [ x ... z ] -- prod ) 1 [ * ] reduce ;
>> : cat ( [ seq1 ... seq2 ] -- seq ) ( ) [ concat ] reduce ;
\end{verbatim}
%>>
Eine alternative, endrekursive (\emph{tail recursive}) Definition für \verb|size| (siehe Kap.~\ref{Sec:Friends}) ist:
\begin{verbatim}
: size ( seq -- n ) 0 [ drop 1 + ] reduce ;
\end{verbatim}
Die Wörter \verb|map| und \verb|reduce| sind ein besonderes Paar, da sie ein gewichtiges Prinzip verkörpern, das als Idee z.B.\ die Konzeption der Sprache \href{http://de.wikipedia.org/wiki/MapReduce}{MapReduce} geprägt hat: Mit \verb|map| kann eine Operation in Form einer Quotierung im Grunde parallel auf den einzelnen Daten einer Sequenz arbeiten, mit \verb|reduce| werden die Einzelergebnisse zusammengetragen und ausgewertet. Nach diesem Prinzip verarbeitet Google mit MapReduce die riesigen Datenmengen, die bei der Erfassung von Webseiten und anderen Datenquellen anfallen. Die Berechnung verteilt Google auf Rechencluster von mehreren tausend Rechnern.
Auch wenn sich Programme sehr kompakt mit \verb|map| und \verb|reduce| darstellen lassen, nicht immer sind diese Wörter die ideale Wahl. Die Definitionen von \verb|any?| und \verb|all?| haben einen entscheidenden Nachteil: Sie laufen Gefahr zuviel des Guten zu tun. Bei \verb|any?| ist der Abbruch sinnvoll, sobald die Anwendung des Prädikats auf ein Element erfolgreich ist -- Folgewerte müssen per \verb|map| nicht mehr untersucht werden. Ebenso kann \verb|all?| abbrechen, sobald ein Prädikatstest fehl schlägt.
\begin{verbatim}
>> : any? ( seq pred -- t/f ) map f [ or ] reduce ;
>> : all? ( seq pred -- t/f ) map t [ and ] reduce ;
\end{verbatim}
%>>
\begin{verbatim}
> clear ( 1 3 -4 5 0 7 2 ) [ 0 <= ] any?
t
> clear ( 1 3 -4 5 0 7 2 ) [ 0 >= ] all?
f
\end{verbatim}
Natürlich kann man \verb|any?| und \verb|all?| entsprechend anders rekursiv programmieren. Doch die konzeptuelle Kürze mit \verb|map| und \verb|reduce| besticht! Es gibt funktionale Sprachen, wie z.B. \href{http://de.wikipedia.org/wiki/Haskell_(Programmiersprache)}{Haskell}, die auf eine andere Strategie zur \href{http://de.wikipedia.org/wiki/Auswertung_(Informatik)}{Auswertung} von Programmausdrücken zurückgreifen. Mit einer verzögerten Auswertung (\href{http://en.wikipedia.org/wiki/Lazy_evaluation}{\emph{lazy evaluation}}) werden überflüssige Rechenschritte vermieden, die konzeptuelle Kürze aber beibehalten.\footnote{Trivial sind solche Überlegungen nicht, wie der Beitrag "`\href{http://heise.de/-1871934}{Reducers in Clojure 1.5}"' von Stefan Kamphausen auf heise-Developer aufzeigt.}
Zur Arbeit mit zwei oder drei Sequenzen stehen die folgenden Varianten von \verb|map| und \verb|reduce| bereit:
\begin{verbatim}
>> : 2map ( seq1 seq2 quot -- seq ) [ zip ] dip \ unstack push map ;
>> : 3map ( seq1 seq2 seq3 quot -- seq ) [ 3zip ] dip \ unstack push map ;
>> : 2reduce ( seq1 seq2 identity quot -- res )
>> [ zip ] 2dip \ unstack push reduce ;
>> : 3reduce ( seq1 seq2 seq3 identity quot -- res )
>> [ 3zip ] 2dip \ unstack push reduce ;
\end{verbatim}
%>>
\subsection{Sequenzverschnitte: \texttt{zip}}
Oft ist der Wunsch, die Elemente von zwei oder mehr Stapeln zusammen bearbeiten möchte. Eine Lösung dazu bietet \verb|zip|, das im Reißverschlußverfahren die jeweils obersten Elemente zweier Stapel zusammenfasst und aus den Paaren einen neuen Stapel erstellt.
\begin{verbatim}
>> : zip ( stk1 stk2 -- stk )
>> 2dup [ empty? ] bi@ or
>> [ 2drop ( ) ]
>> [ unpush ( ) cons rot
>> unpush rot cons -rot swap zip cons ]
>> if ;
\end{verbatim}
%>>
Am einfachsten ist \verb|zip| am Beispiel zu verstehen.
\begin{verbatim}
> clear ( 1 2 3 ) ( 4 5 6 ) zip
[ [ 1 4 ] [ 2 5 ] [ 3 6 ] ]
\end{verbatim}
Sind die beiden Stapel nicht gleich in der Anzahl ihrer Elemente, endet der Reißverschluß mit dem letzten Element des kürzeren Stapels.
\begin{verbatim}
> clear ( 1 2 3 4 ) ( 5 6 ) zip
[ [ 1 5 ] [ 2 6 ] ]
\end{verbatim}
Die Wörter \verb|3zip| und \verb|4zip| bringen die Elemente von drei bzw. vier Stapeln zusammen.
\begin{verbatim}
>> : 3zip ( stk1 stk2 stk3 -- stk ) zip zip [ unstack cons ] map ;
>> : 4zip ( stk1 stk2 stk3 stk4 -- stk ) 3zip zip [ unstack cons ] map ;
\end{verbatim}
%>>
\begin{verbatim}
> clear ( 1 2 ) ( 3 4 ) ( 5 6 ) 3zip
[ [ 1 3 5 ] [ 2 4 6 ] ]
> clear ( 1 2 ) ( 3 4 ) ( 5 6 ) ( 7 8 ) 4zip
[ [ 1 3 5 7 ] [ 2 4 6 8 ] ]
\end{verbatim}
\subsection{Aussortieren: \texttt{filter}, \texttt{remove}}
Das Wort \verb|filter| nutzt die Quotierung als Prädikat, um nur die Elemente aus der Sequenz herauszufiltern, die den Prädikatstest bestehen. Eine Quotierung heißt Prädikat, wenn sie als Ergebnis ihrer Ausführung entweder ein \emph{true} oder \emph{false} in Form von \verb|t| bzw.\ \verb|f| auf dem Datastack ablegt.
\begin{verbatim}
>> : filter ( seq pred -- seq' ) % pred is a quotation
>> ( ) -rot [ keep and [ push ] when* ] cons each reverse ;
\end{verbatim}
%>>
\begin{verbatim}
> clear ( 1 3 -4 5 0 7 2 ) [ 0 > ] filter
[ 1 3 5 7 2 ]
\end{verbatim}
Das Wort \verb|remove| macht das Gegenteil von \verb|filter|: Es fasst die von \verb|filter| verworfenen Elemente zusammen. Die Definition macht genau das, indem es das Prädikatsergebnis mit \verb|not| negiert.
\begin{verbatim}
>> : remove ( seq quot -- seq' ) [ not ] concat filter ;
\end{verbatim}
%>>
\begin{verbatim}
> clear ( 1 3 -4 5 0 7 2 ) [ 0 > ] remove
[ -4 0 ]
\end{verbatim}
\section{Wiederholungskombinatoren}
%>> % LOOPING COMBINATORS
%>> %
%>> % http://docs.factorcode.org/content/article-looping-combinators.html
%>>
In einer funktionalen Sprache gibt es einzig die Rekursion als Mittel, um die Idee der Wiederholungen eines Vorgangs auszudrücken. Sequenz- wie auch Wiederholungskombinatoren abstrahieren gängige Muster der Wiederholung für verschiedene Zwecke und machen den Programmcode leichter lesbar.
\subsection{Abbruch via Prädikat: \texttt{loop}, \texttt{do}, \texttt{while}, \texttt{until}}
Die Wörter \verb|while| und \verb|until| abstrahieren ein gängiges Rekursionsschema: Wiederhole den Aufruf der Quotierung solange, wie das Prädikat ein \emph{true} (\verb|while|) bzw. ein \emph{false} (\verb|until|) zurück liefert. Beide Abstraktionen lassen sich auf das Wort \verb|loop| zurückführen.
\begin{verbatim}
>> : loop ( pred -- ... ) [ call ] keep [ loop ] curry when ;
>> : do ( pred quot -- pred quot ) dup 2dip ;
>> : while ( pred quot -- ... ) swap do concat [ loop ] curry when ;
>> : until ( pred quot -- ... ) [ [ not ] concat ] dip while ;
\end{verbatim}
%>>
Die Beispiele zeigen den Gebrauch der Wiederholungskombinatoren am Beispiel der Berechnung der Fakultät von \verb|4|.
\begin{verbatim}
> clear 1 4 [ [ * ] keep 1 - dup 0 > ] loop drop
24
> clear 4 1 [ over 0 > ] [ over * [ 1 - ] dip ] while nip
24
> clear 4 1 [ over 0 == ] [ over * [ 1 - ] dip ] until nip
24
\end{verbatim}
Mit \verb|do while| kann der Aufruf der Quotierung einmal vor der Abarbeitung durch \verb|while| erzwungen werden.
%>> : [a,b] ( a b -- seq )
%>> ( ) -rot [ 2dup <= ] [ rot over push -rot 1 - ] while 2drop ;
%>> : [a,b) ( a b -- seq ) 1 - [a,b] ;
%>>
\subsection{Abbruch als Fixpunkt: \texttt{X}, \texttt{Y}}
In der Regel wird die Rekursion dadurch hergestellt, dass ein Wort sich selbst im Definitionrumpf erwähnt und aufruft. Das ist die benamte Rekursion. Aber wie ist es um die anonyme, unbenamte Rekursion bestellt? Wie kann man ohne den Selbstaufruf eines Wortes Rekursion erzeugen?
Den Schlüssel zur Antwort liefert der \verb|X|-Kombinator. Eine Quotierung dupliziert sich vor ihrem Aufruf, womit eine Programmkopie für einen Wiederholungsaufruf auf dem Stapel bereit liegt.
\begin{verbatim}
>> : X ( quot -- ... ) dup call ;
\end{verbatim}
%>>
Der \href{http://de.wikipedia.org/wiki/Lambda-Kalk\%C3\%BCl}{Lambda-Kalkül},
die Basis vieler funktionaler Programmiersprachen, setzt die anonyme Rekursion mit dem Fixpunkt-Kombinator um, auch Y-Kombinator bezeichnet. Der Fixpunkt-Kombinator wiederholt die Anwendung einer Funktion auf einen Funktionswert solange, bis Eingangs- und Ausgangswert identisch sind -- der \href{http://de.wikipedia.org/wiki/Fixpunkt_(Mathematik)}{Fixpunkt} ist erreicht.
In Consize drückt sich der Y-Kombinator wie folgt aus; der X-Kombinator sorgt dafür, dass die Rekursion anonym bleibt.
\begin{verbatim}
>> : Y ( val quot -- res )
>> [ [ [ call ] 2keep -rot dupd equal? ] dip
>> swap [ drop nip ] [ swapd X ] if ] X ;
\end{verbatim}
%>>
Die Fakultät von \verb|4| lässt sich mit dem Y-Kombinator ohne jegliche namentliche Wort-Rekursion berechnen.
\begin{verbatim}
> clear
> 4 1 [ swap dup 0 equal? [ drop 1 ] when [ * ] keep 1 - swap ] Y nip
24
\end{verbatim}
% 1 6 [ dup 0 equal? [ drop 1 ] when [ * ] keep 1 - ] Y drop
% 6 1 [ swap dup 0 equal? [ drop 1 ] when [ * ] keep 1 - swap ] Y nip
% \begin{verbatim}
% >> : fix ( val quot -- res ) [ keep dupd equal? not ] cons loop ;
% >> : fix ( val quot -- res ) % named recursion
% >> 2dup call rot over equal? [ nip ] [ swap fix ] if ;
% \end{verbatim}
Man könnte also durchaus Programme in Consize schreiben, selbst wenn das Wörterbuch fixiert wäre und -- da es dann kein \verb|set-dict| gäbe -- und es unmöglich wäre, neue Wörter im Wörterbuch mit ihren Quotierungen zu hinterlegen. Man müsste alle nicht primitiven Wörter selber händisch auflösen. Das ist mehr als unpraktisch, zeigt aber eines: Ein Rechenformalismus braucht keine benamten Abstraktionen, auch sind benamte Abstraktionen keine Notwendigkeit, um Programmieren zu können. Wenn jemand benamte Abstraktionen braucht, so sind es wir Menschen. Für uns ist eine Programmiersprache ohne benamte Abstraktionen schlicht unbrauchbar, unsere intellektuellen Fähigkeiten sind zu begrenzt. Was andererseits betont, wie wichtig die Wahl eines guten Namens für eine Abstraktion ist. Da geht es um nichts anderes als die Kommunikation von Mensch zu Mensch.
\section{Kompositionskombinatoren: \texttt{curry}}
%>> % COMPOSITIONAL COMBINATORS
%>> %
%>> % http://docs.factorcode.org/content/article-compositional-combinators.html
Zwei Kombinatoren zur Komposition von Programmen bzw. Funktionen sind bereits Bestandteil der Consize-VM. Mit \verb|concat| lassen sich zwei Quotierungen zu einer zusammenfassen. Die Komposition zweier Funktionen erfolgt mit \verb|compose|.
% [ call ] dip call == concat call