Skip to main content
Author: Nikolai Durov
Date: July 4, 2019
: Original whitepaper, PDF

​
Introduction

This document provides a brief description of Fift, a stack-based general-purpose programming language optimized for creating, debugging, and managing TON Blockchain smart contracts. Fift has been specifically designed to interact with the TON Virtual Machine (TON VM or TVM) and the TON Blockchain. In particular, it offers native support for 257-bit integer arithmetic and TVM cell manipulation shared with TVM, as well as an interface to the Ed25519-based cryptography employed by the TON Blockchain. A macro assembler for TVM code, useful for writing new smart contracts, is also included in the Fift distribution. Being a stack-based language, Fift is not unlike Forth. Because of the brevity of this text, some knowledge of Forth might be helpful for understanding Fift.1 However, there are significant differences between the two languages. For instance, Fift enforces runtime type-checking, and keeps values of different types (not only integers) in its stack. A list of words (built-in functions, or primitives) defined in Fift, along with their brief descriptions, is presented in Appendix A. Please note that the current version of this document describes a preliminary test version of Fift; some minor details are likely to change in the future.

​
Contents

  1. Overview
  2. Fift basics
    1. List of Fift stack value types
    2. Comments
    3. Terminating Fift
    4. Simple integer arithmetic
    5. Stack manipulation words
    6. Defining new words
    7. Named constants
    8. Integer and fractional constants, or literals
    9. String literals
    10. Simple string manipulation
    11. Boolean expressions, or flags
    12. Integer comparison operations
    13. String comparison operations
    14. Named and unnamed variables
    15. Tuples and arrays
    16. Lists
    17. Atoms
    18. Command line arguments in script mode
  3. Blocks, loops, and conditionals
    1. Defining and executing blocks
    2. Conditional execution of blocks
    3. Simple loops
    4. Loops with an exit condition
    5. Recursion
    6. Throwing exceptions
  4. Dictionary, interpreter, and compiler
    1. The state of the Fift interpreter
    2. Active and ordinary words
    3. Compiling literals
    4. Defining new active words
    5. Defining words and dictionary manipulation
    6. Dictionary lookup
    7. Creating and manipulating word lists
    8. Custom defining words
  5. Cell manipulation
    1. Slice literals
    2. Builder primitives
    3. Slice primitives
    4. Cell hash operations
    5. Bag-of-cells operations
    6. Binary file I/O and Bytes manipulation
  6. TON-specific operations
    1. Ed25519 cryptography
    2. Smart-contract address parser
    3. Dictionary manipulation
    4. Invoking TVM from Fift
  7. Using the Fift assembler
    1. Loading the Fift assembler
    2. Fift assembler basics
    3. Pushing integer constants
    4. Immediate arguments
    5. Immediate continuations
    6. Control flow: loops and conditionals
    7. Macro definitions
    8. Larger programs and subroutines
  8. References
  9. Appendix A: List of Fift words

​
1 Overview

Fift is a simple stack-based programming language designed for testing and debugging the TON Virtual Machine and the TON Blockchain, but potentially useful for other purposes as well. When Fift is invoked (usually by executing a binary file called 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 -s, in which all command line arguments except the first one are passed to the Fift program by means of the variables $n and $#. 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 type tag, which unambiguously determines the type of the value kept in the corresponding stack entry. The types of values supported by Fift include Integer (representing signed 257-bit integers), Cell (representing a TVM cell, which consists of up to 1023 data bits and up to four references to other cells), Slice (a partial view of a Cell used for parsing cells), and Builder (used for building new cells). These data types (and their implementations) are shared with 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 runvmcode). In addition to the data types shared with TVM, Fift introduces some unique data types, such as Bytes (arbitrary byte sequences), String (UTF-8 strings), WordList, and 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 Object), provided they are derived from C++ class td::CntObject in the current implementation. Fift source files and libraries are usually kept in text files with the suffix .fif. A search path for libraries and included files is passed to the Fift executable either in a -I command line argument or in the FIFTPATH environment variable. If neither is set, the default library search path /usr/lib/fift is used. On startup, the standard Fift library is read from the file 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 dictionary, containing words — or, more precisely, word definitions — that correspond both to builtin primitives and functions and to user-defined functions *. 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 (primitives) are already defined (by some C++ code in the current implementation); other words are defined in the standard library 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 vocabularies, or namespaces; 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 *. 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 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 Integer and pushed into the stack. For instance, if we invoke Fift, type 2 3 + . (and press Enter), Fift first pushes an Integer constant equal to 2 into its stack, followed by another integer constant equal to 3. After that, the built-in primitive + 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, . is a primitive that prints the decimal representation of the top-of-stack Integer, followed by a space. As a result, we observe "5 ok" printed by the Fift interpreter into the standard output. The string "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 A.

​
2 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 A 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.

​
2.1 List of Fift stack value types

Currently, the values of the following data types can be kept in a Fift stack: 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 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 Object.

​
2.2 Comments

Fift recognizes two kinds of comments:
  • "// " (which must be followed by a space) opens a single-line comment until the end of the line, and /* defines a multi-line comment until */. Both words // and /* are defined in the standard Fift library (Fift.fif).

​
2.3 Terminating Fift

The word 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 halt, which terminates Fift with the given exit code (passed as an Integer at the top of the stack). In contrast, quit does not quit to the operating system, but rather exits to the top level of the Fift interpreter.

​
2.4 Simple integer arithmetic

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 2.8 in more detail). Apart from that, several integer arithmetic primitives are defined: In addition, the word . may be used to print the decimal representation of an Integer passed at the top of the stack (followed by a single space), and "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,
computes 7 − 4 = 3 and prints "3 ok", and
computes 2 + 3 · 4 = 14 and (2 + 3) · 4 = 20, and prints "14 20 ok".

​
2.5 Stack manipulation words

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: For instance, "5 dup * ." will compute 5 · 5 = 25 and print "25 ok". One can use the word “.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,
prints
When Fift does not know how to print a stack value of an unknown type, it instead prints ???.

​
2.6 Defining new words

In its simplest form, defining new Fift words is very easy and can be done with the aid of three special words: {, }, and :. One simply opens the definition with { (necessarily followed by a space), then lists all the words that constitute the new definition, then closes the definition with } (also followed by a space), and finally assigns the resulting definition (represented by a WordDef value in the stack) to a new word by writing : <new-word-name>. For instance,
defines a new word square, which executes dup and * when invoked. In this way, typing 5 square becomes equivalent to typing 5 dup *, and produces the same result (25):
prints "25 ok". One can also use the new word as a part of new definitions:
prints "243 ok", which indeed is 3^5. If the word indicated after : 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 square after we have already defined **5 as above, **5 will continue to use the original definition of square.

​
2.7 Named constants

One can define (named) constants — i.e., words that push a predefined value when invoked—by using the defining word constant instead of the defining word : (colon). For instance,
defines a constant Gram equal to Integer 10^9. In other words, 1000000000 will be pushed into the stack whenever Gram is invoked:
prints "2000000000 ok". Of course, one can use the result of a computation to initialize the value of a constant:
prints "1000000 ok". The value of a constant does not necessarily have to be an Integer. For instance, one can define a string constant in the same way:
prints "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 2constant. For instance:
defines a new word 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 =: and 2=: instead of constant and 2constant:
produces
If one wants to recover the execution-time value of such a “constant”, one can prefix the name of the constant with the word @':
produces (3, 9) ok. The drawback of this approach is that @' has to look up the current definition of constants x and y in the dictionary each time showxy is executed. Variables provide a more efficient way to achieve similar results.

​
2.8 Integer and fractional constants, or literals

Fift recognizes unnamed integer constants (called literals to distinguish them from named constants) in decimal, binary, and hexadecimal formats. Binary literals are prefixed by 0b, hexadecimal literals are prefixed by 0x, and decimal literals do not require a prefix. For instance, 0b1011, 11, and 0xb represent the same integer (11). An integer literal may be prefixed by a minus sign - to change its sign; the minus sign is accepted both before and after the 0x and 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 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 /, then Fift interprets it as a fractional literal and represents it by two Integer’s p and q in the stack, the numerator p and the denominator q. For instance, -17/12 pushes −17 and 12 into the Fift stack (being thus equivalent to -17 12), and -0x11/0b1100 does the same thing. Decimal, binary, and hexadecimal fractions, such as 2.39 or -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, 2.39 is equivalent to 239 100, and -0x11.ef is equivalent to -0x11ef 0x100. Such a representation of fractions is especially convenient for using them with the scaling primitive */ 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 nanotons, we can define some helper words:
and then write 2.39 Gram*/ or 17/12 Gram*/ instead of integer literals 2390000000 or 1416666667. If one needs to use such Gram literals often, one can introduce a new active prefix word GR$ as follows:
makes GR$3, GR$2.39, and GR$17/12 equivalent to integer literals 3000000000, 2390000000, and 1416666667, respectively. Such values can be printed in similar form by means of the following words:
produces GR$-17.239 ok. The above definitions make use of tricks explained in later portions of this document (especially Chapter 4). We can also manipulate fractions by themselves by defining suitable “rational arithmetic words”:
will output "31/30 ok", indicating that 1.7 − 2/3 = 31/30. Here "._" is a variant of "." that does not print a space after the decimal representation of an Integer.

​
2.9 String literals

String literals are introduced by means of the prefix word ", which scans the remainder of the line until the next " character, and pushes the string thus obtained into the stack as a value of type String. For instance, “Hello, world!” pushes the corresponding String into the stack:

​
2.10 Simple string manipulation

The following words can be used to manipulate strings: For instance, ."", "" type, 42 emit, and char * emit are four different ways to output a single asterisk.

​
2.11 Boolean expressions, or flags

Fift does not have a separate value type for representing boolean values. Instead, any non-zero Integer can be used to represent truth (with −1 being the standard representation), while a zero Integer represents falsehood. Comparison primitives normally return −1 to indicate success and 0 otherwise. Constants true and false can be used to push these special integers into the stack: If boolean values are standard (either 0 or −1), they can be manipulated by means of bitwise logical operations and, or, xor, not. Otherwise, they must first be reduced to the standard form using 0<>:

​
2.12 Integer comparison operations

Several integer comparison operations can be used to obtain boolean values: Example:
prints "-1 ok", because 2 is less than 3. A more convoluted example:
prints "true false false ok".

​
2.13 String comparison operations

Strings can be lexicographically compared by means of the following words:

​
2.14 Named and unnamed variables

In addition to constants introduced in 2.7, Fift supports variables, which are a more efficient way to represent changeable values. For instance, the last two code fragments of 2.7 could have been written with the aid of variables instead of constants as follows:
producing the same output as before:
The phrase variable x creates a new Box, i.e., a memory location that can be used to store exactly one value of any Fift-supported type, and defines x as a constant equal to this Box: The value currently stored in a Box may be fetched by means of word @ (pronounced “fetch”), and modified by means of word ! (pronounced “store”): Several auxiliary words exist that can modify the current value in a more sophisticated fashion: In this way we can implement a simple counter:
produces
After these definitions are in place, we can even forget the definition of counter by means of the phrase forget counter. Then the only way to access the value of this variable is by means of reset-counter and next-counter. Variables are usually created by variable with no value, or rather with a Null value. If one wishes to create initialized variables, one can use the phrase box constant:
prints "18 ok". One can even define a special defining word for initialized variables, if they are needed often:
prints "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 @. 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:
prints "( 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 4.8, and use this word to define both a getter and a setter at the same time:
show up show right show up show reflect show produces

​
2.15 Tuples and arrays

Fift also supports Tuples, i.e., immutable ordered collections of arbitrary values of stack value types. When a Tuple t consists of values x1, ..., xn (in that order), we write t = (x1, ... , xn). The number n is called the length of Tuple t; it is also denoted by |t|. Tuples of length two are also called pairs, tuples of length three are triples. For instance, both
and
construct and print triple (2, 3, 9):
Notice that the components of a Tuple are not necessarily of the same type, and that a component of a Tuple can also be a Tuple:
produces
Once a Tuple has been constructed, we can extract any of its components, or completely unpack the Tuple into the stack: For instance, we can access individual elements and rows of a matrix:
produces
Notice that Tuples are somewhat similar to arrays of other programming languages, but are immutable: we cannot change one individual component of a Tuple. If we still want to create something like an array, we need a Tuple of Box’es: For instance,
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:

​
2.16 Lists

Lisp-style lists can also be represented in Fift. First of all, two special words are introduced to manipulate values of type Null, used to represent the empty list (not to be confused with the empty Tuple): After that, cons and uncons are defined as aliases for pair and unpair: For instance,
produces
Notice that the three-element list (2 3 9) is distinct from the triple (2, 3, 9).

​
2.17 Atoms

An Atom is a simple entity uniquely identified by its name. Atom’s can be used to represent identifiers, labels, operation names, tags, and stack markers. Fift offers the following words to manipulate Atom’s: For instance,
creates and prints the list
which is the Lisp-style representation of arithmetical expression 2 + 3 · 4. An interpreter for such expressions might use eq? to check the operation sign:
prints
If we load Lisp.fif to enable Lisp-style list syntax, we can enter
with the same result as before. The word (, defined in Lisp.fif, uses an anonymous Atom created by anon to mark the current stack position, and then ) builds a list from several top stack entries, scanning the stack until the anonymous Atom marker is found:

​
2.18 Command line arguments in script mode

The Fift interpreter can be invoked in script mode by passing -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 -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 $n and $#: Additionally, if the very first line of a Fift source file begins with the two characters "#!", this line is ignored. In this way simple Fift scripts can be written in a *ix system. For instance, if
is saved into a file cmdline.fif in the current directory, and its execution bit is set (e.g., by chmod 755 cmdline.fif), then it can be invoked from the shell or any other program, provided the Fift interpreter is installed as /usr/bin/fift, and its standard library Fift.fif is installed as /usr/lib/fift/Fift.fif:
prints
when invoked from a *ix shell such as the Bourne–again shell (Bash).

​
3 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.

​
3.1 Defining and executing blocks

A block is normally defined using the special words { and }. Roughly speaking, all words listed between { and } constitute the body of a new block, which is pushed into the stack as a value of type WordDef. A block may be stored as a definition of a new Fift word by means of the defining word : as explained in 2.6, or executed by means of the word execute:
prints "34 ok", being essentially equivalent to "17 2 * .". A slightly more convoluted example:
applies “anonymous function” x → 2x twice to 17, and prints the result 2 · (2 · 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 ' recovers the current definition of a word. Namely, the construct ' <word-name> pushes the execution token equivalent to the current definition of the word <word-name>. For instance,
is equivalent to dup, and
defines duplicate as a synonym for (the current definition of) dup. Alternatively, we can duplicate a block to define two new words with the same definition:
defines both square and **2 to be equivalent to dup *.

​
3.2 Conditional execution of blocks

Conditional execution of blocks is achieved using the words if, ifnot, and cond: For instance, the last example in 2.12 can be more conveniently rewritten as
still resulting in "true false false ok". Notice that blocks can be arbitrarily nested, as already shown in the previous example. One can write, for example,
to obtain "negative ok", because −17 is negative.

​
3.3 Simple loops

The simplest loops are implemented by times: For instance,
computes and prints 10^70. We can use this kind of loop to implement a simple factorial function:
prints "120 ok", because 5! = 1 · 2 · 3 · 4 · 5 = 120. This loop can be modified to compute Fibonacci numbers instead:
computes the sixth Fibonacci number F6 = 13.

​
3.4 Loops with an exit condition

More sophisticated loops can be created with the aid of until and while: For instance, we can compute the first two Fibonacci numbers greater than 1000:
prints "1597 2584 ok". We can use this word to compute the first 70 decimal digits of the golden ratio φ = (1 + √5) / 2 ≈ 1.61803:
prints "161803 ... 2604 ok".

​
3.5 Recursion

Notice that, whenever a word is mentioned inside a {...} block, the current (compile-time) definition is included in the WordList being created. In this way we can refer to the previous definition of a word while defining a new version of it:
produces "number 2 number 3 5 number 8 ok". Notice that print-sum continues to use the original definition of ".", but print-next already uses the modified ".". 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
will fail to compile, because fact happens to be an undefined word when the definition is compiled. A simple way around this obstacle is to use the word @' that looks up the current definition of the next word during the execution time and then executes it, similarly to what we already did before:
produces "120 ok", as expected. However, this solution is rather inefficient, because it uses a dictionary lookup each time fact is recursively executed. We can avoid this dictionary lookup by using variables:
This somewhat longer definition of the factorial avoids dictionary lookups at execution time by introducing a special variable 'fact to hold the final definition of the factorial. Then, fact is defined to execute whatever WordDef is currently stored in '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 'fact !, which replaces the more customary phrase : fact. We could rewrite the above definition by using special “getter” and “setter” words for vector variable ‘fact as we did for variables in 2.14:
If we need to introduce a lot of recursive and mutually-recursive definitions, we might first introduce a custom defining word for simultaneously defining both the “getter” and the “setter” words for anonymous vector variables, similarly to what we did before:
The first three lines of this fragment define fact and :fact essentially in the same way they had been defined in the first four lines of the previous fragment. If we wish to make fact unchangeable in the future, we can add a forget :fact line once the definition of the factorial is complete:
Alternatively, we can modify the definition of vector-set in such a way that :fact would forget itself once it is invoked:
However, some vector variables must be modified more than once, for instance, to modify the behavior of the comparison word less in a merge sort algorithm:
producing the following output:

​
3.6 Throwing exceptions

Two built-in words are used to throw exceptions: The exception thrown by these words is represented by the C++ exception 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:
prints "safe/: Division by zero", without the usual "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 "-?" is thrown, with the effect indicated above, including the stack being cleared.

​
4 Dictionary, interpreter, and compiler

In this chapter we present several specific Fift word’s for dictionary manipulation and compiler control. The “compiler” is the part of the Fift interpreter that builds lists of word references (represented by WordList stack values) from word names; it is activated by the primitive { employed for defining blocks as explained in 2.6 and 3.1. 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.

​
4.1 The state of the Fift interpreter

The state of the Fift interpreter is controlled by an internal integer variable called state, currently unavailable from Fift itself. When 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 state is positive, the words found in the dictionary are not executed. Instead, they (or rather the references to their current definitions) are compiled, i.e., added to the end of the WordList being constructed. Typically, state equals the number of the currently open blocks. For instance, after interpreting { 0= { ."zero" the state variable will be equal to two, because there are two nested blocks. The WordList being constructed is kept at the top of the stack. The primitive { simply pushes a new empty WordList into the stack, and increases state by one. The primitive } throws an exception if state is already zero; otherwise it decreases state by one, and leaves the resulting WordList in the stack, representing the block just constructed. After that, if the resulting value of state is non-zero, the new block is compiled as a literal (unnamed constant) into the encompassing block.

​
4.2 Active and ordinary words

All dictionary words have a special flag indicating whether they are active words or ordinary words. By default, all words are ordinary. In particular, all words defined with the aid of ":" and 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 state is zero) or “compiled” (if state is greater than zero) as explained in 4.1. On the other hand, if the word is active, then it is always executed, even if state is positive. An active word is expected to leave some values x1 ... xn n e in the stack, where n ≥ 0 is an integer, x1 ... xn are n values of arbitrary types, and e is an execution token (a value of type WordDef). After that, the interpreter performs different actions depending on state: if state is zero, then n is discarded and e is executed, as if a nip execute phrase were found. If state is non-zero, then this collection is “compiled” in the current WordList (located immediately below x1 in the stack) in the same way as if the (compile) primitive were invoked. This compilation amounts to adding some code to the end of the current WordList that would push x1, ... , xn 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 'nop, representing an execution token that does nothing when executed, then this last step is omitted.

​
4.3 Compiling literals

When the Fift interpreter encounters a word that is absent from the dictionary, it invokes the primitive (number) to attempt to parse it as an integer or fractional literal. If this attempt succeeds, then the special value 'nop is pushed, and the interpretation proceeds in the same way as if an active word were encountered. In other words, if state is zero, then the literal is simply left in the stack; otherwise, (compile) is invoked to modify the current WordList so that it would push the literal when executed.

​
5.4 Defining new active words

New active words are defined similarly to new ordinary words, but using :: instead of :. For instance,
defines the active word say, which scans the next blank-separated word after itself and compiles it as a literal along with a reference to the current definition of type into the current WordList (if state is non-zero, i.e., if the Fift interpreter is compiling a block). When invoked, this addition to the block will push the stored string into the stack and execute type, thus printing the next word after say. On the other hand, if state is zero, then these two actions are performed by the Fift interpreter immediately. In this way,
will print "hello3 ok", while
will print "hello3 hello6 ok". Of course, a block may be used to represent the required action instead of ' type. For instance, if we want a version of say that prints a space after the stored word, we can write
to obtain "hello 3 hello 6 ok". Incidentally, the words " (introducing a string literal) and ." (printing a string literal) can be defined as follows:
The new defining word "::_" defines an active prefix word, i.e., an active word that does not require a space afterwards.

​
4.5 Defining words and dictionary manipulation

Defining words are words that define new words in the Fift dictionary. For instance, :, ::_, and constant are defining words. All of these defining words might have been defined using the primitive (create); in fact, the user can introduce custom defining words if so desired. Let us list some defining words and dictionary manipulation words: Notice that most of the above words might have been defined in terms of (create):

​
4.6 Dictionary lookup

The following words can be used to look up words in the dictionary:

​
4.7 Creating and manipulating word lists

In the Fift stack, lists of references to word definitions and literals, to be used as blocks or word definitions, are represented by the values of the type WordList. Some words for manipulating WordList’s include:

​
4.8 Custom defining words

The word does is actually defined in terms of simpler words: ’
It is especially useful for defining custom defining words. For instance, constant and 2constant may be defined with the aid of does and create:
Of course, non-trivial actions may be performed by the words defined by means of such custom defining words. For instance,
will print "hello unknown error ok", because hello is defined by means of a custom defining word says to print "hello" whenever invoked, and similarly error prints "unknown error" when invoked. The above definitions are essentially equivalent to
However, custom defining words may perform more sophisticated actions when invoked, and process their arguments at compile time. For instance, the message can be computed in a non-trivial fashion:
defines word hw, which prints "Hello, world!" when invoked. The string with this message is computed once at compile time (when says is invoked), not at execution time (when hw is invoked).

​
5 Cell manipulation

We have discussed the basic Fift primitives not related to TVM or the TON Blockchain so far. Now we will turn to TON-specific words, used to manipulate Cells.

​
5.1 Slice literals

Recall that a (TVM) Cell consists of at most 1023 data bits and at most four references to other Cell’s, a Slice is a read-only view of a portion of a Cell, and a Builder is used to create new Cell’s. Fift has special provisions for defining Slice literals (i.e., unnamed constants), which can also be transformed into Cell’s if necessary. Slice literals are introduced by means of active prefix words x{ and b{: In this way, b{00011101} and x{1d} both push the same Slice consisting of eight data bits and no references. Similarly, b{111010} and x{EA_} push the same Slice consisting of six data bits. An empty Slice can be represented as b{} or x{}. If one wishes to define constant Slice’s with some Cell references, the following words might be used:

​
5.2 Builder primitives

The following words can be used to manipulate Builder’s, which can later be used to construct new Cell’s: The resulting Builder may be inspected by means of the non-destructive stack dump primitive .s, or by the phrase b> <s csr.. For instance:
outputs
One can observe that .s dumps the internal representation of a Builder, with two tag bytes at the beginning (usually equal to the number of cell references already stored in the Builder, and to twice the number of complete bytes stored in the Builder, increased by one if an incomplete byte is present). On the other hand, csr. dumps a Slice (constructed from a Cell by <s) in a form similar to that used by x{ to define Slice literals. Incidentally, the word mkTest shown above (without the .s in its definition) corresponds to the TL-B constructor
and may be used to serialize values of this TL-B type.

​
5.3 Slice primitives

The following words can be used to manipulate values of the type Slice, which represents a read-only view of a portion of a Cell. In this way data previously stored into a Cell may be deserialized, by first transforming a Cell into a Slice, and then extracting the required data from this Slice step-by-step. For instance, values of the TL-B type Test discussed in 5.2
may be deserialized as follows:
prints "17239 -1000000001 ok" as expected. Of course, if one needs to check constructor tags often, a helper word can be defined for this purpose:
We can do even better with the aid of active prefix words:
A shorter but less efficient solution would be to reuse the previously defined tag?:
first outputs "x{F55AA}", and then throws an exception with the message “constructor tag mismatch”.

​
5.4 Cell hash operations

There are few words that operate on Cell’s directly. The most important of them computes the (sha256-based) representation hash of a given cell, which can be roughly described as the sha256 hash of the cell’s data bits concatenated with recursively computed hashes of the cells referred to by this cell:

​
5.5 Bag-of-cells operations

A bag of cells is a collection of one or more cells along with all their descendants. It can usually be serialized into a sequence of bytes (represented by a Bytes value in Fift) and then saved into a file or transferred by network. Afterwards, it can be deserialized to recover the original cells. The TON Blockchain systematically represents different data structures (including the TON Blockchain blocks) as a tree of cells according to a certain TL-B scheme, and then these trees of cells are routinely imported into bags of cells and serialized into binary files. Fift words for manipulating bags of cells include: For instance, the cell created in 5.2 with a value of TL-B Test type may be serialized as follows:
outputs "B5EE9C7201040101000000000900000E4A4357C46535FF ok". Here Bx. is the word that prints the hexadecimal representation of a Bytes value.

​
5.6 Binary file I/O and Bytes manipulation

The following words can be used to manipulate values of type Bytes (arbitrary byte sequences) and to read them from or write them into binary files: For instance, the bag of cells created in the example in 5.5 can be saved to disk as sample.boc as follows:
It can be loaded and deserialized afterwards (even in another Fift session) by means of file>B and B>boc:
prints "17239 -1000000001 ok". Additionally, there are several words for directly packing (serializing) data into Bytes values, and unpacking (deserializing) them afterwards. They can be combined with B>file and file>B to save data directly into binary files, and load them afterwards.

​
6 TON-specific operations

This chapter describes the TON-specific Fift words, with the exception of the words used for Cell manipulation, already discussed in the previous chapter.

​
6.1 Ed25519 cryptography

Fift offers an interface to the same Ed25519 elliptic curve cryptography used by TVM, described in Appendix A:

​
6.2 Smart-contract address parser

Two special words can be used to parse TON smart-contract addresses in human-readable (base64 or base64url) forms: A sample human-readable smart-contract address could be deserialized and displayed as follows:
outputs "-1 538fa7...0f7d 0", meaning that the specified address is in workchain −1 (the masterchain of the TON Blockchain), and that the 256-bit address inside workchain −1 is 0x538... f7d.

​
6.3 Dictionary manipulation

Fift has several words for hashmap or (TVM) dictionary manipulation, corresponding to values of TL-B type HashmapE n X as described in [4, 3.3]. These (TVM) dictionaries are not to be confused with the Fift dictionary, which is a completely different thing. A dictionary of TL-B type HashmapE n X is essentially a key-value collection with distinct n-bit keys (where 0 ≤ n ≤ 1023) and values of an arbitrary TL-B type X. Dictionaries are represented by trees of cells (the complete layout may be found in [4, 3.3]) and stored as values of type Cell or Slice in the Fift stack. Fift also offers some support for prefix dictionaries:

​
6.4 Invoking TVM from Fift

TVM can be linked with the Fift interpreter. In this case, several Fift primitives become available that can be used to invoke TVM with arguments provided from Fift. The arguments can be prepared in the Fift stack, which is passed in its entirety to the new instance of TVM. The resulting stack and the exit code are passed back to Fift and can be examined afterwards. For example, one can create an instance of TVM running some simple code as follows:
The TVM stack is initialized by three integers 2, 3, and 9 (in this order; 9 is the topmost entry), and then the Slice x{1221} containing 16 data bits and no references is transformed into a TVM continuation and executed. By consulting the TVM instructions table, we see that x{12} is the code of the TVM instruction XCHG s1 s2, and that x{21} is the code of the TVM instruction OVER. The latter is not to be confused with the Fift primitive over, which incidentally has the same effect on the stack, but applies to the Fift stack, not the TVM one. The result of the above execution is:
Here 0 is the exit code (indicating successful TVM termination), and 3 2 9 2 is the final TVM stack state. If an unhandled exception is generated during the TVM execution, the code of this exception is returned as the exit code:
produces
Notice that TVM is executed with internal logging enabled, and its log is displayed in the standard output. Simple TVM programs may be represented by Slice literals with the aid of the x{...} construct similarly to the above examples. More sophisticated programs are usually created with the aid of the Fift assembler as explained in the next chapter.

​
7 Using the Fift assembler

The Fift assembler is a short program (currently less than 30KiB) written completely in Fift that transforms human-readable mnemonics of TVM instructions into their binary representation. For instance, one could write <{ s1 s2 XCHG OVER }>s instead of x{1221} in the example discussed in 6.4, provided the Fift assembler has been loaded beforehand (usually by the phrase “Asm.fif” include).

​
7.1 Loading the Fift assembler

The Fift assembler is usually located in file Asm.fif in the Fift library directory (which usually contains standard Fift library files such as Fift.fif). It is typically loaded by putting the phrase “Asm.fif” include at the very beginning of a program that needs to use Fift assembler: The current implementation of the Fift assembler makes heavy use of custom defining words; its source can be studied as a good example of how defining words might be used to write very compact Fift programs. In the future, almost all of the words defined by the Fift assembler will be moved to a separate vocabulary (namespace). Currently they are defined in the global namespace, because Fift does not support namespaces yet.

​
7.2 Fift assembler basics

The Fift assembler inherits from Fift its postfix operation notation, i.e., the arguments or parameters are written before the corresponding instructions. For instance, the TVM assembler instruction represented as XCHG s1,s2 is represented in the Fift assembler as s1 s2 XCHG. Fift assembler code is usually opened by a special opening word, such as <{, and terminated by a closing word, such as }> or }>s. For instance,
compiles two TVM instructions XCHG s1,s2 and OVER, and returns the result as a Slice (because }>s is used). The resulting Slice is displayed by csr., yielding
One can use Appendix A and verify that x{12} is indeed the (codepage zero) code of the TVM instruction XCHG s1,s2, and that x{21} is the code of the TVM instruction OVER (not to be confused with Fift primitive over). In the future, we will assume that the Fift assembler is already loaded and omit the phrase "Asm.fif" include from our examples. The Fift assembler uses the Fift stack in a straightforward fashion, using the top several stack entries to hold a Builder with the code being assembled, and the arguments to TVM instructions. For example: In particular, note that the word OVER defined by the Fift assembler has a completely different effect from Fift primitive over. The actual action of OVER and other Fift assembler words is somewhat more complicated than that of x{21} s,. If the new instruction code does not fit into the Builder b (i.e., if b would contain more than 1023 data bits after adding the new instruction code), then this and all subsequent instructions are assembled into a new Builder ˜b, and the old Builder b is augmented by a reference to the Cell obtained from ˜b once the generation of ˜b is finished. In this way long stretches of TVM code are automatically split into chains of valid Cells containing at most 1023 bits each. Because TVM interprets a lonely cell reference at the end of a continuation as an implicit JMPREF, this partitioning of TVM code into cells has almost no effect on the execution.

​
7.3 Pushing integer constants

The TVM instruction PUSHINT x, pushing an Integer constant x when invoked, can be assembled with the aid of Fift assembler words INT or PUSHINT: Notice that the argument to PUSHINT is an Integer value taken from the Fift stack and is not necessarily a literal. For instance, <{ 239 17 * INT }>s is a valid way to assemble a PUSHINT 4063 instruction, because 239·17 = 4063. Notice that the multiplication is performed by Fift during assemble time, not during the TVM runtime. The latter computation might be performed by means of <{ 239 INT 17 INT MUL }>s:
produces
Notice that the Fift assembler chooses the shortest encoding of the PUSHINT x instruction depending on its argument x.

​
7.4 Immediate arguments

Some TVM instructions (such as PUSHINT) accept immediate arguments. These arguments are usually passed to the Fift word assembling the corresponding instruction in the Fift stack. Integer immediate arguments are usually represented by Integer’s, cells by Cell’s, continuations by Builder’s and Cell’s, and cell slices by Slice’s. For instance, 17 ADDCONST assembles TVM instruction ADDCONST 17, and x{ABCD_} PUSHSLICE assembles PUSHSLICE xABCD_:
produces
On some occasions, the Fift assembler pretends to be able to accept immediate arguments that are out of range for the corresponding TVM instruction. For instance, ADDCONST x is defined only for −128 ≤ x < 128, but the Fift assembler accepts 239 ADDCONST:
produces
We can see that "ADDCONST 239" has been tacitly replaced by PUSHINT 239 and ADD. This feature is convenient when the immediate argument to ADDCONST is itself a result of a Fift computation, and it is difficult to estimate whether it will always fit into the required range. In some cases, there are several versions of the same TVM instructions, one accepting an immediate argument and another without any arguments. For instance, there are both LSHIFT n and LSHIFT instructions. In the Fift assembler, such variants are assigned distinct mnemonics. In particular, LSHIFT n is represented by n LSHIFT#, and LSHIFT is represented by itself.

​
7.5 Immediate continuations

When an immediate argument is a continuation, it is convenient to create the corresponding Builder in the Fift stack by means of a nested <{ ... }> construct. For instance, TVM assembler instructions
can be assembled and executed by
producing
More convenient ways to use literal continuations created by means of the Fift assembler exist. For instance, the above example can be also assembled by
or even
both producing "x{710192A70AE4} ok". Incidentally, a better way of implementing the above loop is by means of REPEATEND:
or
both produce "x{7101E7A70A}" and output "10000000" after seven iterations of the loop. Notice that several TVM instructions that store a continuation in a separate cell reference (such as JMPREF) accept their argument in a Cell, not in a Builder. In such situations, the <{ ... }>c construct can be used to produce this immediate argument.

​
7.6 Control flow: loops and conditionals

Almost all TVM control flow instructions—such as IF, IFNOT, IFRET, IFNOTRET, IFELSE, WHILE, WHILEEND, REPEAT, REPEATEND, UNTIL, and UNTILEND — can be assembled similarly to REPEAT and REPEATEND in the examples of 7.5 when applied to literal continuations. For instance, TVM assembler code
which computes 3n + 1 or n/2 depending on whether its argument n is odd or even, can be assembled and applied to n = 7 by
producing
Of course, a more compact and efficient way to implement this conditional expression would be
or
both producing the same code "x{2071B093A703A4DCAB00}". Fift assembler words that can be used to produce such “high-level” conditionals and loops include IF:<{, IFNOT:<{, IFJMP:<{, }>ELSE<{, }>ELSE:, }>IF, REPEAT:<{, UNTIL:<{, WHILE:<{, }>DO<{, }>DO:, AGAIN:<{, }>AGAIN, }>REPEAT, and }>UNTIL. Their complete list can be found in the source file Asm.fif. For instance, an UNTIL loop can be created by UNTIL:<{ ... }> or <{ ... }>UNTIL, and a WHILE loop by WHILE:<{ ... }>DO<{ ... }>. If we choose to keep a conditional branch in a separate cell, we can use the <{ ... }>c construct along with instructions such as IFJMPREF:
has the same effect as the code from the previous example when executed, but it is contained in two separate cells:

​
7.7 Macro definitions

Because TVM instructions are implemented in the Fift assembler using Fift words that have a predictable effect on the Fift stack, the Fift assembler is automatically a macro assembler, supporting macro definitions. For instance, suppose that we wish to define a macro definition RANGE x y, which checks whether the TVM top-of-stack value is between integer literals x and y (inclusive). This macro definition can be implemented as follows:
which produces
Notice that GEQINT and LEQINT are themselves macro definitions defined in Asm.fif, because they do not correspond directly to TVM instructions. For instance, x GEQINT corresponds to the TVM instruction GTINT x − 1. Incidentally, the above code can be shortened by two bytes by replacing IFNOT: DROP ZERO with AND.

​
7.8 Larger programs and subroutines

Larger TVM programs, such as TON Blockchain smart contracts, typically consist of several mutually recursive subroutines, with one or several of them selected as top-level subroutines (called main() or recv_internal()). The execution starts from one of the top-level subroutines, which is free to call any of the other defined subroutines, which in turn can call whatever other subroutines they need. Such TVM programs are implemented by means of a selector function, which accepts an extra integer argument in the TVM stack; this integer selects the actual subroutine to be invoked. Before execution, the code of this selector function is loaded both into special register c3 and into the current continuation cc. The selector of the main function (usually zero) is pushed into the initial stack, and the TVM execution is started. Afterwards a subroutine can be invoked by means of a suitable TVM instruction, such as CALLDICT n, where n is the (integer) selector of the subroutine to be called. The Fift assembler offers several words facilitating the implementation of such large TVM programs. In particular, subroutines can be defined separately and assigned symbolic names (instead of numeric selectors), which can be used to call them afterwards. The Fift assembler automatically creates a selector function from these separate subroutines and returns it as the top-level assembly result. Here is a simple example of such a program consisting of several subroutines. This program computes the complex number $$(5 + i)^4 * (239 − i)$:
This program produces:
Some observations and comments based on the previous example follow:
  • A TVM program is opened by PROGRAM{ and closed by either }END>c, which returns the assembled program as a Cell, or }END>s, which returns a Slice.
  • A new subroutine is declared by means of the phrase NEWPROC <name>. This declaration assigns the next positive integer as a selector for the newly-declared subroutine, and stores this integer into the constant <name>. For instance, the above declarations define add, sub, and mul as integer constants equal to 1, 2, and 3, respectively.
  • Some subroutines are pre-declared and do not need to be declared again by NEWPROC. For instance, main is a subroutine identifier bound to the integer constant (selector) 0.
  • Other predefined subroutine selectors such as recv_internal (equal to 0) or recv_external (equal to −1), useful for implementing TON Blockchain smart contracts, can be declared by means of constant (e.g., -1 constant recv_external).
  • A subroutine can be defined either with the aid of the word PROC, which accepts the integer selector of the subroutine and the Slice containing the code for this subroutine, or with the aid of the construct selector PROC:<{ ... }>, convenient for defining larger subroutines.
  • CALLDICT and JMPDICT instructions may be assembled with the aid of the words CALL and JMP, which accept the integer selector of the subroutine to be called as an immediate argument passed in the Fift stack.
  • The current implementation of the Fift assembler collects all subroutines into a dictionary with 14-bit signed integer keys. Therefore, all subroutine selectors must be in the range −213...213−1−2^{13} ... 2^{13 − 1}.
  • If a subroutine with an unknown selector is called during runtime, an exception with code 11 is thrown by the code automatically inserted by the Fift assembler. This code also automatically selects codepage zero for instruction encoding by means of a SETCP0 instruction.
  • The Fift assembler checks that all subroutines declared by NEWPROC are actually defined by PROC or PROC:<{ before the end of the program. It also checks that a subroutine is not redefined.
One should bear in mind that very simple programs (including the simplest smart contracts) may be made more compact by eliminating this general subroutine selection machinery in favor of custom subroutine selection code and removing unused subroutines. For instance, the above example can be transformed into
which produces

​
References

  • L. Brodie, Starting Forth: Introduction to the FORTH Language and Operating System for Beginners and Professionals, 2nd edition, Prentice Hall, 1987. Available at https://www.forth.com/starting-forth/.
  • L. Brodie, Thinking Forth: A language and philosophy for solving problems, Prentice Hall, 1984. Available at http://thinking-forth.sourceforge.net/.
  • N. Durov, Telegram Open Network, 2017.
  • N. Durov, Telegram Open Network Virtual Machine, 2018.
  • N. Durov, Telegram Open Network Blockchain, 2018.

​
Appendix A: List of Fift words

This Appendix provides an alphabetic list of almost all Fift words—including primitives and definitions from the standard library Fift.fif, but excluding Fift assembler words defined in Asm.fif (because the Fift assembler is simply an application from the perspective of Fift). Some experimental words have been omitted from this list. Other words may have been added to or removed from Fift after this text was written. The list of all words available in your Fift interpreter may be inspected by executing words. Each word is described by its name, followed by its stack notation in parentheses, indicating several values near the top of the Fift stack before and after the execution of the word; all deeper stack entries are usually assumed to be left intact. After that, a text description of the word’s effect is provided. If the word has been discussed in a previous section of this document, a reference to this section is included. Active words and active prefix words that parse a portion of the input stream immediately after their occurrence are listed here in a modified way. Firstly, these words are listed alongside the portion of the input that they parse; the segment of each entry that is actually an emphasized Fift word. Secondly, their stack effect is usually described from the user’s perspective, and reflects the actions performed during the execution phase of the encompassing blocks and word definitions. For example, the active prefix word B{, used for defining Bytes literals, is listed as B{<hex-digits>}, and its stack effect is shown as ( – B) instead of ( – B 1 e), even though the real effect of the execution of the active word B{ during the compilation phase of an encompassing block or word definition is the latter one.