Введение
Примерно год назад я писал язык программирования под названием ALLang. Расшифровка его звучит так: Another LISP Language, что незамысловато даёт понимание его второсортности. Тем не менее, таковой язык всё же предлагает интересные особенности в своей реализации со стороны эзотерических языков. Писал я ALLang исключительно по фану. Но начнём мы пожалуй по порядку с его высокоуровневых особенностей и будем постепенно углубляться вниз, в самую его крамешную бездну эзотерического внутреннего выполнения.
Внешние особенности
Язык программирования ALLang выглядит как обычный язык LISP диалекта Scheme. При этом язык ALLang является чисто функциональным языком программирования. У него не существует операций ввода/вывода, переменных, циклов и т.п. вещей связанных как-либо с императивными языками.
В языке ALLang существует три основных ключевых слова, описывающих инструкции: include, define, if. Инструкция include содержит ещё два ключевых слова assembly и source. В сумме ALLang содержит пять ключевых слов.
; Подгружаем точку входа (include assembly lib/vms/init.vms) ; Подгружаем библиотеки с операциями ; <, -, + и ret (include source lib/all/lr.all lib/all/ret.all lib/all/dec.all lib/all/mul.all) ; Вычисляем факториал от x (define (main x) (fact x)) ; f(x) = 1, if x < 1 ; f(x) = x * f(x-1) (define (fact x) (if (lr x 1) (ret 1) (mul x (fact (dec x)))))
Результат исполнения при x = 5:
{ "result": [120], "return": 0 }
В сравнении с языками LISP диалекта Scheme здесь есть некоторые "тонкости". Во-первых, существует два типа библиотек - assembly и source. Первый тип библиотеки подгружает низкоуровневые детали исполнения язык��, которые могут модифицировать язык как угодно, добавляя всеразличные операции. Второй тип подгружает код написанный уже на языке ALLang, собственно является типичным способом импортирования кода.
Если мы посмотрим в код lib/vms/init.vms, то увидим просто точку начала исполнения в виде функции main, хоть и в виде ассемблерного кода (о котором мы поговорим позднее).
labl _init push main call hlt
Библиотеки типа source мы оставим напоследок. Сейчас же давайте посмотрим "узкие" места языка программирования. Во-первых, язык действительно не обладает никакими операциями ввода и вывода, сам язык - это чистый алгоритм и не более. Алгоритму на вход поступают аргументы (в функцию main), а на выходе код возвращает результат выполнения. Во-вторых, язык работает исключительно с числами типа int32, он не знает что такое int8, string, struct, list и т.п. В общем он крайне примитивен. В-третьих, у него нет ни переменных, ни циклов. Всю цикличность он производит через рекурсию, а таковая рекурсия неоптимизирована! Это было сделано исключительно для того, чтобы сохранить уже приобретённую примитивность языка, но о таковой ещё будет разговор на низком уровне разбора языка.
Таким образом, язык крайне плох в практическом своём применении, но с другой стороны его особенность подгрузки ассемблерного кода может кардинально его изменить, в том числе добавив некоторые типы, циклы и т.п. Иными словами, сам язык можно рассматривать как конструктор для развлечения программиста.
Внутренние особенности
Язык программирования ALLang базируется на самописной стековой виртуальной машине CVM. Таковая виртуальная машина достаточно гибка и не менее примитивна, в сравнении с языком ALLang. Она принимает на вход свой ассемблерный код и преобразует его в машинный код (байткод) для своего исполнения.
Основные инструкции CVM изображены в следующей таблице.
Bytecode | Stack | Args | Instruction |
0x0A | 0 | 1 | push |
0x0B | 1 | 0 | pop |
0x0C | 1 | 0 | inc |
0x0D | 1 | 0 | dec |
0x0E | 3 | 0 | jg |
0x0F | 3 | 0 | je |
0x1A | 1 | 0 | jmp |
0x2A | 2 | 0 | stor |
0x3A | 1 | 0 | load |
0x4A | 1 | 0 | call |
0x5A | 0 | 0 | hlt |
Компиляция языка ALLang выполняется в несколько этапов:
Компиляция. Происходит преобразование высокоуровневого кода в код языка ассемблера для виртуальной машины CVM.
Трансляция. Происходит преобразование ассемблерного кода в машинный код (байткод) виртуальной машиной CVM.
Исполнение. Виртуальная машина CVM начинает исполнять байткод.
Такое же можно описать просто в виде интерфейсных функций:
extern int all_compile(FILE *output, FILE *input); extern int cvm_compile(FILE *output, FILE *input); extern int cvm_load(uint8_t *memory, int32_t msize); extern int cvm_run(int32_t **output, int32_t *input);
Следовательно, виртуальная машина CVM никак не привязана к языку ALLang и может самостоятельно исполнять другие коды, которые просто были написаны на её ассемблерном диалекте. Как пример:
labl _start push begin jmp ; main labl begin ; mul5(x) = x * 5 ; where x = 10 push 10 push mul5 call push end jmp ; exit labl end hlt ; x = arg[1] labl mul5 ; y = x * 5 push -2 load push 5 mul ; x = y push -1 push -3 stor ; return pop jmp
Результат исполнения выглядит так:
{ "result": [50], "return": 0 }
Кто более внимательный, тот обнаружит, что CVM выполнила инструкцию mul, хотя таковой не было представлено в списке инструкций. Суть заключается в том, что помимо основных инструкций, благодаря которым в теории (в теории) можно выполнить всё, таковая виртуальная машина также предоставляет более практические инструкции, которые изображены в следующей таблице.
Bytecode | Stack | Args | Instruction |
0xA0 | 2 | 0 | add |
0xB0 | 2 | 0 | sub |
0xC0 | 2 | 0 | mul |
0xD0 | 2 | 0 | div |
0xE0 | 2 | 0 | mod |
0xF0 | 2 | 0 | shr |
0xA1 | 2 | 0 | shl |
0xB1 | 2 | 0 | xor |
0xC1 | 2 | 0 | and |
0xD1 | 2 | 0 | or |
0xE1 | 1 | 0 | not |
0xF1 | 3 | 0 | jl |
0xA2 | 3 | 0 | jne |
0xB2 | 3 | 0 | jle |
0xC2 | 3 | 0 | jge |
0xD2 | 1 | 0 | allc |
И вот здесь начинается самая интересная часть связанная с языком ALLang. Таковой язык программирования базируется исключительно на основных операциях виртуальной машины CVM. Это значит, что любое сложение он выполняет через множество рекурсивных операций инкрементирования. Любое умножение выполняет через множество рекурсивных операций сложения и т.д. В этом истинная ужасность данного языка и одновременно его красота. Можно сказать, что таковой язык придерживается "втупую" аксиомы Пеано каждый раз, когда ему необходимо что-либо сделать.
Именно по этой причине, если мы скажем ALLang вычислить факториал с x = 6, он просто рухнет из-за того, что стек виртуальной машины будет переполнен.
{ "error": "run byte code", "return": 7 }
Зная это, мы теперь можем посмотреть как его внутреннию ужасную компиляцию в язык ассемблера, так и его библиотечные функции.
Код вычисления факториала на языке ассемблера после компиляции ALLang
labl _init push main call hlt labl _eq push -3 load push -3 load push _if_eq je labl _else_eq push 0 push _end_eq jmp labl _if_eq push 1 labl _end_eq push -1 push -4 stor pop jmp labl _inc push -2 load inc push -1 push -3 stor pop jmp labl inc push -2 load push -1 load push _inc call push -1 push -4 stor pop pop jmp labl _dec push -2 load dec push -1 push -3 stor pop jmp labl dec push -2 load push -1 load push _dec call push -1 push -4 stor pop pop jmp labl ret push -2 load push -1 load push inc call push dec call push -1 push -4 stor pop pop jmp labl not push -2 load push -1 load push 0 push _eq call pop push 0 push _else_0 je labl _if_0 push 1 push ret call push _end_0 jmp labl _else_0 push 0 push ret call labl _end_0 push -1 push -4 stor pop pop jmp labl _gr push -3 load push -3 load push _if_gr jg labl _else_gr push 0 push _end_gr jmp labl _if_gr push 1 labl _end_gr push -1 push -4 stor pop jmp labl neq push -3 load push -3 load push -2 load push -2 load push _eq call pop push not call push -1 push -6 stor pop pop pop jmp labl or push -3 load push -3 load push -2 load push 0 push neq call pop push 0 push _else_1 je labl _if_1 push 1 push ret call push _end_1 jmp labl _else_1 push -1 load push 0 push neq call pop push 0 push _else_2 je labl _if_2 push 1 push ret call push _end_2 jmp labl _else_2 push 0 push ret call labl _end_2 labl _end_1 push -1 push -6 stor pop pop pop jmp labl ge push -3 load push -3 load push -2 load push -2 load push _eq call pop push -3 load push -3 load push _gr call pop push or call pop push -1 push -6 stor pop pop pop jmp labl lr push -3 load push -3 load push -2 load push -2 load push ge call pop push not call push -1 push -6 stor pop pop pop jmp labl eq push -3 load push -3 load push -2 load push -2 load push _eq call pop push -1 push -6 stor pop pop pop jmp labl add push -3 load push -3 load push -1 load push 0 push eq call pop push 0 push _else_3 je labl _if_3 push -2 load push ret call push _end_3 jmp labl _else_3 push -1 load push 0 push lr call pop push 0 push _else_4 je labl _if_4 push -2 load push -2 load push inc call push add call pop push dec call push _end_4 jmp labl _else_4 push -2 load push -2 load push dec call push add call pop push inc call labl _end_4 labl _end_3 push -1 push -6 stor pop pop pop jmp labl sub push -3 load push -3 load push -1 load push 0 push eq call pop push 0 push _else_5 je labl _if_5 push -2 load push ret call push _end_5 jmp labl _else_5 push -1 load push 0 push lr call pop push 0 push _else_6 je labl _if_6 push -2 load push -2 load push inc call push sub call pop push inc call push _end_6 jmp labl _else_6 push -2 load push -2 load push dec call push sub call pop push dec call labl _end_6 labl _end_5 push -1 push -6 stor pop pop pop jmp labl neg push -2 load push 0 push -2 load push sub call pop push -1 push -4 stor pop pop jmp labl abs push -2 load push -1 load push 0 push lr call pop push 0 push _else_7 je labl _if_7 push -1 load push neg call push _end_7 jmp labl _else_7 push -1 load push ret call labl _end_7 push -1 push -4 stor pop pop jmp labl and push -3 load push -3 load push -2 load push 0 push neq call pop push 0 push _else_8 je labl _if_8 push -1 load push 0 push neq call pop push 0 push _else_9 je labl _if_9 push 1 push ret call push _end_9 jmp labl _else_9 push 0 push ret call labl _end_9 push _end_8 jmp labl _else_8 push 0 push ret call labl _end_8 push -1 push -6 stor pop pop pop jmp labl xor push -3 load push -3 load push -2 load push not call push -2 load push and call pop push -3 load push -3 load push not call push and call pop push or call pop push -1 push -6 stor pop pop pop jmp labl mul push -3 load push -3 load push -2 load push 0 push lr call pop push -2 load push 0 push lr call pop push xor call pop push 0 push _else_10 je labl _if_10 push -2 load push abs call push -2 load push abs call push mul call pop push neg call push _end_10 jmp labl _else_10 push -1 load push 0 push eq call pop push 0 push _else_11 je labl _if_11 push 0 push ret call push _end_11 jmp labl _else_11 push -2 load push abs call push -3 load push abs call push -3 load push abs call push dec call push mul call pop push add call pop labl _end_11 labl _end_10 push -1 push -6 stor pop pop pop jmp labl main push -2 load push 2 push -2 load push fact call push mul call pop push -1 push -4 stor pop pop jmp labl fact push -2 load push -1 load push 1 push lr call pop push 0 push _else_12 je labl _if_12 push 1 push ret call push _end_12 jmp labl _else_12 push -1 load push -2 load push dec call push fact call push mul call pop labl _end_12 push -1 push -4 stor pop pop jmp
*Код факториала мог выглядить куда более миниатюрным, если бы использовались добавочные (а не основные) функции виртуальной машины, и если бы не использовалась везде и постоянно рекурсия.
labl begin push 10 push fact call push end jmp labl end hlt ; A <- fact(A) labl fact ; B <- A push -2 load labl _fact_for ; IF B < 2 push -1 load push 2 push _fact_end jl ; B <- B - 1 push -1 load push 1 sub push -1 push -2 stor pop ; A <- A * B push -3 load push -2 load mul push -1 push -4 stor pop push _fact_for jmp labl _fact_end ; return pop jmp
Библиотечные функции
Теперь посмотрим некоторые реализации библиотечных функций, разберём assembly и source типы. Начнём пожалуй с assembly, директория lib/vms.
Библиотека типа assembly добавляет обёрточные функции над инструкциями виртуальной машины CVM с целью, чтобы язык ALLang мог ими пользоваться. Как пример, операция inc.
labl _inc push -2 load inc push -1 push -3 stor pop jmp
В данном случае, labl _inc - это определение имени функции и таковую мы действительно можем вызвать из ALLang, если импортируем таковую библиотеку прямо или косвенно (как пример через высокоуровневые функции inc, add и т.д.).
Операции push -2 и load подгружают переменную из аргумента функции, далее при помощи операции inc создаётся новая переменная, к которой прибавляется единица. При помощи операций push -1, push -3, stor результат инкрементирования перемещается обратно в принимаемый аргумент. Операция pop удаляет созданную переменную. Операция jmp перепрыгивает обратно на точку вызова функции labl _inc. В общем по такому шаблону создаются и другие низкоуровневые функции для языка ALLang.
Примеры никзоуровневых функция для языка ALLang
Функция декремента:
labl _dec push -2 load dec push -1 push -3 stor pop jmp
Функция сравнения двух чисел (==):
labl _eq push -3 load push -3 load push _if_eq je labl _else_eq push 0 push _end_eq jmp labl _if_eq push 1 labl _end_eq push -1 push -4 stor pop jmp
Функция сравнения двух чисел (>):
labl _gr push -3 load push -3 load push _if_gr jg labl _else_gr push 0 push _end_gr jmp labl _if_gr push 1 labl _end_gr push -1 push -4 stor pop jmp
В нашем контексте я привёл лишь четыре низкоуровневых функций и один код связанный с инициализацией функции main. На самом деле этого вполне достаточно, но могут существовать также функции, которые будут нечистыми со стороны функционального программирования. Например, виртуальная машина позволяет вводить несколько аргументов и получать несколько результатов. В нашем же случае мы можем принимать несколько аргументов, но выводим всегда одно число. Мы можем легко исправить данный случай просто написав функции _get (для игнорирования аргументов и взятия их по адресу) и _set (для сохранения результатов):
(include assembly lib/vms/init.vms lib/vms/set.vms lib/vms/get.vms) (include source lib/all/lr.all lib/all/ret.all lib/all/dec.all lib/all/mul.all) ; arg[2] <- _set(arg[0], fact(arg[1])) = 0 (define (var1) (ret 1)) ; arg[1] (define (var0) (ret 0)) ; arg[0] <- fact(arg[1]) ; args: 2 1 0 ; input: [0, 5, 0] ; output: [0, 5, 120] (define (main) (_set (var0) (fact (_get (var1))))) ; f(x) = 1, if x < 1 ; f(x) = x * f(x-1) (define (fact x) (if (lr x 1) (ret 1) (mul x (fact (dec x)))))
Результат исполнения:
{ "result": [0,5,120], "return": 0 }
Низкоуровневые функции _get и _set
Функция _set:
labl _set push -3 load push -3 load push -1 push -3 load stor push 0 push -1 push -6 stor pop pop pop jmp
Функция _get:
labl _get push -2 load load push -1 push -3 stor pop jmp
Вышеописанный код показывает, что мы можем в буквальном смысле модифицировать язык ALLang налету, изменяя его же правила. Тем не менее, показанный код наверное не очень хорош в том плане, что он всё же "грязнит" чистую функциональность языка.
Теперь давайте приступим к рассмотрению высокоуровневых функций языка ALLang, которые находятся в директории lib/all. Таковых функций я написал достаточно большое количество, но давайте разберём лишь несколько.
Наверное самыми основными функциями являются функции инкрементирования и декрементирования, но уже в виде высокоуровневых примитивов. Как пример, функция inc:
(include assembly lib/vms/inc.vms) ; inc(x) = x + 1 (define (inc x) (_inc x))
Здесь происходит обычное импортирование низкоуровневой функции и её последующая обёртка. Ровно такая же ситуация с функциями dec, eq, gr.
Иногда есть необходимость использовать не функцию eq, а обратную ей функцию. В таком случае нужно лишь выполнить операцию eq и применить к ней операцию not. Также оно и работает в ALLang.
(include source lib/all/eq.all lib/all/not.all) ; neq(x, y) = 0, if x = y ; neq(x, y) = 1 (define (neq x y) (not (eq x y)))
Функция not
Функция not:
(include source lib/all/eq.all lib/all/ret.all) ; not(x) = 1, if x = 0 ; not(x) = 0 (define (not x) (if (eq x 0) (ret 1) (ret 0)))
Функция ret:
(include source lib/all/inc.all lib/all/dec.all) ; ret(x) = x (define (ret x) (dec (inc x)))
Далее, операция сложения может быть представлена как её рекурсивное применение операции с операцией инкрементирования.
(include source lib/all/inc.all lib/all/dec.all lib/all/eq.all lib/all/ret.all lib/all/lr.all) ; add(x, y) = x, if y = 0 ; add(x, y) = add(x, y+1) - 1, if y < 0 ; add(x, y) = add(x, y-1) + 1 (define (add x y) (if (eq y 0) (ret x) (if (lr y 0) (dec (add x (inc y))) (inc (add x (dec y))))))
И ещё несколько подобных функций
Функция умножения:
(include source lib/all/add.all lib/all/dec.all lib/all/eq.all lib/all/abs.all lib/all/neg.all lib/all/xor.all lib/all/ret.all lib/all/lr.all) ; mul(x, y) = -mul(|x|, |y|), if x < 0 xor y < 0 = 1 ; mul(x, y) = 0, if y = 0 ; mul(x, y) = |x| + mul(|x|, |y| - 1) (define (mul x y) (if (xor (lr x 0) (lr y 0)) (neg (mul (abs x) (abs y))) (if (eq y 0) (ret 0) (add (abs x) (mul (abs x) (dec (abs y)))))))
Функция вычитания:
(include source lib/all/inc.all lib/all/dec.all lib/all/eq.all lib/all/ret.all lib/all/lr.all) ; sub(x, y) = x, if y = 0 ; sub(x, y) = sub(x, y+1) + 1 ; sub(x, y) = sub(x, y-1) - 1 (define (sub x y) (if (eq y 0) (ret x) (if (lr y 0) (inc (sub x (inc y))) (dec (sub x (dec y))))))
Функция деления:
(include source lib/all/sub.all lib/all/inc.all lib/all/abs.all lib/all/ret.all lib/all/lr.all lib/all/xor.all lib/all/neg.all) ; div(x, y) = -div(|x|, |y|), if x < 0 xor y < 0 = 1 ; div(x, y) = 0, if |x| < |y| ; div(x, y) = div(|x| - |y|, |y|) + 1 (define (div x y) (if (xor (lr x 0) (lr y 0)) (neg (div (abs x) (abs y))) (if (lr (abs x) (abs y)) (ret 0) (inc (div (sub (abs x) (abs y)) (abs y))))))
Функция abs:
(include source lib/all/neg.all lib/all/ret.all lib/all/lr.all) ; abs(x) = -x, if x < 0 ; abs(x) = x (define (abs x) (if (lr x 0) (neg x) (ret x)))
Функция neg:
(include source lib/all/sub.all) ; neg(x) = -x (define (neg x) (sub 0 x))
Далее логические функции представляются следующим образом:
(include source lib/all/ret.all lib/all/neq.all) ; and(x, y) = 1, if x = 1, y = 1 ; and(x, y) = 0 (define (and x y) (if (neq x 0) (if (neq y 0) (ret 1) (ret 0)) (ret 0)))
И ещё несколько функций
Функция not:
(include source lib/all/eq.all lib/all/ret.all) ; not(x) = 1, if x = 0 ; not(x) = 0 (define (not x) (if (eq x 0) (ret 1) (ret 0)))
Функция or:
(include source lib/all/ret.all lib/all/neq.all) ; or(x, y) = 0, if x = 0, y = 0 ; or(x, y) = 1 (define (or x y) (if (neq x 0) (ret 1) (if (neq y 0) (ret 1) (ret 0))))
Функция xor:
(include source lib/all/and.all lib/all/or.all lib/all/not.all) ; xor(x, y) = (~x and y) or (x and ~y) (define (xor x y) (or (and (not x) y) (and x (not y))))
В результате, мы буквально восстанавливаем все базовые функции с нуля, которые в других языках программирования представляются как по умолчанию (логично, ведь кому в здравом уме захочется писать собственные функции сложения, умножения и т.д.). Данные "конструкторы" становятся возможными лишь из природы языка ALLang, когда таковой сильно привязан к языку ассемблера виртуальной машины CVM (аналогии на самом деле существуют и в нормальных языках, подобия языка Си).
Заключение
Сам ALLang и виртуальная машина CVM написаны на языке Си. Кому интересно, весь исходный код ALLang'a вы можете посмотреть тут, а код CVM тут. Что там, что там находится малое количество кода.
Чтобы проверить выполнение ALLang, можно воспользоваться следующей инструкцией:
make install # Скачивает и компилирует CVM make build # Компилирует код ALLang в язык ассемблера make run # CVM транслирует ассемблерный код в байткод и исполняет его # Последние две инструкции можно заменить просто как make make # Последовательное выполнение build и run
Как вы увидели, сам язык программирования является более эзотерическим языком, нежели реально применимым. Тем не менее, его интересно�� особенностью является лёгкая "кастомизация", при помощи которой можно буквально модифицировать язык посредством ассемблерного кода, добавляя всё больше новых операций. Другой, не менее интересной особенностью, является ужасное его выполнение при котором большинство операций вычисляются через множество вызовов inc и dec в рекурсивном исполнении (из-за чего стек виртуальной машины от такой наглости перестаёт наполняться). Ну и последним интересным пунктом является его чистая функциональность и примитивность исполнения, что в настоящее время уже редко где можно встретить. Поэтому язык является по своей сути бесполезным и красиво ужасным (а может и ужасно красивым).
