[Ненормальное программирование] Сколько нужно примитивов для реализации форт системы?
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
В 1992-м году проходил очередной конкурс по обфусцированному программированию на языке С. Один из представленных проектов был небольшой форт системой. Меня поразило, что виртуальная машина была реализована всего в 794 байтах С кода. Остальная часть форт системы загружалась из исходника на форте. После изучения проекта первоначальный восторг уступил место разочарованию, так как автор использовал не совсем “честный” трюк: для парсинга фортового исходника он использовал функцию scanf(). С этого момента меня терзал вопрос — сколько нужно примитивов для реализации форт системы без подобных трюков?
Через некоторое время я познакомился с форт системой sod32 написанной Lennart Benschop. У этой форт системы виртуальная машина написана на С, а двоичный образ, который загружается в виртуальную машину, не зависит от порядка байтов в слове хост системы. 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" INCLUDED\n12345\nBYE')
В таблице ниже вы можете увидеть как каждое изменение повлияло на размер и производительность. Ссылки из колонки «изменение» ведут на соответствующий коммит в гитхабе.
изменение
размер kernel.img
время исполнения tester.fr
original sod32
10164
0m0.059s
lshift, rshift
10312
0m0.071s
+, um*, um/mod
11552
0m0.123s
c@, c!a
11952
0m0.795s
0=, negate <, u<
12340
0m2.800s
drop
12784
0m5.022s
swap, rot, over
13436
0m5.860s
sp@, sp!, rp@, rp!, dup
13680
0m8.696s
r@, r>, >r
14160
0m15.463s
and, or, xor
14336
0m21.198s
0, 1, 4
15236
0m21.671s
0branch
15912
0m41.765s
В итоге размер двоичного образа форт системы увеличился с 10164 до 15912 (+57%), производительность упала в 708 раз (почти 3 порядка). Возможно производительность можно было бы улучшить если отпрофилировать код и оптимизировать узкие места, но я уверен, что результат все равно будет очень медленным по сравнению с исходной sod32.
С 32-х примитивов плюс дополнительной логики во внутреннем интерпретаторе я пришел к 7: nop, nand, !, @, um+, special, lit. Во внутреннем интерпретаторе осталась логика для исполнения примитивов и высокоуровневых определения (call), а также логика для завершения высокоуровневого определения (next). Ответ на свой вопрос я нашел: форт систему можно построить на базе 9-ти примитивов (или 8-ми, если nop не обязательно должен быть примитивом). Меня смущает то, что для доступа к памяти присутствует целых 3 примитива: @,! и lit, но я не придумал, как этого можно избежать. Я вполне мог что-то упустить, так что если вы знаете как можно избавиться от бОльшего количества примитивов — пожалуйста напишите в комментариях.
===========
Источник:
habr.com
===========
Похожие новости:
- [Ненормальное программирование, Разработка игр, Алгоритмы] Трассировка лучей в Notepad.exe со скоростью 30 кадров в секунду (перевод)
- [Ненормальное программирование, Visual Studio, Софт] Разработчик VS Code Stories написал Tinder для программистов
- [Ненормальное программирование, Семантика, Программирование, Совершенный код, Natural Language Processing] Интернациональное программирование на естественных языках
- [Ненормальное программирование, Занимательные задачки, Программирование, Искусственный интеллект] Russian AI Cup 2020 — a new strategy game for developers
- [Ненормальное программирование, Спортивное программирование, Хакатоны, Конференции] [Анонс] Advent of Code 2020: решаем вместе с разработчиками Контура
- [Ненормальное программирование, Занимательные задачки, Программирование, Искусственный интеллект] Russian AI Cup 2020 — новая игра-стратегия для разработчиков
- [Ненормальное программирование, Разработка веб-сайтов, Python, Программирование] iPad для разработчика
- [Ненормальное программирование, Prolog, Forth, Старое железо] Что за X++? Что за ABAP? Древние языки, про которые интересно слушать, но не дай бог на них писать
- [Ненормальное программирование, Программирование, SQL, ERP-системы, Разработка для Office 365] Электронные таблицы, как средство разработки бизнес-приложений
- [Ненормальное программирование, Программирование, Rust] Пишем ОС на Rust. Настройка среды. Бинарник для «голого» железа
Теги для поиска: #_nenormalnoe_programmirovanie (Ненормальное программирование), #_forth, #_nenormalnoe_programmirovanie (
Ненормальное программирование
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 19:10
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
В 1992-м году проходил очередной конкурс по обфусцированному программированию на языке С. Один из представленных проектов был небольшой форт системой. Меня поразило, что виртуальная машина была реализована всего в 794 байтах С кода. Остальная часть форт системы загружалась из исходника на форте. После изучения проекта первоначальный восторг уступил место разочарованию, так как автор использовал не совсем “честный” трюк: для парсинга фортового исходника он использовал функцию scanf(). С этого момента меня терзал вопрос — сколько нужно примитивов для реализации форт системы без подобных трюков? Через некоторое время я познакомился с форт системой sod32 написанной Lennart Benschop. У этой форт системы виртуальная машина написана на С, а двоичный образ, который загружается в виртуальную машину, не зависит от порядка байтов в слове хост системы. 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" INCLUDED\n12345\nBYE')
В таблице ниже вы можете увидеть как каждое изменение повлияло на размер и производительность. Ссылки из колонки «изменение» ведут на соответствующий коммит в гитхабе. изменение размер kernel.img время исполнения tester.fr original sod32 10164 0m0.059s lshift, rshift 10312 0m0.071s +, um*, um/mod 11552 0m0.123s c@, c!a 11952 0m0.795s 0=, negate <, u< 12340 0m2.800s drop 12784 0m5.022s swap, rot, over 13436 0m5.860s sp@, sp!, rp@, rp!, dup 13680 0m8.696s r@, r>, >r 14160 0m15.463s and, or, xor 14336 0m21.198s 0, 1, 4 15236 0m21.671s 0branch 15912 0m41.765s В итоге размер двоичного образа форт системы увеличился с 10164 до 15912 (+57%), производительность упала в 708 раз (почти 3 порядка). Возможно производительность можно было бы улучшить если отпрофилировать код и оптимизировать узкие места, но я уверен, что результат все равно будет очень медленным по сравнению с исходной sod32. С 32-х примитивов плюс дополнительной логики во внутреннем интерпретаторе я пришел к 7: nop, nand, !, @, um+, special, lit. Во внутреннем интерпретаторе осталась логика для исполнения примитивов и высокоуровневых определения (call), а также логика для завершения высокоуровневого определения (next). Ответ на свой вопрос я нашел: форт систему можно построить на базе 9-ти примитивов (или 8-ми, если nop не обязательно должен быть примитивом). Меня смущает то, что для доступа к памяти присутствует целых 3 примитива: @,! и lit, но я не придумал, как этого можно избежать. Я вполне мог что-то упустить, так что если вы знаете как можно избавиться от бОльшего количества примитивов — пожалуйста напишите в комментариях. =========== Источник: habr.com =========== Похожие новости:
Ненормальное программирование ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 19:10
Часовой пояс: UTC + 5