[0001] The Aber Programming Language _____________________________________________________________ Язык программирования, представляющий обширные возможности по выводу данных, имеющий мульти-этапную систему сборки с "часоморфизмом", представляющий каждое выражение набором символов. Поток: ~Amchik/aber * The Aber Programming Language ...................... [0001] * Аннотация ........................................ [0002] * Основные принципы .................................. [0003] * Синтаксис .......................................... [0004] * Aber SIL ........................................... [0005] * Используемые упрощения ........................... [0006] * Получение Aber SIL из AST ........................ [0007] * Aber Intermediate Language ......................... [0008] * Ссылки и используемая литература ................... [0009] 09 December 2024 Revision 1a --[0002] Аннотация ------------------------------------------ Изначально "язык" представлял собой шутку. Александр Иванович, автор синтаксиса, заявлял о невероятных возможностях, которыми будет обладать Aber, но лишь недавно язык получил официальный репозиторий[1] с реализацией. На момент написания данного документа, Aber может только парсить числа. Этот документ описывает моё видение языка Aber, и соответственно, мою реализацию. Далее под языком Aber будет подразумеваться моя реализация и эта спецификация. Если это необходимо, я буду явно ссылаться на оригинального автора. Язык писался с попыткой реализовать спецификацию Андрея[2], но быстро выяснилось, что документ не имеет под собой никакого практического смысла. Отсюда вытекают странные решения в плане синтаксиса и алгоритма компиляции (в частности, Aber SIL). Так как спецификация почти ничего не описывает, стоит отметить, что лишь [0004] Синтаксис был ею вдохновлён, что не отменяет проделаную мной работу по его тестированию, исправлению и документированию. Остальные части данной спецификации не имеют отношения к трудам Андрея Ивановича. Пересмотр "1a" является косметическим исправлением пересмотра "1", в котором были изменены краткое описание и секция [0002] Аннотация. [0003] Основные принципы _____________________________________________________________ Язык Aber представляет собой крайне общий способ представления сущностей, таких как алгоритмы и данные. Синтаксис языка определяет почти весь язык, и без дополнительных инструментов Aber является языком разметки. Сначала разберём части компиляции и интерпретации, зависящие лишь от спецификации Aber. Компилятор преобразует код на языке Aber в промежуточный код, представленный символами второго рода, иначе говоря, в структуру данных. Такая структура данных затем может быть использована напрямую, например как конфигурационный формат, или быть преобразована дальше. Работа компилятора может быть описана следующими шагами: 1. Чтение кода, разбиение его на лексемы (лексер). 2. Парсинг лексем: получение синтаксического дерева. 3. Парсинг дерева: получение из синтаксического дерева команд (структур данных, символов первого рода). Результатом этого этапа является Aber Simplified Intermediate Language (Aber SIL). 4. Проверка на корректность и первичная оптимизация. На этом моменте проверяются правильность передаваемых аргументов в символы первого рода, а также разрешаются некоторые символьные структуры. Под разрешением подразумевается упрощение выражений (eg. Call[Integer[42]] -> Integer[42]) и подстановка значений вместо неизвестных символов. 5. Преобразование оптимизированного Aber SIL в более общий Aber IL (Aber Intermediate Language). После выполнение последнего (5го) действия, компилятор может выдать полученный код, либо по данным дополнительным входным данным начать его исполнять. Структура Aber IL будет рассмотрена в главе [0008], но Aber IL не является основным объектом этого документа. [0004] Синтаксис _____________________________________________________________ Под документом будем подразумевать один файл на языке Aber. Принимаем, что обычно, код на Aber имеет расширение ".aber". Синтаксически, документ представляет собой массив выражений, в котором важен порядок. Формально: DOCUMENT := { EXPRESSION ';' }; Определение выражению будет дано ближе к концу этой главы. Дополнительно уточним, что наличие и количество пробелов, табов (\t) и новых линий (\n или \r) учитывается в синтаксисе (за исключением комментариев). Такие символы могут разделять литералы и лексемы, но они будут влиять, если будут стоять внутри литерала. Например, "42 51" и "4251" это разный код, а "42.foo" и "42 . foo" один и тот же. Все числа в Aber синтаксически можно записать только в base10 При этом между цифрами могут стоять знаки "_" (но числа не могут на них начинаться). Определим DIGIT как цифра от 0 до 9 включительно. Формально, целые числа (INTEGER) и числа с плавающей запятой (FLOAT) записываются так: INTEGER := DIGIT { DIGIT | "_" }; FLOAT := DIGIT { DIGIT | "_" } "." { DIGIT | "_" }; Дополнительно, все литералы не должны выходить за более, чем одну строку. По понятным причинам, для INTEGER и FLOAT это невозможно по определению, но это важно для символа (CHAR) и строки (STRING). CHAR или STRING могут состоять лишь из символов UTF-8. Все символы из (UTF-8), кроме ', " и \, будем называть UNESCAPED_CHAR. Синтаксически, "\" можно ставить перед теми же символами, что и позволяет стандарт C89, и дополнительно перед "e". Теперь определим формально: ESCAPED_CHAR := "\" ( DIGIT | "a" | "b" | "t" | "n" | "t" | "v" | "f" | "r" | "\"" | "'" | "\\" | "e" ); CHAR := "'" ( UNESCAPED_CHAR | ESCAPED_CHAR ) "'"; STRING := '"' { UNESCAPED_CHAR | ESCAPED_CHAR } '"'; Замечание: ESCAPED_CHAR раскрывается лишь при получении AST. Цифры от 0 до 9 будут раскрыты в соответствующие байтовые значения, символ "e" в 27ой символ ASCII. Для остальных символов смотрите man ascii(7). Теперь, можно формально определить, что такое литерал: LITERAL := INTEGER | FLOAT | CHAR | STRING; Идентификатором (IDENT) мы будем называть выражение, не содержащее пробелов, табов и новых линий. IDENT не может содержать следующие символы: [ ()[]{}/@.,=;:"'\ ]. IDENT не может начинаться на [ - ] или цифру. Выражения [ - ] и [ / ] являются IDENT как исключение. Заметим, что [ - ] это IDENT, но [ -foo ] нет. В языке большинство выражений является вызовом. Определим их типы: 1. Прозрачный. Прозрачный вызов это либо литерал, либо идентификатор. Самый простой тип. 2. Шаблонный (generic). После прозрачного вызова в квадратных скобках будут идти аргументы шаблона, разделённые запятой. Должен быть хотя бы один аргумент. 3. Кортеж (tuple). Набор выражений, разделённых запятой, в круглых скобках. Может не быть выражений вовсе, тогда кортеж будет выглядеть так: (). 4. Блок. Перечисление выражений в фигурных скобках, через ';' Формально, все типы, и вызов, записываются следующим образом: CALL_TRANSPARENT := (IDENT | LITERAL); CALL_GENERIC := (IDENT | LITERAL) "[" EXPRESSION { "," EXPRESSION } [","] "]"; CALL_TUPLE := "(" [ EXPRESSION { "," EXPRESSION } "," ] ")"; CALL_BLOCK := "{" { EXPRESSION ";" } "}"; CALL := (CALL_TRANSPARENT | CALL_GENERIC | CALL_TUPLE | CALL_BLOCK); Определим тип единицы выражения, EXPR_UNIT. В частном случае, это просто символ "=". В остальных, EXPR_UNIT определяется как способ вызова: 1. Единичный. Это обычный вызов, т.е. CALL. 2. Метод. Вызов выражения как метод чего-либо, определяется как CALL "." EXPR_UNIT. 3. Путь. Аналогичен методу, но вызывается через "::". Формально, EXPR_UNIT определяется так: EXPR_UNIT_C := ( CALL | CALL "." EXPR_UNIT_C | CALL "::" EXPR_UNIT_C ); EXPR_UNIT := ( EXPR_UNIT_C | "=" ); Само выражение (синтаксически) состоит из EXPR_UNIT: EXPRESSION := { [ "@" ] EXPR_UNIT [ ":" ] }; Хотя, уже на этапе перевода AST в SIL, есть некоторое ограничение по нему. Например, все функции в Aber принимают либо 1 аргумент, либо вообще не принимают аргументов. Важно отметить, что хоть такое определение выражение и позволяет писать сколь угодно много присвоений (знак "="), но SIL допускает лишь одно присвоение в строке. Таким образом, можно выделить более правильное определение: +--[draft]------------------------------------------------+ | | | EXPRESSION_VALUE := { [ "@" ] EXPR_UNIT_C [ ":" ] }; | | EXPRESSION_ASSIGN := EXPR_UNIT_C "=" EXPRESSION_VALUE; | | EXPRESSION := (EXPRESSION_VALUE | EXPRESSION_ASSIGN); | | | +---------------------------------------------------------+ Тут также описано, что перед и после "=" нельзя поставить "@" или ":". Текущая реализация пока лишь частично использует альтернативное определение в построении синтаксического дерева. При этом, если выражение не будет соответствовать альтернативному определению, то оно скорее всего вызовет ошибку при построении или выполнении Aber SIL. Немного добавим смысла символам "@" и ":". Первый символ (negate) используется для взятия значения литерала, вместо его вызова. Как было ранее обговорено, в Aber литералы по умолчанию вызываются. Это инвертированный синтаксис, где нужно убирать вызов, вместо того, чтобы его проставлять, как в остальных языках. При парсинге в AST, выражения с "@" называются negated. При парсинге в Aber SIL все выражения, что не были negated, оборачиваются в Call[...]. Ниже представлен пример, сравнивающий код на Aber и код на Python: +--[example.aber]------------+--[example.py]--------------+ | | | | foo bar; | foo( bar() ) | | foo @bar; | foo( bar ) | | | | +----------------------------+----------------------------+ Символ ":" используется для оборота в пару (Pair). Не смотря на название, пара содержит лишь одно выражение. Пара может быть использована для превращения литерала в вызываемый объект. Ниже приведён пример, как можно использовать пару для функции определения других функций: +--[add.aber]---------------------------------------------+ | | | define-function[@shift] n: { | | return n .+ 1; | | }; | | | | define-function[@add] (a, b): { | | return a .+ b; | | }; | | | +---------------------------------------------------------+ Небольшое пояснение к коду: функция "define-function" вызывается с шаблонным аргументом "@shift". "shift" это идентификатор, и для того, чтобы он не вызывался, нужно поставить "@" перед ним. Тогда, в Aber SIL, аргументом будет UnknownSymbol["shift"], вместо Call[UnknownSymbol[...]] Далее, этой функции передаётся аргументом следующее выражение представляющее собой пару n (Pair[UnknownSymbol["n"]]), которая вызывается с аргументом { ... }. Внутри блока, функция return вызывается с аргументом, получаемым как вызов метода "+" у "n" с аргументом "1". Ниже приведён аналог первого выражения на языка Python: +--[add.py]-----------------------------------------------+ | | | n = Literal() | | define_function( Pair(n)(Block([ | | return( n["+"](1) ), | | ])) ) | | | +---------------------------------------------------------+ [0005] Aber SIL _____________________________________________________________ Aber Simplified Intermediate Language (Aber SIL) это язык, или формат данных, предшествующий Aber IL. Aber Intermediate Language представляет собой единое символьное выражение, обычно начинающиеся блоком, в аргументы которого передаются другие символы. Aber SIL имеет упрощённое понимание, что такое символ, а также имеет лишь ограниченное их количество. В Aber IL, символ это объект, содержащий некоторые данные, и имеющий некоторый набор эффектов, а также правил оптимизации. Это довольно общий объект, поэтому ниже мы будем говорить только об упрощённом поминании символа, который есть в Aber SIL. Для начала, определим примитивный символ. Примитивный символ, это один из следующих символов: 1. Integer. Число, signed 64bit integer. 2. Float. Число, float64. 3. Char. Символ в UTF-8 (16 бит). 4. String. Строка. 5. UnknownSymbol. Идентификатор, внутри представляет из себя строку. Примитивный символ знает свой тип, и данные, которые в него вложены. Иными словами, имея примитивный символ, мы может сказать его тип и получить из него данные. Заметим, что тип примитивного символа и тип данных это разные вещи, так как String и UnknownSymbol имеют одинаковый тип данных, но являются разными типами. Символ в Aber SIL это один из следующих символов, наделённый данными (сами данные также могут являться другими символами), а также знающий свой тип: 1. Любой примитивный символ, Primitive. 2. Generic. Шаблон, отнесённый к примитивному символу и имеющий хотя бы один аргумент символом. Условно, определяется как Generic[Primitive, Symbol...]. 3. Pair. Пара, аргументом имеет символ. Определяется как Pair[Symbol]. Пример: Pair[Integer[42]]. 4. Set. Символ, принимающий аргументами два символа. Является оператором присвоения. Опр.: Set[Symbol, Symbol]. 5. Tuple. Кортеж, может быть пустым, или содержать неограниченное количество символов. Опр.: Tuple[] или Tuple[Symbol...]. Примеры: Tuple[], Tuple[Integer[1], String["foo"]]. 6. Method. Вызывает у первого аргумента метод, представленный вторым аргументом. Опр.: Method[Symbol, Symbol]. Пример: Method[Integer[-42], UnknownSymbol["abs"]] 7. Path. Аналогичен Method, вызывает по пути. Опр.: Path[Symbol, Symbol] 8. Block. Блок, или набор символов. Принимает 0 или несколько аргументов. Опр.: Block[] или Block[Symbol...]. Весь документ также является блоком. 9. Call. Вызывает другой символ. Может передать дополнительный аргумент. В отличии от самого Aber, в Aber SIL сам по себе символ не вызывается, а выражение без Call (если это не Set) не содержит в себе смысла. Опр.: Call[Symbol] или Call[Symbol, Symbol] Пример: Выражение UnknownSymbol["exit"] само по себе ничего не делает, но если обернуть его в Call[...], то при доходе до этого выражения и выполнения его программа может завершиться (аналогично вызову функции exit() в Py). Ситуация без Call[...] будет аналогичная (_ = exit) в Python (без вызова функции). Символами первого рода называются символы из Aber SIL. --[0006] Используемые упрощения ----------------------------- В Aber SIL по умолчанию используются некоторые оптимизации, сокращающие количество символов, или раскрывающие их. Например, Set[UnknownSymbol["foo"], Integer[42]] после оптимизации заменяет все UnknownSymbol["foo"] в блоке на Integer[42]. При этом, если больше в блоке (включая вложенные блоки) нет UnknownSymbol["foo"], и это разрешено, символ Set пропадёт из блока. Ниже будут рассмотрены все базовые оптимизации, которые сделает Aber. 1. Set[...]: Если первым аргументом передан UnknownSymbol, а вторым любой примитивный символ, то все символы, соответствующие первому аргументу, заменяются на второй символ. 2. Tuple[...]: Если в Tuple был передан лишь один аргумент, то выражение Tuple[b] заменяется на b. 3. Block[...]: Если в Block не было передано ни одного аргумента, то он заменяется на Tuple[]. 4. Call[...]: Если в Call был передан лишь один аргумент, и этим аргументом является любой примитивный символ P, кроме UnknownSymbol, то Call[P] заменяется на P. Список используемых упрощений может быть дополнен компилятором, при предоставлении пользователем дополнительных правил. Например, упрощения могут зависеть от значений символов. Данный список упрощений может быть изменён в зависимости от ревизии документа. При ссылке на упрощения (1-4) используйте номер ревизии документа. Одна ревизия соответствует одному набору правил упрощения. --[0007] Получение Aber SIL из AST -------------------------- Так как AST состоит из выражений, их и будем рассматривать. Сами наборы выражений, то есть блоки и документ, преобразуются в символ Block[...]. В Aber SIL есть всего одно большое выражение: символ Block, в который передаются аргументы. Выражения разбиваются на два типа: обычные и присвоение. Рассмотрим присвоения: первым аргументом ожидается примитивный символ. Обычно, это UnknownSymbol, то есть идентификатор, хотя это не является правилом. Заметим, что даже если идентификатор не был negated, он всё равно не должен оборачиваться в Call[...]. Выражение, идущее после знака "=", должно передаваться как второй аргумент. При этом в второго выражения важно, является ли оно negated. Например, "a = b" должно преобразовываться в "Set[UnknownSymbol["a"], Call[UnknownSymbol["b"]]]". Чтобы избежать вызова, и присвоить UnknownSymbol, нужно добавить "@": "a = @b". Обычные (значимые) выражения преобразуются циклично: если выражение задано единицами (A, B, C, ...), то берётся первая единица A и ставится первым аргументом Call[...]. Второй аргумент вычисляется как выражение (B, C, ...). Если выражение задано всего одной единицей, то Call берётся всего с одним аргументом. Если единица выражения M является negated, то оно не оборачивается в Call[...], а передаётся как второй аргумент. В таком случае M должно оказаться последним, в противном случае компилятор должен выдавать ошибку. Первая единица A также может быть negated, в таком случае всё выражение должно состоять лишь из единицы A: (A). Если единица выражения оказывается вызовом метода, или пути тогда единица (lhs, rhs) преобразуется в Method[LHS, RHS] или Path[LHS, RHS], соответственно. Если единица выражения оказалась единичным вызовом, то она парсится в зависимости от типа своего вызова: 1. Прозрачный. В примитивный символ. 2. Generic (шаблонный). Оборачивается в Generic[...], первым аргументом идёт примитив, последующими преобразованные выражения. 3. Tuple (кортеж). Оборачивается в Tuple[...], где аргументы это преобразованные выражения. 4. Block (блок). Оборачивается в Block[...], где аргументы это преобразованные выражения. [0008] Aber Intermediate Language _____________________________________________________________ Данная глава будет достаточно общей, и не описывать конкретной реализации, по двум причинам: на момент написания документа компилятор ещё не дошёл до преобразования в Aber IL и сам язык является конечной точкой, с которой самое общее представление языка Aber уже не работает. Aber Intermediate Language (Aber IL) представляет собой набор символьных выражений, образующих структуру данных. Символьные выражения состоят из символов, которые содержат другие символы. Символ это набор данных, метаданных, эффектов и правил упрощения. Данные символа - это прямые данные, которые передаются символу через его аргументы. Данными могут быть строки, числа, числа с плавающей запятой, и символы. Метаданные это некоторые набор внутренних данных, которые не определяются явно. При этом, метаданные могут быть общими для всех символов разом, для всех символов в определённом символе (т.е. для всех символах, находящихся в данных другого символа), или быть доступны только одному символу. Эффект символа это некоторая внешняя функция, которая может манипулировать с данными, метаданными и другими эффектами символа. Результатом эффекта может быть изменение самого символа и данных в нём. Символом второго рода называются символы из Aber IL. Эффекты привязаны к этапам прохода. Каждое исполнение Aber IL происходит при определённом этапе. По определению, Stage 0 (нулевой этап), это оптимизации Aber SIL. На каждом следующем этапе могут быть загружены дополнительные данные. Этап считается разрешённым, если не осталось символов с эффектами, соответствующими текущему этапу. Загрузка данных подразумевает изменение общих для всех символов метаданных, а также замена некоторых UnknownSymbol[..] на другие символы. Как пример, рассмотрим выдуманный символ DebugStr[...], принимающий несколько аргументов. DebugStr[Integer[1]] это символ. Его данные это набор (Integer[1]). Допустим, что Stage 2 - это интерпретация программы. Тогда, на Stage 2, если в общих метаданных написано, что сейчас идёт отладка, то эффектом DebugStr будет написать в консоль "Integer[1]", и преобразоваться в Integer[1]. Второй пример, это ResolveOnStageOr[...], первым аргументом принимающий номер этапа, на котором он выдаёт 3тий аргумент если второй аргумент это UnknownSymbol. ResolveOnStageOr[3, UnknownSymbol["v"], Integer[42]] имеет данные (3, UnknownSymbol["v"], Integer[42]). Эффектом на втором этапе будет проверить, чем является второй аргумент, и если он не UnknownSymbol, то замениться на него. Правила замены определяются пользователем, подключением внешних библиотек, либо модификацией параметров компиляции. Для языка программирования предлагаются следующие этапы: ЭТАП | ОПИСАНИЕ ---------+------------------------------------------------ Stage 0 | Базовые оптимизации, выполняемые на Aber SIL Stage 1 | Подключение базовой стандартной библиотеки, | выполнение арифметики, работа с данными и т.д. Stage 2 | Подключение расширенной стандартной библиотеки, | позволяющей работать с системой (например, с | файлами). Stage 3 | Подключение пользовательских библиотек. Stage 4 | Исполнение программы, либо преобразование Aber | IR в другой формат данных или код (например, | LLVM IR) [0009] Ссылки и используемая литература _____________________________________________________________ [1] Репозиторий с реализацией основных возможностей языка Aber по его спецификации[2]. / ~Hedgehogo/aber-core URL: https://github.com/Hedgehogo/aber-core Commit SHA256: 7d60ba506b594108d09f0639c41ce986069e64e6 [2] Спецификация языка Aber. / ~Hedgehogo URL: https://github.com/Hedgehogo/aber.io Commit SHA256: d13557b43bd8717b57fa93d5302362df46f4f928