На листинге 3 приведен пример объявления интерфейса в TypeScript.

export interface NiaGetDevicesResponseObject {

devices: Array<NiaDeviceInfo>

message: string

success: boolean

error: boolean

failure: boolean

}



Листинг 3: Пример объявления интерфейса в языке программирования TypeScript

2.2.3 Google Protocol Buffers

Google Protocol Buffers - независимый от языка, независимый от используемый платформы, расширяемый механизм для сериализации и десериализации структурированных данных. Разработка сериализаторов и десериализаторов сообщений сводится к описанию сообщений на специальном языке protocol buffer language. На листинге 4 приведено описание одного из сообщений протокола на этом языке.

message GetDevicesRequest {

}

message GetDevicesResponse {

message SuccessResult {

repeated DeviceInfo devices_info = 1;

}

message ErrorResult {

string message = 1;

}

message FailureResult {

string message = 1;

}

oneof result {

SuccessResult success_result = 1;

ErrorResult error_result = 2;

FailureResult failure_result = 3;

}

}



Листинг 4: Пример описания сообщения запроса и ответа на запрос

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

· Protoc - осуществляет генерацию сериализаторов и десериализаторов на языке JavaScript. В дополнение к нему, для генерации деклараций типов для TypeScript использовался плагин ts-protoc-gen [17].

· Для генерации сериализаторов и десериализаторов на языке Rust использовалась библиотека rust-protobuf [18].

2.2.4 Node.js

Node.js - асинхронная, событийно-ориентированная среда выполнения JavaScript кода, основанная на движке V8 веб-браузера Chrome. Платформа представляет набор поставляемых библиотек для разработки серверных приложений вместе с пакетным менеджером npm, состоящим из инструмента командной строки и репозитория содержащего более миллиона различных пакетов.

2.2.5 Vue.js

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

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

Помимо основной библиотеки, экосистема Vue предоставляет следующие средства:

· Vuex - библиотека для хранения состояния приложения. Так же, как и в фреймворке Vue.js, состояние приложение выражается в объекте, изменение состояние которого влечет дальнейшее оповещение, всех подписанных на изменения, компонентов. В Vuex существует пять главных составляющих:

o Состояние - представляет собой хранимое состояние приложения;

o Геттеры - функции, объявленные пользователем, осуществляющие вычисление по входным данных, полученных из объекта состояния;

o Мутаторы - функции, осуществляющие изменение объекта состояния;

o Действия - функции, вызывающие мутаторы. Главное отличие действий - невозможность изменения объекта состояния напрямую и возможность выполнения в асинхронном контексте;

o Модули - средство для разбиения объекта состояния на меньшие. Для каждого из таких объектов состояний могут объявляться свои геттеры, мутаторы, действия и модули. После разбиения объекта состояния на модули, происходит их компоновка в единственный объект состояния.

Vuex позволяет простым образом органично выстроить однонаправленный поток данных: Компоненты -> Действия -> Состояние -> Компоненты.

· Vue router - инструмент для организации маршрутизации для Vue приложений. Под маршрутизацией в данном контексте понимается разбиение приложения на компоненты, каждой из которых соответствует определенный маршрут. Пользователи таких приложений могут свободно перемещаться взад и вперед по истории переходов между маршрутами.

2.2.6 Electron

Electron.js - инструмент для создания кроссплатформенных приложений с использованием JavaScript, HTML и CSS. Инструмент объединяет в себе движок Chromium и среду выполнения Node.js.

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

2.2.7 WebSocket

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

2.2.8 IDE

В качестве интегрированных средств разработки использовались IDE от JetBrains:

· CLion - использовалась для разработки консольного клиента, сервера и интерпретатора;

· WebStorm - использовалась для разработки графического клиента.



Глава 3. Техническая реализация

В данной главе подробно описана архитектура и устройство разработанного приложения.

Исходный код разработанного приложения опубликован на GitHub:

· https://github.com/emirayka/nia_interpreter_core. Содержит в себе разработанный интерпретатор скриптового языка;

· https://github.com/emirayka/nia_events. Содержит в себе библиотеку для обработки событий устройств и графического сервера;

· https://github.com/emirayka/nia_server. Разработанный сервер приложения;

· https://github.com/emirayka/nia_state_machine. Разработанная реализация конечного автомата;

· https://github.com/emirayka/nia-protos. Содержит в себе описание протокола взаимодействия между сервером и клиентами на языке proto3;

· https://github.com/emirayka/nia-protocol-js. Содержит в себе сгенерированные инструментом protoc сериализаторы и десериализаторы сообщений протокола для графического клиента;

· https://github.com/emirayka/nia_protocol_rust. Содержит в себе сгенерированные сериализаторы и десериализаторы сообщений протокола для сервера и консольного клиента;

· https://github.com/emirayka/nia_protocol_rust_generator. Осуществляет генерацию сериализаторов и десериализаторов сообщений на языке Rust с использованием библиотеки protobuf-rust;

· https://github.com/emirayka/nia_front. Содержит в себе графический клиент приложения;

· https://github.com/emirayka/nia_console_client. Содержит в себе консольный клиент приложения;

· https://github.com/emirayka/nia_basic_assertions. Содержит в себе вспомогательные функции для проведения тестирования для серверной части и интерпретатора.

3.1 Архитектура приложения

Приложение разделено на следующие части:

· Интерпретатор;

· Сервер;

· Консольный клиент;

· Графический клиент.

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

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

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

Графический клиент предоставляет графический интерфейс, в котором:

· Выводится информация об устройствах, включающая имя устройства, путь к соответствующему(-им) файлу(-ам) событий, графическую модель устройства, при выделении клавиш которой пользователь, может просматривать те последовательности переназначенных клавиатурных сочетаний, в которых участвует набор выделенных клавиш;

· Предоставляется редактор скриптов, с помощью которого пользователь может создавать новые файлы скриптов, открывать их с диска, сохранять их, закрывать их, передавать их или их части серверу для исполнения;

· Выводит список доступных устройств для осуществления их переназначения.

Интерпретатор состоит из трех частей:

· Парсер;

· Считыватель;

· Вычислитель.

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

Считыватель осуществляет трансляцию иерархической структуры данных во внутреннее представление интерпретатора. Результат трансляции является последовательностью значений интерпретатора.

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

3.2 Скриптовый язык

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



3.2.1 Описание синтаксиса скриптового языка

Язык имеет схожий с языками Lisp-семейства синтаксис, в котором весь код разрабатываемых скриптов состоит из последовательности s-выражений. S-выражение является либо атомом, либо состоит из следующих частей:

· Открывающая скобка;

· Последовательности s-выражений, разделенных пробелами;

· Закрывающая скобка.

Атомами являются последовательности текстовых символов, которые не имеют в себе пробела. Однако, не каждая последовательность символов является корректной в разработанном языке. Так, атом не может содержать не экранированными:

· Текстового символа “'”. Этот символ является отдельным конструктом языка, и, во время разбора кода, раскрывается в отдельную структуру, не являющуюся структурой, описывающей атом языка. На этапе отображения во внутреннее представление интерпретатора, s-выражения, предваренные символом “'”, отображаются в отдельное s-выражение.

· Последовательности текстовых символов “#'”. Эта последовательность также является отдельным конструктом языка, и на этапе отображения, s-выражения, предваренные этими символами, отображаются в отдельное s-выражение;

· Текстовых символов “`” и “,”. Подобно предыдущим двум последовательностям символов, s-выражения, предваренные этими символами, раскрываются в отдельное s-выражение. Эти символы предназначены для облегчения построения списков, и, главным образом используются во время написания макросов.

· Текстовых символов “(“ и “)”, эти текстовые символы используются для обозначения s-выражений, описывающих списки.

· Текстовых символов “{“ и “}”, эти текстовые символы используются для обозначения объектов.

· Текстового символа “””. Этот текстовый символ используется для обозначения строк;

· Текстового символа “\”. Этот текстовый символ используется для экранирования текстовых символов, указанных выше.

Атомы не могут содержать текстового символа “#”, за исключением специально указанных случаев, рассмотренных далее. Этот символ в языке имеет специальное значение.

Атомы подразделяются на следующие типы:

· Атомы целочисленных значений. Эти атомы состоят из последовательности цифр после опционального текстового символа знака - “+” или “-“. Атомы целых чисел должны быть в следующем диапазоне: [-2^63, 2^63 - 1]. Пример: “1”, “234”, “-136”;

· Атомы чисел с плавающей точкой, удовлетворяющих стандарту IEEE 754. Атомы чисел состоят из опционального текстового символа знака, целой части - последовательности цифр, текстового символа “.”, плавающей части - последовательности цифр, опциональной экспоненты - последовательности цифр после текстовых символов “e” или “E” и опционального текстового символа знака - “+” или “-“. Пример: “3.0”, “1.1E+19”;

· Атомы булевых значений. Последовательность символов “#t” представляет значение “Истина”, последовательность текстовых символов “#f” означает значение “Ложь”. Пример: “#t”, “#f”;

· Атомы строк. Состоят из открывающего текстового символа “””, последовательности любых текстовых символов или экранированного текстового символа “””, закрывающего текстового символа “””. Пример: “”string””, “”””;

· Атомы символов. Состоят из последовательности текстовых символов, за исключением неэкранированных текстовых символов “\”, “(“, “)”, “{“, “}”, “,”, “`”, “'”, “ “, “:”, “””, и не удовлетворяющих вышеуказанным правилам. Пример: “symbol”, “dashed-symbol”;

· Атомы ключевых слов. Состоят из текстового символа “:”, последовательности текстовых символов, за исключением неэкранированных текстовых символов “\”, “(“, “)”, “{“, “}”, “,”, “`”, “'”, “ “, “””, и не удовлетворяющих вышеуказанным правилам. Пример: “:keyword”, “::keyword-with-additional-colon”.

Существует группа специальных символов, которые начинаются с текстового символа “#”. На данный момент существует три специальных символа: “#opt”, “#rest”, “#keys”. Они используются для обозначения опциональных аргументов, variadic аргумента и аргументов ключевых слов соответственно во время определения функций.

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

Функции создаются следующими путями:

· Использование специальной формы “function”, которая создает объект функции с заданными аргументами и телом функции;

· Использовании макроса “fn”, который раскрывается в вызов специальной формы “function”;

· Использование синтаксиса сокращенного создания функции. На этапе отображения, происходит трансляция в вызов специальной формы “function”. Пример: “#(+ %1 %2)” эквивалентно “(function (lambda (%1 %2) (+ %1 %2)))”.

· Использование специальных форм “flet”, “flet*”, “mlet”, “mlet*”. Эти специальные формы определяют лексические окружения, в которых они определяют функции с заданными аргументами и телом.

Функции имеют следующие типы аргументов:

· Обычные аргументы;

· Опциональные аргументы;

· Variadic аргумент;

· Аргументы ключевых слов.

Объекты создаются следующими путями:

· Использование литерала объекта. Состоит из открывающей фигурной скобки, последовательности значений и закрывающей фигурной скобки. Последовательность значений состоит из набора пар (ключевое слово, значение) разделенных пробелами. На этапе отображения во внутреннее представление интерпретатора, объектные литералы транслируются в вызов функции “make” объекта “object”. Пример: “{:a 1}”, “{:a 1 :key `symbol}”.

· Использование синтаксиса объекта-паттерна. Литерал объекта-паттерна состоит из текстового символа “#”, открывающей фигурной скобки, последовательности атомов ключевых слов, закрывающей фигурной скобки. На этапе отображения, оно транслируется в вызов функции “make” объекта “object”. Пример: “#{:a :b}” эквивалентно “{:a `a :b `b}”.

· Вызова функций “new”, “make” объекта “object”. Пример: “(object:make :a 1 :b 2}”, “(object:new {})”.

Для того, чтобы облегчить работу с объектами, была добавлена возможность получения значения объекта следующими путем использования специального правила вычисления, которое позволяет напрямую возвращать значение из объекта и устанавливать значение объекта. Пример: “(:key {:key 1})”, “(:key {} 2)”.

Через использование синтаксиса разделенных объектов удобно получать значения вложенных объектов. Он состоит из последовательности символов, разделенных текстовым символом “:”. На этапе отображения, этот синтаксический конструкт раскрывается в s-выражение, использующее правило вычисления, указанное выше. Пример: “a:b:c” эквивалентно “(:c (:b a))”.

3.2.2 Реализация парсера на языке программирования Rust

Для реализации парсера использовался языка программирования Rust.

Использовались следующие примитивные парсеры:

· digit1 - этот парсер возвращает успех, если переданная ему последовательность символов начинается на последовательность цифр. В противном случае, этот парсер возвращает ошибку;

· digit0 - этот парсер возвращает успех, если переданная ему последовательность символов начинается на последовательность цифр. В противном случае, этот парсер возвращает в качестве успеха пустую строку;

· parse_symbol_element - этот парсер возвращает успех, если переданная ему последовательность текстовых символа начинается на валидный элемент символа: валидный экранированный или не экранированный текстовый символ - составляющая символа;

· parse_keyword_element - этот парсер возвращает успех, если переданная ему последовательность текстовых символа начинается на валидный элемент ключевого слова: валидный экранированный или не экранированный текстовый символ - составляющая ключевого слова;

· space0, space1, multispace0, multispace1 - эти парсеры производят разбор пробельных символов.

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

· alt - этот комбинатор принимает набор парсеров и конструирует парсер, последовательно пытающийся применить набор переданных парсеров до тех пор, пока один из них не вернет успех. Если ни один из них не вернул успех, то возвращается ошибка;

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

· map_res - этот комбинатор принимает парсер, возвращающий результат типа A и функцию, принимающую результат типа A, а возвращающую результат типа B. Комбинатор возвращает парсер, возвращающий в результате успеха результат применения переданной функции к результату применения переданного комбинатору парсера;

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

· opt - этот комбинатор принимает парсер, который возвращает парсер, который пытается применить переданный комбинатору парсер к переданной последовательности текстовых символов. Если переданный комбинатору парсер удалось применить, возвращенный парсер возвращает результат применения, в противном случае, парсер возвращает пустую структуру;

· recognize - этот комбинатор принимает парсер, возвращает парсер, который в случае успеха возвращает ту часть переданной ему последовательности символов, разбор которой произошел в процессе вызова переданного комбинатору парсера;

· preceded - этот комбинатор принимает два парсера, возвращает парсер, применяющий первый парсер, затем второй парсер. Сконструированный парсер возвращает результат применения второго парсера, а первого отбрасывает. Если любой из переданных комбинатору парсеров вернул ошибку, возвращается ошибка;

· terminated - этот комбинатор принимает два парсера, возвращает парсер, применяющий первый парсер, затем второй парсер. Сконструированный парсер возвращает результат применения первого парсера, а второго отбрасывает. Если любой из переданных комбинатору парсеров вернул ошибку, возвращается ошибка;

· delimited - этот комбинатор принимает три парсера, возвращает парсер, применяющий первый парсер, затем второй и третий парсеры. Сконструированный парсер возвращает результат применения второго парсера, а первого и третьего отбрасывает. Если любой из переданных комбинатору парсеров вернул ошибку, возвращается ошибка;

· many0 - этот комбинатор принимает парсер, возвращает парсер, который применяет переданный комбинатору парсер до тех пор, пока переданный парсер не вернет ошибку. Сконструированный парсер возвращает агрегированные результаты применения переданного парсера. Если парсер применить не получилось, возвращается пустая последовательность;

· many1 - этот комбинатор принимает парсер, возвращает парсер, который применяет переданный комбинатору парсер до тех пор, пока переданный парсер не вернет ошибку. Сконструированный парсер возвращает агрегированные результаты применения переданного парсера. Если парсер применить не получилось, возвращается ошибка;

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

3.2.2.1 Парсер логических значений

Парсер логических значений приведен на листинге 5.

let parse_boolean = alt((tag("#t"), tag("#f")));

let parse_element = map_res(parse_boolean, make_boolean_element);

Листинг 5: Парсер атомов логических значений

В начале, с использованием комбинатора tag, осуществляется построение парсеров строк “#t” и “#f”. После этого, эти парсеры передаются комбинатору alt.

3.2.2.2 Парсер целочисленных значений

Парсер логических значений приведен на листинге 6.

let parse_plus_sign = tag::<_, _, (&str, ErrorKind)>("+");

let parse_minus_sign = tag::<_, _, (&str, ErrorKind)>("-");

let parse_sign = alt((parse_plus_sign, parse_minus_sign));

let parse_integer = recognize(

pair(

opt(parse_sign),

digit1

)

);

let parse_i64 = map_res(parse_integer, |s: &str| s.parse::<i64>());

let parse_integer_element = map_res(parse_i64, make_integer_element);

Листинг 6: Парсер атомов целочисленных значений

В начале с помощью комбинаторов tag и alt конструируется парсер опционального знака числа. Затем, с помощью комбинаторов recognize, pair, opt и парсера digit1, производится построение парсера, способного производить разбор целочисленного значения, возможно предваренную знаком.

3.2.2.3 Парсер значений чисел с плавающей точкой

Парсер значений чисел с плавающей точкой приведен на листинге 7.



let parse_float = recognize(

tuple((

recognize(pair(opt(alt((tag("-"), tag("+")))),digit1)),

tag("."),

digit1,

opt(complete(pair(

alt((tag("e"), tag("E"))),

recognize(pair(opt(alt((tag("-"), tag("+")))),digit1)),

)))

))

);

let parse_f64 = map_res(parse_float, |s: &str| s.parse::<f64>());

let parse_float_element = map_res(parse_f64, make_float_element);

Листинг 7: Парсер атомов значений чисел с плавающей точкой

Изначально, с помощью комбинаторов recognize, tuple, pair, opt, alt, tag конструируется парсер, возвращающий парсер, способный осуществлять разбор чисел с плавающей точкой.

3.2.2.4 Парсер строк

Парсер строк приведен на листинге 8.

let parse_escaped_character = alt((

map_res::<_, _, _, _, (char, ErrorKind), _, _>(tag("\\\\"), |_| Ok('\\')),

map_res::<_, _, _, _, (char, ErrorKind), _, _>(tag("\\\""), |_| Ok('\"')),

map_res::<_, _, _, _, (char, ErrorKind), _, _>(tag("\\n"), |_| Ok('\n')),

map_res::<_, _, _, _, (char, ErrorKind), _, _>(tag("\\r"), |_| Ok('\r')),

));

let parse_not_escaped_character = none_of::<_, _, (&str, ErrorKind)>(r#"\""#);

let parse_inner_character = alt((parse_escaped_character, parse_not_escaped_character));

let parse_inner_characters = map_res::<_, _, _, _, (&str, ErrorKind), _, _>(

many0(parse_inner_character),

|chars: Vec<char>| Ok(chars.iter().cloned().collect::<String>())

);

let parse_string = delimited(

tag("\""),

parse_inner_characters,

tag("\"")

);

let parse_string_element = map_res(parse_string, make_string_element);

Листинг 8. Парсер атомов строк

Изначально, осуществляется конструирование парсеров экранированных и не экранированных текстовых символов. После этого, с помощью комбинатора alt, осуществляется конструирование парсера элемента строки. После этого, с помощью комбинатора many0, осуществляется построение парсера той части строки, что ограничена текстовым символом “””. После этого, с помощью комбинатора delimited, осуществляется построение парсера строк.

3.2.2.5 Парсер символов

Парсер символов приведен на листинге 9.

let parse_special_symbols = alt((

tag("#opt"),

tag("#rest"),

tag("#keys"),

));

let parse_symbol = alt((

map_res( many1(parse_symbol_character()), join),

map_res(parse_special_symbols, str_to_string)

));

let parse_symbol_element = map_res(parse_symbol, make_symbol_element);

Листинг 9: Парсер атомов символов

В начале конструируется парсер специальных символов “#opt”, “#rest”, “#keys”. После этого конструируется парсер символов.

3.2.2.6 Парсер ключевых слов

Парсер ключевых слов приведен на листинге 10.

let parse_keyword = map_res(

preceded(tag(":"), many1(parse_keyword_character())),

join);

let parse_keyword_element = map_res(parse_keyword, make_keyword_element);

Листинг 10: Парсер ключевых слов

Парсер ключевых слов путем применения комбинатора preceded к парсеру текстового символа “:” и парсеру тела ключевого слова.

3.2.2.7 Парсер литералов объектов

Парсер литералов объектов приведен на листинге 11.

let parse_pairs = many0(pair(

preceded(multispace0, parse_keyword_element),

preceded(multispace0, parse_element)

));

let opening_brace = terminated(tag("{"), multispace0);

let closing_brace = preceded(multispace0, tag("}"));

let parse_object = preceded(

opening_brace,

terminated(

parse_pairs,

closing_brace

)

);

let parse_object_element = map_res(parse_object, make_object_element);

Листинг 11: Парсер литералов объекта

В начале конструируется парсер пар (ключевое слово, элемент), разделенных пробелами. После этого, из прошлого парсера, конструируется новый парсер, игнорирующий текстовые символы “{“, “}” до и после применения прошлого парсера соответственно.

3.2.2.8 Парсер литералов объектов-паттернов

Парсер литералов объектов-паттернов приведен на листинге 12.

let parse_pairs = many0(

preceded(multispace0, parse_keyword_element)

);

let opening_brace = terminated(tag("#{"), multispace0);

let closing_brace = preceded(multispace0, tag("}"));

let parse_object = preceded(

opening_brace,

terminated(

parse_pairs,

closing_brace

)

);

let parse_object_element = map_res(parse_object, make_object_pattern_element);

parse_object_element(s)

Листинг 12: Парсер литералов объектов-паттернов

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

3.2.2.9 Парсер элементов с префиксом

Парсер элементов с префиксом приведен на листинге 13.

let parse_prefix = alt(

(

tag("`"),

tag("'"),

recognize(pair(tag(","), opt(tag("@")))),

tag("#'")

)

);

let parse_prefix = map_res(parse_prefix, make_prefix);

let parse_prefixed = pair(parse_prefix, parse_element);

let parse_prefixed_element = map_res(parse_prefixed, make_prefixed_element);

parse_prefixed_element(s)

Листинг 13: Парсер элементов с префиксом

В начале конструируется парсер альтернатив “'”, “`”, “,”, “,@” и “#'”. Этот парсер называется парсером префикса. Затем, конструируется парсер пары (префикс, элемент).

3.2.2.10 Парсер s-выражений

Парсер s-выражений приведен на листинге 14.

let parse_expressions = many0(preceded(multispace0, parse_element));

let opening_brace = terminated(tag("("), multispace0);

let closing_brace = preceded(multispace0, tag(")"));

let parse_s_expression = preceded(

opening_brace,

terminated(

parse_expressions,

closing_brace

)

);

let parse_s_expression_element = map_res(parse_s_expression, make_s_expression_element);

Листинг 14: Парсер s-выражений

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

3.2.2.11 Парсер объявления сокращенной функции

Парсер сокращенной функции приведен на листинге 15.

let parse_short_lambda = preceded(tag("#"), parse_s_expression_element);

let parse_short_lambda_element = map_res(

parse_short_lambda,

make_short_lambda_element

);



Листинг 15: Парсер объявления сокращенной функции

Парсер сокращенной функции комбинируется применением комбинатора pair к парсеру текстового символа “#” и парсера s-выражений.

3.2.2.12 Парсер синтаксиса разделенных объектов

Парсер синтаксиса разделенных объектов приведен на листинге 16.

let parse_part = preceded(

tag(":"),

parse_symbol_element

);

let parse_delimited_symbols = pair(

parse_symbol_element,

many1(parse_part)

);

let parse_delimited_symbols_element = map_res(

parse_delimited_symbols,

make_delimited_symbols_element

);

Листинг 16: Парсер синтаксиса разделенных объектов

Парсер синтаксиса разделенных объектов составляется путем применения комбинатора pair к:

· Парсеру символа;

· Парсеру последовательностей пар из текстового символа “:” и символа.

3.2.2.13 Парсер элемента

Парсер элемента слишком объемен, поэтому на листинге 17 приведена только его часть.



let s_expression_parser = map_res::<_, _, _, _, (&str, error::ErrorKind), _, _>(

terminated(

s_expression_element::parse_s_expression_element,

alt((

peek(multispace1),

peek(tag(")")),

peek(tag("(")),

peek(tag("}")),

all_consuming(tag(""))

))),

|el| Ok(Element::SExpression(el))

);

let parser = alt((

boolean_parser,

short_lambda_parser,

object_pattern_parser,

float_parser,

int_parser,

string_parser,

keyword_parser,

s_expression_parser,

object_parser,

prefix_parser,

symbol_parser,

delimited_parser,

));



Листинг 17: Часть парсера элемента

Парсер элемента состоит из двух частей:

· Построение из ранее определенных парсеров, парсеров, способных игнорировать пробелы и правильно разбирать отдельные элементы внутри s-выражений и литералов объектов;

· Комбинация всех ранее созданных парсеров с помощью комбинатора alt.

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

3.3 Интерпретатор

3.3.1 Типы данных

В интерпретаторе существуют следующие типы данных:

· Целочисленный тип. Значениями этого типа являются 64-битные числа со знаком;

· Тип чисел с плавающей точкой. Значения этого типа 64-битные числа с плавающей точкой;

· Тип логических значений. Значения этого типа являются либо значение “Истина”, либо значением “Ложь”;

· Тип строк. Значения этого типа являются валидные строки из символов кодировки UTF-8;

· Тип ключевых слов. Этот тип состоит из значений, которые имеют имя;

· Тип символов. Этот тип состоит из значений, которые имеют имя и идентификатор символа;

· Тип cons ячеек. Этот тип состоит из упорядоченных пар значений, иногда называемых cons-ячейками, или списками. Первое значение пары называется “car”, второе значение пары называется “cdr”;

· Тип объектов. Этот тип представляет значения, которые в себе содержат последовательность пар (символ, значение);

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

3.3.2 Функции

В интерпретаторе существуют 4 типа функций:

· Интерпретируемые функции. Состоят из тройки (лексическое окружение, сигнатура аргументов и тело функции - массив значений);

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

· Макросы. Состоят из тройки (лексическое окружение, сигнатура аргументов и тело функции - массив значений). Ключевое отличие макросов от интерпретируемых функций - последующее вычисление результатов первого вычисления макроса;

· Специальные формы. Являются обертками функций, написанных на языке Rust.

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

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

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

Аргументы интерпретируемых функций и макросов делятся на 4 категории:

· Обязательные аргументы. Представляют собой аргументы, наличие которых для вызова функции обязательно. Если передано аргументов меньше количества обязательных аргументов, возвращается ошибка. Например, функция “(fn (a b c) (list:new a b c))” имеет три обязательных аргумента, и, если она будет вызвана с количеством аргументов не равным трем, возвращается ошибка;

· Опциональные аргументы. Представляют собой аргументы, наличие которых для вызова функции не обязательно. Например, функция “(fn (a #opt b c) (list:new a b c))” имеет один обязательный аргумент и два опциональных. Функция может быть вызвана с количеством аргументов равным 1, 2 или 3;

· Variadic аргумент. Представляет собой аргумент переменной длины. Например, функция “(fn (a #rest b) (cons a b))” может быть вызвана с одним или более аргументами;

· Аргументы ключевых слов. Представляют собой именованные аргументы. Каждый аргумент ключевых слов предваряется ключевым словом - именем аргумента. При вызове функции могут передаваться только объявленные аргументы ключевых слов. Один аргумент ключевых слов не может использоваться дважды. Например, функция “(defn fun (a #keys b c) (list:new a b c))” может быть вызвана одним из следующих способов: “(fun 1)”, “(fun :a 1)”, “(fun :b 2)”, “(fun :a 1 :b 2)” или “(fun :b 2 :a 1)”.

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

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

· Аргументы ключевых слов после опциональных аргументов;

· Обязательные аргументы после variadic аргумента;

· Опциональные аргументы после variadic аргумента;

· Variadic аргумент после variadic аргумента;

· Аргументы ключевых слов после variadic аргумента;

· Variadic аргумента после аргументов ключевых слов;

· Опциональные аргументы после аргументов ключевых слов.

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

· “(fn (#opt (a 2) (b 3)) (+ a b))” - функция принимает два опциональных аргумента, по умолчанию равных “2” и “3” соответственно.

· “(fn (#keys (a 1 a?) (b 2 b?)) (+ a b))” - функция принимает два аргумента ключевых слов, равных по умолчанию “1” и “2” соответственно. В лексическом окружении, которое создается во время вызова функции, также задаются переменные “a?” и “b?”, принимающих значение “#t” если соответствующие им аргументы были переданы в функцию.

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



3.3.3 Внутреннее устройство

Поскольку, Rust запрещает наличие в коде циклических ссылок, а наличие циклических зависимостей ссылок необходимо, несколько решений существует:

· Использование структур стандартной библиотеки Rust, таких как Rc, RefCell и Weak, которые позволяют компилировать код, содержащий циклические ссылки;

· Использование паттерна Arena.

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

· Значительно усложняется код внутреннего представление интерпретатора;

· Усложняется поддержка кода;

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

По этим причинам, было решено использовать паттерн Arena, в котором:

· Все значения хранятся в коллекции;

· Коллекцией владеет только один объект;

· Для получения и изменения объектов, необходимо иметь указатель на него - целое число, по которому можно получить ссылку на значение;

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

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

Существуют следующие правила вычисления:

· Значения типов, отличных от Cons ячеек и символов, вычисляются в себя самих;

· Символ вычисляется в значение переменной ближайшего лексического окружения, в которой вычисляется символ;

· Значения Cons ячеек вычисляются следующим образом:

o В текущем лексическом окружении, агрегируются все car значения всех cdr значений;

o Если car значение текущей Cons ячейки есть символ, то берется значение функции этого символа из ближайшего лексического окружения. Если такого лексического окружения нет, возвращается ошибка. Затем, функция вызывается с агрегированными ранее аргументами;

o В противном случае, вычисляется car значение текущей ячейки, и:

§ Если вычисленное значение есть функция, то она вызывается с агрегированными ранее аргументами;

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

Примеры:

· Результат вычисления целого числа 1 есть целое число 1;

· Результат вычисления числа с плавающей точкой 1.1 есть плавающее число с точкой 1.1;

· Результат вычисления значений “Истина” и “Ложь”, есть значения “Истина” и “Ложь” соответственно;

· Результат вычисления строки “123” есть строка “123”;

· Результат вычисления ключевого слова :keyword есть ключевое слово :keyword;

· Результат вычисления “(let ((a 1)) a)” есть целое число 1;

· Результат вычисления объекта {:a 1} есть объект {:a 1};

· Результат вычисления функции #(+ %1 %2) есть сама функция #(+ %1 %2);

· Результат вычисления (cons 1 2) есть упорядоченная пара из целых значений 1 и 2;

· Результат вычисления (:key {:key 2}) есть целое число 2;

· Результат вычисления (:key {:key 2} 3) есть 3. В результате вычисления, значение объекта, связанное с символом key становится равным трем;

· Результат вычисления (if #t 1 2) есть целое число 1;

· Результат вычисления ((function (macro () (list:new `list:new 1)))) есть целое число 1.

3.3.4 Реализация на языке Rust

В данном разделе описываются основные структуры интерпретатора.

Структура, представляющая значение интерпретатора приведена на листинге 18.

pub enum Value {

Integer(i64),

Float(f64),

Boolean(bool),

Keyword(KeywordId),

Symbol(SymbolId),

String(StringId),

Cons(ConsId),

Object(ObjectId),

Function(FunctionId),

}

Листинг 18. Структура Value

Эта структура является перечислением из 9 типов:

· Целое число. Представляет собой целое 64-битное число со знаком;

· Число с плавающей точкой. Представляет собой 64-битное число с плавающей точкой;

· Логическое значение. Представляет собой логическое значение;

· Ключевое слово. Является идентификатором ключевого слова в арене ключевых слов;

· Символ. Является идентификатором символа в арене ключевых слов;

· Строка. Является идентификатором строки в арене строк;

· Упорядоченная пара. Является идентификатором упорядоченной пары в арене упорядоченных пар;

· Объект. Является идентификатором объекта в арене объектов;

· Функция. Является идентификатором функции в арене функций.

Использование такого представления позволило:

· Прозрачно реализовать передачу значений в аргументы функций по ссылке;

· Позволило реализовать trait Copy для значений - из-за того, что количество байт на хранение информации, заложенной в перечислении Value, не превышает 8 байт, затраты на копирование значений перечисления сравнимы с затратами на копирование 64 битных чисел;

· Упростить процесс сборки мусора. Поскольку все значения, которые могут оказаться недоступными, теперь сосредоточены в аренах, проверка того, является ли объект недоступным сводится к обходу значений, хранящихся в аренах;

Лексические окружения представлены структурой LexicalEnvironment, приведенной в листинге 19:

pub struct EnvironmentValueWrapper {

value: Value,

flags: u8,

}

pub struct LexicalEnvironment {

variables: HashMap<SymbolId, EnvironmentValueWrapper>,

functions: HashMap<SymbolId, EnvironmentValueWrapper>,

parent: Option<EnvironmentId>,

}

Листинг 19. Структуры LexicalEnvironmentWrapper и LexicalEnvironment

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

· Если установлен флаг 0x1, то это означает, что данное значение может быть возвращено из лексического окружения;

· Если установлен флаг 0x2, то это означает, что данное значение может быть изменено в лексическом окружении;

· Если установлен флаг 0x80, то это означает, что флаги данного значения могут быть изменены.

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

Структура LexicalEnvironment состоит из:

· Поля variables - последовательности пар (идентификатор символа в арене символов, значения типа EnvironmentValueWrapper). Это поле хранит значения переменных данного лексического окружения;

· Поля functions - последовательности пар (идентификатор символа в арене символов, значения типа EnvironmentValueWrapper). Это поле хранит значения функций данного лексического окружения;

· Поля parent - являющегося ссылкой на родителя данного лексического окружения. Оно установлено для всех лексических окружений, кроме глобального лексического окружения. Ссылка является идентификатором лексического окружения в арене лексических окружений.

Объекты представлены структурами ObjectValueWrapper и Object, приведенными на листинге 20.

· pub struct ObjectValueWrapper {

· value: Value,

· flags: u8,

· }

· pub struct Object {

· properties: HashMap<SymbolId, ObjectValueWrapper>,

· prototype: Option<ObjectId>,

· frozen: bool,

· }

Листинг 20. Структуры ObjectValueWrapper, Object

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

· Установка флага 0x1 означает, что значение свойство может быть возвращено из объекта;

· Установка флага 0x2 означает, что значение свойства может быть изменено;

· Установка флага 0x4 означает, что свойство может участвовать в перечислении;

· Установка флага 0x80 означает, что флаги свойства могут быть изменены.

Структура Object состоит из:

· Поля properties - последовательности пар (идентификатор символа в арене символов, значения типа ObjectValueWrapper);

· Поля prototype, которая хранит идентификатор прототипа объекта в арене объектов, если прототип установлен;

· Поля frozen, которое, в случае его установки в значение истины, запрещает любые манипуляции со свойствами и ссылкой на прототип объекта.

Ошибки представлены структурой Error и перечислением ErrorKind, которые представлены на листинге 21.

pub enum ErrorKind {

Failure,

ParseError,

GenericError,

GenericExecution,

Overflow,

ZeroDivision,

InvalidCons,

InvalidArgument,

InvalidArgumentCount,

Assertion,

Break,

Continue,

}

pub struct Error {

error_kind: ErrorKind,

message: String,

caused_by: Option<Box<Error>>,

symbol_name: String,

}

Листинг 21. Структура Error и перечисление ErrorKind

Структура Error состоит из:

· Поля error_kind, хранящую тип ошибки;

· Поля message, хранящую описания ошибки;

· Поля caused_by, хранящую опциональную причину ошибки;

· Поля symbol_name, хранящую имя символа, зарегистрированного для ошибки. Идентификатор символа в арене здесь использоваться не должен, поскольку объекты ошибок не являются значениями интерпретатора. Это поле используется преимущественно в специальных формах try и throw.

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

Вариант ErrorKind::ParseError означает, что данная ошибка возникла во время произведения разбора кода парсером.

Вариант ErrorKind::Break и ErrorKind::Continue означают, что во время выполнения циклов, произошло преждевременное завершения цикла и текущей итерации цикла соответственно.

Вариант ErrorKind::Assertion означает, что возникла ошибка во время проверки инварианты во время выполнения встроенной функции assert.

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

Функции представляются перечислением Function, представленной на листинге 22.

pub type BuiltinFunctionType = fn(

interpreter: &mut Interpreter,

environment: EnvironmentId,

argument_values: Vec<Value>

) -> Result<Value, Error>;

pub type SpecialFormFunctionType = fn(

interpreter: &mut Interpreter,

environment: EnvironmentId,

argument_values: Vec<Value>

) -> Result<Value, Error>;

pub struct BuiltinFunction {

func: BuiltinFunctionType,

}

pub struct InterpretedFunction {

environment: EnvironmentId,

arguments: Arguments,

code: Vec<Value>,

}

pub struct MacroFunction {

environment: EnvironmentId,

arguments: Arguments,

code: Vec<Value>,

}

pub struct SpecialFormFunction {

func: SpecialFormFunctionType,

}

pub enum Function {

Builtin(BuiltinFunction),

Interpreted(InterpretedFunction),

Macro(MacroFunction),

SpecialForm(SpecialFormFunction),

}

Листинг 22. Перечисление Function и структуры BuiltinFunction, InterpretedFunction, MacroFunction, SpecialFormFunction

Существуют 4 альтернативы:

· Builtin, представляющая встроенную функцию. Ей соответствует структура BuiltinFunction. Значения типа BuiltinFunction являются обертками над функциями сигнатуры BuiltInFunctionType;

· Interpreted, представляющая встроенную функцию. Ей соответствует структура InterpretedFunction;

· Macro, представляющая встроенную функцию. Ей соответствует структура MacroFunction;

· SpecialForm, представляющая встроенную функцию. Ей соответствует структура SpecialFormFunction. Значения типа SpecialFormFunction являются обертками над функциями сигнатуры SpecialFormFunctionType.

Значения типов BuiltInFunctionType и SpecialFormFunctionType являются функциями, которые принимают:

· Мутабельную ссылку на объект интерпретатора;

· Идентификатор лексического окружения, в которой были вызваны эти функции;

· Набора аргументов, с которыми были вызваны эти функции.

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

· Идентификатора лексического окружения, в котором функция была создана;

· Значения структуры Arguments, описывающей аргументы функции;

· Последовательности значений интерпретатора - кода функции или макроса.

Пример арены, арена функций, приведена на листинге 23.

pub struct FunctionId {

id: usize,

}

pub struct FunctionArena {

arena: HashMap<FunctionId, Function>,

next_id: usize,

}

Листинг 23. Структуры FunctionId и FunctionArena

Значения типа FunctionId являются простыми 4-х или 8-ми байтными (в зависимости от архитектуры системы) целыми числами.

Тип Function уже был описан ранее.

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

В интерпретаторе предусмотрена возможность загрузки кода в виде модулей с использованием специальных форм import и export. Структура, используемая для хранения содержимого модулей приведена на листинге 24.

pub struct Module {

path: String,

environment_id: EnvironmentId,

exports: HashMap<SymbolId, Value>,

default_export: Option<Value>,

}

Листинг 24. Структуры FunctionId и FunctionArena

Структура Module имеет вид:

· Поле path, хранящая абсолютный путь к файлу модуля. Гарантируется, что один и тот же модуль не может быть загружен более одного раза. Если модуль с заданным путем уже был загружен, во время произведения импорта экспортируемых значений модуля используется ранее загруженный модуль;

· Поле environment_id, хранящее идентификатор лексического окружения, в котором было исполнено содержимое модуля;

· Поле exports, хранящее именованные экспортируемые значения модуля;

· Поле default_export, хранящее экспортируемое значение по умолчанию.

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