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

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

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

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 , ,

C++ для Java и C# разработчиков

10 комментариев

Думаю мы все можем согласиться с идеей о том, что С++ разработчику достаточть легко в последствии освоить C#, Java или еще какой-то более современный язык. Но вот обратное — не совсем так. Многие разработчики начинают плеваться как только слышат про «ручное управление памятью» и подобные вещи. Суть этого поста — попытаться донести для разработчиков во-первых зачем им нужен С++, ну и показать как можно на нем делать те же вещи, к которым они возможно привыкли в других языка. А также объективно рассказать про те проблемы, которые в С++ до сих пор не решены.

Зачем нужен С++

Сегодня существуют три основных индустрии, которым нужен С++. Это

  • Игровая индустрия

  • Embedded development

  • Quant finance

В играх нужна производительность, поэтому С++ помогает ее достичь будучи ближе к железу чем языки основанные на виртуальных машинах. В С++ можно работать с памятью напрямую и даже вставлять в код куски Assembler’а.

В разработке для встроенных устройств тоже важна производительность, а также там ограничения по памяти которые порой не дают развернуть управляемую среду. Поэтому С и С++ все еще там популярны, хотя были и есть попытки запускать и C# (.NET) и Java на таких устройствах.

У нас в quant finance, С++ остался по историческим причинам. Финансовая индустрия весьма консервативна, а современные веяния высокочастотной торговли требуют максимум производительности. На уровне рассчетов моделей есть популярная библиотека QuantLib, но большинство алгоритмов пишут in-house, хотя тоже часто на С++.

Помимо производительности, есть еще несколько причин писать на С++. Одна из них это портативность (внезапно, да?) — на С++ вполне можно писать полностью портативный код. Я вот например использую Intel C++ Compiler (по фичам он «не очень»), который существует как на Windows так и на Linux.

Еще одна причина использовать С++ заключается в том, что это единственный способ амортизировать мощные аппаратные платформы, такие как CUDA и Intel Xeon Phi. Но это в основном для тех кто любит гоняться за пиковой производительностью.

Целочисленные типы

Когда я пишу в C# что-то вроде int x; я четко знаю две вещи:

  • Переменная x – это 32-битное целое число со знаком

  • Изначально, x содержит значение 0 (ноль)

В С++, мы не можем быть уверены ни в одном из этих утверждений. Тип int не определен с той строгостью какой бы хотелось (подразумевалось, что на других платформах — например embedded — у него может быть другой размер), а его дефолтное значение в большинстве случаев не определено, и там может быть что угодно.

Для решения первой проблемы, можно использовать С++ заголовок <cstdint>, который определяет такие типы как uint8_t, int32_t и так далее. Это существенно улучшает портативность кода.

Вторая проблема толком не решена, поэтому вам придется писать int32_t x{0};. К счастью, в С++ с последнее время наконец-то можно инициализировать поля класса прямо в теле, вот так:

class Foo
{
  int32_t bar{0};
  uint32_t baz = 42;
};

Статические поля так инициализировать, к сожалению, все ещё нельзя.

Строки

Со строками в С++ беда. Во-первых, изначально в С++, как и в С, строка была просто указателем на массив байтов (да-да, байтов а не code point’ов) с нулевым байтом \0 на конце. Это значит что вычисление длины строки — это O(n) операция.

Далее в C++ появился тип string, но с ним есть масса проблем. Например, у этого типа есть функции size() и length(), которые делают одно и тоже, но из API это совсем не очевидно. Но еще обиднее что там нет таких очевидных вещей как to_lower/upper() или split(), в результате чего приходится пользоватся сторонними библиотеками вроде Boost.

С++ весьма амбивалентентен в плане поддержки Unicode. Под Windows, кодировка строки типа string — ANSI, а вовсе не UTF-8. Есть также тип wstring, который использует UTF16 (ту же кодировку, что C# и Java).

Массивы

Изначально, массивы достались С++ из С, и это означает что массив — это просто указатель на первый элемент, и всё. То есть массив сам не знает какой он длины, и чтобы написать функцию которая обрабатывает массив, нужно 2 аргумента: указатель и длина.

Сейчас у нас есть такие типы как array и vector. Эти типы позволяют хранить либо массивы фиксированной длины (например array<int,3>) или, в случае с vector, иметь динамический массив, который расширяется и сужается по мере добавления в него элементов.

Многомерные массивы в С++ (как и в С) тоже выглядят плохо, т.к. являются всего лишь массивами указателей. Для них тоже стоит использовать array/vector, а еще лучше, если требуются вычисления, использовать специализированную библиотеку вроде Eigen.

Выделение памяти

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

В связи с этим, в отличии от языков со «сборкой мусора», в С++ есть два способа выделения (аллокации) памяти: на стэке и в куче.

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

int i;
Person person;

Другое дело — выделение в куче. Она для более долгосрочного хранения данных, и ответственность за очистку этой памяти лежит на вас. Если забудете, будет «утечка памяти», что очень плохо.

int* i = new int;
Person* p = new Person;
// а потом не забываем удалить
delete i;
delete p;

Как видите, для выделения в куче, мы используем оператор new, и он нам возвращает указатель на выделенную память. Чтобы освободить эту память, нужно использовать оператор delete.

Значения, указатели и ссылки

Давайте начнем с опеределений. Вот есть у вас переменная int32_t x{42}; — под нее выделено 4 байта, и каждый раз когда вы «берете» x, вы получаете значение 42 (ну, пока вы его не поменяли). Запись x = 11; запишет в эту память значение 11.

У нас также есть такая штука как указатель — это переменная, которая содержит адрес другой переменной. То есть можно написать вот так:

int32_t x{42};
int32_t* y = &x;

Тип этой переменной — со звездочкой, и звездочка означает что это указатель. Ее значение — это адрес переменной x, а чтобы взять адрес чего-либо в С++ нужно посдавить амперсанд, вот так: &x.

Хитрость тут в том, что через адрес переменной можно манипулировать самой переменной. То есть вместо x = 42 можно написать *y = 42. Заметьте что тут звездочка стоит перед именем переменной, и означает «следовать за». То есть мы идем туда, куда указывает y и в том месте памяти меняем значение.

Наконец, третий способ доступа к переменной — это ссылка. Ссылка действует так же как и указатель, только синтаксис другой. Вот смотрите:

int32_t x{42};
int32_t& z = x;
z = 11;

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

Также, в отличии от C#/Java, в С++ ссылка не может быть пустой (null). Это значит что все ссылки должны быть инициализированы, т.е. ссылаться на что-то. Это с одной стороны хорошо (в управляемых языках многие мечтают о non-nullable objects), но с другой стороны создает много проблем — например, если в классе есть поле-ссылка, вы обязаны инициализировать ее в конструкторе.

Умные указатели

К сожалению, ни один из типов приведенных ранее не ведет себя как ссылка в C# или Java, т.к. любой объект, выделенный в куче, нужно удалять вручную. Но как это сделать если ты не знаешь, кому, когда и на сколько времени понадобится твой объект? Для этого есть умные указатели.

Умный указатель содержит в себе указатель на объект в куче и счетчик использований. Как только счетчик доходит до нуля, объект уничтожается. Выглядит это вот как-то так:

shared_ptr<Person> person = make_shared<Person>("Dmitri", 123);

Такой объект можно передавать куда угодно и не бояться его использовать, и он — пожалуй лучший аналог ссылок в C#/Java, хотя и с ограничениями. Одно из ограничений — невозможность рекурсии, то есть нельзя писать вот так:

struct Parent
{
  shared_ptr<Child> child;
}
struct Child
{
  shared_ptr<Parent> parent; // так нельзя
}

Поскольку нет никакого централизованного учета ссылок, подобная конструкция не приведет ни к чему хорошему — в Child вместо shared_ptr придется использовать weak_ptr ну или обычную ссылку.

shared_ptr<> также решает проблему хранения ссылок в таких коллекциях как vector. Проблема в том, что нельзя сделать vector<Foo&>, но вполне можно сделать vector<shared_ptr<Foo>>.

Помимо shared_ptr<> есть несколько других типов умных указателей.

Алгоритмы

С++ не обладает никаким «интерфейсом» который символизирует перечисляемые объекты. Вместо этого он использует итераторы, которые умеют ходить по той или иной структуре. Любой перечисляемый тип может определить функции begin() и end() который возвращают итераторы на первый и за-последним элементы.

С++ также определяет цикл for для обхода коллекций, то есть можно написать:

vector v{1,2,3};
for (auto x : v)
  cout << c << endl;

Код выше также использует ключевое слово auto (аналог var в C#) для вывода типов.

В целом, алгоритмы в С++ это глобальные функции с такими красочными названиями как count_if и всякими прелестями вроде того факта, что remove на контейнере вовсе не удаляет объекты из контейнера, а только сваливает их в конец, а собственно удаляет их функция erase() (очень неинтуитивно).

У контейнеров нет функций-членов с алгоритмами вроде sort() или search(). И добавить их в контейнер нельзя (за исключением наследования) т.к. в С++ нет функций расширения. Алгоритмы специально спроектированы так, чтобы работать на всех возможных контейнерах путем итерирования.

Заключение

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

В плане компиляторов тоже все лучше и лучше. Есть компилятор Clang (дает вменяемые ошибки при компиляции вместо километров ада), интерпретатор Cling (REPL-среда на базе Clang, рекомендую!), C++ компилятор от Microsoft поддерживает инкрементальную и Edit & Continue компиляцию, а еще скоро процесс компиляции существенно ускорится путем введения модулей.

Что касается инструментов, то ReSharper C++ (если вы пишете под Visual Studio) и CLion (кросс-платформенная IDE) позволяют комфортно писать на этом языке. А такие технологии как CUDA Toolkit и Intel Parallel Studio позволяют амортизировать популярные аппаратные платформы CUDA и Intel Xeon Phi. ■

Written by Dmitri

4 августа 2016 at 14:27

Опубликовано в С++

Tagged with , ,

Проектные идеи

5 комментариев

Знаете почему возникает субсидирование? Потому, что некоторые вещи в корне невыгодны. Вот взять например сельское хозяйство — они катастрофически неприбыльно и имеет смысл только если вы занимаетесь “натуральным хозяйством”, т.е. кормите себя самого.

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

Так вот, в этом посте я хотел описать несколько своих идей которые есть (или были?) у меня. Может кому-то что-то понравится.

Кастомная разработка клавиатур

Современная клавиатура — это трэш. Я печатаю этот пост на Dell XPS 15 у которого высота клавиш снижена практически до нуля — меньше только у 12-дюймовых МакБуков (и я их клаву пробовал — вообще бред полный).

Так вот, модель “под одну гребенку” не работает. Я например использую TypeMatrix:

tmx-2030_gallery-1[1]

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

Еще одна, еще более безумная идея — это предоставлять этот же сервис для пользователей ноутбуков. На ноутбуках нельзя мухлевать с высотой клавиш (вы же не хотите чтобы клавиши касались экрана?) но можно менять раскладку. Я например хотел бы ортогональную раскладку вообще везде.

Если интересно, есть вот сайт для дизайна своей клавиатуры, но только на экране. А я бы хотел это делать IRL.

Специфичные аппаратные ускорители

Смотрите, у нас почти все пересели на ноутбуки. Потому что тупо удобно. Я купил 13- и 15-дюймовые ноуты несколько дней назад, и я понимаю почему людям так нравится — современное индустриальное исскусство доставляет. Но проблема в том, что ноуты все же не особо подходят для супер-мега-загруженных задач.

Для игр есть решения вроде вот такого:

Razer%20Blade%20Stealth-12-1200-80[1]

Но фишка в том, что нам порой нужны не совсем игры. Нужны просто вычислительные ресурсы. И тут-то пока ничего кроме Remote Desktop не придумали.

Поэтому у меня была такая идея, что может ноуты (особенно те, у которых выдув не снизу) как-то утолщать раза в 2 — это кстати уже делают с помощью slice-батареек (привет, Lenovo!) но никто не делает для других целей. А ведь сколько FPGA можно туда засунуть. Там можно делать, например, аппаратное кодирование 4К экрана (т.к. обычный ноутбук, увы, такую задачу не потянет). Ну или например сделать уйстройство которое держит огромную базу данных и предоставляет всякие мощные возможности (sharding, full-text search) на аппаратном уровне. Я думаю с технологией М.2 это вполне реально.

Вот вам практическая задача: у меня есть фотоаппарат, который снимает с разрешением 42Мп. У него есть WiFi и я по идее могу перегружать данные куда-то еще. Но проблема с обработкой — я обычно на фотках гоняю DxO, потом делаю ресамплинг для социалочек и все такое. Я бы хотел вам сказать, что все работает супер-быстро, но нет. И я не говорю про 4К видео где вообще беда с точки зрения любых попыток монтажа и обработки. Да что там, даже 720р видосоки из Camtasia кодируются неприемлимо долго — практически в realtime.

Безрамочные супербольшие экраны

Купленные мной XPS 13 и 15 практически не имеют рамки вокруг дисплея. Это — будущее, уверен что следующий МВР будет иметь то же самое. Мораль тут вот в чем — люди которые любят использовать несколько мониторов ставят их рядом и получается, честно говоря, не очень, потому что бортики.

Теоретически никто не мешает просто делать большой экран как сетку из 3*2 из 15-дюймовых 4К дисплеев. Если еще все это закруглить… кстати, закругленные дисплеи уже делают, я пока как-то не “вкусил плод”:

maxresdefault[1]

Но проблема в том, что пока никто еще не делает карточки которые держат по 6 4К мониторов, в отличии от AMD Eyefinity где 6*FullHD поддерживается без каких либо проблем.

Да, и в стиле офтопика, я на самом деле не настаиваю на 4К… если взять сетку 3×2 из 1080р мониторов, это разрешение в аггрегате будет больше чем 4К, а без рамок можно именно на нем и смотреть те несуществующие 4К фильмы которые никто так и не начал выпускать (эй, где 4К BlueRay уже, а?).

Reminder: 6 экранов это норма, я рекомендую использовать минимум 3. 2 экрана — не так удобно, т.к. у них будет полоса идти прямо по центру.

Аппаратный Continuous Integration

Если коротко — поставить систему a la TeamCity на Intel Xeon Phi и продавать это как программно-аппаратное решение.

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

  • Большие параллельные вычислительные ресурсы, т.к. “много ядер”

  • Не очень много памяти, т.к. CI в основном собирает маленькие бинарники и прогоняет тесты

В связи с этим, штуки вроде Xeon Phi подходят практически идеально. При том что там есть файловая система на которую можно поставить веб-сервер и все что угодно.

Надъязыки

Дядя Боб вон считает что нам уже хватит языков и процессов и пора “работу работать”. Я, в свою очередь, большой фанат всяких DSL которые потом могут конвертироваться или кросс-компилироваться в то что вам нужно — будь то C++, C# или Java.

Проблема только в том, что писать этот “надъязык” нужно так же как и обычный язык, а потом еще писать правила конверсии. И что самое болезненное, что обычные манипуляции вроде операции со строками очень болезненно транслировать из какого-то надуманного языка в тот же STL.

К слову, предостаточно людей не согласны с идеей что текущих языков нам хватит. Самый большой наверное лагерь это Rust’овики, их кажется легион. ■

Written by Dmitri

31 июля 2016 at 17:25

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

К вопросу о front-end’ах

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

Да, я обещал написать про front-end’ы, так что вот. Для начала расскажу что это такое. Если коротко — можно писать код как plain text, а можно его писать с помощью редактора a la Microsoft Equation Editor. Именно это делает Mathematica, и получается неплохо.

Но мы начнем с простого, например с того факта что * не умножение а звездочка и было бы логичнее использовать \times или хотя бы \cdot. Я понимаю что кого-то нервирует что произведение x и y будет выглядеть как x×y, но это пожалуй единственный кейс который приходит в голову, и тут можно написать x \cdot y и все довольны.

Вы заметили что я начал использовать \LaTeX? Его Дональд Кнут изобрел чтобы математику верстать. Выглядит сугубо приличнее чем plain text Вот например хочу я, допустим, деление: конечно x/y выглядит более менее сносно, но \frac{x}{y} как-то солиднее. Или foo->bar() все же не так круто как \text{foo}\to\ bar().

Вообще идентификаторы символов тоже хочется иметь погибче, например почему я не могу назвать меременную C^1_k или же например \widetilde{abc}?

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

Вообщем такие вот мысли…

Written by Dmitri

18 июля 2016 at 0:33

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

Плохие и хорошие идеи в языках программирования

12 комментариев

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

На самом деле нет. Как 5 лет назад было нормой 2-4 ядра, так и сейчас. И да, я знаю что есть процы подороже и посерьезнее, только вот косяк: подавляющее большинство людей нынче пользуют скорее макбуки нежели десктопные РС, а на них сколько ядер? 12? 16? Древнее индейское поселение фигвам.

Поэтому в этом посте немного троллинга “современных” языков. При этом я не жалуюсь, у меня все работает. Просто мысли в слух.

Дорогая, мы продолбали операторы

Даже не операторы. Вы на раскладку клавиатуры смотрели? Что это за !@#$%^&*()_+ мля? Я вообще не понимаю почему у нас на главном органе компьютера такой вагон легаси. Ладно, я вас не прошу с QWERTY следать, но хоть мусор-то можно было убрать?

Я сотственно вот о чем:

  • Единственный вменяемый оператор в ЯП это +. Всё. Кроме плюса все остальное – бред.

  • Минуса на клавиатуре нет вообще. Есть тире - и я тут не пытаюсь быть педантом или типографилом, я просто говорю что использовать тире как минус это вообще неправильно.

  • Деление и умножение тоже продолбано. С какого перепугу “звездочка” это умножение? Умножение это ×. Насчет деления конечно можно поспорить, может / без полноценного фронт-енда a la Mathematica — это приемлимо, но я не уверен.

  • Оператор = никаким образом не означает присваивание. Коротко, Delphi, Mathematica и прочие – правы, нужно разделять присвоение и определение, если вы уж решили использовать = для записи значения в переменную. Я конечно склонен думать что x := 2 это первичное определение переменной (даже auto/var не нужен) а для записи значения подойдет x <- 3 или 3 -> x (это кстати подход в F#, VHDL).

  • Использование = для сравнения — абсолютно нормальная практика (т.е. if (x = 3)) если бы не одно но — числа с плавующей точкой так сравнивать нельзя т.к. нужно указывать погрешность. Я бы, может, и не отказался вместо abs(x-y) < tol писать что-то вроде x =1e-10= y хоть это и выносит порядочно мозг.

  • Вот эта галочка ^ это либо оператор возведения в степень (ну или **), либо ничего. XOR из нее сделали безумцы.

  • Скобки продолбали все и полностью. Вы понимаете, что в математике разные скобки ([], {}, ()) все имеют право на жизнь и используются чтобы не запутаться в сложных выражениях? Так тогда зачем квадратные скобки узурпировали для массовов а фигурные — для scope? А представьте ЯП где можно использовать любые для выражений, плюс компилятор проверяет согласованность.

  • Вообще в математике оператор × можно опускать, и я склонен думать что выражение 3x в том же С++ или C#, при желании, нельзя мизинтерпритировать как ничто кроме 3×x. Также сюда можно приплести units of measure, чтобы можно было писать 52m вместо 52 mm. (И да, я понимаю что непонятно xy это переменная или x*y, но можно же из контекста выводить? Или опасно?)

  • F# узурпировал prime mark ' как символ, но я бы его взял как транспозицию, как делает MATLAB.

  • А еще я бы разрешил произвольные названия переменных, только не как в F# (ВОТ ТАК) а что-то вроде:

    struct Values { #1, #2:i32 }
    Values v; print(v.2)
    

    Кстати, писать v.2 можно в Rust, тоже неплохая возможность.

Косяки с именами типов в C++ и не только

С++ ставит рекорд по полному факапу системы типов. Что такое unsigned long long? Никто не знает, поэтому мы и используем <cstdint>, но можно лучше (спасибо Rust):

  • Целочисленные типы = знаковость (i/u) + размер (сколько вешать в битах), например i32, u64 итд.

  • Для чисел с плавающей в луже точкой просто делаем f32/f64 (спасибо за вынос мозга, F#). Эй SG14, где там 16-bit float?

  • Если вам вдруг нужны пакованые SIMD типы, их можно добавить как p128/256/512. Но это экзотика. Придется вводить векторные операторы (.+, .*, и так далее) как это сделал MATLAB.

  • Использование этих коротеньких типов как постфиксы (var z = 3.0f32) — гениально, спасибо Rust.

  • Целочисленные переменные isize/usize с размером, равным слову проца — это очень умно, опять же спасибо, Rust. И что еще более гениально, так это то, что в Rust индекс массива — unsigned. А в С++ вполне можно написать x[-1] т.к. это всего лишь смещение указателя.

Поддержка векторно-матричных операций

Если все так пекутся о многопоточности и векторизации, почему нигде кроме MATLAB никто не напрягся впаять вектора/матрицы в язык? Более того, я бы предложил:

  • Улучшенную инициализацию, то есть

    X = [1 2; 3 4]; // instead of {{1,2},{3,4}
    X = [ 1 2
          3 4 ]; // also works, kind of
    

  • Вменяемые скалярные и векторные произведения, как сделал MATLAB — X*Y и X.*Y как векторное и Адамарово произведение соответственно.

  • Маски для определенно-нулевых элементов матрицы чтобы сократить кол-во операций если у вас, например, треугольная матрица.

  • Статические и динамические размеры. Очевидно но все же, хочется хороший API. То, что сейчас в С++ это адъ.

И ещё…

Ладно C# запилил observer pattern как event (немного неуклюже, конечно), но было бы неплохо получить binding operator =:= который жестко связывает два значения. А там и до резолва сложных выражений недалеко. Вообщем в современном мире это актуально.

Да, и неплохо было бы оставить операторы < и > в покое и не использовать их для шаблонов. Хотите шаблоны? Используйте « и » и мне плевать что этих символов нет на клавиатуре, т.к. клавиатуры ущербны по определению. И нет, я не предлагаю адъ вроде APL, я скорее предлагаю просто делать уже языкам графические front-end’ы как Mathematica.

Но об этом в следующем посте. ■

Written by Dmitri

4 июля 2016 at 20:40

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

Tagged with

Задача про 2008

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

Этот пост — репост одного моего поста который был на Hexlet до того как Hexlet решил изобрести себя снова и сдвинул мой курс в «песочницу». Он немного технический, и я не хочу его терять. Надеюсь вы поймете. К сожалению, комментарии оригинального поста потеряны, но с этим ничего не поделать.

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

Как с помощью 13 (тринадцати) нулей и простых математических операций получить число 2008?

Сразу скажу, что как количество нулей, так и число 2008 выбраны неслучайно — они не дают получить решение быстро и, более того, не дают получить слишком большое количество решений. Также, иногда эта задача (попробуйте ее пока не гуглить) дается с дополнительной подсказкой, с которой она менее интересна.

Итак, вот небольшое описание процесса рассуждений о наборе возможных решений.

Вещественность

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

Самое очевидное решение — это 0^0 = 1 (это кстати спорно и вызвало много дебатов), но это в результате дает нам \left \lfloor{\frac{13}{2}}\right \rfloor = 6 нулей из которых, как вы понимаете, 2008 никаким образом не сделать. Должны ведь быть и другие варианты? Попробуйте угадать, какой оператор делает из нуля единицу?

Конечно же это факториал. Факториал — это обычно произведение всех чисел от 1 до n, так что например 3!=3\times2\times1, но у факториала есть одна особенность: 0!=1, а следовательно у нас теперь 13 единиц, а с ними уже можно работать. И кстати, пока не поздно, обращу внимание на то, что в условии задачи я упомянул простые математические операции. Если бы можно было использовать, например, логарифмы, то задача уже решена т.к. любое натуральное число можно выразить через логарифмы, корни, и три двойки (доказательство), а соответственно решение нашей задачи выглядело бы вот так:

\displaystyle 2008 = - \log_2\left(\log_2\left(\underbrace{\sqrt{\sqrt{...\sqrt{2}}}}_{2008}\right)\right)

Для решения выше потребовалось бы всего шесть нулей (т.к. 2 = 0! + 0!) а также 2008 квадратных корней но, как я уже сказал, хочется получить решение с помощью известных операторов, не привлекая в решение всякие сложные функции. Корни, возведение в степень, факториалы — это все ок.

Возведение в степень

Итак, нужно получить 2008. Самое очевидное — это найти близлежащее число 2^n. В данном случае, это 2^{11} и соответственно мы можем подобраться к решению вот так:

\displaystyle \begin{aligned}  2008 &= 2^{11} - 40 \\  &= 2^{2^3+3} - 5\times2^3  \end{aligned}

К сожалению, числа 2, 3 и 5 идут «по себестоимости» (т.е. чтобы сделать 5 нужно 5 нулей), и соответственно в 13 нулей мы ну никак не уложимся: для решения выше нужно аж 20 нулей!

Соответственно нашей первоочередной задачей становится поиск более «дешевых» чисел, и тут на помощь приходят…

Факториалы

Факториалы дают нам не только единицы с которыми можно работать, но также дешевые крупные числа. Например, 3!=6 а это значит что за три нуля мы можем получить не только 3 но также 6=3!, 720=(3!)!, и так далее. Если форма записи X_Y обозначает что число X требует для записи Y нулей, то мы получим следующие значения:

\displaystyle \begin{aligned}  0_1 =& 0 \\  1_1 =& 0! \\  2_2 =& 0! + 0! \\  3_3 =& 0! + 0! + 0! \\  4_4 =& 3 + 0! = 2^2 \\  5_4 =& 3! - 0! \\  6_3 =& 3! \\  7_4 =& 3! + 1 \\  8_5 =& 3! + 0! + 0! = 2^3 \\  9_5 =& 3^2  \end{aligned}

Более крупные значения (с точки зрения стоимости) лучше не трогать. И скажу сразу, что даже некоторые из значений выше мы сможем впоследствии немного улучшить.

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

\displaystyle \begin{aligned}  2008 &= 2^3 \times 251 \\  &= 2^3 \times (216+36-1) \\  &= 2^3 \times (6^3 + 6^2 - 1) \\  &= \underbrace{2^3 \times \left(6^2(6+1)-1)\right)}_{14}  \end{aligned}

Увы, решение выше требует на один ноль больше, чем у нас имеется.

Другой подход к решению задачи — это разложить на множители не 2008 а, скажем 2008\pm10. Вот что нам дает MATLAB:

1998=2   3   3   3  37
1999=1999
2000=2  2  2  2  5  5  5
2001=3  23  29
2002=2   7  11  13
2003=2003
2004=2    2    3  167
2005=5  401
2006=2  17  59
2007=3    3  223
2008=2    2    2  251
2009=7   7  41
2010=2   3   5  67
2011=2011
2012=2    2  503
2013=3  11  61
2014=2  19  53
2015=5  13  31
2016=2  2  2  2  2  3  3  7
2017=2017
2018=2  1009

Из интересных чисел тут, пожалуй, 2000 и 2016. Также соблазнительно число 1998 (у него есть множитель 37=3!^2+1). Возьмем сначала 2000:

\displaystyle \begin{aligned}  2000 =& \underbrace{2^4\times5^3}_{12} \\  =& \underbrace{2\times\left(2^{3}+2\right)^3}_{11}  \end{aligned}

Это решение нам явно не подходит т.к. 2008 = 2000+8_5 т.е. для решения нужно 16 единиц. Попробуем 2016:

\displaystyle \begin{aligned}  2016 =& \underbrace{2^3\times6^2\times7}_{14} \\  =& \underbrace{6^4+(3!)!}_{10}  \end{aligned}

Но даже так, у нас остается три нуля, а 2008=2016-8_5, то есть для этого решения нам всяко не хватает двух нулей. Что же, подход с обычными (намек!) факториалами почти себя исчерпал, давайте еще попробуем что-нибудь сделать с числом 1998:

\displaystyle \begin{aligned}  1998 &= \underbrace{3!^2\times\left(3!^2+1\right)}_{11}  \end{aligned}

Это достаточно бессмысленное занятие т.к. двумя нулями лишние 10 не набрать, но, по крайней мере, мы выловили тот факт, что возможно стоит попробовать 3!^4:

\displaystyle \begin{aligned}  2008 &= 3!^4 + 712 \\  &= \underbrace{3!^4 + (3!)! - 2^3}_{15}  \end{aligned}

Увы и ах. Как я уже говорил в самом начале, число 2008 выбрано неслучайно — это число вставляет максимальное число палок в колеса. Нужен какой-то трюк чтобы снизить «стоимость» простых чисел вроде 8. К счастью, такой трюк имеется, и это…

Двойной факториал

Двойной факториал n!! — это тоже произведение всех чисел от 1 до n, но с шагом 2, т.к. например 5!!=5\times3\times1=15. Само по себе это кардинально меняет картину, и я хочу обратить ваше внимание на два равенства:

  • 8_4 = 4!!, то есть восьмерка стала «дешевле» на один ноль.

  • 48_3=(3!)!!

Итак, делим 2008 на 48 и получаем 41.8(3), а поскольку 42=6\times7, мы наконец-то можем попробовать получить ответ:

\displaystyle \begin{aligned}  2008 &= 48\times42-8 \\  &= \underbrace{(3!)!!\times\left(3!\times(3!+1)\right)-4!!}_{14}  \end{aligned}

Но что-то тут не так: 42 нам далось адским трудом, мы заплатили за него аж 7 нулей. На один ноль поменьше и все получится. На самом же деле, 42=48-6=(3!)!!-3! и вот, ура, у нас готово первое решение:

\displaystyle 2008 = \underbrace{(3!)!!\times\left((3!)!!-3!\right)-4!!}_{13}

Субфакториал

Разных факториалов бывает много и субфакториалы — это такой особый тип факториала, который определяет количество беспорядков порядка n. Высчитывается он так

\displaystyle !n=n!\sum_{k=0}^n \frac{\left(-1\right)^k}{k!}

Прелесть этого факториала в том, что он в очередной раз дает нам другие равенства, например 265_3 = !(3!). А это в свою очередь заставляет нас в очередной раз посмотреть на разложение 2008 на множители:

\displaystyle \begin{aligned}  2008 &= 4!! \times 251 \\  &= 4!! \times (!(3!) - 14) \\  &= \underbrace{4!! \times \left(!(3!)-5!!+1\right)}_{13}  \end{aligned}

Оптимизация задачи

Кому-то может показаться, что 13 нулей — это предел мечтания, но нет — вот например пара решений, где используются только 12 нулей:

\displaystyle \begin{aligned}  2008 &= \underbrace{(!5)^2 + \sqrt{\left((3!)!+1\right)} + 1}_{12} \\  &= \underbrace{\left(!(4!!)-1\right)\times2+5!}_{12}  \end{aligned}

Предлагаю игру в стиле code golf — оставляйте в комментариях решения, которые используют 11 нулей и меньше, посмотрим чье кунг‑фу лучше. No cheating! ■

Written by Dmitri

15 февраля 2016 at 0:39

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

Tagged with

Runtime Compiled C++

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

Нынче грех жаловаться на компиляцию. Я вот смотрю на то, что сейчас возможно в последней версии MSVC — там по сути компиляция инкрементальна не на уровне файлов (де компилим только те файлы, которые поменялись), а на уровне функций — остальное берется из кэша. Как оно точно работает я не знаю, знаю лишь что при изменениях я вижу нечто вроде

166 of 3863 functions ( 4.3%) were compiled, the rest were copied from previous compilation.
4 functions were new in current compilation
335 functions had inline decision re-evaluated but remain unchanged

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

Вообщем, рассказ-то у меня не про это, а про runtime-компиляцию, про которую я уже часто говорил под термином ‘динамическое прототипирование’ — вот тут у меня .NET-ное видео есть, можно посмотреть как это делать на C#-е.

Вообще этот подход хорошо иллюстрирует зачем вообще нужен Dependency Inversion Principle — да-да, именно inversion а не injection. Если попытаться объяснить этот принцип словами, получится что-то вроде этого:

Делайте Extract Interface на любом классе, по поводу и без повода. Замените все типы с Foo на IFoo. Если кому че не нравятся, пусть пишут официальную жалобу, в дубликате и с ксерокопией паспорта.

Вот как-то так. А вы думали, зачем Extract Interface? Конечно чтобы в рантайме заменить один тип на другой. Как? Объясняю:

  • Вы сделали объект типа Person.

  • В рантайме вы поменяли объект типа Person, скомпилировав еще один такой же но с пофикшенной багой.

  • Теперь у вас два объекта типа Person, но это разные типы!

Никакого вам duck typing’а! Следовательно, вы в принципе не можете зависеть от Person, а только от некого интерфейса IPerson который, кстати, менять нельзя если только вы не абстрагировались еще выше (но боюсь что это непрактино в 99% ситуаций).

А что в C++?

Да по сути то же самое, только еще проще т.к. ничего не надо делать, умные дяди уже все сделали. Естественно, что этот подход сугубо intrusive, т.к. это «плюсы» и тут нету reflection и иже с ним.

  • Файлы которые нужно подменить помечаются специальным макросом REGISTERCLASS.

  • В момент запуска вашей проги, система строит табличку того какой класс где определен.

  • Классы, которые хочется менять в рантайме есессно не положено инстанцировать «в лоб», так что

    IObjectConstructor* pCtor = m_pRuntimeObjectSystem->GetObjectFactorySystem()->GetConstructor( "RuntimeObject01" );
    if (pCtor)
    {
    	IObject* pObj = pCtor->Construct();
    	pObj->GetInterface( &m_pUpdateable );
    	if( 0 == m_pUpdateable )
    	{
    		delete pObj;
    		m_pCompilerLogger->LogError("Error - no updateable interface found\n");
    		return false;
    	}
    	m_ObjectId = pObj->GetObjectId();
    }
    

На этом этапе у кого-то может политься кровь из глаз, но я напоминаю, что это C++. Выше происходит следующее: мы через нашу runtime систему находим фабрику которая инстанцирует объект и вызываем конструктор, а потом пытаемся подкрутить его к интерфейсу — если получилось, сохраняем также id объекта чтобы его потом можно было правильно удалить.

Значит теперь к объекту мы можем достучаться только через его интерфейс. Интерфейс — это просто структура с pure virtual функциями, наподобии вот этой:

struct IUpdateable : public IObject
{
  virtual void Update(float deltaTime) = 0;
};

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

  • После запуска, система начинает мониторить все изменения. Если файл поменялся, этот файл (а также все его зависимости) собирается в отдельную динамическую либу.

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

  • Внешние компоненты, которые сами по себе не являются runtime-modifiable могут отлавливать события когда меняется структура изменяемых объектов и как-то на это реагировать.

Вообщем, все это очень интересно и, резюмируя, является еще одним козырем в рукаве, наряду с Cling, обертыванием C++ либ в Питон, и прочими извращениями. Enjoy!

Written by Dmitri

2 февраля 2016 at 2:01

Опубликовано в С++

Tagged with