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…

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…

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…

I've finally hit the first real roadblock in the development: unification. Instantiating a free variable and unifying that with a term is simple enough (and works). The problem is when you start unifying free variables with each other. For example you have three free variables: X, Y, Z. You unify X with Y, and then Y with Z. Finally, unify Z with a term "foo". The value of X (and Y and Z, for that matter) should now be "foo". What stumps me is how to implement this in a sane way. I've looked at the AI::Logic and "Perl and Prolog and [...]" versions, but I haven't managed to duplicate them in…

The inspiration for this project is primarily due to my reading On Lisp by Paul Graham, which talks about implementing non-deterministic search (or backtracking, if you will) with continuations (chapter 2022). Since I know Parrot supports continuations natively, it was an obvious choice. Some googling also revealed a very interesting PerlMonks post, entitled Perl and Prolog and Continuations... oh my!, which it turns out is the inspiration for Ovid's…