2009 -> Выпуск 2

История разработки одного компилятора

Дмитрий Зуйков

Аннотация:
Данная статья не является учебным курсом по написанию компиляторов, не ставит задачи подробно описать алгоритмы выведения типов или оптимизации. Это просто история о том, как внешне большая, сложная и страшная задача оказывается небольшой и не очень сложной, если использовать правильные инструменты для её решения. Тем не менее, ожидается, что читатель владеет хотя бы основными представлениями о компиляторах.

This article is not a tutorial on how to write a compiler and does not aim to describe the type inference algorithms in detail. This is just a history which tells how big, complex and scary task turns out to be small and quite simple, if proper instruments are utilized. Nevertheless, it is expected that the reader knows at least some basics about compilers.

Обсуждение статьи ведётся по адресу
http://community.livejournal.com/fprog/1605.html.

1 Предпосылки

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

В настоящий момент сервис на базе данной системы находится в стадии запуска в северо-западном регионе РФ в качестве совместного проекта с одним из операторов большой тройки, планируется развёртывание и в других регионах. Помимо этого, разрабатываются совместные проекты с несколькими государственными структурами.

Основные компоненты сервисной системы:

Инфраструктурные сервисы:: данный слой обеспечивает взаимодействие системы с операторами связи и централизованное управление мобильными терминалами. Для реализации используется платформа Erlang/OTP, а в качестве СУБД — Mnesia.
Прикладные приложения:: данный слой реализует различные приложения для пользователей системы; в настоящий момент это решения, предназначенные для контроля личного автотранспорта, а также планирования и мониторинга грузов (логистики). Данные приложения предоставляют веб-интерфейс, но его использование необязательно — может использоваться как «толстый клиент», так и доступ с мобильного телефона посредством IVR. Для реализации приложений также используется Erlang.
Мобильные терминалы:: GSM/GPS и GSM/GLONASS трекеры — автономные модули на базе микроконтроллеров, GSM модема и приемника системы глобального позиционирования. Данные устройства устанавливаются на контролируемых системой объектах и могут взаимодействовать с ней посредством SMS или GPRS. Устройства имеют различные варианты исполнения и могут дистанционно перепрограммироваться в зависимости от решаемых задач.

Применяемые в системе мобильные терминалы должны обладать возможностью очень гибкой удалённой настройки, так как они могут быть использованы в самых различных приложениях, условиях эксплуатации и географических регионах: использование устройств на личных автомобилях с питанием от бортовой сети на дорогах в пределах Московской области, практически полностью покрытой сетями GSM, имеет совершенно иную специфику, чем использование модулей, располагающих только собственным источником питания, перемещающихся вместе с железнодорожными контейнерами через Урал в условиях длительного отсутствия связи и получающих техническое обслуживание (включая зарядку и замену батарей) не чаще, чем раз в полгода.

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

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

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

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

Совокупность этих факторов привела к тому, что от системы, состоящей из серверной части, сети GSM и примитивных автономных устройств добиться надежной устойчивой работы было невозможно. Требовался в корне другой подход.

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

Они должны быть очень компактными.
Они должны с разумной скоростью выполняться на восьмибитных микроконтроллерах (мы начинали с устройств на базе микроконтроллера семейства PIC18), c небольшим объемом RAM (1–3 КБ), ограниченным объемом перезаписываемой постоянной памяти, доступ к которой может быть достаточно дорогим (например, по шине I²C с частотой максимум 400 кГц).
Среда исполнения для них должна обходиться минимальным объемом памяти.
Они должны быть безопасными: никакой загруженный извне скрипт не должен приводить к падению системы с потерей связи с ней.

Было рассмотрено достаточное число готовых реализаций различных языков: форты, лиспы, Joy, Cat, Raven, Tcl, Staapl, Squeak, Lua, Haxe, Python, Java и другие. Был рассмотрен вариант написания своего рантайма для существующего компилятора.

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

По плотности байткода в финал вышли форты и Java (на самом деле squeak, но он отсеялся по другим причинам), но спецификация JVM весьма сложна, и были серьезные сомнения, что за разумное время удастся реализовать её для нашей платформы. При этом пришлось бы научиться дорабатывать компилятор Java самостоятельно, а это сводило преимущества использования чужого решения к нулю. Разрабатывать свой компилятор Java в планы точно не входило.

В результате было принято решение реализовать скриптовый язык и его рантайм самостоятельно.

2 Первое приближение: Форт

Итак, в качестве скриптового языка в первом приближении был выбран Форт. Его преимущества очевидны: он крайне прост в реализации, но при этом довольно мощен. Программа на Форте представляет собой поток токенов, разделённых пробельными символами — таким образом, транслятор Форта не требует парсера, нужен лишь лексический анализатор, он же токенайзер.

В качестве языка реализации транслятора был выбран Python по причине его широкого, на тот момент, применения в проекте.

Рантайм представлял собой типичную двухстековую Форт-машину, без какого-либо управления динамической памятью, реализованную по мотивам F21¹.

Инструкции и литералы (константы) имеют разрядность 8 бит. Используется token threaded code, то есть код, представленный потоком чисел, каждое из которых соответствует смещению в таблице обработчиков².

Транслятор был реализован на Python достаточно быстро, в императивном стиле, и занял в районе двух тысяч строк кода. Останавливаться на его дизайне или реализации, равно как и на подробном описании Форта, выходит за рамки данной статьи: Python — весьма распространенный императивный язык программирования, по Форту тоже доступна масса информации.

При всей красоте Форта как идеи, язык все-таки имеет ряд особенностей, которые делают его использование не таким уж и простым.

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

Еще одна проблема — наиболее компактный код на Форте получается, когда все вычисления проводятся на стеке. Но доступная глубина стека для вычислений в общем случае (не рассматривая Форты с командами типа pickn) ограничена приблизительно четырьмя его верхними ячейками. Более того, циклы со счетчиком организуются либо путем организации третьего «программного» стека для переменных циклов, что разрушает всю изящность языка, либо хранением переменной цикла в стеке адресов, что приводит к различным казусам в случае попытки возврата из слова, вызываемого внутри цикла. Данная проблема приводит к нарушению двух важных требований сразу: безопасности и компактности байткода. Если для реализации некоторого алгоритма не хватает двух-трех переменных, то приходится прибегать к различным ухищрениям: использованию стека адресов для промежуточного хранения данных, неуправляемой памяти — для хранения переменных, а также примитивов типа rot, swap или over. Это раздувает код и, в случае использования стека адресов, может приводить к непредсказуемым ошибкам времени исполнения, а также весьма затрудняет написание и прочтение кода. Как правило, чтобы понять некий алгоритм, реализованный на Форте, требуется его мысленно выполнить, что удаётся не всем.

Теперь можно сказать пару слов о применимости Python в качестве инструмента для реализации трансляторов. Особенности Python — динамическая типизация, неявное введение переменных и «утиная типизация»³. Все это означает, что многие ошибки будут обнаружены только во время исполнения. Разработка сколько-нибудь нетривиального кода зачастую требует многократного рефакторинга и попросту переписывания кода, с частыми откатами назад. Большое количество юнит-тестов в такой ситуации — это не просто признак культуры разработки, а вопрос выживания проекта; при этом тестами мы пытаемся поймать не только функциональные дефекты, но и элементарные ошибки и опечатки, которых при рефакторинге возникает масса. В случае разработки компилятора, придумывать юнит-тесты (в отличие от прочих видов тестов) может быть очень непросто, и этот фактор со временем сильно сокращает преимущество в производительности от применения высокоуровневого языка программирования.

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

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

3 Второе приближение — Бип /Beep/

Несмотря на то, что нами была разработана версия прошивки с реализацией Форт-машины для сторонних GPS-трекеров, применить её в деле не удалось из-за постоянных проблем аппаратного характера, помноженных на особенности ведения бизнеса компанией-разработчиком.

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

Для их реализации был выбран микроконтроллер семейства MSP430, который выгодно отличается от PIC простой и удобной архитектурой, а также является 16-разрядным.

Предыдущий рантайм был реализован на ассемблере для PIC18 и не подлежал портированию, так что предстояло реализовывать его с нуля. Учитывая описанные выше недостатки Форта как прикладного языка, а также бОльшие возможности MSP430, было решено попробовать разработать более удобный, безопасный и доступный скриптовый язык, который бы давал возможность прямого программирования устройств их конечными пользователями.

Данный язык получил название Бип (англ. Beep) в честь звука, которым заглушают нецензурные выражения в средствах массовой информации, так как реалистичность подобной разработки была совсем неочевидна (а еще потому, что у автора есть правило — не тратить на придумывание названий более десяти минут).

3.1 Требования и дизайн языка

Дизайн языка определялся следующими первоначальными требованиями:

«Скриптовость»,

трактуемая как:

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

Высокоуровневость:

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

Универсальность:

Так как границы области применения языка заранее не ясны, то язык должен быть универсальным, использование DSL нецелесообразно.

Императивность:

По предыдущему опыту, типичные реализуемые алгоритмы выглядели императивными, так что логично делать язык императивным.

Простой синтаксис:

Чтобы язык можно было быстро изучить, и чтобы его можно было быстро реализовать.

Расширяемость:

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

Типизация:

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

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

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

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

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

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

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

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

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

3.2 Выбор инструмента разработки

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

Рассматривались два варианта — Haskell и OCaml. Оба языка весьма зрелые, имеют давнюю историю и большое сообщество пользователей, а также большое количество библиотек и различных вспомогательных средств.

Несмотря на то, что Haskell выглядел более выигрышно: богатая, хорошо организованная и единообразная встроенная библиотека, имеется много большее количество сторонних решений, больше доступных онлайн руководств, примеров и книг, начать получать результаты оказалось проще с OCaml. Он и был выбран в итоге.

Существует большое количество примеров компиляторов, реализованных на OCaml, с которыми оказалось интересно ознакомиться перед тем, как начать разрабатывать свой. Вот некоторые из них:

Haxe: Высокоуровневый компилируемый язык со статической типизацией и выводом типов. Компилируется в код для виртуальной машины NekoVM, которая является весьма интересным проектом сама по себе.
MinCaml: Подмножество ML, компилируется в оптимизированный машинный код для SPARC, обгоняющий на некоторых тестах gcc. Являясь частью учебного курса японского Tohoku University, интересен как пример генерации кода и реализации различных оптимизаций.
The Programming Language Zoo: Учебное пособие по курсу разработки трансляторов от Andrej Bauer, включающее реализацию интерпретаторов нескольких языков программирования. Хороший пример базовых техник, применяемых при разработке трансляторов, демонстрирующий использование ocamlyacc и ocamllex.

3.3 Инфраструктура проекта

После того, как было принято решение использовать OCaml, требовалось определиться со средством генерации парсеров и системой сборки проекта. Наиболее простым и хорошо документированным генератором парсеров и лексеров для OCaml является комплект ocamlyacc и ocamllex. Как правило, они распространяются в одном пакете с компилятором, так что фактически их можно считать частью языка.

Для сборки удобно использовать ocamlbuild — эта утилита в простейшем случае вообще не требует конфигурирования и собирает проект в текущем каталоге, самостоятельно определяя зависимости. Кроме того, она понимает входные файлы ocamlyacc и ocamllex, и примеры из Language Zoo используют именно её.

3.4 Дизайн компилятора

Процесс компиляции состоит из следующих фаз:

лексический анализ,
синтаксический разбор и построение AST⁴,
раскрытие макроподстановок,
валидация AST,
построение словаря,
вывод и проверка типов,
оптимизация на уровне AST,
генерация промежуточного кода,
оптимизация на уровне кода,
генерация выходных файлов и
генерация стабов.

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

3.4.1 Синтаксический разбор и построение AST

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

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

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

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

Распространенным способом обработки синтаксического дерева в функциональных языках является рекурсивный обход в сочетании с сопоставлением с образцом; это вообще одна из часто встречающихся при разработке на этих языка идиом.

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

Разумеется, для успешной разработки AST необходимо определить, из чего состоит сам язык и как он устроен.

Бип на текущий момент состоит из следующих основных элементов:

Модули: , каждый из которых представляет собой список определений.
Определения: , которые могут быть декларациями функций, внешних функций, типов или макроопределений.
Операторы: — основные примитивы языка. Они определяют синтаксические конструкции языка и не возвращают значений.
Блоки: представляют собой последовательности операторов, разделённые символом «;» (точка с запятой).
Выражения: Выражение есть некая операция, возвращающая значение и, следовательно, имеющая тип.
Макроопределения: Макроопределение есть идентифицированный блок кода. На этапе раскрытия макроподстановок идентификатор кода в AST заменяется самим кодом. На текущий момент таким образом реализуются только именованные константы, но инфраструктура для макроопределений вполне настоящая, более сложные макроопределения оставлены на следующие фазы развития языка.

Исходный код описания AST:

type ast_top = Module of mod_props * parser_ctx and block = Block of blk_props * parser_ctx and definition = | FuncDef of func_props * parser_ctx | ExternFunc of (name * beep_type) | TypeDef of (name * beep_type) * parser_ctx | MacroDef of macro * parser_ctx and statement = | StEmpty of parser_ctx | StLocal of (name * beep_type) * parser_ctx | StArg of (name * beep_type) * parser_ctx | StAssign of expression * expression * parser_ctx | StWhile of (expression * block) * parser_ctx | StIf of if_props * parser_ctx | StBranch of (expression * block) * parser_ctx | StBranchElse of block * parser_ctx | StCall of expression * parser_ctx | StRet of expression * parser_ctx | StBreak of parser_ctx | StContinue of parser_ctx | StEmit of Opcodes.opcode list and expression = | ELiteral of literal * parser_ctx | EIdent of name * parser_ctx | ECall of (expression * expression list) * parser_ctx | EAriphBin of operation * (expression * expression) * parser_ctx | EAriphUn of operation * expression * parser_ctx | ECmp of operation * (expression * expression) * parser_ctx | EBoolBin of operation * (expression * expression) * parser_ctx | EBoolUn of operation * expression * parser_ctx | EListNil of parser_ctx | EList of (expression * expression ) * parser_ctx | EPair of (expression * expression ) * parser_ctx | ERecord of (name * expression list) * parser_ctx | ERecordFieldInit of (name * expression ) * parser_ctx | ERecordField of rec_desc * rec_field | ENothing | EVoid of expression | EQuot of name * parser_ctx and lvalue = Named of name * parser_ctx and rec_desc = Rec of expression and rec_field = RecField of name * parser_ctx and operation = Plus | Minus | Mul | Div | Mod | BAnd | BOr | BXor | BShl | BShr | BInv | Less | More | LessEq | MoreEq | Equal | Unequal | And | Or | Not and literal = | LInt of int | LBool of bool | LString of string and mod_props = { mod_defs:definition list } and func_props = { func_name:name; func_type:beep_type; func_code:block } and blk_props = { blk_code:statement list; } and if_props = { if_then:statement; if_elif:statement list; if_else:statement } and macro = MacroLiteral of (name * expression)

3.4.2 Валидация AST

После того, как осуществлен разбор исходного кода, требуется проверить корректность построенного AST с точки зрения семантики.

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

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

Типичные примеры валидации: проверка корректности управляющих конструкций (например, того, что операторы continue и break находятся внутри циклов) и проверка корректности выражений (например, того, что в левой части оператора присваивания находится lvalue, т. е. значение, которому можно что-либо присваивать).

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

and assignment e1 e2 ct = match e1 with | EIdent(n,c) -> ct |> add_expr e2 |> add_code (store (get_var ct (n, id_of c))) | ERecordField(Rec(re),RecField(fn,c2)) -> let fi = typeof_name (dot fn,id_of c2) ctx in let rt = field_rec_type fi in let off = rec_field_offset rt fn in ct |> add_expr re |> add_expr e2 |> add_code (op (TBCWD(off)) ~comment:(dot fn) :: []) | other -> raise (Type_error("lvalue required"))

Оператор |> можно назвать «конвейерным оператором», который определен как

let (|>) f x = x f

Это очень часто встречающаяся в программах на OCaml идиома, которая позволяет представить последовательность действий в виде конвейера, где результаты предыдущего этапа передаются на вход текущему, аналогично тому, как это можно делать в командной строке при помощи оператора | («пайп»):

find . -name '*.c' | xargs cat | wc -lc

В нашем случае, запись

st |> push_loop e |> nest

можно интерпретировать как последовательность операций: «взять начальный контекст, добавить цикл, добавить вложенный контекст».

Приведённая функция генерирует промежуточный код для оператора присваивания, принимая два узла AST типа «выражение» и контекст. В левой части присваивания в Бипе в настоящий момент может быть только выражение типа «идентификатор» или «ссылка на поле структуры», остальные типы выражений приведут к генерации ошибки.

Пример использования данной функции при генерации кода (и весь верхний уровень генератора кода):

in let code_fold st code = match code with | StArg((n,t),c) -> st |> add_arg n | StLocal((n,t),c) -> st |> add_loc n | StAssign(e1,e2,c) -> st |> assignment e1 e2 | StWhile((e,_),_) -> st |> push_loop e |> nest | StCall(e,_) -> st |> add_expr (EVoid(e)) | StIf({if_elif=ef},_) -> st |> push_if |> nest | StBranch((e,_),c) -> st |> branch (Some(e)) CBr (id_of c) |> nest | StBranchElse(_,c) -> st |> branch None CBrElse (id_of c) |> nest | StRet(e, _) -> st |> ret e | StContinue _ -> st |> continue | StBreak _ -> st |> break | StEmpty _ -> st | StEmit(l) -> st |> add_emit l

Можно заметить, что генератор кода ориентирован на стековую машину.

Делать какие-либо дополнительные проверки необходимости не возникло.

Очень часто упоминается сложность отладки парсеров, генерируемых автоматическими построителями. Могу сказать, что, благодаря сильной статической типизации и дизайну типа AST, удалось практически совсем избежать отладки. Во всяком случае, на анализ логов парсера ушло пренебрежимо мало времени. После разработки сходного проекта на динамическом языке такой результат кажется неправдоподобным.

3.4.3 Построение словаря

Бип обладает следующими областями видимости:

Модуль: Имена модуля (функции, типы, макроопределения).
Функция: Формальные аргументы функции и переменные верхнего блока.
Блок: Каждый блок может содержать объявления переменных.

Подход к областям видимости совершенно традиционен и похож на Си, Java и другие подобные им языки. Любая область видимости может содержать объявления, перекрывающие имена вышестоящих областей видимости.

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

((имя, идентификатор), дескриптор)

где дескриптор содержит необходимую компилятору информацию об идентификаторе.

3.4.4 Вывод и проверка типов

Для вывода типов в Бипе используется алгоритм Хиндли–Милнера, как наиболее простой и хорошо описанный в литературе и сети. Существует большое количество примеров его реализации на различных языках.

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

Структура типов данных в языке описывается при помощи алгебраических типов OCaml. Например, атомарные типы данных:

| TInt | TString | TBool

или составные типы данных:

| TPair of beep_type * beep_type | TList of beep_type | TVect of beep_type

или тип «полиморфный параметр»:

| TAny of int

или тип «неизвестный тип данных»:

| TVar of int

Типы TVar и TAny очень похожи, наличие обоих типов в реализации типизации обусловлено необходимостью отличать автоматически введённые переменные типов от параметров полиморфных функций.

Ограничения представляют собой равенства вида:

x_i

где слева находится автоматически введённый «неопределённый тип данных», а справа — условие, полученное из анализа выражений, в которых данный тип участвует, и явных деклараций типов, которые язык также допускает.

Операторы и выражения накладывают определённые ограничения на типы операндов. Арифметические и битовые операции подразумевают, что их операнды и возвращаемые значения являются целыми числами. Логические операции подразумевают булев тип данных, операции и функции над списками требуют аргумента типа список (и являются полиморфными, так как список — составной тип данных). Циклы и оператор ветвления требуют булева типа в условии, а оператор присваивания декларирует, что типы переменных в левой и правой частях присваивания одинаковы.

Процесс решения системы уравнений заключается в выводе всех типов TVar и TAny через типы, не содержащие значений неизвестных и полиморфных типов.

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

Система уравнений может быть решена не всегда, как например, в случае типов, определения которых содержат циклические ссылки (таких как рекурсивные типы данных) либо противоречивые условия:

x₁	=	A
x₂	=	x₁
x₂	=	B

Проверка типов осуществляется в два основных этапа. Алгоритм унификации обнаруживает наличие ошибок типов и, в случае, если система уравнений не решаема, порождает исключение.

Второй класс ошибок — отсутствие достаточной информации для выведения типов, т. е. случаи, когда не удаётся устранить все типы TVar и TAny.

Данные ошибки обнаруживаются на этапе формирования промежуточного представления кода, так как генератор кода может произвести только конструкции для известных ему типов, за исключением нескольких случаев, где полное определение неважно (например, функциям для работы со списками не существенно, списки чего именно имеются ввиду). Если при генерации кода встречается значение неизвестного или недоопределённого типа, порождается исключение.

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

Жёсткая типизация операций,

например, арифметических. Если у нас есть целочисленные операции

+ - * /

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

+. -. *. /.

либо сделать их полиморфными. При этом они станут бесполезны для выведения типов своих операндов, что сократит количество случаев успешного автоматического выведения типов и потребует большего количества аннотаций. Можно ввести классы типов и применять другой, более сложный алгоритм выведения. С подобной проблемой сталкиваются и «большие» языки. При этом OCaml, например, выбирает наиболее простое решение — использование разных обозначений для таких операций. Тот же путь приемлем и для нашего языка.

Трудность реализации рекурсивных типов данных.

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

Подробно теория систем типов изложена в книге Benjamin C. Pierce Types and Programming Languages. Примеры из этой книги исключительно полезны для понимания различных аспектов типизации.

3.4.5 Оптимизация на уровне AST

Многие оптимизации удобно проводить на уровне AST в случае, если дерево сохраняет семантику языка, и её не требуется реконструировать.

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

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

Замена последовательности операций сложения с единицей и присваивания на инкремент.
Замена последовательности вычитания единицы и присваивания на декремент.
Замена целого литерала ’0’ на команду VM ’FALSE’ размером один байт.
Замена целого литерала ’1’ на команду VM ’TRUE’ (аналогична предыдущей).

Отметим удобство механизма сопоставления с образцом в данном случае: он позволяет сначала реализовать общую схему генерации кода, добавляя обработку частных случаев по мере необходимости.

Типичные примеры — замена сложения инкрементом и вычитания декрементом:

| EAriphBin(Plus, (_,ELiteral(LInt(1),_)),_) -> repl_inc st | EAriphBin(Plus, _, _) -> st @ [op ADD] | EAriphBin(Minus,(_,ELiteral(LInt(1),_)),_) -> repl_dec st | EAriphBin(Minus,_, _) -> st @ [op SUB]

операция ’@’ в OCaml — конкатенация списков

3.4.6 Генерация промежуточного кода

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

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

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

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

3.4.7 Оптимизация на уровне кода

Полученное представление кода тоже требует оптимизации, включая устранение артефактов генерации кода, таких как лишние команды NOP, устранение бессмысленного кода, такого как сочетание команд вида:

JMP X JMP Y

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

LIT X CALLT

в:

CALL X

3.4.8 Генерация выходных файлов

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

3.4.9 Генерация стабов

Поскольку язык имеет возможности FFI⁵, для связи с функциями на низкоуровневых языках порождаются различные стабы, предназначенные для линковки с кодом виртуальной машины — обертки функций, обертки структур (осуществляющие отображение структур Бипа на структуры Си) и таблицы опкодов виртуальной машины.

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

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

Унификация — не самый дешевый в смысле производительности алгоритм, так что важно поддерживать количество данных, участвующих в унификации, минимальным и не допускать повторных вычислений того, что уже вычислено.

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

В остальном обычный профайлинг и не очень агрессивная мемоизация позволили удержать производительность на уровне, неформально определённом нами как «менее секунды на любом файле, который в состоянии написать человек». Это означает, что как только на каком-либо скрипте время компиляции превышает секунду, берётся в руки профайлер, и эта проблема устраняется. До сих пор это получалось.

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

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

В целом производительность компилятора следует признать удовлетворительной, хотя до идеала далеко — в частности, компилятор OCaml работает существенно быстрее.

3.6 Дизайн рантайма

Рантайм представляет собой двухстековую виртуальную машину, оптимизированную для шестнадцатибитной архитектуры. Текущей платформой является микроконтроллер MSP430 от Texas Instruments, но существует и версия, запускающаяся на PC, используемая в настоящий момент для прототипирования и отладки логики скриптов.

Стек A представляет собой стек данных, стек R — стек для адресов возврата и служебных данных. В отличие от Форта, в Бипе прямой доступ к стеку R невозможен, виртуальная машина управляет им сама.

Стек A разделен на фреймы. В начале каждого фрейма находятся ячейки, зарезервированные для локальных переменных и формальных параметров функции, вершина стека используется для вычислений. Каждый фрейм создаётся соответствующими инструкциями в прологе вызова функции, после возврата из функции восстанавливается предыдущий фрейм.

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

На текущий момент виртуальная машина насчитывает 73 команды.

Опкоды имеют разрядность 8 бит, литералы — 16 бит.

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

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

Данные, умещающиеся в слово, размещаются на стеке A, а данные, превосходящие в размере слово, размещаются в динамической памяти.

Динамическая память (куча) управляется автоматически: реализован консервативный сборщик мусора, важной особенностью которого является отсутствие затрат памяти на обход графа объектов.

Не используются ни стек, ни дополнительное поле заголовка для применения техники reversed pointers. Использование такого алгоритма ухудшает асимптотику алгоритма обхода, но, ввиду отсутствия глобальных переменных, периметр сборки мусора определяется только текущей глубиной стека A, и в некоторые моменты память может быть очищена за гарантированное время O(1).

Куча организована в виде связного списка свободных и занятых блоков, накладные расходы на управление памятью — одно слово на блок. Максимальный размер блока — 8191 слово, что превышает количество RAM на типичном представителе целевой архитектуры.

Параметр Размер Источник ограничения

Code memory ~~3 килобайта реализация VM

Системный стек + RAM < 100 байт реализация VM

Стек A 128 слов определяется пользователем

Стек R 64 слова определяется пользователем

Куча 4096 слов определяется пользователем

Таблица 1: Приблизительные требования виртуальной машины к ресурсам

Микроконтроллер Частота Code memory RAM … в т. ч. куча

MSP430F1612 7.3728 МГц 55 КБ 5 КБ 1 КБ

MSP430F5418 7.3728 МГц 41 КБ⁶ 16 КБ до 14 КБ

Таблица 2: Типичные используемые конфигурации

Производительность виртуальной машины можно характеризовать как «достаточно приличную». Оценивать её имеет смысл только в сравнении с другими, но на целевой платформе сравнивать не с чем, а сравнение с PC будет происходить в слишком неравных условиях, так как рантайм Бипа ориентирован на очень маленькое количество оперативной памяти, и её экономия имеет больший приоритет, чем производительность. И сборка мусора, и выделение памяти ориентированы на минимизацию накладных расходов по памяти, а не на максимальную производительность.

Тем не менее, сравнение работы приблизительно одинакового алгоритма синтаксического разбора строки NMEA⁷ на Lua, Python и Beep показало, что даже в условиях, когда в VM Beep за цикл работы скрипта GC вызывается более десяти тысяч раз⁸, Бип оказывается в три — пять раз быстрее Python, и в полтора — два раза быстрее Lua. Отнести такие результаты можно на счет статической типизации, при которой отсутствуют накладные расходы на проверку типов во время исполнения.

4 Окончательный вид языка

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

Типы данных

Язык поддерживает следующие встроенные типы данных:

Int: Целочисленный тип шириной в слово. Может быть знаковым и беззнаковым. Символы и байты также представляются числом.
String: Строка, интерпретируемая как последовательность символов (чисел). В текущей реализации предполагается, что символ не превышает в разрядности один байт, строка хранится в упакованном виде (каждое слово содержит два символа). Строки являются иммутабельными, одинаковые константные строки в программе являются ссылками на одну и ту же строку⁹.
Bool: Логический тип данных. Управляющие конструкции и логические операторы оперируют значениями этого типа.
Pair: Кортеж элементов разных типов размерностью 2.
List: Список однородных элементов.
Vector: Массив однородных элементов с произвольным доступом.
Fun: Функция.
Record: «Запись», аналог структуры в языках C, C++.

Литералы

Поддерживаются численные шестнадцатеричные, десятичные и строковые литералы, а также литералы «символ», транслируемые в Int.

Переменные

Переменные объявляются оператором local и могут содержать спецификации типов. Переменные могут объявляться в любом месте блока и являются только локальными. Глобальных переменных в Бипе не существует. При объявлении каждая переменная должна быть инициализирована значением, попытка объявить переменную без её инициализации приводит к ошибке компиляции. В Бипе также не существует значений, подобных null, None или undefined в других языках.

Операции

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

Все операции типизированы, например, логические операции принимают и возвращают значения типа Bool.

Оператор сравнения полиморфен и может принимать значения типов Int и String. В последнем случае компилятор генерирует вызов встроенной функции strcmp, которую можно вызвать и напрямую.

Можно также отметить операцию конструирования списка ::, аналогичную соответствующей конструкции языка OCaml, которая создает новый список из указанных головы и хвоста.

Встроенные функции

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

Управляющие конструкции

Язык включает минимум управляющих конструкций: цикл с условием while, условный оператор if-elif-else и операторы break и continue, прерывающий цикл и переходящий к следующей итерации цикла, соответственно.

Условный оператор и оператор цикла требуют в качестве условия выражение типа Bool.

Блоки

Блоки являются последовательностями операторов, разделённых символом «;» (точка с запятой).

Функции

Функции объявляются ключевым словом def и вызываются при помощи оператора ().

Функции в Бипе являются первоклассным типом^10<, могут присваиваться переменным, передаваться как параметры функций и возвращаться из них, помещаться в списки и массивы и так далее.

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

Макрокоманды

На текущий момент язык поддерживает макроопределение только для литералов.

FFI

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

Обработка ошибок

Бип является языком с сильной статической типизацией, вследствие чего скрипты на нем гарантированно корректны в отношении типов. Исключения на текущий момент отсутствуют, ошибки времени исполнения, такие как переполнения стеков, обрабатываются на уровне API рантайма.

5 Примеры скриптов

Hello, world!

def main() { putsn("Hello, world!"); }

Создадим и распечатаем список пар строк

Ради разнообразия здесь мы декларируем типы явно.

def print(val:(string,string)):void { puts(fst(val)); puts(snd(val)); } def main() { local l = ("B","E")::("E","P") ::("R","U")::("L","Z")::[]; local t = l; while !nil(t) { print(head(t)); t = tail(t); } }

Функции — почти совсем первоклассные граждане

def print_smth() { putsn("BEEP RULZ!"); } def print(x: fun(void):void ) { x(); } def main() { local l:[fun(void):void] = print_smth :: print_smth :: print_smth :: []; local t = l; while !nil(t) { print(head(t)); t = tail(t); } }

Работаем с приемником GPS

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

# FFI - declaring external functions # stubs are generated automatically @extern gps_power(bool):void; @extern nmea_read() : string; @extern seconds(void):int; type gps_data { gps_utc:string ,gps_fx:int ,gps_sat:int ,gps_hdop:string ,gps_lat:string ,gps_lats:int ,gps_lon:string ,gps_lons:int } def str_ntok(s,seps,n) { local len = strlen(s); local len2 = vect_len(seps); local off = 0, size = 0; if n == 0 then { off = 0; size = vect_get(seps,0); } elif n >= len2 then { n = len2; off = vect_get(seps, len2-1) + 1; size = len - off + 1; } else { off = vect_get(seps,n-1) + 1; size = vect_get(seps,n) - off; } ret strsub(s, off, size); } def collect_gps_data() { local fx = 0; local utc = ""; local sat = 0; local hdop = ""; local lat = ""; local lats = ""; local lon = ""; local lons = ""; local i = 0; local timeout = 30; local t1 = seconds(), dt =0; while i < 10 && timeout != 0 { dt = seconds() - t1; t1 = seconds(); if timeout >= dt then timeout = timeout - dt; else timeout = 0; local s = nmea_read(); if s != "" then { #putsn(s); local sep = strfindall(s,','); if startswith(s, "$GPGGA") then { fx = strtoul(str_ntok(s,sep,6),16); sat = strtoul(str_ntok(s,sep,7),16); utc = strsub(str_ntok(s,sep,1),0,6); lat = str_ntok(s,sep,2); lats = str_ntok(s,sep,3); lon = str_ntok(s,sep,4); lons = str_ntok(s,sep,5); hdop = str_ntok(s,sep,8); i = i + 1; } } if fx > 0 then break; } local ss = strnth(lats, 0); ret { gps_data: gps_utc = utc ,gps_fx = fx ,gps_sat = sat ,gps_hdop = hdop ,gps_lat = lat ,gps_lats = strnth(lats,0) ,gps_lon = lon ,gps_lons = strnth(lons,0) }; } def main() { putsn("GPS ON"); gps_power(true); while true { local nmea = collect_gps_data(); if nmea.fx > 0 then { putsn("Coords fixed") puts("Satellites: "); putsn(utoa(nmea.gps_sat, 16)); puts("Latitude: "); putsn(nmea.gps_lat); puts("Longitude: "); putsn(nmea.gps_lat); } } }

Модем (и макросы)

И напоследок, поработаем с модемом и немного с макросами:

@extern gps_power(bool) : void; @extern modem_power(bool) : void; @extern modem_power_check(void) : bool; @extern modem_init(int) : bool; @extern modem_ussd(string, int) : string; @extern modem_sms_send(string, string) : bool; @extern nmea_read() : string; @extern seconds(void) : int; @literal INITIAL 0; @literal DIGIT 1; @literal NOPINCODE 0xFFFF; def parse_account(s) { local i = 0, begin =0, end = 0; local len = strlen(s); local state = `INITIAL; while i < len { local c = strnth(s, i); if state == `INITIAL && c >= '0' && c <= '9' then { state = `DIGIT; begin = i; } if state == `DIGIT && c == '.' then { end = i; break; } if state == `DIGIT && c < '0' || c > '9' then state = `INITIAL; i = i + 1; } if begin >= end then ret (false,0); ret (true,strtoul(strsub(s,begin,end-begin),10)); } def main() { gps_power(true); modem_power(true); putsn("MODEM ON"); local i = 0; while i < 20 { puts("."); sleep_ms(1000); i = i + 1; } modem_init(`NOPINCODE); sleep_ms(2000); local money = snd(parse_account( modem_ussd("#102#",32))); puts("MONEY: "); put_int(money); sleep_ms(2000); modem_sms_send("+71234567890" "PRIVED, KRIVEDKO!"); }

6 Итоги

Практическое применение языка

Разумеется, Бип был разработан вовсе не как фан-проект для обучения написанию компиляторов. И его предтеча, Форт, и он сам применялись в разрабатываемых системах, даже будучи не совсем стабильными, развиваясь параллельно с основными системами.

Основные цели, которые ставились при разработке Бипа, были достигнуты, а по отдельным параметрам он даже превзошел связанные с ним ожидания.

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

Еще один немаловажный аспект: байткод Бипа плотнее, чем машинный код, генерируемый компилятором Си. В то время, когда ресурсы code memory, отведённые под прошивку (около 32 КБ flash), практически исчерпаны, 8 КБ сегмента, отведённого под байткод, еще имеют резервы. В связи с этим нехватка функциональности прошивки вполне может быть компенсирована за счет скрипта.

Применение Бипа позволило добиться таких характеристик системы, как надежное удалённое изменение поведения устройств и отсутствие необходимости в фиксированных протоколах работы: протокол реализуется скриптом и может быть любым, удобным для конкретного применения устройства.

В некоторых случаях устройствам, несущим на борту Бип, даже не требуется никакой специальной серверной инфраструктуры. В случае, если их в системе не очень много, и им достаточно работы по GPRS/HTTP, трекеры могут работать на общих основаниях с остальными пользователями веб-приложения, что помогает значительно упростить интеграцию уже существующими системами.

HTTP-клиент, разумеется, также реализован на Бипе; ничто не мешает реализовать SOAP или XMLRPC, если возникнет такая необходимость.

Обновление скрипта может происходить различными способами, наиболее простой из них — HTTP с докачкой.

Удалённое обновление скрипта уже многократно использовалось при пользовательском тестировании, позволяя устранять различные проблемы на лету, практически между двумя событиями трекинга, менее чем за 30 секунд. Пользователи даже не замечали, что произошло что-то особенное.

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

OCaml в качестве языка разработки

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

В рамках данной задачи именно OCaml оказался идеальным инструментом — остальные альтернативы неизбежно привели бы к сильному проигрышу в сроках, что в нашем случае было эквивалентно смерти проекта, так как он мог выжить только в случае очень быстрого появления хотя бы proof-of-concept реализации, которая показала бы, что язык с требуемыми характеристиками вообще возможно разработать за реалистичное время имеющимися силами.

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

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

Рост размера кода, увеличение его структурной сложности, количества предположений, соглашений и взаимосвязей, уменьшение его понятности — очень существенные негативные факторы, которые нельзя игнорировать.

Можно привести такой пример: существуют довольно интересные языки программирования Haxe и Boo. Они во многом похожи, например, строгой статической типизацией и выводом типов. Первый язык реализован преимущественно на OCaml, второй — на C#.

Реализация системы типов в Boo, написанном на C#, занимает более семнадцати тысяч строк кода (более половины мегабайта кода на высокоуровневом языке), размещающихся в ста двадцати двух файлах. При этом представлявший наибольший интерес алгоритм вывода типов надежно декомпозирован на слои и «шаблоны проектирования» и код, который его реализует является вполне идиоматичным для этого класса языков. Задача идентифицировать основной код алгоритма и понять его не выглядела решаемой за разумное время и была оставлена.

Ни одной понятной реализации системы типов и алгоритма выведения на императивных языках найдено не было (были рассмотрены варианты на C#, С++ и даже Perl).

Реализация системы типов в языке Haxe, занимает 4088 строк (127624 байт кода) на OCaml и размещается в трех файлах, при этом интересующий алгоритм идентифицируется сразу же и представляет собой, в основном, свертку списков с применением сопоставления с образцом. Прочитать и понять его было достаточно легко, несмотря на то, что на тот момент опыт разработки и чтения кода, написанного на императивных языках, сильно превосходил аналогичный опыт для функциональных.

Даже со всеми возможными оговорками разница в функциональности систем типов Boo и Haxe гораздо меньше, чем разница в количестве кода, эту функциональность реализующего: 100072 строки (2955595 байт) кода текущей реализации Boo убивали всякую надежду, что подобный проект может вообще быть реализован самостоятельно.

Для сравнения, текущие значения для Бипа: 2592 строки (109780 байт) кода, а время, затраченное на реализацию вместе с рантаймом, не превышает трех человеко-месяцев. Это маленький проект, и сделать его маленьким помог именно выбор OCaml в качестве языка разработки.

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

Не было никаких оснований полагать, что выбор низкоуровневого статического языка для реализации Бипа приведет к результатам, которые ближе к тем, что получились у авторов Haxe, чем к показателям авторов Boo.

Использование динамических языков, таких как Python или Ruby¹³, наверняка бы привело к разрастанию количества юнит-тестов и отказу от продолжения разработки проекта на этапе еще второго рефакторинга. Эта тенденция четко прослеживалась на нашем опыте использования Python в качестве основного языка разработки в различных проектах, и разработка транслятора Форта, речь о котором шла в начале статьи, её только подтвердила. Исследование возможности применения проекта PyPy (реализация транслятора Python на Python, а также инфраструктура для построения компиляторов на этом языке) тоже не убедило в обратном.

Никакое количество тестов не может гарантировать отсутствие ошибок. Между тем, сильная статическая типизация именно гарантирует отсутствие ошибок определённого класса.

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

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

Последний фактор оказался весьма важен, так как скорость компиляции — это заметный фактор, влияющий на использование языка.

Принимая во внимание усилия, которые пришлось (и еще придется в дальнейшем) приложить для достижения приемлемого для работы времени компиляции, можно констатировать правильность этого выбора.

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

Попытки использовать Haskell также предпринимались, но он был с сожалением отложен, несмотря на все его возможности, которых недостаёт в OCaml. Довольно быстро стало ясно, что использование Haskell неподготовленным человеком может привести к затягиванию сроков, а кроме того, было неочевидно влияние его ленивости на разработку.

В заключение хотелось бы сказать, что не стоит рассматривать OCaml и Haskell как языки, предназначенные исключительно для разработки компиляторов — это отличные инструменты, подходящие для обширного круга задач. Эти языки предлагают удачный набор абстракций, который позволяет концентрироваться на решении задачи, не размениваясь на второстепенные цели типа обслуживания инфраструктуры¹⁴ или то, что обычно называют строительством велосипедов. Они обладают развитым инструментарием 15 и набором библиотек, при этом позволяют генерировать код, по производительности не сильно уступающий, а иногда превосходящий код более распространённых низкоуровневых языков.

1: Известный, даже можно сказать, культовый в Форт-среде процессор, см. например: http://www.ultratechnology.com/f21data.pdf.
2: На самом деле, конкретный способ обработки может варьироваться в зависимости от реализации виртуальной машины.
3: Duck typing.
4: Abstract syntax tree, «абстрактное синтаксическое дерево».
5: Foreign Function Interface, интерфейс для вызова функций, реализованных на других языках, в нашем случае на C или ассемблере.
6: Расширенная память не используется.
7: Стандарт на обмен данными для GPS устройств.
8: При ограничении кучи в 1 КБ.
9: Константы размещаются в памяти кода, не занимая память кучи.
10: Насколько это возможно без реализации замыканий.
11: Управляемые исключения не противоречат концепции системы, здесь имеются ввиду исключения вида NullPointerException, исключения при ошибках типов и тому подобные, которыми «радует» своих пользователей, например, Java, и которые были бы фатальны для устройства. Декларируемые, управляемые исключения с гарантированной обработкой компилятором вполне допустимы и не были реализованы исключительно из-за недостатка времени.
12: Разумеется, падения из-за ошибок реализации присутствовали и устранялись в процессе разработки.
13: Ruby не демонстрирует особенных преимуществ перед Python, но имеет ряд очень существенных недостатков, так что реально его рассматривать было бессмысленно.
14: Пресловутые «шаблоны проектирования».
15: Если не понимать под ним исключительно IDE.

Этот документ был получен из L^AT_EX при помощи H^EV^EA


Параметр	Размер	Источник ограничения

Code memory	~~3 килобайта	реализация VM
Системный стек + RAM	< 100 байт	реализация VM
Стек A	128 слов	определяется пользователем
Стек R	64 слова	определяется пользователем
Куча	4096 слов	определяется пользователем


Микроконтроллер	Частота	Code memory	RAM	… в т. ч. куча

MSP430F1612	7.3728 МГц	55 КБ	5 КБ	1 КБ
MSP430F5418	7.3728 МГц	41 КБ⁶	16 КБ	до 14 КБ

Практика функционального программирования