Хабрахабр

Язык программирования, рассчитанный на минификацию

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

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

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

Но даже так большинство существующих языков не предназначены для данной оптимизации — очевидно, они имеют множество элементов, которые нужны для понимания человеку, а не машине. А что, если разработать язык, специально рассчитанный на минификацию?

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

Я решил провести эксперимент — сделать прототип языка и посмотреть, что из этого выйдет.

Ключевые особенности

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

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

Функциональную парадигму — потому что она более выразительна (позволяет меньшим объёмом кода выразить больше алгоритмов).

На двух остальных остановлюсь подробнее.

Отсутствие разделителей

Рассмотрим следующий код:

add(2, multiple(2, 2))

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

add 2 multiple 2 2

Точно так же можно поступить и с операторами, просто считая их функциями:

+ 2 * 2 2

При этом операторам не требуется иметь приоритет — порядок действий задаётся порядком записи, так как для вызова функции сначала требуется вычислить все её параметры. Так выражение выше вернёт значение 8. А чтобы получить 6, код потребуется записать так:

* 2 + 2 2

Классы идентификаторов

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

А затем мне пришла идея разделить все идентификаторы на два класса: буквенные и пунктуационные.

Дело в том, что в любом языке идентификаторы необходимо чем-то разделять — либо другими элементами синтаксиса, либо пробельными символами. Иначе будет неоднозначность: xy — это идентификатор xy или два идентификатора x и y?

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

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

Для примера возьмём такое выражение:

foo($(5))

На моём языке его можно записать следующим образом:

foo$5

Решение проблем

В процессе разработки языка возникло несколько интересных проблем, которых я не ожидал, но всё-таки смог решить: вызов функций без аргументов и построение структуры кода (AST).

Вызов функций без аргументов

Так как для вызова функции у меня нет специального синтаксиса, как в других языках, функции без аргументов должны вызываться простым указанием их имени:

fn answer() 42
; answer

Так оно и работало, но только на одном уровне вложенности. Что, если такая функция вернёт ещё одну такую же?

fn answer() fn() 42 ;
; answer

Тогда результатом будет замыкание, а не внутреннее значение. И как вызвать это замыкание? Ведь его имя мы уже и так указали.

Пришлось использовать подход из языка Clojure — trampoline: любые значения после их вычисления попадают в специальный цикл, который циклически вызывает замыкания, не требующие аргументов, до тех пор, пока результатом не будет что-то иное. Таким образом результатом второго примера выше так же будет 42, как и в первом.

Построение структуры кода

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

И когда мы знаем число аргументов всех функций, это несложно. Например, код:

add 2 multiple 2 2

Имеет следующую структуру:

Однако, как только я начинаю возвращать замыкания, появляется неоднозначность:

fn add(x y) + x y
; fn increase(x) + x 1
; fn foo(n) if == n 2 add increase
; foo x ...

Сколько надо передать аргументов результату вызова функции foo? Это возможно определить только во время исполнения кода, но никак не на стадии его разбора. И это делает невозможным осуществление минификации.

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

fn make_adder(bias):2 fn(x y) + bias + x y ;
; make_adder 1 2 2

В определении функции make_adder явно указано, что её результат является замыканием и ожидает два параметра. Поэтому легко построить структуру последнего вызова:

Общие возможности

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

Язык имеет набор встроенных функций: базовые математические функции и операции (в том числе для битовой арифметики), функции для работы со списками и хеш-таблицами, базовый ввод-вывод.

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

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

Бенчмарк

Для оценки возможностей минификации я решил сравнить свой язык с JavaScript. Для этого я написал одну и ту же программу на обоих.

В качестве задачи выбрал алгоритм сравнения деревьев Virtual DOM. За основу взял эти статьи:

  1. How to write your own Virtual DOM.
  2. Write your Virtual DOM 2: Props & Events.

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

Версия на JavaScript

function make_node(type, properties, ...children) { return { 'type': type, 'properties': properties || {}, 'children': children, }
} function make_difference(path, action, ...parameters) { return { 'path': path, 'action': action, 'parameters': parameters, }
} function is_different(node_1, node_2) { return typeof node_1 !== typeof node_2 || (typeof node_1 === 'object' ? node_1['type'] !== node_2['type'] : node_1 !== node_2)
} function compare_property(path, name, old_value, new_value) { let difference if (!new_value) { difference = make_difference(path, 'remove_property', name) } else if (!old_value || new_value !== old_value) { difference = make_difference(path, 'set_property', name, new_value) } return difference
} function compare_properties(path, old_properties, new_properties) { const properties = Object.assign({}, old_properties, new_properties) return Object.keys(properties) .map(name => compare_property(path, name, old_properties[name], new_properties[name])) .filter(difference => difference)
} function compare_nodes(old_node, new_node, index=0, path=[]) { let differences = [] if (!old_node) { differences.push(make_difference(path, 'create', new_node)) } else if (!new_node) { differences.push(make_difference(path, 'remove', index)) } else if (is_different(old_node, new_node)) { differences.push(make_difference(path, 'replace', index, new_node)) } else if (old_node['type']) { const child_path = [...path, old_node['type']] const properties_differences = compare_properties(child_path, old_node['properties'], new_node['properties']) differences.push(...properties_differences) const maximal_children_length = Math.max(old_node['children'].length, new_node['children'].length) for (let i = 0; i < maximal_children_length; i++) { const child_differences = compare_nodes(old_node['children'][i], new_node['children'][i], i, child_path) differences.push(...child_differences) } } return differences
} module['exports'] = { 'make_node': make_node, 'compare_nodes': compare_nodes,
}

Версия на моём языке

let map:2 load "std/list/map";
let filter:2 load "std/list/filter";
let zip_longest:3 load "std/list/zip_longest";
let reduce:3 load "std/list/reduce"; fn make_node(kind properties children) #"type" kind #"properties" properties #"children" children
{}; fn make_difference(path action parameters) #"path" path #"action" action #"parameters" parameters
{}; fn is_different(node_i node_ii) || != type node_i type node_ii fn() if == "hash" type node_i fn() != ."type"node_i ."type"node_ii; fn() != node_i node_ii; ;
; fn compare_property(path name old_value new_value) if !new_value fn() make_difference path "remove_property" ,name[]; fn() if || !old_value != new_value old_value fn() make_difference path "set_property" ,name,new_value[]; fn() nil; ;
; fn compare_properties(path old_properties new_properties) let properties + old_properties new_properties; let differences map keys properties fn(name) compare_property path name .name old_properties .name new_properties ;; filter differences fn(difference) difference ;
; fn compare_nodes(old_node new_node index path) if !old_node fn() , make_difference path "create" ,new_node[] []; fn() if !new_node fn() , make_difference path "remove" ,index[] []; fn() if is_different old_node new_node fn() , make_difference path "replace" ,index,new_node[] []; fn() if == "hash" type old_node fn() let child_path + path , ."type"old_node []; let properties_differences compare_properties child_path ."properties"old_node ."properties"new_node ; let children_pairs zip_longest ."children"old_node ."children"new_node fn(node_i node_ii) ,node_i,node_ii[] ; ; let children_differences let result reduce {} children_pairs fn(result children_pair) let index ?? ."index"result 0; let differences compare_nodes .0 children_pair .1 children_pair index child_path ; #"differences" + ?? ."differences"result [] differences #"index" ++ index {}; ; ?? ."differences"result [] ; + properties_differences children_differences ; fn() []; ; ; ;
; #"make_node" fn(kind properties children) make_node kind properties children
;
#"compare_nodes" fn(old_node new_node index path) compare_nodes old_node new_node index path
;
{}

Версию на JavaScript я минифицировал при помощи Google Closure Compiler (JavaScript-версии), версию на моём языке — вручную.

Результаты:

Параметр JavaScript Мой язык
Объём полной версии 2398 Б 2827 Б
Объём минифицированной версии 794 Б 872 Б
Экономия объёма 66.89% 69.16%

Итоги

Чтобы моя идея имела смысл, требовалось превзойти JavaScript по сжатию в несколько раз (ведь нужно место для самого интерпретатора). А результат оказался даже больше.

Таким образом эксперимент закончился неудачей. Идеи, которые я заложил в основу языка, не принесли ожидаемой выгоды.

Репозиторий

Исходный код интерпретатора (реализован на Python), стандартной библиотеки и примеров, а также документация доступны в репозитории под лицензией MIT.

Теги
Показать больше

Похожие статьи

Кнопка «Наверх»
Закрыть