Alexander
хотя если равенство в синтаксическом смысле
Alexander
Да норм
Vladislav
В синтаксическом конечно
Ilya
Да не, про завтра я шучу
Vladislav
Синтаксически это просто AST сравнить, можно еще альфа-эквивалентность добавить для порядочности.
Vladislav
Я не говорю, что это невозможно. Я говорю, что смелое начинание
Vladislav
Спрашивать про то, поможет ли тут AST, это как спрашивать, в какой цвет красить свой космический корабль
Vladislav
В белый крась, а дальше удачи 🙂
Ilya
Спасибо)
Anonymous
@paul_khuzhin будет жить. Поприветствуем!
Vladislav
Возьмем такую программу на JS:
function f(a) {
for (;;) {}
}
Используем твой алгоритм, чтобы сравнивать другие программы с этой.
Ilya
Vladislav
Значит, твой алгоритм может определить, завершаются ли те другие программы за конечное число шагов.
Vladislav
Потому что если он выдал true, значит не завершаются (и эквивалентны бесконечному бесполезному циклу).
Vladislav
Если выдал false, значит завершаются (либо не эквивалентны по другой причине, например что-то на экран выводят в процессе вычислений, но это не интересно и не меняет результата).
Vladislav
Так что теперь я убедил себя, что затея в полной общности невозможна.
Ilya
Подскажите, пожалуйста, в какой юрисдикции выгоднее платить налог с Millenial Prize?
Ilya
Vladislav
Я же говорю, что это не меняет результата.
Vladislav
Возьмем подмножество JS, в котором убрали console.log и глобальные переменные. Функции остались только чистые. Твой алгоритм все еще применим к этому подмножеству.
Vladislav
Если он работает на всём JS, то и на подмножестве будет работать
Vladislav
Соответственно на этом подмножестве он для любой функции определит, завершается ли она за конечное число шагов.
Vladislav
Так как это является решеним halting problem, а ее неразрешимость доказана, то из этого следует точный вывод, что твой алгоритм не может работать на весь JS
Vladislav
Может быть он может работать для языков, где все функции завершаются и трюк с бесконечным циклом не прокатит.
Ilya
Vladislav
То есть на бесконечном цикле твой алгоритм будет исключение выкидывать?
Vladislav
Вместо метрики эквивалентности
Vladislav
Типа, неподдерживаемое помножество JS
Ilya
Можно захардкодить эвристику определения бесконечных циклов, и даже выдавать степень похожести 1.0 для любой пары функций, инициирующих бесконечный цикл
Vladislav
Тогда ты тоже halting problem решил, потому что можно запустить твой алгоритм и узнать, завершается какая-то программа или нет, судя по тому, выбросил ты исключение или нет.
Vladislav
Ты как только сказал слово “эвристика” ты уже подразумеваешь, что будут несовершенные результаты (ложно-положительные или ложно-отрицательные).
Vladislav
А значит просто соглашаешься с моим изначальным утверждением, что любой такой алгоритм иногда ложные результаты выдаст
Ilya
К тому же, это не доказывает невозможность "примерного" решения, т. е. какой-то апроксимации. Люди ведь думают, что могут определить эквивалентность двух функций. Значит, какое-то решение тут возможно
Vladislav
Так с этого начался разговор!
Ilya
Vladislav
> Можно придумать алгоритм, который сравнивает, но он точно будет давать ложные результаты (ложно-отрицательные точно, когда две функции одинаковы, а алгоритм не смог это увидеть).
Vladislav
Вот мое утверждение, с которого мы начали.
Vladislav
Если мы тут согласны, то мы согласны.
Vladislav
Поскольку я такой алгоритм точно могу назвать.
compare _ _ = False
Vladislav
А дальше можешь улучшать постепенно. Синтаксическая проверка, эвристики разные, и т.д.
Ilya
Да, я его тоже уже нашел. Но я не нашел место, где я бы это отрицал) Вопрос только в том, как часто алгоритм будет ошибаться. Может это будет в 0.1% случаев
Vladislav
Но до идеала не доведешь
Ilya
(его — утверждение)
Vladislav
Ну не то чтоб отрицал, скорее так
> В чем фундаментальное ограничение? Я пока не понимаю.
Поэтому я попытался подумать и назвал его. Halting problem это фундаментальное ограничение
Vladislav
0.1% не знаю насколько трудно, но допустим реально, 0% нереально.
Ilya
Но до идеала не доведешь
Я просто хотел сделать open source проект на хаскелле, и делать что-нибудь тривиальное мне было не интересно. Кто же виноват, что мне попалась такая интересная задачка
Зигохистоморфный
Зигохистоморфный
Зигохистоморфный
Vladislav
Да я уже понял, что там вместо этого halting problem решена. Хотя из этого и P=NP следует, ex falso 😁
Зигохистоморфный
так можно утверждать, что уравнение Навье-Стокса тоже решено, ибо есть куча частных решений в численных методах
Vladislav
Это утверждение я не понял.
Зигохистоморфный
когда возникают парадоксы?
бесконечные рекурсии (нарушено правило выхода или правило входных параметров в новый виток рекурсии), исключения и прочее
Vladislav
Не следует. Дальше в разговоре выяснили
Anonymous
я не то, чтобы прям очень глубоко в теме, но саму формулировку проблемы понимаю (по крайней мере, мне так казалось доселе).
Anonymous
а, ок
Vladislav
Точнее, если следует, то не по той причине, которая у меня была на уме.
Vladislav
Поэтому я ее и озвучивать не стал.
Anonymous
все, тогда все сходится, а то я подумал, что я что-то критически не понимаю, если следует и прям интересно стало, че как
Anonymous
спасибо
Vladislav
Я думал о том, что для любой NP программы можно будет перебором строк найти P эквивалент.
Vladislav
Но потом понял, что этот поиск не обязан завершиться
Anonymous
А значит просто соглашаешься с моим изначальным утверждением, что любой такой алгоритм иногда ложные результаты выдаст
Любой такой алгоритм уже хотя бы потому не существует, что можно взять любые две фукнции, хотя бы одна из которых (назовем ее f) впадает в бесконечный цикл хотя бы при каком-нибудь входном параметре x, и попытаться их сравнить. По определению, на x это будет невозможно. Чтобы избежать этого, потребовалась бы заранее выяснить, что f x не впадет в бесконечный цикл, но в общем случае, как и звестно, это невозможно. Как-то так.
Vladislav
Возьмем такую программу на JS:
function f(a) {
for (;;) {}
}
Используем твой алгоритм, чтобы сравнивать другие программы с этой.
Vladislav
К этому выводу я в итоге тоже пришел
Anonymous
Хотя справедливости ради - есть немало вполне распространненых на практике частных случаев, когда анализ кода (и приведение дерева выражений к "нормальнйо форме") вполне работают.
Anonymous
но это прям бомбическая задача. анализаторы кода, нормализтора, полный гешефт короче.
Anonymous
а выхлоп не то, чтобы уже слишком полезынй
Зигохистоморфный
Anonymous
да и потом - возьми функцию от int32. 2^32 степени сравнений. удачи.
Anonymous
ключевое слово частных - это не приемлемо
почему? программирование - инженерная дисциплина, очень даже приелемы с этой точки зрения. математически частные случае тоже принимаются, но разумеется как частные случае, а не общее правило.
Anonymous
но вот какая-то тихая интуиция внутри подсказывает мне, что это проблема изоморфизма графов.
Anonymous
хотя, вроде сходится. дерево выражений есть граф.
Anonymous
или нет, не знаю, слишком поздно уже.