Сколько нужно примитивов для реализации форт системы?

В 1992-м году проходил очередной конкурс по обфусцированному программированию на языке С ^[1]. Один из представленных проектов был небольшой форт системой ^[2]. Меня поразило, что виртуальная машина была реализована всего в 794 байтах С кода. Остальная часть форт системы загружалась из исходника на форте. После изучения проекта первоначальный восторг уступил место разочарованию, так как автор использовал не совсем “честный” трюк: для парсинга фортового исходника он использовал функцию scanf(). С этого момента меня терзал вопрос — сколько нужно примитивов для реализации форт системы без подобных трюков?

Через некоторое время я познакомился с форт системой sod32 ^[3] написанной Lennart Benschop ^[4]. У этой форт системы виртуальная машина написана на С, а двоичный образ, который загружается в виртуальную машину, не зависит от порядка байтов в слове хост системы. sod32 имеет 32 примитива, вот они:





NOOP
( --- )
Do nothing


SWAP
( x1 x2 --- x2 x1 )
Swap the two top items on the stack.


ROT
( x1 x2 x3 --- x2 x3 x1 )
Rotate the three top items on the stack.


0=
( x --- f)
f is true if and only if x is 0.


NEGATE
( n1 --- -n1)
Negate top number on the stack.


UM*
( u1 u2 --- ud )
Multiply two unsigned numbers, giving double result.


C@
( c-addr --- c)
Fetch character c at c-addr.


@
( a-addr --- x)
Fetch cell x at a-addr.


+
( w1 w2 --- w3) 
Add the top two numbers on the stack.


AND
( x1 x2 --- x3)
Bitwise and of the top two cells on the stack.


OR
( x1 x2 --- x3)
Bitwise or of the top two cells on the stack.


XOR
( x1 x2 --- x3)
Bitwise exclusive or of the top two cells on the stack.


U<
( u1 u2 ---- f)
f is true if and only if unsigned number u1 is less than u2.


<
( n1 n2 --- f)
f is true if and only if signed number n1 is less than n2.


LSHIFT
( x1 u --- x2)
Shift x1 left by u bits, zeros are added to the right.


RSHIFT
( x1 u --- x2)
Shift x1 right by u bits, zeros are added to the left.


UM/MOD
( ud u1 --- urem uquot)
Divide the unsigned double number ud by u1, giving unsigned quotient and remainder.


+CY
( n1 n2 cy1 --- n3 cy2)
Add n1 and n2 and the carry flag cy1 (must be 0 or 1) giving sum n3 and carry flag cy2. (n3 cy2 can be seen as a double number)


SCAN1
( x d --- u)
Scan x for the first 1 bit. u is the position of that bit (counted from the scan direction) and 32 if x=0. d is the scan direction, 0 is left-to-right, 1 is right-to-left.


SPECIAL
( x ---)
Any of a large number of special instructions, indicated by x.


DROP
( x ---)
Discard the top item on the stack.


>R
( x ---)
Push x on the return stack.


C!A
( c c-addr --- c-addr)
Store character c at c-addr, keep address.


!A
( x a-addr --- a-addr)
Store cell x at a-addr, keep address.


DUP
( x --- x x )
Duplicate the top cell on the stack.


OVER
( x1 x2 --- x1 x2 x1)
Copy the second cell of the stack.


R@
( --- x)
x is a copy of the top of the return stack.


R>
( --- x)
Pop the top of the return stack and place it on the stack.


0
( --- 0)
The constant number 0.


1
( --- 1)
The constant number 1.


4
( --- 4)
The constant number 4.


LIT
( --- lit)
Push literal on the stack (literal number is in-line).

Я понял, что у меня появился шанс найти ответ на свой вопрос и я начал превращать примитивы в высокоуровневые определения. Хочу сразу отметить, что вся эта деятельность имеет чисто академический смысл. Применить полученные результаты на практике вряд ли получится из-за потери производительности. В процессе своих экспериментов я отслеживал изменения размера двоичного образа форт системы и время выполнения набора тестов за авторством John Hayes. Новый двоичный образ я строил командой

echo 'S" extend-cross.4" INCLUDED '|./sod32 kernel.img

а тесты запускал вот так:

time ./sod32 kernel.img <<< $(echo -e 'S" tester.fr" INCLUDEDn12345nBYE')

В таблице ниже вы можете увидеть как каждое изменение повлияло на размер и производительность. Ссылки из колонки «изменение» ведут на соответствующий коммит в гитхабе.

изменение	размер kernel.img	время исполнения tester.fr
original sod32	10164	0m0.059s
lshift, rshift ^[5]	10312	0m0.071s
+, um*, um/mod ^[6]	11552	0m0.123s
c@, c!a ^[7]	11952	0m0.795s
0=, negate <, u< ^[8]	12340	0m2.800s
drop ^[9]	12784	0m5.022s
swap, rot, over ^[10]	13436	0m5.860s
sp@, sp!, rp@, rp!, dup ^[11]	13680	0m8.696s
r@, r>, >r ^[12]	14160	0m15.463s
and, or, xor ^[13]	14336	0m21.198s
0, 1, 4 ^[14]	15236	0m21.671s
0branch ^[15]	15912	0m41.765s

В итоге размер двоичного образа форт системы увеличился с 10164 до 15912 (+57%), производительность упала в 708 раз (почти 3 порядка). Возможно производительность можно было бы улучшить если отпрофилировать код и оптимизировать узкие места, но я уверен, что результат все равно будет очень медленным по сравнению с исходной sod32.

С 32-х примитивов плюс дополнительной логики во внутреннем интерпретаторе я пришел к 7: nop, nand, !, @, um+, special, lit. Во внутреннем интерпретаторе осталась логика для исполнения примитивов и высокоуровневых определения (call), а также логика для завершения высокоуровневого определения (next). Ответ на свой вопрос я нашел: форт систему можно построить на базе 9-ти примитивов (или 8-ми, если nop не обязательно должен быть примитивом). Меня смущает то, что для доступа к памяти присутствует целых 3 примитива: @,! и lit, но я не придумал, как этого можно избежать. Я вполне мог что-то упустить, так что если вы знаете как можно избавиться от бОльшего количества примитивов — пожалуйста напишите в комментариях.

Автор: kt97679

Источник ^[16]

Сайт-источник PVSM.RU: https://www.pvsm.ru

Путь до страницы источника: https://www.pvsm.ru/forth/360104

Ссылки в тексте:

[1] конкурс по обфусцированному программированию на языке С: https://en.wikipedia.org/wiki/International_Obfuscated_C_Code_Contest

[2] форт системой: https://github.com/kt97679/forth-dev/tree/master/ioccc-obfuscated-c-contest-1992-buzzard.2

[3] sod32: https://lennartb.home.xs4all.nl/sod32.tar.gz

[4] Lennart Benschop: https://lennartb.home.xs4all.nl/

[5] lshift, rshift: https://github.com/kt97679/forth-dev/commit/c0871becc4847c2578b4781df54ae37190cbc1f1

[6] +, um*, um/mod: https://github.com/kt97679/forth-dev/commit/f9c9b713590c2a79dac409174ffac7096d2cd1f2

[7] c@, c!a: https://github.com/kt97679/forth-dev/commit/cb702db36be9f0dc25e341f795ff7d71104d4088

[8] 0=, negate <, u<: https://github.com/kt97679/forth-dev/commit/f81b8f2e3a605f20d958dd0735d8df2abc5fac84

[9] drop: https://github.com/kt97679/forth-dev/commit/45cffa66268f26135eafa0851a495ff3dc3ed556

[10] swap, rot, over: https://github.com/kt97679/forth-dev/commit/2a3b456d1cf536a8ac2b901488b01261cc8e25f3

[11] sp@, sp!, rp@, rp!, dup: https://github.com/kt97679/forth-dev/commit/6aef58d7714fc3e3ba23f39f386f7dd05a3e8fc9

[12] r@, r>, >r: https://github.com/kt97679/forth-dev/commit/56874b104f352a1d0268a2701cb2fd766608b140

[13] and, or, xor: https://github.com/kt97679/forth-dev/commit/4217c290541fcb902aeb43b308a8c019a6e5c8f9

[14] 0, 1, 4: https://github.com/kt97679/forth-dev/commit/30640cff9ebcc128ed26012f62f33963b980c1bd

[15] 0branch: https://github.com/kt97679/forth-dev/commit/cfeedc76045104f9d0200eb66b11ef9c719a5449

[16] Источник: https://habr.com/ru/post/535186/?utm_source=habrahabr&utm_medium=rss&utm_campaign=535186

Нажмите здесь для печати.

NOOP	( --- )	Do nothing
SWAP	( x1 x2 --- x2 x1 )	Swap the two top items on the stack.
ROT	( x1 x2 x3 --- x2 x3 x1 )	Rotate the three top items on the stack.
0=	( x --- f)	f is true if and only if x is 0.
NEGATE	( n1 --- -n1)	Negate top number on the stack.
UM*	( u1 u2 --- ud )	Multiply two unsigned numbers, giving double result.
C@	( c-addr --- c)	Fetch character c at c-addr.
@	( a-addr --- x)	Fetch cell x at a-addr.
+	( w1 w2 --- w3)	Add the top two numbers on the stack.
AND	( x1 x2 --- x3)	Bitwise and of the top two cells on the stack.
OR	( x1 x2 --- x3)	Bitwise or of the top two cells on the stack.
XOR	( x1 x2 --- x3)	Bitwise exclusive or of the top two cells on the stack.
U<	( u1 u2 ---- f)	f is true if and only if unsigned number u1 is less than u2.
<	( n1 n2 --- f)	f is true if and only if signed number n1 is less than n2.
LSHIFT	( x1 u --- x2)	Shift x1 left by u bits, zeros are added to the right.
RSHIFT	( x1 u --- x2)	Shift x1 right by u bits, zeros are added to the left.
UM/MOD	( ud u1 --- urem uquot)	Divide the unsigned double number ud by u1, giving unsigned quotient and remainder.
+CY	( n1 n2 cy1 --- n3 cy2)	Add n1 and n2 and the carry flag cy1 (must be 0 or 1) giving sum n3 and carry flag cy2. (n3 cy2 can be seen as a double number)
SCAN1	( x d --- u)	Scan x for the first 1 bit. u is the position of that bit (counted from the scan direction) and 32 if x=0. d is the scan direction, 0 is left-to-right, 1 is right-to-left.
SPECIAL	( x ---)	Any of a large number of special instructions, indicated by x.
DROP	( x ---)	Discard the top item on the stack.
>R	( x ---)	Push x on the return stack.
C!A	( c c-addr --- c-addr)	Store character c at c-addr, keep address.
!A	( x a-addr --- a-addr)	Store cell x at a-addr, keep address.
DUP	( x --- x x )	Duplicate the top cell on the stack.
OVER	( x1 x2 --- x1 x2 x1)	Copy the second cell of the stack.
R@	( --- x)	x is a copy of the top of the return stack.
R>	( --- x)	Pop the top of the return stack and place it on the stack.
0	( --- 0)	The constant number 0.
1	( --- 1)	The constant number 1.
4	( --- 4)	The constant number 4.
LIT	( --- lit)	Push literal on the stack (literal number is in-line).