Byte-machine for the fort (and not only) in Indian (Part 4)

    Byte-machine for the fort (and not only) in Indian

    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 ячейки.

    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 GNU GPL v2 DFC v1 license - Do What You Want :-)

    Also popular now: