27 Mar 2005 crhodes   » (Master)

OK, so what were the weasel words in my last entry about Norvig's Prolog implementation? Well, Prolog has a number of control constructs, which look like functors except that their semantics, in one important respect, are not as regular.

(Aside: in many ways, these control constructs of Prolog are similar to Lisp's concept of a special operator; neither Prolog nor Lisp provides for a way to extend the initial set of predefined magical constructs, but Lisp's macros provide sufficient control over evaluation semantics that things which look like special operators can be defined, while I'm pretty sure that unification in Prolog allows for similar implementation of new control constructs.)

Now, the issue with these special operators, and in particular the ->/2 and ->/2 ;/2 ‘if-then’ and ‘if-then-else’[*] control constructs have particular semantics in conjunction with the cut, !/0: the then and then-else portions of those operators are transparent to the cut, meaning that backtracking is inhibited from the predicate which is defined, rather than any notional -> predicate.

This means that any definition of -> as a predicate is doomed to fail. Norvig effectively defines if/2 (corresponding to ->/2 as

(<- (if ?test ?then) (call ?test) (call ?then))
which has the right semantics except when one of ?test or ?then contains a cut.

I have not yet fixed this is my local extension of Norvig's Prolog; I'm pretty sure I know how to do it (my experience of Lisp compiler technology is enough to tell me how to implement special forms; essentially, what needs to be done is to teach the compiler about if-then and if-then-else, and then implement call/1 by requiring it to compile a dummy uninterned predicate), but I've been occupied with parsing ISO prolog instead. One thing which is demotivating me from making this fix is the somewhat lamentable state of the test suites available for ISO Prolog: one from the committee and one from INRIA, neither of which tests any of the difficult cases from the standard. Now I realise how spoilt we in the Common Lisp community are by pfdietz and his test suite.

In case anyone is wondering what the cut is: passing a cut during the execution of a predicate prevents backtracking past that point: any attempt to backtrack will simply cause failure. For more details, see your nearest Prolog tutorial, because my limited experience prevents a good didactic presentation.

[*] these are in fact very bad names.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!