- }:+()___ [Smile]
- Постоялец
Delfigamer
> В общем, по задумке, этот тред - это не просто помойка для идей, а всё-таки попытка родить нечто прекрасное.
Напишу и я тогда пару мыслей по поводу идеального языка программирования.
Сначала мои требования к идеальному языку:
1) Заменяет все языки — может одновременно быть: системой сборки, произвольным кодогенератором, низкоуровневым ассемблером, компилируемым высокоуровневым и скриптовым языком.
2) Предоставляет полный контроль за преобразованием исходный код → машинный код, т. е. можно вмешиваться в стадии оптимизации, если автоматика недостаточно умная.
Мои идеи, как этого можно добиться:
Язык должен быть, внезапно, интерпретируемым скриптовым, результатом исполнения которого является скомпилированный исполняемый файл.
Все стадии преобразования в машинный код явно реализованы на этом скриптовом языке и могут быть включены стандартным инклюдом.
Т. е. если нужен ассемблер, пишем "use asm.x86", если нужен C-подобный язык — "use C.base" и т. п.
Однако, я не уверен, что подобную схему, в принципе, можно реализовать с приемлемой производительностью.
}:+()___ [Smile]
> Сначала мои требования к идеальному языку
Читаешь мои мысли. Не хватает только пункта:
3) Можно добавлять синтаксический сахар на свой вкус, средствами самого языка.
Great V.
> 3) Можно добавлять синтаксический сахар на свой вкус, средствами самого языка.
Лично я решил, что в построение AST вмешиваться нельзя, т. е. набор операторов и их приоритеты жестко фиксирован.
А вот в рамках построенной AST можно реализовывать любой сахар, какой хочется.
}:+()___ [Smile]
> Лично я решил, что в построение AST вмешиваться нельзя, т. е. набор операторов
> и их приоритеты жестко фиксирован.
Ну хз. Что будешь делать когда захочется писать в стиле sql или html?
Great V.
> Что будешь делать когда захочется писать в стиле sql или html?
Какой то аналог sql/html можно будет реализовать и в рамках стандартного AST, мне этого вполне хватит.
Делать же абсолютно произвольный синтаксис — это путь к бардаку и лапше.
Я, например, предполагаю отказаться от стандартного представления флоатов с целью упрощения правил разбора.
Т. е. вместо 1.23e-4 надо будет писать 1.23*10^(-4) или 1.23/10^4.
Принцип "линии Вирта" кто-нить пробовал? как ощущения?
Кажется, я понял, как разобраться с сайд-эффектами.
Итак, базовая семантика.
Операторы. FEF.
В своей основе, вымышленный язык - чисто функциональный.
Базовая единица программы - это оператор. Оператор берёт на вход несколько значений и выдаёт на выходе несколько новых значений. Графически, оператор можно представить в виде ящика.
Операторы - это чистые функции. Всё, что читает оператор, подаётся ему на входы. Всё, что он записывает, снимается с выходов. В частости, если два вызова одного оператора получают одинаковые входы, то выходы так же будут идентичны.
Внутри, оператор - это граф из блоков. Блоки так же ведут себя как чистые функции - берут значения на входе и детерминистски преобразуют их в выходы. Само преобразование определяется типом блока - это может быть как интринсик, встроенный в виртуальную машину, так и обращение к другому оператору. В последнем случае, вычисление блока происходит так, как если бы его заменили на полное содержание соответствующего оператора.
Таким образом, в вымышленном языке, программа - это математическое выражение, а выполнение кода - это последовательное вычисление этого выражения.
Операторы могут рекурсивно обращаться к самим себе - так, в частности, формулируются циклические алгоритмы. Таким образом, во многих программах, их полностью развёрнутое выражение окажется бесконечно глубоким и, в определённых участках, самоподобным; поэтому я называю такую форму "фрактальным выражением" (fractal expression form). Фрактальное выражение, по своим свойствам, так же является и SSA. Отличие от классических вариантов заключается в том, что вместо отдельного потока управления, используются select_if и рекурсия; а роль фи-узлов по большей части выполняют входы операторов.
А вообще, виртуальная машина не обязана хранить все промежуточные значения в графе. Она может вообще скомпилировать граф в линейную функцию и пользоваться только ей. И вообще, действует as-if rule - ВМ может хоть на ушах стоять и чертей призывать, лишь бы результат совпадал с полученным по базовой семантике.
Объекты.
Вымышленный язык оперирует объектами.
Подобно C++, у объекта есть чётко определённое время жизни. В отличие от C++, у объекта есть чётко определённый хозяин и пользователи.
Параметры операторов обязательно характеризуются тем, что происходит со владением объекта.
Для иллюстрации, представим переменную
в таком виде:
std::unique_ptr<type> var;
Возможны следующие виды параметров:
std::unique_ptr<type> f(); var = f( );
Это выходной параметр. Внутри, оператор каким-то образом добывает себе объект. По окончании работы оператора, владение этим объектом переходит от оператора к вызывающей стороне.
void f(std::unique_ptr<type>&&); f( std::move( var));
Вызывающая сторона передаёт объект во владение оператору. У вызывающей стороны остаётся тыква.
std::unique_ptr<type> f(std::unique_ptr<type>&&); var = f( std::move( var));
Это двусторонний параметр. В начале, вызывающая стороны передаёт объект во владение оператору. По окончании работы, оператор должен возвратить объект вызывающей стороне.
Пока работает оператор, у вызывающей стороны остаётся тыква.
Для описания читающих параметров, введём дополнительный объект:
template<typename T> class reader_ptr { private: reader_ptr<T> const* m_parent; T* m_object; mutable int m_children = 0; public: reader_ptr(std::unique_ptr<T>&& uptr) { m_parent = nullptr; m_object = uptr.release( ); } reader_ptr( reader_ptr<T> const& parent) { m_parent = &parent; m_object = parent.m_object; parent.m_children += 1; } reader_ptr( reader_ptr<T>&& other) { m_parent = other.m_parent; other.m_parent = nullptr; m_object = other.m_object; other.m_object = nullptr; } void close( reader_ptr const& parent) { assert( m_children == 0 && parent == m_parent); parent.m_children -= 1; m_parent = nullptr; m_object = nullptr; } std::unique_ptr<T> release( ) { assert( m_children == 0 && m_parent == nullptr); std::unique_ptr<T> uptr( m_object); m_object = nullptr; return uptr; } ~reader_ptr( ) { assert( m_parent == nullptr && m_object == nullptr); } type operator*( ) const { assert( m_object != nullptr); return *m_object; } };
На объекта можно повесить читающую ссылку. В отличие от владельца, читателей может быть множество. Пока на объекте висит хотя бы один читатель - его владение нельзя передавать, что означает невозможность изменить его.
В отличие от С++, читающие ссылки так же обладают "личностью" и временем жизни. Ссылка рождается либо от владеющей переменной, либо от другой такой же ссылки. Читающую ссылку нельзя просто уничтожить - её обязательно нужно вернуть к родительской ссылке/переменной. Это позволяет дать гарантию, что после закрытия ссылки у неё не останется висящих производных.
То есть, reader/writer lock - это одна из деталей базовой семантики языка.
void f(reader_ptr<type> const&); { reader_ptr<type> reader( std::move( var)); f( reader); var = reader.release( ); } // or, when `var` is itself a reader: { reader_ptr<type> child_reader( var); f( child_reader); child_reader.close( var); }
Это читающий входной параметр. Оператору даётся читающая ссылка, которую по окончании работы он должен вернуть наверх.
void f(std::unique_ptr<type>); f( new type( *var));
Это копирующий входной параметр. Вызывающая сторона копирует объект, копия передаётся оператору во владение и у него и остаётся. Копию можно сделать как от объекта под владением, так и от читающей ссылки.
Переменные оператора и поля объекта так же могут быть владеющими или читающими. Например, возможна такая ситуация:
procedure f[external list: List]
for local iterator -> iter: ListIterator in list do
print[iter.target is list] -- "true"
end
end
external-ссылки учитываются статически, в процессе создания функции.
_
С точки зрения FEF, такая семантика проявляется в том, что некоторые блоки могут разрушать объекты на своих входах, что накладывает некоторые ограничения на порядок вычисления блоков и, в частности, делает выборочное исполнение select_if-веток обязательной возможностью ВМ.
Треды.
Поскольку язык функциональный, то примитив для многопоточности - это корутины, так же известные как async/await.
В вымышленном языке, тред - это асинхронно работающая лямбда, которая общается с владельцем через трубу объектов.
local thread: UpperPipe[Pair[Int32, Int32], Int32] = start_thread[thread_body]
for in range[1000] do
with local p from block_read[modify thread] do
print[p.first]
write[modify thread, p.second]
end
end
terminate[consume thread]
Собственно, базовая семантика работает таким образом.
start_thread берёт лямбду единственным аргументом и создаёт новый поток. Поскольку в базовой семантике все функции - чистые, то сам по себе новый тред полностью изолирован от внешнего мира. Для связи, дополнительно создаётся "объектная труба" - по сути, две очереди объектов. "Нижний" конец трубы передаётся аргументов в лямбду, "верхний" - возвращается результатом из start_thread.
"Верхний" конец трубы ассоциируется с потоком. С точки зрения вызывающей стороны, write в верхний конец кладёт объекты в очередь, тогда как read из верхнего конца продвигает лямбду и может вернуть объект с того конца.
"Нижний" конец трубы ассоциируется с окружением. С точки зрения потока, write в нижний конец так же кладёт объект в очередь, а read из нижнего конца - продвигает окружение.
Таким образом, согласно базовой семантике, сами по себе потоки стоят на месте и ничего не делают. Единственный момент, когда поток включается - это во время вычисления read. С точки зрения самого потока ситуация аналогичная - окружение стоит на месте и не меняется, пока не его не попросят. В каком-то смысле, read из нижнего конца - это явная команда на разморозку всего остального мира. Конечно же, по завершению read, мир снова заморожен в ожидании.
В действительности же, разрешается и даже поощряется гонять потоки параллельно.
Сами по себе read и write синхонизируются по-минимуму - гарантируется только, что read из одного конца трубы увидит объекты в том же порядке, в каком их засунул write с другого конца. read не ждёт на пустой очереди, для этого есть block_read. read и write на одном конце трубы не синхронизируются друг относительно друга, хотя, разумеется, write значения, явно зависящего от результата read, произойдёт позже по времени.
}:+()___ [Smile]
> Делать же абсолютно произвольный синтаксис — это путь к бардаку и лапше.
Наговнокодить можно при любом синтаксисе. Не аргумент.
Актёры. Координатор.
В принципе, описанных средств уже достаточно, чтобы из них составить параллельную систему с общими элементами.
В качестве примера рассмотрим терминал - единый объект console, на который можно сделать print.
Прежде всего, print изменяет состояние терминала (переписывает буфер). Следовательно, требуемая сигнатура - это print[modify console, ...].
Даже если на минуту представить, что мы обманули систему и прописали print как читающую функцию - тогда у функции не останется никаких результатов, и каждый вызов скомпилируется в FEF в блок, который никак не участвует в образовании результатов - что, согласно базовой семантике, является мёртвым кодом, и при первом же преобразовании этот вызов рискует бесследно исчезнуть из программы.
Поскольку язык функциональный - чтобы сделать modify console, придётся в каждую функцию завозить текущий console, а затем новое состояние забирать с результатов. Пока программа работает в один поток - всё в порядке (C99 и C++98 так и делали, говорят, брат выжил), осталось только научить компилятор автоматически продёргивать console вдобавок к явным аргументам и будет ништяк.
С описанной моделью многопоточности, однако, такой фокус не прокатит. Проблема опять состоит в том, чтобы сделать modify console - потоков может быть сколько угодно, но владелец в любой момент времени должен быть один. Единственный способ передать владение - объектные трубы - не подходит для этой задачи, потому что в таком случае, по этому объекту все потоки выстроятся в одну длинную линию и язык окажется бесполезным.
Вот это и есть "проблема сайд-эффектов".
Собственно, моё решение выглядит так. local console сидит в какой-нибудь функции верхнего уровня и никуда оттуда не уходит. Эта функция вызывает основной код через start_thread и затем в цикле слушает трубу на предмет запросов. Наконец, когда основной код хочет чего-либо напечатать - он делает print[modify lower_pipe, ...], который, в свою очередь, делает write[modify lower_pipe, new PrintRequest {...}]. Верхняя функция ловит этот запрос, выводит его в свой console и продолжает вращение в цикле.
Итак, обобщение этой концепции - это координатор - специально написанный оператор, предоставляемый стандартной библиотекой, который крутится в цикле и ворочает запросами. Координатор выглядит приблизительно так:
class CoordinatorState
local threads: Map[Id, ObjectPipe[Request]]
local objects: Map[Id, Value]
local upper: ObjectPipe[Request]
local terminate: Boolean = false
end
operator coordinator_body[consume pipe: ObjectPipe[Request]]
local state = new CoordinatorState {upper -> consume pipe}
while not state.terminate do
local pending: Worklist[Request]
for local thread in state.threads do
with local request from read[thread] do
push[pending, request] -- can't modify state from inside a for loop
end
end
for local request in modify pending do
invoke[consume request, modify state]
end
with local request from read[state.upper] do
invoke[consume request, modify state]
end
end
end
operator create_thread[f: operator type [] requires environment]: Id requires environment
operator g[consume pipe: ObjectPipe[Request]]
invoke[f, environment -> create_environment[consume pipe]]
end
write[
modify current environment,
consume closure [modify state: CoordinatorState]
insert[modify state.threads, start_thread_bare[]]
end]
end
operator send_to_thread[target: Id, rq: Request] requires environment
write[
modify current environment,
consume closure [modify state: CoordinatorState]
with local thread from get[state.threads, target] do
write[modify thread, rq]
else
write[modify state.upper, consume current closure]
end
end]
end
Координатор позволяет делать две вещи.
Во-первых - он позволяет обмениваться информацией нескольким равноправным потокам.
Во-вторых - он позволяет хранить множество объектов, доступных для чтения и записи одновременно нескольким потокам, посредством отправки запросов и получения ответов. Эти объекты в данном языке носят особое название "актёры", и для работы с ними предоставляется дополнительный синтаксис, частью которого является и current environment.
Постояв ещё часок в очереди, я обнаружил, что описанная модель - недостаточно расслаблена.
Вообще, в конечном итоге должно получиться так, чтобы код координатора можно было без потерь инлайнить прямо по месту отправки реквеста, что в конечном итоге должно свернуть отправку/получение до элементарных атомиков.
С описанием выше - чтобы оптимизация была корректной, в каждом таком инлайне придётся блокировать весь координатор мьютексом, что, вообще-то, довольно жирно.
Поэтому сделаем несколько по-другому.
Чтобы не путаться в терминах, назовём поточный примитив файбером.
Процесс создания выглядит так же - функция рождается во вселенском вакууме и получает трубу.
Реквесты сразу включают в себя встроенный механизм для ответов - по сути, являются промисами.
operator is_ready[
external handle: RequestHandle,
modify : Thread,
]: Testable
operator receive_response[
consume handle: RequestHandle,
modify : Thread,
]: Value
-- receiver
operator listen[
modify : Thread,
]: Optional[Pair[Request, Value]]
operator send_response[
consume : Request,
consume data: Value,
]
Вместо write, для отправки данных используется комбинация send_request+receive_response. send_request кладёт запрос в трубу и тут же возвращает управление. receive_response "размораживает" файбер и получает подтверждение.
send_request не выстраиваются в единый порядок - если отправить два send_request подряд, второй может быть обработан и отвечен раньше, чем первый. Если же send_request стоит после receive_response - это создаёт порядок между ними, и второй запрос обязательно будет отправлен только после получения ответа на первый, даже если между ними нет зависимостей помимо fiber-объекта.
По идее, такие реквесты можно реализовать в виде непосредственных acquire/release-операций над самими объектами.
Кроме того, такие реквесты позволяют без костылей передавать external-ссылки между файберами - send_request забирает ссылку, RequestHandle её хранит, response возвращает обратно.
Жизнь программы выглядит примерно таким образом.
0. Кто-то делает запрос на загрузку модуля. Это может быть import, это может быть адд-он в language, это может быть сама ОС.
1. Рантайм находит модуль по имени. Если есть уже загруженный инстанс в кэше рантайма - может тут же вернуть его. Если находит файл - пытается его загрузить. Десериализация байткода и компиляция исходного текста - это частные случаи "загрузки". Загрузка может закончиться неудачей - тогда запрос вместо модуля возвращает ошибку.
2. Если найден исходный текст - загрузка начинается с определения языка. Система допускает множество различных вариантов сериализации. Чтобы идентифицировать, что происходит именно в этом файле - рантайм считывает language-прелюдию к файлу, такого вида:
Парсер и расширения так же являются модулями. После прочтения прелюдии, рантайм рекурсивно пытается загрузить модуль base_parser_name.syntax. Этот модуль описывает базовый синтаксис.
operator create_parser[]: Checkable[Parser] requires current context
Парсер может быть расширяемым - в таком случае, модуль описывает свой подкласс SpecificParser, предоставляющий методы, дополнительно настраивающие синтаксис.
После создания объекта парсера, рантайм по очереди загружает модули extension_n_name.syntax. Эти модули дополняют переданный им парсер своими правилами.
Если в ходе загрузки языка возникнет цикл - это уф, генерируется ошибка. Если какой-то из модулей не экспортирует правильные операторы - это ошибка. Если тип парсера в register_extension не сходится с типом от create_parser - это ошибка.
Заметьте, что расширения не могут корёжить синтаксис как угодно - новые правила могут вставляться только там, где этого допускает базовый язык. Он же проверяет свои сборные правила на предмет противоречий, и может выдать ошибку, если по-хорошему зарегистрировать расширения не получается.
Расширения синтаксиса играют роль макросов.
Для стандартного парсера, библиотека предоставляет специализированный язык для syntax-модулей, в котором расширения записываются в виде BNF-подобных выражений.
3. Если рантайму удалось собрать парсер со всеми причиндалами - он приводится в действие. Парсеру передаётся поток байтов сразу после закрывающей скобки прелюдии. Парсер возвращает абстрактное синтаксическое дерево, составленное из записей такого вида:
Пример дерева приведён в ИТТ #39.
4. Следующий шаг - это семантический анализатор.
Большинство узлов в стандартном языке - это выражения,
Рантайм держит словарь, где каждому имени узла соответствует некоторый объект.
При загрузке модуля, рантайм берёт из этого словаря обработчик корневого узла. В результате его обработки, на выходе должна получится функция инициализации.
5. Рантайм вызывает эту функцию - код модуля исполняется. В процессе исполнения, инстанцируются и регистрируются в контексте модуля все его объявления - операторы, типы, переменные и прочие.
После компиляции модуля, тела внутренних функций остаются в виде синтаксического дерева. Функция превращается в байт-код в момент исполнения выражения "operator ... end". Статический анализ так же откладывается до этого момента.
6. В рантайме так же могут быть зарегистрированы оптимизаторы - функции, которые определённым образом преобразуют переданные им ProgramGraph. Оптимизаторы так же, как и парсеры, являются внешними модулями по отношению к ядру рантайма.
7. Функции могут быть использованы в дальнейших преобразованиях. В частности - скомпилированную до байткода функцию можно передать отдельному транслятору, который докомпилирует её до нативного кода и сохранит в виде отдельного исполняемого файла. В общем случае, такой файл теряет возможность интероперировать с модулями, не включёнными в начальную сборку, поскольку больше не принадлежит рантайму и не участвует в его инфраструктуре.
Значение. Поведение. Лейаут.
В вымышленном языке, 'объект' разделяется на несколько изолированных абстракций.
Значение - это та сущность, которая передаётся между блоками FEF.
Базовую семантику можно проиллюстрировать таким образом:
Собственно, значение - это тот void*, который передаётся между блоками.
Основной инструмент типизации в языке - это поведение. На более физическом уровне, поведение - это массив указателей на функции.
В отличие от виртуальной таблицы, поведение не входит в состав объекта, а является частью контекста. Это позволяет определять поведение сразу для нескольких логически связанных объектов.
Язык предоставляет свой аналог ADL - при вызове функции просматривается не только текущий лексический контекст, но также и все поведения, имеющиеся в контексте и применимые к аргументам.
Основной способ, которым поведение попадает в контекст - это requires behavior-параметры. При переходе к базовой семантике, каждый requires behavior транслируется в дополнительный параметр, через который передаётся экземпляр поведения, соответствующий актуальным типам явных параметров.
Лейаут - это набор функций, похожий на поведение, который предоставляет доступ к полям класса. Чтение и запись полей - конструкция вида object.field - транслируется в вызов функции лейаута, соответствующей этому полю. Лейауты так же транслируются в отдельные параметры, передаваемые вместе со значением объекта.
Лейаут - это абстракция, разделяющая структуру объекта и его физическое представление.
По умолчанию, рантайм автоматически генерирует лейаут для переменной, исходя из рекомендаций оптимизатора и хинтов в атрибутах. Также программисту даётся возможность предоставить свой собственный лейаут, который даст явное представление одного объекта как функции от другого. В предельном случае, создание лейаута относительно двоичных типов - Int32, ByteString, ByteBuffer[24] и прочих - позволяет полностью контроллировать двоичное представление объекта, что будет особенно полезно для взаимодействия с программами на других языках, которые не предоставляют таких возможностей.
Класс, во многих аспектах, идентичен поведению одного параметра. В дополнение к поведению, класс также содержит объявления полей - local- и external-конструкции. При использовании, язык предоставляет доступ к объявленным полям согласно их статическому типу (который включает поведения и лейауты для каждого поля). При объявлении, эти поля становятся требованиями к лейауту - для автоматического, язык сгенерирует лейаут, способный сохранить все объявленные поля без обозримого наложения, для явного, он статически удостоверится в его достаточности.
Обработка ошибок.
В языке, вместо исключений, присущих императивным языкам, для сообщений о неудачах используется специальное семейство типов, называемых "checkable".
Если какая-то функция может потерпеть неудачу - то её результат заворачивается в специальный контейнер, который представляет своего рода юнион успешного результата и возможных вариантов ошибок.
Поскольку язык избегает понятий "критических ошибок" и "неопределённого поведения", то извлечение успешного результата из контейнера нельзя сделать в виде обычной функции - ведь, если в контенере хранится ошибка, то извлечение успешного результата не имеет смысла.
Поэтому, разбор структуры происходит путём передачи лямбды в метод контейнера, которая получает результат аргументом в случае успеха.
В C++, такая идиома выглядит следующим образом:
template<typename T> struct PossibleValue { union { T success_result; Failure failure_result; }; bool is_success; }; template<typename T, typename F1, typename F2> void with_do(PossibleValue<T> self, F1 if_success, F2 if_failure) { if ( self.is_success) if_success( std::move( self.success_result)); else if_failure( std::move( self.failure_result)); } template<typename Dom, typename Cod> PossibleValue<Cod> Map<Dom, Cod>::get( Dom const& key) const { Cod* ptr = this->internal_get_value_ptr( key); if ( ptr) return make_success<Cod>( *ptr); else return make_failure<Cod>( MissingKeyFailure{}); } void f( Map<int, char const*> const& map) { with_do( map.get( 1020), []( char const* value) { printf( "%s\n", value); }, []( Failure const& e) { printf( "%s\n", e.what( )); }); }
В описываемом языке, для работы с такими объектами вводится дополнительная синтаксическая конструкция:
expression-sequence впоследствии передаются методам объекта, возвращаемого source-expression, в виде функций. В случае соответствия, внутренний код объекта вызывает эту функцию, передавая ей действительные значения соответствующего типа.
Главная особенность состоит в том, что такая схема позволяет полностью избежать "висящих переменных" - само создание переменной только при условии валидности запроса. При альтернативных подходах, либо существуют ситуации, когда переменная может быть невалидной:
char const* str = nullptr; // str is invalid if (try_get( map, 1020, str)) { puts( str); } // str may be invalid
либо существует возможность неопределённого поведения:
if (exists( map, 1020)) { char const* str = get( map, 1020); puts( str); } else { char const* str = get( map, 1020); // str is what?? }
либо происходит процедурный бедлам с исключениями и longjmp, которые очень плохо вписываются в функциональную природу вымышленного языка.
Кроме того, такая семантика позволяет пойти ещё дальше. Раз "висящие переменные" в коде нигде не нужны, то можно усилить саму семантику языка и утвердить правило, что "висящие переменные" невозможны. Если к переменной можно обратиться - значит, она гарантированно обладает валидным значением.
Соответственно, если некая функция объявлена с возвращаемым типом Stuff - значит, какие бы входные данные в неё не поступили, в каком бы состоянии не находилось окружение, эта функция в любом случае вернёт валидный Stuff. И напротив - если в некоторых случаях функция не может вернуть осмысленный результат, то это будет явно указано в прототипе формулировкой Optional[Stuff].
