Logic.pm preview

Due to a request from several people, I am releasing a not-yet-CPAN-ready module called Logic.pm. The development of the idea to write this module is long and boring. But it’s my blog, not yours, so I’ll talk about it.

Many of the problems that I have been solving recently in programming have involved backtracking: rule matching, a simple-minded expert system, pattern matching in argument lists (the first and third are for Perl 6). So I decided to write a backtracking engine module that would help me out. Since I couldn’t find a good namespace to put it in, it was just going to be called Backtracker. I began that on saturday at about 1:00 pm, and finished at about 2:00 pm. You see, the backtracking algorithm is very simple in concept, and a module that implements it doesn’t buy you much. Essentially all a backtracker is is an object interface, plus two combinators: and and or.

Unsatisfied with my result, I decided that I was going to include a proof-of-concept implementation of my Argument Patterns proposal. In my prior art research, I downloaded gprolog, and started playing around. When I saw:

  | ?- append(X, Y, [1,2,3,4]).

  X = []
  Y = [1,2,3,4]

  X = [1]
  Y = [2,3,4]

  X = [1,2]
  Y = [3,4]

  X = [1,2,3]
  Y = [4]

  X = [1,2,3,4]
  Y = []

I was totally impressed. I decided that I must implement prolog unification in my engine. One hour and 135 lines of code later, I had finished Logic::Data::Unify. Wow. It’s amazing how simple and elegant the extremely powerful unification algorithm is.

Anyway, the status of the module: the logic subsystem works pretty well. It’s low on primitives, but those are pretty easy to write. There’s no syntax; you write everything out in essentially syntax-tree form (see examples/append.pl). There’s no documentation, but there are tests (and more than the one-test-for-every-ten-lines-of-code ratio that I like to maintain). The design is solid, but needs a little refactoring, as I’m seeing some limitations as far as custom backtracking control.

Here’s where I’m going: I have to implement some sort of global statefulness so you don’t have to pass that pesky $state object around. Then I’ll try to make some intuitive operator syntax based on overload (but that is a large challenge given the available operators). Maybe I’ll punt and make it look like lisp with the head moved out front. Then I plan to implement junctions using Logic, and finally multimethod dispatch. Then it’s CPAN time.


Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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