Альтернатива Emacs Lisp’у

в 9:29, , рубрики: compilers, emacs, emacs lisp, Go, Компиляторы

image

Вы когда-нибудь искали альтернативу Emacs Lisp'у? Давайте попробуем добавить в Emacs ещё один язык программирования.

В этой статье:

  • Потенциальные преимущества, которые будут получены при возможности расширять Emacs на Go;
  • Определим способы взаимодействия Go и Emacs Lisp;
  • Затронем некоторые детали реализации описанного транскомпилятора;

Статья может заинтересовать пользователей Emacs'а, а также тех, кому небезразличны все эти бесчисленные реализации бесчисленных языков программирования.

В самом конце статьи представлена ссылка на work in progress проект, который позволяет конвертировать Go в Emacs Lisp.

Выбираем Emacs Go

Как и любой другой язык программирования, Emacs Lisp имеет ряд "недостатков", которые мы будем политкорректно назвать "design tradeoffs". Говорить "лучше" или "хуже" о тех или иных свойствах языка программирования на объективном уровне достаточно сложно, потому что почти всегда найдутся защитники противоположных позиций. Нам же, как пользователям языков программирования, можно стараться выбрать тот язык, чьи компромиссы нам принять проще в силу наших задач или личных предпочтений. Ключевой момент — возможность выбора.

Предположим, что мы выбрали Go. Как вы будете использовать Go для взаимодействия с редактором?
Ваши варианты:

  1. Использовать Emacs модули для запуска Go функций. Вдохновение можно черпать из проекта go-emacs.
  2. Найти (или написать) интерпретатор Go, встроить его в Emacs путём патчинга или теми же C модулями, а затем вызывать eval из редактора.
  3. Транслировать Go в Emacs Lisp байт-код.

Способов может быть больше, но ни один из них не будет ближе к "нативному" лиспу, чем (3). Он позволяет на уровне исполнения иметь ту же виртуальную машину, что и обычный Emacs Lisp.

Это, в свою очередь, означает, что:

  • Emacs Lisp код сможет вызывать транслированный Go код;
  • FFI бесплатен. Вызов уже определённой в Emacs функции из Go максимально эффективен;
  • Легко распространять сконвертированные пакеты (родной для Emacs формат);

Если вы в первый раз слышите о байт-коде Emacs'а, ознакомьтесь со статьёй Chris Wellons.

Почему Go?

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

Есть несколько причин из-за которых сделанный выбор становится более обоснованным. Основные из них:

  • Компилятор языка внутри стандартной библиотеки;
  • Лаконичная спецификация;
  • Скромный runtime;
  • Tooling;

Есть также те свойства, которые могли бы быть аргументами в пользу выбора, но конкретно для меня они были менее значимыми:

  • Go — достаточно популярный язык с С-подобным синтаксисом (т.е. это тебе не Scheme);
  • Статическая типизация;

Компилятор языка внутри стандартной библиотеки

Пакеты go/* значительно упрощают написание инструментов для Go.

Не нужно писать parser, typechecker и прочие прелести frontend'а компилятора. За 20 строк кода мы можем получить AST и информацию о типах для целого пакета.

Документация, по большей части, хороша. А для go/types на мой взгляд — образцовая.

Изначально для меня это было убийственным аргументом. Задача казалась на 90% решённой благодаря этому секретному оружию: "осталось только преобразовать AST в байт-код Emacs'а".

Ложка дёгтя

На практике возникали сложности с теми или иными нюансами.

В первую очередь — запутанность API и дублирование разными пакетами похожих сущностей, да ещё и под одинаковыми именами. Часто одно и то же можно сделать через go/ast и go/types; не редко вам нужно перемешивать сущности из обоих пакетов (да-да, в том числе те, что с одинаковыми именами).

Ещё на удивление неудобной оказалась работа с import'ами и декларациями (ох уж этот ast.GenDecl).

Многие решения, с помощью которых вы можете решить эти проблемы, выглядят как "грязные хаки". Детальное описание этих хаков — это, возможно, материал для отдельной статьи (тем более я не проверял обилие информации на эту тему в интернете, наверняка уже всё успели разжевать и не раз).

Лаконичная спецификация

Создать реализацию, которая в большей степени (~80%) конформна спецификации — вполне посильная задача для одного человека. Спецификацию Go легко читать, её можно осилить за вечер.

Особенности спецификации:

  1. Некоторые моменты вызывают сомнения в однозначности трактовки. Цена краткости;
  2. Кроме спецификации есть ещё Effective Go. Без него в спецификации останутся белые пятна;

Скромный runtime

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

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

Tooling

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

Для Go многие функции, которые обычно переизобретаются для каждой IDE отдельно, реализованы в виде отдельных утилит. Самый простой пример, известный каждому Go разработчику — gofmt. В немалой степени этому способствуют упомянутые выше go/types,
go/build и остальные пакеты из группы go/*.

Sublime text, Emacs, Visual Studio Code — выбираешь любой из них, ставишь плагин(ы), и наслаждаешься рефакторингом через gorename, множеством линтеров и автоматическими import'ами. А автодополнение… превосходит company-elisp во многих аспектах.

Рефакторить и поддерживать проект на Emacs Lisp уже после 1000 строк кода лично мне уже некомфортно. Программировать Emacs на Go чуть ли не удобнее, чем на Emacs Lisp.

Как выглядит Emacs Go

Пофантазируем на тему того, как мог бы выглядеть Go для Emacs'а. Насколько он был бы удобен и функционален?

Мост типов

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

С примитивными типами вроде int, float64, string и другими всё более-менее просто. И в Go, и в Emacs Lisp эти типы присутствуют.

Интерес представляют слайсы, символьные типы (symbol) и беззнаковые целочисленные типы фиксированной разрядности (uintX).

  • Слайсы реализуем в рантайме (например, на том же Emacs Lisp);
  • Символы представляем в виде opaque типа;
  • Беззнаковую арифметику с детерминированным переполнением — эмулируем;

Тип, который может выразить "объект произвольного типа", который возвращается Emacs Lisp функцией, назовём lisp.Object. Его определение дано под спойлером lisp.Object: детали реализации.

Go slices

Для аналогии: слайсы в Go по своему "интерфейсу" — это std::vector из C++, но с возможностью брать полноценный subslice без копирования элементов.

Начнём с интуитивного представления {data, len, cap}.
data будет вектором, len и cap — числами. Чтобы хранить атрибуты выбираем improper list, где у нас нет финального nil, чтобы немного экономить память:
(cons data (cons len cap))

Почему список, а не вектор?

Если вкратце, то: выбор между списком и вектором здесь не особо критичен, так что можно было взять вектор.

Более развёрнутый ответ на этот вопрос поможет найти дизассемблер (или таблица опкодов). Доступ к спискам из 2-3 элементов — очень эффективный. Чем ближе к голове списка, тем более ощутима разница. Атрибут data используется чаще всего, поэтому он в самом начале списка.

При N=4 можно считать, что список начинает уступать по эффективности в случае считывания последнего элемента, но остальные три атрибута всё так же более эффективны в доступе => даже для объектов из четырёх атрибутов я склонен полагать, что список является более удачной структурой, чем вектор.

Оговорка: это всё справедливо для виртуальной машины Emacs'а, её набора инструкций. Вырывать из контекста не стоит.

Операции slice-get/slice-set будут очень эффективными. У нас будет тот же aset/aget, но с одной дополнительной инструкцией car для извлечения атрибута data.

Но что будет, когда нам нужен subslice?

В C можно было бы data сделать указателем и сместить его, куда нужно. Адресация была бы такой же, 0-based. В нашем случае это невозможно, что приводит к необходимости хранить ещё и offset:
(cons data (cons offset (cons len cap)))

Для каждого slice-get/slice-set теперь нужно к индексу прибавлять offset.

Сравним байт-код для операции slice-get.

;; Обычный вектор
<vector> ;; [vector]
<index>  ;; [vector index]
aref     ;; [elem]

;; Slice без offset (не поддерживаем subslice)
<slice> ;; [slice]
car     ;; [data]
<index> ;; [data index]
aref    ;; [elem]

;; Slice с поддержкой subslice
<slice>     ;; [slice]
dup         ;; [slice slice] (1)
car         ;; [slice data]
stack-ref 1 ;; [slice data slice]
cdr         ;; [slice data slice.cdr]
car         ;; [slice data offset]
<index>     ;; [slice data offset index]
plus        ;; [slice data real-index]
aref        ;; [slice elem]
stack-set 1 ;; [elem] (2)

;; (1) Поскольку <slice> может быть дорогим выражением, мы
;; вычисляем его единожды.

;; (2) Нам требуется восстановить инвариант стека и удалить
;; лишний slice со стека. 

С помощью нотации <X> выделены выражения, которые могут быть произвольно сложными (от обычного stack-ref, до call со множеством аргументов). Справа от кода отображено состояние стека данных.

Opaque types

Некоторые типы мы не захотим/не сможем выразить как Go структуры. К таким типам относятся lisp.Object, lisp.Symbol и lisp.Number.

Главной целью opaque типа для нас является запрет на произвольное создание объектов через литералы. С этим отлично справляются интерфейсные типы с неэкспортируемым методом.

type Symbol interface {
    symbol()
}

type Object interface {
    object()
    // Другие методы...
}

// Для создания объектов должна использоваться специальная функция-конструктор.

// Intern returns the canonical symbol with specified name.
func Intern(name string) Symbol

Функция Intern обрабатывается компилятором по-особому. Другими словами она — intrinsic функция.

Теперь мы можем быть уверены, что у этих особых типов такое API, которое мы хотим им придать, а не то, какое возможно по законам Go.

lisp.Object

Если lisp.Object представляет "любое значение", то почему мы не используем interface{}?

Вспомним, что такое interface{} в Go — это структура, хранящая в себе динамический тип объекта, плюс сам объект — "данные".

Это не совсем то, чего хотелось бы, потому что для Emacs'а такое представление "чего угодно" не является эффективным. lisp.Object нужен для того чтобы хранить unboxed Emacs Lisp значения,
которые легко можно передавать в функции лиспа и получать в качестве результата.

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

type Object interface {
    object()

    Int() int
    Float() float64
    String() string
    // ... etc.

    // Можно также предоставить следующие методы:
    IsInt() bool                // Предикат для проверки типа
    GetInt() (val int, ok bool) // Для "comma, ok"-style извлечения
    // ... аналоги для оставшихся типов.
}

Каждый вызов генерирует проверку типа. Если внутри lisp.Object хранится значение отличного от запрошенного типа, должен быть вызван panic. Чем-то напоминает API reflect.Value, не так ли?

Emacs Lisp из Go

Если сигнатура функции неизвестна, то единственное, что нам остаётся — это принимать вариативное количество аргументов произвольного типа, а возвращать lisp.Object.

pair := lisp.Call("cons", 1, "2")
a, b := lisp.Call("car", pair), lisp.Call("cdr", pair)
lisp.Call("insert", "Hello, Emacs!")
sum := lisp.Call("+", 1, 2).Int()

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

part := "c"
lisp.Insert("Hello, Emacs!")     // Возвращает void
s := lisp.Concat("a", "b", part) // Возвращает string, принимает ...string

FFI DSL

DSL для аннотирования функций можно написать на макросах.

;; Пример описания функций, доступных через FFI.
(ffi-declare
 (concat Concat (:string &parts) :string)
 (message Message (:string format :any &args) :string)
 (insert Insert (:any &args) :void)
 (+ IntAdd (:int &xs) :int))

;; Разворачивается макрос, например, в Go сигнатуры.

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

// IntAdd - ... <комментарий функции + из Emacs>
//$GO-ffi:+
func IntAdd(xs ...int) int

// ... Остальные функции

Документацию можно подтягивать из Emacs'а функцией documentation. Получаем функции с известной арностью и при этом не теряем ценные docstrings.

Go из Emacs Lisp

Результатом транскомпиляции будет Emacs Lisp пакет, в котором все символы из Go имеют преобразованный вид.

Схема преобразования идентификаторов может быть, например, такой:

package "foo" func "f"       => "$GO-foo.f"
package "foo/bar" func "f"   => "$GO-foo/bar.g"
package "foo" func (typ) "m" => "$GO-foo.typ.m"
package "foo" var "v"        => "$GO-foo.v"

Соответственно для того, чтобы вызвать функцию или воспользоваться переменной, нужно знать какому Go пакету она принадлежала (и её название, разумеется). Префикс $GO позволяет избежать конфликтов с уже определёнными в Emacs именами.

Тонкости транскомпиляции

Bytecode или lapcode?

В качестве выходного формата можно выбирать среди трёх вариантов:

  1. Emacs Lisp код (source-to-source compilation)
  2. Bytecode
  3. Lapcode (Lisp Assembly Program)

Первый вариант сильно проигрывает остальным вариантам, потому что он не позволит эффективно транслировать return statement, а ещё в нём сложнее реализовать оператор goto (который есть в Go).

Второй и третий варианты по возможностям практически эквивалентны.

  • Bytecode — это аналог машинного кода, самый низкий уровень;
  • Lapcode — это язык ассемблера виртуальной машины со стековой архитектурой;

Компилятор Emacs'а умеет оптимизировать на уровне исходного кода и lapcode представления.
Если выбираем lapcode, то можем дополнительно применять низкоуровневые оптимизации,
реализованные Emacs разработчиками.

Недостатки lapcode

Lisp assembly program — это внутренний формат компилятора Emacs'а (IR). Документации по нему ещё меньше, чем по байт-коду.

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

Я так и не нашёл точного описания формата инструкций. Здесь помогает метод проб и ошибок, а также чтение исходников компилятора Emacs Lisp'а (вам понадобятся стальные нервы).

Производительность генерируемого кода

Go, который "бегает" внутри Emacs VM не может быть быстрее Emacs Lisp.

Или может?

В Emacs Lisp есть динамический scoping для переменных. Если вы заглянете в "emacs/lisp/emacs-lisp/byte-opt.el", то сможете найти множество отсылок к этой особенности языка; из-за неё некоторые оптимизации либо невозможны, либо значительно затруднены.

Констант в Emacs Lisp нет. Имена, объявленные с помощью defconstant менее неизменяемые, чем те, что определены через defvar. В Go константы встраиваются в место использования, что позволяет сворачивать больше константных выражений.

Оптимизировать Go код проще, поэтому можно ожидать как минимум не уступающую обычному Emacs Lisp коду производительность. Потенциально, обгон в плане быстродействия реален.

Трудности реализации

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

Наиболее интересной трудностью являются указатели.

Для векторов (массивов), строк и структур эта задача решается относительно просто:

  • Внутри T и *T всегда лежит ссылочный тип;
  • При передаче по значению, создаётся новый ссылочный тип, в который копируются данные;
  • Для взятия указателя от T не генерировать никакого кода (уже ссылочный тип);
  • Для взятия указателя от *T создавать обёртку-указателя;

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

The most challenging part

А теперь кое-что по-настоящему увлекательное.

Как реализовать взятие адреса от переменной типа int или float?

Заворачивая число в cons, следуя схеме, описанной выше для ссылочных типов, пролетаем по семантике — значение, у которого взяли адрес, не будет меняться в случае изменения данных, хранимых в cons.

Если все числа изначально создавать в boxed виде (внутри cons), то теряется производительность и сильно растёт количество аллокаций.

Нужно учитывать, что над указателями опделён оператор =. Решение с созданием cons объектов при каждом взятии адреса не соблюдает тождества адресов, а значит оно не является корректным.

Другие не вполне работающие варианты:

  • Модифицировать значение переменной, у которой брали адрес, после выхода из блока,
    внутри которого жил указатель (новым значением будет то, что хранилось в cons);
  • Хранить глобальный массив, возвращать индекс из него, который означает "адрес"
    значения. Это позволит избежать постоянного создания cons объектов,
    но потребует некоторого механизма сборки мусора внутри массива;

Это открытый для обсуждения вопрос. Если кто-то предложит оптимальную схему — это будет замечательно!

Seems like Go-ism inside Emacs

Проект goism — это инструмент, который позволяет получать из Go пакетов близкий к оптимальному Emacs Lisp байт-код.

Библиотека времени выполнения изначально была написана на лиспе, но с недавних пор полностью переписана на транслируемом в lapcode Go.
emacs/rt на данный момент — один из самых крупных пакетов, написанных с помощью goism.

На данный момент goism не особо дружелюбен по отношению к конечному пользователю,
придётся работать руками, чтобы правильно его собрать и настроить
(guick start guide должен упростить задачу).

Почему статья написана именно сейчас, а не когда вышла более стабильная версия? Ответ довольно прост: нет гарантий, что эта самая версия когда-либо будет готова, плюс дорабатывать можно очень и очень долго.

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

Автор: quasilyte

Источник

Поделиться

* - обязательные к заполнению поля