22497

Разработка компилятора расширяемого языка системного программирования

Дипломная

Информатика, кибернетика и программирование

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

Русский

2015-01-19

194 KB

4 чел.

Разработка компилятора расширяемого языка системного программирования


РЕФЕРАТ

Косенко В. В. РАЗРАБОТКА КОМПИЛЯТОРА РАСШИРЯЕМОГО ЯЗЫКА СИСТЕМНОГО ПРОГРАММИРОВАНИЯ диссертация на степень магистра наук: стр. ?, рис. ?, табл. ?,  библ. ? назв.

Ключевые слова: РАСШИРЯЕМЫЕ ЯЗЫКИ ПРОГРАММИРОВАНИЯ, СИСТЕМНОЕ ПРОГРАММИРОВАНИЕ, КОМПИЛЯТОР, ГЕНЕРАЦИЯ ПРОМЕЖУТОЧНОГО КОДА, НИЗКОУРОВНЕВОЕ ПРОГРАММИРОВАНИЕ, CSEL.

Объект исследования –расширяемый язык программирования.

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

В ходе работы были описаны лексика и синтаксис языка, а также были приведены ключевые алгоритмы этапы генерации кода и рассмотрен пример практического использования. Результатом стала реализация компилятора на  C# и набора библиотек для нового языка, описывающих конструкции для удобной регистрации его абстракций, а так же известные примитивы if, if-else, for-break.

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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ 4

. Литературный обзор 5

.1. Языки прикладного программирования 5

.2. Языки системного программирования 9

. Постановка задачи 12

. описание языка 13

.1. Концепция 13

.2. Лексика 14

.3. Синтаксис 17

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

.5. Пример 28

Заключение 30

Литература 31

ПРИЛОЖЕНИЕ 1 33

Приложение 2 35


ВВЕДЕНИЕ

Системное программирование как подход к программированию подразумевает:

  1.  Разработку сложных структур данных и алгоритмов.
  2.  Неавтоматическое управление ресурсами.

Изначально всё не узкоспециализированное программирование было системным. Программисты работали на уровне операционной системы, опираясь только на её абстракции. Позже появились виртуальные машины, добавляющие новый уровень абстракций времени исполнения языка программирования, включающий динамическую типизацию, исключения, автоматическую сборку мусора, декларативное описание вычислений. Оказалось, что эти нововведения позволяют решать многие системные задачи эффективнее по скорости и удобству разработки, но с потерями в производительности получающихся программ. Подход стал очень популярен. Например, в версии Lenny широко известного дистрибутива Debian Linux языки Perl, Python, Java, Haskell и Scheme применяются примерно в 40% официальных пакетов. Вокруг таких языков и сформировалось прикладное программирование, но замены одного подхода на другой не произошло.

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

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

. Литературный обзор

.1. Языки прикладного программирования

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

  1.  Системное программирование по своей природе императивно.
  2.  Виртуальные машины нельзя широко использовать:
  3.  Интерпретация медленнее исполнения машинного кода.
  4.  JIT-компиляторы слишком сложны.

Декларативная парадигма

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

Декларативная парадигма не является прерогативой языков прикладного программирования. Найдется ряд довольно низкоуровневых языков её реализующих, но здесь мы рассмотрим высокоуровневые примеры: функциональный Haskell, логический Prolog и далее несколько языков со «смешанной» парадигмой.

Нaskell

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

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

  1.  Побочные эффекты.
  2.  Строгость порядка исполнения.

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

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

Prolog

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

Так практика показывает, что back-end классического для системного программирования компилятора эффективно реализуется на логическом языке Prolog, а front-end – нет [2]. Логические языки – это специфический инструмент, и в сферах, не связанных с базами знаний, пригодный только для разработки прототипов.

Мультипарадигменные языки

В попытке сделать логические языки более универсальными был создан функционально-логический Mercury [3], сочетающий в себе Haskell и Prolog, но не исключающий сложностей с изменяемым состоянием.

Языки OCaml, F# и Oz [4] продолжают развивать идеи декларативно-императивного ML. Возникающие на стыке парадигм подходы справляются с задачами системного программирования с точки зрения выразительности, и на первый план выходят проблемы исполнения виртуальными машинами.

Виртуальные машины

Технологически виртуальные машины реализуются интерпретацией или just-in-time компиляцией. В первом случае базовым конструкциям языка соответствуют подпрограммы, вызываемые виртуальной машиной по ходу разбора исходного кода. При этом всё внутреннее состояние выполняемой программы (типы, переменные, функции …) целиком поддерживается интерпретатором. Подход высокоуровневый и не затрагивает особенностей платформы, поэтому легко и широко распространяется, но, как видно из Таблицы 1.1, сильно отстает от статической компиляции по времени исполнения и эффективности использования памяти [5].

Таблица 1.1. Сравнение эффективности языков

X/C++

Время исполнения

Используемая память

Java

2x

10x

Lua

25x

1.9x

CPython

x

3.4x

Mozart/Oz

x

24x

Ruby

x

27x

Perl

x

.5x

От сложного первичного разбора часто отказываются, интерпретируя не исходный код, а его оптимизированное представление, байт-код как в Java, CPython и Oz, но переломить ситуацию не получается.

JIT-компиляция

Настоящее ускорение получается во втором случае, при включении в цикл интерпретации мощного компилятора с кэшем. Рассмотрим простой пример LuaJIT [6]:

  1.  Сначала интерпретация с накоплением статистики. В некоторых «точках» программы начинаем трассу1: если такая трасса уже в кэше, выполняем соответствующий ей машинный код, иначе переход к 2.
  2.  Продолжение интерпретации и запись трассы в виде SSA2-микрокода (поток выполнения и состояние окружения). Если происходит ошибка, возвращаемся назад, если трасса кончилась, переходим дальше.
  3.  Оптимизация и компиляция микрокода трассы в машинный код, который кэшируется интерпретатором.
  4.  Возврат к началу.

Наиболее сложным является определение «точек», моментов, когда динамическому фрагменту программы можно сопоставить статический скомпилированный аналог. Метод становится более низкоуровневым, и замедление сокращается, а эффективность использования памяти возрастает, но двукратное отставание –лучший результат по данным Таблицы 1.2 [5].

Таблица 1.2. Сравнение эффективности языков


X
/C++

Время исполнения

Используемая память

LuaJIT

x

1.5x

C#

x

.7x

F#

x

.7x

Python PyPy

x

x

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

.2. Языки системного программирования

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

Известно, что ключевыми языками системного программирования является пара: Си и Си++.

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

Си++ создавался как расширение Си. Была добавлена поддержка объектно-ориентированного программирования, шаблоны. Возможности осмысленно выбирались «неортогональные». Такая разнородность, почти полная обратная совместимость с предшественником и, кончено, высокая эффективность компилятора сделали новый язык очень популярным.

Остановимся на проблемах. Оба языка основываются на разработках 60-70-х годов и не учитывают наработок, связанных с виртуальными машинами. Отсутствие сопрограмм в Си, уникальность функций по имени в условиях современности осложняют программирование. Более мощный Си++ лучше адаптируется, но перегруженный разными техниками язык труднее освоить, а его компилятор – реализовать. Альтернативой является Objective-C, созданный примерно в то же время и реализующий объекты не процедурами, а пересылкой сообщений. Подход проще и однороднее, но, несмотря на все возможные оптимизации, такая абстракция медленнее Си++ в полтора раза по времени исполнения. В Приложении 1 приведены результаты тестов. Проблемы давно известны, но предложить что-то принципиально новое и, в то же время, не потерять сильные стороны сложно.

Диалекты C/C++

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

  •  динамическая генерация кода Tick-C [7];
  •  система типов с безопасными указателями Cyclone [8];
  •  параллельное программирование OpenMP.

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

Особняком стоит разработка Clang [9], исправляющая недостатки прежних компиляторов, и новая версия стандарта C++0x [10]. Оба проекта развиваются с целью продлить срок широкого использования C/C++ еще как минимум на десять лет, но, как и диалекты, они не смогут в полной мере избавиться от концептуальных ограничений. Си будет только наращивать свои выразительные возможности, усложнять компилятор, при этом уровень абстракций языка будет оставаться примерно тем же.

Новые языки

Создатели языка D [11] в своём проекте сделали выводы из практики C++, часть механизмов переработали, что-то добавили из Java и Python. Но несмотря на большой объем проделанной работы с точки зрения системного программирования ничего не поменялось, просто всё что делается в C++ на уровне библиотек, здесь является механизмом языка.

По-другому спроектирован экспериментальный Go [12], на основе Си-подобного языка выстроена более мощная система типов с обобщенными интерфейсами, добавлена встроенная поддержка многопоточности и всё это с упором на очень быструю компиляцию. Язык получился современным и легким, но уже сейчас видно, что структура получается жёсткая, а, значит, дальнейшее развитие будет напоминать расширение Си.

Рассмотренные языки, так или иначе, исходили из сложившейся практики императивного системного программирования. Не так давно сочетание  декларативной и императивной парадигм было эффективно реализовано в ATS [13, 5]. Мощнейшая система типов, позволяющая проводить огромное количество статических проверок, сборка мусора, сопоставление с образцом, шаблоны, исключения и отлаженный FFI3 с Си делают язык действительно перспективным. Но из-за отсутствия полной документации и нестандартной модели исполнения на основе автоматического доказательства теорем продвижение идёт медленно. На данный момент неакадемических примеров использования пока нет. Нестандартные модели вообще трудно усваиваются программистским сообществом, тому же Haskell’у потребовалось около 15 лет для этого.

. Постановка задачи

Как было показано выше, прикладные языки не дают нужного уровня производительности, а системные, идут путём экстенсивного расширения или опираются на нестандартные подходы, эффективность которых на практике не подтверждена. Недостаток удачных разработок компенсируется только временными решениями, адаптирующими C/C++ к текущим задачам.

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

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

  •  Императивность;
  •  Расширяемый синтаксис;
  •  Наличие механизма низкоуровневого программирования;
  •  Компактность и эффективность компилятора соизмеримые с Си.


3. описание языка

.1. Концепция

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

На практике разработчики Nemerle [14] реализуют операторы if и все циклы в своей стандартной библиотеке за счёт макросов и сопоставления с образцом, а Katahdin [15] вообще предлагает программировать грамматики. Оба проекта подтверждают жизнеспособность идеи, но, во-первых, делают это неэффективно, используя .Net, следовательно, проигрывая даже C#, во-вторых, не пытаются таким образом реализовать более сложные абстракции, такие как обработка ошибок, конструкторы типов или объекты. Ситуацию можно исправить и развить идею расширяемых языков применительно к системному программированию.

С этой целью была разработана концепция CSeL [16], использующая в рамках языка арифметических выражений со статической типизацией перегрузку операторов и метатипы для программирования конструкций if-else, for-break-continue и switch-case-default-break. При первой же реализации выявилась несостоятельность операторного подхода: значительный объём вспомогательного кода с одной стороны и отчасти, как следствие, очень медленная компиляция с другой. Например, определение if’а требует 3 типа, 5 операторов и специальный механизм накопления результата, что в итоге даёт программу в 90 строк, а аналогичное объявление в Nemerle занимает всего 10 строк одним макросом. Возникла проблема.

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

.2. Лексика

Лексически исходный код CSeL состоит из пробельных символов, комментариев и смысловых единиц, токенов:

<CSeL> = ( <whitespace> | <comment> | <token> )*

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

Таблица 3.1. Базовые понятия

Десятичные цифры

<dec> = “0” –“9”

<ds> = <dec>+

Шестнадцатеричные цифры

<hs> = ( <dec> | “A” –“F” | “a” –“f” )+

Алфавитный символ

<alpha> = “A” –“Z” | “a” –“z”

Символ перевода строки

<newline> = 0A5

Пробельный символ

<whitespace> = <newline> | 20 | 09

Кавычка

<q> = 27

Комментарий

<comment> = “//” ( ! <newline> )*

Токены

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

  •  атомарные операнды;
  •  операции;
  •  скобки.

<token> = <atom> | <op> | <bracket>

Атомарные операнды

Атомарные операнды CSeL разделяются на идентификаторы, числовые константы и строки:

<atom> = <id> | <number> | <string>

Идентификаторы имеют классическое определение:

<idstart> = “_” | <alpha>

<id > =  <idstart> ( <idstart> | <dec> )*

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

<number> = <deciconst> | <hexaconst>

<deciconst> = <ds> [ “.” <ds> ] [ ( “e” | “E” ) [ “-”  ] <ds> ]

<hexaconst> = “0” ( “x” | “X” ) <hs>

Строки заключаются в одинарные кавычки и могут содержать esc-последовательности, автоматически преобразуемые при лексическом разборе в соответствующие символы. В текущем варианте “\n” заменяется на 0A, “\t” на 09, “\xYY” или “\XYY” на символ ASCII с шестнадцатеричным кодом YY.

<string> = <q> ( !<q> )* <q>

На данном этапе лексика реализует только символы US-ASCII, но на будущее уже запланирован переход на UTF-8, с поддержкой национальных алфавитов для идентификаторов и строковых констант.

Операции

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

<op> = <point> | <unary> | <mul> | <add> | <rel> | <logand> | <logor> | <colon> | <dots> | <semicolon> | <comma> | <tick> | <assign> | <apply>

Чтобы упростить синтаксический анализатор и несколько облегчить программирование, побитовые операции не выделены в отдельные классы токенов, а распределены между сложением и умножением как в Go.

<point> = “.”

<unary> = “~” | “!”

<mul> = “*” | “/” | “%” | “&” | “<<” | “>>”

<add> = “+” | “-” | “|” | “^”

<rel> = “<” | “<=” | “>=” | “>” | “!=” | “==”

<logand> = “&&”

<logor> = “||”

<colon> = “:”

<dots> = “..”

<semicolon> = “;”

<comma> = “,”

<tick> = “`”

<assign> = ( <mul> | <add> ) “=”

Скобки

<bracket> = <{> | <}> | <(> | <)>

<{> = “{”

<}> = “}”

<(> = “(”

<)> = “)”

Замечания

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

пара подряд идущих токенов t1t2 заменяется на тройку t1<apply>t2, если

t1∈{ <id>, <number>, <string>, <)>, <}> }

t2{ <id>, <number>, <string>, <(>, <{> }.

Рассмотрим пример:

if ( … ) { … }

преобразуется в

<idif> <apply> <(> … <)> <apply> <{> … <}>

Цепочка «склеивается» связками и получается регулярная операторная структура, которую легко перегружать как целиком, так и по частям. Связки позволяют свести весь привычный синтаксис к операторам, в этом их смысл.

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

.3. Синтаксис

Все синтаксические конструкции CSeL – выражения. Это и атомарные операнды, и более сложные структуры, сформированные из них, символов операций и скобок. Синтаксис в таких случаях определяют неоднозначной грамматикой и таблицей ассоциативности/приоритетов операций, так как в этом случае есть алгоритм построения минимального SLR(1)-анализатора, при котором вариативность устраняется автоматически [16, Приложение 2]. Кроме того, если появится необходимость что-то поменять, конфигурировать таблицы проще, чем пытаться переделать грамматику.

Итак, грамматика:

<E> = <number>

<E> = <string>

<E> = <id>

<E> = <unary> <E>

<E> = <add> <E>

<E> = <tick> <E>

<E> = <E> <point> <E>

<E> = <E> <apply> <E>

<E> = <E> <mul> <E>

<E> = <E> <add> <E>

<E> = <E> <rel> <E>

<E> = <E> <logand> <E>

<E> = <E> <logor> <E>

<E> = <E> <assign> <E>

<E> = <E> <colon> <E>

<E> = <E> <dots> <E>

<E> = <E> <semicolon> <E>

<E> = <E> <comma> <E>

<E> = <(> <E> <)>

<E> = <{> <E> <}>

Параметризация бинарных операций приведена в Таблице 3.2.

Таблица 3.2. Приоритет и ассоциативность бинарных операций

Операция

Приоритет

Ассоциативность

point

12

левая

apply

11

левая

mul

10

левая

add

9

левая

rel

8

левая

logand

7

левая

logor

6

левая

assign

правая

colon

левая

dots

левая

semicolon

левая

comma

левая

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

Итак, дерево синтаксического разбора построено. Последним этапом, предваряющим генерацию кода, является преобразование поддеревьев colon и semicolon только учитывающее порядок, но не вложенность:

*colon

*colon

*colon

d

a

b

c

d

*colon

c

a

b

С этого момента с каждым узлом синтаксического дерева связывается две переменные value (результат) и code (промежуточный код –реализация), и в процесс компиляции включается генератор кода. Далее под компиляцией будем понимать вычисление значений этих переменных для некоторого узла. С учётом этого определения, задача генератора –компиляция корня дерева.

Рассмотрим элементы языка, отвечающие за этот процесс: IR7-вставку и механизм вывода на её основе.

IR-вставка

Синтаксически вставка имеет вид:

apply

apply

idir

string

или

idir

colon

x

y

z

string

x, y, … z –необязательные аргументы, строка –текст из инструкций.

Инструкции описываются формально:

Метка (число)

Имя инструкции

Операнды инструкции

[“*” <ds> <whitespace>]

<id>

([ “#” | “%” | “&” ] <ds>)*

Метки инструкций должны использоваться без повторений (SSA).

Операнды могут быть метками или указателями на аргументы вставки:  на узел соответствующий аргументу (#), на результат узла (%) и на лексему узла-идентификатора (&). Заметим, что аргументы нумеруются с нуля, а при обращении % вызывается процедура компиляции узла. Следует иметь в виду общее правило, если узел уже был скомпилирован, то дублирующего вызова не происходит.

Инструкции подразделяются на две группы:

  •  Директивы, начинающиеся с «_», интерпретируемые во время компиляции, через которые осуществляется всё взаимодействие с абстракциями языка;
  •  Прочие инструкции, которые составляют реализацию узла IR-вставки, результат при этом считается неопределенным.

Абстракции языка

Типы

В CSeL три базовых типа: type, number и string.

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

Переменные

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

Синтаксические подстановки

Подстановки лежат в основе работы механизма вывода CSeL, любая из них определяются тройкой (P, R, A), где

P и R – это указатели на узлы в дереве; P – шаблон, R – замена.

A – словарь аргументов: имя аргумента его тип.

Именованные метки

Именованные метки CSeL – это переменные без типов, не связанные с хранилищем.

Области видимости

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

Такими структурами являются все абстракции и метки. Для абстракций действуют строгие правила регистрации, иногда допускающие перекрывание имён, иногда – нет. Метки переименовываются автоматически, например:

{

ir

jmp 0

halt

’;

ir’*0 nop’

};

ir’*0 nop’

jmp 22

halt

*22 nop

*23 nop

Директивы

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

На данный момент в CSeL реализовано шесть директив. Рассмотрим их синтаксис и семантику.

_store <from: метка> <to: метка>

Копирует значение времени компиляции из ячейки с меткой  from в ячейку с меткой to.

<r> _type [ <size: целое число> ] <x1: идентификатор или тип> …

Регистрирует новый тип во внешней области видимости (родительской по отношению к текущей), указывая в качестве объёма памяти операнд size, если он есть, или нуль –иначе, и вычисляя сигнатуру по алгоритму:

Signature = ‘’.

Цикл по xi

 Signature += ‘(’+

 (если xi –тип, то его сигнатура, иначе лексема идентификатора) + ‘)’.

Под идентификатором понимается операнд &.

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

<r> _var <type: тип> <name: идентификатор>

Регистрирует во внешней области видимости новую переменную с именем name и типом type. Если такой переменной нет вообще или она определена в области видимости выше внешней в иерархии, то переменная создаётся успешно, иначе генерируется ошибка. В случае успеха оценивается тип переменной, если для значения требуется ненулевой объем памяти, то к реализации компилируемого узла добавляется инструкция <r> #allocN, где N – число байт.

_syntax <patter: узел> <replace: узел> <ids: узел> <types: узел>

Узлы передаются как операнды #.

Регистрирует во внешней области видимости новую синтаксическую подстановку (pattern, replace, A), где словарь А строится по алгоритму:

split(n) = если метка узла ncolon, то

возвращаем список его сыновей,

иначе – список, состоящий из него самого.

ids = split ids.

types = split types.

компилируем все элементы types.

если длина ids и types не совпадает, то генерируем ошибку.

цикл по индексам ids (i)

A[ids[i]] = types[i] –тип, иначе undef

_link <name: идентификатор> <e: метка>

Регистрирует в текущей области видимости именованную метку e под именем name. Если такой переменной нет вообще или она определена в области видимости выше внешней в иерархии, то переменная создаётся успешно, иначе генерируется ошибка.

Под идентификатором понимается операнд &.

<r> _label <name: идентификатор>

Если именованная метка с именем name существует хотя бы в одной области видимости в иерархии, то соответствующая ей метка переименует метку r далее во всей текущей области видимости.

Под идентификатором понимается операнд &.

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

Механизм вывода

Примитивные конструкции

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

Атомами являются идентификаторы и константы. В обоих случаях реализация не содержит ни одной инструкции. Для узлов-идентификаторов результатом служат метки соответствующих им переменных. Если какой-то переменной не зарегистрировано, генерируется ошибка. Для узлов-констант отводятся метки и ячейки, хранящие лексемы, для строк с типом string, для чисел –number, эти метки и становится результатами.

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

Итак, смысл основных всех элементов языка кроме одного раскрыт. Речь идёт о механизме синтаксических подстановок. Рассмотрим этапы, из которых он состоит: выбор и применение.

Выбор

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

Сначала выбираются все наилучшие синтаксические совпадения так, как если бы подстановки были обычными макросами:

match(syntax, node) =

обход в ширину одновременно syntax.P (a) и node (b)

если a –узел-идентификатор и syntax.A[a] –определено, то

сохраняем совпадение a  b в syntax.match

   иначе

если в a и b не совпадают

либо типы узлов, либо лексемы, либо число дочерних узлов, то

         return false.

return true.

cmp(s1, s2) =

если match(s1, s2.P), то

   если в s1.match все правые стороны из s2.A, то

     return 0 т.е. аргументы в s1 являются аргументами в s2.

return -1.

return 1.

matches = []

X –корень поддерева, для которого проводим поиск

цикл по всем подстановкам (s)

если match(s, X), то

   если matches –пусто, то

matches.add(s)

иначе

sxэлемент из matches

варианты cmp(sx, s)

если -1: matches = [s] т.е. sлучшее совпадение

если 0: matches.add(s) т.е. s –не лучше и не хуже.

Теперь необходимо провести отбор на основе типов:

цикл по matches слева направо (match.a, match.b)

если в matches есть подстановки, у которых A[a] – undef, то

   это должны быть все подстановки, или ошибка

иначе

компилируем b

фильтруем matches, так чтобы A[a] равнялось типу результата b

   если в matches ничего не осталось, то ошибка.

если в matches более одной подстановки, то ошибка.

Наилучшее совпадение выбрано.

Заметим, что возможно вложенное использование подстановок, и в этом случае информацию о последнем успешном сопоставлении (.match) следует реализовывать в виде стека. Например, есть подстановка с шаблоном a+b, где a и b – аргументы. Выбор подстановки для выражения (x+y)+z при сопоставлении a  x+y приведет к рекурсивному вызову {a  x, b  y}, и если .match была обычной переменной, то данные о первом сопоставлении потеряются.

Применение

Когда синтаксическая подстановка выбрана, остаётся её применить:

X –корень дерева, компилируемого с помощью механизма вывода

S –подстановка

компилируем S.R с замещением

всех узлов из левых частей S.A на соответствующие правые.

X.code = S.code

X.value = S.value

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

Итоговая схема компиляции

compile(X) =

варианты X

если примитивная конструкция: …

если IR-вставка: …

иначе

запускаем механизм подстановок.  

Управление памятью

В архитектуре x86 есть пара специальных инструкций enter/leave для реализации стековых переменных в высокоуровневых языках. Схема очень проста, поэтому именно её предполагается взять за основу в управлении памятью CSeL в первом приближении.

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

compile(X) =

варианты X

 если {Y}:

вызвать compile(Y) в новой области видимости S

   list = []

   цикл по меткам S (a)

если под a –выделена память, то list.add(a)

вернуть a фабрике.

если list –пусто, то

     X.code = Y.code

иначе

X.code = #enter + Y.code + #free list

 X.value = Y.value

 если

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

Приведённое описание языка –единственное на данный момент.

.5. Пример

Обработка ошибок –пожалуй, самая распространённая подзадача для системного программирования. В подавляющем большинстве современных языков реализован специальный механизм обработки на основе исключений с раскручиванием стека вызовов. Подход довольно трудоёмкий с точки зрения реализации, снижает скорость работы программ по сравнению с анализом кодов ошибок, но код получается на вид простым и компактным. Насколько велики накладные расходы, в точности сложно определить, но обычно речь идёт о процентах. Этого достаточно, чтобы разработчики на C++ отказывались от исключений везде, где важна производительность.

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

Начнём с описания удобной регистрации синтаксических подстановок:

//syntax

{

ir(def pattern ids types replace,

{ir(pattern, replace, ids, types, '_syntax #0 #1 #2 #3')},

(pattern,ids,types,replace),

(0,0,0,0),

   '_syntax #0 #1 #2 #3')

}

Теперь опишем идею на примере:

try

{

do init;

check(status == 'ready');

do work;

check(status == 'done')

}

catch

{

 

}

Блок try регистрирует именованную метку, указывающую на код-обработчик catch. Если условие внутри check не выполнено, происходит переход к обработчику. При вложении блоков try-catch проблем не будет, так как внутренняя регистрация метки скроет внешнюю.

Рассмотрим реализацию:

def (try x catch y)(x,y)(0,0)

{

ir(catch, '_link &0 0');

x;

ir

'

jmp 1

*0 nop

';

y;

ir'*1 nop'

};

def (check x) x 0

{

ir(x; catch;

'

*0 load %0

*1 _label &1

test 0

je 1

')

}

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

Другие примеры кода на CSeL приведены в Приложении 2.

Заключение

В ходе работы на C# .Net Framework 4.0 был разработан компилятор языка, генерирующий промежуточный код, c учётом требований:

  •  Императивность;
  •  Расширяемость синтаксиса за счёт синтаксических подстановок;
  •  Примитив низкоуровневого программирования IR-вставка;
  •  Компактность компилятора: 100Кб исходного кода в 16 файлах;
  •  Эффективность компилятора предполагается, исходя из описания реализаций всех конструкций языка на низкоуровневом IR-языке, на практике не проверена.

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

  •  регистрации типов, переменных и синтаксических подстановок в Си-подобном стиле;
  •  конструкций if, if-else и for-break.

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


Литература

  1.  D. Stewart, S. Jansse. Design and Implementation of XMonad. A Tiling Window Manager // Haskell Workshop 2007.
  2.  J. Paakki. Prolog in practical compiler writing // The Computer Journal, Volume 34 Issue 1, Feb. 1991.
  3.  F. Henderso, T. Conway, Z. Somogyi, D. Jeffery, P. Schacht, S. Taylor, C. Speirs, T. Dowd, R. Becket, M. Brown, P. Wang. The Mercury Language Reference Manual // Version 11.01.
  4.  P.V. Roy, S. Haridi. Concepts, Techniques, and Models of Computer Programming // The MIT Press, February 20, 2004.
  5.  The Computer Languages Benchmarks. http://shootout.alioth.debian.org
  6.  LuaJIT roadmap. http://lua-users.org/lists/lua-l/2008-02/msg00051.html
  7.  M. Poletto. Language and compiler support for dynamic code generation. Ph.D. thesis, MIT, June 1999.
  8.  D. Grossman, M. Hicks, T. Jim, G. Morrisett. Cyclone: A Type-Safe Dialect of C //  C/C++ User’s Journal, January 2005.
  9.  C. Lattner. LLVM 2.0 and Beyond! // Google Tech Talk, Mountain View, CA, July 2007.
  10.  B. Stroustrup. Trends and future of C++: Evolving a systems language by performance // Leganes, Madrid, March 18th and 28th, 2011.
  11.  A. Alexandrescu. The D Programming Language // Addison-Wesley Professional, June 12, 2010.
  12.  http://golang.org/doc/go_spec.html
  13.  Hongwei Xi. The ATS Programming Language. ATS/Anairiats User’s Guide // Working Draft of October 22, 2010.
  14.  K. Skalski. Syntax-extending and type-reflecting macros in an object-oriented language // Master Thesis, University of Wroclaw, 2005.
  15.  http://www.chrisseaton.com/katahdin/katahdin-slides.pdf
  16.  Косенко В.В. Императивный язык программирования с конструируемой семантикой на основе операторного полиморфизма и свободной системы типов для высокопроизводительных вычислений // квалификационная работа на степень бакалавра наук по направлению «Математика. Компьютерные науки» / Екатеринбург, УрГУ, 2009.

ПРИЛОЖЕНИЕ 1

Конфигурация

/proc/cpuinfo

vendor_id

GenuineIntel

cpu family

6

model

23

model name

Intel(R) Xeon(R) CPU           E5430  @ 2.66GHz

stepping

10

cpu MHz

.994

cache size

KB

siblings

1

cpu cores

1

fpu

yes

fpu_exception

yes

cpuid level

13

wp

yes

flags

fpu tsc msr pae mce cx8 apic mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm syscall nx lm constant_tsc up pni monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr dca lahf_lm

bogomips

5509.42

clflush size

64

cache_alignment

64

address sizes

bits physical, 48 bits virtual

/proc/meminfo

MemTotal

637480 kB

компилятор

GCC 4.3.2

“g++ X.cpp -O3 -o Y.out” или “gcc -x objective-c X.m -lobjc -O3 -o Y.out”

Тестовые задачи

Cpp

ObjC

#include <stdlib.h>

class Foo {

public:

int bar(float x){

if (x > 0.5)

return 1;

else

return 0;

}

};

int main() {

Foo* obj = new Foo();

int i = 100000000;

while (i-- > 0)

obj->bar(rand());

return 0;

}

#import <objc/Object.h>

@interface Foo : Object {}

-(int) bar: (float) x;

@end

@implementation Foo

-(int) bar: (float) x {

if (x > 0.5)

return 1;

else

return 0;

}

@end

int main(void) {

Foo *obj = [Foo new];

int i = 100000000;

while( i-- > 0)

[obj bar: rand()];

return 0;

}

Результаты

Метод: 50 запусков каждой из программ, время среднее арифметическое.

Задача

Время real утилиты time, сек

X/C++

Cpp

1.129

1

Objc

1.811

1.6


Приложение 2

Переменные

def (x y)(x,y)(type,0)

{

x; ir(x, y, '*0 _var %0 &1'), x

}

Типы

def (newtype(x,s))(x,s)(0,number)

{

ir(type, x, s,

'

*0 _type %2 &1

*1 _var %0 &1

_store 0 1

')

}

Целые числа

newtype(int,4);

def (x-y)(x,y)(int,int)

{

int z; x; y;

ir(x, y, z,

'

*0 load %0

*1 load %1

*2 sub 0 1

store 2 %2

'),

z

}

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

if

def (if x y)(x,y)(0,0)

{

x;

ir(x,

'

*0 load %0

test 0

je 1

');

y;

ir'*1 nop'

}

if-else

def (if x y else z)(x,y,z)(0,0,0)

{

x;

ir(x,

'

*0 load %0

test 0

je 1

');

y;

ir'jmp 2 *1 nop'; z; ir'*2 nop'

}

for-break

def (`break)(x)(0)

{

ir(break, '*0 _label &0 jmp 0')

};

def (for(a;b;c)d)(a,b,c,d)(0,0,0,0)

{

a; ir'*0 nop';

b;

ir(b, break,

'

*1 load %0

test 1

je 2

_link &1 2

');

d;

c;

ir(for,

'

jmp 0

*2 nop

')

}

1 Трасса – последовательность операций, включая переходы, проверку типов, вызовы методов.

2 Static Single Assignment form – форма записи, при которой значения переменных после первого присвоения не меняются

3 Foreign Function Interface – возможность вызывать код, написанный на другом языке.

4 Используем форму записи из предыдущей работы [16].

5 Шестнадцатеричные коды символов соответствуют US-ASCII.

6 Вопрос о подключении модулей с бинарным или промежуточным представлением пока открыт.

7 IR – Intermediate Representation – промежуточное представление, промежуточный код.

PAGE 1


 

А также другие работы, которые могут Вас заинтересовать

69902. Составление программ на Borland Pascal 93 KB
  Составить программу, выбрав вариант задачи согласно последней цифре шифра. Вывести результаты решения во внешний файл. Вариант 0 Задана матрица A размера 4x4 с вещественными элементами. Найти и вывести на печать все положительные элементы матрицы...
69903. Построение графиков с использованием электронных таблиц 79 KB
  Указание к лабораторной работе №10. В работе необходимо построить график функции с использованием программ Excel или Calc. Основанием для построения графика служат числовые данные, полученных ранее в ходе выполнения лабораторной...
69904. Подготовка схем в системе Visio 146 KB
  Нестандартные фигуры автор рисует с помощью универсального переключаемого через ниспадающее меню инструмента. Затем фигуры соединяются рисованными линиями или автоматически вызовом соединителей и в них впечатывается текст с помощью имеющегося в составе Windows набора шрифтов Fonts.
69905. Работа с командной строкой в ОС MS DOS 93.5 KB
  Цель: Познакомиться с основными принципами управления работой ПК на базе ОС MS DOS изучить основные команды управления ОС MS DOS. Для того чтобы быть полноценной ОС должна как минимум содержать следующие основные компоненты: Файловую систему Драйверы внешних устройств...
69906. Простая выборка данных 99 KB
  Пусть реляционная база данных, состоящая из одной или нескольких таблиц, создана, и произведено подключение к ней. В этом случае типичной практической задачей является получение (извлечение) нужных данных. Например, может потребоваться просто просмотреть все содержимое...
69907. ЕТАПИ ПРОЦЕСУ ПРИЙНЯТТЯ РІШЕНЬ. КОМП’ЮТЕРНА ПІДТРИМКА ЕТАПУ ДІАГНОСТИКИ ПРОБЛЕМИ 150.5 KB
  Цілі виконання завдання: пройти на практиці основні етапи процесу прийняття рішень; отримати навички виявлення та аналізу конкретних виробничих проблем; набути досвіду використання комп’ютерної підтримки яку надає програма Decision Explorer на етапі діагностики проблеми...
69908. Операційна система Windows. Провідник. Текстовий редактор WordPad 2.54 MB
  Однією із найважливіших проблем забезпечення якості програмних засобів являється формалізація характеристик якості і методологія їх оцінки. Для визначення адекватності якості функціонування наявності технічних можливостей програмних засобів до взаємодії удосконаленню і розвитку...
69909. Создание и редактирование документа 4.47 MB
  Цель работы Научиться запускать Microsoft Word, создавать, загружать, сохранять и просматривать документы. Теоретическая часть Запуск Word Запустить Microsoft Word можно одним из следующих способов. С помощью главного меню, выбрав команду Пуск...
69910. Інформаційні технології. Основні поняття та визначення 88 KB
  Поняття інформації є багатозначним тому розглядають різних тлумачення: В кібернетичному розумінні поняття інформації широко використовується в системі керуючого сигналу який передається по лініях зв’язку. Властивості інформації...