Skip to content

Prolog as a Ruby DSL

Tuesday, 19 September 2006  |  richard dale

I just read Pat Eyler's blog Reading Ola Bini writing about some interesting discussions on Ruby metaprogramming and how it compared with Lisp macros for writing Domain Specific Languages. In one of the references Why Ruby is an acceptable LISP, amongst other things people discuss how to implement prolog as a DSL in Ruby or Lisp. A long time ago some of my 'hobby programming' projects were writing prolog interpreters in various languages; I started off with a Pascal one and added things to it, translated it into Modula-2, and I did a Object Oriented one in Objective-C. I've started translating the Objective-C one into Ruby, and it's quite fun seeing how the code compares in the two languages.

In the Objective-C prolog I didn't attempt to use the language as a DSL, I used lex and yacc to tokenise and parse the prolog code. That allowed me to do a pretty complete implementation, apart from the 'op' predicate which allows you to define new operators with precedences to implement DSLs in prolog (although they weren't called DSLs then). With Ruby I think the language is just about powerful enough to implement a simple prolog in Ruby itself. Here's my idea of what it could look like:

# Edinburgh Prolog: # # [consult('comp.pl'), write(comp), nl]. # # -[consult('comp.pl'), write(comp), nl] # # Edinburgh Prolog: # # female(mary). # likes(mary, wine). # likes(john, X) :- female(X), likes(Y, wine). # # female(mary) likes(mary, wine) likes(john, X) << [female(X), likes(X, wine)] # # Edinburgh Prolog: # # my_numbervars(F, I, N) :- # F =.. [_ | Args], # my_numbervars(Args, I, N). # my_numbervars(F, I, N) << [F === [_ | Args], my_numbervars(Args, I, N)]

The first form consists of a list of goals in square brackets, and it executed when the prolog code is parsed like class or module method calls in Ruby. It is usually used to read prolog sources from files into your running program. To implement that in Ruby, you can add a unary minus operator to the Array class like this:

# Parse code like '-[consult('comp.pl'), write(comp), nl]' class Array def -@() return SomePrologClass.new(self) end end Ruby will attempt to call each of the non-literal items in the list as methods, and so if there are actually no existing 'nl' or 'write(comp)' methods, they will be diverted to the catch-all method for trapping missing calls, 'method_missing'. As the list is defined outside any Ruby method definition, method_missing() will be called for the class containing the Array definition. So if we add a suitable method_missing() we can trap the calls and transform them into suitable prolog code. This is how Ruby itself can be used to tokenise and parse a DSL. # take 'id' as a missing method with its args, and return a version transformed into prolog code def self.method_missing(id, *args) end

The same method_missing() will also trap calls like 'female(mary)', but if we have 'female(X)', the logic variable as a missing constant X, will be diverted to another method, 'const_missing'. So we need to define that method to return a logic variable, as an instance of the 'NamedVariable' class:

# Look for logic variable such as X in 'female(X)' def self.const_missing(const, *args) return NamedVariable.new(const) end

A prolog clause consists of a head, followed by an 'if' operator and a sequence of goals. In Ruby the 'if' operator is a left shift, and the sequence of goals are in an Array. So we need to define left shift as an operator method which takes two arguments; the head of the clause, and the list of sub-goals. To make this work we need method_missing() to return a 'ListTerm' class that will build a clause from the two terms like this:

class ListTerm def <<(term) return Clause.new(self, term) end end # # To parse this, implement the '<<' operator in the ListTerm class, and # return the head of a Clause as a ListTerm: # # likes(john, X) << [female(X), likes(X, wine)] # def self.method_missing(id, *args) terms = *args case terms when Array # Iterate through the Array, and return each element as a prolog Term. else ListTerm.new(FunctionTerm.new(id), terms) end end

For other prolog operator methods, we just do something similar. In Ruby there is no '=..' operator to implement Univ, which converts a predicate into a list, and so I've chosen to map it onto '==='. A '|' operator is used to denote the head and tail of a list, and so that can be implemented as an operator method for prolog Terms too.

In prolog, anonymous logic variables are defined as underscores like 'female(_)', and these won't be Ruby constants like 'female(X)', but method calls that get diverted to method_missing(). So '_' methods need to be special cased as logic variable in method_missing():

# To parse this, implement '===' and '|' operator methods for prolog Terms, # and '_' as Anonymous variables # # my_numbervars(F, I, N) << # [F === [_ | Args], # my_numbervars(Args, I, N)] # class Term def ===(a) return UnivOp.new([self, a]) end
def |(a)
    return ListHeaddTail.new[self, a]

end end ... def self.method_missing(id, *args) ... if id == :_ return AnonymousVariable.new end end

So that's the basic idea, Ruby does the tokenising and passes a stream of tokens to method missing, which in turn returns prolog Term instances that implement operator methods to further parse and reduce the token stream to compiled prolog Clauses. The main difficulty with this approach is that there is no way to tell when one prolog clause ends and another starts. So I've come up with a hack to get round that - use the SCRIPT_LINES__ Array which contains the code for the Ruby source currently being parsed to have a look at whether the current line is the start of a new prolog clause, or a continuation of a previous clause. Yuck! But I haven't come up with anything better yet.

def self.method_missing(id, *args) filename = caller.first name, num = filename.split(":") # Do ugly things with SCRIPT_LINES__[name][num.to_i - 1] end

So that's the basics of how to parse prolog clauses, and the hard bit is how to run the code and 'Unify' the parsed clauses with a prolog query. However, that has translated quite easily from the working Objective-C code I have and so I'm pretty confident that once I can build the correct data structures the matching process shouldn't be too impossible to get working.. If anyone is interested in looking at the code so far, please email me and I can send it to you - it's a bit too early to actually release yet.