Saturday, February 18, 2017

Diary: my day with a Prolog interpreter in Lisp

The subject: implementing a Prolog interpreter in Common Lisp, using an excellent - if rather old-fashioned - textbook as my guide. I had copied-and-pasted the code across (it never quite works first time) and was debating this morning: finally get Peter Norvig's code to run, or strike out in my own direction?

There's a lot in Chapter 11 of "Paradigms of Artificial Intelligence programming" to be wary of:
  • For efficiency reasons he stores the clauses on clause-head-predicate property lists
  • He uses destructive operations such as nconc
  • The resolution inference step and depth-first control strategy are interwoven.
I'd prefer to keep the clause database as an explicit object to be transformed and analysed throughout the proof. I'd also like to modularise the 'which clauses to try to resolve next' strategy, trying different things such as unit preference, set-of-support, hyperresolution. And it would be good to extract a proof tree, not just the final question-answering bindings.

All these things demand a rewrite.

But I was glad I persevered, because Peter Norvig's code finally came good this afternoon and I was able to successfully run it on a serious logic puzzle - the Zebra problem.

Where it ran remarkably quickly - forty times faster than in Dr Norvig's textbook-writing days. I was reminded of AI programming back in the late 1980s, when everything was slow and hard.

I imagined him developing his code on some ancient VAX 11/780 (as I used to do).

No comments:

Post a Comment

Comments are moderated. Keep it polite and no gratuitous links to your business website - we're not a billboard here.