Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Category:

C±±

Keywords: C--, Cyclone, Vault, Safe-C++

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

Скажем, выделение динамической памяти вы хотите в части мест реализовывать сами, а значит языки с принудительно автоматизированным управлением памятью отпадают. В тех же глубинах вам может понадобиться пользоваться экзотическими структурами данных типа XOR-двусвязного списка. А это значит, языки с ограниченной арифметикой указателей тоже мимо. Наконец, в некоторых местах вам может понадобиться goto для более эффективной реализации. Или switch с проваливанием для приспособы Даффа и её аналогов. Вам нужен доступ ко всему богатству арифметических и синхронизационных команд, доступных на распространённых ныне машинах.

Си

Сейчас языком выбора в такой ситуации является Си. Он очень кроссплатформенный, очень близкий к железу и там неограниченная арифметика указателей. Однако насчёт ненавязывания есть заковыки:
– Си жёстко навязывает абсолютно неудачную модель строк — строки, оканчивающиеся нулём. Причины у этого чисто исторические. А следствия уж воистину исторические: эти строки привели к такому количеству переполнений буфера, фатальных уязвимостей, лишнего кода и неэффективных алгоритмов, как наверное, никакое другое решение. И эта реализация строк сделана обязательной стандартами POSIX. Дело в том, что обработка строк неоправданно затратна, простейшие операции (конкатенация) требуют непредсказуемого заранее количества памяти.
– Си навязывает довольно неудачную модель вызова функций, которая исключает оптимизацию хвостовой рекурсии и возвращение нескольких результатов (а не одного). Последний аспект приводит к необходимости изврата с пересылкой адресов “ячеек с памятью для возвращаемых значений” как в scanf. (Причём сишную модель вызова можно починить не потеряв ни в чём.)
– Вследствие наличия вот этого механизма в Си должно быть возможно обращаться по указателям ко всем локальным переменным. В результате их становится невозможно хранить в регистрах. В архитектурах со стеком регистров реализация ещё проблематичней. Вперемешку передача аргументов по значению и по адресу. Нет отдельно выделенных констант.
– В не только хвостовую рекурсию реализовать нормально невозможно, но и continuations/сопрограммы. Часть алгоритмов нельзя реализовать с должной эффективностью!
– Для реализации bignum-библиотеки требуется доступ к сложению-вычитанию с переносом, расширенному умножению и делению. В Си это достигается очень через зопу.
– Система типов предполагает, что размер чисел в битах от системы к системе меняется, в то время как программы де-факто привязываются к конкретному размеру. Все эти int, short и long должны быть убраны и сделаны int8, int16, int32, int64.
– Язык допускает конструкции, в которых порядок выполнения спорный и поэтому поведение непредсказуемое.

C--

Нашлись люди, которые решили сделать язык, который бы все эти недочёты исправлял. Они его задумали, как “кросс-платформенный ассемблер” и, на мой взгляд, в этом качестве он является идеалом. Ничего лучше я не видел и сам бы придумать не смог.
– Он превосходно ложится на х86, Power и MMIX.
– На неё превосходно ложатся функциональные и императивные языки.
– Отделены локальные переменные (которые по возможности регистровые) и стековое размещение.
– Дереференцирование указателей всегда явное, поэтому указатели совершенно не вызывают путаницы, как они не вызывают её у программистов на ассемблере.
– Механизм организации динамической памяти не навязывается, но дизайн языка весь насквозь такой, чтоб насколько это возможно облегчить применение сборщика мусора любой из известных на данный момент парадигмы (включая compile-time optimized reference counting и region analysis, см. ниже).

Писать на этом языке можно прямо так и для реализации низкоуровневых алгоритмов он заметно удобнее Си. Но для, так сказать, повседневного программирования очень не хватает системы типов. Авторы не хотят навязывать определённое устройство сложных типов данных и к тому же хотят сделать язык максимально простым в компиляции, посему там там нет struct-типов, enum-типов и union-типов. Всё ручками. А это в “повседневном” программировании катастрофически неудобно. Да, type safety в C-- тоже никакой нет, что никак не баг, но фича.

export sum_product;
sum_product(bits32 n) {
  bits32 s, p;
  if n == 1 {
    return (1, 1);
  } else {
    s, p = sum_product(n - 1);
    return (s + n, p * n);
  }
}

Cyclone

На самом деле, struct, enum и tagged union являются частными случаями algebraic datatypes. Языком добавляющим в Си (увы, увы не С--, что очень жаль) алгебраические типы данных с pattern matching'ом, обработку исключений и type safety называется Cyclone. Синтаксически Cyclone является расширением С99 + GNU extensions. По семантически он, к сожалению, слабее, потому что в нём запрещена полноценная арифметика указателей. Зато type safety на высоте и в большинстве случаев с нулевым оверхедом: алгебраические типы данных могут быть полиморфными (generics), так что сделать можно все типобезопасные структуры данных.

В Си указатели, как известно, используются двояко: как указатель на объект и как указатель на массив (фиксированного размера). В Cyclone это две разные вещи. Пользуясь генериксовым синтаксисом:
addr<int> pointerToAnInteger и arrayRef<int> pointerToIntegerArray. Дескриптор массива содержит два значения: указатель на первый элемент и размер массива. В случае если размер массива известен в compile time, память этим дополнительным знанием не занимают. Доступ к элементам массива всегда происходит с проверкой границы. Если хочется сделать массив переменного размера, его элементарно реализовать как addr<arrayRef<int>>.
Nullable pointer с семантической точки зрения представляет собой maybe<addr<int>> ну и так далее.

Cyclone во время компиляции убеждается в том, что объекты из стека удаляются не раньше, чем исчезают все указатели на них. Для достижения надёжности динамической памяти, Cyclone предписывает пользоваться сборщиком мусора и/или специальными аннотациями, управляющими регионами. Сборщик мусора — это нулевой оверхед со стороны программиста, но некоторый оверхед при работе программы и некоторый нондетерминизм (источник опасности в критических секциях). Эксплицитный контроль за регионами это заметный оверхед для программиста (впрочем, не больше, чем правильное использование Сишного free/delete), но нулевой оверхед во время выполнения.

Тут с одной стороны благодаря работам Леванони-Петранка последних 10 лет
(http://www.cs.technion.ac.il/~erez/Papers/refcount.pdf, http://www.cs.technion.ac.il/~erez/Papers/rc-prefetch-cc07.pdf, http://portal.acm.org/citation.cfm?doid=1255450.1255453)
стало понятно, как делать reference-counting GC с поражающей воображение эффективностью, а с другой что исчисление линейных регионов полно. Кстати Microsoft разработало развитие Cyclone в необычную сторону. Там концепция регионов расширяется до концепции capabilities и таким способом решаются вопросы блокировки любых ресуров. Вроде как оно даже гарантированно deadlock-free получается. Этот язык называется Vault.

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

Safe-C++

А вот некоторым хочется большей модульности и наличия объектно-ориентированности. Не обязательно полноценной с динамическими классами, но чтобы можно хотя бы засовывать функции в нутра структур, с которыми они работают. Такую штуку, как подмножество C++ с кучкой библиотек и добавленных макросов реализовали разработчики микроядра Fiasco. Называется Safe-C++. Про него я много писать не буду, там всё очевидно.

Если честно, после привычки к системе типов Скалы выглядит С++ная система типов убогонько. Реализация скальной системы типов с (Singleton) Objects, Classes и Traits как они там сделаны заметно проще чем реализация адово-сложной сишной. Сделать её по-С++ному, то есть так, чтобы если тип точно известен в compile time, оверхеда с использованием dispatch tables не было, тоже несложно. Даёшь C±±!
Subscribe

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

    Как известно, питьевая вода во многих странах дефицитный ресурс. И даже в дождливой Германии летом иногда случаются засухи, в результате которых она…

  • 36

    Традиционный деньрожденный пост. Год выдался необычный. :)

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 3 comments