По правде сказать, я с самого начала (ещё до обнаружения статьи в Science) размышлял над этой задачей преимущественно со стороны физики. Связь с компиляторами мне поначалу показалась поверхностной и чуть ли не случайной. Не поделитесь чем-нибудь интересным и релевантным по теме супероптимизации?
Кстати, сейчас полюбопытствовал и обнаружил, что физики продолжают довольно активно писать об этом предмете, и кажется, безо всякой связи с компиляторами.
Напомню, это был пример повсеместности указателей на середину структуры. Чем он плох в этом качестве, я так и не понял. Для полноты картины туда стоит добавить какую-нибудь функцию в программе на C, которая требует именно ClrPt как есть (чтобы совсем отбить соблазн заменять указателем).
Что касается времени жизни - да, в данном случае будет работать. Немного изменится скрипт - и уже не будет. В любом случае, я не собирался демонстрировать этим примером трудности анализа времени жизни указателей.
Уделяю ровно столько внимания, сколько потребовалось бы в любом языке, признающем классические структуры с полями-значениям (снова упомяну Go). Встречается это сплошь это и рядом. И если вы предлагаете "запретить на уровне синтаксиса" такой код, то я вас не понимаю:
У вас есть возможность выделять память, с указанием того, где находятся указатели.
Как-то не впечатлился. Притащить увесистую внешнюю зависимость, но при этом всё равно вручную перекодировать всю иерархию типов в битовые поля. Да ещё и не решить проблему указателей на середину структуры (или теперь у Бёма это тоже можно?).
А чем другие языки принципиально отличаются? Они лишь добавляют синтаксического сахара и возможных гарантий.
Когда в языке сборщик мусора полностью интегрирован в runtime-библиотеку, он может (и должен) получать и использовать информацию о типах, чтобы точно знать, где указатель, где нет. В C эта интеграция невозможна, сборщик Бёма вынужден догадываться сам и поэтому не гарантирует отсутствия утечек. Т.е., строго говоря, он некорректен.
Чем продиктован данный выбор, в частности почему проект не написан на c++ с использованием библиотечной реализации(std) или же какой-то другой библиотеки, даже для си?
Ради отсутствия внешних зависимостей и лёгкости встраивания в основную программу на C. Так же сделаны Lua и Wren.
Об этом я много раз говорил, и даже в комментариях под этим постом :) Не поленюсь повторить:
Статическая типизация: делает намерения программиста более ясными, позволяет обнаруживать несовместимости типов ещё на этапе компиляции скрипта и выдавать понятные сообщения об ошибках. Lua - динамически типизированный язык, ошибки типов обнаруживаются лишь случайно во время исполнения скрипта.
Типы данных, совместимые с типами C: позволяют скрипту легко обмениваться структурами данных с основной программой на C/C++, сохраняя при этом раскладку полей структур в памяти. Lua использует типы, совершенно чуждые C, и предлагает громоздкий механизм userdata.
Есть библиотечные реализации, думаю подключить библиотеку будет проще уже проделанной работы.
Не совсем понимаю, как они работают. Ведь они должны иметь доступ к типам данных разрабатываемого языка (что я и обозначил "первой проблемой"). Без этого обходится, среди известного мне, только сборщик Бёма, но его принцип действия мне по сей день кажется странным: любая последовательность байт, которая выглядит как указатель, является указателем. Для C сгодится и это, коль скоро программа на C при всём желании не сообщит ничего о типах. Для других языков - сомнительное решение.
Насколько помню, передать из go в си интерфейс невозможно.
Скорее всего так, поскольку там появляются указатели, сборка мусора и таблицы методов. В Umka тоже нельзя.
Здесь имелся в виду пример с приведением слабого указателя к сильному в синтаксисе умки
a := 42
var p: weak ^int = &a
if q := ^int(p); q != null {
printf(repr(q^) + '\n')
}
а так же вопрос борьбы с висячими указателями, чтобы, например, при удалении одного объекта, и создании нового, нельзя было бы по старому указателю обратится к новому объекту.
Ситуация маловероятная, но нет уверенности, что невозможная. Стоит подумать.
Довольно низкоуровневый скриптовый язык получается.
Так и задумывалось.
Были тесты, или это просто общее впечатление?
Общее впечатление. Здравый смысл подсказывает, что общие накладные расходы в случае подсчёта ссылок и трассирующей сборки мусора примерно одинаковы, однако при подсчёте ссылок они более равномерно "размазаны" и гарантированно не дают подвисаний. В конце концов, обход потомков, про который я писал, - это практически то же, что делает трассирующий сборщик, только разбитое на мелкие кусочки. А чтобы делать тесты, нужно было реализовать оба варианта. Я этого не делал.
Насколько часто придётся сталкиваться Object(или местным аналогом)?
Насколько я понимаю, речь идёт о пустом интерфейсе interface{}. По опыту практического использования, встречается не очень часто, но за неимением обобщённых типов - несколько чаще, чем хотелось бы.
На чём основан такой выбор? Это полностью прозрачно, или как в go некоторые вещи недоступны из си кода?
Не совсем понял вопрос. Но во избежание недоразумений подчеркну, что речь идёт не об FFI, позволяющем вызывать любую функцию, а о функциях с заранее оговорённой сигнатурой. Точно так же сделано в Lua: "When we say that Lua can call C functions, this does not mean that Lua can call any C function... As we saw previously, when C calls a Lua function, it must follow a simple protocol to pass the arguments and to get the results." Ну и конечно, из C недоступно то, что относится к подсчёту ссылок.
реализация слабых указателей практически не описана — как именно они устроены и как ими пользоваться в умке.
Это как раз совершенно классическая тема, где я не придумал ничего оригинального. Так же сделан std::weak_ptr в C++ и всё управление памятью в Swift. Слабый указатель - такой, который при навешивании на объект не меняет его счётчика ссылок. Следовательно, он не мешает довести счётчик ссылок до нуля и уничтожить объект, поэтому сам рискует оказаться висячим. Так что пытаться разыменовывать слабый указатель опасно.
Управление памятью полностью самописное?
Да, полностью самописное. В основном оно сводится к тому, что при присвоении рекурсивно вызывается функция обхода потомков, меняющая их счётчики.
Были ли проблемы с использованием уже освобождённой памяти? Если да, то как они были решены?
Имеется в виду обращение по висячим указателям, память из-под которых уже очистили? Проблемы были, но только по недомыслию и невнимательности (например, как правильно менять счётчики при вызове append() для динамического массива).
Язык уже полностью готов, или ещё есть вещи, всё ещё не реализованые?
Языком вполне можно пользоваться. Из интересного не готовы замыкания (хотя безымянные функции есть), поддержка Unicode (она работает сейчас ровно настолько, насколько это поддерживает терминал и локаль в C). Обобщённые типы - пока только на дальнем горизонте (их ещё и в Go не сделали).
Какие преимущества перед существующими языками, кроме скорости компиляции?
О преимуществах я говорил. В нише доминирует Lua. По сравнению с ним, имеем раннее обнаружение ошибок типов (с понятным сообщением об ошибке) и хорошую "стыкуемость" типов с типами C: целые/дробные разной длины, массивы, структуры. А скорость компиляции (имеется в виду, в байт-код перед запуском?) - здесь не очень интересный параметр. И кстати, ничего особенного я тут и не заявлял.
Что с библиотеками, например, если я захочу обрабатывать js, то какие у меня варианты, кроме написания парсера с нуля?
Библиотеки пока не особо обширные: мои и сторонние (среди последних есть разбор JSON, но если хотите JavaScript - то, боюсь, с нуля).
Надо делить типы на Value и Reference, как в C#. Тогда указатель (как Reference тип) на int будет просто невозможен.
Добавлю, что в Umka, как и в Go, не различаются классы и структуры (такое различение мне вообще кажется абсолютно искусственным). Методы навешиваются на структуры. Тогда каким типом должна являться структура: value или reference? Лично мне требуется value - для естественного взаимодействия с C.
Тогда смысл морочиться с циклическими ссылками и т.п.
Возможны алгоритмы со списками/деревьями, которые на выходе дают число/массив/структуру, которые уже вполне пригодны для передачи.
... список любых бинарных структур, прочитанных из файла в буфер одним большим куском.
Прямо в таком виде буфер нельзя отдать в umka, потому что как только будет выполнено в скрипте присваивание указателя, память перед объектом (где umka ожидает заголовок со счётчиком ссылок) будет испорчена.
Не совсем понял. "Список" в узком смысле слова (с указателями) в файле хранить и нельзя. По-любому понадобится замена указателей на файловые смещения. "Список" в широком смысле слова (по сути, массив) передать можно вполне. Umka вовсе не требует наличия заголовка со счётчиком перед каждым куском, на который есть указатель. Возможны указатели на глобальные или стековые переменные, на переменные C. Требование наличия заголовка касается только памяти, выделяемой в куче Umka.
То есть, вы какую-то свою частную задачу решаете.
А что такое "общая задача"? Универсальных языков всё равно нет. Я решал на Umka свою задачу, какие-то чешские энтузиасты - свою и т.д. В каких-то задачах Umka удобен, в каких-то - нет. Для меня вот до сих пор поразительно, что предназначенный для сопряжения с C язык Lua имеет типы данных, вообще никак не стыкующиеся с типами C.
Структуры, содержащие указатели - разумеется, нельзя передать. Более того, я в принципе не представляю себе этого хоть в каком-нибудь скриптовом языке, коль скоро в C нет никакого автоматического управления памятью. Так что в таком виде эта "цель" и недостижима.
Но все прочие структуры - передавать можно и нужно. И таких в моей практике было большинство: векторы, матрицы, показания датчиков, наборы настроек. Ср. с использованием userdata в Lua. Удобство очевидно.
Я вижу, вы взялись унижать и оскорблять. Жаль. Ожидал более квалифицированной дискуссии. Особенно с учётом того, что когда-то в далёком прошлом вы, кажется, публиковали достойные материалы.
На оскорбления отвечать не стану. А вот на конкретные замечания не поленюсь ответить, хотя уже много раз это делал.
Но какая цель вообще достигается этим велосипедом? Вроде как заявляется как скриптовый язык, но при этом структуры, совместимые с C, и списки.
Именно так. Мне был нужен скриптовый язык, в котором я мог бы перекидывать структуры целиком в C и обратно. Это для меня фактор комфорта. Как и статическая типизация, которая делает намного более ясными намерения программиста и избавляет от огромного числа ошибок, с которыми я сталкиваюсь, например, в Python и ещё более в JS. Сейчас Umka используется у меня на работе в симуляторе динамики трактора.
Что вы умеете делать лучше, чем другие, те же Go, Lua, Haskell или Rust со Swift ом?
Упоминание Go, Haskell, Rust, Swift я считаю вообще неуместным, поскольку всё это языки совершенно иного назначения. Остаётся Lua. Ну а преимущества относительно Lua я перечислил выше. Если же вопрос касался не языка в целом, а управления памятью, то моя задача тут не "делать лучше", а "делать достойно". Этого для начала вполне достаточно.
Вот уж никогда не знаешь, с какой стороны придёт удар :)
Но согласен, айсберг должен расширяться книзу. На подлинных фотографиях это отчётливо видно. Ну и да, такой айсберг, как у меня, вряд ли бы угрожал кораблям своей подводной частью.
А почему нельзя из адреса поля вычесть размеры предыдущих полей с учетом выравнивания?
Получается вычислительная сложность, линейно растущая с количеством полей. Ну и если вообразить "матрёшку" вложенных типов, то требуется обратный проход по ней -- изнутри наружу. Такой возможности нет, да и не совсем понятно, как реализовать.
Судя по исходнику требуется два параметра — указатель на страницу и указатель на поле.
Да. Посмотрите на мой список из четырёх шагов. Первый шаг как раз даёт страницу, второй шаг -- указатель на заголовок, когда страница уже найдена. Вы говорите о втором шаге.
Получается, при помощи обычной рекурсии, начинающейся от корневых объектов, мы теоретически получаем возможность обойти всю иерархию объектов и вычислить объем выделенной под поток памяти. Однако здесь у нас возникли сложности...
Очень похоже на подход к разметке объектов в сборщиках мусора. Вроде бы эта область хорошо разработана — может быть, позаимствовать какие-то решения оттуда?
И кстати, статические поля класса выделяются в куче или по фиксированному адресу?
По правде сказать, я с самого начала (ещё до обнаружения статьи в Science) размышлял над этой задачей преимущественно со стороны физики. Связь с компиляторами мне поначалу показалась поверхностной и чуть ли не случайной. Не поделитесь чем-нибудь интересным и релевантным по теме супероптимизации?
Кстати, сейчас полюбопытствовал и обнаружил, что физики продолжают довольно активно писать об этом предмете, и кажется, безо всякой связи с компиляторами.
Напомню, это был пример повсеместности указателей на середину структуры. Чем он плох в этом качестве, я так и не понял. Для полноты картины туда стоит добавить какую-нибудь функцию в программе на C, которая требует именно ClrPt как есть (чтобы совсем отбить соблазн заменять указателем).
Что касается времени жизни - да, в данном случае будет работать. Немного изменится скрипт - и уже не будет. В любом случае, я не собирался демонстрировать этим примером трудности анализа времени жизни указателей.
Не только чуть менее оптимально, но и вызывает много вопросов о времени жизни указателя при передаче в C.
По сути, вы предлагаете вычеркнуть классические структуры. Нет. Ради них всё и затевалось.
Уделяю ровно столько внимания, сколько потребовалось бы в любом языке, признающем классические структуры с полями-значениям (снова упомяну Go). Встречается это сплошь это и рядом. И если вы предлагаете "запретить на уровне синтаксиса" такой код, то я вас не понимаю:
Как-то не впечатлился. Притащить увесистую внешнюю зависимость, но при этом всё равно вручную перекодировать всю иерархию типов в битовые поля. Да ещё и не решить проблему указателей на середину структуры (или теперь у Бёма это тоже можно?).
Когда в языке сборщик мусора полностью интегрирован в runtime-библиотеку, он может (и должен) получать и использовать информацию о типах, чтобы точно знать, где указатель, где нет. В C эта интеграция невозможна, сборщик Бёма вынужден догадываться сам и поэтому не гарантирует отсутствия утечек. Т.е., строго говоря, он некорректен.
Ради отсутствия внешних зависимостей и лёгкости встраивания в основную программу на C. Так же сделаны Lua и Wren.
Об этом я много раз говорил, и даже в комментариях под этим постом :) Не поленюсь повторить:
Статическая типизация: делает намерения программиста более ясными, позволяет обнаруживать несовместимости типов ещё на этапе компиляции скрипта и выдавать понятные сообщения об ошибках. Lua - динамически типизированный язык, ошибки типов обнаруживаются лишь случайно во время исполнения скрипта.
Типы данных, совместимые с типами C: позволяют скрипту легко обмениваться структурами данных с основной программой на C/C++, сохраняя при этом раскладку полей структур в памяти. Lua использует типы, совершенно чуждые C, и предлагает громоздкий механизм
userdata.Не совсем понимаю, как они работают. Ведь они должны иметь доступ к типам данных разрабатываемого языка (что я и обозначил "первой проблемой"). Без этого обходится, среди известного мне, только сборщик Бёма, но его принцип действия мне по сей день кажется странным: любая последовательность байт, которая выглядит как указатель, является указателем. Для C сгодится и это, коль скоро программа на C при всём желании не сообщит ничего о типах. Для других языков - сомнительное решение.
Скорее всего так, поскольку там появляются указатели, сборка мусора и таблицы методов. В Umka тоже нельзя.
Ситуация маловероятная, но нет уверенности, что невозможная. Стоит подумать.
Так и задумывалось.
Общее впечатление. Здравый смысл подсказывает, что общие накладные расходы в случае подсчёта ссылок и трассирующей сборки мусора примерно одинаковы, однако при подсчёте ссылок они более равномерно "размазаны" и гарантированно не дают подвисаний. В конце концов, обход потомков, про который я писал, - это практически то же, что делает трассирующий сборщик, только разбитое на мелкие кусочки. А чтобы делать тесты, нужно было реализовать оба варианта. Я этого не делал.
Насколько я понимаю, речь идёт о пустом интерфейсе
interface{}. По опыту практического использования, встречается не очень часто, но за неимением обобщённых типов - несколько чаще, чем хотелось бы.Не совсем понял вопрос. Но во избежание недоразумений подчеркну, что речь идёт не об FFI, позволяющем вызывать любую функцию, а о функциях с заранее оговорённой сигнатурой. Точно так же сделано в Lua: "When we say that Lua can call C functions, this does not mean that Lua can call any C function... As we saw previously, when C calls a Lua function, it must follow a simple protocol to pass the arguments and to get the results." Ну и конечно, из C недоступно то, что относится к подсчёту ссылок.
Это как раз совершенно классическая тема, где я не придумал ничего оригинального. Так же сделан
std::weak_ptrв C++ и всё управление памятью в Swift. Слабый указатель - такой, который при навешивании на объект не меняет его счётчика ссылок. Следовательно, он не мешает довести счётчик ссылок до нуля и уничтожить объект, поэтому сам рискует оказаться висячим. Так что пытаться разыменовывать слабый указатель опасно.Да, полностью самописное. В основном оно сводится к тому, что при присвоении рекурсивно вызывается функция обхода потомков, меняющая их счётчики.
Имеется в виду обращение по висячим указателям, память из-под которых уже очистили? Проблемы были, но только по недомыслию и невнимательности (например, как правильно менять счётчики при вызове
append()для динамического массива).Языком вполне можно пользоваться. Из интересного не готовы замыкания (хотя безымянные функции есть), поддержка Unicode (она работает сейчас ровно настолько, насколько это поддерживает терминал и локаль в C). Обобщённые типы - пока только на дальнем горизонте (их ещё и в Go не сделали).
О преимуществах я говорил. В нише доминирует Lua. По сравнению с ним, имеем раннее обнаружение ошибок типов (с понятным сообщением об ошибке) и хорошую "стыкуемость" типов с типами C: целые/дробные разной длины, массивы, структуры. А скорость компиляции (имеется в виду, в байт-код перед запуском?) - здесь не очень интересный параметр. И кстати, ничего особенного я тут и не заявлял.
Библиотеки пока не особо обширные: мои и сторонние (среди последних есть разбор JSON, но если хотите JavaScript - то, боюсь, с нуля).
Практически нет.
Именно так и сделано. И вот тут как раз было бы интересно понять, насколько это отличается, например, от того, что сделано в Go.
Можно, конечно. И сами создатели не раз говорили об этом и анализировали проистекающие отсюда сложности: https://blog.golang.org/ismmkeynote
Добавлю, что в Umka, как и в Go, не различаются классы и структуры (такое различение мне вообще кажется абсолютно искусственным). Методы навешиваются на структуры. Тогда каким типом должна являться структура: value или reference? Лично мне требуется value - для естественного взаимодействия с C.
Возможны алгоритмы со списками/деревьями, которые на выходе дают число/массив/структуру, которые уже вполне пригодны для передачи.
Не совсем понял. "Список" в узком смысле слова (с указателями) в файле хранить и нельзя. По-любому понадобится замена указателей на файловые смещения. "Список" в широком смысле слова (по сути, массив) передать можно вполне. Umka вовсе не требует наличия заголовка со счётчиком перед каждым куском, на который есть указатель. Возможны указатели на глобальные или стековые переменные, на переменные C. Требование наличия заголовка касается только памяти, выделяемой в куче Umka.
А что такое "общая задача"? Универсальных языков всё равно нет. Я решал на Umka свою задачу, какие-то чешские энтузиасты - свою и т.д. В каких-то задачах Umka удобен, в каких-то - нет. Для меня вот до сих пор поразительно, что предназначенный для сопряжения с C язык Lua имеет типы данных, вообще никак не стыкующиеся с типами C.
Структуры, содержащие указатели - разумеется, нельзя передать. Более того, я в принципе не представляю себе этого хоть в каком-нибудь скриптовом языке, коль скоро в C нет никакого автоматического управления памятью. Так что в таком виде эта "цель" и недостижима.
Но все прочие структуры - передавать можно и нужно. И таких в моей практике было большинство: векторы, матрицы, показания датчиков, наборы настроек. Ср. с использованием
userdataв Lua. Удобство очевидно.Я вижу, вы взялись унижать и оскорблять. Жаль. Ожидал более квалифицированной дискуссии. Особенно с учётом того, что когда-то в далёком прошлом вы, кажется, публиковали достойные материалы.
На оскорбления отвечать не стану. А вот на конкретные замечания не поленюсь ответить, хотя уже много раз это делал.
Именно так. Мне был нужен скриптовый язык, в котором я мог бы перекидывать структуры целиком в C и обратно. Это для меня фактор комфорта. Как и статическая типизация, которая делает намного более ясными намерения программиста и избавляет от огромного числа ошибок, с которыми я сталкиваюсь, например, в Python и ещё более в JS. Сейчас Umka используется у меня на работе в симуляторе динамики трактора.
Упоминание Go, Haskell, Rust, Swift я считаю вообще неуместным, поскольку всё это языки совершенно иного назначения. Остаётся Lua. Ну а преимущества относительно Lua я перечислил выше. Если же вопрос касался не языка в целом, а управления памятью, то моя задача тут не "делать лучше", а "делать достойно". Этого для начала вполне достаточно.
Не совсем понятное замечание. Вас не устраивает подсчёт ссылок как таковой? А что предпочитаете взамен?
Вот уж никогда не знаешь, с какой стороны придёт удар :)
Но согласен, айсберг должен расширяться книзу. На подлинных фотографиях это отчётливо видно. Ну и да, такой айсберг, как у меня, вряд ли бы угрожал кораблям своей подводной частью.
Получается вычислительная сложность, линейно растущая с количеством полей. Ну и если вообразить "матрёшку" вложенных типов, то требуется обратный проход по ней -- изнутри наружу. Такой возможности нет, да и не совсем понятно, как реализовать.
Да. Посмотрите на мой список из четырёх шагов. Первый шаг как раз даёт страницу, второй шаг -- указатель на заголовок, когда страница уже найдена. Вы говорите о втором шаге.
И кстати, статические поля класса выделяются в куче или по фиксированному адресу?