LINQ does Logic?

It’s been two generations since Logic Programming hit the scene with Prolog. Logic programming is a seductive concept, holding out the promise of squaring the circle of Artificial Intelligence.

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 ProvingReasoning Over KnowledgeIntelligent 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.


~ by rebcabin on August 22, 2012.

3 Responses to “LINQ does Logic?”

  1. […] the zeroth post in this series, we proposed to revisit the curious and alluring Prolog as an approach to computing over knowledge […]

  2. By Win7 for policy management in system console this was changed up to a version of the CSP from Microsoft Solver Foundation, which resolves problems of conflict in configurations pushed out to all machines by corporate IT.
    There were real advances in constraint solving during the 90’s and naughts, leaving the old Prolog engines far behind. It is impressive how capable and flexible modern solvers are. For MSF we used a language much more like Mathematica than Prolog, though there are obviously shared roots.

  3. Thanks for the link to the NT Prolog interpreter! It’s a great read. This blog is awesome!!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: