Prolog Use

It is no news that I have just taken a new job. This job has giving me a pretty nice setup (better than my setup at home, at any rate): (2) 24" monitors, next to each other. Everyone who has set up 2 monitors knows the potential problem of setting them up: making the computer realize which monitor is the left or the right can be annoying to fix. Of course, you could just reverse the order of the monitor connections into the computer, but that doesn't work if the two monitors are set up differently (maybe one is sitting vertically instead of horizontally) or if the two monitors are fundamentally different pieces of hardware. I was thinking: Wouldn't it be nice if the monitors themselves would automatically realize where they were in relation to each other?

This got me thinking about the problem. I felt that the most straightforward way for such a system to be set up would be if each monitor had a wireless transmitter/receiver inside of it. Not only that, but if each monitor had two directional antennas, one directed to each side of the monitor (assuming none of the monitors are on top of the others), then each monitor would know the set of other monitors that are on each side of it. However, finding the order (and therefore placement) of the monitors given this information is no easy task.

Or is it? This is a constraint satisfaction problem - the kind that Prolog is really good at solving. (Haskell, too, for what it's worth, but Prolog is a little more suited for this problem). Essentially, there are a set of possible scenarios: all the permutations of orders of the monitors. There are also a set of rules (or predicates) which must be true. Not only are there these predicates, but they all have a specific form: Monitor X is to the left of Monitor Y, and Monitor Y is to the right of Monitor X. Prolog has really good support for predicates, and predicates can even have arguments to them, so the similar form of all of these predicates can be captured in one higher-level predicate.

So, I wrote a prolog program that would solve one particular configuration of the problem. Doing all the actual logic was actually really easy and straightforward: the rightOf() predicate is simply 2 lines of simple recursion. Because of the architecture of Prolog and the fact that free variables can be set or not-set at will, a rightOf predicate is unnecessary: simply switch the free/bound argument to leftOf and it becomes rightOf.

The difficult part was actually getting the program to compile and run just the way I wanted it to. It would be nice if I could compile the Prolog program and tell the compiler to run a specific predicate in the executable (and not run the prolog repl). It turns out that this is much more difficult that you would expect, mostly because the two prolog compilers (gprolog and swipl) act very differently. The gprolog documentation (which sucks, by the way, it took me forever to figure out how to use a directive) said that in order to make the compiled program not run the repl, I needed to specify the --no-top-level flag to the compiler. This flag, however, makes the program do absolutely nothing, as no query gets run. The fix is to include a compiler directive to tell gprolog to run a specific predicate as soon as it loads the file (and, as this predicate is the only thing that prints information, is just as good of a time to run it as any other time). This works just fine.

However, swipl does things very differently. First of all, there is a command line flag you can pass to the compiler and it will compile the program to load in the prolog program, execute a specific directive, and then quit, which is exactly what I want. However, my program still has that compiler directive that makes it run the main predicate as soon as the file is loaded, so using this command line option makes the program run twice - not what I want. Not including this command line option, however, makes the compiler compile in the top level repl, which I want to skip. To get around this, I used the command line argument, but instead of pointing it to the predicate which runs my program, I pointed it to the predicate of "fail". This makes the compilation occur correctly in both compilers. This also has the side effect of the compiler actually running the program, because the compiler loads the program, and the directive tells Prolog to run the program when it's loaded... so compiling the program itself runs it.

Another difficulty was making prolog print out all the possible solutions to the satisfaction constraint problem, instead of just one solution. Doing that actually requires knowledge about how the internal Prolog algorithm works. Prolog will search the space it needs to search, and if it finds a successful state in the space, it will consider that predicate satisfied and stop searching. You (the programmer) can't change that. So, you have to have the predicate find a solution, print it out, and then fail. This makes the algorithm keep searching through the whole tree, because it never successfully satisfies the predicate. What you have, in the end, is a predicate that prints out all the correct answers to your problem, and then fails (because you can't have it fail during the search and then make the overall search successful). It seems like this is the standard architecture for the top-level predicate of your program... Perhaps this is standard practice to turn your program into these top-level predicates that are supposed to fail and then the logic predicates that have semantic meaning. Because of the setup described earlier, Prolog prints out a warning that the directive the compiler ran to generate the file failed. It's a harmless warning, but annoying nonetheless. There is a way to get rid of this, however: after your main predicate, have another predicate after the first main predicate just saying "main.". This makes main always return true (after doing the search), so the predicate the compiler directive calls is successful, and there is no warning.

The benefit of using this Prolog approach is that all of the data for this specific program is contained in one predicate. Everything else in the program is a constant (from one problem of this type to the next).

The system I'm envisioning is a shell script of some kind. It would first call an executable written in C of some program to actually do the device interfacing to simply read in the data from all the monitors. Then a Perl script (or something) could generate the Prolog program. This would be simple for the point above, where all the changing code in the prolog program is contained within one predicate. Then the script would compile the Prolog program and then run it. The operating system could then read in the output of the script (which is just the output of the Prolog program) and set up the order of the monitors accordingly. If there are 0 lines of output, there are conflicting results, and the user will have to configure the location of their monitors by hand. If there is one result, it should be chosen. If there are more than one result, a menu could be displayed with all of the possible setups.

There aren't very many domains where I've seen Prolog be a suitable candidate to solve a real problem. This is interesting, perhaps because (I believe) it is on.

My code can be found here.