Бесполезный и красиво ужасный язык программирования ALLang

Введение

Примерно год назад я писал язык программирования под названием 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 изображены в следующей таблице.

Компиляция языка ALLang выполняется в несколько этапов:

1. Компиляция. Происходит преобразование высокоуровневого кода в код языка ассемблера для виртуальной машины CVM.

2. Трансляция. Происходит преобразование ассемблерного кода в машинный код (байткод) виртуальной машиной CVM.

3. Исполнение. Виртуальная машина 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, хотя таковой не было представлено в списке инструкций. Суть заключается в том, что помимо основных инструкций, благодаря которым в теории (в теории) можно выполнить всё, таковая виртуальная машина также предоставляет более практические инструкции, которые изображены в следующей таблице.

И вот здесь начинается самая интересная часть связанная с языком ALLang. Таковой язык программирования базируется исключительно на основных операциях виртуальной машины CVM. Это значит, что любое сложение он выполняет через множество рекурсивных операций инкрементирования. Любое умножение выполняет через множество рекурсивных операций сложения и т.д. В этом истинная ужасность данного языка и одновременно его красота. Можно сказать, что таковой язык придерживается "втупую" аксиомы Пеано каждый раз, когда ему необходимо что-либо сделать.

Именно по этой причине, если мы скажем ALLang вычислить факториал с x = 6, он просто рухнет из-за того, что стек виртуальной машины будет переполнен.

{
	"error": "run byte code",
	"return": 7
}

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

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.

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
}

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

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)))

(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)))

(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))))))

(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)))

(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)))

(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)))

(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))))

(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 в рекурсивном исполнении (из-за чего стек виртуальной машины от такой наглости перестаёт наполняться). Ну и последним интересным пунктом является его чистая функциональность и примитивность исполнения, что в настоящее время уже редко где можно встретить. Поэтому язык является по своей сути бесполезным и красиво ужасным (а может и ужасно красивым).