- PVSM.RU - https://www.pvsm.ru -
Интересный небольшой эксперимент по использованию Cи в качестве цели компиляции для получения портативности программы, ее оптимизации и функциональной совместимости. В ходе эксперимента мы также напишем саму программу, реализующую алгоритм Эвклида, выполним ее отладку и профилирование, а также попутно задействуем функцию «красивой» печати gdb.
Ниже показан процесс отладки программы Forth в KDevelop – графическом отладчике, не поддерживающем Forth:
Круто, не так ли? По умолчанию здесь есть только добавленное кем-то ранее выделение синтаксиса для файлов Forth. Остальные же возможности вроде выполнения в этом отладчике Forth, определения точек останова и просмотра состояния программы мы реализуем ниже сами.
Я покажу вам весь необходимый код. Делать нам придется не так много, поскольку большую часть всего мы получим в готовом виде, использовав Си в качестве промежуточного языка.
Применение высокоуровневого языка на роли промежуточного нельзя назвать необычным. Многие компиляторы нацелены на существующую высокоуровневую платформу, а не генерацию нативного кода – та же генерация байткода JVM или исходного кода JS. Почему? Потому что таким образом мы попутно получаем:
Среди языков, нацеленных на высокоуровневые платформы, есть весьма популярные: Scala и Clojure, чьи компиляторы ориентированы на JVM, CoffeeScript и Dart, которые уже компилируются в JavaScript. (Есть еще Java, код которого, как известно, GWT компилирует в JavaScript [1]– хотя это все же отдельный случай).
Какие из подобных языков являются наиболее успешными? Без сомнений на сегодня ответом будет С++ и Objective-C – языки, чьи первые компиляторы генерировали код Си.
Я считаю, что Си является прекрасным промежуточным языком для компиляции. Он чрезвычайно портативен, быстро компилируется, хорошо оптимизируется, и при этом вы получаете функциональную совместимость с кучей возможностей.
Когда я хотел создать компилятор для интерпретируемого языка нашей собственной разработки, то изначально думал о генерации кода для VM, а не исходного языка. Я планировал получать LLVM IR, но потом подумал, а почему именно LLVM IR? В конце концов LLVM IR менее читаем, чем Си, менее стабилен, чем стандарт Си, и при этом менее портативен. Скорее всего, так всегда и будет.
Даже если LLVM выполняется на каждой аппаратной платформе, LLVM IR будет поддерживаться только инструментами LLVM, но уже не GNU или Visual Studio, к примеру. При этом генерация кода Си обеспечивает отличную поддержку и инструментов LLVM, и GNU и VS. Отладка сгенерированной LLVM IR программы в Visual Studio наверняка будет уступать аналогичному процессу для автоматически сгенерированного кода Си, скомпилированного через Visual Studio.
«Cи в качестве промежуточного языка» — это одна из тем, о которой я думал написать уже несколько лет. Мешало лишь то, что я хотел сделать это на примере, включая дополнительную работу, которая может потребоваться для лучшей поддержки отладки. Вот только пример, который бы вместился в компактный формат блога, никак придумать не получалось.
Пока однажды меня не осенило: Forth! Минималистский язык, в который я когда-то влюбился (статья на англ.) [2], и который по-прежнему занимает место в моем сердце.
Итак, я создам компилятор из Forth в C. Данный проект впишется в один пост – по крайней мере в него войдет небольшой сегмент Forth – а этот язык достаточно отличен от Си, чтобы вызвать интерес. Так я хочу показать, что это не обязательно должен быть Си с расширениями вроде С++ или Objective-C. Это может быть нечто далекое от него, но вы все равно получите много пользы от инструментов Си, предоставляемых вашей платформой.
Что ж, хватит лишних слов, пора переходить к делу – реализации экспериментального компилятора из Forth в Cи. План будет таков:
Опасным было бы включить поддержку CREATE/DOES>
, COMPILE
, POSTPONE
или чего-то подобного. Мы этого делать не будем и задействуем лишь столько Forth, чтобы хватило для реализации Эвклидова алгоритма (gcd
).
Вот описание нашего сегмента Forth – если этот язык вы знаете, то можете его пропустить:
2 3
, сначала передается 2
, а затем 3
.6 2 /
извлекает 6
и 2
, помещая 6/2=3
. При этом 2 3 =
помещает 0
(ложно), потому что 2
не равно 3
.DUP
повторяет вершину стека: 2 DUP
равнозначно
2 2
. Swap
производит обмен значений: 2 3 SWAP
равнозначно 3 2
. Tuck
выполняет подбор, т.е. помещает значение из вершины стека в его третью позицию: 2 3 TUCK
равнозначно 3 2 3
. Как вы уже можете себе представить, чем меньше таких слов, тем более читаемый получается код.: MYNAME …code… ;
Если далее вы введете MYNAME
, то выполните код и при достижении точки с запятой вернетесь к моменту вызова. Никаких «аргументов функций» не объявляется – вместо этого код извлекает аргументы из стека и помещает туда результат. Предположим, : SQUARE DUP * ;
определяет слово, возводящее значение в квадрат; теперь 3 SQUARE
равнозначно 3 DUP *
– извлекает из стека 3
и помещает туда 9
.BEGIN … cond UNTIL
аналогичен { … } while(!cond)
, и cond
в нем извлекается UNTIL
. BEGIN … cond WHILE … REPEAT
аналогичен while(1) { … if(!cond) break; … }
, и cond
в нем извлекается WHILE
.2 .
выводит 2
. CR
выводит новую строку.*Прим. пер.: существуют реализации Forth, чувствительные к регистру.
Вот и все – этого достаточно, чтобы реализовать GCD
и напугать (ну или поразить) ваших привыкших к инфиксам друзей.
Стратегия, конечно, громко сказано, но все же наш компилятор, втиснутый в масштаб блога и имеющий соответствующие возможности, будет работать так:
data
. data
– это typedef
для long
.data*
, указывающую на вершину стека (TOS), и возвращает новый указатель TOS.s=WORD(s)
.+
не может стать s=+(s)
, потому что это не валидный Cи. Для таких слов мы выполняем простое преобразование. 2
становится PUSH(2)
, +
становится OP2(+)
. Аналогичным образом слова потока управления переводятся в do/while
, if
и break
.s[0]
представляет TOS, значит s[1]
будет элементом под ним и т.д. Команда s++
уменьшает стек, извлекая TOS.
Вот и все. Например, функция gcd
отсюда [3]:
: gcd begin dup while tuck mod repeat drop ;
…компилируется в код Си, приведенный ниже. Как видите, каждое слово преобразуется по-отдельности – у компилятора практически нет понятия «контекста» или «грамматики»:
data* gcd(data* s) { //: gcd
do { //begin
s=dup(s); //dup
if(!*s++) break; //while
s=tuck(s); //tuck
OP2(%); //mod
} while(1); //repeat
s=drop(s); //drop
return s; //;
}
Вот весь исходный код Python для компилятора (forth2c.py
) – немного повторяющийся после всех объяснений:
#!/usr/bin/python
import sys
# "special" слова – не способны генерировать s=WORD(s)
special = {
':':'data* ',
';':'return s; }',
'.':'PRINT();',
'begin':'do {',
'until':'} while(!*s++);',
'repeat':'} while(1);',
'while':'if(!*s++) break;',
}
# бинарные операторы
binops='+ - * / = < > mod'.split()
op2c={'=':'==','mod':'%'}
def forth2c(inf,out):
n = 0
for line in inf:
n += 1
# генерирует строковую информацию для инструментов Си (отладчиков и т.д.)
# - приятная опция Си дает нам:
print >> out,'n#line',n,'"%s"'%infile
for token in line.lower().strip().split():
if token in special:
print >> out,special[token],
else:
try:
num = int(token)
print >> out, 'PUSH(%d);'%num,
except ValueError:
if token in binops:
print >> out,'OP2(%s);'%op2c.get(token,token),
else:
if defining:
print >> out,token+'(data* s) {',
else: # call
print >> out,'s=%s(s);'%token,
defining = token == ':'
out = open('forth_program.c','w')
print >> out, '#include "forth_runtime.h"'
for infile in sys.argv[1:]:
forth2c(open(infile),out)
А вот «библиотека среды выполнения», если можно ее так назвать (forth_runtime.h
). Она представляет некую форму предполагаемого манипулирования стеком: s++
, s--
, s[0]=something
.
#include <stdio.h>
typedef long data;
#define PUSH(item) (--s, *s = (item))
#define OP2(op) (s[1] = s[1] op s[0], ++s)
#define PRINT() (printf("%ld ", s[0]), ++s)
#define cr(s) (printf("n"), s)
#define drop(s) (s+1)
#define dup(s) (--s, s[0]=s[1], s)
#define tuck(s) (--s, s[0]=s[1], s[1]=s[2], s[2]=s[0], s)
#define MAX_DEPTH 4096 //произвольно
data stack[MAX_DEPTH];
data* forth_main(data*);
int main() { forth_main(stack+MAX_DEPTH); return 0; }
Заметьте, что в нашем диалекте Forth есть слово для точки входа – forth_main
– которому Си-функция main
передает указатель на пустой стек. В реальном Forth нет точки входа – он больше подобен скриптовому языку. Однако хак с forth_main
для нашего примера вполне сработает.
Вот и все! Весь диалект уместился в 60 строк. Самый короткий из всех написанных мной компиляторов, если не самый эффективный.
Протестируем наш forth2c
, используя несколько примеров исходного кода.
countdown.4th (отсюда [4])
: COUNTDOWN
BEGIN
DUP .
1 -
DUP 0 =
UNTIL
DROP
;
gcd.4th (многострочная версия – с целью упрощения дальнейшей пошаговой отладки):
: gcd
begin
dup
while
tuck
mod
repeat
drop
;
main.4th:
: forth_main
5 countdown
cr
10 6 gcd .
35 75 gcd .
12856 3248 gcd .
cr
;
Можно выполнить эту программу с помощью скрипта оболочки:
./forth2c.py countdown.4th gcd.4th main.4th
gcc -g -static -Wall -o forth_program forth_program.c
./forth_program
Вывод должен получиться таким:
5 4 3 2 1
2 5 8
Итак, функция обратного отсчета (countdown
) исправно отсчитывает от 5 до 1, а gcd
успешно находит наибольший общий делитель (НОД). Все молодцы.
Опробуем нашу программу с помощью доверенного gdb
:
$ gdb forth_program
There is NO WARRANTY!! etc. etc.
(gdb) b countdown # помещаем точку останова
Breakpoint 1: file countdown.4th, line 3.
(gdb) r # выполняем
Breakpoint 1, countdown (s=0x804e03c) at countdown.4th:3
(gdb) bt # обратная трассировка
#0 countdown (s=0x804e03c) в countdown.4th:3
#1 forth_main (s=0x804e03c) в main.4th:2
#2 main () в forth_runtime.h:14
(gdb) l # вывод исходного кода
1 : COUNTDOWN
2 BEGIN
3 DUP .
4 1 -
5 DUP 0 =
6 UNTIL
7 DROP
8 ;
(gdb)
Круто!
Действительно, круто. Мы установили точку останова, получили стек вызовов – forth_main
, названный countdown
, и увидели исходный код Forth отлаживаемой функции – все это в отладчике, который понятия не имеет о Forth.
Отчасти причина в компиляции в высокоуровневые примитивы, такие как функции, которые поддерживаются инструментами – это бы у нас получилось в любом языке. А отчасти связано с #inline
– которая есть не везде.
Эта возможность просто восхитительна – с помощью #inline
мы сообщаем отладчикам, откуда на самом деле берется код ассемблера – не промежуточный код Си, а реальный исходный.
Инструкцию #inline
понимают не только отладчики – это относится и к профилировщикам, и к программам проверки, и т.д.
А вот вывод KCachegrind, показывающий профиль нашей программы Forth, полученный через фреймворк Valgrind:
valgrind --tool=callgrind ./forth_program
kcachegrind `ls -t callgrind* | head -1`
Разве не здорово?
Компиляторы Си также в курсе #inline
– чем мы можем воспользоваться, переложив выдачу сообщений об ошибках на компилятор. Например, если использовать неопределенное слово do_something
, мы получим указание на ошибку с точностью до виновной в ней строки исходного кода:
main.4th:3: implicit declaration of function ‘do_something’
Очень чувствительное сообщение об ошибке – и делать для этого ничего не пришлось. А теперь попробуем BEGIN
без REPEAT
, для чего удалим REPEAT
из countdown.4th
:
gcd.4th:1: error: expected ‘while’ before ‘data’
Хм, не очень хорошее сообщение. Возможно, все же идея была не очень удачной. Если нас интересует качественный отчет об ошибках, то их проверку нужно выполнять на уровне исходного языка.
Все выглядит довольно неплохо. Инструменты Си – gdb, Valgrind, KCachegrind – с нашими задачами справляются, не так ли?
За исключением стека данных. Вместо элементов стека gdb показывает нам указатель TOS в hex-формате: countdown (s=0x804e03c)
, forth_main (s=0x804e03c)
, что выглядит не очень удачно.
Не то, чтобы локальная переменная s
бесполезна – наоборот, именно ее мы используем для просмотра стека данных. Это можно сделать с помощью команд gdb вроде p s[0]
(выводит TOS), p s[1]
(выводит элемент, следующий за TOS) и т.д. Но нам куда интереснее наблюдать весь стек сразу, чтобы видеть, как по мере нашего прохождения через код TUCK
подбирает числа в стек.
#line
, нельзя выполнить кастомную «красивую» печать общим способом для всех инструментов. Не существует «#line
для «красивой» печати» — очень жаль. stack[]
.(Если бы у нас были потоки, этот массив был бы локальным для потока, но смысл вы поняли).
Итак, вот gdb_forth.py
:
class StackPrettyPrinter(object):
bottom = None
bot_expr = 'stack + sizeof(stack)/sizeof(stack[0])'
def __init__(self,s):
self.s = s
def to_string(self):
if not self.bottom:
self.bottom = gdb.parse_and_eval(self.bot_expr)
s = self.s
i = 0
words = []
while s[i].address != self.bottom:
words.append(str(s[i]))
i += 1
return ' '.join(reversed(words))
def stack_lookup_func(val):
if str(val.type) == 'data *':
return StackPrettyPrinter(val)
gdb.pretty_printers.append(stack_lookup_func)
print 'loaded Forth extensions'
gdb.pretty_printers
– это список функций, которые решают, нужно ли обернуть передаваемое им gdb.Value
в объект класса «красивой» печати. Как правило, это решение принимается на основе типа значения. gdb.parse_and_eval
возвращает gdb.Value
, представляющее значение заданного выражения Си. У gdb.Value
есть тип, адрес и т.д. Если gdb.Value
является указателем, можно индексировать его как список Python: val[ind]
, а если структурой, то использовать как словарь: val['member_name']
(примера для этого случая у нас здесь нет).
Если вас заинтересовали возможности «красивой» печати gdb, то вот пара примечаний:
parse_and_eval
, которая просто перегружает процессор. Так что освоить своеобразный синтаксис обращения к gdb.Value
очень даже стоит.
Что ж, давайте протестируем нашу функцию «красивой» печати – но сначала зарегистрируем ее в ~/.gdbinit
:
python execfile('/your/path/to/gdb_forth.py')
А теперь:
$ gdb forth_program
There is NO WARRANTY!!
loaded Forth extensions # ага, вот наш вывод!
(gdb) b gcd
(gdb) r
Breakpoint 1, gcd (s=10 6) # а вот и стек
(gdb) python for i in range(4): gdb.execute('c')
# продолжаем 4 раза
Breakpoint 1, gcd (s=6 4)
Breakpoint 1, gcd (s=4 2)
Breakpoint 1, gcd (s=2 0)
# это были шаги gcd(10,6)
Breakpoint 1, gcd (s=35 75)
3 dup
# новые входные данные - gcd(35,75). Прошагаем:
(gdb) s # шаг (выполнение DUP)
4 while
(gdb) p s # вывод s
$1 = 35 75 75 # DUP повторила 75.
(gdb) s # шаг (выполнение WHILE)
5 tuck
(gdb) p s
$2 = 35 75 # ...а WHILE 75 извлекла.
(gdb) s # теперь выполняем могучую TUCK:
6 mod
(gdb) p s
$3 = 75 35 75 # Подбор произведен!
(gdb) bt # а как выглядит стек данных main?
#0 gcd (s=75 35 75) в gcd.4th:6
#1 forth_main (s=75 35) в main.4th:5
# выглядит он короче – вроде в разумных пределах
# (Указатель TOS в main остается неизменным, пока gcd не сделает возврат)
Считаю, что вполне неплохо. 10 6
, 6 4
, 4 2
, 2 0
– довольно лаконичная прогулка по алгоритму Эвклида в Forth.
И, наконец, так выглядит KDevelop (где стек, отображаемый в GUI, изменяется с каждым шагом, чего мы и ожидаем от хорошего отладчика). Стек показан в окне Variables слева.
Для того, чтобы все заработало в KDevelop, ничего особенного делать не нужно, разве что сообщить отладчику о необходимости обработать пользовательский исходный код, как это иногда делается с программами Си.
Некоторые возможности исходного языка отображаются в Си более естественно, чем другие. Если попробовать задействовать не Forth, а другой язык, или использовать его весь, а не выборку, то некоторые возможности вызовут серьезные сложности.
Какие-то из них можно без проблем обработать с помощью другого промежуточного языка. Например, атрибуты динамических данных более естественно отображаются в JavaScript, чем в Си.
Но во многих случаях выбор промежуточного языка делается не на основе его совместимости с исходным. К примеру, если ваша цель браузеры, тогда и выбор должен наверняка пасть на JS, даже если он окажется плохим компаньоном для исходного языка. То же касается и других ситуаций, когда нужно выбирать Си или JVM, или .NET и т.д.
На деле многие разработчики языков намеренно сделали их гармонично сочетающимися именно с соответствующей платформой – промежуточным языком. Некоторые указывают на плавную интеграцию с этой платформой в самом названии языка: C++, Objective-C, CoffeScript, TypeScript. Они знают, что многие пользователи скорее выберут их язык из-за его платформы, чем по какой-либо другой причине, потому что они ей ограничены.
С учетом этого я приведу несколько возможностей, которые не переводятся лаконично в Си, и попутно опишу, как можно это решить:
call(object,method_id)
или call(object,"method_name")
, multidispatch(method,obj1,obj2)
– что предпочтете. Должно сработать.eval
и т.д.: в Си нет eval
, но есть fopen("tmp.c")
, fwrite, system("gcc -o tmp.so tmp.c …")
, dlopen("tmp.so")
и dlsym
. Это может дать вам неплохое подобие eval
. Для реализации потребуется непортируемый код, но совсем немного. В качестве альтернативы, если относительно медленная eval
с относительно слабой поддержкой отладки вас устроит (часто так и бывает), то можете реализовать эту функцию с помощью интерпретатора, который сможет воспользоваться парсером вашего статического компилятора. Мы задействуем оба этих метода в нескольких местах, и все работает прекрасно.access(object,"attr_name")
или любой другой вариант. Самое неприятное – это просматривать такие объекты в отладчиках. Один из подходов – это использовать «красивую» печать или написать скрипт аналогичного отладчика. Другой вариант – для «достаточно статических данных» — это сгенерировать определения структур Си в среде выполнения, скомпилировать их в общую библиотеку с информацией об отладке и загрузить эту библиотеку, как в случае с реализацией eval
. setjmp/longjmp
. Думаю, именно так работал cfront
.collection<item>
или нечто аналогичное. (Соглашение о декорировании имен в С++ не портируемо, поэтому вам может потребоваться поддержка нескольких их вариантов).(+ (* 2 3) 5)
в (+ 6 5)
, а затем в 11
): ой-ой. Думаю, можно было бы написать на Си интерпретатор для выполнения этого, но от оптимизатора Си вы не получите столько пользы, и вообще никакой пользы не получите от отладчиков Си, профилировщиков и т.д. Базовая модель вычисления должна быть достаточно близка к Си, чтобы получить от цепочки инструментов этого языка не только портативность кода Си, реализующего ваш язык. (Я имею ввиду не то, что вам однозначно нужно создать представление в памяти для (+ 6 5)
в среде выполнения – а то, что если вы захотите его создать, то инструменты Си не поймут вашу программу).
Вы можете это сделать, и я даже попробовал. В итоге – не советую. Вместо возни с setjump/longjump
вы на халяву получаете исключения. В результате, когда вы выбрасываете их из одной общей библиотеки и перехватываете в другой, то они не работают (я думаю, что RTTI* имеет аналогичные проблемы с общими библиотеками). Вы также получаете халявные шаблоны, и в итоге ваш автогенерируемый код компилируется вечность.
*RTTI – динамическая идентификация типа данных.
Эли Бендерски писал [7]о переходе с Си на С++ для реализации языковой виртуальной машины. Он говорит, что когда возможности С++ соответствуют нуждам вашей виртуальной машины, то проще использовать их, чем переписывать альтернативу на Си.
В моем же случае это привело вот к чему. Однажды я реализовал VM и интерпретатор на С++. Затем мы написали для этого языка компилятор. Поскольку VM была написана на С++, компилятору было намного проще для взаимодействия с ней генерировать код С++, чем код Си. В итоге из-за этого автогенерируемого кода С++ мы столкнулись с проблемами работы общих библиотек, проблемами со скоростью сборки и другими, которые остались по сей день.
Конечно, это не правило, и ваш опыт может отличаться. Одна из причин использовать С++ в том, что отладчики все лучше отображают коллекции STL и указатели на объекты базового класса (которые они не забывают привести к реальному типу среды выполнения и показать членов производного класса). Если конструкции вашего языка сочетаются с этими возможностями С++, то вы получите улучшенное отображение данных отладки портативным способом.
Си отлично подходит в качестве промежуточного языка, и я буду рад увидеть варианты компиляции в него других языков. В последнее время я не работаю ни с Java, ни с JavaScript. Определенно, не я один. Язык, компилируемый в Си, может не только быть быстрым, портативным, обладать хорошими инструментами и поддержкой библиотек, но также оказаться пригодным для многих, работающих с Си, С++ и Objective-C.
Автор: Дмитрий Брайт
Источник [8]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/c-3/370014
Ссылки в тексте:
[1] компилирует в JavaScript : https://developers.google.com/web-toolkit/overview
[2] когда-то влюбился (статья на англ.): http://yosefk.com/blog/my-history-with-forth-stack-machines.html
[3] отсюда: https://literateprograms.org/euclidean_algorithm__forth_.html
[4] отсюда: http://galileo.phys.virginia.edu/classes/551.jvn.fall01/primer.htm
[5] Noam : http://www.dreampie.org
[6] Boehm collector: http://www.hpl.hp.com/personal/Hans_Boehm/gc/
[7] писал: http://eli.thegreenplace.net/2011/11/30/how-i-stopped-worrying-and-switched-to-c-for-my-bob-scheme-vm/
[8] Источник: https://habr.com/ru/post/589839/?utm_source=habrahabr&utm_medium=rss&utm_campaign=589839
Нажмите здесь для печати.