Byte-machine for the fort (and not only) in Indian (Part 4)
And again I overestimated the volume of the article! Planned that this will be the final article, where we will make the compiler and perform testing. But the volume was great, and I decided to split the article into two.
In this article we will do almost all the basic functions of the compiler. It will come to life already, and it will be possible to write, compile and execute quite serious code. And we will do the testing in the next part. (By the way, the previous parts: one , two , three ).
I write for the first time on Habré, perhaps it’s not always good. In my opinion, articles 2, 3 turned out pretty dry, a lot of code, a little description. This time I will try to do differently, focus on the description of the ideas themselves. Well, the code ... the code, of course, will be! Who wants to understand thoroughly, such an opportunity will be. In many cases, I will put the code under the spoiler. And, of course, you can always look at the full source on github.
The compiler will continue to write some time in assembler, but then we will go to the fort and continue to write the compiler on itself. This will resemble Baron Munchausen, who pulled himself by the hair out of the swamp. But, for a start, I will tell in general how the compiler works on the fort. Welcome under the cut!
How the compiler works
The memory in the fort consists of a continuous fragment in which the dictionary entries are sequentially arranged. After they are finished, there is a free area of memory. The first free byte is indicated by the variable h. There is also the frequently used word here, which pushes onto the stack the address of the first free byte, it is determined very simply:
: here h @ ;
It is worth mentioning the word allot, which reserves the specified number of bytes by moving the pointer h. The word allot can be defined as:
: allot h +! ;
In fact, the compiler uses a special interpreter mode plus some special words. So, in one sentence, you can describe the whole principle of the compiler in the forte. In which mode the interpreter is running, the state variable determines. If it is equal to zero, then the execution mode is set, otherwise - the compilation mode. We are already familiar with the execution mode, in it the words from the input buffer are simply executed one after another. And in compilation mode, they are not executed, but compiled into memory at the pointer h. Accordingly, the pointer moves forward.
In the classical forte, the word "," is used to compile an integer value, and the word "c," is used to compile a byte. In our system, values of different widths are used (8, 16, 32, 64), therefore, we will additionally make the words “w,” and “i,”. Let's also make the word “str,” which will compile the string, taking two values from the stack — the address and the length of the string.
Special words of the compiler are used to form control structures. These are the words if, then, do, loop, and others. These words are executed even in compilation mode. For example, the word if at execution compiles a byte conditional jump command (? Nbranch). To let the system know which words need to be executed in compilation mode, and not to compile, the immediate flag (attribute) is used. We already have it in the flags field of the dictionary entry. In source code in assembler, it is called f_immediate. To set this flag, use the word immediate. It has no parameters, the immediate flag is set on the last word in the dictionary.
And now let's move from theory to practice!
Training
In the beginning, you need to do some simple byte commands that we need. Here they are: move (copy a memory area), fill (fill a memory area), bit operations (and, or, xor, invert), bit shift commands (rshift, lshift). Let's do the same rpick (this is the same as pick, only works with the return stack, not the data stack).
These commands are very simple, here is their code.
b_move = 0x66
bcmd_move: pop rcx
pop rdi
pop rsi
repz movsb
jmp _next
b_fill = 0x67
bcmd_fill: pop rax
pop rcx
pop rdi
repz stosb
jmp _next
b_rpick = 0x63
bcmd_rpick: pop rcx
push [rbp + rcx * 8]
jmp _next
b_and = 0x58
bcmd_and: pop rax
and [rsp], rax
jmp _next
b_or = 0x59
bcmd_or: pop rax
or [rsp], rax
jmp _next
b_xor = 0x5A
bcmd_xor: pop rax
xor [rsp], rax
jmp _next
b_invert = 0x5B
bcmd_invert: notq [rsp]
jmp _next
b_rshift = 0x5C
bcmd_rshift: pop rcx
or rcx, rcx
jz _next
1: shrq [rsp]
dec rcx
jnz 1b
jmp _next
b_lshift = 0x5D
bcmd_lshift: pop rcx
or rcx, rcx
jz _next
1: shlq [rsp]
dec rcx
jnz 1b
jmp _next
Still need to make the word word. This is the same as blword, but a specific separator is indicated on the stack. I do not give the code, it can be found in the source code. I copied / paste the words blworld and replaced the comparison commands.
Finally we make the word syscall. With it you can do the missing system operations, for example, work with files. This solution will not work if platform independence is required. But this system is used now for tests, so let it be for now. If necessary, all operations can be redone to byte commands, it is not at all difficult. The syscall command will take from the stack 6 parameters for the system call and the call number. It will return one parameter. Parameter assignments and return values are determined by the system call number.
b_syscall = 0xFF
bcmd_syscall: sub rbp, 8
mov [rbp], r8
pop rax
pop r9
pop r8
pop r10
pop rdx
pop rsi
pop rdi
syscall
push rax
mov r8, [rbp]
add rbp, 8
jmp _next
Now let's proceed directly to the compiler.
Compiler
Create a variable h, everything is simple.
item h
h: .byte b_var0
.quad 0
We initialize its initialization in the starting line:# forth last_item context @ ! h dup 8 + swap ! quit
start: .byte b_call16
.word forth - . - 2
.byte b_call16
.word last_item - . - 2
.byte b_call16
.word context - . - 2
.byte b_get
.byte b_set
.byte b_call16
.word h - . - 2
.byte b_dup, b_num8, b_add, b_swap, b_set
.byte b_quit
Let's make the word here:
item here
.byte b_call8, h - . - 1
.byte b_get
.byte b_exit
And also the words to compile the values: "allot" and "c,", "w,", "i,", ",", "str,"
# : allot h +! ;
item allot
allot: .byte b_call8, h - . - 1, b_setp, b_exit
# : , here ! 8 allot ;
item ","
.byte b_call8, here - . - 1, b_set, b_num8, b_call8, allot - . - 1, b_exit
# : i, here i! 4 allot ;
item "i,"
.byte b_call8, here - . - 1, b_set32, b_num4, b_call8, allot - . - 1, b_exit
# : w, here w! 2 allot ;
item "w,"
.byte b_call8, here - . - 1, b_set16, b_num2, b_call8, allot - . - 1, b_exit
# : c, here c! 1 allot ;
item "c,"
.byte b_call8, here - . - 1, b_set8, b_num1, b_call8, allot - . - 1, b_exit
# : str, dup -rot dup c, here swap move 1+ h +!;
item "str,"
c_str: .byte b_dup, b_mrot, b_dup
callb c_8
callb here
.byte b_swap, b_move
callb h
.byte b_setp
.byte b_exit
And now let's make a state variable and two words to control its value: "[" and "]". Usually these words are used to accomplish something at the time of compilation. Therefore, the word "[" turns off the compilation mode, and the word "]" includes. But nothing prevents them from being used in other cases when it is necessary to turn on or turn off the compilation mode. The word "[" will be with us the first word that has the sign immediate. Otherwise, it will not be able to turn off the compilation mode, since it will be compiled and not executed.
item state
.byte b_var0
.quad 0
item "]"
.byte b_num1
callb state
.byte b_set, b_exit
item "[", f_immediate
.byte b_num0
callb state
.byte b_set, b_exit
The turn has come for the word $ compile. It will take from the stack the address of the dictionary entry and compile the specified word. In order to compile the word in the usual implementations of the fort, it is enough to apply the word "," to the address of the execution. We are much more complicated. First, there are two types of words - bytecode and machine code. The first are compiled byte, and the second - byte-command call. And secondly - we have as many as four options for the call: call8, call16, call32 and call64 command. Four? Not! When I wrote the compiler, I added 16 more to these four! :)
How did this happen? We'll have to make a small digression.
Improving the call team
When the compiler started working, I found that in many cases (but not all) the call8 command was enough. This is when the called word is within 128 bytes. I wondered - how to make it happen in almost all cases? How to put in bytes more than 256 values?
The first point I paid attention to is that in a fort the call always goes in the direction of smaller addresses. This means that you can remake the call command in such a way that it can call only smaller addresses, but by 256 bytes, not 128. It is already better.
But if I had to put a few bits somewhere ... It turns out that there is where! We have two bytes: one byte is the command, the second is the offset. But nothing interferes with a few lower bits of the command to place the higher bits of the parameter (offset). For a byte-machine, it looks as if instead of one command, there are several call commands. Yes, this way we occupy several cells of the byte-command code table with one command, but sometimes it is worth doing. The call command is one of the most used commands, so I decided to put 4 bits of offset into the command. Thus, you can make a call at a distance of 4095 bytes! This means that such a short call command will be used almost always. I placed these commands from code 0xA0 and the following lines appeared in the command table:
.quad bcmd_call8b0, bcmd_call8b1, bcmd_call8b2, bcmd_call8b3, bcmd_call8b4, bcmd_call8b5, bcmd_call8b6, bcmd_call8b7 # 0xA0
.quad bcmd_call8b8, bcmd_call8b9, bcmd_call8b10, bcmd_call8b11, bcmd_call8b12, bcmd_call8b13, bcmd_call8b14, bcmd_call8b15
The first of these byte commands simply makes a call to smaller addresses by the offset specified in the parameter (up to 255). The rest add to the parameter the corresponding offset. bcmd_call8b1 adds 256, bcmd_call8b2 adds 512, and so on. I made the first call command separately, the rest with a macro.
First team:
b_call8b0 = 0xA0
bcmd_call8b0: movzx rax, byte ptr [r8]
sub rbp, 8
inc r8
mov [rbp], r8
sub r8, rax
jmp _next
Macros and creation of other call commands:
.macro call8b N
b_call8b\N = 0xA\N
bcmd_call8b\N: movzx rax, byte ptr [r8]
sub rbp, 8
inc r8
add rax, \N * 256
mov [rbp], r8
sub r8, rax
jmp _next
.endm
call8b 1
call8b 2
call8b 3
call8b 4
call8b 5
call8b 6
call8b 7
call8b 8
call8b 9
call8b 10
call8b 11
call8b 12
call8b 13
call8b 14
call8b 15
Well, I redid the old command call8 into a call ahead, since we already make as many as 16 teams backward. To avoid confusion, I renamed it b_call8f:
b_call8f = 0x0C
bcmd_call8f: movzx rax, byte ptr [r8]
sub rbp, 8
inc r8
mov [rbp], r8
add r8, rax
jmp _next
By the way, for convenience, I made a macro, which on the assembler automatically compiles the corresponding call call back within 4095. And then I never needed :)
.macro callb adr
.if \adr > .
.error "callb do not for forward!"
.endif
.byte b_call8b0 + (. - \adr + 1) >> 8
.byte (. - \adr + 1) & 255
.endm
And now…
Compiling a command
So, we have a rather complicated command compilation algorithm. If this is a byte command, we simply compile a byte (byte command code). And if this word is already written in bytecode, you need to compile it with the call command, choosing one of the twenty. More precisely, 19, so we do not have a call ahead, and the call8f for the fort will not be used.
So the choice is this. If the offset is in the range of 0 ...- 4095, select the bcmd_call8b command with the 0xA0 code, placing the four high-order bits of the offset in the lower-order bits of the command. In this case, for the byte-machine to get the code of one of the commands bcmd_call8b0 - bcmd_call8b15.
If the back offset is greater than or equal to 4095, then we determine in which dimension the offset is placed, and use the appropriate command from call16 / 32/64. It should be borne in mind that the offset for these teams with a sign. They can trigger both forward and backward. For example, call16 can call to a distance of 32767 in both directions.
This is how the implementation turned out:
$ compile
Compiles the word. As the parameter takes the address of the dictionary entry of the compiled word. In fact, it checks the f_code flag, calculates the code address (cfa) and calls compile_b or compile_c (if the flag is set).
compile_c
Compiles a byte command. The simplest word here, on the fort is described as:
: compile_c c@ c, ;
compile_b
Receives the bytecode address on the stack and compiles its call.
test_bv
Takes from the stack an offset (with a sign) and determines how much bit should be used (1, 2, 4 or 8 bytes). Returns the value 0, 1, 2, or 3. With the help of this word, you can determine which one to use from the call16 / 32/64 commands. This word will also be useful when compiling numbers (choose from lit8 / 16/32/64).
By the way, you can start the system and "play" in the fort console with any of these words. For example:
$ ./forth
( 0 ): > 222 test_bv
( 2 ): 222 1 > drop drop
( 0 ): > 1000000 test_bv
( 2 ): 1000000 2 > drop drop
( 0 ): > -33 test_bv
( 2 ): -33 0 >
test_bvc
Takes an offset (with a sign) from the stack and determines which command to use. In fact, it checks if the offset does not lie within 0 ... -4095, and returns 0. In this case, if there is no hit in this interval, it calls test_bv.
That's all you need to compile a command.
# : test_bvc dup 0 >= over FFF <= andif0exitelse ...
item test_bvc
test_bvc: .byte b_dup, b_neg
.byte b_num0
.byte b_gteq
.byte b_over, b_neg
.byte b_lit16
.word 0xFFF
.byte b_lteq
.byte b_and
.byte b_qnbranch8, 1f - .
.byte b_num0
.byte b_exit
item test_bv
test_bv: .byte b_dup, b_lit8, 0x80, b_gteq, b_over, b_lit8, 0x7f, b_lteq, b_and, b_qnbranch8, 1f - ., b_num0
.byte b_exit
1: .byte b_dup
.byte b_lit16
.word 0x8001
.byte b_gteq
.byte b_over
.byte b_lit16
.word 0x7ffe
.byte b_lteq, b_and, b_qnbranch8, 2f - ., b_num1, b_exit
2: .byte b_dup
.byte b_lit32
.int0x80000002
.byte b_gteq
.byte b_over
.byte b_lit32
.int0x7ffffffd
.byte b_lteq, b_and, b_qnbranch8, 3f - ., b_num2, b_exit
3: .byte b_num3
.byte b_exit
# компиляция байт-кода
item compile_c
compile_c: .byte b_get8
callb c_8
.byte b_exit
# компиляция вызова байт-кода
item compile_b
compile_b: callb here
.byte b_num2, b_add
.byte b_sub
callb test_bvc
.byte b_dup
.byte b_zeq
.byte b_qnbranch8, 1f - .
.byte b_drop
.byte b_neg
.byte b_dup
.byte b_lit8, 8
.byte b_rshift
.byte b_lit8, b_call8b0
.byte b_or
callb c_8
callb c_8
.byte b_exit
1: .byte b_dup, b_num1, b_eq, b_qnbranch8, 2f - ., b_drop, b_lit8, b_call16
callb c_8
.byte b_wm
callb c_16
.byte b_exit
2: .byte b_num2, b_eq, b_qnbranch8, 3f - ., b_lit8, b_call32
callb c_8
.byte b_num3, b_sub
callb c_32
.byte b_exit
3: .byte b_lit8, b_call64
callb c_8
.byte b_lit8, 7, b_sub
callb c_64
.byte b_exit
#: $compile dup c@ 0x80andif cfa compile_c else cfa compile_b then ;
item "$compile"
_compile: .byte b_dup, b_get8, b_lit8, 0x80, b_and, b_qnbranch8, 1f - ., b_cfa
callb compile_c
.byte b_exit
1: .byte b_cfa
callb compile_b
.byte b_exit
And now we need to compile the numbers.
Compilation of number (literal)
I wrote a whole subtitle,
got ready to specifically describe the literal compilation, but it turns out there is nothing special to describe :) We have already done half of the work in the word test_bv. It remains only to call test_bv, and, depending on the result, to compile lit8 / 16/32/64, and then the corresponding value of 1, 2, 4 or 8 bytes.
We do this by defining the word compile_n
# компиляция числа
item compile_n
compile_n: callb test_bv
.byte b_dup
.byte b_zeq
.byte b_qnbranch8, 1f - .
.byte b_drop, b_lit8, b_lit8
callb c_8
callb c_8
.byte b_exit
1: .byte b_dup, b_num1, b_eq, b_qnbranch8, 2f - ., b_drop, b_lit8, b_lit16
callb c_8
callb c_16
.byte b_exit
2: .byte b_num2, b_eq, b_qnbranch8, 3f - ., b_lit8, b_lit32
callb c_8
callb c_32
.byte b_exit
3: .byte b_lit8, b_lit64
callb c_8
callb c_64
.byte b_exit
Modifying the interpreter
To compile the command and literals everything is ready. Now it needs to be embedded in the interpreter. This modification is simple. Where the command was executed, you must add a state check. If state is not null and the word does not contain an immediate flag, you need to call $ compile instead of execution. And about the same thing to do where the number is received from the input stream. If state is zero, we simply leave the number on the stack, and if not, we call compile_n.
This is the interpreter.
item interpret
interpret: .byte b_blword
.byte b_dup
.byte b_qnbranch8
.byte 0f - .
.byte b_over
.byte b_over
.byte b_find
.byte b_dup
.byte b_qnbranch8
.byte 1f - .
.byte b_mrot
.byte b_drop
.byte b_drop
callb state
.byte b_get
.byte b_qnbranch8, irpt_execute - . # если 0, поехали на исполнение
.byte b_dup, b_get8, b_lit8, f_immediate, b_and # вытащили immediate из флагов слова
.byte b_qbranch8, irpt_execute - . # если флаг установлен - на исполнение
# все сложилосьб компилируем!
callb _compile
.byte b_branch8, 2f - .
irpt_execute: .byte b_cfa # сюда попадаем, когда надо исполнять (state = 0 или immediate слова установлен)
.byte b_execute
.byte b_branch8, 2f - .
1: .byte b_drop
.byte b_over, b_over
.byte b_numberq
# проверка, что число преобразовалось
.byte b_qbranch8, 3f - . # если на стеке не 0, значит, преобразовалось и идем на метку 3
.byte b_type # иначе печатаем слово
.byte b_strp # потом диагностику
.byte 19 # это длинна сообщениЯ ниже
.ascii " : word not found!\n"
.byte b_quit # и завершаем интерпретацию
3: .byte b_nip, b_nip # удалим значения, сохраненные для печати слова (команды b_over, b_over)
# в стеке - преобразованное число
callb state # проверим, компиляция или исполнение
.byte b_get
.byte b_qnbranch8, 2f - . # если исполнение - больше ничего делать не нужно; на проверку - и выход
# компиляция числа
callb compile_n
2: # проверка стека на выход за границу
.byte b_depth # получаем глубину стека
.byte b_zlt # сравниваем, что меньше 0 (команда 0<)
.byte b_qnbranch8, interpret_ok - . # если условие ложно, то все в порЯдке, делаем переход
.byte b_strp # иначе выводим диагностику
.byte 14
.ascii "\nstack fault!\n"
.byte b_quit # и завершаем интерпретацию
interpret_ok: .byte b_branch8
.byte interpret - .
0: .byte b_drop
.byte b_exit
Now we are one step away from the compiler ...
Definition of new words (the word ":")
Now, if we set the state variable to a non-zero value, the compilation process begins. But the result will be useless, we can neither execute it, nor even find it in memory. To be able to do all this, it is necessary to issue the result of the compilation in the form of a dictionary entry. To do this, before turning on the compilation mode, you need to create a word header.
The header should contain flags, a link field and a name. Here we have a familiar story - the communication field can be 1, 2, 4, or 8 bytes. Let's make the word compile_1248, which will help us form such a field of communication. It will take two numbers on the stack - the offset and the value generated by the test_bv command.
compile_1248
# компиляция значения в один, два, четыре или восемь байт
# на стеке значение и байт, полученный test_dv
item compile_1248
compile_1248: .byte b_dup
.byte b_zeq
.byte b_qnbranch8, 1f - .
.byte b_drop
callb c_8
.byte b_exit
1: .byte b_dup, b_num1, b_eq, b_qnbranch8, 2f - .
.byte b_drop
callb c_16
.byte b_exit
2: .byte b_num2, b_eq, b_qnbranch8, 3f - .
callb c_32
.byte b_exit
3: callb c_64
.byte b_exit
Now make the word $ create. It will come in handy again and again. You can use it whenever you need to create a dictionary entry title. It will take two values from the stack - the address of the name of the word being created and its length. After the execution of this word on the stack will be the address of the dictionary entry.
$ create
# : $create here current @ @ here - test_bv dup c, compile_1248 -rot str, current @ ! ' var0 here c!;
item "$create"
create: callb here
callb current
.byte b_get, b_get
callb here
.byte b_sub
callb test_bv
.byte b_dup
callb c_8
callb compile_1248
.byte b_mrot
callb c_str
# обновим указатель на последнее слово словаря
callb current
.byte b_get, b_set
# новое слово будет содержать байт-код var0, но он будет за границей here
# с одной стороны, это для безопасности - если выполнить это слово, система не упадет
# но можно продолжить формирование слова, и этот байт затрется
# или просто сделать 1 allot и получиться слово, содержащее данные
.byte b_lit8, b_var0
callb here
.byte b_set8
.byte b_exit
The next word will take the name of the new word from the input stream using the word blword and call $ create, creating a new word with the specified name.
create_in
item "create_in"
create_in: .byte b_blword
.byte b_dup
.byte b_qbranch8
.byte 1f - .
.byte b_strp # выводим диагностику (не получили слово из входного потока)
.byte 3f - 2f # это длинна сообщениЯ ниже
2: .ascii "\ncreate_in - name not found!\n"3: .byte b_quit
1: callb create
.byte b_exit
And finally, let's make the word ":". It will create a new word with create_in and set the compilation mode; it is not set. And if installed, it gives an error. The word ":" will have an immediate indication.
word:
# : : create_in 1 state dup @ if ." : - no execute state!" then ! 110 ; immediate
item ":", f_immediate
colon: callb create_in
.byte b_num1
callb state
.byte b_dup
.byte b_get
.byte b_qnbranch8, 2f - .
.byte b_strp # выводим диагностику (не получили слово из входного потока)
.byte 4f - 3f # это длинна сообщения ниже
3: .ascii "\n: - no execute state!\n"4: .byte b_quit
2: .byte b_set
.byte b_lit8, 110
.byte b_exit
If someone looked into the code, he saw that this word does something else :)
And here 110 ???
Yes, this word also puts the number 110 on the stack, and that's why. When compiling, the various constructs must be integrated. For example, after if must be then. And the word created using ":" must end with ";". To check these conditions, the special words of the compiler put certain values on the stack and check their presence. For example, the word ":" puts the value 110, and the word ";" checks that 110 is at the top of the stack. If not, then this is an error. Hence, the control structures were not paired.
Such a check is carried out in all similar words of the compiler, so we will make for this a special word - "? Pairs". It will take two values from the stack, and give an error if they are not equal.
Also in such words it is often necessary to check whether the compilation mode is set. Let's do for this the word "? State".
? pairs? state
#: ?pairs = ifnot exit then ." \nerror: no pairs operators" quit then ;
item "?pairs"
.byte b_eq, b_qbranch8, 1f - .
.byte b_strp
.byte 3f - 2f2: .ascii "\nerror: no pairs operators"3: .byte b_quit
1: .byte b_exit
#: ?state state @ 0= ifabort" error: no compile state" then ;
item "?state"
callb state
.byte b_get, b_zeq, b_qnbranch8, 1f - .
.byte b_strp
.byte 3f - 2f2: .ascii "\nerror: no compile state"3: .byte b_quit
1: .byte b_exit
Everything! We will not compile anything else into the assembler manually anymore :)
But the compiler is not yet written to the end, so in the beginning we will have to use several non-ordinary methods ...
Prepare to compile the generated compiler by the created compiler.
For starters, you can check how the word ":" works by compiling something simple. Let's make, for example, such a word:
: ^2 dup * ;
This word is squared. But we do not have the word ";" how to be? Write the word exit instead, and it will compile. And then turn off the compilation mode with the word "[" and drop the value 110:
$ ./forth
( 0 ): > : ^2 dup * exit [ drop
( 0 ): > 4 ^2
( 1 ): 16 >
Works! Let's
continue ...
As we will continue to write the fort on the fort, we need to think about where the source code of the fort will be and when to compile. Let's make the easiest option. The source code of the fort will be placed in the source code on the assembler, in the form of a text string. And whatever he takes up extra space, we will place it immediately after the address here, in the area of free memory. Of course, we will need this area for compilation, but the speed of “runaway” interpretation will be greater than the need for a new memory. Thus, the compiled code will begin to overwrite the source on the fort, starting from the beginning, but we will no longer need it, since we have already read and used this section.
fcode: .ascii "
2 2 + . quit"
But, at the beginning of the line it is still worth putting a dozen spaces.
To make it all work, we change the start bytecode so that tib, #tib point to this line. At the end is quit to enter the usual command line of the system.
Start bytecode has become such
start: .byte b_call16
.word forth - . - 2
.byte b_call16
.word last_item - . - 2
.byte b_call16
.word context - . - 2
.byte b_get
.byte b_set
.byte b_call16
.word vhere - . - 2
.byte b_dup
.byte b_call16
.word h - . - 2
.byte b_set
.byte b_call16
.word definitions - . - 2
.byte b_call16
.word tib - . - 2
.byte b_set
.byte b_lit16
.word fcode_end - fcode
.byte b_call16
.word ntib - . - 2
.byte b_set
.byte b_call16
.word interpret - . - 2
.byte b_quit
Run!
$ ./forth
4
( 0 ): >
Fine!
And now…
Compile compiler compiler
Further we write the code in the fcode line. The first thing to do, of course, is the word ";".
: ; ?state 110 ?pairs lit8 [ blword exit find cfa c@ c, ] c, 0 state ! exit [ current @ @ dup c@ 96or swap c! drop
I will make some explanations.
?state 110 ?pairs
Here we check that the compilation state is indeed set, and there is 110 on the stack. Otherwise, there will be an interrupt by mistake.
lit8 [ blword exit find cfa c@ c, ]
This is what we compile the lit command with the exit command bytecode. I had to go into execution mode, find the word exit, get the address of the execution, and take the command code from there. All this was required because we do not yet have the word compile. If it were, instead of all this, it would be enough just to write “compile exit” :)
c, 0 state !
This will be compiled command exit at the time of execution of the word ";", and then set the interpretation mode. The word "[" cannot be used here, since it has an immediate sign and is executed now , but we need to compile such commands into the word ";" so that they turn off the compilation mode.
exit [
This we have already experienced. The word exit is compiled and compile mode is turned off. All the word ";" compiled And what else is there further?
current @ @ dup c@ 96 or swap c! drop
You need to set the immediate flag for the new word. This is exactly what this sequence does, except for the word drop. The word drop removes the forgotten 110, which placed the word ":" at the beginning of creation.
Now that's it!
Run and try.
$ ./forth
( 0 ): > : ^3 dup dup * * ;
( 0 ): > 6 ^3 .
216
( 0 ): >
There is! Here and the first word which was compiled by our compiler "on the present".
But we still have neither conditions, nor cycles, nor much else ... Let's start with a small, but very necessary to create a compiler word: immediate. It sets the immediate sign of the last word created:
: immediate current @ @ dup c@ 96or swap c! ;
A familiar sequence :) Recently, it was written by hand, no longer required.
Now we’ll do some small but useful words:
: hex 16 base ! ;
: decimal 10 base ! ;
: bl 32 ;
: tab 9 ;
: lf 10 ;
hex and decimal set the corresponding number system. The rest are constants for obtaining the corresponding character codes.
We will also make a word to copy the line with the counter
:: cmove over c @ 1 + move;
Now let's deal with the conditions. In general, if there was a word compile, it would look like this:
: if ?state compile ?nbranch8 here 0 c, 111 ; immediate
: then ?state 111 ?pairs dup here swap - swap c! ; immediate
All these words at the beginning verify that the compilation mode is set and generate an error if this is not the case.
The word if compiles a conditional branch, reserves a byte for the parameter of a conditional branch command, and pushes the address of that byte onto the stack. Then he puts the control value 111 on the stack.
The word then checks for the presence of the control value 111, and then writes an offset to the address on the stack.
And immediately make the word else. It first compiles the unconditional branch command, to bypass the else branch. Just like with if, the transition offset is not yet known, it is simply reserved, and its address is put on the stack. Well, after that, everything is exactly the same as with then: the address of the mouth transition is set to the else branch. Something is more difficult to describe than the code itself :) If someone wants to thoroughly understand, it is better to disassemble the work of this, as simple as possible code:
: if compile ?nbranch8 here 0 c, ; immediate
: then dup here swap - swap c! ; immediate
Well, now let's program the real code. Since we do not have the word compile, apply the same trick as when creating the word ";":
: if ?state lit8 [ blword ?nbranch8 find cfa c@ c, ] c, here 0 c, 111 ; immediate
: then ?state 111 ?pairs dup here swap - swap c! ; immediate
: else ?state 111 ?pairs lit8 [ blword branch8 find cfa c@ c, ] c, here 0 c, swap dup here swap - swap c! 111 ; immediate
Now you can try to compile the condition. For example, let's make a word that displays 1000, if the number on the stack is 5, and 0 in other cases:
$ ./forth
( 0 ): > : test 5 = if 1000 . else 0 . then ;
( 0 ): > 22 test
0
( 0 ): > 3 test
0
( 0 ): > 5 test
1000
( 0 ): >
It is clear that this result was not immediately, there were errors, there was a debugging. But in the end, the conditions are working!
A small digression about the width of transition teams
Стоит отметить, что тут используются переходы с восьмиразрядным смещением, которые может выполняться в пределах 127 байт. Это ограничивает объем кода в ветках условия. Но, к сожалению, мы не можем выбирать разрядность команд автоматически. Потому что компилятор форта однопроходный, используются переходы вперед, и надо сразу резервировать место под команду перехода. Для экспериментов 8 бит нам хватит, это примерно от 40 до 127 команд в ветке условия. А как быть, если бы мы делали систему для продакшен?
Вариантов тут несколько. Самый простой — это использовать переходы 16 бит.
Но я бы сделал по другому. 16 бит на смещение для перехода по условиям — это с огромным избытком. Поэтому, я бы применил тот же трюк, что и с командой call, поместив несколько бит смещения в команду. Думаю, 11 бит на смещение достаточно (по 1023 в обе стороны). Это позволит поместить в ветки условия примерно от 300 до 1000 фортовских команд. Обычно бывает не больше нескольких десятков, в противном случае код будет просто не читаем. Тогда в код команды уходит 3 бита смещения, и команда перехода займет 8 ячеек в таблице кодов. Команд у нас три: по нулю (?nbranch), по не нулю (?branch) и безусловный (branch). Итого — 24 ячейки.
Вариантов тут несколько. Самый простой — это использовать переходы 16 бит.
Но я бы сделал по другому. 16 бит на смещение для перехода по условиям — это с огромным избытком. Поэтому, я бы применил тот же трюк, что и с командой call, поместив несколько бит смещения в команду. Думаю, 11 бит на смещение достаточно (по 1023 в обе стороны). Это позволит поместить в ветки условия примерно от 300 до 1000 фортовских команд. Обычно бывает не больше нескольких десятков, в противном случае код будет просто не читаем. Тогда в код команды уходит 3 бита смещения, и команда перехода займет 8 ячеек в таблице кодов. Команд у нас три: по нулю (?nbranch), по не нулю (?branch) и безусловный (branch). Итого — 24 ячейки.
We have conditions, life becomes simpler :)
Let's make a word. "(Dot-quote). It displays the specified text when executed. Used in this way:
." этот текст будет выведен"
You can use this word only in compilation mode. This will become apparent after we disassemble the device of this word:
: ." ?state 34 word dup if lit8 [ blword (.") find cfa c@ c, ] c, str, else drop then ; immediate
This word is executed in compilation mode. It accepts a string from the input stream before quotes (34 word). If the string could not be obtained, does nothing. Although, here it would be better to withdraw the diagnosis. But for the output of the line, this word we are doing is just necessary :) If necessary, then you can redefine this word again, already with diagnostics.
If the string was obtained, the buy command (. ") Is compiled, and then the resulting string. This byte command (a dot-quote in parentheses) displays the string that was compiled by the command byte.
Check.
$ ./forth
( 0 ): > : test ." этот текст будет выведен" ;
( 0 ): > test
этот текст будет выведен
( 0 ): >
And finally, let's make the word compile.
It is clear that in the compilation mode this word should take from the stream the name of the next word, find it in the dictionary. And then there will be options: it may be a byte-command, and maybe a word written in byte-code. These words need to be compiled in different ways. Therefore, we make two auxiliary words: "(compile_b)" and "(compile_c)".
(compile_b) will compile the call command to call the bytecode. As a parameter there will be a 64-bit word - the address of the byte-code being called.
(compile_c) will compile a byte command. Accordingly, the parameter of this command will be one byte - the command code.
Well, the word compile itself will compile either (compile_b) or (compile_c) with the appropriate parameters.
Let's start with (compile_c), as with the most simple:
: (compile_c) r> dup c@ swap 1+ >r c, ;
Despite the simplicity, we first write the word in bytecode, which itself has parameters. Therefore, I will comment. After logging in (compile_c) on the stack of returns is, as it is not trivial, the return address. This is the address of the next byte after the call command. Below is the situation at the time of the call. A0 is the command code call, XX is a parameter of the command call is the address of the call (offset) of the word byte code (compile_c).
The return address points to the NN byte. Usually there is the code of the next command byte. But we have the word has parameters, so NN is just the parameters of the word "(compile_c)", namely, the byte-code of the compiled command. You need to read this byte and change the return address by moving it forward to the next byte command. This is done by the sequence "r> dup c @ swap 1+> r". This sequence pulls the return address from the return stack to the normal stack, extracts a byte on it, adds one to it (the return address), and returns it back to the return stack. The remaining “c,” command compiles the byte-command code obtained from the parameters.
(compile_b) is not much more complicated:
: (compile_b) r> dup @ swap 8 + >r compile_b ;
Here everything is the same, only the 64-bit parameter is read, and the word compile_b, which we have already created for the compiler, is used to compile the word.
And now the word compile. As already discussed, it reads the name of the word, finds it, and compiles one of the two previous commands. I will not comment on it, we have already applied and dismantled all the constructions used.
Word compile
: compile
blword over over find dup
if
dup c@ 128andif cfa c@ (compile_b) [ blword (compile_c) find cfa , ] c,
else cfa (compile_b) [ blword (compile_b) find cfa , ] , then
drop drop
else
drop ." compile: " type ." - not found"
then
; immediate
To verify the created word, we will make, with its help, the word ifnot.
: ifnot ?state compile ?branch8 here 0 c, 111 ; immediate
Check it out!
$ ./forth
( 0 ): > : test 5 = ifnot 1000 . else 0 . then ;
( 0 ): > 22 test
1000
( 0 ): > 3 test
1000
( 0 ): > 5 test
0
( 0 ): >
Everything is good! And it's time to do cycles ...
In this article we will make cycles with a condition. In the fort two variants of the cycle with the condition.
The first option is begin ... until. The word until removes the value from the stack, and if it is not zero, the loop ends.
The second option is begin ... while ... repeat. In this case, the test occurs when the word while is executed. The exit from the loop occurs if the value on the stack is zero.
The cycles on the fort are made in the same way as the conditions on conditional and unconditional transitions. I give the code, comments, I think, are not needed.
: begin ?state here 112 ; immediate
: until ?state 112 ?pairs compile ?nbranch8 here - c, ; immediate
: while ?state 112 ?pairs compile ?nbranch8 here 0 c, 113 ; immediate
: repeat ?state 113 ?pairs swap compile branch8 here - c, dup here swap - swap c! ; immediate
For today we will finish with the compiler. There are very few. Of the key functions that have not yet been implemented - these are only cycles with a counter. And still it is worth making a command of an exit from the leave cycles. This will be done next time.
But we have not experienced the command cycle!
We do this by writing the standard word words. We must look, finally, our dictionary.
To do this, in the beginning, we will make the word link @. It will extract a communication field from the dictionary entry (offset to the previous entry). As we remember, the communication field can have a different size: 1, 2, 4 or 8 bytes. This word will take the address of the dictionary entry in the stack, and return two values: the address of the name field and the value of the link field.
: link@ dup c@ 3and swap 1+ swap
dup 0= if drop dup 1+ swap c@ else
dup 1 = if drop dup 2 + swap w@ else2 = if drop dup 4 + swap i@ else
drop dup 8 + swap @
then then then ;
And now you can make the word words:
: words context @ @ 0
begin
+ dup link@
swap count type tab emit
dup 0=
until
drop drop ;
Running ...
$ ./forth
( 0 ): > words
words link@ repeat while until begin ifnot compile (compile_b) (compile_c) ." else then if cmove tab bl decimal hex immediate ; bye ?state ?pairs : str, interpret $compile compile_b compile_n compile_1248 compile_c c, w, i, , allot here h test_bv test_bvc [ ] state .s >in #tib tib . #> #s 60 # hold span holdpoint holdbuf base quit execute cfa find word blword var16 var8 (.") (") count emit expect type lshift rshift invert xor or and >= <= > < = 0> 0< 0= bfind compare syscall fill move rpick r@ r> >r -! +! i! i@ w! w@ c! c@ ! @ depth roll pick over -rot rot swap drop dup abs /mod mod / * - + 1+ 1- exit ?nbranch16 ?nbranch8 ?branch16 ?branch8 branch16 branch8 call8b0 call64 call32 call16 call8f lit64 lit32 lit16 lit8 8 4 3 2 1 0 context definitions current forth
( 0 ): >
Here it is, our wealth :)
I wanted to say everything ... no, let's, nevertheless, make it possible to specify as a parameter a file with the fort program for compilation and execution.
We will make opening, closing and reading a file through syscall. We define the constants necessary for them.
: file_open 0002 syscall ;
: file_close 000003 syscall ;
: file_read 0000 syscall ;
: file_O_RDONLY 0 ;
: file_O_WRONLY 1 ;
: file_O_RDWR 3 ;
Now you can make the starting word _start:
: _start
0 pick 1 > if2 pick file_O_RDONLY 0 file_open
dup 0< if .\" error: \" . quit then
dup here 32 + 32768 file_read
dup 0< if .\" error: \" . quit then
swap file_close drop
#tib ! here 32 + tib ! 0 >in ! interpret
then
;
This word will load from a file and execute any fort program. More precisely, the interpreter will execute everything that will be in this file. And there may be, for example, a compilation of new words and their execution. The file name is indicated by the first parameter at startup. I will not go into details, but the startup parameters in Linux are passed through the stack. The word _start will get them with the commands 0 pick (number of parameters) and 2 pick (pointer to the first parameter). For the fort system, these values lie outside the stack, but pick can get them. The file size is limited to 32 KB, while there is no memory management.
It now remains to write in the fcode line at the end:
_start
quit
Create a file test.f and write something on the forte there. For example, the Euclidean algorithm for finding the greatest common divisor:
: NOD
begin
over over <>
while
over over > if swap over - swap else over - then
repeat
drop ;
2310144425 NOD .
bye
We start.
$ ./forth test.f
1777
Bye!
$
The answer is correct. The word was compiled, then fulfilled. The result is displayed, then the bye command is executed. If you remove the last two lines, the word NOD will be added to the dictionary and the system will go to its command line. You can already write programs :-)
That's all. To whom it is interesting, you can download the source code or a ready-made Linux binary on x86-64 from the GitHub: https://github.com/hal9000cc/forth64. The
sources come with a