Дмитpий Hecтepук

Блог о программировании — C#, F#, C++, архитектура, и многое другое

Итоги 2016 года

leave a comment »

Я сел тут писать подведение итогов, посмотрел аналогичный пост за 2015 и понял что хочется писать то же самое. Абсолютно. То же отсутствие технических подвижек, тихое почитывание мат.книжек, те же Канары. Все одно и то же.

oyz5vst5-me1

Но если серьезно, я все же повторюсь. Год был офигенен! Особенно после того, как я в конце мая прекратил работать евангелистом — это потеряло финансовый смысл уже давно, и несмотря на то что оплаченный бизнес-класс в США чуть ли не каждый месяц это как бы хорошо, я пожалуй дать отказ, сорри. Мы кстати все равно на очень позитивных отношениях с конторой – я уже как минимум на 2-х эвентах там был, плюс я планирую сделать для PS курс по Rider когда он выйдет. JB много чего мне дал и, сугубо имхо, все еще одна из лучших контор для личностного саморазвития и путешествий за чужой счёт. А вот для кэша – это другой, менее приятный разговор :)

9zmq7ia_ygi1

Мои технологические взгляды остаются такими же, я все еще большой поклонник C++ и C#, оба языка прекрасно себя показывают на соответствующих задачах. Я начал серьезно заниматься FPGA разработкой (на VHDL, что возможно было не лучшей идеей), много чего изучил и в мечтах построить feed handler — для какой биржи и протокола – пока не знаю. Это сложная, запутанная дисциплина, и я приобрел массу уважения к людям которые занимаются этим не смотря на низкие, по сравнению с software engineering, зарплаты.

Подвижки в мире меня мало тронули: реакционные действия масс (Brexit и выборы Трампа) понять можно, т.к. люди устали от политкорректности и подлизывания ко всяким меньшинствам. В моем универе в Англии уже и петиции насчет gender-neutral туалетов, и “транс” студенты уже не то что дико, а это стало нормой. Тем временем, Германия и прочие страны (Меркель войдет в историю как Гитлер со знаком минус) напустили толпы иммигрантов, и теперь развал ЕС не за горами – как только Франция выберет Марин Ле Пен. Думаете не выберут? То же самое говорили про Трампа. А он выиграл. Продемонстрировал как один человек победил всю систему. Я это уважаю, т.к. сам индивидуалист и ратую за победу индивидуума над обществом.

ginc-s7n8ys1

На личном фронте, не смотря на мои подвижки в сторону Лаппеэнранты (я всегда презирал дачников, а тут вдруг нате), я планирую двигаться в сторону Эстонии. Для меня это хороший языковой компромисс, а также вынужденная мера, т.к. Британия пожет выйти из ЕС по-разному, и если она выйдет боком, то это и мне выйдет боком, увы. Как и в каком ключе у меня это получится — не знаю, но охота пуще неволи, так что поживем-увидим. Многие удивлены моему повороту дел и считают что я должен вернуться к трудовой жизни. Что ж, так уж и быть, но это будет по моим правилам. А чем я буду заниматься — это пока сюрприз, хотя немного предсказуемый. А в Лапу я все равно буду ездить — это очень близко к Петербургу, и думаю весной-летом там будет самое то. По крайней мере, надо же откуда-то брать нормальный сыр и рыбу. Хотя в Стокгольм тоже ездить буду периодически, хоть оно и подальше.

jawcaklu1u1

А еще в этом году я стал велосипедистом (но не велофанатом, это другая порода, менее адекватная) — началось все с того, что мы купили себе складные велосипеды, а закончилось тем, что я поехал в Стокгольм чтобы купить себе электронно-двухподвесный Crescent, на котором отныне гоняю по городу и пригородам в любую погоду. Жизнь на скорости 25км/ч безусловно поменяла меня, надеюсь что к лучшему. Но на этом фронте я не думаю увидеть какие-то перемены; наоборот — мне теперь нужно следующее хобби.

Ладно, пора резюмировать уже!

У меня есть подозрение что 2017 будет не просто очень хорош, а у меня, по крайней мере, будет качественный скачок: уход от мелочных, приземленных задач и реализация более серьезных проектов. Хотя я, ей-Сотоне, готов просто сидеть тут, пить Сотерн и слушать новый альбом Энигмы. И пусть весь мир подождёт…

С Новым Годом!!!

gzsdzwgdcvi1

Written by Dmitri

31 декабря 2016 at 23:59

Опубликовано в Life

Tagged with

Проект CallSharp: I/O Call Instrumentation на платформе .NET

4 комментария

Что мне нравится во всяких разработческих тулах, так это то, что они не только помогают решать какие-то задачи, но порой еще и учат программированию. Тула, про которую я хочу рассказать – она именно такая. CallSharp – так называется мой проект – пытается алгоритмически вывести цепочку вызовов на основе набора входных и ожидаемых выходных данных.

callsharp_0_1_1

Сначала простой пример: у вас есть "abc", нужно получить "cba". Ниже я представил это схематично, и далее в статье я буду продолжать использовать такие заголовки.

ff0

Этот пример идеально иллюстрирует проблему, т.к. в .NET у строки нету метода Reverse(), и решений этой задачи – несколько. Например, можно написать вот так:

new string(input.Reverse().ToArray())

Следовательно, хотелось бы получить программу, которая сама выводила бы эти цепочки вызовов на основе входных и выходных данных, гуляя по .NET BCL API, делая все возмножные вызовы и проверяя их на соответствие. Звучит немного фантастично, да?

Давайте возьмем для начала простой пример:

ff1

В нашем случае abc – это точно строка, и ничто иное. Теперь нам предстоит понять что на abc можно вызвать чтобы получить ABC.

Нам повезло что строки в .NET немутабельны, и нам не нужно проверять изменения оригинальной строки после вызовов на ней – только выходного значения. А следовательно, мы можем взять и поискать все методы (а также свойства, которые в .NET тоже методы с приставкой get_), которые

  • Являются нестатическими методами класса string (System.String, если быть педантичными)

  • Могут не принимать ни одного аргумента

  • Возвращают строку

Примечательно, что «могут не принимать ни одного аргумента» – это три раздельных случая, а именно

  • Функция не имеет параметров вообще, т.е. Foo()

  • Функция может и имеет параметры, но у всех них есть дефолтные значения, т.е. Foo(int n = 0)

  • Функция берет упакованый список, т.е. Foo(params char[] letters)

Если руководствоваться этими критериями, мы получим список фунций string, которых было бы неплохо вызвать на строке "abc":

Normalize 
ToLower 
ToLowerInvariant 
ToUpper 
ToUpperInvariant 
ToString 
Trim
TrimStart
TrimEnd

Берем каждую из этих функций, вызываем на "abc", смотрим на результат. Подходят только две функции:

input.ToUpper()
input.ToUpperInvariant()

Ура, первая миссия выполнена!

ff2

Как понять, что за тип у числа 3 справа? Я предлагаю вот такой алгоритм:

  • Через reflection, берем все типы у которых есть метод TryParse().

  • Вызываем на всех данных. Если возвращает true – делаем боксинг распаршенного (неологизм?) объекта, возвращая его как object.

  • Не забываем, что любой ввод это как минимум string. А если ввод имеет длину 1, то это еще и char.

Согласно этому алгоритму, тройка (3) справа может быть и string и char (а также float или даже TimeSpan!), но в текущем примере, мы допустим что это все же Int32 или просто int.

Используя все тот же линейный поиск по нестатическим методам, мы моментально находим

input.Length

Естественно, что на самом деле это вызов функции get_Length(), но CallSharp заранее удаляет все ненужные декорации для удобства пользователя.

ff3

Читерский пример. Если бы я взял true, мне бы попался IsNormalized(), а так на не-статике вариантов нет. Что же, придется расширить наш алгоритм – теперь будем перебирать ещё и статические методы, которые

  • Не обязательно являются членами класса (в нашем случае – строки), но тем не менее попадают в список одобренных типов. Причина: я не хочу произвольно вызывать File.Delete(), например

  • Возвращают нужный нам тип (в данном случае – bool)

Расширив наш поиск до статики, мы получили два вполне корректных результата:

string.IsNullOrEmpty(input)
string.IsNullOrWhiteSpace(input)

Прекрасно! Давайте что-нибудь посложнее уже!

ff4

Ухх, тут ситуация посложнее – "abc ", то есть два пробела на конце: это одной функцией уже не получить. Надо делать цепочку вызовов. В данном случае цепочка не должна быть stringstringstring, она может быть stringчто угодноstring, т.к. промежуточные данные нам не важны.

Именно на этом этапе происходит комбинаторный взрыв. Ну, а что вы хотели? Зато мы на наших входных данных получаем очень много вариантов:

string.Concat(input.Split()).ToUpper()
string.Concat(input.Split()).ToUpperInvariant()
input.ToUpper().Trim()
input.ToUpper().TrimEnd()
input.ToUpperInvariant().Trim()
input.ToUpperInvariant().TrimEnd()
input.Trim().ToUpper()
input.Trim().ToUpperInvariant()
input.TrimEnd().ToUpperInvariant()
input.TrimEnd().ToUpper() // + lots more solutions

Я не стал выкладывать все решения, их достаточно много. Как видите, все варианты являются более-менее правильными, но не учтена коммутативность вызовов: ведь по сути не важно, вызывать нам .Trim().ToUpper() или .ToUpper().Trim(), но программа этого не знает.

Это не ужасная проблема когда вызовов 2, но когда их 3 или больше, количество излишней работы, которую вынуждена делать программа, весьма внушительно.

ff5

Мы пока что обсуждали только «няшные» функции которые можно вызывать без аргументов. Всё – такое дело больше не прокатит. Чтобы удалить bbb на конце нужно вызвать что-то, что жестко выпиливает или b или bbb или удаляет 3 последние буквы в тексте.

Естественно, что все аргументы вызова должны как-то коррелировать с объектом, на котором идет вызов. Для этого сделан страшный и ужасный FragmentationEngine – класс-дробитель, который умеет дробить другие типы на составные части. (Тут должна быть картинка Дробителя из Hearthstone.)

Давайте возьмем строку aaabbb. Ее можно раздробить так:

  • Все возмоджные буквы (в данном случае – 'a' и 'b')

  • Все возможные подстроки (в т.ч. пустая строка). Это реально болезненная операция, т.к. на длинной строке их очень много.

  • Все возможные числа в пределах длины самой строки. Это нужно для вызовов всяких Substring().

Надробив строку на всякие объекты, мы ищем методы – статические или нет – которые берут эти объекты. Тут все более менее предсказуемо, за иключением того что

  • Вызовы с 2+ аргументами делают нехилый комбинаторный взрыв. Простой пример – это Substring().

  • Вызовы функций которые берут params[] теоретически создают ничем не ограниченный комбинаторный взрыв, поэтому их нужно или лимитировать или не вызывать вообще.

CallSharp, конечно, справляется с нашим синтетическим примером и выдает нам

input.Trim('b')
input.TrimEnd('b')

Как вы уже наверное догадались, комбинаторные взрывы могут поднабросить на вентилятор очень много вариантов которые, будучи корректными, являются излишне сложными. Вот например:

ff6

Хмм, казалось бы, нужно всего лишь удалить er ну или e и r по отдельности. Если запустить CallSharp на этом примере, мы получим

input.Trim('e','r')
input.Trim('r','e')
input.Trim('a','e','r')
input.Trim('a','r','e')
input.Trim('e','a','r')
input.Trim('e','r','a')
input.Trim('r','a','e')
input.Trim('r','e','a')
input.TrimEnd('e','r')
input.TrimEnd('r','e') 
// 30+ more options

Как видите, первые два варианта – единственные, которые хотелось бы использовать. Все остальные обладают излишней информацией, которая не делает никому погоды. Или вот еще

ff7

Тут вариантов меньше, вот они:

input.Replace("aabb", "aa")
input.Replace("bb", "")
input.Replace("bbcc", "cc")

Единственная правильная опция выше – средняя. Две другие хоть и корректны с точки зрения семантики, все же – скорее всего не то, чего мы хотели добиться.

Еще одно интересное наблюдение – это то, что иногда интересные решения кроются на глубине, а не на поверхности. Вот например

ff8

Тут можно просто удалить пробел, но CallSharp дает много вариантов, например

input.Replace(" ", string.Empty)
input.Replace(" b ", "b")
input.Replace("a b ", "ab")
input.Replace(" b c", "bc")
input.Replace("a b c", "abc")
// at greater depth,
string.Concat(input.Split())

Лучшие варианты – первый и, возможно, последний – он хоть и подороже с точки зрения выполнения (наверное, не проверял, интуиция подсказывает), но выглядит элегантно. Это хороший пример того, как программа может вывести то, что человек сразу не увидит.

Резюмируя

Сейчас CallSharp работает, скажем так, небыстро. Проблема в основном в использовании reflection (в частности, MethodInfo.Invoke()) а также в комбинаторных взрывах связанных с глубиной вызовов и количеством аргументов и их вариаций.

Текущие проблемы с перформансом отчасти решатся при переезде от динамического до статического reflection (предполагается сделать всё на T4). Оптимизаций можно делать очень много – я бы например хотел сделать аннотации для разметки «коммутативности» как наборов функций, так и аргументов в функциях (например, порядок букв в Trim() не важен).

CallSharp – open source проект, лежит на GitHub. Там же есть его релизы – по ссылке click here установится ClickOnce дистрибутив, которые самообновляется по мере выхода новых версий.

Для тех, кому хочется чуть более живого повествования, ниже представлен мой доклад на Петербургской .NET User Group:

Спасибо за внимание!

Written by Dmitri

17 декабря 2016 at 14:34

Опубликовано в .NET

Tagged with ,

Ключевые особенности FPGA

2 комментария

Многие из вас наверное видели, что Amazon запускает инстансы EC2 с FPGA на борту. Я сразу признаюсь, что я никогда не пользовался облаками Amazon: я использую только Azure, и то только потому что мне некоторый объем вычислительным мощностей дают бесплатно как MVP (которым я являюсь уже ажъ 8 лет!), а до этого у меня просто стоял свой собственный сервер в универе, про который мало кто знал пока через одно веб-приложение (MindTouch Core, если кому интересно) на сервере кто-то установил спамбота, и понеслась.

Короче, я не юзаю Амазон облако, да и в последнее время стараюсь поменьше заказывать с Амазона: сейчас ведь там продают очень многие ритейлеры, у которых есть свои сайты, соответственно я скорее куплю за ту же стоимость у них, чтобы им перепало побольше, а Амазону — нуль. Думаю причины сего поведения с моей стороны вы итак прекрасно понимаете — Амазон прекрасен для покупателя (хотя скорость доставки в Англии упала до неприличия), но вот к программистам они, судя по “среднему по больнице”, относятся как к шлаку. И да, понятно что есть продуктовые команды в которых все нормально, но судя по тому что пишут на Reddit, общее положение все же весьма бредовое. Если вы там работаете, можете меня поправить и рассказать как все шикарно.

Ах, да, тьфу ты, я на самом деле немного некорректно тут написал. Основная проблема моя с Амазоном не в этом, а в том что они не берут PayPal. Это как бы критично т.к. на мелкие покупки я трачу только свой disposable income, а он у меня весь на PayPal.

Че-то я отъехал от темы. Вроде пост был про FPGA.

Концепция dataflow

У нас есть много разных плохо коммутируемых парадигм разработки – например процедурная, объектно-ориентированная, функциональная. А есть парадигма, которую можно называть “потоковой”, а по-английски она называется словом dataflow.

Идея dataflow тривиальна как в танке: представьте, что входные данные в системе проходят через некий map-reduce, т.е. обработку потока этих данных с некоторыми критериями выборки. Например на вход могут прийти три числа и нужна их сумма, то есть

int sum(int a, int b, int c)
{
  return a + b + c;
}

Возникает вопрос: сколько времени занимает код выше? Если мыслить о том что написано выше в терминах C++, C#, Java или аналогичных языков, то код — то есть набор инструкций — будет транслирован в несколько вызовов add, и соответствено займет ненулевое время на выполнение.

Сколько займет тот же самый алгоритм на FPGA? Ну, если утрировать до боли, но он займет нуль времени. Сигналы a, b и c будут поданы на соответствующие схемы, который в момент на выходе выдадут результат. Никаких “инструкций” не произойдет.

Понимание того, что программрование FPGA — это конфигурирование интегральной микросхемы (я тут возможно путаю терминологию, поправьте если что), а не описание набора инструкций — это ключ к пониманию того, что собственно можно выудить из технологии FPGA и к каким она задачам применима. Сейчас мы как бы понимаем, что когда по проводам идут данные с бешеной скоростью (например, интернет на 10G), обычный CPU — даже самый навороченный Xeon — не сможет эти данные переварить содержательно, разбирая, например, коммуникационный протокол по которому идут биржевые данные. Но это только часть задачи.

Аппаратный параллелизм

Современный процессор, безусловно, поддерживает некоторый уровень параллелизма: у нас есть “многоядерность”, у нас есть т.к. hyper-threading, ну и конечно у нас есть SIMD, который помошает делать больше вычислений за счет больших регистров. Но, так или иначе, этот паралеллизм заранее лимитирован процессором: мы знаем, например, что на Xeon Phi (60 ядер по 4 аппаратных потока каждое) не имеет особого смысла запускать более 240 потоков и, более того, на обычных CPU мы не контролируем, какая задача ложится на какой поток: это обычно делает операционная система (в случае с Xeon Phi там используется свой собственный Linux).

Ситуация с FPGA несколько другая: там за один такт можно делать совершенно несвязанные операции, и количество таких операций лимитировано только количеством логических элементов на кристалле. Иначе говоря, FPGA способствуют такому масштабу параллелизма, о котором с обычными CPU остается только мечтать.

Это не значит, что FPGA дает самый лучший performance. У нас есть очень мощные модели параллелизма (например SIMT на GPU) с которыми FPGA не может бодаться в плане обработки больших объемов данных. Но и цель у FPGA немножко не такая: ведь на GPU каждый поток должен делать одно и то же (иначе теряется вся эффективность), а FPGA может на разных своих участках делать абсолютно разные вещи. Синхронизация между этими участками — это достаточно сложная задача, конечно, но with great power… ну вы поняли.

Да, еще один аспект, который нужно упомянуть — это тактовая частота. На CPU тактовая частота одна, и все задачи синхронизуются на нее. На FPGA вы можете использовать разные генераторы (по английски clock), т.е. сигналы разной частоты для разных задач. Тактовая частота FPGA в целом существенно уступает CPU, но сравнивать их напрямую не особенно интересно, т.к. они служат разным целям.

Концепция pipelining

Я не буду скрывать, что и на обычных Intel’евских CPU происходит много всякой магии вроде branch prediction. По сути, современный ассемблерный код, который выдает вам С++ компилятор с включенными оптимизациями, читать достаточно сложно про причине того, что количество “магии”, которое обычно вкладывается в погони за перформансом, огромно. Ассемблер можно читать разве что в идеальном мире, без оптимизаций.

Pipelining объяснить просто. Возьмем следующий код:

void mad(int* a, int* b, int* c, int* result size_t count)
{
  for (size_t i = 0; i < count; ++i)
    result[i] = a[i]*b[i] + c[i];
}

Вы наверное думаете что каждая итерация цикла for должна закончиться прежде, чем начнется новая. В контексте С++ вы правы, а в контексте FPGA — нет!

Представьте операцию a*b+c как микросхему, работающую под определенной тактовой частотой: на первый шаг, вы подаеет значения a и b и получаете их произведение. Потом надо бы прибавить c, а что в это время делает та часть которая умонжает. Думаете она простаивает и ждет пока завершится вычисление? А вот и нет! Эта часть схемы может брать и считать следующее произведение, т.е. a*b для следующей пары чисел a и b.

Вот это и называется pipelining: возможность сразу пропускать целый поток значений, не дожидаясь завершения всего вычисления. И, как вы надеюсь уже догадались, это приводить к существенному ускорению, т.к. является de facto еще одним уровнем аппаратного параллелизма.

Что такое SoC

SoC расшифровывется как System-on-a-Chip, и в контекте она подразумевает некую аггломерацию FPGA с обычными процессорами вроде ARMов. При этом эти процессоры не просто “сосуществуют на плате”, а ARM встроен прямо в FPGA.

А вот это уже интересно, т.к. на ARM мы просто ставим свою собственную ось (вопрос про то, можно ли туда поставить Windows остается открытым, т.к. MS как-то протормаживают в этом плане), и тем самым получаем на одном кристалле, по сути, полноценно-работающий компьютер — нужно только добавить оперативки и периферию (например PCIe, Ethernet, …) по вкусу. Собственно это должно объяснять почему это “system on a chip” — на одном кристалле все, что нужно чтобы выполнять какую-то экспертную задачу.

Покупка Intel’ем компании Altera, второго по размеру производителя FPGA, намекает на симметричное развитие Xeon’ов: идея в том чтобы воткнуть в процессор какой-нть FPGA и дать разработчикам программировать его и осуществлять взаимодействие между CPU и FPGA вместо того чтобы ходить по PCIe шине, как предлагает Amazon.

Кстати, покупка Altera может выйти сильным боком Российским производителям (в т.ч. ВПК и тем кто под санкциям). Причина проста — сейчас, Altera и в частности ее дистрибьютор Terasic — это коррумпированая Тайваньская лавочка, которая вышлет что угодно и куда угодно, в то время как лидер рынка, Xilinx, каждую закупку пропускает через DoD на предмет санкций, dual use и так далее. Если Intel начнет себя вести так же, настанут очень веселые времена. Или вы думаете что в РФ у кого-то есть производственные мощности для импотрозамещения? Ну-ну.

Высокоуровневый синтез

HLS (high-level synthesis) — это не что иное, как кодогенерация VHDL/Verilog из более популярных языков вроде С++ и SystemC. Последний — этот тот же С++, как мне видится, только с некоторым набором конструктов для системного мира (например fixed-point types).

HLS подходов очень много, и объединяет их то, что все они генерируют очень сложную к прочтению и пониманию кашу, которую уже некомфортно читать. Помимо этого, наивно полагать что вы можете взять уже существующий С++ и просто нажать кнопочку “сделать мне хорошо” — вы не можете так просто поменять процедурную парадигму на поточную. Возможность писать что-то новое на С++ дает, разве что, варианты портирования этого “что-то” на x86 и иже с ним, но опять же, непонятно что это дает — разве что тестировать это можно быстрее, да и в Cling-е гонять.

Лично я склонен думать, что у HLS будущее, и что HDL’и должны отмереть за их чрезмерной низкоуровневостью. Но пока что, они — лучший способ описать, что и как должно произходить в системе. ■

Written by Dmitri

11 декабря 2016 at 22:00

Опубликовано в FPGA

Tagged with , , ,

Приемы взятия сложных интегралов

3 комментария

Интегралы, что может быть веселее? Ну, возможно не для всех, но все же, я уже давно ничего не постил такого сугубо математического, так что попробую. Этот пост – про то как брать «сложные» интегралы. Этот пост подразумевает что читатель учился таки в школе и знает тривиальные подходы (например, интегрирование по частям). В посте мы будем обсуждать только интегралы Римана, а не интегралы Лебега-Стилтьеса, Ито, Скорохода и так далее (хотя я бы с удовольствием, чесслово).

Весь этот пост — маленькая выборка рецептов или «паттернов» которые можно взять в копилку и потом применять. Пост рекомендуется читать на high-DPI дисплее дабы предотвратить глазное кровотечение. Я предупредил.

Переход к полярным координатам

Начнем с немного избитого метода — перехода к полярным координатам. Примечательно, что переход к полярным координатам можно применять даже там где, казалось бы, речь о декартовых координатах не идет вообще. Например, неопределенный интеграл Гаусса \textstyle \int e^{-x^2} {\mathrm d}x не имеет аналитического решения, а вот определенный интеграл \textstyle \int_{-\infty}^{\infty} e^{-x^2} {\mathrm d}x = \sqrt{\pi}.

Доказать это можно вот как: сначала, чтобы применить преобразование координат, мы вводим две переменные интегрирования \textstyle x и \textstyle y так что

I = \int_{-\infty}^{\infty} e^{-x^2} {\mathrm d}x = \int_{-\infty}^{\infty} e^{-y^2} {\mathrm d}y

Декартовы координаты можно выразить через полярные \textstyle (r, \theta) вот так:

\begin{align*}
x &= r \cos \theta \\
y &= r \sin \theta \\
r^2 &= x^2 + y^2
\end{align*}

Интегрирование от \textstyle -\infty до \textstyle \infty в декартовой системе координат — это то же, что интегрирование \textstyle r от \textstyle 0 до \textstyle \infty и \textstyle \theta от \textstyle 0 до \textstyle 2\pi.

В результате получим следующее:

\begin{aligned}
I\cdot I &= \int_{-\infty}^{\infty} e^{-x^2} {\mathrm d}x \int_{-\infty}^{\infty} e^{-y^2} {\mathrm d}y \\
&= \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} e^{-x^2-y^2} \;{\mathrm d}x\;{\mathrm d}y \\
&= \int_{0}^{2\pi} {\mathrm d}\theta \int_{0}^{\infty} e^{-r^2} r \;{\mathrm d}r \\
&= 2\pi\int_{0}^{\infty}  e^{-r^2} r \;{\mathrm d}r \\
&= \pi\int_0^{\infty} e^{-r^2} \;{\mathrm d}r^2 = \pi \\
\end{aligned}

\therefore I = \sqrt{\pi}

Этот же подход может применять и в 3-х измерениях с использованим сферических координат \textstyle (x,y,z) \rightarrow (r,\theta,\phi).

Геометрические интерпретации

Вообще, «скатывание в геометрию» порой приносит плоды. Вот например допустим вам надо посчитать

\int_0^\infty \frac{{\mathrm d}x}{1+x^2}

Уверен, многие из вас знают что у этого интеграла есть аналитическое решение \textstyle \tan^{-1}x, поэтому посчитать определенный интеграл не составляет труда. Но на самом деле, этот интеграл можно посчитать даже без этого знания.

Представьте круг с радиусом \textstyle r с центром \textstyle (0,0). Длина дуги этого круга с центральным углом \textstyle \theta равна \textstyle L = r\theta, а если круг единичный – то просто \textstyle \theta. Тогда

L = \theta = \int_0^{\theta} \;{\mathrm d}t

где \textstyle t — это произвольная переменная интегрирования.

При таком раскладе, подынтегральное выражение равно \textstyle 1, но мы можем его усложнить, например

\begin{align*}
L &= \int_0^{\theta}1 \;{\mathrm d}t \\
&= \int_0^{\theta}\frac{\frac{1}{\cos^2t}}{\frac{1}{\cos^2t}} \;{\mathrm d}t \\
&= \int_0^{\theta}\frac{\frac{1}{\cos^2t}}{\frac{\cos^2t+\sin^2t}{\cos^2t}} \;{\mathrm d}t \\
&= \int_0^{\theta}\frac{\frac{1}{\cos^2t}}{1+\tan^2t} \;{\mathrm d}t \\
\end{align*}

Далее, делаем подстановку

x = \tan t \Rightarrow {\mathrm d}x = \frac{{\mathrm d}t}{\cos^2 t}

Тем самым, получаем

L = \int_0^{\tan \theta}\frac{{\mathrm d}x}{1+x^2}

Допустим что \textstyle \theta = \frac{\pi}{2}. Тогда \textstyle \tan \theta = \tan \frac{\pi}{2} = \infty, а поскольку \textstyle \frac{\pi}{2} отмеряет нам ровно четверть круга (длина всего единичного круга \textstyle 2\pi), мы моментально получаем результат

\frac{\pi}{2}=\int_0^{\infty} \frac{{\mathrm d}x}{1+x^2}

По аналогии с этим результатом можно получить и другие, разбивая круг на разное количество отрезков, например

\begin{align*}
\frac{\pi}{4} &= \int_0^1 \frac{{\mathrm d}x}{1+x^2} \\
\frac{\pi}{3} &= \int_0^{\sqrt{3}} \frac{{\mathrm d}x}{1+x^2} \\
\end{align*}

и так далее.

Разбиение диапазона интегрирования

Допустим вам надо посчитать

\int_0^{\infty} \frac{\ln x}{1 + x^2} \;{\mathrm d}x

Для взятия этого интеграла, разобъем диапазон интегрирования на два, т.к. \textstyle \int_0^{\infty}=\int_0^1+\int_1^{\infty}.

Займемся сначала первым интегралом, т.е. \textstyle \int_0^1. Сделаем подстановку \textstyle t = 1/x \Rightarrow {\mathrm d}x=-{\mathrm d} t/t^2 . Получим

\begin{align*}
\int_0^1 \frac{\ln x}{1+x^2} \;{\mathrm d}x &= \int_{\infty}^1 \frac{\ln(1/t)}{1+1/(t^2)}\left(-\frac{1}{t^2}\;{\mathrm d}t\right) \\
&= - \int_{\infty}^1 \frac{\ln(1/t)}{t^2+1}\;{\mathrm d}t \\
&= \int_1^{\infty} \frac{\ln(1/t)}{t^2+1}\;{\mathrm d}t \\
&= - \int_1^{\infty} \frac{\ln t}{t^2+1}\;{\mathrm d}t
\end{align*}

То есть внезапно оказалось, что поставленная переменная \textstyle t выполняет такую же функцию что и \textstyle x. Другими словами, \textstyle \int_0^1 = -\int_1^{\infty} а это значит что мы автоматически получаем значение искомого интеграла:

\int_0^{\infty}\frac{\ln x}{1+x^2}\;{\mathrm d}x = 0

Разбиениe на четное и нечетное

Вот нужно вам например посчитать

\int_{-1}^{1} \frac{\cos x}{e^{1/x}+1} \;{\mathrm d}x

Давайте сделаем несколько замен:

\begin{align*}
f(x) &:= e^{1/x} \\
g(x) &:= \frac{\cos x}{f(x)+1}
\end{align*}

Теперь нам нужно посчитать \textstyle \int_{-1}^{1} g(x) \;{\mathrm d}x, и вот тут начинается самое интересное. Мы переписываем \textstyle g(x) как сумму четной и нечетной функции:

g(x) = g_e(x) + g_o(x)

Многие спросят «а так вообще можно?» — на самом деле да, и вот почему. Возьмите и воткните в определение выше \textstyle -x вместо \textstyle x. Вы получите

g(-x)=g_e(-x)+g_o(-x)=g_e(x) - g_o(x)

благодаря свойствам четности и нечетности функций. Следовательно, мы можем выразить четную и нечетную сторону функции как

g_e(x)=\frac{g(x)+g(-x)}{2}

и

g_o(x)=\frac{g(x)-g(-x)}{2}

Так-то. Соответственно, наш интеграл можно переписать как

\int_{-1}^{1}g(x) \;{\mathrm d}x = \int_{-1}^{1}g_e(x) \;{\mathrm d}x + \int_{-1}^{1}g_o(x) \;{\mathrm d}x = \int_{-1}^{1}g_e(x) \;{\mathrm d}x

Как видно выше, нечетная функция пропала полностью, осталась только четная сторона, т.к.

\int_{-1}^{1}g_o(x) \;{\mathrm d}x = 0

Ладно, вам уже наверное надоело ждать сути этого примера. Так вот, у нас есть формула \textstyle g_e(x)=\frac{g(x)+g(-x)}{2}, дайвате воткнем в эту формулу \textstyle g(x). Мы получим

g_e(x)=\frac{1}{2}\left(\frac{\cos x}{f(x)+1}+\frac{\cos (-x)}{f(-x)+1}\right)

Но мы-то знаем, что \textstyle \cos x — четная функция, поэтому \textstyle g_e(x) можно переписать как

\begin{align*}
g_e(x) &= \frac{\cos x}{2}\left(\frac{1}{f(x)+1} + \frac{1}{f(-x)+1}\right) \\
&= \frac{\cos x}{2}\left(\frac{f(-x)+1+f(x)+1}{f(x)f(-x)+f(x)+f(-x)+1}\right) \\
&= \frac{\cos x}{2}\left(\frac{2+f(-x)+f(x)}{f(x)f(-x)+f(x)+f(-x)+1}\right) \\
\end{align*}

Это какое-то месиво и непонятно что с ним делать. Но с другой стороны посмотрите, у нас в формуле присутствует \textstyle f(x)f(-x). Давайте вспомним, что \textstyle f(x)=e^{1/x} и мы получим

f(x)f(-x)=e^{1/x}e^{-1/x}=e^0=1

Ну вот и всё — наша страшная дробь выше уже совсем не страшная т.к. числитель и знаменатель равны, а это значит что

g_e(x) = \frac{\cos x}{2}

а сам интеграл теперь легко посчитать:

\int_{-1}^{1} \frac{\cos x}{e^{1/x}+1}\;{\mathrm d}x &= \int_{-1}^{1} \frac{\cos x}{2} \;{\mathrm d}x = \sin(1) = 0.841...

Хотите ещё?

Я на самом деле понял, что по объему для одного поста вполне достаточно. Сорри если что написал не так — я по-русски прочитал ровно нуль математических книг (чего и вам советую), так что терминология может страдать.

Существует еще вагон разных трюков, так что, если интересно, советую глянуть соответствующую литературу. Удачи! ■

Written by Dmitri

9 ноября 2016 at 16:57

Опубликовано в Mathematics

Tagged with

Разработка под FPGA бесит, но что делать?

2 комментария

В моем предыдущем посте, я жалуюсь на FPGA но, как вы знаете, нытьё я не люблю — если что-то не нравится, нужно это что-то менять. Но для того чтобы понять что конкретно не нравится, нужно описать проблемы, что и будет в этом посте.

Давайте для начала сформулируем несколько банальных отличий HDL языков от обычных языков вроде С или С++. Тут все до боли банально:

  • HDL языки позволяют писать как последовательный (как и С) код, так и код который выполняется параллельно в конструкции, которую они называют process но на самом деле мы можем назвать как “условно-бесконечный while(true)”. На самом деле я лукавлю, т.к. этот бесконечный цикл работает не постоянно, а на основе событий (изменений сигналов), но это сводит его к обычному event loop в одном аппаратном потоке. Никакой магии тут нет.

  • HDL языки позволяют из маленьких логических компонент строить более сложные путем “соединения проводков” между разными элементами дизайна. Это конечно красиво, но это можно делать и в обычных языках путем правильной записи переменных. Разница лишь в том, что касательно HDL переменные — это то что ты присваиваешь последовательно (не очень-то эффективно), а параллельно присваиваются сигналы.

  • HDL языки, когда им нужно один компонент несколько раз разместить в схеме, используют статическую кодогенерацию (generate statement) которая конечно очень круто, с одной стороны, но с другой стороны — весьма тривиальная вещь которой вообще не стоит гордиться.

  • HDL языки можно симулировать прежде чем заливать в FPGA. Это конечно классно, но то как это выглядит — не особо удобоваримо.

Все это выглядит так, как будто над нами издеваются, причем жестко: ничего в списке выше не требует создания нового языка. Экосистемы — да, конечно, но языка — увольте, это какое-то безумие. Вместо этого, один из языков который можно использовать — это SystemC. Другой, который наглая Altera (читай Intel) дает использовать только на некоторых, б-гоизбранных платах, это OpenCL — да-да, та самая поделка которая програла CUDA войну за GPU.

Один из вариантов — это адаптировать Тлён для кросс-компиляции в VHDL, но для этого нужно сначала обсудить самые простые особенности, например типы данных.

Типы данных в VHDL

Вот список типов которые есть в VHDL (ну или в SystemC или чем-то аналогичном):

  • bit — вот эта штука действительно 0 или 1, тут не поспоришь.

  • bit_vector — это, соответственно, произвольный набор бит. Например bit_vector(0 to 8) делает вам целый байт! Количество битов можно самому выбирать, что очень хорошо ложится на Rust-образное описание целочисленных значений.

  • std_logic (VHDL) / sc_logic (SystemC) — понятие “логическое значение”, что на самом деле просто перечисление в котором есть как варианты 0/1 так и другие, причем в SystemC вариантов логического значения 4, а в VHDL – целых 9! Формально, посторонние значения нужны для симуляции, но есть также понятие tri-state logic (когда сигнал вообще ни к чему не подключен).

  • std_logic_vector это соответственно целый набор этих логических значений.

  • sc_fixed (SystemC) — возможность делать fixed-point arithmetic. Это пока вообще не доступно на С++ и подобных, разве что вы сами библиотеку напишете. Не то чтобы это сложно, но тут это “в железе”.

  • integer/float/wtf — возможность не только выделять нужный объем бит, но и делать всякие операции вроде сложения и даже умножения и деления (хотя эти две операции – не очень дешевые).

  • character — восьмибитная буква (ASCII). Все конечно хорошо, но…

  • string — я сейчас даже не буду говорить про то, что в VHDL, “010101” это одновременно и строка и bit_vector и std_logic_vector, просто скажу что строка на FPGA конечно же нединамическая. То есть tweet : string(1 to 160) дает нам фиксированный массив букв.

Естественно что работать без std::vector/set/map очень больно. Точнее, возможно кто-то скажет что так и надо, что мы описываем электрическую схему, которая не может просто аллоцировать и деаллоцировать память как хочется. С другой стороны, мы не маленькие и понимаем что в принципе можно выделить большое количество регистров и потом пытаться трекать общую длину полезных данных на этом поле.

Последовательность и параллелизм

То, как VHDL делит последовательные и параллельные конструкты – в корне неправильно. По идее, должно быть так: за один такт часиков мы хотим сделать ABC. Потом, мы хотим сделать DEF. Вот как-то так. А не перемешивать все в одной куче. Но тут есть один нюанс.

Нюанс в том, что в качестве сигнала изменения может быть не только clock, но и сигнал, который просто поменял своё значение. Например кто-то на кнопочку нажал. А вот это уже существенно ломает как мозг, так и нашу модель.

Вообще, если вы почитаете интернеты, по поймете что делать все “в один такт” на FPGA не реально. И помимо этого, есть еще пренеприятнейшая проблема которая называется glitching. Я сейчас не буду вдаваться в детали, но проблема в том, что даже имея схему которая дает детерминированный результат, из-за того что переход уровней сигнала идет не моментально, у вас может возникнуть ситуация, в которой на какие-то несколько наносекунд сигнал перейдет в состояние, которое не согласуется с тем, что должно быть на выходе. Сейчас найду видео… вот, ловите.

Так вот, о чем я… да, с одной стороны массовый паралеллизм, с другой стороны все равно не на глобальном масштабе, что впрочем итак нереально ввиду того, что описывать комбинаторно алгоритмы — это мучительно. Да, можно развить бешеную скорость относительно CPU, но… вообщем я оставлю эту дискуссию на будущее.

Что делать-то?

Тулы делать, товарищи. Тулы. На текущий момент симулятор выглядит как-то вот так:

Ничего странного не замечаете? Тут линиями показаны уровни сигнала – 0, 1, иногда U (уровень неизвестен). И вообще, в классической логике уровней сигнала всего два: 0 или 1, false или true. В std_logic их девять. И да, эти безумные типы для симуляции и прочего.

Короче, для начала нужен симулятор которые воспринимает VHDL (или Verilog, мне все равно) как последовательно-паралелльную программу, и позволяет ее гонять и дебажить примерно так же, как Visual Studio со всякими там Parallel Stacks и иже с ним. Это вполне реально написать, причем за не очень большие сроки.

Вторая часть уравнения — это сделать все это еще и на девайсе. Все равно то, что мы делаем когда захватываем несколько тысяч сэмплов с FPGA — это по сути historical debugging a la IntelliTrace. То же самое.

Короче, решение этой проблемы простое — нужно просто переделать все на высоком уровне. Лучше всего — выкинуть на помойку VHDL/Verilog, взять OpenCL (его кстати уже поддерживают некоторые, богоизбранные платы) и воткнуть все это в какую-нибудь вменяемую IDE (например IntelliJ). Profit! Но не тот профит к которому привыкли тул вендоры, т.к. FPGA, как показывает практика, это технологически закрытая тема, там новых игроков не любят.

Вообщем что-то нужно делать. Я пока еще думаю, как все эти мысли конкретно описать.

Ложка дегтя

Заказал отладочную плату, она пришла в СПб DHLем, и понеслась Рассея матушка, безумная и беспощадная, втирать мне как я должен 100 штук бумажек вручную оформить чтобы все это ввезти… вообщем поедет она назад в Тайвань, а оттуда куданть еще. Мой вам совет: заказываете железки обычной почтой. На обычную почту не смотрят. ■

Written by Dmitri

29 октября 2016 at 0:55

Опубликовано в FPGA

Почему разработка под FPGA бесит

3 комментария

Сегодня я ходил на конференцию Joker (это Java конфа, так что не совсем моя тематика) и, в разговоре с (бывшими) коллегами из JetBrains, я упомянул что в разработке железа (всякие HDLи) настоящая катастрофа с тулами и производительностью разработчика. В этом посте я хочу немного раскрыть тему, рассказать про то, что вообще можно сделать с железом и почему же разработка под него так мучительна.

Status Quo

Мы живем в мире, где доминируют микропроцессоры, работающие на основе инструкций. Самым популярным набором инструкций является конечно x86, но есть и другие варианты. Эта технология, если говорить конкретно про Intel’евские i7 и Xeon’ы, обкатана, хорошо работает, и самое главное она везде, что гарантирует некую совместимость, на тот случай если вы поставляете софтварный продукт.

Поверх x86 есть еще ряд технологий, которые выдают аппаратную оболочку через софтварный API: это например OpenGL и DirectX для игр и CUDA для обобщенных вичислений на графических картах компании NVIDIA. Это из того что популярно и хоть где-то используется — например, Adobe в своих видео продуктах использует Mercury Engine, которая как раз амортизирует CUDA (умеет ли она использовать OpenCL — не знаю, не уверен).

В целом, игровые карточки — это единственный пример железа, который докупается к компьютеру для ускорения производительности в некоторых сценариях. Ничего аналогичного не существует. Даже звуковые карточки канули в лету, да и на графику сам же Intel наступает, добавляя ее к процессору. Но с графикой — уникальная ситуация.

Аппаратные ускорители

x86 решает подавляющее большинство задач. К сожалению, есть задачи которые отдельно взятый процессор, даже самый дорогой Xeon решить по тем или иным причинам не может. Огромный поток данных, которые льются с биржи, не всегда реально обработать на CPU, а если и реально, то с большими задержками. Или аппаратное шифрование — то, что дает вам возможность использовать BitLocker или его аналоги: это отдельный модуль в компьютере.

Есть куча доменно-специфичных задач, которые можно ускорить железом. Также, некоторые структуры данных и алгоритмы, которые вы используете в C++, можно сделать быстрее в железе, т.к. в отличии от Intel процессоров, где уровень параллелизма заранее ограничен кол-вом ядер (ну и плюс “аппаратными потоками”, это я про hyper-threading итп), уровень параллелизма на FPGA массивен. Нужно только задачу найти.

Вообще, в контексте аппаратных ускорителей, я бы упомянул вот эти категории

  • GPGPU — вычисления на графических картах. Хороши только для численных вычислений (математика) и только для data-parallel вещей (там где нет брэнчинга).

  • Intel Xeon Phi — копроцессоры от Intel. Отдельная PCIe карта, на которой 60+ ядер (4 аппаратных потока на ядро), свой Linux, и которую можно использовать либо как компьютер-в-компьютере, либо в тандеме с хостом, отгружая часть данных для рассчетов.

  • FPGA — ПЛИСы или “вентильные матрицы”, технология реконфигурируемого комьютинга, которая позволяет по сути создать свой собственный процессор вместо того чтобы использовать готовый. Ест очень мало энергии. Поддерживает нереальную параллелизацию, но программируется на языках описания железа (Hardware Description Languages, HDLs).

FPGA решают очень много интересных задач и, будь они чуть развитее, на них бы все и писали. Но эта технология, как и вся хардварная область, не торопится становиться удобоваримой для обычных разработчиков.

Языки описания железа

Железо можно конечно описывать цифровыми схемами, но если учесть что на умножение двух 16-битных чисел может потребоваться 6000 логических ворот, это как-то некомильфо. Поэтому придумали другие языки (самый популярные — VHDL и Verilog), на которых описывается структура и поведение конфигурируемых цифровых систем вроде FPGA.

Проблема №1 этой затеи заключается в том, что вся работа идет на низком уровне. Это значит что нет:

  • Механизмов динамического управления памятью, и как следствие…

  • Динамических структур данных, таких как динамический массив/список/отображение

  • Стандартных алгоритмов (сортировка, поиск)

Короче, нет ничего, с чем мы обычно привыкли работать. Всесто этого, у нас есть совершенно другая модель, под которой мы моделируем движение электричества по системе. Впрочем, для этого нужно отдельную секцию нам с вами выделить, а так можно потеряться в этом безумном многообразии.

Модели описания поведения интегральной схемы

Для начала, следует понимать, что у нас есть два режима взаимодействия с железом, а именно:

  • Последовательный — это когда все те “инструкции” что вы написалы выполняются одна за одной. Это касается в основном присваивания переменных — а в разработке железа есть еще и “сигналы”, с которыми можно работать в параллельном ключе.

  • Параллельный — тут все самое интересное, т.к. можно описать поведение системы, в которой несколько вещей происходят действительно одновременно.

Соответственно мы, как разработчики железа, можем описывать и оптимизировать параллельно-последовательную структуру FPGA в одном приложении и, заметьте, что такие термины как “многопоточность” не имеют никакого смысла вообще, т.к. нет никаких “виртуальных потоков” в контексте одного аппаратного.

Одна вещь, которую мы не обсудили — это хранение в памяти. Точно так же как у CPU есть регистры, кэши разного уровня и RAM, на FPGA есть возможность хранить данные — прямо в логических ячейках или в RAM, если он вам предоставлен. То есть чисто теоретически, можно конечно пытаться строить динамические структуры, но что там по перформансу — я не знаю.

В чем проблема?

Субъективно говоря, разработывать на FPGA то же самое что на CPU раз в 100 сложнее. Вреня-деньги, и никто их не будет тратить на мучения.

Отчасти в катастрофическом, просто идиотском затыке виноваты чисто тулы, то есть EDA которые используются для разработки. Тулы воспринимают FPGA как электрическую схему с набором сигналов вместо того чтобы воспринимать ее как некоторый domain transform обычных программ в зону параллельного.

Вообще, как нынче модно на рынке, сюда могут забежать люди и сказать что де “меняй менталитет”, у нас все так, терпи или вон с рынка. Но мне кажется что нужно как раз больше думать про high-level synthesis: может кому-то и нравятся VHDL/Verilog, но все-таки нужно начинать с того чтобы переходить полностью на высокоуровневый синтез.

Я в какой-то момент пробовал MATLAB, но что-то мне подсказываeт, что будущее на FPGA за OpenCL. Но это решает только проблему языка: еще есть проблема отладки, в которой пока все почему-то считают что мы следим за уровнем сигналов, а не за агрегированным состоянием ООП-образных структур.

И да, объекты, товарищи! Я не настаиваю на присутствии v-табличке, но если мне нужно распарсить биржевой протокол, то лучше все это будет на каком-то вменяемом языке.

Про низкоуровневость

Чтобы реализовать устройство для ethernet на PCIe нужно по обе стороны реализовывать протоколы. Это ппц как сложно. Вот вы, вы хотите писать свой собственный драйвер? Я — нет. Я даже не знаю как все это устроено.

А ведь производители могли бы все разжевать и в рот полодить. Почему CUDA может, а FPGA производители — нет? Потому что им всем на нас плевать, и они ничего не понимают.

Ничего…

Со всем этим нужно бороться. Менять парадигму, выводить тулы строго в опенсорс (это хороший пример где проприетарщина == гниль). Всех несогласных закопать.

Я пишу feed handler. Детали будут позже. ▪

Written by Dmitri

17 октября 2016 at 21:08

Опубликовано в FPGA

Не нравится ООП? Делайте свой язык программирования!

24 комментария

В интернете нынче модно говорить что «ООП это шлак», и многие мечтают сделать свой собственный язык программирования но чего-то боятся. А на самом деле, если подойти с умом, тут все просто. Серьезно! Я знаю, вы хотите мне возразить, что дескать…

  • Писать свой компилятор в native code/IL/bytecode слишком сложно — а и не надо!! Вы понимаете, что существующие компиляторы вроде С или Java оттачивались годами, сотнями людей? Почему бы не воспользоваться всем этим богатством, компилируя ваш язык в тот же С/C++, и потом получая от С/C++ компилятора все оптимизации и плюшки?

  • Меня не прет идея возиться с кастомными форматами файлов для лексинга и парсинга, это депрессивно — а и не надо!! Просто возьмите фреймворк, который поддерживает парсеростроение прямо в коде.

  • У меня сейчас весь код на Java/C#/C++ написан, как я сделаю interop? — да очень просто, ведь с подходом транскомпиляции, вы можете транслировать свой язык в любой из вышеперечисленных, генеря и потом потребляя любой интерфейс, причем в обе стороны.

  • Язык-то я сделаю, а как насчет поддержки языка в моей любимой IDE? — о, ну это уже высший полет. Для начала, постарайтесь сделать лаконичный маленький язык, для которого инструменты не критичны. А потом можно научиться и тулы поддерживать (или писать свои).

Ну что, убедил?

Чтобы показать насколько это все просто, вот небольшой пример: представим, что вы хотите расширить определение С-образной глобальной функции, добавив следующие фичи:

  • Определить свой набор «коротких» типов переменных, вроде i32 или f64 на замену int и double.

  • Передавать аргументы в формате x,y : i32, то есть переиспользуя определение типа для нескольких сразу.

  • Добавлять в тело функции определения переменных вроде x = 5 так чтобы, при условии что x не имя параметра, это преврашалось в полноценную декларацию переменной, а иначе просто присваивалось значиние.

Для начала такой фичесет подойдет? Я знаю что мало, но я тут и не пытаюсь целый язык сделать. Вот как это будет выглядеть:

Наш язык… …станет вот этим
void foo(x,y:i32, z:f64)
{
  x = 5;
  w = 123;
}
void foo(int32_t x, int32_t y, double z)
{
  x = 5;
  int w = 123;
}

Структуры для языка

Во всех языках есть механизмы построения парсеров. Я возьму C++ и Boost.Spirit, для примера, но вообще язык тут особого значения не имеет. Для начала давайте сделаем новые типы вроде f32 вместо float:

struct numeric_types_ : qi::symbols<wchar_t, wstring>
{
  numeric_types_()
  {
    add(L"i32", L"int32_t");
    add(L"f32", L"float");
    add(L"f64", L"double");
  }
} numeric_types;

Теперь определяем функцию:

struct function
{
  wstring name;
  vector<parameter> params;
  vector<assignment_statement> assignments;
 
  // поиск параметра по имени; реализация банальна
  boost::optional<const parameter&> find_parameter(const wstring& name) const;
};

У любой функции есть имя, она берет сколько-то там параметров (ну, деклараций параметров, но краткость сестра таланта), и у нее есть тело, которое в нашем случае будет состоять исключительно из присвоений значений переменным (не очень практично, I know).

Поскольку мы умеем определять аргументы в стиле x,y:i32, т.е. несколько с одним типом, собственно структур parameter мы определим вот так:

struct parameter
{
  vector<wstring> names;
  wstring type;
};

Ну и наконец присвоение значений переменным можно сделать вот так:

struct assignment_statement
{
  wstring variable_being_assigned;
  wstring value;
  wstring infer_type() const
  {
    if (value.find(L'.') == wstring::npos)
      return L"int"s;
    return L"float"s;
  }
};

Выше показан г~код для определения типа, думаю вы понимаете что в последствии это можно пофиксить.

Всё, структуры готовы, можно строить парсер. (На самом деле есть еще этап их адаптации через Boost.Fusion, но это implementation-specific деталь, если что гляньте в сорцы.)

Парсер

Парсер для нашего языка написать настолько легко что я просто приведу весь код целиком, а потом мы его обсудим, ок?

template<typename Iterator>
struct function_parser : qi::grammar<Iterator, function(), space_type>
{
  function_parser() : function_parser::base_type(start)
  {
    using qi::lit;
    param %= 
      +alnum % ','
      >> ':'
      >> numeric_types
      >> -char_(',');
    assignment %=
      +alnum
      >> '='
      >> +alnum
      >> ';';
    start %= lit("void ")
      >> +(char_ - '(')
      >> '('
      >> *param
      >> ')'
      >> '{'
      >> *assignment
      >> '}';
  }

  qi::rule<Iterator, parameter(), space_type> param;
  qi::rule<Iterator, assignment_statement(), space_type> assignment;
  qi::rule<Iterator, function(), space_type> start;
};

Для начала, вот эти qi::rule просто говорят парсеру как то что он распарсит ложится на структуры что мы определили ранее. Например, вот хочется распарсить присваивание вроде x = 3, что это? Это идентификатор (то есть, 1 и более alphanumeric символов), потом =, потом еще раз набор символов и в конце ;.

Конкретно в Boost.Sprit, в отличии от регулярок, «один и более» записывается как + до типа символа, т.е. +alnum. То есть + означает «один и более», * — «сколько угодно», и так далее. Вот и получается что присваивание мы распарсили, а поскольку наш qi::rule мэпит его на assignment_statement, поля этой структуры будут присвоены автоматически. Это гениально, или как?

То же и с другими частями языка. Хочешь распарсить несколько переменных через запятую и запихнуть их в вектор? Пишем +alnum % ',' где оператор % – это как сказать *(+alnum >> ','), только короче. Что тоже удобно.

Так вот, парсер у нас готов, можно парсить. На Spirit это делается вот так:

template<typename Iterator>
wstring parse(Iterator first, Iterator last)
{
  using boost::spirit::qi::phrase_parse;
  function f;
  function_parser<wstring::const_iterator> fp{};
  auto b = phrase_parse(first, last, fp, space, f);
  if (b)
  {
    return render(f);
  }
  return wstring(L"FAIL");
}

…где render() – это функция которая обходит то что мы напарсили и генерит из этого чистейший, готовый к компиляции С (никто не мешает вам выводить сразу в N разных языков).

Pretty print

Короче, мы попарсили функцию, получили из нее ООП структуры, ну и теперь можно из них чего-нибудь нагенерить. Для этого их нужно обойти, что в нашем конкретном случае не сложно. Сначала пишем название функции:

inline wstring render(const function& f)
{
  wostringstream s;
  // name of the function (assume void-returning)
  s << "void " << f.name << "(";

Потом выводим параметры, не забывая что у нас может быть несколько имен для одного и того же типа аргумента:

// each of the parameters
const auto param_count = f.params.size();
for (auto i = 0u; i < param_count; ++i)
{
  auto& p = f.params[i];
  for (int j = 0; j < p.names.size(); ++j)
  {
    s << p.type << " " << p.names[j];
    if (j + 1 < p.names.size()) s << ", ";
  }
  if (i + 1 < param_count) s << ", ";
}
s << ")\r\n{\r\n";

А потом, аккуратненько, присваивания. Не забываем что тип нужно прописывать только если переменная не фигурирует где-то в параметрах функции:

// each of the assignments
const auto assign_count = f.assignments.size();
for (auto i = 0u; i < assign_count; ++i)
{
  s << "  ";
  auto& a = f.assignments[i];
  auto type = a.infer_type();
  bool is_param = f.find_parameter(a.variable_being_assigned) != boost::none;
  if (!is_param)
    s << type << " ";
  s << a.variable_being_assigned << " = " << a.value << ";\r\n";
}
s << "}";
return s.str();

Вот собственно и всё. Тут в принципе можно реализовать «полноценный» Visitor, если хочется.

Заключение

Как вы поняли, тут остался шаг компиляции полученного кода — думаю всем итак очевидно как это делать, это зависит от языка который вы нагенерили. Вообще я ратую за «портативный» C/C++, но решать в конечном счете вам.

Если хотите сорцы проекта, они тут. Мой пример на С++, но вы можете реализовать свой язык на чем угодно. Мораль в том что создать сейчас свой кросс-компилируемый язык легко, поэтому вместо того чтобы ныть про ООП и воевать с ветряными мельницами, проще сесть и запилить что-то своё. Так что садитесь и пишите спеку вашего чудо-юдо языка. Удачи!

Written by Dmitri

2 сентября 2016 at 16:10

Опубликовано в Programming

Tagged with , ,