Comments 24
А скажите еще что-нибудь на умном :)
Некоторые языки страдают от недостатка оптимизаций при компиляции, возможно ли описать некоторые общие правила которые будут переносимы между разными компиляторами?
Тем не менее, статья набирает плюсы. Как-то даже грустно становится.
Хотя, если подумать, то для лабораторки первого семестра первого курса вполне себе нормальный туториал как делали предки «в далёкой-далёкой галактике, давным-давно» и как делать не нужно. Особенно в контексте запуска 4х терминалов и проверки работоспособности.
Кстати, замечу, что лет 20-25 назад подобная тема могла потянуть даже на курсач/итоговую лабораторку в постсоветском университете, если делать по реальной сети, с планированием оптимальной нагрузки на узлы и прочим.
Но в 2022 году — это уже грустновато выглядит.
Как ни странно, этот коммент сильно понятнее, чем исходная статья. Я так и не понял, что автор хочет сверх "давайте представим алгоритмы деревьям", что, как упомянул Kroleg, уже давно интенсивно применяется, и тем более при чем тут Erlang. Да, акторная модель Erlang значительно опередила свое время, но это не отменяется того факта, что распределенную систему на Erlang может быть очень сложно писать.
Дерево операций (из AST) разворачивается в промежуточное представление SSA-Form, проходит ряд анализов, оптимизаций, раскрасок и SSA превращается в код целевой машины, который может быть чем угодно, от машинного кода процессора до параллельно работающей сети на FPGA
Проблема в том, что традиционные машины Тьюринга сильно ограничены в доступных инструкциях. Например, в логических схемах очень часто реагируют на изменение состояния. Изменение состояния -- это точно такая же информация, но классическая машина Тьюринга абсолютно слепа к изменению состояния, и по этой причине очень много теряет. Как правило, передачу сигналов от одного агента приходится делать через прерывания, спинлоки, функции кооперативной многозадачности ОС, то есть, через кривые костыли и то же состояние.
Еще одна похожая проблема машинки Тьюринга -- это опора на строго фиксированные состояния входных параметров, то есть, упомянутое SSA. Команда должна для неизменяемых входных параметров выдавать по строгому алгоритму результат -- но что делать, если параметры изменились? Если результат уже не нужен? Большинство lock-free алгоритмов в современных C/C++/Pascal/etc строятся примерно по одному принципу:
while not целевое_состояние_достигнуто() do
идти_к_целевому_состоянию();Причем, при выполнении сложных вложенных операций используется внешний цикл:
while not целевое_состояние_достигнуто() do
if not идти_к_целевому_состоянию1() then
continue;
if not идти_еще_дальше() then
continue;И даже процессоры внутри используют похожие механизмы, но на уровне ЯП и их компиляторов у нас почему-то одно сплошное SSA и стэк-машина.
но классическая машина Тьюринга абсолютно слепа к изменению состояния, и по этой причине очень много теряет. Как правило, передачу сигналов от одного агента приходится делать через прерывания, спинлоки, функции кооперативной многозадачности ОС, то есть, через кривые костыли и то же состояние.
Погодите, откуда взялись прерывания в классической машине Тьюринга?
Еще одна похожая проблема машинки Тьюринга — это опора на строго фиксированные состояния входных параметров, то есть, упомянутое SSA.
Откуда взялось SSA в машите Тьюринга?
Погодите, откуда взялись прерывания в классической машине Тьюринга?
Потому что классическая машина Тюринга -- это бесполезный конь в вакууме, потому на самом деле ни одно современное бытовое вычислительное устройство не может быть смоделировано машиной Тьюринга. Даже контроллер стиральной машинки или микроволновки.
Откуда взялось SSA в машите Тьюринга?
SSA -- это популярная абстракция для компиляторов в код машины Тьюринга, чуть повысокоуровневее, чем стэк-машина. Так или иначе, SSA намного ближе к Тьюрингу, чем к FPGA логике.
Вы не объяснили откуда взялись прерывания в классической машине Тьюринга.
SSA — это популярная абстракция для компиляторов в код машины Тьюринга
Приведите пример хоть одного полулярного компилятора из SSA в код машины Тьюринга.
чуть повысокоуровневее, чем стэк-машина
С чего бы регистровой машине быть высокоуровневее стековой? Вообще-то это абстракции одного уровня.
Вы не объяснили откуда взялись прерывания в классической машине Тьюринга.
Естественно, никто не программирует на самой машине Тьюринга -- я имел в виду Тьюринг-эквивалентную штуку, алгоритмы с которой могут быть выполнены на машине Тьюринга, и наоборот, алгоритмы с машины Тьюринга могут быть выполнены на той "машине Тьюринга", которую я имел в виду. В этом как бы и был смысл создания определения "машина Тьюринга" - на этой машине никто не программирует ведь, программируют на ее аналогах.
Приведите пример хоть одного полулярного компилятора из SSA в код машины Тьюринга.
LLVM.
С чего бы регистровой машине быть высокоуровневее стековой? Вообще-то это абстракции одного уровня.
Регистровая машина -- да, того же уровня. SSA -- нет, не того же уровня, а выше. SSA с натяжкой можно назвать функциональной формой записи, то есть, описание взаимоотношений аргументов и результата без побочных эффектов. Конечно, с натяжкой потому, что на самом деле эти условия далеко не всегда выполняются, но иногда все-таки выполняются.
Если вы под "машиной Тьюринга" имели в виду любую машину, которая эквивалентна машине Тьюринга — то вот это утверждение всё ещё не имеет смысла:
Еще одна похожая проблема машинки Тьюринга — это опора на строго фиксированные состояния входных параметров, то есть, упомянутое SSA.
"Тьюринг-эквивалентных штук" существует множество, и далеко не для всех из них SSA имеет смысл.
Было бы очень не плохо развернуть свои рассуждения в статью, расшифровав все аббревиатуры и смысловые умолчания. Например, мне было бы крайне интересно понять последнее:
Давайте лучше подумаем как эффективно закодировать промежуточное представление в SSA форме.
Давайте лучше подумаем как эффективно закодировать промежуточное представление в SSA форме.
SSA в виде своего подмножества "логические связи между данными" является очень крутой штукой в плане свободы оптимизации и натягивания на самые разные исполнители. Проблема в том, что это же и наиболее ограниченная форма представления, потому SSA в прикладном программировании неизбежно скатывается в операции над переиспользуемыми ячейками и таким образом в рекуррентность, которую уже намного сложнее понимать. Как расширить SSA таким образом, чтобы скатывание в переиспользование и рекуррентность наступало как можно позже, или как наделить SSA такими промежуточными выразительными средствами, чтобы они были и предсказуемы и достаточно мощны -- это и есть хорошие сложные вопросы.
Конечно, если автор оригинальной цитаты не имел банальное "как оттранслировать исходники в хороший SSA" -- потому что лично я не вижу никакой перспективы в старых императивных языках, попытки их вытянуть на современный уровень приводят к тому, что с каждым годом эффект от этих усилий становится меньше и меньше.
Честно говоря, теоретически мало что понял. А вопрос простой и лежит в прагматической плоскости: как устранить семантический разрыв? Если его решите, я первый как практикующий программист Вам буду очень благодарен.
Испытываю стыд.
Если вы уже дерево используете, нафига польская запись? Обычная человеческая на дерево ровно так же ложится.
А зачем использовать "обычную человеческую"? Тут я расписывал, что с ней не так:
Вопрос справедливый. Нужно было показать, что теоретически имеем две стороны одной медали, но прямой способ после свертки и развертки приводит к дереву, которое более понятно человеку.
Согласен, что не проработан вопрос, как ложится человеское мышление на дерево.
"Это выдвинутый без доказательства фундаментальное положение теории алгоритмов [8] принималось научным сообществом неукоснительно из поколения в поколение"
Что значит - принимался? никаких конструкций, способных вывести за пределы возможностей МТ, не удалось найти, вот и все. Кстати, есть эквивалентный тезис Черча.
"парадигма машины Тьюринга была нарушена в архитектуре фон Неймана"
Парадигма-то, м.б., и была нарушена, только ничего нового это не дает же.
Из Википедии: "К 1963 г. Гёдель отказался от рекурсии Хербранда-Гёделя и λ-исчисления в пользу машины Тьюринга как определения «алгоритма» или «механической процедуры» или «формальной системы»". Примем это как факт.
Честно говоря, мне не понятно, почему, например, алгоритмы модели акторов не представимы в форме машина Тьюринга, а она все еще считается определением «алгоритма». Может Гёдель в 1963г. был не прав?
А все остальное справедливо!
Сильно не вчитывался, но похоже автор изобретает dataflow архитектуру:
Всегда думал, что кто-то уже бежит впереди... А почему об этой архитектуре почти нет информации и есть ли русскоязычные публикации? Вопросы без ирониии:-)
Там вроде проблемы с координацией начинаются. В синхронной архитектуре у тебя все узлы гарантированно принимают актуальное состояние одновременно миллиарды раз в секунду. В асинхронной получается разброд и шатание с микро-утечками тока, которые надо компенсировать, перепадами напряжения и тд. Короче, схемотехника становится сложнее, а значит работа медленнее. Но я тут не специалист, не знаю.
Вы пишите про dataflow архитектуру, а такое впечатление, что это про модель акторов. Я не стал глубоко разбираться (у меня же не академический, а прагматический интерес), но там авторы отказались от единого времени, т.к. невозможно синхронизироваться посылками сообщений. Похоже, проблема везде одинаковая.
Анти–Тьюринг