May 19 2010

The Prolog Story

Published by at 8:10 pm under Technology   

I’ve told this story in person dozens of times, it’s time to write it down and share it here. I’ve again experimentally recorded a video version (below), which you can view on a non-Flash device here.

I know a little Prolog, which I learned in college – just enough to be dangerous. Armed with that, and some vigorous just-in-time online learning, I used Prolog in a production system a few years ago, with great results. There are two stories about that woven together here; one about the technical reasons for choosing this particular tool, and the other about the business payoff for taking a road less travelled.

In 2004 (or so) I was working on a project for an Oasis Digital customer on a client/server application with SQL Server behind it. This application worked (and still works) very well for the customer, who remains quite happy with it. This is the kind of project where there is an endless series of enhancement and additions, some of them to attack a problem-of-the-moment and some of them to enrich and strengthen the overall application capabilities.

The customer approached us with a very unusual feature request – pardon my generic description here; I don’t want to accidentally reveal any of their business secrets. The feature was described to us declaratively, in terms of a few rules and a bunch of examples of those rules. The wrinkle is that these were not “forward” rules (if X, do Y). Rather, these rules describe scenarios, such that if those scenarios happen, then something else should happen. Moreover, the rules were are on complex transitive/recursive relationships, the sort of thing that SQL is not well suited for.

An initial analysis found that we would need to implement a complex depth/breadth search algorithm either in the client application or in SQL. This wasn’t a straightforward graph search, though, rather that part was just the tip of the iceberg. I’m not afraid of algorithmic programming, Oasis Digital is emphatically not an “OnClick-only” programming shop, so I dug in. After spending a couple of days attacking the problem this way, I concluded that this would be a substantial block of work, at least several person-months to get it working correctly and efficiently. That’s not a lot in the grand scheme of things, but for this particular customer, this would use up their reasonable-but-not-lavish budget for months, even ignoring their other feature needs.

We set this problem aside for a few days, and upon more though I realized that:

  • this would be a simple problem to describe in Prolog
  • the Prolog runtime would then solve the problem
  • the Prolog runtime would be responsible for doing it correctly and efficiently, i.e. our customer would not foot the bill to achieve those things.

We proceeded with the Prolog approach.

….

It actually took one day of work to get it working, integrated, and into testing, then a few hours a few weeks later to deploy it.

The implementation mechanism is pretty rough:

  • The rules (the fixed portions of the Prolog solution) are expressed in a prolog source file, a page or two in length.
  • A batch process runs every N minutes, on a server with spare capacity for this purpose.
  • The batch process executes a set of SQL queries (in stored procs), returning a total of tens or hundreds of thousands of rows of data. SQL is used to format that query output as Prolog terms. These stored procs are executed using SQL Server BCP, making it trivial to save the results in files.
  • The batch process run a Prolog interpreter, passing the data and rules (both are code, both are data) as input. This takes up to a few minutes.
  • The Prolog rules are set up, with considerable hackery, to emit the output data we needed in the form of CSV data. This output is directed to a file.
  • SQL Server BCP imports this output data back in to the production SQL Server database.
  • The result of the computation is thus available in SQL tables for the application to use.

This batch process is not an optimal design, but it has the advantage of being quick to implement, and robust in operation. The cycle time is very small compared to the business processes being controlled, so practically speaking it is 95% as good as a continuous calculation mechanism, at much less cost.

There are some great lessons here:

  • Declarative >>> Imperative. This is among the most important and broad guidelines to follow in system design.
  • Thinking Matters. We cut the cost/time of this implementation by 90% or more, not by coding more quickly, but by thinking more clearly. I am a fan of TDD and incremental design, but you’re quite unlikely to ever make it from a handcoded solution to this simply-add-Prolog solution that way.
  • The Right Tool for the Job. Learn a lot of them, don’t be the person who only has a hammer.
  • A big problem is a big opportunity. It is quite possible that another firm would not have been able to deliver the functionality our customer needed at a cost they could afford. This problem was an opportunity to win, both for us and for our customer.

That’s all for now; it’s time for LessConf.

Post to Twitter Post to Facebook Post to Reddit

If you found this post useful, please link to it from your web site, mention it online, or mention it to a colleague.

13 responses so far

13 Responses to “The Prolog Story”

  1. Hans says:

    likes(hans, prolog_story).

  2. Nice :-)

    I occasionally find problems like that, which are far easier to solve in a declarative style than anything else.

    There’s been many a time when I’ve built myself a little continuation-passing micro-prolog in whatever the current-default-language happens to be since it’s easier than reformulating the problem in another way (see http://www.perlmonks.org/?node_id=193649 for a naive Prolog-in-Perl implementation for example!)

  3. That’s a great story.

    As a Prolog programmer turned SQL guy, I’ve often wanted to see both languages working together on a common problem.

    It would be really nice to call Prolog directly from .NET but I’ve not seen that done.

  4. Marc Chung says:

    Which Prolog implementation did you go with?

  5. Romy says:

    Well played sir, I’d also like to know what implementation you went with.

  6. Thanks for sharing your experience, I was going to experience the same thing in the near future; Helped my a lot, thanks!

  7. Danilo says:

    Very interesting article!

    I developed an home automation system (EgidaLive project). Some years ago I thought that a good home automation system must manage rules. I choose .Net (I’m listening some comments… but the system functions very well!)
    When you think about rules you think Prolog. I searched a .Net implementation but I didn’t succedeed to find one. I found only Mercury, but it was impossibile to use in a real system. So I developed a rule manager that takes a XML file and manages all the rules. You can imagine an infinite numbers of scenarios: “when something happens than … “. The system integrates sensors, ligths (also leds), cameras, music, flagrances, audio and video communications, …

    I’d like to introduce something like a Prolog engine in order to build a smarter system. I’ve just launched a Google search and I’ve found http://sourceforge.net/projects/cs-prolog/

    Is someone interested in talking about problems like these ones?

  8. Ed says:

    Very interesting story! I’ve been very interested in this subject. I am a student at a computer science college and this semester we studied Expert systems and knowledge based decision support system and one of the options (“languages”) was Prolog (Turbo Prolog). As a case study i developped a C# app that allows the user to create rules (simple or chained) and then asks a series of questions and based on those rules offers the answer. I just wanted to ask do you think it is best (speed, performance wise) to use Prolog or to create my own “language” that does almost the same thing (rules evaluation) that runs on top of .Net. Thanks!

  9. Matt Borack says:

    Wikipedia’s article on Prolog links to P#, which works with .Net

    http://en.wikipedia.org/wiki/P_Sharp

    http://homepages.inf.ed.ac.uk/stg/research/Psharp/

    Hope this helps.

  10. Danilo says:

    My personal opinion is that… it’s depends on the system architecture. If you program a real-time system I think that is better a custom solution. The question is: how much time (milliseconds, seconds… month… :-)) you have to wait for a response? I don’t think that there a unique yes/no response. As a programmer I say: it depends!

  11. Kyle Cordes says:

    A few answers for everyone above:

    * The Prolog implementation we used was http://www.swi-prolog.org/

    * I’m not aware of any Prolog implementations in .NET, other than the ones Matt mentioned.

    * I could have developed a rule engine; but a point of this post was the money and schedule saved by not doing so.

    * Of course the timing depends on the system needs. For this system, a few-minutes cycle time is amply good enough.

  12. Ed says:

    Thank you for your reply! indeed it is a rule engine, and yes it takes some time to what i want, but i am learning and i am refining it. I’ll try P# for .net as it sound as the right solution for me (infering an answer based on some rules and values stored in a database).
    Thanks!

  13. Stewart says:

    I found this article quite encouraging, in that I believe Prolog has a life outside of academia and so its great to see examples of situations where it has been successfully integrated into enterprise software.

    I don’t think Prolog is a language in which to code entire applications, but nevertheless in some circumstances its very useful at what it does – Logic Programming, particularly rules based decision making.

    The project I’m currently working on involves Prolog heavily as a back-end to carry out logical queries in a Service Oriented Architecture. The way I see it there’s many advantages to Prolog if you use it in the right circumstances: a well written piece of Prolog code can convey much more about its meaning than if the same logic were implemented in another language, and can be rapidly developed and modified as requirements change.