The joys of backtracking

I'm pleased to say that Parrotlog is now at a point where it can actually do stuff. It can call predicates and backtrack (more on that in a moment). Unification probably works as well.

Now, backtracking is tricky to get right. Currently Parrotlog has a problem with cuts. A cut is supposed to remove all choice points encountered after the currently executing predicate was invoked. Parrotlog's cut prunes all choice points since the invocation of the last predicate that matched successfully. Close, but no cigar.

Graham's CL implementation (that Parrotlog owes quite a bit to) solv…

Decoding HMMs in Perl 6

I've wanted to write a reasonably useful Perl 6 module for a while, and I finally realised that the Viterbi algorithm would be a pretty simple place to start (hopefully it'll be useful as well).

There's a module with the same name on CPAN, but I've based the code on a Common Lisp version I wrote for school a while back. At the moment the module is pretty basic, and doesn't support assigning probabilities to unseen data for example. The module is available on ="http://github.com/arnsholt/A…

Parrotlog - Parsing Prolog

For the syntax and semantics of Prolog, Parrotlog is based on a draft of the ISO/IEC Prolog standard (seeing how the actual standard costs muchos dineros).

Now, the good news are that the Prolog spec is actually an operator precedence grammar, which happens to be how NQP does its expression parsing as well. The bad news are that the spec uses term for everything, while NQP makes a distinction between terms (atomic expressions) and expressions (expressions, with or without operators). Th…

Parrotlog - Backtracking

Backtracking is probably the defining feature of Prolog. Abstractly, the execution of a Prolog program can be seen as traversing a tree, looking for a path that fits certain criteria. Each node represents a choice between several options, and are usually referred to as choice points (for reasons that should be obvious). If at any time the path taken is found to be inconsistent with the constraints, execution goes back to the previous choice point and tries the next option. The search is depth-first, left-to-right.

Now, as I've mentioned before, in Parrotlog this is implemented using c…

Parrotlog - Unification (again)

In the I went with the simple solution to the problem of unification. Variables point to other variables, and in the end a variable either points to a term, or nothing. What happens when you unify X with Y, Y with Z, and Z with X should probably not be considered just yet, and will probably have to be fixed at some point. But that should be reasonably simple. Finding cycles in a graph is after all a well-known problem.

This means that the core infrastructure I need should now be in place: unification, backtracking and cuts (a post on those last two is coming up). Now it's time to star…