2

If you write a compiler in pure Prolog (no extra-logical bits), will it work as a decompiler also?

(A book I was reading opined on this, but I wonder if anyone has actually tried it)

MWB
  • 11,740
  • 6
  • 46
  • 91

2 Answers2

2

I once wrote the equivalent of cdecl.org as a reversible program. It was a bit tricky, but I demonstrated that it could be done. (Somewhere in a pile of papers is the source code; one of these days, I hope to publish it on github.) The code was 2 or 3 times as compact at some existing code that used tools such as yacc/lex (bison/flex).

For something like cdecl -- where you're translating between char ** const * const x and declare x as const pointer to const pointer to pointer to char, compiling/decompiling makes sense. But what does it mean to translate from arbitrary machine code to source code? Even translating between some IR and source code doesn't seem to make a lot of sense.

Peter Ludemann
  • 985
  • 6
  • 8
  • It's not really difficult to translate from machine code to a high level language. Doing it in the simplest way will create source code which not easy to read and understand, but a valid program with the same behavior. (Though it might be easier if we go with "machine code in the set of possible compiler outputs" rather than "arbitrary machine code".) – aschepler Dec 16 '20 at 05:38
  • aschepler The Theoretical IT way to decompile would be 1) generate a high-level language header that interpretes the machine code (whatever the machines is ... register, stack, lambda-reducer, turing machine) 2) append machine code underneath in an array. 3) Lunchtime! – David Tonhofer Dec 16 '20 at 11:42
  • 1
    @aschepler wrote "It's not really difficult to translate from machine code to a high level language." I've written a couple of disassemblers, and I strongly disagree with that, at least if you want to be able to reconstruct the variable names. – Peter Ludemann Dec 17 '20 at 19:51
  • 2
    @DavidTonhofer Your comment gave me a flashback of grad school seminars. Anyway: "Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy." - Alan Perlis – Peter Ludemann Dec 17 '20 at 19:54
1

This question needs to be much more precise, as we don't know what a "compiler" is (an extraneous-information-dumping transformation from a graph - the program in language 1 - to another graph - the algorithmically equivalent graph in language 2, I suppose). It also not clear what "no-extra logical bits implies". If yo get rid of these, what kind of compilers can you still build?

Seen this way, compilation looks like pure deduction (Prolog running forward, or CHR) while decompilation looks like possibly very hard search (you will get a program among the gazillion possible ones but it won't be pleasant too look at and in no way resemble the one you had earlier). Someone who as a toolbox of theorems freshly in his mind can certainly say more.

But I would say not automagically, no. For one, there will be no guarantee that an infinite "recursion on the left" loop won't appear when "decompiling".

David Tonhofer
  • 14,559
  • 5
  • 55
  • 51
  • 1
    "you will get a program among the gazillion possible ones" On the one hand, this is true. On the other hand, Prolog is a language where we routinely write programs that (a) can enumerate a sequence of a gazillion solutions, and (b) with some care, do this in a "fair" way such that the simplest solutions come first. So yes, if the compiled program is `add a, b, c`, then all of `plus(a, plus(b, c))`, `plus(a, plus(b, plus(c, 0)))`, `plus(a, plus(b, plus(c, plus(0, 0))))` etc. will be valid decompiled versions, but the best one will come first. – Isabelle Newbie Dec 15 '20 at 13:29
  • That said, I agree that the question is too broad etc. – Isabelle Newbie Dec 15 '20 at 13:30
  • @IsabelleNewbie But what is the "best" when decompiling? When you look at decompiled Java code for example, it sometimes makes no sense. Multiple times worse when the compilate was passed through obfuscator, A Prolog decompiler, same as a Java decompiler, has to make a decision ... "best" sounds suspiciously NP-hard. – David Tonhofer Dec 15 '20 at 15:02
  • *"what kind of compilers can you still build?"* Any kind, I think, based on the Turing-completeness of pure Prolog. Just start with `compile(SourceAsList, AssemblyAsList) :- ` and keep tweaking it until it works. – MWB Dec 16 '20 at 10:52