Using RegExp backtracking to implement Prolog? :-)

BerntB has asked for the wisdom of the Perl Monks concerning the following question:

This is probably really a Meditation. OK by me if it is moved there.

I saw this neat blog post on Planet Perl. I got to think about an idea.

Regular Expressions can be seen as unification.
Code is executed with (?{ }), depending on how far the unification has gone.
Backtracking in Regular Expressions could be used as Prolog backtracking.

Sounds like a good basis for implementing Prolog! Is there a simple way to compile unification/backtracking in a Prolog program to a Regular Expression?

I should write some code before asking, but I can't be the first (or the fiftieth) person to think of this. You could call other RE:s from the inserted code (the inserted code needs a functionality to fail).

I did search perlmonks and didn't find anything.

Comment on Using RegExp backtracking to implement Prolog? :-) Download Code

Replies are listed 'Best First'.
Re: Using RegExp backtracking to implement Prolog? :-) by diotalevi (Canon) on Oct 17, 2006 at 16:08 UTC
You probably want to know about Language::Prolog::Yaswi, DBD::Yaswi (both wrappers over SWI-Prolog) and AI::Prolog (a perl Prolog interpreter). ⠤⠤ ⠙⠊⠕⠞⠁⠇⠑⠧⠊	[reply]
Re: Using RegExp backtracking to implement Prolog? :-) by salva (Canon) on Oct 17, 2006 at 13:55 UTC
There is more than backtracking in a Prolog system. You need a logical database with facts and clauses, and being able to call predicates there (that btw, can be recursive). To make anything practical you also need arithmetic, tail recursion, the cut and being able to assert and retract clauses on the database.	[reply]
Re^2: Using RegExp backtracking to implement Prolog? :-) by BerntB (Deacon) on Oct 17, 2006 at 18:09 UTC
Each predicate is compiled down to a method which contains a RE. The subroutine returns true if it succeeds, false otherwise and a specific constant if it has run into a cut. Matched data etc is stored in the blessed object. For all predicates, there is a "master" method that dispatches calls to other predicates of the same name, depending on number of parameters. If a clause referenced a predicate, then code is inserted into the RE which calls the sub. Depending on the return value of the sub, the code fails/succeeds matching. At least, that was how far I have gotten in my planning. I don't know how to unsets unification when it do RE backtracking (there is no support for that in the `(?{ })` construct?). And I probably have missed other stuff. This idea probably reminds more than me about the idi.. uhm, heroes which implemented logical circuits in the game of Life. :-) Update: Please don't flame me if I got the vocabulary wrong; it was a long time ago I read Prolog. :-)	[reply] [d/l]
Re: Using RegExp backtracking to implement Prolog? :-) by Anonymous Monk on Oct 17, 2006 at 14:09 UTC
No, there's no simple way. It's certainly possible, but the few people who would find it a simple task wouldn't have to ask.	[reply]
Re^2: Using RegExp backtracking to implement Prolog? :-) by BerntB (Deacon) on Oct 17, 2006 at 18:12 UTC
Well, I ask, since I assume some of those halfgods hangs here.	[reply]