Не путайте помощника шерифа с депутатом*!

6 август, 2007 - 18:17Андрей Зубинский

Мир маленьких в той или иной мере интеллектуальных устройств с каждым днем становится все больше и больше – факт бесспорный. Как и то, что всеядный, прожорливый и падкий до всяческих новеньких «штучек» потребительский рынок растет за счет быстро наливающихся силой и деньгами стран еще вчера третьего мира. Из двух этих слагаемых можно породить множество сумм в разных контекстах. Нас же будет интересовать всего одна...

*Deputy – помощник шерифа (амер.), депутат

В контексте этой статьи приведенные в преамбуле совершенно очевидные факты в сумме дают вовсе уж неочевидное – ...несмотря на заслуженную критику, на наличие множества лучших даже на уровне идей разработок, язык программирования C не собирается утрачивать популярность. Дело в том, что тотальная интеллектуализация бытовой техники и появление доступных и принципиально новых именно благодаря встроенным вычислителям изделий требуют этих самых вычислителей в огромных количествах. И, что немаловажно, – разнообразных. В этом мире однообразие не в чести – здесь принято подбирать возможности вычислителя под самые тонкие нюансы требований решаемой задачи. А вот для кораллово-рифового разнообразия архитектур встраиваемых вычислителей, как оказывается, нет ничего более подходящего, чем старый и раскритикованный от и до язык С – именно его кросс-компиляторы (выполняющиеся на машине одной архитектуры и генерирующие код для принципиально иных целевых платформ) и среды разработки безусловно и до сих пор беспрекословно доминируют на рынке встраиваемых систем. Соответственно, и спрос на квалифицированных C-программистов, специализирующихся на «встраиваемом» (embedded) программировании, остается высоким, и одновременно растут требования к качеству производимого ими продукта. Ведь один и тот же пользователь, даже приученный ко всякому особенностями ПО «настольного» мира, буквально взорвется, когда его стиральная машина откажется выполнить программу стирки и для устранения этой проблемы потребуется установить «заплатку», доступную с сайта производителя. Об иных, связанных с повышенными рисками, нюансах функционирования встраиваемых систем (например, автомобильных или оборудования для подводного плавания), даже и не хочется говорить. Именно поэтому сегодня любой инструмент, позволяющий в той или иной мере улучшить показатели качества С-кода, представляет немалый интерес. И тем более интересны инструменты, придающие стандартному языку C новые, присущие куда более развитым его собратьям возможности.

Deputy как инструмент

Начнем с того, что Deputy – не «еще один» статический анализатор исходных текстов (как, например, Splint, а полноценный компилятор весьма щадящего синтаксис и семантику стандартного C расширения этого языка. Deputy практически полностью совместим с компилятором GNU, что позволяет одним движением руки «интегрировать» его в уже имеющийся gcc-ориентированный проект (например, заменой значения одной переменной, скажем, CC, в make-файле). Этой скудной информации уже достаточно для того, чтобы определить вероятные области применения Deputy.

Во-первых, с его помощью можно прототипировать С-программы, изучать их поведение и тестировать так, как это невозможно сделать в разумные сроки с помощью традиционных средств. К слову, о технике прототипирования программ сказано очень мало даже по сравнению с теми же обычными (и совершенно очевидными) организационными приемами, а жаль. Создание прототипа, тщательное его изучение, оптимизация, отладка – мощный инструмент традиционной, классической инженерии, и уж если с его помощью получается работать с материальными системами самых разных масштабов, то в программной инженерии для его использования вообще нет никаких ограничений. Сомнения появляются разве что когда речь заходит о стоимости проекта... но подождите, совсем недавно, в период расцвета экстремального программирования, его адептами было как-будто убедительно доказано, что избыточные организационные приемы приводят к экономии средств и времени. Так почему проверенное годами и инженерной практикой прототипирование непременно должно приводить к повышению проектных расходов? Впрочем, прототипы программ действительно создаются (иначе легендарный пакет Matlab был бы вовсе не таким легендарным), и Deputy расширяет инструментальный набор разработчика-прототиписта, позволяя понизить уровень детализации прототипа до фактически уровня кода, который будет использован в готовом устройстве.

Во-вторых, многие современные встраиваемые системы создаются с помощью инструментального набора GNU. С учетом уже сказанного в подобных случаях инструмент класса Deputy позволяет свести к минимуму дистанцию между прототипом и готовым к промышленному применению production-кодом.

О Deputy как инструменте остается сказать немногое. Любителям функционального программирования согреет сердце тот факт, что Deputy реализован на языке OCaml. Нелюбители «функциональщины» также не останутся без «подарка» – возможности Deputy как формально описанной системы типов, расширяющей систему типов стандартного C, весьма близки к таким страшно именуемым вещам из модного языка Haskell, как «обобщенные алгебраически типы» и «синглетонные типы».

И наконец, последнее в этом разделе. Deputy легко и традиционно для GNU-дистрибутивов (configure – make – make install) собирается в любой UNIX-подобной операционной системе.

Deputy как система типов

Deputy-инструмент является овеществлением одноименной системы зависимых типов для языка C, созданной небольшой командой разработчиков из Калифорнийского университета (Беркли) и Intel Research. В этой статье мы не будем даже пытаться заглянуть в алгебраические дебри теоретических построений в области систем типов (type systems), ограничимся лишь упоминанием того факта, что для некоторых специалистов типы данных, используемые в языках программирования, являются предметом исследований, в результате которых строятся формально определенные системы типов. Deputy же отличается от прочих таких систем приставкой «зависимых». Давайте попробуем разобраться с ее значением «на пальцах», без сложной, да и, по большому счету, совершенно ненужной (в этом случае, только в этом случае!) программисту-практику математики.

Итак, типы данных. Они позволяют очевидное – классифицировать данные и специфицировать для каждого класса способы хранения в памяти и механизмы доступа к ним, допустимость использования данных в качестве входных или выходных для разных процессов, видимость данных разными процессами и т. п. Менее очевидно то, что типы данных являются механизмом описания исключительно важных сущностей – инвариантов. Например, тип int (целое число со знаком) в C-программе не зависит ни от чего – он всегда int. Иными словами, после объявления переменной int A; высказывание «объект с именем A является переменной типа int» – истинно, и его истинность остается неизменной на всем временном участке существования переменной А. Это латентное свойство типов позволяет сформулировать конечный набор критериев, с помощью которых можно проверять программу на правильность. Примером работы таких критериальных правил является поведение компилятора при попытке передать функции, объявленной как int sum(int* A, int* B), в качестве параметров A и B переменных с типом int – злой компилятор обязательно за это «надает по рукам». Теперь давайте попробуем взглянуть «глазами компилятора» на прототип такой C-функции: int walk( char * pStart, char * pEnd, char * Cursor). Что мы видим? В качестве параметров – три инварианта, три одинаковых типа – «указатель на объект символьного типа». О многом ли это говорит? Да, это не даст возможности передать функции walk в качестве параметров данные других типов и тем самым исключит возможность грубой ошибки на стадии проектирования программы. Но все ли это? А если дополнить прототип функции словесным описанием, например упоминанием того, что все три указателя ссылаются на один и тот же массив символов и что указатель Cursor не должен выходить за границы, определенные указателями pStart и pEnd? Согласитесь, это описание говорит действительно о многом. Но в мире типов-инвариантов оно доступно только программисту, но не компилятору.

Система зависимых типов как раз предназначена для сокращения этой семантической пропасти (между «понятное программисту» и «понятное компилятору»). Слово «зависимых» подчеркивает, что тип становится... как бы вычисляемым на основе данных. Потенциально это означает, что конечный для традиционных систем типов набор правил, на основании которых проверяется программа, для систем зависимых типов становится бесконечным и расширяемым – от обычных несложных механизмов контроля (assertions) до полной формальной спецификации всей программы. Как показывает практика, система зависимых типов исключительно важна в первую очередь для низкоуровневого программирования – области, где сегодня безраздельно царит язык С. Именно в ней обыденной практикой является использование таких сложных типов, которые описываются исключительно на уровне «понятно программисту» – «элемент фрагмента массива с определенным началом и концом», «элемент буферного массива, определенный адресом начала буфера и целочисленным смещением», «тип, определяемый полем варианта» (широко известный прием «экономичной упаковки» в одну структуру множества объединений с указанием типа конкретного содержимого кодом числового поля структуры) и т. д.

Не следует думать, что построение работоспособной в реальном программном изделии системы зависимых типов – дело несложное. На самом деле Deputy – разработка уникальная. Хотя бы потому, что ее создателям удалось преодолеть барьер, существенно отдалявший ранее созданные аналогичные системы от применений в реальном программировании – так называемую проблему «правдоподобности типов» (types soundness). В «чистом функциональном» программировании способность переменных или объектов, расположенных на «куче» (heap), менять свое значение – даже не персоны нон-грата, а ужасная ересь, соответственно, чисто функциональные системы зависимых типов всегда строились на предположении принципиального исключения всего, что может в ходе исполнения программы изменять свое значение, из определяющей части зависимого типа. Как теоретическое построение эти системы, безусловно, имеют ценность, но практикующему программисту они ничем помочь не могут.

Больше того, в отличие от предшественников, даже теоретически позволявших создавать исключительно статические анализаторы кода, система зависимых типов Deputy обеспечивает, кроме статического контроля правильности, также и проверки во время исполнения.

И наконец, третье, касающееся больше особенностей Deputy как инструмента. Использование расширенной типизации в реальной программе, естественно, связано с затратами времени, в большинстве очевидных случаев – непродуктивными. Кроме того, языки описания расширенных типов традиционно сложны (если не сказать – ужасны). Оба этих фактора обычно отталкивают программистов от применения соответствующего инструментария (особенно таких чувствительных к изяществу кода C-программистов). Создатели Deputy эти факторы учли – транслятор берет на себя приличный кусок работы по автоматическому формированию гипотез о зависимых типах локальных и глобальных переменных и функций, а язык описания расширенных типов предельно лаконичен, прозрачен и минимально затрагивает синтаксис стандартного C.

Deputy как код

Для практикующего программиста Deputy – это спецификаторы, располагающиеся непосредственно за C-описанием типа, но перед именем переменной. Так, введенный во втором объявлении тип «указатель со счетчиком» – достойный представитель системы зависимых типов:

int Size;
int * COUNT(Size) iPtr;

На уровне «понятно для программиста» это означает – iPtr является указателем на один из элементов массива, содержащего Size элементов. Определяться такой тип может не только константой или значением переменной, но и вычисляемым в ходе исполнения программы выражением (с незначительными ограничениями, указанными в документации).

Более общий тип – «ограниченный указатель»:

int * pStart;
int * pEnd;
int * BOUND(pStart, pEnd) iPtr;

«Понятно для программиста» iPtr – это указатель на один из элементов подмассива, заданного указателями на начало (pStart) и конец (pEnd).

Интересные типы данных позволяют с помощью указанных выше конструкций создавать спецификатор NT – «ограниченный нулевым элементом». Так как для представления строк символов в С можно использовать две конструкции (массив символов определенного размера и ограниченная нулевым символом строка), с помощью спецификатора NT можно задать, например, следующий тип:

char * pStart;
char * pEnd;
char * NT BOUND(pStart, pEnd) iPtr;

Это – указатель на символ из подмассива, ограниченного указателями начала и конца или нулевым символом. То есть если нулевой символ в массиве встретится «раньше» pStart, множество допустимых значений объекта iPtr будет пустым, и только если нулевой символ располагается «позже» pEnd, множество допустимых значений объекта iPtr будет включать все элементы между pStart и pEnd («раньше» и «позже» здесь измеряются в расстоянии от начального элемента всего массива).

Естественно, так как речь идет о полноценной системе типов, Deputy поддерживает приведение типов. Но делает это весьма строго – если множество значений типа B, к которому приводится тип А, является допустимым подмножеством А, приведение будет выполнено. В противном случае компилятор или код времени исполнения сгенерируют ошибку. В следующем примере первое приведение типов будет допустимым и выполнимым, второе – вызовет ошибку на этапе компиляции (если бы в определении типа iPtr_3 использовалось вычисляемое во время исполнения выражение, ошибка была бы также сгенерирована во время исполнения при превышении значением выражения числа 10):

int * COUNT(10) iPtr_1;
int * COUNT(8) iPtr_2;
int * COUNT(12) iPtr_3;
iPtr_2 = (int * COUNT(8)) iPtr_1;
iPtr_3 = (int * COUNT(12)) iPtr_1;

Кроме этих спецификаторов типов, которые понятны, легко добавляются (в том числе – автоматически формируются компилятором в очевидных случаях) и удаляются из кода, Deputy предусматривает ряд конструкций, позволяющих специфицировать полиморфные функции и вариантные структуры данных, строгие указатели (использование которых в операциях адресной арифметики недопустимо) и т. д.