LINQ does Logic?
Each generation of technologists seems to go through a more-or-less heavy infatuation with it, investing in a more-or-less serious dalliance. When the affair is over, the lover parts with a mix of disappointments and fruitful spin-offs like Theorem Proving, Reasoning Over Knowledge, Intelligent Agents, the Semantic Web, and more.
In the early 80’s, Japan, Inc. lost hundreds of millions on the Fifth Generation Project ,building parallel Prolog machines. One aspect of the project’s failure was overreach: Prolog was used for every aspect of the computer, including its operating system. Stretching logic programming to fulfill the requirements of imperative programming entailed so many compromises and complexities that even devotés became skeptics in the end.
Ten years later, Prolog, as alluring a courtesan as ever, enticed another application, this time successful, and, ironically enough, in an operating-system kernel. Windows NT has an enormous problem to solve: booting up in the presence of driver conflicts. The problem is enormous because the number of possible hardware and device-driver configurations in a PC is astronomical (or combinatorial, if you prefer, since PCs are built from combinations of independently purchased parts like motherboards, network interface cards, I/O controllers, and more, and each one has multiple possible drivers with idiosyncratic dependencies on other components and drivers). It’s infeasible to store a boot-order list for every possible configuration. Instead, conflict information must be stored in a compact list of facts and rules.
Well, anyone who had ever glimpsed the ankle of Prolog knew exactly where to turn, since that’s what Prolog does at heart: reason over facts and rules. One of the world’s most widely distributed and successful operating systems shipped with a public-domain prolog interpreter in the kernel and a script that resolves device-driver conflicts.
The current generation of technologists is hearing the siren song again, this time in the context of ginormous web-based social and knowledge graphs of entities, relationships, intents, plans, and actions. Let’s give logic programming another look and see whether our old friend Prolog is still capable or whether new approaches like LINQ and term-rewriting can and should take its place. This is the first post in a series of investigations into alternatives. We’ll begin by resurrecting the Prolog interpreter that Windows NT used and recapitulating its samples in other forms, namely with LINQ and with term-rewriting. We’ll progress into more modern scenarios such as fantasy sports, choosing constrained entertainment options, and satisfying exotic trading specifications.