Goal reordering

I’m using: SWI-Prolog version 8.0.3 for x64-win64

Suppose I want Prolog to automatically reorder (some) goals according to a set of rules, such as in an attempt to optimize code. Where would I start? I suspect that altering the source code for SWI-Prolog might yield more efficient results, but also be rather harder, and more likely to break things. Vs, I suspect there’s some predicate or other you could wrap a chunk of code in, which could list variables / reorder goals / selectively evaluate sub-expressions / etc. I don’t know what questions to ask, if the former is the way to go, but if the latter is the way to go, I suspect I’d need predicates to do things such as the following:

  1. List variables
  2. Check for choice points
  3. Evaluate an expression by one step (i.e., replace a predicate’s head with its body, but leave the body untouched, for further examination)
  4. Check for (and deconstruct) and/or (it looks like (X,Y) = Expression and (X;Y) = Expression might suffice)
  5. Deconstruct a CLP FD/R/Q expression (they seem more complicated than combinations of and/or)
  6. Reorder an expression (maybe can be derived from #4)
  7. Maybe detect order-dependent operations, like cut?

Any help on any of these, or tips in general? (Or, if messing around with SWI-Prolog’s source is likely to be vastly faster, any hints on where to start with that?)

Prolog can treat prolog source as just terms which you can analyze and manipulate like any data. That is certainly much easier than diving into the C source code. Once you have rewritten a chunk of source code to suit your objectives, you can generate a new source file, assert predicate clauses, or just call your text to get it executed.

There are Prolog facilities to do any of your 7 items, except there is no high-level logic to make this easy. You will probably have to simply work out the logic of your requirements and code that as basic logic.

Let me restate: It is very easy to read in Prolog code, work with the code, and generate new code using Prolog. Getting your program to understand that code is entirely on you. Start in the manual looking at the definition of clause/2, and related stuff.

1 Like

I presume you have some background in compilers, because this can get complicated very quickly, even for a “simple” language like Prolog. (And don’t forget to run expand_term/2 before processing.)

You might want to look at the Aquarius compiler https://www.info.ucl.ac.be/~pvr/aquarius.html – it even includes source code. I also suggest looking at the EDCG pack, which was used to write the compiler.

You might also want to look at the Interpreters chapter in O’Keefe’s Craft of Prolog.

1 Like