-
Notifications
You must be signed in to change notification settings - Fork 2
/
zh_fiftbase.tex
2205 lines (2032 loc) · 208 KB
/
zh_fiftbase.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
\documentclass[12pt,oneside]{article}
\usepackage{xeCJK}
\setCJKmainfont{SimSun}
\usepackage[T1]{fontenc}
%\usepackage{euler}
\usepackage{amssymb, amsmath, amsfonts, stmaryrd}
\usepackage[mathscr]{euscript}
\usepackage{mathrsfs}
\usepackage{theorem}
\usepackage[english]{babel}
\usepackage{bm}
\usepackage[all]{xy}
\usepackage{array}
\usepackage{multirow}
%\usepackage{chngcntr}
%\CompileMatrices
\usepackage[bookmarks=false,pdfauthor={Nikolai Durov},pdftitle={Fift: A Brief Introduction}]{hyperref}
\usepackage{fancyhdr}
\usepackage{caption}
%
\setlength{\headheight}{15.2pt}
\pagestyle{fancy}
\renewcommand{\headrulewidth}{0.5pt}
%
\def\makepoint#1{\medbreak\noindent{\bf #1.\ }}
\def\zeropoint{\setcounter{subsection}{-1}}
\def\zerosubpoint{\setcounter{subsubsection}{-1}}
\def\nxpoint{\refstepcounter{subsection}%
\smallbreak\makepoint{\thesubsection}}
\def\nxsubpoint{\refstepcounter{subsubsection}%
\smallbreak\makepoint{\thesubsubsection}}
\def\nxsubsubpoint{\refstepcounter{paragraph}%
\makepoint{\paragraph}}
%\setcounter{secnumdepth}{4}
%\counterwithin{paragraph}{subsubsection}
\def\refpoint#1{{\rm\textbf{\ref{#1}}}}
\let\ptref=\refpoint
\def\embt(#1.){\textbf{#1.}}
\def\embtx(#1){\textbf{#1}}
\def\emb#1{\textbf{#1.}}
\long\def\nodo#1{}
%
%\def\markbothsame#1{\markboth{#1}{#1}}
\fancyhf{}
\fancyfoot[C]{\thepage}
\def\markbothsame#1{\fancyhead[C]{#1}}
\def\mysection#1{\section{#1}\fancyhead[C]{\textsc{Chapter \textbf{\thesection.} #1}}}
\def\mysubsection#1{\subsection{#1}\fancyhead[C]{\small{\textsc{\textrm{\thesubsection.} #1}}}}
\def\myappendix#1{\section{#1}\fancyhead[C]{\textsc{Appendix \textbf{\thesection.} #1}}}
%
\let\tp=\textit
\let\vr=\textit
\def\workchainid{\vr{workchain\_id\/}}
\def\shardpfx{\vr{shard\_prefix}}
\def\accountid{\vr{account\_id\/}}
\def\currencyid{\vr{currency\_id\/}}
\def\uint{\tp{uint}}
\def\opsc#1{\operatorname{\textsc{#1}}}
\def\CellRepr{\opsc{CellRepr}}
\def\blkseqno{\opsc{blk-seqno}}
\def\blkprev{\opsc{blk-prev}}
\def\blkhash{\opsc{blk-hash}}
\def\Hash{\opsc{Hash}}
\def\Sha{\opsc{sha256}}
\def\SHA#1{\opsc{sha#1}}
\def\Int{\opsc{int}}
\def\height{\opsc{height}}
\def\len{\opsc{len}}
\def\leaf{\opsc{Leaf}}
\def\node{\opsc{Node}}
\def\Seqno{\opsc{SeqNo}}
\def\LT{\opsc{Lt}}
\def\NextHop{\opsc{NextHop}}
\def\root{\opsc{Root}}
\def\emptyroot{\opsc{EmptyRoot}}
\def\code{\opsc{code}}
\def\Ping{\opsc{Ping}}
\def\Store{\opsc{Store}}
\def\FindNode{\opsc{Find\_Node}}
\def\FindValue{\opsc{Find\_Value}}
\def\Bytes{\tp{Bytes}}
\def\Transaction{\tp{Transaction}}
\def\Account{\tp{Account}}
\def\State{\tp{State}}
\def\Maybe{\opsc{Maybe}}
\def\List{\opsc{List}}
\def\Block{\tp{Block}}
\def\Blockchain{\tp{Blockchain}}
\def\isValidBc{\tp{isValidBc}}
\def\evtrans{\vr{ev\_trans}}
\def\evblock{\vr{ev\_block}}
\def\Hashmap{\tp{Hashmap}}
\def\HashmapE{\tp{HashmapE}}
\def\Type{\tp{Type}}
\def\nat{\tp{nat\/}}
\def\hget{\vr{hget\/}}
\def\bbB{{\mathbb{B}}}
\def\bbP{{\mathbb{P}}}
\def\bbF{{\mathbb{F}}}
\def\bbZ{{\mathbb{Z}}}
\def\st#1{{\mathbf{#1}}}
\def\sgn{\operatorname{sgn}}
\def\charact{\operatorname{char}}
\def\caret{\^{}}
\def\cF{\mathscr{F}}
%
\hfuzz=0.8pt
\title{Fift: A Brief Introduction}
\author{Nikolai Durov\\
TL: Dr Awesome Doge}
\begin{document}
%\pagestyle{myheadings}
\maketitle
\begin{abstract}
本文旨在簡要描述 Fift,一種專門設計用於創建和管理 TON 區塊鏈智能合約的新型編程語言,以及其用於與 TON 虛擬機~\cite{TVM} 和 TON 區塊鏈~\cite{TBC} 進行交互的功能。
\end{abstract}
\section*{Introduction}
\markbothsame{Introduction}
本文提供了對 Fift 的簡要描述。Fift 是一種基於堆棧的通用編程語言,優化了創建、調試和管理 TON 區塊鏈智能合約的功能。
Fift 是專門設計用於與 TON 虛擬機(TON VM 或 TVM)~\cite{TVM} 和 TON 區塊鏈~\cite{TBC} 交互的語言。它提供原生支持 257 位整數算術和與 TVM 共享的 TVM 單元格操作,以及一個基於 Ed25519 的加密系統的接口,該加密系統被 TON 區塊鏈所使用。Fift 分發版本還包括一個用於 TVM 代碼的宏組合器,可用於編寫新的智能合約。
作為一種基於堆棧的語言,Fift 有點像 Forth。由於本文篇幅簡短,了解 Forth 的一些知識可能有助於理解 Fift。\footnote{有一些良好的 Forth 入門書籍,我們可以推薦~\cite{Brodie}。}然而,這兩種語言之間存在重大差異。例如,Fift 強制執行運行時類型檢查,並將不同類型(不僅僅是整數)的值保存在其堆棧中。
附錄~\ref{app:words} 中列出了 Fift 中定義的單詞(內置函數或原語),以及它們的簡要描述。
請注意,本文所描述的 Fift 目前版本是一個初步測試版本;未來可能會有一些細微的變化。
\clearpage
\tableofcontents
\clearpage
\mysection{Overview}\label{sect:overview}
Fift is a simple stack-based programming language designed for testing and debugging the TON Virtual Machine \cite{TVM} and the TON Blockchain \cite{TBC}, but potentially useful for other purposes as well. When Fift is invoked (usually by executing a binary file called {\tt fift}), it either reads, parses, and interprets one or several source files indicated in the command line, or enters the interactive mode and interprets Fift commands read and parsed from the standard input. There is also a ``script mode'', activated by command line switch {\tt -s}, in which all command line arguments except the first one are passed to the Fift program by means of the variables {\tt \$$n$} and {\tt \$\#}. In this way, Fift can be used both for interactive experimentation and debugging as well as for writing simple scripts.
All data manipulated by Fift is kept in a (LIFO) stack. Each stack entry is supplemented by a {\em type tag}, which unambiguously determines the type of the value kept in the corresponding stack entry. The types of values supported by Fift include {\em Integer\/} (representing signed 257-bit integers), {\em Cell\/} (representing a TVM cell, which consists of up to 1023 data bits and up to four references to other cells as explained in \cite{TVM}), {\em Slice\/} (a partial view of a {\em Cell\/} used for parsing cells), and {\em Builder\/} (used for building new cells). These data types (and their implementations) are shared with TVM~\cite{TVM}, and can be safely passed from the Fift stack to the TVM stack and back when necessary (e.g., when TVM is invoked from Fift by using a Fift primitive such as {\tt runvmcode}).
In addition to the data types shared with TVM, Fift introduces some unique data types, such as {\em Bytes\/} (arbitrary byte sequences), {\em String\/} (UTF-8 strings), {\em WordList\/}, and {\em WordDef\/} (used by Fift to create new ``words'' and manipulate their definitions). In fact, Fift can be extended to manipulate arbitrary ``objects'' (represented by the generic type {\em Object}), provided they are derived from C++ class {\tt td::CntObject} in the current implementation.
Fift source files and libraries are usually kept in text files with the suffix {\tt .fif}. A search path for libraries and included files is passed to the Fift executable either in a {\tt -I} command line argument or in the {\tt FIFTPATH} environment variable. If neither is set, the default library search path {\tt /usr/lib/fift} is used.
On startup, the standard Fift library is read from the file {\tt Fift.fif} before interpreting any other sources. It must be present in the library search path, otherwise Fift execution will fail.
A fundamental Fift data structure is its global {\em dictionary}, containing {\em words}---or, more precisely, {\em word definitions\/}---that correspond both to built-in primitives and functions and to user-defined functions.\footnote{Fift words are typically shorter than functions or subroutines of other programming languages. A nice discussion and some guidelines (for Forth words) may be found in~\cite{Brodie2}.} A word can be executed in Fift simply by typing its name (a UTF-8 string without space characters) in interactive mode. When Fift starts up, some words ({\em primitives\/}) are already defined (by some C++ code in the current implementation); other words are defined in the standard library {\tt Fift.fif}. After that, the user may extend the dictionary by defining new words or redefining old ones.
The dictionary is supposed to be split into several {\em vocabularies}, or {\em name\-spaces}; however, namespaces are not implemented yet, so all words are currently defined in the same global namespace.
The Fift parser for input source files and for the standard input (in the interactive mode) is rather simple: the input is read line-by-line, then blank characters are skipped, and the longest prefix of the remaining line that is (the name of) a dictionary word is detected and removed from the input line.\footnote{Notice that in contrast to Forth, Fift word names are case-sensitive: {\tt dup} and {\tt DUP} are distinct words.} After that, the word thus found is executed, and the process repeats until the end of the line. When the input line is exhausted, a subsequent line is read from the current input file or the standard input.
In order to be detected, most words require a blank character or an end-of-line immediately after them; this is reflected by appending a space to their names in the dictionary. Other words, called {\em prefix words}, do not require a blank character immediately after them.
If no word is found, the string consisting of the first remaining characters of the input line until the next blank or end-of-line character is interpreted as an {\em Integer\/} and pushed into the stack. For instance, if we invoke Fift, type {\tt 2 3 + .} (and press Enter), Fift first pushes an {\em Integer\/} constant equal to $2$ into its stack, followed by another integer constant equal to $3$. After that, the built-in primitive ``{\tt +}'' is parsed and found in the dictionary; when invoked, it takes the two topmost elements from the stack and replaces them with their sum ($5$ in our example). Finally, ``{\tt .}'' is a primitive that prints the decimal representation of the top-of-stack {\em Integer}, followed by a space. As a result, we observe ``{\tt 5 ok}'' printed by the Fift interpreter into the standard output. The string ``{\tt ok}'' is printed by the interpreter whenever it finishes interpreting a line read from the standard input in the interactive mode.
A list of built-in words may be found in Appendix~\ref{app:words}.
\mysection{Fift basics}
This chapter provides an introduction into the basic features of the Fift programming language. The discussion is informal and incomplete at first, but gradually becomes more formal and more precise. In some cases, later chapters and Appendix~\ref{app:words} provide more details about the words first mentioned in this chapter; similarly, some tricks that will be dutifully explained in later chapters are already used here where appropriate.
\mysubsection{List of Fift stack value types}\label{p:stack.types}
Currently, the values of the following data types can be kept in a Fift stack:
\begin{itemize}
\item {\em Integer\/} --- A signed 257-bit integer. Usually denoted by $x$, $y$, or $z$ in the stack notation (when the stack effect of a Fift word is described).
\item {\em Cell\/} --- A TVM cell, consisting of up to 1023 data bits and up to 4 references to other cells (cf.~\cite{TVM}). Usually denoted by~$c$ or its variants, such as $c'$ or $c_2$.
\item {\em Slice\/} --- A partial view of a TVM cell, used for parsing data from {\em Cell\/}s. Usually denoted by~$s$.
\item {\em Builder\/} --- A partially built {\em Cell}, containing up to 1023 data bits and up to four references; can be used to create new {\em Cell\/}s. Usually denoted by~$b$.
\item {\em Null\/} --- A type with exactly one ``null'' value. Used to initialize new {\em Box\/}es. Usually denoted by~$\bot$.
\item {\em Tuple\/} --- An ordered collection of values of any of these types (not necessarily the same); can be used to represent values of arbitrary algebraic data types and Lisp-style lists.
\item {\em String\/} --- A (usually printable) UTF-8 string. Usually denoted by~$S$.
\item {\em Bytes\/} --- An arbitrary sequence of 8-bit bytes, typically used to represent binary data. Usually denoted by~$B$.
\item {\em WordList\/} --- A (partially created) list of word references, used for creating new Fift word definitions. Usually denoted by~$l$.
\item {\em WordDef\/} --- An execution token, usually representing the definition of an existing Fift word. Usually denoted by~$e$.
\item {\em Box\/} --- A location in memory that can be used to store one stack value. Usually denoted by~$p$.
\item {\em Atom\/} --- A simple entity uniquely identified by its name, a string. Can be used to represent identifiers, labels, operation names, tags, and stack markers. Usually denoted by~$a$.
\item {\em Object\/} --- An arbitrary C++ object of any class derived from base class {\tt td::CntObject}; may be used by Fift extensions to manipulate other data types and interface with other C++ libraries.
\end{itemize}
The first six types listed above are shared with TVM; the remainder are Fift-specific. Notice that not all TVM stack types are present in Fift. For instance, the TVM {\em Continuation\/} type is not explicitly recognized by Fift; if a value of this type ends up in a Fift stack, it is manipulated as a generic {\em Object}.
\mysubsection{Comments}\label{p:comments}
Fift recognizes two kinds of comments: ``{\tt // }'' (which must be followed by a space) opens a single-line comment until the end of the line, and {\tt /*} defines a multi-line comment until {\tt */}. Both words {\tt //} and {\tt /*} are defined in the standard Fift library ({\tt Fift.fif}).
\mysubsection{Terminating Fift}\label{p:exit.fift}
The word {\tt bye} terminates the Fift interpreter with a zero exit code. If a non-zero exit code is required (for instance, in Fift scripts), one can use word {\tt halt}, which terminates Fift with the given exit code (passed as an {\em Integer\/} at the top of the stack). In contrast, {\tt quit} does not quit to the operating system, but rather exits to the top level of the Fift interpreter.
\mysubsection{Simple integer arithmetic}\label{p:arith.op}
When Fift encounters a word that is absent from the dictionary, but which can be interpreted as an integer constant (or ``literal''), its value is pushed into the stack (as explained in~\ptref{p:int.lit} in more detail). Apart from that, several integer arithmetic primitives are defined:
\begin{itemize}
\item {\tt +} ($x$ $y$ -- $x+y$), replaces two {\em Integer\/}s $x$ and $y$ passed at the top of the stack with their sum $x+y$. All deeper stack elements remain intact. If either $x$ or $y$ is not an {\em Integer}, or if the sum does not fit into a signed 257-bit {\em Integer}, an exception is thrown.
\item {\tt -} ($x$ $y$ -- $x-y$), computes the difference $x-y$ of two {\em Integer\/}s $x$ and $y$. Notice that the first argument $x$ is the second entry from the top of the stack, while the second argument $y$ is taken from the top of the stack.
\item {\tt negate} ($x$ -- $-x$), changes the sign of an {\em Integer}.
\item {\tt *} ($x$ $y$ -- $xy$), computes the product $xy$ of two {\em Integer\/}s $x$ and $y$.
\item {\tt /} ($x$ $y$ -- $q:=\lfloor x/y\rfloor$), computes the floor-rounded quotient $\lfloor x/y\rfloor$ of two {\em Integer\/}s.
\item {\tt mod} ($x$ $y$ -- $r:=x\bmod y$), computes the remainder $x\bmod y=x-y\cdot\lfloor x/y\rfloor$ of division of $x$ by $y$.
\item {\tt /mod} ($x$ $y$ -- $q$ $r$), computes both the quotient and the remainder.
\item {\tt /c}, {\tt /r} ($x$ $y$ -- $q$), division words similar to {\tt /}, but using ceiling rounding ($q:=\lceil x/y\rceil$) and nearest-integer rounding ($q:=\lfloor 1/2+x/y\rfloor$), respectively.
\item {\tt /cmod}, {\tt /rmod} ($x$ $y$ -- $q$ $r:=x-qy$), division words similar to {\tt /mod}, but using ceiling or nearest-integer rounding.
\item {\tt <{}<} ($x$ $y$ -- $x\cdot 2^y$), computes an arithmetic left shift of binary number $x$ by $y\geq0$ positions, yielding $x\cdot 2^y$.
\item {\tt >{}>} ($x$ $y$ -- $q:=\lfloor x\cdot 2^{-y}\rfloor$), computes an arithmetic right shift by $y\geq0$ positions.
\item {\tt >{}>c}, {\tt >{}>r} ($x$ $y$ -- $q$), similar to {\tt >{}>}, but using ceiling or nearest-integer rounding.
\item {\tt and}, {\tt or}, {\tt xor} ($x$ $y$ -- $x\oplus y$), compute the bitwise AND, OR, or XOR of two {\em Integer\/}s.
\item {\tt not} ($x$ -- $-1-x$), bitwise complement of an {\em Integer}.
\item {\tt */} ($x$ $y$ $z$ -- $\lfloor xy/z\rfloor$), ``multiply-then-divide'': multiplies two integers $x$ and $y$ producing a 513-bit intermediate result, then divides the product by $z$.
\item {\tt */mod} ($x$ $y$ $z$ -- $q$ $r$), similar to {\tt */}, but computes both the quotient and the remainder.
\item {\tt */c}, {\tt */r} ($x$ $y$ $z$ -- $q$), {\tt */cmod}, {\tt */rmod} ($x$ $y$ $z$ -- $q$ $r$), similar to {\tt */} or {\tt */mod}, but using ceiling or nearest-integer rounding.
\item {\tt *>{}>}, {\tt *>{}>c}, {\tt *>{}>r} ($x$ $y$ $z$ -- $q$), similar to {\tt */} and its variants, but with division replaced with a right shift. Compute $q=xy/2^z$ rounded in the indicated fashion (floor, ceiling, or nearest integer).
\item {\tt <{}</}, {\tt <{}</c}, {\tt <{}</r} ($x$ $y$ $z$ -- $q$), similar to {\tt */}, but with multiplication replaced with a left shift. Compute $q=2^zx/y$ rounded in the indicated fashion (notice the different order of arguments $y$ and $z$ compared to {\tt */}).
\end{itemize}
In addition, the word ``{\tt .}'' may be used to print the decimal representation of an {\em Integer\/} passed at the top of the stack (followed by a single space), and ``{\tt x.}'' prints the hexadecimal representation of the top-of-stack integer. The integer is removed from the stack afterwards.
The above primitives can be employed to use the Fift interpreter in interactive mode as a simple calculator for arithmetic expressions represented in reverse Polish notation (with operation symbols after the operands). For instance,
\begin{verbatim}
7 4 - .
\end{verbatim}
computes $7-4=3$ and prints ``{\tt 3 ok}'', and
\begin{verbatim}
2 3 4 * + .
2 3 + 4 * .
\end{verbatim}
computes $2+3\cdot 4=14$ and $(2+3)\cdot 4=20$, and prints ``{\tt 14 20 ok}''.
\mysubsection{Stack manipulation words}\label{p:stack.ops}
Stack manipulation words rearrange one or several values near the top of the stack, regardless of their types, and leave all deeper stack values intact. Some of the most often used stack manipulation words are listed below:
\begin{itemize}
\item {\tt dup} ($x$ -- $x$ $x$), duplicates the top-of-stack entry. If the stack is empty, throws an exception.\footnote{Notice that Fift word names are case-sensitive, so one cannot type {\tt DUP} instead of {\tt dup}.}
\item {\tt drop} ($x$ -- ), removes the top-of-stack entry.
\item {\tt swap} ($x$ $y$ -- $y$ $x$), interchanges the two topmost stack entries.
\item {\tt rot} ($x$ $y$ $z$ -- $y$ $z$ $x$), rotates the three topmost stack entries.
\item {\tt -rot} ($x$ $y$ $z$ -- $z$ $x$ $y$), rotates the three topmost stack entries in the opposite direction. Equivalent to {\tt rot rot}.
\item {\tt over} ($x$ $y$ -- $x$ $y$ $x$), creates a copy of the second stack entry from the top over the top-of-stack entry.
\item {\tt tuck} ($x$ $y$ -- $y$ $x$ $y$), equivalent to {\tt swap over}.
\item {\tt nip} ($x$ $y$ -- $y$), removes the second stack entry from the top. Equivalent to {\tt swap drop}.
\item {\tt 2dup} ($x$ $y$ -- $x$ $y$ $x$ $y$), equivalent to {\tt over over}.
\item {\tt 2drop} ($x$ $y$ -- ), equivalent to {\tt drop drop}.
\item {\tt 2swap} ($a$ $b$ $c$ $d$ -- $c$ $d$ $a$ $b$), interchanges the two topmost pairs of stack entries.
\item {\tt pick} ($x_n$ \dots $x_0$ $n$ -- $x_n$ \dots $x_0$ $x_n$), creates a copy of the $n$-th entry from the top of the stack, where $n\geq0$ is also passed in the stack. In particular, {\tt 0 pick} is equivalent to {\tt dup}, and {\tt 1 pick} to {\tt over}.
\item {\tt roll} ($x_n$ \dots $x_0$ $n$ -- $x_{n-1}$ \dots $x_0$ $x_n$), rotates the top $n$ stack entries, where $n\geq0$ is also passed in the stack. In particular, {\tt 1 roll} is equivalent to {\tt swap}, and {\tt 2 roll} to {\tt rot}.
\item {\tt -roll} ($x_n$ \dots $x_0$ $n$ -- $x_0$ $x_n$ \dots $x_1$), rotates the top $n$ stack entries in the opposite direction, where $n\geq0$ is also passed in the stack. In particular, {\tt 1 -roll} is equivalent to {\tt swap}, and {\tt 2 -roll} to {\tt -rot}.
\item {\tt exch} ($x_n$ \dots $x_0$ $n$ -- $x_0$ \dots $x_n$), interchanges the top of the stack with the $n$-th stack entry from the top, where $n\geq0$ is also taken from the stack. In particular, {\tt 1 exch} is equivalent to {\tt swap}, and {\tt 2 exch} to {\tt swap rot}.
\item {\tt exch2} (\dots $n$ $m$ -- \dots), interchanges the $n$-th stack entry from the top with the $m$-th stack entry from the top, where $n\geq0$, $m\geq0$ are taken from the stack.
\item {\tt ?dup} ($x$ -- $x$ $x$ or $0$), duplicates an {\em Integer\/} $x$, but only if it is non-zero. Otherwise leaves it intact.
\end{itemize}
For instance, ``{\tt 5 dup * .}'' will compute $5\cdot 5=25$ and print ``{\tt 25 ok}''.
One can use the word ``{\tt .s}''---which prints the contents of the entire stack, starting from the deepest elements, without removing the elements printed from the stack---to inspect the contents of the stack at any time, and to check the effect of any stack manipulation words. For instance,
\begin{verbatim}
1 2 3 4 .s
rot .s
\end{verbatim}
prints
\begin{verbatim}
1 2 3 4
ok
1 3 4 2
ok
\end{verbatim}
When Fift does not know how to print a stack value of an unknown type, it instead prints {\tt ???}.
\mysubsection{Defining new words}\label{p:colon.def}
In its simplest form, defining new Fift words is very easy and can be done with the aid of three special words: ``{\tt \{}'', ``{\tt \}}'', and ``{\tt :}''. One simply opens the definition with {\tt \{} (necessarily followed by a space), then lists all the words that constitute the new definition, then closes the definition with {\tt \}} (also followed by a space), and finally assigns the resulting definition (represented by a {\em WordDef\/} value in the stack) to a new word by writing {\tt:\ $\langle\textit{new-word-name}\rangle$}. For instance,
\begin{verbatim}
{ dup * } : square
\end{verbatim}
defines a new word {\tt square}, which executes {\tt dup} and {\tt *} when invoked. In this way, typing {\tt 5 square} becomes equivalent to typing {\tt 5 dup *}, and produces the same result ($25$):
\begin{verbatim}
5 square .
\end{verbatim}
prints ``{\tt 25 ok}''. One can also use the new word as a part of new definitions:
\begin{verbatim}
{ dup square square * } : **5
3 **5 .
\end{verbatim}
prints ``{\tt 243 ok}'', which indeed is $3^5$.
If the word indicated after ``{\tt :}'' is already defined, it is tacitly redefined. However, all existing definitions of other words will continue to use the old definition of the redefined word. For instance, if we redefine {\tt square} after we have already defined {\tt **5} as above, {\tt **5} will continue to use the original definition of {\tt square}.
\mysubsection{Named constants}\label{p:constants}
One can define {\em (named) constants}---i.e., words that push a predefined value when invoked---by using the defining word {\tt constant} instead of the defining word ``{\tt :}'' (colon). For instance,
\begin{verbatim}
1000000000 constant Gram
\end{verbatim}
defines a constant {\tt Gram} equal to {\em Integer\/} $10^9$. In other words, $1000000000$ will be pushed into the stack whenever {\tt Gram} is invoked:
\begin{verbatim}
Gram 2 * .
\end{verbatim}
prints ``{\tt 2000000000 ok}''.
Of course, one can use the result of a computation to initialize the value of a constant:
\begin{verbatim}
Gram 1000 / constant mGram
mGram .
\end{verbatim}
prints ``{\tt 1000000 ok}''.
The value of a constant does not necessarily have to be an {\em Integer}. For instance, one can define a string constant in the same way:
\begin{verbatim}
"Hello, world!" constant hello
hello type cr
\end{verbatim}
prints ``{\tt Hello, world!}'' on a separate line.
If a constant is redefined, all existing definitions of other words will continue to use the old value of the constant. In this respect, a constant does not behave as a global variable.
One can also store two values into one ``double'' constant by using the defining word {\tt 2constant}. For instance,
\begin{verbatim}
355 113 2constant pifrac
\end{verbatim}
defines a new word {\tt pifrac}, which will push $355$ and $113$ (in that order) when invoked. The two components of a double constant can be of different types.
If one wants to create a constant with a fixed name within a block or a colon definition, one should use {\tt =:} and {\tt 2=:} instead of {\tt constant} and {\tt 2constant}:
\begin{verbatim}
{ dup =: x dup * =: y } : setxy
3 setxy x . y . x y + .
7 setxy x . y . x y + .
\end{verbatim}
produces
\begin{verbatim}
3 9 12 ok
7 49 56 ok
\end{verbatim}
If one wants to recover the execution-time value of such a ``constant'', one can prefix the name of the constant with the word {\tt @'}:
\begin{verbatim}
{ ."( " @' x . .", " @' y . .") " } : showxy
3 setxy showxy
\end{verbatim}
produces
\begin{verbatim}
( 3 , 9 ) ok
\end{verbatim}
The drawback of this approach is that {\tt @'} has to look up the current definition of constants {\tt x} and {\tt y} in the dictionary each time {\tt showxy} is executed. Variables (cf.~\ptref{p:variables}) provide a more efficient way to achieve similar results.
\mysubsection{Integer and fractional constants, or literals}\label{p:int.lit}
Fift recognizes unnamed integer constants (called {\em literals\/} to distinguish them from named constants) in decimal, binary, and hexadecimal formats. Binary literals are prefixed by {\tt 0b}, hexadecimal literals are prefixed by {\tt 0x}, and decimal literals do not require a prefix. For instance, {\tt 0b1011}, {\tt 11}, and {\tt 0xb} represent the same integer ($11$). An integer literal may be prefixed by a minus sign ``{\tt -}'' to change its sign; the minus sign is accepted both before and after the {\tt 0x} and {\tt 0b} prefixes.
When Fift encounters a string that is absent from the dictionary but is a valid integer literal (fitting into the 257-bit signed integer type {\em Integer}), its value is pushed into the stack.
Apart from that, Fift offers some support for decimal and common fractions. If a string consists of two valid integer literals separated by a slash {\tt /}, then Fift interprets it as a fractional literal and represents it by two {\em Integer\/}s $p$ and $q$ in the stack, the numerator $p$ and the denominator $q$. For instance, {\tt -17/12} pushes $-17$ and $12$ into the Fift stack (being thus equivalent to {\tt -17 12}), and {\tt -0x11/0b1100} does the same thing. Decimal, binary, and hexadecimal fractions, such as {\tt 2.39} or {\tt -0x11.ef}, are also represented by two integers $p$ and $q$, where $q$ is a suitable power of the base (10, 2, or 16, respectively). For instance, {\tt 2.39} is equivalent to {\tt 239 100}, and {\tt -0x11.ef} is equivalent to {\tt -0x11ef 0x100}.
Such a representation of fractions is especially convenient for using them with the scaling primitive {\tt */} and its variants, thus converting common and decimal fractions into a suitable fixed-point representation. For instance, if we want to represent fractional amounts of Grams by integer amounts of nanograms, we can define some helper words
\begin{verbatim}
1000000000 constant Gram
{ Gram * } : Gram*
{ Gram swap */r } : Gram*/
\end{verbatim}
and then write {\tt 2.39 Gram*/} or {\tt 17/12 Gram*/} instead of integer literals {\tt 2390000000} or {\tt 1416666667}.
If one needs to use such Gram literals often, one can introduce a new active prefix word {\tt GR\$} as follows:
\begin{verbatim}
{ bl word (number) ?dup 0= abort"not a valid Gram amount"
1- { Gram swap */r } { Gram * } cond
1 'nop
} ::_ GR$
\end{verbatim}
makes {\tt GR\$3}, {\tt GR\$2.39}, and {\tt GR\$17/12} equivalent to integer literals {\tt 3000000000}, {\tt 2390000000}, and {\tt 1416666667}, respectively. Such values can be printed in similar form by means of the following words:
\begin{verbatim}
{ dup abs <# ' # 9 times char . hold #s rot sign #>
nip -trailing0 } : (.GR)
{ (.GR) ."GR$" type space } : .GR
-17239000000 .GR
\end{verbatim}
produces {\tt GR\$-17.239 ok}. The above definitions make use of tricks explained in later portions of this document (especially Chapter~\ptref{s:dict.compiler}).
We can also manipulate fractions by themselves by defining suitable ``rational arithmetic words'':
\begin{verbatim}
// a b c d -- (a*d-b*c) b*d
{ -rot over * 2swap tuck * rot - -rot * } : R-
// a b c d -- a*c b*d
{ rot * -rot * swap } : R*
// a b --
{ swap ._ ."/" . } : R.
1.7 2/3 R- R.
\end{verbatim}
will output ``{\tt 31/30 ok}'', indicating that $1.7-2/3=31/30$. Here ``{\tt .\_}'' is a variant of ``{\tt .}'' that does not print a space after the decimal representation of an {\em Integer}.
\mysubsection{String literals}\label{p:string.lit}
String literals are introduced by means of the prefix word {\tt "}, which scans the remainder of the line until the next {\tt "} character, and pushes the string thus obtained into the stack as a value of type {\em String}. For instance, {\tt "Hello, world!"} pushes the corresponding {\em String\/} into the stack:
\begin{verbatim}
"Hello, world!" .s
\end{verbatim}
\mysubsection{Simple string manipulation}\label{p:string.ops}
The following words can be used to manipulate strings:
\begin{itemize}
\item {\tt"$\langle\textit{string}\rangle$"} ( -- $S$), pushes a {\em String\/} literal into the stack.
\item {\tt."$\langle\textit{string}\rangle$"} ( -- ), prints a constant string into the standard output.
\item {\tt type} ($S$ -- ), prints a {\em String\/} $S$ taken from the top of the stack into the standard output.
\item {\tt cr} ( -- ), outputs a carriage return (or a newline character) into the standard output.
\item {\tt emit} ($x$ -- ), prints a UTF-8 encoded character with Unicode codepoint given by {\em Integer\/} $x$ into the standard output.
\item {\tt char $\langle\textit{string}\rangle$} ( -- $x$), pushes an {\em Integer\/} with the Unicode codepoint of the first character of {\tt $\langle\textit{string}\rangle$}.
\item {\tt bl} ( -- $x$), pushes the Unicode codepoint of a space, i.e., 32.
\item {\tt space} ( -- ), prints one space, equivalent to {\tt bl emit}.
\item {\tt \$+} ($S$ $S'$ -- $S.S'$), concatenates two strings.
\item {\tt \$len} ($S$ -- $x$), computes the byte length (not the UTF-8 character length!) of a string.
\item {\tt +"$\langle\textit{string}\rangle$"} ($S$ -- $S'$), concatenates {\em String\/}~$S$ with a string literal. Equivalent to {\tt "$\langle\textit{string}\rangle$" \$+}.
\item {\tt word} ($x$ -- $S$), parses a word delimited by the character with the Unicode codepoint $x$ from the remainder of the current input line and pushes the result as a {\em String}. For instance, {\tt bl word abracadabra type} will print the string ``{\tt abracadabra}''. If $x=0$, skips leading spaces, and then scans until the end of the current input line. If $x=32$, skips leading spaces before parsing the next word.
\item {\tt (.)} ($x$ -- $S$), returns the {\em String\/} with the decimal representation of {\em Integer\/}~$x$.
\item {\tt (number)} ($S$ -- $0$ or $x$ $1$ or $x$ $y$ $2$), attempts to parse the {\em String\/} $S$ as an integer or fractional literal as explained in~\ptref{p:int.lit}.
\end{itemize}
For instance, {\tt ."*"}, {\tt "*" type}, {\tt 42 emit}, and {\tt char * emit} are four different ways to output a single asterisk.
\mysubsection{Boolean expressions, or flags}\label{p:bool}
Fift does not have a separate value type for representing boolean values. Instead, any non-zero {\em Integer\/} can be used to represent truth (with $-1$ being the standard representation), while a zero {\em Integer\/} represents falsehood. Comparison primitives normally return $-1$ to indicate success and $0$ otherwise.
Constants {\tt true} and {\tt false} can be used to push these special integers into the stack:
\begin{itemize}
\item {\tt true} ( -- $-1$), pushes $-1$ into the stack.
\item {\tt false} ( -- $0$), pushes $0$ into the stack.
\end{itemize}
If boolean values are standard (either $0$ or $-1$), they can be manipulated by means of bitwise logical operations {\tt and}, {\tt or}, {\tt xor}, {\tt not} (listed in~\ptref{p:arith.op}). Otherwise, they must first be reduced to the standard form using {\tt 0<>}:
\begin{itemize}
\item {\tt 0<>} ($x$ -- $x\neq0$), pushes $-1$ if {\em Integer\/} $x$ is non-zero, $0$ otherwise.
\end{itemize}
\mysubsection{Integer comparison operations}\label{p:int.comp}
Several integer comparison operations can be used to obtain boolean values:
\begin{itemize}
\item {\tt <} ($x$ $y$ -- $?$), checks whether $x<y$ (i.e., pushes $-1$ if $x<y$, $0$ otherwise).
\item {\tt >}, {\tt =}, {\tt <>}, {\tt <=}, {\tt >=} ($x$ $y$ -- $?$), compare $x$ and $y$ and push $-1$ or $0$ depending on the result of the comparison.
\item {\tt 0<} ($x$ -- $?$), checks whether $x<0$ (i.e., pushes $-1$ if $x$ is negative, $0$ otherwise). Equivalent to {\tt 0 <}.
\item {\tt 0>}, {\tt 0=}, {\tt 0<>}, {\tt 0<=}, {\tt 0>=} ($x$ -- $?$), compare $x$ against zero.
\item {\tt cmp} ($x$ $y$ -- $z$), pushes $1$ if $x>y$, $-1$ if $x<y$, and $0$ if $x=y$.
\item {\tt sgn} ($x$ -- $y$), pushes $1$ if $x>0$, $-1$ if $x<0$, and $0$ if $x=0$. Equivalent to {\tt 0 cmp}.
\end{itemize}
Example:
\begin{verbatim}
2 3 < .
\end{verbatim}
prints ``{\tt -1 ok}'', because $2$ is less than $3$.
A more convoluted example:
\begin{verbatim}
{ "true " "false " rot 0= 1+ pick type 2drop } : ?.
2 3 < ?. 2 3 = ?. 2 3 > ?.
\end{verbatim}
prints ``{\tt true false false ok}''.
\mysubsection{String comparison operations}\label{p:string.cmp.ops}
Strings can be lexicographically compared by means of the following words:
\begin{itemize}
\item {\tt \$=} ($S$ $S'$ -- $?$), returns $-1$ if strings $S$ and $S'$ are equal, $0$ otherwise.
\item {\tt \$cmp} ($S$ $S'$ -- $x$), returns $0$ if strings $S$ and $S'$ are equal, $-1$ if $S$ is lexicographically less than $S'$, and $1$ if $S$ is lexicographically greater than $S'$.
\end{itemize}
\mysubsection{Named and unnamed variables}\label{p:variables}
In addition to constants introduced in~\ptref{p:constants}, Fift supports {\em variables}, which are a more efficient way to represent changeable values. For instance, the last two code fragments of~\ptref{p:constants} could have been written with the aid of variables instead of constants as follows:
\begin{verbatim}
variable x variable y
{ dup x ! dup * y ! } : setxy
3 setxy x @ . y @ . x @ y @ + .
7 setxy x @ . y @ . x @ y @ + .
{ ."( " x @ . .", " y @ . .") " } : showxy
3 setxy showxy
\end{verbatim}
producing the same output as before:
\begin{verbatim}
3 9 12 ok
7 49 56 ok
( 3 , 9 ) ok
\end{verbatim}
The phrase {\tt variable x} creates a new {\em Box}, i.e., a memory location that can be used to store exactly one value of any Fift-supported type, and defines {\tt x} as a constant equal to this {\em Box\/}:
\begin{itemize}
\item {\tt variable} ( -- ), scans a blank-delimited word name $S$ from the remainder of the input, allocates an empty {\em Box}, and defines a new ordinary word $S$ as a constant, which will push the new {\em Box\/} when invoked. Equivalent to {\tt hole constant}.
\item {\tt hole} ( -- $p$), creates a new {\em Box\/}~$p$ that does not hold any value. Equivalent to {\tt null box}.
\item {\tt box} ($x$ -- $p$), creates a new {\em Box\/} containing specified value~$x$. Equivalent to {\tt hole tuck !}.
\end{itemize}
The value currently stored in a {\em Box\/} may be fetched by means of word {\tt @} (pronounced ``fetch''), and modified by means of word {\tt !} (pronounced ``store''):
\begin{itemize}
\item {\tt @} ($p$ -- $x$), fetches the value currently stored in {\em Box\/}~$p$.
\item {\tt !} ($x$ $p$ -- ), stores new value~$x$ into {\em Box\/}~$p$.
\end{itemize}
Several auxiliary words exist that can modify the current value in a more sophisticated fashion:
\begin{itemize}
\item {\tt +!} ($x$ $p$ -- ), increases the integer value stored in {\em Box\/}~$p$ by {\em Integer\/}~$x$. Equivalent to {\tt tuck @ + swap !}.
\item {\tt 1+!} ($p$ -- ), increases the integer value stored in {\em Box\/}~$p$ by one. Equivalent to {\tt 1 swap +!}.
\item {\tt 0!} ($p$ -- ), stores {\em Integer\/} $0$ into {\em Box\/}~$p$. Equivalent to {\tt 0 swap !}.
\end{itemize}
In this way we can implement a simple counter:
\begin{verbatim}
variable counter
{ counter 0! } : reset-counter
{ counter @ 1+ dup counter ! } : next-counter
reset-counter next-counter . next-counter . next-counter .
reset-counter next-counter .
\end{verbatim}
produces
\begin{verbatim}
1 2 3 ok
1 ok
\end{verbatim}
After these definitions are in place, we can even forget the definition of {\tt counter} by means of the phrase {\tt forget counter}. Then the only way to access the value of this variable is by means of {\tt reset-counter} and {\tt next-counter}.
Variables are usually created by {\tt variable} with no value, or rather with a {\em Null\/} value. If one wishes to create initialized variables, one can use the phrase {\tt box constant}:
\begin{verbatim}
17 box constant x
x 1+! x @ .
\end{verbatim}
prints ``{\tt 18 ok}''. One can even define a special defining word for initialized variables, if they are needed often:
\begin{verbatim}
{ box constant } : init-variable
17 init-variable x
"test" init-variable y
x 1+! x @ . y @ type
\end{verbatim}
prints ``{\tt 18 test ok}''.
The variables have so far only one disadvantage compared to the constants: one has to access their current values by means of an auxiliary word {\tt @}. Of course, one can mitigate this by defining a ``getter'' and a ``setter'' word for a variable, and use these words to write better-looking code:
\begin{verbatim}
variable x-box
{ x-box @ } : x
{ x-box ! } : x!
{ x x * 5 x * + 6 + } : f(x)
{ ."( " x . .", " f(x) . .") " } : .xy
3 x! .xy 5 x! .xy
\end{verbatim}
prints ``{\tt ( 3 , 30 ) ( 5 , 56 ) ok}'', which are the points $(x,f(x))$ on the graph of $f(x)=x^2+5x+6$ with $x=3$ and $x=5$.
Again, if we want to define ``getters'' for all our variables, we can first define a defining word as explained in~\ptref{p:custom.defw}, and use this word to define both a getter and a setter at the same time:
\begin{verbatim}
{ hole dup 1 ' @ does create 1 ' ! does create } : variable-set
variable-set x x!
variable-set y y!
{ ."x=" x . ."y=" y . ."x*y=" x y * . cr } : show
{ y 1+ y! } : up
{ x 1+ x! } : right
{ x y x! y! } : reflect
2 x! 5 y! show up show right show up show reflect show
\end{verbatim}
produces
\begin{verbatim}
x=2 y=5 x*y=10
x=2 y=6 x*y=12
x=3 y=6 x*y=18
x=3 y=7 x*y=21
x=7 y=3 x*y=21
\end{verbatim}
\mysubsection{Tuples and arrays}\label{p:tuples}
Fift also supports {\em Tuple\/}s, i.e., immutable ordered collections of arbitrary values of stack value types (cf.~\ptref{p:stack.types}). When a {\em Tuple\/}~$t$ consists of values $x_1$, \dots, $x_n$ (in that order), we write $t=(x_1,\ldots,x_n)$. The number~$n$ is called the {\em length\/} of {\em Tuple\/}~$t$; it is also denoted by~$|t|$. Tuples of length two are also called {\em pairs}, tuples of length three are {\em triples}.
\begin{itemize}
\item {\tt tuple} ($x_1$ \dots $x_n$ $n$ -- $t$), creates new {\em Tuple\/} $t:=(x_1,\ldots,x_n)$ from $n\geq0$ topmost stack values.
\item {\tt pair} ($x$ $y$ -- $t$), creates new pair $t=(x,y)$. Equivalent to {\tt 2 tuple}.
\item {\tt triple} ($x$ $y$ $z$ -- $t$), creates new triple $t=(x,y,z)$. Equivalent to {\tt 3 tuple}.
\item {\tt |} ( -- $t$), creates an empty {\em Tuple\/} $t=()$. Equivalent to {\tt 0 tuple}.
\item {\tt ,} ($t$ $x$ -- $t'$), appends $x$ to the end of {\em Tuple\/}~$t$, and returns the resulting {\em Tuple\/}~$t'$.
\item {\tt .dump} ($x$ -- ), dumps the topmost stack entry in the same way as {\tt .s} dumps all stack elements.
\end{itemize}
For instance, both
\begin{verbatim}
| 2 , 3 , 9 , .dump
\end{verbatim}
and
\begin{verbatim}
2 3 9 triple .dump
\end{verbatim}
construct and print triple $(2,3,9)$:
\begin{verbatim}
[ 2 3 9 ] ok
\end{verbatim}
Notice that the components of a {\em Tuple\/} are not necessarily of the same type, and that a component of a {\em Tuple\/} can also be a {\em Tuple\/}:
\begin{verbatim}
1 2 3 triple 4 5 6 triple 7 8 9 triple triple constant Matrix
Matrix .dump cr
| 1 "one" pair , 2 "two" pair , 3 "three" pair , .dump
\end{verbatim}
produces
\begin{verbatim}
[ [ 1 2 3 ] [ 4 5 6 ] [ 7 8 9 ] ]
[ [ 1 "one" ] [ 2 "two" ] [ 3 "three" ] ] ok
\end{verbatim}
Once a {\em Tuple\/} has been constructed, we can extract any of its components, or completely unpack the {\em Tuple\/} into the stack:
\begin{itemize}
\item {\tt untuple} ($t$ $n$ -- $x_1$ \dots $x_n$), returns all components of a {\em Tuple\/}~$t=(x_1,\ldots,x_n)$, but only if its length is equal to~$n$. Otherwise throws an exception.
\item {\tt unpair} ($t$ -- $x$ $y$), unpacks a pair $t=(x,y)$. Equivalent to {\tt 2 untuple}.
\item {\tt untriple} ($t$ -- $x$ $y$ $z$), unpacks a triple $t=(x,y,z)$. Equivalent to {\tt 3 untuple}.
\item {\tt explode} ($t$ -- $x_1$ \dots $x_n$ $n$), unpacks a {\em Tuple\/}~$t=(x_1,\ldots,x_n)$ of unknown length~$n$, and returns that length.
\item {\tt count} ($t$ -- $n$), returns the length $n=|t|$ of {\em Tuple\/}~$t$.
\item {\tt tuple?} ($t$ -- $?$), checks whether $t$ is a {\em Tuple}, and returns $-1$ or $0$ accordingly.
\item {\tt []} ($t$ $i$ -- $x$), returns the $(i+1)$-st component $t_{i+1}$ of {\em Tuple\/}~$t$, where $0\leq i<|t|$.
\item {\tt first} ($t$ -- $x$), returns the first component of a {\em Tuple}. Equivalent to {\tt 0 []}.
\item {\tt second} ($t$ -- $x$), returns the second component of a {\em Tuple}. Equivalent to {\tt 1 []}.
\item {\tt third} ($t$ -- $x$), returns the third component of a {\em Tuple}. Equivalent to {\tt 2 []}.
\end{itemize}
For instance, we can access individual elements and rows of a matrix:
\begin{verbatim}
1 2 3 triple 4 5 6 triple 7 8 9 triple triple constant Matrix
Matrix .dump cr
Matrix 1 [] 2 [] . cr
Matrix third .dump cr
\end{verbatim}
produces
\begin{verbatim}
[ [ 1 2 3 ] [ 4 5 6 ] [ 7 8 9 ] ]
6
[ 7 8 9 ]
\end{verbatim}
Notice that {\em Tuple\/}s are somewhat similar to arrays of other programming languages, but are immutable: we cannot change one individual component of a {\em Tuple}. If we still want to create something like an array, we need a {\em Tuple\/} of {\em Box\/}es (cf.~\ptref{p:variables}):
\begin{itemize}
\item {\tt allot} ($n$ -- $t$), creates a {\em Tuple\/} that consists of $n$ new empty {\em Box\/}es. Equivalent to {\tt | \{ hole , \} rot times}.
\end{itemize}
For instance,
\begin{verbatim}
10 allot constant A
| 3 box , 1 box , 4 box , 1 box , 5 box , 9 box , constant B
{ over @ over @ swap rot ! swap ! } : swap-values-of
{ B swap [] } : B[]
{ B[] swap B[] swap-values-of } : swap-B
{ B[] @ . } : .B[]
0 1 swap-B 1 3 swap-B 0 2 swap-B
0 .B[] 1 .B[] 2 .B[] 3 .B[]
\end{verbatim}
creates an uninitialized array~$A$ of length~10, an initialized array~$B$ of length~6, and then interchanges some elements of $B$ and prints the first four elements of the resulting~$B$:
\begin{verbatim}
4 1 1 3 ok
\end{verbatim}
\mysubsection{Lists}\label{p:lists}
Lisp-style lists can also be represented in Fift. First of all, two special words are introduced to manipulate values of type {\em Null}, used to represent the empty list (not to be confused with the empty {\em Tuple}):
\begin{itemize}
\item {\tt null} ( -- $\bot$), pushes the only value~$\bot$ of type {\em Null}, which is also used to represent an empty list.
\item {\tt null?} ($x$ -- $?$), checks whether~$x$ is a {\em Null}. Can also be used to check whether a list is empty.
\end{itemize}
After that, {\tt cons} and {\tt uncons} are defined as aliases for {\tt pair} and {\tt unpair}:
\begin{itemize}
\item {\tt cons} ($h$ $t$ -- $l$), constructs a list from its head (first element) $h$ and its tail (the list consisting of all remaining elements)~$t$. Equivalent to {\tt pair}.
\item {\tt uncons} ($l$ -- $h$ $t$), decomposes a non-empty list into its head and its tail. Equivalent to {\tt unpair}.
\item {\tt car} ($l$ -- $h$), returns the head of a list. Equivalent to {\tt first}.
\item {\tt cdr} ($l$ -- $t$), returns the tail of a list. Equivalent to {\tt second}.
\item {\tt cadr} ($l$ -- $h'$), returns the second element of a list. Equivalent to {\tt cdr car}.
\item {\tt list} ($x_1$ \dots $x_n$ $n$ -- $l$), constructs a list $l$ of length~$n$ with elements $x_1$, \ldots, $x_n$, in that order. Equivalent to {\tt null ' cons rot times}.
\item {\tt .l} ($l$ -- ), prints a Lisp-style list~$l$.
\end{itemize}
For instance,
\begin{verbatim}
2 3 9 3 tuple .dump cr
2 3 9 3 list dup .dump space dup .l cr
"test" swap cons .l cr
\end{verbatim}
produces
\begin{verbatim}
[ 2 3 9 ]
[ 2 [ 3 [ 9 (null) ] ] ] (2 3 9)
("test" 2 3 9)
\end{verbatim}
Notice that the three-element list $(2\ 3\ 9)$ is distinct from the triple $(2,3,9)$.
\mysubsection{Atoms}\label{p:atoms}
An {\em Atom\/} is a simple entity uniquely identified by its name. {\em Atom\/}s can be used to represent identifiers, labels, operation names, tags, and stack markers. Fift offers the following words to manipulate {\em Atom\/}s:
\begin{itemize}
\item {\tt (atom)} ($S$ $x$ -- $a$ $-1$ or $0$), returns the only {\em Atom\/} $a$ with the name given by {\em String\/}~$S$. If there is no such {\em Atom\/} yet, either creates it (if {\em Integer\/}~$x$ is non-zero) or returns a single zero to indicate failure (if $x$ is zero).
\item {\tt atom} ($S$ -- $a$), returns the only {\em Atom\/}~$a$ with the name~$S$, creating such an atom if necessary. Equivalent to {\tt true (atom) drop}.
\item {\tt `$\langle\textit{word\/}\rangle$} ( -- $a$), introduces an {\em Atom\/} literal, equal to the only {\em Atom\/} with the name equal to $\langle\textit{word\/}\rangle$. Equivalent to {\tt "$\langle\textit{word\/}\rangle$" atom}.
\item {\tt anon} ( -- $a$), creates a new unique anonymous {\em Atom}.
\item {\tt atom?} ($u$ -- $?$), checks whether $u$ is an {\em Atom}.
\item {\tt eq?} ($u$ $v$ -- $?$), checks whether $u$ and $v$ are equal {\em Integer\/}s, {\em Atom\/}s, or {\em Null\/}s. If they are not equal, or if they are of different types, or not of one of the types listed, returns zero.
\end{itemize}
For instance,
\begin{verbatim}
`+ 2 `* 3 4 3 list 3 list .l
\end{verbatim}
creates and prints the list
\begin{verbatim}
(+ 2 (* 3 4))
\end{verbatim}
which is the Lisp-style representation of arithmetical expression $2+3\cdot 4$. An interpreter for such expressions might use {\tt eq?} to check the operation sign (cf.~\ptref{p:recursion} for an explanation of recursive functions in Fift):
\begin{verbatim}
variable 'eval
{ 'eval @ execute } : eval
{ dup tuple? {
uncons uncons uncons
null? not abort"three-element list expected"
swap eval swap eval rot
dup `+ eq? { drop + } {
dup `- eq? { drop - } {
`* eq? not abort"unknown operation" *
} cond
} cond
} if
} 'eval !
`+ 2 `* 3 4 3 list 3 list dup .l cr eval . cr
\end{verbatim}
prints
\begin{verbatim}
(+ 2 (* 3 4))
14
\end{verbatim}
If we load {\tt Lisp.fif} to enable Lisp-style list syntax, we can enter
\begin{verbatim}
"Lisp.fif" include
( `+ 2 ( `* 3 4 ) ) dup .l cr eval . cr
\end{verbatim}
with the same result as before. The word {\tt (}, defined in {\tt Lisp.fif}, uses an anonymous {\em Atom\/} created by {\tt anon} to mark the current stack position, and then {\tt )} builds a list from several top stack entries, scanning the stack until the anonymous {\em Atom\/} marker is found:
\begin{verbatim}
variable ')
{ ") without (" abort } ') !
{ ') @ execute } : )
{ null { -rot 2dup eq? not } { swap rot cons } while 2drop
} : list-until-marker
{ anon dup ') @ 2 { ') ! list-until-marker } does ') ! } : (
\end{verbatim}
\mysubsection{Command line arguments in script mode}\label{p:cmdline.ops}
The Fift interpreter can be invoked in {\em script mode\/} by passing {\tt -s} as a command line option. In this mode, all further command line arguments are not scanned for Fift startup command line options. Rather, the next argument after {\tt -s} is used as the filename of the Fift source file, and all further command line arguments are passed to the Fift program by means of special words {\tt \$$n$} and {\tt \$\#}:
\begin{itemize}
\item {\tt \$\#} ( -- $x$), pushes the total number of command-line arguments passed to the Fift program.
\item {\tt \$$n$} ( -- $S$), pushes the $n$-th command-line argument as a {\em String}~$S$. For instance, {\tt \$0} pushes the name of the script being executed, {\tt \$1} the first command line argument, and so on.
\item {\tt \$()} ($x$ -- $S$), pushes the $x$-th command-line argument similarly to {\tt \$$n$}, but with {\em Integer\/}~$x$ taken from the stack.
\end{itemize}
Additionally, if the very first line of a Fift source file begins with the two characters ``{\tt \#!}'', this line is ignored. In this way simple Fift scripts can be written in a *ix system. For instance, if
\begin{verbatim}
#!/usr/bin/fift -s
{ ."usage: " $0 type ." <num1> <num2>" cr
."Computes the product of two integers." cr 1 halt } : usage
{ ' usage if } : ?usage
$# 2 <> ?usage
$1 (number) 1- ?usage
$2 (number) 1- ?usage
* . cr
\end{verbatim}
is saved into a file {\tt cmdline.fif} in the current directory, and its execution bit is set (e.g., by {\tt chmod 755 cmdline.fif}), then it can be invoked from the shell or any other program, provided the Fift interpreter is installed as {\tt /usr/bin/fift}, and its standard library {\tt Fift.fif} is installed as {\tt /usr/lib/fift/Fift.fif}:
\begin{verbatim}
$ ./cmdline.fif 12 -5
\end{verbatim}
prints
\begin{verbatim}
-60
\end{verbatim}
when invoked from a *ix shell such as the Bourne--again shell (Bash).
\mysection{Blocks, loops, and conditionals}
Similarly to the arithmetic operations, the execution flow in Fift is controlled by stack-based primitives. This leads to an inversion typical of reverse Polish notation and stack-based arithmetic: one first pushes a block representing a conditional branch or the body of a loop into the stack, and then invokes a conditional or iterated execution primitive. In this respect, Fift is more similar to PostScript than to Forth.
\mysubsection{Defining and executing blocks}\label{p:blocks}
A block is normally defined using the special words ``{\tt \{}'' and ``{\tt \}}''. Roughly speaking, all words listed between {\tt \{} and {\tt \}} constitute the body of a new block, which is pushed into the stack as a value of type {\em WordDef}. A block may be stored as a definition of a new Fift word by means of the defining word ``{\tt :}'' as explained in \ptref{p:colon.def}, or executed by means of the word {\tt execute}:
\begin{verbatim}
17 { 2 * } execute .
\end{verbatim}
prints ``{\tt 34 ok}'', being essentially equivalent to ``{\tt 17 2 * .}''. A slightly more convoluted example:
\begin{verbatim}
{ 2 * } 17 over execute swap execute .
\end{verbatim}
applies ``anonymous function'' $x\mapsto 2x$ twice to $17$, and prints the result $2\cdot(2\cdot 17)=68$. In this way a block is an execution token, which can be duplicated, stored into a constant, used to define a new word, or executed.
The word {\tt '} recovers the current definition of a word. Namely, the construct {\tt ' $\langle\textit{word-name}\rangle$} pushes the execution token equivalent to the current definition of the word $\langle\textit{word-name}\rangle$. For instance,
\begin{verbatim}
' dup execute
\end{verbatim}
is equivalent to {\tt dup}, and
\begin{verbatim}
' dup : duplicate
\end{verbatim}
defines {\tt duplicate} as a synonym for (the current definition of) {\tt dup}.
Alternatively, we can duplicate a block to define two new words with the same definition:
\begin{verbatim}
{ dup * }
dup : square : **2
\end{verbatim}
defines both {\tt square} and {\tt **2} to be equivalent to {\tt dup *}.
\mysubsection{Conditional execution of blocks}\label{p:cond.ops}
Conditional execution of blocks is achieved using the words {\tt if}, {\tt ifnot}, and {\tt cond}:
\begin{itemize}
\item {\tt if} ($x$ $e$ -- ), executes $e$ (which must be an execution token, i.e., a {\em WordDef\/}),\footnote{A {\em WordDef\/} is more general than a {\em WordList}. For instance, the definition of the primitive {\tt +} is a {\em WordDef}, but not a {\em WordList}, because {\tt +} is not defined in terms of other Fift words.} but only if {\em Integer\/} $x$ is non-zero.
\item {\tt ifnot} ($x$ $e$ -- ), executes execution token $e$, but only if {\em Integer\/} $x$ is zero.
\item {\tt cond} ($x$ $e$ $e'$ -- ), if {\em Integer\/} $x$ is non-zero, executes $e$, otherwise executes $e'$.
\end{itemize}
For instance, the last example in \ptref{p:int.comp} can be more conveniently rewritten as
\begin{verbatim}
{ { ."true " } { ."false " } cond } : ?.
2 3 < ?. 2 3 = ?. 2 3 > ?.
\end{verbatim}
still resulting in ``{\tt true false false ok}''.
Notice that blocks can be arbitrarily nested, as already shown in the previous example. One can write, for example,
\begin{verbatim}
{ ?dup
{ 0<
{ ."negative " }
{ ."positive " }
cond
}
{ ."zero " }
cond
} : chksign
-17 chksign
\end{verbatim}
to obtain ``{\tt negative ok}'', because $-17$ is negative.
\mysubsection{Simple loops}\label{p:simple.loops}
The simplest loops are implemented by {\tt times}:
\begin{itemize}
\item {\tt times} ($e$ $n$ -- ), executes $e$ exactly $n$ times, if $n\geq0$. If $n$ is negative, throws an exception.
\end{itemize}
For instance,
\begin{verbatim}
1 { 10 * } 70 times .
\end{verbatim}
computes and prints $10^{70}$.
We can use this kind of loop to implement a simple factorial function:
\begin{verbatim}
{ 0 1 rot { swap 1+ tuck * } swap times nip } : fact
5 fact .
\end{verbatim}
prints ``{\tt 120 ok}'', because $5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120$.
This loop can be modified to compute Fibonacci numbers instead:
\begin{verbatim}
{ 0 1 rot { tuck + } swap times nip } : fibo
6 fibo .
\end{verbatim}
computes the sixth Fibonacci number $F_6=13$.
\mysubsection{Loops with an exit condition}\label{p:loops}
More sophisticated loops can be created with the aid of {\tt until} and {\tt while}:
\begin{itemize}
\item {\tt until} ($e$ -- ), executes $e$, then removes the top-of-stack integer and checks whether it is zero. If it is, then begins a new iteration of the loop by executing $e$. Otherwise exits the loop.
\item {\tt while} ($e$ $e'$ -- ), executes $e$, then removes and checks the top-of-stack integer. If it is zero, exits the loop. Otherwise executes $e'$, then begins a new loop iteration by executing $e$ and checking the exit condition afterwards.
\end{itemize}
For instance, we can compute the first two Fibonacci numbers greater than 1000:
\begin{verbatim}
{ 1 0 rot { -rot over + swap rot 2dup >= } until drop
} : fib-gtr
1000 fib-gtr . .
\end{verbatim}
prints ``{\tt 1597 2584 ok}''.
We can use this word to compute the first 70 decimal digits of the golden ratio $\phi=(1+\sqrt{5})/2\approx 1.61803$:
\begin{verbatim}
1 { 10 * } 70 times dup fib-gtr */ .
\end{verbatim}
prints ``{\tt $161803\ldots2604$ ok}''.
\mysubsection{Recursion}\label{p:recursion}
Notice that, whenever a word is mentioned inside a {\tt \{ \dots \}} block, the current (compile-time) definition is included in the {\em WordList\/} being created. In this way we can refer to the previous definition of a word while defining a new version of it:
\begin{verbatim}
{ + . } : print-sum
{ ."number " . } : .
{ 1+ . } : print-next
2 . 3 . 2 3 print-sum 7 print-next
\end{verbatim}
produces ``{\tt number 2 number 3 5 number 8 ok}''. Notice that {\tt print-sum} continues to use the original definition of ``{\tt .}'', but {\tt print-next} already uses the modified ``{\tt .}''.
This feature may be convenient on some occasions, but it prevents us from introducing recursive definitions in the most straightforward fashion. For instance, the classical recursive definition of the factorial
\begin{verbatim}
{ ?dup { dup 1- fact * } { 1 } cond } : fact
\end{verbatim}
will fail to compile, because {\tt fact} happens to be an undefined word when the definition is compiled.
A simple way around this obstacle is to use the word {\tt @'} (cf.~\ptref{p:dict.lookup}) that looks up the current definition of the next word during the execution time and then executes it, similarly to what we already did in~\ptref{p:constants}:
\begin{verbatim}
{ ?dup { dup 1- @' fact * } { 1 } cond } : fact
5 fact .
\end{verbatim}
produces ``{\tt 120 ok}'', as expected.
However, this solution is rather inefficient, because it uses a dictionary lookup each time {\tt fact} is recursively executed. We can avoid this dictionary lookup by using variables (cf.~\ptref{p:variables} and \ptref{p:constants}):
\begin{verbatim}
variable 'fact
{ 'fact @ execute } : fact
{ ?dup { dup 1- fact * } { 1 } cond } 'fact !
5 fact .
\end{verbatim}
This somewhat longer definition of the factorial avoids dictionary lookups at execution time by introducing a special variable {\tt 'fact} to hold the final definition of the factorial.\footnote{Variables that hold a {\em WordDef\/} to be {\tt execute}d later are called {\em vector variables}. The process of replacing {\tt fact} with {\tt 'fact @ execute}, where {\tt 'fact} is a vector variable, is called {\em vectorization}.} Then {\tt fact} is defined to execute whatever {\em WordDef} is currently stored in {\tt 'fact}, and once the body of the recursive definition of the factorial is constructed, it is stored into this variable by means of the phrase {\tt 'fact !}, which replaces the more customary phrase {\tt :\ fact}.
We could rewrite the above definition by using special ``getter'' and ``setter'' words for vector variable {\tt 'fact} as we did for variables in \ptref{p:variables}:
\begin{verbatim}
variable 'fact
{ 'fact @ execute } : fact
{ 'fact ! } : :fact
forget 'fact
{ ?dup { dup 1- fact * } { 1 } cond } :fact
5 fact .
\end{verbatim}
If we need to introduce a lot of recursive and mutually-recursive definitions, we might first introduce a custom defining word (cf.~\ptref{p:custom.defw}) for simultaneously defining both the ``getter'' and the ``setter'' words for anonymous vector variables, similarly to what we did in~\ptref{p:variables}:
\begin{verbatim}
{ hole dup 1 { @ execute } does create 1 ' ! does create
} : vector-set
vector-set fact :fact
{ ?dup { dup 1- fact * } { 1 } cond } :fact
5 fact .
\end{verbatim}
The first three lines of this fragment define {\tt fact} and {\tt :fact} essentially in the same way they had been defined in the first four lines of the previous fragment.
If we wish to make {\tt fact} unchangeable in the future, we can add a {\tt forget :fact} line once the definition of the factorial is complete:
\begin{verbatim}
{ hole dup 1 { @ execute } does create 1 ' ! does create
} : vector-set
vector-set fact :fact
{ ?dup { dup 1- fact * } { 1 } cond } :fact
forget :fact
5 fact .
\end{verbatim}
Alternatively, we can modify the definition of {\tt vector-set} in such a way that {\tt :fact} would forget itself once it is invoked:
\begin{verbatim}
{ hole dup 1 { @ execute } does create
bl word tuck 2 { (forget) ! } does swap 0 (create)
} : vector-set-once
vector-set-once fact :fact
{ ?dup { dup 1- fact * } { 1 } cond } :fact
5 fact .
\end{verbatim}
However, some vector variables must be modified more than once, for instance, to modify the behavior of the comparison word {\tt less} in a merge sort algorithm:
\begin{verbatim}
{ hole dup 1 { @ execute } does create 1 ' ! does create
} : vector-set
vector-set sort :sort
vector-set merge :merge
vector-set less :less
{ null null rot
{ dup null? not }
{ uncons swap rot cons -rot } while drop
} : split
{ dup null? { drop } {
over null? { nip } {
over car over car less ' swap if
uncons rot merge cons
} cond
} cond
} :merge
{ dup null? {
dup cdr null? {
split sort swap sort merge
} ifnot
} ifnot
} :sort
forget :merge
forget :sort
// set `less` to compare numbers, sort a list of numbers
' < :less
3 1 4 1 5 9 2 6 5 9 list
dup .l cr sort .l cr
// set `less` to compare strings, sort a list of strings
{ $cmp 0< } :less
"once" "upon" "a" "time" "there" "lived" "a" "kitten" 8 list
dup .l cr sort .l cr
\end{verbatim}
producing the following output:
\begin{verbatim}
(3 1 4 1 5 9 2 6 5)
(1 1 2 3 4 5 5 6 9)
("once" "upon" "a" "time" "there" "lived" "a" "kitten")
("a" "a" "kitten" "lived" "once" "there" "time" "upon")
\end{verbatim}
\mysubsection{Throwing exceptions}\label{p:exception.ops}
Two built-in words are used to throw exceptions:
\begin{itemize}
\item {\tt abort} ($S$ -- ), throws an exception with an error message taken from {\em String\/} $S$.
\item {\tt abort"$\langle\textit{message}\rangle$"} ($x$ -- ), throws an exception with the error message $\langle\textit{message}\rangle$ if $x$ is a non-zero integer.
\end{itemize}
The exception thrown by these words is represented by the C++ exception {\tt fift::IntError} with its value equal to the specified string. It is normally handled within the Fift interpreter itself by aborting all execution up to the top level and printing a message with the name of the source file being interpreted, the line number, the currently interpreted word, and the specified error message. For instance:
\begin{verbatim}
{ dup 0= abort"Division by zero" / } : safe/
5 0 safe/ .
\end{verbatim}
prints ``{\tt safe/: Division by zero}'', without the usual ``{\tt ok}''. The stack is cleared in the process.
Incidentally, when the Fift interpreter encounters an unknown word that cannot be parsed as an integer literal, an exception with the message ``{\tt -?}'' is thrown, with the effect indicated above, including the stack being cleared.
\mysection{Dictionary, interpreter, and compiler}\label{s:dict.compiler}
In this chapter we present several specific Fift words for dictionary manipulation and compiler control. The ``compiler'' is the part of the Fift interpreter that builds lists of word references (represented by {\em WordList\/} stack values) from word names; it is activated by the primitive ``{\tt \{}'' employed for defining blocks as explained in~\ptref{p:colon.def} and~\ptref{p:blocks}.
Most of the information included in this chapter is rather sophisticated and may be skipped during a first reading. However, the techniques described here are heavily employed by the Fift assembler, used to compile TVM code. Therefore, this section is indispensable if one wishes to understand the current implementation of the Fift assembler.
\mysubsection{The state of the Fift interpreter}\label{sp:fift.state}
The state of the Fift interpreter is controlled by an internal integer variable called {\tt state}, currently unavailable from Fift itself. When {\tt state} is zero, all words parsed from the input (i.e., the Fift source file or the standard input in the interactive mode) are looked up in the dictionary and immediately executed afterwards. When {\tt state} is positive, the words found in the dictionary are not executed. Instead, they (or rather the references to their current definitions) are {\em compiled}, i.e., added to the end of the {\em WordList\/} being constructed.
Typically, {\tt state} equals the number of the currently open blocks. For instance, after interpreting ``{\tt \{ 0= \{ ."zero"}'' the {\tt state} variable will be equal to two, because there are two nested blocks. The {\em WordList\/} being constructed is kept at the top of the stack.
The primitive ``{\tt \{}'' simply pushes a new empty {\em WordList\/} into the stack, and increases {\tt state} by one. The primitive ``{\tt \}}'' throws an exception if {\tt state} is already zero; otherwise it decreases {\tt state} by one, and leaves the resulting {\em WordList\/} in the stack, representing the block just constructed.\footnote{The word {\tt \}} also transforms this {\em WordList\/} into a {\em WordDef}, which has a different type tag and therefore is a different Fift value, even if the same underlying C++ object is used by the C++ implementation.} After that, if the resulting value of {\tt state} is non-zero, the new block is compiled as a literal (unnamed constant) into the encompassing block.
\mysubsection{Active and ordinary words}\label{p:active.words}
All dictionary words have a special flag indicating whether they are {\em active\/} words or {\em ordinary\/} words. By default, all words are ordinary. In particular, all words defined with the aid of ``{\tt :}'' and {\tt constant} are ordinary.
When the Fift interpreter finds a word definition in the dictionary, it checks whether it is an ordinary word. If it is, then the current word definition is either executed (if {\tt state} is zero) or ``compiled'' (if {\tt state} is greater than zero) as explained in~\ptref{sp:fift.state}.
On the other hand, if the word is active, then it is always executed, even if {\tt state} is positive. An active word is expected to leave some values $x_1$ \dots $x_n$ $n$ $e$ in the stack, where $n\geq 0$ is an integer, $x_1\dots x_n$ are $n$ values of arbitrary types, and $e$ is an execution token (a value of type {\em WordDef\/}). After that, the interpreter performs different actions depending on {\tt state}: if {\tt state} is zero, then $n$ is discarded and $e$ is executed, as if a {\tt nip execute} phrase were found. If {\tt state} is non-zero, then this collection is ``compiled'' in the current {\em WordList} (located immediately below $x_1$ in the stack) in the same way as if the {\tt (compile)} primitive were invoked. This compilation amounts to adding some code to the end of the current {\em WordList\/} that would push $x_1$, \dots, $x_n$ into the stack when invoked, and then adding a reference to $e$ (representing a delayed execution of $e$). If $e$ is equal to the special value {\tt 'nop}, representing an execution token that does nothing when executed, then this last step is omitted.
\mysubsection{Compiling literals}
When the Fift interpreter encounters a word that is absent from the dictionary, it invokes the primitive {\tt (number)} to attempt to parse it as an integer or fractional literal. If this attempt succeeds, then the special value {\tt 'nop} is pushed, and the interpretation proceeds in the same way as if an active word were encountered. In other words, if {\tt state} is zero, then the literal is simply left in the stack; otherwise, {\tt (compile)} is invoked to modify the current {\em WordList\/} so that it would push the literal when executed.
\mysubsection{Defining new active words}\label{p:def.active}
New active words are defined similarly to new ordinary words, but using ``{\tt ::}'' instead of ``{\tt :}''. For instance,
\begin{verbatim}