Pure regex implementation using rational trees and if_/3

[hurufu]

Rational trees (aka cyclic terms) are closely related to finite automata, and so are regular expressions. Here is a quick sketch of pure Prolog implementation of regexes:

:- use_module(library(lists)).
:- use_module(library(reif)).

run(R, L) :-
    example(R, P),
    length(L, _),
    regex(L, P).

% Currently you need to "compile" regex manually. Here are couple of examples:
example("c*(a|b)*", P1) :-
    P1 = sym(c, P1, P2),
    P2 = sym(a, P2, sym(b, P2, end)).
example("ab*c", P1) :-
    P1 = sym(a, P2, stp),
    P2 = sym(b, P2, P3),
    P3 = sym(c, end, stp).

% Actual regex implementation is 5 LoC!
regex([], end).
regex([], sym(_,_,Fail)) :-
    regex([], Fail).
regex([H|T], sym(X,Succ,Fail)) :-
    if_(H = X, regex(T, Succ), regex([H|T], Fail)).

What do you think? Is it a good approach to implement regular expressions?

[hurufu]

I think this is better then DCG, because with this very simple representation it would be possible to implement more interesting functionality: union and intersection of multiple regexes, conversion from NFA to DFA, visualization, maybe even finding the smallest regex that can describe a given string...

[UWN]

This can never be used together with

:- set_prolog_flag(occurs_check, true).

or

:- set_prolog_flag(occurs_check, error).

Also termination considerations are much more complex with rational trees since the natural numbers can no longer be used to model terms. Much more complex means, there are no termination inferencers/analyzers ready to use. A couple of papers, no more than that. Such "clever" implementations just limit the application area. Think of the current CHR implementation in SWI that uses also such infinite terms internally.

[hurufu]

Everything is more complex with cyclic terms, that's true. I'll take a look into that SWI module, thanks for a pointer.