Если вы напишете компилятор на чистом Прологе, будет ли он работать и как декомпилятор?
Если написать компилятор на чистом Прологе (без лишних логических битов), будет ли он работать как декомпилятор?
(Книга, которую я читал, высказалась по этому поводу, но мне интересно, пробовал ли кто-нибудь это на самом деле)
Я проголосовал за это близко по тем же причинам, что и Дэвид.
Я согласен с закрытым голосованием. Вопрос интересный, поэтому я бы посоветовал @MaxB задать его еще раз более конкретно. Может быть, написать игрушечный компилятор и попросить помощи, чтобы заставить его работать как декомпилятор?
@DavidTonhofer на первый взгляд очень похож на лямбда-пролог.
@MaxB Да, это основная идея.
Ответы 2
Этот вопрос должен быть гораздо более точным, так как мы не знаем, что такое «компилятор» (преобразование избыточной информации из графа — программы на языке 1 — в другой граф — алгоритмически эквивалентный граф на языке 2). , Я полагаю). Также неясно, что означает «отсутствие дополнительных логических битов». Если вы избавитесь от них, какие компиляторы вы все равно сможете создавать?
С этой точки зрения, компиляция выглядит как чистая дедукция (пролог вперед, или CHR), в то время как декомпиляция выглядит как, возможно, очень трудный поиск (вы получите программу среди миллиона возможных, но это будет не очень приятно смотреть и никоим образом похожа на ту, что была у вас раньше). Тот, у кого в голове свежий набор теорем, безусловно, может сказать больше.
Но я бы сказал не автоматически, нет. Во-первых, не будет никакой гарантии, что бесконечный цикл «рекурсия слева» не появится при «декомпиляции».
"Вы получите программу среди миллионов возможных" С одной стороны, это правда. С другой стороны, Пролог — это язык, на котором мы регулярно пишем программы, которые (а) могут перечислять последовательность из миллиона решений и (б) с некоторой осторожностью делать это «справедливым» способом, так что самые простые решения идут первыми. . Так что да, если скомпилированная программа add a, b, c, то все plus(a, plus(b, c)), plus(a, plus(b, plus(c, 0))), plus(a, plus(b, plus(c, plus(0, 0)))) и т. д. будут действительными декомпилированными версиями, но лучшая из них будет первой.
Тем не менее, я согласен, что вопрос слишком широк и т.
@IsabelleNewbie Но что является «лучшим» при декомпиляции? Например, когда вы смотрите на декомпилированный код Java, это иногда не имеет смысла. В несколько раз хуже, когда компиляция прошла через обфускатор, декомпилятор Prolog, так же как и декомпилятор Java, должен принять решение ... «лучший» звучит подозрительно NP-сложно.
какие компиляторы вы еще можете построить?" Любой вид, я думаю, основанный на полноте по Тьюрингу чистого Пролога. Просто начните с compile(SourceAsList, AssemblyAsList) :- и продолжайте настраивать его, пока он не сработает.
Однажды я написал эквивалент cdecl.org в виде обратимой программы. Это было немного сложно, но я продемонстрировал, что это можно сделать. (Где-то в куче бумаг лежит исходный код; на днях я надеюсь опубликовать его на github.) Код был в 2 или 3 раза компактнее некоторого существующего кода, использующего такие инструменты, как yacc/lex (bison/ флекс).
Для чего-то вроде cdecl — когда вы переводите между char ** const * const x и declare x as const pointer to const pointer to pointer to char, компиляция/декомпиляция имеет смысл. Но что означает перевод произвольного машинного кода в исходный код? Даже перевод между некоторым IR и исходным кодом не имеет особого смысла.
Переводить с машинного кода на язык высокого уровня несложно. Делая это самым простым способом, вы создадите исходный код, который нелегко читать и понимать, но это действующая программа с таким же поведением. (Хотя было бы проще, если бы мы использовали «машинный код в наборе возможных выходных данных компилятора», а не «произвольный машинный код».)
aschepler Теоретический ИТ-способ декомпиляции будет заключаться в следующем: 1) сгенерировать заголовок языка высокого уровня, который интерпретирует машинный код (какими бы ни были машины... регистр, стек, лямбда-редуктор, машина Тьюринга) 2) добавить машинный код внизу в множество. 3) Время обеда!
@aschepler написал: «Перевести машинный код на язык высокого уровня несложно». Я написал пару дизассемблеров и категорически с этим не согласен, по крайней мере, если вы хотите восстановить имена переменных.
@DavidTonhofer Ваш комментарий напомнил мне о семинарах в аспирантуре. В любом случае: «Остерегайтесь тьюринговой ямы со смолой, в которой все возможно, но ничто интересное не является легким». - Алан Перлис
Несвязанный: вы взглянули на lix.polytechnique.fr/~dale/papers/apal91.pdf — «Единообразные доказательства как основа логического программирования»